操作系统死锁检测：资源分配图化简分析

操作系统课程设计

 

设计内容：

       进程死锁的检测：资源分配图的化简判断是否有死锁发生

 

设计要求：

       ・建立所需的数据结构。

       ・从文件中读取资源分配的情况（文件格式自定义）。

       ・编写资源分配图的化简算法。

       ・每化简一步，在屏幕上显示化简的当前结果。

       ・最后给出结论，是否死锁。如果死锁，给出死锁进程和资源。

 

设计思路：

       程序中主要涉及两个方面：进程、资源。两者通过占有和申请发生联系。因此对于每一个进程Pi，建立“占有”和“申请”的数据结构来保存与之相关联的资源（由于事先不知道进程拥有和申请的资源数，故用Vector作为数据结构）。同时记录下程序处理的总的进程数目和资源数目。对于资源，另建立两个数组res和work分别记录第i类资源的总数和当前可用数。

       从文件中读入资源和进程的情况时，要进行一些判断。①处理的资源和进程数目不得超过500（500已满足当前实际机器的情况）。②资源及进程的编号不得超过相应的数目也不得小于0。③资源的起始值不应该小于0。 ④起始情况下，所有进程拥有的第i资源总数不应该比其总的资源数目还要多。

    由于在理论上已经证明，化简的次序不影响化简的最终结果。所以化简的过程就是不停的寻找满足条件（此进程所申请的资源全部都可以满足）的进程进行化简（即把它拥有的资源加到work数组中），直到不再能找到这样的进程为止。然后检查所有的进程，如果仍有未被化简的进程，则表明死锁已经产生。此时记录下发生死锁的进程编号。然后，为进一步明确哪些进程在哪些资源上发生死锁，给定一个进程入口点采用DFS搜索和次进程相关的所有进程。

       为了能在每一步化简后显示当前进程资源的状况，定义了两个画图函数。一个是根据当前资源和进程的“占有”和“申请”状况，画出整体的资源分配图。另一个是在每次化简掉一个进程时删除和它相关的所有边。

       程序在VC++6.0中调试、验收通过。

 

程序主要模块和相关定义介绍：

       ・主函数模块main()： 在其中调用读入模块和化简模块，只是个驱动。

・读入模块read_data()：此模块分为两个部分（对应于文件的格式），首先是读入资源的情况，包括资源的种类数和每类资源的数目。然后是进程的情况，包括进程的个数，每个进程“占有”的资源和“申请”的资源。所有的输入都经过合法性检查。

・化简模块predigest()：首先调用初始画图模块根据初始情况下的进程资源关系画出最初的资源分配图。然后，预处理那些不申请任何资源便可以运行的进程（即把它的占有资源添加到work数组中）。然后进入化简的主体部分，这时，需要设置一个标志以表示这轮扫描是否化简了进程，若这轮扫描化简了进程，则应该进行下一轮扫描，因为可能这轮释放的资源可以使用前不可以化简的进程在下一轮扫描时被化简。否则，不再进行下一轮扫描。然后，把所有的未被化简的进程放到一个Vector中。判断这个Vector是否为空，不为空则表示有进程发生了死锁。输出相应的提示信息后，初始化DFS在中需要的一些数据结构。然后，对每一个死锁进程，若它未被访问过，则由它作为入口，进入DFS，搜索所有和它的死锁有关系的进程和资源。当搜索结束后，输出相关的资源（相关的进程已经在DFS中输出）。若Vector为空，则表示所有的进程都顺利的运行完，则只要简单的输出提示信息即可。

・初始画图模块Draw()：参考在控制台下画图的程序，对每一类资源画一个圈，这类资源的数目在圈中用小圆来表示，有几个资源就画几个小圆。对每一个进程，画一个矩形。然后根据每个进程的“占有”、“申请”状况，矩形和圈之间用绿线表示此进程拥有一个此类资源；用红线表示此进程申请一个此类资源。由于在控制台下画曲线在坐标的确定和布局上比较困难，本程序没有像大多数教材中表示资源分配图那样用环形布局，而是变通的用两行表示，一行表示资源，一行表示进程。

・化简时画图模块ers()：要把某个进程的所有相关边都消去，只需要用窗口的背景色（黑色）重新绘制一下需要擦除的线即可。

・输入的资源分配图文件格式：按以下次序在文件中存放数据：资源种类、每类资源的数目、进程数目、每个进程的相关信息（进程号、进程拥有的资源数目、每个资源的种类号、进程申请的资源数目、申请的资源种类号）

 

程序测试：

①  死锁的情况：

输入文件：2       1    1     2     0     1     0     1     1     1     1     1     1     0