Kisser Leon

这个kisser不太冷
posts - 100, comments - 102, trackbacks - 0, articles - 0

银行家算法学习

Posted on 2007-03-21 19:00 kk 阅读(5022) 评论(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

Feedback

# re: 银行家算法学习  回复  更多评论   

2007-03-22 10:37 by jeanofne
呵呵,前几天 在看数据库,刚好看到 银行家算法,书上讲的不太详细 ,现在听你讲了 ,一下子都懂了 。。

# re: 银行家算法学习  回复  更多评论   

2008-05-20 08:57 by liuhong
very good

# re: 银行家算法学习  回复  更多评论   

2008-06-17 18:13 by haha
有没有C的源程序---银行家算法源程序

# re: 银行家算法学习  回复  更多评论   

2008-11-26 08:14 by
很好,比我们老师讲的简易多了。

# re: 银行家算法学习  回复  更多评论   

2010-02-09 18:36 by 花皓
这个问题楼主想过吗
一个进程究竟需要多少资源
事先可以知道吗

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理