Source: Chapter 8 (Part II) from lecture slides by Neerja Mhaskar, McMaster University.

Overview

This part of the lecture series on deadlocks in operating systems covers topics such as deadlock avoidance algorithms (including the Banker’s algorithm), deadlock detection, and recovery from deadlock. The notes include detailed explanations of how deadlock avoidance strategies function, and how to use algorithms like the Banker’s algorithm to manage resource allocation and prevent deadlock.

Deadlock Avoidance Algorithms

Single Instance of a Resource Type

• Resource-allocation graph is used to detect deadlock.
• Claim edges (dashed lines) indicate that a process may request a resource in the future.
  • If a process requests a resource, the claim edge is converted into an assignment edge.
  • A request is granted only if adding the edge does not form a cycle (detected using a cycle-detection algorithm).

Multiple Instances of a Resource Type

• Banker’s Algorithm is used.

Banker’s Algorithm

Outline

The Banker’s Algorithm consists of two parts:

1. Safety Algorithm: Checks whether the system is in a safe state.
2. Resource-Request Algorithm: Checks if a process's resource request can be safely granted.

Data Structures

• Available: A vector of length m, where Available[j] = k means there are k instances of resource type Rj available.
• Max: An n x m matrix where Max[i,j] = k means process Pi may request up to k instances of resource type Rj.