written 6.6 years ago by | modified 2.6 years ago by |
Subject: Operating System
Topic: PROCESS COORDINATION
Difficulty: Hard
written 6.6 years ago by | modified 2.6 years ago by |
Subject: Operating System
Topic: PROCESS COORDINATION
Difficulty: Hard
written 6.4 years ago by |
A process requests resources, if those are not available at that time; a process enters into the wait state.
It may happen that waiting processes will never change the state again, because resources requested by the process is occupied by some other process. This is known as deadlock
For example:
In multiprogramming system, suppose two processes are there and each want to print a very large file.
Process A requests permission to use the printer and is granted. Process B then requests permission to use the tape drive and is also granted. Now A asks for the tape drive, B asks for the printer.
At this point both processes are blocked and will remain so forever. This situation is called a deadlock.
Conditions of Deadlock:
Mutual Exclusion:
At least one resource is held in a non-shareable mode; that is only one process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released. Each resource is either currently assigned to exactly one process or is available.
Hold and Wait:
There must exist a process that is holding at least one resource and is waiting to acquire additional resources that are currently being held by another process. Process currently holding resources granted earlier can request new resources.
No Pr-emption:
Resources cannot be pre-empted; i.e. resource can only be released voluntarily by the process holding it, after the process has completed its task. Resources previously granted cannot be forcibly taken away from the process. They must be explicitly released by the process holding them.
Circular Wait:
There exist a set (P0, P1... Pn) of waiting processes such that P0 is waiting for a resource which is held by P1, P1 is waiting for resource which is held by P2. Pn – 1 is waiting for resources which are held by Pn and Pn is waiting for a resource which is held by P0. Thus there must be a circular chain of two or more processes, each of which is waiting for a resource held by the next member of the chain.
Resource allocation graph
Resource Allocation Graph
• Deadlock can be described through a resource allocation graph.
• The RAG consists of a set of vertices P={P1,P2 ,…,P n} of processes and R={R1,R2,…,Rm} of resources.
• A directed edge from a processes to a resource, Pi->R j, implies that Pi has requested Rj.
• A directed edge from a resource to a process, Rj->Pi, implies that Rj has been allocated by Pi.
• If the graph has no cycles, deadlock cannot exist. If the graph has a cycle, deadlock may exist.
Example of a Resource Allocation Graph
REQUEST:
If process Pi has no outstanding request, it can request simultaneously any number (up to multiplicity) of resources R1, R2, ..Rm. The request is represented by adding appropriate requests edges to the RAG of the current state.
ACQUISITION:
If process Pi has outstanding requests and they can all be simultaneously satisfied, then the request edges of these requests are replaced by assignment edges in the RAG of the current state
RELEASE:
If process Pi has no outstanding request then it can release any of the resources it is holding, and remove the corresponding assignment edges from the RAG of the current state.
Process
-Resource Type with 4 instances
-Pi requests instance of Rj
-Pi is holding an instance of Rj
Resource Allocation Graph With A Deadlock
Deadlock Prevention & Avoidance: Ensurethat the system will never enter a deadlock state
Deadlock Detection & Recovery: Detect that a deadlock has occurred and recover
Deadlock Ignorance: Pretend that deadlocks will never occur.
Resource Allocation Graph With A Cycle But No Deadlock
Safe, Unsafe, Deadlock State
• If graph contains no cycles Þ no deadlock.
• If graph contains a cycle Þ then
if only one instance per resource type, then deadlock.
if several instances per resource type,then there is a possibility of deadlock.
Resource-Allocation Graph For Deadlock Avoidance
Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need. The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition.
Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.
Unsafe State In Resource-Allocation Graph