計(jì)算機(jī)操作系統(tǒng)課件：第4章進(jìn)程同步與通信-進(jìn)程之間的關(guān)系01

1、1第四章 進(jìn)程同步與通信2知識(shí)回顧與展開在本節(jié)課，我們學(xué)習(xí)第四章進(jìn)程同步與互斥1 進(jìn)程同步和互斥的思想2 進(jìn)程同步與互斥的軟件硬件解決方法3 信號(hào)量機(jī)制與P/V原語4 經(jīng)典進(jìn)程的同步問題3教學(xué)目的和要求了解同步互斥問題的原因掌握臨界區(qū)和信號(hào)量概念掌握解決簡(jiǎn)單同步互斥問題的信號(hào)量方法重點(diǎn)臨界區(qū)和信號(hào)量概念難點(diǎn)應(yīng)用信號(hào)量解決同步互斥問題2.4 進(jìn)程同步與互斥4進(jìn)程的互斥與同步在多道程序系統(tǒng)中，由于資源共享或進(jìn)程合作，使進(jìn)程間形成間接相互制約和直接相互制約關(guān)系。這種相互依賴、相互合作又相互競(jìng)爭(zhēng)的關(guān)系，意味著進(jìn)程間需要用某種形式的通信來實(shí)現(xiàn)，主要表現(xiàn)為進(jìn)程互斥與同步兩方面。5進(jìn)程同步（相互合作關(guān)系）：

2、直接制約：“進(jìn)程進(jìn)程” 進(jìn)行協(xié)作等待來自其他進(jìn)程的信息，否則就進(jìn)行不下去，“同步”。概念：指系統(tǒng)中多個(gè)進(jìn)程中發(fā)生的事件存在某種時(shí)序關(guān)系，必須協(xié)同動(dòng)作，相互配合，從而共同完成一項(xiàng)任務(wù)。一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待（阻塞）狀態(tài)，獲得消息后被喚醒進(jìn)入就緒狀態(tài)。進(jìn)程間的關(guān)系（一）6接收進(jìn)程必須等待發(fā)送進(jìn)程發(fā)送信件。電子郵件信箱發(fā)送進(jìn)程 A接收進(jìn)程 B12n例 1:7例 2:X = fun1(y)*fun2(Z)計(jì)算fun1(y)進(jìn)程p2算完fun2(Z)?取用P2計(jì)算結(jié)果計(jì)算fun2(Z)設(shè)置計(jì)算完成標(biāo)志終 止YN進(jìn)程P1進(jìn)程P2 兩個(gè)協(xié)同工作進(jìn)

3、程的同步8進(jìn)程互斥：間接制約：“進(jìn)程資源進(jìn)程” 進(jìn)行競(jìng)爭(zhēng)獨(dú)占分配到的部分或全部共享資源，等待釋放后才能使用，“互斥”。概念：有些資源需要互斥使用，因此各進(jìn)程間要相互競(jìng)爭(zhēng)，以使用這些互斥資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥。 解決進(jìn)程互斥有兩種辦法： 1.由競(jìng)爭(zhēng)各方平等協(xié)商。 2.引入進(jìn)程管理者，由管理者來協(xié)調(diào)競(jìng)爭(zhēng)各方對(duì)互斥資源的使用。進(jìn)程間的關(guān)系（二）9例 3:公共地段交通十字路口的控制：公共地段互斥10 系統(tǒng)中某些軟件或者硬件資源在同一時(shí)刻只允許被一個(gè)進(jìn)程訪問，稱這樣的資源為臨界資源 或互斥資源 或共享變量。 如：外設(shè)（打印機(jī)、磁帶機(jī)、繪圖儀等）、共享代碼段、共享數(shù)據(jù)結(jié)構(gòu)等。臨界資源11共享變量

4、的修改沖突例如：有兩個(gè)進(jìn)程A和B，它們共享一個(gè)變量x，且兩 個(gè)進(jìn)程按以下方式對(duì)變量x進(jìn)行訪問和修改。 A：R1 = x； R1 = R1 + 1； x = R1; B：R2 = x； R2 = R2 + 1； x = R2; 兩個(gè)進(jìn)程各自對(duì)x作了加1操作，x增加2。12共享變量的修改沖突如果按照另一種順序?qū)ψ兞縳進(jìn)行修改：A：R1 = x；B：R2 = x；A：R1 = R1 + 1； x = R1;B：R2 = R2 + 1； x = R2;雖然兩個(gè)進(jìn)程各自對(duì)x作了加1操作。但x卻只增1。為了防止這種錯(cuò)誤發(fā)生，應(yīng)把變量x作為臨界資源處理，即讓兩個(gè)進(jìn)程順序互斥地使用變量x。13互斥：指多個(gè)進(jìn)程

