行家算法課程設(shè)計(jì)

1、<p><b>　　目 錄</b></p><p>　　第一章 關(guān)于死鎖2</p><p>　　1.1死鎖的概念2</p><p>　　1.2死鎖的一些結(jié)論2</p><p>　　1.3 產(chǎn)生死鎖的必要條件2</p><p>　　1.4安全狀態(tài)與不安全狀態(tài)3</p&g

2、t;<p>　　第二章 課程設(shè)計(jì)的目的3</p><p>　　第三章 課程設(shè)計(jì)的要求3</p><p>　　第四章 課程設(shè)計(jì)題目描述4</p><p>　　第五章 課程設(shè)計(jì)之銀行家算法原理5</p><p>　　5.1 銀行家算法的思路5</p><p>　　5.2．銀行家算法中用到的主要數(shù)據(jù)結(jié)

3、構(gòu)5</p><p>　　5.3．銀行家算法6</p><p>　　5.4．安全性檢查算法7</p><p>　　第六章 源程序結(jié)構(gòu)分析及代碼實(shí)現(xiàn)8</p><p>　　6.1．程序結(jié)構(gòu)8</p><p>　　6.2．?dāng)?shù)據(jù)結(jié)構(gòu)8</p><p>　　6.3．函數(shù)聲明9</p&

4、gt;<p>　　6.4．主函數(shù)main()9</p><p>　　6.5.源程序代碼10</p><p>　　第七章 課程設(shè)計(jì)的總結(jié)10</p><p><b>　　第一章 關(guān)于死鎖</b></p><p><b>　　1.1死鎖的概念</b></p><p

5、>　　在多道程序系統(tǒng)中，雖可借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行，來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險(xiǎn)——死鎖。所謂死鎖(Deadlock),是指多個(gè)進(jìn)程在運(yùn)行中因爭奪資源而造成的一種僵局(Deadly_Embrace),當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無外力作用，它們都將無法再向前推進(jìn)。一組進(jìn)程中，每個(gè)進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。

6、</p><p>　　1.2死鎖的一些結(jié)論</p><p>　　參與死鎖的進(jìn)程最少是兩個(gè)（兩個(gè)以上進(jìn)程才會(huì)出現(xiàn)死鎖）</p><p>　　參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源</p><p>　　參與死鎖的所有進(jìn)程都在等待資源</p><p>　　參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集</p><

7、p>　　注：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。</p><p>　　1.3 產(chǎn)生死鎖的必要條件</p><p>　　1、互斥使用（資源獨(dú)占）</p><p>　　一個(gè)資源每次只能給一個(gè)進(jìn)程使用</p><p>　　2、不可強(qiáng)占（不可剝奪）</p><p>　　資源申請(qǐng)者不能強(qiáng)行的從資源占有者手中

8、奪取資源，資源只能由占有者自愿釋放</p><p>　　3、請(qǐng)求和保持（部分分配，占有申請(qǐng)）</p><p>　　一個(gè)進(jìn)程在申請(qǐng)新的資源的同時(shí)保持對(duì)原有資源的占有（只有這樣才是動(dòng)態(tài)申請(qǐng)，動(dòng)態(tài)分配）</p><p><b>　　4、循環(huán)等待</b></p><p>　　存在一個(gè)進(jìn)程等待隊(duì)列</p><p

9、>　　{P1 , P2 , … , Pn}, </p><p>　　其中P1等待P2占有的資源，P2等待P3占有的資源，…，Pn等待P1占有的資源，形成一個(gè)進(jìn)程等待環(huán)路。</p><p>　　1.4安全狀態(tài)與不安全狀態(tài)</p><p>　　安全狀態(tài)：如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，…Pn，則系統(tǒng)處于安全狀態(tài)。一個(gè)進(jìn)程序列{P1，…，Pn}是安全

10、的，如果對(duì)于每一個(gè)進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j <i )當(dāng)前占有資源量之和，系統(tǒng)處于安全狀態(tài) (安全狀態(tài)一定是沒有死鎖發(fā)生的) 。</p><p>　　不安全狀態(tài):不存在一個(gè)安全序列，不安全狀態(tài)一定導(dǎo)致死鎖。</p><p>　　第二章 課程設(shè)計(jì)的目的</p><p>　　操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)的核心系

11、統(tǒng)軟件，它負(fù)責(zé)控制和管理整個(gè)系統(tǒng)的資源并組織用戶協(xié)調(diào)使用這些資源，使計(jì)算機(jī)高效的工作。設(shè)計(jì)目的具體如下：</p><p>　　1、了解多道程序系統(tǒng)中，多個(gè)進(jìn)程并發(fā)執(zhí)行的資源分配。</p><p>　　2、掌握死鎖的產(chǎn)生的原因、產(chǎn)生死鎖的必要條件和處理死鎖的基本方法。</p><p>　　3、掌握預(yù)防死鎖的方法，系統(tǒng)安全狀態(tài)的基本概念。</p><

