[Type here]

MODULE-3 Hours Process Synchronization: Synchronization: The critical

section problem; Peterson’s solution; Synchronization hardware;
Semaphores; Classical problems of synchronization; Deadlocks: System
model; Deadlock characterization; Methods for handling deadlocks; Deadlock
prevention; Deadlock avoidance; Deadlock detection and recovery from
deadlock.

PROCESS SYNCHRONIZATION

🔹 Meaning of Synchronization

 Co-operating processes are those that can affect or be affected by each other’s actions.
 These processes may share:
o Logical address space (same code and data), or
o Files, or
o Messages through threads.

🔹 Problem of Data Inconsistency

 When multiple processes access shared data at the same time, results can become
inconsistent.
 To avoid this, the execution order of cooperating processes must be controlled — this
is called synchronization.

🔹 Producer–Consumer Example

 Suppose we have a shared variable:

counter → tracks how many buffers are full.
o Initially, counter = 0
o Producer increases counter when it produces a new buffer.
o Consumer decreases counter when it consumes a buffer.

🔹 Race Condition
[Type here]

 A race condition occurs when two or more processes access shared data
simultaneously, and the final result depends on the timing or order of execution.
 Example:
 counter++ // Producer
 counter-- // Consumer

These can be broken into machine-level steps:

counter++:

load counter

add 1

store counter

counter--:

load counter

subtract 1

store counter

 If these operations interleave, unexpected results occur:

o Suppose counter = 5
o After both run together, counter might end up as 4 or 6, instead of 5
o This is a race condition.

 Step-by-step interleaving

Step Operation Value in register Value in memory (counter)

1 T1: load counter 5 5
2 T2: load counter 5 5
3 T1: add 1 6 5
4 T2: subtract 1 4 5
5 T1: store counter — 6
6 T2: store counter — 4

 Final result = 4, but correct answer should be 5.

[Type here]

🔹 Solution

 Synchronization ensures that only one process accesses shared data at a time.
 This prevents race conditions and maintains data consistency.

CRITICAL-SECTION PROBLEM

What is a Critical Section?

 A critical section is a part of the program where a process:

o Changes shared variables
o Updates tables
o Writes to a file
 Since the data is shared, only one process should access it at a time.

🔹 Structure of a Process

Each process has four main sections:

1. Entry Section – requests permission to enter the critical section.

2. Critical Section – the part where shared data is accessed (only one process allowed).
3. Exit Section – executed after leaving the critical section.
4. Remainder Section – the rest of the program (non-critical part).

Figure : General structure of a typical

[Type here]

process

🔹 Problem Statement

“Ensure that when one process is executing in its critical section, no other process executes its
critical section.”

This is called the Critical-Section Problem — and synchronization techniques are used to solve
it.

🔹 Requirements of a Good Solution

A correct solution must satisfy three conditions:

1. Mutual Exclusion
o Only one process can be in its critical section at a time.
2. Progress
o If no process is in the critical section, only those ready to enter can decide who
goes next.
o The choice should not be delayed forever.
3. Bounded Waiting
o After a process requests to enter its critical section, there should be a limit on how
long it waits.
o Prevents starvation (waiting forever).

🔹 Kernel Approaches

Type Description
Allows a process to be interrupted even in kernel mode (more
Preemptive Kernel
concurrency, needs synchronization).
Non-Preemptive Once a process enters kernel mode, it runs till it exits (simpler, but less
Kernel responsive).
[Type here]

PETERSON’S SOLUTION

What is Peterson’s Solution?

 It is a software-based algorithm that provides a way for two

processes to share a single resource without conflicts.
 It solves the critical-section problem for two processes only (say,
P0 and P1).

🔹 Shared Variables

The two processes share two variables:

1. int turn;
o Indicates whose turn it is to enter the critical section.
o If turn == i, then process Pi can enter.
2. boolean flag[2];
o Indicates whether a process is ready to enter its critical section.
o If flag[i] == true, then process Pi is ready.

The structure of process Pi in Peterson‘s solution

Algorithm (Structure of Process Pi)

do {
[Type here]

flag[i] = true; // Pi wants to enter

turn = j; // Give chance to Pj

while (flag[j] && turn == j)

; // Wait until Pj finishes

// ---- CRITICAL SECTION ----

flag[i] = false; // Pi done with critical section

// ---- REMAINDER SECTION ----

} while (true);

🔹 Working Logic

1. Each process sets flag[i] = true → shows interest in entering.

2. Then it sets turn = j → gives priority to the other process.
3. If both processes want to enter together, the turn variable decides
who enters first.
4. Once one process is inside its critical section, the other waits until the
first finishes.

🔹 Why It’s Correct

1. Mutual Exclusion – Both can’t be in their critical sections at once

because of the while condition.
2. Progress – The process not in the remainder section can decide who
enters next; no indefinite delay.
3. Bounded Waiting – Each process gets a fair turn due to the turn
variable.
[Type here]

2.13 SYNCHRONIZATION HARDWARE

