第4章進(jìn)程及進(jìn)程管理3

1、2021-11-2914.4 進(jìn)程之間的約束關(guān)系進(jìn)程之間的約束關(guān)系問(wèn)題的提出問(wèn)題的提出為了解決多道程序并發(fā)執(zhí)行時(shí)產(chǎn)生的與時(shí)間有關(guān)的錯(cuò)誤，協(xié)調(diào)并發(fā)進(jìn)程間的正常運(yùn)行，需先分析進(jìn)程間的各種可能的約束關(guān)系。4.4.1 進(jìn)程的競(jìng)爭(zhēng)與合作進(jìn)程的競(jìng)爭(zhēng)與合作進(jìn)程間相互制約關(guān)系分兩種：v1、競(jìng)爭(zhēng)系統(tǒng)資源：處理機(jī)的競(jìng)爭(zhēng)，內(nèi)存頁(yè)面的競(jìng)爭(zhēng)，進(jìn)程向系統(tǒng)申請(qǐng)，由系統(tǒng)統(tǒng)一分配。v2、進(jìn)程協(xié)作：進(jìn)程間通過(guò)同步機(jī)構(gòu)自行協(xié)調(diào)。信息共享，并行處理。2021-11-2934.4.2 進(jìn)程互斥的概念進(jìn)程互斥的概念兩個(gè)概念：臨界資源臨界資源與臨界區(qū)臨界區(qū)。1臨界資源臨界資源臨界資源臨界資源指的是一次只允許一個(gè)進(jìn)程使用的獨(dú)占資源。諸進(jìn)程對(duì)

2、它的訪問(wèn)必須互斥。（包括可能的系統(tǒng)資源及用戶(hù)資源）2 2臨界區(qū)臨界區(qū)臨界區(qū)臨界區(qū)是指包含了訪問(wèn)臨界資源的那段程序。臨界區(qū)作為特殊的程序段進(jìn)行如下處理：1）進(jìn)程在進(jìn)入臨界區(qū)之前必須先申請(qǐng)，2）當(dāng)且僅當(dāng)臨界區(qū)中涉及的臨界資源沒(méi)有其它進(jìn)程使用時(shí)才能進(jìn)入臨界區(qū)；3）在出臨界區(qū)后立即釋放臨界資源。2021-11-2944.4.2 進(jìn)程互斥的概念進(jìn)程互斥的概念互斥必要條件：互斥必要條件：諸進(jìn)程共享同一個(gè)臨界資源諸進(jìn)程共享同一個(gè)臨界資源；共享的方式是先來(lái)者先使用的異步方式共享的方式是先來(lái)者先使用的異步方式。只有同時(shí)滿(mǎn)足以上兩個(gè)必要條件的多進(jìn)程共享臨界資源的問(wèn)題，才是互斥問(wèn)題。操作系統(tǒng)提供的互斥機(jī)制必須滿(mǎn)足以

3、下要求：操作系統(tǒng)提供的互斥機(jī)制必須滿(mǎn)足以下要求：(臨界區(qū)問(wèn)題的解答必須滿(mǎn)足的要求臨界區(qū)問(wèn)題的解答必須滿(mǎn)足的要求)1實(shí)現(xiàn)互斥：即任意時(shí)刻最多只能有一個(gè)進(jìn)程進(jìn)入臨界區(qū)，執(zhí)行臨界區(qū)的進(jìn)程不能受到其它進(jìn)程的干擾。2有空讓進(jìn)：當(dāng)臨界資源空閑時(shí)，應(yīng)該允許申請(qǐng)進(jìn)入臨界區(qū)的進(jìn)程進(jìn)入臨界區(qū)。3有限等待：對(duì)要求進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)在有限時(shí)間內(nèi)進(jìn)入，以免陷入“死等“；進(jìn)入臨界區(qū)的進(jìn)程不能被無(wú)限期地延遲或死鎖2021-11-2954.4.3 進(jìn)程進(jìn)程同步的概念同步的概念同步問(wèn)題：同步問(wèn)題：當(dāng)各進(jìn)程的執(zhí)行具有一定先后順序的限制時(shí)，稱(chēng)為當(dāng)各進(jìn)程的執(zhí)行具有一定先后順序的限制時(shí)，稱(chēng)為同步問(wèn)題同步問(wèn)題。同步與互斥的比較：同步與

