這是以前寫(xiě)的一篇文章记盒，今天發(fā)布出來(lái)
該問(wèn)題涉及多線(xiàn)程的內(nèi)容，可以看我的這篇文章 POSIX多線(xiàn)程初步
GitHub 地址：https://github.com/doooooit/Dining-philosophers-problem

問(wèn)題描述

哲學(xué)家就餐問(wèn)題（Dining philosophers problem）是有關(guān)死鎖的一個(gè)經(jīng)典問(wèn)題攒巍，是計(jì)算機(jī)系統(tǒng)解決死鎖問(wèn)題的一個(gè)抽象簡(jiǎn)化表達(dá)。它可以這樣表述荒勇，假設(shè)有五位哲學(xué)家圍坐在一張圓形餐桌旁窑业，做以下兩件事情之一：吃飯，或者思考枕屉。吃東西的時(shí)候常柄，他們就停止思考，思考的時(shí)候也停止吃東西搀擂。餐桌上每?jī)晌徽軐W(xué)家之間有一只餐叉西潘，哲學(xué)家吃東西必須且只能使用左右手兩邊的兩只餐叉。

之所以被稱(chēng)為一個(gè)“問(wèn)題”哨颂，是因?yàn)檫@個(gè)系統(tǒng)可能會(huì)出現(xiàn)無(wú)法進(jìn)行下去的情況喷市。

第一種情況，假設(shè)某一時(shí)刻威恼，所有的哲學(xué)家都想要吃東西品姓，他們同時(shí)拿起了各自左手邊的餐叉，然后當(dāng)他們想要拿起右手邊的餐叉時(shí)箫措，發(fā)現(xiàn)已經(jīng)被右邊的哲學(xué)家拿起來(lái)了腹备，如果每一個(gè)哲學(xué)家都不同意放棄自己已經(jīng)拿到手的餐叉，則整個(gè)系統(tǒng)就無(wú)法運(yùn)行下去了斤蔓，出現(xiàn)了被稱(chēng)為“死鎖”的狀態(tài)植酥。

另一種情況，哲學(xué)家覺(jué)得不能這么自私，如果自己已經(jīng)拿起了一個(gè)餐叉友驮，而遲遲無(wú)法獲得另一個(gè)餐叉時(shí)漂羊，則他在等待一段時(shí)間后會(huì)放下自己已經(jīng)拿起的餐叉。當(dāng)所有哲學(xué)家都這樣想卸留，他們同時(shí)拿起左手邊的餐叉走越，等待相同的時(shí)間，又同時(shí)放下餐叉耻瑟，然后拿起旨指、放下、拿起匆赃、放下如此循環(huán)淤毛，出現(xiàn)被成為“活鎖”的狀態(tài)今缚。

這個(gè)問(wèn)題模型最初是著名的計(jì)算機(jī)科學(xué)家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）在1971年提出的一個(gè)同步問(wèn)題算柳，他假設(shè)有五臺(tái)計(jì)算機(jī)都試圖訪(fǎng)問(wèn)五份共享的磁帶驅(qū)動(dòng)器。后來(lái)姓言，這個(gè)問(wèn)題被托尼·霍爾（Charles Antony Richard Hoare）重新表述為哲學(xué)家就餐問(wèn)題瞬项。這個(gè)問(wèn)題可以用來(lái)解釋死鎖和資源耗盡。

哲學(xué)家就餐問(wèn)題就是要采用適當(dāng)?shù)乃惴ūＷC系統(tǒng)不會(huì)出現(xiàn)死/活鎖何荚。

解決算法

一共有三種解法囱淋，分別是 服務(wù)生解法，資源分級(jí)解法 和 Chandy/Misra解法

服務(wù)生算法

一個(gè)簡(jiǎn)單的解法是引入一個(gè)餐廳服務(wù)生餐塘，哲學(xué)家要想得到餐叉妥衣，必須先叫服務(wù)生送給他，服務(wù)生按先來(lái)后到的順序服務(wù)完一位哲學(xué)家后才能服務(wù)下一為哲學(xué)家戒傻。這時(shí)税手，如果正在被服務(wù)生服務(wù)的哲學(xué)家兩邊的餐叉都沒(méi)有被占用的話(huà)，這位哲學(xué)家就一定會(huì)得到這兩個(gè)餐叉需纳，而不會(huì)被別的哲學(xué)家搶走芦倒，從而避免死鎖。