2.13.1 Hardware-based Solution for Critical Section Problem

 A lock is a basic mechanism to prevent race conditions (when multiple

processes try to access shared data at the same time).
 Rule:
o A process must acquire the lock before entering its critical
section.
o It releases the lock when it leaves the critical section.
 This ensures only one process can be in the critical section at a time.

Fig:Solution to the critical-section problem using locks

2.13.2 Hardware Instructions for Solving Critical Section Problem

 Modern CPUs provide special atomic instructions to handle

synchronization.
These can:
o Test and modify a word’s value in memory atomically, or
o Swap two memory values atomically.
 Atomic operation = executes completely without being interrupted.

[Link] TestAndSet() Instruction

[Type here]

 TestAndSet() is a hardware instruction that performs two actions atomically (without

interruption):

1. It returns the old value of a variable.

2. It sets that variable to true.

 So, if the variable was false before, it becomes true after execution.

 This line defines a function named TestAndSet that takes a pointer to a boolean
variable (target).
It means the function can directly modify the variable stored in memory.

boolean TestAndSet(boolean *target) {

boolean old = *target;

*target = true;

return old;

 If two CPUs execute this simultaneously, the hardware ensures they are done one after
another — not at the same time — ensuring atomicity.

[Link] TestAndSet with Mutual Exclusion

 We can use TestAndSet() to create a simple lock mechanism ensuring mutual

exclusion.
 Declare a shared boolean variable lock, initialized to false

do {
while (TestAndSet(&lock))
; // Busy waiting (wait until lock becomes false)

// Critical Section

lock = false; // Release lock

// Remainder Section
} while (true);

Figure : Mutual-exclusion implementation with test and set()

[Type here]

Explanation:

 When a process enters the while (TestAndSet(&lock)) loop:

o If lock is false, it becomes true → process enters critical section.
o If lock is already true, the process keeps waiting.
 When done, the process sets lock = false, allowing others to enter.

Problem with Simple TestAndSet

 A simple version of TestAndSet ensures mutual exclusion, but not bounded waiting —
→ one process may wait indefinitely while others repeatedly enter the critical section
(starvation).

[Link] Swap() Instruction

Purpose:

To achieve mutual exclusion (only one process in the critical section at a

time) using hardware support.

➤ Definition:

swap() exchanges the values of two variables atomically — meaning it

happens in one single, uninterruptible step.

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

boolean temp = *a;
*a = *b;
*b = temp;
}

Figure 2.17 The definition of swap() instruction

➤ How it ensures mutual exclusion:

 A global variable lock is initialized to false.

 Each process has a local variable key, also initialized to true.

Before entering the critical section:

do {
[Type here]

key = true;
while (key == true)
Swap(&lock, &key);
} while (key == true);

Figure : Mutual-exclusion implementation with the swap() instruction

 If lock is false, after swapping, it becomes true and the process enters
the critical section.
 If lock is already true, the process keeps looping until it becomes false.

On exiting the critical section:

lock = false;

✅ Only one process can have lock = true at a time — so mutual exclusion is
maintained.

[Link] Bounded waiting Mutual Exclusion with TestAndSet()

Problem with Simple TestAndSet

A simple version of TestAndSet ensures mutual exclusion, but not bounded waiting —
→ one process may wait indefinitely while others repeatedly enter the critical section
(starvation).

// ---------- Common Data Structures ----------

boolean waiting[n]; // Array indicating which process is waiting
boolean lock = false; // Shared lock variable (false = free, true =
busy)
// ---------- Process Pi ----------
do {
waiting[i] = true; // Mark process Pi as waiting to enter critical
section
key = true; // Local variable to check if lock acquired
while (waiting[i] && key) // Keep trying to acquire lock while still
waiting
key = TestAndSet(&lock); // Atomically test and set lock
waiting[i] = false; // Process Pi got the lock → stop waiting
// ---------- CRITICAL SECTION ----------
// Only one process can be here at a time
// ---------- EXIT SECTION ----------
j = (i + 1) % n; // Find the next process in circular order
[Type here]

while ((j != i) && !waiting[j]) // Search for the next waiting

process
j = (j + 1) % n;
if (j == i) // If no other process is waiting, release the lock
lock = false;
else
waiting[j] = false; // Give permission to the next waiting
process
// ---------- REMAINDER SECTION ----------
// Non-critical work of the process
} while (true);

Figure : Bounded-waiting mutual-exclusion with TestandSet()

Explanation

1. Each process marks itself as waiting.

2. The TestAndSet() ensures only one process sets lock = true and enters
the critical section.
3. After finishing, the process finds the next waiting process and gives
it a chance.
4. This ensures bounded waiting — every process gets a turn in order.

🔹 Key Features

Property Ensured
Mutual Exclusion ✅ Only one process enters at a time
Progress ✅ No unnecessary delay
Bounded Waiting ✅ Each process eventually gets a turn

2.14 – Semaphores

🔹 What is a Semaphore?

 A semaphore is a synchronization tool used to control access to

shared resources (like variables, files, buffers, etc.).
 It ensures that only one process at a time can modify a shared