4、互斥的比較：是否一定共享臨界資是否一定共享臨界資源源運(yùn)行方式運(yùn)行方式互斥問(wèn)題互斥問(wèn)題一定一定異步：先來(lái)者先進(jìn)入，無(wú)先后異步：先來(lái)者先進(jìn)入，無(wú)先后順序，異步順序，異步同步問(wèn)題同步問(wèn)題不一定不一定同步：有先后順序同步：有先后順序同步互斥混合問(wèn)題同步互斥混合問(wèn)題一定一定進(jìn)入臨界區(qū)異步執(zhí)行、進(jìn)程間進(jìn)入臨界區(qū)異步執(zhí)行、進(jìn)程間同步同步2021-11-2964.4.3 進(jìn)程進(jìn)程同步的概念同步的概念u解決同步問(wèn)題的信號(hào)量為解決同步問(wèn)題的信號(hào)量為私有信號(hào)量私有信號(hào)量，局限于需要同步的協(xié)，局限于需要同步的協(xié)作進(jìn)程之間使用。作進(jìn)程之間使用。u協(xié)作進(jìn)程之間的關(guān)聯(lián)屬于協(xié)作進(jìn)程之間的關(guān)聯(lián)屬于直接關(guān)聯(lián)直接關(guān)聯(lián)。u互斥可以看

5、成是同步的一種特殊情況，互斥可以看成是同步的一種特殊情況，廣義上的同步廣義上的同步包含了包含了互斥在內(nèi)，我們將兩者統(tǒng)稱(chēng)為進(jìn)程的同步問(wèn)題。廣義上的同互斥在內(nèi)，我們將兩者統(tǒng)稱(chēng)為進(jìn)程的同步問(wèn)題。廣義上的同步可以定義為諸進(jìn)程之間步可以定義為諸進(jìn)程之間在執(zhí)行時(shí)間上所加的某種約束在執(zhí)行時(shí)間上所加的某種約束，如，如果這種約束是因?yàn)楣蚕砼R界資源，而且約束的方式是異步的果這種約束是因?yàn)楣蚕砼R界資源，而且約束的方式是異步的則為互斥約束；否則就是同步約束。則為互斥約束；否則就是同步約束。2021-11-2974.4.3 進(jìn)程進(jìn)程同步的概念同步的概念協(xié)作進(jìn)程之間一般有以下幾種不同的同步問(wèn)題：協(xié)作進(jìn)程之間一般有以下幾種

6、不同的同步問(wèn)題：前驅(qū)與后繼同步問(wèn)題前驅(qū)與后繼同步問(wèn)題單緩沖與多緩沖讀寫(xiě)同步問(wèn)題單緩沖與多緩沖讀寫(xiě)同步問(wèn)題生產(chǎn)者消費(fèi)者同步問(wèn)題生產(chǎn)者消費(fèi)者同步問(wèn)題2021-11-2984.5.1 鎖和上鎖、開(kāi)鎖操作鎖和上鎖、開(kāi)鎖操作解決互斥的最簡(jiǎn)單方法：解決互斥的最簡(jiǎn)單方法：為臨界區(qū)設(shè)置鎖位為臨界區(qū)設(shè)置鎖位。4.5 同步機(jī)構(gòu)同步機(jī)構(gòu)2021-11-2994.5.1 鎖和上鎖、開(kāi)鎖操作鎖和上鎖、開(kāi)鎖操作上鎖原語(yǔ)上鎖原語(yǔ)算法lock輸入：鎖變量輸入：鎖變量w輸出：無(wú)輸出：無(wú)/*檢測(cè)鎖位為檢測(cè)鎖位為0嗎？不為嗎？不為0繼續(xù)檢測(cè)繼續(xù)檢測(cè)*/while(w=1);w=1;/進(jìn)入臨界區(qū)前先上鎖進(jìn)入臨界區(qū)前先上鎖開(kāi)鎖原語(yǔ)開(kāi)鎖

7、原語(yǔ)算法 unlock輸入：鎖變量輸入：鎖變量w輸出：無(wú)輸出：無(wú)w=0; /開(kāi)鎖開(kāi)鎖該方法的缺點(diǎn)：可能產(chǎn)生進(jìn)程的忙等待！該方法的缺點(diǎn)：可能產(chǎn)生進(jìn)程的忙等待！CPU效率下降！效率下降！改進(jìn)辦法？改進(jìn)辦法？2021-11-29104.5.2 信號(hào)燈及其信號(hào)燈及其P、V操作操作v信號(hào)量（信號(hào)燈）信號(hào)量是一種數(shù)據(jù)結(jié)構(gòu)信號(hào)量的一般構(gòu)成（s和q）信號(hào)量s值的含義v信號(hào)量機(jī)制使用信號(hào)量實(shí)現(xiàn)進(jìn)程間的同步和互斥的機(jī)制，是操作系統(tǒng)提供的一種進(jìn)程通信方式。2021-11-29114.5.2 信號(hào)量及其信號(hào)量及其P、V操作操作v信號(hào)量總結(jié)：信號(hào)量總結(jié)：信號(hào)量的值與相應(yīng)資源的使用情況有關(guān)信號(hào)量的值與相應(yīng)資源的使用情況有

