CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 1 of 7 · 1 min read

Why this page comes first

In this module you will

  • Define a deadlock precisely and tell it apart from a program that is only slow.
  • Reproduce a deadlock between two threads and describe the exact interleaving that causes it.
  • Name the four conditions for a deadlock and point to each one in a piece of code.
  • Explain why a deadlock can hide for thousands of runs and then strike.
  • Find out which thread holds which lock in a stuck program.

Level 4 gave threads the tools to share data: locks, condition variables and semaphores. Each tool makes a thread wait, and waiting is where a deadlock starts. Pages 6 and 7 of Level 4 showed two small deadlocks and promised a full treatment. This level delivers it. This page defines the problem and the four conditions. Pages 2 to 5 then show how to draw it, prevent it, avoid it, and detect it. Pages 6 and 7 cover related troubles and a full case study. The facts come from "Operating System Concepts" (OSC), chapter 8, "Modern Operating Systems" (MOS), chapter 6, and "Operating Systems: Three Easy Pieces" (OSTEP), chapter 32. All programs were compiled with gcc -Wall -Wextra -pthread 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.