Race condition; critical section approaches

Race condition and critical section problem

A race condition occurs when two or more processes access shared data and the result depends on the exact order of execution. The part of the program that accesses the shared data is the critical section (region). The critical section problem is to design a protocol so that when one process is executing in its critical section, no other process is allowed to execute in its critical section. A solution must satisfy:

1. mutual exclusion;
2. progress (a process outside the critical section must not block others);
3. bounded waiting (no starvation);
4. no assumptions about speed or number of CPUs.

Approaches to achieve mutual exclusion

1. Disabling interrupts: a process disables all interrupts just after entering its critical region and enables them before leaving. No clock interrupt means no preemption. Simple, but dangerous to give to user processes (they may never re-enable), and it does not work on multiprocessors.

2. Lock variable (software): while (lock != 0); lock = 1; ...critical...; lock = 0;. Fails: two processes can both see lock = 0 before either sets it, which is itself a race.

3. Strict alternation:

/* Process 0 */ while (TRUE) { while (turn != 0); critical_region(); turn = 1; noncritical(); }
/* Process 1 */ while (TRUE) { while (turn != 1); critical_region(); turn = 0; noncritical(); }

Ensures mutual exclusion by busy waiting (spin lock), but violates condition 2 (progress): a slow process outside its critical region can block the other.

4. Peterson's algorithm: software solution for two processes using turn and interested[] flags; satisfies all conditions using busy waiting.

void enter_region(int p) { int other = 1 - p;
    interested[p] = TRUE; turn = p;
    while (turn == p && interested[other] == TRUE); }
void leave_region(int p) { interested[p] = FALSE; }

5. Hardware: TSL / XCHG instruction: atomically reads and sets a lock word, so only one process gets the lock. Works for multiprocessors, but uses busy waiting.

enter_region: TSL REGISTER,LOCK ; CMP REGISTER,#0 ; JNE enter_region ; RET
leave_region: MOVE LOCK,#0 ; RET

6. Sleep and wakeup: instead of busy waiting, a blocked process sleeps. The producer-consumer problem with plain sleep/wakeup can lose a wakeup signal (race on the count variable).

7. Semaphores: integer variable with atomic down and up; mutex = 1 gives mutual exclusion: down(&mutex); critical(); up(&mutex); Blocked processes sleep, so no CPU is wasted.

8. Monitors: language construct in which only one process can be active inside the monitor; condition variables wait/signal are used for synchronization. Mutual exclusion is automatic.

9. Message passing: processes use send and receive; no shared variable is needed, so it also works in distributed systems.

Of these, 2, 3, 4, 5 use busy waiting; 6-9 block the waiting process. Semaphores and monitors are the practical choices for general use.