]>
Commit | Line | Data |
---|---|---|
bd371182 AL |
1 | % Dining Philosophers |
2 | ||
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 | |
62682a34 SL |
5 | 1965, but we’ll use a lightly adapted version from [this paper][paper] by Tony |
6 | Hoare in 1985. | |
bd371182 AL |
7 | |
8 | [paper]: http://www.usingcsp.com/cspbook.pdf | |
9 | ||
10 | > In ancient times, a wealthy philanthropist endowed a College to accommodate | |
62682a34 SL |
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 | |
bd371182 AL |
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 centre stood a large bowl of spaghetti, which | |
62682a34 SL |
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. | |
bd371182 AL |
27 | |
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: | |
32 | ||
33 | 1. A philosopher picks up the fork on their left. | |
34 | 2. They then pick up the fork on their right. | |
35 | 3. They eat. | |
36 | 4. They return the forks. | |
37 | ||
38 | Now, let’s imagine this sequence of events: | |
39 | ||
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! | |
46 | ||
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 modelling the problem itself. | |
49 | We’ll start with the philosophers: | |
50 | ||
51 | ```rust | |
52 | struct Philosopher { | |
53 | name: String, | |
54 | } | |
55 | ||
56 | impl Philosopher { | |
57 | fn new(name: &str) -> Philosopher { | |
58 | Philosopher { | |
59 | name: name.to_string(), | |
60 | } | |
61 | } | |
62 | } | |
63 | ||
64 | fn main() { | |
62682a34 | 65 | let p1 = Philosopher::new("Judith Butler"); |
bd371182 AL |
66 | let p2 = Philosopher::new("Gilles Deleuze"); |
67 | let p3 = Philosopher::new("Karl Marx"); | |
62682a34 | 68 | let p4 = Philosopher::new("Emma Goldman"); |
bd371182 AL |
69 | let p5 = Philosopher::new("Michel Foucault"); |
70 | } | |
71 | ``` | |
72 | ||
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. | |
77 | ||
d9579d0f AL |
78 | [struct]: structs.html |
79 | [string]: strings.html | |
80 | ||
bd371182 AL |
81 | Let’s continue: |
82 | ||
83 | ```rust | |
84 | # struct Philosopher { | |
85 | # name: String, | |
86 | # } | |
87 | impl Philosopher { | |
88 | fn new(name: &str) -> Philosopher { | |
89 | Philosopher { | |
90 | name: name.to_string(), | |
91 | } | |
92 | } | |
93 | } | |
94 | ``` | |
95 | ||
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: | |
98 | ||
99 | ```rust | |
100 | # struct Philosopher { | |
101 | # name: String, | |
102 | # } | |
103 | # impl Philosopher { | |
104 | fn new(name: &str) -> Philosopher { | |
105 | # Philosopher { | |
106 | # name: name.to_string(), | |
107 | # } | |
108 | # } | |
109 | # } | |
110 | ``` | |
111 | ||
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. | |
114 | ||
115 | ```rust | |
116 | # struct Philosopher { | |
117 | # name: String, | |
118 | # } | |
119 | # impl Philosopher { | |
120 | # fn new(name: &str) -> Philosopher { | |
121 | Philosopher { | |
122 | name: name.to_string(), | |
123 | } | |
124 | # } | |
125 | # } | |
126 | ``` | |
127 | ||
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`. | |
132 | ||
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. | |
138 | ||
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 | |
144 | up returning it. | |
145 | ||
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: | |
149 | ||
150 | ```rust | |
151 | # struct Philosopher { | |
152 | # name: String, | |
153 | # } | |
c1a9b12d | 154 | # |
bd371182 AL |
155 | # impl Philosopher { |
156 | # fn new(name: &str) -> Philosopher { | |
157 | # Philosopher { | |
158 | # name: name.to_string(), | |
159 | # } | |
160 | # } | |
161 | # } | |
c1a9b12d | 162 | # |
bd371182 | 163 | fn main() { |
62682a34 | 164 | let p1 = Philosopher::new("Judith Butler"); |
bd371182 AL |
165 | let p2 = Philosopher::new("Gilles Deleuze"); |
166 | let p3 = Philosopher::new("Karl Marx"); | |
62682a34 | 167 | let p4 = Philosopher::new("Emma Goldman"); |
bd371182 AL |
168 | let p5 = Philosopher::new("Michel Foucault"); |
169 | } | |
170 | ``` | |
171 | ||
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: | |
175 | ||
176 | ```rust | |
177 | # struct Philosopher { | |
178 | # name: String, | |
179 | # } | |
180 | fn main() { | |
62682a34 | 181 | let p1 = Philosopher { name: "Judith Butler".to_string() }; |
bd371182 AL |
182 | let p2 = Philosopher { name: "Gilles Deleuze".to_string() }; |
183 | let p3 = Philosopher { name: "Karl Marx".to_string() }; | |
62682a34 | 184 | let p4 = Philosopher { name: "Emma Goldman".to_string() }; |
bd371182 AL |
185 | let p5 = Philosopher { name: "Michel Foucault".to_string() }; |
186 | } | |
187 | ``` | |
188 | ||
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. | |
191 | ||
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: | |
196 | ||
197 | ```rust | |
198 | struct Philosopher { | |
199 | name: String, | |
c1a9b12d | 200 | } |
bd371182 | 201 | |
c1a9b12d | 202 | impl Philosopher { |
bd371182 AL |
203 | fn new(name: &str) -> Philosopher { |
204 | Philosopher { | |
205 | name: name.to_string(), | |
206 | } | |
207 | } | |
c1a9b12d | 208 | |
bd371182 AL |
209 | fn eat(&self) { |
210 | println!("{} is done eating.", self.name); | |
211 | } | |
212 | } | |
213 | ||
214 | fn main() { | |
215 | let philosophers = vec![ | |
62682a34 | 216 | Philosopher::new("Judith Butler"), |
bd371182 AL |
217 | Philosopher::new("Gilles Deleuze"), |
218 | Philosopher::new("Karl Marx"), | |
62682a34 | 219 | Philosopher::new("Emma Goldman"), |
bd371182 AL |
220 | Philosopher::new("Michel Foucault"), |
221 | ]; | |
222 | ||
223 | for p in &philosophers { | |
224 | p.eat(); | |
225 | } | |
226 | } | |
227 | ``` | |
228 | ||
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 | |
233 | philosopher in turn. | |
234 | ||
235 | [for]: for-loops.html | |
236 | ||
237 | In the body of the loop, we call `p.eat()`, which is defined above: | |
238 | ||
239 | ```rust,ignore | |
240 | fn eat(&self) { | |
241 | println!("{} is done eating.", self.name); | |
242 | } | |
243 | ``` | |
244 | ||
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 | |
249 | output: | |
250 | ||
251 | ```text | |
62682a34 | 252 | Judith Butler is done eating. |
bd371182 AL |
253 | Gilles Deleuze is done eating. |
254 | Karl Marx is done eating. | |
62682a34 | 255 | Emma Goldman is done eating. |
bd371182 AL |
256 | Michel Foucault is done eating. |
257 | ``` | |
258 | ||
259 | Easy enough, they’re all done! We haven’t actually implemented the real problem | |
260 | yet, though, so we’re not done yet! | |
261 | ||
262 | Next, we want to make our philosophers not just finish eating, but actually | |
263 | eat. Here’s the next version: | |
264 | ||
265 | ```rust | |
266 | use std::thread; | |
267 | ||
268 | struct Philosopher { | |
269 | name: String, | |
c1a9b12d | 270 | } |
bd371182 | 271 | |
c1a9b12d | 272 | impl Philosopher { |
bd371182 AL |
273 | fn new(name: &str) -> Philosopher { |
274 | Philosopher { | |
275 | name: name.to_string(), | |
276 | } | |
277 | } | |
c1a9b12d | 278 | |
bd371182 AL |
279 | fn eat(&self) { |
280 | println!("{} is eating.", self.name); | |
281 | ||
282 | thread::sleep_ms(1000); | |
283 | ||
284 | println!("{} is done eating.", self.name); | |
285 | } | |
286 | } | |
287 | ||
288 | fn main() { | |
289 | let philosophers = vec![ | |
62682a34 | 290 | Philosopher::new("Judith Butler"), |
bd371182 AL |
291 | Philosopher::new("Gilles Deleuze"), |
292 | Philosopher::new("Karl Marx"), | |
62682a34 | 293 | Philosopher::new("Emma Goldman"), |
bd371182 AL |
294 | Philosopher::new("Michel Foucault"), |
295 | ]; | |
296 | ||
297 | for p in &philosophers { | |
298 | p.eat(); | |
299 | } | |
300 | } | |
301 | ``` | |
302 | ||
303 | Just a few changes. Let’s break it down. | |
304 | ||
305 | ```rust,ignore | |
306 | use std::thread; | |
307 | ``` | |
308 | ||
309 | `use` brings names into scope. We’re going to start using the `thread` module | |
310 | from the standard library, and so we need to `use` it. | |
311 | ||
312 | ```rust,ignore | |
313 | fn eat(&self) { | |
314 | println!("{} is eating.", self.name); | |
315 | ||
316 | thread::sleep_ms(1000); | |
317 | ||
318 | println!("{} is done eating.", self.name); | |
319 | } | |
320 | ``` | |
321 | ||
322 | We now print out two messages, with a `sleep_ms()` in the middle. This will | |
323 | simulate the time it takes a philosopher to eat. | |
324 | ||
62682a34 | 325 | If you run this program, you should see each philosopher eat in turn: |
bd371182 AL |
326 | |
327 | ```text | |
62682a34 SL |
328 | Judith Butler is eating. |
329 | Judith Butler is done eating. | |
bd371182 AL |
330 | Gilles Deleuze is eating. |
331 | Gilles Deleuze is done eating. | |
332 | Karl Marx is eating. | |
333 | Karl Marx is done eating. | |
62682a34 SL |
334 | Emma Goldman is eating. |
335 | Emma Goldman is done eating. | |
bd371182 AL |
336 | Michel Foucault is eating. |
337 | Michel Foucault is done eating. | |
338 | ``` | |
339 | ||
340 | Excellent! We’re getting there. There’s just one problem: we aren’t actually | |
341 | operating in a concurrent fashion, which is a core part of the problem! | |
342 | ||
343 | To make our philosophers eat concurrently, we need to make a small change. | |
344 | Here’s the next iteration: | |
345 | ||
346 | ```rust | |
347 | use std::thread; | |
348 | ||
349 | struct Philosopher { | |
350 | name: String, | |
c1a9b12d | 351 | } |
bd371182 | 352 | |
c1a9b12d | 353 | impl Philosopher { |
bd371182 AL |
354 | fn new(name: &str) -> Philosopher { |
355 | Philosopher { | |
356 | name: name.to_string(), | |
357 | } | |
358 | } | |
359 | ||
360 | fn eat(&self) { | |
361 | println!("{} is eating.", self.name); | |
362 | ||
363 | thread::sleep_ms(1000); | |
364 | ||
365 | println!("{} is done eating.", self.name); | |
366 | } | |
367 | } | |
368 | ||
369 | fn main() { | |
370 | let philosophers = vec![ | |
62682a34 | 371 | Philosopher::new("Judith Butler"), |
bd371182 AL |
372 | Philosopher::new("Gilles Deleuze"), |
373 | Philosopher::new("Karl Marx"), | |
62682a34 | 374 | Philosopher::new("Emma Goldman"), |
bd371182 AL |
375 | Philosopher::new("Michel Foucault"), |
376 | ]; | |
377 | ||
378 | let handles: Vec<_> = philosophers.into_iter().map(|p| { | |
379 | thread::spawn(move || { | |
380 | p.eat(); | |
381 | }) | |
382 | }).collect(); | |
383 | ||
384 | for h in handles { | |
385 | h.join().unwrap(); | |
386 | } | |
387 | } | |
388 | ``` | |
389 | ||
390 | All we’ve done is change the loop in `main()`, and added a second one! Here’s the | |
391 | first change: | |
392 | ||
393 | ```rust,ignore | |
394 | let handles: Vec<_> = philosophers.into_iter().map(|p| { | |
395 | thread::spawn(move || { | |
396 | p.eat(); | |
397 | }) | |
398 | }).collect(); | |
399 | ``` | |
400 | ||
d9579d0f | 401 | While this is only five lines, they’re a dense five. Let’s break it down. |
bd371182 AL |
402 | |
403 | ```rust,ignore | |
c1a9b12d | 404 | let handles: Vec<_> = |
bd371182 AL |
405 | ``` |
406 | ||
407 | We introduce a new binding, called `handles`. We’ve given it this name because | |
408 | we are going to make some new threads, and that will return some handles to those | |
409 | threads that let us control their operation. We need to explicitly annotate | |
410 | the type here, though, due to an issue we’ll talk about later. The `_` is | |
411 | a type placeholder. We’re saying “`handles` is a vector of something, but you | |
412 | can figure out what that something is, Rust.” | |
413 | ||
414 | ```rust,ignore | |
415 | philosophers.into_iter().map(|p| { | |
416 | ``` | |
417 | ||
418 | We take our list of philosophers and call `into_iter()` on it. This creates an | |
419 | iterator that takes ownership of each philosopher. We need to do this to pass | |
420 | them to our threads. We take that iterator and call `map` on it, which takes a | |
421 | closure as an argument and calls that closure on each element in turn. | |
422 | ||
423 | ```rust,ignore | |
424 | thread::spawn(move || { | |
425 | p.eat(); | |
426 | }) | |
427 | ``` | |
428 | ||
429 | Here’s where the concurrency happens. The `thread::spawn` function takes a closure | |
430 | as an argument and executes that closure in a new thread. This closure needs | |
431 | an extra annotation, `move`, to indicate that the closure is going to take | |
432 | ownership of the values it’s capturing. Primarily, the `p` variable of the | |
433 | `map` function. | |
434 | ||
62682a34 SL |
435 | 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]. |
436 | ||
437 | [es]: functions.html#expressions-vs.-statements | |
bd371182 AL |
438 | |
439 | ```rust,ignore | |
440 | }).collect(); | |
441 | ``` | |
442 | ||
443 | Finally, we take the result of all those `map` calls and collect them up. | |
444 | `collect()` will make them into a collection of some kind, which is why we | |
445 | needed to annotate the return type: we want a `Vec<T>`. The elements are the | |
446 | return values of the `thread::spawn` calls, which are handles to those threads. | |
447 | Whew! | |
448 | ||
449 | ```rust,ignore | |
450 | for h in handles { | |
451 | h.join().unwrap(); | |
452 | } | |
453 | ``` | |
454 | ||
455 | At the end of `main()`, we loop through the handles and call `join()` on them, | |
456 | which blocks execution until the thread has completed execution. This ensures | |
457 | that the threads complete their work before the program exits. | |
458 | ||
459 | If you run this program, you’ll see that the philosophers eat out of order! | |
d9579d0f | 460 | We have multi-threading! |
bd371182 AL |
461 | |
462 | ```text | |
c1a9b12d | 463 | Judith Butler is eating. |
bd371182 | 464 | Gilles Deleuze is eating. |
c1a9b12d | 465 | Karl Marx is eating. |
62682a34 | 466 | Emma Goldman is eating. |
bd371182 | 467 | Michel Foucault is eating. |
62682a34 | 468 | Judith Butler is done eating. |
c1a9b12d | 469 | Gilles Deleuze is done eating. |
bd371182 | 470 | Karl Marx is done eating. |
c1a9b12d | 471 | Emma Goldman is done eating. |
bd371182 AL |
472 | Michel Foucault is done eating. |
473 | ``` | |
474 | ||
475 | But what about the forks? We haven’t modeled them at all yet. | |
476 | ||
477 | To do that, let’s make a new `struct`: | |
478 | ||
479 | ```rust | |
480 | use std::sync::Mutex; | |
481 | ||
482 | struct Table { | |
483 | forks: Vec<Mutex<()>>, | |
484 | } | |
485 | ``` | |
486 | ||
62682a34 | 487 | This `Table` has a vector of `Mutex`es. A mutex is a way to control |
bd371182 AL |
488 | concurrency: only one thread can access the contents at once. This is exactly |
489 | the property we need with our forks. We use an empty tuple, `()`, inside the | |
490 | mutex, since we’re not actually going to use the value, just hold onto it. | |
491 | ||
492 | Let’s modify the program to use the `Table`: | |
493 | ||
494 | ```rust | |
495 | use std::thread; | |
496 | use std::sync::{Mutex, Arc}; | |
497 | ||
498 | struct Philosopher { | |
499 | name: String, | |
500 | left: usize, | |
501 | right: usize, | |
502 | } | |
503 | ||
504 | impl Philosopher { | |
505 | fn new(name: &str, left: usize, right: usize) -> Philosopher { | |
506 | Philosopher { | |
507 | name: name.to_string(), | |
508 | left: left, | |
509 | right: right, | |
510 | } | |
511 | } | |
512 | ||
513 | fn eat(&self, table: &Table) { | |
514 | let _left = table.forks[self.left].lock().unwrap(); | |
515 | let _right = table.forks[self.right].lock().unwrap(); | |
516 | ||
517 | println!("{} is eating.", self.name); | |
518 | ||
519 | thread::sleep_ms(1000); | |
520 | ||
521 | println!("{} is done eating.", self.name); | |
522 | } | |
523 | } | |
524 | ||
525 | struct Table { | |
526 | forks: Vec<Mutex<()>>, | |
527 | } | |
528 | ||
529 | fn main() { | |
530 | let table = Arc::new(Table { forks: vec![ | |
531 | Mutex::new(()), | |
532 | Mutex::new(()), | |
533 | Mutex::new(()), | |
534 | Mutex::new(()), | |
535 | Mutex::new(()), | |
536 | ]}); | |
537 | ||
538 | let philosophers = vec![ | |
62682a34 | 539 | Philosopher::new("Judith Butler", 0, 1), |
bd371182 AL |
540 | Philosopher::new("Gilles Deleuze", 1, 2), |
541 | Philosopher::new("Karl Marx", 2, 3), | |
62682a34 | 542 | Philosopher::new("Emma Goldman", 3, 4), |
bd371182 AL |
543 | Philosopher::new("Michel Foucault", 0, 4), |
544 | ]; | |
545 | ||
546 | let handles: Vec<_> = philosophers.into_iter().map(|p| { | |
547 | let table = table.clone(); | |
548 | ||
549 | thread::spawn(move || { | |
550 | p.eat(&table); | |
551 | }) | |
552 | }).collect(); | |
553 | ||
554 | for h in handles { | |
555 | h.join().unwrap(); | |
556 | } | |
557 | } | |
558 | ``` | |
559 | ||
560 | Lots of changes! However, with this iteration, we’ve got a working program. | |
561 | Let’s go over the details: | |
562 | ||
563 | ```rust,ignore | |
564 | use std::sync::{Mutex, Arc}; | |
565 | ``` | |
566 | ||
567 | We’re going to use another structure from the `std::sync` package: `Arc<T>`. | |
568 | We’ll talk more about it when we use it. | |
569 | ||
570 | ```rust,ignore | |
571 | struct Philosopher { | |
572 | name: String, | |
573 | left: usize, | |
574 | right: usize, | |
575 | } | |
576 | ``` | |
577 | ||
578 | We need to add two more fields to our `Philosopher`. Each philosopher is going | |
579 | to have two forks: the one on their left, and the one on their right. | |
580 | We’ll use the `usize` type to indicate them, as it’s the type that you index | |
581 | vectors with. These two values will be the indexes into the `forks` our `Table` | |
582 | has. | |
583 | ||
584 | ```rust,ignore | |
585 | fn new(name: &str, left: usize, right: usize) -> Philosopher { | |
586 | Philosopher { | |
587 | name: name.to_string(), | |
588 | left: left, | |
589 | right: right, | |
590 | } | |
591 | } | |
592 | ``` | |
593 | ||
594 | We now need to construct those `left` and `right` values, so we add them to | |
595 | `new()`. | |
596 | ||
597 | ```rust,ignore | |
598 | fn eat(&self, table: &Table) { | |
599 | let _left = table.forks[self.left].lock().unwrap(); | |
600 | let _right = table.forks[self.right].lock().unwrap(); | |
601 | ||
602 | println!("{} is eating.", self.name); | |
603 | ||
604 | thread::sleep_ms(1000); | |
605 | ||
606 | println!("{} is done eating.", self.name); | |
607 | } | |
608 | ``` | |
609 | ||
610 | We have two new lines. We’ve also added an argument, `table`. We access the | |
611 | `Table`’s list of forks, and then use `self.left` and `self.right` to access | |
612 | the fork at that particular index. That gives us access to the `Mutex` at that | |
613 | index, and we call `lock()` on it. If the mutex is currently being accessed by | |
614 | someone else, we’ll block until it becomes available. | |
615 | ||
616 | The call to `lock()` might fail, and if it does, we want to crash. In this | |
617 | case, the error that could happen is that the mutex is [‘poisoned’][poison], | |
618 | which is what happens when the thread panics while the lock is held. Since this | |
619 | shouldn’t happen, we just use `unwrap()`. | |
620 | ||
621 | [poison]: ../std/sync/struct.Mutex.html#poisoning | |
622 | ||
623 | One other odd thing about these lines: we’ve named the results `_left` and | |
624 | `_right`. What’s up with that underscore? Well, we aren’t planning on | |
625 | _using_ the value inside the lock. We just want to acquire it. As such, | |
626 | Rust will warn us that we never use the value. By using the underscore, | |
627 | we tell Rust that this is what we intended, and it won’t throw a warning. | |
628 | ||
629 | What about releasing the lock? Well, that will happen when `_left` and | |
630 | `_right` go out of scope, automatically. | |
631 | ||
632 | ```rust,ignore | |
633 | let table = Arc::new(Table { forks: vec![ | |
634 | Mutex::new(()), | |
635 | Mutex::new(()), | |
636 | Mutex::new(()), | |
637 | Mutex::new(()), | |
638 | Mutex::new(()), | |
639 | ]}); | |
640 | ``` | |
641 | ||
642 | Next, in `main()`, we make a new `Table` and wrap it in an `Arc<T>`. | |
643 | ‘arc’ stands for ‘atomic reference count’, and we need that to share | |
644 | our `Table` across multiple threads. As we share it, the reference | |
645 | count will go up, and when each thread ends, it will go back down. | |
646 | ||
647 | ||
648 | ```rust,ignore | |
649 | let philosophers = vec![ | |
62682a34 | 650 | Philosopher::new("Judith Butler", 0, 1), |
bd371182 AL |
651 | Philosopher::new("Gilles Deleuze", 1, 2), |
652 | Philosopher::new("Karl Marx", 2, 3), | |
62682a34 | 653 | Philosopher::new("Emma Goldman", 3, 4), |
bd371182 AL |
654 | Philosopher::new("Michel Foucault", 0, 4), |
655 | ]; | |
656 | ``` | |
657 | ||
658 | We need to pass in our `left` and `right` values to the constructors for our | |
659 | `Philosopher`s. But there’s one more detail here, and it’s _very_ important. If | |
660 | you look at the pattern, it’s all consistent until the very end. Monsieur | |
661 | Foucault should have `4, 0` as arguments, but instead, has `0, 4`. This is what | |
662 | prevents deadlock, actually: one of our philosophers is left handed! This is | |
663 | one way to solve the problem, and in my opinion, it’s the simplest. | |
664 | ||
665 | ```rust,ignore | |
666 | let handles: Vec<_> = philosophers.into_iter().map(|p| { | |
667 | let table = table.clone(); | |
668 | ||
669 | thread::spawn(move || { | |
670 | p.eat(&table); | |
671 | }) | |
672 | }).collect(); | |
673 | ``` | |
674 | ||
675 | Finally, inside of our `map()`/`collect()` loop, we call `table.clone()`. The | |
676 | `clone()` method on `Arc<T>` is what bumps up the reference count, and when it | |
62682a34 SL |
677 | goes out of scope, it decrements the count. This is needed so that we know how |
678 | many references to `table` exist across our threads. If we didn’t have a count, | |
679 | we wouldn’t know how to deallocate it. | |
680 | ||
681 | You’ll notice we can introduce a new binding to `table` here, and it will | |
682 | shadow the old one. This is often used so that you don’t need to come up with | |
683 | two unique names. | |
bd371182 AL |
684 | |
685 | With this, our program works! Only two philosophers can eat at any one time, | |
686 | and so you’ll get some output like this: | |
687 | ||
688 | ```text | |
689 | Gilles Deleuze is eating. | |
62682a34 SL |
690 | Emma Goldman is eating. |
691 | Emma Goldman is done eating. | |
bd371182 | 692 | Gilles Deleuze is done eating. |
62682a34 | 693 | Judith Butler is eating. |
bd371182 | 694 | Karl Marx is eating. |
62682a34 | 695 | Judith Butler is done eating. |
bd371182 AL |
696 | Michel Foucault is eating. |
697 | Karl Marx is done eating. | |
698 | Michel Foucault is done eating. | |
699 | ``` | |
700 | ||
701 | Congrats! You’ve implemented a classic concurrency problem in Rust. |