8、關(guān)信號(hào)量的初值設(shè)定信號(hào)量的初值設(shè)定信號(hào)量的值僅由信號(hào)量的值僅由P、V操作來(lái)改變操作來(lái)改變vPV操作操作用來(lái)申請(qǐng)或釋放信號(hào)量的操作，由系統(tǒng)提供的系統(tǒng)調(diào)用完成用來(lái)申請(qǐng)或釋放信號(hào)量的操作，由系統(tǒng)提供的系統(tǒng)調(diào)用完成: P操作表示申請(qǐng)資源；操作表示申請(qǐng)資源； V操作表示釋放資源。操作表示釋放資源。P、V操作用原語(yǔ)實(shí)現(xiàn)，不允許中斷。操作用原語(yǔ)實(shí)現(xiàn)，不允許中斷。2021-11-29124.5.2 信號(hào)量及其信號(hào)量及其P、V操作操作/*P操作原語(yǔ)操作原語(yǔ)請(qǐng)求資源或條件請(qǐng)求資源或條件*/P（s）s；if（s0）保留調(diào)用進(jìn)程的保留調(diào)用進(jìn)程的CPU現(xiàn)場(chǎng)；現(xiàn)場(chǎng)； 將該進(jìn)程插入將該進(jìn)程插入s的等待隊(duì)列；的等待隊(duì)列；置該

9、進(jìn)程為等待態(tài)置該進(jìn)程為等待態(tài);轉(zhuǎn)進(jìn)程調(diào)度轉(zhuǎn)進(jìn)程調(diào)度;2021-11-29134.5.2 信號(hào)量及其信號(hào)量及其P、V操作操作/*V操作原語(yǔ)操作原語(yǔ)釋放資源或條件釋放資源或條件*/V（s）s；if (s0) 移出移出s等待隊(duì)列中的第一個(gè)進(jìn)等待隊(duì)列中的第一個(gè)進(jìn)程；程； 將該進(jìn)程插入就緒隊(duì)列；將該進(jìn)程插入就緒隊(duì)列； 置該進(jìn)程為就緒態(tài)置該進(jìn)程為就緒態(tài);2021-11-29144.6 進(jìn)程互斥與同步的實(shí)現(xiàn)進(jìn)程互斥與同步的實(shí)現(xiàn)4.6 .1上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥 上鎖上鎖 臨界區(qū)臨界區(qū)csb 開(kāi)鎖開(kāi)鎖進(jìn)程進(jìn)程B 上鎖上鎖 臨界區(qū)臨界區(qū)csa 開(kāi)鎖開(kāi)鎖進(jìn)程進(jìn)程A2021-1

10、1-29154.6 進(jìn)程互斥與同步的實(shí)現(xiàn)進(jìn)程互斥與同步的實(shí)現(xiàn)4.6 .1上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥main()int w=0;cobeginppa();ppb();coendppa()lock(w)csa;unlock(w)ppb()lock(w)csb;unlock(w)2021-11-29164.6.2 用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥假設(shè)有假設(shè)有多種多種臨界資源提供給多個(gè)進(jìn)程共享，對(duì)其實(shí)現(xiàn)互斥使用臨界資源提供給多個(gè)進(jìn)程共享，對(duì)其實(shí)現(xiàn)互斥使用的方法為：的方法為：針對(duì)針對(duì)每一類(lèi)臨界資源每一類(lèi)臨界資源設(shè)一個(gè)互斥信號(hào)量設(shè)一個(gè)互斥信號(hào)量mutexi，若某類(lèi)