variable — preventing race conditions.
[Type here]

🔹 Semaphore Definition

 A semaphore (S) is an integer variable.

 It can be accessed only through two atomic operations:
1. wait() → also called P (proberen), meaning “to test.”
2. signal() → also called V (verhogen), meaning “to increment.”

🔹 Operations

1️⃣ wait(S)

wait(S) {
while (S <= 0) ; // Busy-wait until S > 0
S--; // Then decrement S
}

 Used before entering the critical section.

 If S is not positive, the process waits.
 When S > 0, the process decreases it by 1 and proceeds.

2️⃣ signal(S)

signal(S) {
S++; // Increment S
}

 Used after leaving the critical section.

 It increases the semaphore value, allowing other waiting
processes to enter.

🔹 Atomicity

 Both wait() and signal() are atomic operations —

meaning they execute completely without interruption.
 Especially in wait(S), the two steps:
1. Checking S <= 0
[Type here]

2. Decrementing S
must happen together — no other process can interfere in
between.

2.14.1 Semaphore Usage

1️⃣ Binary Semaphore (Mutex Semaphore)

 A binary semaphore can take only two values: 0 or 1.

 It is mainly used to achieve mutual exclusion — that is, to make sure only one process
enters its critical section at a time.
 When a process enters its critical section, the semaphore is set to 0 (locked).
 When the process exits, the semaphore is set back to 1 (unlocked).
 Hence, it works exactly like a mutex lock.

Figure 2.20 Mutual-exclusion implementation with semaphores

Explanation:

 Initially, mutex = 1 (free).

 A process calls wait(mutex) and enters the critical section, setting mutex = 0.
 Other processes trying to enter will wait until mutex becomes 1 again.
 After finishing, signal(mutex) sets mutex = 1, letting another process proceed.

This ensures mutual exclusion.

2️⃣ Counting Semaphore

 A counting semaphore can take any integer value.

 It is useful when there are multiple instances of a resource (like printers, buffers, etc.).
 The semaphore is initialized to the number of available resources (n).
[Type here]

 When a process uses one resource → it performs wait(S) → count decreases.

 When a process releases it → it performs signal(S) → count increases.

semaphore S = n;

