【2】章2進(jìn)程控制與同步-2課件

1、2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系1上次問(wèn)題上次問(wèn)題v“無(wú)序無(wú)序”并發(fā)的運(yùn)行特征？并發(fā)的運(yùn)行特征？v進(jìn)程是什么？進(jìn)程三種基本狀態(tài)是什么？運(yùn)進(jìn)程是什么？進(jìn)程三種基本狀態(tài)是什么？運(yùn)行中如何有序轉(zhuǎn)換的？行中如何有序轉(zhuǎn)換的？vPCB是什么？包含什么信息，請(qǐng)列舉一些？是什么？包含什么信息，請(qǐng)列舉一些？系統(tǒng)如何組織所有的系統(tǒng)如何組織所有的PCB？2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系2 本次問(wèn)題本次問(wèn)題v操作系統(tǒng)通過(guò)操作系統(tǒng)通過(guò)PCB進(jìn)行進(jìn)程創(chuàng)建、終止、進(jìn)行進(jìn)程創(chuàng)建、終止、阻塞的過(guò)程如何；阻塞的過(guò)程如何；v如何理解進(jìn)程同步的含義；如何理解進(jìn)程同步的含義；v控制同步的關(guān)鍵在哪里?？刂仆降年P(guān)鍵在哪里。2

2、022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系3第第2章章 進(jìn)程管理進(jìn)程管理2.1 進(jìn)程基本概念進(jìn)程基本概念2.2 進(jìn)程控制進(jìn)程控制 2.3 進(jìn)程進(jìn)程同步、同步、管程管程2.4 經(jīng)典進(jìn)程同步問(wèn)題經(jīng)典進(jìn)程同步問(wèn)題2.5 進(jìn)程通信進(jìn)程通信2.6 線(xiàn)程線(xiàn)程2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系42.2 進(jìn)程控制進(jìn)程控制進(jìn)程控制的基本過(guò)程：進(jìn)程控制的基本過(guò)程：進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建進(jìn)程的終止進(jìn)程的終止進(jìn)程的阻塞與喚醒進(jìn)程的阻塞與喚醒進(jìn)程的掛起和激活進(jìn)程的掛起和激活2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系5關(guān)于進(jìn)程的親屬關(guān)系關(guān)于進(jìn)程的親屬關(guān)系系統(tǒng)中運(yùn)行的系統(tǒng)中運(yùn)行的進(jìn)程并不都是孤立的進(jìn)程并不都是孤立的，有的有的進(jìn)程運(yùn)

3、行后，會(huì)調(diào)用其他進(jìn)程來(lái)執(zhí)行，進(jìn)程運(yùn)行后，會(huì)調(diào)用其他進(jìn)程來(lái)執(zhí)行，這樣就組成了這樣就組成了進(jìn)程間的父子關(guān)系進(jìn)程間的父子關(guān)系?？捎每捎?“進(jìn)程圖進(jìn)程圖”描述一個(gè)進(jìn)程的家族關(guān)系，描述一個(gè)進(jìn)程的家族關(guān)系，該圖實(shí)際就是一種有向樹(shù)。該圖實(shí)際就是一種有向樹(shù)。2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系6A AB BD DK KE EF FL LM MJ JI IH HG GC C進(jìn)程樹(shù)示例進(jìn)程樹(shù)示例2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系7* 感受進(jìn)程及進(jìn)程樹(shù)感受進(jìn)程及進(jìn)程樹(shù)1.“運(yùn)行運(yùn)行”輸入輸入“cmd”，啟動(dòng)命令行控制臺(tái)，啟動(dòng)命令行控制臺(tái)2.在在cmd窗口輸入窗口輸入“notepad”啟動(dòng)記事本。啟動(dòng)記事本。3

4、.現(xiàn)在進(jìn)程現(xiàn)在進(jìn)程“cmd.exe”和進(jìn)程和進(jìn)程“notepad.exe”就組成了一個(gè)進(jìn)程樹(shù)，后者為子進(jìn)程，前者為父就組成了一個(gè)進(jìn)程樹(shù)，后者為子進(jìn)程，前者為父進(jìn)程。進(jìn)程。 4.用用“任務(wù)管理器任務(wù)管理器”在在“進(jìn)程進(jìn)程”頁(yè)，右擊頁(yè)，右擊cmd.exe選擇選擇“結(jié)束進(jìn)程樹(shù)結(jié)束進(jìn)程樹(shù)”。則記事本子進(jìn)。則記事本子進(jìn)程也會(huì)結(jié)束。程也會(huì)結(jié)束。一些木馬服務(wù)端程序運(yùn)行后會(huì)同時(shí)生成兩個(gè)木馬一些木馬服務(wù)端程序運(yùn)行后會(huì)同時(shí)生成兩個(gè)木馬進(jìn)程，這兩個(gè)進(jìn)程互相監(jiān)控、互相保護(hù)。對(duì)此類(lèi)進(jìn)程，這兩個(gè)進(jìn)程互相監(jiān)控、互相保護(hù)。對(duì)此類(lèi)木馬，我們就可以分別對(duì)兩個(gè)木馬進(jìn)程嘗試使用木馬，我們就可以分別對(duì)兩個(gè)木馬進(jìn)程嘗試使用“結(jié)束進(jìn)程樹(shù)結(jié)

