如果做错了，为什么用餐哲学家不会陷入僵局？

Question

根据 Rust exercise docs，他们基于互斥量的哲学家就餐问题实现通过始终选择 ID 最低的叉子作为每个哲学家的左叉子来避免死锁，即，让一个左撇子：

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),
    ];

但是，如果我不遵守此规则并在最后 Philosopher 中交换分叉索引，程序仍然可以运行，不会出现死锁或恐慌。

我尝试的其他事情：

延长eat()函数调用中的睡眠参数
注释掉睡眠参数
将主体包裹在 loop{} 中，看看它最终是否会发生

我需要做什么才能正确破解它？

这是没有任何上述更改的完整源代码：

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：遗憾的是，当前的 Rust 文档不包含此示例，因此上面的 link 已损坏。

Answer 1

当每个哲学家"simultaneously"拿起左边his/her的叉子，然后发现his/her右边的叉子已经被拿走时，就会出现死锁。为了使这种情况经常发生，你需要在 "simultaneity" 中引入一些软糖因素，这样如果哲学家们在一定时间内都拿起他们左边的叉子，那么 none 他们将能够拿起正确的叉子。换句话说，你需要在拿起两个叉子之间引入一点睡眠：

    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);
    }

（当然，这并不能保证会出现死锁，它只会增加死锁的可能性。）

如果做错了，为什么用餐哲学家不会陷入僵局？

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

concurrency

mutex

rust