src/doc/trpl/dining-philosophers.md

   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
   5 1965, but we’ll use a lightly adapted version from [this paper][paper] by Tony
   6 Hoare in 1985.
   7
   8 [paper]: http://www.usingcsp.com/cspbook.pdf
   9
  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 centre 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.
  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 modeling 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() {
  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");
  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
  78 [struct]: structs.html
  79 [string]: strings.html
  80
  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 # }
 154 #
 155 # impl Philosopher {
 156 #     fn new(name: &str) -> Philosopher {
 157 #         Philosopher {
 158 #             name: name.to_string(),
 159 #         }
 160 #     }
 161 # }
 162 #
 163 fn main() {
 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");
 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() {
 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() };
 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,
 200 }
 201
 202 impl Philosopher {
 203     fn new(name: &str) -> Philosopher {
 204         Philosopher {
 205             name: name.to_string(),
 206         }
 207     }
 208
 209     fn eat(&self) {
 210         println!("{} is done eating.", self.name);
 211     }
 212 }
 213
 214 fn main() {
 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"),
 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
 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.
 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,
 270 }
 271
 272 impl Philosopher {
 273     fn new(name: &str) -> Philosopher {
 274         Philosopher {
 275             name: name.to_string(),
 276         }
 277     }
 278
 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![
 290         Philosopher::new("Judith Butler"),
 291         Philosopher::new("Gilles Deleuze"),
 292         Philosopher::new("Karl Marx"),
 293         Philosopher::new("Emma Goldman"),
 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
 325 If you run this program, you should see each philosopher eat in turn:
 326
 327 ```text
 328 Judith Butler is eating.
 329 Judith Butler is done eating.
 330 Gilles Deleuze is eating.
 331 Gilles Deleuze is done eating.
 332 Karl Marx is eating.
 333 Karl Marx is done eating.
 334 Emma Goldman is eating.
 335 Emma Goldman is done eating.
 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,
 351 }
 352
 353 impl Philosopher {
 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![
 371         Philosopher::new("Judith Butler"),
 372         Philosopher::new("Gilles Deleuze"),
 373         Philosopher::new("Karl Marx"),
 374         Philosopher::new("Emma Goldman"),
 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
 401 While this is only five lines, they’re a dense five. Let’s break it down.
 402
 403 ```rust,ignore
 404 let handles: Vec<_> =
 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
 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
 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!
 460 We have multi-threading!
 461
 462 ```text
 463 Judith Butler is eating.
 464 Gilles Deleuze is eating.
 465 Karl Marx is eating.
 466 Emma Goldman is eating.
 467 Michel Foucault is eating.
 468 Judith Butler is done eating.
 469 Gilles Deleuze is done eating.
 470 Karl Marx is done eating.
 471 Emma Goldman is done eating.
 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
 487 This `Table` has a vector of `Mutex`es. A mutex is a way to control
 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![
 539         Philosopher::new("Judith Butler", 0, 1),
 540         Philosopher::new("Gilles Deleuze", 1, 2),
 541         Philosopher::new("Karl Marx", 2, 3),
 542         Philosopher::new("Emma Goldman", 3, 4),
 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![
 650     Philosopher::new("Judith Butler", 0, 1),
 651     Philosopher::new("Gilles Deleuze", 1, 2),
 652     Philosopher::new("Karl Marx", 2, 3),
 653     Philosopher::new("Emma Goldman", 3, 4),
 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
 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.
 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.
 690 Emma Goldman is eating.
 691 Emma Goldman is done eating.
 692 Gilles Deleuze is done eating.
 693 Judith Butler is eating.
 694 Karl Marx is eating.
 695 Judith Butler is done eating.
 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.