5、不能同時(shí)使用同一個(gè)資源。 是正確使用資源的基本要求。死鎖： 指多個(gè)進(jìn)程互不相讓，都得不到足夠的 資源。饑餓： 指一些進(jìn)程一直得不到資源或得到資源 的概率很小。 系統(tǒng)中資源的共享程度14臨界區(qū)的訪問過程（進(jìn)程對(duì)臨界資源的訪問過程）進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)不論是硬件臨界資源，還是軟件臨界資源，多個(gè)進(jìn)程必須互斥地對(duì)它進(jìn)行訪問。15進(jìn)入?yún)^(qū)(entry section)檢查當(dāng)前進(jìn)程可否進(jìn)入臨界區(qū)的一段代碼。如果當(dāng)前進(jìn)程可以進(jìn)入臨界區(qū)，通常設(shè)置相應(yīng)“正在訪問臨界區(qū)”標(biāo)志，防止其他進(jìn)程同時(shí)進(jìn)入臨界區(qū)。臨界區(qū)(critical section)進(jìn)程中訪問臨界資源的一段代碼。退出區(qū)(exit section)用

6、于將“正在訪問臨界區(qū)”的進(jìn)程的標(biāo)志清除。剩余區(qū)(remainder section)代碼中的其余部分。臨界區(qū)的訪問過程16進(jìn)程同步機(jī)制應(yīng)遵循的準(zhǔn)則空閑讓進(jìn)： 當(dāng)無進(jìn)程處于臨界區(qū)時(shí)，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立刻進(jìn)入自己的臨界區(qū)，以有效地利用資源。忙則等待： 當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，表明臨界資源正在被訪問，因此其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對(duì)臨界資源的互斥訪問。有限等待： 等待進(jìn)入臨界區(qū)的進(jìn)程不能無限期死等；讓權(quán)等待： 在進(jìn)入?yún)^(qū)等待而不能進(jìn)入臨界區(qū)的進(jìn)程應(yīng)釋放處理機(jī)，給其它進(jìn)程用,并將自己轉(zhuǎn)換到阻塞狀態(tài)，。17進(jìn)程互斥和同步的解決方法軟件方法硬件方法信號(hào)量

7、方法18進(jìn)程互斥的軟件方法通過平等協(xié)商方式實(shí)現(xiàn)進(jìn)程互斥的最初方法是軟件方法。軟件方法基本思路： 在進(jìn)入?yún)^(qū)先設(shè)置一些標(biāo)志和循環(huán)，確定是否已有進(jìn)程在臨界區(qū)訪問臨界資源。 如果有，則該進(jìn)程在進(jìn)入?yún)^(qū)進(jìn)行等待； 如果沒有，則該進(jìn)程進(jìn)入臨界區(qū)訪問臨界資源，最后還要在退出區(qū)修改該進(jìn)程的標(biāo)志。其中的主要問題： 設(shè)置什么標(biāo)志和如何循環(huán)檢查標(biāo)志。19進(jìn)程互斥的軟件方法有兩個(gè)進(jìn)程Pi和Pj，實(shí)現(xiàn)互斥訪問同一個(gè)臨界資源設(shè)立一個(gè)公用整型變量 turn：描述允許進(jìn)入臨界區(qū)的進(jìn)程編號(hào)（i或j）。算法1：?jiǎn)螛?biāo)志實(shí)現(xiàn)過程：在進(jìn)入?yún)^(qū)循環(huán)檢查是否允許本進(jìn)程進(jìn)入： 當(dāng)turn為i時(shí)，進(jìn)程Pi可進(jìn)入臨界區(qū)；在退出區(qū)修改允許下一次訪問臨

