【正文】 值為 0 (3) 私用信號(hào)量 Sn， 用以表示可用緩沖區(qū)數(shù) ， 初值為 n 。 P, R: integer。 p∶ =R∶ =0 S∶ =1。 S 0∶ =0。 P(S n)。 B［ P］ ∶ =product。 V(S 0)。 process consumer j(j=1, 2, …, k) begin L2: P(S0)。 take a product from B［ R］ 。 V(S n)。 consume go to L2 end coend。 第三章 進(jìn)程管理 5. 讀者與寫者問題 (Reader Writer Problems) 為了實(shí)現(xiàn)讀者與寫者的同步和互斥 ， 我們?cè)O(shè)置一個(gè)信號(hào)量 S， 用于讀者與寫者之間或?qū)懻吲c寫者之間的互斥 ， 初值為“ 1”。 故必須定義另一個(gè)用于互斥的信號(hào)量 Sr， 初值也是 “ 1”。 rc: integer。 rc∶ =0。 rc∶ =rc+1。 V(Sr)。 P(Sr) rc∶ =rc1。 V(Sr) end process Writer j(j=1, 2, …, k) 第三章 進(jìn)程管理 begin P(S)。 V(S) end。 end 第三章 進(jìn)程管理 在這個(gè)程序中 ， 當(dāng)有進(jìn)程在讀而使一個(gè)請(qǐng)求寫的進(jìn)程阻塞時(shí) ， 如果仍有進(jìn)程不斷地請(qǐng)求讀則寫進(jìn)程將被長期地推遲運(yùn)行 。 即當(dāng)有進(jìn)程在讀文件時(shí) ， 如果有進(jìn)程請(qǐng)求寫 ， 那么新的讀者被拒絕 ， 待現(xiàn)有讀者完成讀操作后立即讓寫者運(yùn)行 ， 只當(dāng)無寫者工作時(shí)才讓讀者工作 。 其中信號(hào)量 S，初值為 1， 用于讀者與寫者或?qū)懻吲c寫者之間的互斥 ， 另一信號(hào)量 Sn， 初值為 n, 表示系統(tǒng)中最多有 n個(gè)進(jìn)程可同時(shí)進(jìn)行讀操作： 第三章 進(jìn)程管理 Begin S, Sn: Semaphore。 Sn=n。 P(Sn)。 read file F。 process Writer j(j=1, 2, …, k) 第三章 進(jìn)程管理 begin P(S) for i∶ =1 to n do P(Sn)。 for i∶ =1 to n do V(Sn)。 coend。 第三章 進(jìn)程管理 高級(jí)通訊原語 1. 消息緩沖區(qū)作為進(jìn)程間通訊的一個(gè)基本單位 。 由于接收進(jìn)程可能會(huì)收到幾個(gè)進(jìn)程發(fā)來的消息 ， 故應(yīng)將所有的消息緩沖區(qū)鏈成一個(gè)隊(duì)列 ，其隊(duì)頭由接收進(jìn)程 PCB中的隊(duì)列隊(duì)首指針 mq來指出 。 1) 信箱通訊過程 圖 信箱頭格子1進(jìn)程 A 進(jìn)程 B格子2格子3?發(fā)送信件接收回答接收信件發(fā)送回答第三章 進(jìn)程管理 2) 信箱是一種數(shù)據(jù)結(jié)構(gòu) ， 邏輯上可分為兩部分：信箱頭和信箱體 。 信箱頭包括如下信 信箱名： boxname。 已存信件數(shù)： mesnum。 第三章 進(jìn)程管理 信箱名 ： b o x n a m e信箱大小 ： b o x s i z e已存信件數(shù) ： m e s n u m空格子數(shù) ： fr o m n u m滿 信件滿 信件滿 信件空 格子? ?空 格子圖 3.16 信箱的數(shù)據(jù)結(jié)構(gòu) 第三章 進(jìn)程管理 進(jìn)程調(diào)用 send原語發(fā)送信件前 ， 必須事先組織好信件 ， 然后再調(diào)用 send原語并在調(diào)用時(shí)給出參數(shù)：信箱名和信件內(nèi)容或信件存放地址 。 由此 ， send和 receive原語格 send (boxname, msg) receive (boxname, msg) 第三章 進(jìn)程管理 4) 發(fā)送原語的執(zhí)行過程是： 根據(jù) send原語中的第一個(gè)參數(shù)信箱名 ， 找到相應(yīng)的信箱 ， 若信箱有空的格子 ， 則按第二個(gè)參數(shù)指出的地址把信件送入該信箱中 ， 如果有進(jìn)程在等待該信箱中的信件 ， 則將其喚醒；若該信箱已滿 ， 則調(diào)用 send原語的進(jìn)程被阻塞并插入等信箱隊(duì)列 。 如果有進(jìn)程在等信箱 ，則將其喚醒 ， 若信箱中無信件 ， 則調(diào)用 receive原語的進(jìn)程被阻塞 ， 并插入等信件隊(duì)列 。 根據(jù) boxname P (fromnum) 把消息 msg 放入空的格子 X 置格子 X V (mesnum)。 根據(jù) boxname P (mesnum) 選擇標(biāo)志為滿的格子 X 將格子 X中的信件取出放入 msg 置格子 X V (fromnum)。 (2) 非剝奪控制 。 (4) 環(huán)路條件 。 P、 V操作是實(shí)現(xiàn)進(jìn)程間通訊的原語 ， 它能有效地實(shí)現(xiàn)進(jìn)程間的同步和互斥 ， 但由于 P、 V操作使用不當(dāng) ， 也會(huì)導(dǎo)致系統(tǒng)死鎖 。 進(jìn)程 A 進(jìn)程 B P(S1) P(S2) r1: P(S2) r2: P(S1) … … … … 第三章 進(jìn)程管理 例 2 存儲(chǔ)器共享的死鎖。若每個(gè)進(jìn)程都要求 i個(gè)存儲(chǔ)單位 ， 當(dāng) mni時(shí)就可能發(fā)生死鎖 。 當(dāng) m=2, n=3, i=2 時(shí) ， P P2 第一次請(qǐng)求就把存儲(chǔ)器分配完了 ， P3 在第一次請(qǐng)求后就處于阻塞狀態(tài) ， 當(dāng) P P2 第二次請(qǐng)求時(shí)紛紛進(jìn)入阻塞狀態(tài) 。 在加鎖法中，我們用加鎖 LOCK (W)和開鎖 UNLOCK(W)實(shí)現(xiàn)進(jìn)程的互斥控制。 一般把系統(tǒng)中的資源分為兩類：一類稱為可逐次再使用資源 ， 也稱做永久性資源 ， 記以 SR， 它可供進(jìn)程逐次使用 ，例如處理機(jī) 、 主存 、 I/O設(shè)備等 ， 都是永久性資源 。 例如進(jìn)程間同步時(shí)交換的信息 、 數(shù)據(jù)文件等 。 進(jìn)程 P3產(chǎn)生信息 S3， 而要求從 P2 接收信息 S2。 P2: 釋放 S2, 請(qǐng)求 S1。 則不會(huì)出現(xiàn)死鎖。 P2: 請(qǐng)求 S1, 釋放 S2。 則必然出現(xiàn)死鎖。 r1r2r3r4r5P3P1P2P4P5第三章 進(jìn)程管理 begin S1， S2, S3, S4, S5: semaphore。 hungry。 pickup ri。 第三章 進(jìn)程管理 pickup r i+1 。 putdown r i。 V(S i)。 go to Li end。 hungry。 第三章 進(jìn)程管理 pickup r 5。 pickup r 1。 putdown r 5。 V(S 5)。 go to L5 end。 end 第三章 進(jìn)程管理 對(duì)死鎖采取的對(duì)策 (1) 鴕鳥策略。 (3) 避免策略。 第三章 進(jìn)程管理 死鎖的預(yù)防 (1)資源靜態(tài)分配法。 這種方法的基本思想是對(duì)系統(tǒng)的全部資源加以全局編號(hào)： ＃ 1: ＃ 2： ＃ 3： ＃ 4： ＃ 5： 然后規(guī)定一條規(guī)則： 進(jìn)程任何時(shí)候都能夠申請(qǐng)資源， 不過所有的申請(qǐng)必須按編號(hào)增加的順序進(jìn)行。 假定 A、 B、 C已分別占用了 2 臺(tái) 、 3 臺(tái) 、 3 臺(tái) ， 它們的最大需求量分別為 4 臺(tái) 、 6 臺(tái) 、 8 臺(tái) 。 進(jìn)程名 已分配數(shù) 尚需申請(qǐng)數(shù) 最大需求數(shù) A B C 2 3 3 2 3 5 4 6 8 第三章 進(jìn)程管理 入口清所有進(jìn)程“能運(yùn)行完”標(biāo)志對(duì)申請(qǐng)者預(yù)分配系統(tǒng)剩余資源數(shù)與“能執(zhí)行完”標(biāo)志為0 的進(jìn)程尚需資源數(shù)比較，找出一個(gè)系統(tǒng)能滿足要求的進(jìn)程檢查是否有“能運(yùn)行完”標(biāo)志尚未設(shè)置的進(jìn)程設(shè)置該進(jìn)程“能運(yùn)行完”標(biāo)志并假設(shè)它歸還全部資源分配不安全不能分配分配安全進(jìn)行實(shí)際分配有？找到？YYNN圖 3.23單項(xiàng)資源的銀行家算法 第三章 進(jìn)程管理 2. 現(xiàn)在考慮多種資源的銀行家算法 。 各類資源的總數(shù)用 W=(6, 3, 4, 2)表示 ， 即有 6 臺(tái)磁帶驅(qū)動(dòng)器 ， 3 臺(tái)繪圖儀 ， 4 臺(tái)打印機(jī) ， 2 臺(tái)卡片穿孔機(jī) 。 倘若不存在這樣的向量 ， 就說明沒有進(jìn)程能夠獲得全部資源運(yùn)行到完成 ， (3) 假設(shè)被選到的那一行的進(jìn)程獲得了全部資源而運(yùn)行到結(jié)束 ， 則設(shè)置該進(jìn)程 “ 能運(yùn)行完 ” 標(biāo)志 ， 并把它的資源全部加入向量 S； (4) 重復(fù)步驟 (2)和 (3)， 直到下述情況之一出現(xiàn)：或者所有進(jìn)程都設(shè)置 “ 能運(yùn)行完 ” 標(biāo)志 ， 則系統(tǒng)是安全的 ， 可以進(jìn)行實(shí)際分配；或者發(fā)生死鎖 ， 則預(yù)先分配是不安全的 ， 應(yīng)予以撤消 。 圖 表示了一個(gè)極為簡(jiǎn)單的狀態(tài)圖 (σ， π)， 其中 σ={S, T, U, V}, π={P1, P2}。 圖 S U 1 S U 2 U V 1 S T 1 等狀態(tài)變化。 第三章 進(jìn)程管理 由圖 中可以看出 P1(S)={T、 U} P1(T)=Ω P1(U)={V} P2(S)={U} P2(T)={S、 V} P2(V)=Ω 其中 Ω表示無意義。 顯然它可以包括： * 第三章 進(jìn)程管理 (3) 一個(gè)進(jìn)程 Pi在狀態(tài) S是阻塞的 ， 是指不存在狀態(tài) T， 使得 S→T ， 即進(jìn)程 Pi在那個(gè)狀態(tài)下不能執(zhí)行任何操作 。 換句話說 ， 進(jìn)程 Pi在狀態(tài) S是死鎖的 ， 必定是它在狀態(tài) S以及由它可能到達(dá)的所有未來狀態(tài) T都是阻塞的 。 同樣 ， P2 在狀態(tài) V也是死鎖的 。按此定義 ， 只要設(shè)法使系統(tǒng)每一可能到達(dá)的狀態(tài)都限制在非死鎖狀態(tài) ， 就可避免死鎖 。 第三章 進(jìn)程管理 2. 進(jìn)程 — 資源圖 以下給出進(jìn)程 —資源圖的形式定義和限制 。 另一個(gè)是資源結(jié)點(diǎn)子集 ， ρ={R1, R2, …, Rn}，N=ρ∪ π。 在圖 中 ， ρ={R}, π={P1, P2, P3, P4}, N={R}∪ {P1, P2, P3, P4}。 若 e=(Pi, Rj)， 則 e稱為一條資源請(qǐng)求邊 ， 由進(jìn)程 Pi指向資源 Rj， 它表示進(jìn)程 Pi請(qǐng)求一個(gè)單位的Rj資源 (即 Rj的一個(gè)部件 )。 圖 中存在兩條請(qǐng)求邊和兩條分配邊： E={(A, R2), (B, R1), (R1, A), (R2, B)}。 第三章 進(jìn)程管理 死鎖的檢測(cè) 1. 一個(gè)處于非阻塞的進(jìn)程要想達(dá)到運(yùn)行的終點(diǎn) ， 它應(yīng)獲得所需的全部資源 ， 然后釋放這些資源 。 繼續(xù)這種推斷過程 ， 直到系統(tǒng)中的狀態(tài)不再發(fā)生變化為止 。 照此可以斷言：對(duì)于前一種結(jié)局 ， 過程的初始狀態(tài)必定是一個(gè)死鎖狀態(tài)；而對(duì)于后一種結(jié)局 ， 過程的初始狀態(tài)必定不是死鎖狀態(tài) 。 由于 Pi是非阻塞進(jìn)程 ， 它對(duì)某類資源 Rj的請(qǐng)求 ， 應(yīng)滿足 ? ??kjjj WPkRRPi ),(),(第三章 進(jìn)程管理 圖 進(jìn)程 — 資源圖的化簡(jiǎn) P1R1R2（ a ）P1R1R2（ b ）P1P2R1R2（ c ）P2 P2