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 the version from [this paper][paper] by Tony Hoare in 1985.
   6
   7 [paper]: http://www.usingcsp.com/cspbook.pdf
   8
   9 > In ancient times, a wealthy philanthropist endowed a College to accommodate
  10 > five eminent philosophers. Each philosopher had a room in which he could
  11 > engage in his 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 his
  17 > time thinking; but when he felt hungry, he went to the dining room, sat down
  18 > in his own chair, picked up his own fork on his 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 his right. When we was finished he would put down both his
  22 > forks, get up from his 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, he
  24 > just has to wait until the fork is available again.
  25
  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:
  30
  31 1. A philosopher picks up the fork on their left.
  32 2. They then pick up the fork on their right.
  33 3. They eat.
  34 4. They return the forks.
  35
  36 Now, let’s imagine this sequence of events:
  37
  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!
  44
  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:
  48
  49 ```rust
  50 struct Philosopher {
  51     name: String,
  52 }
  53
  54 impl Philosopher {
  55     fn new(name: &str) -> Philosopher {
  56         Philosopher {
  57             name: name.to_string(),
  58         }
  59     }
  60 }
  61
  62 fn main() {
  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");
  68 }
  69 ```
  70
  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.
  75
  76 [struct]: structs.html
  77 [string]: strings.html
  78
  79 Let’s continue:
  80
  81 ```rust
  82 # struct Philosopher {
  83 #     name: String,
  84 # }
  85 impl Philosopher {
  86     fn new(name: &str) -> Philosopher {
  87         Philosopher {
  88             name: name.to_string(),
  89         }
  90     }
  91 }
  92 ```
  93
  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:
  96
  97 ```rust
  98 # struct Philosopher {
  99 #     name: String,
 100 # }
 101 # impl Philosopher {
 102 fn new(name: &str) -> Philosopher {
 103 #         Philosopher {
 104 #             name: name.to_string(),
 105 #         }
 106 #     }
 107 # }
 108 ```
 109
 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.
 112
 113 ```rust
 114 # struct Philosopher {
 115 #     name: String,
 116 # }
 117 # impl Philosopher {
 118 #    fn new(name: &str) -> Philosopher {
 119 Philosopher {
 120     name: name.to_string(),
 121 }
 122 #     }
 123 # }
 124 ```
 125
 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`.
 130
 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.
 136
 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
 142 up returning it.
 143
 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:
 147
 148 ```rust
 149 # struct Philosopher {
 150 #     name: String,
 151 # }
 152 #
 153 # impl Philosopher {
 154 #     fn new(name: &str) -> Philosopher {
 155 #         Philosopher {
 156 #             name: name.to_string(),
 157 #         }
 158 #     }
 159 # }
 160 #
 161 fn main() {
 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");
 167 }
 168 ```
 169
 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:
 173
 174 ```rust
 175 # struct Philosopher {
 176 #     name: String,
 177 # }
 178 fn main() {
 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() };
 184 }
 185 ```
 186
 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.
 189
 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:
 194
 195 ```rust
 196 struct Philosopher {
 197     name: String,
 198 }
 199
 200 impl Philosopher {
 201     fn new(name: &str) -> Philosopher {
 202         Philosopher {
 203             name: name.to_string(),
 204         }
 205     }
 206
 207     fn eat(&self) {
 208         println!("{} is done eating.", self.name);
 209     }
 210 }
 211
 212 fn main() {
 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"),
 219     ];
 220
 221     for p in &philosophers {
 222         p.eat();
 223     }
 224 }
 225 ```
 226
 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
 231 philosopher in turn.
 232
 233 [for]: for-loops.html
 234
 235 In the body of the loop, we call `p.eat()`, which is defined above:
 236
 237 ```rust,ignore
 238 fn eat(&self) {
 239     println!("{} is done eating.", self.name);
 240 }
 241 ```
 242
 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
 247 output:
 248
 249 ```text
 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.
 255 ```
 256
 257 Easy enough, they’re all done! We haven’t actually implemented the real problem
 258 yet, though, so we’re not done yet!
 259
 260 Next, we want to make our philosophers not just finish eating, but actually
 261 eat. Here’s the next version:
 262
 263 ```rust
 264 use std::thread;
 265
 266 struct Philosopher {
 267     name: String,
 268 }
 269
 270 impl Philosopher {
 271     fn new(name: &str) -> Philosopher {
 272         Philosopher {
 273             name: name.to_string(),
 274         }
 275     }
 276
 277     fn eat(&self) {
 278         println!("{} is eating.", self.name);
 279
 280         thread::sleep_ms(1000);
 281
 282         println!("{} is done eating.", self.name);
 283     }
 284 }
 285
 286 fn main() {
 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"),
 293     ];
 294
 295     for p in &philosophers {
 296         p.eat();
 297     }
 298 }
 299 ```
 300
 301 Just a few changes. Let’s break it down.
 302
 303 ```rust,ignore
 304 use std::thread;
 305 ```
 306
 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.
 309
 310 ```rust,ignore
 311     fn eat(&self) {
 312         println!("{} is eating.", self.name);
 313
 314         thread::sleep_ms(1000);
 315
 316         println!("{} is done eating.", self.name);
 317     }
 318 ```
 319
 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.
 322
 323 If you run this program, you should see each philosopher eat in turn:
 324
 325 ```text
 326 Baruch Spinoza is eating.
 327 Baruch Spinoza is done eating.
 328 Gilles Deleuze is eating.
 329 Gilles Deleuze is done eating.
 330 Karl Marx is 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.
 336 ```
 337
 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!
 340
 341 To make our philosophers eat concurrently, we need to make a small change.
 342 Here’s the next iteration:
 343
 344 ```rust
 345 use std::thread;
 346
 347 struct Philosopher {
 348     name: String,
 349 }
 350
 351 impl Philosopher {
 352     fn new(name: &str) -> Philosopher {
 353         Philosopher {
 354             name: name.to_string(),
 355         }
 356     }
 357
 358     fn eat(&self) {
 359         println!("{} is eating.", self.name);
 360
 361         thread::sleep_ms(1000);
 362
 363         println!("{} is done eating.", self.name);
 364     }
 365 }
 366
 367 fn main() {
 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"),
 374     ];
 375
 376     let handles: Vec<_> = philosophers.into_iter().map(|p| {
 377         thread::spawn(move || {
 378             p.eat();
 379         })
 380     }).collect();
 381
 382     for h in handles {
 383         h.join().unwrap();
 384     }
 385 }
 386 ```
 387
 388 All we’ve done is change the loop in `main()`, and added a second one! Here’s the
 389 first change:
 390
 391 ```rust,ignore
 392 let handles: Vec<_> = philosophers.into_iter().map(|p| {
 393     thread::spawn(move || {
 394         p.eat();
 395     })
 396 }).collect();
 397 ```
 398
 399 While this is only five lines, they’re a dense five. Let’s break it down.
 400
 401 ```rust,ignore
 402 let handles: Vec<_> =
 403 ```
 404
 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.”
 411
 412 ```rust,ignore
 413 philosophers.into_iter().map(|p| {
 414 ```
 415
 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.
 420
 421 ```rust,ignore
 422     thread::spawn(move || {
 423         p.eat();
 424     })
 425 ```
 426
 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
 431 `map` function.
 432
 433 Inside the thread, all we do is call `eat()` on `p`.
 434
 435 ```rust,ignore
 436 }).collect();
 437 ```
 438
 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.
 443 Whew!
 444
 445 ```rust,ignore
 446 for h in handles {
 447     h.join().unwrap();
 448 }
 449 ```
 450
 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.
 454
 455 If you run this program, you’ll see that the philosophers eat out of order!
 456 We have multi-threading!
 457
 458 ```text
 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.
 466 Karl Marx is eating.
 467 Karl Marx is done eating.
 468 Michel Foucault is done eating.
 469 ```
 470
 471 But what about the forks? We haven’t modeled them at all yet.
 472
 473 To do that, let’s make a new `struct`:
 474
 475 ```rust
 476 use std::sync::Mutex;
 477
 478 struct Table {
 479     forks: Vec<Mutex<()>>,
 480 }
 481 ```
 482
 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.
 487
 488 Let’s modify the program to use the `Table`:
 489
 490 ```rust
 491 use std::thread;
 492 use std::sync::{Mutex, Arc};
 493
 494 struct Philosopher {
 495     name: String,
 496     left: usize,
 497     right: usize,
 498 }
 499
 500 impl Philosopher {
 501     fn new(name: &str, left: usize, right: usize) -> Philosopher {
 502         Philosopher {
 503             name: name.to_string(),
 504             left: left,
 505             right: right,
 506         }
 507     }
 508
 509     fn eat(&self, table: &Table) {
 510         let _left = table.forks[self.left].lock().unwrap();
 511         let _right = table.forks[self.right].lock().unwrap();
 512
 513         println!("{} is eating.", self.name);
 514
 515         thread::sleep_ms(1000);
 516
 517         println!("{} is done eating.", self.name);
 518     }
 519 }
 520
 521 struct Table {
 522     forks: Vec<Mutex<()>>,
 523 }
 524
 525 fn main() {
 526     let table = Arc::new(Table { forks: vec![
 527         Mutex::new(()),
 528         Mutex::new(()),
 529         Mutex::new(()),
 530         Mutex::new(()),
 531         Mutex::new(()),
 532     ]});
 533
 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),
 540     ];
 541
 542     let handles: Vec<_> = philosophers.into_iter().map(|p| {
 543         let table = table.clone();
 544
 545         thread::spawn(move || {
 546             p.eat(&table);
 547         })
 548     }).collect();
 549
 550     for h in handles {
 551         h.join().unwrap();
 552     }
 553 }
 554 ```
 555
 556 Lots of changes! However, with this iteration, we’ve got a working program.
 557 Let’s go over the details:
 558
 559 ```rust,ignore
 560 use std::sync::{Mutex, Arc};
 561 ```
 562
 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.
 565
 566 ```rust,ignore
 567 struct Philosopher {
 568     name: String,
 569     left: usize,
 570     right: usize,
 571 }
 572 ```
 573
 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`
 578 has.
 579
 580 ```rust,ignore
 581 fn new(name: &str, left: usize, right: usize) -> Philosopher {
 582     Philosopher {
 583         name: name.to_string(),
 584         left: left,
 585         right: right,
 586     }
 587 }
 588 ```
 589
 590 We now need to construct those `left` and `right` values, so we add them to
 591 `new()`.
 592
 593 ```rust,ignore
 594 fn eat(&self, table: &Table) {
 595     let _left = table.forks[self.left].lock().unwrap();
 596     let _right = table.forks[self.right].lock().unwrap();
 597
 598     println!("{} is eating.", self.name);
 599
 600     thread::sleep_ms(1000);
 601
 602     println!("{} is done eating.", self.name);
 603 }
 604 ```
 605
 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.
 611
 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()`.
 616
 617 [poison]: ../std/sync/struct.Mutex.html#poisoning
 618
 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.
 624
 625 What about releasing the lock? Well, that will happen when `_left` and
 626 `_right` go out of scope, automatically.
 627
 628 ```rust,ignore
 629     let table = Arc::new(Table { forks: vec![
 630         Mutex::new(()),
 631         Mutex::new(()),
 632         Mutex::new(()),
 633         Mutex::new(()),
 634         Mutex::new(()),
 635     ]});
 636 ```
 637
 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.
 642
 643
 644 ```rust,ignore
 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),
 651 ];
 652 ```
 653
 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.
 660
 661 ```rust,ignore
 662 let handles: Vec<_> = philosophers.into_iter().map(|p| {
 663     let table = table.clone();
 664
 665     thread::spawn(move || {
 666         p.eat(&table);
 667     })
 668 }).collect();
 669 ```
 670
 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.
 676
 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:
 679
 680 ```text
 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.
 686 Karl Marx 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.
 691 ```
 692
 693 Congrats! You’ve implemented a classic concurrency problem in Rust.