这是我如何(没有)解决影响QWaitCondition的竞争条件的故事,并且在所有其他条件变量实现(pthread,boost,std :: condition_variable)上也存在。
如果满足条件变量,则bool QWaitCondition :: wait(int timeout)应该返回true,如果超时则返回false。比赛是即使它实际上被唤醒了,它也可能返回false(超时)。
该问题已经在2012年报告过。但是,我只是在David Faure试图修复由该比赛引起的QThreadPool中的另一个错误时才开始研究它。
QMutexLocker储物柜(&互斥锁); taskQueue。 append(任务); //((waitingThreads> 0){//已经有正在运行的空闲线程。他们正在等待' runnableReady' // QWaitCondition。叫醒他们一个。等待线程-; runnableReady。 awawOne();}否则if(runningThreadCount&maxThreadCount){startNewThread(task);}
无效的QThreadPoolThread :: run(){QMutexLocker更衣室(& manager->互斥锁); while(true){/ * ... * / if(manager-> taskQueue。isEmpty()){//没有待处理的任务,请等待一个。布尔已过期=!经理-> runnableReady。等待(更衣室。互斥(),管理器-> expiryTimeout);如果(已过期){manager-> runningThreadCount--;返回; }其他{继续; } QRunnable * r = manager-> 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(& d->互斥锁); ++ d->服务员;互斥锁->开锁(); //(为简明起见)int code = 0;做{code = d-> wait_relative(时间); //调用pthread_cond_timedwait},同时(code == 0& d->唤醒== 0); -d->服务员; if(code == 0)-d->唤醒; // [!!] pthread_mutex_unlock(& d->互斥锁);互斥锁->锁();返回代码== 0;} void QWaitCondition :: awakOne(){pthread_mutex_lock(& d->互斥体); d-唤醒次数= qMin(d->唤醒次数+ 1,d->服务员); pthread_cond_signal(& d-> cond); pthread_mutex_unlock(& d->互斥锁);}
请注意,d-> mutex是本机pthread互斥量,而局部变量互斥量是用户互斥量。在标有[!!]的行中,我们有效地拥有唤醒权限,但是我们在锁定用户之前执行了此操作39; s互斥。如果我们再次检查用户锁下的服务员该怎么办?
bool QWaitCondition :: wait(QMutex * Mutex,unsigned long){//与以前相同:pthread_mutex_lock(& d-> Mutex); ++ d->服务员;互斥锁->开锁();整数代码= 0;做{code = d-> wait_relative(时间); //调用pthread_cond_timedwait},同时(code == 0& d->唤醒== 0); // --d->侍者; //如果(code == 0)-d->唤醒; pthread_mutex_unlock(& d->互斥锁);互斥锁->锁(); //现在再次检查唤醒:pthread_mutex_lock(& d->互斥锁); -d->服务员; if(code!= 0& d->唤醒){//检测并纠正了种族-d->唤醒;代码= 0; } pthread_mutex_unlock(& d->互斥锁);返回代码== 0;}
至此,我们已经解决了比赛!我们只需要再次锁定内部互斥锁,因为d-> waiters和d-> wakeups需要受到它的保护。我们需要解锁它,因为在锁定内部互斥锁的情况下锁定用户的互斥锁可能会导致死锁,因为不遵守锁定顺序。
但是,我们现在引入了另一个问题:如果有三个线程,则可能在一个线程被唤醒之前
//线程1 //线程2 //线程3mutex-> lock()cond-> 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的隐私权政策。