<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
But, is it common? Ok to make it contribute significantly to spurious wakeups?<BR>
That is, I have this crazy theory...really need to come back to this fresh, try coding it, testing it..where you can implement a condition variable simply by waking everyone whenever a mutex is exited.<BR>
<BR>
<BR>
I had this thought that what a condition variable represents is, instead of telling the kernel, here is one bit, an event, I am waiting for, instead you are telling it, hey, I have some custom code to evaluate, but it is false currently, and can only change when some exits such and such a lock, so just let me know when that lock is exited.<BR>
<BR>
<BR>
The guy releasing the lock, or signal or broadcast..if he is signaling or broadcasting, he knows more specifically what he changed, not everything computable based on data protected by the lock, just something specific, but you can just wake everyone waiting on any of the conditions associated with the lock and it isn't maximally efficient but it should be correct.<BR>
<BR>
Basically, condition variable equals "wake me when someone changes some data and exits its lock".<BR>
A better condition variable is that when there are multiple "conditions" in the data, the code making the change can target the wakeup better. But it isn't requires. And sometimes might not even matter much -- if in fact the ratio of locks to conditions is close to or equal to 1.<BR>
<BR>
- Jay<BR><BR> <BR>
<HR id=stopSpelling>
CC: m3devel@elegosoft.com<BR>From: hosking@cs.purdue.edu<BR>To: jay.krell@cornell.edu<BR>Subject: Re: [M3devel] condition variables/win32<BR>Date: Thu, 8 Oct 2009 10:09:31 -0400<BR><BR>
<DIV><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span>
<DIV style="WORD-WRAP: break-word"><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span>
<DIV style="WORD-WRAP: break-word"><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span>
<DIV><SPAN style="FONT-SIZE: medium" class=ecxApple-style-span><FONT class=ecxApple-style-span color=#0000ff face="'Gill Sans'">In general, it is OK in M3 to associate multiple conditions with the same mutex. But not vice versa.</FONT></SPAN></DIV>
<DIV><FONT class=ecxApple-style-span color=#0000ff face="'Gill Sans'"><SPAN style="FONT-SIZE: medium" class=ecxApple-style-span><BR></SPAN></FONT></DIV></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></DIV></SPAN></DIV></SPAN></DIV>
<DIV>
<DIV>On 8 Oct 2009, at 09:32, Jay K wrote:</DIV><BR class=ecxApple-interchange-newline>
<BLOCKQUOTE><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: medium Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span>
<DIV style="FONT-FAMILY: Verdana; FONT-SIZE: 10pt" class=ecxhmmessage>condition variables/win32<BR> <BR><BR>So..one way I think about condition variables<BR>is that you want to be woken when someone else<BR>leaves the mutex that guards the data that you are dealing with.<BR>You want to know when another thread modifies the data.<BR>(If you have a reader/writer lock, you only want to be<BR>woken when someone exits a write.)<BR> <BR><BR>Now, if you consider a producer/consumer queue.<BR>There are two interesting occurences.<BR>Transitions from empty to non-empty<BR>and transitions from full to non-full (optionally,<BR>if it is fixed size).<BR> <BR><BR>Consumers wait for empty to non-empty.<BR>Consumers signal full to non-full.<BR>Producers wait for full to non-full.<BR>Producers signal non-empty to empty.<BR> <BR><BR>So, in this case, one mutex is likely used with with two condition variables.<BR> <BR><BR>But, what if we take a simplifying deoptimization and assume that a condition<BR>variable is only ever associated with one mutex?<BR>Anyone existing that mutex wakes up anyone waiting on any condition associated with it?<BR>Like, a condition variable I think becomes stateless and everything is<BR>about the mutex?<BR> <BR> <BR>What is the downside?<BR> <BR><BR>Condition variables are allowed to have spurious wakeups.<BR>This would "just" increase them. Too much?<BR> <BR><BR>So, therefore, what would be wrong with the following design?<BR> a mutex contains an event<SPAN class=ecxApple-converted-space> </SPAN><BR> and a number of waiters, zero or non-zero<SPAN class=ecxApple-converted-space> </SPAN><BR> if a mutex is exiting with a non-zero number of waiters, signal the event<BR> <BR><BR>To handle Signal vs. Broadcast<BR>method 1:<BR> the number of waiters might be interlocked<BR> the woken would decrement it<BR> if it isn't zero, signal the event again<BR> <BR><BR>method 2:<BR> the number of waiters is both an integer and a semaphore<BR> and the lock exiter raises the semaphore by the the integer<BR><BR> <BR>method 3:<BR> it is not an auto-reset event and there is a count<BR> and when the count goes to 0, reset the event<BR> I think in this case you have to maintain a "wait generation"<SPAN class=ecxApple-converted-space> </SPAN><BR> so that new waiters don't prevent the count from ever hitting 0.<BR> I think this #3 is what Java might be doing, and is described here:<BR><A href="http://www.cs.wustl.edu/~schmidt/win32-cv-1.html">http://www.cs.wustl.edu/~schmidt/win32-cv-1.html</A><BR> "3.3. The Generation Count Solution"<BR><BR> <BR>also:<BR><A href="http://www.cs.wustl.edu/~schmidt/win32-cv-1.html">http://www.cs.wustl.edu/~schmidt/win32-cv-1.html</A><BR>3.2. The SetEvent Solution<BR>Evaluating the SetEvent Solution<BR>Incorrectness --<SPAN class=ecxApple-converted-space> </SPAN><BR> <BR><BR>Is that incorrect case really necessarily incorrect?<BR>It seems unfair, since first waiter should be first woken, but..?<BR><BR> <BR>Am I missing something? A lot?<BR> <BR><BR> - Jay<BR></DIV></SPAN></BLOCKQUOTE></DIV><BR> </body>
</html>