【導(dǎo)讀】執(zhí)行程序規(guī)定的動(dòng)作。每個(gè)動(dòng)作都必須在前一動(dòng)作結(jié)束后。除了人為的干預(yù)造成機(jī)器暫時(shí)停頓外，前一動(dòng)。的活動(dòng)嚴(yán)格一一對(duì)應(yīng)。程序的執(zhí)行結(jié)果與其執(zhí)行速度無(wú)關(guān)。資源共享是現(xiàn)代操作系統(tǒng)另一基本特性。指系統(tǒng)中的硬件資源和軟件資源不再為單個(gè)用戶程序所獨(dú)占，而由幾道用戶程序共同使用。于一道程序，而是由多道程序的活動(dòng)所決定。破了一道程序封閉于一個(gè)系統(tǒng)中執(zhí)行的局面。享資源進(jìn)行有效的管理，也就降低了程序并發(fā)執(zhí)行的效果。在一條單向行駛的公路。觀察者不斷觀察并對(duì)通過(guò)的卡車計(jì)數(shù)。此時(shí)我們可以寫(xiě)出如下程序，其中Cobegin和。Coend表示它們之間的程序可以并發(fā)執(zhí)行。由于觀察者和報(bào)告者各自獨(dú)立地并行工作，相互依賴和制約方面。所發(fā)生的活動(dòng)稱為進(jìn)程?？刂茐K是進(jìn)程存在的一個(gè)惟一標(biāo)志。PCB，隨之該進(jìn)程也就消亡了。進(jìn)程標(biāo)識(shí)名或標(biāo)識(shí)數(shù)。進(jìn)程現(xiàn)場(chǎng)保護(hù)區(qū)。隊(duì)列指針或鏈接字。

　　