11、臨，若某類(lèi)臨界資源有界資源有n個(gè)，初值為個(gè)，初值為n；如果只有一個(gè)或者抽象表示只能；如果只有一個(gè)或者抽象表示只能一個(gè)進(jìn)程進(jìn)入，則初值設(shè)為一個(gè)進(jìn)程進(jìn)入，則初值設(shè)為1。在每個(gè)進(jìn)程中對(duì)涉及臨界資源在每個(gè)進(jìn)程中對(duì)涉及臨界資源i的臨界區(qū)做如下處理的臨界區(qū)做如下處理 P（mutexi）；）； 臨界區(qū)；臨界區(qū)；V (mutexi)；2021-11-29174.6.2 用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥步驟：步驟：尋找共享的臨界尋找共享的臨界資源；資源；判定臨界區(qū)；判定臨界區(qū)；設(shè)置信號(hào)量及其設(shè)置信號(hào)量及其初值；初值；使用使用mutex的的P、V操作將臨界區(qū)操作將臨界區(qū)括起來(lái)。括起來(lái)。2021-11-29

12、184.6.2 用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥 對(duì)于飛機(jī)訂票系統(tǒng)的例子，可以采用下列方法解決對(duì)于飛機(jī)訂票系統(tǒng)的例子，可以采用下列方法解決“與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤”：針對(duì)臨界資源機(jī)票庫(kù)設(shè)置一個(gè)信號(hào)量針對(duì)臨界資源機(jī)票庫(kù)設(shè)置一個(gè)信號(hào)量mutex，初值為，初值為1。每個(gè)終端進(jìn)程中的程序。每個(gè)終端進(jìn)程中的程序描述如下：描述如下：P（mutex）；）；在機(jī)票數(shù)據(jù)庫(kù)中取出當(dāng)前剩余票數(shù)在機(jī)票數(shù)據(jù)庫(kù)中取出當(dāng)前剩余票數(shù)X；判斷判斷X0（有票嗎）？（有票嗎）？如果有，如果有， XN（票夠嗎）？（票夠嗎）？如果夠，則出票（打印票據(jù)）；如果夠，則出票（打印票據(jù)）；XXN（修改剩余票數(shù)）；（修改剩余票

13、數(shù)）；將將X回寫(xiě)到數(shù)據(jù)庫(kù)中；回寫(xiě)到數(shù)據(jù)庫(kù)中；V（mutex）；）；如果終端如果終端A先來(lái)，對(duì)先來(lái)，對(duì)mutex進(jìn)行進(jìn)行P操作后，進(jìn)入臨界區(qū)，此時(shí)操作后，進(jìn)入臨界區(qū)，此時(shí)mutex為為0。當(dāng)它還沒(méi)。當(dāng)它還沒(méi)有處理完畢時(shí)，其它任何終端到來(lái)都因其執(zhí)行有處理完畢時(shí)，其它任何終端到來(lái)都因其執(zhí)行P(mutex)后被阻塞，直到終端后被阻塞，直到終端A執(zhí)行了執(zhí)行了V(mutex)后將它們喚醒后才能進(jìn)入其臨界區(qū)對(duì)后將它們喚醒后才能進(jìn)入其臨界區(qū)對(duì)x進(jìn)行操作，從而保證了只進(jìn)行操作，從而保證了只有一個(gè)進(jìn)程進(jìn)入臨界區(qū)，避免了有一個(gè)進(jìn)程進(jìn)入臨界區(qū)，避免了“與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤” 的發(fā)生。的發(fā)生。2021-11

14、-29194.6.2 用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥如果有如果有n個(gè)終端，則個(gè)終端，則mutex信號(hào)量的取值范圍為：信號(hào)量的取值范圍為： （n1）mutex1其物理含義為：其物理含義為：當(dāng)機(jī)票庫(kù)空閑時(shí)，當(dāng)機(jī)票庫(kù)空閑時(shí)，mutex=1。當(dāng)有一個(gè)終端進(jìn)入，對(duì)機(jī)票進(jìn)行處理，其它終端進(jìn)程還沒(méi)有當(dāng)有一個(gè)終端進(jìn)入，對(duì)機(jī)票進(jìn)行處理，其它終端進(jìn)程還沒(méi)有到來(lái)時(shí)，到來(lái)時(shí)，mutex=0。當(dāng)所有終端進(jìn)程都到來(lái)，且有一個(gè)正在對(duì)機(jī)票進(jìn)行處理時(shí)，當(dāng)所有終端進(jìn)程都到來(lái)，且有一個(gè)正在對(duì)機(jī)票進(jìn)行處理時(shí)，mutex=（n1）。它表示有）。它表示有n1個(gè)進(jìn)程在等待隊(duì)列上等個(gè)進(jìn)程在等待隊(duì)列上等待。待。2021-11-292

