食事する哲学者を python で実装してみる

なんとなく Rust が気になって、[検索して見つけたドキュメント](https://rust-lang-ja.github.io/the-rust-programming-language-ja/1.6/book/dining-philosophers.html)を写経ししたりしてました。（このドキュメントはちょっと古いようで食事する哲学者のページは今はなくなってる模様）
実際に実行してみたところどうも想定した挙動になって無いように見えて、Rust もまだよく分かってないしなー、と思い python で実装してみた。
ちなみに threading 使うのは初めて。 python 3 系から asyncio ってモジュールも入ってるようだったけど、[詳しそうな記事をあたってみたところ](http://qiita.com/icoxfog417/items/07cbf5110ca82629aca0) マルチスレッドで事は足りるかなと。

```python:dining_philosopher.py
from threading import Thread, Lock
import time

class Philosopher():
    def __init__(self, name, left, right):
        self.name = name
        self.left = left
        self.right = right

    def eat(self, table):
        with table["forks"][self.left]:
            # print("%s taked fork(%s)" % (self.name, self.left) )
            time.sleep(0.1)
            with table["forks"][self.right]:
                # print("  %s taked fork(%s)" % (self.name, self.right))
                print("    %s is eating" % self.name)

                time.sleep(1)

                print("    %s is done eating" % self.name)

class EatingThread(Thread):
    def __init__(self, phirosopher, table):
        super(EatingThread, self).__init__()
        self.philosopeher = phirosopher
        self.table = table

    def run(self):
        self.philosopeher.eat(self.table)


if __name__ == "__main__":
    table = {
        "forks": [
            Lock(),
            Lock(),
            Lock(),
            Lock(),
            Lock(),
        ]
    }

    philosophers = [
        Philosopher("Judith Butler", 0, 1),
        Philosopher("Gilles Deleuze", 1, 2),
        Philosopher("Karl Marx", 2, 3),
        Philosopher("Emma Goldman", 3, 4),
        Philosopher("Michel Foucault", 0, 4),
    ]

    def make_thread(p):
        thread = EatingThread(p, table)
        thread.start()
        return thread

    threads = [make_thread(p) for p in philosophers]
    for thread in threads:
        thread.join()
```

結果は想定通りにならず、哲学者がひとりずつ食事してる。

    Emma Goldman is eating
    Emma Goldman is done eating
    Karl Marx is eating
    Karl Marx is done eating
    Gilles Deleuze is eating
    Gilles Deleuze is done eating
    Judith Butler is eating
    Judith Butler is done eating
    Michel Foucault is eating
    Michel Foucault is done eating

元のドキュメントではデッドロックを避けるために Foucault さんを左利き扱いにしてて、たしかにデッドロックは回避されてるんだけど、 Butler, Gilles, Marx, Emma が 0, 1, 2, 3 のフォークもって行った時点で Foucault が0番目を取れずに Emma が4番目とって、あとは右手にフォーク持ってる人が順々に食べていくと、何回やってもこの順序になってドキュメントにあるような順序にはならない。ここまでは Rust で写経した結果も同じだった。

とりあえず、いっせーのせで食べに来るのではなく、各々思索活動しておなかがすいたら来てもらうようにしたらそれっぽくなりました。

```python
from threading import Thread, Lock
import time
import random

class Philosopher():
    def __init__(self, name, left, right):
        self.name = name
        self.left = left
        self.right = right

    # 思索活動時間
    def philosophizing(self):
        time.sleep( random.random() )

    def eat(self, table):
        with table["forks"][self.left]:
            # print("%s taked fork(%s)" % (self.name, self.left) )
            time.sleep(0.1)
            with table["forks"][self.right]:
                # print("  %s taked fork(%s)" % (self.name, self.right))
                print("    %s is eating" % self.name)

                time.sleep(1)

                print("    %s is done eating" % self.name)

class EatingThread(Thread):
    def __init__(self, phirosopher, table):
        super(EatingThread, self).__init__()
        self.philosopeher = phirosopher
        self.table = table

    def run(self):
        # ご飯を食べる前に哲学者らしく思索活動してもらう
        self.philosopeher.philosophizing()
        self.philosopeher.eat(self.table)


if __name__ == "__main__":
    table = {
        "forks": [
            Lock(),
            Lock(),
            Lock(),
            Lock(),
            Lock(),
        ]
    }

    philosophers = [
        Philosopher("Judith Butler", 0, 1),
        Philosopher("Gilles Deleuze", 1, 2),
        Philosopher("Karl Marx", 2, 3),
        Philosopher("Emma Goldman", 3, 4),
        Philosopher("Michel Foucault", 0, 4),
    ]

    def make_thread(p):
        thread = EatingThread(p, table)
        thread.start()
        return thread

    threads = [make_thread(p) for p in philosophers]
    for thread in threads:
        thread.join()
```

思索活動時間が random なので、実行結果は毎回異なりますが、隣り合ってない人なら同時に食事するようにはなった気がします。

    Judith Butler is eating
    Karl Marx is eating
    Judith Butler is done eating
    Michel Foucault is eating
    Karl Marx is done eating
    Gilles Deleuze is eating
    Michel Foucault is done eating
    Emma Goldman is eating
    Gilles Deleuze is done eating
    Emma Goldman is done eating

本来の問題の意図は「同着の時のデッドロックを防ぐためにはどうしたら良いか」のようなので、まぁ実行結果が異なっていたにせよ、利き手変えるとデッドロックしない、戻すとデッドロックするのが観測できたので問題無かったのかなとここまで書いて思いました。

[wikipedia にいくつか解決方法が載ってる](https://ja.wikipedia.org/wiki/食事する哲学者の問題)けど、利き手変えれば良いじゃんって言うのはドキュメント書いた人のユーモアでしたね。

ついでに元の Rust の方も思索活動時間を random でとるようにしてみた。

```rust
extern crate rand;

use std::thread;
use std::time::Duration;
use std::sync::{Mutex, Arc};
use rand::Rng;

struct Philosopher {
    name: String,
    left: usize,
    right: usize,
}

impl Philosopher {
    fn new(name: &str, left: usize, right: usize) -> Philosopher {
        Philosopher {
            name: name.to_string(),
            left: left,
            right: right,
        }
    }

    fn thinking(&self) {
        let thinking_time = rand::thread_rng().gen_range(1, 150);
        thread::sleep(Duration::from_millis(thinking_time));
    }

    fn eat(&self, table: &Table) {
        let _left = table.forks[self.left].lock().unwrap();
        // thread::sleep(Duration::from_millis(150));
        let _right = table.forks[self.right].lock().unwrap();

        println!("{} is eating.", self.name);

        thread::sleep(Duration::from_millis(1000));

        println!("{} is done eating.", self.name);
    }
}

struct Table {
    forks: Vec<Mutex<()>>,
}

fn main() {
    let table = Arc::new(Table { forks: vec![
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
    ]});

    let philosophers = vec![
        Philosopher::new("Judith Butler", 0, 1),
        Philosopher::new("Gilles Deleuze", 1, 2),
        Philosopher::new("Karl Marx", 2, 3),
        Philosopher::new("Emma Goldman", 3, 4),
        Philosopher::new("Michel Foucault", 0, 4),
    ];

    let handles: Vec<_> = philosophers.into_iter().map(|p| {
        let table = table.clone();

        thread::spawn(move || {
            p.thinking();
            p.eat(&table);
        })
    }).collect();

    for h in handles {
        h.join().unwrap();
    }
}
```