Deadlock prevention

Deadlock prevention

Removing the mutual exclusion condition means that no process will have exclusive(not shared) access to a resource
Algorithms that avoid mutual exclusion are called non-blocking synchronization algorithms.


The hold and wait or resource holding conditions may be removed by requiring processes to request all the resources they will need before starting up
Another way is to require processes to request resources only when it has none.
(These algorithms, such as serializing tokens, are known as the all-or-none algorithms.


The no preemption condition may also be difficult or impossible to avoid as a process has to be able to have a resource for a certain amount of time,
Algorithms that allow preemption include lock-free and wait-free algorithms and optimistic concurrency control.


Approaches that avoid circular waits include disabling interrupts during critical sections and using a hierarchy to determine a partial ordering of resources.
The Dijkstra's solution can also be used.


http://en.wikipedia.org/wiki/Deadlock#Distributed_deadlock_prevention

















all four of the conditions are necessary for deadlock to occur, it follows that deadlock might be prevented by denying any one of the conditions.

Elimination of “Mutual Exclusion” Condition
several processes cannot simultaneously share a single resource
This condition is difficult to eliminate because some resources, such as the tap drive and printer, are inherently non-shareable

Elimination of “Hold and Wait” Condition
The first alternative is that a process request be granted all of the resources it needs at once, prior to execution.
The second alternative is to disallow a process from requesting resources whenever it has previously allocated resources.

Elimination of “No-preemption” Condition
When a process release resources the process may lose all its work to that point. One serious consequence of this strategy is the possibility of indefinite postponement (starvation). A process might be held off indefinitely as it repeatedly requests and releases the same resources.

Elimination of “Circular Wait” Condition
The last condition, the circular wait, can be denied by imposing a total ordering on all of the resource types and than forcing, all processes to request the resources in order (increasing or decreasing)


http://www.personal.kent.edu/~rmuhamma/OpSystems/Myos/deadlockPrevent.htm










Preventing Deadlock (by denying one of the conditions)

Denying Mutual Exclusion

Not desirable to deny - we want dedicated resources

Denying Hold-And-Wait

Force processes to request and gain all their resources in one go.

Disadvantages are other processes are made to wait.

A resource which will not be used until the end of a process still has to be requested at the beginning - poor resource utilisation

Denying No Pre-emption

Some non-shareable resources can be pre-empted if the hardware/software saves the context of the interrupted process - but what about printers?

Only partial denial of no pre-emption is possible.

Denying Circular Waiting

Resources are grouped into `Frequency of Use' classes, C1, C2, C3, etc.

All required resources belonging to the same class are requested at the same time in class order

No circular wait because either all required resources one class are held, or process waits until all required resources within a class are available.

Disadvantages are that resources must be requested in an artifical order - not necessarily the order in which they will be used.

http://staff.um.edu.mt/csta1/courses/lectures/csm202/os7.html#2