5、束進(jìn)程樹(shù)”命令。命令。2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系8*還可用還可用ProcessExplorerNt查看進(jìn)程的父子關(guān)系查看進(jìn)程的父子關(guān)系 優(yōu)化大師的進(jìn)程查看器優(yōu)化大師的進(jìn)程查看器2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系9進(jìn)程間的父子關(guān)系關(guān)系著資源的繼承。進(jìn)程間的父子關(guān)系關(guān)系著資源的繼承。創(chuàng)建和撤銷(xiāo)進(jìn)程時(shí)，其父、子進(jìn)程要?jiǎng)?chuàng)建和撤銷(xiāo)進(jìn)程時(shí)，其父、子進(jìn)程要相應(yīng)的被影響。相應(yīng)的被影響。下面通過(guò)進(jìn)程生命周期，了解操下面通過(guò)進(jìn)程生命周期，了解操作系統(tǒng)如何利用作系統(tǒng)如何利用PCB進(jìn)行基本的進(jìn)行基本的進(jìn)程控制？進(jìn)程控制？2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系10u用戶(hù)登錄：分時(shí)情況下用戶(hù)的請(qǐng)求用戶(hù)登錄

6、：分時(shí)情況下用戶(hù)的請(qǐng)求u作業(yè)調(diào)度：批處理中作業(yè)調(diào)度：批處理中u提供服務(wù)：運(yùn)行中的用戶(hù)程序提出功能提供服務(wù)：運(yùn)行中的用戶(hù)程序提出功能請(qǐng)求，要?jiǎng)?chuàng)建服務(wù)進(jìn)程（如打印服務(wù)）請(qǐng)求，要?jiǎng)?chuàng)建服務(wù)進(jìn)程（如打印服務(wù)）u應(yīng)用請(qǐng)求：應(yīng)用請(qǐng)求：應(yīng)用程序自己創(chuàng)建進(jìn)程，應(yīng)用程序自己創(chuàng)建進(jìn)程，完完成特定功能的新進(jìn)程。（木馬程序）成特定功能的新進(jìn)程。（木馬程序）1.進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建1）一個(gè)進(jìn)程創(chuàng)建另一進(jìn)程的事件（原因）一個(gè)進(jìn)程創(chuàng)建另一進(jìn)程的事件（原因）2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系11(1) (1) 申請(qǐng)空白申請(qǐng)空白PCBPCB(2) (2) 為新進(jìn)程分配為新進(jìn)程分配資源資源主要是內(nèi)存資源的處理主要是內(nèi)存資源的處

7、理(3) (3) 初始化進(jìn)程控制塊初始化進(jìn)程控制塊標(biāo)識(shí)符（包括父進(jìn)程的）、程序計(jì)標(biāo)識(shí)符（包括父進(jìn)程的）、程序計(jì)數(shù)器指向程序入口地址，就緒態(tài)、優(yōu)數(shù)器指向程序入口地址，就緒態(tài)、優(yōu)先級(jí)等信息的填寫(xiě)。先級(jí)等信息的填寫(xiě)。(4) (4) 將新進(jìn)程插入將新進(jìn)程插入就緒隊(duì)列就緒隊(duì)列2）創(chuàng)建過(guò)程）創(chuàng)建過(guò)程 2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系12上述過(guò)程很關(guān)鍵，不能被打斷！上述過(guò)程很關(guān)鍵，不能被打斷！原語(yǔ)原語(yǔ)是由若干指令構(gòu)成的原子操作過(guò)是由若干指令構(gòu)成的原子操作過(guò)程，作為整體實(shí)現(xiàn)功能，程，作為整體實(shí)現(xiàn)功能，不可被打斷不可被打斷。OS通過(guò)調(diào)用進(jìn)程創(chuàng)建原語(yǔ)通過(guò)調(diào)用進(jìn)程創(chuàng)建原語(yǔ)Creat()創(chuàng)建新進(jìn)程。創(chuàng)建新進(jìn)程。

