Mumbai University > Information Technology > Sem5 > Operating System

Marks: 10M

Year: Dec 14

• 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 sharable 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 Pre-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.

  

Deadlock Prevention:

1. Elimination of “Mutual Exclusion” Condition:

• Sharable resources need to mutual exclusion (no need to wait for sharable resources)

• Must hold for non-sharable resources.

2. Elimination of “Hold and Wait” Condition:

• Must guarantee that whenever a process requests a resource, it does not hold any other resources.

• Pre-allocation - to require process to request and be allocated all its resources before it begins execution.

• Single allocation – to allow process to request resources only when the process has none.

• Low resource utilization; starvation possible.

3. Elimination of “No pre-emption ” Condition:

• If a process holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released.

• Pre-empted resources are added to the list of resources for which the process is waiting.

• Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting.

4. Elimination of “Circular Wait” Condition:

• To impose a total ordering of all resource types and requires that each process requests resources in an increasing order of enumeration.