Process Synchronization in OS: Semaphores, Mutex

Processes and threads that share data are cooperating: a producer fills a buffer a consumer empties, two threads update one bank balance. Because the scheduler can interrupt either of them between any two machine instructions, their steps can interleave in ways the programmer never intended. Process synchronization is the set of rules and tools that make shared data come out right whatever the interleaving. Every tool below solves the same problem, the critical section problem, at a different level.

Race conditions

counter++ looks like one step, but the CPU runs it as three: load the value into a register, add one, store it back. Suppose counter is 5, thread T1 runs counter++ and thread T2 runs counter-- at the same time:

1. Each one-line statement is three instructions: load counter into a register, change the register, store it back. counter starts at 5, and the two threads run interleaved in the order on the bottom row.
2. Step 1: T1 loads counter (5) into r1.
3. Step 2: T1 changes only its own register: r1 = 6. counter in memory is still 5.
4. Step 3: T2 loads counter (5) into r2. T1 has not stored yet, so T2 reads the old value — this is where the update gets lost.
5. Step 4: T2 changes only its own register: r2 = 4. counter in memory is still 5.
6. Step 5: T1 stores r1: counter = 6.
7. Step 6: T2 stores r2: counter = 4, overwriting the 6 that T1 stored a moment ago.
8. One increment and one decrement should leave 5, but this run ends at 4. Of all 20 interleavings of the six instructions, 2 give 5, 9 give 4 and 9 give 6: the answer depends on timing.

The right answer is 5, but this interleaving gives 4, and swapping the last two stores gives 6. A race condition is exactly this: the outcome depends on the timing of concurrent accesses to shared data where at least one is a write. Races are hard to find because they rarely show: only 2 of the 20 possible interleavings here are right, but a thread is so seldom preempted inside those three instructions that almost every run takes one of those two.

The critical section problem

A critical section is the part of a program that accesses shared data. Each process loops through four parts: an entry section that asks permission, the critical section, an exit section that announces it has left, and the remainder section, everything else.

A correct solution to the critical section problem must satisfy three requirements:

1. Mutual exclusion. If one process is in its critical section, no other process is in its own.
2. Progress. If no process is in its critical section and some want to enter, only processes that are not in their remainder section take part in choosing the next one, and the choice cannot be postponed forever.
3. Bounded waiting. Once a process has asked to enter, there is a limit on how many times others may enter before it does. This rules out starvation.

No assumption may be made about the relative speed of the processes, only that each makes progress when it runs.

A tempting broken attempt uses one shared turn variable: process i enters only when turn == i and sets turn to the other on exit. It gives mutual exclusion but violates progress: the processes must strictly alternate, so if P0 wants to enter twice while P1 is busy elsewhere, P0 waits for nothing.

Peterson's solution

Peterson's algorithm solves the problem for two processes in software, with two shared variables: flag[i] says process i wants to enter, and turn says whose turn it is to give way.

int flag[2] = {0, 0};        /* flag[i] == 1: process i wants to enter */
int turn;                    /* who must give way if both want to enter */

void enter(int i) {          /* i is 0 or 1 */
    int j = 1 - i;
    flag[i] = 1;             /* I want to enter */
    turn = j;                /* but you go first if you want to as well */
    while (flag[j] && turn == j)
        ;                    /* busy wait */
}

void leave(int i) {
    flag[i] = 0;             /* I am out */
}

Here it is run with both processes competing:

1. P0 sets flag[0] = 1: it wants to enter.
2. P1 sets flag[1] = 1: it wants to enter.
3. P0 sets turn = 1, offering to let P1 go first.
4. P1 sets turn = 0, offering to let P0 go first. Both want in, and turn holds whichever value was written last — so exactly one of them will wait.
5. P0 tests: turn is 0, not 1, so it leaves the loop and enters its critical section.
6. P1 tests: flag[0] is 1 and turn is 0, so it spins in the while loop.
7. P0 leaves its critical section and sets flag[0] = 0.
8. P1 tests: flag[0] is 0, so it leaves the loop and enters its critical section. Each entered once and they were never inside together: whoever wrote turn last waited.

Why it satisfies all three requirements:

• Mutual exclusion. Pi passes its loop only if flag[j] is 0 or turn == i. If both were inside, both flags would be 1, so turn would have to equal both 0 and 1 at once.
• Progress. If Pj does not want to enter, flag[j] is 0 and Pi enters at once. If both want to, turn holds one value, so exactly one of them gets in.
• Bounded waiting. When Pj leaves and tries to enter again, it sets turn = i itself, so Pi waits for at most one entry by Pj.

