3 For our second project, let’s look at a classic concurrency problem. It’s
4 called ‘the dining philosophers’. It was originally conceived by Dijkstra in
5 1965, but we’ll use the version from [this paper][paper] by Tony Hoare in 1985.
7 [paper]: http://www.usingcsp.com/cspbook.pdf
9 > In ancient times, a wealthy philanthropist endowed a College to accommodate
10 > five eminent philosophers. Each philosopher had a room in which she could
11 > engage in her professional activity of thinking; there was also a common
12 > dining room, furnished with a circular table, surrounded by five chairs, each
13 > labelled by the name of the philosopher who was to sit in it. They sat
14 > anticlockwise around the table. To the left of each philosopher there was
15 > laid a golden fork, and in the centre stood a large bowl of spaghetti, which
16 > was constantly replenished. A philosopher was expected to spend most of her
17 > time thinking; but when she felt hungry, she went to the dining room, sat down
18 > in her own chair, picked up her own fork on her left, and plunged it into the
19 > spaghetti. But such is the tangled nature of spaghetti that a second fork is
20 > required to carry it to the mouth. The philosopher therefore had also to pick
21 > up the fork on her right. When she was finished she would put down both her
22 > forks, get up from her chair, and continue thinking. Of course, a fork can be
23 > used by only one philosopher at a time. If the other philosopher wants it, she
24 > just has to wait until the fork is available again.
26 This classic problem shows off a few different elements of concurrency. The
27 reason is that it's actually slightly tricky to implement: a simple
28 implementation can deadlock. For example, let's consider a simple algorithm
29 that would solve this problem:
31 1. A philosopher picks up the fork on their left.
32 2. They then pick up the fork on their right.
34 4. They return the forks.
36 Now, let’s imagine this sequence of events:
38 1. Philosopher 1 begins the algorithm, picking up the fork on their left.
39 2. Philosopher 2 begins the algorithm, picking up the fork on their left.
40 3. Philosopher 3 begins the algorithm, picking up the fork on their left.
41 4. Philosopher 4 begins the algorithm, picking up the fork on their left.
42 5. Philosopher 5 begins the algorithm, picking up the fork on their left.
43 6. ... ? All the forks are taken, but nobody can eat!
45 There are different ways to solve this problem. We’ll get to our solution in
46 the tutorial itself. For now, let’s get started modelling the problem itself.
47 We’ll start with the philosophers:
55 fn new(name: &str) -> Philosopher {
57 name: name.to_string(),
63 let p1 = Philosopher::new("Baruch Spinoza");
64 let p2 = Philosopher::new("Gilles Deleuze");
65 let p3 = Philosopher::new("Karl Marx");
66 let p4 = Philosopher::new("Friedrich Nietzsche");
67 let p5 = Philosopher::new("Michel Foucault");
71 Here, we make a [`struct`][struct] to represent a philosopher. For now,
72 a name is all we need. We choose the [`String`][string] type for the name,
73 rather than `&str`. Generally speaking, working with a type which owns its
74 data is easier than working with one that uses references.
76 [struct]: structs.html
77 [string]: strings.html
82 # struct Philosopher {
86 fn new(name: &str) -> Philosopher {
88 name: name.to_string(),
94 This `impl` block lets us define things on `Philosopher` structs. In this case,
95 we define an ‘associated function’ called `new`. The first line looks like this:
98 # struct Philosopher {
102 fn new(name: &str) -> Philosopher {
104 # name: name.to_string(),
110 We take one argument, a `name`, of type `&str`. This is a reference to another
111 string. It returns an instance of our `Philosopher` struct.
114 # struct Philosopher {
118 # fn new(name: &str) -> Philosopher {
120 name: name.to_string(),
126 This creates a new `Philosopher`, and sets its `name` to our `name` argument.
127 Not just the argument itself, though, as we call `.to_string()` on it. This
128 will create a copy of the string that our `&str` points to, and give us a new
129 `String`, which is the type of the `name` field of `Philosopher`.
131 Why not accept a `String` directly? It’s nicer to call. If we took a `String`,
132 but our caller had a `&str`, they’d have to call this method themselves. The
133 downside of this flexibility is that we _always_ make a copy. For this small
134 program, that’s not particularly important, as we know we’ll just be using
135 short strings anyway.
137 One last thing you’ll notice: we just define a `Philosopher`, and seemingly
138 don’t do anything with it. Rust is an ‘expression based’ language, which means
139 that almost everything in Rust is an expression which returns a value. This is
140 true of functions as well, the last expression is automatically returned. Since
141 we create a new `Philosopher` as the last expression of this function, we end
144 This name, `new()`, isn’t anything special to Rust, but it is a convention for
145 functions that create new instances of structs. Before we talk about why, let’s
146 look at `main()` again:
149 # struct Philosopher {
154 # fn new(name: &str) -> Philosopher {
156 # name: name.to_string(),
162 let p1 = Philosopher::new("Baruch Spinoza");
163 let p2 = Philosopher::new("Gilles Deleuze");
164 let p3 = Philosopher::new("Karl Marx");
165 let p4 = Philosopher::new("Friedrich Nietzsche");
166 let p5 = Philosopher::new("Michel Foucault");
170 Here, we create five variable bindings with five new philosophers. These are my
171 favorite five, but you can substitute anyone you want. If we _didn’t_ define
172 that `new()` function, it would look like this:
175 # struct Philosopher {
179 let p1 = Philosopher { name: "Baruch Spinoza".to_string() };
180 let p2 = Philosopher { name: "Gilles Deleuze".to_string() };
181 let p3 = Philosopher { name: "Karl Marx".to_string() };
182 let p4 = Philosopher { name: "Friedrich Nietzche".to_string() };
183 let p5 = Philosopher { name: "Michel Foucault".to_string() };
187 That’s much noisier. Using `new` has other advantages too, but even in
188 this simple case, it ends up being nicer to use.
190 Now that we’ve got the basics in place, there’s a number of ways that we can
191 tackle the broader problem here. I like to start from the end first: let’s
192 set up a way for each philosopher to finish eating. As a tiny step, let’s make
193 a method, and then loop through all the philosophers, calling it:
201 fn new(name: &str) -> Philosopher {
203 name: name.to_string(),
208 println!("{} is done eating.", self.name);
213 let philosophers = vec![
214 Philosopher::new("Baruch Spinoza"),
215 Philosopher::new("Gilles Deleuze"),
216 Philosopher::new("Karl Marx"),
217 Philosopher::new("Friedrich Nietzsche"),
218 Philosopher::new("Michel Foucault"),
221 for p in &philosophers {
227 Let’s look at `main()` first. Rather than have five individual variable
228 bindings for our philosophers, we make a `Vec<T>` of them instead. `Vec<T>` is
229 also called a ‘vector’, and it’s a growable array type. We then use a
230 [`for`][for] loop to iterate through the vector, getting a reference to each
233 [for]: for-loops.html
235 In the body of the loop, we call `p.eat()`, which is defined above:
239 println!("{} is done eating.", self.name);
243 In Rust, methods take an explicit `self` parameter. That’s why `eat()` is a
244 method, but `new` is an associated function: `new()` has no `self`. For our
245 first version of `eat()`, we just print out the name of the philosopher, and
246 mention they’re done eating. Running this program should give you the following
250 Baruch Spinoza is done eating.
251 Gilles Deleuze is done eating.
252 Karl Marx is done eating.
253 Friedrich Nietzsche is done eating.
254 Michel Foucault is done eating.
257 Easy enough, they’re all done! We haven’t actually implemented the real problem
258 yet, though, so we’re not done yet!
260 Next, we want to make our philosophers not just finish eating, but actually
261 eat. Here’s the next version:
271 fn new(name: &str) -> Philosopher {
273 name: name.to_string(),
278 println!("{} is eating.", self.name);
280 thread::sleep_ms(1000);
282 println!("{} is done eating.", self.name);
287 let philosophers = vec![
288 Philosopher::new("Baruch Spinoza"),
289 Philosopher::new("Gilles Deleuze"),
290 Philosopher::new("Karl Marx"),
291 Philosopher::new("Friedrich Nietzsche"),
292 Philosopher::new("Michel Foucault"),
295 for p in &philosophers {
301 Just a few changes. Let’s break it down.
307 `use` brings names into scope. We’re going to start using the `thread` module
308 from the standard library, and so we need to `use` it.
312 println!("{} is eating.", self.name);
314 thread::sleep_ms(1000);
316 println!("{} is done eating.", self.name);
320 We now print out two messages, with a `sleep_ms()` in the middle. This will
321 simulate the time it takes a philosopher to eat.
323 If you run this program, you should see each philosopher eat in turn:
326 Baruch Spinoza is eating.
327 Baruch Spinoza is done eating.
328 Gilles Deleuze is eating.
329 Gilles Deleuze is done eating.
331 Karl Marx is done eating.
332 Friedrich Nietzsche is eating.
333 Friedrich Nietzsche is done eating.
334 Michel Foucault is eating.
335 Michel Foucault is done eating.
338 Excellent! We’re getting there. There’s just one problem: we aren’t actually
339 operating in a concurrent fashion, which is a core part of the problem!
341 To make our philosophers eat concurrently, we need to make a small change.
342 Here’s the next iteration:
352 fn new(name: &str) -> Philosopher {
354 name: name.to_string(),
359 println!("{} is eating.", self.name);
361 thread::sleep_ms(1000);
363 println!("{} is done eating.", self.name);
368 let philosophers = vec![
369 Philosopher::new("Baruch Spinoza"),
370 Philosopher::new("Gilles Deleuze"),
371 Philosopher::new("Karl Marx"),
372 Philosopher::new("Friedrich Nietzsche"),
373 Philosopher::new("Michel Foucault"),
376 let handles: Vec<_> = philosophers.into_iter().map(|p| {
377 thread::spawn(move || {
388 All we’ve done is change the loop in `main()`, and added a second one! Here’s the
392 let handles: Vec<_> = philosophers.into_iter().map(|p| {
393 thread::spawn(move || {
399 While this is only five lines, they’re a dense five. Let’s break it down.
402 let handles: Vec<_> =
405 We introduce a new binding, called `handles`. We’ve given it this name because
406 we are going to make some new threads, and that will return some handles to those
407 threads that let us control their operation. We need to explicitly annotate
408 the type here, though, due to an issue we’ll talk about later. The `_` is
409 a type placeholder. We’re saying “`handles` is a vector of something, but you
410 can figure out what that something is, Rust.”
413 philosophers.into_iter().map(|p| {
416 We take our list of philosophers and call `into_iter()` on it. This creates an
417 iterator that takes ownership of each philosopher. We need to do this to pass
418 them to our threads. We take that iterator and call `map` on it, which takes a
419 closure as an argument and calls that closure on each element in turn.
422 thread::spawn(move || {
427 Here’s where the concurrency happens. The `thread::spawn` function takes a closure
428 as an argument and executes that closure in a new thread. This closure needs
429 an extra annotation, `move`, to indicate that the closure is going to take
430 ownership of the values it’s capturing. Primarily, the `p` variable of the
433 Inside the thread, all we do is call `eat()` on `p`.
439 Finally, we take the result of all those `map` calls and collect them up.
440 `collect()` will make them into a collection of some kind, which is why we
441 needed to annotate the return type: we want a `Vec<T>`. The elements are the
442 return values of the `thread::spawn` calls, which are handles to those threads.
451 At the end of `main()`, we loop through the handles and call `join()` on them,
452 which blocks execution until the thread has completed execution. This ensures
453 that the threads complete their work before the program exits.
455 If you run this program, you’ll see that the philosophers eat out of order!
456 We have multi-threading!
459 Gilles Deleuze is eating.
460 Gilles Deleuze is done eating.
461 Friedrich Nietzsche is eating.
462 Friedrich Nietzsche is done eating.
463 Michel Foucault is eating.
464 Baruch Spinoza is eating.
465 Baruch Spinoza is done eating.
467 Karl Marx is done eating.
468 Michel Foucault is done eating.
471 But what about the forks? We haven’t modeled them at all yet.
473 To do that, let’s make a new `struct`:
476 use std::sync::Mutex;
479 forks: Vec<Mutex<()>>,
483 This `Table` has a vector of `Mutex`es. A mutex is a way to control
484 concurrency: only one thread can access the contents at once. This is exactly
485 the property we need with our forks. We use an empty tuple, `()`, inside the
486 mutex, since we’re not actually going to use the value, just hold onto it.
488 Let’s modify the program to use the `Table`:
492 use std::sync::{Mutex, Arc};
501 fn new(name: &str, left: usize, right: usize) -> Philosopher {
503 name: name.to_string(),
509 fn eat(&self, table: &Table) {
510 let _left = table.forks[self.left].lock().unwrap();
511 let _right = table.forks[self.right].lock().unwrap();
513 println!("{} is eating.", self.name);
515 thread::sleep_ms(1000);
517 println!("{} is done eating.", self.name);
522 forks: Vec<Mutex<()>>,
526 let table = Arc::new(Table { forks: vec![
534 let philosophers = vec![
535 Philosopher::new("Baruch Spinoza", 0, 1),
536 Philosopher::new("Gilles Deleuze", 1, 2),
537 Philosopher::new("Karl Marx", 2, 3),
538 Philosopher::new("Friedrich Nietzsche", 3, 4),
539 Philosopher::new("Michel Foucault", 0, 4),
542 let handles: Vec<_> = philosophers.into_iter().map(|p| {
543 let table = table.clone();
545 thread::spawn(move || {
556 Lots of changes! However, with this iteration, we’ve got a working program.
557 Let’s go over the details:
560 use std::sync::{Mutex, Arc};
563 We’re going to use another structure from the `std::sync` package: `Arc<T>`.
564 We’ll talk more about it when we use it.
574 We need to add two more fields to our `Philosopher`. Each philosopher is going
575 to have two forks: the one on their left, and the one on their right.
576 We’ll use the `usize` type to indicate them, as it’s the type that you index
577 vectors with. These two values will be the indexes into the `forks` our `Table`
581 fn new(name: &str, left: usize, right: usize) -> Philosopher {
583 name: name.to_string(),
590 We now need to construct those `left` and `right` values, so we add them to
594 fn eat(&self, table: &Table) {
595 let _left = table.forks[self.left].lock().unwrap();
596 let _right = table.forks[self.right].lock().unwrap();
598 println!("{} is eating.", self.name);
600 thread::sleep_ms(1000);
602 println!("{} is done eating.", self.name);
606 We have two new lines. We’ve also added an argument, `table`. We access the
607 `Table`’s list of forks, and then use `self.left` and `self.right` to access
608 the fork at that particular index. That gives us access to the `Mutex` at that
609 index, and we call `lock()` on it. If the mutex is currently being accessed by
610 someone else, we’ll block until it becomes available.
612 The call to `lock()` might fail, and if it does, we want to crash. In this
613 case, the error that could happen is that the mutex is [‘poisoned’][poison],
614 which is what happens when the thread panics while the lock is held. Since this
615 shouldn’t happen, we just use `unwrap()`.
617 [poison]: ../std/sync/struct.Mutex.html#poisoning
619 One other odd thing about these lines: we’ve named the results `_left` and
620 `_right`. What’s up with that underscore? Well, we aren’t planning on
621 _using_ the value inside the lock. We just want to acquire it. As such,
622 Rust will warn us that we never use the value. By using the underscore,
623 we tell Rust that this is what we intended, and it won’t throw a warning.
625 What about releasing the lock? Well, that will happen when `_left` and
626 `_right` go out of scope, automatically.
629 let table = Arc::new(Table { forks: vec![
638 Next, in `main()`, we make a new `Table` and wrap it in an `Arc<T>`.
639 ‘arc’ stands for ‘atomic reference count’, and we need that to share
640 our `Table` across multiple threads. As we share it, the reference
641 count will go up, and when each thread ends, it will go back down.
645 let philosophers = vec![
646 Philosopher::new("Baruch Spinoza", 0, 1),
647 Philosopher::new("Gilles Deleuze", 1, 2),
648 Philosopher::new("Karl Marx", 2, 3),
649 Philosopher::new("Friedrich Nietzsche", 3, 4),
650 Philosopher::new("Michel Foucault", 0, 4),
654 We need to pass in our `left` and `right` values to the constructors for our
655 `Philosopher`s. But there’s one more detail here, and it’s _very_ important. If
656 you look at the pattern, it’s all consistent until the very end. Monsieur
657 Foucault should have `4, 0` as arguments, but instead, has `0, 4`. This is what
658 prevents deadlock, actually: one of our philosophers is left handed! This is
659 one way to solve the problem, and in my opinion, it’s the simplest.
662 let handles: Vec<_> = philosophers.into_iter().map(|p| {
663 let table = table.clone();
665 thread::spawn(move || {
671 Finally, inside of our `map()`/`collect()` loop, we call `table.clone()`. The
672 `clone()` method on `Arc<T>` is what bumps up the reference count, and when it
673 goes out of scope, it decrements the count. You’ll notice we can introduce a
674 new binding to `table` here, and it will shadow the old one. This is often used
675 so that you don’t need to come up with two unique names.
677 With this, our program works! Only two philosophers can eat at any one time,
678 and so you’ll get some output like this:
681 Gilles Deleuze is eating.
682 Friedrich Nietzsche is eating.
683 Friedrich Nietzsche is done eating.
684 Gilles Deleuze is done eating.
685 Baruch Spinoza is eating.
687 Baruch Spinoza is done eating.
688 Michel Foucault is eating.
689 Karl Marx is done eating.
690 Michel Foucault is done eating.
693 Congrats! You’ve implemented a classic concurrency problem in Rust.