8、其他各控制工作也都是由其他各控制工作也都是由OS內(nèi)核以?xún)?nèi)核以“原語(yǔ)原語(yǔ)”的方式實(shí)現(xiàn)，以保證不被打斷。的方式實(shí)現(xiàn)，以保證不被打斷。2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系132.進(jìn)程的終止進(jìn)程的終止1）引起進(jìn)程終止的事件）引起進(jìn)程終止的事件u正常結(jié)束正常結(jié)束u異常結(jié)束異常結(jié)束 內(nèi)存越界錯(cuò)誤內(nèi)存越界錯(cuò)誤 保護(hù)錯(cuò)（權(quán)限錯(cuò)，如修保護(hù)錯(cuò)（權(quán)限錯(cuò)，如修改只讀文件等）改只讀文件等） 非法指令（不存在的指非法指令（不存在的指令，程序異常轉(zhuǎn)向而把令，程序異常轉(zhuǎn)向而把數(shù)據(jù)當(dāng)指令）數(shù)據(jù)當(dāng)指令） 特權(quán)指令錯(cuò)（用戶(hù)態(tài)程特權(quán)指令錯(cuò)（用戶(hù)態(tài)程序試圖執(zhí)行只有序試圖執(zhí)行只有OSOS可執(zhí)可執(zhí)行的指令）行的指令） 運(yùn)行超時(shí)、運(yùn)算錯(cuò)、

9、運(yùn)行超時(shí)、運(yùn)算錯(cuò)、i/oi/o故障等故障等u外界干預(yù)外界干預(yù) 操作員或操作系統(tǒng)干操作員或操作系統(tǒng)干預(yù)（死鎖時(shí)，可人為預(yù)（死鎖時(shí)，可人為結(jié)束）結(jié)束） 父進(jìn)程請(qǐng)求終止子進(jìn)父進(jìn)程請(qǐng)求終止子進(jìn)程程 父進(jìn)程終止，子孫進(jìn)父進(jìn)程終止，子孫進(jìn)程也跟著終止程也跟著終止2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系142）終止過(guò)程）終止過(guò)程對(duì)上述事件，對(duì)上述事件，OSOS調(diào)用內(nèi)核終止原語(yǔ)，執(zhí)行下列過(guò)程：調(diào)用內(nèi)核終止原語(yǔ)，執(zhí)行下列過(guò)程：(1) (1) 根據(jù)進(jìn)程標(biāo)示符，檢索出該進(jìn)程根據(jù)進(jìn)程標(biāo)示符，檢索出該進(jìn)程PCBPCB，讀其，讀其狀態(tài)狀態(tài)。* *IF IF 執(zhí)行態(tài)，立即終止該進(jìn)程，置執(zhí)行態(tài)，立即終止該進(jìn)程，置調(diào)度調(diào)度標(biāo)志為

10、標(biāo)志為真，指示重新進(jìn)行調(diào)度。真，指示重新進(jìn)行調(diào)度。* *IF IF 有子孫進(jìn)程，亦應(yīng)予以終止，以防成為不有子孫進(jìn)程，亦應(yīng)予以終止，以防成為不可控進(jìn)程。可控進(jìn)程。(2) (2) 歸還全部歸還全部資源資源至其父進(jìn)程或系統(tǒng)。至其父進(jìn)程或系統(tǒng)。(3) (3) 將該進(jìn)程將該進(jìn)程PCBPCB從所在隊(duì)列或鏈表中移出。從所在隊(duì)列或鏈表中移出。2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系15u請(qǐng)求系統(tǒng)服務(wù)的滿(mǎn)足情況請(qǐng)求系統(tǒng)服務(wù)的滿(mǎn)足情況u啟動(dòng)某種需等待（啟動(dòng)某種需等待（I/OI/O）操作）操作u合作需要的新數(shù)據(jù)尚未到達(dá)合作需要的新數(shù)據(jù)尚未到達(dá)u執(zhí)行某功能的進(jìn)程暫時(shí)無(wú)新工作可執(zhí)行某功能的進(jìn)程暫時(shí)無(wú)新工作可做做( (如發(fā)

11、送數(shù)據(jù)進(jìn)程如發(fā)送數(shù)據(jù)進(jìn)程) )3.進(jìn)程的阻塞與喚醒進(jìn)程的阻塞與喚醒1）引起進(jìn)程阻塞和喚醒的事件）引起進(jìn)程阻塞和喚醒的事件2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系162）阻塞和喚醒過(guò)程）阻塞和喚醒過(guò)程由進(jìn)程調(diào)用阻塞原語(yǔ)阻塞自己，是主動(dòng)行為：由進(jìn)程調(diào)用阻塞原語(yǔ)阻塞自己，是主動(dòng)行為：（1 1）將）將PCBPCB中的中的狀態(tài)狀態(tài)改為阻塞改為阻塞（2 2）該）該P(yáng)CBPCB加入到阻塞隊(duì)列中加入到阻塞隊(duì)列中（3 3）轉(zhuǎn)進(jìn)程）轉(zhuǎn)進(jìn)程調(diào)度調(diào)度，將處理機(jī)分配給另一進(jìn)，將處理機(jī)分配給另一進(jìn)程程（4 4）進(jìn)行）進(jìn)行進(jìn)程切換進(jìn)程切換，即根據(jù)兩切換進(jìn)程的，即根據(jù)兩切換進(jìn)程的PCBPCB，保護(hù)與重新設(shè)置處理機(jī)狀態(tài)。，保護(hù)與

