Index

Free, with Google

Keep going, free.

A free account opens lessons 2 and 3 of every track, 33 more lessons, and keeps your progress and review cards on every device.

Start free with Google

Launch price

Open everything on chalk.

Every lesson, board, video, lab and paper, and the full review decks. Yearly is $39/year, or $19.50 for your first year with LAUNCH50, ends 1 Nov, 18:30 UTC.

See plansStart free instead

Module 04 · How Computers Work · Inside the operating system

Four ways to get stuck: deadlock

Concurrency and the Hardware
Concurrency and the Hardware · Open board

Two cores, one lock, and the rule that only one core may hold it at a time. This lesson is what happens when there are two locks and each core is holding the one the other wants.

Before you start. A lock lets only one thread at a time near a shared value, and a thread that cannot get it has to wait (Concurrency & the Hardware). A waiting thread is set aside by the scheduler and gets no turns until something wakes it, so it costs nothing while it waits (Waiting without spinning). Waiting is safe. This lesson is about the one way waiting can last forever.

Lesson 16 of 19 in How Computers Work

The rest of this lesson is part of a plan.

A plan opens every lesson, board, video, lab and paper on chalk. Yearly is $39/year, or $19.50 for your first year with LAUNCH50, ends 1 Nov, 18:30 UTC.

See plansAlready a member? Sign in

Or start free: a free account opens lessons 2 and 3 of every track.

In this lesson

  • 1965: an exam question about tape drives
  • The knife and the board: a deadlock
  • 1971: the four things that must all be true, the Coffman conditions
  • Drawing it: the resource-allocation graph and its cycle
  • Prevention: knock out one condition, and lock ordering
  • Avoidance: the banker’s algorithm and a safe state
  • Detection and recovery: find the cycle, kill a victim

Terms it explains: deadlock, mutual exclusion, hold and wait, no preemption, circular wait, resource-allocation graph, cycle, wait-for graph, lock ordering, Avoidance, safe state, unsafe, detect, recover, victim, actor / message passing, Amdahl's law, async / event loop, atomic, cache coherence (MESI), CAS, concurrency, coroutine/channel, critical section, happens-before, memory barrier/fence, memory reordering, mutex/lock, parallelism, race condition, starvation / livelock.

Lab

Ninety-five percent of the job splits across cores. How much faster can it possibly finish?

Leave The part that can be split up at 95%, drag Cores you throw at it upward, and watch What the next core buys.

Open The parallel ceiling

Related papers

Review How Computers Work