《操作系統(tǒng)》中銀行家算法的研究性教學(xué)

摘要《操作系統(tǒng)》課程中死鎖是一個重要的問題，銀行家算法是采用死鎖避免策略來解決死鎖問題的經(jīng)典算法，也是本課程教學(xué)的重難點，本文根據(jù)實際教學(xué)經(jīng)驗探討以銀行家算法為例的研究性教學(xué)方法。

關(guān)鍵詞死鎖 死鎖避免 銀行家算法 安全性算法

中圖分類號:G423文獻(xiàn)標(biāo)識碼:A

1 引言

《操作系統(tǒng)》是計算機(jī)專業(yè)的核心理論課程之一，該課程首次引入進(jìn)程以及進(jìn)程并發(fā)執(zhí)行等相關(guān)概念，無論對于教師的專業(yè)教學(xué)還是對于學(xué)生的系統(tǒng)學(xué)習(xí)都具有重要的作用。由于本課程涉及的學(xué)科多、理論知識點多、內(nèi)容難理解等特征，在整個學(xué)習(xí)過程中，最讓學(xué)生關(guān)注的是對于死鎖問題中銀行家算法的討論，這不僅涉及計算機(jī)專業(yè)問題，同樣在日常生活中也存在很多類似的現(xiàn)象，具有實踐意義。

為了讓學(xué)生深入掌握理論知識，本文根據(jù)實際教學(xué)經(jīng)驗，結(jié)合大部分學(xué)生學(xué)習(xí)該課程的情況，以銀行家算法為例探討了該課程的教學(xué)方法。

2 銀行家算法的教學(xué)思路

2.1 銀行家算法的引入

對于多個進(jìn)程的并發(fā)執(zhí)行可以改善系統(tǒng)的資源利用率和提高系統(tǒng)的處理能力，學(xué)生通過前序內(nèi)容的學(xué)習(xí)都能夠理解，但在系統(tǒng)運(yùn)行過程中由于進(jìn)程執(zhí)行的異步性特征以及系統(tǒng)資源的有限，如果操作系統(tǒng)為這些并發(fā)進(jìn)程分配資源順序不當(dāng)時，就可能會產(chǎn)生死鎖(Deadlock)，而死鎖最終可能導(dǎo)致整個系統(tǒng)癱瘓，危及系統(tǒng)安全。

那么在操作系統(tǒng)設(shè)計過程中如果產(chǎn)生死鎖又是如何解決呢?

通常解決死鎖的方法有預(yù)防、避免、檢測和解除三種，其中采用死鎖避免可以獲得滿意的系統(tǒng)性能，而銀行家算法(Banker’s Algorithm)則是典型的采用死鎖避免策略來解決死鎖問題的著名算法。是由艾茲格·迪杰斯特拉在1965年為T.H.E系統(tǒng)設(shè)計的一種避免死鎖產(chǎn)生的算法。它以銀行借貸系統(tǒng)的分配策略為基礎(chǔ)，判斷并保證系統(tǒng)的安全運(yùn)行。銀行家就好比操作系統(tǒng)，資金就是資源，客戶就相當(dāng)于要申請資源的進(jìn)程。

2.2 掌握銀行家算法的基本原理

首先讓學(xué)生了解系統(tǒng)通常工作的兩個狀態(tài):即安全狀態(tài)和不安全狀態(tài)，在系統(tǒng)動態(tài)的為各進(jìn)程分配資源的過程中，只要保證系統(tǒng)處于安全狀態(tài)，即系統(tǒng)可按照某一順序為每一進(jìn)程分配資源直至完成釋放，存在這樣的安全序列系統(tǒng)就不會發(fā)生死鎖。接下來具體分析銀行家算法的數(shù)據(jù)結(jié)構(gòu)及算法步驟。

2.2.1 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)

可利用資源向量:Available[j]=k，表示系統(tǒng)中現(xiàn)有Rj類資源k個。

最大需求矩陣:Max[i，j]=k，表示進(jìn)程i需要Rj類資源的最大數(shù)目為k。

分配矩陣:Allocation[i，j]=k，表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為k。

需求矩陣:Need[i，j]=k，表示進(jìn)程i還需要Rj類資源k個，方能完成其任務(wù)。

不難看出上述矩陣間存在下述關(guān)系:

Need[i，j]= Max[i，j]- Allocation[i，j]。

2.2.2 銀行家算法的具體描述

進(jìn)程Pi的請求向量:Requesti[j]=k，表示進(jìn)程Pi需要k個Rj類型的資源。

當(dāng)Pi發(fā)出資源請求Requesti后，系統(tǒng)按下述步驟進(jìn)行檢查:

(1)若Requesti<=Needi，則轉(zhuǎn)向(2);否則錯誤，因為Pi所請求的資源已超過它的需求最大值。

(2)若Requesti<=Available，則轉(zhuǎn)向(3);否則進(jìn)程Pi等待，因為此時系統(tǒng)沒有足夠的資源。

(3)系統(tǒng)進(jìn)入試探性分配，并修改相應(yīng)的數(shù)據(jù)結(jié)構(gòu):

Available=Available-Requesti

Allocationi=Allocationi+Requesti;

Needi=Needi-Requesti;