12、重新設(shè)置處理機(jī)狀態(tài)。2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系17阻塞進(jìn)程等待的事件發(fā)生時(shí)，有關(guān)進(jìn)程阻塞進(jìn)程等待的事件發(fā)生時(shí)，有關(guān)進(jìn)程( (如放棄該資源的進(jìn)程如放棄該資源的進(jìn)程) )調(diào)用喚醒原語(yǔ)把調(diào)用喚醒原語(yǔ)把等待該事件的進(jìn)程喚醒。等待該事件的進(jìn)程喚醒。（1 1）把阻塞進(jìn)程從等待該事件的阻把阻塞進(jìn)程從等待該事件的阻塞隊(duì)列中移出塞隊(duì)列中移出（2 2）將其將其PCBPCB中的現(xiàn)行狀態(tài)改為就緒中的現(xiàn)行狀態(tài)改為就緒（3 3）將將PCBPCB插入到就緒隊(duì)列中。插入到就緒隊(duì)列中。阻塞與喚醒原語(yǔ)作用相反，成對(duì)使用阻塞與喚醒原語(yǔ)作用相反，成對(duì)使用2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系18掛起原語(yǔ)將指定進(jìn)程或阻塞進(jìn)

13、程掛起。掛起原語(yǔ)將指定進(jìn)程或阻塞進(jìn)程掛起。（1 1）檢查）檢查被掛起進(jìn)程的被掛起進(jìn)程的狀態(tài)狀態(tài)，活動(dòng)就緒則改為活動(dòng)就緒則改為靜止就緒，活動(dòng)阻塞則改為靜止阻塞靜止就緒，活動(dòng)阻塞則改為靜止阻塞（2 2）將該）將該P(yáng)CBPCB復(fù)制到內(nèi)存（方便檢查）復(fù)制到內(nèi)存（方便檢查）/ /外存外存（對(duì)換）指定區(qū)域（對(duì)換）指定區(qū)域（3 3）* *若掛起的進(jìn)程是執(zhí)行態(tài)，則需重新進(jìn)行進(jìn)若掛起的進(jìn)程是執(zhí)行態(tài)，則需重新進(jìn)行進(jìn)程調(diào)度。程調(diào)度。注意：進(jìn)程只能掛起自己或其子孫進(jìn)程。注意：進(jìn)程只能掛起自己或其子孫進(jìn)程。4.進(jìn)程的掛起與激活進(jìn)程的掛起與激活2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系19激活原語(yǔ)的執(zhí)行過(guò)程激活原語(yǔ)的執(zhí)行過(guò)程

14、若掛起進(jìn)程在外存上，將其調(diào)入內(nèi)存若掛起進(jìn)程在外存上，將其調(diào)入內(nèi)存檢查進(jìn)程狀態(tài)，若處于靜止就緒，則改為檢查進(jìn)程狀態(tài)，若處于靜止就緒，則改為活動(dòng)就緒，若處于靜止阻塞，則改為活動(dòng)活動(dòng)就緒，若處于靜止阻塞，則改為活動(dòng)阻塞阻塞2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系20* 關(guān)于調(diào)度關(guān)于調(diào)度進(jìn)程控制中，狀態(tài)轉(zhuǎn)換和調(diào)度密切相關(guān)。進(jìn)程控制中，狀態(tài)轉(zhuǎn)換和調(diào)度密切相關(guān)。運(yùn)行態(tài)運(yùn)行態(tài)進(jìn)程的改變必然產(chǎn)生調(diào)度行為進(jìn)程的改變必然產(chǎn)生調(diào)度行為只要產(chǎn)生只要產(chǎn)生新就緒新就緒態(tài)進(jìn)程，就需考慮調(diào)度策態(tài)進(jìn)程，就需考慮調(diào)度策略略l只要是采用搶占式調(diào)度，要檢查新就緒只要是采用搶占式調(diào)度，要檢查新就緒進(jìn)程是否可搶占進(jìn)程是否可搶占CPUCPU

