- Assume N Processes , M Resources
- Availability vector , units of each resource (initialized to maximum, changes dynamically)
- Let be an matrix
means Process will request at most units of
- Units of currently held by
- Remaining need by for units of
, for all
- Resource Request
- At any instance, posts its request for resources in vector (i.e., no hold-and-wait)
- Step 1: verify that a process matches its needs.
abort -error, impossible
- Step 2: check if the requested amount is available.
goto Step 1 -Pi must wait
- Step 3: provisional allocation (i.e., guess and check).
if isSafe() then grant resources (system is safe) else cancel allocation; goto Step 1-Pi must wait
- Find out whether the system is in a safe state. Work and Finish are two temporary vectors.
- Step 1: initialize.
for all ;
- Step 2: find a process such that
, for all
if no such process, goto Step 4
- Step 3:
(i.e., pretend it finishes and frees up the resources)
goto Step 2
- Step 4: if
then return true-yes, the system is safe
else return false-no, the system is NOT safe
- What is safe?
- Safe with respect to some resource allocation
- very safe
for all Processes . Processes can run to completion in any order.
- safe (but take care)
for at least one such that There is at least one correct order in which the processes may complete their use of resources.
- unsafe (deadlock inevitable)
for at least one But some processes cannot complete successfully.
for all Processes are already blocked or will become so as they request a resource.