[Bug nptl/12875] pthread_cond_timedwait can steal the wakeup of slower thread in pthread_cond_wait

["triegel at redhat dot com" <sourceware-bugzilla at sourceware dot org>]

http://sourceware.org/bugzilla/show_bug.cgi?id=12875

--- Comment #12 from Torvald Riegel <triegel at redhat dot com> 2012-09-19 15:34:48 UTC ---
(In reply to comment #11)
> Here's the related bug report, whose thread concluded with the claim that this
> bug (12875) is probably a manifestation of it:
> http://sourceware.org/bugzilla/show_bug.cgi?id=13165
> 
> With that said, some comments on Torvald's last reply:
> 
> > Second, the sentence from the spec that you quote is vague on when those other
> > threads would block (e.g., is there any guarantee of linearizability or such?).
> > Specifically, it doesn't state which blocked threads should be wakened, or
> > which threads blocked at which time.
> 
> The relevant text is in the specification for pthread_cond_wait regarding
> atomically unlocking the mutex and blocking:
> 
> "These functions atomically release mutex and cause the calling thread to block
> on the condition variable cond; atomically here means "atomically with respect
> to access by another thread to the mutex and then the condition variable". That
> is, if another thread is able to acquire the mutex after the about-to-block
> thread has released it, then a subsequent call to pthread_cond_broadcast() or
> pthread_cond_signal() in that thread shall behave as if it were issued after
> the about-to-block thread has blocked."

That states that the signaler needs to respect a happens-before relation
established by the mutex.  Thus, the prior cond_wait will be considered as a
wake-up target.  There is no guarantee there that it is the first to be
wakened. There is no statement there about the relationship to other writers,
nor when the signal is actually delivered.

> That is, if the mutex was held by a thread entering pthread_cond_wait and
> another thread successfully acquires the mutex, the first thread "has blocked".

Indeed.  However, that doesn't mean that it will be the first to be unblocked. 
If there are no other waiters, it is the only candidate though, and will be
unblocked (i.e., there are no lost wake-ups).

> > > If another waiter arriving after the N
> > > signals consumes any of the signals and prevents those N from being blocked,
> > > then the above cited requirement has been violated;
> > 
> > I don't see how this is violated. You say it unblocked the waiter and N-1
> > other threads, so N overall for N signals.  That's what the guarantee is,
> > isn't it?
> 
> Perhaps my typo in the above-quoted text is the source of confusion. It should
> have read "prevents those N from being _unblocked_".

I read this as unblocked.

> With the above reading of the standard in mind, at the moment
> pthread_cond_signal is called, it's provable that exactly those N, and not the
> new waiter that's about to arrive, "have blocked" on the condition variable. > So

It says that those have blocked, not that those are exactly the ones that can
be considered to have blocked (i.e., the first "if" in what you quoted is an
"if", not an "iff" (if and only if)).

> if the N signals don't wake all N of them, it's a bug - each signal is required
> to unblock at least one thread that "has blocked" in the above sense.

No.  See above.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.