12、p>　　4、掌握銀行家算法，了解資源在進(jìn)程并發(fā)執(zhí)行中的資源分配策略。</p><p>　　5、理解死鎖避免在當(dāng)前計(jì)算機(jī)系統(tǒng)不常使用的原因</p><p>　　第三章 課程設(shè)計(jì)的要求</p><p>　　1．分析設(shè)計(jì)內(nèi)容，給出解決方案（要說明設(shè)計(jì)實(shí)現(xiàn)的原理，采用的數(shù)據(jù)結(jié)構(gòu)）。</p><p>　　2．對(duì)程序的每一部分要有詳細(xì)的設(shè)計(jì)分析說明

13、。</p><p>　　3．源代碼格式要規(guī)范。</p><p>　　4．設(shè)計(jì)合適的測(cè)試用例，對(duì)得到的運(yùn)行結(jié)果要有分析。</p><p>　　5．設(shè)計(jì)中遇到的問題，設(shè)計(jì)的心得體會(huì)。</p><p>　　6．按期提交完整的程序代碼、可執(zhí)行程序和課程設(shè)計(jì)報(bào)告。</p><p>　　第四章 課程設(shè)計(jì)題目描述 </p&g

14、t;<p>　　銀行家算法是一種最有代表性的避免死鎖的算法。</p><p>　　要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。</p><p>　　安全狀態(tài)：如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。</p><p>　　不安全狀態(tài):不存在一個(gè)安全序列。不安全狀態(tài)不一定導(dǎo)致死

15、鎖。</p><p>　　那么什么是安全序列呢？</p><p>　　安全序列：一個(gè)進(jìn)程序列{P1，…，Pn}是安全的，如果對(duì)于每一個(gè)進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j < i )當(dāng)前占有資源量之和。</p><p><b>　　銀行家算法：</b></p><p&

16、gt;　　我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過了該進(jìn)程對(duì)資源的最大需求量。若超過則拒絕

17、分配資源，若沒有超過則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。</p><p>　　在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。</p><p>　　銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是

18、安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。</p><p>　　設(shè)進(jìn)程cusneed提出請(qǐng)求REQUEST [i]，則銀行家算法按如下規(guī)則進(jìn)行判斷。</p><p>　　(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉(zhuǎn)(2)；否則，出錯(cuò)。</p><p>　　(2)如果REQUEST [cusnee

19、d] [i]<= AVAILABLE[cusneed][i]，則轉(zhuǎn)(3)；否則，出錯(cuò)。</p><p>　　(3)系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)：</p><p>　　AVAILABLE[i]-=REQUEST[cusneed][i];</p><p>　　ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];</p&g

