7

该函数的 POSIX 文档（IEEE 1003.1，2013）pthread_cond_timedwait说：

需要注意的是，当 pthread_cond_wait() 和 pthread_cond_timedwait() 无错误返回时，关联的谓词可能仍然为假。类似地，当 pthread_cond_timedwait() 返回超时错误时，由于超时到期和谓词状态更改之间不可避免的竞争，相关谓词可能为真。

（强调我的）

我们都知道由条件变量控制的谓词应该在 while 循环中检查的故事，并且可能会出现虚假唤醒。但我的问题是关于不可避免的词——这是一个强有力的词。为什么这样的竞赛是无法避免的？

请注意，如果不存在这样的竞争，我们可以只检查 pthread_cond_timedwait 是否超时；而不是再次检查谓词，然后才处理超时条件。（当然，假设我们仅在 1）持有互斥锁时和 2）当谓词实际更改时收到信号。）

如果我们被超时唤醒或收到信号，在持有“用户互斥锁”的情况下进行原子检查还不够吗？

例如，让我们考虑建立在 POSIX 之上的条件变量的实现。（错误处理和初始化省略，明显的空白可以补）。

class CV 
{
pthread_mutex_t mtx;
pthread_cond_t cv;
int waiters; // how many threads are sleeping
int wakeups; // how many times this cv got signalled

public:    
CV();
~CV();

// returns false if it timed out, true otherwise
bool wait(Mutex *userMutex, struct timespec *timeout)
{
    pthread_mutex_lock(&mtx);

    waiters++;
    const int oldWakeups = wakeups;

    userMutex->unlock();

    int ret; // 0 on success, non-0 on timeout

    for (;;) {
        ret = pthread_cond_timedwait(&mtx, &cv, timeout);
        if (!(ret == 0 && wakeups == 0))
            break; // not spurious
    }

    if (ret == 0) // not timed out
        wakeups--;

    pthread_mutex_unlock(&mtx);

    userMutex->lock();

    pthread_mutex_lock(&mtx);
    waiters--;
    if (ret != 0 && wakeups > oldWakeups) {
        // got a wakeup after a timeout: report the wake instead
        ret = 0;
        wakeups--;    
    }
    pthread_mutex_unlock(&mtx);

    return (ret == 0);
}

void wake()
{
    pthread_mutex_lock(&mtx);
    wakeups = min(wakeups + 1, waiters);
    pthread_cond_signal(&cv);
    pthread_mutex_unlock(&mtx);
}
};

有可能表明

  • 如果CV::wait报告超时，那么我们没有收到信号，因此谓词没有改变；然后
  • 如果超时到期但我们在返回用户代码之前收到信号，并持有用户互斥锁，则我们报告唤醒。

上面的代码是否包含一些严重的错误？如果不是，那么说比赛是不可避免的标准是错误的，还是它必须做一些我错过的其他假设？

4

3 回答 3

3

首先，请注意，这通常有一个危险的部分：

pthread_mutex_unlock(&mtx);
// Trouble is here
userMutex->lock();

pthread_mutex_lock(&mtx);

在评论点，任何事情都可能发生。您没有持有任何锁。条件变量的强大之处在于它们总是要么持有锁，要么等待。

然后是手头的问题，不可避免的比赛

if (ret != 0 && wakeups > oldWakeups) {
    // got a wakeup after a timeout: report the wake instead
    ret = 0;
    wakeups--;    
}

无法保证会唤醒一堆等待的 pthread_cond_t 的顺序，这会对您的计数造成严重破坏

Thread1           Thread2        Thread3
{lock userMtx in calling code}
{lock mtx}
waiters++ (=1)
oldWakeups = 0
{unlock userMtx }
wait {unlock mtx}
                  {lock userMtx in calling code}
                  {lock mtx}
                  signal_all
                  wakeups = 1
                  {unlock mtx}
                  {unlock userMtx in calling code}
timeout(unavoid. racecase) {lock mtx}
{unlock mtx}
                                  {lock userMtx in calling code}
                                  {lock mtx}
                                  waiters++ (=2)
                                  oldWawkupes = 1
                                  {unlock userMtx }
                                  wait {unlock mtx}

                                  timeout {lock mtx}
                                  {unlock mtx}
                                  {lock userMtx}
                                  {lock mtx}
                                  waiters-- (=1)
                                  wakeups-- (=0)*
                                  {unlock mtx}
                                  {unlock userMtx in calling code}
 {lock userMtx}
 {lock mtx}
 waiters--(=0)
 wakeups == oldWakeups (=0)
 {unlock mtx}
 {unlock userMtx in calling code}

此时，在线程 1 上，oldWakeups = wakeups，因此对不可避免的比赛情况的检查没有注意到比赛情况，重新创建了不可避免的比赛情况。这是由于线程 3 窃取了用于线程 1 的信号，使线程 3（真正的超时）看起来像一个信号，而线程 1（一个竞争信号/超时）看起来像一个超时

于 2013-09-06T05:36:38.033 回答
2

当线程发出信号时，您的实现不会阻止虚假 TIMEOUT 的可能性。你会立即减少 cond_wait 成功时的唤醒次数，如果 cond_wait 失败时你会减少唤醒次数，如果看起来有一个信号是给你的（wakeup 有更高的数字）。但是，您用来确保信号适用于某人的数学运算实际上并没有这样做。

问题在于您在等待后解锁所有互斥锁的比赛情况

if (ret == 0)
    wakeups--;

pthread_mutex_unlock(&mtx);

// no locks held.  If interrupted, ANYTHING can happen

userMutex->lock();

pthread_mutex_lock(&mtx);

