Module 3: Process Synchronization Operating Systems

Operating Systems — Module 3 (Part 3)

Deadlocks and Synchronization (Q57 – Q64)

Q57. What are the four conditions that create dead-

lock?
A deadlock situation can arise if and only if the following four conditions hold simulta-
neously in a system (known as the Coffman conditions):

1. Mutual Exclusion: At least one resource must be held in a non-shareable mode.

If another process requests that resource, the requesting process must be delayed
until the resource has been released.
2. Hold and Wait: A process must be holding at least one resource and waiting to
acquire additional resources that are currently being held by other processes.
3. No Preemption: Resources cannot be preempted; that is, a resource can be
released only voluntarily by the process holding it, after that process has completed
its task.
4. Circular Wait: There must exist a set {P0 , P1 , . . . , Pn } of waiting processes such
that P0 is waiting for a resource held by P1 , P1 is waiting for a resource held by P2 ,
. . . , Pn−1 is waiting for a resource held by Pn , and Pn is waiting for a resource held
by P0 .

Q58. How can the hold-and-wait condition be pre-

vented?
To prevent the hold-and-wait condition, the system must guarantee that whenever a
process requests a resource, it does not hold any other resources.
Methods to achieve this:

• Protocol 1 (Pre-allocation): Require each process to request and be allocated

all its resources before it begins execution.
• Protocol 2 (Release before Request): Allow a process to request resources
only when the process has none. Before it can request any additional resources, it
must release all the resources that it is currently allocated.

Disadvantages:

• Low Resource Utilization: Resources may be allocated but unused for a long
period (e.g., a process holding a printer while computing for hours before printing).

Page 1
Module 3: Process Synchronization Operating Systems

• Starvation: A process that needs several popular resources may have to wait
indefinitely, as at least one of the resources may always be allocated to some other
process.

Q59. List two ways in which the no preemption con-

dition can be prevented.
To prevent the ”no preemption” condition, the OS must be allowed to forcefully take
away resources from a process. Two ways to do this are:

1. Preempting the Requesting Process: If a process is holding some resources

and requests another resource that cannot be immediately allocated to it, then all
resources currently being held by this process are preempted (implicitly released).
The process will be restarted only when it can regain its old resources, as well as
the new ones that it is requesting.
2. Preempting the Waiting Process: If a process requests a resource, we check if it
is available. If it is held by another process that is waiting for additional resources,
we preempt the desired resource from the waiting process and allocate it to the
requesting process.

Note: These protocols are often applied to resources whose state can be easily saved and
restored later, such as CPU registers and memory space. They cannot generally be applied
to resources like printers.

Q60. How can the circular wait condition be pre-

vented?
The circular-wait condition is the easiest of the four conditions to prevent.
Method: Total Ordering of Resources We impose a linear ordering of all resource
types. Let R = {R1 , R2 , . . . , Rm } be the set of resource types. We assign to each resource
type a unique integer number, which allows us to compare two resources and to deter-
mine whether one precedes another in our ordering. For example: F (Tape Drive) = 1,
F (Disk Drive) = 5, F (Printer) = 12.
The Rule:

• A process must request resources in an strictly increasing order of enumeration.

• That is, a process can request resource Rj only if F (Rj ) > F (Ri ) for all resources
Ri that the process is currently holding.
• If a process needs a lower-numbered resource, it must first release all higher-
numbered resources it holds.

By enforcing this strict chronological ordering, it is mathematically impossible for a cycle

to form, thus preventing deadlock.

Page 2
Module 3: Process Synchronization Operating Systems

Q61. What is the difference among deadlock avoid-

ance, detection and prevention?

Feature Prevention Avoidance Detection & Re-

covery

Basic Idea Design the system Allow the 4 con- Do not restrict
rules so that at ditions, but use the system at all.
least one of the 4 an algorithm (like Allow deadlocks
Coffman conditions Banker’s) to dy- to happen, detect
cannot hold. namically check them periodically,
every request to and recover.
ensure the system
stays in a ”Safe
State”.
Strictness Very strict. Im- Moderately strict. Least strict. Al-
poses heavy Requires advance lows maximum
constraints on knowledge of max- concurrency until a
processes. imum resource problem occurs.
needs.
Resource Utilization Very low (due to Moderate to High. Highest (until a
pre-allocation or deadlock actually
forced preemp- occurs).
tion).
Overhead Low runtime over- High runtime over- Periodic overhead
head, but high con- head (must run (running cycle
ceptual restriction. safety algorithm on detection algo-
every request). rithms).

Page 3
Module 3: Process Synchronization Operating Systems

Q62. Numerical on Resource allocation graph.

Resource Allocation Graph (RAG)

A RAG is a directed graph consisting of a set of vertices V and a set of edges E.
Vertices are partitioned into two types: Processes P = {P1 , P2 , . . . , Pn } (represented
as circles) and Resource Types R = {R1 , R2 , . . . , Rm } (represented as rectangles).

• Request Edge: Pi → Rj (Process Pi requests an instance of Rj ).

• Assignment Edge: Rj → Pi (An instance of Rj is allocated to Pi ).

Problem Statement: Consider the following system state:

• Processes: P1 , P2 , P3

• Resources: R1 , R2 , R3 (each with exactly 1 instance).

• Allocations: P1 holds R1 ; P2 holds R2 ; P3 holds R3 .

• Requests: P1 requests R2 ; P2 requests R3 ; P3 requests R1 .

