Vidyavardhini’s College of Engineering Technology
Department of Computer Engineering
Academic Year : 2024-25
Experiment No.7
Implement deadlock detection and avoidance using Banker’s algorithm.
Date of Performance: 20/02/2025
Date of Submission:06/03/2025
CSL403: Operating System Lab
Vidyavardhini’s College of Engineering Technology
Department of Computer Engineering
Academic Year : 2024-25
Aim: To study and implement deadlock detection and avoidance using Banker’s algorithm.
Objective: The banker’s algorithm is a resource allocation and deadlock avoidance algorithm
that tests for safety by simulating the allocation for predetermined maximum possible amounts of
all resources, then makes an “s-state” check to test for possible activities, before deciding
whether allocation should be allowed to continue.
Theory:
Data Structures for the Banker’s Algorithm.
Let n = number of processes, and m = number of resources types.
1. Available: Vector of length m. If available [j] = k, there are k instances of resource type Rj
available
2.Max: n x m matrix.
If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj
3. Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj
4.Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete
its task
Need [i,j] = Max[i,j] – Allocation [i,j]
Safety Algorithm
1. Let Work and Finish be vectors of length m and n, respectively. Initialize:
CSL403: Operating System Lab
Vidyavardhini’s College of Engineering Technology
Department of Computer Engineering
Academic Year : 2024-25
Work = Available
Finish [i] = false for i = 0, 1, …, n- 1
2. Find an i such that both:
(a) Finish [i] = false
(b) Needi £ Work
If no such i exists, go to step 4
3. Work = Work + Allocationi
Finish[i] = true
go to step 2
4. If Finish [i] == true for all i, then the system is in a safe state.
Resource-Request Algorithm for Process Pi
Request i = request vector for process Pi . If Requesti [j] = k then process Pi wants k
instances of resource type Rj
1. If Requesti £ Needi go to step 2. Otherwise, raise error condition, since process has
exceeded its maximum claim
2. If Requesti £ Available, go to step 3. Otherwise Pi must wait, since resources are not
available 3. Pretend to allocate requested resources to Pi by modifying the state as
follows:
Available = Available – Requesti ;
Allocationi = Allocationi + Requesti ;
CSL403: Operating System Lab
Vidyavardhini’s College of Engineering Technology
Department of Computer Engineering
Academic Year : 2024-25
Needi = Needi – Requesti ;
1.If safe Þ the resources are allocated to Pi
2. If unsafe Þ Pi must wait, and the old resource-allocation state is restored.
Program:
#include <stdio.h>
void main() {
int k = 0, a = 0, b = 0, instance[5], availability[5], allocated[10][5],
need[10][5], MAX[10][5], process, P[10], op[10], no_of_resources,
cnt = 0, i, j;
printf("\nEnter the number of resources: ");
scanf("%d", &no_of_resources);
printf("\nEnter the max instances of each resource:\n");
for (i = 0; i < no_of_resources; i++) {
availability[i] = 0;
printf("%c = ", (i + 97));
scanf("%d", &instance[i]);
printf("\nEnter the number of processes: ");
scanf("%d", &process);
printf("\nEnter the allocation matrix:\n ");
for (i = 0; i < no_of_resources; i++)
printf(" %c", (i + 97));
CSL403: Operating System Lab
Vidyavardhini’s College of Engineering Technology
Department of Computer Engineering
Academic Year : 2024-25
printf("\n");
for (i = 0; i < process; i++) {
P[i] = i;
printf("P[%d] ", P[i]);
for (j = 0; j < no_of_resources; j++) {
scanf("%d", &allocated[i][j]);
availability[j] += allocated[i][j];
printf("\nEnter the MAX matrix:\n ");
for (i = 0; i < no_of_resources; i++) {
printf(" %c", (i + 97));
availability[i] = instance[i] - availability[i]; // Correcting the available resources
printf("\n");
for (i = 0; i < process; i++) {
printf("P[%d] ", i);
for (j = 0; j < no_of_resources; j++) {
scanf("%d", &MAX[i][j]);
printf("\n");
CSL403: Operating System Lab
Vidyavardhini’s College of Engineering Technology
Department of Computer Engineering
Academic Year : 2024-25
A:
a = -1;
for (i = 0; i < process; i++) {
cnt = 0;
b = P[i];
for (j = 0; j < no_of_resources; j++) {
need[b][j] = MAX[b][j] - allocated[b][j];
if (need[b][j] <= availability[j])
cnt++;
if (cnt == no_of_resources) {
op[k++] = P[i];
for (j = 0; j < no_of_resources; j++)
availability[j] += allocated[b][j];
} else {
P[++a] = P[i];
if (a != -1) {
process = a + 1;
goto A;
CSL403: Operating System Lab
Vidyavardhini’s College of Engineering Technology
Department of Computer Engineering
Academic Year : 2024-25
printf("\nSafe Sequence: <");
for (i = 0; i < k; i++)
printf(" P[%d] ", op[i]);
printf(">\n");
return;
Output:
CSL403: Operating System Lab
Vidyavardhini’s College of Engineering Technology
Department of Computer Engineering
Academic Year : 2024-25
Conclusion: Comment on how Banker’s algorithm is useful in deadlock detection and
avoidance.
The Banker's Algorithm is used in deadlock avoidance. It ensures that resource requests are
granted only if they maintain the system in a safe state, preventing deadlock. It does this by
simulating resource allocation and checking if all processes can eventually finish without leading
to circular dependencies. It does not detect deadlocks but prevents them from occurring.
CSL403: Operating System Lab
