7.2 7.5 7.6 7.7 7.11

7.2 Consider the deadlock situation that could occur in the dining-philosophers problem when the philosophers obtain the chopsticks one at a time. Discuss how the four necessary conditions for deadlock indeed hold in this setting. Discuss how deadlocks could be avoided by eliminating any one of the four conditions.

答:死锁的四个条件:

  • 互斥条件。资源具有排他锁。

  • 占有和等待条件。已经得到了某个资源的进程可以再请求新的资源。

  • 不可抢占条件。已经分配给一个进程的资源不能强制性地被抢占,它只能被占有它的进程显式地释放。

  • 环路等待条件。死锁发生时,系统中一定有由两个或两个以上的进程组成的一条环路,该环路中的每个进程都在等待着下一个进程所占有的资源。

要避免死锁,可以要求当拿起筷子一段时间后不使用超时,从而被其它哲学家抢占。

7.5 In a real computer system, neither the resources available nor the demands of processes for resources are consistent overlong periods(months).Resources break or are replaced, new processes come and go, new resources are bought and added to the system. If deadlock is controlled by the banker’s algorithm, which of the following changes can be made safely (without introducing the possibility of deadlock), and under what circumstances?

a. Increase Available (new resources added).

如果增加资源不会导致其它资源临时不可用,则可以。

b. Decrease Available (resource permanently removed from system)

不一定可以,因为资源可能正在被使用。

c. Increase Max for one process (the process needs more resources than allowed, it may want more)

不一定可以,因为可能导致抢占资源,造成死锁。

d. Decrease Max for one process (the process decides it does not need that many resources)e. Increase the number of processes.

可以,但需要措施确保进程能够归还超额的资源。

f. Decrease the number of processes.

可以。

7.6 Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlock-free.

答:假设发生死锁,则根据鸽巢原理,4/3 > 1,则至少有一个进程能够满足其最大需求量。一旦该进程完成,就会释放最多 2 个资源。从而系统将有 4 个资源分配给两个进程,即便两个进程都占用两个资源,也能满足。

7.7 Consider a system consisting of m resources of the same type, being shared by n processes. Resources can be requested and released by processes only one at a time. Show that the system is deadlock free if the following two conditions hold:

和上一题同理,根据鸽巢原理,m/n > 1,所以一定有一个进程能完成。从而 m 个资源分配给 n - 1 个进程。相当于 $m' = m , n' = n-1$ 的情况。

7.11 Consider the following snapshot of a system:

image-20211120212750725

a. What is the content of the matrix Need?

$$ \begin{pmatrix}0&0&1&2\\ 1&7&5&0\\ 2&3&5&6\\ 0&6&5&2\\ 0&6&5&6\end{pmatrix}-\begin{pmatrix}0&0&1&2\\ 1&0&0&0\\ 1&3&5&4\\ 0&6&3&2\\ 0&0&1&4\end{pmatrix}=\begin{pmatrix}0&0&0&0\\ 0&7&5&0\\ 1&0&0&2\\ 0&0&2&0\\ 0&6&4&2\end{pmatrix} $$

b. Is the system in a safe state?

是,因为可以先分给需求小的 p3,p3 结束后剩下:

[1 5 2 0] + [0 6 4 2] = [1 6 6 2],从而可以分配给 p2

[1 6 6 2] + [2 3 5 6] = [3 9 11 8],从而可以分配给 p1, p4

c. If a request from process P1 arrives for (0,4,2,0), can the requestbe granted immediately?

可以。