15、04.6.2 進(jìn)程同步的實(shí)現(xiàn)進(jìn)程同步的實(shí)現(xiàn)用用P、V操作實(shí)現(xiàn)進(jìn)程同步的算法可以簡(jiǎn)單歸納如下：操作實(shí)現(xiàn)進(jìn)程同步的算法可以簡(jiǎn)單歸納如下：設(shè)置信號(hào)量設(shè)置信號(hào)量分析每個(gè)進(jìn)程的分析每個(gè)進(jìn)程的執(zhí)行條件和釋放條件執(zhí)行條件和釋放條件，針對(duì)每個(gè)執(zhí)行條件針對(duì)每個(gè)執(zhí)行條件設(shè)置一個(gè)信號(hào)設(shè)置一個(gè)信號(hào)量，其初值根據(jù)初始情況確定；量，其初值根據(jù)初始情況確定；對(duì)每個(gè)進(jìn)程的處理：對(duì)每個(gè)進(jìn)程的處理：u在請(qǐng)求條件處執(zhí)行在請(qǐng)求條件處執(zhí)行P（執(zhí)行條件信號(hào)量）；（執(zhí)行條件信號(hào)量）；u在釋放條件處執(zhí)行在釋放條件處執(zhí)行V（釋放條件信號(hào)量）。（釋放條件信號(hào)量）。解決同步問(wèn)題與互斥問(wèn)題的區(qū)別解決同步問(wèn)題與互斥問(wèn)題的區(qū)別：互斥問(wèn)題互斥問(wèn)題中各進(jìn)程

16、涉及共同的臨界資源，因此每個(gè)進(jìn)程中涉及同一個(gè)臨中各進(jìn)程涉及共同的臨界資源，因此每個(gè)進(jìn)程中涉及同一個(gè)臨界資源的臨界區(qū)中界資源的臨界區(qū)中所執(zhí)行的所執(zhí)行的P、V操作的信號(hào)量是相同的操作的信號(hào)量是相同的；同步問(wèn)題同步問(wèn)題中每個(gè)進(jìn)程由于執(zhí)行條件和釋放條件的不同因而其中每個(gè)進(jìn)程由于執(zhí)行條件和釋放條件的不同因而其P、V操作涉操作涉及的信號(hào)量不同及的信號(hào)量不同。2021-11-2921例如：設(shè)有例如：設(shè)有4個(gè)進(jìn)程，其執(zhí)行的先后流圖如下圖所示。用個(gè)進(jìn)程，其執(zhí)行的先后流圖如下圖所示。用P、V操作實(shí)現(xiàn)操作實(shí)現(xiàn)其同步。其同步。P 1P 4P 3P 2前驅(qū)與后繼同步問(wèn)題前驅(qū)與后繼同步問(wèn)題進(jìn)程進(jìn)程Pj有 無(wú) 前 驅(qū)有 無(wú)

17、 前 驅(qū)（執(zhí)行條件）（執(zhí)行條件）請(qǐng)求信號(hào)量請(qǐng)求信號(hào)量信號(hào)量初值信號(hào)量初值有無(wú)后繼有無(wú)后繼（釋放條件）（釋放條件）釋放信號(hào)量釋放信號(hào)量P1無(wú)無(wú)無(wú)無(wú)無(wú)無(wú)P2、P3S12、S13P2P1結(jié)束結(jié)束S120P4S24P3P1結(jié)束結(jié)束S130P4S34P4P2、P3結(jié)束結(jié)束S24、S340無(wú)無(wú)無(wú)無(wú)同步分析：2021-11-2922算法描述算法描述：main()int s12 = s13 = s24 = s34 = 0;cobeginp1(); p2(); p3(); p4();coendp1()執(zhí)行執(zhí)行P1自己的程序自己的程序;/無(wú)前驅(qū)，所以無(wú)無(wú)前驅(qū)，所以無(wú)P操作操作V(s12);/有后繼有后繼P2，釋放

18、條件，釋放條件s12V(s13);/有后繼有后繼P3，釋放條件，釋放條件s13p2()P(s12);/有前驅(qū)有前驅(qū)P1，申請(qǐng)條件，申請(qǐng)條件s12執(zhí)行執(zhí)行P2自己的程序自己的程序;V(s24); /有后繼有后繼P4，釋放條件，釋放條件s24p3( )P(s13);/有前驅(qū)有前驅(qū)P1，申請(qǐng)條件，申請(qǐng)條件s13執(zhí)行執(zhí)行P3自己的程序自己的程序;V(s34);/有后繼有后繼P4，釋放條件，釋放條件s34p4( )P(s24);/有前驅(qū)有前驅(qū)P2，申請(qǐng)條件，申請(qǐng)條件s24P(s34);/有前驅(qū)有前驅(qū)P3，申請(qǐng)條件，申請(qǐng)條件s34執(zhí)行執(zhí)行P4自己的程序自己的程序; /無(wú)后繼，所以無(wú)無(wú)后繼，所以無(wú)V操作操作

