MODULE 3 — OPERATING SYSTEMS

Process Synchronization &

Deadlock
Comprehensive Study Notes — All Topics Covered

✓ Race Conditions & Critical Section Problem

✓ Peterson's Solution & Software Algorithms

✓ Semaphores: Binary, Counting — Theory & Examples

✓ Mutex Locks & Monitors

✓ Hardware Support: TSL, Swap, Memory Barriers

✓ Classic Problems: Producer-Consumer, Dining Philosophers, Readers-Writers

✓ Deadlock: Characterization, Prevention, Avoidance, Detection, Recovery

Duration: 12 Hours | Complete Theory + Code + Examples + Diagrams

Table of Contents

1. PROCESS SYNCHRONIZATION
1.1 Introduction & Overview
1.2 Types of Processes: Independent & Co-operative
1.3 Race Condition — Definition, Causes, Example
1.4 Critical Section — Structure & Purpose
1.5 Requirements for Synchronization (Mutual Exclusion, Progress, Bounded Waiting, Portability)
1.6 Software Solution Attempts (Attempt 1 & 2)

2. PETERSON'S SOLUTION
2.1 Algorithm & Shared Variables
2.2 Working Mechanism & Step-by-step Trace
2.3 Proof of Correctness
2.4 Advantages & Disadvantages

3. SEMAPHORES
3.1 Definition & Atomic Operations (wait/signal)
3.2 Binary Semaphore — Theory, Code & Full Example
3.3 Counting Semaphore — Theory, Code & Full Example
3.4 Semaphore vs Mutex Comparison
3.5 Advantages & Disadvantages

4. HARDWARE SUPPORT FOR SYNCHRONIZATION

4.1 Memory Barriers — Strongly/Weakly Ordered Memory
4.2 Test-and-Set Lock (TSL) — Algorithm & Example
4.3 Swap Instruction — Algorithm & Example
4.4 Unlock & Lock (Bounded Waiting Solution)
4.5 Lock Variable & Using Interrupts
4.6 Compare-and-Swap (CAS)

5. MUTEX LOCKS
5.1 Definition & API
5.2 Acquire & Release Implementation
5.3 Spinlock vs Blocking Mutex

6. MONITORS
6.1 Motivation & Definition
6.2 Monitor Syntax & Structure
6.3 Condition Variables (wait & signal)
6.4 Monitor vs Semaphore Comparison

7. CLASSIC SYNCHRONIZATION PROBLEMS

7.1 Bounded Buffer (Producer-Consumer) — Full Solution
7.2 Dining Philosophers — All Solutions
7.3 Readers-Writers — Full Solution

8. DEADLOCKS
8.1 System Model & Resource Types
8.2 Deadlock Characterization (4 Conditions)
8.3 Resource Allocation Graph
8.4 Methods for Handling Deadlocks
8.5 Deadlock Prevention
8.6 Deadlock Avoidance — Banker's Algorithm
8.7 Deadlock Detection — Algorithm & Wait-for Graph
8.8 Recovery from Deadlock
 CHAPTER 1

Process Synchronization

Coordinating concurrent processes to prevent data inconsistency

1.1 Introduction & Overview

In a multiprogramming environment, multiple processes execute concurrently and may share resources
such as memory, files, and hardware devices. When these processes access shared data simultaneously
without any control mechanism, the integrity of that data can be compromised. Process Synchronization
is the mechanism that ensures orderly access to shared resources, preventing data inconsistency and
race conditions.

Why Is Synchronization Needed?

• Multiple processes may try to read and write the same variable at the same time.
• The result of concurrent unsynchronized access depends on the order (scheduling) of execution —
which is non-deterministic.
• A change made by one process may not be visible to another process reading the same data.
• Without synchronization: Inconsistent data, wrong results, system crashes.
• With synchronization: Correct, predictable, and safe shared data access.

Process synchronization provides an efficient mechanism for shared data access among threads within
one process or across different processes. It resolves race conditions by ensuring only one process
modifies shared data at a time.

1.2 Types of Processes

Independent A process that cannot affect and is not affected by other processes. It
Process does NOT share any data, variable, or resource (Memory, CPU, I/O
devices). These processes execute in complete isolation.

Co-operative A process that CAN affect and IS affected by other processes. It SHARES
Process data, variables, or resources. These processes must be synchronized to
prevent race conditions.
 Property Independent Process Co-operative Process

Shares resources No Yes

Can affect others No Yes

Can be affected by others No Yes

Needs synchronization No Yes

Examples Standalone calculator Shared database, print spooler

1.3 Race Condition

Definition: A race condition is a situation where multiple processes/threads access and manipulate
the same shared data concurrently, and the final result of execution depends on the particular order in
which accesses take place — leading to unpredictable and incorrect outcomes.

Detailed Explanation
• Even a simple statement like counter++ is NOT atomic at the machine level.
• At assembly level, counter++ expands to 3 separate instructions:
■ Step 1: Load counter value from RAM into CPU register R1 → R1 = counter
■ Step 2: Increment the register → R1 = R1 + 1
■ Step 3: Store the register back to RAM → counter = R1
• If the CPU context-switches between these steps, another process can read/write the same variable.
• This interleaving of instructions from different processes leads to incorrect final values.

Step-by-Step Race Condition Example

Shared variable: int counter = 5. Process 0 does counter++, Process 1 does counter--. Expected result:
counter = 5. Actual result may be 4 or 6 due to interleaving.

Time Process 0 (counter++) Process 1 (counter--) Counter Value Registers

T1 R1 = counter (R1=5) — 5 R1=5

T2 R1 = R1 + 1 (R1=6) — 5 R1=6

T3 [SWITCH] — (preempted) R2 = counter (R2=5) 5 R1=6, R2=5

T4 — R2 = R2 - 1 (R2=4) 5 R1=6, R2=4

T5 — counter = R2 4 R2=4

T6 [SWITCH] counter = R1 — 6 (WRONG!) R1=6

Important: Expected: counter=5 (one increment, one decrement). Got: counter=6. The final value
depends on the scheduling order — this is the race condition.

The Problem with counter-- (counter = counter - 1) similarly:

Scenario P0 Completes First P1 Completes First Interleaved (Problem)

Final counter value 5 (correct) 5 (correct) 4 or 6 (WRONG!)

1.4 Critical Section

Definition: A Critical Section is a segment of code where a process accesses shared resources
(shared variables, data structures, files, or hardware). Only ONE process is permitted to execute in its
critical section at any given time. This mutual exclusion eliminates race conditions.

Structure of a Process with Critical Section

Every process that uses a critical section must be structured as follows:

General Process Structure

