【正文】 運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息 ,在未獲得消息之前 ,該進(jìn)程處于等待狀態(tài) ,獲得消息后 ,被喚醒進(jìn)入就緒態(tài) . 第三章 進(jìn) 程 管 理 2020/11/17 63 例 : 司機(jī) (P1) 售票員 (P2) While(true) { 啟動(dòng)車輛 正常運(yùn)行 到站停車 } While(true) { 關(guān)門 售票 開門 } 第三章 進(jìn) 程 管 理 2020/11/17 64 同步的例子 : 1. 矩陣運(yùn)算 A+B 進(jìn)程甲 :負(fù)責(zé)輸入 A矩陣 進(jìn)程乙 :負(fù)責(zé)輸入 B矩陣 ,并計(jì)算 A+B S=0 輸 入 A 輸 入 B P(s) V(s) 慢 。 P(S1)。 V(S2)。 從緩沖區(qū)中取產(chǎn)品 。 消費(fèi)產(chǎn)品 。 While (true) { 生產(chǎn)產(chǎn)品 。 往 Buffer[i]放產(chǎn)品 V(S2)。 } j=0。 從 Buffer[j]中取產(chǎn)品 。 消費(fèi)產(chǎn)品 。 } 此例所關(guān)注的問(wèn)題 1. 生產(chǎn)的產(chǎn)品放在緩沖區(qū)的哪個(gè)位置上去 . S1 S2 =n =0 2. 初值 第三章 進(jìn) 程 管 理 2020/11/17 70 思考題 :要不要對(duì)緩沖區(qū) (臨界資源 )進(jìn)程互斥操作 ? 生產(chǎn)者 消費(fèi)者的歸類 ① 單一資源的生產(chǎn)者 消費(fèi)者 S1 S2 =1 =0 S1 S2 =n =0 S2 =0 ② 有限資源的生產(chǎn)者 消費(fèi)者 ③ 無(wú)限資源的生產(chǎn)者 消費(fèi)者 第三章 進(jìn) 程 管 理 2020/11/17 71 4. ∞ 個(gè) 緩沖區(qū)的生產(chǎn)者－消費(fèi)者問(wèn)題 P: Q: i=0。 P(S1)。 i=(i+1) % n。 While (true) { P(S2)。 V(S1)。 j=(j+1) % n。 While (true) { 生產(chǎn)產(chǎn)品 。 P(mutex) 往 Buffer[i]放產(chǎn)品 V(mutex) V(S2)。 } j=0。 P(mutex) 從 Buffer[j]中取產(chǎn)品 。 消費(fèi)產(chǎn)品 。 } S2= mutex= S1= n 0 1 第三章 進(jìn) 程 管 理 2020/11/17 73 [注意 :] 互斥信號(hào)量使用不當(dāng) ,會(huì)產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤 ① P操作的順序非常重要 (如顛倒兩個(gè) P操作的順序 ) ② 對(duì)臨界區(qū) (倉(cāng)庫(kù) )使用不當(dāng) P: Q: i=0。 P(S1)。 i=(i+1) % n。 While (true) { P(mutex)。 從 Buffer[j]中取產(chǎn)品 。 消費(fèi)產(chǎn)品 。 } 第三章 進(jìn) 程 管 理 2020/11/17 74 [解決辦法 :] 引入兩個(gè)互斥信號(hào)量 : mutex1 mutex2 =1 =1 P: Q: i=0。 P(S1)。 往 Buffer[i]放產(chǎn)品 。 V(mutex1) V(S2)。 While (true) { P(S2)。 j=(j+1) % n。 V(S1)。 } ① 生產(chǎn)者所關(guān)心的 ② 消費(fèi)者所關(guān)心的 ①② : 說(shuō)明他們針對(duì)的臨界資源是不一樣的 ,完全可以把他們劃分開來(lái) 第三章 進(jìn) 程 管 理 2020/11/17 75 ① S0:S表示可用資源的個(gè)數(shù) . ② S=0:S表示無(wú)資源使用 ,也無(wú)等待進(jìn)程 . ③ S0: 表示等待隊(duì)列中進(jìn)程的個(gè)數(shù) S [ :] 1. 信號(hào)量的物理意義 P(S):表示申請(qǐng)或使用一個(gè)資源 .因此 S=S1。 信號(hào)量的初值應(yīng)該大于等于 0 說(shuō)明 : 2. ,有一個(gè) P操作就一定有一個(gè) V操作 ① 當(dāng)為互斥操作時(shí) ,它們處于同一進(jìn)程 . ② 當(dāng)為同步操作時(shí) ,則不在同一進(jìn)程 . ③ 如果 P(S1)和 P(S2)兩個(gè)操作在一起 ,那么 P操作的順序至關(guān)重要 ,一個(gè)同步 P操作與一個(gè)互斥 P操作在一起時(shí) ,同步 P操作在互斥 P操作前 ,而兩個(gè) V操作無(wú)關(guān)緊要 . 第三章 進(jìn) 程 管 理 2020/11/17 76 3. 優(yōu)點(diǎn) :簡(jiǎn)單 ,而且表達(dá)能力強(qiáng) (用 ) ① 不夠安全 . ② . ③ 遇到復(fù)雜同步互斥問(wèn)題時(shí)實(shí)現(xiàn)復(fù)雜 缺點(diǎn) : 第三章 進(jìn) 程 管 理 2020/11/17 77 例 : 有一個(gè)充分大的池子 ,兩個(gè)人分別向池子里扔球 ,甲扔 紅 球 ,乙扔 蘭 球 , 一次扔一個(gè) .開始時(shí)池子里有 紅 、 蘭 球各一個(gè)。開始時(shí)池子里有 紅 、 蘭、 綠 球各一個(gè)。 P(b2)。 V(r) V(r) V(g) 要求池子里球滿足條件： ① 蘭 ≤ 紅＋蘭 綠 ≤ ② 扔蘭球者 ... P(g) 扔一個(gè)綠球 V(b2) r= b1= g= b2= 說(shuō)明： b1表明蘭球受到紅球的制約， b2表明蘭球受到綠球的制約 1 0 1 0 第三章 進(jìn) 程 管 理 2020/11/17 79 例 : 有一倉(cāng)庫(kù)，可以存放 A和 B兩種產(chǎn)品。 int a=M1。 main() { while(true) { 取一個(gè)產(chǎn)品； if (A) { P(a)。 將產(chǎn)品入庫(kù)； v(mutex)。 } else { P(b)。 將產(chǎn)品入庫(kù)； v(mutex)。 } } } 第三章 進(jìn) 程 管 理 2020/11/17 80 第二類經(jīng)典的同步問(wèn)題 ：有兩組并發(fā)進(jìn)程：讀者和寫著共享一組數(shù)據(jù)區(qū)。 ? 有寫者寫，新讀者等。 ? 有讀者，新寫者等待。 第三章 進(jìn) 程 管 理 2020/11/17 81 寫進(jìn)程 ... P(Wrt)。 讀進(jìn)程 ... P(Wrt)； 讀； V(Wrt)。 readcount++。 V(mutex)。 readcount 。 V(mutex)。 寫； V(w)。每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉。 為防止死鎖發(fā)生可采取的措施： ? 最多允許 4個(gè)哲學(xué)家同時(shí)坐在桌子周圍 ? 僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子。 為了避免死鎖，把哲學(xué)家分成三種狀態(tài)：思考、饑餓、進(jìn) 食。 第三章 進(jìn) 程 管 理 2020/11/17 84 哲學(xué)家就餐問(wèn)題解法 define N 5 define THINKING 0 define HUNGRY 1 define EATING 2 typedef int semaphore Int state[N]。 Semaphpre S[N]。amp。amp。 v(amp。 } } 第三章 進(jìn) 程 管 理 2020/11/17 85 Void philosopher(int i) { while(true) { 思考； p(amp。 state[i]=HUNGRY。 v(amp。 p(amp。 拿左叉子； 拿右叉子； 吃飯； 放左叉子； 放右叉子； P(amp。 state[i]=THINKING。 test([i+1]%5)。mutex)。 s[i]=0。 要求：允許多個(gè)讀者同時(shí)執(zhí)行讀操作 不允許讀者、寫著同時(shí)操作（讀、寫互斥） 不允許多個(gè)寫者同時(shí)操作（只能一個(gè)寫） 第二類：寫者優(yōu)先策略 ? 多個(gè)讀者可以同時(shí)進(jìn)行讀。 ? 讀、寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待， 喚醒時(shí)優(yōu)先考慮寫者。 ： 1. 易讀性差。 2. 不利于修改和維護(hù)。 3. 正確性難以保證。 第三章 進(jìn) 程 管 理 2020/11/17 88 管程的定義：指關(guān)于共享資源的數(shù)據(jù)及在其上操作的一組過(guò)程或共享數(shù) 據(jù)結(jié)構(gòu)及其規(guī)定的所有操作。 管程是相應(yīng)語(yǔ)言中的一個(gè)成分。 ? 共享變量說(shuō)明； ? define 本管程內(nèi)所定義、本管程外可調(diào)用的過(guò)程（函數(shù)）名字表。 第三章 進(jìn) 程 管 理 2020/11/17 89 Procedure 過(guò)程名（形參表）； 過(guò)程局部變量說(shuō)明； BEGIN 語(yǔ)句序列； END。 BEGIN 共享變量初始化語(yǔ)句序列； END。 ② 抽象數(shù)據(jù)類型，管程是一種特殊的數(shù)據(jù)類型，其中不僅有數(shù)據(jù)，而且還有對(duì)數(shù)據(jù)進(jìn)行操作的代碼。 第三章 進(jìn) 程 管 理 2020/11/17 91 管程的 3個(gè)要素 ① 管程中的共享變量在管程外部是不可見(jiàn)的，外部只能通過(guò)調(diào)用管程中所說(shuō)的外部過(guò)程（函數(shù)）來(lái)間接地訪問(wèn)管程中的共享變量。 ③ 管程通常是用來(lái)管理資源的，因而在管程中應(yīng)當(dāng)設(shè)有進(jìn)程等待隊(duì)列以及相應(yīng)的等待和喚醒操作。 第三章 進(jìn) 程 管 理 2020/11/17 92 處理方法有三種： ① P等待， Q繼續(xù)，直到 Q退出或等待 ② Q等待， P繼續(xù)，直到 P等待或退出 ③ 規(guī)定喚醒為管程中最后一個(gè)可執(zhí)行的操作 由于管程是互斥進(jìn)入的，所以當(dāng)一個(gè)進(jìn)程試圖進(jìn)入一個(gè)已被占用的管程時(shí)，它應(yīng)當(dāng)在管程的入口處等待，因而在管程的入口處應(yīng)當(dāng)有一個(gè)進(jìn)程等待隊(duì)列，稱為入口等待隊(duì)列。如果進(jìn)程 Q在執(zhí)行時(shí)又喚醒進(jìn)程R，則 Q等待 R執(zhí)行 ...,如此，在管程內(nèi)部，由于執(zhí)行喚醒操作，可能會(huì)出現(xiàn)多個(gè)等待進(jìn)程，因而還需要有一個(gè)進(jìn)程等待隊(duì)列，這個(gè)等待隊(duì)列被稱為緊急等待隊(duì)列。 第三章 進(jìn) 程 管 理 2020/11/17 93 由于管程通常是用于管理資源的，因而在管程內(nèi)部，應(yīng)當(dāng)存在某種 等待機(jī)制。為此在管程內(nèi)部可以說(shuō)明和使用一種特殊類型的變量， 稱作條件變量。 ① Wait（ c):如果緊急等待隊(duì)列非空，則喚醒第一個(gè)等待者。 ② Signal(c):如果 C鏈為空，則相當(dāng)于空操作，執(zhí)行此操作的進(jìn)程繼續(xù)；否則喚醒第一個(gè)等待者，執(zhí)行此操作的進(jìn)程的 PCB入緊急等待隊(duì)列的尾部。 define enter,leave,wait,signal。 BEGIN P()。 第三章 進(jìn) 程 管 理 2020/11/17 96 Procedure leave(VAR instance:one_instance)。 V()。 END。VAR s: semaphore。 BEGIN count ++。 V()。 P(s)。 第三章 進(jìn) 程 管 理 2020/11/17 98 Procedure signal(VAR instance:one_instance。VAR count:integer)。 ++。 P()。