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实现。无论何时编写代码，您都应该考虑是否使用现有的实现或自己编写代码是您项目的更好选择。Linux 3.0：futex-lock死锁错误？

以上是基于futex的一个锁（互斥，1个许可证计数信号）的实现和在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

来源

2012-03-08 Andrew Tomazos

我听说futexes看起来很简单，很难正确使用它们。你有这样的理由吗？ – 2012-03-08 16:43:13

见第1款 – 2012-03-08 16:44:04

呵呵？ pthread_mutex有什么问题？ – 2012-03-08 16:46:11

的问题是，您明确-1分配给x如果SubFetch未能获取锁。这与解锁的比赛。

线程1获取锁定。 x==0。
线程2尝试获取锁。 SubFetch将x设置为-1，然后挂起线程2。
线程1释放锁。 AddFetch将x设置为0，所以代码然后明确地将x设置为1并且调用Wake。
线程2唤醒并将x设置为-1，然后调用CompareWait。

线程2现在卡住等待，x设置为-1，但由于线程1已经释放了锁，因此没有人会将其唤醒。

来源

2012-03-08 16:49:46

我明显误读了futex（7）它说“应该将计数器设置为-1”。什么是修复？ – 2012-03-08 17:13:29

在http://www.justsoftwaresolutions.co.uk/files/c_mutexes.zip有一个基于futex的互斥体的代码。基本上，你不能盲目地设置'x'的值，你必须使用原子比较 - 并且交换操作，并检查所有情况下的返回值。 – 2012-03-08 17:30:28

请参阅更新/重写。现在这是否正确？ – 2012-03-08 18:22:34

这个怎么样的情况与三个线程，A，B和C.

这种情况下的初始状态有：

线程A持有锁
线程B不争锁在CompareWait()
x == -1从当C未能获得锁，只是还没有
线程C-

 
     A     B    C 
    ============== ================ =============== 
    AddFetch() 
    (so x == 0) 
         SubFetch() 
         (so x == -1) 

    x = 1 

         x = -1 

    Wake()

此时B或C是否畅通，他们不会得到0当他们SubFetch()结果。

来源

2012-03-08 16:55:56

好吧，我完全误解了futex（7）的语义部分，或者描述被完全破坏了。这里的修复是什么？ – 2012-03-08 17:16:29

请参阅更新/重写。现在这是否正确？ – 2012-03-08 18:22:20

的正确实施基于futex的，互斥的乌利齐·德雷珀的论文“futexes的猫腻”被描述

http://people.redhat.com/drepper/futex.pdf

它不仅包括代码也是为什么它是正确的一个非常详细的解释。从本文的代码：

class mutex 
{ 
public: 
mutex() : val (0) { } 
void lock() { 
    int c; 
    if ((c = cmpxchg (val, 0, 1)) != 0) 
    do { 
     if (c == 2 || cmpxchg (val, 1, 2) != 0) 
     futex_wait (&val, 2); 
    } while ((c = cmpxchg (val, 0, 2)) != 0); 
} 
void unlock() { 
//NOTE: atomic_dec returns the value BEFORE the operation, unlike your SubFetch ! 
    if (atomic_dec (val) != 1) { 
    val = 0; 
    futex_wake (&val, 1); 
    } 
} 
private: 
    int val; 
};

的代码在你的代码的文件进行比较，我发现了一个差异

你有

如果（X == 2 || CompareAssign（X，1 ，2））

直接使用futex的值，而Drepper使用前一个CompareAssign（）的返回值。这种差异可能只会影响性能。

您的解锁代码也不同，但似乎在语义上相同。

无论如何，我强烈建议您按照Drepper的代码来写信。这篇论文经受了时间的考验，并获得了很多同行评议。你从滚动你自己一无所获。

来源

2012-03-13 21:13:36 MSB

Linux 3.0：futex-lock死锁错误？

回答

相关问题