CSS Optional — Paper-II, Section-A · P-II.III.III
A race condition occurs when two or more processes/threads access and manipulate shared data concurrently, and the final outcome depends on the unpredictable order in which their instructions happen to be interleaved by the scheduler — producing incorrect or inconsistent results.
Classic example: two processes both executing counter = counter + 1 can, if interleaved at the machine-instruction level, both read the same old value and each write back the same incremented value — one increment is silently lost.
The segment of code where a process accesses shared data is its critical section. Any valid solution must satisfy three requirements:
| Mechanism | How it works | Main weakness |
|---|---|---|
| Disabling interrupts | CPU can't be preempted while in the critical section | Only works on single-processor systems; dangerous if not re-enabled; inefficient |
| Strict alternation (turn variable) | Processes take turns via a shared "turn" flag | Forces waiting even when the other process doesn't want to enter (violates Progress) |
| Peterson's Algorithm | Software-only: a "turn" variable + per-process "interested" flags | Correct, but relies on busy-waiting (spinning); only for 2 processes in its classic form |
| Hardware atomic instructions | Test-and-Set (TSL) / Compare-and-Swap — atomic read-modify-write guaranteed uninterruptible by hardware | Still busy-waiting (spinlocks) — wastes CPU cycles |
| Semaphores | OS-provided integer variable, accessed only via atomic wait()/signal(); blocks (sleeps) a waiting process instead of spinning |
Easy to misuse — a forgotten wait/signal causes deadlock or violates mutual exclusion |
| Monitors | High-level language construct that bundles shared data with automatic mutual exclusion + condition variables | Needs language/runtime support; programmer still designs condition-variable logic correctly |
Semaphores in detail: a semaphore S is an integer manipulated only through two atomic operations — wait(S) (a.k.a. P): decrement S, block if S < 0; and signal(S) (a.k.a. V): increment S, wake a waiting process if any. A binary semaphore (0 or 1) gives plain mutual exclusion (equivalent to a mutex); a counting semaphore tracks how many units of a resource are available (used for producer-consumer below). If a semaphore's value is negative, its magnitude equals the number of processes currently blocked waiting on it — a frequently tested MCQ fact.
A producer generates items into a fixed-size shared buffer; a consumer removes them. Without synchronization: the producer could overwrite an unread slot, or the consumer could read from an empty buffer — both are race conditions.
Standard solution — one mutex + two counting semaphores:
semaphore mutex = 1; // mutual exclusion on the buffer itself
semaphore empty = N; // N = buffer size; counts empty slots
semaphore full = 0; // counts filled slots
// Producer // Consumer
do { do {
produce an item; wait(full); // wait for a filled slot
wait(empty); // wait for space wait(mutex);
wait(mutex); remove item from buffer;
place item in buffer; signal(mutex);
signal(mutex); signal(empty); // freed a slot
signal(full); // one more item consume item;
} while(true); } while(true);
Note the order matters: the producer waits on empty (space) before mutex (exclusive access) — waiting on mutex first while the buffer is full would deadlock, since the consumer could never get mutex to free a slot.
Multiple processes share a data store; readers only read (many can proceed concurrently with no conflict), writers modify it (a writer needs exclusive access — no reader or other writer may touch the data simultaneously).
First (Readers-Preference) solution sketch: use a counter readcount (protected by a mutex) and a semaphore wrt guarding the resource itself.