第三章進程管理-資料下載頁

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

　　

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