Process Pi {

wait(S);

// ---- USING RESOURCE ----

signal(S);

3️⃣ Semaphore for Synchronization

Used to ensure one process executes after another — not for resource sharing, but execution
order.

Example:
P1 should execute statement S1 first, then P2 executes S2.

Program: Synchronization Example

semaphore synch = 0; // initialized to 0, means P2 must wait

Process P1 {
S1; // statement to execute first
signal(synch); // ↑ sets synch = 1 → allows P2 to proceed
}

Process P2 {
wait(synch); // ↓ waits until synch > 0
S2; // executes only after P1 finishes S1
}

Explanation:

 Initially, synch = 0 → P2 is blocked.

 When P1 finishes S1, it does signal(synch) → sets synch = 1.
 Now P2’s wait(synch) succeeds, and P2 executes S2.
[Type here]

Thus, S2 always follows S1.

2.14.2 Semaphore Implementation

 Problem:
The main disadvantage of semaphores is busy waiting.
When a process tries to enter its critical section and the semaphore is locked, it keeps
checking repeatedly (looping) until it becomes free.
This wastes CPU time — known as busy waiting or spinlock.
 Example of busy waiting:
 wait(S); // keeps looping until S > 0

During this time, CPU cycles are wasted.

Solution — Blocking Instead of Busy Waiting

To avoid busy waiting, the process should be blocked (suspended) instead of spinning.

Two system operations are assumed:

1. block() → suspends (stops) the process that calls it.

2. wakeup(P) → resumes the execution of process P.

We redefine the semaphore as a structure:

typedef struct {
int value; // semaphore counter
struct process *list; // queue of waiting processes
} semaphore;

Modified wait() and signal() Operations

wait(S) {
[Link]--; // decrease semaphore value
if ([Link] < 0) { // no resources available
add this process to [Link];
block(); // suspend current process
}
}

signal(S) {
[Link]++; // increase semaphore value
if ([Link] <= 0) { // if some process is waiting
[Type here]

remove a process P from [Link];

wakeup(P); // resume that process
}
}

Explanation

 When wait(S) is called:

o If [Link] > 0 → process continues normally.
o If [Link] ≤ 0 → process cannot proceed, so it is blocked and added to the
waiting list.
 When signal(S) is called:
o It increases [Link].
o If some process was waiting, one process is removed from the queue and
resumed using wakeup().

Thus, CPU is not wasted, and no busy waiting occurs.

In Different Environments

1. Uni-processor system:
o Can disable interrupts while performing wait() and signal() to prevent
other processes from interfering.
2. Multiprocessor system:
o Disabling interrupts doesn’t work globally.
o Use hardware instructions (like TestAndSet, Swap) or software synchronization
methods.

3. 2.14.3 Deadlocks & Starvation

1️⃣ Deadlock

Definition:
When two or more processes keep waiting for each other forever, and none of them can
continue.
In semaphore terms, that event is the execution of a signal() operation.
Example:
Two semaphores — S and Q — both initialized to 1.
[Type here]

Step-by-Step Explanation5

1. Initially,
2. S = 1, Q = 1
3. P0 executes wait(S) → S = 0 (P0 holds S).
4. P1 executes wait(Q) → Q = 0 (P1 holds Q).
5. Now P0 tries wait(Q) → but Q = 0 → so P0 waits.
6. Simultaneously, P1 tries wait(S) → but S = 0 → so P1 waits.

Result:
Both P0 and P1 are waiting forever, each holding one semaphore and waiting for the other.
Neither can reach its signal() statement → hence deadlock.

2️⃣ Starvation (Indefinite Blocking)

Definition:
Starvation occurs when a process waits indefinitely in a queue even though resources eventually
become free.

 It happens when the scheduler or semaphore queue unfairly favors some processes over
others.
 For example, if the waiting list inside the semaphore is managed in LIFO (Last-In-First-
Out) order, new processes may always get preference, and the old ones may never be
resumed.

🧩 Example of Starvation

wait(S); // Process P1 waits

wait(S); // Process P2 waits (added later)
signal(S); // Wakes up P2 (last entered), not P1

If this continues, P1 may never get CPU time → starvation.

[Type here]

✅ Solution

 Use FIFO (First-In-First-Out) order in the semaphore waiting queue.

2.15 Classic Problems of Synchronization

2.15.1 The Bounded-Buffer Problem

 Also known as the Producer–Consumer Problem.

 There are n buffers, each buffer can hold one item.
 The producer creates data items and puts them into the buffer.
 The consumer takes items from the buffer and uses them.

To make sure both don’t access the buffer at the same time, we use semaphores.

Shared Data

int n;
semaphore mutex = 1; // ensures mutual exclusion for buffer access
semaphore empty = n; // counts number of empty buffers
semaphore full = 0; // counts number of full buffers

 mutex → allows only one process (producer or consumer) to access the buffer at a time.
 empty → number of empty slots available.
 full → number of full slots available.

Producer Process

do {
// produce an item
wait(empty); // ↓ check if buffer is [Link] produce
wait(mutex); // ↓ lock the buffer section

// ---- ADD ITEM TO BUFFER ----

signal(mutex); // ↑ unlock buffer

signal(full); // ↑ increase count of full buffers
} while(true);
[Type here]

Consumer Process

do {
wait(full); // ↓ check if full [Link] so Cant consume.
wait(mutex); // ↓ lock buffer section

// ---- REMOVE ITEM FROM BUFFER ----

signal(mutex); // ↑ unlock buffer

signal(empty); // ↑ increase count of empty buffers
// consume the item
} while(true);

Synchronization Rules Ensured

Requirement How it’s Achieved

Mutual Exclusion mutex semaphore
No Buffer Overflow wait(empty) before producer adds
No Buffer Underflow wait(full) before consumer removes

2.15.2 Readers–Writers Problem — Explanation

Concept:
A shared database is used by multiple processes.

 Readers → only read data.

 Writers → read + modify data.

Problem:

 Multiple readers can read at the same time (no conflict).

 But no writer should access data while another reader or writer is using it — to
avoid inconsistency.

Shared Data

semaphore mutex = 1; // ensures mutual exclusion for readcount update

semaphore wrt = 1; // controls writer or first/last reader access
int readcount = 0; // number of active readers
[Type here]

Writer Process

do {
wait(wrt); // writer locks database
// --- WRITING DATA ---
signal(wrt); // writer releases database
} while (true);

Reader Process

do {
wait(mutex); // lock mutex to update readcount safely
readcount++; // increase number of active readers
if (readcount == 1) // if this is the first reader
wait(wrt); // block writers from writing
signal(mutex); // release mutex after updating readcount

// ---- READING DATA ----

// reader is now reading the shared data

wait(mutex); // lock mutex before changing readcount

readcount--; // one reader finished reading
if (readcount == 0) // if this is the last reader
signal(wrt); // allow writers to write again
signal(mutex); // release mutex after updating readcount
} while (true); // repeat for continuous reading

2.15.3 The Dining-Philosophers Problem

Concept:

 5 philosophers sit around a round table with 5 chopsticks.

 Each philosopher alternates between thinking and eating.
 To eat, a philosopher must pick up both chopsticks — the one on the left and the one on
the right.
 After eating, they put both down and start thinking again.

Goal:
Avoid deadlock (no one can eat) and starvation (some never eat).
[Type here]

Shared Data:

semaphore chopstick[5] = {1,1,1,1,1};

Philosopher Process

do {
wait(chopstick[i]); // pick up left chopstick
wait(chopstick[(i+1)%5]); // pick up right chopstick
// ---- EATING ----
signal(chopstick[i]); // put down left chopstick
signal(chopstick[(i+1)%5]); // put down right chopstick
// ---- THINKING ----
} while(true);

Deadlock Prevention Methods:

1. Allow only 4 philosophers to sit at the table at once.

2. Allow philosopher to pick chopsticks only if both are available.
3. Use asymmetric approach:
o Odd philosophers pick left then right.
o Even philosophers pick right then left.

3.1 Deadlocks — Definition

A deadlock is a condition in which two or more processes are permanently blocked, each
holding a resource and waiting for another resource held by some other process.
[Type here]

Real-life Example

Two trains on a single track facing each other —

neither can move forward because both are waiting for the other to move first.

Figure 3.1 Deadlock Situation

Same in OS:
Each process is waiting for a resource held by another process → all are stuck.

Example in OS

Process P1 holds Printer and waits for [Link] P2 holds Scanner and
waits for Printer.
➡️Both wait forever → Deadlock (Figure 3.1).

3.2 System Model

The system has a finite set of resources (like memory, CPU, printers).
Each process follows this sequence while using resources:

Step Action Example

1️⃣ Request resource open(), malloc()
2️⃣ Use resource print, read, write
3️⃣ Release resource close(), free()

If a process cannot get a resource immediately, it must wait.

🔁 Deadlock Example (Figure

 P1 holds R2, needs R1.

 P2 holds R1, needs R2.
[Type here]

 ➡️Both are waiting for each other → No progress → Deadlock.

🧵 Note:

Multithreaded programs are more prone to deadlocks because threads share data and resources
like memory, files, and locks.

3.3 Deadlock Characterization

A deadlock occurs when processes never finish executing because system resources are stuck
(held by waiting processes).
No process can proceed, and no resource can be freed.

🧩 3.3.1 Necessary Conditions for Deadlock

For a deadlock to occur, all four of these conditions must hold simultaneously:

1️⃣ Mutual Exclusion

 At least one resource is non-shareable (only one process can use it at a time).
 If another process requests it, it must wait.
Example: Printer — only one process can print at a time.

2️⃣ Hold and Wait

 A process is holding one resource and waiting for another held by someone else.
🧠 Example:
P1 holds a printer, waits for a scanner.

3️⃣ No Preemption

 Resources cannot be forcibly taken from a process.

 The process must release it voluntarily after finishing.
[Type here]

4️⃣ Circular Wait

 There exists a circular chain of processes {P0, P1, …, Pn} where

o P0 waits for a resource held by P1,
o P1 waits for one held by P2,
o … and Pn waits for one held by P0.

🔁 Example:
P1 → waits for P2 → waits for P3 → waits for P1

✅ In short:
Deadlock occurs only if all four conditions exist together —
👉 Mutual Exclusion + Hold & Wait + No Preemption + Circular Wait

3.3.2 Resource-Allocation Graph (RAG)

A Resource Allocation Graph (RAG) is a directed graph used to represent deadlocks in a

system.

🧩 Components

 V (Vertices) → includes
o P = {P1, P2, …, Pn} → all processes (shown as circles)
o R = {R1, R2, …, Rm} → all resources (shown as rectangles)
 E (Edges) → includes
1️⃣Request Edge (Pi → Rj) → process Pi is waiting for resource Rj
2️⃣ Assignment Edge (Rj → Pi) → resource Rj is assigned to process Pi

🧠 How it works

 When Pi requests Rj, a request edge is drawn.

 When Rj is given to Pi, the request edge is changed to an assignment edge.
 If converting this edge causes a cycle, the system might enter a deadlock.
[Type here]

🧩 Graph Symbols

 Process → ○ (circle)
 Resource → ⬜ (rectangle)
 Edge → → (arrow)

(a) Resource allocation Graph (b) With a deadlock (c) with cycle but no deadlock Figure
3.3 Resource allocation graphs

Three Possible Situations

1️⃣ No Cycle → No Deadlock

2️⃣ Cycle Present → Deadlock Possible
3️⃣ Cycle + One Instance per Resource → Deadlock Exists

✅ Conclusion

Graph Condition Deadlock Status

No Cycle ❌ No Deadlock
Cycle Exists ⚠️Deadlock may exist
Cycle with single instance resources ✅ Deadlock exists

3.4 Methods for Handling Deadlocks

There are 3 ways to deal with deadlocks:
[Type here]

1) Prevention / Avoidance

 Goal: Never allow the system to enter a deadlock.

 System must know in advance what resources a process may request.

2) Detection & Recovery

 Allow deadlock to occur → detect it → fix it by:

