×

Loading...

事实上这个问题有个隐形的属性几乎没有书讲过,那就是多余的resource从代数的角度来说必须是等于 a= (p -sup[acuirable resource]) mod p, 且a>=50% useable resource.

我当年读研时候具体研究过这个问题。

即能拿满的resource状态下,其剩余resource在哲学家modulus状态下必须超过一半的acquirable resource才行,且resource 数不能是maximum acquirable的倍数。举个糖炒栗子:

7个哲学家,7个筷子,acquirable resource是2, 那么最大 sup[acquirable resource]其实是 6个筷子, 那么7(p)-6=1 mod 7, 且 1=50% * 2(筷子能工作的数)。

也就是说如果resource和需求者,从代数上不符合这个式子的时候,resource分配反而是很容易的,举个例子,如果是8个哲学家,8个筷子,那么每次间隔拿筷子2个,根本不用semaphore,recursive decision就可以,因为这个时候8(p)-8=0 mod 8, 因为和2是4倍偶数关系(resource数 8 是acquirable (2)的4倍)。

这个问题有一个极值讨论的问题,就是什么状态下,resource调度是个recursive最深问题,我记得当时做过一个模公式,有一个sup极值的状态的。并且还有很多特例的,比如3个时候,反而不需要深度recursive分配resource,所有拿起的等待即可,我记得好像有个公式是如果gcd(p(3),2)=1的时候是这个状态。

这个问题的深入讨论非常复杂。

Sign in and Reply Report