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

1、上次問題“無序”并發(fā)的運(yùn)行特征？進(jìn)程是什么？進(jìn)程三種基本狀態(tài)是什么？運(yùn)行中如何有序轉(zhuǎn)換的？PCB是什么？包含什么信息，請列舉一些？系統(tǒng)如何組織所有的PCB？7/20/20221山東農(nóng)業(yè)大學(xué)計算機(jī)系第1頁，共43頁。 本次問題操作系統(tǒng)通過PCB進(jìn)行進(jìn)程創(chuàng)建、終止、阻塞的過程如何；如何理解進(jìn)程同步的含義；控制同步的關(guān)鍵在哪里。7/20/20222山東農(nóng)業(yè)大學(xué)計算機(jī)系第2頁，共43頁。第2章 進(jìn)程管理2.1 進(jìn)程基本概念2.2 進(jìn)程控制 2.3 進(jìn)程同步、管程2.4 經(jīng)典進(jìn)程同步問題2.5 進(jìn)程通信2.6 線程7/20/20223山東農(nóng)業(yè)大學(xué)計算機(jī)系第3頁，共43頁。2.2 進(jìn)程控制進(jìn)程控制的基本過

2、程：進(jìn)程的創(chuàng)建進(jìn)程的終止進(jìn)程的阻塞與喚醒進(jìn)程的掛起和激活7/20/20224山東農(nóng)業(yè)大學(xué)計算機(jī)系第4頁，共43頁。關(guān)于進(jìn)程的親屬關(guān)系系統(tǒng)中運(yùn)行的進(jìn)程并不都是孤立的，有的進(jìn)程運(yùn)行后，會調(diào)用其他進(jìn)程來執(zhí)行，這樣就組成了進(jìn)程間的父子關(guān)系?？捎?“進(jìn)程圖”描述一個進(jìn)程的家族關(guān)系，該圖實際就是一種有向樹。7/20/20225山東農(nóng)業(yè)大學(xué)計算機(jī)系第5頁，共43頁。ABDKEFLMJIHGC進(jìn)程樹示例7/20/20226山東農(nóng)業(yè)大學(xué)計算機(jī)系第6頁，共43頁。* 感受進(jìn)程及進(jìn)程樹“運(yùn)行”輸入“cmd”，啟動命令行控制臺在cmd窗口輸入“notepad”啟動記事本?，F(xiàn)在進(jìn)程“cmd.exe”和進(jìn)程“notepa

3、d.exe”就組成了一個進(jìn)程樹，后者為子進(jìn)程，前者為父進(jìn)程。 用“任務(wù)管理器”在“進(jìn)程”頁，右擊cmd.exe選擇“結(jié)束進(jìn)程樹”。則記事本子進(jìn)程也會結(jié)束。一些木馬服務(wù)端程序運(yùn)行后會同時生成兩個木馬進(jìn)程，這兩個進(jìn)程互相監(jiān)控、互相保護(hù)。對此類木馬，我們就可以分別對兩個木馬進(jìn)程嘗試使用“結(jié)束進(jìn)程樹”命令。7/20/20227山東農(nóng)業(yè)大學(xué)計算機(jī)系第7頁，共43頁。*還可用ProcessExplorerNt查看進(jìn)程的父子關(guān)系 優(yōu)化大師的進(jìn)程查看器7/20/20228山東農(nóng)業(yè)大學(xué)計算機(jī)系第8頁，共43頁。進(jìn)程間的父子關(guān)系關(guān)系著資源的繼承。創(chuàng)建和撤銷進(jìn)程時，其父、子進(jìn)程要相應(yīng)的被影響。下面通過進(jìn)程生命周期，

4、了解操作系統(tǒng)如何利用PCB進(jìn)行基本的進(jìn)程控制？7/20/20229山東農(nóng)業(yè)大學(xué)計算機(jī)系第9頁，共43頁。用戶登錄：分時情況下用戶的請求作業(yè)調(diào)度：批處理中提供服務(wù)：運(yùn)行中的用戶程序提出功能請求，要創(chuàng)建服務(wù)進(jìn)程（如打印服務(wù)）應(yīng)用請求：應(yīng)用程序自己創(chuàng)建進(jìn)程，完成特定功能的新進(jìn)程。（木馬程序）1.進(jìn)程的創(chuàng)建1）一個進(jìn)程創(chuàng)建另一進(jìn)程的事件（原因）7/20/202210山東農(nóng)業(yè)大學(xué)計算機(jī)系第10頁，共43頁。(1) 申請空白PCB(2) 為新進(jìn)程分配資源主要是內(nèi)存資源的處理(3) 初始化進(jìn)程控制塊標(biāo)識符（包括父進(jìn)程的）、程序計數(shù)器指向程序入口地址，就緒態(tài)、優(yōu)先級等信息的填寫。(4) 將新進(jìn)程插入就緒隊列2

