QWaitCondition：解决不可避免的比赛（2014）

这是我如何（没有）解决影响QWaitCondition的竞争条件的故事，并且在所有其他条件变量实现（pthread，boost，std :: condition_variable）上也存在。

如果满足条件变量，则bool QWaitCondition :: wait（int timeout）应该返回true，如果超时则返回false。比赛是即使它实际上被唤醒了，它也可能返回false（超时）。

该问题已经在2012年报告过。但是，我只是在David Faure试图修复由该比赛引起的QThreadPool中的另一个错误时才开始研究它。

QMutexLocker储物柜（＆amp;互斥锁）; taskQueue。 append（任务）; //（（waitingThreads＆gt; 0）{//已经有正在运行的空闲线程。他们正在等待＆＃39; runnableReady＆＃39; // QWaitCondition。叫醒他们一个。等待线程-; runnableReady。 awawOne（）;}否则if（runningThreadCount＆maxThreadCount）{startNewThread（task）;}

无效的QThreadPoolThread :: run（）{QMutexLocker更衣室（＆amp; manager-＆gt;互斥锁）; while（true）{/ * ... * / if（manager-＆gt; taskQueue。isEmpty（））{//没有待处理的任务，请等待一个。布尔已过期=！经理-＆gt; runnableReady。等待（更衣室。互斥（），管理器-> expiryTimeout）;如果（已过期）{manager-＆gt; runningThreadCount--;返回; }其他{继续； } QRunnable * r = manager-＆gt; taskQueue。 takeFirst（）; //运行任务柜。开锁（）; -跑（）;储物柜。 relock（）; }}

这个想法是线程将等待一个任务给定的秒数，但是如果在给定的时间内没有添加任何任务，则该线程将到期并终止。这里的问题是我们依赖于的返回值runnableReady。如果有一个任务计划在线程到期的同时进行，则该线程将看到false并将到期。但是主线程不会重新启动任何其他线程。这将使应用程序挂起，因为该任务将永远不会运行。

条件变量的许多实现都有相同的问题。它甚至记录在POSIX文档中：

[W]当pthread_cond_timedwait（）返回超时错误时，由于超时到期和谓词状态更改之间不可避免的竞争，关联的谓词可能为true。

pthread文档将其描述为不可避免的竞争。等待条件与互斥量相关联，该互斥量在调用wake（）时由用户锁定，并且也传递给了wait（）锁定状态。该实现应该解锁并自动进行等待。

C ++ 11标准库的condition_variable甚至具有用于返回代码的枚举（cv_status）。 C ++标准没有记录比赛，但是我尝试过的所有实现都遭受了比赛的困扰。 （因此，没有实现符合要求。）

让我尝试更好地解释比赛：此代码显示了QWaitCondition的典型用法

竞争是线程2中的等待条件超时并返回false，但与此同时，线程1唤醒了该条件。可以预料，由于所有内容均受互斥锁保护，因此不应发生这种情况。在内部，等待条件会解锁内部互斥锁，但不会在用户互斥锁再次锁定后检查是否尚未唤醒它。

QWaitCondition具有内部状态，该状态对等待的QWaitCondition数量和等待被唤醒的QWaitCondition数量进行计数。让我们回顾一下QWaitCondition的实际代码（为便于阅读而进行了编辑）

bool QWaitCondition :: wait（QMutex * Mutex，unsigned long）{// [...] pthread_mutex_lock（＆amp; d-＆gt;互斥锁）; ++ d-＆gt;服务员;互斥锁->开锁（）; //（为简明起见）int code = 0;做{code = d-＆gt; wait_relative（时间）; //调用pthread_cond_timedwait}，同时（code == 0＆amp; d-＆gt;唤醒== 0）; -d-＆gt;服务员; if（code == 0）-d->唤醒； // [!!] pthread_mutex_unlock（＆amp; d-＆gt;互斥锁）;互斥锁->锁（）;返回代码== 0;} void QWaitCondition :: awakOne（）{pthread_mutex_lock（＆amp; d-＆gt;互斥体）; d-唤醒次数= qMin（d->唤醒次数+ 1，d->服务员）; pthread_cond_signal（＆amp; d-＆gt; cond）; pthread_mutex_unlock（＆amp; d-＆gt;互斥锁）;}

请注意，d-> mutex是本机pthread互斥量，而局部变量互斥量是用户互斥量。在标有[!!]的行中，我们有效地拥有唤醒权限，但是我们在锁定用户之前执行了此操作39; s互斥。如果我们再次检查用户锁下的服务员该怎么办？

bool QWaitCondition :: wait（QMutex * Mutex，unsigned long）{//与以前相同：pthread_mutex_lock（＆amp; d-＆gt; Mutex）; ++ d-＆gt;服务员;互斥锁->开锁（）;整数代码= 0;做{code = d-＆gt; wait_relative（时间）; //调用pthread_cond_timedwait}，同时（code == 0＆amp; d-＆gt;唤醒== 0）; // --d-＆gt;侍者; //如果（code == 0）-d-＆gt;唤醒； pthread_mutex_unlock（＆amp; d-＆gt;互斥锁）;互斥锁->锁（）; //现在再次检查唤醒：pthread_mutex_lock（＆amp; d-＆gt;互斥锁）; -d-＆gt;服务员; if（code！= 0＆amp; d-＆gt;唤醒）{//检测并纠正了种族-d-＆gt;唤醒；代码= 0; } pthread_mutex_unlock（＆amp; d-＆gt;互斥锁）;返回代码== 0;}

至此，我们已经解决了比赛！我们只需要再次锁定内部互斥锁，因为d-> waiters和d-> wakeups需要受到它的保护。我们需要解锁它，因为在锁定内部互斥锁的情况下锁定用户的互斥锁可能会导致死锁，因为不遵守锁定顺序。

但是，我们现在引入了另一个问题：如果有三个线程，则可能在一个线程被唤醒之前

//线程1 //线程2 //线程3mutex-＆gt; lock（）cond-＆gt; wait（mutex）;互斥锁-> lock（）cond-> wake（）;互斥锁-> unlock（）互斥锁-> lock（）cond-> wait（mutex，0）;

我们不希望线程3窃取线程1的信号。但是，如果线程1的睡眠时间太长并且在线程3到期之前没有设法及时锁定内部互斥锁，则可能会发生这种情况。

解决此问题的唯一方法是，如果我们可以在线程开始等待之前对其进行排序。受比特币区块链的启发，我在线程堆栈上创建了代表顺序的节点的链表。当线程开始等待时，它将自己添加到双链表的末尾。当一个线程唤醒其他线程时，它标记了链表的最后一个节点。 （通过增加节点内的唤醒计数器）。当线程超时时，它将检查该线程是否已被标记，或在链接列表中是否在该线程之后被标记。我们只在那种情况下解决比赛，否则我们认为这是超时。

该补丁添加了很多代码，以添加和删除链表中的节点，并遍历该列表以检查我们是否确实被唤醒。链表由等待线程数限制。我期望与QWaitCondition的其他费用相比，此链表处理可以忽略不计

但是，QWaitCondition基准测试的结果表明，在10个线程和高竞争的情况下，我们要付出约10％的代价，在5个线程中要付出约5％的代价。

付出这笔罚款来解决比赛是否值得？到目前为止，我们决定不合并补丁并继续比赛。

可以解决比赛，但是对性能的影响很小。这些实现均未尝试解决竞赛。我想知道如果您不能依靠它，为什么甚至根本没有返回状态。

Woboq是一家软件公司，专门从事Qt和C ++的开发和咨询。雇用我们！

如果您喜欢此博客并希望阅读类似的文章，请考虑通过我们的RSS feed（通过Google Feedburner，隐私权政策）订阅，通过电子邮件订阅（通过Google Feedburner，隐私权政策），或者在twitter上关注我们，或者在G +上添加我们。

加载评论...加载评论会嵌入来自disqus.com的外部小部件。查看Disqus隐私权政策以获取更多信息。

当我们发布新的有趣文章时，您将获得通知！ 单击以通过RSS或电子邮件在Google Feedburner上进行订阅。 （外部服务）。 单击以查看Google Feedburner的隐私权政策。