《操作系統》中銀行家算法的研究性教學

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

關鍵詞死鎖 死鎖避免 銀行家算法 安全性算法

中圖分類號:G423文獻標識碼:A

1 引言

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

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

2 銀行家算法的教學思路

2.1 銀行家算法的引入

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

那么在操作系統設計過程中如果產生死鎖又是如何解決呢?

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

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

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

2.2.1 銀行家算法中的數據結構

可利用資源向量:Available[j]=k，表示系統中現有Rj類資源k個。

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

分配矩陣:Allocation[i，j]=k，表示進程i當前已分得Rj類資源的數目為k。

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

不難看出上述矩陣間存在下述關系:

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

2.2.2 銀行家算法的具體描述

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

當Pi發出資源請求Requesti后，系統按下述步驟進行檢查:

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

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

(3)系統進入試探性分配，并修改相應的數據結構:

Available=Available-Requesti

Allocationi=Allocationi+Requesti;

Needi=Needi-Requesti;

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

2.2.3安全性算法描述

Work:表示系統可提供給進程繼續運行所需要的各類資源數目。

Finish:表示系統是否有足夠的資源分配給進程，使之運行完成。

(1)Work= Available;

Finish[i]=1。

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

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

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

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

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

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

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

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

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

(3)在進行安全性檢查時若找不到安全序列，系統處于不安全狀態，此時的系統可能會產生死鎖而不是一定產生死鎖。學生在以后的學習過程中實現銀行家算法應考慮到這一點，并作出合理的過程設計。

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

3 總結

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

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

參考文獻

[1]湯子贏，哲鳳屏，湯小丹.計算機操作系統[M].西安:西安電子科技大學出版社，2006.

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

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

[4]仲兆滿.銀行家算法的改進及其在操作系統上的推廣.連云港師范高等專科學校學報，2002(2):46～48.