Lab 5: Synchronization

01 Lab overview

Course	COMP 3150 / CMIS 3150 — Operating Systems
Unit	Unit 6 — Synchronization
Weight	1.25% of the final grade (1/12 of the 15% laboratory component)
Estimated duration	4–5 hours of hands-on work
Submission	One archive containing the C source files, the Makefile, the output logs, and a short lab report (see § 06)
Environment	Linux VM, `gcc`, `make`, `perf`, `valgrind` (with the Helgrind tool, if available), `strace`

This lab contributes to U6.1 through U6.5, and to course learning outcomes CLO3, CLO6, and CLO8.

02 Learning objectives

By the end of this laboratory you will be able to

Use POSIX mutexes to protect a critical section from race conditions.
Use POSIX semaphores and condition variables to implement the classical synchronisation patterns.
Implement the producer-consumer problem with a bounded buffer.
Implement the readers-writers problem with reader-preference and writer-preference policies.
Identify deadlock and starvation risks in a synchronisation design and mitigate them.
Measure and explain the performance cost of mutexes, semaphores, and condition variables.

03 Background

3.1 The critical section

A critical section is a region of code that accesses a shared resource and must be executed by at most one thread at a time. The classical requirements for a correct critical-section solution are:

Mutual exclusion. At most one thread is in the critical section at a time.
Progress. If no thread is in the critical section and some threads want to enter, the decision of which thread enters cannot be postponed indefinitely.
Bounded waiting. There is a bound on the number of times other threads can enter the critical section after a thread has requested entry and before it is granted.

3.2 POSIX mutexes

