一种操作系统的死锁预防算法
本文主要探讨了一种基于调整操作系统的资源分配策略的死锁预防算法，即要求进程在申请新的资源前必须先释放所有的资源。采用这种算法可以避免死锁的发生，但需要以增加系统开销为代价。因此，我们对算法进行了改进，改进后的算法在实现死锁预防功能的基础上减少了分配开销对系统的影响。
【关键词】操作系统 死锁预防 资源分配 效率 改进
在计算机操作系统的理论研究与实现过程中，面临着一个始终没有被很好地解决的问题，这便是操作系统的死锁现象。所谓死锁，是指在一组进程当中，每一个进程都占用着若干资源，同时它又在等待另外一个进程所占用的其他资源，从而造成的所有进程都无法进展下去的现象，这种现象称为死锁，这一组相关的进程就称为死锁进程。在死锁状态下，每一个进程都无法运行，因为他们都在等待其他进程释放其所占据的资源。
1 预防死锁发生的算法
如前所述，对资源的竞争访问是产生死锁的根本原因。1971年，Coffman提出了死锁发生的四个条件，即互斥访问条件，请求和保持条件，不可抢占条件，环路等待条件。只有当这四个条件同时成立时，才有可能会出现死锁。
为了解决死锁的问题，人们提出了一些列算法。包括银行家算法，运用资源轨迹图来避免死锁的算法以及在当前的操作系统当中广泛采用的“鸵鸟”算法。这些算法的提出对计算机操作系统的研究起了很大的推动作用。在学习操作系统课程的过程中，我认为有一种方法可以很好地预防死锁的发生，所以在此做一简单介绍。
1.1 算法一
对于系统中的每一个进程，执行如下操作：
（1）进程在运行过程中，发现还要申请其它的资源，转（2）。
（2）进程释放已经占有的全部不可抢占资源，转（3）。
（3）进程一次性申请在第二步中释放的资源与在第一步中所需的新的资源，转（4）。
（4）若申请资源成功，即得到所需的全部系统资源，继续运行，并转（6）。
（5）若申请资源失败，即进程所需的全部系统资源无法一次性得到满足，则该进程需要先唤醒阻塞队列中的第一个进程，然后进入阻塞队列的尾部变为阻塞状态。算法结束。
（6）进程运行结束时释放资源并唤醒在阻塞队列中的第一个进程。算法结束。
可以看出，这个算法的实质就是要求进程在请求一个新资源时，先暂时释放它已经占用的各个资源，然后再重新申请它所需的全部资源，包括它原来占用的资源和新的资源。
事实上，如果系统中的所有进程都采用这种运行方式，系统将肯定不会发生死锁现象。但是这种方式可能会降低系统的使用效率，因为如果所有进程都要在每一次申请资源时先释放已有资源再去重新申请，则进程浪费在申请资源上的时间还是比较多的。基于此，我们可以对算法一做出如下改进。
1.2 算法二
对于系统中的每一个进程，执行如下操作：
（1）进程在运行过程中，发现还要申请其它的资源，执行第二步。
（2）进程判断该资源属于可抢占资源还是不可抢占资源，如果是可抢占资源，则直接申请，如果是不可抢占资源，则转第三步。
（3）进程检查当前阻塞队列是否为空，如果为空，则说明当前系统中没有被阻塞的进程，转（4）；如果阻塞队列非空，说明当前系统中存在被阻塞的进程，转（6）。
（4）若系统中剩余的资源数大于进程申请的资源数，则申请资源成功，转（10）。否则，转（5）。
（5）若系统中剩余的资源数小于进程申请的资源数，则该进程进入阻塞状态。算法结束。
（6）进程释放已经占有的全部不可抢占资源，转（7）。
（7）进程一次性申请在第二步中释放的资源与在第一步中所需的新的资源，转（8）。
（8）若申请资源成功，即得到所需的全部系统资源，进程继续运行，转（10）。否则，转（9）。
（9）若申请资源失败，即进程所需的全部系统资源无法一次性得到满足，此时该进程需要首先唤醒阻塞队列中的第一个进程，然后该进程进入阻塞队列的尾部转化为阻塞状态。算法结束。
（10）进程运行结束时释放占有的所有资源并唤醒在阻塞队列中的第一个进程。算法结束。
在该算法中，首先要判断申请的资源是可抢占资源还是不可抢占资源，如果是可抢占资源，则一定不会引发死锁，因为进程得到该资源后依然无法满足死锁所发生的四个必要条件之一的不可抢占条件。所以，我们在进行死锁避免的考察时，只需对不可抢占资源进行讨论。接下来需要检查阻塞队列是否为空，为了提高系统的运行效率，我们可以规定只有当阻塞队列中已经有进程时才让其它进程执行在申请资源前先释放资源的操作。因为在发生死锁时至少要有两个进程同时处在阻塞队列中，所以我们允许第一个申请非抢占资源的进程在执行到算法二的第（5）项时进入阻塞状态。
采用这种算法可以保证系统当中不会出现死锁现象，并且对操作系统的运行效率的影响相对较小。
2 结论
本文简单介绍了一种操作系统的死锁预防算法，即要求进程在申请资源前先释放它所占有资源，然后再一次申请全部的资源。这种算法能够保证系统不发生死锁，但频繁地释放与申请资源也增加了系统开销，因此本文对该算法进行了改进。在对运行时的稳定性要求较高的操作系统中，在进程调度时使用该算法是能够满足系统运行要求的。
参考文献
[1]谌卫军等.操作系统[M].北京：清华大学出版社，2012.
[2] Andrew S.Tanenbaum. Modern Operating Systems[M].北京：机械工业出版社，2002.
作者单位
海南大学 海南省海口市 570228
