What the difference between deadlock avoidance and deadlock prevention?

Question

I have heard both of these terms used, are they the same thing or different things?

Answer 1

Deadlock:

A deadlock is a situation where two or more competing actions are each waiting for the other to finish, and thus neither ever does. It can also be defined as a set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.

For example if there is a system with two disk drives. If there are two processes P1 and P2 each hold one disk drive and each needs the other one, then the situation of deadlock occurs. The following conditions will be held simultaneously in case of deadlock:

• Mutual exclusion: only one process at a time can use a resource

• Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes

• No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task

• Circular wait: there exists a set {P0, P1, …, Pn} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.

Differences between Deadlock prevention, avoidance and detection are as follows:

Prevention:

• The goal is to ensure that at least one of the necessary conditions for deadlock can never hold.

• Deadlock prevention is often impossible to implement.

• The system does not require additional a priori information regarding the overall potential use of each resource for each process.

• In order for the system to prevent the deadlock condition it does not need to know all the details of all resources in existence, available and requested.

• Deadlock prevention techniques include non-blocking synchronization algorithms, serializing tokens, Dijkstra's algorithm etc.

• Resource allocation strategy for deadlock prevention is conservative, it under commits the resources.

• All resources are requested at once.

• In some cases preempts more than often necessary.

Avoidance:

• The goal for deadlock avoidance is to the system must not enter an unsafe state.

• Deadlock avoidance is often impossible to implement.

• The system requires additional a priori information regarding the overall potential use of each resource for each process.

• In order for the system to be able to figure out whether the next state will be safe or unsafe, it must know in advance at any time the number and type of all resources in existence, available, and requested.

• Deadlock avoidance techniques include Banker’s algorithm, Wait/Die, Wound/Wait etc.

• Resource allocation strategy for deadlock avoidance selects midway between that of detection and prevention.

• Needs to be manipulated until at least one safe path is found.

• There is no preemption.

Detection:

• The goal is to detect the deadlock after it occurs or before it occurs.

• Detecting the possibility of a deadlock before it occurs is much more difficult and is, in fact, generally undecidable. However, in specific environments, using specific means of locking resources, deadlock detection may be decidable.

• The system does not requires additional a priori information regarding the overall potential use of each resource for each process in all cases.

• In order for the system to detect the deadlock condition it does not need to know all the details of all resources in existence, available and requested.

• A deadlock detection technique includes, but is not limited to, Model checking. This approach constructs a Finite State-model on which it performs a progress analysis and finds all possible terminal sets in the model.

• Resource allocation strategy for deadlock detection is very liberal. Resources are granted as requested.

• Needs to be invoked periodically to test for deadlock.

• Preemption is seen.