COMP 3150Operating Systems

Module 2 · Unit 6 of 5

Synchronization

The hardest unit in the course — and the most important. Concurrent programs that share mutable state must be synchronised, or they will produce results that depend on timing. This unit develops the theory of critical sections and the toolbox of synchronization primitives that make correct concurrent code possible.

Start Lesson 6.1 See all lessons
7 lessons Lab 5 · Synchronization CLO3 · CLO8 ≈ 2 weeks at recommended pace
A data race and its solution Two threads increment the same shared counter. Without synchronisation, the read-modify-write sequence interleaves and one update is lost. With a lock, the critical sections are serialised. RACE CONDITION shared int counter = 0; /* two threads both do counter++ */ Thread A load 0 add 1 store 1 Thread B load 0 add 1 store 1 expected: 2 actual: 1 one update lost WITH A LOCK pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER; Thread A lock counter++ unlock Thread B lock (waiting) unlock expected: 2 actual: 2 correct every run

Module 2 · Unit 6

Synchronization

Seven lessons on the theory and practice of coordinating concurrent processes and threads. The material is dense; the labs make it concrete.

01 Unit learning outcomes

Upon completion of this unit you will be able to

  • U6.1 — Explain concurrency problems.
  • U6.2 — Identify race conditions.
  • U6.3 — Apply synchronization mechanisms.
  • U6.4 — Design synchronization solutions.
  • U6.5 — Implement Linux synchronization solutions.

This unit addresses course learning outcomes CLO3, CLO6, and CLO8. It is the primary source material for Assignment 1.

02 Lessons in this unit

The first two lessons define the problem. The next five develop the mechanisms, from the simplest (locks) to the most structured (monitors and condition variables), and close with the Linux facilities you will use in practice.

Lesson 6.1

Race Conditions

What a race is, why non-determinism is so damaging, and how to recognise the pattern.

 Lesson 6.2

Critical Sections

The three properties a correct solution must satisfy, and the classical attempts to achieve them.

 Lesson 6.3

Locks

Spinlocks, blocking locks, and the hardware primitives (test-and-set, compare-and-swap) they rely on.

 Lesson 6.4

Semaphores

Counting and binary semaphores, and the classic producer–consumer and readers–writers patterns.

 Lesson 6.5

Monitors

The structured synchronization abstraction that bundles a lock and condition variables.

 Lesson 6.6

Condition Variables

Waiting for a predicate to become true — and why the wait must always be in a while loop.

 Lesson 6.7

Synchronization in Linux

Mutexes, semaphores, futexes, atomic operations, and the C11 memory model.

03 What you will learn, lesson by lesson

6.1 Race Conditions

  • Define a race condition.
  • Identify interleaving hazards.
  • Explain non-determinism.
  • Analyse outcomes.
  • Recognise race patterns.

6.2 Critical Sections

  • Define the critical-section problem.
  • State mutual exclusion.
  • State progress.
  • State bounded waiting.
  • Evaluate proposed solutions.

6.3 Locks

  • Define a lock.
  • Compare spin and blocking locks.
  • Explain test-and-set.
  • Explain compare-and-swap.
  • Analyse lock performance.

6.4 Semaphores

  • Define semaphores.
  • Use counting semaphores.
  • Use binary semaphores.
  • Solve producer–consumer.
  • Analyse semaphore pitfalls.

6.5 Monitors

  • Define a monitor.
  • Explain monitor semantics.
  • Compare with locks.
  • Analyse monitor design.
  • Evaluate monitor use.

6.6 Condition Variables

  • Define condition variables.
  • Explain wait and signal.
  • Explain the while-loop rule.
  • Analyse lost wakeups.
  • Design predicate-based waits.

6.7 Synchronization in Linux

  • Use pthread mutexes.
  • Use POSIX semaphores.
  • Explain futexes.
  • Apply atomic operations.
  • Analyse memory-ordering issues.

04 Worked example

The producer–consumer problem, solved with a mutex and two condition variables. This pattern appears in every message queue and every thread pool. 

#include <pthread.h>

#define N 16

int buffer[N];
int count = 0;
int in = 0, out = 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 = 0; i < 100; i++) {
        pthread_mutex_lock(&m);
        while (count == N)
            pthread_cond_wait(&not_full, &m);
        buffer[in] = i;
        in = (in + 1) % N;
        count++;
        pthread_cond_signal(&not_empty);
        pthread_mutex_unlock(&m);
    }
    return NULL;
}

