哲學(xué)家就餐問題

哲學(xué)家就餐問題

對于我們的第二個(gè)項(xiàng)目，讓我們來看一個(gè)典型的并發(fā)性問題。這就是“哲學(xué)家就餐問題”。這最初是由迪杰斯特拉在 1965 年提出的，但我們將要使用的版本出自托尼?霍爾在 1985 年發(fā)表的一篇論文。

在古代，一個(gè)富有的慈善家捐贈了一所學(xué)院來安排五個(gè)著名的哲學(xué)家。每個(gè)哲學(xué)家都有一個(gè)房間，他可以在其中從事他自己專業(yè)的思考活動；學(xué)校里有一個(gè)公共的餐廳，這里配備有一個(gè)圓形的桌子，桌子周邊有五個(gè)椅子，每個(gè)椅子用坐在上面的哲學(xué)家的名字來標(biāo)記。他們以逆時(shí)針的方向來圍著桌子坐。每個(gè)哲學(xué)家的左側(cè)放了一個(gè)金叉，桌子中間有一大碗不斷添滿的意大利面。哲學(xué)家將花費(fèi)大部分時(shí)間去思考；但是當(dāng)他餓了，他就會去餐廳，坐在自己的椅子上，拿起在自己左邊的叉子來吃意大利面。但是意大利面條比較難吃到，需要第二個(gè)叉子才能把面條送到嘴里。因此，哲學(xué)家也要拿起他右邊的叉子。當(dāng)哲學(xué)家吃完面條后，他會把兩個(gè)叉子都放下，離開自己的椅子，并繼續(xù)思考。當(dāng)然了，一個(gè)叉子一次只能有一個(gè)哲學(xué)家來使用。如果其他哲學(xué)家想要使用你的叉子，那么他僅僅需要等到這個(gè)叉子沒人用了即可。

這個(gè)經(jīng)典問題展示了一些不同的并發(fā)性的元素。原因在于，其實(shí)際實(shí)現(xiàn)起來比較復(fù)雜：一個(gè)簡單的實(shí)現(xiàn)可能導(dǎo)致死鎖。舉一個(gè)例子，讓我們先想一個(gè)簡單的算法來解決這個(gè)問題：

1. 一個(gè)哲學(xué)家拿起了自己左邊的叉子。
2. 然后他又拿起了他右邊的叉子。
3. 吃意大利面。
4. 放下叉子。

現(xiàn)在，讓我們來想象一下這一系列的事件：

1. 哲學(xué)家 1 開始此算法，拿起他左邊的叉子。
2. 哲學(xué)家 2 開始此算法，拿起他左邊的叉子。
3. 哲學(xué)家 3 開始此算法，拿起他左邊的叉子。
4. 哲學(xué)家 4 開始此算法，拿起他左邊的叉子。
5. 哲學(xué)家 5 開始此算法，拿起他左邊的叉子。
6. …？所有的餐叉都被拿起來了，沒人能吃面了!

有不同的方法來解決這個(gè)問題。在本教程中我們將用我們的方法來解決它?，F(xiàn)在，讓我們開始從問題的本身開始建模。我們先從哲學(xué)家身上開始：

    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");
    }

在這里，我們創(chuàng)建了一個(gè)結(jié)構(gòu)體來代表一個(gè)哲學(xué)家。在結(jié)構(gòu)體里，我們現(xiàn)在所需要的僅僅是一個(gè)名字。我們將名字的類型選擇成 String 型，而不是 &str。一般來說，使用一種自身擁有數(shù)據(jù)的類型比使用一個(gè)利用引用的類型容易的多。

我們繼續(xù)看下面的部分：

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

