Question

When a special machine instruction is used to provide mutual exclusion in the fashion of Figure 5.2, there is no control over how long a process must wait before being granted access to its critical section. Devise an algorithm that uses the compare & swap instruction but that guarantees that any process waiting to enter its critical section will do so within n −1 turns, where n is the number of processes that may require access to the critical section and a “turn” is an event consisting of one process leaving the critical section and another process being granted access.

Answer 1

var j: 0..n-1;

key: boolean; while (true) {

 

 

waiting[i] = true; key := true;

 

 

while (waiting[i] && key)

 

 

key = (compare_and_swap(lock, 0, 1) == 0); waiting[i] = false;

 

 

j = i + 1 mod n;

 

 

while (j != i && !waiting[j]) j = j + 1 mod n; if (j == i) lock := false

 

 

else waiting = false;

 

 

 

 

 

}

 

 

 

The algorithm uses the common data structures var waiting: array [0..n - 1] of boolean

 

 

lock: boolean

 

 

 

These data structures are initialized to false. When a process leaves its critical section, it scans the array waiting in the cyclic ordering (i + 1, i + 2, ..., n - 1, 0, ..., i - 1). It designates the first process in this ordering that is in the entry section (waiting[j] = true) as the next one to enter the critical section. Any process waiting to enter its critical section will thus do so within n - 1 turns.

These data structures are initialized to false. When a process leaves its critical section, it scans the array waiting in the cyclic ordering (i + 1, i + 2, ..., n - 1, 0, ..., i - 1). It designates the first process in this ordering that is in the entry section (waiting[j] = true) as the next one to enter the critical section. Any process waiting to enter its critical section will thus do so within n - 1 turns.