5、）創(chuàng)建過程 7/20/202211山東農(nóng)業(yè)大學(xué)計算機(jī)系第11頁，共43頁。上述過程很關(guān)鍵，不能被打斷！原語是由若干指令構(gòu)成的原子操作過程，作為整體實現(xiàn)功能，不可被打斷。OS通過調(diào)用進(jìn)程創(chuàng)建原語Creat()創(chuàng)建新進(jìn)程。其他各控制工作也都是由OS內(nèi)核以“原語”的方式實現(xiàn)，以保證不被打斷。7/20/202212山東農(nóng)業(yè)大學(xué)計算機(jī)系第12頁，共43頁。2.進(jìn)程的終止1）引起進(jìn)程終止的事件正常結(jié)束異常結(jié)束內(nèi)存越界錯誤保護(hù)錯（權(quán)限錯，如修改只讀文件等）非法指令（不存在的指令，程序異常轉(zhuǎn)向而把數(shù)據(jù)當(dāng)指令）特權(quán)指令錯（用戶態(tài)程序試圖執(zhí)行只有OS可執(zhí)行的指令）運(yùn)行超時、運(yùn)算錯、i/o故障等外界干預(yù)操作員或操作

6、系統(tǒng)干預(yù)（死鎖時，可人為結(jié)束）父進(jìn)程請求終止子進(jìn)程父進(jìn)程終止，子孫進(jìn)程也跟著終止7/20/202213山東農(nóng)業(yè)大學(xué)計算機(jī)系第13頁，共43頁。2）終止過程對上述事件，OS調(diào)用內(nèi)核終止原語，執(zhí)行下列過程：(1) 根據(jù)進(jìn)程標(biāo)示符，檢索出該進(jìn)程PCB，讀其狀態(tài)。*IF 執(zhí)行態(tài)，立即終止該進(jìn)程，置調(diào)度標(biāo)志為真，指示重新進(jìn)行調(diào)度。*IF 有子孫進(jìn)程，亦應(yīng)予以終止，以防成為不可控進(jìn)程。(2) 歸還全部資源至其父進(jìn)程或系統(tǒng)。(3) 將該進(jìn)程PCB從所在隊列或鏈表中移出。7/20/202214山東農(nóng)業(yè)大學(xué)計算機(jī)系第14頁，共43頁。請求系統(tǒng)服務(wù)的滿足情況啟動某種需等待（I/O）操作合作需要的新數(shù)據(jù)尚未到達(dá)執(zhí)行

7、某功能的進(jìn)程暫時無新工作可做(如發(fā)送數(shù)據(jù)進(jìn)程)3.進(jìn)程的阻塞與喚醒1）引起進(jìn)程阻塞和喚醒的事件7/20/202215山東農(nóng)業(yè)大學(xué)計算機(jī)系第15頁，共43頁。2）阻塞和喚醒過程由進(jìn)程調(diào)用阻塞原語阻塞自己，是主動行為：（1）將PCB中的狀態(tài)改為阻塞（2）該P(yáng)CB加入到阻塞隊列中（3）轉(zhuǎn)進(jìn)程調(diào)度，將處理機(jī)分配給另一進(jìn)程（4）進(jìn)行進(jìn)程切換，即根據(jù)兩切換進(jìn)程的PCB，保護(hù)與重新設(shè)置處理機(jī)狀態(tài)。7/20/202216山東農(nóng)業(yè)大學(xué)計算機(jī)系第16頁，共43頁。阻塞進(jìn)程等待的事件發(fā)生時，有關(guān)進(jìn)程(如放棄該資源的進(jìn)程)調(diào)用喚醒原語把等待該事件的進(jìn)程喚醒。（1）把阻塞進(jìn)程從等待該事件的阻塞隊列中移出（2）將其PCB

