Why doesn't the dining philosophers exercise deadlock if done incorrectly?

Question

According to the Rust exercise docs, their mutex-based implementation of the Dining Philosophers problem avoids deadlock by always selecting the lowest ID fork as the left fork of each philosopher, i.e., by making one left-handed:

let philosophers = vec![
        Philosopher::new("Judith Butler", 0, 1),
        Philosopher::new("Gilles Deleuze", 1, 2),
        Philosopher::new("Karl Marx", 2, 3),
        Philosopher::new("Emma Goldman", 3, 4),
        Philosopher::new("Michel Foucault", 0, 4),
    ];

However, if I disobey this rule and swap the fork indices in the last Philosopher, the program still runs with no deadlocking or panicking.

Other things I tried:

• Lengthening the sleep argument in the eat() function call
• Commenting out the sleep argument
• Wrapping the main body in a loop{} to see if it would happen eventually

What do I have to do to break this properly?

---

Here is the complete source without any of the above changes:

use std::thread;
use std::sync::{Mutex, Arc};

struct Philosopher {
    name: String,
    left: usize,
    right: usize,
}

impl Philosopher {
    fn new(name: &str, left: usize, right: usize) -> Philosopher {
        Philosopher {
            name: name.to_string(),
            left: left,
            right: right,
        }
    }

    fn eat(&self, table: &Table) {
        let _left = table.forks[self.left].lock().unwrap();
        let _right = table.forks[self.right].lock().unwrap();

        println!("{} is eating.", self.name);

        thread::sleep_ms(1000);

        println!("{} is done eating.", self.name);
    }
}

struct Table {
    forks: Vec<Mutex<()>>,
}

fn main() {
    let table = Arc::new(Table { forks: vec![
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
    ]});

    let philosophers = vec![
        Philosopher::new("Judith Butler", 0, 1),
        Philosopher::new("Gilles Deleuze", 1, 2),
        Philosopher::new("Karl Marx", 2, 3),
        Philosopher::new("Emma Goldman", 3, 4),
        Philosopher::new("Michel Foucault", 0, 4),
    ];

    let handles: Vec<_> = philosophers.into_iter().map(|p| {
        let table = table.clone();

        thread::spawn(move || {
            p.eat(&table);
        })
    }).collect();

    for h in handles {
        h.join().unwrap();
    }
}

---

PS: Sadly the current Rust docs do not include this example, so the above link is broken.

Answer 1

The deadlock arises when every philosopher "simultaneously" picks up the fork on his/her left, and then finds that the fork on his/her right is already taken. To make this happen non-negligibly often, you need to introduce some fudge factor into the "simultaneity", so that if the philosophers all pick up their left forks within a certain amount of time of each other, that none of them will be able to pick up their right forks. In other words, you need to introduce a bit of sleep between picking up the two forks:

    fn eat(&self, table: &Table) {
        let _left = table.forks[self.left].lock().unwrap();
        thread::sleep_ms(1000);     // <---- simultaneity fudge factor
        let _right = table.forks[self.right].lock().unwrap();

        println!("{} is eating.", self.name);

        thread::sleep_ms(1000);

        println!("{} is done eating.", self.name);
    }

(Of course, this doesn't guarantee a deadlock, it just makes it much more likely.)