東京大学 情報理工学系研究科 コンピュータ科学専攻 2015年8月実施 専門科目I 問題4

标签：

• Tokyo-University
• Deadlock-and-Starvation

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

系统有进程 $p_1,\ldots,p_M$ 和同类资源 $r_1,\ldots,r_N$。进程 $p_i$ 必须同时占有 $n_i$ 个资源才能完成；资源只被占用而不被消耗，进程完成后会释放；同一资源不能同时分配给多个进程。

（1）当 $M=N=2$ 且 $n_1=n_2=2$ 时，举例说明死锁发生的资源分配与释放时序。

（2）举出一种防止（1）中死锁的方法，并说明限制或缺点。

（3）当 $M=3,N=4,n_1=n_2=n_3=2$ 时，判断能否发生死锁并说明理由。

（4）设 $M,N\ge1$ 且 $1\le n_i\le N$，记 $n=\sum_i n_i$。用 $M,N$ 表示保证任意 $n_1,ldots,n_M$ 都不会死锁的最大 $n$。

Kai

(1)

先把 $r_1$ 分配给 $p_1$，再把 $r_2$ 分配给 $p_2$。此后 $p_1$ 等待 $r_2$，$p_2$ 等待 $r_1$；两者都未取得所需的两个资源，因而都不会完成并释放资源。

(2)

可采用一次性分配：只有在某进程所需的全部资源均空闲时，才把这些资源同时分配给它；否则该进程不占有任何资源并等待。这样消除了“占有并等待”，不会形成上述死锁。

缺点是已经空闲的部分资源也可能长期闲置，并可能造成等待时间增加或饥饿；实现时还需用互斥操作保证“检查并分配”具有原子性。

(3)

不会。若三个进程均未完成，则每个进程最多只能占有 $n_i-1=1$ 个资源，总共至多占有 $3$ 个。由于 $N=4$，至少还有一个空闲资源；将它分配给某个已占有一个资源的进程，该进程即可凑齐两个资源、完成并释放资源。因此不存在所有进程都无法继续的状态。

(4)

在死锁状态中，每个未完成进程至多持有 $n_i-1$ 个资源，同时必须没有空闲资源。因此死锁的必要条件为

$$N\le\sum_{i=1}^M(n_i-1)=n-M.$$

所以当 $n\le N+M-1$ 时，死锁不可能发生。

该界是紧的：当 $M,N\ge2$ 时，取

$$n_1=N,\qquad n_2=2,\qquad n_3=\cdots=n_M=1,$$

则 $n=N+M$。让 $p_1$ 持有 $N-1$ 个资源、$p_2$ 持有剩余一个资源，二者都还差一个资源，便形成死锁。边界情形 $M=1$ 或 $N=1$ 时，可行的最大总需求本身也等于 $N+M-1$。故答案为

$$\boxed{N+M-1}.$$