Posted on 2007-03-21 19:00
kk 阅读(5353)
评论(5) 编辑 收藏 引用 所属分类:
Algorithm
银行家算法是著名的操作系统用来解决死锁问题的算法。
它是如何实现解决死锁问题的呢？
今天稍微学习了一下，就稍微说一下其原理吧，免得忘了。其实原理很简单！
Banker algorithm
最重要的一点是：保证操作系统的安全状态！这也是操作系统判断是否分配给一个进程资源的标准！那什么是安全状态？举个小例子，进程
P
需要申请
8
个资源（假设都是一样的），已经申请了
5
个资源，还差
3
个资源。若这个时候操作系统还剩下
2
个资源。很显然，这个时候操作系统无论如何都不能再分配资源给进程
P
了，因为即使全部给了他也不够，还很可能会造成死锁。若这个时候操作系统还有
3
个资源，无论
P
这一次申请几个资源，操作系统都可以满足他，因为操作系统可以保证
P
不死锁，只要他不把剩余的资源分配给别人，进程
P
就一定能顺利完成任务。
为什么银行家算法是可行的呢？这里需要严格的证明一下。我这里就简单得说一下吧。不管任何时候，操作系统分配资源的时候都可以保证当前接受资源的进程不会陷入死锁，因为操作系统总是可以满足该进程需要的资源的。
假设有
n
个进程
{p1, p2, p3, … pn}
，最后一个分配到资源的是
pi
，
pi
还需要
mi
个资源，假设此时操作系统还有
m
个资源剩余。那么很显然
m>=mi
！而且如果之后操作系统又把资源分配给其他进程了，假设是
pj
，
pj
还需要
mj
个资源，同理可知
m>=mj
！也就是说在所有的进程中，还需要的资源数总是有小于
m
的！这样就可以保证资源数永远不会为
0
，即使可能暂时性为
0
。另外，还需要保证资源数不会减少！而且，所有已经分配到资源的进程总有一天会归还它所拥有的资源！根据操作系统再分配的时候的状态即可判定。
胡说八道了一通。。。不知有没有把问题讲明白了，还是越讲越糊涂？
GL & HF