Process Synchronization and Semaphores: race conditions, Peterson's solution, wait and signal

Process synchronization is where Operating Systems stops being descriptive and starts being logical, which is exactly why GATE weights it heavily. Aspirants who can trace a semaphore value through a sequence of wait and signal calls answer these questions with certainty. Those who memorise "semaphore is a variable" freeze the moment two processes interleave. Let us build the topic from the race condition up and finish with a worked semaphore trace.

The race condition

A race condition is when two or more processes access shared data concurrently and the final result depends on the exact order in which their operations interleave. Consider two processes both running count = count + 1 on a shared variable that starts at 5. That single line is really three machine steps: load count into a register, add one, store the register back.

If process A loads 5, then process B loads 5 before A stores, both compute 6, both store 6, and one increment is lost. The correct answer was 7. Nothing is broken in either process; the bug is the uncontrolled interleaving. Preventing exactly this is what synchronization is for.

The critical-section problem

The shared code that must not be interleaved is the critical section. A correct solution to the critical-section problem must satisfy three requirements:

• Mutual exclusion: at most one process is in its critical section at any time.

• Progress: if no process is in its critical section, one of the processes wanting to enter must be allowed to, and the decision cannot be postponed indefinitely by a process not interested in entering.

• Bounded waiting: there is a limit on how many times other processes can enter their critical sections after a process has requested entry and before it is granted, so no process starves.

Any synchronization mechanism is judged against these three, and examiners ask which one a flawed solution violates.

Peterson's solution

Peterson's solution is the classic software solution for two processes, and it satisfies all three requirements. It uses a shared boolean array flag[2] and a shared turn variable. For process i (with the other being j):

1. Set flag[i] = true (I want to enter).

2. Set turn = j (but I politely give the other the turn first).

3. Wait while flag[j] is true and turn == j.

4. Enter the critical section.

5. On exit, set flag[i] = false.

Mutual exclusion holds because a process enters only when the other has not raised its flag or has yielded the turn. It provides progress and bounded waiting because turn alternates, so neither process can loop forever while the other waits. Peterson's is beautiful for two processes but does not scale cleanly to many, which is why real systems use semaphores.

Semaphores: binary vs counting, wait and signal

A semaphore is an integer variable accessed only through two atomic operations, wait (also called P or down) and signal (also called V or up):

• wait(S): decrement S; if S becomes negative, block the calling process on S's queue.

• signal(S): increment S; if a process is blocked on S, wake one of them.

Because wait and signal are atomic, no race can occur inside them. Two flavours exist:

• Binary semaphore takes only 0 or 1 and acts as a lock (a mutex) for mutual exclusion.

• Counting semaphore takes any non-negative count and manages a pool of identical resources, such as five available printer slots.

[DIAGRAM: A counting semaphore as a box labelled S with a value and a waiting queue beside it, showing wait() decrementing S and pushing a blocked process onto the queue, and signal() incrementing S and popping one process off the queue.]

Producer-consumer and readers-writers

Two standard patterns show semaphores at work.

Producer-consumer uses a bounded buffer with three semaphores: mutex (binary, protects the buffer), empty (counting, counts free slots), and full (counting, counts filled slots). A producer does wait(empty), wait(mutex), add item, signal(mutex), signal(full). A consumer mirrors it with wait(full) and signal(empty). The counting semaphores block the producer on a full buffer and the consumer on an empty one, automatically.

Readers-writers allows many concurrent readers but gives a writer exclusive access. A mutex protects a reader count, and a write semaphore is held by the first reader in and released by the last reader out, so writers wait while any reader is active. These two patterns appear again and again in exams.

A worked semaphore trace

Take a counting semaphore S initialised to 2 (two identical resource units) and three processes P1, P2, P3, each calling wait(S) to acquire a unit, using the model where wait decrements first and blocks if the value goes negative.

1. S = 2 initially.

2. P1 calls wait(S): S becomes 1, not negative, so P1 proceeds.

3. P2 calls wait(S): S becomes 0, not negative, so P2 proceeds.

4. P3 calls wait(S): S becomes −1, negative, so P3 blocks. The magnitude 1 tells you exactly one process is waiting.

5. P1 finishes and calls signal(S): S becomes 0, and because a process is blocked, P3 is woken and proceeds.

The final value 0 means both remaining units are in use and no one is waiting. In the alternative model, where the value never goes negative and blocking happens when S is already 0, S would sit at 0 while P3 waits; either way, exactly two processes run at once and the third waits. Tracing this value change is the exact skill the exam tests.

How process synchronization is tested in GATE, NET and placements

GATE CS hands you a semaphore initialised to some value with an interleaving of wait and signal calls and asks for the final value, the maximum number of processes in the critical section, or whether a given solution deadlocks. It also asks which requirement (mutual exclusion, progress, bounded waiting) a flawed solution breaks. Work the full topic with solved traces on the Operating System learn module.

UGC NET Computer Science stays conceptual: define a race condition, state the three critical-section requirements, and distinguish binary from counting semaphores. Placement interviews ask you to solve producer-consumer or readers-writers with semaphores in code, and often connect synchronization to the memory hierarchy and virtual memory whose shared frames these very locks protect.

The short version

Start from the race condition: uncontrolled interleaving of shared data. The critical-section problem demands mutual exclusion, progress, and bounded waiting; Peterson's solution meets all three for two processes, and semaphores generalise it with atomic wait and signal. Trace a counting semaphore's value through a sequence by hand until it is automatic, and learn producer-consumer and readers-writers as templates. For a GATE-depth OS sequence with hundreds of solved synchronization problems, GATE Guidance by Sanchit Sir is built for it, and the GATE CS exam category covers the rest of the paper.