void *consumer(void *arg) {
    for (int i = 0; i < 100; i++) {
        pthread_mutex_lock(&m);
        while (count == 0)
            pthread_cond_wait(&not_empty, &m);
        int v = buffer[out];
        out = (out + 1) % N;
        count--;
        pthread_cond_signal(&not_full);
        pthread_mutex_unlock(&m);
    }
    return NULL;
}

Why every line is there

  1. The mutex m guards all shared state. count, in, out, and the buffer contents can only be touched while holding the lock.
  2. The condition variables signal state changes. not_full is signalled when the producer adds an item; not_empty is signalled when the consumer removes one.
  3. The wait is inside a while loop. This is the single most important rule in this lesson. When pthread_cond_wait returns, the thread does not necessarily own the predicate it was waiting for. Another thread may have consumed the condition before this one reacquired the mutex. The loop re-checks.
  4. The signal is issued while holding the lock. This is not strictly required by POSIX, but it is the clearest discipline: signal after you have changed the predicate, before you release the lock. It eliminates a class of subtle races that are extremely difficult to debug.
  5. Both threads return the mutex before re-looping. Holding the lock across an unbounded operation would block the other side and defeat the purpose of the pattern.

Use while, not if

Using if (count == N) instead of while (count == N) is the single most common synchronization bug. It causes failures that reproduce once in a million runs and are almost impossible to reproduce on demand.

05 Required reading

  • OSTEP — Chapters 28–34 (locks, condition variables, semaphores, and the classic concurrency problems).
  • Operating System Concepts — Chapter 6, Synchronization Tools, and Chapter 7, Synchronization Examples.
  • Man pages: pthread_mutex_lock(3), pthread_cond_wait(3), sem_overview(7), futex(2).

Read slowly

The material in this unit is dense and the details matter. Multiple readings of the same chapter with code in hand is the normal approach. Do not try to skim.

06 Unit discussion

Discussion prompt

Some modern languages and libraries avoid shared-memory synchronization altogether by having concurrent tasks communicate only through message channels — Go's "Do not communicate by sharing memory; instead, share memory by communicating" is the canonical slogan. Others, such as Rust, use the type system to make data races a compile-time error.

Pick one of these approaches and explain how it reduces the class of bugs this unit has been describing. Then identify a class of bug it does not eliminate. Support your answer with a concrete example.

Post your response to the Unit 6 discussion forum and reply to at least two classmates. This activity contributes directly to Assignment 1's synchronization design criterion.

07 Laboratory connection

Lab 5 — Synchronization is completed at the end of this unit. It asks you to implement the classical concurrency problems from scratch, deliberately break them to observe failures, and then repair them.

Lab 5 coverage
Lesson Lab 5 exercise
6.1 Race ConditionsReproduce a race with two threads incrementing a counter
6.3 LocksFix the race with a pthread mutex; measure the cost
6.4 SemaphoresImplement producer–consumer with POSIX semaphores
6.6 Condition VariablesImplement the same with mutex + condition variables
6.7 LinuxInspect blocking with strace -f and ltrace

08 Knowledge check & quiz

Quick check before you begin

Question 1

State the three properties a correct critical-section solution must satisfy.

Show answer
Mutual exclusion: at most one thread may execute inside the critical section at a time. Progress: if no thread is inside the critical section and some thread wants to enter, the choice of which thread enters next cannot be postponed indefinitely. Bounded waiting: there is a limit on the number of times other threads may enter the critical section before a waiting thread is admitted.

Question 2

Why must pthread_cond_wait always be called inside a while loop that re-checks the predicate, rather than an if?

Show answer
Because pthread_cond_wait can wake up spuriously, and even a signal-driven wakeup does not guarantee that the predicate is still true. Between the signal and the moment the woken thread reacquires the mutex, another thread may have consumed the condition the signal announced. The while loop re-evaluates the predicate under the protection of the mutex, so the thread either proceeds safely or goes back to waiting.

Question 3

What is a futex, and why is it important for the performance of Linux synchronization primitives?

Show answer
A futex (fast user-space mutex) is a kernel primitive that allows a synchronization object to be implemented almost entirely in user space. In the common uncontended case, acquiring a lock is just an atomic compare-and-swap on a shared memory word — no system call at all. Only when a thread must actually block does it enter the kernel. This makes uncontended lock operations extremely cheap, which matters because most lock acquisitions in a healthy program are uncontended.
👤