Turn Variable in Process Synchronization
When you are dealing with two processes that need to share a resource, one of the simplest approaches is the turn variable. The idea is straightforward: a single variable decides whose turn it is to enter the critical section. No complex data structures, no kernel support needed, just a variable that flips between two values.
Why It Exists
Lock variables were one of the earlier attempts at solving the critical section problem, but they had a flaw. Under certain timing conditions, more than one process could read the lock variable as free and both enter the critical section at the same time. Mutual exclusion was not reliably guaranteed.
The turn variable came out of that problem as a cleaner alternative. Instead of checking whether a resource is free, processes just check whose turn it is. Only one value can be current at a time, so only one process gets in.
How It Works
The turn variable is initialized to either 0 or 1, which determines which process goes first.
If turn is set to 0, Process P0 runs first. P1 sits in a loop checking whether turn equals 1. Since it does not, P1 keeps waiting. If turn is set to 1, Process P1 goes first and P0 waits.
Entry and Exit Code
For Process P0:
while (turn != 0); // Wait until it's P0's turn
// --- Critical Section ---
// Access shared resource safely
turn = 1; // Hand the turn to P1
// --- Remainder Section ---For Process P1:
while (turn != 1); // Wait until it's P1's turn
// --- Critical Section ---
// Access shared resource safely
turn = 0; // Hand the turn back to P0
// --- Remainder Section ---Once a process finishes its critical section, it flips the turn variable to the other value, which unblocks the other process. They alternate like this indefinitely.
Initial: turn = 0
P0: turn == 0? YES -> P0 enters critical section
P1: turn == 1? NO -> P1 spins (busy wait)
... P0 finishes ...
P0: turn = 1 -> Hands off to P1
P1: turn == 1? YES -> P1 enters critical section
... P1 finishes ...
P1: turn = 0 -> Hands off to P0
(cycle repeats)A Working Example in C
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
int turn = 0; // Start with P0's turn
void* process0(void* arg) {
for (int i = 0; i < 5; i++) {
while (turn != 0); // Entry: wait for my turn
// --- Critical Section ---
printf("Process 0 in critical section (iteration %d)\n", i);
sleep(1);
printf("Process 0 leaving critical section (iteration %d)\n", i);
turn = 1; // Exit: give turn to P1
sleep(1); // Remainder section
}
return NULL;
}
void* process1(void* arg) {
for (int i = 0; i < 5; i++) {
while (turn != 1); // Entry: wait for my turn
// --- Critical Section ---
printf("Process 1 in critical section (iteration %d)\n", i);
sleep(1);
printf("Process 1 leaving critical section (iteration %d)\n", i);
turn = 0; // Exit: give turn back to P0
sleep(1); // Remainder section
}
return NULL;
}
int main() {
pthread_t t0, t1;
pthread_create(&t0, NULL, process0, NULL);
pthread_create(&t1, NULL, process1, NULL);
pthread_join(t0, NULL);
pthread_join(t1, NULL);
printf("Both processes completed.\n");
return 0;
}Output:
Process 0 in critical section (iteration 0)
Process 0 leaving critical section (iteration 0)
Process 1 in critical section (iteration 0)
Process 1 leaving critical section (iteration 0)
Process 0 in critical section (iteration 1)
Process 0 leaving critical section (iteration 1)
Process 1 in critical section (iteration 1)
...
Both processes completed.They alternate cleanly. P0 goes, flips the turn to 1, P1 goes, flips it back to 0, and so on.
What It Gets Right and Where It Stumbles
| Requirement | Satisfied? | Explanation |
|---|---|---|
| Mutual Exclusion | Yes | Only one value of turn can be active at a time. It is physically impossible for both processes to be in the critical section simultaneously. |
| Bounded Waiting | Yes | Each process gets its turn once the other finishes. No process can go twice in a row, so neither waits forever. |
| Deadlock Freedom | Yes | Once one process exits and updates turn, the other gets to go. No circular dependency exists. |
| Progress | No | Strict alternation is enforced. If P0 has nothing to do but P1 wants in, P1 is stuck waiting because turn has not been flipped. This is the lockstep problem. |
What It Cannot Do
- Only works for two processes. Extending it to three or more breaks the logic entirely. For multi-process scenarios, the Bakery Algorithm handles N processes using a ticket-based approach.
- Uses busy waiting (spinning). A process loops repeatedly checking the turn variable instead of sleeping and being woken up. This wastes CPU cycles, especially when the other process has a lot of work to do in its remainder section.
- Cannot be used in modern multi-core systems without memory barriers. The CPU might cache the turn variable locally and never see the update from the other core.
From Turn Variable to Peterson's Algorithm
Despite its limitations, the turn variable is still worth understanding. It is one of the earliest software synchronization ideas and forms the conceptual foundation for more complete solutions.
Peterson's Algorithm took the turn variable and added a flag array on top of it. The flag lets each process express intent ("I want to enter"), while the turn variable breaks ties when both want in. This combination fixes the progress problem because a process can enter without waiting for the other to go first, as long as the other is not interested.
| Aspect | Turn Variable Alone | Peterson's (Turn + Flags) |
|---|---|---|
| Mutual Exclusion | Yes | Yes |
| Progress | No (lockstep) | Yes |
| Bounded Waiting | Yes | Yes |
| Shared Variables | turn only | turn + flag[2] |
| Key Fix | N/A | Flags let a process enter without waiting for the other to go first |