8、中的現(xiàn)行狀態(tài)改為就緒（3）將PCB插入到就緒隊列中。阻塞與喚醒原語作用相反，成對使用7/20/202217山東農(nóng)業(yè)大學(xué)計算機(jī)系第17頁，共43頁。掛起原語將指定進(jìn)程或阻塞進(jìn)程掛起。（1）檢查被掛起進(jìn)程的狀態(tài)，活動就緒則改為靜止就緒，活動阻塞則改為靜止阻塞（2）將該P(yáng)CB復(fù)制到內(nèi)存（方便檢查）/外存（對換）指定區(qū)域（3）*若掛起的進(jìn)程是執(zhí)行態(tài)，則需重新進(jìn)行進(jìn)程調(diào)度。注意：進(jìn)程只能掛起自己或其子孫進(jìn)程。4.進(jìn)程的掛起與激活7/20/202218山東農(nóng)業(yè)大學(xué)計算機(jī)系第18頁，共43頁。激活原語的執(zhí)行過程若掛起進(jìn)程在外存上，將其調(diào)入內(nèi)存檢查進(jìn)程狀態(tài)，若處于靜止就緒，則改為活動就緒，若處于靜止阻塞，則改

9、為活動阻塞7/20/202219山東農(nóng)業(yè)大學(xué)計算機(jī)系第19頁，共43頁。* 關(guān)于調(diào)度進(jìn)程控制中，狀態(tài)轉(zhuǎn)換和調(diào)度密切相關(guān)。運(yùn)行態(tài)進(jìn)程的改變必然產(chǎn)生調(diào)度行為只要產(chǎn)生新就緒態(tài)進(jìn)程，就需考慮調(diào)度策略只要是采用搶占式調(diào)度，要檢查新就緒進(jìn)程是否可搶占CPU，引起新的調(diào)度。7/20/202220山東農(nóng)業(yè)大學(xué)計算機(jī)系第20頁，共43頁?？刂撇l(fā)：基本控制進(jìn)程、PCB、狀態(tài)、基本控制過程合理控制 * 控制進(jìn)程的相互影響，得到可再現(xiàn)的正確結(jié)果 *同步7/20/202221山東農(nóng)業(yè)大學(xué)計算機(jī)系第21頁，共43頁。第2章 進(jìn)程管理2.1 進(jìn)程基本概念2.2 進(jìn)程控制 2.3 進(jìn)程同步、管程2.4 經(jīng)典進(jìn)程同步問題2.

10、5 進(jìn)程通信2.6 線程7/20/202222山東農(nóng)業(yè)大學(xué)計算機(jī)系第22頁，共43頁。2.3 進(jìn)程同步理解同步的含義信號量機(jī)制控制進(jìn)程同步管程7/20/202223山東農(nóng)業(yè)大學(xué)計算機(jī)系第23頁，共43頁。進(jìn)程間有什么相互影響？兩種制約關(guān)系：間接相互制約關(guān)系：主要源于資源共享,表現(xiàn)為進(jìn)程A-打印機(jī)資源-進(jìn)程B（互斥）直接相互制約關(guān)系：主要源于進(jìn)程合作，表現(xiàn)為進(jìn)程A寫緩沖-進(jìn)程B讀緩沖（有序）7/20/202224山東農(nóng)業(yè)大學(xué)計算機(jī)系第24頁，共43頁。1.進(jìn)程同步的基本概念1）進(jìn)程同步的主要任務(wù)： 使并發(fā)執(zhí)行的諸進(jìn)程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。7/20/2022

