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

Question

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

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 中交换 fork 索引，程序仍然可以运行，不会出现死锁或 panic 。

我尝试过的其他事情:

• 延长 eat() 函数调用中的 sleep 参数
• 注释掉 sleep 参数
• 将主体包裹在一个循环{}中，看看它最终是否会发生

我该怎么做才能正确破解它？

---

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

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 文档不包含此示例，因此上面的链接已损坏。

Answer 1

当每个哲学家“同时”拿起他/她左边的 fork ，然后发现他/她右边的 fork 已经被拿走时，就会出现死锁。为了使这种情况经常发生，你需要在“同时性”中引入一些软糖因素，这样如果哲学家们在一定时间内都拿起了他们左边的 fork ，那么他们中没有人能够拿起他们正确的 fork 。换句话说，您需要在拿起两把 fork 之间引入一点 sleep :

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

(当然，这并不能保证死锁，它只会增加死锁的可能性。)