o Aborting a process, or
o Taking back (preempting) resources.

3) Ignore Deadlock

 If deadlocks are rare, OS simply does nothing.

 Example: Many operating systems follow this; if deadlock happens → the system slows
→ user restarts.

3.5 Deadlock Prevention

Deadlock happens when all four conditions are true.
To prevent deadlock → break at least one of these:

1. Mutual Exclusion
2. Hold and Wait
3. No Preemption
4. Circular Wait

3.5.1 Mutual Exclusion

 Some resources cannot be shared (printer, tape drive).

→ Mutual exclusion must exist; cannot remove this condition.
 Sharable resources (read-only files) do not cause deadlock.
 Therefore: We cannot prevent deadlocks by removing mutual exclusion, because many
resources are naturally exclusive.

3.5.2 Hold and Wait

[Type here]

To prevent this:

 Do not let a process hold some resources while waiting for more.

Two Protocols

Protocol 1: Request Everything at the Start

 Process must ask for all resources before starting.

 Example: tape drive + disk + printer allocated at the beginning.

Disadvantage:
→ Very low utilization (many resources remain idle).

Protocol 2: Request Only When Holding None

 Process releases all current resources before requesting new ones.

 Flow:
o Get tape drive + disk → work → release
o Then get disk + printer → work → release