15、，引起新的調(diào)度。，引起新的調(diào)度。2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系21控制并發(fā)：控制并發(fā)：基本控制基本控制進(jìn)程、進(jìn)程、PCB、狀態(tài)、基本控制過(guò)程、狀態(tài)、基本控制過(guò)程合理控制合理控制 * 控制進(jìn)程的控制進(jìn)程的相互影響相互影響，得到可再現(xiàn)的正確結(jié)果，得到可再現(xiàn)的正確結(jié)果 *同步同步2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系22第第2章章 進(jìn)程管理進(jìn)程管理2.1 進(jìn)程基本概念進(jìn)程基本概念2.2 進(jìn)程控制進(jìn)程控制 2.3 進(jìn)程進(jìn)程同步、同步、管程管程2.4 經(jīng)典進(jìn)程同步問(wèn)題經(jīng)典進(jìn)程同步問(wèn)題2.5 進(jìn)程通信進(jìn)程通信2.6 線(xiàn)程線(xiàn)程2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系232.3 進(jìn)程同步進(jìn)程同步1.理解

16、同步的含義理解同步的含義2.信號(hào)量機(jī)制控制進(jìn)程同步信號(hào)量機(jī)制控制進(jìn)程同步3.管程管程2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系24進(jìn)程間有什么相互影響？進(jìn)程間有什么相互影響？?jī)煞N制約關(guān)系：兩種制約關(guān)系：1.1.間接相互制約關(guān)系：主要源于資源共間接相互制約關(guān)系：主要源于資源共享享, ,表現(xiàn)為表現(xiàn)為進(jìn)程進(jìn)程A-A-打印機(jī)資源打印機(jī)資源-進(jìn)程進(jìn)程B B（互斥）（互斥）2.2.直接相互制約關(guān)系：主要源于進(jìn)程合直接相互制約關(guān)系：主要源于進(jìn)程合作，表現(xiàn)為作，表現(xiàn)為進(jìn)程進(jìn)程A A寫(xiě)緩沖寫(xiě)緩沖-進(jìn)程進(jìn)程B B讀緩沖（有序）讀緩沖（有序）2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系251.進(jìn)程同步的基本概念進(jìn)程同步的基本

17、概念1 1）進(jìn)程同步的主要任務(wù)：）進(jìn)程同步的主要任務(wù)： 使并發(fā)執(zhí)行的諸進(jìn)程之間能有效使并發(fā)執(zhí)行的諸進(jìn)程之間能有效地地和和，從而使，從而使程序的執(zhí)行具有程序的執(zhí)行具有。2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系262）臨界資源）臨界資源一次僅允許一個(gè)進(jìn)程使用的資源。一次僅允許一個(gè)進(jìn)程使用的資源。例例1：兩個(gè)進(jìn)程：兩個(gè)進(jìn)程A、B，它們共享一個(gè)變，它們共享一個(gè)變量量x，他們共同使，他們共同使x值增長(zhǎng)。值增長(zhǎng)。A： R1=x； R1=R1+1； x=R1B： R2=x； R2=R2+1； x=R2R1和和R2為處理機(jī)中的兩個(gè)寄存器。兩個(gè)進(jìn)程各自對(duì)為處理機(jī)中的兩個(gè)寄存器。兩個(gè)進(jìn)程各自對(duì)x作加作加1操作。操作

18、。2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系27直觀上，若順序運(yùn)行兩進(jìn)程，直觀上，若順序運(yùn)行兩進(jìn)程，x應(yīng)被加應(yīng)被加2。A： R1=x；B： R2=x；A： R1=R1+1； x=R1B： R2=R2+1； x=R2X的值的值 0 0（1） 1（1） 1一個(gè)假發(fā)實(shí)際上有多步。一個(gè)假發(fā)實(shí)際上有多步。A，B對(duì)對(duì)x操作的過(guò)程被彼操作的過(guò)程被彼此影響，兩者都運(yùn)行完后，此影響，兩者都運(yùn)行完后，x卻只增加了卻只增加了1。共享變量共享變量x應(yīng)按臨界資應(yīng)按臨界資源處理，一個(gè)進(jìn)程還沒(méi)有源處理，一個(gè)進(jìn)程還沒(méi)有用完畢前不能讓其他進(jìn)程用完畢前不能讓其他進(jìn)程使用使用但若如此異步運(yùn)行，即使有保護(hù)現(xiàn)但若如此異步運(yùn)行，即使有保護(hù)現(xiàn)

