🎓 A1Learner
🔍

Rust Dining Philosophers

The dining philosophers story is the classic way to teach a deadlock. Five philosophers sit at a table with five forks.

The table: five philosophers, five forks

Five philosophers sit at a round table. Between each pair lies one fork. That makes five forks in all. Eating takes two. Each fork is a Mutex<()>: the value inside is nothing, because only the holding matters:

use std::sync::Mutex;
fn main() {
    let forks: Vec<Mutex<()>> = (0..5).map(|_| Mutex::new(())).collect();
    println!("forks on the table = {}", forks.len());
}

The naive rule walks into a circle

Deadlock, named precisely, is a circle of waiting. Each thread holds one lock and waits for the next. This dinner table is that circle drawn with chairs:

// every philosopher runs the same two lines:
let _left = forks[i].lock().unwrap();
let _right = forks[(i + 1) % 5].lock().unwrap();
// if all five grab their left fork in the same moment, each one
// holds a fork and waits forever for a right fork that never frees

The fix: the lower fork always goes first

One shared order for everyone, so no circle of waiting can form. The closing program uses scoped threads for the table. The forks live in one local Vec. Each philosopher borrows them. The program also records each meal behind a Mutex:

let first = i.min((i + 1) % 5);
let second = i.max((i + 1) % 5);
let _a = forks[first].lock().unwrap();
let _b = forks[second].lock().unwrap();

A witness: try_lock instead of waiting forever

Even the naive version could have carried a witness. A try_lock on the second fork is one witness. The philosopher backs off and retries. That turns the freeze into a limp. The Rust Deadlock Detection lesson at the end of this section builds these witnesses properly:

match forks[second].try_lock() {
    Ok(_guard) => { /* both forks held: eat */ }
    Err(_) => { /* put the first fork down, try again later */ }
}

Example

use std::sync::Mutex;
use std::thread;
fn main() {
    let forks: Vec<Mutex<()>> = (0..5).map(|_| Mutex::new(())).collect();
    let ate: Mutex<Vec<&str>> = Mutex::new(Vec::new());
    let names = ["Ana", "Bo", "Cy", "Di", "Ed"];
    thread::scope(|s| {
        for i in 0..5 {
            let forks = &forks;
            let ate = &ate;
            s.spawn(move || {
                let first = i.min((i + 1) % 5);
                let second = i.max((i + 1) % 5);
                let _a = forks[first].lock().unwrap();
                let _b = forks[second].lock().unwrap();
                ate.lock().unwrap().push(names[i]);
            });
        }
    });
    let mut done = ate.into_inner().unwrap();
    done.sort();
    for name in &done {
        println!("{name} ate");
    }
    println!("everyone ate: {}", done.len() == 5);
}

Key points

  • Rust does not prevent this: ownership rules stop data races, not two locks taken in clashing orders
  • The smell of a deadlock in the wild: the program is alive.
  • The CPUs are idle.
  • Nothing will ever print again.
  • Before changing any code, list who holds what.
  • List who waits for what, too.
  • The circle is usually visible on paper first.
  • A deadlocked program is still memory-safe: the data is consistent, nobody reads garbage — the program is simply stuck.
  • A deadlock is a circle where each thread holds a lock and waits for the next one.

In this example, philosopher i needs forks i and i+1, with fork 0 following fork 4. The key lines are first and second. Each philosopher works out the lower fork number. Each takes that lock first, whatever their seat. Everyone reaches for forks in the same global order. So the circle of waiting from the naive rule can never form. Each philosopher who holds both forks records their name in the shared list. The scope ends only when all five threads finish, and the sorted list proves everyone ate.

Note

Safety and progress are two different promises.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

What makes the deadlock possible in the naive version of this program?