Disadvantage:
→ Possible starvation
→ Low resource utilization (frequent release/reacquire cycles)

3.5.3 No Preemption

To prevent deadlock, resources are allowed to be preempted (taken away from a process).

Protocol 1

 A process is holding some resources.

 It requests another resource that is not available.
 Then:
o All currently held resources are preempted.
o These resources are added to the list of resources the process is waiting for.
o The process restarts only after it gets:
 All its old resources
 The new requested resource

➡️Works for resources whose states can be saved/restored.

[Type here]

Protocol 2

 When a process requests a resource, the system checks availability.

 If unavailable → preemption may occur just like Protocol 1.

If (resources are available) then

{
allocate resources to the process
}
else
{
If (resources are allocated to waiting process) then
{
preempt the resources from the waiting process
allocate the resources to the requesting-process the
requesting-process must wait
}

➡️both Works for resources like registers and memory.

❌ both are Not suitable for devices like printers or tape drives.

3.5.4 Circular Wait

Deadlock can be prevented by eliminating circular waiting among processes.

Protocol 1: Resource Ordering

 Assign a unique number to each resource.

 Processes must request resources only in increasing or decreasing order.

This prevents circular chains.

Protocol 2

 Whenever a process requests a resource, it must first release all resources with a lower
number.
[Type here]

This ensures no circular waiting.

Challenge

 Difficult to determine the correct numbering of resources in a complex system.

3.6 Deadlock Avoidance

 Goal: Don’t allow deadlocks to occur at all.
 The system checks every resource request before granting it to make sure the system
will remain safe.

Requirements

Deadlock-avoidance needs extra information about each process:

1. Simple algorithms
→ Need to know the maximum number of each resource a process may require.
2. Complex algorithms
→ Need to know exact order in which the process will request resources.

How avoidance works

 The algorithm looks at the current state of resource allocation.

 It ensures that the system will never move into a circular-wait condition.
 The resource-allocation state includes:
o Number of resources available
o Number of resources allocated
o Maximum demand of each process

3.6.1 Safe State

 A state is safe if the system can satisfy all process requests eventually without
deadlock.
 A state is safe if there exists a safe sequence of processes:
{P0, P1, P2, …, PN}
where each process can get the required resources from currently available resources.

Unsafe State

 If no safe sequence exists, the system is in an unsafe state.

[Type here]

 Unsafe does not always mean deadlock, but it might lead to deadlock.

Figure 3.4 Safe, unsafe, and deadlock state spaces

3.6.2 Resource-Allocation-Graph (RAG) Algorithm

 Works only when each resource type has a single instance.

 Deadlock can be detected by checking for cycles in the RAG.
 To avoid unsafe states, the graph is extended using claim edges (dashed lines).

Claim Edge

 Pi → Rj means process Pi may request Rj in the future.

Steps of the Algorithm

1) Requesting a Resource

 When Pi actually requests Rj →

Convert claim edge Pi → Rj → request edge.

2) Releasing a Resource

 When Pi releases Rj →
Convert assignment edge Rj → Pi → claim edge Pi → Rj.

3) Grant Only If No Cycle

[Type here]

 Request from Pi for Rj is granted only if converting the request edge to an assignment
edge does NOT create a cycle.
 If it creates a cycle → request must be denied to avoid unsafe state.

Requirements

 Each process must declare all future resource claims before starting execution.

Conclusion
1. No cycle → system remains safe, allocation allowed.
2. Cycle exists → system becomes unsafe → potential deadlock → allocation denied.

(a)For deadlock avoidance(b) an unsafe state

Figure 3.5 Resource Allocation graphs

 If P2 requests R2:
o Even though R2 is free, granting it forms a cycle.
o Unsafe, because later:
 P1 may request R2
 P2 may request R1
→ This leads to a deadlock.

Limitation
[Type here]

 This algorithm does NOT work when resources have multiple instances.

Solution

 Use the Banker's Algorithm, which handles multiple instances.

3.6.3 Banker’s Algorithm

 Used when the system has multiple instances of each resource type.
 Less efficient than RAG algorithm but more general.
 Each process must declare its maximum resource requirement before starting.
 When a process requests resources:
o The system checks: Will the system remain in a safe state after granting this?
o If safe → allocate
o If unsafe → process must wait

Assumptions

 n = number of processes
 m = number of resource types

Data Structures Used

