Turn Variable and Strict Alternation for Mutual Exclusion: Simple Concurrency Control

Understand simple software-based mechanisms for achieving mutual exclusion: the turn variable and strict alternation approaches. This tutorial explains their algorithms, limitations (only two processes, busy-waiting), and how they ensure that only one process accesses a shared resource (critical section) at a time.

Turn Variable and Strict Alternation Approach for Mutual Exclusion

Addressing Mutual Exclusion with a Turn Variable

The turn variable approach is a software-based mechanism for achieving mutual exclusion—ensuring that only one process can access a shared resource (critical section) at a time. This approach is relatively simple to implement but is limited to only two processes and is a busy-waiting solution. A shared variable, the "turn variable," acts as a lock, determining which process is allowed to enter the critical section. This simple approach suffers from several limitations, particularly involving fairness and efficiency.

The Turn Variable Algorithm

Let's consider two processes, P_i and P_j. They share a variable called turn. The algorithm is:

// Non-critical section
while (turn != i); // Busy-wait until turn is i
// Critical Section
turn = j; // Give turn to Pj
// Non-critical section

// Non-critical section
while (turn != j); // Busy-wait until turn is j
// Critical Section
turn = i; // Give turn to Pi
// Non-critical section

The turn variable can be either i or j. A process enters the critical section only when the turn variable matches its ID.

Addressing Limitations of Simple Lock Variable Approaches

The simple lock variable approach (setting a lock to 1 to indicate the critical section is in use) doesn't guarantee mutual exclusion because multiple processes might see the lock as 0 simultaneously. The turn variable approach avoids this; only the process whose ID matches the turn variable can enter.

Analysis of Strict Alternation (Based on Concurrency Requirements)

Mutual Exclusion

Strict alternation (using the turn variable) guarantees mutual exclusion for only two processes because only one process can enter the critical section at a time. The code ensures that the turn variable is updated, preventing simultaneous access.

Progress

Progress is *not* guaranteed. If a process doesn't want to enter the critical section on its turn, the other process is blocked indefinitely.

Bounded Waiting

Bounded waiting is also *not* guaranteed. There is no limit on how long a process might have to wait.

Portability

The turn variable solution is portable since it's a pure software mechanism, requiring no special hardware instructions.