Deadlock Detection Using Banker’s Algorithm (Safety Algorithm)

 

Deadlock Detection Using Banker’s Algorithm (Safety Algorithm)

---

1. Aim

To detect whether a system is in a deadlocked (unsafe) state by applying the Banker’s Algorithm safety check and to identify a safe sequence if it exists.

---

2. Objective

• To apply Banker’s Algorithm to the current system state

• To determine whether the system is safe or unsafe

• To identify processes that may be deadlocked

---

3. Theory

Banker’s Algorithm

Banker’s Algorithm avoids deadlock by ensuring the system always remains in a safe state.

A system is:

• Safe → if a safe execution sequence exists

• Unsafe (Deadlock-prone) → if no safe sequence exists

When used for deadlock detection:

• If the safety algorithm fails → deadlock detected

---

4. Data Structures Used

Structure	Description
Allocation[n][m]	Currently allocated resources
Max[n][m]	Maximum resource requirement
Need[n][m]	Remaining resource need
Available[m]	Currently available resources
Finish[n]	Process completion status

---

5. Given Process Mix

Processes: P0, P1, P2

Resource Types: R0, R1

---

Allocation Matrix

Process	R0	R1
P0	1	0
P1	0	1
P2	1	1

---

Maximum Requirement Matrix

Process	R0	R1
P0	1	1
P1	1	1
P2	2	2

---

Available Resources

Available = [0, 0]

---

6. Need Matrix Calculation

Need = Max – Allocation

Process	R0	R1
P0	0	1
P1	1	0
P2	1	1

---

7. Banker’s Safety Algorithm (for Detection)

Steps

1. Initialize Work = Available

2. Set Finish[i] = false

3. Find a process such that

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

4. If found:

   • Work = Work + Allocation[i]

   • Finish[i] = true

5. Repeat until no process satisfies the condition

6. If any Finish[i] == false → Deadlock detected

---

8. C Program Implementation (Banker’s Algorithm – Deadlock Detection)

#include <stdio.h>

int main() {
    int n = 3, m = 2;

    int allocation[3][2] = {
        {1, 0},
        {0, 1},
        {1, 1}
    };

    int max[3][2] = {
        {1, 1},
        {1, 1},
        {2, 2}
    };

    int available[2] = {0, 0};

    int need[3][2];
    int finish[3] = {0};
    int work[2];
    int safeSeq[3];
    int count = 0;

    // Calculate Need matrix
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            need[i][j] = max[i][j] - allocation[i][j];

    // Initialize Work = Available
    for (int i = 0; i < m; i++)
        work[i] = available[i];

    // Safety Algorithm
    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] += allocation[i][k];

                    safeSeq[count++] = i;
                    finish[i] = 1;
                    found = 1;
                }
            }
        }
        if (!found)
            break;
    }

    // Deadlock Detection Result
    if (count == n) {
        printf("System is in SAFE state\nSafe sequence: ");
        for (int i = 0; i < n; i++)
            printf("P%d ", safeSeq[i]);
        printf("\n");
    } else {
        printf("System is in DEADLOCK (UNSAFE STATE)\nDeadlocked processes: ");
        for (int i = 0; i < n; i++)
            if (!finish[i])
                printf("P%d ", i);
        printf("\n");
    }

    return 0;
}

---

9. Sample Output

System is in DEADLOCK (UNSAFE STATE)
Deadlocked processes: P0 P1 P2

---

10. Observations

• No process can satisfy Need ≤ Available

• No safe sequence exists

• All processes remain unfinished

---

11. Result

Using Banker’s Algorithm safety check, the system was found to be in an unsafe (deadlocked) state, and the deadlocked processes were successfully identified.