(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配之后，系統(tǒng)是否處于安全狀態(tài)。若安全則試探性分配生效;否則，將試探性分配作廢，進(jìn)程Pi等待。

2.2.3安全性算法描述

Work:表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源數(shù)目。

Finish:表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。

(1)Work= Available;

Finish[i]=1。

(2)從進(jìn)程集合中找到一個滿足下述條件的進(jìn)程:

Finish[i]=1;Needi<=Work。若找到轉(zhuǎn)向(3);否則轉(zhuǎn)向(4)。

(3)當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行直至完成，并釋放出分配給它的資源:

Work=Work+Available;Finish[i]=true;轉(zhuǎn)向(1)。

(4)若所有進(jìn)程的Finish[i]=true，表示系統(tǒng)處于安全狀態(tài);否則系統(tǒng)處于不安全狀態(tài)。

2.3 銀行家算法教學(xué)過程中的注意事項

通過上述對銀行家算法及安全性算法的基本原理及詳細(xì)步驟的分析，教學(xué)過程中結(jié)合教材、參考資料中相關(guān)例題的講解，進(jìn)一步加深學(xué)生對于銀行家算法的理解和掌握。但學(xué)生在解題過程中往往會忽略一些細(xì)節(jié)，導(dǎo)致對該算法的理解出現(xiàn)偏差，本人在教學(xué)過程中總結(jié)了一些經(jīng)驗，現(xiàn)羅列如下幾點:

(1)系統(tǒng)在開始執(zhí)行銀行家算法時，檢查Requesti、Needi和Available的先后順序一定不能顛倒。應(yīng)先檢查Pi進(jìn)程所提出的請求向量Requesti是否在該進(jìn)程的需求范圍內(nèi)，即是否小于等于Needi，若超過則產(chǎn)生一個錯誤。然后再確定當(dāng)前系統(tǒng)中可利用資源數(shù)能否滿足此次請求向量Requesti，即Requesti是否小于等于Available，若大于說明此時系統(tǒng)中沒有足夠的資源滿足該進(jìn)程的請求，進(jìn)程Pi等待。

(2)在安全性算法執(zhí)行到從進(jìn)程集合中找滿足Finish[i]=1和Needi<=Work兩個條件的進(jìn)程時，若同時存在若干個進(jìn)程均符合條件，則不管選中哪一個進(jìn)程都可以。

(3)在進(jìn)行安全性檢查時若找不到安全序列，系統(tǒng)處于不安全狀態(tài)，此時的系統(tǒng)可能會產(chǎn)生死鎖而不是一定產(chǎn)生死鎖。學(xué)生在以后的學(xué)習(xí)過程中實現(xiàn)銀行家算法應(yīng)考慮到這一點，并作出合理的過程設(shè)計。

(4)在某一時刻，系統(tǒng)處于安全狀態(tài)，即存在安全序列，則安全序列的個數(shù)只能是1(最小值)和正偶數(shù)，最大值是n!(n表示進(jìn)程個數(shù))。

3 總結(jié)

在本課程整個教學(xué)過程中，只要將知識點理清，并圍繞操作系統(tǒng)的五大功能展開教學(xué)，對每個功能的介紹要結(jié)合各大功能知識點內(nèi)在的聯(lián)系，特別對于像死鎖這樣理論性較強(qiáng)并且抽象的問題，應(yīng)特別強(qiáng)調(diào)進(jìn)程執(zhí)行的相關(guān)特征如并發(fā)性與異步性等，由淺入深，并就難點如銀行家算法逐步分析解決死鎖問題的過程。該教學(xué)方法已經(jīng)進(jìn)行了幾年的教學(xué)實踐，把復(fù)雜抽象問題加以概念闡述并結(jié)合實際，重點難理解的部分特別強(qiáng)調(diào)，知識有條理，學(xué)生比較容易接受，從而能夠熟練掌握解決此類問題的方法，普遍反映良好。

不足之處在于實驗教學(xué)部分需要改善。操作系統(tǒng)是所有軟件中最復(fù)雜的，而目前幾大主流操作系統(tǒng)的地位已相當(dāng)堅固，所以師生幾乎沒有參與編制實際操作系統(tǒng)的機(jī)會，這樣在教學(xué)過程中原理的抽象性和實際開發(fā)嚴(yán)重脫節(jié)，直接影響學(xué)生學(xué)習(xí)該課程的興趣。不過近年來為改善教學(xué)效果，我校在理論教學(xué)的同時，開設(shè)了實驗課程，主要針對目前最有潛力的Linux系統(tǒng)。下一步準(zhǔn)備嘗試讓學(xué)生分析Linux內(nèi)核代碼，了解系統(tǒng)的整個構(gòu)架及內(nèi)部運(yùn)行模式，引發(fā)學(xué)生學(xué)習(xí)的興趣，同時不斷探索新的教學(xué)方式與方法，使理論、命令和程序融為一體。

參考文獻(xiàn)

[1]湯子贏，哲鳳屏，湯小丹.計算機(jī)操作系統(tǒng)[M].西安:西安電子科技大學(xué)出版社，2006.

[2]高煜.操作系統(tǒng)原理.北京:海洋出版社[M].2006.

[3]于廣斌，葛元康，李宗民.“操作系統(tǒng)”課程改革的探索與實踐.計算機(jī)教育，2009(14):22～23.

[4]仲兆滿.銀行家算法的改進(jìn)及其在操作系統(tǒng)上的推廣.連云港師范高等?？茖W(xué)校學(xué)報，2002(2):46～48.