7 - Synchronization-mod

1.

10/8/2026
Synchronization
Silberschatz, Galvin and Gagne ©2013
Operating System Concepts – 9th Edition
1
Synchronization
Background
The Critical-Section Problem
Peterson’s Solution
Hardware Support: atomic instructions and variables
Mutex Locks
Semaphores
Classic Problems of Synchronization
Monitors and Condition Variables
Synchronization in Practice: POSIX, Python, Linux, Windows
Alternative Approaches
Operating System Concepts – 9th Edition
5.2
Silberschatz, Galvin and Gagne ©2013
2
1

2.

10/8/2026
Recap from Chapter 4
Threads of one process share global data and the heap, but each has its own
stack
Practice 1 already showed what goes wrong:
Ex. 6 – two threads read/write the same sharedvar
Ex. 7 – pthread_race.c: without the mutex, Actual < Expected
Ex. 8 – OpenMP sum without reduction gives a wrong result
Python’s GIL does not make your code thread-safe
This chapter: why it happens and which tools prevent it
Threads share memory: Ch. 4, slide 4.5 – Single and Multithreaded Processes
Python threads and the GIL: Ch. 4, slide 4.35 – Python Threads and the GIL
Implicit threading: Ch. 4, slides 4.45–4.46 – OpenMP
Silberschatz, Galvin and Gagne ©2013
5.3
Operating System Concepts – 9th Edition
3
Quick Quiz: Chapter 4
QUIZ
1. Threads of the same process share their …
A) stack
B) registers
C) heap
D) program counter
2. Linux, Windows and macOS use which multithreading model?
A) many-to-one
B) one-to-one
C) many-to-many
D) two-level
3. A CPU-bound pure-Python task runs on 4 threads (standard CPython).
Speedup ≈
4. OpenMP parallel for with sum += i and no reduction gives …
A) 4×
B) 2×
C) 1×
D) 0.25×
A) always the right sum B) a wrong sum that changes every run
compile error D) a deadlock
C) a
5. Five asyncio tasks each call time.sleep(1). Total time ≈
A) 1 s
B) 5 s
C) 0 s
D) an error
Answers: 1 C 2 B 3 C 4 B 5 B
Operating System Concepts – 9th Edition
5.4
Silberschatz, Galvin and Gagne ©2013
4
2

3.

10/8/2026
Objectives
Describe the critical-section problem and illustrate a race condition
Illustrate hardware solutions: memory barriers, compare-and-swap, and
atomic variables
Demonstrate how mutex locks, semaphores, monitors, and condition
variables solve the critical-section problem
Apply them to classic problems: bounded buffer, readers–writers, dining
philosophers
Use the synchronization APIs of POSIX (C) and Python, and know what
Linux and Windows provide
Operating System Concepts – 9th Edition
5.5
Silberschatz, Galvin and Gagne ©2013
5
Predict: OpenMP
PREDICT
• Run with OMP_NUM_THREADS=4 ./omp_predict. How many “Hello”
lines? Is the sum always 500000500000?
Answer: 4 “Hello” lines (one per thread).
The sum is wrong and different on every
run: all threads update sum at the same
time (a race condition).
Fix: reduction(+:sum).
#include <stdio.h>
#include <omp.h>
int main(void) {
#pragma omp parallel
printf("Hello\n");
long sum = 0;
#pragma omp parallel for
for (long i = 1; i <= 1000000; i++)
sum += i;
printf("sum = %ld\n", sum);
return 0;
}
Compile: gcc -fopenmp omp_predict.c -o omp_predict (see Practice 1, Ex. 8)
Operating System Concepts – 9th Edition
5.6
Silberschatz, Galvin and Gagne ©2013
6
3

4.

10/8/2026
Motivation: Sending Data
Task: a parent thread reads lines from the keyboard; a child thread prints them in
UPPERCASE. Both loop forever.
Problem: the child must read only when new data is ready, and the parent must not overwrite
unread data.
Threads vs processes: no pipe needed (shared memory), but we must synchronize.
Python: queue.Queue does this for you (Practice 1, Ex. 13).
keyboard
parent
thread
buffer
child
thread
screen
reads line
"hello"
to upper
HELLO
Question: how does the child know that the buffer holds new data?
Silberschatz, Galvin and Gagne ©2013
5.7
Operating System Concepts – 9th Edition
7
Race Condition
Result of executing program/thread(s) depends on who runs precisely
when
balance starts at 1000
Thread 1
Thread 2
b = getBalance(“1234”);
b -= 100;
setBalance(“1234”, b);
b = getBalance(“1234”);
b += 500;
setBalance(“1234”, b);
Answer: should be
1400. Without a lock it
can end at 900, 1400 or
1500.
Removing b does not
help: balance += 500
is still read–modify–
write.
Fix: a mutex around get
+ set.
What should the ending balance be? What will it be?
Will getting rid of the local variable b solve the problem?
How can we solve this problem?
Operating System Concepts – 9th Edition
5.8
Silberschatz, Galvin and Gagne ©2013
8
4

5.

