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

　　

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