Deadlock occurrence and avoidance methods

Deadlock

A set of processes is in deadlock when each is waiting for a resource held by another process in the set, so none can proceed.

How deadlock occurs

It occurs when four conditions hold simultaneously: mutual exclusion, hold and wait, no preemption and circular wait. Example: P1 holds tape drive and requests printer; P2 holds printer and requests tape drive; both wait forever.

Deadlock avoidance

Avoidance means the OS examines each resource request and grants it only if the system stays in a safe state, using advance information on the maximum needs of each process. A state is safe if there is a sequence of all processes in which each can get its maximum needs and finish.

1. Resource-allocation graph algorithm (single instance per resource) Add claim edges Pi → Rj showing that Pi may request Rj later. A request is granted (claim edge converted to assignment edge) only if it does not form a cycle in the graph.

2. Banker's algorithm (multiple instances) Data: Available, Max, Allocation, Need = Max − Allocation.

• Safety algorithm: Work = Available; find process with Need ≤ Work; Work += Allocation; repeat; if all can finish the state is safe.
• Resource-request algorithm: for a request, check Request ≤ Need and ≤ Available; pretend to allocate; run the safety algorithm; grant only if safe, otherwise the process waits.

Example: 3 processes, one resource type with 12 units. Max needs: P0 = 10, P1 = 4, P2 = 9. Currently allocated: P0 = 5, P1 = 2, P2 = 2, so Available = 3.

P1 (need 2 ≤ 3) finishes → Work = 5; P0 (need 5 ≤ 5) finishes → Work = 10; P2 (need 7 ≤ 10) finishes. Safe sequence: P1, P0, P2. If P2 now asked for 1 more unit, and the system pretended to grant it: Available = 2, P1 could finish → 4, but P0 needs 5 and P2 needs 6 > 4, so unsafe; the request is delayed.

Avoidance is less strict than prevention but needs prior knowledge of maximum demands and a fixed number of processes.