【正文】 一般把系統(tǒng)中的資源分為兩類：一類稱為可逐次再使用資源 ， 也稱做永久性資源 ， 記以 SR， 它可供進(jìn)程逐次使用 ，例如處理機(jī) 、 主存 、 I/O設(shè)備等 ， 都是永久性資源 。 另一類資源是消耗性資源 ， 也叫做臨時(shí)性資源 ， 記以 CR， 這類資源由一進(jìn)程產(chǎn)生而被另一進(jìn)程消耗掉 ， 只能使用短暫的時(shí)間 。 例如進(jìn)程間同步時(shí)交換的信息 、 數(shù)據(jù)文件等 。 第三章 進(jìn)程管理 圖 信息傳送引起的死鎖 P1S2P3S1P2S3第三章 進(jìn)程管理 設(shè)進(jìn)程 P1 產(chǎn)生信息 S1， 而要求從 P3 接收信息 S3；進(jìn)程P2 產(chǎn)生信息 S2， 而要求從 P1 接收信息 S1。 進(jìn)程 P3產(chǎn)生信息 S3， 而要求從 P2 接收信息 S2。 P1： 釋放 S1, 請(qǐng)求 S3。 P2: 釋放 S2, 請(qǐng)求 S1。 P3: 釋放 S3, 請(qǐng)求 S2。 則不會(huì)出現(xiàn)死鎖。 第三章 進(jìn)程管理 P1: 請(qǐng)求 S3, 釋放 S1。 P2: 請(qǐng)求 S1, 釋放 S2。 P3: 請(qǐng)求 S2, 釋放 S3。 則必然出現(xiàn)死鎖。 第三章 進(jìn)程管理 圖 例 5 哲學(xué)家吃通心面問(wèn)題 (Dining Philosophers Problem)。 r1r2r3r4r5P3P1P2P4P5第三章 進(jìn)程管理 begin S1， S2, S3, S4, S5: semaphore。 S1∶ =S2∶ =S3∶ =S4∶ =S5∶ =1 Cobrgin process Pi(i=1, 2, 3, 4) begin Li: thinking。 hungry。 P(Si)。 pickup ri。 P(Si+1 )。 第三章 進(jìn)程管理 pickup r i+1 。 eating。 putdown r i。 putdown r i+1 。 V(S i)。 V(S i+1 )。 go to Li end。 process P5 begin L5: thinking。 hungry。 P(S 5)。 第三章 進(jìn)程管理 pickup r 5。 P(S 1)。 pickup r 1。 eating。 putdown r 5。 putdown r 1。 V(S 5)。 V(S 1)。 go to L5 end。 coend。 end 第三章 進(jìn)程管理 對(duì)死鎖采取的對(duì)策 (1) 鴕鳥(niǎo)策略。 (2) 預(yù)防策略。 (3) 避免策略。 (4) 檢測(cè)和解除。 第三章 進(jìn)程管理 死鎖的預(yù)防 (1)資源靜態(tài)分配法。 (2) 資源順序分配法。 這種方法的基本思想是對(duì)系統(tǒng)的全部資源加以全局編號(hào)： ＃ 1: ＃ 2： ＃ 3： ＃ 4： ＃ 5： 然后規(guī)定一條規(guī)則： 進(jìn)程任何時(shí)候都能夠申請(qǐng)資源， 不過(guò)所有的申請(qǐng)必須按編號(hào)增加的順序進(jìn)行。 第三章 進(jìn)程管理 死鎖的避免 1. 例如 ， 設(shè)系統(tǒng)中有 10 臺(tái)磁帶機(jī) ， 由三個(gè)進(jìn)程 A、 B、 C共享 。 假定 A、 B、 C已分別占用了 2 臺(tái) 、 3 臺(tái) 、 3 臺(tái) ， 它們的最大需求量分別為 4 臺(tái) 、 6 臺(tái) 、 8 臺(tái) 。 這一要求如下表所示 ，并假定只有當(dāng)滿足了最大需求量后才能釋放所占用的全部資源 。 進(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è)系統(tǒng)有四類資源：磁帶驅(qū)動(dòng)器 、 繪圖儀 、 打印機(jī)和卡片穿孔機(jī) 。 各類資源的總數(shù)用 W=(6, 3, 4, 2)表示 ， 即有 6 臺(tái)磁帶驅(qū)動(dòng)器 ， 3 臺(tái)繪圖儀 ， 4 臺(tái)打印機(jī) ， 2 臺(tái)卡片穿孔機(jī) 。 現(xiàn)有五個(gè)進(jìn)程 A、 B、 C、 D和 E， 已獲得的資源的種類及數(shù)量用矩陣 R表示： 第三章 進(jìn)程管理 進(jìn)程 磁帶驅(qū)動(dòng)器 繪圖儀 打印機(jī) 穿孔機(jī) A 3 0 1 1 B 0 1 0 0 C 1 1 1 0 D 1 1 0 1 E 0 0 0 0 第三章 進(jìn)程管理 尚需資源的種類和數(shù)量用矩陣 Q表示： 進(jìn)程 磁帶驅(qū)動(dòng)器 繪圖儀 打印機(jī) 穿孔機(jī) A 1 1 0 0 B 0 1 1 2 C 3 1 0 0 D 0 0 1 0 E 2 1 1 0 第三章 進(jìn)程管理 (1) 如果某一進(jìn)程對(duì)某一種資源提出請(qǐng)求 ， 就假定預(yù)先分配給它 ， 然后修改矩陣 R、 Q以及向量 S (2) 在矩陣 Q中找出一行 ， 使該行向量小于等于 S。 倘若不存在這樣的向量 ， 就說(shuō)明沒(méi)有進(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)予以撤消 。 第三章 進(jìn)程管理 1. 系統(tǒng)狀態(tài)圖 (1) 系統(tǒng)狀態(tài)圖是一組系統(tǒng)狀態(tài) σ={S 1, S 1, …)和一組進(jìn)程 π={P1, P2, …)構(gòu)成的一個(gè)數(shù)對(duì) (σ, π)。 圖 表示了一個(gè)極為簡(jiǎn)單的狀態(tài)圖 (σ， π)， 其中 σ={S, T, U, V}, π={P1, P2}。 第三章 進(jìn)程管理 圖 SUTV22 21111第三章 進(jìn)程管理 (2) 系統(tǒng)由一種狀態(tài) S演變?yōu)榱硪环N狀態(tài) T， 是由于某個(gè)進(jìn)程 Pi對(duì)資源實(shí)施了請(qǐng)求 、 獲得或釋放的單個(gè)操作的結(jié)果 。 圖 S U 1 S U 2 U V 1 S T 1 等狀態(tài)變化。我們把進(jìn)程 Pi在單個(gè)操作下，系統(tǒng)由 S狀態(tài)可能過(guò)渡到的狀態(tài)的集合表示為 Pi(S)。 第三章 進(jìn)程管理 由圖 中可以看出 P1(S)={T、 U} P1(T)=Ω P1(U)={V} P2(S)={U} P2(T)={S、 V} P2(V)=Ω 其中 Ω表示無(wú)意義。 第三章 進(jìn)程管理 在一般情況下 ， 系統(tǒng)由一個(gè)狀態(tài)過(guò)渡到另一個(gè)狀態(tài) ， 是由于不同進(jìn)程執(zhí)行了若干次操作的結(jié)果 ， 此時(shí)狀態(tài)的演變表示為： S W。 顯然它可以包括： * 第三章 進(jìn)程管理 (3) 一個(gè)進(jìn)程 Pi在狀態(tài) S是阻塞的 ， 是指不存在狀態(tài) T， 使得 S→T ， 即進(jìn)程 Pi在那個(gè)狀態(tài)下不能執(zhí)行任何操作 。 (4) 一個(gè)進(jìn)程 Pi在狀態(tài) S是死鎖的 ， 是指對(duì)任何使 S→T 的 T，Pi在狀態(tài) T是阻塞的 。 換句話說(shuō) ， 進(jìn)程 Pi在狀態(tài) S是死鎖的 ， 必定是它在狀態(tài) S以及由它可能到達(dá)的所有未來(lái)狀態(tài) T都是阻塞的 。 例如圖 中 P2在狀態(tài) U是死鎖的 ， 因?yàn)?P2 無(wú)論在狀態(tài)U還是在狀態(tài) V都是阻塞的 。 同樣 ， P2 在狀態(tài) V也是死鎖的 。 * i 第三章 進(jìn)程管理 (5) 如果在狀態(tài) S有一個(gè)死鎖進(jìn)程 ， 則 S稱為死鎖狀態(tài) 。按此定義 ， 只要設(shè)法使系統(tǒng)每一可能到達(dá)的狀態(tài)都限制在非死鎖狀態(tài) ， 就可避免死鎖 。 (6) 如果在狀態(tài) S以及它可能到達(dá)的所有狀態(tài)都是非死鎖狀態(tài)， 則 S稱為安全狀態(tài)。 第三章 進(jìn)程管理 2. 進(jìn)程 — 資源圖 以下給出進(jìn)程 —資源圖的形式定義和限制 。 (1) N被分為兩個(gè)互斥的子集：一個(gè)是進(jìn)程結(jié)點(diǎn)子集 ， π={P1, P2, …, Pn}。 另一個(gè)是資源結(jié)點(diǎn)子集 ， ρ={R1, R2, …, Rn}，N=ρ∪ π。 在圖 中 ， ρ={R1, R2}, π={A, B}, N={R1, R2}∪ {A, B}。 在圖 中 ， ρ={R}, π={P1, P2, P3, P4}, N={R}∪ {P1, P2, P3, P4}。 第三章 進(jìn)程管理 (2) 凡是屬于 E中的一個(gè)邊 e∈ E， 都連接 π中的一個(gè)結(jié)點(diǎn)和 ρ中的一個(gè)結(jié)點(diǎn) 。 若 e=(Pi, Rj)， 則 e稱為一條資源請(qǐng)求邊 ， 由進(jìn)程 Pi指向資源 Rj， 它表示進(jìn)程 Pi請(qǐng)求一個(gè)單位的Rj資源 (即 Rj的一個(gè)部件 )。 若 e={Rj, Pi)， 則 e稱為一條資源分配邊 ， 由資源 Rj指向進(jìn)程 Pi， 它表示一個(gè)單位的資源 Rj分配給進(jìn)程 Pi。 圖 中存在兩條請(qǐng)求邊和兩條分配邊： E={(A, R2), (B, R1), (R1, A), (R2, B)}。 第三章 進(jìn)程管理 (3) 若資源 Rj有 Wj個(gè)單位 (部件 )， 并用 |(Rj, Pi)|表示資源 Rj分配給進(jìn)程 Pi的單位 (部件 )數(shù) ， 用 |(Pi, Rj)|表示進(jìn)程 Pi請(qǐng)求資源 Rj的單位 (部件 )數(shù) ， 則每一張合理的進(jìn)程 —資源圖必須滿足如下兩個(gè)條件： ① 對(duì)于資源 Rj所進(jìn)行的分配不能多于 Wj， 亦即對(duì)于所有的 j均應(yīng)滿足下式： jij WPiR ?? ,第三章 進(jìn)程管理 ② 對(duì)于一個(gè)具體的資源 Rj來(lái)說(shuō) ， 任何進(jìn)程對(duì)它的請(qǐng)求及分配數(shù)量之和 ， 不能大于 Rj的可用部件數(shù) Wj， 亦即對(duì)任何 i和 j均應(yīng)滿足下式： jjj WRPiPiR ?? ,),((4) 每一張合理的進(jìn)程 — 資源圖代表了一個(gè)系統(tǒng)狀態(tài)， 反之亦然。 第三章 進(jìn)程管理 死鎖的檢測(cè) 1. 一個(gè)處于非阻塞的進(jìn)程要想達(dá)到運(yùn)行的終點(diǎn) ， 它應(yīng)獲得所需的全部資源 ， 然后釋放這些資源 。 于是 ， 某進(jìn)程所占有的資源的釋放過(guò)程又可喚醒某些以前處于阻塞狀態(tài)的進(jìn)程 ，從而使被喚醒的進(jìn)程又可得到它所需要的全部資源 。 繼續(xù)這種推斷過(guò)程 ， 直到系統(tǒng)中的狀態(tài)不再發(fā)生變化為止 。 此時(shí)可能出現(xiàn)兩種結(jié)局：一是剩下若干進(jìn)程 ， 它們?nèi)蕴幱谧枞麪顟B(tài)；二是系統(tǒng)中的全部進(jìn)程都運(yùn)行到了終點(diǎn) 。 照此可以斷言：對(duì)于前一種結(jié)局 ， 過(guò)程的初始狀態(tài)必定是一個(gè)死鎖狀態(tài)；而對(duì)于后一種結(jié)局 ， 過(guò)程的初始狀態(tài)必定不是死鎖狀態(tài) 。 第三章 進(jìn)程管理 2. 進(jìn)程 — (1) 從進(jìn)程 —資源圖中找到既非阻塞又非孤立的進(jìn)程結(jié)點(diǎn)Pi。 由于 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