Deadlock Avoidance

---

Requires that the system has some additional a priori information available

 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

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

That is:

• If Pi resource needs are not immediately available, then Pi can wait until all Pj have finished
• When Pj is finished, Pi can obtain needed resources, execute, return allocated resources, and terminate
• When Pi terminates, Pi +1 can obtain its needed resources, and so on

Basic Facts

---

If a system is in safe state ⇒ no deadlocks

If a system is in unsafe state ⇒ possibility of deadlock

Avoidance ⇒ ensure that a system will never enter an unsafe state.

Safe, Unsafe, Deadlock State

---

Avoidance algorithms

---

Single instance of a resource type => Use a resource-allocation graph

Multiple instances of a resource type => Use the banker’s algorithm