《操作系统》中银行家算法的研究性教学

叶承琼

摘要《操作系统》课程中死锁是一个重要的问题,银行家算法是采用死锁避免策略来解决死锁问题的经典算法,也是本课程教学的重难点,本文根据实际教学经验探讨以银行家算法为例的研究性教学方法。

关键词死锁 死锁避免 银行家算法 安全性算法

中图分类号:G423文献标识码:A

1 引言

《操作系统》是计算机专业的核心理论课程之一,该课程首次引入进程以及进程并发执行等相关概念,无论对于教师的专业教学还是对于学生的系统学习都具有重要的作用。由于本课程涉及的学科多、理论知识点多、内容难理解等特征,在整个学习过程中,最让学生关注的是对于死锁问题中银行家算法的讨论,这不仅涉及计算机专业问题,同样在日常生活中也存在很多类似的现象,具有实践意义。

为了让学生深入掌握理论知识,本文根据实际教学经验,结合大部分学生学习该课程的情况,以银行家算法为例探讨了该课程的教学方法。

2 银行家算法的教学思路

2.1 银行家算法的引入

对于多个进程的并发执行可以改善系统的资源利用率和提高系统的处理能力,学生通过前序内容的学习都能够理解,但在系统运行过程中由于进程执行的异步性特征以及系统资源的有限,如果操作系统为这些并发进程分配资源顺序不当时,就可能会产生死锁(Deadlock),而死锁最终可能导致整个系统瘫痪,危及系统安全。

那么在操作系统设计过程中如果产生死锁又是如何解决呢?

通常解决死锁的方法有预防、避免、检测和解除三种,其中采用死锁避免可以获得满意的系统性能,而银行家算法(Bankers 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]=false。

(2)从进程集合中找到一个满足下述条件的进程:

Finish[i]=false;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]=false和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.