🏷️ 知识点：临界资源
��某个十字路口，每个车道只允许一辆汽车通过，且允许直行、左拐和右拐，如图 1 所示。如果把各个方向的车看成进程，则需要对这些进程进行同步，那么这里临界资源个数至少应该有（ ）个。
A. 1 B. 2 C. 4 D. 不确定
[tag_link]
正确答案：C
不妨如上图所示，把十字路口车道的公共区域分为 4 块，分别为图上的 1、2、3、4，直行的车辆需要获得该方向上的两个邻近的临界资源，如北方开来的车辆需要获得 1、2 两个临界资源。 > 南方开来的车需要获得 3、4 两个临界资源。 > 而往右转的车辆则只需要获得一个临界资源，比如北方来车右转的情况需要获得 1 这个临界资源。 > 左转的情况需要获得 3 个临界资源，比如北方来车左转组需要 1、2、3 号临界资源。 > 综上所述，4 个临界资源便可以很好地保证车子不相撞（即互斥的效果）。 > 当然只用 4 个信号量还是很容易造成死锁的，不过这并不是本题要考虑的问题，题目中问到的是至少用几个信号量。 >
也可以用排除法来做该题，该路口可以有南北方向车同时直行，所以临界资源个数大于或等于 2，排除 A。 > 该路口可以 4 个方向车都左转，所以临界资源个数大于或等于 4，排除 B。 > D 选项通常不会选，所以选 C。 >
系统中有3个不同的临界资源R1、R2和R3，被4个进程p1、p2、p3及p4共享。各进程对资源的需求为：p1申请R1和R2，p2申请R2和R3，p3申请R1和R3，p4申请R2。若系统出现死锁，则处于死锁状态的进程数至少是（ ）。
A. 1 B. 2 C. 3 D. 4
[tag_link]
正确答案：C
对于本题，先满足一个进程的资源需求，再看其他进程是否能出现死锁状态。因为p4只申请一个资源，当将R2分配给p4后，p4执行完后将R2释放，这时使得系统满足死锁的条件是R1分配给p1，R2分配给p2，R3分配给p3（或者R2分配给p1，R3分配给p2，R1分配给p3）。穷举其他情况如p1申请的资源R1和R2，先都分配给p1，运行完并释放占有的资源后，可以分别将R1、R2和R3分配给p3、p4和p2，也满足系统死锁的条件。各种情况需要使得处于死锁状态的进程数至少为 3。
关于临界区问题（critical section problem）的一个算法（假设只有进程 P0 和 P1 可能会进入该临界区）如下（i 为 0 或 1），该算法（ ）。
A. 不能保证进程互斥进入临界区，且会出现“饥饿” B. 不能保证进程互斥进入临界区，但不会出现“饥饿” C. 保证进程互斥进入临界区，但会出现“饥饿” D. 保证进程互斥进入临界区，不会出现“饥饿”
[tag_link]
正确答案：B
该算法不能保证进程互斥进入临界区。 > 分析两个进程 P0 和 P1 的执行流程：假设初始时共享变量 turn=0，P0 首先执行，检查 turn!=0 为假，跳过 turn=0 的设置，再检查 turn!=0 为假，不跳转，然后设置 turn=1 并进入临界区。 > 此时 P1 也开始执行，检查 turn!=1 为假，跳过 turn=1 的设置，再检查 turn!=1 为假，不跳转，设置 turn=0 并进入临界区。 > 这样，P0 和 P1 同时处于临界区，违反了互斥条件。 >
虽然互斥无法保证，但算法不会导致“饥饿”（即某个进程永远无法进入临界区）。 > 因为每个进程在尝试进入时，都会通过循环检查 turn 是否等于自己的标识 i。 > 无论 turn 初始值如何，进程在执行中总会将 turn 设置为对方或 0，使得另一个进程在后续尝试中能够通过检查并进入临界区。 > 例如，P0 退出临界区时设置 turn=0，之后 P1 尝试时可能先设置 turn=1 再检查通过，从而进入临界区。 > 两个进程在竞争中有机会交替进入，没有进程会被永久阻塞。 >
因此，该算法不能保证互斥，但不会出现饥饿。 >