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 a lightly adapted version from [this paper][paper] by Tony
8 [paper]: http://www.usingcsp.com/cspbook.pdf
10 > In ancient times, a wealthy philanthropist endowed a College to accommodate
11 > five eminent philosophers. Each philosopher had a room in which they could
12 > engage in their professional activity of thinking; there was also a common
13 > dining room, furnished with a circular table, surrounded by five chairs, each
14 > labelled by the name of the philosopher who was to sit in it. They sat
15 > anticlockwise around the table. To the left of each philosopher there was
16 > laid a golden fork, and in the center stood a large bowl of spaghetti, which
17 > was constantly replenished. A philosopher was expected to spend most of
18 > their time thinking; but when they felt hungry, they went to the dining
19 > room, sat down in their own chair, picked up their own fork on their left,
20 > and plunged it into the spaghetti. But such is the tangled nature of
21 > spaghetti that a second fork is required to carry it to the mouth. The
22 > philosopher therefore had also to pick up the fork on their right. When
23 > they were finished they would put down both their forks, get up from their
24 > chair, and continue thinking. Of course, a fork can be used by only one
25 > philosopher at a time. If the other philosopher wants it, they just have
26 > to wait until the fork is available again.
28 This classic problem shows off a few different elements of concurrency. The
29 reason is that it's actually slightly tricky to implement: a simple
30 implementation can deadlock. For example, let's consider a simple algorithm
31 that would solve this problem:
33 1. A philosopher picks up the fork on their left.
34 2. They then pick up the fork on their right.
36 4. They return the forks.
38 Now, let’s imagine this sequence of events:
40 1. Philosopher 1 begins the algorithm, picking up the fork on their left.
41 2. Philosopher 2 begins the algorithm, picking up the fork on their left.
42 3. Philosopher 3 begins the algorithm, picking up the fork on their left.
43 4. Philosopher 4 begins the algorithm, picking up the fork on their left.
44 5. Philosopher 5 begins the algorithm, picking up the fork on their left.
45 6. ... ? All the forks are taken, but nobody can eat!
47 There are different ways to solve this problem. We’ll get to our solution in
48 the tutorial itself. For now, let’s get started modeling the problem itself.
49 We’ll start with the philosophers:
57 fn new(name: &str) -> Philosopher {
59 name: name.to_string(),
65 let p1 = Philosopher::new("Judith Butler");
66 let p2 = Philosopher::new("Gilles Deleuze");
67 let p3 = Philosopher::new("Karl Marx");
68 let p4 = Philosopher::new("Emma Goldman");
69 let p5 = Philosopher::new("Michel Foucault");
73 Here, we make a [`struct`][struct] to represent a philosopher. For now,
74 a name is all we need. We choose the [`String`][string] type for the name,
75 rather than `&str`. Generally speaking, working with a type which owns its
76 data is easier than working with one that uses references.
78 [struct]: structs.html
79 [string]: strings.html
84 # struct Philosopher {
88 fn new(name: &str) -> Philosopher {
90 name: name.to_string(),
96 This `impl` block lets us define things on `Philosopher` structs. In this case,
97 we define an ‘associated function’ called `new`. The first line looks like this:
100 # struct Philosopher {
104 fn new(name: &str) -> Philosopher {
106 # name: name.to_string(),
112 We take one argument, a `name`, of type `&str`. This is a reference to another
113 string. It returns an instance of our `Philosopher` struct.
116 # struct Philosopher {
120 # fn new(name: &str) -> Philosopher {
122 name: name.to_string(),
128 This creates a new `Philosopher`, and sets its `name` to our `name` argument.
129 Not just the argument itself, though, as we call `.to_string()` on it. This
130 will create a copy of the string that our `&str` points to, and give us a new
131 `String`, which is the type of the `name` field of `Philosopher`.
133 Why not accept a `String` directly? It’s nicer to call. If we took a `String`,
134 but our caller had a `&str`, they’d have to call this method themselves. The
135 downside of this flexibility is that we _always_ make a copy. For this small
136 program, that’s not particularly important, as we know we’ll just be using
137 short strings anyway.
139 One last thing you’ll notice: we just define a `Philosopher`, and seemingly
140 don’t do anything with it. Rust is an ‘expression based’ language, which means
141 that almost everything in Rust is an expression which returns a value. This is
142 true of functions as well, the last expression is automatically returned. Since
143 we create a new `Philosopher` as the last expression of this function, we end
146 This name, `new()`, isn’t anything special to Rust, but it is a convention for
147 functions that create new instances of structs. Before we talk about why, let’s
148 look at `main()` again:
151 # struct Philosopher {
156 # fn new(name: &str) -> Philosopher {
158 # name: name.to_string(),
164 let p1 = Philosopher::new("Judith Butler");
165 let p2 = Philosopher::new("Gilles Deleuze");
166 let p3 = Philosopher::new("Karl Marx");
167 let p4 = Philosopher::new("Emma Goldman");
168 let p5 = Philosopher::new("Michel Foucault");
172 Here, we create five variable bindings with five new philosophers. These are my
173 favorite five, but you can substitute anyone you want. If we _didn’t_ define
174 that `new()` function, it would look like this:
177 # struct Philosopher {
181 let p1 = Philosopher { name: "Judith Butler".to_string() };
182 let p2 = Philosopher { name: "Gilles Deleuze".to_string() };
183 let p3 = Philosopher { name: "Karl Marx".to_string() };
184 let p4 = Philosopher { name: "Emma Goldman".to_string() };
185 let p5 = Philosopher { name: "Michel Foucault".to_string() };
189 That’s much noisier. Using `new` has other advantages too, but even in
190 this simple case, it ends up being nicer to use.
192 Now that we’ve got the basics in place, there’s a number of ways that we can
193 tackle the broader problem here. I like to start from the end first: let’s
194 set up a way for each philosopher to finish eating. As a tiny step, let’s make
195 a method, and then loop through all the philosophers, calling it:
203 fn new(name: &str) -> Philosopher {
205 name: name.to_string(),
210 println!("{} is done eating.", self.name);
215 let philosophers = vec![
216 Philosopher::new("Judith Butler"),
217 Philosopher::new("Gilles Deleuze"),
218 Philosopher::new("Karl Marx"),
219 Philosopher::new("Emma Goldman"),
220 Philosopher::new("Michel Foucault"),
223 for p in &philosophers {
229 Let’s look at `main()` first. Rather than have five individual variable
230 bindings for our philosophers, we make a `Vec<T>` of them instead. `Vec<T>` is
231 also called a ‘vector’, and it’s a growable array type. We then use a
232 [`for`][for] loop to iterate through the vector, getting a reference to each
235 [for]: loops.html#for
237 In the body of the loop, we call `p.eat()`, which is defined above:
241 println!("{} is done eating.", self.name);
245 In Rust, methods take an explicit `self` parameter. That’s why `eat()` is a
246 method, but `new` is an associated function: `new()` has no `self`. For our
247 first version of `eat()`, we just print out the name of the philosopher, and
248 mention they’re done eating. Running this program should give you the following
252 Judith Butler is done eating.
253 Gilles Deleuze is done eating.
254 Karl Marx is done eating.
255 Emma Goldman is done eating.
256 Michel Foucault is done eating.
259 Easy enough, they’re all done! We haven’t actually implemented the real problem
260 yet, though, so we’re not done yet!
262 Next, we want to make our philosophers not just finish eating, but actually
263 eat. Here’s the next version:
267 use std::time::Duration;
274 fn new(name: &str) -> Philosopher {
276 name: name.to_string(),
281 println!("{} is eating.", self.name);
283 thread::sleep(Duration::from_millis(1000));
285 println!("{} is done eating.", self.name);
290 let philosophers = vec![
291 Philosopher::new("Judith Butler"),
292 Philosopher::new("Gilles Deleuze"),
293 Philosopher::new("Karl Marx"),
294 Philosopher::new("Emma Goldman"),
295 Philosopher::new("Michel Foucault"),
298 for p in &philosophers {
304 Just a few changes. Let’s break it down.
310 `use` brings names into scope. We’re going to start using the `thread` module
311 from the standard library, and so we need to `use` it.
315 println!("{} is eating.", self.name);
317 thread::sleep(Duration::from_millis(1000));
319 println!("{} is done eating.", self.name);
323 We now print out two messages, with a `sleep` in the middle. This will
324 simulate the time it takes a philosopher to eat.
326 If you run this program, you should see each philosopher eat in turn:
329 Judith Butler is eating.
330 Judith Butler is done eating.
331 Gilles Deleuze is eating.
332 Gilles Deleuze is done eating.
334 Karl Marx is done eating.
335 Emma Goldman is eating.
336 Emma Goldman is done eating.
337 Michel Foucault is eating.
338 Michel Foucault is done eating.
341 Excellent! We’re getting there. There’s just one problem: we aren’t actually
342 operating in a concurrent fashion, which is a core part of the problem!
344 To make our philosophers eat concurrently, we need to make a small change.
345 Here’s the next iteration:
349 use std::time::Duration;
356 fn new(name: &str) -> Philosopher {
358 name: name.to_string(),
363 println!("{} is eating.", self.name);
365 thread::sleep(Duration::from_millis(1000));
367 println!("{} is done eating.", self.name);
372 let philosophers = vec![
373 Philosopher::new("Judith Butler"),
374 Philosopher::new("Gilles Deleuze"),
375 Philosopher::new("Karl Marx"),
376 Philosopher::new("Emma Goldman"),
377 Philosopher::new("Michel Foucault"),
380 let handles: Vec<_> = philosophers.into_iter().map(|p| {
381 thread::spawn(move || {
392 All we’ve done is change the loop in `main()`, and added a second one! Here’s the
396 let handles: Vec<_> = philosophers.into_iter().map(|p| {
397 thread::spawn(move || {
403 While this is only five lines, they’re a dense five. Let’s break it down.
406 let handles: Vec<_> =
409 We introduce a new binding, called `handles`. We’ve given it this name because
410 we are going to make some new threads, and that will return some handles to those
411 threads that let us control their operation. We need to explicitly annotate
412 the type here, though, due to an issue we’ll talk about later. The `_` is
413 a type placeholder. We’re saying “`handles` is a vector of something, but you
414 can figure out what that something is, Rust.”
417 philosophers.into_iter().map(|p| {
420 We take our list of philosophers and call `into_iter()` on it. This creates an
421 iterator that takes ownership of each philosopher. We need to do this to pass
422 them to our threads. We take that iterator and call `map` on it, which takes a
423 closure as an argument and calls that closure on each element in turn.
426 thread::spawn(move || {
431 Here’s where the concurrency happens. The `thread::spawn` function takes a closure
432 as an argument and executes that closure in a new thread. This closure needs
433 an extra annotation, `move`, to indicate that the closure is going to take
434 ownership of the values it’s capturing. Primarily, the `p` variable of the
437 Inside the thread, all we do is call `eat()` on `p`. Also note that the call to `thread::spawn` lacks a trailing semicolon, making this an expression. This distinction is important, yielding the correct return value. For more details, read [Expressions vs. Statements][es].
439 [es]: functions.html#expressions-vs-statements
445 Finally, we take the result of all those `map` calls and collect them up.
446 `collect()` will make them into a collection of some kind, which is why we
447 needed to annotate the return type: we want a `Vec<T>`. The elements are the
448 return values of the `thread::spawn` calls, which are handles to those threads.
457 At the end of `main()`, we loop through the handles and call `join()` on them,
458 which blocks execution until the thread has completed execution. This ensures
459 that the threads complete their work before the program exits.
461 If you run this program, you’ll see that the philosophers eat out of order!
462 We have multi-threading!
465 Judith Butler is eating.
466 Gilles Deleuze is eating.
468 Emma Goldman is eating.
469 Michel Foucault is eating.
470 Judith Butler is done eating.
471 Gilles Deleuze is done eating.
472 Karl Marx is done eating.
473 Emma Goldman is done eating.
474 Michel Foucault is done eating.
477 But what about the forks? We haven’t modeled them at all yet.
479 To do that, let’s make a new `struct`:
482 use std::sync::Mutex;
485 forks: Vec<Mutex<()>>,
489 This `Table` has a vector of `Mutex`es. A mutex is a way to control
490 concurrency: only one thread can access the contents at once. This is exactly
491 the property we need with our forks. We use an empty tuple, `()`, inside the
492 mutex, since we’re not actually going to use the value, just hold onto it.
494 Let’s modify the program to use the `Table`:
498 use std::time::Duration;
499 use std::sync::{Mutex, Arc};
508 fn new(name: &str, left: usize, right: usize) -> Philosopher {
510 name: name.to_string(),
516 fn eat(&self, table: &Table) {
517 let _left = table.forks[self.left].lock().unwrap();
518 thread::sleep(Duration::from_millis(150));
519 let _right = table.forks[self.right].lock().unwrap();
521 println!("{} is eating.", self.name);
523 thread::sleep(Duration::from_millis(1000));
525 println!("{} is done eating.", self.name);
530 forks: Vec<Mutex<()>>,
534 let table = Arc::new(Table { forks: vec![
542 let philosophers = vec![
543 Philosopher::new("Judith Butler", 0, 1),
544 Philosopher::new("Gilles Deleuze", 1, 2),
545 Philosopher::new("Karl Marx", 2, 3),
546 Philosopher::new("Emma Goldman", 3, 4),
547 Philosopher::new("Michel Foucault", 0, 4),
550 let handles: Vec<_> = philosophers.into_iter().map(|p| {
551 let table = table.clone();
553 thread::spawn(move || {
564 Lots of changes! However, with this iteration, we’ve got a working program.
565 Let’s go over the details:
568 use std::sync::{Mutex, Arc};
571 We’re going to use another structure from the `std::sync` package: `Arc<T>`.
572 We’ll talk more about it when we use it.
582 We need to add two more fields to our `Philosopher`. Each philosopher is going
583 to have two forks: the one on their left, and the one on their right.
584 We’ll use the `usize` type to indicate them, as it’s the type that you index
585 vectors with. These two values will be the indexes into the `forks` our `Table`
589 fn new(name: &str, left: usize, right: usize) -> Philosopher {
591 name: name.to_string(),
598 We now need to construct those `left` and `right` values, so we add them to
602 fn eat(&self, table: &Table) {
603 let _left = table.forks[self.left].lock().unwrap();
604 thread::sleep(Duration::from_millis(150));
605 let _right = table.forks[self.right].lock().unwrap();
607 println!("{} is eating.", self.name);
609 thread::sleep(Duration::from_millis(1000));
611 println!("{} is done eating.", self.name);
615 We have three new lines. We’ve added an argument, `table`. We access the
616 `Table`’s list of forks, and then use `self.left` and `self.right` to access
617 the fork at that particular index. That gives us access to the `Mutex` at that
618 index, and we call `lock()` on it. If the mutex is currently being accessed by
619 someone else, we’ll block until it becomes available. We have also a call to
620 `thread::sleep` between the moment the first fork is picked and the moment the
621 second forked is picked, as the process of picking up the fork is not
624 The call to `lock()` might fail, and if it does, we want to crash. In this
625 case, the error that could happen is that the mutex is [‘poisoned’][poison],
626 which is what happens when the thread panics while the lock is held. Since this
627 shouldn’t happen, we just use `unwrap()`.
629 [poison]: ../std/sync/struct.Mutex.html#poisoning
631 One other odd thing about these lines: we’ve named the results `_left` and
632 `_right`. What’s up with that underscore? Well, we aren’t planning on
633 _using_ the value inside the lock. We just want to acquire it. As such,
634 Rust will warn us that we never use the value. By using the underscore,
635 we tell Rust that this is what we intended, and it won’t throw a warning.
637 What about releasing the lock? Well, that will happen when `_left` and
638 `_right` go out of scope, automatically.
641 let table = Arc::new(Table { forks: vec![
650 Next, in `main()`, we make a new `Table` and wrap it in an `Arc<T>`.
651 ‘arc’ stands for ‘atomic reference count’, and we need that to share
652 our `Table` across multiple threads. As we share it, the reference
653 count will go up, and when each thread ends, it will go back down.
657 let philosophers = vec![
658 Philosopher::new("Judith Butler", 0, 1),
659 Philosopher::new("Gilles Deleuze", 1, 2),
660 Philosopher::new("Karl Marx", 2, 3),
661 Philosopher::new("Emma Goldman", 3, 4),
662 Philosopher::new("Michel Foucault", 0, 4),
666 We need to pass in our `left` and `right` values to the constructors for our
667 `Philosopher`s. But there’s one more detail here, and it’s _very_ important. If
668 you look at the pattern, it’s all consistent until the very end. Monsieur
669 Foucault should have `4, 0` as arguments, but instead, has `0, 4`. This is what
670 prevents deadlock, actually: one of our philosophers is left handed! This is
671 one way to solve the problem, and in my opinion, it’s the simplest. If you
672 change the order of the parameters, you will be able to observe the deadlock
676 let handles: Vec<_> = philosophers.into_iter().map(|p| {
677 let table = table.clone();
679 thread::spawn(move || {
685 Finally, inside of our `map()`/`collect()` loop, we call `table.clone()`. The
686 `clone()` method on `Arc<T>` is what bumps up the reference count, and when it
687 goes out of scope, it decrements the count. This is needed so that we know how
688 many references to `table` exist across our threads. If we didn’t have a count,
689 we wouldn’t know how to deallocate it.
691 You’ll notice we can introduce a new binding to `table` here, and it will
692 shadow the old one. This is often used so that you don’t need to come up with
695 With this, our program works! Only two philosophers can eat at any one time,
696 and so you’ll get some output like this:
699 Gilles Deleuze is eating.
700 Emma Goldman is eating.
701 Emma Goldman is done eating.
702 Gilles Deleuze is done eating.
703 Judith Butler is eating.
705 Judith Butler is done eating.
706 Michel Foucault is eating.
707 Karl Marx is done eating.
708 Michel Foucault is done eating.
711 Congrats! You’ve implemented a classic concurrency problem in Rust.