10/8/2026
Race Condition in Python
DEMO
The GIL runs one thread at a time, but a thread can be switched out between the
read and the write
import threading
counter = 0
def work():
pass
# e.g. logging, validation ...
def increment(n):
global counter
for _ in range(n):
value = counter
work()
counter = value + 1
# read
# any call: thread switch possible
# write
Sample run (Python 3.13):
expected 800000, got
513992
– different on every run
threads = [threading.Thread(target=increment, args=(200_000,))
for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()
print("expected 800000, got", counter)
Operating System Concepts – 9th Edition
5.9
Silberschatz, Galvin and Gagne ©2013
9
Synchronization Primitives
Need to prevent race conditions
Critical region: part of a program that accesses shared memory (or another shared
resource)
Allow only one thread at a time: a lock operation blocks or lets a thread in, an unlock
releases the next waiting thread
Common synchronization primitives:
Binary semaphore – the oldest and most basic mechanism
Mutex – the most commonly used
Counting semaphore – lets up to N threads into a region
Reader–writer lock – many readers at the same time, writers alone
Operating System Concepts – 9th Edition
5.10
Silberschatz, Galvin and Gagne ©2013
10
5

6.

10/8/2026
Mutex Lock APIs
Operation
C (Pthreads)
lock: block if not available pthread_mutex_lock(&m)
C++ (std::mutex)
Python (threading.Lock)
m.lock()
m.acquire()
try to lock, return if not
available
pthread_mutex_trylock(&m)
m.try_lock()
m.acquire(blocking=Fal
se)
unlock
pthread_mutex_unlock(&m)
m.unlock()
m.release()
scoped (auto-unlock)
–
std::lock_guard
lk(m);
with m: ...
Source: cppreference.com (std::mutex, since C++11), POSIX and Python docs
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
5.11
11
counter++ is not atomic
counter++ could be implemented as
register1 = counter
register1 = register1 + 1
counter = register1
counter-- could be implemented as
register2 = counter
register2 = register2 - 1
counter = register2
Consider this execution interleaving with “count = 0” initially:
Step 0: thread1 execute register1 = counter
Step 1: thread1 execute register1 = register1 + 1
Step 2: thread2 execute register2 = counter
Step 3: thread2 execute register2 = register2 – 1
Step 4: thread1 execute counter = register1
Step 5: thread2 execute counter = register2
Operating System Concepts – 9th Edition
5.12
{register1 = 0}
{register1 = 1}
{register2 = 0}
{register2 = -1}
{counter = 1 }
{counter = -1}
Silberschatz, Galvin and Gagne ©2013
12
6

7.

10/8/2026
Predict: How Small Can counter Get?
PREDICT
counter = 0. Two threads run this loop at the same time, without a lock:
for (int i = 0; i < 10; i++)
counter++;
/* load, add 1, store */
1. What is the largest possible final value of counter?
2. What is the smallest possible final value? (Hint: it is not 10)
Write your answer, then compare with your neighbour. Use the load/add/store steps of
the previous slide.
Answer: 1. Largest: 20. 2. Smallest: 2.
T1 loads 0 and stops; T2 does 9 iterations (9); T1 stores 1; T2 loads 1 and stops; T1 does 9 iterations (10); T2
stores 1 + 1 = 2.
Operating System Concepts – 9th Edition
5.13
Silberschatz, Galvin and Gagne ©2013
13
Critical Section Problem
System of n processes {p0, p1, …, pn-1}
Each process has a critical section: code that
changes shared variables, updates a table, writes
a file, …
When one process is in its critical section, no
other may be in its critical section
Critical-section problem: design a protocol that
guarantees this
A process asks permission in the entry section,
then runs the critical section, the exit section
and the remainder section
Operating System Concepts – 9th Edition
5.14
Silberschatz, Galvin and Gagne ©2013
14
7

8.

10/8/2026
Solution to Critical-Section Problem
1. Mutual Exclusion - If process Pi is executing in its critical section, then no other processes can be
executing in their critical sections
2. Progress - If no process is executing in its critical section and there exist some processes that wish to
enter their critical section, then the selection of the processes that will enter the critical section next
cannot be postponed indefinitely
3. Bounded Waiting - A bound must exist on the number of times that other processes are allowed to
enter their critical sections after a process has made a request to enter its critical section and before
that request is granted
Assume that each process executes at a nonzero speed
No assumption concerning relative speed of the n processes
Two approaches depending on if kernel is preemptive or non-preemptive
Preemptive – allows preemption of process when running in kernel mode
Non-preemptive – runs until exits kernel mode, blocks, or voluntarily yields CPU
Essentially free of race conditions in kernel mode
5.15
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
15
Peterson’s Solution
Good algorithmic description of solving the problem
Two process solution
Assume that the load and store instructions are atomic; that is, cannot be
interrupted
The two processes share two variables:
int turn;
Boolean flag[2]
The variable turn indicates whose turn it is to enter the critical section
The flag array is used to indicate if a process is ready to enter the critical section.
flag[i] = true implies that process Pi is ready!
Operating System Concepts – 9th Edition
5.16
Silberschatz, Galvin and Gagne ©2013
16
8

9.

10/8/2026
Algorithm for Process Pi
Assumption i=0, j=1
do {
P0
flag[i] = true;
turn = j;
P1
while (flag[j] && turn == j);
critical section
flag[i] = false;
entry
remainder section
} while (true);
Provable that
1.
Mutual exclusion is preserved
2.
Progress requirement is satisfied
3.
Bounded-waiting requirement is met
entry
flag[0]=T
turn =1
while exit
critical section
exit
flag[0]=F
while exit
critical section
Operating System Concepts – 9th Edition
5.17
Silberschatz, Galvin and Gagne ©2013
17
Predict: Swap Two Lines of Peterson
PREDICT
We swap the first two lines of the entry section. Is mutual exclusion still
guaranteed?
do {
turn = j;
/* swapped */
flag[i] = true;
/* swapped */
while (flag[j] && turn == j)
;
/* critical section */
flag[i] = false;
/* remainder section */
} while (true);
Try to find a schedule of P0 and
P1 that puts both in the critical
section.
Simulate it with OSTEP’s
x86.py (peterson.s).
Answer: No. P0: turn = 1. P1: turn = 0, flag[1] = true, sees flag[0] == false → enters. P0: flag[0] = true, sees turn
== 0 → enters. Both are in the critical section. The flag must be set before giving the turn away.
Operating System Concepts – 9th Edition
5.18
Silberschatz, Galvin and Gagne ©2013
18
9

10.

10/8/2026
Peterson’s Solution Today
Peterson’s solution is not guaranteed to work on modern computers
To improve performance, processors and compilers may reorder reads and
writes that have no dependencies
Example: two threads share boolean flag = false; and int x = 0;
Thread 1: while (!flag) ;
Thread 2: x = 100;
Expected output: 100 – but if the two writes of thread 2 are reordered, thread 1
may print 0
print x
flag = true;
For Peterson’s solution, reordering can let both threads enter the critical
section
Fix: use the hardware support described next
Operating System Concepts – 9th Edition
5.19
Silberschatz, Galvin and Gagne ©2013
19
Synchronization Hardware
Many systems provide hardware support for critical section code
All solutions below based on idea of locking
Protecting critical regions via locks
Uniprocessors – could disable interrupts
Currently running code would execute without preemption
Generally too inefficient on multiprocessor systems
Operating systems using this not broadly scalable
Modern machines provide special atomic hardware instructions
Atomic = non-interruptible
Either test memory word and set value
Or swap contents of two memory words
Operating System Concepts – 9th Edition
5.20
Silberschatz, Galvin and Gagne ©2013
20
10

11.

10/8/2026
Memory Barriers
Memory model: the guarantees an architecture gives an application about
memory
Strongly ordered: a modification on one processor is immediately visible to all
others
Weakly ordered: it may not be immediately visible (e.g., ARM)
A memory barrier (fence) is an instruction that forces all earlier loads and
stores to complete before later ones
Thread 2: x = 100;
memory_barrier();
flag = true;
Very low-level: used by kernel developers and inside lock implementations
C11: atomic_thread_fence(); locks and atomic variables include the right
barriers for you
Silberschatz, Galvin and Gagne ©2013
5.21
Operating System Concepts – 9th Edition
21
test_and_set()
Shared boolean variable lock, initialized to FALSE
Definition:
Solution:
boolean test_and_set (boolean
*target)
do {
while (test_and_set(&lock))
{
; /* do nothing */
boolean rv = *target;
/* critical section */
*target = TRUE;
lock = false;
return rv;
}
Operating System Concepts – 9th Edition
/* remainder section */
} while (true);
5.22
Silberschatz, Galvin and Gagne ©2013
22
11

12.

10/8/2026
compare_and_swap()
Definition:
int compare_and_swap(int *value, int
expected, int new_value) {
Shared Boolean variable lock initialized to FALSE; Each
process has a local Boolean variable key
Solution:
do {
while (compare_and_swap(&lock, 0,
1) != 0)
int temp = *value;
if (*value == expected)
; /* do nothing */
*value = new_value;
/* critical section */
return temp;
lock = 0;
}
/* remainder section */
} while (true);
Silberschatz, Galvin and Gagne ©2013
5.23
Operating System Concepts – 9th Edition
23
Atomic Variables
Atomic instructions are used to build atomic variables: updates (e.g., increment)
happen as one indivisible step
C11 <stdatomic.h>, C++ std::atomic, Java AtomicInteger; Python has
none – use a Lock
#include <stdio.h>
#include <stdatomic.h>
#include <pthread.h>
atomic_int counter = 0;
/* C11 atomic variable */
void *worker(void *arg) {
for (int i = 0; i < 100000; i++)
atomic_fetch_add(&counter, 1);
return NULL;
}
/* one indivisible step */
int main(void) {
pthread_t t1, t2;
pthread_create(&t1, NULL, worker, NULL);
pthread_create(&t2, NULL, worker, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("counter = %d\n", atomic_load(&counter));
return 0;
}
Operating System Concepts – 9th Edition
5.24
/* 200000 */
Silberschatz, Galvin and Gagne ©2013
24
12

13.

10/8/2026
acquire() and release()
acquire() {
while (!available)
; /* busy wait */
available = false;;
}
Boolean variable indicating if lock is available or not
release() {
available = true;
}
Calls to acquire() and release() must be atomic
do {
acquire lock
Usually implemented via hardware atomic
instructions
critical section
release lock
remainder section
} while (true);
But this solution requires busy waiting
This lock therefore called a spinlock
5.25
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
25
Mutex Locks in Practice
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&mutex);
counter++;
pthread_mutex_unlock(&mutex);
/* acquire the lock */
/* critical section */
/* release the lock */
C: Practice 1, Ex. 7 (pthread_race.c)
lock = threading.Lock()
def increment(n):
global counter
for _ in range(n):
with lock:
value = counter
work()
counter = value + 1
# acquire() ... release()
# now always 800000
The mutex is the door handle of the
phone booth: only the person holding
it uses the phone
Python: the fix for “Race Condition in Python”
Operating System Concepts – 9th Edition
5.26
Silberschatz, Galvin and Gagne ©2013
26
13

14.

10/8/2026
Finding Races: ThreadSanitizer
DEMO
Races are timing-dependent: a test can pass 1000 times and fail on the 1001st. Let a tool
find them
Compile pthread_race.c without the mutex using -fsanitize=thread and run it:
$ gcc -g -fsanitize=thread pthread_race.c -o race -pthread
$ ./race
WARNING: ThreadSanitizer: data race (pid=247)
Read of size 4 at 0x55fcffbc3014 by thread T2:
#0 deposit pthread_race.c:8
Previous write of size 4 at 0x55fcffbc3014 by thread T1:
#0 deposit pthread_race.c:8
Location is global 'shared_balance' of size 4
SUMMARY: ThreadSanitizer: data race pthread_race.c:8 in deposit
It names the variable, the line and the threads involved. With the mutex back, the warning
disappears
Alternatives: valgrind --tool=helgrind ./race; in Go: go run -race
5.27
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
27
Semaphore
In 1965, Dijkstra proposed a new and very significant technique for managing concurrent
processes by using the value of a simple integer variable to synchronize the progress of
interacting processes.
Synchronization tool that does not require busy waiting
Semaphore S – integer variable
Two standard operations modify S: wait() and signal()
Originally called P() and V()
Less complicated
Can only be accessed via two indivisible (atomic) operations
wait (S) {
while (S <= 0)
; // busy wait
S--;
}
signal (S) {
S++;
}
Operating System Concepts – 9th Edition
5.28
Silberschatz, Galvin and Gagne ©2013
28
14

15.

10/8/2026
Exercises
1. Statement S1 in thread T1 must run before S2 in thread
T2. Which semaphore do you need, what is its initial value,
and where do you call wait() and signal()?
2. Nightclub: the club holds at most N people; a bouncer lets
someone in only when someone leaves. Model it with one
semaphore.
3. What happens if a thread calls wait(mutex) twice in a
row? And signal(mutex) before wait(mutex)?
Answer: 1. One semaphore synch = 0: T1 runs S1 then signal(synch); T2
calls wait(synch) then S2.
2. One counting semaphore initialized to N: wait() to enter, signal() to leave.
3. Two wait(mutex): the thread blocks on itself (deadlock). signal() before
wait(): two threads can be in the critical section (no mutual exclusion).
A counting semaphore is like a nightclub
with a bouncer
Operating System Concepts – 9th Edition
5.29
Silberschatz, Galvin and Gagne ©2013
29
Semaphore Usage
Counting semaphore – integer value can range over an unrestricted domain
Binary semaphore – integer value can range only between 0 and 1
Can implement a counting semaphore S as a binary semaphore
Can solve various synchronization problems
Consider P1 and P2 that require S1 to happen before S2
Then a mutex lock
P1:
S1;
signal(synch);
P2:
wait(synch);
S2;
Operating System Concepts – 9th Edition
5.30
Silberschatz, Galvin and Gagne ©2013
30
15

16.

10/8/2026
Activity: Order Three Threads
ACTIVITY
The threads are started in the order C, B, A. Add only semaphores so that the output is
always A B C
import threading
# 1) create your semaphores here: how many? initial value? Work in pairs, 10 minutes
Run it 5 times: is the order always
correct?
Bonus: make the order C B A
without moving the prints
def a():
print("A")
def b():
print("B")
def c():
print("C")
ts = [threading.Thread(target=f) for f in (c, b, a)]
for t in ts: t.start()
for t in ts: t.join()
Operating System Concepts – 9th Edition
5.31
Answer: two semaphores, both 0:
a: print; s_ab.release()
b: s_ab.acquire(); print;
s_bc.release()
c: s_bc.acquire(); print
Silberschatz, Galvin and Gagne ©2013
31
Semaphore Implementation
Must guarantee that no two processes can execute wait() and signal() on the same semaphore at
the same time
Thus, implementation becomes the critical section problem where the wait and signal code are placed in
the critical section
Could now have busy waiting in critical section implementation
But implementation code is short
Little busy waiting if critical section rarely occupied
Note that applications may spend lots of time in critical sections and therefore this is not a good solution
Operating System Concepts – 9th Edition
5.32
Silberschatz, Galvin and Gagne ©2013
32
16

17.

10/8/2026
Semaphore Without Busy Waiting
With each semaphore there is an associated waiting
queue
Each entry in a waiting queue has two data items:
value (of type integer)
pointer to next record in the list
typedef struct{
int value;
struct process *list;
} semaphore;
wait(semaphore *S) {
S->value--;
Two operations:
block – place the process invoking the
operation on the appropriate waiting queue
if (S->value < 0) {
add this process to S->list;
wakeup – remove one of processes in the
waiting queue and place it in the ready queue
}
block();
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
5.33
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
33
Semaphores in Practice
#include <semaphore.h>
sem_t sem;
sem_init(&sem, 0, 2);
sem_wait(&sem);
/* ... */
sem_post(&sem);
/* 0 = shared by threads, value 2 */
/* wait(): at most 2 threads inside */
/* signal() */
POSIX unnamed semaphore (C, Linux)
club = threading.Semaphore(3)
# capacity: 3 people inside
def person(i):
print(f"{i} wants to enter")
with club:
# acquire() ... release()
print(f"{i} is in!")
time.sleep(random.uniform(0.5, 1.5))
print(f"{i} leaves")
Python: the nightclub with threading.Semaphore
Operating System Concepts – 9th Edition
5.34
Silberschatz, Galvin and Gagne ©2013
34
17

18.

10/8/2026
Quick Quiz: Locks and Semaphores
QUIZ
1. A spinlock is a good choice when …
2. A semaphore initialized to 0 is typically used for …
B) ordering / signalling
C) counting free buffer slots
A) the lock was free and now I hold it
the lock was released
B) the lock is busy
C) an error
D)
4. Which is not a requirement for a critical-section solution?
A) mutual exclusion
D) nothing
3. compare_and_swap(&lock, 0, 1) returns 0. This means …
A) the critical section is very short, on a multicore CPU B) the system has
one core C) the critical section waits for disk I/O D) never
A) mutual exclusion B) progress
thread always goes first
C) bounded waiting
D) the fastest
5. In CPython, the GIL …
A) makes counter += 1 thread-safe B) does not protect your own data
C) replaces threading.Lock D) only exists on Windows
Answers: 1 A 2 B 3 A 4 D 5 B
Silberschatz, Galvin and Gagne ©2013
5.35
Operating System Concepts – 9th Edition
35
Deadlock and Starvation
Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of
the waiting processes
Let S and
Q be two semaphores initialized to 1
P0
P1
wait(S);
wait(Q);
wait(Q);
wait(S);
.
.
signal(S);
signal(Q);
signal(Q);
signal(S);
Starvation – indefinite blocking
Priority Inversion – Scheduling problem when lower-priority process holds a lock needed by higherpriority process
A process may never be removed from the semaphore queue in which it is suspended
Solved via priority-inheritance protocol
Operating System Concepts – 9th Edition
5.36
Silberschatz, Galvin and Gagne ©2013
36
18

