c++ - Linux 3.0 : futex-lock deadlock bug?

Question

// SubFetch(x,y) = atomically x-=y and return x (__sync_sub_and_fetch)
// AddFetch(x,y) = atomically x+=y and return x (__sync_add_and_fetch)
// CompareWait(x, y) = futex(&x, FUTEX_WAIT, y) wait on x if x == y
// Wake(x, y) = futex(&x, FUTEX_WAKE, y) wake up y waiters

struct Lock
{
Lock() : x(1) {}

void lock()
{
    while (true)
    {
        if (SubFetch(x, 1) == 0)
            return;

        x = -1;

        CompareWait(x, -1);
    }
}

void unlock()
{
    if (AddFetch(x, 1) == 1)
        return;

    x = 1;

    Wake(x, 1);
}

private:
    int x;
};

Linux 3.0 提供了一个名为futex 的系统调用，许多并发实用程序都基于它，包括最近的 pthread_mutex 实现。每当您编写代码时，您都应该始终考虑是使用现有实现还是自己编写对您的项目来说是更好的选择。

以上是一个基于futex的Lock(mutex, 1 permit counting semaphore)实现，语义描述见man futex(7)

它似乎包含一个死锁错误，在多个线程尝试锁定和解锁它几千次后，线程可能会进入 x == -1 的状态，并且所有线程都卡在 CompareWait 中，但是没有人持有锁。

谁能看出错误在哪里？

更新: 我有点惊讶 futex(7)/语义如此糟糕。我完全重写了 Lock，如下所示...现在这样正确吗？

// CompareAssign(x,y,z) atomically: if (x == y) {x = z; ret true; } else ret false;

struct Lock
{
Lock() : x(0) {}

void lock()
{
    while (!CompareAssign(x, 0, 1))
        if (x == 2 || CompareAssign(x, 1, 2))
            CompareWait(x, 2);
}

void unlock()
{
    if (SubFetch(x, 1) == 0)
        return;

    x = 0;

    Wake(x, 1);
}

private:
int x;
};

这里的思路是x有以下三种状态:

0: unlocked
1: locked & no waiters
2: locked & waiters

Answer 1

问题是你明确地 -1 分配给 x如果SubFetch获取锁失败。这与解锁赛跑。

1. 线程 1 获取锁。 x==0 .
2. 线程 2 尝试获取锁。 SubFetch套x为-1，然后线程 2 被挂起。
3. 线程 1 释放锁。 AddFetch套x为 0，因此代码随后显式设置 x到 1 并调用 Wake .
4. 线程 2 唤醒并设置 x到 -1，然后调用 CompareWait .

线程 2 现在处于等待状态，x设置为 -1，但周围没有人唤醒它，因为线程 1 已经释放了锁。