【文章內容簡介】 進入就緒狀態(tài) 。 2022/2/6 太湖學院信機系 48 司機 P1 While（ true） { 啟動汽車； 正常行駛； 到站停車 } 售票員 P2 While（ true） { 關門； 售票； 開門； } 2022/2/6 太湖學院信機系 49 進程的互斥（間接作用） 進程的互斥 ： mutual exclusion 由于各進程要求共享資源，而有些資源需要互斥使用，因此進程間競爭使用這些資源，進程的這種關系稱為進程的互斥。 臨界資源 ： critical resource 系統(tǒng)中某些資源一次只允許一個進程使用，稱這樣的資源為臨界資源或互斥資源或共享變量。 與時間有關的錯誤 2022/2/6 太湖學院信機系 50 臨界區(qū) （互斥區(qū)）： critical section 一個程序片段的集合，這些程序片段分散在不同的進程中，對某個共享的數(shù)據(jù)結構（共享資源）進行操作。 在進程中，涉及到臨界資源的程序片段叫臨界區(qū) ，多個進程的臨界區(qū)稱為相關臨界區(qū)。 2022/2/6 太湖學院信機系 51 i f a 0 t h e na : = a + 1 。e l s ea : = a 1 。P 3a : = a 1 。p r i n t ( a ) 。P 1P 2a : = a + 1 。p r i n t ( a ) 。互 斥進程的互斥作用（間接作用） 2022/2/6 太湖學院信機系 52 程 序 段 1 程 序 段 2共 享 變 量程 序 段 n… …2022/2/6 太湖學院信機系 53 使用臨界區(qū)的原則： ① 有空讓進 ② 無空等待 ③ 多中選一 ④ 有限等待 ⑤ 讓權等待 2022/2/6 太湖學院信機系 54 前提：任何進程無權停止其它進程的運行 進程之間相對運行速度無硬性規(guī)定 進程互斥的解決有兩種做法： ? 由競爭各方平等協(xié)商 ? 引入進程管理者由管理者來協(xié)調競爭各方對互斥資源的使用 具體的實現(xiàn)方法： 硬件（當一個進程進入臨界區(qū)就屏蔽所有中斷，成本高，并行程度會降低） 軟件（用編程解決，但常常忙等待） 2022/2/6 太湖學院信機系 55 軟件方法 1 free：表示臨界區(qū)的標志 true：有進程在臨界區(qū) false：無進程在臨界區(qū)（初值） … while (free)。 free=true。 臨界區(qū) free=false。 2022/2/6 太湖學院信機系 56 軟件方法 2 turn: true P進程進入臨界區(qū) false Q進程進入臨界區(qū) … P: while (not turn)。 turn=false。 Q: while (turn)。 turn=true。 臨界區(qū) 臨界區(qū) ① 交替使用 ②某進程失敗 2022/2/6 太湖學院信機系 57 例： 進程 0 … while(flag[1])。 flag[0]:=true。 flag[0]:=false。 進程 1 … while(flag[0])。 flag[1]:=true。 flag[1]:=false。 臨界區(qū) 臨界區(qū) 存在問題：可能有兩個進程同時進入臨界區(qū)，達不到互斥的效果 2022/2/6 太湖學院信機系 58 改進后： 進程 0 … flag[0]:=true。 while(flag[1])。 flag[0]:=false。 進程 1 … flag[1]:=true。 while(flag[0])。 flag[1]:=false。 臨界區(qū) 臨界區(qū) 存在問題：造成謙讓，兩個進程同時處于等待狀態(tài) 2022/2/6 太湖學院信機系 59 繼續(xù)改進： 進程 0 … flag[0]:=true。 while(flag[1]) begin flag[0]:=false。 等會； flag[0]:=true。 end flag[0]:=false。 進程 1 … flag[1]:=true。 while(flag[0]) begin flag[1]:=false。 等會； flag[1]:=true。 end flag[1]:=false。 臨界區(qū) 臨界區(qū) 2022/2/6 太湖學院信機系 60 軟件方法 3的形成： P進程 pturn=true。 while (qturn)。 pturn=false。 … Q進程 qturn=true。 while (pturn)。 qturn=false。 … pturn , qturn :初值為 false P進入臨界區(qū)的條件： pturn ∧ not qturn Q進入臨界區(qū)的條件： not pturn ∧ qturn 臨界區(qū) 臨界區(qū) 存在問題：可能造成死鎖 2022/2/6 太湖學院信機系 61 軟件方法 4（ Dekker 算法） 進程 P: pturn:= true。 while (qturn) { if (turn= =2) { pturn:=false。 while (turn= =2)。 pturn:=true。 } } turn:=2。 pturn:=false … 進程 Q: qturn:= true。 while (pturn) { if (turn= =1) { qturn:=false。 while (turn= =1)。 qturn:=true。 } } turn:=1。 qturn:=false … 在方法 3的基礎上引入 turn枚舉類型，初值可以任意設置。在這里： turn==1（ P進）， turn==2（ Q進） 臨界區(qū) 臨界區(qū) 2022/2/6 太湖學院信機系 62 軟件算法有其缺點： ?忙等待（用循環(huán)在不停地等待） ?實現(xiàn)過于復雜，需要較高的編程技巧 2022/2/6 太湖學院信機系 63 改進的 Dekker 算法（ Peterson 算法） P: pturn:=true。 turn:=2。 while (qturn amp。amp。 turn= =2)。 pturn:=false。 Q: qturn:=true。 turn:=1。 while (pturn amp。amp。 turn= =1)。 qturn:=false。 臨界區(qū) 臨界區(qū) 2022/2/6 太湖學院信機系 64 信號量及 （解決進程同步） 同步機制： ?信號量及 、管程；條件臨界域；路徑表達式等（用于集中式系統(tǒng)中） ?會合；通信順序進程；分布進程；遠程過程調用等；（適用于分布式系統(tǒng)中） 2022/2/6 太湖學院信機系 65 同步機制滿足的基本要求： ?描述能力 ?可以實現(xiàn) ?效率高 ?使用方便 2022/2/6 太湖學院信機系 66 信號量： semaphore ? 是一個數(shù)據(jù)結構 ? 定義如下： struct semaphore { int value。 pointer_PCB queue。 } ? 信號量說明： semaphore s。 2022/2/6 太湖學院信機系 67 信號量機制的提出者： ? 偉大的計算機科學家 Dijkstra，主要貢獻： ① 提出“ goto有害論” 。 ② 提出信號量和 PV原語 。 ③ 解決了有趣的“哲學家聚餐”問題 。 ④ 最短路徑算法 (SPF)的創(chuàng)造者 。 ⑤ 第一個 Algol 60編譯器的設計者和實現(xiàn)者 。 …… ? 與 D. E. Knuth并稱為我們這個時代最偉大的計算機科學家的人 2022/2/6 太湖學院信機系 68 信號量機制 1 .整型信號量 ? 是一個整型量，通過 2個原子操作 wait(s)和 signal(s)來訪問。 Wait(s): while s= 0 do noop； s:=s1。 Signal(s): s:=s+1。 P、 V 操作 （兩個原語） 2022/2/6 太湖學院信機系 69 關于信號量的問題 信號量： ? 互斥： wait與 signal在同一個進程中 ? 同步： wait與 signal在不同的進程中 信號量的物理意義： ? S0：表示可用資源的個數(shù) ? S=0：表示無資源，無等待進程 ? S0： ∣ S∣ 表示等待隊列中進程個數(shù) 2022/2/6 太湖學院信機系 70 2. 記錄型信號量 wait(S) { = 。 if ( 0 ) { 該進程狀態(tài)置為等待狀態(tài) 將該進程的 PCB插入相應的等 待隊列末尾 } } 2022/2/6 太湖學院信機系 71 signal(S) { = ++。