19.

10/8/2026
Priority Inversion
Three tasks: L (low), M (medium), H (high priority)
L holds a lock that H needs → H waits for L
M preempts L → H now indirectly waits for M, a lower-priority task
Mars Pathfinder rover (1997): a high-priority bus-management task waited
too long on a lock held by a low-priority task
A watchdog timer detected the missed deadline and reset the whole system –
again and again
Solution: priority inheritance – L temporarily runs with H’s priority while it
holds the lock
Enabled on Pathfinder by a remote software update; POSIX:
PTHREAD_PRIO_INHERIT
Operating System Concepts – 9th Edition
5.37
Silberschatz, Galvin and Gagne ©2013
37
Real-World Failures
REAL WORLD
Therac-25 radiation therapy machine (1985–1987)
A race condition in the control software, triggered when operators edited the treatment
data quickly
Six accidents with massive radiation overdoses; several patients died. Hardware safety
interlocks had been replaced by software
Northeast blackout (USA and Canada, August 2003)
A race condition stalled the alarm system of the control-room software, silently
Operators got no warnings while lines failed; about 55 million people lost power
Mars Pathfinder (1997): priority inversion – previous slide
Lesson: these bugs are rare and timing-dependent, so testing alone does not find
them. Use simple, proven patterns and tools
Operating System Concepts – 9th Edition
5.38
Silberschatz, Galvin and Gagne ©2013
38
19

