CSE Roadmap

Core tier · about 5 hours · 8 parts

Part 1 of 8 · 1 min read

Why this page comes third

In this module you will

  • Explain how each of the four conditions can be removed, and what each choice costs.
  • Write a transfer function that cannot deadlock, by lock ordering.
  • Write an all-or-nothing version with a single lock, and a version with pthread_mutex_trylock and back-off.
  • Prove that a global lock order makes a cycle impossible.
  • Add a run-time check that catches an out-of-order lock at the first mistake.

Page 1 showed that all four conditions are necessary, and page 2 showed how to see a cycle. A natural idea follows: if all four must hold, make sure that one of them never does. This is deadlock prevention. It is the method used by most real programs, because it costs nothing at run time once the rule is followed. Page 4 covers the more careful method of avoidance, and page 5 covers detection. The sources are OSC chapter 8, MOS chapter 6 and OSTEP chapter 32. All programs were 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.