11、25山東農(nóng)業(yè)大學(xué)計算機(jī)系第25頁，共43頁。2）臨界資源一次僅允許一個進(jìn)程使用的資源。例1：兩個進(jìn)程A、B，它們共享一個變量x，他們共同使x值增長。A： R1=x； R1=R1+1； x=R1B： R2=x； R2=R2+1； x=R2R1和R2為處理機(jī)中的兩個寄存器。兩個進(jìn)程各自對x作加1操作。7/20/202226山東農(nóng)業(yè)大學(xué)計算機(jī)系第26頁，共43頁。直觀上，若順序運(yùn)行兩進(jìn)程，x應(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一個假發(fā)實際上有多步。A，B對x操作的過程被彼此影響，兩者都運(yùn)行完后，x

12、卻只增加了1。共享變量x應(yīng)按臨界資源處理，一個進(jìn)程還沒有用完畢前不能讓其他進(jìn)程使用但若如此異步運(yùn)行，即使有保護(hù)現(xiàn)場的處理，結(jié)果是1。7/20/202227山東農(nóng)業(yè)大學(xué)計算機(jī)系第27頁，共43頁。例2：生產(chǎn)者消費(fèi)者問題：一群生產(chǎn)者進(jìn)程生產(chǎn)產(chǎn)品供給消費(fèi)者進(jìn)程消費(fèi)，在兩者之間設(shè)置具有n個緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中，消費(fèi)者進(jìn)程可從一個緩沖區(qū)中取走產(chǎn)品去消費(fèi)。生產(chǎn)者和消費(fèi)者都以異步方式運(yùn)行，但它們之間必須保持同步：沒有產(chǎn)品不能取，沒有空間不能放。也不能同時對一個空間進(jìn)行取和放1230n-1n-2Inout7/20/202228山東農(nóng)業(yè)大學(xué)計算機(jī)系第28頁，共43頁。type

13、item=;表示一個產(chǎn)品Var n, integer;緩沖區(qū)大小counter:0, 1, , n; 緩沖區(qū)內(nèi)產(chǎn)品計數(shù)的變量var buffer: array0, 1, , n-1 of item;in, out: 0, 1, , n-1;該數(shù)組代表具有n個緩沖區(qū)的緩沖池注意：緩沖池組織為循環(huán)緩沖，in加1表示為in:=(in+1)mod nout加1表示為out:=(out+1)mod n當(dāng)(in+1)mod n=out時表示緩沖池滿in=out表示緩沖池空。使用的變量：指示生產(chǎn)者和消費(fèi)者放或取的下一個緩沖區(qū)位置指針，初值均為0。7/20/202229山東農(nóng)業(yè)大學(xué)計算機(jī)系第29頁，共43頁。

14、Producer: repeat 生產(chǎn) an item in nextp; while counter= n do no-op; bufferin:=nextp; in:=in+1 mod n; counter:=counter+1; until false;Consumer: repeat while counter= 0 do no-op; nextc:=bufferout; out:=out+1 mod n; counter:=counter-1; 消費(fèi)產(chǎn)品item in nextc; until false;空操作操作過程1230n-1n-2outIn一個生產(chǎn)者nextp一個消費(fèi)者ne

15、xtcIn交替運(yùn)行中的彼此打斷會有什么問題？Counter=17/20/202230山東農(nóng)業(yè)大學(xué)計算機(jī)系第30頁，共43頁。生產(chǎn)者和消費(fèi)者共同要影響的變量counter的獨(dú)立操作被打斷才有重要影響。設(shè)當(dāng)前持續(xù)正常運(yùn)行到counter=5bufferin:=nextp;in:=in+1 mod n;（實際緩沖區(qū)已經(jīng)有了6個產(chǎn)品）R1=counter；（5）R1=R1+1；6counter=R1（6）nextc:=bufferout;out:=out+1 mod n;R2=counter；（5）R2=R2-1；4Counter=R2（4）生產(chǎn)一個，消費(fèi)一個，還有的產(chǎn)品數(shù)應(yīng)是5。 本例順序得到結(jié)果4

16、，生產(chǎn)方會認(rèn)為還可以繼續(xù)生產(chǎn)n-4個。比實際需求的n-5多生產(chǎn)的一個必然會覆蓋一個舊產(chǎn)品。 若后兩句交換順序得到結(jié)果又是6，消費(fèi)方則會錯誤的向下多消費(fèi)一個7/20/202231山東農(nóng)業(yè)大學(xué)計算機(jī)系第31頁，共43頁。所以對生產(chǎn)者和消費(fèi)者而言，counter應(yīng)作為臨界資源，應(yīng)對其互斥訪問若是一群生產(chǎn)者和消費(fèi)者生產(chǎn)者之間共同要影響的變量in要互斥；消費(fèi)者間的out也一樣；7/20/202232山東農(nóng)業(yè)大學(xué)計算機(jī)系第32頁，共43頁?；コ猓涸诓僮飨到y(tǒng)中，當(dāng)一個進(jìn)程進(jìn)入臨界區(qū)使用臨界資源時，另一個進(jìn)程必須等待，直到占用臨界資源的進(jìn)程退出臨界區(qū)，我們稱進(jìn)程之間的這種相互制約關(guān)系為“互斥”。同步：多個相互

17、合作的進(jìn)程，在一些關(guān)鍵點上可能需要互相等待或互相交換信息，這種相互制約關(guān)系稱為進(jìn)程同步關(guān)系?？衫斫鉃椤坝行颉薄Ｈ纾荷a(chǎn)和消費(fèi)的“有序”關(guān)系靠對counter的正確判斷達(dá)到，而對counter的修改必須“互斥”修改。理解同步同步7/20/202233山東農(nóng)業(yè)大學(xué)計算機(jī)系第33頁，共43頁。3）臨界區(qū)每個進(jìn)程中訪問臨界資源的那段代碼叫臨界區(qū)。為了正確同步，對臨界區(qū)的代碼要增加控制進(jìn)程代碼分四部分：repeat critical section remainder sectionuntil false進(jìn)入?yún)^(qū)：對欲訪問的臨界資源進(jìn)行檢。若此刻未被訪問，設(shè)正在訪問的標(biāo)志臨界區(qū)：訪問臨界資源的代碼。退出區(qū)

