Dining philosophers from Rust documentation don't eat at the same time

Question

I am trying to follow the example of dining philosophers from the Rust documentation. The final code for the link:

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

Running this causes the following output:

 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. 

According to the documentation, philosophers should be able to eat at the same time. The desired result looks something like this:

 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. 

Unfortunately, this does not happen no matter how often the code is executed.

I am currently using rustc 1.5.0 (3d7cd77e4 2015-12-04) for Windows, but a problem also occurs on the Rust playground. Feel free to try it yourself .

Answer 1

The implementation of the problem and the proposed conclusion do not coincide due to sleep between the forks.

I'm not sure why Michel Foucault always starts all over again (maybe how thread dispatch works), but everything else is easily explained.

Due to the pause (*) between the main and remote forks, there are two phases:

• Phase 1: grab the fork of the main arm
• Stage 2: grab your fork

After phase 1:

• Fork 0 is in the hand of Michel Foucault or Judith Butler.
• Plug 1 is in the hands of Gilles Deleuze
• Fork 2 is in the hand of Karl Marx
• Fork 3 is in the hands of Emma Goldman

Now note that only Fork 4 is available for capture!

We have two cases in Phase 2:

a) Judith grabbed the plug 0 b) Michelle grabbed the plug 0

Starting from (a):

• All philosophers are blocked except for Emma, ​​who captures Fork 4
• When Emma is done, she releases Fork 3, which Carl immediately captures.
• When Karl finished ...
• Finally, Judith finished, she releases plug 0, and Michelle eats

In case (a), only one philosopher can eat at any given time.

Note. I forced the case by stopping Michel for 150 ms before letting him grab his first fork.

Case (b) is more complicated, because again we have a race, this time between Emma and Michel to grab fork 4. We are gentlemen, so Emma will go first, and the case of Michel who grabbed fork 4 is now called (c) :

• Emma captures Fork 4, now all other philosophers are blocked.
• When Emma finished, she releases the forks 3 and 4, and Michelle and Karl jump on them.
• When Michelle is done, he releases Forks 0 and 4, Judith grabs him immediately ... and starts to wait; now no one cares about Fork 4.
• When Carl is complete, he releases Fork 2, which Gilles immediately captures.
• When Gilles is completed, he releases Fork 1, which Judith immediately captures
• When Judith finished, all 5 ate

We observe very limited concurrency here: first Emma appears, and only when she is finished, we have two parallel threads, one with Michel, and one going to Karl> Gilles> Judith.

Note. I forced the case by stopping Michel for 150 ms before letting him grab his second fork.

Finally, we have case (c):

• Michelle grabs Fork 4, now all other philosophers are blocked.
• When Michelle is done, he releases Fork 4 and 0, which respectively capture Emma and Judith; Judith is still blocked (first sleeping, and then waiting for Fork 1), but Emma begins to eat
• When Emma is finished ...

And here again there is no concurrency.

(*) This is not really guaranteed, but 150 ms for a long time computer, if the machine is not loaded, this will happen.

---

While the solution proposed in the book really works (there is no deadlock, no matter what the circumstances), it does not show much concurrency, therefore it is more a manifestation of rust than an exhibit of concurrency ... but it is Rust's book, not concurrency alone!

I do not understand why the Michel thread is systematically planned first at the arena; but it can be easily contrasted by making him sleep specifically.

Answer 2

This is a semi-general question for this example. Programmers tend to think of threads as “random,” because threads usually have different start times and durations. Most thread applications also do not block a shared resource for the life of the thread. Remember that threads are deterministic because they are scheduled using an algorithm.

In this example, the main thread creates an entire chain of threads and adds them to a queue managed by the operating system. In the end, the main thread is blocked or interrupted by the scheduler. The scheduler scans the thread queue and asks for "first" if it can work. If it is running, it starts for a temporary fragment or before it is locked.

The "first" thread is OS dependent. Linux, for example, has several custom schedulers that let you prioritize threads. The scheduler can also choose to interrupt a thread sooner or later.

If you add print at the very beginning of the stream, you can see that the flows start in a different order. Here is the table from which the stream starts, based on 100 starts:

 | 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 | 

If I do my statistics correctly, the most common starting order is:

• Judith Butler
• Gilles Deleuze
• Karl Marx
• Emma Goldman
• Michel Foucault

Note that this is consistent with the sequence of philosophers defined in the code!

Also note that the algorithm itself imposes order. All but one philosopher first take a fork in his left hand, then wait a little. If the threads are executed in order, each of them, in turn, waits for what is in front of it. Most threads are dependent on the thread sitting "on the left." If we depicted a round table with everyone who held the left fork (dead end), and we chose one person to give an additional fork (breaking the dead end), then you will see that there will be a cascade of people who can eat.

Also remember that println! uses standard output; A mutable global resource that must be protected by the mutex. Thus, printing can block and reconfigure the flow.

I'm on OS X, which probably explains the order that I get semi-sequentially, which is different from yours.