Process Synchronization

Process Synchronization
The 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 some processes

wish to enter their critical sections, then only those processes that are not
executing in their remainder sections can participate in deciding which will enter its
critical section next, and this selection cannot be postponed indefinitely.

3. Bounded waiting. There exists a bound, or limit, 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.
Peterson’s Solution

We now prove that this solution is correct.

We need to show that:

- Mutual exclusion is preserved.

- The progress requirement is
satisfied.
- The bounded-waiting requirement is
met.
Memory Barriers
1. Strongly ordered, where a memory modification on one processor is
immediately visible to all other processors.

2. Weakly ordered, where modifications to memory on one processor may not be

immediately visible to other processors.
test_and_set()
test_and_set()

Property Description

Mutual Exclusion Achieved (only one process can set lock to true first)

Progress As soon as lock is false, one waiting process can enter.

Bounded Waiting Not guaranteed; a process could theoretically spin forever if

unlucky

Busy Waiting Yes — wastes CPU time in the while loop.

compare_and_swap()
compare_and_swap()

Property Description

Mutual Exclusion Yes — only one process sets lock to 1 successfully.

Progress Yes — as soon as lock = 0, one waiting process will enter.

Bounded Waiting Not guaranteed; a process could theoretically spin forever if

unlucky

Busy Waiting Yes — still spins in while loop.

Atomic variable
Atomic variables can be used in to ensure mutual exclusion in situations where
there may be a data race on a single variable while it is being updated, as when a
counter is incremented.

- Counter
- Integer
Mutex Locks
operating-system designers build higher-level software tools to solve the
critical-section problem. The simplest of these tools is the mutex lock.
acquire() and release() functions
Semaphores
a more robust tool that can behave similarly to a mutex lock but can also provide
more sophisticated ways for processes to synchronize their activities.

A semaphore S is an integer variable that, apart from initialization, is accessed

only through two standard atomic operations: wait() and signal().
Semaphore Usage
In process P1, we insert the statements:

In process P2, we insert the statements:

Mechanism Allows How Wait Type Managed By
Many states?

Spinlock 1 Busy-wait CPU

(hardware)

Mutex 1 Blocking (sleep) OS kernel

Semaphore N Blocking (sleep) OS kernel

Monitors: high-level language constructs
Although semaphores provide a convenient and effective mechanism for process
synchronization, using them incorrectly can result in timing errors that are difficult
to detect:

Examples:
Monitors
Monitors
Monitors
- High-level synchronization construct
- Mutual exclusion + condition synchronization
- Shared data, monitor procedures, condition variables
- Mutual Exclusion: Automatic — only one thread active inside
- Condition Variables: Allow waiting/signaling within the monitor
- Languages Supporting Monitors: Java, C#, Modula-3, Concurrent Pascal
The Bounded-Buffer Problem (Producer–Consumer
Problem)

- There’s a buffer (shared memory area) with limited size N.

- Producer threads generate data items and put them into the buffer.
- Consumer threads remove items from the buffer and process them.
- Synchronization is needed so that:
- Producers don’t add items when the buffer is full.
- Consumers don’t remove items when the buffer is empty.
Pseudocode for addressing Bounded-Buffer Problem
semaphore mutex = 1;

semaphore empty = N;

semaphore full = 0;
Initial states are empty = 3, full = 0, mutex = 1

buffer = [ _ , _ , _ ]

Step 1: Producer P1 produces an item

Action empty full mutex Buffer

P1: wait(empty) 2 0 1 [_,_,_]

P1: wait(mutex) 2 0 0 enters critical section

P1: insert_item(X1) 2 0 0 [ X1 , _ , _ ]

P1: signal(mutex) 2 0 1 leaves CS

P1: signal(full) 2 1 1 buffer now has one full slot

 Step 2: Producer P2 produces another item
current states are empty = 2, full = 1, mutex = 1

Action empty full mutex Buffer

P2: wait(empty) 1 1 1 [ X1 , _ , _ ]

P2: wait(mutex) 1 1 0 enters critical section

P2: 1 1 0 [ X1 , X2 , _ ]
insert_item(X2)

P2: signal(mutex) 1 1 1 leaves CS

P2: signal(full) 1 2 1 [ X1 , X2 , _ ]
 Step 3: Consumer C1 starts consuming
current states are empty = 1, full = 2, mutex = 1

Action empty full mutex Buffer

C1: wait(full) 1 1 1 checks full slot

C1: wait(mutex) 1 1 0 enters CS

C1: 1 1 0 [ _ , X2 , _ ]
remove_item(X1)

C1: signal(mutex) 1 1 1 leaves CS

C1: signal(empty) 2 1 1 one slot freed

 Step 4: Producer P1 produces another item
current states are empty = 2, full = 1, mutex = 1

Action empt full mutex Buffer

y

P1: wait(empty) 1 1 1 [ _ , X2 , _ ]

P1: wait(mutex) 1 1 0 enters CS

P1: insert_item(X3) 1 1 0 [ X3 , X2 , _ ]

P1: signal(mutex) 1 1 1 leaves CS

P1: signal(full) 1 2 1 [ X3 , X2 , _ ]
Step 5: Consumer C1 consumes again
current states are empty = 1, full = 2, mutex = 1

Action empty full mutex Buffer

C1: wait(full) 1 1 1 has full slot

C1: wait(mutex) 1 1 0 enters CS

C1: remove_item(X2) 1 1 0 [ X3 , _ , _ ]

C1: signal(mutex) 1 1 1 leaves CS

C1: signal(empty) 2 1 1 frees one slot

Readers–Writers Problem
A shared database (like a file or table):

- Readers only read the data.

- Writers modify the data.