這里的 impl 塊能讓我們?yōu)?Philosopher 結(jié)構(gòu)體定義一些內(nèi)容。在本例中，我們定義了一個(gè)名叫 new 的關(guān)聯(lián)函數(shù)。它的第一行如下所示：

    fn new(name: &str) -> Philosopher {

這里我們需要輸入一個(gè)參數(shù) name，類型是 &str。這是另一個(gè)字符串的一個(gè)引用。此函數(shù)會返回一個(gè) Philosopher 結(jié)構(gòu)體的實(shí)例。

    Philosopher {
        name: name.to_string(),
    }

這將會創(chuàng)建一個(gè)新的 Philosopher，并將它的 name 值設(shè)置成前面 name 的參數(shù)值。但這不是參數(shù)的自身，因?yàn)槲覀儗ζ湔{(diào)用了 .to_string()。這將創(chuàng)建一個(gè) &str 所指向字符串的副本，此副本的類型是 Philosopher 的 name 字段的 String 類型。

那么為什么不直接用 String 類型的參數(shù)？這樣更容易調(diào)用。如果我們采用了 String 類型參數(shù)，但是我們的調(diào)用者所有的是 &str，那么他們必須自己調(diào)用這個(gè) .to_string() 的方法。這種靈活性的缺點(diǎn)是，它總是產(chǎn)生一個(gè)副本。對于這個(gè)小程序，這并不是特別重要，因?yàn)槲覀冎?，我們僅僅使用的是短字符串。

最后一件你可能會注意到的事：我們只定義了一個(gè) Philosopher，似乎用它什么事情也沒有做。Rust 是一種基于表達(dá)式的語言，這意味著 Rust 中幾乎所有的內(nèi)容都是返回一個(gè)值的表達(dá)式。這個(gè)說法對函數(shù)亦是如此，因?yàn)楹瘮?shù)的最后一個(gè)表達(dá)式將自動返回。由于這個(gè)函數(shù)的最后一個(gè)表達(dá)式是我們創(chuàng)建了一個(gè)新的 Philosopher，我們最終返回這個(gè) Philosopher。

對于 Rust，這個(gè)名字，new()，沒有什么特別，但是它是創(chuàng)建新的結(jié)構(gòu)體實(shí)例的函數(shù)的約定俗成的叫法。在我們討論為什么是這樣之前，讓我們先再看看 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");
    }

在這里，我們創(chuàng)建了五個(gè) Philosopher 的變量綁定。這五個(gè)名字都是我最喜歡的，你也可以用任何你想要的名字來替換他們。如果我們沒有定義 new() 函數(shù)，它會看起來會是這樣的：

    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() };
    }

這看起來就比較麻煩了。當(dāng)然使用 new 也有其他的一些優(yōu)勢，而在我這個(gè)簡單的例子中，使用它也使我們的代碼簡潔了不少。

現(xiàn)在我們在這里已經(jīng)寫好了基本的內(nèi)容，同時(shí)會有很多方法可以解決上述問題。我想從問題的結(jié)束端先開始：讓我們建立一個(gè)每個(gè)哲學(xué)家吃完的方案。這是很小的一步，我們先創(chuàng)建一個(gè)方法，然后遍歷所有的哲學(xué)家，如下所示：

    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()。我們沒有采用有五個(gè)哲學(xué)家 Philosopher 的變量綁定，相反我們創(chuàng)建了一個(gè)哲學(xué)家的 Vec<T>。 Vec<T> 也被稱為“向量”，這是一個(gè)可增長的數(shù)組類型。然后，我們使用一個(gè) for 循環(huán)迭代向量體，也就是會輪流的獲取到每個(gè)哲學(xué)家的引用。

在循環(huán)體內(nèi)，我們調(diào)用的是 p.eat()，下面是關(guān)于其函數(shù)定義：

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

在 Rust 中，方法可以用一個(gè)明確的 self 參數(shù)。這就是為什么 eat() 是一個(gè)方法，而 new 是一個(gè)關(guān)聯(lián)函數(shù)： new() 中沒有 self。我們 eat() 的第一個(gè)版本，只打印出哲學(xué)家的名字，并且提及他們正在吃。現(xiàn)在運(yùn)行這個(gè)程序，你可以得到以下的輸出：

    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.

夠簡單吧，程序運(yùn)行完全沒有問題!然而我們還沒有實(shí)現(xiàn)真正的問題，所以我們還沒有完成整個(gè)程序!

接下來，我們想想做的是：我們的哲學(xué)家不僅吃完，而且實(shí)際上他們也是在吃的。下面是程序的下一個(gè)版本：

    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();
        }
    }

僅有幾個(gè)變化。讓我們一個(gè)一個(gè)的來講。

    use std::thread;