现在要定义成功和失败，我必须声明您的 cond_wait 跨越从 initialpthread_mutex_lock到 final pthread_mutex_unlock。要声明您没有信号看起来像超时的竞争情况，必须是这种情况。如果你设法防止 pthread_cond_wait 上的虚假超时，只是引入另一个你自己的虚假超时，没有问题得到解决

因此，所有必须证明的是，存在这样一种情况，即线程在运行时发出信号，但唤醒检查失败。事实证明，最简单的方法是通过让一个线程窃取另一个线程的唤醒来欺骗唤醒为 -1。3 个线程将等待，一个将发出两次信号。这样做的诀窍是在 Wake 中滥用 min()。它还依赖于两个同时结束的 cond_waits 之间的竞争情况。其中一个必须获得mtx，并且不确定哪一个成功。在这种情况下，我假设最坏的情况（正如你总是可以使用比赛案例证明）

initial state {
   waiters = 0
   wakeups = 0
}

Thread 1     Thread 2    Thread 3      Thread 4
1: {acquire userMutex}
1: wait(...) {
1:   {acquire mtx}
1:   {release userMutex}
1:   waiters++; // = 1
1:   oldWakeups = wakeups; // 0
1:   pthread_cond_wait // releases mtx
1:   ptrheads TIMES OUT // acquires mtx
1:   sees timeout
1:   {release mtx}
1:   // world's worst context switch occurs here
             2: {acquire userMutex}
             2: wait(...) {
             2:   {acquire mtx}
             2:   {release userMutex}
             2:   waiters++; // = 2
             2:   oldWakeups = wakeups; // = 0
             2:   pthread_cond_wait // releases mtx
                         3:  {acquires userMutex}
                         3:  wait(...) {
                         3:    {acquire mtx}
                         3:    {release userMutex}
                         3:    waiters++; // = 3
                         3:    oldWakeups = wakeups; // = 0
                         3:    pthread_cond_wait // releases mtx
                                       4:  {acquire userMtx}
                                       4:  wake() {
                                       4:    {acquire mtx}
                                       4:    wakeups = min(wakeups + 1, waiters);
                                       4:    //      = min(0 + 1, 3) = 1
                                       4:    pthread_cond_signal
                                       4:    {release mtx}
                                       4:  }
                                       4:  {release userMtx}
 RACE:       2: TIMEOUT  3: SIGNALED
 RACE:       both of these threads need to acquire mtx
             2:   {acquires mtx}
             2:   sees that it times out
             2:   if (timeout && (wakeups > oldWakeups)) { // (1 > 0)
             2:     // thinks the wakeup was for this thread
             2:     waiters--; // = 2
             2:     wakeups--; // = 0
             2:   }
             2:   {releases mtx}
             2:   returns SIGNALED;
             2: }
             2: {releases userMtx}
                         3:    {acquires mtx}
                         3:    sees that it was signaled
                         3:    wakeups--; // = -1 ... UH O!
                         3:    waiters--; // = 1
                         3:    {releases mtx}
                         3:    returns SIGNALED;
                         3:  }
                         3:  {releases userMtx}

 --- some synchronization which makes it clear that both thread 2 ---
 --- and thread 3 were signaled occurs here.  Thread 1 is still   ---
 --- technically waiting in limbo.  User decides to wake it up.   ---

                                       4:  {acquire userMtx}
                                       4:  wake() {
                                       4:    {acquire mtx}
                                       4:    wakeups = min(wakeups + 1, waiters);
                                       4:    //      = min(-1 + 1, 1) = 0  !!!
                                       4:    pthread_cond_signal
                                       4:    {release mtx}
                                       4:  }
                                       4:  {release userMtx}
1:   {acquire userMtx}
1:   {acquire mtx}
1:   waiters--; // = 0
1:   if (timeout && (wakeups > oldWakeups)) {..}  (0 > 0)
1:   // no signal detected
1:   {release mtx}
1:   return TIMEOUT;
1: }
1: {release userMtx}

多亏了一个有趣的比赛案例，设法让唤醒到 -1，避免丢失信号的技巧不起作用。 pthreads_cond_signal允许唤醒多个线程，因此同时唤醒线程 2 和 3 是合法的。但是，第二个信号显然只有一个线程要发出信号，所以线程 1 肯定已经发出信号。然而，我们返回了 TIMEOUT，产生了臭名昭著的不可避免的比赛案例。

据我所知，您越努力将这些唤醒锁定到正确的线程，在技术上不等待任何条件变量的情况下丢弃所有互斥锁的方法就越多，这更致命。

于 2013-09-07T19:20:51.410 回答
1

仅供参考，关于同一主题的有趣条目：

http://woboq.com/blog/qwaitcondition-solving-unavoidable-race.html

解决这个问题的唯一方法是，如果我们可以在线程开始等待时对其进行排序。

受比特币区块链的启发，我在线程堆栈上创建了一个表示订单的节点链表。当一个线程开始等待时，它会将自己添加到双链表的末尾。当一个线程唤醒其他线程时，它会标记链表的最后一个节点。（通过增加节点内的唤醒计数器）。当一个线程超时时，它会检查它是否被标记，或者链表中在他之后的任何其他线程。我们只在这种情况下解决比赛，否则我们认为这是一个超时。

https://codereview.qt-project.org/#/c/66810/

这个补丁添加了相当多的代码来添加和删除链表中的节点，并检查链表是否真的被唤醒了。链表受等待线程数的限制。与 QWaitCondition 的其他成本相比，我期望这个链接列表处理可以忽略不计

然而，QWaitCondition 基准测试的结果表明，在 10 个线程和高争用情况下，我们有大约 10% 的损失。使用 5 个线程会有约 5% 的惩罚。

为解决比赛而支付这笔罚款是否值得？到目前为止，我们决定不合并补丁并保持比赛。

于 2014-08-05T09:28:59.477 回答