Deadlock Prevention in Operating System

To Simulate Algorithm for Deadlock prevention in Operating System

1. EE-332 Operating System
Department of Electrical Engineering | The University of Faisalabad
Zeeshan Iqbal BEE-FA18-022
(Computer)

Experiment # 11

Title:
Deadlock Prevention.
Objective:
To Simulate Algorithm for Deadlock prevention.
Introduction of Deadlock in Operating System:
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.
Consider an example when two trains are coming toward each other on the same track and there
is only one track, none of the trains can move once they are in front of each other. A similar
situation occurs in operating systems when there are
two or more processes that hold some resources and
wait for resources held by other(s). For example, in
the below diagram, Process 1 is holding Resource 1
and waiting for resource 2 which is acquired by
process 2, and process 2 is waiting for resource 1.



Resource Allocation Graph (RAG) in
Operating System:
Resource allocation graph is explained to us what is the state of the system in terms
of processes and resources. Like how many resources are available, how many are allocated
and what is the request of each process. Everything can be represented in terms of the
diagram. One of the advantages of having a diagram is, sometimes it is possible to see a
deadlock directly by using RAG, but then you might not be able to know that by looking at the
table. But the tables are better if the system contains lots of process and resource and Graph
is better if the system contains less number of process and resource.
We know that any graph contains vertices and edges. So RAG also contains vertices and
edges. In RAG vertices are two type –
Process vertex: Every process will be represented as a process vertex. Generally, the
process will be represented with a circle.
Resource vertex: Every resource will be represented as a resource vertex. It is also two type
• Single instance type resource :It represents as a box, inside the box, there will be one dot.
So the number of dots indicate how many instances are present of each resource type.
• Multi-resource instance type resource : It also represents as a box, inside the box, there
will be many dots present.

2. EE-332 Operating System
Department of Electrical Engineering | The University of Faisalabad
Zeeshan Iqbal BEE-FA18-022
(Computer)

Now coming to the edges of RAG.There are two types of edges in RAG –

1. Assign Edge – If you already assign a resource to a process then it is called Assign edge.
2. Request Edge – It means in future the process might want some resource to complete the
execution, that is called request edge.

Example 1 (Single instances RAG)

3. EE-332 Operating System
Department of Electrical Engineering | The University of Faisalabad
Zeeshan Iqbal BEE-FA18-022
(Computer)

Example 2 (Multi-instances RAG) –

Algorithm for Deadlock prevention:
• Start the program
• Attacking Mutex condition: never grant exclusive access. But this may not be possible
for several resources.
• Attacking preemption: not something you want to do.
• Attacking hold and wait condition: make a process hold at the most 1 resource
• At a time. Make all the requests at the beginning. Nothing policy. If you feel, retry.
• Attacking circular wait: Order all the resources. Make sure that the requests are issued
in the Correct order so that there are no cycles present in the resource graph. Resources
numbered 1 ... n.
• Resources can be requested only in increasing
• Order. i.e. you cannot request a resource whose no is less than any you may be holding.
• Stop the program

PROGRAM: (SIMULATE ALGORITHM FOR DEADLOCK PREVENTION)
#include <stdio.h>
#include <stdlib.h>
int main()
{
int Max[10][10], need[10][10], alloc[10][10], avail[10], completed[10], safeSequence[10];
int p, r, i, j, process, count;
count = 0;

printf("Enter the no of processes : ");
scanf("%d", &p);

for(i = 0; i< p; i++)
completed[i] = 0;

4. EE-332 Operating System
Department of Electrical Engineering | The University of Faisalabad
Zeeshan Iqbal BEE-FA18-022
(Computer)

printf("\n\nEnter the no of resources : ");
scanf("%d", &r);

printf("\n\nEnter the Max Matrix for each process : ");
for(i = 0; i < p; i++)
{
printf("\nFor process %d : ", i + 1);
for(j = 0; j < r; j++)
scanf("%d", &Max[i][j]);
}

printf("\n\nEnter the allocation for each process : ");
for(i = 0; i < p; i++)
{
printf("\nFor process %d : ",i + 1);
for(j = 0; j < r; j++)
scanf("%d", &alloc[i][j]);
}

printf("\n\nEnter the Available Resources : ");
for(i = 0; i < r; i++)
scanf("%d", &avail[i]);

for(i = 0; i < p; i++)

for(j = 0; j < r; j++)
need[i][j] = Max[i][j] - alloc[i][j];

do
{
printf("\n Max matrix:\tAllocation matrix:\n");

for(i = 0; i < p; i++)
{
for( j = 0; j < r; j++)
printf("%d ", Max[i][j]);
printf("\t\t");
for( j = 0; j < r; j++)
printf("%d ", alloc[i][j]);
printf("\n");
}

process = -1;

5. EE-332 Operating System
Department of Electrical Engineering | The University of Faisalabad
Zeeshan Iqbal BEE-FA18-022
(Computer)

for(i = 0; i < p; i++)
{
if(completed[i] == 0)//if not completed
{
process = i ;
for(j = 0; j < r; j++)
{
if(avail[j] < need[i][j])
{
process = -1;
break;
}
}
}
if(process != -1)
break;
}

if(process != -1)
{
printf("\nProcess %d runs to completion!", process + 1);
safeSequence[count] = process + 1;
count++;
for(j = 0; j < r; j++)
{
avail[j] += alloc[process][j];
alloc[process][j] = 0;
Max[process][j] = 0;
completed[process] = 1;
}
}
}
while(count != p && process != -1);
if(count == p)
{
printf("\nThe system is in a safe state!!\n");
printf("Safe Sequence : < ");
for( i = 0; i < p; i++)
printf("%d ", safeSequence[i]);
printf(">\n");
}
else
printf("\nThe system is in an unsafe state!!");

6. EE-332 Operating System
Department of Electrical Engineering | The University of Faisalabad
Zeeshan Iqbal BEE-FA18-022
(Computer)
}

OUTPUT: