经典算法

您所在的位置:网站首页 假设有n个进程,m个资源,每个进程 经典算法

经典算法

2024-07-16 04:09| 来源: 网络整理| 查看: 265

假如有多个进程争夺一种资源,这个资源共有n个,每个进程需要这种资源m个,并且每个进程当得到某一个资源之后不会直到执行完成都不会释放这个占有的资源,只有这个进程的需求得到满足之后他才会执行完成,那么问最多有多少个这样的进程争夺这m个资源,一定不会发生死锁?

其实这个问题的简化版本是哲学家问题,哲学家问题是说有n个餐具,每个哲学家需要2个餐具才能用餐,问最多可以有多少个哲学家,才能保证每个哲学家能够用餐完成。

我们可以考虑有m个哲学家围成一圈,按顺序给每个哲学家分一个餐具,假如每个哲学家都分到了一个餐具,这个时候餐具还有剩余,那么对于m个哲学家而言,他们一定能够用餐完成。

也就是说只要n > m * (2 – 1) ,那么对于这m个哲学家,他们一定能够用餐完成,当n < m * 1,的时候,有可能出现哲学家不能用餐完成,循环等待的情况,也就是说最多可以有n – 1个哲学家用餐。

再回到题目的问题,假如餐具有n个,每个哲学家需要m个餐具,有t个哲学家,那么当n > t * (m - 1)的时候,不会出现循环等待,那么同理,当n % (m – 1) !=0的时候,最多有n / (m – 1)个哲学家,当n % (m – 1) == 0的时候,最多有n / (m – 1) – 1个哲学家。



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3