Roger Fan

Notes

High School Notes
University Notes
Computer Networking
Computer Architecture
Operating System
Chapter 0
Chapter 1: Operating System Introduction
Chapter 2: OS Structure
Chapter 3: Process Concept
Chapter 4: Multithreaded Programming
Chapter 5: Process Scheduling
Chapter 6: Process Synchronization
Chapter 7: Deadlocks
Chapter 8: Memory Management
Chapter 9: Virtual Memory Management
Chapter 10: File System Interface
Chapter 11: File System Implementation
Chapter 12: Mass Storage System
Chapter 13: IO System
Discrete Math
Calculus
Calculus I
Calculus II
Linear Algebra
Probability
General Physics
General Education
Tech Notes
TMUX
SSH
Fail2ban
SSHD
UFW
DNS Bind9
Notes
University Notes
Operating System
Chapter 7: Deadlocks

Login Required

This note requires login to view the full content (95 lines total). Showing first 20 lines as preview. Please login to view the full content.

Login to unlock

Chapter 7: Deadlocks

Created: 2025-12-16
Updated: 2025-12-16

Login to unlock full content

Login Now
roger@roger.tw
roger@roger.tw
© 2026 Roger Fan. All rights reserved.
  • Necessary Conditions for Deadlock
    1. Mutual Exclusion: exist a resource that only can be used by one process at a time
    2. Hold and Wait: a process holding some resources and is waiting for another resource
    3. No Preemption: a resource can only be released voluntarily
    4. Circular Wait: a set of processes are waiting for each other in a circular chain
  • System Model
    • resources types: R1,R2,...,RmR_1, R_2, ..., R_mR1​,R2​,...,Rm​ (e.g. CPU, memory, IO devices)
    • each resource type RiR_iRi​ has WiW_iWi​ instances (e.g. a computer has 2 CPUs)
    • each process: request → use → release
  • Resource-Allocation Graph
    • a directed graph with processes and resources as nodes
    • Pi→RjP_i \to R_jPi​→Rj​ edge: PiP_iPi​ requests RjR_jRj​
    • Rj→PiR_j \to P_iRj​→Pi​ edge: RjR_jRj is allocated to
    • if the graph contains no cycles → no deadlock
    • if the graph contains a cycle
      • only one instance per resource type → deadlock
      • multiple instances per resource type → may or may not be deadlock OS-ch7-ResourceAllocationGraph.png
​
PiP_iPi​