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

Question

这里在this video at 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是一个原子操作returns将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循环也会导致内核间流量。因此，您可能会使内核间总线饱和，从而减慢其他无辜线程（以及持有锁的线程）的爬行速度。

以此类推

我讨厌在原始代码中看到测试和设置循环（这只适用于玩具代码，即使是很短的时间）但至少它不会一直旋转另一个线程持有锁作为你会的。

Answer 2

“有一个通过使用等待通道避免忙等待的锁的实现”——我仍然可以看到一个忙等待，以这种 while (test_and_set(guard));) 的形式。但代码的本质是让忙碌等待一小段时间。你所有的代码都是这样的：

声明一个锁队列，进程可以在其中为自己注册锁。
将有兴趣获取锁的进程添加到该锁队列。
当一个已经持有的进程释放锁时，从锁队列中释放一个进程。

获取()

while (test_and_set(guard)); -- 获取编辑锁队列的密码。

if (value == BUSY) {release_guard_and_wait();} -- 如果已经获得了锁，将自己加入到锁队列中，并释放对锁队列的守卫，以便其他进程可以将自己加入到锁队列中。等到你被叫醒。

else { value = BUSY; guard = 0;} -- 如果没有进程获取锁，则自己获取并释放锁队列上的守卫。

释放()

while (test_and_set(guard)); -- 获取编辑锁队列的密码。

if (!wait_queue.empty()) wake_one(); -- 如果锁队列不为空则唤醒一个进程。

else value = FREE; -- 如果锁队列中没有进程在等待锁，就释放锁。

guard = 0; -- 当然在最后，释放锁队列上的守卫，这样其他进程就可以编辑队列了。

现在来看您修改后的代码，您可以立即发现两个进程运行 acquire() 和 release() 可以同时编辑队列。此外，多个进程同时尝试获取锁也可能会破坏锁队列并使其处于损坏状态。

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

Why a guard exists in this implementation of a lock?

multithreading

synchronization

locking