A mutex (mutual exclusion lock) is the simplest synchronisation primitive: it is either locked or unlocked. The operations are pthread_mutex_lock, pthread_mutex_unlock, and pthread_mutex_init / pthread_mutex_destroy.

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void *worker(void *arg) {
    for (long i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&lock);
        counter++;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

3.3 POSIX semaphores

A semaphore is a non-negative integer with two atomic operations: sem_wait (decrement; block if the value would go below zero) and sem_post (increment; wake a waiter if any). POSIX semaphores are available in the unnamed (in-memory) and named (file-system) variants. The unnamed variant is used with threads:

#include <semaphore.h>
sem_t sem;
sem_init(&sem, 0, 0);   /* value = 0, shared between threads */
...
sem_wait(&sem);        /* decrement, block if zero */
sem_post(&sem);        /* increment */
sem_destroy(&sem);

3.4 Condition variables

A condition variable lets a thread block until some condition becomes true. It is always used with a mutex:

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  c = PTHREAD_COND_INITIALIZER;

/* waiter */
pthread_mutex_lock(&m);
while (!condition) {
    pthread_cond_wait(&c, &m);  /* atomically unlocks and blocks */
}
/* ... consume the condition ... */
pthread_mutex_unlock(&m);

/* signaller */
pthread_mutex_lock(&m);
condition = 1;
pthread_cond_signal(&c);        /* or pthread_cond_broadcast(&c) */
pthread_mutex_unlock(&m);

The while loop around pthread_cond_wait is essential: the wait can return spuriously, and even a legitimate signal does not guarantee that this thread is the one that should proceed.

3.5 Barriers

A barrier makes a group of threads wait until all of them have reached the barrier. It is useful for phased computations (each phase must complete before the next begins):

pthread_barrier_t bar;
pthread_barrier_init(&bar, NULL, N);   /* N = number of threads */
...
pthread_barrier_wait(&bar);            /* wait for all N */
pthread_barrier_destroy(&bar);

04 Guided activities

Activity 4.1 — Fixing the race with a mutex

Create the lab directory and the file counter_mutex.c:
```
mkdir -p ~/comp3150/lab5 && cd ~/comp3150/lab5
```
Reimplement the race from Lab 3, with a global counter incremented by 4 threads, 1,000,000 times each.
Wrap the increment in a mutex. Verify that the final value is exactly 4,000,000 across many runs.
Measure the wall-clock time with and without the mutex. What is the cost of synchronising 4 million increments?
Repeat with n = 1, 2, 4, 8 threads. Does the mutex's cost grow with contention? Explain.

Activity 4.2 — Producer-consumer with a bounded buffer

Implement a bounded buffer of size B with a single producer and a single consumer. Use a mutex plus two condition variables (not_full, not_empty).
The producer generates N items and sem_posts the consumer. The consumer removes items and signals the producer. The producer sleeps a small random time between items; the consumer likewise.
Run with B = 1, 4, 16 and N = 10⁶. Record the total wall-clock time and the number of items produced/consumed. Verify that no item is lost or duplicated.
Modify the consumer to be slower than the producer (e.g., the consumer sleeps 5× as long as the producer). What happens? What does the buffer fullness distribution look like? Measure the producer's blocking time.
Repeat with multiple producers and multiple consumers. Verify correctness and measure the throughput.

Activity 4.3 — Producers-consumers with semaphores

Reimplement the bounded buffer with three semaphores: empty (initialized to B), full (initialized to 0), and mutex (initialized to 1).
Compare the semaphore version's performance to the mutex+condition-variable version. Which is faster? Why?
Introduce a deliberate bug: swap the order of sem_wait(&mutex) and sem_wait(&empty) in the producer. Run the program under a workload that fills the buffer, and observe the hang. Explain the deadlock.

Activity 4.4 — Readers-writers

Implement the readers-writers problem with reader preference. Multiple readers may read concurrently; writers are exclusive.
Run the program with 4 readers and 2 writers, each performing 10⁵ operations. Record the total wall-clock time and the number of reads and writes.
Modify the design to give writers priority. Use a second mutex to block new readers while a writer is waiting. Measure the wall-clock time again.
Construct a workload that starves a writer under reader preference, and another that starves readers under writer preference. Explain what happens.

Activity 4.5 — Barriers in a phased computation

Implement a program with 4 threads that performs 5 phases. In each phase, every thread updates its own portion of a shared array, and then all threads wait at a barrier before the next phase begins.
Replace the barrier with a mutex and a counter (the classical sense-reversing barrier). Verify correctness and compare the wall-clock time.
Demonstrate the difference between the barrier and a simple join-based synchronisation (i.e., without the barrier, run each phase as a separate batch of threads). Why is the barrier more efficient?

05 Exercises

Dining philosophers. Implement the dining philosophers problem with 5 philosophers and 5 forks. First implement the naive solution (each philosopher picks up the left fork, then the right). Run for a few seconds and demonstrate the deadlock. Then implement one of the classical solutions (resource ordering, or a global semaphore limiting the number of seated philosophers). Verify that no deadlock occurs.
Sleeping barber. Implement the sleeping barber problem: one barber, one barber's chair, and N waiting chairs. Customers arrive, sit if there is a free waiting chair, and wake the barber if he is asleep. The barber cuts hair, then sleeps if there are no customers. Verify with 10,000 customers that no customer is lost and the barber's utilization is measured.
Fair reader-writer. Implement the readers-writers problem with a fair policy: no reader waits if a writer is waiting and no writer waits if a reader is waiting beyond one writer's service time. Measure the read and write throughput and compare to the reader-preference and writer-preference policies.
Cost of contention. Write a program in which n threads each increment a shared counter M times under a mutex. Measure the throughput (increments per second) as a function of n for M = 10⁶. Explain the drop in throughput as n grows. Then pad the counter to a full cache line and measure again. Explain the difference (this is the false sharing effect).
Priority inversion. With three threads of high, medium, and low priority (using pthread_setschedparam and SCHED_FIFO), demonstrate priority inversion: a low-priority thread holds a mutex, a high-priority thread waits for it, and a medium-priority thread preempts the low-priority thread. Then demonstrate the priority-inheritance protocol (PTHREAD_PRIO_INHERIT) and show that the inversion is bounded.
Lamport's bakery algorithm. Implement Lamport's bakery algorithm for n threads and verify that the critical section is protected and that every thread eventually enters. Compare its performance with a mutex. Why is the bakery algorithm not used in practice?
Synchronisation vs. parallelism. Measure the total wall-clock time of the counter program under a mutex, an atomic increment (__atomic_fetch_add), and a per-thread counter (each thread increments its own counter and sums at the end). Plot the three times as functions of n. Explain the result in terms of cache coherence and contention.

06 Deliverables

Submit a single archive named lab5-<lastname>-<studentnumber>.tar.gz containing:

counter_mutex.c — Activity 4.1.
pc_cv.c — the producer-consumer with condition variables.
pc_sem.c — the producer-consumer with semaphores, including the deadlock's demonstration (kept in a separate target or guarded by a compile-time flag).
rw_reader_pref.c and rw_writer_pref.c — Activity 4.4.
barrier.c — Activity 4.5.
philosophers.c — Exercise 1 (naive and corrected, with a command-line flag to select which).
The Makefile with one target per program and a clean target.
outputs.txt — the output logs of all programs with the commands that produced them.
report.md (or report.pdf) — the lab report described below.

Lab report

The report should be 4–6 pages (excluding code) and contain:

Design. For each program, a brief description of the shared data, the critical sections, the synchronisation primitives, and the invariants the program maintains.
Correctness evidence. For each program, the checks that confirm no item is lost, no duplicate is produced, and the invariants hold. Include the output of the counter's final value over many runs.
Performance data. The timing measurements with the methodology (warm-up, repetitions, mean and standard deviation).
Deadlock and starvation analysis. The producer-consumer semaphore deadlock and the readers-writers starvation demonstrations, with the step-by-step interleavings that produce each failure.
Reflection. A discussion of which synchronisation primitive is appropriate for which pattern, and of how the Linux kernel's primitives (futexes, RCU, spinlocks) differ from the user-space POSIX primitives.

07 Grading rubric

Lab 5 grading rubric (100 points)
Criterion	Points	CLOs	Exemplary (90–100%)	Proficient (80–89%)	Developing (70–79%)
Correctness of synchronisation	35	CLO3, CLO8	All programs are free of race conditions, deadlocks, and starvation; invariants verified.	Programs correct under the tested workloads; minor edge cases unverified.	Programs occasionally fail or have a race that was not detected.
Use of primitives	20	CLO6, CLO8	Each primitive is used where it is idiomatic; mutex/condition-variable patterns are correct (spurious wakeups handled).	Primitives used correctly in most cases; one or two non-idiomatic uses.	Primitives used but with the common errors (missing while loop, wrong initial values).
Deadlock and starvation analysis	20	CLO3	The failures are demonstrated, the interleavings are traced, and the fixes are explained.	Failures demonstrated; explanations are partially complete.	Failures described but not demonstrated or traced.
Performance analysis	15	CLO3, CLO5	Measurements are rigorous and the analysis of contention and false sharing is quantitative.	Measurements are adequate; analysis is mostly correct.	Measurements lack methodology or the analysis is superficial.
Report quality	10	CLO8	Report is well-structured, evidence-based, and the reflection is insightful.	Report is clear; some claims are unsupported.	Report is disorganised or has significant inaccuracies.

Late submission penalty: 10% per day, up to a maximum of three days, after which the lab is accepted only with documented extenuating circumstances.

08 Knowledge check

Check your understanding

Question 1

Explain why pthread_cond_wait must be called inside a while loop rather than an if statement.

Show answer

There are two reasons. First, the POSIX standard permits spurious wakeups: pthread_cond_wait may return without any thread having signalled the condition variable. If the code used an if statement, a spurious wakeup would lead the thread to proceed as if the condition were true when it might not be. Second, even a legitimate signal does not guarantee that the signalled thread is the one that should run: if multiple threads are waiting, pthread_cond_signal wakes an arbitrary one, and the woken thread may find that another thread has already consumed the condition (a "stolen wakeup"). The while loop re-checks the predicate after every wakeup, so the thread only proceeds when the condition is actually true. The general rule is: the condition variable must always be used with a predicate and the predicate must be re-checked after the wait.

Question 2

In the semaphore-based producer-consumer, why must the mutex-protected insert and remove operations occur between the semaphore operations, not before or after them?

Show answer

The semaphores empty and full control how many slots are available and how many are filled; the mutex protects the buffer's index variables and the slot array itself from concurrent modification. The correct sequence is: wait on the semaphore to claim a slot (or a filled item), then lock the mutex, modify the buffer, unlock the mutex, then post the semaphore that signals the other side. If the mutex is acquired first and the semaphore wait blocks while holding the mutex, the other side can never proceed: the consumer, for example, cannot consume because it is blocked on the mutex that the producer holds while waiting for an empty slot that only the consumer can create. This is a deadlock. If the semaphore wait and post are inverted (post before the buffer is modified, or wait after it), a consumer may see a "filled" signal before the data is actually present, or may remove an item that no producer has yet produced. The rule is: the semaphore operations bracket the critical section in the correct order — wait on the "resource available" semaphore before entering, post the "resource produced" semaphore after leaving.

Question 3

What is priority inversion? Describe the scenario with three threads, explain why it violates the real-time requirements, and describe the priority-inheritance solution.

Show answer

Priority inversion is the phenomenon in which a high-priority thread is indirectly delayed by a low-priority thread. Consider three threads: a high-priority thread H, a medium-priority thread M, and a low-priority thread L. L acquires a mutex; H becomes runnable and tries to acquire the same mutex, so H blocks (waiting for L to release the mutex). Now M becomes runnable; because M's priority is higher than L's, M preempts L and runs. H remains blocked — even though H is the highest-priority thread in the system — because L is not running, so L cannot release the mutex. In effect, M blocks H, even though M does not use the mutex at all. In a real-time system this violates the priority guarantee: a high-priority thread must not be delayed by lower-priority threads. The priority-inheritance protocol solves the problem: while L holds a mutex that H is waiting for, L inherits H's priority. Now L has priority equal to H, so M cannot preempt L; L runs, releases the mutex, and H acquires it. When H is done, L drops back to its original priority. The protocol bounds the inversion: the maximum delay H can experience is the time L needs to finish its critical section, plus the time of any lower-priority threads with the same inherited priority. POSIX pthreads exposes the protocol through the PTHREAD_PRIO_INHERIT mutex attribute.

Question 4

Compare mutexes, semaphores, and condition variables. For each primitive, state what shared state it manages and which pattern it is best suited to.

Show answer

A mutex is a binary lock: it protects a critical section from concurrent access. It is best suited to the simplest pattern: mutual exclusion on a shared data structure whose accesses are short. A mutex is not a signalling primitive: a thread cannot use a mutex to wait for a condition to become true. A semaphore is a non-negative integer counter with wait (decrement, block if zero) and post (increment, wake a waiter). It is best suited to patterns that count resources: the producer-consumer bounded buffer, the reader-writer problem, the dining philosophers (the resource ordering solution), and the sleeping barber. It is also useful as a general-purpose signalling mechanism because the initial value is a parameter. A condition variable is a waiting mechanism that is always used with a mutex. It is best suited to patterns where a thread must wait for a predicate that is not simply a count: a buffer becoming non-empty, a state machine reaching a particular state, a task being ready. It is more flexible than a semaphore because the wait and signal can be conditioned on an arbitrary predicate, and because broadcast can wake all waiters when the predicate changes in a way that might satisfy several of them. The three primitives are complementary; in practice, a single pattern may use more than one (for example, the bounded buffer with condition variables uses a mutex plus two condition variables).

Question 5

In the readers-writers problem, explain the difference between reader preference and writer preference, and describe a workload that starves a writer under reader preference.

Show answer

In the reader-preference policy, a reader is allowed to read as long as no writer is currently writing. If readers keep arriving, they keep each other "in" (because they do not exclude each other), and a waiting writer may never get to write. In the writer-preference policy, a writer that is waiting for access blocks any new reader until the writer has completed, so readers cannot starve the writer. A workload that starves a writer under reader preference is a stream of readers arriving faster than the average reader's service time. Concretely: readers arrive at 1000 per second and each reader's critical section takes 1 ms, so the readers collectively saturate the read path. A writer arrives; because there are always readers inside (each reader's arrival overlaps the previous reader's service), the writer's request blocks. A new reader arriving a moment later sees "no writer currently writing" (because the writer is waiting, not writing) and enters, so the writer's wait is extended. If reader arrivals continue at this rate, the writer waits indefinitely. The standard fix is a second mutex (wrt in the classical solution) or a queue that records the writer's waiting so that new readers queue behind it.

09 References

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 6 and Chapter 7.
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 28–34.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2.
Dijkstra, E. W. Cooperating Sequential Processes. Academic Press, 1968.
Hoare, C. A. R. Monitors: An Operating System Structuring Concept. Communications of the ACM, 1974.
Lamport, L. A New Solution of Dijkstra's Concurrent Programming Problem. Communications of the ACM, 1974.
Linux man-pages: man 3 pthread_mutex_init, man 3 pthread_cond_wait, man 3 sem_init, man 3 sem_wait, man 3 sem_post, man 3 pthread_barrier_init, man 7 pthreads, man 7 futex.