Deadlocks Flashcards
Each process utilizes a resource as follows:
Request
Use
Release
Deadlock Conditions?
Mutual Exclusion
Hold and Wait
No Preemption
Circular Wait
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 of waiting processes such that P0 is waiting for a resoruce that is help by P1, P1 is waiting for a resource that is held by P2
2 edges?
Request Edge
Assignment Edge
Basic Facts of deadlock?
If graph contains no cycles - no deadlock
If graph contains a cycle -> if only one instance per resource type, then deadlock
if several instances per resource type, possibility of deadlock
Methods for handling deadlocks?
Deadlock Prevention
Deadlock Avoidance
Deadlock Prevention?
Mutual Exclusion
Hold and Wait
Deadlock Avoidance?
Requires that the system has some additional a priori information available
Declares the maximum number of resources of each type
Safe State?
When process requests an available resource, system must decide if immediate allocation leaves the system in a safe statew
When is System in a safe state?
If there exists a sequence of ALL the processes in the systems such that for each Pi, the resources that Pi can still request can be satisfied by currently available resources
Basic Safe State facts?
If in a safe state then no deadlocks
If in unsafe state possibility of a deadlock
Avoidance Algorithms?
Single instance of a resource type
* use resource-allocation graph
Multiple instances of a resource type
* Use banker’s algorithm
