Subject: Operating System

Topic : Process And Process Scheduling

Difficulty: Hard

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

Principles of Deadlock:

Deadlock characteristics

• Permanent blocking of a set of processes that either compete for system resources or communicate with each other.

• No efficient solutions

• Involve conflicting needs for resources by two or more processes.

Types of resources

• Reusable: Used by only one process at a time and is not depleted by that use.

• Consumable: Can be created (produced) and destroyed (consumed).

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 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:

That the system never enters a deadlock state. It provides a set of methods to make sure that at least one of the four necessary conditions for a deadlock is never satisfied.

Elimination of “Mutual Exclusion” Condition:

This condition is needed to be checked for non-shareable resources (e.g. Printer)

• Shareable resources need to have mutual exclusion (no need to wait for shareable resources)

• Must hold for non-shareable resources.

Elimination of “Hold and Wait” Condition:

It requires a process to request a resource and get allocated before execution or allow process to request resources when the process has none.

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

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.

Elimination of “Circular Wait” Condition:

•we can impose a total ordering of all resource types, and ask that each process requests resources in an increasing order of enumeration.

Disadvantage is that it can lead to low device utilization and reduced system throughput.

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