【正确答案】解法1:本题中只有一种资源,不妨设Max
i为第i个进程的资源总需要量,Need
i为第i个进程还需要的资源数量,Allocation
i表示第i个进程已经分配到的资源数量,Available为系统剩余的资源数量,其中i=1,2,…,n。
若n=0,则没有进程,必然不会死锁,所以现在证明n≥1时的情形,如下所示:
假设此系统可以发生死锁。
系统剩余的资源数量为Available(Available≥0),由假设可知,因为系统处于死锁状态,所以Available个资源无法分配出去,所以每个进程的Need
i都大于Available。
即
Needi≥Available+1
所以
∑Needi≥n×(Available+1)=n×Available+n ①
因为剩下的资源数是Available,所以已分配出去的资源数为m-Available。即
∑Allocationi=m-Available ②
由式①和式②可以得到:
∑Needi+∑Allocationi≥n×Available+n+m-Available=(n-1)×Available+m+n ③
又因为n≥1,所以n-1≥0;又因为Available≥0,所以(n-1)×Available≥0。 ④
由式③和式④可以得到:∑Need
i+∑Allocation
i≥0+m+n=m+n ⑤
由题意可知
∑Maxi<m+n ⑥
又因为Max
i=Need
i+Allocation
i,所以:∑Max
i=∑Need
i+∑Allocation
i ⑦
由式⑥和式⑦得
∑Needi+∑Allocationi<m+n ⑧
由假设推出的式⑤与由题意推出的式⑧相矛盾,所以假设是错误的,即此系统无法发生死锁。
本题还有一种较为简便的解法,供大家参考。
解法2:设Max
i表示第i个进程的最大资源需求量,Need
i表示第i个进程还需要的资源量,Allocation
i表示第i个进程已经分配的资源量,由题设条件可得
∑Maxi=∑Allocationi+∑Needi ①
假设该系统已经发生死锁,那么m个资源应该已经被全部分配出来,且各个进程都没有得到足够的资源运行(所有进程Needi≥1)即
∑Allocationi=m ②
∑Needi≥n ③
由式①和式②可得
∑Needi<n ④
由于式③和式④矛盾,故不可能发生死锁。
式②中没有考虑∑Allocation(i)<m的情形。不一定所有的资源都分配完了才会发生死锁,可能还有剩余资源,当剩余资源的数量小于任何一个进程的需求量时也会发生死锁。这种方法将系统的资源分配方式假设为当进程有资源请求时,逐步分配可用资源,直到满足请求或无可用资源,因此会出现资源全部分配的情况。