Chapter 5.15 Operating Systems: Consider how to implement a mutex lock using an

Question

Chapter 5.15 Operating Systems:
Consider how to implement a mutex lock using an atomic hardware instruction. Assume that the following structure de?ning the mutex lockisavailable:
typedef struct{ int available; }lock;

(available == 0) indicates that the lock is available, and a value of 1 indicates that the lock is unavailable. Using this struct, illustrate how the following functions can be implemented using the test and set() and compare and swap() instructions: • void acquire(lock *mutex) • void release(lock *mutex) Be sure to include any initialization that may be necessary.
Exercises 245
do {while (true) { flag[i] = want in; j = turn; while (j != i) { if (flag[j] != idle) { j = turn; else j = (j + 1) % n; } flag[i] = in cs; j = 0;
while ( (j < n) && (j == i || flag[j] != in cs)) j++;
if ( (j >= n) && (turn == i || flag[turn] == idle)) break;
}
/* critical section */
j = (turn + 1) % n;
while (flag[j] == idle) j = (j + 1) % n;
turn = j; flag[i] = idle;
/* remainder section */ } while (true);

Explanation / Answer

Below is your answer: -

Test and Set :

typedef struct { int available; } lock;

void init(lock *mutex) {

// available=0 -> lock is available, available=1 -> lock is unavailabe

mutex->available = 0;

}

void acquire(lock *mutex) {
while (mutex->available == 1) // TEST the available
; // spin-wait (do nothing)
mutex->available = 1; // now SET it!
}

void release(lock *mutex) {
mutex->available = 0;
}

Compare and Swap:

int CompareAndSwap(int *ptr, int expected, int new) {
int actual = *ptr;
if (actual == expected)
*ptr = new;
return actual;
}

void lock(lock_t *lock) {
while (CompareAndSwap(&lock->flag, 0, 1) == 1)
; // spin
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.