19、這樣，無(wú)論哪個(gè)進(jìn)程先來(lái)，只要不是這樣，無(wú)論哪個(gè)進(jìn)程先來(lái)，只要不是p1p1進(jìn)程，都會(huì)在執(zhí)行了相應(yīng)的進(jìn)程，都會(huì)在執(zhí)行了相應(yīng)的P P操作后，操作后，因?yàn)閳?zhí)行條件不成立而被掛到相應(yīng)因?yàn)閳?zhí)行條件不成立而被掛到相應(yīng)信號(hào)量的等待隊(duì)列上，等待其前驅(qū)信號(hào)量的等待隊(duì)列上，等待其前驅(qū)執(zhí)行該信號(hào)量的執(zhí)行該信號(hào)量的V V操作后將其喚醒，操作后將其喚醒，從而保證這些進(jìn)程并發(fā)執(zhí)行時(shí)其執(zhí)從而保證這些進(jìn)程并發(fā)執(zhí)行時(shí)其執(zhí)行的時(shí)序遵循給定的同步關(guān)系行的時(shí)序遵循給定的同步關(guān)系。2021-11-2923生產(chǎn)者消費(fèi)者問(wèn)題生產(chǎn)者消費(fèi)者問(wèn)題一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享一個(gè)緩沖區(qū)一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享多個(gè)緩沖區(qū)多個(gè)生產(chǎn)者、多個(gè)消費(fèi)者共享多個(gè)

20、緩沖區(qū)多個(gè)生產(chǎn)者、多個(gè)消費(fèi)者共享一個(gè)緩沖區(qū)多個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享多個(gè)緩沖區(qū)一個(gè)生產(chǎn)者、多個(gè)消費(fèi)者共享多個(gè)緩沖區(qū)2021-11-2924一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享一個(gè)緩沖區(qū)（同步問(wèn)題）一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享一個(gè)緩沖區(qū)（同步問(wèn)題）v同步分析進(jìn)程進(jìn)程執(zhí)行條件與信號(hào)量執(zhí)行條件與信號(hào)量初值初值釋放條件與信號(hào)釋放條件與信號(hào)量量生產(chǎn)者生產(chǎn)者緩沖區(qū)有空，緩沖區(qū)有空，empty1 1緩沖區(qū)有產(chǎn)品，緩沖區(qū)有產(chǎn)品，fullfull消費(fèi)者消費(fèi)者緩沖區(qū)有產(chǎn)品，緩沖區(qū)有產(chǎn)品，fullfull0 0緩沖區(qū)有緩沖區(qū)有空空,empty,empty2021-11-2925算法描述：算法描述：main()int empty

21、=1; /設(shè)置信號(hào)量及初值設(shè)置信號(hào)量及初值int full=0;cobeginproducer( ); cosumer( );coendproducer( )while(生產(chǎn)未完成生產(chǎn)未完成) 生產(chǎn)出產(chǎn)品生產(chǎn)出產(chǎn)品;P(empty); /申請(qǐng)條件申請(qǐng)條件empty將該產(chǎn)品送到緩沖區(qū)；將該產(chǎn)品送到緩沖區(qū)；V(full); /釋放條件釋放條件full cosumer( )while(輸出未完成輸出未完成) P(full); /申請(qǐng)條件申請(qǐng)條件full從緩沖區(qū)中獲取產(chǎn)品從緩沖區(qū)中獲取產(chǎn)品;V(empty); /釋放條件釋放條件empty 一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享一個(gè)緩沖區(qū)（同步問(wèn)題）一個(gè)生產(chǎn)者、一

