操作系統(tǒng)課程設計--銀行家算法(已修改)
2025-06-23 06:21 本頁面
【正文】 課程設計說明書 沈 陽 大 學 銀行家算法 1. 課程設計的目的 了解 多道程序系統(tǒng)中，多個進程并發(fā)執(zhí)行的資源分配，及死鎖的產生原因、必要條件和處理死鎖的基本方法，掌握預防死鎖的方法，系統(tǒng)安全狀態(tài)的基本概念，了解銀行家算法，及資源在進程并發(fā)執(zhí)行中的資源分配策略，并且理解死鎖避免在當前計算機系統(tǒng)不常使用的原因。 根據(jù)設計題目的要求，充分地分析和理解 題目 ，敘述系統(tǒng)的要求，明確 程序 要求 實現(xiàn) 的功能 以及限制條件 。明白自己需要用代碼實現(xiàn)的功能，清楚編寫每部分代碼的目的，做到有的放矢，有條理不遺漏的用代碼實現(xiàn)銀行家算法。 銀行家 算法是一種最有代表性的避免死鎖的算法。 在多道程序系統(tǒng)中，多個進程的并發(fā)執(zhí)行來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險 —— 死鎖。所謂死鎖 (Deadlock)，是指多個進程在運行過程中因爭奪資源而造成的一種僵局（ DeadlyEmbrace），當進程處于這種狀態(tài)時，若無外力作用，他們都無法在向前推進。要預防死鎖，有摒棄“請求和保持”條件，摒棄“不剝奪”條件，摒棄“環(huán)路等待”條件等方法。但是，在預防死鎖的幾種方法之中，都施加了較強的限制條件；而在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令 人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，便可避免死鎖的發(fā)生。 要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全狀態(tài) 是指系統(tǒng)能按照某種進程順序{P1,P2,?， Pn}（稱 {P1,P2,?， Pn }序列為安全序列），來為每個進程 Pi 分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可以順利完成。安全狀態(tài)一定沒有死鎖發(fā)生。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。 安全序列：一個進程序列 {P1，?， Pn}是安全的，如果對于每一個進程 Pi(1≤ i≤ n） ，它以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程 Pj (j i )當前占有資源量之和， 則稱此進程序列 {P1,P2,?， Pn}是安全的，稱作安全序列。 銀行家算法：我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當于銀行家管理的資金，進程向操作系統(tǒng)請求分配資源相當于用戶向銀行家貸款。操作系統(tǒng)按照 課程設計說明書 沈 陽 大 學 銀行家制定的規(guī)則為進程分配資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執(zhí)行中繼續(xù)申請資源時，先測 試該進程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進程尚需的最大資源量，若能滿足則按當前的申請量分配資源，否則也要推遲分配。 算法思路 先對用戶提出的請求進行合法性檢查，即檢查請求是否大于需要的，是否大于可利用的。若請求合法，則進行預分配，對分配后的狀態(tài)調用安全性算法進行檢查。若安全，則分配；若不安全，則拒絕申請，恢復到原來的狀態(tài)，拒絕申請。 銀行家算法中的數(shù)據(jù)結構 （ 1）可利用 資源向量 Available。這是一個含有 m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果 Available [j]= K，則表示系統(tǒng)中現(xiàn)有 R 類資源 K個 （ 2）最大需求矩陣 Max。這是一個 n*m 的矩陣，它定義了系統(tǒng)中 n 個進程對 m類資源的最大需求。如果 Max[i,j]=K，則表示進程 i需要 R 類資源的數(shù)目為 K。 （ 3）分配矩陣 Allocation。這也是一個 n*m 的矩陣，它定義了系統(tǒng)中每一類資源當前已分配給每一 進程的資源數(shù)。如果 Allocation [i,j]=K，則表示進程 i當前已分得 R類資源的數(shù)目為 K。 （ 4）需求矩陣 Need[][]。這也是一個 n*m的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果 Need [i,j]=K，則表示進程 i還需要 R類資源 K個，才能完成其任務。 上述矩陣存在關系： Need[i,j]= Max[i,j]﹣ Allocation[i,j] 銀行家算法 設 Requesti是進程 Pi的請求向量， Requesti=K 表示進程 Pi 需要 K 個 j 類資源。 Pi發(fā)出資源請求后，按下列步驟進行檢查 ： 課程設計說明書
畢業(yè)設計相關推薦
鄂ICP備17016276號-1