c++ - Linux 3.0:futex-lock死锁错误？

// 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和man futex(7)中语义描述的Lock(互斥锁，1个允许计数信号量)的实现

它似乎包含一个死锁错误，即在多个线程尝试将其锁定和解锁数千次之后，线程可能会进入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

最佳答案

问题是，如果x无法获取锁，则您明确将-1分配给SubFetch。这与解锁比赛。

线程1获取锁。 x==0。

线程2尝试获取锁。 SubFetch将x设置为-1，然后线程2被挂起。

线程1释放锁定。 AddFetch将x设置为0，因此该代码随后将x显式设置为1并调用Wake。

线程2唤醒，并将x设置为-1，然后调用CompareWait。

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

关于c++ - Linux 3.0:futex-lock死锁错误？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9621254/