Peterson's solution is the textbook proof that the problem can be solved in software, but it is not guaranteed to work on modern processors as written. CPUs and compilers may reorder independent loads and stores, so Pi could read flag[j] before its own write to flag[i] is visible. Real code needs memory barriers or the atomic instructions below.

Hardware support

Disabling interrupts around the critical section works on a single CPU, because nothing can preempt the running process. It fails on a multiprocessor, where another core keeps running, and it is far too dangerous to let user programs do.

Modern CPUs instead provide instructions that read and modify a memory word atomically, as one indivisible step.

Test-and-set sets a word to true and returns its old value:

/* the hardware executes this as one atomic step */
bool test_and_set(bool *target) {
    bool old = *target;
    *target = true;
    return old;
}

bool lock = false;
void acquire(void) { while (test_and_set(&lock)) ; }   /* spin until it was false */
void release(void) { lock = false; }

Compare-and-swap (CAS) writes a new value only if the word still holds the expected one, and returns what it held:

/* the hardware executes this as one atomic step */
int compare_and_swap(int *value, int expected, int new_value) {
    int old = *value;
    if (old == expected)
        *value = new_value;
    return old;
}

int lock = 0;
void acquire(void) { while (compare_and_swap(&lock, 0, 1) != 0) ; }
void release(void) { lock = 0; }