Draw the RAG and determine if the system is in a deadlock.

Solution:

P1

R1 R2

P3 P2

R3

Analysis: In a graph where every resource type has exactly one instance, a cycle implies
that a deadlock has occurred. Tracing the path: P1 → R2 → P2 → R3 → P3 → R1 → P1 .
A cycle exists. Therefore, the system is in a Deadlock state.

Page 4
Module 3: Process Synchronization Operating Systems

Q63. Numerical on banker’s algorithm.

Problem Statement: Consider a system with 5 processes (P0 through P4 ) and 3 re-
source types (A, B, C). Resource A has 10 instances, B has 5 instances, and C has 7
instances. Suppose at time T0 , the following snapshot of the system has been taken:

Allocation Max Available

Process 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 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3

Questions: 1. Find the contents of the Need matrix. 2. Is the system in a safe state?
If so, find the safe sequence.

Solution Step 1: Calculate the Need Matrix Formula: Need[i, j] = Max[i, j] −

Allocation[i, j]

Process A B C

P0 (7-0)=7 (5-1)=4 (3-0)=3

P1 (3-2)=1 (2-0)=2 (2-0)=2
P2 (9-3)=6 (0-0)=0 (2-2)=0
P3 (2-2)=0 (2-1)=1 (2-1)=1
P4 (4-0)=4 (3-0)=3 (3-2)=1

Solution Step 2: Apply the Safety Algorithm Initialize ‘Work‘ = ‘Available‘ = (3,
3, 2). ‘Finish‘ array = (False, False, False, False, False).

• Step 1: Find Pi such that Finish[i] == False and Needi ≤ Work.

– Try P0 : Need(7,4,3) ̸≤ Work(3,3,2). Skip.
– Try P1 : Need(1,2,2) ≤ Work(3,3,2). Execute P1 .
• Update after P1 : Work = Work + Allocation1 = (3, 3, 2) + (2, 0, 0) = (5, 3, 2).
Finish[1] = True. Sequence so far: ⟨P1 ⟩.
• Step 2: Check remaining processes.
– Try P2 : Need(6,0,0) ̸≤ Work(5,3,2). Skip.

Page 5
Module 3: Process Synchronization Operating Systems

– Try P3 : Need(0,1,1) ≤ Work(5,3,2). Execute P3 .

• Update after P3 : Work = (5, 3, 2) + (2, 1, 1) = (7, 4, 3).

Finish[3] = True. Sequence: ⟨P1 , P3 ⟩.

• Step 3: Check remaining processes.

– Try P4 : Need(4,3,1) ≤ Work(7,4,3). Execute P4 .

• Update after P4 : Work = (7, 4, 3) + (0, 0, 2) = (7, 4, 5).

Finish[4] = True. Sequence: ⟨P1 , P3 , P4 ⟩.

• Step 4: Re-evaluate skipped processes.

– Try P0 : Need(7,4,3) ≤ Work(7,4,5). Execute P0 .

• Update after P0 : Work = (7, 4, 5) + (0, 1, 0) = (7, 5, 5).

Finish[0] = True. Sequence: ⟨P1 , P3 , P4 , P0 ⟩.

• Step 5: Finally, check P2 .

– Try P2 : Need(6,0,0) ≤ Work(7,5,5). Execute P2 .

• Update after P2 : Work = (7, 5, 5) + (3, 0, 2) = (10, 5, 7).

Finish[2] = True. Sequence: ⟨P1 , P3 , P4 , P0 , P2 ⟩.

Conclusion: Since all processes in the ‘Finish‘ array are ‘True‘, the system is in a Safe
State. The Safe Sequence is: ⟨P1 , P3 , P4 , P0 , P2 ⟩.

Page 6
Module 3: Process Synchronization Operating Systems

Q64. What is thrashing? How is it handled?

(Note: Although this topic generally belongs to Memory Management, it is addressed here
as part of the requested question set.)
Thrashing
A system is in a state of thrashing if a process is spending more time paging (swap-
ping pages in and out of the backing store/disk) than executing actual instructions.
It results in a severe performance collapse.

Cause of Thrashing: Thrashing occurs when the system has too high a Degree of
Multiprogramming. The OS tries to run too many processes at once, meaning no single
process has enough memory frames to hold its actively used pages (its working set). As a
result, processes constantly trigger page faults. The CPU scheduler sees decreasing CPU
utilization (because processes are waiting for I/O page swaps), so it admits even more
processes, making the situation worse.

CPU Utilization

Normal Setup

Thrashing
(Sudden Drop)

Degree of Multiprogramming

How is Thrashing Handled? To prevent or handle thrashing, the operating system

must provide a process with as many frames as it currently needs. Two primary techniques
are used:

1. Working-Set Model: This model assumes the principle of locality. The OS tracks
the set of pages in the most recent ∆ page references (the working set). If the total
sum of the working-set sizes of all processes exceeds the total number of available
frames, the OS suspends one or more processes to free up frames and stop the
thrashing.

2. Page-Fault Frequency (PFF): This is a more direct approach. The OS sets an

upper and lower bound on the desired page-fault rate.

• If the actual page-fault rate exceeds the upper limit, the process needs more
frames, so the OS allocates them.
• If the rate falls below the lower limit, the process has too many frames, so
the OS takes frames away from it.

Page 7
Module 3: Process Synchronization Operating Systems

• If the rate is high and no free frames are available, a process must be suspended.

End of Module 3 Notes

Page 8