use 可以使后面的庫加載在作用域內(nèi)。我們稍后會使用標(biāo)準(zhǔn)庫中的 thread 模塊，所以我們需要 use 它。

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

        thread::sleep_ms(1000);

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

我們現(xiàn)在打印了兩個(gè)消息，其中間有一個(gè) sleep_ms() 將其分隔開。sleep_ms() 將模擬哲學(xué)家吃的時(shí)間。

如果現(xiàn)在你運(yùn)行這個(gè)程序，你會看到每個(gè)哲學(xué)家輪流吃：

    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.

太好了!我們又前進(jìn)了一步。這里還有一個(gè)問題：我們實(shí)際上并沒有以并行的方式操作，并行才是就餐問題的核心部分!

為了能讓我們的哲學(xué)家并發(fā)的吃，我們需要做一個(gè)小改變。下面是下一個(gè)版本：

    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() 里面的循環(huán)，在其中添加上第二個(gè)循環(huán)體!下面是第一個(gè)改變：

    let handles: Vec<_> = philosophers.into_iter().map(|p| {
        thread::spawn(move || {
            p.eat();
        })
    }).collect();

雖然這里只有五行，但這五行代碼確很密集。讓我們一個(gè)一個(gè)的來講。

    let handles: Vec<_> =

我們這里引入了一個(gè)名叫 handles 新的綁定。我們這樣叫它，是因?yàn)槲覀円獎?chuàng)建一些新的線程，而這些線程會返回一些能讓我們控制此些線程操作的 handles。由于一個(gè)我們過后要講到的問題，這里我們要明確解釋這個(gè)類型。_ 是一個(gè)類型的占位符。我們說“handles 是一個(gè)某項(xiàng)的向量，在Rust 中，你可以找出到這項(xiàng)到底是什么?！?/p>

    philosophers.into_iter().map(|p| {

我們的哲學(xué)家 philosophers 調(diào)用了 into_iter()。這將創(chuàng)建一個(gè)迭代器，它將擁有每個(gè)哲學(xué)家的所有權(quán)。我們要這樣才能將哲學(xué)家傳遞到線程中。我們用迭代器調(diào)用 map，它以一個(gè)閉包作為參數(shù)，并且依次調(diào)用閉包中的每個(gè)元素。

    thread::spawn(move || {
        p.eat();
    })

這里就是發(fā)生并發(fā)的地方。thread::spawn 函數(shù)以一個(gè)閉包作為參數(shù)，并會在一個(gè)新線程里執(zhí)行這個(gè)閉包。關(guān)于這個(gè)閉包的一些額外的解釋， move，表明閉包要獲取它的捕獲值的所有權(quán)。主體函數(shù)上，p 是 map 函數(shù)的變量。

在線程內(nèi)部，我們所做的就是用 p 調(diào)用 eat()。

    }).collect();

最后，我們獲取了所有的 map 調(diào)用的結(jié)果并把它們收集起來。collect() 會將它們生成某種集合，這就是為什么我們要解釋返回類型的原因：因?yàn)槲覀兿胍粋€(gè) Vec<T>。集合的元素就是 thread::spawn 調(diào)用的返回值，也就是這些線程的 handles。

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

main() 函數(shù)的結(jié)尾部分，我們對 handles 進(jìn)行循環(huán)處理，對其調(diào)用 join()，這可以阻塞其它線程的執(zhí)行，直到本線程執(zhí)行完成。這確保了線程在程序?qū)⑵渫顺銮皶瓿伤鼈兊墓ぷ鳌?/p>

如果你運(yùn)行這個(gè)程序，你會發(fā)現(xiàn)哲學(xué)家可以自由的吃啦!到這兒，我們已經(jīng)有多線程程序啦!

    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.

但是叉子呢？我們還沒有為它們建模。

要做到這一點(diǎn)，讓我們寫一個(gè)新的 struct：

    use std::sync::Mutex;

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

這桌子 Table 有一個(gè)互斥元(Mutex)的向量。互斥元是控制并發(fā)性的一種方法：一次只能有一個(gè)線程可以訪問內(nèi)容。這正是我們叉子所需要的屬性。在互斥元中我們用了一個(gè)空的元組，()，因?yàn)槲覀儾⒉淮蛩闶褂闷渲械闹担瑑H僅獲取到它就可以。

