问答题 考虑由n个进程共享的具有m个同类资源的系统,证明:如果对i=1,2,…,n,有Needi>0而且所有最大需求量之和小于m+n,那么该系统是死锁无关的。
【正确答案】解法1:本题中只有一种资源,不妨设Maxi为第i个进程的资源总需要量,Needi为第i个进程还需要的资源数量,Allocationi表示第i个进程已经分配到的资源数量,Available为系统剩余的资源数量,其中i=1,2,…,n。
若n=0,则没有进程,必然不会死锁,所以现在证明n≥1时的情形,如下所示:
假设此系统可以发生死锁。
系统剩余的资源数量为Available(Available≥0),由假设可知,因为系统处于死锁状态,所以Available个资源无法分配出去,所以每个进程的Needi都大于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。 ④
由式③和式④可以得到:∑Needi+∑Allocationi≥0+m+n=m+n ⑤
由题意可知
∑Maxi<m+n ⑥

又因为Maxi=Needi+Allocationi,所以:∑Maxi=∑Needi+∑Allocationi
由式⑥和式⑦得
∑Needi+∑Allocationi<m+n ⑧

由假设推出的式⑤与由题意推出的式⑧相矛盾,所以假设是错误的,即此系统无法发生死锁。
本题还有一种较为简便的解法,供大家参考。
解法2:设Maxi表示第i个进程的最大资源需求量,Needi表示第i个进程还需要的资源量,Allocationi表示第i个进程已经分配的资源量,由题设条件可得
∑Maxi=∑Allocationi+∑Needi

假设该系统已经发生死锁,那么m个资源应该已经被全部分配出来,且各个进程都没有得到足够的资源运行(所有进程Needi≥1)即
∑Allocationi=m ②

∑Needi≥n ③

由式①和式②可得
∑Needi<n ④

由于式③和式④矛盾,故不可能发生死锁。
式②中没有考虑∑Allocation(i)<m的情形。不一定所有的资源都分配完了才会发生死锁,可能还有剩余资源,当剩余资源的数量小于任何一个进程的需求量时也会发生死锁。这种方法将系统的资源分配方式假设为当进程有资源请求时,逐步分配可用资源,直到满足请求或无可用资源,因此会出现资源全部分配的情况。
【答案解析】