Rust文档中的用餐哲学家不同时吃饭

Question

我试图按照Rust文档中的示例进行操作。链接中的最终代码：

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();
        thread::sleep_ms(150);
        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();
    }
}

运行此命令将生成以下输出：

Michel Foucault is eating.
Michel Foucault is done eating.
Emma Goldman is eating.
Emma Goldman is done eating.
Karl Marx is eating.
Karl Marx is done eating.
Gilles Deleuze is eating.
Gilles Deleuze is done eating.
Judith Butler is eating.
Judith Butler is done eating.

根据文献记载，哲学家应该能够同时吃饭。预期结果如下所示：

Gilles Deleuze is eating.
Emma Goldman is eating.
Emma Goldman is done eating.
Gilles Deleuze is done eating.
Judith Butler is eating.
Karl Marx is eating.
Judith Butler is done eating.
Michel Foucault is eating.
Karl Marx is done eating.
Michel Foucault is done eating.

不幸的是，无论代码执行的频率有多高，这种情况都不会发生。

我目前正在Windows上使用rustc 1.5.0（3d7cd77e4 2015-12-04），但问题也发生在生锈的操场上。你自己试试吧。

Answer 1

对于这个例子，这是一个半常见的问题。程序员倾向于认为线程是“随机的”，因为线程通常有不同的开始时间和运行长度。线程的大多数用法也不会在线程的整个生命周期内锁定共享资源。请记住，线程是确定性的，因为它们是由算法调度的。

在本例中，主线程创建了一大堆线程，并将它们添加到操作系统管理的队列中。最终，主线程被调度程序阻塞或中断。调度程序查看线程队列并询问“第一个”线程是否可以运行。如果它是可运行的，那么它将运行一个时间片或直到它被阻塞。

“第一个”线程由操作系统决定。例如，Linux有多个可调整的调度程序，允许您确定运行哪些线程的优先级。调度程序还可以选择提前或推迟中断线程

如果在线程的最开始添加打印，可以看到线程的开始顺序不同。下面是一个表，根据100次运行，哪个线程首先启动：

| Position | Emma Goldman | Gilles Deleuze | Judith Butler | Karl Marx | Michel Foucault |
|----------+--------------+----------------+---------------+-----------+-----------------|
|        1 |            4 |              9 |            81 |         5 |               1 |
|        2 |            5 |             66 |             9 |        17 |               3 |
|        3 |           19 |             14 |             5 |        49 |              13 |
|        4 |           46 |              9 |             3 |        20 |              22 |
|        5 |           26 |              2 |             2 |         9 |              61 |

如果我正确地做了统计，最常见的开始顺序是：

1. 朱迪思·巴特勒

请注意，这与代码中定义的哲学家序列相匹配！

还要注意的是，算法本身强加了一个顺序。除了一位哲学家外，其他哲学家都先拿起左手的叉子，然后稍等片刻。如果线程按顺序运行，则每个线程依次等待它前面的线程。大多数线程都依赖于位于“左侧”的线程。如果我们画了一张圆桌，每个人都拿着一把左叉子（死锁），然后我们选了一个人给他一把额外的叉子（打破死锁），那么你可以看到会有很多人可以吃饭。

还要记住println！使用标准输出；必须由互斥锁保护的可变全局资源。因此，打印可能会导致线程被阻塞和重新安排。

我使用的是OSX，这可能解释了我半一致地得到的与您不同的顺序。

Answer 2

由于分叉之间的Hibernate，问题的实现和建议的输出不匹配。

我不确定为什么米歇尔·福柯总是先开始（可能是线程调度的工作方式），但其余的很容易解释。

由于抓取主叉和非手叉之间的停顿（*），分为两个阶段：

• 第一阶段：抓住你的主手叉
• 第二阶段：拿起你的非手动叉子

第1阶段之后：

• 叉子0在米歇尔·福柯或朱迪思·巴特勒手中

现在，请注意，只有Fork 4可用于抓取！

我们在第二阶段有两个案例：

a） 朱迪思抓住了叉子。米歇尔抓住了叉子

从（a）开始：

• 除了艾玛，所有的哲学家都被封锁了，她抓住了叉子4
• 爱玛完成后，她松开叉子3，卡尔立即抓住叉子
• 卡尔做完后
• 最后，朱迪思完成了，她松开叉子，米歇尔吃了

在情况（a）中，在任何给定的时间只有一个哲学家可以吃饭。

注意：在让米歇尔抓住他的第一个叉子之前，我暂停了他150毫秒，迫使他这样做。

案件（b）更为复杂，因为我们又一次有了一场比赛，这次是艾玛和米歇尔争夺福克4号。我们都是绅士，所以艾玛会先说，米歇尔抓叉4的案例现在命名为（c）：

• 艾玛拿起叉子4，所有其他哲学家现在都被封杀了

我们在这里观察到非常有限的并发：艾玛先命中，只有当她完成时，我们才有两个并行流，一个是米歇尔，一个是卡尔

注：我强迫米歇尔暂停150毫秒，然后让他拿第二把叉子。

最后，我们有案例（c）：

• 米歇尔抓起叉子4，其他所有哲学家现在都被挡住了
• 当米歇尔完成后，他释放叉子4和0，分别被艾玛和朱迪思抓住；朱迪思仍然被阻止（首先睡觉，然后等待叉子1），但艾玛开始吃东西
• 等Emma做完了...

这里再次强调，根本没有并发性。

（*）这实际上并不能保证，但150ms是一个很长的计算机时间，除非机器负载很大，否则它就会发生。

虽然这本书提出的解决方案确实有效（无论在什么情况下都不会出现死锁），但它并没有表现出太多的并发性，因此它更多的是一种生锈的表现，而不是并发性的表现。。。但是，这是铁锈书，而不是并发书！

我不明白为什么Michel的线程被系统地排在playpen的第一位；但这很容易通过让他睡觉来对抗。