CSE Roadmap

Common tier · about 5 hours · 8 parts

Part 1 of 8 · 1 min read

Why this page comes fifth

In this module you will

  • Run the detection algorithm for resources with several instances and name the deadlocked threads.
  • Say how it differs from the banker's safety check.
  • Choose when to run the check, and explain the cost.
  • Describe the three recovery methods and the rules for choosing a victim.
  • Write timeout-and-rollback recovery in C, and explain how the timeout length changes the result.

Prevention (page 3) restricts every program, and avoidance (page 4) needs claims that programs cannot give. A third choice is to impose no rule at all: let deadlocks happen, look for them, and break them when they appear. This is the method of databases, where users lock rows in any order they like, and of the Linux kernel for file record locks. It needs two parts: a way to find a deadlock (this page, sections 1 to 3) and a way to end it (sections 4 to 6). The sources are OSC chapter 8, MOS chapter 6, Kerrisk's "The Linux Programming Interface" (TLPI) chapter 55 and the PostgreSQL and MySQL manuals. The code was compiled with gcc -O2 -Wall -Wextra -pthread and run on a two-processor Linux machine.

About this example About this example

Real: The C programs, commands and outputs on this page were compiled with gcc -Wall -Wextra -pthread and run on a Linux test machine (2 processors, kernel 6.18, glibc 2.39).

Scripted: The worked traces use small numbers chosen so they can be followed by hand.

Not real: The page simplifies real systems. Actual kernels add more cases, limits and tuning than a short page can show.