严格交替如何保证有界等待? 假设有两个进程P⁰和P1。 假设turn=0,但P⁰不想进入CS。 P1 也想这样做。不会导致饥饿,那么如何保证有界等待呢?
严格交替意味着由于您所描述的场景而存在无限等待。如果轮到进程 2 并且它不想进入临界区,则进程 1 必须等待进程 2 进入并退出临界区,即使进程 1 可以安全地进入。更糟糕的是,如果进程 2 在进程 1 等待时停止,那么进程 1 将永远等待。
“严格”交替的算法违反了进度和有界等待属性。 顺便说一句,大多数“好”的交替算法仅在竞争的情况下才会这样做。例如,当临界区发生争用时,彼得森算法会在进程之间交替。但是,如果没有争用(如您所描述的情况),那么即使没有轮到进程,也可以进入临界区。因此,彼得森算法有界等待。
有界等待条件简单地说,“在一个进程发出进入其临界区的请求之后,在它被授予进入权限之前,
允许其他进程进入的轮数这仅仅意味着任何进程都不应该被其他进程绕过。 有界等待并没有说一个进程是否真的可以进入,它只是说不应该有绕过。
现在,在严格更改的情况下,满足有界等待,因为如果进程 0 进入临界区,那么下一个可以进入临界区的进程是进程 1。正如您所看到的,另一个进程的次数有限制进程,假设进程0可以在进程1获得许可之前进入CS。在本例中,界限为 1,因此过程是 1 界限的。因此,满足有界等待。
有界等待⇏免饥饿:即使满足有界等待,进程仍然可以被锁定在入口部分(
进度失败),就像您在问题中提到的情况一样。 免于饥饿⇏有限等待: 饥饿自由表示该过程最终可以进入其临界区,但这确实意味着等待时间是有限的。