20.

10/8/2026
Classical Problems of Synchronization
Classical problems used to test newly-proposed synchronization schemes
Bounded-Buffer Problem
Readers and Writers Problem
Dining-Philosophers Problem
5.39
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
39
Bounded-Buffer Problem
n buffers, each can hold one item
Semaphore mutex initialized to the value 1
Semaphore full initialized to the value 0
Semaphore empty initialized to the value n
Operating System Concepts – 9th Edition
5.40
Silberschatz, Galvin and Gagne ©2013
40
20

21.

10/8/2026
Producer and Consumer
The structure of the producer process
do {
The structure of the consumer process
do {
...
/* produce an item in
next_produced */
wait(full);
wait(mutex);
...
/* remove an item from buffer to
next_consumed */
...
wait(empty);
wait(mutex);
...
...
/* add next produced to the buffer
signal(mutex);
signal(empty);
*/
...
/* consume the item in next consumed */
...
signal(mutex);
...
} while (true);
signal(full);
} while (true);
Operating System Concepts – 9th Edition
5.41
Silberschatz, Galvin and Gagne ©2013
41
Predict: Swap Two wait() Calls
PREDICT
The producer now calls wait(mutex) before wait(empty). The consumer is
unchanged
do {
/* produce an item in next_produced */
wait(mutex);
/* swapped */
wait(empty);
/* swapped */
/* add next_produced to the buffer */
signal(mutex);
signal(full);
} while (true);
Operating System Concepts – 9th Edition
5.42
What happens when the
buffer becomes full?
And when it is empty?
Answer: Full buffer → deadlock. The
producer sleeps in wait(empty) while
holding mutex; the consumer blocks on
wait(mutex), so nobody frees a slot.
Empty buffer: no problem for the
producer.
Silberschatz, Galvin and Gagne ©2013
42
21