22、個(gè)消費(fèi)者共享一個(gè)緩沖區(qū)（同步問(wèn)題）2021-11-2926多個(gè)生產(chǎn)者、多個(gè)消費(fèi)者共享多個(gè)緩沖區(qū)多個(gè)生產(chǎn)者、多個(gè)消費(fèi)者共享多個(gè)緩沖區(qū)（同步互斥共存）（同步互斥共存）v互斥分析設(shè)互斥信號(hào)量mutex，初值為1，表示一次只能進(jìn)一個(gè)生產(chǎn)者或消費(fèi)者進(jìn)程。v同步分析(設(shè)有n個(gè)緩沖區(qū))生產(chǎn)者進(jìn)程消費(fèi)者進(jìn)程多緩沖區(qū)進(jìn)程進(jìn)程執(zhí)行條件與信號(hào)量執(zhí)行條件與信號(hào)量初值初值釋放條件與信號(hào)釋放條件與信號(hào)量量第第i i個(gè)生產(chǎn)個(gè)生產(chǎn)者者緩沖區(qū)有空，緩沖區(qū)有空，emptyn n緩沖區(qū)有產(chǎn)品，緩沖區(qū)有產(chǎn)品，fullfull第第j j個(gè)消費(fèi)個(gè)消費(fèi)者者緩沖區(qū)有產(chǎn)品，緩沖區(qū)有產(chǎn)品，fullfull0 0緩沖區(qū)有緩沖區(qū)有空空,empty,

23、empty2021-11-2927算法描述：算法描述：main() /*定義信號(hào)量及其初值定義信號(hào)量及其初值*/int full=0;int empty=n;int mutex=1;cobegin produceri(); consumerj();coend/*某個(gè)生產(chǎn)者進(jìn)程某個(gè)生產(chǎn)者進(jìn)程i*/produceri() while(生產(chǎn)未完成生產(chǎn)未完成)生產(chǎn)一個(gè)產(chǎn)品；生產(chǎn)一個(gè)產(chǎn)品； P(empty);/請(qǐng)求緩請(qǐng)求緩沖區(qū)有空條件沖區(qū)有空條件 P(mutex); /請(qǐng)求進(jìn)請(qǐng)求進(jìn)入臨界區(qū)入臨界區(qū) 送一個(gè)產(chǎn)品到緩沖區(qū)；送一個(gè)產(chǎn)品到緩沖區(qū)；/臨界區(qū)臨界區(qū) V(mutex); /釋放臨釋放臨界區(qū)界區(qū) V(f

24、ull);/釋放緩釋放緩沖區(qū)有數(shù)條件沖區(qū)有數(shù)條件/*某個(gè)消費(fèi)者進(jìn)程某個(gè)消費(fèi)者進(jìn)程j*/cosumerj() while(還要繼續(xù)消費(fèi)還要繼續(xù)消費(fèi))P(full); /請(qǐng)求緩沖區(qū)有數(shù)請(qǐng)求緩沖區(qū)有數(shù)條件條件 P(mutex); /請(qǐng)求請(qǐng)求進(jìn)入臨界區(qū)進(jìn)入臨界區(qū) 從緩沖區(qū)中取一個(gè)產(chǎn)從緩沖區(qū)中取一個(gè)產(chǎn)品；品；/臨界區(qū)臨界區(qū) V(mutex); /釋放釋放臨界區(qū)臨界區(qū) V(empty); /釋放釋放緩沖區(qū)有空條件緩沖區(qū)有空條件 消費(fèi)產(chǎn)品；消費(fèi)產(chǎn)品；多個(gè)生產(chǎn)者、多個(gè)消費(fèi)者共享多個(gè)緩沖區(qū)多個(gè)生產(chǎn)者、多個(gè)消費(fèi)者共享多個(gè)緩沖區(qū)（同步互斥共存）（同步互斥共存）2021-11-2928蘋(píng)果桔子問(wèn)題（同步問(wèn)題） 桌上有

25、一只盤(pán)子，每次只能放入一只水果；爸爸專(zhuān)向盤(pán)子中放蘋(píng)果桌上有一只盤(pán)子，每次只能放入一只水果；爸爸專(zhuān)向盤(pán)子中放蘋(píng)果(apple)(apple)，媽媽專(zhuān)向盤(pán)子中放桔于，媽媽專(zhuān)向盤(pán)子中放桔于(orange)(orange)，一個(gè)兒子專(zhuān)等吃盤(pán)子中，一個(gè)兒子專(zhuān)等吃盤(pán)子中的桔子，一個(gè)女兒專(zhuān)等吃盤(pán)子里的蘋(píng)果。的桔子，一個(gè)女兒專(zhuān)等吃盤(pán)子里的蘋(píng)果。 同步分析：（設(shè)盤(pán)子可裝n個(gè)水果）進(jìn)程進(jìn)程執(zhí)行條件與信號(hào)量執(zhí)行條件與信號(hào)量初值初值釋放條件與信號(hào)量釋放條件與信號(hào)量fatherfather盤(pán)子里可以放水果，盤(pán)子里可以放水果，spn n盤(pán)子中有蘋(píng)果，盤(pán)子中有蘋(píng)果，samothermother盤(pán)子里可以放水果，盤(pán)子里可以放