19、場(chǎng)的處理，結(jié)果是場(chǎng)的處理，結(jié)果是1。2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系28例例2：生產(chǎn)者：生產(chǎn)者消費(fèi)者問(wèn)題：消費(fèi)者問(wèn)題：一群一群生產(chǎn)者進(jìn)程生產(chǎn)產(chǎn)品供給消費(fèi)者進(jìn)生產(chǎn)者進(jìn)程生產(chǎn)產(chǎn)品供給消費(fèi)者進(jìn)程消費(fèi)，在兩者之間設(shè)置具有程消費(fèi)，在兩者之間設(shè)置具有n n個(gè)緩沖區(qū)的緩個(gè)緩沖區(qū)的緩沖池沖池，生產(chǎn)者進(jìn)程所生產(chǎn)的產(chǎn)品放入一個(gè)緩，生產(chǎn)者進(jìn)程所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中，消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)中取走沖區(qū)中，消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)中取走產(chǎn)品去消費(fèi)。產(chǎn)品去消費(fèi)。生產(chǎn)者和消費(fèi)者都以異步方式運(yùn)行，但生產(chǎn)者和消費(fèi)者都以異步方式運(yùn)行，但它們之間必須保持同步：它們之間必須保持同步：沒(méi)有產(chǎn)品不能取，沒(méi)有產(chǎn)品不能取，沒(méi)有空

20、間不能放。也不能同時(shí)對(duì)一個(gè)空間進(jìn)沒(méi)有空間不能放。也不能同時(shí)對(duì)一個(gè)空間進(jìn)行取和放行取和放1230n-1n-2Inout2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系29type item=;表示一個(gè)產(chǎn)品表示一個(gè)產(chǎn)品Var n, integer;緩沖區(qū)大小緩沖區(qū)大小counter:0, 1, , n; 緩沖區(qū)內(nèi)產(chǎn)品計(jì)數(shù)的變量緩沖區(qū)內(nèi)產(chǎn)品計(jì)數(shù)的變量var buffer: array0, 1, , n-1 of item;in, out: 0, 1, , n-1;該數(shù)組代表具有該數(shù)組代表具有n個(gè)個(gè)緩沖區(qū)的緩沖池緩沖區(qū)的緩沖池注意：緩沖池組織為循環(huán)緩沖，注意：緩沖池組織為循環(huán)緩沖，in加加1表示為表示為in:=

21、(in+1)mod nout加加1表示為表示為out:=(out+1)mod n當(dāng)當(dāng)(in+1)mod n=out時(shí)表示緩沖池時(shí)表示緩沖池滿(mǎn)滿(mǎn)in=out表示緩沖池空。表示緩沖池空。使用的變量：使用的變量：指示生產(chǎn)者和消費(fèi)者放指示生產(chǎn)者和消費(fèi)者放或取的下一個(gè)緩沖區(qū)位或取的下一個(gè)緩沖區(qū)位置指針，初值均為置指針，初值均為0。Producer: repeat 生產(chǎn)生產(chǎn) an item in nextp; while counter= n do no-op; until false;Consumer: repeat while counter= 0 do no-op; 消費(fèi)產(chǎn)品消費(fèi)產(chǎn)品item in

22、nextc; until false;空操作空操作操作過(guò)程操作過(guò)程1230n-1n-2outIn一個(gè)生產(chǎn)者一個(gè)生產(chǎn)者nextp一個(gè)消費(fèi)者一個(gè)消費(fèi)者nextcIn交替運(yùn)行中的彼此打斷會(huì)有什么問(wèn)題？交替運(yùn)行中的彼此打斷會(huì)有什么問(wèn)題？Counter=12022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系31生產(chǎn)者和消費(fèi)者共同要影響的變量生產(chǎn)者和消費(fèi)者共同要影響的變量counter的獨(dú)立操作被打斷才有重要影響。的獨(dú)立操作被打斷才有重要影響。設(shè)當(dāng)前持續(xù)正常運(yùn)行到設(shè)當(dāng)前持續(xù)正常運(yùn)行到counter=5（實(shí)際緩沖區(qū)已經(jīng)有了（實(shí)際緩沖區(qū)已經(jīng)有了6個(gè)產(chǎn)品）個(gè)產(chǎn)品）R1=counter；（；（5）R1=R1+1；6counte