8、界區(qū)的進(jìn)程標(biāo)識(shí)： 當(dāng)進(jìn)程Pi退出時(shí)，改turn為進(jìn)程Pj的標(biāo)識(shí)j；20進(jìn)程互斥的軟件方法有兩個(gè)進(jìn)程Pi, Pj，設(shè)立一個(gè)公用整型變量 turn：描述允許進(jìn)入臨界區(qū)的進(jìn)程編號(hào)。算法1：?jiǎn)螛?biāo)志21缺點(diǎn)：強(qiáng)制進(jìn)程輪流進(jìn)入臨界區(qū)，沒有考慮進(jìn)程的實(shí)際需要，容易造成資源利用不充分。（在Pi出讓臨界區(qū)之后，Pj使用臨界區(qū)之前，Pi不能再次使用臨界區(qū)。）算法1：?jiǎn)螛?biāo)志22算法2：雙標(biāo)志、先檢查后修改設(shè)立兩個(gè)標(biāo)志flagi和flagj ： 描述是否有進(jìn)程在臨界區(qū)，初值均為false(未 使用臨界資源)。實(shí)現(xiàn)過程：先檢查，后修改： 在進(jìn)入?yún)^(qū)檢查另一個(gè)進(jìn)程是否在臨界區(qū)，不在時(shí)修改本進(jìn)程在臨界區(qū)的標(biāo)志為true；在退

9、出區(qū)修改本進(jìn)程在臨界區(qū)的標(biāo)志為false；23算法2：雙標(biāo)志、先檢查后修改設(shè)立兩個(gè)標(biāo)志flagi和flagj ： 描述是否有進(jìn)程在臨界區(qū)，初值均為false(未使用臨界資源)。24優(yōu)點(diǎn)：不用強(qiáng)制進(jìn)程交替進(jìn)入臨界區(qū)，進(jìn)程可連續(xù)訪問臨界區(qū)。算法2：雙標(biāo)志、先檢查后修改缺點(diǎn)：Pi和Pj可能同時(shí)進(jìn)入臨界區(qū)。 按下面序列執(zhí)行時(shí)，會(huì)同時(shí)進(jìn)入： “Pi， Pj， Pi， Pj”。即在檢查對(duì)方flag之后和修改自己flag之前有一段時(shí)間，結(jié)果雙方都檢查通過。 問題出在：檢查和修改操作不能連續(xù)進(jìn)行25算法3：雙標(biāo)志、先修改后檢查類似于算法2，與算法2的區(qū)別在于： 先修改后檢查；flag 表示進(jìn)程是否想進(jìn)入臨界區(qū)

10、。26缺點(diǎn)：Pi和Pj可能都進(jìn)入不了臨界區(qū) 按下面序列執(zhí)行時(shí)，會(huì)都進(jìn)不了臨界區(qū)： “Pi，Pj，Pi，Pj” 即在切換自己flag之后和檢查對(duì)方flag之前有一段時(shí)間，結(jié)果都切換flag，結(jié)果都檢查不通過。優(yōu)點(diǎn)：可防止兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)，保證對(duì)臨界資源的互斥訪問。算法3：雙標(biāo)志、先修改后檢查27算法4:先修改、后檢查、后修改者等待結(jié)合算法1和算法3，是實(shí)現(xiàn)互斥訪問的正確算法。turn描述標(biāo)志修改的先后，flag表示否想進(jìn)入臨界區(qū)。實(shí)現(xiàn)過程： 在進(jìn)入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后。實(shí)現(xiàn)了：空閑則入、忙則等待。檢查對(duì)方flag: 如果對(duì)方不想進(jìn)入臨界區(qū)，則自己進(jìn)入“空閑則入”。否則再檢查

11、turn： turn中保存的是較晚的一次賦值。則較晚的進(jìn)程等待，較早的進(jìn)程進(jìn)入先到先入，后到等待。28算法4:先修改、后檢查、后修改者等待turn描述標(biāo)志修改的先后，flag表示否想進(jìn)入臨界區(qū)。29在進(jìn)入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后。實(shí)現(xiàn)了：空閑則入、忙則等待。檢查對(duì)方flag: 如果對(duì)方不想進(jìn)入臨界區(qū)，則自己進(jìn)入 “空閑則入”。否則再檢查turn： turn中保存的是較晚的一次賦值。則較晚的進(jìn)程等待，較早的進(jìn)程進(jìn)入 先到先入，后到等待。算法4:先修改、后檢查、后修改者等待30進(jìn)程互斥的軟件實(shí)現(xiàn) 軟件實(shí)現(xiàn)方法中： 兩個(gè)和三個(gè)以上進(jìn)程間的互斥的進(jìn)入?yún)^(qū)要區(qū)別對(duì)待。 不適合進(jìn)程較多的進(jìn)程間的

