Semaphores, mutexes and monitors
Clear, exam-focused notes on semaphores, mutexes and monitors: definitions, exact laws, proofs, C examples (pthreads), common mistakes and likely exam questions.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Two-sentence practical use: Synchronisation primitives (semaphores, mutexes, monitors) let engineers coordinate multiple threads or processes that share data or hardware without corrupting state. You will use them when writing kernels, device drivers, concurrent servers or multithreaded applications to ensure mutual exclusion, ordering and to avoid race conditions and inconsistent data.
Key ideas
Start from first principles and define each term before using it.
- Concurrency — multiple sequences of operations (threads or processes) that can overlap in time. Used when a CPU switches between tasks or on multiprocessors.
- Race condition — a situation where the final outcome depends on the unpredictable order of execution of concurrent operations.
- Critical section (CS) — a section of code that accesses shared resources that must not be concurrently executed by more than one thread/process.
- Starvation — a thread or process may be perpetually denied progress despite resources being available, often due to unfair scheduling or lock acquisition order.
- Priority inversion — a lower-priority thread holds a lock needed by a higher-priority thread, indirectly blocking the higher-priority thread; mitigations include priority inheritance or priority ceiling protocols.
Semaphores, mutexes and monitors are synchronization primitives that solve the critical-section problem under different models.
Semaphore — an integer variable S with two atomic operations defined by Dijkstra: wait (P) and signal (V). The semaphore value counts available resources or a synchronization state.
- Definition (exact): A semaphore S supports atomic operations P(S) and V(S) where:
- P(S): while S == 0 do block; otherwise S := S - 1; then proceed.
- V(S): S := S + 1; if there are blocked processes on S, wake one.
- Assumptions: P and V are atomic; blocked processes are queued (implementation detail: FIFO or undefined order).
- Types: Counting semaphore (integer >= 0) and binary semaphore (only 0 or 1, used as a lock).
- Definition (exact): A semaphore S supports atomic operations P(S) and V(S) where:
Mutex — short for mutual exclusion lock. It is a binary lock object providing two operations: lock() and unlock(). Mutex semantics require that the thread that locked must unlock (ownership), and many implementations block the caller if lock is unavailable.
- Definition (exact): A mutex M supports atomic operations lock(M) and unlock(M) such that at most one thread holds M at a time and unlock must be called by the holder (ownership property).
- Assumptions: lock and unlock are atomic; mutexes often provide priority inheritance options in OS implementations to handle priority inversion.
Monitor — a high-level synchronization construct combining mutual exclusion and condition synchronization. A monitor is an abstract data type that encapsulates shared variables, procedures (methods) and condition variables.
- Definition (exact): A monitor ensures that at most one thread is executing any monitor procedure at a time (automatic mutual exclusion). It provides condition variables with operations wait() and signal() to block and wake threads inside the monitor.
- Assumptions: Monitor entry and exit are implicit; on signal, Hoare-style monitors transfer control and the lock immediately to a waiting thread, whereas Mesa-style (used in Java/pthreads) only wakes a waiter which must re-acquire the lock later.
Exact properties and proofs universities ask for (step-by-step):
- Mutual exclusion with a binary semaphore S initialised to 1:
- Before entering CS: P(S)
- After leaving CS: V(S) Proof outline: Let two processes A and B both attempt P(S). S initial 1. First P decrements to 0 and proceeds into CS. The second P sees S==0 so blocks. Therefore they cannot both be in CS simultaneously. This uses atomicity of P.
- Producer-consumer with a bounded buffer uses three semaphores:
empty(count = buffer size),full(count = 0), andmutex(binary semaphore 1) to protect buffer structure. Step-by-step derivation maps resource counts to semaphore initial values and placements of P/V.
What to draw (diagrams):
- For semaphores: draw a timeline with two process rectangles and mark P and V operation times; label semaphore value above timeline before and after each operation. Show how value prevents second process from entering CS.
- For producer-consumer: draw buffer slots, show
emptyinitialized to N,fullto 0, arrows wherePandVoccur relative to buffer insert/remove. Label critical section region where buffer indices and count are updated.
Formulas
For this programming topic list the syntax to remember (POSIX threads and semaphores and C):
#include <pthread.h> — use for pthread APIs.
#include <semaphore.h> — use for POSIX unnamed semaphores (sem_t).
sem_t s; sem_init(&s, 0, value); — initialize unnamed semaphore; 2nd arg 0 means intra-process threads.
sem_wait(&s); — P operation (may block). Return type int; on success returns 0.
sem_post(&s); — V operation (increments and wakes one waiter).
sem_destroy(&s); — destroy semaphore.
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER; — initialize statically, or use pthread_mutex_t m; pthread_mutex_init(&m, NULL); — initialize dynamically (use one, not both).
pthread_mutex_lock(&m); pthread_mutex_unlock(&m); — lock and unlock operations.
pthread_cond_t cv = PTHREAD_COND_INITIALIZER; pthread_cond_wait(&cv, &m); pthread_cond_signal(&cv); — condition variables inside monitor-style code. Note: pthread_cond_wait atomically releases m and re-acquires it before returning.
pthread_create(...) and pthread_join(...) — create and join threads.
Notes: In C, always check return values of these functions in production code.
Worked examples
Example 1 — C program (POSIX semaphores) for producer-consumer with one producer and one consumer and buffer size 3. Code (complete): #include <stdio.h> #include <pthread.h> #include <semaphore.h> #include <unistd.h>
#define BUF_SIZE 3 int buffer[BUF_SIZE]; int in = 0, out = 0; sem_t empty, full; sem_t mutex; // using semaphore as binary mutex
void *producer(void *arg) { for (int i = 1; i <= 5; ++i) { sem_wait(&empty); sem_wait(&mutex); buffer[in] = i; printf("Produced %d at index %d\n", i, in); in = (in + 1) % BUF_SIZE; sem_post(&mutex); sem_post(&full); sleep(1); } return NULL; }
void *consumer(void *arg) { for (int i = 1; i <= 5; ++i) { sem_wait(&full); sem_wait(&mutex); int v = buffer[out]; printf("Consumed %d from index %d\n", v, out); out = (out + 1) % BUF_SIZE; sem_post(&mutex); sem_post(&empty); sleep(2); } return NULL; }
int main() { pthread_t p, c; sem_init(&empty, 0, BUF_SIZE); sem_init(&full, 0, 0); sem_init(&mutex, 0, 1);
pthread_create(&p, NULL, producer, NULL);
pthread_create(&c, NULL, consumer, NULL);
pthread_join(p, NULL);
pthread_join(c, NULL);
sem_destroy(&empty);
sem_destroy(&full);
sem_destroy(&mutex);
return 0;
}
Sample output (one possible interleaving; ordering may vary across runs and systems): Produced 1 at index 0 Consumed 1 from index 0 Produced 2 at index 1 Produced 3 at index 2 Consumed 2 from index 1 Produced 4 at index 0 Produced 5 at index 1 Consumed 3 from index 2 Consumed 4 from index 0 Consumed 5 from index 1
Example 2 — C program (pthread mutex + condition variables) implementing the same bounded buffer as a monitor. Code (complete): #include <stdio.h> #include <pthread.h> #include <unistd.h>
#define BUF_SIZE 3 int buffer[BUF_SIZE]; int in = 0, out = 0, count = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER; pthread_cond_t not_full = PTHREAD_COND_INITIALIZER; pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER;
void *producer(void *arg) { for (int i = 1; i <= 5; ++i) { pthread_mutex_lock(&m); while (count == BUF_SIZE) pthread_cond_wait(¬_full, &m); buffer[in] = i; in = (in + 1) % BUF_SIZE; count++; printf("Produced %d at index %d\n", i, (in+BUF_SIZE-1)%BUF_SIZE); pthread_cond_signal(¬_empty); pthread_mutex_unlock(&m); sleep(1); } return NULL; }
void *consumer(void *arg) { for (int i = 1; i <= 5; ++i) { pthread_mutex_lock(&m); while (count == 0) pthread_cond_wait(¬_empty, &m); int v = buffer[out]; out = (out + 1) % BUF_SIZE; count--; printf("Consumed %d from index %d\n", v, (out+BUF_SIZE-1)%BUF_SIZE); pthread_cond_signal(¬_full); pthread_mutex_unlock(&m); sleep(2); } return NULL; }
int main() { pthread_t p, c; pthread_create(&p, NULL, producer, NULL); pthread_create(&c, NULL, consumer, NULL); pthread_join(p, NULL); pthread_join(c, NULL); return 0; }
Sample output (one possible interleaving; ordering may vary across runs and systems): Produced 1 at index 0 Consumed 1 from index 0 Produced 2 at index 1 Produced 3 at index 2 Consumed 2 from index 1 Produced 4 at index 0 Produced 5 at index 1 Consumed 3 from index 2 Consumed 4 from index 0 Consumed 5 from index 1
Example 3 — Theory model answer (short essay): Explain how semaphores can cause deadlock and how to avoid it. Model answer: Deadlock occurs when each process in a set waits for a resource held by another in the set. Using semaphores without careful ordering can produce circular wait (e.g., two binary semaphores A and B and two processes each doing P(A);P(B) and P(B);P(A) respectively). To avoid deadlock use one of Coffman strategies: impose a strict global ordering on resource acquisition (always P(A) before P(B)), allocate resources atomically, or use deadlock-avoidance algorithms like Banker's when resource request sizes are known.
Common mistakes
- Unlocking a pthread mutex from a different thread is undefined behaviour (ownership violation). Binary semaphores do not enforce ownership, so using them as a mutex can mask this mistake; avoid mixing semantics.
- Forgetting to protect shared counters when using counting semaphores as the only protection; semaphore increments/decrements are atomic but compound updates of multiple shared variables need a mutex.
- Mixing up semaphore order: calling V before updating shared state can wake a thread that sees inconsistent state.
- Assuming fair wake order — POSIX does not guarantee which waiter is awakened; do not rely on FIFO unless specified.
For your exam
Question types you will get on this topic:
- Definitions and short notes (define semaphore, mutex, monitor and describe operations).
- Derivations and proofs (prove binary semaphore gives mutual exclusion; show why
whileis essential with condition variables). - Diagram questions (draw timeline of processes using semaphores; draw bounded buffer and show semaphore values).
- Code/programming (small C programs with semaphores or pthreads; explain sequence of outputs).
- Long answers (compare and contrast primitives; discuss deadlock, starvation and priority inversion).
What full-marks answers include:
- Precise definitions (bold terms), initial values and full sequence of operations (e.g., show P/V placement), clear assumptions (atomicity, blocking semantics), and if a proof is asked, a step-by-step logical argument using those assumptions. For code, give compilable C code and explain expected output or edge cases.
Quick check
- Define a counting semaphore in one sentence.
- Why must
pthread_cond_waitbe called with awhileloop checking the predicate? - Which primitive enforces ownership: semaphore or mutex?
Answers: 1) A counting semaphore is an integer-valued synchronization object that supports atomic P (wait) and V (signal) to decrement and increment the count and block or wake waiters accordingly; 2) Because condition variables can have spurious wakeups and a signaller does not guarantee the predicate holds, so the waiting thread must re-check the predicate in a loop; 3) Mutex enforces ownership (the thread that locks should be the one to unlock).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?