Why does the pthread_cond_timedwait doc say "inevitable race"?

Question

The POSIX documentation (IEEE 1003.1, 2013) for the pthread_cond_timedwait function says:

It is important to note that when pthread_cond_wait () and pthread_cond_timedwait () return without errors, the predicate associated with it may still be false. Similarly, when pthread_cond_timedwait () returns with a timeout error, the associated predicate may be true due to the inevitable race between the timeout expiration and the change in state of the predicate .

(my accent)

We all know the story that predicates controlled by state variables must be checked in a while loop, and there may be side wakes. But my question about the inevitable word is a strong word. Why cannot such a race be prevented?

Note that if such a race does not exist, we can simply check to see if pthread_cond_timedwait expires; instead of checking the predicate again, and only then processing the timeout condition. (Assuming, of course, that we only get 1) with the mutex and 2) when the predicate really changes.)

Wouldn’t it be enough to check atomically using the “user mutex” if we woke up in timeout or were signalized?

---

For example, consider the implementation of condition variables built on top of POSIX. (Error handling and initialization omitted, you can fill in the obvious gaps).

 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); } }; 

It can be shown that

• If CV::wait reports a timeout, then we received a not signal and, therefore, the predicate has not changed; So what
• if the timeout expires, but we receive a signal before returning to the user code with the user mutex stored, then we report an awakening.

---

Is there any serious error in the code above? If not, is the standard misconception that a race is inevitable, or should it make some other assumption that I am missing?

Answer 1

First of all, note that this has a generally dangerous part:

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

Everything can happen in the comments. You have no locks. The strength of a condition variable is that they always either hold the lock or wait.

Then there is the problem, the inevitable race

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

There is no guarantee what order will be launched while waiting for pthread_cond_t, which can lead to chaos when counting

 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} 

At this point in thread 1, oldWakeups = awakenings, so checking for the inevitable racial affair does not notice the racial situation, recreating the inevitable race event. This is because thread 3 gets theft of the signal destined for thread1, making thread 3 (true timeout) look like a signal, and thread1 (race signal / timeout) looks like a timeout

Answer 2

Your implementation does not prevent the possibility of a false TIMEOUT when transmitting a stream. You immediately decrease awakenings on successful cond_wait, and you decrease awakenings on failed cond_wait if it looks like a signal intended for you (awakening has a larger number). However, the math you use to provide the signal is designed to prevent someone from actually doing this.

The problem is when you open all the mutexes after waiting

 if (ret == 0) wakeups--; pthread_mutex_unlock(&mtx); // no locks held. If interrupted, ANYTHING can happen userMutex->lock(); pthread_mutex_lock(&mtx); 

Now, to determine success and failure, I have to declare that your cond_wait spans from the initial pthread_mutex_lock to the final pthread_mutex_unlock . To state that you have no race, when the signal may look like a timeout, it should be like this. If you manage to prevent a strong wait time for pthread_cond_wait, just to enter another delayed timeout, the problem is not solved.

So, all that needs to be proven is the case where a stream is transmitted during operation, but wake-up checks are not performed. It turned out that the easiest way to do this is to trick the awakenings to be -1 if one thread stole another awakening. 3 threads will wait and one will signal twice. The trick to use is the abuse of min () in Wake. He also relies on a race event between two cond_waits that end immediately. One of them should get mtx , and this is undefined, which will succeed. In this case, I assume the worst (as you can always with race evidence)

 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 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} 

Thanks to a fun racing game that allows you to get awakenings up to -1, the trick to avoid missing signals does not work. pthreads_cond_signal allowed to wake up multiple threads, so waking threads 2 and 3 at the same time is legal. However, the second signal obviously has only one stream for the signal, so stream1 must be signaled. However, we returned TIMEOUT, losing to the infamous inevitable racial affair.

As far as I can tell, the more difficult you are trying to block these awakenings in the correct flow, the more ways to reset all mutexes, and not technically wait for any conditional variable, the more deadly.

Answer 3

For reference only, an interesting entry on the same subject:

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

The only way to solve this problem is if we can order a stream by the time they begin to wait.

Inspired by the blockchain of bitcoins, I created a linked list of nodes in the stream stack that represent the order. When a thread starts to wait, it adds itself to the end of a double linked list. When a thread wakes up another thread, it marks the last node of the linked list. (by increasing the swell counter inside the node). When a thread is disconnected, it checks to see if it was marked or any other thread after it in the linked list. In this case, we decide only the race, otherwise we believe that this is a timeout.

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

This patch adds quite a lot of code to add and remove nodes in a linked list, as well as to view the list to see if we really woke up. The linked list is linked by the number of waiting threads. I expected that handling a linked list would be negligible compared to the other QWaitCondition cost

However, the QWaitCondition test results show that with 10 threads and a high level of competition, we have a penalty of 10%. With 5 threads fine ~ 5%.

Is this punishment worth an investigation? So far, we decided not to merge the patch and keep the race.