<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
That seems a little strange to me but I guess I'll have to keep it in mind.<BR>
<BR>
- Jay<BR><BR> <BR>
<HR id=stopSpelling>
From: hosking@cs.purdue.edu<BR>To: mika@async.async.caltech.edu<BR>Date: Thu, 8 Oct 2009 11:00:36 -0400<BR>CC: m3devel@elegosoft.com<BR>Subject: Re: [M3devel] condition variables/win32<BR><BR>Sorry, yes, you are right of course! The Modula-3 spec (and the current pthreads-based implementation as also the win32 implementation I expect) do allow a condition variable being mediated by different mutexes. My comment was clouded by my recollection from the pthreads spec that for pthread mutex/cv behavior for other than 1 mutex per cv is undefined. This confusion may have been the source of prior bugs in the pthreads threading implementation, but those bugs are gone now. We support the M3 spec properly.
<DIV><FONT class=ecxApple-style-span color=#0000ff face="'Gill Sans'"><BR></FONT></DIV>
<DIV>
<DIV>
<DIV>On 8 Oct 2009, at 10:34, Mika Nystrom wrote:</DIV><BR class=ecxApple-interchange-newline>
<BLOCKQUOTE>
<DIV>Why can't you use the same condition variable with different mutexes?<BR><BR>This is dynamic, up to the M3 programmer, no?<BR><BR>Tony Hosking writes:<BR>
<BLOCKQUOTE><BR></BLOCKQUOTE>
<BLOCKQUOTE>--Apple-Mail-96--321618545<BR></BLOCKQUOTE>
<BLOCKQUOTE>Content-Type: text/plain;<BR></BLOCKQUOTE>
<BLOCKQUOTE><SPAN style="WHITE-SPACE: pre" class=ecxApple-tab-span></SPAN>charset=US-ASCII;<BR></BLOCKQUOTE>
<BLOCKQUOTE><SPAN style="WHITE-SPACE: pre" class=ecxApple-tab-span></SPAN>format=flowed;<BR></BLOCKQUOTE>
<BLOCKQUOTE><SPAN style="WHITE-SPACE: pre" class=ecxApple-tab-span></SPAN>delsp=yes<BR></BLOCKQUOTE>
<BLOCKQUOTE>Content-Transfer-Encoding: 7bit<BR></BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE>
<BLOCKQUOTE>In general, it is OK in M3 to associate multiple conditions with the <BR></BLOCKQUOTE>
<BLOCKQUOTE>same mutex. But not vice versa.<BR></BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE>
<BLOCKQUOTE>On 8 Oct 2009, at 09:32, Jay K wrote:<BR></BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>condition variables/win32<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>So..one way I think about condition variables<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>is that you want to be woken when someone else<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>leaves the mutex that guards the data that you are dealing with.<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>You want to know when another thread modifies the data.<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>(If you have a reader/writer lock, you only want to be<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>woken when someone exits a write.)<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>Now, if you consider a producer/consumer queue.<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>There are two interesting occurences.<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>Transitions from empty to non-empty<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>and transitions from full to non-full (optionally,<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>if it is fixed size).<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>Consumers wait for empty to non-empty.<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>Consumers signal full to non-full.<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>Producers wait for full to non-full.<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>Producers signal non-empty to empty.<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>So, in this case, one mutex is likely used with with two condition <BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>variables.<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>But, what if we take a simplifying deoptimization and assume that a <BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>condition<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>variable is only ever associated with one mutex?<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>Anyone existing that mutex wakes up anyone waiting on any condition <BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>associated with it?<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>Like, a condition variable I think becomes stateless and everything is<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>about the mutex?<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>What is the downside?<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>Condition variables are allowed to have spurious wakeups.<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>This would "just" increase them. Too much?<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>So, therefore, what would be wrong with the following design?<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>a mutex contains an event<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>and a number of waiters, zero or non-zero<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>if a mutex is exiting with a non-zero number of waiters, signal the <BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>event<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>To handle Signal vs. Broadcast<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>method 1:<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>the number of waiters might be interlocked<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>the woken would decrement it<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>if it isn't zero, signal the event again<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>method 2:<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>the number of waiters is both an integer and a semaphore<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>and the lock exiter raises the semaphore by the the integer<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>method 3:<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>it is not an auto-reset event and there is a count<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE> and when the count goes to 0, reset the event<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>I think in this case you have to maintain a "wait generation"<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>so that new waiters don't prevent the count from ever hitting 0.<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>I think this #3 is what Java might be doing, and is described here:<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><A href="http://www.cs.wustl.edu/~schmidt/win32-cv-1.html">http://www.cs.wustl.edu/~schmidt/win32-cv-1.html</A><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>"3.3. The Generation Count Solution"<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>also:<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><A href="http://www.cs.wustl.edu/~schmidt/win32-cv-1.html">http://www.cs.wustl.edu/~schmidt/win32-cv-1.html</A><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>3.2. The SetEvent Solution<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>Evaluating the SetEvent Solution<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>Incorrectness --<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>Is that incorrect case really necessarily incorrect?<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>It seems unfair, since first waiter should be first woken, but..?<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>Am I missing something? A lot?<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>- Jay<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE>
<BLOCKQUOTE>--Apple-Mail-96--321618545<BR></BLOCKQUOTE>
<BLOCKQUOTE>Content-Type: text/html;<BR></BLOCKQUOTE>
<BLOCKQUOTE><SPAN style="WHITE-SPACE: pre" class=ecxApple-tab-span></SPAN>charset=US-ASCII<BR></BLOCKQUOTE>
<BLOCKQUOTE>Content-Transfer-Encoding: quoted-printable<BR></BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE>
<BLOCKQUOTE><html><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: space; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-line-break: after-white-space; "><div =<BR></BLOCKQUOTE>
<BLOCKQUOTE>apple-content-edited=3D"true"><span class=3D"Apple-style-span" =<BR></BLOCKQUOTE>
<BLOCKQUOTE>style=3D"border-collapse: separate; color: rgb(0, 0, 0); font-family: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>Helvetica; font-size: 12px; font-style: normal; font-variant: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>font-weight: normal; letter-spacing: normal; line-height: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>white-space: normal; widows: 2; word-spacing: 0px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>auto; -webkit-text-stroke-width: 0; "><div style=3D"word-wrap: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>break-word; -webkit-nbsp-mode: space; -webkit-line-break: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>after-white-space; "><span class=3D"Apple-style-span" =<BR></BLOCKQUOTE>
<BLOCKQUOTE>style=3D"border-collapse: separate; -webkit-border-horizontal-spacing: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); =<BR></BLOCKQUOTE>
<BLOCKQUOTE>font-family: Helvetica; font-size: 12px; font-style: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>font-variant: normal; font-weight: normal; letter-spacing: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>line-height: normal; -webkit-text-decorations-in-effect: none; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div =<BR></BLOCKQUOTE>
<BLOCKQUOTE>style=3D"word-wrap: break-word; -webkit-nbsp-mode: space; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-line-break: after-white-space; "><span class=3D"Apple-style-span" =<BR></BLOCKQUOTE>
<BLOCKQUOTE>style=3D"border-collapse: separate; -webkit-border-horizontal-spacing: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); =<BR></BLOCKQUOTE>
<BLOCKQUOTE>font-family: Helvetica; font-size: 12px; font-style: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>font-variant: normal; font-weight: normal; letter-spacing: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>line-height: normal; -webkit-text-decorations-in-effect: none; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-style-span" style=3D"border-collapse: separate; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>font-style: normal; font-variant: normal; font-weight: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>letter-spacing: normal; line-height: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-decorations-in-effect: none; text-indent: 0px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>white-space: normal; widows: 2; word-spacing: 0px; "><span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-style-span" style=3D"border-collapse: separate; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>font-style: normal; font-variant: normal; font-weight: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>letter-spacing: normal; line-height: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-decorations-in-effect: none; text-indent: 0px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>white-space: normal; widows: 2; word-spacing: 0px; "><span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-style-span" style=3D"border-collapse: separate; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>font-style: normal; font-variant: normal; font-weight: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>letter-spacing: normal; line-height: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-decorations-in-effect: none; text-indent: 0px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>white-space: normal; widows: 2; word-spacing: 0px; "><span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-style-span" style=3D"border-collapse: separate; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>font-style: normal; font-variant: normal; font-weight: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>letter-spacing: normal; line-height: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-decorations-in-effect: none; text-indent: 0px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>white-space: normal; widows: 2; word-spacing: 0px; "><span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-style-span" style=3D"border-collapse: separate; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>font-style: normal; font-variant: normal; font-weight: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>letter-spacing: normal; line-height: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-decorations-in-effect: none; text-indent: 0px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>white-space: normal; widows: 2; word-spacing: 0px; "><span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-style-span" style=3D"border-collapse: separate; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>font-style: normal; font-variant: normal; font-weight: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>letter-spacing: normal; line-height: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-decorations-in-effect: none; text-indent: 0px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>white-space: normal; widows: 2; word-spacing: 0px; "><span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-style-span" style=3D"border-collapse: separate; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>font-style: normal; font-variant: normal; font-weight: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>letter-spacing: normal; line-height: normal; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-decorations-in-effect: none; text-indent: 0px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>white-space: normal; widows: 2; word-spacing: 0px; "><div><span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-style-span" style=3D"font-size: medium;"><font =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-style-span" color=3D"#0000FF" face=3D"'Gill Sans'">In =<BR></BLOCKQUOTE>
<BLOCKQUOTE>general, it is OK in M3 to associate multiple conditions with the same =<BR></BLOCKQUOTE>
<BLOCKQUOTE>mutex. But not vice versa.</font></span></div><div><font =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-style-span" color=3D"#0000FF" face=3D"'Gill Sans'"><span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-style-span" style=3D"font-size: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>medium;"><br></span></font></div></span></span></span></span></span></span=<BR></BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE></span></span></div></span></div></span></div><div><div>On 8 Oct 2009, =<BR></BLOCKQUOTE></BLOCKQUOTE>
<BLOCKQUOTE>at 09:32, Jay K wrote:</div><br =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-interchange-newline"><blockquote type=3D"cite"><span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-style-span" style=3D"border-collapse: separate; color: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>rgb(0, 0, 0); font-family: Helvetica; font-size: medium; font-style: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>normal; font-variant: normal; font-weight: normal; letter-spacing: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>normal; line-height: normal; orphans: 2; text-align: auto; text-indent: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>0px; text-transform: none; white-space: normal; widows: 2; word-spacing: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>0px; -webkit-border-horizontal-spacing: 0px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-border-vertical-spacing: 0px; =<BR></BLOCKQUOTE>
<BLOCKQUOTE>-webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: =<BR></BLOCKQUOTE>
<BLOCKQUOTE>auto; -webkit-text-stroke-width: 0px; "><div class=3D"hmmessage" =<BR></BLOCKQUOTE>
<BLOCKQUOTE>style=3D"font-size: 10pt; font-family: Verdana; ">condition =<BR></BLOCKQUOTE>
<BLOCKQUOTE>variables/win32<br> <br><br>So..one way I think about condition =<BR></BLOCKQUOTE>
<BLOCKQUOTE>variables<br>is that you want to be woken when someone else<br>leaves =<BR></BLOCKQUOTE>
<BLOCKQUOTE>the mutex that guards the data that you are dealing with.<br>You want to =<BR></BLOCKQUOTE>
<BLOCKQUOTE>know when another thread modifies the data.<br>(If you have a =<BR></BLOCKQUOTE>
<BLOCKQUOTE>reader/writer lock, you only want to be<br>woken when someone exits a =<BR></BLOCKQUOTE>
<BLOCKQUOTE>write.)<br> <br><br>Now, if you consider a producer/consumer =<BR></BLOCKQUOTE>
<BLOCKQUOTE>queue.<br>There are two interesting occurences.<br>Transitions from =<BR></BLOCKQUOTE>
<BLOCKQUOTE>empty to non-empty<br>and transitions from full to non-full =<BR></BLOCKQUOTE>
<BLOCKQUOTE>(optionally,<br>if it is fixed size).<br> <br><br>Consumers wait =<BR></BLOCKQUOTE>
<BLOCKQUOTE>for empty to non-empty.<br>Consumers signal full to =<BR></BLOCKQUOTE>
<BLOCKQUOTE>non-full.<br>Producers wait for full to non-full.<br>Producers signal =<BR></BLOCKQUOTE>
<BLOCKQUOTE>non-empty to empty.<br> <br><br>So, in this case, one mutex is =<BR></BLOCKQUOTE>
<BLOCKQUOTE>likely used with with two condition =<BR></BLOCKQUOTE>
<BLOCKQUOTE>variables.<br> <br><br>But, what if we take a simplifying =<BR></BLOCKQUOTE>
<BLOCKQUOTE>deoptimization and assume that a condition<br>variable is only ever =<BR></BLOCKQUOTE>
<BLOCKQUOTE>associated with one mutex?<br>Anyone existing that mutex wakes up anyone =<BR></BLOCKQUOTE>
<BLOCKQUOTE>waiting on any condition associated with it?<br>Like, a condition =<BR></BLOCKQUOTE>
<BLOCKQUOTE>variable I think becomes stateless and everything is<br>about the =<BR></BLOCKQUOTE>
<BLOCKQUOTE>mutex?<br> <br> <br>What is the =<BR></BLOCKQUOTE>
<BLOCKQUOTE>downside?<br> <br><br>Condition variables are allowed to have =<BR></BLOCKQUOTE>
<BLOCKQUOTE>spurious wakeups.<br>This would "just" increase them. Too =<BR></BLOCKQUOTE>
<BLOCKQUOTE>much?<br> <br><br>So, therefore, what would be wrong with the =<BR></BLOCKQUOTE>
<BLOCKQUOTE>following design?<br> a mutex contains an event<span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-converted-space"> </span><br> and a number of =<BR></BLOCKQUOTE>
<BLOCKQUOTE>waiters, zero or non-zero<span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-converted-space"> </span><br> if a mutex is =<BR></BLOCKQUOTE>
<BLOCKQUOTE>exiting with a non-zero number of waiters, signal the =<BR></BLOCKQUOTE>
<BLOCKQUOTE>event<br> <br><br>To handle Signal vs. Broadcast<br>method =<BR></BLOCKQUOTE>
<BLOCKQUOTE>1:<br> the number of waiters might be interlocked<br> the =<BR></BLOCKQUOTE>
<BLOCKQUOTE>woken would decrement it<br> if it isn't zero, signal the event =<BR></BLOCKQUOTE>
<BLOCKQUOTE>again<br> <br><br>method 2:<br> the number of waiters is both =<BR></BLOCKQUOTE>
<BLOCKQUOTE>an integer and a semaphore<br> and the lock exiter raises the =<BR></BLOCKQUOTE>
<BLOCKQUOTE>semaphore by the the integer<br><br> <br>method 3:<br> it is =<BR></BLOCKQUOTE>
<BLOCKQUOTE>not an auto-reset event and there is a count<br> and when the =<BR></BLOCKQUOTE>
<BLOCKQUOTE>count goes to 0, reset the event<br> I think in this case you have =<BR></BLOCKQUOTE>
<BLOCKQUOTE>to maintain a "wait generation"<span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-converted-space"> </span><br> so that new =<BR></BLOCKQUOTE>
<BLOCKQUOTE>waiters don't prevent the count from ever hitting 0.<br> I think =<BR></BLOCKQUOTE>
<BLOCKQUOTE>this #3 is what Java might be doing, and is described here:<br><a =<BR></BLOCKQUOTE>
<BLOCKQUOTE>href=3D"<A href="http://www.cs.wustl.edu/~schmidt/win32-cv-1.html">http://www.cs.wustl.edu/~schmidt/win32-cv-1.html</A>"><A href="http://www.cs.wu/">http://www.cs.wu</A>=<BR></BLOCKQUOTE>
<BLOCKQUOTE>stl.edu/~schmidt/win32-cv-1.html</a><br> "3.3. The Generation Count =<BR></BLOCKQUOTE>
<BLOCKQUOTE>Solution"<br><br> <br>also:<br><a =<BR></BLOCKQUOTE>
<BLOCKQUOTE>href=3D"<A href="http://www.cs.wustl.edu/~schmidt/win32-cv-1.html">http://www.cs.wustl.edu/~schmidt/win32-cv-1.html</A>"><A href="http://www.cs.wu/">http://www.cs.wu</A>=<BR></BLOCKQUOTE>
<BLOCKQUOTE>stl.edu/~schmidt/win32-cv-1.html</a><br>3.2. The SetEvent =<BR></BLOCKQUOTE>
<BLOCKQUOTE>Solution<br>Evaluating the SetEvent Solution<br>Incorrectness --<span =<BR></BLOCKQUOTE>
<BLOCKQUOTE>class=3D"Apple-converted-space"> </span><br> <br><br>Is that =<BR></BLOCKQUOTE>
<BLOCKQUOTE>incorrect case really necessarily incorrect?<br>It seems unfair, since =<BR></BLOCKQUOTE>
<BLOCKQUOTE>first waiter should be first woken, but..?<br><br> <br>Am I missing =<BR></BLOCKQUOTE>
<BLOCKQUOTE>something? A lot?<br> <br><br> - =<BR></BLOCKQUOTE>
<BLOCKQUOTE>Jay<br></div></span></blockquote></div><br></body></html>=<BR></BLOCKQUOTE>
<BLOCKQUOTE><BR></BLOCKQUOTE>
<BLOCKQUOTE>--Apple-Mail-96--321618545--<BR></BLOCKQUOTE></DIV></BLOCKQUOTE></DIV><BR></DIV> </body>
</html>