题目一

考虑下图所示的交通死锁的情况：

（1）请说明这个实例中死锁的 4个必要条件
（2）请设计条简单的规则来避免产生死锁

解：（1）该实例中死锁的四个必要条件：四个交叉路口在同一个时间点只能通过一辆车（互斥）；车1占据路口一并等待车3通过路口三、车3占据路口三并等待车4通过路口四、车4占据路口四并等待车2通过路口二、车2占据路口二并等待车1通过路口一（即占有并等待）；当路口有车辆时其它车辆无法经过该路口（非抢占）；车1等待的路口三正在被车3占有、车3等待的路口四正在被车4占用、车4等待的路口二正在被车2占有、车2等待的路口一正在被车1占有（循环等待）
（2）可以设置红绿信号灯，前一分钟可以让横向车通过，后一分钟可以让纵向车通过；每个一分钟进行一次轮转

题目二

考虑如下系统：该系统包含 3 个进程，共享同一类型的资源 4 个，每一个进程最多需要 2个该类型的资源，试说明为什么该系统不会发生死锁。

解：该系统包含3个进程，共享同一类型的资源有4个，每一个进程最多需要2个该类型的资源，则无论如何，都有一个进程可以得到2个该类型的资源，因此不需要等待其它进程释放该共享资源就可以使用该共享资源了，故可以顺利完成释放这两个资源，释放之后，其它的两个进程就也可以顺利的执行下去了。
通解：一个系统包含b个进程，共享同一类型的资源a个，每个进程最多需要c个该类型的资源；假设此时一个进程已经分配了c个该类型的资源，另外b-1个进程分配了c-1个该类型的资源，那么只需要满足（b-1）*（c-1）+c=b(c-1)+1<=a即可以不发生死锁。

题目三

现有单实例资源系统：进程 P1 占有资源 R2，请求资源 R1；进程 P2 占有资源 R1，
请求资源 R3 R4 R5；进程 P3 占有资源 R4，请求资源 R5；进程 P4 占有资源 R5，请求资源 R2；进程 P5 占有资源 R3，请求资源 R1；
（1）请画出对应的资源分配图和资源等待图；
（2）请问该系统中存在死锁吗？并请给出解释。

解：资源分配图和资源等待图分别为上图和下图


存在死锁，进程P1、P2、P4构成了一个有向环；P2、P5也构成了一个有向环；
P4等待P1占有的资源R2，P1等待P2占有的资源R1，P2等待P4占有的资源R5；
P2等待P5占有的资源R3，P5等待P2占有的资源R1

题目四

考虑系统的情况如下图所示，请依据银行家算法回答如下问题：

（1）请给出 Need 矩阵。
（2）该系统目前是否是安全的？
（3）如果 P1 请求资源 (0, 4, 2, 0)，是否应该给该进程立即分配资源？

解：

1. Need矩阵：
   A B C D
   P0 0 0 0 0
   P1 0 7 5 0
   P2 1 0 0 2
   P3 0 0 2 0
   P4 0 6 4 2

2. 能找到一个安全序列<P0,P2,P3,P4,P1>，系统可以按照这一安全序列为每个进程分配不超过其最大值的资源并能避免死锁

3. 假设资源分配给P1，此时Allocation、Need、Available矩阵如下所示：
   Allocation矩阵：
   A B C D
   P0 0 0 1 2
   P1 1 4 2 0
   P2 1 3 5 4
   P3 0 6 3 2
   P4 0 0 1 4
   Need矩阵：
   A B C D
   P0 0 0 0 0
   P1 0 3 3 0
   P2 1 0 0 2
   P3 0 0 2 0
   P4 0 6 4 2
   Available矩阵：
   A B C D
   1 1 0 0
   Need0<Available，所以进程P0可以顺利完成，资源被回收；Available=（0，0，1，2），之后找不到一个安全的序列使得进程P1，P2，P3，P4顺利结束