We must ensure:

- No writer is writing while any reader is reading.

- Multiple readers can read simultaneously (no conflict).
- But only one writer can write at a time.
Pseudocode for addressing Readers–Writers Problem
Step 1: R2 starts reading
Initial states are readcount = 0, mutex = 1, wrt = 1

Step Action readcount mutex wrt Notes

1 R1 executes 0 0 1 enters mutex

wait(mutex)

2 R1 increments 1 0 1 first reader

readcount = 1

3 Since readcount == 1 0 0 locks writers

1, R1 executes
wait(wrt)

4 R1 executes 1 1 0 leaves mutex

signal(mutex)

Now R1 is reading, writers are blocked (wrt = 0).

Step 1: R2 starts reading

current states are readcount = 1, mutex = 1, wrt = 0

Step Action readcount mutex wrt Notes

5 R2 executes 1 0 0 enters mutex

wait(mutex)

6 R2 increments 2 0 0 not first reader, no

readcount = 2 wait(wrt)

7 R2 increments 2 1 0 leaves mutex

readcount = 2

Both R1 and R2 are reading.

Writers still blocked (wrt = 0).

Step 3: W1 tries to write
current states are readcount = 2, mutex = 1, wrt = 0

Step Action readcou mutex wrt Notes

nt

8 W1 2 1 0 must wait (blocked)

executes
wait(wrt)

Writer is blocked until all readers finish.

Step 4: R1 finishes reading

current states are readcount = 2, mutex = 1, wrt = 0

Step Action read mut wrt Notes

coun ex
t

9 R1 executes 2 0 0 enters mutex

wait(mutex)

10 R1 decrements 1 0 0 still one reader left

readcount = 1

11 No signal(wrt) (not 1 0 0 writers still blocked

last reader)

12 R1 executes 1 1 0 leaves mutex

signal(mutex)

R2 still reading; W1 still waiting.

Step 5: R2 finishes reading;

Current states are readcount = 1; mutex = 1; wrt = 0

Step Action read mut wrt Notes

cou ex
nt

13 R2 executes 1 0 0 enters mutex

wait(mutex)

14 R2 decrements 0 0 0 last reader

readcount = 0

15 Since readcount 0 0 1 writers unblocked

== 0, R2 executes
signal(wrt)

16 R2 executes 0 1 1 leaves mutex

signal(mutex)

No readers left — now W1 can proceed.

Step 6: W1 writes

current states are readcount = 0, mutex = 1, wrt = 1

Step Action readc mut wrt Notes

ount ex

17 W1 (previously 0 1 0 gains exclusive access

blocked) now
executes wait(wrt)

18 W1 writes data 0 1 0 critical section

19 W1 executes 0 1 1 releases lock

signal(wrt)

Writer done.

Now other readers/writers may proceed.

Dining-Philosophers Problem
- Five philosophers sit around a circular
table.
- Between each pair, there is one
chopstick.
- Each philosopher needs two chopsticks
to eat.
- Problem: prevent deadlock and
starvation.
Naive Solution (with Deadlock Risk)
- If all philosophers pick
their left chopstick at the
same time
- means: no one can get
the right one
- means: deadlock.
Avoiding Deadlock (One Common Fix)
Let one philosopher pick up chopsticks in reverse order:

Ensures asymmetry and avoids circular wait condition.

Several possible solutions
Several possible remedies to the deadlock problem are the following:

- Allow at most four philosophers to be sitting simultaneously at the table.

- Allow a philosopher to pick up her chopsticks only if both chopsticks are
available (to do this, she must pick them up in a critical section).
- Use an asymmetric solution—that is,an odd-numbered philosopher picks up
first her left chopstick and then her right chopstick, whereas an even-
numbered philosopher picks up her right chopstick and then her left chopstick.
Monitor Solution
Each philosopher must:

- Think for a while,

- Request to eat (only when both
chopsticks available),
- Release chopsticks when done.

We’ll use a state variable per philosopher

and condition variables to manage who
can eat.
Time Philosopher Action State Array (T=Thinking, Explanation
H=Hungry, E=Eating)

t0 0 HUNGRY HTTTT 0 can eat (no neighbors

eating)

t1 0 EATING ETTTT

t2 1 HUNGRY EHTTT 1 cannot eat (left neighbor 0

is eating)

t3 2 HUNGRY EHHTT 2 cannot eat (neighbor 1

HUNGRY, 0 EATING)

t4 0 puts down THHTT test(1) and test(4): now 1

can eat

t5 1 EATING TEHTT

t6 1 puts down TTHTT test(0) and test(2): now 2

can eat

t7 2 EATING TTETT
Deadlocks
- A set of blocked processes each holding a resource and waiting to acquire a
resource held by another process in the set.
- Example:
- System has 2 disk drives.
- P1 and P2 each hold one disk drive and each needs another one.
- Example:
- semaphores A and B, initialized to 1
Bridge Crossing Example

- Traffic only in one direction.

- Each section of a bridge can be viewed as a resource.
- If a deadlock occurs, it can be resolved if one car backs up (preempt resources and
rollback).
- Several cars may have to be backed up if a deadlock Occurs.
- Starvation is possible.
System Model

- Resource types R1, R2, . . ., Rm

- CPU cycles, memory space, I/O devices
- Each resource type Ri has Wi instances.
- Each process utilizes a resource as follows:
- Request
- Use
- release
Deadlock Characterization
- Mutual exclusion:
- Hold and wait:
- No preemption:
- Circular wait:
Example of a Resource Allocation Graph
Resource Allocation Graph With A Deadlock
Graph With A Cycle But No Deadlock
[Link]
nners/#basic-file-compression-tool