12、互斥。 現(xiàn)在已很少單獨(dú)采用軟件方法。在平等協(xié)商時(shí)利用某些硬件指令來實(shí)現(xiàn)進(jìn)程互斥。 最主要的問題：修改和檢查標(biāo)志不能作為一個(gè)整體被執(zhí)行。31進(jìn)程互斥的硬件方法 硬件方法基本思路： 用一條指令完成讀和寫兩種操作，因而保證讀操作與寫操作不被打斷。 分類： 依據(jù)所采用的指令不同，分為兩種： 1。TS 指令 2。Swap 指令32進(jìn)程互斥的硬件方法Test-and-Set指令TS指令功能：讀出指定標(biāo)志后將其設(shè)為TRUE。boolean TS (boolean *lock) boolean old; old = *lock; *lock = TRUE; return old;公共布爾變量lock表示資源的

13、兩種狀態(tài)。（TRUE表示正被占用，F(xiàn)ALSE表示空閑。）33利用TS實(shí)現(xiàn)進(jìn)程互斥： - 每個(gè)臨界資源設(shè)置一個(gè)公共布爾變量lock，初值為false。 lock=false,表示臨界資源空閑； lock=true,表示臨界資源正在被使用。 在進(jìn)入?yún)^(qū)利用TS進(jìn)行檢查： - 有其它進(jìn)程在臨界區(qū)時(shí)，即lock=true，則重復(fù)循環(huán)檢查； - 直到其它進(jìn)程退出臨界區(qū)時(shí)，即lock=false,循環(huán)檢查通過，當(dāng)前進(jìn)程才可以訪問臨界區(qū)?；コ馑惴ǎ═S指令）Test-and-Set指令34進(jìn)程互斥的硬件方法Test-and-Set指令TS指令功能：讀出指定標(biāo)志后將其設(shè)為TRUE。boolean TS (boo

14、lean lock) boolean old; old = lock; lock = TRUE; return old;公共布爾變量lock表示資源的兩種狀態(tài)。（TRUE表示正被占用，F(xiàn)ALSE表示空閑。）35互斥算法（TS指令）所有訪問臨界資源的進(jìn)程的 進(jìn)入?yún)^(qū)代碼和退出區(qū)代碼相同。36Swap指令（交換指令）利用Swap指令實(shí)現(xiàn)進(jìn)程互斥： -每個(gè)臨界資源設(shè)置一個(gè)公共布爾變量lock，初值為FALSE。 -每個(gè)進(jìn)程設(shè)置一個(gè)私有布爾變量key，用于與lock 進(jìn)行信息交換。在進(jìn)入?yún)^(qū)交換lock和key的值，然后檢查 key的狀態(tài)； -有進(jìn)程在臨界區(qū)時(shí)，即lock=true重復(fù)交換和檢查過程； -直到其他進(jìn)程退出時(shí)，即lock=false通過檢查。37void SWAP(int *a, int *b) int temp; temp = *a; *a = *b; *b = temp;Swap指令的功能：交換兩個(gè)字（字節(jié)）的內(nèi)容。Swap指令（交換指令）38互斥算法（Swap指令）39硬件方法的優(yōu)點(diǎn)：適用范圍廣： 適用于任意數(shù)目的進(jìn)程，在單處理器或多處理器上完全相同。簡(jiǎn)單： 標(biāo)志設(shè)置簡(jiǎn)單，含義明確，容易驗(yàn)證其正確性。支持多個(gè)臨界區(qū)： 一個(gè)進(jìn)程在多個(gè)臨界區(qū)時(shí)，只需為每個(gè)臨界區(qū)設(shè)立一個(gè)布爾變量。40硬件方法的缺點(diǎn)：不能實(shí)現(xiàn)“讓權(quán)等待”。 進(jìn)程在進(jìn)入?yún)^(qū)等待進(jìn)入臨界區(qū)時(shí)，要耗