CSE Roadmap

Common tier · about 5 hours · 7 parts

Part 1 of 7 · 1 min read

Why this page comes fourth

In this module you will

  • Explain the difference between deadlock prevention and deadlock avoidance.
  • Decide whether a state is safe, and find a safe sequence.
  • Run the banker's algorithm by hand on a table with several resource types.
  • Decide whether a request can be granted, and explain why a refused request is not yet a deadlock.
  • Write the algorithm in C and state why real systems rarely use it.

Page 3 removed one of the four conditions by a fixed rule. The rules cost something: idle resources, extra waiting, or a strict order. Avoidance asks a different question. It leaves all four conditions in place, and looks at each request before granting it. The system grants a request only if the resulting state still leaves a way for everyone to finish. This needs more information than prevention does, and more computing. Page 5 covers the opposite choice, which is to allow deadlocks and then find them. The sources are OSC chapter 8 and MOS chapter 6, and Anderson and Dahlin (AD) for the safe-state argument. The code was compiled with gcc -O2 -Wall -Wextra 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.