Menu
I'm trying to follow the dining philosophers example from the Rust documentation. Final code from 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 produces 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, the philosophers should be able to eat at the same time. Desired result is 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 being executed.
I'm currently using rustc 1.5.0 (3d7cd77e4 2015-12-04) on Windows, but the problem occurs on the Rust playground as well. Feel free to try it yourself.
562
The implementation of the problem and the suggested output do not match because of the sleep between picking forks.
I am unsure as to why Michel Foucault always starts first (probably the way thread dispatch works), but the rest is easily explained.
Due to the pause (*) between grabbing the main-hand and off-hand forks, there are two phases:
After phase 1:
Now, note that only Fork 4 is available for grab!
We have two cases in Phase 2:
a) Judith grabbed the Fork 0 b) Michel grabbed the Fork 0
Starting with (a):
In case (a), only one philosopher can eat at any given time.
Note: I forced the case by pausing Michel for 150ms before letting him grab his first fork.
The case (b) is more complicated as once 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 grabbing Fork 4 is now named (c):
We observe very limited concurrency here: Emma hits first, and only when she is finished do we have two parallel streams, one with Michel, and one going Karl > Gilles > Judith.
Note: I forced the case by pausing Michel for 150ms before letting him grab his second fork.
Finally, we have case (c):
And here again, no concurrency at all.
(*) This is not actually guaranteed, but 150ms being a long time computer-wise, unless the machine is very loaded, it will just happen.
While the solution proposed by the book does work (there is no deadlock whatever the circumstances), it does not exhibit much concurrency, so it is more an exhibit of Rust than an exhibit of concurrency... but then, it is the Rust book and not the concurrency one!
I do not understand why Michel's thread is systematically scheduled first on the playpen; but it can easily be countered by making him sleep specifically.
142
This is a semi-common question for this example. Programmers tend to think of threads as "random" because threads usually have differing start times and run lengths. Most usages of threads also don't lock a shared resource for the entire life of the thread. Remember that threads are sort-of deterministic, because they are scheduled by an algorithm.
In this example, the main thread creates a whole bunch of threads and adds them to a queue managed by the operating system. Eventually, the main thread is blocked or is interrupted by the scheduler. The scheduler looks through the queue of threads and asks the "first" one if it can run. If it is runnable, then it is run for a time slice or until it is blocked.
The "first" thread is up to the OS. Linux, for example, has multiple tweakable schedulers that allow you to prioritize which threads run. The scheduler can also choose to interrupt a thread earlier or later
If you add a print at the very beginning of the thread, you can see that the threads do start in a different order. Here's a table of which thread starts first, based on 100 runs:
| 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'm doing my statistics correctly, the most common starting order is:
Note that this matches the sequence of philosophers defined in the code!
Also note that the algorithm itself imposes an ordering. All but one philosopher picks up the fork on the left hand first, then waits a bit. If the threads run in order, then each one in turn is waiting on the one before it. Most of the threads have a dependence on the thread sitting to the "left". If we pictured a circular table with everyone holding a left fork (a deadlock), and we picked one person to give an extra fork to (breaking the deadlock), then you can see there would be a cascade of people able to eat.
Also remember that println! uses standard out; a mutable global resource that must be protected by a mutex. As such, printing can cause the thread to be blocked and rescheduled.
I am on OS X, which likely explains the order that I semi-consistently get that is different from yours.
28
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
