multithreading - 为什么在这个锁的实现中存在一个守卫？

Question

在这里this video在 26:00 ，有一个锁的实现，通过使用等待队列来尽量避免忙等待，代码如下(伪代码):

int guard = 0;
int value = FREE;

Acquire()
{
    while (test_and_set(guard));

    if (value == BUSY) {
        release_guard_and_wait();
    } else {
        value = BUSY;
        guard = 0;
    }
}

Release()
{
    while (test_and_set(guard));

    if (!wait_queue.empty())
        wake_one();
    else
        value = FREE;
        
    guard = 0;
}

test_and_set是一个原子操作，返回旧值 guard并将其设置为 1 .
release_guard_and_wait也必须是原子的，以避免潜在的问题:
如果线程等待然后在唤醒时释放保护，则没有线程能够获取它。
如果线程释放守卫然后等待，可能会发生这种情况:

线程 1(在获取中)-> guard = 0;

线程 2(在发布中)-> test_and_set(guard);

线程 2(在发布中)-> wake_one();

线程 1(在获取中)-> wait();

线程 2(在发布中)-> guard = 0;

wake_one唤醒一个线程(从等待队列中取出并放入就绪队列中)。

我的问题是，为什么使用 guard ?这不是多余的吗？
无 guard的代码可能看起来像这样:

int value = 0;

Acquire()
{
    while (test_and_set(value))
        wait();
}

Release()
{
    value = 0;
    wake_one();
}

在某些情况下，这两种实现的行为会有所不同吗？使用守卫有什么好处吗？

Answer 1

您的代码有两个大问题。
首先，您的代码具有竞争条件。考虑:

线程 1 持有锁，它调用 Release .

线程 2 想要锁，它调用 Acquire .

线程1套value到零。

线程 2 通过 test_and_set .

线程 1 调用 wake_one ，它什么都不做。

线程 2 调用 wait ，它正在等待已经发生的唤醒。

糟糕，僵局。这就是为什么你需要一个原子 release_guard_and_wait功能。
第二个问题:
如果两个线程调用 Acquire同时，您的代码只会导致其中之一等待。另一个会做可怕的事情，例如它会:

保持一个核心忙碌，防止其他核心在许多具有自适应时钟速度的 CPU 上达到其峰值速度。

浪费电。

使用超线程和类似技术在 CPU 上的同一内核中运行另一个线程。

当纺线最终确实通过了 test_and_set循环，它将需要大量的错误预测分支惩罚。因此，如果有多个线程在等待，每个线程都会在获得锁时停止。哎呀。

在某些 CPU 上，test_and_set即使比较失败，循环也会导致内核间流量。因此，您可能会使内核间总线饱和，从而减慢其他无辜线程(以及持有锁的线程)的速度。

等等。
我讨厌在原始代码中看到测试和设置循环(这仅适用于玩具代码，即使是很短的时间)，但至少它不会像你一样在另一个线程持有锁的整个时间内旋转。