20、t;<p>　　NEED[cusneed][i]-=REQUEST[cusneed][i];</p><p>　　(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險(xiǎn)性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。</p><p>　　第五章 課程設(shè)計(jì)之銀行家算法原理</p><p>　　5.1 銀行家算法的思路</p><p>　　先

21、對(duì)用戶提出的請(qǐng)求進(jìn)行合法性檢查，即檢查請(qǐng)求的是不大于需要的，是否不大于可利用的。若請(qǐng)求合法，則進(jìn)行試分配。最后對(duì)試分配后的狀態(tài)調(diào)用安全性檢查算法進(jìn)行安全性檢查。若安全，則分配，否則，不分配，恢復(fù)原來狀態(tài)，拒絕申請(qǐng)。</p><p>　　5.2．銀行家算法中用到的主要數(shù)據(jù)結(jié)構(gòu)</p><p>　　可利用資源向量 int Available[j] j為資源的種類。</p>

22、<p>　　最大需求矩陣 int Max[i][j] i為進(jìn)程的數(shù)量。</p><p>　　分配矩陣 int Allocation[i][j] </p><p>　　需求矩陣 int need[i][j]= Max[i][j]- Allocation[i][j]</p><p>　　申請(qǐng)各類資源數(shù)量

23、 int Request i[j] i進(jìn)程申請(qǐng)j資源的數(shù)量</p><p>　　工作向量 int Work[x] int Finish[y] </p><p>　　可利用資源向量矩陣AVAILABLE。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。

24、如果AVAILABLE [j]= K，則表示系統(tǒng)中現(xiàn)有R類資源K個(gè)</p><p>　　最大需求矩陣MAX。這是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果MAX [i,j]=K，則表示進(jìn)程i需要R類資源的數(shù)目為K。</p><p>　　分配矩陣ALLOCATION。這也是一個(gè)n*m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果ALLOCATION [

25、i,j]=K，則表示進(jìn)程i當(dāng)前已分得R類資源的數(shù)目為K。</p><p>　　需求矩陣NEED。這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果NEED [i,j]=K，則表示進(jìn)程i還需要R類資源K個(gè)，才能完成其任務(wù)。 </p><p>　　上述矩陣存在下述關(guān)系：</p><p>　　NEED [i,j]= MAX[i,j]﹣ ALLOCA

26、TION[i,j]</p><p><b>　　5.3．銀行家算法</b></p><p>　　進(jìn)程i發(fā)出請(qǐng)求申請(qǐng)k個(gè)j資源，Request i[j]=k </p><p>　　(1)檢查申請(qǐng)量是否不大于需求量：Request i[j]<=need[i,j],若條件不符重新輸入，不允許申請(qǐng)大于需求量。</p><p&g

27、t;　　(2)檢查申請(qǐng)量是否小于系統(tǒng)中的可利用資源數(shù)量：Request i[j]<=available[i,j]，若條件不符就申請(qǐng)失敗，阻塞該進(jìn)程，用goto語句跳轉(zhuǎn)到重新申請(qǐng)資源。</p><p>　　(3)若以上兩個(gè)條件都滿足，則系統(tǒng)試探著將資源分配給申請(qǐng)的進(jìn)程，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：</p><p>　　Available[i,j]= Available[i,j]- Re

28、quest i[j]；</p><p>　　Allocation[i][j]= Allocation[i][j]+ Request i[j]；</p><p>　　need[i][j]= need[i][j]- Request i[j]；</p><p>　　(4)試分配后，執(zhí)行安全性檢查，調(diào)用safe()函數(shù)檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將

29、資源分配給進(jìn)程；否則本次試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓該進(jìn)程等待。</p><p>　　(5)用do{…}while 循環(huán)語句實(shí)現(xiàn)輸入字符y/n判斷是否繼續(xù)進(jìn)行資源申請(qǐng)。</p><p>　　5.4．安全性檢查算法</p><p>　　(1)設(shè)置兩個(gè)向量：</p><p>　　工作向量Work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各

30、類資源數(shù)目，在執(zhí)行安全性算法開始時(shí)，Work= Available。</p><p>　　Finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finish[i]=0；當(dāng)有足夠的資源分配給進(jìn)程時(shí)，再令Finish[i]=1。</p><p>　　(2)在進(jìn)程中查找符合以下條件的進(jìn)程：</p><p>　　條件1：Finish[i]=0；<

31、/p><p>　　條件2：need[i][j]<=Work[j]</p><p>　　若找到，則執(zhí)行步驟(3)否則，執(zhí)行步驟(4)</p><p>　　(3)當(dāng)進(jìn)程獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：</p><p>　　Work[j]= Work[j]+ Allocation[i][j]；</p>

32、;<p>　　Finish[i]=1；</p><p>　　goto step 2；</p><p>　　(4)如果所有的Finish[i]=1都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于不安全狀態(tài)。</p><p>　　第六章 源程序結(jié)構(gòu)分析及代碼實(shí)現(xiàn)</p><p><b>　　6.1．程序結(jié)構(gòu)</b>&

33、lt;/p><p>　　程序共有以下五個(gè)部分：</p><p>　　.初始化initial()：用于程序開始進(jìn)行初始化輸入數(shù)據(jù)：進(jìn)程數(shù)量、資源種類、各種資源可利用數(shù)量、各進(jìn)程的各種資源已分配數(shù)量、各進(jìn)程對(duì)各類資源最大需求數(shù)等。</p><p>　　(2).當(dāng)前安全性檢查safe()：用于判斷當(dāng)前狀態(tài)安全性，根據(jù)不同地方的調(diào)用提示處理不同。</p><

34、p>　　(3).銀行家算法bank()：進(jìn)行銀行家算法模擬實(shí)現(xiàn)的模塊，調(diào)用其他各個(gè)模塊進(jìn)行銀行家算法模擬過程。</p><p>　　(4).顯示當(dāng)前狀態(tài)show()：顯示當(dāng)前資源分配詳細(xì)情況，包括：各種資源的總數(shù)量(all)、系統(tǒng)目前各種資源可用的數(shù)量、各進(jìn)程已經(jīng)得到的資源數(shù)量、各進(jìn)程還需要的資源量。</p><p>　　(5).主程序main()</p><p&

35、gt;　　逐個(gè)調(diào)用初始化、顯示狀態(tài)、安全性檢查、銀行家算法函數(shù)，使程序有序的進(jìn)行。</p><p><b>　　6.2．?dāng)?shù)據(jù)結(jié)構(gòu)</b></p><p>　　程序使用的全局變量：</p><p>　　const int x=10，y=10； //定義常量</p><p>　　int Available[x];

