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

Overview

This lecture focuses on deadlocks in operating systems, their characteristics, and the various methods for handling deadlocks. It includes topics such as the system model, resource allocation graphs, deadlock characterization, and safe state determination.

System Model and Resource Representation

• System consists of resources:
  • Resource types: R1, R2, ..., Rm (e.g., CPU cycles, memory space, I/O devices).
  • Each resource type, Ri, has Wi instances (e.g., two instances of a printer).
• Resource utilization by a process:
  1. Request resource
  2. Use resource
  3. Release resource
  • If the resource is not available, the process enters a waiting state.

Deadlock

• Deadlock occurs when:
  • A process is waiting for a resource held by other waiting processes.
  • The system resources are tied up, preventing processes from completing.

Deadlock Characterization

Deadlock occurs when all the following four conditions hold simultaneously:

1. Mutual exclusion: Only one process can use a resource at any given time.
2. Hold and wait: A process holding at least one resource is waiting for additional resources held by other processes.
3. No preemption: Resources cannot be forcibly taken from a process. They are only released when the process voluntarily gives them up.
4. Circular wait: There exists a set of processes {P0, P1, ..., Pn} such that:
   • P0 is waiting for a resource held by P1,
   • P1 is waiting for a resource held by P2, and so on,
   • Pn is waiting for a resource held by P0.

Visual Representation:

Consider a circular wait with P0, P1, ..., Pn, where each process is waiting for a resource held by the next process in the sequence, forming a cycle.