23、r=R1（6）R2=counter；（；（5）R2=R2-1；4Counter=R2（4）生產(chǎn)一個(gè)，消費(fèi)一個(gè)，還有的產(chǎn)品數(shù)應(yīng)是生產(chǎn)一個(gè)，消費(fèi)一個(gè)，還有的產(chǎn)品數(shù)應(yīng)是5。 本例順序得到結(jié)果本例順序得到結(jié)果4，生產(chǎn)方會(huì)認(rèn)為還可以繼續(xù)生，生產(chǎn)方會(huì)認(rèn)為還可以繼續(xù)生產(chǎn)產(chǎn)n-4個(gè)。比實(shí)際需求的個(gè)。比實(shí)際需求的n-5多生產(chǎn)的一個(gè)必然會(huì)覆多生產(chǎn)的一個(gè)必然會(huì)覆蓋一個(gè)舊產(chǎn)品。蓋一個(gè)舊產(chǎn)品。 若后兩句交換順序得到結(jié)果又是若后兩句交換順序得到結(jié)果又是6，消費(fèi)方則會(huì)錯(cuò)，消費(fèi)方則會(huì)錯(cuò)誤的向下多消費(fèi)一個(gè)誤的向下多消費(fèi)一個(gè)2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系32所以對(duì)生產(chǎn)者和消費(fèi)者而言，所以對(duì)生產(chǎn)者和消費(fèi)者而言，counte

24、r應(yīng)作為臨界資源，應(yīng)對(duì)其互應(yīng)作為臨界資源，應(yīng)對(duì)其互斥訪問(wèn)斥訪問(wèn)若是一群生產(chǎn)者和消費(fèi)者若是一群生產(chǎn)者和消費(fèi)者生產(chǎn)者之間共同要影響的變量生產(chǎn)者之間共同要影響的變量in要互要互斥；消費(fèi)者間的斥；消費(fèi)者間的out也一樣；也一樣；2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系33互斥：互斥：在操作系統(tǒng)中，當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū)使用臨在操作系統(tǒng)中，當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū)使用臨界界時(shí)，另一個(gè)進(jìn)程必須等待，直到占用臨界時(shí)，另一個(gè)進(jìn)程必須等待，直到占用臨界資源的進(jìn)程退出臨界區(qū)，我們稱(chēng)進(jìn)程之間的這種相資源的進(jìn)程退出臨界區(qū)，我們稱(chēng)進(jìn)程之間的這種相互制約關(guān)系為互制約關(guān)系為“互斥互斥”。同步：同步：多個(gè)相互多個(gè)相互的進(jìn)程，在一些關(guān)

25、鍵點(diǎn)上可能的進(jìn)程，在一些關(guān)鍵點(diǎn)上可能需要互相等待或互相交換信息，這種相互制約關(guān)系需要互相等待或互相交換信息，這種相互制約關(guān)系稱(chēng)為進(jìn)程同步關(guān)系?？衫斫鉃榉Q(chēng)為進(jìn)程同步關(guān)系?？衫斫鉃椤坝行蛴行颉?。如：生產(chǎn)和消費(fèi)的如：生產(chǎn)和消費(fèi)的“有序有序”關(guān)系靠對(duì)關(guān)系靠對(duì)counter的正的正確判斷達(dá)到，而對(duì)確判斷達(dá)到，而對(duì)counter的修改必須的修改必須“互斥互斥”修改。修改。理解同步理解同步2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系343）臨界區(qū)）臨界區(qū)每個(gè)進(jìn)程中訪問(wèn)臨界資源的每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段代碼那段代碼叫臨界區(qū)。叫臨界區(qū)。為了正確同步，對(duì)臨界區(qū)的代碼要增加控制為了正確同步，對(duì)臨界區(qū)的代碼要增加控制進(jìn)

