計算機操作系統(tǒng)-銀行家算法

操作系統(tǒng)課程設(shè)計題目：銀行家算法的設(shè)計與實現(xiàn)系別：計算機信息與技術(shù)系專業(yè)：計算機科學(xué)與技術(shù)班級：B130601姓名：伏海龍學(xué)號：B13060105指導(dǎo)教師：魏少華×××2016年01月摘要此次課程設(shè)計的主要內(nèi)容是模擬實現(xiàn)資源分配。同時要求編寫和調(diào)試一個系統(tǒng)動態(tài)分配資源的簡單模擬程序，觀察死鎖產(chǎn)生的條件，并用適當?shù)乃惴?，有效的防止和避免死鎖的發(fā)生。銀行家算法是一個避免死鎖的一種重要方法，通過高級語言編寫和調(diào)試一個簡單的銀行家算法程序。加深了解有關(guān)資源申請、避免死鎖等概念，并體會了解死鎖和避免死鎖的具體實施方法。死鎖的產(chǎn)生，必須同時滿足四個條件，即一個資源每次只能由一個進程占用；第二個為等待條件，即一個進程請求資源不能滿足時，他必須等待，但他仍繼續(xù)保持已得到的所有其他資源；第四個為循環(huán)等待條件，系統(tǒng)中存在若干個循環(huán)等待的進程，即其中每一個進程分別等待他前一個進程所持有的資源。當不滿足以上條件時就能防止系統(tǒng)的死鎖，讓系統(tǒng)流暢運行。通過該算法可以解決生活中的實際問題，如銀行貸款等。通過對該算法的設(shè)計，讓學(xué)生能夠?qū)镜闹R有更深刻的理解，在操作和其他方面有大幅度的提高。

2.2死鎖的結(jié)論產(chǎn)生死鎖的原因是：競爭資源和進程推進順序不當處理死鎖的基本方法是：預(yù)防死鎖，避免死鎖，檢測死鎖，解除死鎖。2.3資源分類1.可剝奪性資源，某些進程在獲得此類資源后，該資源可以被其他進程或系統(tǒng)比多。CPU和每寸均屬于可剝奪性資源。2.不可剝奪性資源，當系統(tǒng)把類資源分配給進程后，不能強行收回，只能在進程用完后自動釋放，如磁帶機，打印機3.非剝奪性資源，在系統(tǒng)中所配置的非剝奪性資源，由于他們的數(shù)量不能滿足諸進程的需要，會使進程在運行中，因爭奪這些資源而陷入僵局。4.臨時資源，他是指由一個進程產(chǎn)生，倍另一個進程使用短暫時間后便無用的資源，也稱之為消耗性資源。2.4產(chǎn)生死鎖的必要條件1.互斥條件：進程對他所分配的資源進行排他性使用，即在一段時間內(nèi)摸個資源由一個進程占有。如果此時還有其他進程請求該資源，則請求者只能等待，直至占有該資源的進程用畢釋放。2.請求和保持條件：進程已經(jīng)保持了至少一個資源，但又提出新的資源請求，而該資源又被其他進程占有，此時請求進程阻塞，但有對自己獲得的其他資源保持不放。3.不剝奪條件：進程已獲得的資源，在未使用完之前，不能剝奪，只有在使用完由自己釋放。4環(huán)路等待條件：發(fā)生死鎖時，必然存在一個進程一資源的環(huán)形鏈。2.5銀行家算發(fā)的意義依次對進程測試，直到每一進程能夠運行并釋放，從而實現(xiàn)了避免死鎖的功能。也能提供多種序列可完美實現(xiàn)要求。3.數(shù)據(jù)結(jié)構(gòu)分析設(shè)計3.1可利用資源向量矩陣available[]這是一個含有m個元素的數(shù)組，其中每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源數(shù)目，起數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果available[j]=k，則表示系統(tǒng)中現(xiàn)有R類資源K個3.2最大需求矩陣max[][]這是一個n*m的矩陣，用以表示每一個進程對m類資源的最大需求。如果max[i,j]=K，則表示進程i需要R類資源的數(shù)目為K。3.3分配矩陣allocation[][]這也是一個n*m的矩陣，他/她定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。如果allocation[i，j]=K，則表示進程i當前已分得R類資源的數(shù)目為K。3.4需求矩陣need[][]這也是一個n*m的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果need[i，j]=K，則表示進程i還需要R類資源K個，才能完成其任務(wù)。上述矩陣存在下述關(guān)系:Need[i,j]=max[i,j]-allocation[i,j]4.算法的實現(xiàn)4.1初始化1.創(chuàng)建available[]數(shù)組，用以存放系統(tǒng)中可用的資源數(shù)目；2.創(chuàng)建max[][]數(shù)組，用以存放各個進程對各類資源的最大需求數(shù)目；3.創(chuàng)建allocation[][]數(shù)組，用以存放各個進程已經(jīng)分得的各類資源數(shù)目；4.創(chuàng)建need[][]數(shù)組，用以存放個各個進程還需要的各類資源數(shù)目；5.創(chuàng)建allocationl[][]；need[][];availablel[][]，用以存放系統(tǒng)試分配資源前系統(tǒng)資源分配情況；4.2銀行家算法設(shè)Request是請求P的請求向量，Request=K表示進程P需要K個j類資源。P發(fā)出資源請求后，按下列步驟進行檢查：如果reques[j]<=need[i,j]，轉(zhuǎn)向步驟②；否則報錯，所需要的資源數(shù)已超過它所宣布的最大值；如果request[j]<=available[j]，轉(zhuǎn)向步驟③；否則報錯，尚無足夠資源P需等待；嘗試將資源分配給進程P，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：acailable[j]:=available[j]-request[j];allocation[i,j]:=allocation[i,j]]+request;need[i,j]:=need[i,j]-request[j];執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)師傅處于安全狀態(tài)。若安全，才正式將資源分配給P[i]，已完成本次分配；否則，將本溪試探分配作廢，回復(fù)原來的資源分配狀態(tài)，讓P[i]等待。

4.3算法流程圖4.3.1.初始化算法流程圖：計算各個進程還需的資源數(shù)計算各個進程還需的資源數(shù)NEED[i][j]=Max[i][j]–Allocation[i][j]結(jié)束開始輸入進程總數(shù)M輸入資源種類個數(shù)N輸入每個進程最大資源需求數(shù)Max[][]輸入每個進程已分配的資源數(shù)Allocation輸入現(xiàn)在可用資源數(shù)Available4.3.2銀行家算法流程圖：NONOYESYESNO開始錄入請求資源數(shù)RQUEST[i]>NEED[i]或者REQUEST[i]>AVAILABLE[i]報錯，重新輸入AVAILABLE[i]-=REQUEST[i];

ALLOCATION[i]+=REQUEST[i];

NEED[i]-=REQUEST[i];初始化安全性檢查安全AVAILABLE[i]+=REQUEST[i];

ALLOCATION[i]-=REQUEST[i];

NEED[i]+=REQUEST[i];保持原分配進程執(zhí)行完釋放資源繼續(xù)分配結(jié)束YESNOYESNO測試與實例分析

實驗總結(jié)多個進程同時運行時，系統(tǒng)根據(jù)各類系統(tǒng)資源的最大需求和各類系統(tǒng)的剩余資源