Think about the key to a single-room office cabin. Whoever holds the key can go in; everyone else waits until the key comes back. That is a mutex lock.
Now think about the token counter at a parking lot with 50 spaces. The board shows how many spaces are free. Each car that enters reduces the number, each car that leaves increases it, and when it shows 0, new cars wait at the gate. That is a semaphore.
In Critical Section Problem & Peterson's Solution we learned the rules for a correct critical section and saw the hardware instructions (test-and-set, compare-and-swap) that make it possible. Writing those loops by hand every time is error-prone, so operating systems and libraries wrap them in two simple tools: mutex locks and semaphores. These are what you actually use in real programs, and they are among the most asked topics in OS interviews and GATE.
Mutex Locks
A mutex lock (short for mutual exclusion lock) is a synchronization tool with two operations,
acquire()andrelease(). A thread must acquire the lock before entering its critical section and release it when it leaves. Only one thread can hold the lock at a time.
Conceptually, a mutex is a boolean available:
acquire() {
while (!available)
; /* wait */
available = false;
}
release() {
available = true;
}The check and the set inside acquire() must happen atomically, otherwise we are back to the broken "lock variable" from the previous chapter. In practice, acquire() is built on test-and-set or compare-and-swap.
Using a lock always follows the same pattern:
acquire(lock);
/* critical section */
release(lock);
/* remainder section */Fixing our counter with a POSIX mutex
Here is the counter++ program from Process Synchronization & Race Conditions, which lost almost half of its updates, now protected by a pthread_mutex_t:
#include <stdio.h>
#include <pthread.h>
#define N 1000000
long counter = 0;
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
void *work(void *arg)
{
(void)arg;
for (int i = 0; i < N; i++) {
pthread_mutex_lock(&lock); /* acquire() */
counter++; /* critical section */
pthread_mutex_unlock(&lock); /* release() */
}
return NULL;
}
int main(void)
{
pthread_t t1, t2;
pthread_create(&t1, NULL, work, NULL);
pthread_create(&t2, NULL, work, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("Expected: %d\n", 2 * N);
printf("Actual : %ld\n", counter);
return 0;
}$ gcc -std=c17 -Wall -pthread mutex_counter.c -o mutex_counter
$ ./mutex_counter
Expected: 2000000
Actual : 2000000Correct, every time. The lock makes the three-step load-add-store happen as one unit from the point of view of the other thread.
Fixing the bank example
The check-then-act bug needs the check and the update inside the same lock. Locking only the update would not help, because both threads could still pass the check first.
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
int balance = 1000;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
void *withdraw(void *arg)
{
int amount = *(int *)arg;
pthread_mutex_lock(&m); /* check AND act under one lock */
if (balance >= amount) {
sleep(1);
balance = balance - amount;
printf("Withdrew %d\n", amount);
} else {
printf("Insufficient funds for %d\n", amount);
}
pthread_mutex_unlock(&m); /* unlock on EVERY path */
return NULL;
}
int main(void)
{
pthread_t a, b;
int amt = 800;
pthread_create(&a, NULL, withdraw, &amt);
pthread_create(&b, NULL, withdraw, &amt);
pthread_join(a, NULL);
pthread_join(b, NULL);
printf("Final balance: %d\n", balance);
return 0;
}$ gcc -std=c17 -Wall -pthread bank_fixed.c -o bank_fixed
$ ./bank_fixed
Withdrew 800
Insufficient funds for 800
Final balance: 200Now exactly one withdrawal succeeds. Notice that pthread_mutex_unlock runs on both branches of the if. Forgetting to unlock on some path (for example, an early return on error) leaves the lock held forever and every other thread hangs.
Spinlocks vs Blocking (Sleeping) Locks
What should a thread do while it waits for a lock? There are two options.
Spinlock: keep trying
A spinlock waits by looping ("spinning") until the lock becomes free. This is busy waiting. Here is a working spinlock built on C11's atomic_flag, which compiles down to a hardware test-and-set:
#include <stdio.h>
#include <stdatomic.h>
#include <pthread.h>
#define N 1000000
atomic_flag lock = ATOMIC_FLAG_INIT; /* clear = unlocked */
long counter = 0;
void acquire(void)
{
/* test_and_set: set the flag, return its OLD value, atomically */
while (atomic_flag_test_and_set(&lock))
; /* someone else holds it: spin */
}
void release(void)
{
atomic_flag_clear(&lock);
}
void *work(void *arg)
{
(void)arg;
for (int i = 0; i < N; i++) {
acquire();
counter++;
release();
}
return NULL;
}
int main(void)
{
pthread_t t1, t2;
pthread_create(&t1, NULL, work, NULL);
pthread_create(&t2, NULL, work, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("Expected: %d, Actual: %ld\n", 2 * N, counter);
return 0;
}$ gcc -std=c17 -Wall -pthread spinlock.c -o spinlock
$ ./spinlock
Expected: 2000000, Actual: 2000000Blocking lock: go to sleep
A blocking (sleeping) lock puts the waiting thread into the waiting state (see Processes & Process States) and lets the scheduler run something else. When the lock is released, the OS wakes one waiter and moves it to the ready queue.
Spinlock | Blocking lock | |
|---|---|---|
While waiting | Loops on the CPU (busy waiting) | Sleeps; CPU is free for other work |
Cost of waiting | Wastes CPU cycles | Two context switches (sleep + wake up) |
Best when | Lock is held for a very short time and there are multiple cores | Lock may be held for a long time, or there is only one core |
On a single core | Bad: the holder cannot run while the waiter spins, so the waiter just burns its whole time slice | Fine |
Typical users | OS kernels (for example, the Linux kernel's | Application programs |
The rule of thumb: if the lock will be held for less time than two context switches would take, spinning is cheaper; otherwise, sleep.
Real implementations combine both. On Linux, pthread_mutex_lock is built on the futex ("fast user-space mutex") system call. If the lock is free, it is taken with a single atomic instruction entirely in user space, with no system call at all. Only when there is contention does the thread call into the kernel to sleep. So an uncontended mutex is extremely cheap.
Semaphores
A mutex answers one question: "is it free or taken?". Many problems need more: "how many are free?" or "has that other thread finished yet?". For these we use a semaphore, introduced by Edsger Dijkstra in the 1960s.
A semaphore S is an integer variable that, apart from initialisation, is accessed only through two atomic operations:
wait()andsignal().
The simplest definition (with busy waiting):
wait(S) { /* also called P(S), down(S) */
while (S <= 0)
; /* wait until positive */
S--;
}
signal(S) { /* also called V(S), up(S) */
S++;
}The names P and V come from Dijkstra's Dutch words, usually given as proberen ("to test") and verhogen ("to increment"). In POSIX they are sem_wait() and sem_post().
The key idea: wait takes one unit (and blocks if there are none), signal gives one unit back. The value tells you how many units are currently available.
Counting and binary semaphores
Counting semaphore – the value can range over any non-negative integer. Used to manage a resource with several identical instances (printers, database connections, buffer slots).
Binary semaphore – the value is only 0 or 1. It behaves like a mutex lock and is used for mutual exclusion.
Three Ways to Use a Semaphore
1. Mutual exclusion (initial value 1)
semaphore mutex = 1;
wait(mutex);
/* critical section */
signal(mutex);The first process takes the value from 1 to 0 and enters. Others find 0 and wait. When the first leaves, signal makes it 1 again and one waiter can go in.
2. Ordering (initial value 0)
Suppose statement S1 in thread T1 must run before statement S2 in thread T2. Use a semaphore that starts at 0:
semaphore done = 0;
/* T1 */ /* T2 */
S1; wait(done);
signal(done); S2;If T2 arrives first, it finds 0 and blocks. It can only continue after T1 runs S1 and calls signal. Here it is in C, where we deliberately start the "server" thread first and make the "loader" slow:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
sem_t done; /* starts at 0 */
void *loader(void *arg)
{
(void)arg;
sleep(1); /* loading takes time */
printf("S1: config loaded\n");
sem_post(&done); /* signal(done) */
return NULL;
}
void *server(void *arg)
{
(void)arg;
sem_wait(&done); /* wait(done): blocks until S1 has finished */
printf("S2: server started using config\n");
return NULL;
}
int main(void)
{
pthread_t a, b;
sem_init(&done, 0, 0); /* 0 = shared between threads, initial value 0 */
pthread_create(&b, NULL, server, NULL); /* server created FIRST on purpose */
pthread_create(&a, NULL, loader, NULL);
pthread_join(a, NULL);
pthread_join(b, NULL);
sem_destroy(&done);
return 0;
}$ gcc -std=c17 -Wall -pthread sem_order.c -o sem_order
$ ./sem_order
S1: config loaded
S2: server started using configEven though the server thread starts first, S2 always prints after S1.
The same trick chains: to force three threads to print in the order C, A, B no matter how they are scheduled, use two semaphores that start at 0:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
sem_t sA, sB; /* both start at 0 */
void *ta(void *x) { (void)x; sem_wait(&sA); printf("A\n"); sem_post(&sB); return NULL; }
void *tb(void *x) { (void)x; sem_wait(&sB); printf("B\n"); return NULL; }
void *tc(void *x) { (void)x; printf("C\n"); sem_post(&sA); return NULL; }
int main(void)
{
pthread_t a, b, c;
sem_init(&sA, 0, 0);
sem_init(&sB, 0, 0);
pthread_create(&a, NULL, ta, NULL); /* start them in the "wrong" order */
pthread_create(&b, NULL, tb, NULL);
pthread_create(&c, NULL, tc, NULL);
pthread_join(a, NULL); pthread_join(b, NULL); pthread_join(c, NULL);
return 0;
}$ gcc -std=c17 -Wall -pthread abc.c -o abc
$ ./abc
C
A
B
$ ./abc
C
A
B
$ ./abc
C
A
B3. Counting resources (initial value n)
Our parking lot has 3 slots and 6 cars. The semaphore starts at 3:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#define CARS 6
#define SLOTS 3
sem_t slots; /* counting semaphore: number of free slots */
sem_t lock; /* binary semaphore protecting 'inside' */
int inside = 0; /* only for printing */
void *car(void *arg)
{
int id = *(int *)arg;
sem_wait(&slots); /* take a slot; blocks if all 3 are taken */
sem_wait(&lock);
inside++;
printf("Car %d parked (cars inside: %d)\n", id, inside);
sem_post(&lock);
sleep(1); /* stay parked for a while */
sem_wait(&lock);
inside--;
printf("Car %d left (cars inside: %d)\n", id, inside);
sem_post(&lock);
sem_post(&slots); /* give the slot back */
return NULL;
}
int main(void)
{
pthread_t t[CARS];
int id[CARS];
sem_init(&slots, 0, SLOTS);
sem_init(&lock, 0, 1);
for (int i = 0; i < CARS; i++) {
id[i] = i + 1;
pthread_create(&t[i], NULL, car, &id[i]);
}
for (int i = 0; i < CARS; i++)
pthread_join(t[i], NULL);
return 0;
}One run (the order differs from run to run, because the scheduler decides which waiting car goes next):
$ gcc -std=c17 -Wall -pthread parking.c -o parking
$ ./parking
Car 1 parked (cars inside: 1)
Car 2 parked (cars inside: 2)
Car 3 parked (cars inside: 3)
Car 1 left (cars inside: 2)
Car 2 left (cars inside: 1)
Car 4 parked (cars inside: 2)
Car 5 parked (cars inside: 3)
Car 3 left (cars inside: 2)
Car 6 parked (cars inside: 3)
Car 4 left (cars inside: 2)
Car 5 left (cars inside: 1)
Car 6 left (cars inside: 0)Whatever the order, the "cars inside" count never goes above 3. The first three cars to reach sem_wait get in immediately (usually cars 1, 2 and 3, but not always, since thread start order is also up to the scheduler); the other three block inside sem_wait until someone leaves. The program also uses a second, binary semaphore lock to protect the shared inside counter, which shows both uses side by side.
Implementing Semaphores Without Busy Waiting
The while (S <= 0); loop in the simple definition wastes CPU. Real semaphores block the process instead. Each semaphore gets a list of waiting processes:
typedef struct {
int value;
struct process *list; /* queue of processes waiting on this semaphore */
} semaphore;
void wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
block(); /* move to waiting state, run someone else */
}
}
void signal(semaphore *S) {
S->value++;
if (S->value <= 0) { /* somebody is waiting */
remove a process P from S->list;
wakeup(P); /* move P to the ready queue */
}
}In this version the value can go negative, and when it does, its magnitude tells you how many processes are waiting. Here is a trace for a semaphore starting at 2 with four processes (computed with a small simulation):
Operation | S.value after | Waiting list | What happens |
|---|---|---|---|
P1: wait(S) | 1 | empty | P1 enters |
P2: wait(S) | 0 | empty | P2 enters |
P3: wait(S) | −1 | P3 | P3 blocks |
P4: wait(S) | −2 | P3, P4 | P4 blocks |
P1: signal(S) | −1 | P4 | wakes P3 |
P2: signal(S) | 0 | empty | wakes P4 |
P3: signal(S) | 1 | empty | nobody waiting |
P4: signal(S) | 2 | empty | nobody waiting |
At value −2 there were exactly 2 processes waiting. When a process is woken, it does not decrement again; its earlier decrement already "reserved" the unit.
One subtle point: wait and signal themselves touch shared data (value and list), so they must be critical sections too! The OS protects them with a spinlock (on multicore) or by briefly disabling interrupts (on a single core). So busy waiting has not disappeared completely, but it has moved from the application's critical section (which may be long) to the few instructions inside wait/signal (which are very short).
The fairness of a semaphore depends on how the waiting list is managed. A FIFO queue guarantees bounded waiting; a LIFO stack can starve a process that has been waiting for a long time.
POSIX Semaphore API (Linux)
Function | Meaning |
|---|---|
| Create an unnamed semaphore with an initial value. |
| wait / P: decrement, blocking while the value is 0 |
| Like |
| signal / V: increment, waking a waiter if any |
| Read the current value (only a snapshot; it may change immediately) |
| Destroy an unnamed semaphore |
| Create or open a named semaphore that unrelated processes can share by name |
Note that POSIX semaphore values never go below 0 from the programmer's point of view; the "negative value" is the textbook implementation idea above. Also, unnamed semaphores (sem_init) are not supported on macOS, so run these examples on Linux or WSL.
Solved Problems (GATE Style)
Problem 1
A counting semaphore S is initialised to 10. Then 6 P operations and 4 V operations are performed. What is the final value of S?
Answer: each P subtracts 1, each V adds 1: 10 − 6 + 4 = 8.
Problem 2
S is initialised to 7. Then 20 P operations and 15 V operations are performed, in some order. What is the final value, assuming the textbook (negative-allowed) implementation?
Answer: 7 − 20 + 15 = 2. The order does not change the final value, only who blocks along the way.
Problem 3
A semaphore S has value −3. What does that mean?
Answer: no units are available and 3 processes are blocked on S. Three signal operations are needed before the value becomes 0, and a fourth would make it 1.
Problem 4
A semaphore used for mutual exclusion is accidentally initialised to 3 instead of 1. What happens?
Answer: up to 3 processes can be in the critical section at the same time, so mutual exclusion is broken. The initial value of a semaphore = how many processes can pass wait without blocking.
Problems With Semaphores
Deadlock
Two processes, two semaphores both initialised to 1, taken in opposite orders:
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
... ...
signal(S); signal(Q);
signal(Q); signal(S);If P0 takes S and P1 takes Q before either reaches its second wait, each waits forever for the other. This is a deadlock; it gets its own chapter, Deadlocks. The simple fix here: make every process take the semaphores in the same order.
Starvation
If waiters are removed from the list in LIFO order or by some unfair rule, one process may wait indefinitely while others keep getting through.
Priority inversion
Imagine three processes with priorities L < M < H. L holds a lock; H wants it and blocks. Now M, which does not need the lock at all, becomes ready and preempts L (it has higher priority than L). L cannot run, so it cannot release the lock, so H keeps waiting for M, a lower-priority process. The priorities are effectively inverted.
L: takes lock ─── preempted by M ───────────────── (finally runs) releases lock
H: wants lock → BLOCKED .................................... runs
M: runs, runs, runs ... (does not need the lock)This really happened on NASA's Mars Pathfinder lander in 1997: a high-priority task was blocked behind a low-priority one holding a shared lock while medium-priority tasks ran, a watchdog timer noticed the high-priority task had not finished, and the computer kept resetting. Engineers fixed it from Earth by turning on priority inheritance:
Priority inheritance: while a low-priority process holds a lock that a higher-priority process is waiting for, it temporarily inherits the higher priority. When it releases the lock, its priority goes back to normal.
With inheritance, L runs at H's priority, M cannot preempt it, L finishes quickly and releases the lock, and H proceeds. POSIX offers this through pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT).
Simple programming errors
Semaphores are powerful but low-level. One wrong line breaks everything, and the bug may appear only under rare timing:
signal(mutex); ... critical section ... wait(mutex);(order swapped) → several processes in the CS together.wait(mutex); ... critical section ... wait(mutex);(secondwaitinstead ofsignal) → the process blocks itself forever.Forgetting
wait→ no mutual exclusion. Forgettingsignal→ everyone else blocks forever.
These dangers are the motivation for the higher-level construct in the chapter Monitors.
Mutex vs Semaphore
Mutex lock | Semaphore | |
|---|---|---|
What it is | A lock: locked or unlocked | An integer counter with wait/signal |
Values | 2 states | 0, 1, 2, ... (binary semaphore: 0 or 1) |
Purpose | Mutual exclusion only | Mutual exclusion, ordering between threads, counting resources |
Ownership | Yes: the thread that locked it must unlock it | No: any thread may call |
Threads inside at once | 1 | Up to the initial value |
Priority inheritance | Possible (because there is an owner) | Not possible in general (no single owner) |
Typical example | Protecting a shared counter or list | Bounded buffer slots, connection pool, "wait until loaded" |
The most important difference is ownership. A mutex is like a key you carry: only you can return it. A semaphore is like the parking-lot counter: anybody leaving can increase it. That is exactly why a semaphore can be used for signalling between threads (one thread waits, another signals), while a mutex should not be. With POSIX, unlocking a mutex from a thread that does not own it is undefined behaviour for a default mutex, and returns an error (EPERM) for an error-checking mutex.
Common Mistakes
"A binary semaphore and a mutex are the same thing." They behave alike for mutual exclusion, but a mutex has an owner and a semaphore does not.
Locking only part of the check-then-act. The check and the update must be inside the same critical section.
Forgetting to unlock on an error path. Every
returnbetween lock and unlock is a potential hang.Holding a lock while doing slow work (disk I/O, network,
sleep). Others wait for nothing. Keep critical sections short.Using a spinlock on a single-core machine or for long critical sections. It just burns CPU.
Wrong initial value. Mutual exclusion → 1. "Wait for an event" → 0. n identical resources → n.
Trusting
sem_getvalue. The value can change right after you read it, so do not make decisions based on it.
Interview Questions
What is a mutex?
A lock that provides mutual exclusion. A thread calls acquire (lock) before its critical section and release (unlock) after. Only one thread can hold it at a time, and only the holder may release it.
What is a semaphore? What are wait and signal?
An integer variable accessed only through two atomic operations. wait (P) decrements it and blocks if no units are available; signal (V) increments it and wakes a waiting process if there is one.
Difference between a counting and a binary semaphore?
A counting semaphore can take any non-negative value and manages a resource with many instances. A binary semaphore takes only 0 or 1 and is used like a lock.
Difference between a mutex and a binary semaphore?
A mutex has ownership: only the thread that locked it can unlock it, which also allows priority inheritance. A binary semaphore has no owner; any thread can signal it, so it can be used for signalling between threads.
What is busy waiting? What is a spinlock?
Busy waiting is repeatedly checking a condition in a loop instead of sleeping. A spinlock is a lock that waits this way. It wastes CPU but avoids context switches, so it is good only for very short critical sections on multicore systems.
What does a negative semaphore value mean?
In the textbook blocking implementation, a value of −n means n processes are waiting on the semaphore.
How do you make thread B run only after thread A finishes a step?
Use a semaphore initialised to 0. A calls signal after the step; B calls wait before its step.
What is priority inversion and how is it solved?
A high-priority task waits for a lock held by a low-priority task, while a medium-priority task keeps preempting the low-priority one, so the high-priority task is effectively delayed by a lower-priority one. It is solved by priority inheritance (the lock holder temporarily gets the waiter's high priority) or priority ceiling protocols. The Mars Pathfinder resets in 1997 are the famous example.
Can semaphores cause deadlock?
Yes. If two processes each hold one semaphore and wait for the other's (for example, P0 does wait(S) then wait(Q) while P1 does wait(Q) then wait(S)), both block forever. Acquiring in a fixed global order prevents this.
Summary
A mutex lock gives mutual exclusion with
acquire/release; the holder owns it. Our counter and bank programs became correct with apthread_mutex_t.A spinlock busy-waits (good for very short sections on multicore); a blocking lock sleeps. Linux mutexes use futexes: no system call when there is no contention.
A semaphore is an integer with atomic
wait(P) andsignal(V). Initial value 1 → mutual exclusion; 0 → ordering; n → n identical resources.Blocking semaphores keep a waiting list; in the textbook version a value of −n means n waiters.
Semaphores can cause deadlock, starvation and priority inversion (fixed with priority inheritance), and are easy to misuse.
Next, Classical Synchronization Problems uses semaphores to solve the bounded-buffer, readers–writers and dining-philosophers problems.