18、：將正在訪問的標(biāo)志恢復(fù)為未被訪問的標(biāo)志剩余區(qū)：其余部分 “進(jìn)入”和“退出”臨界區(qū)的處理對實現(xiàn)互斥尤其重要entry sectionexit section7/20/202234山東農(nóng)業(yè)大學(xué)計算機(jī)系第34頁，共43頁。4）同步機(jī)制應(yīng)遵循的規(guī)則實現(xiàn)互斥的方法應(yīng)符合如下每條原則空閑讓進(jìn)：資源使用最基本原則忙則等待：保證互斥有限等待：合適時被喚醒防止死等讓權(quán)等待：能主動釋放CPU防止忙等7/20/202235山東農(nóng)業(yè)大學(xué)計算機(jī)系第35頁，共43頁。早期實現(xiàn)互斥并不容易 軟件的方法舉例：問題：兩個進(jìn)程Pi, Pj互斥訪問共享資源R算法1：設(shè)置單標(biāo)志，Pi，Pj想要操作R都要判斷共享標(biāo)志turn是否是自己

19、。其中的Pi如下：RepeatWhile turni do no-op; 操作R的代碼turn=j; (其他操作)Until false問題：Pi將turn置為j后，若j暫時不訪問R，Pi也不能訪問。不符“空閑讓進(jìn)”。7/20/202236山東農(nóng)業(yè)大學(xué)計算機(jī)系第36頁，共43頁。算法1缺點：強(qiáng)制輪流進(jìn)入臨界區(qū)，沒有考慮進(jìn)程的實際需要。算法2 ：設(shè)置多標(biāo)志（標(biāo)志數(shù)組flag） flagi表示進(jìn)程i是否在臨界區(qū)，初值均為FALSE。進(jìn)入前先檢查對方標(biāo)志。其中的Pi如下：RepeatWhile flagj do no-op;flagi=true; 操作R的代碼flagi=false; (其他操作)U

20、ntil falseflagi=F, flagj=F問題：Pi和Pj可能同時進(jìn)入臨界區(qū)。違反“忙則等待”，根本達(dá)不到互斥。源于：檢查和修改操作可能會不連續(xù)。7/20/202237山東農(nóng)業(yè)大學(xué)計算機(jī)系第37頁，共43頁。修改算法3：其中的Pi如下：Repeatflagi=true;While flagj do no-op;操作R的代碼flagi=false; (其他操作)Until falseflagi=F, flagj=F先改寫自己的狀態(tài)問題：產(chǎn)生都不能進(jìn)入的狀態(tài)。又不符合“空閑讓進(jìn)”7/20/202238山東農(nóng)業(yè)大學(xué)計算機(jī)系第38頁，共43頁。一種正確的方法算法4：先修改、后檢查、后修改者等待Repeatflagi=true; turn=j;While (flagj and turn=j) do no-op;操作R的