1) Available[m]

 Vector showing how many instances of each resource type are currently free.
 Example: Available[j] = k → k instances of resource Rj are free.

2) Max[n][m]

 Matrix showing the maximum resources each process may ever request.
 Example:
Max[i][j] = k → Process Pi may need up to k instances of Rj.

3) Allocation[n][m]

 Matrix showing current allocation.

[Type here]

 Example:
Allocation[i][j] = k → Process Pi is currently holding k instances of Rj.

4) Need[n][m]

 Matrix showing remaining resources each process may still request.

 Need[i][j] = Max[i][j] - Allocation[i][j]

Two Parts of Banker’s Algorithm

1. Safety Algorithm
2. Resource-Request Algorithm

[Link] Safety Algorithm

This checks whether the system is in a safe state.

Assumptions

 Work:
o A temporary copy of Available[].
o Will be updated during the algorithm.
 Finish[n]:
o Boolean array.
o Finish[i] = true means process Pi can complete with current + assumed
resources.

Step 1:

Let Work and Finish be two vectors of length m and n respectively.

Initialize:
Work = Available
Finish[i] = false for i=1,2,3,…….n

Step 2:

Find an index(i) such that both

a) Finish[i] = false
[Type here]

b) Need i <= Work.

If no such i exist, then go to step 4

Step 3:

Set:
Work = Work +
Allocation(i)
Finish[i] = true
Go to step 2

Step 4:

If Finish[i] = true for all i, then the system is in safe state.

[Link] Resource-Request Algorithm

Used to check whether a new resource request from a process can be safely granted.

Let Request(i) be the request vector for process Pi.

If Request(i)[j] = k → process Pi is asking for k instances of resource Rj.

Steps of the Algorithm

Step 1: Check if the request is valid

 Check whether:
 Request(i) ≤ Need(i)
 If Request(i) is greater than its Need, the process is asking for more than its maximum
→ error.

Step 2: Check if resources are available

 Check whether:
 Request(i) ≤ Available
 If resources are not available → process must wait.
[Type here]

Step 3: Pretend to allocate (simulation step)

Temporarily modify the matrices:

1. Available = Available – Request(i)

2. Allocation(i) = Allocation(i) + Request(i)
3. Need(i) = Need(i) – Request(i)

This is just a trial run.

Step 4: Run the Safety Algorithm

 Check whether the system is still in a safe state after the simulated allocation.

Decision

 If the system is safe → grant the request.

 If the system becomes unsafe →
o Roll back the temporary changes
o Deny the request
o Let the process wait

3.6.3.3An Illustrative Example

Question: Consider the following snapshot of a system:

Allocation Max Available

A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 3 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3

Answer the following questions using Banker's algorithm.

i) What is the content of the matrix need?

ii) Is the system in a safe state?
iii) If a request from process P1 arrives for (1 0 2) can the request be granted immediately?
[Type here]

(i) Need matrix (Need = Max − Allocation)

Need
A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1

(ii) Is the system in a safe state? — Yes.

Initial: Work = Available = (3, 3, 2)

Finish = [F, F, F, F, F]

Pick processes whose Need ≤ Work in order:

1. P1: (1,2,2) ≤ (3,3,2) → yes →

Work = Work + Allocation[P1] = (3,3,2) + (2,0,0) = (5,3,2)
Finish[P1] = T
2. P3: (0,1,1) ≤ (5,3,2) → yes →
Work = (5,3,2) + (2,1,1) = (7,4,3)
Finish[P3] = T
3. P4: (4,3,1) ≤ (7,4,3) → yes →
Work = (7,4,3) + (0,0,2) = (7,4,5)
Finish[P4] = T
4. P0: (7,4,3) ≤ (7,4,5) → yes →
Work = (7,4,5) + (0,1,0) = (7,5,5)
Finish[P0] = T
5. P2: (6,0,0) ≤ (7,5,5) → yes →
Work = (7,5,5) + (3,0,2) = (10,5,7)
Finish[P2] = T

All Finish = true → system is safe.

Safe sequence: <P1, P3, P4, P0, P2>.

(iii) Request(P1) = (1,0,2) — Can it be granted?

1. Check Request ≤ Need:

(1,0,2) ≤ (1,2,2) → true
2. Check Request ≤ Available:
(1,0,2) ≤ (3,3,2) → true
3. Pretend to allocate (trial):
o Available' = (3,3,2) - (1,0,2) = (2,3,0)
o Allocation'[P1] = (2,0,0) + (1,0,2) = (3,0,2)
[Type here]

o Need'[P1] = (1,2,2) - (1,0,2) = (0,2,0)

4. Run Safety with Work = Available' = (2,3,0):
Following the safety steps we can find a sequence:
P1 → P3 → P4 → P0 → P2 — all Finish = true.

Conclusion: The resulting state is safe, so the request (1,0,2) by P1 can be granted
immediately.

3.7 Deadlock Detection

If the system does not use

 deadlock prevention, or
 deadlock avoidance,

then deadlocks can occur.

So the OS must provide:

