Please enable JavaScript.
Coggle requires JavaScript to display documents.
Deadlocks (Safe state (When a process requests an available resource,…
Deadlocks
Safe state
When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state
System is in safe state if there exists a sequence <P1, P2, …, Pn> 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 + resources held by all the Pj, with j < I
-
-
-
Characterization
Hold and wait
A process holding at least one resource is waiting to acquire additional resources held by other processes
-
-
Circular wait
There exists a set {P0, P1, …, Pn}
-
-
-
-
-
Detection
When, and how often, to invoke
-
-
An algorithm to detect a cycle in a graph requires an order of n^2 operations, where n is the number of vertices in the graph
Periodically invoke an algorithm that searches for a cycle in the graph. If there is a cycle, there exists a deadlock
If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked processes “caused” the deadlock
-
Avoidance
Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need
The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition
Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes
Recovery
-
-
Order to abort
- How many processes will need to be terminated
- Resources process needs to complete
- Is process interactive or batch?
- Resources the process has used
- How long process has computed, and how much longer to completion
-
-
-