22.

10/8/2026
Bounded Buffer in Python
import threading, collections
N = 5
buffer = collections.deque()
mutex = threading.Semaphore(1)
empty = threading.Semaphore(N)
full = threading.Semaphore(0)
def producer():
for item in range(10):
empty.acquire()
mutex.acquire()
buffer.append(item)
mutex.release()
full.release()
def consumer():
for _ in range(10):
full.acquire()
mutex.acquire()
item = buffer.popleft()
mutex.release()
empty.release()
print("consumed", item)
# free slots
# filled slots
# wait(empty)
# wait(mutex)
Same structure as the book’s
producer and consumer.
In real code use
queue.Queue(maxsize=N):
it is a ready-made bounded
buffer (Practice 1, Ex. 13)
# signal(mutex)
# signal(full)
# wait(full)
# wait(mutex)
# signal(mutex)
# signal(empty)
threading.Thread(target=producer).start()
consumer()
Operating System Concepts – 9th Edition
5.43
Silberschatz, Galvin and Gagne ©2013
43
Readers-Writers Problem
A data set is shared among a number of concurrent processes
Readers – only read the data set; they do not perform any updates
Writers – can both read and write
Problem – allow multiple readers to read at the same time
Only one single writer can access the shared data at the same time
Several variations of how readers and writers are treated – all involve priorities
Shared Data
Data set
Semaphore rw_mutex initialized to 1
Semaphore mutex initialized to 1
Integer read_count initialized to 0
Operating System Concepts – 9th Edition
5.44
Silberschatz, Galvin and Gagne ©2013
44
22

23.

10/8/2026
Writer and Reader
The structure of a writer process
The structure of a reader process
do {
do {
wait(mutex);
read count++;
if (read_count == 1)
wait(rw_mutex);
...
/* writing is performed */
wait(rw_mutex);
signal(mutex);
...
...
signal(rw_mutex);
} while (true);
/* reading is performed */
...
wait(mutex);
read count--;
if (read_count == 0)
signal(rw_mutex);
signal(mutex);
} while (true);
Operating System Concepts – 9th Edition
5.45
Silberschatz, Galvin and Gagne ©2013
45
Readers-Writers Problem Variations
First variation – no reader kept waiting unless writer has permission to use shared
object
Second variation – once writer is ready, it performs write ASAP
Both may have starvation leading to even more variations
Problem is solved on some systems by kernel providing reader-writer locks
POSIX: pthread_rwlock_rdlock(), pthread_rwlock_wrlock(),
pthread_rwlock_unlock()
C++17: std::shared_mutex; Java: ReentrantReadWriteLock; Python: no built-in
RW lock
Operating System Concepts – 9th Edition
5.46
Silberschatz, Galvin and Gagne ©2013
46
23

24.

10/8/2026
Dining-Philosophers Problem
Philosophers spend their lives thinking and eating
Don’t interact with their neighbors, occasionally try to pick up 2 chopsticks (one at a time) to eat from bowl
Need both to eat, then release both when done
In the case of 5 philosophers
Shared data
Bowl of rice (data set)
Semaphore chopstick [5] initialized to 1
Operating System Concepts – 9th Edition
5.47
Silberschatz, Galvin and Gagne ©2013
47
Dining Philosophers: Deadlock
Every philosopher picks up the left chopstick at the same time → nobody can get
the right one → deadlock
Operating System Concepts – 9th Edition
5.48
Silberschatz, Galvin and Gagne ©2013
48
24

25.

