测试和设置指令中的饥饿

Question

在GATE考试中提出了以下问题：

实现流程关键部分的enter_CS()和leave_CS()函数使用测试和设置指令实现，如下所示：

void enter_CS(X)
{
    while test-and-set(X) ;
}
void leave_CS(X)
{
   X = 0;
}

在上述解决方案中，X是与CS相关联的存储器位置，并且被初始化为0。现在考虑以下语句：

I.上述CS问题的解决方案是无死锁的

II.解决方案是无饥饿。

III.进程按FIFO顺序进入CS。

IV多个进程可以同时进入CS。

以上哪一项陈述是正确的？

正确答案是选项I。

虽然I和IV选项对我来说很清楚，但我不能理解饥饿在这里是如何可能的。

如果有人能帮我解释一下，那就太好了。谢谢。

Answer 1

当一个进程在这个enter_CS方法中执行while循环时，它会在每次调用之间间隔一段时间来调用test-and-set方法。(此时间间隔可能取决于操作系统如何安排每个进程使用CPU)

假设process_0在process_1已经在临界区时开始执行while循环。如果process_1总是在此时间间隔内退出并进入临界区，则process_0永远不会成功进入cs。(当等待一个临界区的进程数量很大时，情况会变得更糟)

Peterson Algorithm提供了一个“标志”turn来避免这种饥饿情况。

Answer 2

上面的代码保证，如果多个进程试图获取锁，其中一个进程将获得锁。锁的获取并不依赖于进程的到达。考虑这样一个场景，当总是有两个以上的进程试图获取锁时，不能保证特定进程最终会获得锁。我希望FIFO顺序中的收购对你来说是清楚的。