葉承瓊

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

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

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

1 引言

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

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

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

2.1 銀行家算法的引入

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

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

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

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

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

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

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

最大需求矩陣: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個(gè),方能完成其任務(wù)。

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

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

2.2.2 銀行家算法的具體描述

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

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

(1)若Requesti<=Needi,則轉(zhuǎn)向(2);否則錯(cuò)誤,因?yàn)镻i所請(qǐng)求的資源已超過(guò)它的需求最大值。

(2)若Requesti<=Available,則轉(zhuǎn)向(3);否則進(jìn)程Pi等待,因?yàn)榇藭r(shí)系統(tǒng)沒(méi)有足夠的資源。

(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]=false。

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

Finish[i]=false;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é)過(guò)程中的注意事項(xiàng)

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

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

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

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

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

3 總結(jié)

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

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

參考文獻(xiàn)

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

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

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

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