Deadlock prevention

From WikiEducator
Jump to: navigation, search

For a deadlock to occur, each of the four necessary conditions must hold. By ensuring that at least one of these conditions cannot hold, we can prevent the occurrence of a deadlock.

Mutual Exclusion

The mutual exclusion condition must hold for non-sharable types of resources. For example, a printer cannot be simultaneously shared by several processes. Read only files are a good example of a sharable resource. If several processes attempt to open a read only file at the same time, they can be granted simultaneous access to the file. In general, however, it is not possible to prevent deadlocks by denying the mutual exclusion condition. Some resources are intrinsically non-sharable.

Hold and Wait

In order to ensure that hold and wait condition never holds in the system, we must guarantee that whenever a process requests a resource it does not hold any other resources. Two protocols can be used for this:

First protocol: Each process requests and be allocated all of its resources before it begins execution. This provision can be implemented by requiring that system calls requesting resources for a particular process precede any other system calls.

Second protocol: A process requests resources only when it has none. A process may request some resources and use them. Before it can request any additional resources, however, it must release all the resources that it is currently allocated.

Disadvantages for the above two protocols include:

Low resource utilization Starvation is possible

No Preemption

In order to ensure that this condition does not hold, the following protocol may be used. If the process that is holding some resources requests another resource that cannot be immediately allocated to it (i.e. the process must wait), then all resources currently being held are preempted i.e. these resources are implicitly released. The preempted resources are added to the list of resources for which the process is waiting. The process will only be restarted when it can regain its old resources, as well as the new ones that it is requesting.

Circular Wait

In order to ensure that the circular wait condition never holds, we may impose a total ordering of all resource types i.e. we assign to each resource type a unique integer number which allows us to compare two resources and determine whether one precedes another in our ordering.