如果做错了,为什么餐饮哲学家不能解决僵局？

Question

根据Rust练习文档,他们基于互斥体的Dining Philosophers问题的实现通过总是选择最低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),
    ];

但是,如果我违反此规则并在最后交换fork索引Philosopher,程序仍然运行时没有死锁或恐慌.

我试过的其他事情:

• 在eat()函数调用中延长sleep参数
• 评论睡眠论点
• 将主体包裹起来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文档不包含此示例,因此上述链接已被破坏.

Answer 1

当每个哲学家"同时"拿起他/她左边的叉子然后发现他/她右边的叉子已经被拿走时,就会出现僵局.为了使这种情况经常发生不可忽视,你需要在"同时性"中引入一些软糖因素,这样如果哲学家们在彼此的一定时间内拿起他们的左叉,那么他们都不会能够拿起他们的右叉.换句话说,你需要在拾取两个叉子之间引入一点睡眠:

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

(当然,这并不能保证死锁,它更有可能.)