Deadlock Management & Banker’s Algorithm: Coffman Conditions, Safety Algorithm & Solved TU BCA Numericals
Author: Bhuban Subedi | Subject: Operating Systems (CACS251) | Semester: Fourth Semester
In multiprogramming operating systems where multiple processes share finite hardware resources (printers, memory blocks, disk drives, tape units), resource contention can cause a complete system freeze known as a Deadlock.
A Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process in the set.
In the Tribhuvan University (TU) BCA Fourth Semester Operating Systems (CACS251) board examination, solving a complete numerical on Banker’s Safety Algorithm carrying 10 full marks is one of the most reliable and highest-scoring questions.
In this guide, we will analyze Coffman’s 4 conditions, explain Deadlock Prevention vs Avoidance, calculate the Need Matrix, and find the guaranteed Safe Execution Sequence.
1. Coffman’s 4 Necessary Conditions for Deadlock
A deadlock can arise if and only if all four of the following conditions hold simultaneously in a system:
+---+-------------------------------+---------------------------------------------------------------+
| # | Condition | Explanation & Mechanism |
+---+-------------------------------+---------------------------------------------------------------+
| 1 | **Mutual Exclusion** | At least one resource must be non-shareable (held in an |
| | | exclusive mode by only one process at a time). |
+---+-------------------------------+---------------------------------------------------------------+
| 2 | **Hold and Wait** | A process currently holding at least one resource is allowed |
| | | to request and wait for additional resources held by others. |
+---+-------------------------------+---------------------------------------------------------------+
| 3 | **No Preemption** | Resources cannot be forcibly taken away from a process; they |
| | | can only be released voluntarily after completing its task. |
+---+-------------------------------+---------------------------------------------------------------+
| 4 | **Circular Wait** | A closed chain of processes exists $\{P_0, P_1, \dots, P_n\}$ |
| | | where $P_0$ waits for $P_1$, $P_1$ for $P_2$, and $P_n$ for $P_0$.|
+---+-------------------------------+---------------------------------------------------------------+
2. Deadlock Handling Strategies: Prevention vs. Avoidance
+------------------------------------+------------------------------------+
| Deadlock Prevention | Deadlock Avoidance |
+------------------------------------+------------------------------------+
| Eliminates deadlocks by designing | Allows dynamic resource allocation |
| system rules that ensure at least | by analyzing resource requests |
| one of the 4 Coffman conditions | in advance to ensure the system |
| can NEVER physically occur. | never enters an **Unsafe State**. |
+------------------------------------+------------------------------------+
| Leads to low resource utilization. | High resource utilization. |
| Example: Total ordering of locks. | Example: **Banker's Algorithm**. |
+------------------------------------+------------------------------------+
3. Banker’s Algorithm: Data Structures & Mathematical Formulation
For $n$ processes and $m$ resource types:
1. Available[m]: Vector of available instances of each resource type.
2. Max[n][m]: Maximum resource demand of each process.
3. Allocation[n][m]: Resources currently allocated to each process.
4. Need[n][m]: Remaining resources needed by each process.
$$\mathbf{Need[i][j] = Max[i][j] – Allocation[i][j]}$$
4. Solved TU Board Exam Question (Banker’s Algorithm)
The Problem:
*”A system has 5 processes ${P_0, P_1, P_2, P_3, P_4}$ and 3 resource types ${A, B, C}$. Total system resources are: $A = 10, B = 5, C = 7$. At snapshot time $T_0$, the allocation state is:
Process Allocation (A B C) Max Demand (A B C) P0 0 1 0 7 5 3 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
- Calculate the Need Matrix.
- Is the system in a Safe State? Find the Safe Execution Sequence.
- If process $P_1$ requests $(1, 0, 2)$, can the request be granted immediately?” (TU BCA 10 Marks)
Step 1: Calculate Total Allocated & Initial Available Resources
$$\text{Total Allocated } A = 0 + 2 + 3 + 2 + 0 = \mathbf{7}$$
$$\text{Total Allocated } B = 1 + 0 + 0 + 1 + 0 = \mathbf{2}$$
$$\text{Total Allocated } C = 0 + 0 + 2 + 1 + 2 = \mathbf{5}$$
$$\mathbf{Available} = \text{Total System Instances} – \text{Total Allocated}$$
$$\text{Available } A = 10 – 7 = \mathbf{3}$$
$$\text{Available } B = 5 – 2 = \mathbf{3}$$
$$\text{Available } C = 7 – 5 = \mathbf{2}$$
$$\mathbf{Available = [3,\ 3,\ 2]}$$
Step 2: Compute the Need Matrix ($\text{Need} = \text{Max} – \text{Allocation}$)
+---------+------------------+------------------+---------------------+
| Process | Allocation (A B C)| Max Demand (A B C)| Need Matrix (A B C) |
+---------+------------------+------------------+---------------------+
| **P0** | 0 1 0 | 7 5 3 | **7 4 3** |
| **P1** | 2 0 0 | 3 2 2 | **1 2 2** |
| **P2** | 3 0 2 | 9 0 2 | **6 0 0** |
| **P3** | 2 1 1 | 2 2 2 | **0 1 1** |
| **P4** | 0 0 2 | 4 3 3 | **4 3 1** |
+---------+------------------+------------------+---------------------+
Step 3: Execute Banker’s Safety Algorithm
- Available:
[3, 3, 2] -
Finish:
[F, F, F, F, F] -
Check P0: $\text{Need}(7, 4, 3) \le \text{Available}(3, 3, 2)$? False. P0 must wait.
- Check P1: $\text{Need}(1, 2, 2) \le \text{Available}(3, 3, 2)$? True!
- $P_1$ runs and releases its allocated resources:
- $\text{New Available} = [3, 3, 2] + \text{Alloc}(2, 0, 0) = \mathbf{[5,\ 3,\ 2]}$
- Safe Sequence: $\langle P_1 \rangle$
- Check P3: $\text{Need}(0, 1, 1) \le \text{Available}(5, 3, 2)$? True!
- $P_3$ runs and releases its allocated resources:
- $\text{New Available} = [5, 3, 2] + \text{Alloc}(2, 1, 1) = \mathbf{[7,\ 4,\ 3]}$
- Safe Sequence: $\langle P_1, P_3 \rangle$
- Check P0: $\text{Need}(7, 4, 3) \le \text{Available}(7, 4, 3)$? True!
- $P_0$ runs and releases its allocated resources:
- $\text{New Available} = [7, 4, 3] + \text{Alloc}(0, 1, 0) = \mathbf{[7,\ 5,\ 3]}$
- Safe Sequence: $\langle P_1, P_3, P_0 \rangle$
- Check P2: $\text{Need}(6, 0, 0) \le \text{Available}(7, 5, 3)$? True!
- $\text{New Available} = [7, 5, 3] + \text{Alloc}(3, 0, 2) = \mathbf{[10,\ 5,\ 5]}$
- Safe Sequence: $\langle P_1, P_3, P_0, P_2 \rangle$
- Check P4: $\text{Need}(4, 3, 1) \le \text{Available}(10, 5, 5)$? True!
- $\text{New Available} = [10, 5, 5] + \text{Alloc}(0, 0, 2) = \mathbf{[10,\ 5,\ 7]}$
- Safe Sequence: $\langle P_1, P_3, P_0, P_2, P_4 \rangle$
$$\mathbf{Conclusion:}\ \text{The system is in a }\mathbf{SAFE\ STATE}\text{ with Safe Sequence: }\mathbf{\langle P_1,\ P_3,\ P_0,\ P_2,\ P_4 \rangle}$$
Step 4: Resource-Request Algorithm for $P_1$ Request $(1, 0, 2)$
- $\text{Request}_1 (1, 0, 2) \le \text{Need}_1 (1, 2, 2)$ $\implies$ True $\checkmark$
- $\text{Request}_1 (1, 0, 2) \le \text{Available} (3, 3, 2)$ $\implies$ True $\checkmark$
- Temporarily allocate:
- $\text{Available} = [3, 3, 2] – [1, 0, 2] = [2, 3, 0]$
- $\text{Allocation}_1 = [2, 0, 0] + [1, 0, 2] = [3, 0, 2]$
- $\text{Need}_1 = [1, 2, 2] – [1, 0, 2] = [0, 2, 0]$
- Re-running the safety algorithm reveals that $P_1 \to P_3 \to P_0 \to P_2 \to P_4$ remains safe.
$$\mathbf{\therefore The\ request\ can\ be\ granted\ immediately.}$$
Frequently Asked Questions (FAQ)
Q1: Is an Unsafe State always a Deadlock?
No. An unsafe state is not necessarily a deadlock; rather, an unsafe state is a state from which the operating system cannot prevent processes from eventually deadlocking if they all request their maximum declared resources simultaneously.