Both locks give mutual exclusion and progress but not bounded waiting: an unlucky process can keep losing the race. A version with a waiting[] array, where the leaving process hands the lock to the next waiter in cyclic order, adds bounded waiting. CAS is also the basis of atomic variables (std::atomic, Java's AtomicInteger) and lock-free data structures.

Mutex locks

A mutex (mutual exclusion lock) wraps all this in two calls: acquire() before the critical section and release() after it. Only the thread that acquired a mutex may release it.

A mutex that waits by looping is a spinlock. One that waits by putting the thread to sleep until the lock is released is a blocking (sleeping) mutex. Spinning wastes CPU but avoids two context switches, so kernels use spinlocks for critical sections only a few instructions long on multiprocessors, and sleeping locks for anything that might take longer.

Semaphores

A semaphore S, introduced by Dijkstra, is an integer accessed only through two atomic operations: wait (P, from the Dutch proberen, to test) and signal (V, verhogen, to increment). The simplest definition busy-waits:

wait(S):   while (S <= 0) ;  // busy wait
           S--
signal(S): S++

Real implementations block instead, keeping a queue of waiting processes. The value may then go negative, and its magnitude is the number of processes waiting:

wait(S):   S.value--
           if (S.value < 0) { add this process to S.queue; block() }
signal(S): S.value++
           if (S.value <= 0) { remove a process P from S.queue; wakeup(P) }

There are two kinds:

• A binary semaphore takes only 0 and 1 and is used like a lock: initialize it to 1, wait before the critical section and signal after it.
• A counting semaphore is initialized to the number of identical resources.

Worked trace: a counting semaphore for two printers starts at 2, and processes A, B, C and D each call wait, then A and B finish and call signal. The value ends at 0, with C and D printing and nobody waiting.

1. Two printers, so the semaphore starts at 2. Four processes will each call wait() before printing and signal() when they finish.
2. A calls wait(): the value drops to 1, not below zero, so A goes ahead and takes a printer.
3. B calls wait(): the value drops to 0, not below zero, so B goes ahead and takes a printer.
4. C calls wait(): the value drops to −1, below zero, so C joins the queue and blocks. −1 means one process is waiting.
5. D calls wait(): the value drops to −2, below zero, so D joins the queue and blocks. −2 means two processes are waiting.
6. A calls signal(): the value rises to −1, still not positive, so the first waiter, C, wakes and takes the printer A freed.
7. B calls signal(): the value rises to 0, still not positive, so the first waiter, D, wakes and takes the printer B freed. The value is back to 0: both printers busy, nobody waiting.

Semaphores also impose ordering. To make statement S2 in P2 run only after S1 in P1, share a semaphore synch initialized to 0: P1 runs S1 then signal(synch); P2 runs wait(synch) then S2.

Semaphores are powerful but easy to misuse. Swapping wait and signal breaks mutual exclusion, writing wait twice deadlocks, and forgetting one breaks everything. Two processes doing wait(S); wait(Q) and wait(Q); wait(S) can deadlock, each holding one semaphore and waiting for the other.

Monitors

A monitor is a language construct that groups shared data with the procedures that operate on it, and guarantees that only one process is active inside the monitor at a time. The compiler inserts the locking, so the programmer cannot forget it.

For waiting on a condition, a monitor has condition variables. x.wait() suspends the caller and releases the monitor; x.signal() resumes one process waiting on x, and does nothing if none is waiting. That is the key difference from a semaphore's signal, which is remembered in the count.

monitor Account {
    int balance = 0
    condition funds

    procedure deposit(amount) {
        balance = balance + amount
        funds.signal()
    }
    procedure withdraw(amount) {
        while (balance < amount)
            funds.wait()         // releases the monitor while waiting
        balance = balance - amount
    }
}

After signal, either the signaller waits and the woken process runs at once (Hoare semantics, signal-and-wait) or the signaller continues and the woken process runs later (Mesa semantics, signal-and-continue). Most real systems, including Java and pthreads, use Mesa semantics, which is why the condition is rechecked in a while loop rather than an if. In Java, every object is a monitor: synchronized methods give the mutual exclusion, and wait(), notify() and notifyAll() act as one condition variable.

Busy waiting vs blocking

Mutex vs semaphore

A related trap is priority inversion: a low-priority process holds a lock a high-priority process needs, and a medium-priority process preempts the low one, so the high-priority process waits on the medium one. The fix is priority inheritance: the lock holder temporarily runs at the priority of the highest process waiting for it.

1. L takes the lock at 1. H arrives at 2, needs the lock and blocks. M arrives at 3 and, outranking L, runs for 4 units while L still holds the lock — so H, the most urgent task, waits on M and finishes only at 10.
2. With priority inheritance, L runs at H's priority while H waits for its lock, so M cannot preempt it. L finishes its critical section at 4, H takes the lock and finishes at 6, and M runs after.

A priority inversion famously reset the Mars Pathfinder lander's computer in 1997 until engineers enabled priority inheritance remotely.

Common mistakes

• Thinking count++ is atomic because it is one line of code. It is a load, an add and a store.
• Listing the three requirements as "mutual exclusion, no deadlock, no starvation". The standard names are mutual exclusion, progress and bounded waiting.
• Saying a condition variable's signal works like a semaphore's. A condition signal with no waiter is lost; a semaphore signal is counted.
• Using if instead of while around a condition wait under Mesa semantics, so a woken thread acts on a condition that is no longer true.
• Claiming Peterson's algorithm works unchanged on modern multicore CPUs. Without memory barriers, reordering can break it.
• Treating a binary semaphore and a mutex as identical. The mutex has an owner; the semaphore does not.

Interview questions

What is the critical section problem? Designing a protocol so that when processes share data, at most one is executing code that accesses it at any time. A solution must give mutual exclusion, progress and bounded waiting, without assuming anything about relative process speeds.

Explain Peterson's solution. Each of the two processes sets its own flag to say it wants to enter, then sets turn to the other process, and waits while the other wants to enter and it is the other's turn. Whoever wrote turn last waits, so exactly one enters, and each waits for at most one entry by the other.

What does wait() do on a semaphore whose value is 0? In the blocking implementation the value becomes −1, the caller is added to the semaphore's queue and blocked. It stays blocked until another process calls signal(), which increments the value and wakes one waiting process.

Why can disabling interrupts not be used for mutual exclusion on a multiprocessor? Disabling interrupts only stops preemption on the CPU that did it. Other cores continue to run and can enter the critical section, and disabling interrupts on every core is slow and unsafe.

What is a spinlock, and when is it preferred? A lock whose waiters loop testing it instead of sleeping. It is preferred when critical sections are very short and the system has several cores, because spinning briefly costs less than two context switches.

What is the difference between a monitor and a semaphore? A semaphore is a low-level counter the programmer must call correctly everywhere. A monitor is a language construct where mutual exclusion is automatic, with condition variables for waiting, which makes misuse much harder.

What is priority inversion and how is it solved? A high-priority process waits for a lock held by a low-priority process, which in turn is preempted by medium-priority work, so the high-priority process is effectively delayed by lower ones. Priority inheritance raises the lock holder to the waiter's priority until it releases the lock.

Next, read Classic Synchronization Problems, or test yourself with the Operating Systems (Intermediate) skill test.