DEADLOCKS IN OPERATING SYSTEM
Deadlocks
We all know today's Operating Systems provide multiprogramming facility.Multiprogramming is the ability of system to execute or run two or more task simultaneously, over here CPU switches from one job to other giving a feel that more tasks are running at same time.
And we are also familiar with the fact that an OS(operating system) consists of several processes and it also has fixed number of resource.So what happens over here is these process compete for the resource.An OS is a resource allocator and its responsibility is to manage and allocate resource without any complexities.
Lets assume we have a process Pi requesting for the resource say Ri. If this resource is available then OS actually grants the process request else it is asked to wait unless the resource Ri is free.Now there would be a situation where this process Pi waits forever resulting into a deadlock.
Deadlock is a situation where a set of process waits for an event that is generated by other process which in turn waits for another.
Lets consider a real world example:
suppose there are two trains t1 and t2 both approaching a crossing.Neither of them can move unless any one train stops and gives a way to other.
Now comes the most important thing i.e Resource.These are of following types:
1.CPU cycles 2.Memory 3.Files 4.I/O devices
The system consist of several instance for the same resource type.Ex:for files system can have 2 files,3 or more in number.So these are said instances of resource type.
Lets talk about two scenarios of Deadlock:
1.Deadlock with Same Resource Type 2.Deadlock with Different Resource Type
1.Deadlock with Same Resource Type:
Lets assume we have a system with 3 CDRW,each one is held by separate process. p1CDRW1 p2CDRW2 p3 CDRW3
to accomplish their task if these process require accessing each others resource then this would lead to a deadlock having same resource type.
2.Deadlock with Different Resource Type
We suppose a system with resources Printer held by process pi and DVDRW held by process pj.Now the task is to read the contents from the DVD and print it.This requires both process to access each others resource which will inturn lead to a Deadlock with Different Resource Type.
Before a process access the resource it has to request for that resource.
As soon as process enters into the system it has to specify the max number of instances for each resource type. And the request should not be greater than the number of resource available in the system.
(Request <= Available)
A process access the resource in following steps:
1.request() This system call helps a process to request for the resource.If the resource is not available immediately then process has to wait unless it is available.
2.use After acquiring the resource process finishes its tasks and releases the resource before termination.
3.release() This system call helps a process to release the resource which can be utilized by other waiting process.
DEADLOCK CHARACTERIZATION
Deadlock occurs when few criteria's are met.Now Lets focus on
> Necessary Conditions For Deadlock
> Resource Allocation Graph
Necessary Conditions For Deadlock A Deadlocked process never stops executing and hold all the resource allocated leaving others to wait for them
Following are the conditions which should get satisfied for a deadlock to occur.
- Mutual Exclusion
- Hold and Wait
- No Preemption
- Circular Wait
- > Mutual Exclusion:
It states that no two process should be in their critical section at the same time.Critical section is the segment of code which every process has and it helps to update the file,modify the table content and perform certain operations.
Eg. printer cant be accessed simultaneously by several process.
In other way only one process should access the resource at a time.
- >Hold and Wait
If a process has resource say a file and is requesting another resource let this be a printer.Then this is hold and wait condition
- >No preemption
It states that resource once allotted to process should not be preempted unless the process terminates or does it explicitly.
- >Circular Wait
We have a set of process in the system{p0,p1,p2,....pn} In this each process in the set waits for the resource held by other process.Thus forming a cycle.p0 waits for resource held by p1, p1 waits for the resource held by p2 and so on.
Resource Allocation Graph
This aims to describe the deadlocks in the system and allocation of resource to every process.Like any other graph it has set of vertices and edges.
As u can see from figure vertices are of two kind.
1. process circular one's
2.resource rectangular one's
as every resource has several instances in the system they are represented in graph by dots.
Edges connecting vertices are of two types . 1.Request Edge: an edge from process Pi to Resource Ri means process is requesting the resource and is waiting for it. 2.Assignment Edge
an edge from instance of resource type Ri to process Pj means that instances of the resource type has been allotted to process Pj.
A process has to request for the resource before accessing it.
If the resource allocation graph contains a cycle then a deadlock will occur.If the graph doesnt have a cycle then system is safe and no chance of deadlock.
No comments:
Post a Comment