When will a thread woken via a condition variable run?

Question

When I wake up a thread waiting on a condition variable while holding the corresponding mutex, can I assume that the woken thread will run after I release the mutex and before anyone else (myself included) can lock the mutex again? Or can I only be sure that it will run at some point in the future?

To be precise, assume that I have the following functions.

bool taken = false;
int waiting = 0;

pthread_mutex_t m;   // properly initialised elsewhere
pthread_cond_t c;

void enter() {
    pthread_mutex_lock(&m);
    // Is `taken || (waiting == 0)` guaranteed here? 
    while (taken) {
        ++ waiting;
        pthread_cond_wait(&c, &m);
        -- waiting;
    }
    taken = true;
    pthread_mutex_unlock(&m);
}

void leave() {
    pthread_mutex_lock(&m);
    taken = false;
    if (waiting > 0) {
        pthread_cond_signal(&c);
    }
    pthread_mutex_unlock(&m);
}

(This is a toy example, not meant to be useful.)

Also assume that all threads are using these functions as

enter()
// some work here
leave()

Can I then be sure that directly after acquiring the mutex in enter() (see comment in the code), if taken is false waiting has to be zero? [It seems to me that this should be the case, because the woken thread will assume to find the state that the waking thread has left behind (if the wake-up was not spurious) and this could otherwise not be guaranteed, but I did not find it clearly worded anywhere.]

I am mainly interested in the behaviour on (modern) Linux, but of course knowing whether this is defined by POSIX would also be of interest.

Note: This may have already been asked in another question, but I hope that mine is clearer.

After t0 does pthread_cond_signal, t1 is no longer waiting for the condition variable, but it is also not running, because t0 still holds the mutex; t1 is instead waiting for the mutex. The thread t2 may also be waiting for the mutex, at the beginning of enter(). Now t0 releases the mutex. Both t1 and t2 are waiting for it. Is t1 handled in a special way and guaranteed to get it, or could t2 get it instead?

Please see [this answer](https://stackoverflow.com/a/44417229/2989411) - maybe it would give you some insights. — ArturFH, Jun 07 '17 at 15:56
@ArturR.Czechowski, thanks for pointing out the other question. — Carsten S, Jun 07 '17 at 16:07
@Miket25, I probably could have stated it more clearly. After `t0` does `signal`, `t1` is no longer waiting for the condition variable, but it is also not running, because `t0` still holds the mutex, it is instead waiting for the mutex. The thread `t2` may also be waiting for the mutex, at the beginning of `enter()`. Now `t0` releases the mutex. Bother `t1` and `t2` are waiting for it. Is `t1` handled in a special way and guaranteed to get it, or could `t2` also get it? — Carsten S, Jun 07 '17 at 16:23
In general, there could be multiple threads waiting on a single condition. There's no guarantee which of those threads will run after a `pthread_cond_signal()`. If other threads are using the mutex separately from the condition, there's no guarantee whether one of those threads will get the mutex first. That's why it is crucial to check that the condition a thread is waiting on holds after getting the mutex. — Jonathan Leffler, Jun 07 '17 at 16:52
@JonathanLeffler, that makes total sense, but I had often only read that you should check the condition because of spurious wake-ups. These are not a problem here, because the woken thread actually checks the condition. However, with what you are saying, it would still be an error here if at the line of the comment I argued as followed: "If `taken` is false here, anyone who has entered has exited and on exit woken up a waiting thread, so no thread can be waiting." I am getting convinced now, but at first I thought that I might be paranoid. — Carsten S, Jun 07 '17 at 17:02
In the case of Windows with Windows native mutexes, in the testing I've done, the order in which threads ask for a lock determines the order that the threads will waken when the mutex is unlocked. In other cases, including Windows using non-native mutexes, the ordering by lock request did not occur, and it would be possible for the same thread to repeatedly get the lock, even though other threads already had pending lock requests. If the OS includes a priority boost feature for threads stuck waiting, then the priority boosted thread would get the lock. — rcgldr, Jun 07 '17 at 17:08

Miket25 · Accepted Answer · 2017-06-07T16:44:19.340

2

Thanks for your comment, Carsten, that cleared it up.

No, see this answer for more reference. Given your example, t2 could acquire the mutex before t1 and a race condition may occur leading to unexpected outcomes.

Reiterating, t0 may initially have the mutex and be in the while loop holding on the line pthread_cond_wait(&c, &m);and the mutex is released atomically reference. t1 could call leave() acquiring the mutex signaling the condition c, and then release the mutex. t0 will prepare to run --waiting by trying to acquire the now-freed mutex by t1, but it can become context switched by the OS. Some other thread t2 waiting on the mutex can grab it and run enter() causing undesired outcomes, see non-reentrant. t2 then releases the mutex. t0 may swaps back only to see values have been mutated.

edited Jun 07 '17 at 16:44

answered Jun 07 '17 at 16:31

Miket25

1,895
3
15
29

Thanks, your answer probably states the problem more clearly than my question ;) I would feel more comfortable if it cited something to that effect, though. – Carsten S Jun 07 '17 at 16:46
I can see your difficulty finding an answer this. I had a hard time find verification myself. [Reference](http://pages.cs.wisc.edu/~remzi/OSTEP/threads-cv.pdf) First paragraph on pg.3 "hints" that `t0` does need to "re-acquire" the mutex and that it is not treated specially. I'll see if I can find more. – Miket25 Jun 07 '17 at 17:12

When will a thread woken via a condition variable run?

1 Answers1