作為我們的第二個項目，讓我們看看一個經典的并發問題。它叫做“進餐（ji）的哲學家”。它最初由Dijkstra于1965年（網上說1971年←_←）提出，不過我們會使用Tony Hoare寫于1985年的[這篇論文](http://www.usingcsp.com/cspbook.pdf)的版本 > 在遠古時代，一個富有的慈善家捐贈了一個學院來為5名知名的哲學家提供住處。每個哲學家都有一個房間來進行他專業的思考活動；這也有一個共用的餐廳，布置了一個圓桌，周圍放著5把椅子，每一把都標出了坐在這的哲學家的名字。哲學家們按逆時針順序圍繞桌子做下。每個哲學家的左手邊放著一個金叉子，而在桌子中間有一大碗意大利面，它會不時的被補充。哲學家期望用他大部分的時間思考；不過當他餓了的時候，他走向餐廳，坐在它自己的椅子上，拿起他左手邊自己的叉子，然后把它插進意大利面。不過亂成一團的意大利面需要第二把叉子才能吃到嘴里。因此哲學家不得不拿起他右手邊的叉子。當他吃完了他會放下兩把叉子，從椅子上起來，并繼續思考。當然，一把叉子一次同時只能被一名哲學家使用。如果其他哲學家需要它，他必須等待直到叉子再次可用。 這個經典的問題展示了一些不同的并發元素。原因是事實上實現它需要一些技巧：一個簡單的實現可能會死鎖。例如，讓我們考慮一個可能解決這個問題的簡單算法： 1. 一個哲學家拿起左手邊的叉子 2. 他接著拿起右手邊的叉子 3. 他吃 4. 他返回叉子 現在，讓我們想象一下事件的序列： 1. 哲學家1開始算法，拿起他左手邊的叉子 2. 哲學家2開始算法，拿起他左手邊的叉子 3. 哲學家3開始算法，拿起他左手邊的叉子 4. 哲學家4開始算法，拿起他左手邊的叉子 5. 哲學家5開始算法，拿起他左手邊的叉子 6. 。。。？所有的叉子都被拿走了，不過沒人在吃（意大利面）！ 有不同方法可以解決這個問題。在教程中我們用我們自己的解決辦法。現在，讓我們自己來為問題建模。我將從哲學家開始： ~~~ struct Philosopher { name: String, } impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } } fn main() { let p1 = Philosopher::new("Baruch Spinoza"); let p2 = Philosopher::new("Gilles Deleuze"); let p3 = Philosopher::new("Karl Marx"); let p4 = Philosopher::new("Friedrich Nietzsche"); let p5 = Philosopher::new("Michel Foucault"); } ~~~ 這里，我們創建了一個[`struct`][struct]來代表一個哲學家。目前，我們只需要一個名字。我們選擇[`String`][string]類型作為名字，而不是`&str`。通常來說，處理一個擁有它自己數據的類型要比使用引用的數據來的簡單。 讓我們繼續： ~~~ impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } } ~~~ `impl`塊讓我們在`Philosopher`上定義方法。在這個例子中，我們定義了一個叫做`new`的“關聯函數”。第一行看起來像這樣： ~~~ fn new(name: &str) -> Philosopher { ~~~ 我們獲取了一個參數，`name`，`&str`類型的。這是另一個字符串的引用。它返回了一個我們`Philosopher`結構體的實例。 ~~~ Philosopher { name: name.to_string(), } ~~~ 這創建了一個新的`Philosopher`，并把它的`name`設置為我們的`name`參數。不僅僅是參數自身，雖然，因為我們在它上面調用了`.to_string()`。這將創建一個我們`&str`指向的字符串的拷貝，并給我們一個新的`String`，它是我們`Philosopher`的`name`字段的類型。 為什么不直接接受一個`String`呢？它更方便調用。如果我們獲取一個`String`，而我們的調用者有一個`&str`，它就不得不自己調用這個方法。這個靈活性的缺點是我們_總是_生成了一個拷貝。對于我們這個小程序，這并不是特別的重要，因為我們知道我們只會用短小的字符串。 你要注意到的最后一件事：我們剛剛定義了一個`Philosopher`，不過好像并沒有對它做什么。Rust是一個“基于表達式”的語言，它意味著Rust中幾乎所有的東西都是一個表達式并返回一個值。這對函數也適用，最后的表達式是自動返回的。因為我們創建了一個新的`Philosopher`作為這個函數最后的表達式，我們最終返回了它。 這個名字，`new()`，在Rust中并沒有什么特殊性。不過它是創建一個結構體新實例的函數的傳統名稱。在我們討論為什么之前，讓我們再看看`main()`： ~~~ fn main() { let p1 = Philosopher::new("Baruch Spinoza"); let p2 = Philosopher::new("Gilles Deleuze"); let p3 = Philosopher::new("Karl Marx"); let p4 = Philosopher::new("Friedrich Nietzsche"); let p5 = Philosopher::new("Michel Foucault"); } ~~~ 這里，我們創建了5個新哲學家的變量綁定。這是我最崇拜的5個，不過你可以替換為任何你想要的。如果我們_沒有_定義`new()`函數，它將看起來像這樣： ~~~ fn main() { let p1 = Philosopher { name: "Baruch Spinoza".to_string() }; let p2 = Philosopher { name: "Gilles Deleuze".to_string() }; let p3 = Philosopher { name: "Karl Marx".to_string() }; let p4 = Philosopher { name: "Friedrich Nietzche".to_string() }; let p5 = Philosopher { name: "Michel Foucault".to_string() }; } ~~~ 這看起來更亂。使用`new`還有別的優點，不過即便在這個簡單的例子，它也被證明是易于使用的。 現在我們在這了解到了基礎，這里有多種辦法可以讓我們可以處理更廣泛的問題。首先我想從結尾開始：讓我們準備讓每個哲學家能吃完的方法。作為一個小步驟，讓我們寫一個方法，并接著循環遍歷所有的哲學家，調用這個方法： ~~~ struct Philosopher { name: String, } impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } fn eat(&self) { println!("{} is done eating.", self.name); } } fn main() { let philosophers = vec![ Philosopher::new("Baruch Spinoza"), Philosopher::new("Gilles Deleuze"), Philosopher::new("Karl Marx"), Philosopher::new("Friedrich Nietzsche"), Philosopher::new("Michel Foucault"), ]; for p in &philosophers { p.eat(); } } ~~~ 讓我們先看看`main()`。與其為我們的哲學家寫5個獨立的變量綁定，相反我們為它們創建了一個`Vec`。`Vec`也叫做一個“vector”，它是一個可增長的數組類型。接著我們用[`for`](http://doc.rust-lang.org/nightly/book/for-loops.html)循環遍歷vector，順序獲取每個哲學家的引用。 在循環體中，我們調用`p.eat()`，它定義在上面： ~~~ fn eat(&self) { println!("{} is done eating.", self.name); } ~~~ 在Rust中，方法顯式獲取一個`self`參數。這就是為什么`eat()`是一個方法，而`new`是一個關聯函數：`new()`沒有用到`self`。在我們第一個版本的`eat()`，我們僅僅打印出哲學家的名字，并提到他們吃完了。運行這個程序應該會給你如下的輸出： ~~~ Baruch Spinoza is done eating. Gilles Deleuze is done eating. Karl Marx is done eating. Friedrich Nietzsche is done eating. Michel Foucault is done eating. ~~~ 十分簡單的，他們都吃完了！然而我們還沒有實際上實現真正的問題，所以我們還沒完！ 下一步，我們想要讓我們的哲學家不光說吃完了，而是實際上的吃（意大利面）。這是下一個版本： ~~~ use std::thread; struct Philosopher { name: String, } impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } fn eat(&self) { println!("{} is eating.", self.name); thread::sleep_ms(1000); println!("{} is done eating.", self.name); } } fn main() { let philosophers = vec![ Philosopher::new("Baruch Spinoza"), Philosopher::new("Gilles Deleuze"), Philosopher::new("Karl Marx"), Philosopher::new("Friedrich Nietzsche"), Philosopher::new("Michel Foucault"), ]; for p in &philosophers { p.eat(); } } ~~~ 只有一些變化，讓我們拆開來看。 ~~~ use std::thread; ~~~ `use`將名稱引入作用域。我們將開始使用標準庫的`thread`模塊，所以我們需要`use`它。 ~~~ fn eat(&self) { println!("{} is eating.", self.name); thread::sleep_ms(1000); println!("{} is done eating.", self.name); } ~~~ 現在我們打印出兩個信息，有一個`sleep_ms()`在中間。這會模擬哲學家吃面的時間。 如果你運行這個程序，你應該會看到每個哲學家依次進餐： ~~~ Baruch Spinoza is eating. Baruch Spinoza is done eating. Gilles Deleuze is eating. Gilles Deleuze is done eating. Karl Marx is eating. Karl Marx is done eating. Friedrich Nietzsche is eating. Friedrich Nietzsche is done eating. Michel Foucault is eating. Michel Foucault is done eating. ~~~ 好極了！我們做到了。這僅有一個問題：我們實際上沒有進行并發處理，而這才是我們問題的核心！ 為了讓哲學家并發的進餐。我們需要做一個小的修改。這是下一次迭代： ~~~ use std::thread; struct Philosopher { name: String, } impl Philosopher { fn new(name: &str) -> Philosopher { Philosopher { name: name.to_string(), } } fn eat(&self) { println!("{} is eating.", self.name); thread::sleep_ms(1000); println!("{} is done eating.", self.name); } } fn main() { let philosophers = vec![ Philosopher::new("Baruch Spinoza"), Philosopher::new("Gilles Deleuze"), Philosopher::new("Karl Marx"), Philosopher::new("Friedrich Nietzsche"), Philosopher::new("Michel Foucault"), ]; let handles: Vec<_> = philosophers.into_iter().map(|p| { thread::spawn(move || { p.eat(); }) }).collect(); for h in handles { h.join().unwrap(); } } ~~~ 所有我們做的是改變了`main()`中的循環，并增加了第二個循環！這里是第一個變化： ~~~ let handles: Vec<_> = philosophers.into_iter().map(|p| { thread::spawn(move || { p.eat(); }) }).collect(); ~~~ 雖然這只有5行，它們有4行密集的代碼。讓我們分開看。 ~~~ let handles: Vec<_> = ~~~ 我們引入了一個新的綁定，叫做`handles`。我們用這個名字因為我們將創建一些新的線程，并且它們會返回一些這些線程句柄來讓我們控制它們的行為。然而這里我們需要顯式注明類型，因為一個我們之后會介紹的問題。`_`是一個類型占位符。我們是在說“`handles`是一些東西的vector，不過Rust你自己應該能發現這些東西是什么"。 ~~~ philosophers.into_iter().map(|p| { ~~~ 我們獲取了哲學家列表并在其上調用`into_iter()`。它創建了一個迭代器來獲取每個哲學家的所有權。我們需要這樣做來把它們傳遞給我們的線程。我們取得這個迭代器并在其上調用`map`，他會獲取一個閉包作為參數并按順序在每個元素上調用這個閉包。 ~~~ thread::spawn(move || { p.eat(); }) ~~~ 這就是并發發生的地方。`thread::spawn`獲取一個閉包作為參數并在一個新線程執行這個閉包。這個閉包需要一個額外的標記，`move`，來表明這個閉包將會獲取它獲取的值的所有權。主要指`map`函數的`p`變量。 在線程中，所有我們做的就是在`p`上調用`eat()`。 ~~~ }).collect(); ~~~ 最后，我們獲取所有這些`map`調用的結果并把它們收集起來。`collect()`將會把它們放入一個某種類型的集合，這也就是為什么我們要表明返回值的類型：我們需要一個`Vec`。這些元素是`thread::spawn`調用的返回值，它們就是這些線程的句柄。噢！ ~~~ for h in handles { h.join().unwrap(); } ~~~ 在`main()`的結尾，我們遍歷這些句柄并在其上調用`join()`，它會阻塞執行直到線程完成執行。這保證了在程序結束之前這些線程都完成了它們的工作。 如果你運行這個程序，你將會看到哲學家們無序的進餐！我們有了多線程！ ~~~ Gilles Deleuze is eating. Gilles Deleuze is done eating. Friedrich Nietzsche is eating. Friedrich Nietzsche is done eating. Michel Foucault is eating. Baruch Spinoza is eating. Baruch Spinoza is done eating. Karl Marx is eating. Karl Marx is done eating. Michel Foucault is done eating. ~~~ 不過叉子怎么辦呢？我們還沒有模型化它們呢。 為此，讓我們創建一個新的`struct`： ~~~ use std::sync::Mutex; struct Table { forks: Vec<Mutex<()>>, } ~~~ 這個`Table`有一個`Mutex`的vector，一個互斥鎖是一個控制并發的方法：一次只有一個線程能訪問它的內容。這正是我們需要叉子擁有的屬性。我們用了一個空元組，`()`，在互斥鎖的內部，因為我們實際上并不準備使用這個值，只是要持有它。 讓我們修改程序來使用`Table`： ~~~ use std::thread; use std::sync::{Mutex, Arc}; 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 eat(&self, table: &Table) { let _left = table.forks[self.left].lock().unwrap(); let _right = table.forks[self.right].lock().unwrap(); println!("{} is eating.", self.name); thread::sleep_ms(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("Baruch Spinoza", 0, 1), Philosopher::new("Gilles Deleuze", 1, 2), Philosopher::new("Karl Marx", 2, 3), Philosopher::new("Friedrich Nietzsche", 3, 4), Philosopher::new("Michel Foucault", 0, 4), ]; let handles: Vec<_> = philosophers.into_iter().map(|p| { let table = table.clone(); thread::spawn(move || { p.eat(&table); }) }).collect(); for h in handles { h.join().unwrap(); } } ~~~ 大量的修改！然而，通過這次迭代，我們有了一個可以工作的程序。讓我摸看看細節： ~~~ use std::sync::{Mutex, Arc}; ~~~ 我們將用到`std::sync`包中的另一個結構：`Arc`。我們在用到時再詳細解釋。 ~~~ struct Philosopher { name: String, left: usize, right: usize, } ~~~ 我們需要在我們的`Philosopher`中增加更多的字段。每個哲學家將擁有兩把叉子：一個拿左手，一個拿右手。我們將用`usize`來表示它們，因為它是你的vector的索引的類型。這兩個值將會是我們`Table`中的`forks`的索引。 ~~~ fn new(name: &str, left: usize, right: usize) -> Philosopher { Philosopher { name: name.to_string(), left: left, right: right, } } ~~~ 現在我們需要構造這些`left`和`right`的值，所以我們把它們加到`new()`里。 ~~~ fn eat(&self, table: &Table) { let _left = table.forks[self.left].lock().unwrap(); let _right = table.forks[self.right].lock().unwrap(); println!("{} is eating.", self.name); thread::sleep_ms(1000); println!("{} is done eating.", self.name); } ~~~ 我們有兩個新行。我們也增加了一個參數，`table`。我們訪問`Table`的叉子列表，接著使用`self.left`和`self.right`來訪問特定索引位置的叉子。這讓我們訪問索引位置的`Mutex`，并且我們在其上調用`lock()`。如果互斥鎖目前正在被別人訪問，我們將阻塞直到它可用為止。 `lock()`可能會失敗，而且如果它失敗了，我們想要程序崩潰。在這個例子中，互斥鎖可能發生的錯誤是[“中毒了（poisoned）”](http://doc.rust-lang.org/nightly/std/sync/struct.Mutex.html#poisoning)，它發生于當線程在持有鎖的同時線程恐慌了。因為這不應該發生，所以我們僅僅是使用`unwrap()`。 這些代碼還有另一個奇怪的事情：我們命名結果為`_left`和`_right`。為啥要用下劃線？好吧，我們并不打算在鎖中“使用”這些值。我們僅僅想要獲取它。為此，Rust會警告我們從未使用這些值。通過使用下劃線，我們告訴Rust這是我們意圖做的，這樣它就不會產生一個警告。 那怎么釋放鎖呢？好吧，這會在`_left`和`_right`離開作用域時發生，自動的。 ~~~ let table = Arc::new(Table { forks: vec![ Mutex::new(()), Mutex::new(()), Mutex::new(()), Mutex::new(()), Mutex::new(()), ]}); ~~~ 接下來，在`main()`中，我們創建了一個新`Table`并封裝在一個`Arc`中。“arc”代表“原子引用計數”，并且我們需要在多個線程間共享我們的`Table`。因為我們共享了它，引用計數會增長，而當每個線程結束，它會減少。 ~~~ let philosophers = vec![ Philosopher::new("Baruch Spinoza", 0, 1), Philosopher::new("Gilles Deleuze", 1, 2), Philosopher::new("Karl Marx", 2, 3), Philosopher::new("Friedrich Nietzsche", 3, 4), Philosopher::new("Michel Foucault", 0, 4), ]; ~~~ 我們需要傳遞我們的`left`和`right`的值給我們的`Philosopher`們的構造函數。不過這里有另一個細節，并且是“非常”重要。如果你觀察它的模式，它們從頭到尾全是連續的。米歇爾·福柯應該使用`4`，`0`作為參數，不過我們用了`0`，`4`。這事實上是為了避免死鎖：我們的哲學家中有一個左撇子！這是解決這個問題的一個方法，并且在我看來，是最簡單的方法。 ~~~ let handles: Vec<_> = philosophers.into_iter().map(|p| { let table = table.clone(); thread::spawn(move || { p.eat(&table); }) }).collect(); ~~~ 最后，在我們的`map()`/`collect()`循環中，我們調用了`table.clone()`。`Arc`的`clone()`方法用來增加引用計數，而當它離開作用域，它減少計數。你會注意到這里我們可以引入一個新的`table`的綁定，而且它應該覆蓋舊的一個。這經常用在你不想整出兩個不同的名字的時候。 通過這些，我們的程序能工作了！任何同一時刻只有兩名哲學家能進餐，因此你會得到像這樣的輸出： ~~~ Gilles Deleuze is eating. Friedrich Nietzsche is eating. Friedrich Nietzsche is done eating. Gilles Deleuze is done eating. Baruch Spinoza is eating. Karl Marx is eating. Baruch Spinoza is done eating. Michel Foucault is eating. Karl Marx is done eating. Michel Foucault is done eating. ~~~ 恭喜！你用Rust實現了一個經典的并發問題。