26、水果，spn n盤(pán)子中有桔子盤(pán)子中有桔子, ,sosonson盤(pán)子中有桔子，盤(pán)子中有桔子， so0 0盤(pán)子中可以放水果，盤(pán)子中可以放水果，spspdaughterdaughter盤(pán)子中有蘋(píng)果，盤(pán)子中有蘋(píng)果， sa0 0盤(pán)子中可以放水果，盤(pán)子中可以放水果，sp2021-11-2929算法描述：算法描述：main() /*定義信號(hào)量及其初值定義信號(hào)量及其初值*/int sp=n； /* 盤(pán)子里可以放盤(pán)子里可以放n個(gè)水果個(gè)水果 */int so=0; /* 盤(pán)子里有桔子盤(pán)子里有桔子,初始無(wú)桔子初始無(wú)桔子 */int sa=0; /* 盤(pán)子里有蘋(píng)果盤(pán)子里有蘋(píng)果,初始無(wú)蘋(píng)果初始無(wú)蘋(píng)果 */cobegin

27、 father();mother()； son();daughter(); coendfather() L1:削一個(gè)蘋(píng)果；削一個(gè)蘋(píng)果；P(sp); 把蘋(píng)果放入盤(pán)子；把蘋(píng)果放入盤(pán)子；V(sa);goto L1;mother()L2:剝一個(gè)桔子；剝一個(gè)桔子；P(sp); 把桔子放入盤(pán)子；把桔子放入盤(pán)子；V(so);goto L2;son() L3:P(so); 從從盤(pán)子盤(pán)子中取桔子；中取桔子；V(sp); 吃桔子；吃桔子；goto L3;daughter() L4:P(sa); 從從盤(pán)子盤(pán)子中取蘋(píng)果；中取蘋(píng)果；V(sp); 吃蘋(píng)果；吃蘋(píng)果；goto L4;蘋(píng)果桔子問(wèn)題（同步問(wèn)題）2021-11-2

28、930理發(fā)師問(wèn)題（同步互斥共存）理發(fā)師問(wèn)題（同步互斥共存）v理發(fā)店里有一位理發(fā)師、一把理發(fā)椅和理發(fā)店里有一位理發(fā)師、一把理發(fā)椅和n n把供等候理發(fā)的顧客坐的椅子把供等候理發(fā)的顧客坐的椅子v如果沒(méi)有顧客，理發(fā)師便在理發(fā)椅上睡覺(jué)如果沒(méi)有顧客，理發(fā)師便在理發(fā)椅上睡覺(jué)v一個(gè)顧客到來(lái)時(shí)，它必須叫醒理發(fā)師一個(gè)顧客到來(lái)時(shí)，它必須叫醒理發(fā)師v如果理發(fā)師正在理發(fā)時(shí)又有顧客來(lái)到，如果理發(fā)師正在理發(fā)時(shí)又有顧客來(lái)到，則如果有空椅子可坐，就坐下來(lái)等待，否則如果有空椅子可坐，就坐下來(lái)等待，否則就離開(kāi)則就離開(kāi)互斥分析：互斥分析：對(duì)臨界資源對(duì)臨界資源“剩余的椅子數(shù)剩余的椅子數(shù)”必須采用互斥必須采用互斥, ,互斥信號(hào)量為互斥信

29、號(hào)量為mutexmutex。同步分析：同步分析：進(jìn)程進(jìn)程執(zhí)行條件與信號(hào)量執(zhí)行條件與信號(hào)量初值初值釋放條件與信號(hào)量釋放條件與信號(hào)量barberbarber有顧客需要理發(fā)，有顧客需要理發(fā)，customerscustomers0 0理發(fā)師空閑，理發(fā)師空閑，barbersbarberscustomercustomer理發(fā)師空閑，理發(fā)師空閑，barbersbarbers1 1（有顧客需要理發(fā)（有顧客需要理發(fā), , customerscustomers）2021-11-2931算法描述：算法描述：main()int chairs=n;/*以下為信號(hào)量以下為信號(hào)量*/int mutex;int customers=0;/*等待服務(wù)的顧等待服務(wù)的顧客數(shù)客數(shù)*/int barbers