10/8/2026
Dining-Philosophers Problem Algorithm
The structure of Philosopher i:
do
{
wait (chopstick[i] );
wait (chopStick[ (i + 1) % 5] );
//
eat
Answer: Deadlock. If all five pick up their
left chopstick at the same time, each waits
forever for the right one. Remedies: next
slides.
signal (chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
//
think
} while (TRUE);
What is the problem with this algorithm?
Operating System Concepts – 9th Edition
5.49
Silberschatz, Galvin and Gagne ©2013
49
Dining Philosophers: Remedies
Allow at most four philosophers at the table at the same time (a counting
semaphore initialized to 4)
Allow a philosopher to pick up chopsticks only if both are available (pick
them up inside a critical section)
Asymmetric solution: odd philosophers pick up left then right, even
philosophers right then left
A deadlock-free solution may still allow starvation (see the monitor solution
next)
Operating System Concepts – 9th Edition
5.50
Silberschatz, Galvin and Gagne ©2013
50
25

26.

10/8/2026
Spot the Bug: Bank Transfer
SPOT THE BUG
An AI assistant wrote a thread-safe money transfer. Two threads transfer in opposite
directions. Run it: it never finishes. Why? Fix it
class Account:
def __init__(self, id, balance):
self.id, self.balance = id, balance
self.lock = threading.Lock()
def transfer(src, dst, amount):
with src.lock:
with dst.lock:
src.balance -= amount
dst.balance += amount
Hint: compare with
the dining
philosophers
# lock the source account
# then the destination account
Answer: Deadlock: t1 holds
a.lock and waits for b; t2
holds b.lock and waits for a.
Fix: always lock the account
with the smaller id first.
def many(src, dst):
for _ in range(100_000):
transfer(src, dst, 1)
a, b = Account(1, 1000), Account(2, 1000)
t1 = threading.Thread(target=many, args=(a, b))
t2 = threading.Thread(target=many, args=(b, a))
t1.start(); t2.start(); t1.join(); t2.join()
Operating System Concepts – 9th Edition
5.51
# a -> b
# b -> a
Silberschatz, Galvin and Gagne ©2013
51
Problems with Semaphores
Incorrect use of semaphore operations:
signal (mutex) …. wait (mutex)
wait (mutex) … wait (mutex)
Omitting of wait (mutex) or signal (mutex) (or both)
Deadlock and starvation
Operating System Concepts – 9th Edition
5.52
Silberschatz, Galvin and Gagne ©2013
52
26

27.

10/8/2026
Activity: The Deadlock Empire
ACTIVITY
A free browser game: you are the scheduler. Choose which thread runs the
next line and try to break the program
In pairs, 20 minutes:
deadlockempire.github.io – works on a laptop or a phone, no installation
Tutorial, then the levels on unsynchronized code (find the race)
Locks and semaphores levels (find the deadlock or the hole in the protection)
If you finish early: condition variables
The code is C#-like, but it reads like the C and Python we use
At the end: each pair explains its hardest level to the class
Operating System Concepts – 9th Edition
5.53
Silberschatz, Galvin and Gagne ©2013
53
Monitors
A high-level abstraction that provides a convenient and effective mechanism for
process synchronization
Abstract data type, internal variables only accessible by code within the procedure
Only one process may be active within the monitor at a time
But not powerful enough to model some synchronization schemes
monitor monitor-name
{
// shared variable declarations
procedure P1 (…) { …. }
procedure Pn (…) {……}
Initialization code (…) { … }
}
}
Operating System Concepts – 9th Edition
5.54
Silberschatz, Galvin and Gagne ©2013
54
27

28.

10/8/2026
Schematic view of a Monitor
5.55
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
55
Condition Variables
condition x, y;
Two operations on a condition variable:
– a process that invokes the operation is suspended until x.signal()
x.wait()
x.signal() – resumes one of processes (if any) that invoked x.wait()
If no x.wait() on the variable, then it has no effect on the variable
Operating System Concepts – 9th Edition
5.56
Silberschatz, Galvin and Gagne ©2013
56
28

29.

10/8/2026
Monitor with Condition Variables
Operating System Concepts – 9th Edition
5.57
Silberschatz, Galvin and Gagne ©2013
57
Condition Variables Choices
If process P invokes x.signal(), with Q in x.wait() state, what should happen next?
If Q is resumed, then P must wait
Options include
Signal and wait – P waits until Q leaves monitor or waits for another condition
Signal and continue – Q waits until P leaves the monitor or waits for another condition
Both have pros and cons – language implementer can decide
Monitors implemented in Concurrent Pascal compromise
Implemented in other languages including Mesa, C#, Java
P executing signal immediately leaves the monitor, Q is resumed
Operating System Concepts – 9th Edition
5.58
Silberschatz, Galvin and Gagne ©2013
58
29

30.

10/8/2026
Condition Variables in Practice
pthread_mutex_lock(&mutex);
while (!data_ready)
/* always re-check in a loop */
pthread_cond_wait(&ready, &mutex); /* releases mutex while waiting */
/* ... use the data ... */
pthread_mutex_unlock(&mutex);
/* other thread */
pthread_mutex_lock(&mutex);
data_ready = 1;
pthread_cond_signal(&ready);
pthread_mutex_unlock(&mutex);
cond = threading.Condition()
# a lock + a waiting queue
with cond:
cond.wait_for(lambda: slices > 0)
slices -= 1
# student
# while not ...: wait()
with cond:
slices = 4
cond.notify_all()
# pizza delivery
A class that uses one lock + condition variables for all its methods is a monitor (Java: synchronized,
wait(), notify())
Operating System Concepts – 9th Edition
5.59
Silberschatz, Galvin and Gagne ©2013
59
Spot the Bug: “if” or “while”?
SPOT THE BUG
An AI assistant wrote this consumer. Two consumers wait, one item arrives:
items = []
cond = threading.Condition()
def consumer(name):
with cond:
if not items:
cond.wait()
item = items.pop()
print(name, "got", item)
Real run:
IndexError: pop from
empty list
# AI wrote "if"
Why? Fix it with one word.
Answer: both consumers wake up;
the first takes the item, the second
pops from an empty list.
Fix: `while` not items:
cond.wait()
# ... both consumers are waiting ...
with cond:
items.append(42)
# ONE item ...
cond.notify_all()
# ... but BOTH consumers wake up
Operating System Concepts – 9th Edition
5.60
Silberschatz, Galvin and Gagne ©2013
60
30

31.