36、 //各種資源可利用的數(shù)量</p><p>　　int Allocation[y][y]; //各進(jìn)程當(dāng)前已分配的資源數(shù)量</p><p>　　int Max[y][y]; //各進(jìn)程對(duì)各類資源的最大需求數(shù)</p><p>　　int Need[y][y]; //還需求矩陣</p><p>　　int Re

37、quest[x]; //申請(qǐng)各類資源的數(shù)量</p><p>　　int Work[x]; //工作向量，表系統(tǒng)可提供給進(jìn)程運(yùn)行所需各類資源數(shù)量</p><p>　　int Finish[y]; //表系統(tǒng)是否有足夠的資源分配給進(jìn)程，0為否，1為是</p><p>　　int p[y]; //存儲(chǔ)安全序列</p>&l

38、t;p>　　int i,j; //全局變量，主要用于循環(huán)語句中</p><p>　　int n,m; //n為進(jìn)程的數(shù)量,m為資源種類數(shù)</p><p>　　int l=0,counter=0;</p><p><b>　　6.3．函數(shù)聲明</b></p><p>　　void initia

39、l(); 　　//系統(tǒng)初始化函數(shù)</p><p>　　void safe(); 　//安全性算法函數(shù)</p><p>　　void bank(); //銀行家算法函數(shù)</p><p>　　void show (); 　//輸出當(dāng)前資源分配情況</p><p>　　6.4．主函數(shù)main()</p>&

40、lt;p>　　int main()</p><p><b>　　{</b></p><p>　　cout<<…… //顯示程序開始提示信息</p><p>　　initial(); //初始化函數(shù)調(diào)用</p><p>　　cout<<endl<<endl;</p>

41、<p>　　showdata(); //輸出初始化后的狀態(tài)</p><p>　　//===判斷當(dāng)前狀態(tài)的安全性===</p><p>　　safe(); //安全性算法函數(shù)調(diào)用</p><p><b>　　if (l<n){</b></p><p>　　cout<<"\n當(dāng)前狀態(tài)不

42、安全，無法申請(qǐng),程序退出!!!!!"<<endl;</p><p>　　cout<<endl; </p><p>　　system("pause"); </p><p>　　sign(); //調(diào)用簽名函數(shù)</p><p>　　return 0; // break; </p&

43、gt;<p><b>　　}</b></p><p><b>　　else{ </b></p><p>　　int i; //局部變量</p><p><b>　　l=0;</b></p><p>　　cout<<"\n安全的狀態(tài)!!!&qu

44、ot;<<endl;</p><p>　　cout<<"安全序列為: ";</p><p>　　cout<<endl<<"進(jìn)程"<<"("<<p[0]<<")"; //輸出安全序列，考慮顯示格式，先輸出第一個(gè)</p&g

45、t;<p>　　for (i=1; i<n; i++){</p><p>　　cout<<"==>>"<<"進(jìn)程"<<"("<<p[i]<<")";</p><p><b>　　} </b><

46、/p><p>　　for (i=0; i<n; i++) Finish[i]=0; //所有進(jìn)程置為未分配狀態(tài)</p><p>　　cout<<endl<<endl;</p><p><b>　　}</b></p><p>　　bank(); //銀行家算法函數(shù)調(diào)用</p><

47、;p><b>　　eturn 0; </b></p><p><b>　　}</b></p><p><b>　　6.5.源程序代碼</b></p><p><b>　　見附件</b></p><p>　　第七章 課程設(shè)計(jì)的總結(jié)</p>

48、<p>　　操作系統(tǒng)的基本特征是并發(fā)與共享。系統(tǒng)允許多個(gè)進(jìn)程并發(fā)執(zhí)行，并且共享系統(tǒng)的軟、硬件資源。為了最大限度的利用計(jì)算機(jī)系統(tǒng)的資源，操作系統(tǒng)應(yīng)采用動(dòng)態(tài)分配的策略，但是這樣就容易因資源不足，分配不當(dāng)而引起“死鎖”。</p><p>　　銀行家算法就是一個(gè)分配資源的過程，使分配的序列不會(huì)產(chǎn)生死鎖。此算法的中心思想是：按該法分配資源時(shí)，每次分配后總存在著一個(gè)進(jìn)程，如果讓它單獨(dú)運(yùn)行下去，必然可以獲得它所需要