互斥过滤算法：弱公平

Question

我指的是这个滤波器算法说明： http://cs.nyu.edu/wies/teaching/ppc-14/material/lecture02.pdf

它说，它提供了微弱的公平性和某些线程可以采取的次超越arbitary号。 （幻灯片98）

我无法理解这部分，因为写入受害者值的最后一个必须等​​待并且已经等待的线程移动到下一个层次，那么一个线程如何在这里被超越？

Answer 1

让我们考虑4个线程（t0，t1，t2和t3）使用过滤器锁来获得互斥。

我们假设t0陷入0级，t1陷入1级，依此类推。因此t3进入其关键部分并在之后解锁。注意：t0到t2卡在while((∃k != i) level[k] >= L) && victim[L] == i) {};这实际上是几行代码（见Filter Lock Algorithm）。从现在开始，我将把这段代码称为（C1）。现在t2继续进入临界区并解锁，然后t1。这意味着t0可能会离开0级（C1）......但这并不意味着它不能被超越！现在t3，t2和t1很可能再次获得锁定。结果，三个线程中的一个被过滤掉并且停留在0级（C1），因为一个线程是“受害者”，比如说t1。当t0满足所有离开的要求（C1）时，它仍然可以在（C1）的for循环中，因为它可能由于各种体系结构原因而“运行得慢”。这允许t2和t3超过t0。