26、程代碼分四部分：進(jìn)程代碼分四部分：repeat critical section remainder sectionuntil false進(jìn)入?yún)^(qū)：對(duì)欲訪問(wèn)的臨界資源進(jìn)入?yún)^(qū)：對(duì)欲訪問(wèn)的臨界資源進(jìn)行檢。若此刻未被訪問(wèn)，設(shè)正進(jìn)行檢。若此刻未被訪問(wèn)，設(shè)正在訪問(wèn)的標(biāo)志在訪問(wèn)的標(biāo)志臨界區(qū)：訪問(wèn)臨界資源的代碼。臨界區(qū)：訪問(wèn)臨界資源的代碼。退出區(qū)：將正在訪問(wèn)的標(biāo)志恢退出區(qū)：將正在訪問(wèn)的標(biāo)志恢復(fù)為未被訪問(wèn)的標(biāo)志復(fù)為未被訪問(wèn)的標(biāo)志剩余區(qū)：其余部分剩余區(qū)：其余部分 “進(jìn)入進(jìn)入”和和“退出退出”臨界區(qū)的處理對(duì)實(shí)臨界區(qū)的處理對(duì)實(shí)現(xiàn)互斥尤其重要現(xiàn)互斥尤其重要entry sectionexit section2022-2-

27、20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系354）同步機(jī)制應(yīng)遵循的規(guī)則）同步機(jī)制應(yīng)遵循的規(guī)則實(shí)現(xiàn)互斥的方法應(yīng)符合如下每條原則實(shí)現(xiàn)互斥的方法應(yīng)符合如下每條原則空閑讓進(jìn)空閑讓進(jìn)：資源使用最基本原則：資源使用最基本原則忙則等待忙則等待：保證互斥：保證互斥有限等待有限等待：合適時(shí)被喚醒防止死等：合適時(shí)被喚醒防止死等讓權(quán)等待讓權(quán)等待：能主動(dòng)釋放：能主動(dòng)釋放CPU防止忙等防止忙等2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系36 早期實(shí)現(xiàn)互斥并不容易早期實(shí)現(xiàn)互斥并不容易 軟件的方法舉例：軟件的方法舉例：?jiǎn)栴}：兩個(gè)進(jìn)程問(wèn)題：兩個(gè)進(jìn)程Pi, Pj互斥訪問(wèn)共享資源互斥訪問(wèn)共享資源R算法算法1：設(shè)置單標(biāo)志，：設(shè)置單標(biāo)志，Pi，Pj想要操作

28、想要操作R都要判斷都要判斷共享標(biāo)志共享標(biāo)志turn是否是自己。是否是自己。其中的其中的Pi如下：如下：RepeatWhile turni do no-op; 操作操作R的代碼的代碼turn=j; (其他操作其他操作)Until false問(wèn)題：?jiǎn)栴}：Pi將將turn置為置為j后，后，若若j暫時(shí)不訪問(wèn)暫時(shí)不訪問(wèn)R，Pi也不能訪問(wèn)。不符也不能訪問(wèn)。不符“空閑讓進(jìn)空閑讓進(jìn)”。算法算法1缺點(diǎn)：強(qiáng)制輪流進(jìn)入臨界區(qū)，沒(méi)有考慮進(jìn)程的實(shí)缺點(diǎn)：強(qiáng)制輪流進(jìn)入臨界區(qū)，沒(méi)有考慮進(jìn)程的實(shí)際需要。際需要。算法算法2 ：設(shè)置多標(biāo)志（標(biāo)志數(shù)組：設(shè)置多標(biāo)志（標(biāo)志數(shù)組flag） flagi表示表示進(jìn)程進(jìn)程i是否在臨界區(qū)，是否在臨

29、界區(qū)，初值均為初值均為FALSE。進(jìn)入前先檢查對(duì)。進(jìn)入前先檢查對(duì)方標(biāo)志。方標(biāo)志。其中的其中的Pi如下：如下：RepeatWhile flagj do no-op;flagi=true; 操作操作R的代碼的代碼flagi=false; (其他操作其他操作)Until falseflagi=F, flagj=Fn問(wèn)題：?jiǎn)栴}：Pi和和Pj可能同時(shí)進(jìn)入可能同時(shí)進(jìn)入臨界區(qū)。違反臨界區(qū)。違反“忙則等忙則等待待”，根本達(dá)不到互斥。，根本達(dá)不到互斥。n源于：檢查和修改操作源于：檢查和修改操作可能會(huì)不連續(xù)?？赡軙?huì)不連續(xù)。2022-2-20山東農(nóng)業(yè)大學(xué)計(jì)算機(jī)系38修改修改算法算法3：其中的其中的Pi如下：如下：Repeatflagi=true;While flagj do no-op;操作操作R的代碼的代碼flagi=false; (其他操作其他操作)Until falseflagi=F, flagj=F先改寫(xiě)自己的狀態(tài)先改寫(xiě)自己的狀態(tài)問(wèn)題：?jiǎn)栴}