Process Pi() {

/* INITIAL SECTION — Non-shared data initialization */

...

do {

/* ENTRY SECTION — Request permission, acquire lock */

...

/* CRITICAL SECTION — Access shared resources here */

/* Only ONE process at a time allowed here */

...

/* EXIT SECTION — Release lock, signal completion */

...

/* REMAINDER SECTION — Non-critical code */

...

} while (TRUE);

Section Description Contains Who Can Access

Initial Section Pre-loop setup code Private variable initialization Only this process

Entry Section Gate-keeper before CS Condition checks, lock One at a time

acquisition

Critical Section Core protected region Shared variables, shared files, ONE process only
shared devices
 Exit Section Post-CS cleanup Lock release, notification to One at a time
others

Remainder Rest of the code Non-shared, private operations Any number of

Section processes

How Critical Section Eliminates Race Conditions:

• When Process P1 enters its critical section, the entry section LOCKS the shared resource.
• If an interrupt occurs and the CPU switches to Process P2, P2 tries to enter but finds the lock held.
• P2 is BLOCKED from entering — it must wait until P1 completes its critical section and releases the
lock.
• Only after P1 exits and unlocks can P2 proceed — preventing concurrent access.

1.5 Requirements for Process Synchronization

Any valid solution to the Critical Section Problem must satisfy the following conditions. The first THREE
are mandatory; the fourth is optional.

Requirement 1: Mutual Exclusion [MANDATORY]

When a process Pi is executing in its critical section, NO other process can execute in their critical
sections. If any other process requests the critical section while Pi is inside, it must WAIT until Pi
exits.

Example: If P1 is updating a bank balance, P2 must wait before reading it.

Requirement 2: Progress [MANDATORY]

If no process is executing in the critical section AND some processes wish to enter, then only
processes NOT in their remainder sections can participate in the entry decision. This selection cannot
be postponed indefinitely — a free critical section must be entered without unnecessary delay.

Example: If CS is free and P3 wants in, no idle process should block P3 from entering.

Requirement 3: Bounded Waiting (No Starvation) [MANDATORY]

There must be a bound/limit on the number of times other processes can enter the critical section
after a process has requested entry and before that request is granted. Every process must
eventually get to execute in the critical section — no process should wait FOREVER (starvation).

Example: If P2, P3, P4 each use CS 1000 times, P1 must be granted CS at least once.

Requirement 4: Portability / Architectural Neutrality [OPTIONAL]

 The solution should work correctly on all hardware platforms and operating systems. It should not
assume a specific architecture (32-bit vs 64-bit) or a specific OS (Windows vs Linux). A solution that
works only on certain hardware is not ideal.

Example: Solution works on Intel x86, ARM, MIPS, and on both 32-bit and 64-bit systems.

Note: Starvation = a process waits forever and never gets access to the critical section. Bounded
Waiting directly prevents starvation. 'No Starvation' is the same as 'Bounded Waiting'. Bound Wait
example: if others use CS up to k times, then the waiting process gets access in at most k+1 turns.

1.6 Software Solution Attempts

Before Peterson's elegant solution, two naive software attempts were made. Understanding their failures
explains WHY Peterson's solution uses both flag[] and turn.

Attempt 1 — Using a Shared Turn Variable

Attempt 1: Turn Variable

/* Shared variable */

int turn = 1; // Whose turn to enter CS

/* Process 1 */ /* Process 2 */

while(1) { while(1) {

while(turn == 2); // wait while(turn == 1); // wait

/* critical section */ /* critical section */

turn = 2; // give turn turn = 1; // give turn

/* other code */ /* other code */

} }

Problems with Attempt 1:

• Strict Alternation: Processes must take turns in order (P1→P2→P1→P2). P1 cannot enter CS twice
in a row even if P2 is not interested.
• Violates Progress: If P2 is in its remainder section (doesn't need CS), turn=2 and P1 is blocked —
even though CS is free.
• Satisfies Mutual Exclusion (only one process at a time) but at too high a cost.

Attempt 2 — Using Flag Arrays

Attempt 2: Flag Arrays

/* Shared variables */

boolean p1_inside = false, p2_inside = false;

 /* Process 1 */ /* Process 2 */

while(1) { while(1) {

while(p2_inside == true); while(p1_inside == true);

p1_inside = true; p2_inside = true;

/* critical section */ /* critical section */

p1_inside = false; p2_inside = false;

/* other code */ /* other code */

} }

Problems with Attempt 2:

• Violates Mutual Exclusion: Both processes can enter CS simultaneously!
• Timeline: Both see the other's flag as FALSE → both set own flag TRUE → both enter CS.

Time P1 Action P2 Action p1_inside p2_inside Problem

T1 while(p2_inside==True) — False False —

→ FALSE, skip

T2 — while(p1_inside==True) False False Both pass

[SWITCH] → FALSE, skip while!

T3 — p2_inside = True False True —

T4 p1_inside = True — True True BOTH IN

[SWITCH] CS!

Important: Attempt 2 has NO mutual exclusion! Both processes can be in the critical section
simultaneously — the fundamental requirement is violated.
 CHAPTER 2

Peterson's Solution

Classical software-based solution combining flag[] and turn

2.1 Overview & Shared Variables

Peterson's Solution is a classical software-based solution to the critical section problem for exactly
TWO processes. It elegantly combines a flag array (from Attempt 2) and a turn variable (from Attempt
1) to overcome the individual shortcomings of each approach.

Two Shared Variables

boolean flag[2] flag[i] = TRUE means Process Pi WANTS TO ENTER the critical section.
Initialized to FALSE (initially no process wants to enter).

int turn turn = j means it is Process Pj's TURN to enter the critical section. Used
to break symmetry when both processes want to enter simultaneously.

2.2 The Algorithm

Peterson's Solution — Process Pi

/* Shared variables */

boolean flag[2] = {FALSE, FALSE};

int turn;

/* Process Pi (where j = 1 - i, i.e., j is the other process) */

do {

flag[i] = TRUE; // Step 1: Declare intent to enter CS

turn = j; // Step 2: Give priority/courtesy to the other

 while (flag[j] == TRUE && turn == j); // Step 3: Wait if j wants in AND it's j's t
urn

/* ===== CRITICAL SECTION ===== */

flag[i] = FALSE; // Step 4: Declare exit from CS

/* ===== REMAINDER SECTION ===== */

} while (TRUE);

Understanding Each Step

• Step 1 (flag[i]=TRUE): Process Pi announces that it WANTS to enter the critical section.
• Step 2 (turn=j): Pi gives priority to Pj — 'After you, Pj.' This is the key to fairness.
• Step 3 (while loop): Pi waits ONLY IF both conditions are true simultaneously:
■ Pj ALSO wants to enter (flag[j]==TRUE) AND
■ It is Pj's turn (turn==j)
■ If either condition is false, Pi proceeds — if Pj doesn't want in, or if Pi set turn last, Pi goes first.
• Step 4 (flag[i]=FALSE): Pi signals it has left the critical section — allowing Pj to proceed.

2.3 Step-by-Step Trace

Scenario A: Both P0 and P1 want to enter simultaneously
Step P0 Action P1 Action flag[0] flag[1] turn Who Enters CS?

1 flag[0]=TRUE — T F ? —

2 turn=1 (give to P1) — T F 1 —

3 — flag[1]=TRUE T T 1 —

4 — turn=0 (give to P0) T T 0 —

5 while(flag[1]&&turn;==1)? — T T 0 P0 enters CS
flag[1]=T but turn=0 →
FALSE → ENTERS!

6 — while(flag[0]&&turn;==0) T T 0 P1 waiting
? BOTH TRUE → P1
waits

7 Executes CS Spinning T T 0 Only P0 in CS

8 flag[0]=FALSE — F T 0 P0 exits

9 — while(flag[0]&&turn;==0) F T 0 P1 enters CS
? flag[0]=F → FALSE →
ENTERS!

Scenario B: Only P0 wants to enter (P1 doesn't need CS)

Step P0 Action P1 flag State flag[0] flag[1] turn Result
1 flag[0]=TRUE; turn=1 flag[1]=FALSE (P1 not T F 1 —
interested)

2 while(flag[1]&&turn;==1)? — T F 1 P0 enters i
flag[1]=FALSE → condition mmediatel
FALSE y

3 P0 executes CS; flag[0]=FALSE — F F 1 Done

correctly

2.4 Proof of Correctness

Requirement Proof

Mutual Exclusion P0 enters CS only if: flag[1]==FALSE OR turn==0. P1 enters CS only if:
flag[0]==FALSE OR turn==1. Both can enter only if turn==0 AND turn==1
simultaneously — IMPOSSIBLE. So mutual exclusion holds.

Progress If Pi is in remainder (flag[i]=FALSE), it doesn't block Pj. When CS is free, the while
condition becomes FALSE for the waiting process, which then enters immediately.
No indefinite postponement.

Bounded Waiting After Pi sets flag[i]=TRUE and turn=j, it will enter CS within ONE cycle of Pj (at
most). Once Pj sets flag[j]=TRUE and turn=i, Pi gets to enter. Each process waits
at most 1 cycle — bounded by 1.

Satisfies all 3 mandatory requirements Disadvantages & Limitations

• Achieves full mutual exclusion • Busy waiting (spinlock) — wastes CPU cycles
• Guarantees progress (no unnecessary blocking) • Limited to ONLY 2 processes
• Provides bounded waiting (wait ≤ 1 cycle) • May fail on modern CPUs with instruction
• Pure software — no special hardware needed reordering
• Easy to verify and understand logically • Not efficient for long critical sections
• Scalability issue — does not extend to N
processes
 CHAPTER 3

Semaphores

Kernel-managed synchronization primitives with wait and signal

3.1 Definition & Atomic Operations

Definition: A Semaphore is an integer variable S maintained by the Operating System (kernel). It is
used to solve critical section problems in cooperative multi-process environments. Semaphores can
manage access to a pool of resources and coordinate processes. All semaphore operations are atomic
— they cannot be interrupted.

Operation Names (all equivalent)

Operation Alternative Names Purpose When Called

wait(S) P(), DOWN, Sleep, Acquire Entry operation — request Before entering critical
resource section

signal(S) V(), UP, Post, Release, Wake Exit operation — release After leaving critical
resource section

Basic wait() and signal() Pseudocode

Basic Semaphore Operations

wait(S) { signal(S) {

while (S <= 0); // busy wait S++;

S--; }

/* Note: The above is the simplified (busy-waiting) version */

/* OS uses sleep/wakeup internally to avoid busy waiting */

3.2 Binary Semaphore
A Binary Semaphore (also called a Mutex Semaphore) can only take values 0 or 1. Value 1 means the
resource is FREE; value 0 means it is OCCUPIED. Only ONE process can be in the critical section at a
time.

Binary Semaphore — wait() Code

Binary Semaphore wait()

Wait(S) {

IF ([Link] == 1) { // Resource is free

[Link] = 0; // Occupy it

ELSE { // Resource is busy

Sleep(); // Block this process AND place in Suspended List

Binary Semaphore — signal() Code

Binary Semaphore signal()

Signal(S) {

IF (Suspended List is empty) {

[Link] = 1; // No one waiting; free the resource

ELSE {

WakeUp(); // Select one process from Suspended List and move to Ready Queue

// Note: [Link] stays 0 because selected process will use resource

How Binary Semaphore Works — Detailed Steps

• Initially S=1 → 1 process can enter the critical section.
• Process P1 arrives → wait(S): S==1 → S becomes 0 → P1 enters CS.
• Process P2 arrives → wait(S): S==0 → P2 calls Sleep() → placed in Suspended List.
• Process P3 arrives → wait(S): S==0 → P3 calls Sleep() → placed in Suspended List.
• P1 finishes CS → signal(S): Suspended List NOT empty → WakeUp(P2) → P2 moves to Ready
Queue.
• P2 gets CPU → re-enters wait(S): S==1 → S becomes 0 → P2 enters CS.
 • P2 finishes → signal(S) → WakeUp(P3) → P3 enters CS. And so on.
• Binary semaphore value NEVER goes below 0 or above 1.

Full Binary Semaphore Example (S=1, Processes P1, P2, P3, P4)
Step Proces Operation S Value CS State Suspended Notes
s List

0 — Initialize 1 Empty [] S=1 means 1

process can enter

1 P1 wait(S): S==1 → S=0 0 P1 in CS [] P1 enters CS

successfully

2 P2 wait(S): S==0 → Sleep() 0 P1 in CS [P2] P2 blocked

3 P3 wait(S): S==0 → Sleep() 0 P1 in CS [P2,P3] P3 blocked

4 P4 wait(S): S==0 → Sleep() 0 P1 in CS [P2,P3,P4] P4 blocked

5 P1 Executes CS 0 Only P1 [P2,P3,P4] Only P1 inside

6 P1 signal(S): WakeUp(P2) 0 P2 in CS [P3,P4] P2 woken, S

stays 0

7 P2 Executes CS 0 Only P2 [P3,P4] Only P2 inside

8 P2 signal(S): WakeUp(P3) 0 P3 in CS [P4] P3 woken

9 P3 Executes CS + signal(S): 0 P4 in CS [] P4 woken

WakeUp(P4)

10 P4 Executes CS + signal(S): list 1 Empty [] All done

empty → S=1

3.3 Counting Semaphore

A Counting Semaphore can take any integer value from negative infinity to positive infinity. The value
represents the number of available resource instances. Used when multiple (N) instances of a resource
exist.

Counting Semaphore — wait() Code

Counting Semaphore wait()

Wait(S) {

[Link] = [Link] - 1; // Claim one resource

IF ([Link] < 0) { // No resource available

Sleep(); // Block process, put in Suspended List

}
 ELSE {

// Do work — resource is available, proceed

Return;

Counting Semaphore — signal() Code

Counting Semaphore signal()

Signal(S) {

[Link] = [Link] + 1; // Release one resource

IF ([Link] <= 0) { // Someone is waiting

Select a process from Suspended List;

WakeUp(); // Move selected process to Ready Queue

// If [Link] > 0, no one waiting; resource is free

Interpreting the Semaphore Value

S Value Meaning Example (S=3 initially)

S > 0 (positive) S resources are FREE and available S=3 → 3 resource instances free

S=0 All resources occupied; no one blocked yet S=0 → all 3 in use, no queue

S < 0 (negative) |S| processes are BLOCKED and waiting S=-2 → 2 processes waiting

Rule: If we start with S=k and process requests enter:

• S=k → k processes can enter CS (k resources available)
• S=0 → CS full; new arrivals are blocked
• S=-m → m processes are blocked in the suspended list
• Processes in CS = min(arrivals, initial k)

Full Counting Semaphore Example (S=3, Processes P1–P6)

Step Process Operation S Value CS Occupants Blocked Queue

0 — Initialize 3 [] []

1 P1 wait(S): S=3-1=2, 2>=0 → enters 2 [P1] []

2 P2 wait(S): S=2-1=1, 1>=0 → enters 1 [P1,P2] []

3 P3 wait(S): S=1-1=0, 0>=0 → enters 0 [P1,P2,P3] []

4 P4 wait(S): S=0-1=-1, -1<0 → Sleep() -1 [P1,P2,P3] [P4]

5 P5 wait(S): S=-1-1=-2, -2<0 → Sleep() -2 [P1,P2,P3] [P4,P5]

6 P6 wait(S): S=-2-1=-3, -3<0 → Sleep() -3 [P1,P2,P3] [P4,P5,P6]

7 P1 signal(S): S=-3+1=-2, -2<=0 → -2 [P2,P3,P4] [P5,P6]

WakeUp(P4)

8 P2 signal(S): S=-2+1=-1, -1<=0 → -1 [P3,P4,P5] [P6]

WakeUp(P5)

9 P3 signal(S): S=-1+1=0, 0<=0 → 0 [P4,P5,P6] []

WakeUp(P6)

10 P4 signal(S): S=0+1=1, 1>0 → no one 1 [P5,P6] []

waiting

11 P5 signal(S): S=1+1=2 2 [P6] []

12 P6 signal(S): S=2+1=3 3 [] []

Quick Calculation Formula

Final semaphore value = Initial value − (number of wait/P operations) + (number of signal/V operations)
Example 1: S=12, 10 wait ops, 4 signal ops → S = 12 - 10 + 4 = 6 Example 2: S=5, 8 wait ops, 3 signal
ops → S = 5 - 8 + 3 = 0 (5 in CS, no blocked) Example 3: S=3, 7 wait ops, 2 signal ops → S = 3 - 7 + 2 =
-2 (3 in CS, 2 blocked)

3.4 Binary vs Counting Semaphore

Feature Binary Semaphore Counting Semaphore

Value range 0 or 1 only Any integer (−∞ to +∞)

CS capacity Exactly 1 process Up to N processes (N = initial value)

Resource model Mutual exclusion of single resource Pool of N identical resources

wait() behavior S==1 → enter; S==0 → block S > 0 → decrement and enter; S ≤ 0 →
block

signal() behavior Set S=1 or wakeup one Increment S and wakeup one if S ≤ 0

Can S go negative? No (stays 0 or 1) Yes (|S| = blocked processes)

Example use Mutex, single printer Bounded buffer, connection pool

Advantages of Semaphores Disadvantages of Semaphores
• Allows exactly one process in CS (mutual • OS must track all wait/signal calls — overhead
exclusion) • Priority inversion: low-priority process may block
• No busy waiting — blocked processes sleep high-priority one
(counting semaphore) • Incorrect ordering of wait/signal can cause
• Machine-independent (implemented in OS deadlock
microkernel) • Difficult to implement correctly (easy to forget
• Can manage multiple resource instances signal)
(counting) • Basic binary semaphore still has busy-wait variant
• More efficient than busy-wait solutions for long • No built-in mechanism to prevent programmer
CS errors
• Widely supported in all modern OSes (POSIX
sem_t)
 CHAPTER 4

Hardware Support for Synchronization

Atomic hardware instructions forming the foundation of synchronization

4.1 Memory Barriers (Memory Fences)

A memory barrier (also called a memory fence) is a hardware instruction that ensures all memory
operations (loads and stores) preceding the barrier are completed and visible to all processors BEFORE
any memory operations after the barrier begin.

Memory Models

Strongly Ordered Any memory write on one processor is IMMEDIATELY visible to all other
processors. Provides the strongest guarantees. Less optimization
possible. (e.g., x86 architecture)

Weakly Ordered Memory writes on one processor may NOT be immediately visible to
other processors. Allows more CPU optimizations (reordering). Requires
explicit barriers. (e.g., ARM, PowerPC, Alpha)

The Problem Memory Barriers Solve:

• Modern CPUs and compilers can reorder instructions for performance optimization.
• In multi-processor systems, this reordering can break synchronization assumptions.
• Thread 1 writes x=100, then flag=true; Thread 2 sees flag=true but might still see old x value!

Memory Barrier Example

/* Without memory barrier — PROBLEM */

Thread 1: Thread 2:

x = 100; while (!flag); // Wait for flag

flag = true; print x; // Might print 0! (old value)

/* With memory barrier — CORRECT */

 Thread 1: Thread 2:

x = 100; while (!flag)

memory_barrier(); memory_barrier(); // Ensure flag is loaded fresh

flag = true; print x; // Guaranteed to print 100

Note: Memory barriers are very low-level operations, typically used only by kernel developers.
Application programmers use higher-level abstractions (mutexes, semaphores) which internally use
memory barriers where needed.

4.2 Test-and-Set Lock (TSL)

Test-and-Set (TSL) is an atomic hardware instruction that reads the value of a boolean variable,
unconditionally sets it to TRUE, and returns the original value — all in a SINGLE indivisible machine
operation. The atomicity is guaranteed by the hardware.

Test-and-Set Algorithm

/* Hardware-level atomic operation */

boolean TestAndSet(boolean *target) {

boolean returnValue = *target; // Step 1: Read current value

*target = TRUE; // Step 2: Set to TRUE

return returnValue; // Step 3: Return original value

} // ALL 3 STEPS ARE ATOMIC (cannot be interrupted)

/* Shared variable */

boolean lock = FALSE; // FALSE = free, TRUE = occupied

/* Usage pattern */

do {

while (TestAndSet(&lock)); // Spin until we get the lock

// If TestAndSet returns FALSE: lock was free, we got it (lock now TRUE)

// If TestAndSet returns TRUE: lock was busy, keep spinning

/* ===== CRITICAL SECTION ===== */

lock = FALSE; // Release lock

/* ===== REMAINDER SECTION ===== */

} while (TRUE);
Why TestAndSet() Achieves Mutual Exclusion:
• The first process to call TestAndSet(&lock;) when lock=FALSE gets returnValue=FALSE → exits
while loop → enters CS. Lock is now TRUE.
• Any subsequent process calling TestAndSet(&lock;) gets returnValue=TRUE (lock is TRUE) → stays
in while loop → busy-waits.
• Since the read-and-set is ATOMIC, no two processes can both see lock=FALSE simultaneously.
• On exit, the current process sets lock=FALSE → next process can enter.

TSL Execution Example (P1, P2, P3 arrive simultaneously)

Step P1 Action P2 Action P3 Action lock CS State

1 TSL: reads F, sets T, returns — — TRUE P1 in CS

F → exits loop → enters CS

2 Executes CS TSL: reads T, sets T, TSL: reads T → TRUE Only P1

returns T → spins spins

3 Executes CS Still spinning Still spinning TRUE Only P1

4 lock=FALSE (exit) — — FALSE Empty

5 — TSL: reads F, sets T, TSL: reads T → TRUE P2 in CS

returns F → enters CS spins

6 — Executes CS, then TSL: reads F → TRUE→F P3 in CS

lock=FALSE enters CS →T

Important: TSL guarantees Mutual Exclusion and Progress but does NOT guarantee Bounded Waiting.
A newly arriving process might always grab the lock before a long-waiting process, causing starvation.

4.3 Swap Instruction

Swap is an atomic hardware instruction that exchanges the values of two variables in memory in one
indivisible operation. It is an alternative to TSL for achieving mutual exclusion.

Swap Instruction Algorithm

/* Atomic Swap — exchanges two boolean variables */

void Swap(boolean *a, boolean *b) {

boolean temp = *a; // These 3 lines execute atomically

*a = *b;

*b = temp;

/* Shared: */ boolean lock = FALSE;

 /* Local: */ boolean key;

do {

key = TRUE;

while (key == TRUE) // Keep trying until key becomes FALSE

Swap(&lock, &key); // Atomically exchange lock and key

/* If lock was FALSE: after swap, key=FALSE (exit loop), lock=TRUE */

/* If lock was TRUE: after swap, key=TRUE (stay in loop) */

/* ===== CRITICAL SECTION ===== */

lock = FALSE; // Release — set lock back to FALSE

/* ===== REMAINDER SECTION ===== */

} while (TRUE);

Note: Swap achieves the same effect as TSL with different mechanics. Mutual Exclusion and Progress
are guaranteed, but Bounded Waiting is NOT — same limitation as basic TSL.

4.4 Unlock and Lock (Bounded Waiting Solution)

The Unlock and Lock algorithm extends TSL by maintaining a waiting[] array and scanning for the
next waiting process in circular order. This addition provides the Bounded Waiting guarantee that plain
TSL/Swap lack.

Unlock & Lock Algorithm (with Bounded Waiting)

/* Shared */

boolean lock = FALSE;

boolean waiting[n] = {FALSE, ..., FALSE};

boolean key;

/* Process Pi */

while (1) {

waiting[i] = TRUE;

key = TRUE;

/* Spin: stop when either we're not waiting OR lock was free */

while (waiting[i] && key)

key = TestAndSet(&lock);
 waiting[i] = FALSE;

/* ===== CRITICAL SECTION ===== */

/* Find the next waiting process in circular order */

j = (i + 1) % n;

while (j != i && !waiting[j])

j = (j + 1) % n;

if (j == i) // No one else is waiting

lock = FALSE; // Free the lock

else

waiting[j] = FALSE; // Hand-off to process j directly

/* ===== REMAINDER SECTION ===== */

How Bounded Waiting is Achieved:

• When Pi exits CS, it does NOT simply release the lock for anyone to grab.
• Instead, it scans waiting[] array starting from j=(i+1)%n in circular order.
• It finds the NEXT process that is waiting and directly clears its waiting flag.
• That process's while condition becomes FALSE (waiting[j]=FALSE) → it enters CS.
• This ensures processes are served in a near-FIFO circular order — each process waits at most n-1
turns.

4.5 Lock Variable

A lock variable is the simplest software mechanism — a shared integer variable that acts as a lock. It is
the most naive approach.

Lock Variable (Spinlock)

/* Shared */ int lock = 0; // 0=free, 1=occupied

/* Entry Section */

while (lock != 0); // Busy wait — spin until lock is free

lock = 1; // Claim the lock

/* ===== CRITICAL SECTION ===== */

/* Exit Section */

lock = 0; // Release the lock

 Important: Lock Variable has a CRITICAL FLAW: the 'while(lock!=0)' check and 'lock=1' assignment
are NOT atomic. Two processes can both see lock=0 and both set lock=1 → both enter CS
simultaneously. Does NOT guarantee mutual exclusion!

4.6 Hardware Solution Comparison

Mechanism Mutual Progress Bounded Busy Wait HW Needed Processe
Exclusion Waiting s

Lock Variable NO (race on NO NO YES None N

check)

Disable Interrupts YES YES NO NO Kernel only N (uniproc

essor)

TSL YES YES NO YES Atomic instr N

Swap YES YES NO YES Atomic instr N

Unlock & Lock YES YES YES YES Atomic instr N

Peterson's YES YES YES YES None 2 only

Semaphore YES YES YES NO OS support N

 CHAPTER 5

Mutex Locks

Higher-level software construct for mutual exclusion

5.1 Definition & Overview

A Mutex (Mutual Exclusion) Lock is a synchronization construct provided by the Operating System or
threading library. It is essentially a binary semaphore with acquire/release semantics, designed to be
simpler and safer to use. A mutex is either locked or unlocked.

• A mutex is a binary variable — it can only be 'locked' or 'unlocked'.

• Only the process that locked a mutex can unlock it (ownership concept).
• Provides mutual exclusion to a code section — only one thread/process at a time.
• Implemented as part of OS kernel (e.g., in POSIX pthread library as pthread_mutex_t).

5.2 Acquire and Release Implementation

acquire() Atomically checks if the mutex is available. If yes, sets available=FALSE
and allows the process to proceed. If no, the process BUSY-WAITS
(spins) until available.

release() Sets available=TRUE, allowing one waiting process to acquire the mutex.

Mutex Lock Implementation

/* Mutex state */

boolean available = TRUE; // TRUE=unlocked, FALSE=locked

acquire() {

while (!available) // Busy-wait until mutex is unlocked

; // Spin (no-op)

available = FALSE; // Lock it

 }

release() {

available = TRUE; // Unlock it

/* Usage */

do {

acquire(lock);

/* ===== CRITICAL SECTION ===== */

release(lock);

/* ===== REMAINDER SECTION ===== */

} while (TRUE);

5.3 Spinlock vs Blocking Mutex

Feature Spinlock (Busy-Wait Mutex) Blocking Mutex

Waiting method Loop continuously checking lock Process put to sleep; OS wakes when
free

CPU usage while waiting 100% (wastes cycles) 0% (CPU free for other processes)

Suitable for Short critical sections, multi-core Long critical sections

Context switch None needed Required (overhead)

Latency Very low (no OS call) Higher (OS scheduling involved)

Example Basic mutex from acquire/release pthread_mutex_lock() in Linux

Note: On a SINGLE-core processor, spinlocks are inefficient because the spinning process consumes
all CPU time, preventing the lock holder from making progress. On MULTI-core processors, spinlocks
can be efficient for very short critical sections since the lock may be released by another core while the
current core spins.
 CHAPTER 6

Monitors

High-level language construct for structured synchronization

6.1 Motivation & Definition

A Monitor is a high-level synchronization construct (Abstract Data Type) that combines shared data
variables with the procedures that access them into a single module. The monitor AUTOMATICALLY
ensures that only ONE process executes a monitor procedure at any time — mutual exclusion is built in,
not manually programmed.

Why Monitors Were Invented:

• Semaphores require programmers to manually call wait() and signal() in the right order.
• A single programming mistake (forgetting a signal, wrong order) can cause deadlock or race
conditions.
• Monitors eliminate this by building synchronization into the language/type system itself.
• Monitor procedures act like critical sections — the monitor guarantees mutual exclusion
automatically.
• Created to overcome timing error problems caused by semaphores.

6.2 Monitor Syntax & Structure

Monitor Syntax

monitor MonitorName {

/* ========== SHARED DATA ========== */

/* Data variables — CANNOT be accessed directly by processes */

/* Only accessible through the procedures below */

int shared_variable_1;

boolean shared_variable_2;
 condition x, y; // Condition variables for blocking/signaling

/* ========== PROCEDURES ========== */

/* Only way for processes to access shared data */

/* Only ONE procedure executes at a time (automatic mutual exclusion) */

Procedure P1(parameters) {

/* access and modify shared_variable_1, shared_variable_2 */

Procedure P2(parameters) { ... }

Procedure Pn(parameters) { ... }

/* ========== INITIALIZATION ========== */

Initialization_Code() {

/* Initialize shared variables */

shared_variable_1 = 0;

shared_variable_2 = FALSE;

Key Properties of Monitors

• Automatic Mutual Exclusion: Only ONE process can be active inside the monitor at any time.
Others queue up in the entry queue.
• Encapsulation: Shared data variables are private — processes CANNOT access them directly. They
must call monitor procedures.
• Entry Queue: Processes that want to enter the monitor line up. When the current process exits, the
next in queue enters.
• Procedures as Critical Sections: Each procedure call is effectively a critical section — the monitor
ensures exclusive access.
• Initialization Code: Runs once when the monitor is created — sets initial state of shared variables.

6.3 Condition Variables

Inside a monitor, processes may need to wait for a specific condition to become true (e.g., wait for a buffer
slot to become available). Condition variables provide this capability without releasing the monitor
incorrectly.

condition x A condition variable (also called a condition queue). A process can wait
on or signal a condition variable. Multiple condition variables can exist in
one monitor.
 [Link]() The calling process is SUSPENDED and placed in the blocked queue for
condition x. The monitor is released so another process can enter. The
process remains blocked until another process calls [Link]().

[Link]() RESUMES exactly ONE process that is blocked on condition x (if any). If
no process is waiting on x, the signal has NO effect — unlike semaphore
signal() which always increments the counter.

Monitor with Condition Variable Example

/* Example: Monitor with condition variable */

monitor ResourceManager {

int resource_count = 0;

condition not_empty; // Condition: resource_count > 0

Procedure add_resource() {

resource_count++;

not_empty.signal(); // Wake up one waiting consumer

Procedure use_resource() {

if (resource_count == 0)

not_empty.wait(); // Block until a resource is added

resource_count--;

/* use the resource */

6.4 Monitor vs Semaphore Comparison

Feature Monitor Semaphore

Mutual exclusion Automatic (built-in) Manual (programmer calls

wait/signal)

Error-proneness Low (language-enforced) High (easy to forget or order wrong)

Data encapsulation Yes (data is private) No (data is accessible directly)

Condition variables Yes ([Link](), [Link]()) Can be simulated

signal() effect when no waiter No effect Increments counter (remembered)

Implementation level Programming language construct OS/kernel primitive

Complexity to use Lower (safer) Higher (more error-prone)

Flexibility Less (structured) More (flexible)

Languages with built-in monitors Java (synchronized), Modula, Mesa All languages via library
 CHAPTER 7

Classic Synchronization Problems

Producer-Consumer | Dining Philosophers | Readers-Writers

7.1 Bounded Buffer (Producer-Consumer) Problem

Problem: A finite buffer of N slots is shared between Producer process(es) and Consumer process(es).
Producers insert items into empty slots; Consumers remove items from filled slots. Without
synchronization: race conditions, buffer overflow/underflow.

Problem Constraints:
• Producer must WAIT if the buffer is FULL (no empty slot).
• Consumer must WAIT if the buffer is EMPTY (no filled slot).
• Producer and Consumer should NOT access the buffer simultaneously (mutual exclusion).
• Multiple producers and consumers can exist — all must synchronize correctly.

Semaphore Solution
Semaphore Type Initial Value Meaning & Purpose

mutex Binary 1 Mutual exclusion on buffer. Ensures only one process

accesses buffer at a time.

empty Counting N (buffer size) Number of EMPTY slots. Producer waits when empty=0
(buffer full).

full Counting 0 Number of FULL slots. Consumer waits when full=0 (buffer
empty).

Producer Process

/* ===== PRODUCER PROCESS ===== */

do {

/* Produce an item (outside CS) */

 produce_item();

wait(empty); // Decrement empty count; block if buffer is full (empty=0)

wait(mutex); // Acquire exclusive access to buffer

/* ===== CRITICAL SECTION ===== */

buffer[in] = item; // Insert item at position 'in'

in = (in + 1) % N; // Advance circular buffer pointer

signal(mutex); // Release buffer access

signal(full); // Increment full count; wake consumer if waiting

} while (TRUE);

Consumer Process

/* ===== CONSUMER PROCESS ===== */

do {

wait(full); // Decrement full count; block if buffer is empty (full=0)

wait(mutex); // Acquire exclusive access to buffer

/* ===== CRITICAL SECTION ===== */

item = buffer[out]; // Remove item from position 'out'

out = (out + 1) % N; // Advance circular buffer pointer

signal(mutex); // Release buffer access

signal(empty); // Increment empty count; wake producer if waiting

/* Consume item (outside CS) */

consume_item(item);

} while (TRUE);

Critical Order of wait() Calls:

Important: ALWAYS call wait(resource_semaphore) BEFORE wait(mutex). If wait(mutex) is called first

and then wait(empty/full), a deadlock can occur: Producer holds mutex and waits for empty; Consumer
holds mutex and waits for full — both blocked forever!

Step-by-Step Execution (Buffer size N=2, initial: empty=2, full=0, mutex=1)

Step Process Operation empty full mutex Buffer State
1 Producer wait(empty): 2→1 1 0 1 [ ][ ]

2 Producer wait(mutex): 1→0 → enters 1 0 0 [ ][ ]

3 Producer Insert item A 1 0 0 [A][ ]

4 Producer signal(mutex): 0→1 1 0 1 [A][ ]

5 Producer signal(full): 0→1 1 1 1 [A][ ]

6 Consumer wait(full): 1→0 1 0 1 [A][ ]

7 Consumer wait(mutex): 1→0 → enters 1 0 0 [A][ ]

8 Consumer Remove item A 1 0 0 [ ][ ]

9 Consumer signal(mutex): 0→1 1 0 1 [ ][ ]

10 Consumer signal(empty): 1→2 2 0 1 [ ][ ]

7.2 Dining Philosophers Problem

Problem: 5 philosophers sit around a circular table. 5 chopsticks are placed between them (one
between each adjacent pair). Each philosopher needs BOTH left and right chopsticks to eat. If all 5
simultaneously pick up one chopstick, deadlock occurs.

Problem Analysis:
• 5 philosophers, 5 chopsticks (limited resources), infinite rice in bowl.
• Philosopher states: THINKING (doesn't need chopsticks) → HUNGRY (waiting for chopsticks) →
EATING (has both chopsticks).
• Philosopher i needs chopstick i (left) and chopstick (i+1)%5 (right).
• Two adjacent philosophers cannot eat simultaneously (they share a chopstick).
• Deadlock risk: All 5 pick up left chopstick → each waits for right → circular wait → deadlock.
• Starvation risk: Some philosophers always prioritized → others wait forever.

Solution 1: Naive Semaphore (Has Deadlock Risk)

Solution 1: Naive (Deadlock Possible)

semaphore chopstick[5] = {1, 1, 1, 1, 1}; // All initialized to 1 (free)

/* Philosopher i */

while (TRUE) {

think();

wait(chopstick[i]); // Pick up LEFT chopstick

wait(chopstick[(i+1) % 5]); // Pick up RIGHT chopstick

eat();
 signal(chopstick[i]); // Put down LEFT chopstick

signal(chopstick[(i+1)%5]); // Put down RIGHT chopstick

/* PROBLEM: If ALL 5 philosophers run wait(chopstick[i]) simultaneously,

each gets their left chopstick (all S[i]=0), then ALL block waiting for

right chopstick — DEADLOCK! */

Three Deadlock-Free Solutions:

Solution 2: Allow Only 4 Philosophers at a Table

• Limit simultaneous seat occupancy to 4 (even though 5 exist).

• With 4 philosophers and 5 chopsticks, at least 1 philosopher can always eat.
• This breaks the circular wait condition — prevents deadlock.

Solution 3: Asymmetric Chopstick Ordering

• Odd-numbered philosophers pick LEFT first, then RIGHT.

• Even-numbered philosophers pick RIGHT first, then LEFT.
• This breaks the symmetry that causes circular wait — prevents deadlock.

Solution 4: Both Chopsticks or None (Atomic Pickup)

• A philosopher picks up both chopsticks ONLY IF both are available simultaneously.

• The check-and-pickup must happen inside a critical section (to avoid race).
• If not both available, put down any acquired ones and wait.

Solution 5: Three-State Solution with Mutex (Best — No Deadlock, No

Starvation)
Solution 5: Three-State Dining Philosophers (Deadlock & Starvation Free)

/* Three philosopher states */

#define THINKING 0

#define HUNGRY 1

#define EATING 2

int state[5]; // State of each philosopher

semaphore s[5]; // s[i]=0 initially (philosophers start not eating)

semaphore mutex = 1; // For mutual exclusion on state array

void philosopher(int i) {

while (TRUE) {

think();

take_forks(i); // Try to pick up both forks

eat();

put_forks(i); // Put down both forks

void take_forks(int i) {

wait(mutex); // Lock state array

state[i] = HUNGRY; // Declare intent

test(i); // Check if can eat now

signal(mutex); // Unlock state array

wait(s[i]); // Block if couldn't eat (s[i] still 0)

void put_forks(int i) {

wait(mutex);

state[i] = THINKING; // Done eating

test((i-1+5)%5); // Check if LEFT neighbor can now eat

test((i+1)%5); // Check if RIGHT neighbor can now eat

signal(mutex);

void test(int i) {

/* A philosopher can eat if: they're HUNGRY AND both neighbors are NOT EATING */

if (state[i]==HUNGRY &&

state[(i-1+5)%5]!=EATING &&

state[(i+1)%5]!=EATING) {

state[i] = EATING;

signal(s[i]); // Allow philosopher i to proceed

}
Why This Solution is Correct:
• No Deadlock: A philosopher enters EATING only if BOTH neighbors are not eating. Circular wait is
impossible.
• No Starvation: When a philosopher finishes eating, it checks both neighbors. If either was HUNGRY
and waiting, they get to eat next.
• Mutual Exclusion on state[]: The mutex semaphore protects the state array from concurrent
modification.
• Correct blocking: s[i] semaphore blocks philosopher i until its conditions are satisfied.

7.3 Readers-Writers Problem

Problem: A shared resource (database, file) is accessed by Readers (read-only) and Writers
(read+write). Multiple readers can safely read simultaneously. A writer needs EXCLUSIVE access — no
other reader or writer can access during a write.

Access Rules:
Scenario Allowed? Reason

Reader + Reader YES Reads don't modify data — no conflict

Writer alone (no YES Exclusive write access

readers/writers)

Reader + Writer NO Writer is modifying; reader may read inconsistent data

Writer + Writer NO Concurrent writes corrupt data

New reader while writer Depends on First vs Second Readers-Writers

waiting policy

Variants of the Readers-Writers Problem:

First Readers have higher priority. Writers wait until ALL current readers finish.
Readers-Writers Risk: Writer starvation if readers arrive continuously.

Second Writers have higher priority. Once a writer is waiting, no new readers are
Readers-Writers allowed. Risk: Reader starvation if writers arrive continuously.

Semaphore Solution (First Readers-Writers — Reader Priority)

Variable Type Initial Value Purpose

read_count Integer 0 Number of readers currently reading. Modified

atomically.

mutex Binary Semaphore 1 Protects read_count variable from concurrent

modification.
w Binary Semaphore 1 Write lock. First reader acquires it; last reader
releases it.

Writer Process

/* ===== WRITER PROCESS ===== */

while (TRUE) {

wait(w); // Acquire exclusive write lock

// Blocks if any reader is reading OR another writer is writing

/* ===== WRITE OPERATION ===== */

write_data();

signal(w); // Release write lock

Reader Process

/* ===== READER PROCESS ===== */

while (TRUE) {

/* --- Entry: Update read_count and block writers if needed --- */

wait(mutex); // Lock read_count for safe modification

read_count++; // One more reader

if (read_count == 1) // FIRST reader: block writers

wait(w); // Acquire write lock (blocks any writer)

signal(mutex); // Unlock read_count

/* ===== READ OPERATION ===== */

/* Multiple readers can read simultaneously here */

read_data();

/* --- Exit: Update read_count and unblock writers if needed --- */

wait(mutex); // Lock read_count for safe modification

read_count--; // One fewer reader

if (read_count == 0) // LAST reader: allow writers

signal(w); // Release write lock

signal(mutex); // Unlock read_count

}
Detailed Logic Explanation:
• First reader (read_count goes 0→1): calls wait(w) to block any writers. Writers cannot enter as long
as any reader is reading.
• Subsequent readers (read_count > 1): skip wait(w) — writers are already blocked. Multiple readers
proceed simultaneously.
• Last reader (read_count goes 1→0): calls signal(w) — no more readers. Now a waiting writer can
proceed.
• Why mutex is needed: read_count++ and read_count-- are not atomic. mutex protects these
operations.
• Writer: Simply waits for w. When all readers exit, the last reader signals w — writer gets access.

Step-by-Step Trace (1 Writer, 3 Readers)

Step Process Operation read_cou mutex w Notes
nt

1 R1 wait(mutex)→0; rc++→1; 1 1 0 First

rc==1→wait(w)→0; signal(mutex)→1 reader
locks
out
writers

2 R2 wait(mutex)→0; rc++→2; rc!=1 skip 2 1 0 R2

wait(w); signal(mutex)→1 reads a
longsid
e R1

3 W1 wait(w): w==0 → W1 BLOCKED 2 1 0 Writer

waits
for all
readers

4 R3 wait(mutex)→0; rc++→3; rc!=1; 3 1 0 R3

signal(mutex)→1 reads
with
R1, R2

5 R1 exits wait(mutex)→0; rc--→2; rc!=0; 2 1 0 Not last

signal(mutex)→1 reader,
W1 still
waits

6 R2 exits wait(mutex)→0; rc--→1; rc!=0; 1 1 0 Not last

signal(mutex)→1 reader

7 R3 exits wait(mutex)→0; rc--→0; 0 1 1 LAST

rc==0→signal(w)→1; signal(mutex)→1 reader
unbloc
ks
writer!
8 W1 wait(w): w==1→w=0 → W1 enters 0 1 0 Writer
now
has ex
clusive
access

9 W1 exits signal(w)→1 0 1 1 Writer

done,
CS free
again
 CHAPTER 8

Deadlocks

System Model | Characterization | Prevention | Avoidance | Detection | Recovery

8.1 System Model & Resource Types

Definition: A deadlock is a situation where a set of processes are PERMANENTLY BLOCKED, each
waiting for a resource that is held by another process in the same set. None of the processes can
proceed, release, or be awakened.

Resource Types:

Preemptable Can be taken away from a process without harm. The process can
Resources resume later. Examples: CPU registers (context switch), main memory
(can be swapped). These generally do NOT cause deadlocks.

Non-preemptable CANNOT be taken away from a process without causing it to fail.

Resources Examples: Printer, tape drive, file locks. These CAN cause deadlocks —
they must be released voluntarily.

Resource Usage Sequence (for non-preemptable resources):

• Step 1: Request — Process requests the resource. If available, it is granted. If not, the process
waits.
• Step 2: Use — Process uses the resource (e.g., writes to the printer, accesses file).
• Step 3: Release — Process voluntarily releases the resource when done.

Note: Deadlocks involve ONLY non-preemptable resources. Preemptable resources can be forcibly
reclaimed, so they don't lead to permanent blocking.

8.2 Deadlock Characterization (Four Necessary Conditions)

 A deadlock can occur IF AND ONLY IF all FOUR of the following conditions hold simultaneously. These
are known as the Coffman Conditions (proposed by E.G. Coffman in 1971).

Condition 1: Mutual Exclusion

At least one resource must be held in a non-sharable mode — only ONE process can use the
resource at a time. If another process requests the same resource, it must wait.

Example: A printer can only be used by one process at a time.

Condition 2: Hold and Wait

A process is HOLDING at least one resource AND is WAITING to acquire additional resources
currently held by other processes.

Example: Process P holds Printer and is waiting for Scanner held by Process Q.

Condition 3: No Preemption

Resources CANNOT be preempted (forcibly taken away). A resource can only be released
VOLUNTARILY by the process holding it, after it has completed its task.

Example: P cannot have its Printer taken away; it must voluntarily release it.

Condition 4: Circular Wait

A circular chain of processes exists: P1 is waiting for a resource held by P2, P2 is waiting for a
resource held by P3, ..., Pn is waiting for a resource held by P1.

Example: P1 waits for P2's resource, P2 waits for P3's resource, P3 waits for P1's resource.

Important: ALL FOUR conditions must hold simultaneously for a deadlock to occur. Preventing ANY
ONE of these four conditions prevents deadlocks. This is the key insight behind Deadlock Prevention
strategies.

8.3 Resource Allocation Graph (RAG)

A Resource Allocation Graph is a directed graph used to describe the state of resource allocation. It
helps detect deadlocks visually.

Element Notation Meaning

Process Circle: P1, P2, ... A process in the system

Resource Type Rectangle: R1, R2, ... A resource type (may have multiple instances — dots
inside)
 Request Edge Pi → Rj (process to Process Pi is requesting/waiting for resource Rj
resource)

Assignment Edge Ri → Pj (resource to Resource Ri is currently assigned to process Pj

process)

• If the graph has NO cycle: No deadlock.

• If the graph has a cycle AND each resource has only ONE instance: Deadlock.
• If the graph has a cycle AND resources have MULTIPLE instances: Deadlock is POSSIBLE but
not certain.

8.4 Methods for Handling Deadlocks

Method Approach When Used Cost

Prevention Ensure at least one Coffman System design time Reduced

condition can never hold resource
utilization

Avoidance Dynamically check future resource Runtime (each request) Requires advance
states; only grant safe requests knowledge;
overhead

Detection + Recovery Allow deadlocks; detect when they Periodically at runtime Recovery
occur; recover overhead

Ostrich Algorithm Ignore the problem (assume Some desktop OSes Low cost but risky
deadlocks are rare)

8.5 Deadlock Prevention

Deadlock Prevention eliminates deadlocks by ensuring that at least ONE of the four Coffman conditions
can NEVER be satisfied. Break even one condition → no deadlock.

Prevent: Prevent Mutual Exclusion

Strategy: Make all resources sharable. Allow multiple processes to use any resource simultaneously.
Pros: Eliminates the root cause Cons: NOT possible for inherently non-sharable resources (printer, tape).
Impractical in general.

Prevent: Prevent Hold and Wait

Strategy: Strategy 1: Require processes to request ALL resources at once before starting. Strategy 2:
Require a process to release all held resources before requesting new ones.
Pros: Simple to understand Cons: Low resource utilization (holding resources not currently needed).
Starvation possible for resource-hungry processes.

Prevent: Allow Preemption

Strategy: If a process holding resources requests a new resource that's unavailable, PREEMPT (take
away) all its held resources. The process restarts when all needed resources are available.
Pros: Resources are not wasted on blocked processes Cons: Only works for preemptable resources (CPU,
memory). Cannot preempt printers mid-job.

Prevent: Prevent Circular Wait

Strategy: Assign a unique number to each resource type. Processes can ONLY request resources in
strictly increasing numerical order. A process can only request Rj if Rj's number > all currently held
resources.
Pros: Most practical prevention strategy Cons: Resource ordering may not match natural usage pattern.
Programmer must be aware of ordering.

8.6 Deadlock Avoidance — Banker's Algorithm

Deadlock Avoidance allows the system to dynamically examine resource allocation states before
granting a request. A request is granted only if granting it keeps the system in a SAFE STATE. Uses the
Banker's Algorithm.

Safe State The system is in a safe state if there exists a SAFE SEQUENCE — an
ordering of all processes such that each process can obtain all its needed
resources, execute, and release resources, allowing subsequent
processes to do the same.

Unsafe State No safe sequence exists. The system MAY or MAY NOT deadlock, but
we cannot guarantee it won't. Avoidance never enters an unsafe state.

Data Structures for Banker's Algorithm (n processes, m resource types):

Matrix/Vector Size Content

Available 1 × m vector Available[j] = number of available instances of resource type j

Max n × m matrix Max[i][j] = maximum instances of resource j that process i may

request

Allocation n × m matrix Allocation[i][j] = current instances of resource j allocated to process i

Need n × m matrix Need[i][j] = Max[i][j] - Allocation[i][j] = remaining need of i for j

Safety Algorithm (Check if current state is safe):

Safety Algorithm

1. Let Work = Available (Work is a copy of Available)

Let Finish[i] = FALSE for all processes i

 2. Find index i such that:

a. Finish[i] == FALSE (process not yet finished)

b. Need[i] <= Work (process's remaining need can be satisfied)

If no such i exists, go to step 4.

3. Work = Work + Allocation[i] (process completes; releases its resources)

Finish[i] = TRUE

Go to step 2.

4. If Finish[i] == TRUE for ALL i: System is in SAFE STATE.

Otherwise: System is in UNSAFE STATE.

Resource-Request Algorithm (Process Pi requests Request[i]):

Resource Request Algorithm

1. If Request[i] <= Need[i]: Go to step 2. Else: ERROR (exceeded maximum claim).

2. If Request[i] <= Available: Go to step 3. Else: Process WAITS (resources unavailable

).

3. Pretend to allocate (modify state temporarily):

Available = Available - Request[i]

Allocation[i] = Allocation[i] + Request[i]

Need[i] = Need[i] - Request[i]

4. Run Safety Algorithm on new state:

If SAFE: Grant the request (keep the new state).

If UNSAFE: Reject request; restore old state (process must wait).

Banker's Algorithm Example:

System with 3 resource types (A, B, C): 10, 5, 7 instances. 5 processes.

Process Max A B C Allocation A B C Need A B C Available A B C

P0 753 010 743 3 3 2 (initially)

P1 322 200 122

P2 902 302 600

P3 222 211 011

P4 433 002 431

Safety Check: Available = 3,3,2. Safe sequence: P1 (needs 1,2,2 ≤ 3,3,2 ✓) → P3 (needs 0,1,1 ≤ 5,3,2 ✓)
→ P4 (needs 4,3,1 ≤ 7,4,3 ✓) → P0 (needs 7,4,3 ≤ 7,4,5 ✓) → P2 (needs 6,0,0 ≤ ✓). Safe sequence exists
→ SAFE STATE.

8.7 Deadlock Detection

If neither prevention nor avoidance is used, the system may enter a deadlocked state. Detection
algorithms examine the resource allocation state to determine if a deadlock has occurred.

Case 1: Single Instance per Resource Type — Wait-for Graph

• Derive a Wait-for Graph from the Resource Allocation Graph.
• Remove resource type nodes; collapse request/assignment edges.
• Edge Pi → Pj means Pi is waiting for a resource held by Pj.
• If Wait-for Graph has a CYCLE → DEADLOCK exists.
• Detection algorithm runs periodically (O(n²) where n = number of processes).

Case 2: Multiple Instances per Resource Type — Detection Algorithm

Deadlock Detection Algorithm (Multiple Instances)

Data structures: Work (= Available), Finish[i]

1. For all processes i:

If Allocation[i] == 0: Finish[i] = TRUE (no resources held, not blocked)

Else: Finish[i] = FALSE

2. Find index i such that:

a. Finish[i] == FALSE

b. Request[i] <= Work (can this process's requests be satisfied now?)

If no such i: go to step 4.

3. Work = Work + Allocation[i] (assume process runs to completion)

Finish[i] = TRUE

Go to step 2.

4. If Finish[i] == FALSE for SOME i: DEADLOCK DETECTED.

All processes i with Finish[i]==FALSE are in the deadlocked set.

When to Run Detection Algorithm:

• After EVERY resource request — detects deadlock immediately, but high overhead.
 • Periodically (every hour, every N requests) — lower overhead but delayed detection.
• When CPU utilization drops below a threshold (may indicate deadlock stalling processes).

8.8 Recovery from Deadlock

Once a deadlock is detected, the system must recover. Two main approaches:

Recovery Strategy 1: Process Termination

• Option A — Abort ALL deadlocked processes: Simplest approach. Breaks all cycles. Very
expensive — all work lost.
• Option B — Abort processes ONE AT A TIME: Abort one, run detection again, repeat until
deadlock resolved. Less waste but more overhead.

Selection criteria for which process to terminate (minimize cost):

• Process with lowest priority
• Process with least computation time so far (cheapest to restart)
• Process with least remaining computation (closest to completion)
• Process using fewest resources (least impact)
• Process that is NOT interactive (batch job preferred over interactive)

Recovery Strategy 2: Resource Preemption

• Forcibly take resources FROM some processes and give them to deadlocked processes.
• Three issues to address:
■ Selecting a victim: Which process/resource to preempt? Minimize cost (computation done, resources
held).
■ Rollback: Where to roll back preempted process? Safe option: Total rollback (abort and restart). Better:
Partial rollback (rollback to a checkpoint).
■ Starvation: Must ensure the same process is not ALWAYS chosen as victim. Include the number of
times a process has been rolled back in the cost factor.
 COMPLETE SUMMARY — Process Synchronization & Deadlock

All Synchronization Mechanisms at a Glance

Mechanism Type M.E. Progress [Link] Busy Wait N Procs

Peterson's Solution Software Yes Yes Yes Yes 2 only

Binary Semaphore OS Kernel Yes Yes FIFO queue No (sleep) Any N

Counting Semaphore OS Kernel N-way Yes FIFO queue No (sleep) Any N

Mutex Lock OS/Library Yes Yes Impl.-dep. Yes (spin) Any N

Monitor Language Yes (auto) Yes Cond. vars No Any N

TSL Hardware Yes Yes No Yes Any N

Swap Hardware Yes Yes No Yes Any N

Unlock & Lock Hardware+SW Yes Yes Yes Yes Any N

Classic Problems Quick Reference

Problem Semaphores Key Rule Risk Without
Sync

Bounded Buffer mutex=1, empty=N, full=0 wait(resource) before Buffer overflow/un

wait(mutex) derflow, race on
buffer

Dining Philosophers chopstick[5] all=1, mutex=1 Never let all 5 pick one Deadlock (all wait
chopstick forever),
starvation

Readers-Writers mutex=1, w=1, read_count=0 First reader blocks writers; last Writer data
reader releases corruption,
inconsistent reads

Deadlock Summary
Aspect Details

4 Necessary Conditions Mutual Exclusion + Hold & Wait + No Preemption + Circular Wait (ALL must hold)

Prevention Break ONE condition: impose total ordering (circular wait most practical)

Avoidance Banker's Algorithm: grant requests only if result is SAFE STATE

Detection Wait-for graph (single instance) or matrix algorithm (multiple instances)

Recovery Terminate processes OR preempt resources (with rollback)

Exam Tips: Key Exam Tips: (1) Peterson's solution uses BOTH flag[] AND turn — this is why it works.
(2) Semaphore value interpretation: +k means k resources free; -k means k processes blocked. (3) In
Bounded Buffer, always wait(resource) before wait(mutex) to avoid deadlock. (4) Dining Philosophers
3-state solution: philosopher only eats if BOTH neighbors are not eating. (5) Readers-Writers: first
reader blocks writers; last reader unblocks. (6) Deadlock needs ALL 4 Coffman conditions — breaking
ANY ONE prevents it. (7) Banker's Algorithm: only grant if resulting state is SAFE (safe sequence
exists).