1. A detection algorithm → check if a deadlock has happened.

2. A recovery method → remove/resolve the deadlock.

3.7.1 Single Instance of Each Resource Type

If each resource type has only ONE instance, the detection algorithm uses a Wait-For Graph
(WFG).

Wait-For Graph (WFG)

 A simplified version of Resource-Allocation Graph (RAG).

 It is used only when each resource has one instance.

How WFG is formed from RAG

1. Remove all resource nodes.

2. Collapse edges like this:

If in the RAG:

 Pi → Rq (Pi requests Rq)

 Rq → Pj (Rq allocated to Pj)
[Type here]

Then in the WFG we draw an edge:

 Pi → Pj

Meaning:
Pi is waiting for Pj to release the resource.

Important Rule

 A deadlock exists if and only if the Wait-For Graph contains a cycle.

3.6 Resource-allocation-graph [Link] wait for graph

System must:

 Maintain the Wait-For Graph continuously.

 Regularly run a cycle detection algorithm on the graph.

If a cycle is found → deadlock detected.

3.7.2 Several Instances of a Resource Type

Why a new method is needed?

 The Wait-For Graph works ONLY when each resource has exactly ONE instance.
 When a resource has multiple instances, WFG cannot represent the system properly.

Solution
[Type here]

Use a deadlock detection algorithm similar to the Banker's safety algorithm

(but used only for detection, not avoidance).

Assumptions

 n = number of processes
 m = number of resource types

Data Structures Required

1) Available[m]

 A vector that tells how many instances of each resource are currently free.
 Example: If Available[j] = k,
→ k instances of resource type Rj are available.

2) Allocation[n][m]

 A matrix (n × m)
 Shows how many resources of each type are currently allocated to process Pi.
 Example: If Allocation[i][j] = k,
→ process Pi holds k instances of resource Rj.

3) Request[n][m]

 A matrix (n × m)
 Shows how many more resources each process is requesting.
 Example: If Request[i][j] = k,
→ process Pi is asking for k more instances of Rj.

Step 1:
Let Work and Finish be vectors of length m and n respectively.
a) Initialize Work = Available
b) For i=0,1,2….......n
if
Allocation(i)
!= 0 then
Finish[i] = false;
[Type here]

else
Finish[i] = true;
Step 2:
Find an index(i) such that both
a) Finish[i] = false
b) Request(i) <= Work.
If no such i exist, goto step 4.
Step 3:
Set:
Work = Work +
Allocation(i) Finish[i] =
true
Go to step 2.
Step 4:
If Finish[i] = false for some i where 0 < i < n, then the system is in a deadlock state.

3.7.3 Detection-Algorithm Usage

When should the deadlock detection algorithm run?

It depends on:

1. How often deadlocks occur

2. How many processes get affected when deadlocks occur

Key Points

 If deadlocks happen frequently, run the detection algorithm more often.

 When a deadlock happens, resources held by deadlocked processes remain idle until the
system breaks the deadlock.

Why detection becomes important?

A deadlock happens only when a process requests resources that cannot be granted
immediately.
So the system must decide when to check for deadlocks.

Two Solutions
[Type here]

Solution 1: Run detection whenever a resource request cannot be granted

 If a process asks for resources & the system cannot give them at once → run detection
immediately.
 This helps identify:
o The set of deadlocked processes
o The exact process that caused the deadlock

Solution 2: Run detection periodically

 Execute the detection algorithm at regular time intervals, for example:

o Once every hour
o Whenever CPU utilization drops below a specific threshold
 Useful when deadlocks happen rarely.

3.8 Recovery from Deadlock

When a deadlock is detected, the system must recover.

There are three main recovery approaches:

1. Inform the system operator for manual correction.

2. Terminate one or more deadlocked processes.
3. Preempt (take away) resources from processes.

3.8.1 Process Termination

Deadlock can be removed by killing processes. Two approaches are used:

1) Terminate all deadlocked processes

 Breaks the deadlock immediately.

 Very costly:
o All partial work done by the processes is wasted.
o The work may need to be redone later.
[Type here]

2) Terminate one process at a time

 Kill one process → run detection again → repeat until deadlock is gone.
 This causes high overhead, because detection is repeated after each termination.

Factors to consider before terminating a process

1. Process priority
2. Amount of work already done
3. Resources currently held
4. Additional resources needed to finish
5. How many processes must be killed
6. Whether the process is interactive or batch

3.8.2 Resource Preemption

Instead of killing processes, the system may take resources away from deadlocked processes.

Three issues must be handled:

1) Selecting a Victim

 Choose which process/resource to preempt.

 Try to minimize cost.
 Cost depends on:
o Work done by the process
o Number of resources it holds

2) Rollback

 After taking its resources, a process cannot continue.

 The system must roll it back to a safe state.
 This requires saving extra information about process states.
[Type here]

3) Starvation

Problem:
If selection is always cost-based, the same process may be chosen again and again.

Solution:
Ensure each process is selected as victim only a limited number of times.

More Problems: Refer vtunptesbysri