讓我們使用 Table 來修改這個(gè)程序：

    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();
        }
    }

又有了許多的變化!這一次我們有了最終可運(yùn)行的版本。我們看下細(xì)節(jié)內(nèi)容：

    use std::sync::{Mutex, Arc};

我們將使用 std::sync 包中的另一個(gè)結(jié)構(gòu)：Arc<T>。當(dāng)我們使用它時(shí)，會做進(jìn)一步的講解。

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

我們需要為 Philosopher 添加兩個(gè)字段。每個(gè)哲學(xué)家都有兩個(gè)叉子：一個(gè)在左，一個(gè)在右。我們用 usize 類型來表示它們，因?yàn)檫@類型是索引向量。這兩個(gè)值將被索引到我們 Table 中的 forks 了。

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

我們現(xiàn)在需要構(gòu)造 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);
    }

我們又添加了兩行新代碼。我們還添加了一個(gè)參數(shù)，table。這樣我們就可以訪問 Table 的 fork 列表，然后可以用 self.left 和 self.right 訪問特定索引上的 fork。讓我們可以訪問那個(gè)索引上的互斥元 Mutex，并且用其調(diào)用 lock()。如果互斥元目前正在被別人訪問，那么我們的線程將被阻塞，直到互斥元變得可用。

lock() 的調(diào)用可能會失敗，如果是這樣，程序會崩潰。在這種情況下，錯(cuò)誤的發(fā)生可能是因?yàn)榛コ庠?a rel="nofollow" rel="external nofollow" target="_blank" target="_blank">中毒”了，這是由于當(dāng)鎖已經(jīng)被持有時(shí)會引起線程應(yīng)急。因?yàn)檫@樣的錯(cuò)誤不該發(fā)生，所以我們使用 unwrap() 來解決它。

這些行另一個(gè)奇怪的現(xiàn)象是：我們將結(jié)果命名為 _left 和 _right。這些下劃線有什么用？嗯，因?yàn)槲覀儾淮蛩闶褂面i內(nèi)的值。我們只是想持有鎖。因此，Rust 會警告我們，我們從來沒有使用過鎖內(nèi)值。通過使用下劃線，我們就會告訴 Rust，這就是我們想要的，這樣的話 Rust 就不會拋出警告。

那么如何釋放鎖呢？嗯，當(dāng) _left 和 _right 超出作用域后，鎖會自動釋放。

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

接下來，在 main() 中，我們創(chuàng)建了一個(gè)新的 Table 并定義成 Arc<T> 類型?！癮rc” 是 “atomic reference count” 的縮寫，我們要通過多線程來共享我們的 Table。當(dāng)我們要共享它時(shí)，引用數(shù)就會上升，當(dāng)每個(gè)線程結(jié)束時(shí)，引用數(shù)就會減少。

    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 的構(gòu)造函數(shù)中。這里有一個(gè)非常重要的細(xì)節(jié)。如果你查看他們的樣式，開始直到最后都是一致的。Monsieur Foucault 本應(yīng)該用 4，0 作為參數(shù)，但相反的，用 0，4 作了參數(shù)。這是其實(shí)是防止死鎖：我們的一個(gè)哲學(xué)家是左撇子!這是解決問題的一種方法，在我看來，這是最簡單的。

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

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

最后，在 map()/collect() 循環(huán)中，我們調(diào)用了 table.clone()。Arc<T> 調(diào)用的 clone() 方法會增加引用的計(jì)數(shù)，但是當(dāng)它超出作用域之后，引用的計(jì)數(shù)會相應(yīng)的減少。你會注意到，我們可以在這里引入一個(gè)新的 table 的綁定，它將覆蓋舊的那一個(gè)。這個(gè)方法經(jīng)常使用。這樣可以使你不需要命名兩個(gè)唯一的名字。

到這里，我們的程序就可以工作啦!只有兩個(gè)哲學(xué)家可以在同一時(shí)間吃，所以你會得到一些如下的輸出：

    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.

恭喜你!你已經(jīng)用 Rust 實(shí)現(xiàn)了一個(gè)典型的并發(fā)性問題。