10/8/2026
Solution to Dining Philosophers
monitor DiningPhilosophers
{
enum { THINKING; HUNGRY, EATING) state [5] ;
condition self [5];
void pickup (int i) {
state[i] = HUNGRY;
test(i);
if (state[i] != EATING) self [i].wait;
}
void putdown (int i) {
state[i] = THINKING;
// test left and right neighbors
test((i + 4) % 5);
test((i + 1) % 5);
}
Operating System Concepts – 9th Edition
5.61
Silberschatz, Galvin and Gagne ©2013
61
Solution to Dining Philosophers (Cont.)
void test (int i) {
if ( (state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING) ) {
state[i] = EATING ;
self[i].signal () ;
}
}
initialization_code() {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
}
Operating System Concepts – 9th Edition
5.62
Silberschatz, Galvin and Gagne ©2013
62
31

32.

10/8/2026
Solution to Dining Philosophers (Cont.)
Each philosopher i invokes the operations pickup() and putdown() in the following sequence:
DiningPhilosophers.pickup(i);
EAT
DiningPhilosophers.putdown(i);
No deadlock, but starvation is possible
5.63
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
63
Monitor Implementation Using Semaphores
Variables
semaphore mutex; // (initially
semaphore next;
// (initially
int next_count = 0;
= 1)
= 0)
Each procedure F will be replaced by
wait(mutex);
…
body of F;
…
if (next_count > 0)
signal(next)
else
signal(mutex);
Mutual exclusion within a monitor is ensured
Operating System Concepts – 9th Edition
5.64
Silberschatz, Galvin and Gagne ©2013
64
32

33.

10/8/2026
Monitor Implementation – Condition Variables
For each condition variable x, we have:
semaphore x_sem; // (initially
int x_count = 0;
= 0)
The operation x.wait can be implemented as:
x_count++;
if (next_count > 0)
signal(next);
else
signal(mutex);
wait(x_sem);
x_count--;
Operating System Concepts – 9th Edition
5.65
Silberschatz, Galvin and Gagne ©2013
65
Monitor Implementation (Cont.)
The operation x.signal can be implemented as:
if (x_count > 0) {
next_count++;
signal(x_sem);
wait(next);
next_count--;
}
Operating System Concepts – 9th Edition
5.66
Silberschatz, Galvin and Gagne ©2013
66
33

34.

10/8/2026
Resuming Processes within a Monitor
If several processes queued on condition x, and x.signal() executed, which should be resumed?
FCFS frequently not adequate
conditional-wait construct of the form x.wait(c)
Where c is priority number
Process with lowest number (highest priority) is scheduled next
Operating System Concepts – 9th Edition
5.67
Silberschatz, Galvin and Gagne ©2013
67
A Monitor to Allocate Single Resource
monitor ResourceAllocator
{
boolean busy;
condition x;
void acquire(int time) {
if (busy)
x.wait(time);
busy = TRUE;
}
void release() {
busy = FALSE;
x.signal();
}
initialization code() {
busy = FALSE;
}
}
Operating System Concepts – 9th Edition
5.68
Silberschatz, Galvin and Gagne ©2013
68
34

35.

10/8/2026
Windows Synchronization
Uses interrupt masks to protect access to global resources on uniprocessor systems
Uses spinlocks on multiprocessor systems
Spinlocking-thread will never be preempted
Also provides dispatcher objects in user-land which may act as mutexes,
semaphores, events, and timers
Events: an event acts much like a condition variable
Timers notify one or more threads when time expired
Dispatcher objects either signaled-state (object available) or non-signaled state (thread
will block)
Lighter user-mode primitives: critical sections, slim reader-writer (SRW) locks,
condition variables
5.69
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
69
Linux Synchronization
Linux:
Prior to kernel Version 2.6, disables interrupts to implement short critical sections
Version 2.6 and later, fully preemptive
Linux kernel provides:
atomic integers (atomic_t), spinlocks, mutex locks, semaphores
reader-writer versions of spinlocks and semaphores
RCU (read-copy-update) for read-mostly data
On single-cpu system, spinlocks replaced by enabling and disabling kernel preemption
User space: futex (fast user-space mutex) – an uncontended
pthread_mutex_lock() needs no system call
Operating System Concepts – 9th Edition
5.70
Silberschatz, Galvin and Gagne ©2013
70
35

36.

10/8/2026
Pthreads Synchronization
Pthreads API is OS-independent
It provides:
mutex locks: pthread_mutex_t
condition variables: pthread_cond_t
read-write locks: pthread_rwlock_t
spinlocks: pthread_spinlock_t
barriers: pthread_barrier_t
POSIX semaphores (<semaphore.h>)
named: sem_open() – can be shared by unrelated processes
unnamed: sem_init() – shared by threads (or by related processes)
Silberschatz, Galvin and Gagne ©2013
5.71
Operating System Concepts – 9th Edition
71
Synchronization in Python
threading
Book concept
Typical use
Lock
mutex lock
protect a critical section: with lock:
RLock
reentrant mutex
same thread may acquire it again
Semaphore /
BoundedSemaphore
counting semaphore
limit concurrent access (nightclub)
Condition
condition variable
wait_for(predicate), notify(), notify_all()
Event
one-shot flag
cancellation: set(), is_set(), wait()
Barrier
barrier
all N threads meet before going on
queue.Queue
bounded buffer
producer–consumer, no explicit locks
Same API in multiprocessing (between processes) and async versions in asyncio. The
GIL does not replace these tools.
Operating System Concepts – 9th Edition
5.72
Silberschatz, Galvin and Gagne ©2013
72
36

37.

10/8/2026
Alternative Approaches
Transactional memory: a block of code runs as an atomic transaction; the
system, not the programmer, guarantees atomicity
OpenMP: #pragma omp critical and reduction(+:sum) –
synchronization handled by the compiler
Functional languages (Erlang, Scala, Haskell): immutable data, so no shared
state to protect
Message passing instead of shared memory
Go: “do not communicate by sharing memory; share memory by communicating”
(channels)
Python: queue.Queue, multiprocessing.Pipe
OpenMP and implicit threading: Ch. 4, slides 4.37–4.52
5.73
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
73
Rust: No Data Races
In Rust the data lives inside the mutex: you can reach it only through lock()
use std::sync::{Arc, Mutex};
use std::thread;
fn main() {
let counter = Arc::new(Mutex::new(0));
// data INSIDE the lock
let mut handles = vec![];
for _ in 0..4 {
let c = Arc::clone(&counter);
handles.push(thread::spawn(move || {
for _ in 0..100_000 {
*c.lock().unwrap() += 1;
// only via lock()
}
}));
}
for h in handles { h.join().unwrap(); }
println!("counter = {}", *counter.lock().unwrap());
// 400000
}
Sharing a plain counter between threads does not compile: error[E0373]: closure may outlive the
current function, but it borrows counter
Rust is used in the Linux kernel since version 6.1 (2022), in Android and in Windows
Operating System Concepts – 9th Edition
5.74
Silberschatz, Galvin and Gagne ©2013
74
37

