tag:blogger.com,1999:blog-5246987755651065286.post5233302984094275713..comments2024-02-22T16:15:42.388-08:00Comments on cbloom rants: 02-23-13 - Threading Patterns - Wake Pollingcbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-5246987755651065286.post-52395462203723823192013-02-25T15:31:52.291-08:002013-02-25T15:31:52.291-08:00Yeah. I did a demo a while ago of an implementati...Yeah. I did a demo a while ago of an implementation does does direct handoff of the cond_var from signaller to receiver :<br /><br />http://cbloomrants.blogspot.com/2011/07/07-20-11-condvar-that-actually-atomic.html<br /><br />That is, the mutex & condvar are built together, and the wake-from-wait also takes the lock.<br /><br />I'm not suggesting that the API should promise that, it's too hard to do in practice.<br /><br />What I'm trying to say is the closer you can get to that, the less you have of "I woke up, my conditions not set, I go back to sleep". (or inside the pthreads condvar, I woke up, I can't lock the mutex, go back to sleep).<br /><br />The goal is to maximize the % of times that a condition waiter just goes to sleep once. Then it wakes only once and finds its condition and proceeds.<br />cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-66644438934943446492013-02-25T15:17:06.321-08:002013-02-25T15:17:06.321-08:00Thanks for your reply!
For my internal Futex-base...Thanks for your reply!<br /><br />For my internal Futex-based condition variable implementation, I actually restrict the condvar to a single mutex in the constructor, but you were probably thinking more about a fused mutex-condvar primitive at the OS-level.<br /><br />Regarding the wake-unlock order: Even if the condition is guaranteed to be true when you call wake, that doesn't mean that the condition must be still true when a thread is actually woken up and has succeeded to take the lock (at least if you have multiple waiters). So I'm not sure how much that is an argument for wake before unlock. Note that my implementation with a separate wait and notify count won't call wake too often if a waker manages to obtain the lock again after a wake-unlock but before a previously woken-up thread manages to acquire the lock (which could happen if the waiter does both the increment and decrement of the wait count).<br /><br />To guarantee that the condition is still true when a woken-up waiter obtained the lock, you'd have to prevent all spurious wakeups and the wake_unlock operation would have to atomically unlock and wake *and* give the lock to the woken up thread, i.e. atomically transfer the lock from the waker to the waiter, right?Stephanhttps://www.blogger.com/profile/18089666026496371732noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-27872648610607082762013-02-25T14:50:56.873-08:002013-02-25T14:50:56.873-08:00Of course you can do waker-side checking with the ...Of course you can do waker-side checking with the existing APIs (that's what I do). The way you do it is to use a unique event/cv for each thread's wait condition, and have the waker decide which ones of those to signal. But you shouldn't have to build all that structure yourself, cv is so close to being there already.<br />cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-88050928097366847942013-02-25T13:38:07.615-08:002013-02-25T13:38:07.615-08:00Stephan, yeah I'm being a little fast-and-loos...Stephan, yeah I'm being a little fast-and-loose.<br /><br />The big problem is that the condvar can't assume it's protected by "mutex". If a mutex was bound to condvar, you could more easily have better implementations.<br /><br />The <br /><br />mutex.unlock(); <br />condvar.wake();<br /><br />is a problem; in many cases you'd prefer to wake before unlock, because that ensures that the condition you set is still set at the time you wake(). You'd also like the "wait->lock" sequence to be atomic. If you had that you could ensure that a thread that wakes from wait will see what the waker set.<br /><br />Really you want unlock_wake() to be atomic. (doing unlock after wake can be a bad performance bug on some implementations).<br /><br />Your code sketch looks like it's just to prevent calls to wake() when there's no waiter. Really a good implementation should do that pretty well already internally.<br /><br />The spurious wake case that I'm thinking about occurs when you have multiple waiters on the same cond_var, possibly with slightly different conditions. Something like :<br /><br />thread 1: (waiter)<br /><br />cv.lock();<br />while ( count == 0 && sel != 0 )<br />{<br /> cv.unlock_wait_lock();<br />}<br />count--;<br />// do stuff<br />cv.unlock();<br /><br />thread 2: (waiter)<br />cv.lock();<br />while ( count == 0 && sel != 1 )<br />{<br /> cv.unlock_wait_lock();<br />}<br />count--;<br />// do stuff<br />cv.unlock();<br /><br />thread 3: (waker)<br />cv.lock();<br />// publish item<br />count++;<br />sel = 0 or 1;<br />cv.broadcast_unlock();<br /><br /><br />because of the CV API you have to wake all threads and they then check their condition to decide if the signal can go to them.<br /><br />Obviously through good usage you can avoid this, but the point is that it should be easy to write code well. The way to do that is to make the wake condition part of the wait API.<br />cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-3881832940163396552013-02-25T12:50:03.350-08:002013-02-25T12:50:03.350-08:00What do you mean exactly with the pthreads cond_va...What do you mean exactly with the pthreads cond_var making you call wait and lock as two separate calls? pthread_cond_wait obviously does the unlock-wait-lock in one call, but you probably mean the underlying implementation...<br /><br />Regarding the minimizing of unnecessary wakes: Since a condition variable is associated with a mutex, you can get relatively far with a user-side logic like the one below:<br /><br />int waitCount = 0;<br />int notifyCount = 0;<br /><br />// Waiter<br />// ======<br />mutex.lock();<br />while (!condition) {<br /> ++waitCount;<br /> condvar.wait(mutex); // unlocks, waits and locks again<br /> if (notifyCount > 0) { // the waker decremented the waitCount<br /> --notifyCount;<br /> } else { // adjust waitCount for spurious wake up<br /> --waitCount;<br /> }<br />} // while<br />// ...<br />mutex.unlock();<br /><br />// Waker<br />// ======<br />mutex.lock();<br />condition = true;<br />if (waitCount == 0) mutex.unlock();<br />else {<br /> --waitCount;<br /> ++notifyCount;<br /> mutex.unlock(); <br /> condvar.wake();<br />}<br /><br />If you implement the mutex and condition variable with futexes, you could implement<br />a wake that requeues the condvar waiter directly to the mutex and then reverse the mutex.unlock(); condvar.wake() sequence above, which would further minimize condvar waiters waking up only to immediately wait on the mutex again.Stephanhttps://www.blogger.com/profile/18089666026496371732noreply@blogger.com