這種解法的特點(diǎn)是簡(jiǎn)單但并發(fā)度很低不翩。舉個(gè)例子兵扬，假設(shè)現(xiàn)在2號(hào)哲學(xué)家已經(jīng)在就餐了，他占用了2號(hào)和3號(hào)餐叉口蝠，這時(shí)1號(hào)哲學(xué)家叫了服務(wù)生器钟，服務(wù)生給了1號(hào)哲學(xué)家1號(hào)餐叉，隨后發(fā)現(xiàn)2號(hào)餐叉正在被占用妙蔗，則服務(wù)生必須等待2號(hào)哲學(xué)家就餐結(jié)束才能把2號(hào)餐叉給1號(hào)哲學(xué)家俱箱。因?yàn)榉?wù)生對(duì)1號(hào)哲學(xué)家的服務(wù)還沒(méi)有結(jié)束，所以這時(shí)有其他哲學(xué)家申請(qǐng)服務(wù)的時(shí)候服務(wù)生無(wú)法響應(yīng)灭必，造成整個(gè)系統(tǒng)都阻塞狞谱，知道2號(hào)哲學(xué)家就餐結(jié)束乃摹。

python 風(fēng)格偽代碼：

thread_philosophers():
    lock(mutex_waiter)    #如果請(qǐng)求失敗將在這里阻塞
    wait(sem_firstFork)
    wait(sem_secondFork)
    unlock(mutex_waiter)

    eating()

    post(second-fork)
    post(first-fork)

    thread_exit()

資源分級(jí)算法

另一個(gè)簡(jiǎn)單的解法是為資源分配一個(gè)偏序或者分級(jí)的關(guān)系，并約定所有資源都按照這種順序獲取跟衅，按相反順序釋放孵睬。對(duì)應(yīng)在哲學(xué)家就餐問(wèn)題中就是為各個(gè)餐叉設(shè)置 1 - 2 - 3 - 4 - 5 的序號(hào)，每一個(gè)哲學(xué)家總是先拿起左右兩邊編號(hào)較低的餐叉伶跷，再拿編號(hào)較高的掰读。用完餐叉后，他總是先放下編號(hào)較高的餐叉叭莫，再放下編號(hào)較低的蹈集。在這種情況下，1_{4號(hào)哲學(xué)家都是左邊的餐叉序號(hào)小雇初，而5號(hào)哲學(xué)家是右邊的餐叉序號(hào)小拢肆，當(dāng)1}4號(hào)哲學(xué)家同時(shí)拿起他們手邊編號(hào)較低的餐叉即1～4號(hào)餐叉時(shí)，只有編號(hào)最高的5號(hào)餐叉留在桌上靖诗，5號(hào)哲學(xué)家先申請(qǐng)序號(hào)較小的1號(hào)郭怪，發(fā)現(xiàn)已經(jīng)被拿走，所以他就只能等待刊橘。而剩下的那支5號(hào)餐叉被4號(hào)哲學(xué)家成功獲得鄙才。當(dāng)4號(hào)哲學(xué)家吃完后，他會(huì)先放下編號(hào)最高的餐叉促绵，再放下編號(hào)較低的餐叉攒庵，從而使得3號(hào)哲學(xué)家成功獲得他所需的第二支餐叉，以此類(lèi)推败晴，整個(gè)系統(tǒng)不會(huì)發(fā)生死鎖浓冒。

python 風(fēng)格偽代碼：

thread-philosophers(num_fork1, num_fork2):
    if num_fork1 < num_fork2:
        sem_firstFork = num_fork1
        sem_secondFork = num_fork2
    else:
        sem_firstFork = num_fork2
        sem_secondFork = num_fork1

    wait(sem_firstFork)
    wait(sem_secondFork)

    eating()

    post(sem_secondFork)
    post(sem_firstFork)

    thread-exit()

這種解法的特點(diǎn)是需要對(duì)資源進(jìn)行分級(jí)，相對(duì)較實(shí)用位衩。但同時(shí)在很多情況下裆蒸，我們是無(wú)法得知系統(tǒng)運(yùn)行所需要的資源有哪些，以及算法對(duì)于請(qǐng)求糖驴、釋放的順序的限制僚祷，使得某些情況下這種方法并不適用。

我的實(shí)現(xiàn)

我實(shí)現(xiàn)了 服務(wù)生算法 和 資源分級(jí)算法 贮缕，以及一個(gè)用于演示死鎖的錯(cuò)誤方法辙谜。詳細(xì)代碼請(qǐng)大家移步我的 GitHub： https://github.com/doooooit/Dining-philosophers-problem

版權(quán)聲明 自由轉(zhuǎn)載 - 保持署名 - 不可商用 - 不可演繹 （CC3.0 創(chuàng)意共享3.0許可證）