38.

10/8/2026
Exercises 1–2: Counters and Order
EXERCISE
1. Fun with counters. Two threads share counter = 0: one adds 1, the other subtracts 1,
100,000 times each. Do you get 0? Then protect the update with a mutex and compare the run
time. Is locking free?
2. Print order. Thread T1 prints * N times, T2 prints $ N times (every 100 ms). Make sure all
* come before any $. Then reverse the order. Which part of the code is the critical section?
Answer: 1. Without the lock the result is rarely 0 and changes every run; with the lock it is always 0 but
slower (a lock/unlock on every iteration).
2. A mutex alone does not order threads: use a semaphore s = 0. T2 calls wait(s) before its loop, T1
calls signal(s) after its loop. Reverse: swap the roles.
Operating System Concepts – 9th Edition
5.75
Silberschatz, Galvin and Gagne ©2013
75
Exercises 3–4: Booth and Pair
EXERCISE
3. Phone booth. Many people run to one phone booth. The first who grabs the door handle
talks for a random time; the others wait; there is no queue. Write it with threads: what are the
thread, the mutex, the lock and the resource?
4. Shared pair. a = b = 1. T1 runs a += 1; b += 1, T2 runs a *= 2; b *= 2. Which
final values of (a, b) are possible without a lock? With one lock around each thread’s two
lines?
Answer: 3. Thread = person, mutex = door handle, lock = hand on the handle, resource = phone. No queue
→ someone may wait forever (starvation).
4. Without a lock: (3,3), (4,4), (3,4), (4,3) – a ≠ b breaks the invariant. With the lock: only (4,4) or (3,3).
Operating System Concepts – 9th Edition
5.76
Silberschatz, Galvin and Gagne ©2013
76
38

39.

10/8/2026
Exercises 5–6: Ping-Pong, Club
EXERCISE
5. Ping-pong. Two threads loop forever: sleep(1); print("ping") and sleep(1);
print("pong"). Why can the output be “ping ping pong”? Fix it with semaphores so they
strictly alternate.
6. Nightclub. The club holds at most 3 people; 5 people (threads) arrive. Print “i wants to
enter”, “i is in!”, “i is leaving”. At most 3 may be inside at any time.
Answer: 5. sleep() does not order threads. s_ping = 1, s_pong = 0; ping: wait(s_ping), print,
signal(s_pong); pong: wait(s_pong), print, signal(s_ping).
6. club = Semaphore(3): wait(club) before “is in”, signal(club) after “is leaving”.
Operating System Concepts – 9th Edition
5.77
Silberschatz, Galvin and Gagne ©2013
77
Exercise 7: Precedence Graph
EXERCISE
Nine threads A–I print their name in the order of the graph: a
thread may start only after all threads with an arrow into it
B, C, D may print in any order among themselves; G only
after E and F; I last
Use only semaphores. How many do you need, and with
which initial value?
A
/ | \
B C D
| / \ |
| E F |
| \ / |
| G
H
\ | /
I
Answer: one semaphore per arrow, initialized to 0. Each thread
calls wait() on all its incoming arrows, prints, then signal() on
all its outgoing arrows (11 semaphores). Sample run: ABDHCFEGI.
Operating System Concepts – 9th Edition
5.78
Silberschatz, Galvin and Gagne ©2013
78
39

40.

10/8/2026
Challenge Exercises 8–10
EXERCISE
8. Sleeping barber. A shop has one barber and n waiting chairs. No customers → the barber
sleeps; a customer wakes him up; if all chairs are taken, the customer leaves
9. Unisex bathroom. Men and women may never be inside at the same time, and at most 3
people are inside
10. Dining philosophers. Write a program for 5 philosophers with no deadlock and no
starvation
Answer: 8. Semaphores customers (0), barber (0), mutex (1) + a counter of waiting customers.
9. “Lightswitch”: the first man locks empty, the last man unlocks it (same for women) + Semaphore(3).
10. Monitor solution (pickup/putdown with states) or the asymmetric order + a fair lock.
Silberschatz, Galvin and Gagne ©2013
5.79
Operating System Concepts – 9th Edition
79
Check Your Understanding
QUIZ
1. counter++ on a shared variable needs protection even on one core
because …
A) of the CPU cache B) a thread can be preempted between load and store
C) of the GIL D) the compiler forbids it
2. The producer calls wait(mutex) before wait(empty). When the buffer
is full …
3. wait() on a condition variable must be inside a …
A) if
B) deadlock
B) while loop
C) busy waiting
C) for loop
D) items are lost
D) try block
4. Two threads lock two accounts in opposite order. The risk is …
A) it still works
A) a race condition
B) a deadlock
C) priority inversion
D) nothing
5. Which tool shows the exact line of a data race in a C program?
A) gdb
B) strace
C) ThreadSanitizer
D) htop
Answers: 1 B 2 B 3 B 4 B 5 C
Operating System Concepts – 9th Edition
5.80
Silberschatz, Galvin and Gagne ©2013
80
40

41.

10/8/2026
Further Reading and Practice
READ & PRACTICE
Book: Silberschatz, Galvin, Gagne – Operating System Concepts, 10th ed.,
Chapters 6–7
Free online book: Operating Systems: Three Easy Pieces (OSTEP) –
pages.cs.wisc.edu/~remzi/OSTEP
Ch. 28 Locks, 29 Lock-based Data Structures, 30 Condition Variables, 31
Semaphores, 32 Common Concurrency Problems
Simulator x86.py: run peterson.s and test-and-set.s and watch the
interleavings
Game: The Deadlock Empire – deadlockempire.github.io
Exercises 1–10 at the end of this chapter; Assignment 5 (pizza night)
Tools: gcc -fsanitize=thread, valgrind --tool=helgrind
Operating System Concepts – 9th Edition
5.81
Silberschatz, Galvin and Gagne ©2013
81
End of Chapter 5
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
82
41