Banker’s Algorithm -Finding safe execution sequence

 

Banker’s Algorithm

---

1. Aim

To obtain a deadlock-free process mix and simulate Banker’s Algorithm to determine whether the system is in a safe state and to find a safe execution sequence.

---

2. Objectives

• To understand the concept of deadlock avoidance

• To apply Banker’s Algorithm

• To determine whether a system is in a safe or unsafe state

• To find a safe sequence of processes

---

3. Theory

Deadlock

A deadlock occurs when a set of processes are blocked forever, each waiting for resources held by others.

---

Deadlock Avoidance

Deadlock avoidance ensures that the system never enters an unsafe state.
The Banker’s Algorithm is a classic deadlock avoidance algorithm.

---

Banker’s Algorithm

The algorithm checks for system safety by simulating resource allocation and ensuring that:

• There exists a safe sequence

• Each process can finish execution with available resources

If such a sequence exists → Safe State
Otherwise → Unsafe State

---

4. Data Structures Used

Structure	Description
Available	Currently available resources
Max	Maximum resources required by each process
Allocation	Resources currently allocated
Need	Remaining resource requirement (Max - Allocation)

---

5. Given Process Mix (Deadlock-Free Example)

Number of Processes: 5 (P0 – P4)

Number of Resource Types: 3 (A, B, C)

---

Allocation Matrix

Process	A	B	C
P0	0	1	0
P1	2	0	0
P2	3	0	2
P3	2	1	1
P4	0	0	2

---

Maximum Requirement Matrix

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

---

Available Resources

Available = [3, 3, 2]

---

6. Need Matrix Calculation

Need = Max – Allocation

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

---

7. Banker’s Algorithm (Safety Algorithm)

Algorithm Steps

1. Initialize Work = Available

2. Set Finish[i] = false for all processes

3. Find a process such that:

   Need[i] ≤ Work and Finish[i] == false
   

4. Allocate resources:

   Work = Work + Allocation[i]
   Finish[i] = true
   

5. Repeat until all processes finish or no such process exists

---

8. Simulation (Step-by-Step Execution)

Initial Work

Work = [3, 3, 2]

---

Step 1

• P1 can execute (Need ≤ Work)

• Work = [3,3,2] + [2,0,0] = [5,3,2]

Safe Sequence: P1

---

Step 2

• P3 can execute

• Work = [5,3,2] + [2,1,1] = [7,4,3]

Safe Sequence: P1 → P3

---

Step 3

• P4 can execute

• Work = [7,4,3] + [0,0,2] = [7,4,5]

Safe Sequence: P1 → P3 → P4

---

Step 4

• P0 can execute

• Work = [7,4,5] + [0,1,0] = [7,5,5]

Safe Sequence: P1 → P3 → P4 → P0

---

Step 5

• P2 can execute

• Work = [7,5,5] + [3,0,2] = [10,5,7]

---

9. Safe Execution Sequence

✅ Safe Sequence = P1 → P3 → P4 → P0 → P2

Since all processes can complete, the system is in a SAFE STATE.

---

10. C Program Implementation (Banker’s Algorithm)

#include <stdio.h>

int main() {
    int n = 5, m = 3;
    int alloc[5][3] = {
        {0,1,0},
        {2,0,0},
        {3,0,2},
        {2,1,1},
        {0,0,2}
    };

    int max[5][3] = {
        {7,5,3},
        {3,2,2},
        {9,0,2},
        {2,2,2},
        {4,3,3}
    };

    int avail[3] = {3,3,2};
    int need[5][3];
    int finish[5] = {0};
    int safeSeq[5];
    int work[3];

    for (int i = 0; i < m; i++)
        work[i] = avail[i];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            need[i][j] = max[i][j] - alloc[i][j];

    int count = 0;
    while (count < n) {
        int found = 0;
        for (int i = 0; i < n; i++) {
            if (!finish[i]) {
                int j;
                for (j = 0; j < m; j++)
                    if (need[i][j] > work[j])
                        break;

                if (j == m) {
                    for (int k = 0; k < m; k++)
                        work[k] += alloc[i][k];

                    safeSeq[count++] = i;
                    finish[i] = 1;
                    found = 1;
                }
            }
        }
        if (!found) {
            printf("System is in UNSAFE state\n");
            return 0;
        }
    }

    printf("System is in SAFE state\nSafe sequence: ");
    for (int i = 0; i < n; i++)
        printf("P%d ", safeSeq[i]);

    return 0;
}

---

11. Sample Output

System is in SAFE state
Safe sequence: P1 P3 P4 P0 P2

---

12. Result

The given process mix is deadlock-free.
Using Banker’s Algorithm, a safe execution sequence was successfully determined.