[M3devel] condition variables/win32

[Tony Hosking]

Should we not also consider fixing any problems in the existing Win32  
threading?  That paper does give a very straightforward recipe for  
building Moulda-3 style mutex/condition semantics using semaphores,  
which Windows does provide.

On 20 Oct 2009, at 16:26, jay.krell at cornell.edu wrote:

> I will read the paper, thanks.
>
> The java code demonstrates I believe some important applicable  
> methods. I hope to have a "new" ThreadWin32.m3 "soon". In  
> particular, no per-thread event, no wait lists, and counter to help  
> matching up condition waits and signals. And no giant lock. And stil  
> an efficient mutex with no kernel involvement unless there is  
> contention, could/might use win32 criticalsection with little extra  
> to avoid recursion, or could use something smaller. And no use of  
> SignalObjectAndWait whose documentation recently changed to remove  
> the atomicity claim!
>
>  - Jay (phone)
>
> On Oct 20, 2009, at 9:23 AM, "Randy Coleburn" <rcoleburn at scires.com>  
> wrote:
>
>> Jay:
>>
>> I think we would need to delve deep into the implementation to be  
>> able to answer all your questions precisely.
>>
>> I've attached a short paper by Andrew Birrell "Implementing  
>> Condition Variables with Semaphores" that you may find  
>> interesting / enlightening.
>>
>> My concern about using multiple mutex with same condition lies in  
>> the queuing operations.  My recollection is that I've always  
>> associated only one mutex with a condition variable, but that you  
>> can have multiple conditions associated with the same mutex.
>>
>> I will go back and re-read Nelson again--its been a few years.
>>
>> Regards,
>> Randy Coleburn
>>
>> >>> Jay K <jay.krell at cornell.edu> 10/18/2009 4:16 AM >>>
>> I still have questions here.
>>
>> 1)
>> Page 93 of the Nelson book:
>> A monitor consists of some data, a mutex, and zero or more condition
>> variables. A particular condition variable is always used
>> in conjunction with the same mutex and its data.
>>
>> Doesn't this contradict the point made here?
>> Does a condition variable always map to the same mutex
>> or not?
>>
>> Or is this merely describing a typical usage pattern that is
>> a subset of what interface Thread allows?
>>
>>
>> 2)
>> Can Wait only be satisfied by Signal/Broadcast,
>> or also just via UnlockMutex?
>>
>>
>> Depending on the answer to these questions,
>> it seems you can largely merge mutex and condition variable.
>>
>>
>> Condition variable is basically waiting for a
>> thread to exit a mutex.
>> Which is very very similar to LockMutex, except
>> that it doesn't want to take the mutex in the uncontended
>> case, it actually wants to wait for another thread
>> to both acquire and release the mutex.
>>
>>
>> I suspect I'm wrong on both of these.
>> That condition variable really can use multiple mutexes.
>> That exiting a mutex has no obligation to wake condition variables,
>>   though it might be in good faith to do so...er..if it is
>>   in good faith to not require programmer to use Signal/Broadcast.
>>
>>
>> Thanks,
>>  - Jay
>>
>>
>>
>> From: jay.krell at cornell.edu
>> To: hosking at cs.purdue.edu; mika at async.async.caltech.edu
>> Date: Thu, 8 Oct 2009 19:13:03 +0000
>> CC: m3devel at elegosoft.com
>> Subject: Re: [M3devel] condition variables/win32
>>
>> That seems a little strange to me but I guess I'll have to keep it  
>> in mind.
>>
>>  - Jay
>>
>>
>> From: hosking at cs.purdue.edu
>> To: mika at async.async.caltech.edu
>> Date: Thu, 8 Oct 2009 11:00:36 -0400
>> CC: m3devel at elegosoft.com
>> Subject: Re: [M3devel] condition variables/win32
>>
>> 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.
>>
>> On 8 Oct 2009, at 10:34, Mika Nystrom wrote:
>>
>> Why can't you use the same condition variable with different mutexes?
>>
>> This is dynamic, up to the M3 programmer, no?
>>
>> Tony Hosking writes:
>>
>> --Apple-Mail-96--321618545
>> Content-Type: text/plain;
>> charset=US-ASCII;
>> format=flowed;
>> delsp=yes
>> Content-Transfer-Encoding: 7bit
>>
>> In general, it is OK in M3 to associate multiple conditions with the
>> same mutex.  But not vice versa.
>>
>> On 8 Oct 2009, at 09:32, Jay K wrote:
>>
>> condition variables/win32
>>
>>
>> So..one way I think about condition variables
>> is that you want to be woken when someone else
>> leaves the mutex that guards the data that you are dealing with.
>> You want to know when another thread modifies the data.
>> (If you have a reader/writer lock, you only want to be
>> woken when someone exits a write.)
>>
>>
>> Now, if you consider a producer/consumer queue.
>> There are two interesting occurences.
>> Transitions from empty to non-empty
>> and transitions from full to non-full (optionally,
>> if it is fixed size).
>>
>>
>> Consumers wait for empty to non-empty.
>> Consumers signal full to non-full.
>> Producers wait for full to non-full.
>> Producers signal non-empty to empty.
>>
>>
>> So, in this case, one mutex is likely used with with two condition
>> variables.
>>
>>
>> But, what if we take a simplifying deoptimization and assume that a
>> condition
>> variable is only ever associated with one mutex?
>> Anyone existing that mutex wakes up anyone waiting on any condition
>> associated with it?
>> Like, a condition variable I think becomes stateless and everything  
>> is
>> about the mutex?
>>
>>
>> What is the downside?
>>
>>
>> Condition variables are allowed to have spurious wakeups.
>> This would "just" increase them. Too much?
>>
>>
>> So, therefore, what would be wrong with the following design?
>> a mutex contains an event
>> and a number of waiters, zero or non-zero
>> if a mutex is exiting with a non-zero number of waiters, signal the
>> event
>>
>>
>> To handle Signal vs. Broadcast
>> method 1:
>> the number of waiters might be interlocked
>> the woken would decrement it
>> if it isn't zero, signal the event again
>>
>>
>> method 2:
>> the number of waiters is both an integer and a semaphore
>> and the lock exiter raises the semaphore by the the integer
>>
>>
>> method 3:
>> it is not an auto-reset event and there is a count
>>  and when the count goes to 0, reset the event
>> I think in this case you have to maintain a "wait generation"
>> so that new waiters don't prevent the count from ever hitting 0.
>> I think this #3 is what Java might be doing, and is described here:
>> http://www.cs.wustl.edu/~schmidt/win32-cv-1.html
>> "3.3. The Generation Count Solution"
>>
>>
>> also:
>> http://www.cs.wustl.edu/~schmidt/win32-cv-1.html
>> 3.2. The SetEvent Solution
>> Evaluating the SetEvent Solution
>> Incorrectness --
>>
>>
>> Is that incorrect case really necessarily incorrect?
>> It seems unfair, since first waiter should be first woken, but..?
>>
>>
>> Am I missing something? A lot?
>>
>>
>> - Jay
>>
>>
>> --Apple-Mail-96--321618545
>> Content-Type: text/html;
>> charset=US-ASCII
>> Content-Transfer-Encoding: quoted-printable
>>
>> <html><body style=3D"word-wrap: break-word; -webkit-nbsp-mode:  
>> space; =
>> -webkit-line-break: after-white-space; "><div =
>> apple-content-edited=3D"true"><span class=3D"Apple-style-span" =
>> style=3D"border-collapse: separate; color: rgb(0, 0, 0); font- 
>> family: =
>> Helvetica; font-size: 12px; font-style: normal; font-variant:  
>> normal; =
>> font-weight: normal; letter-spacing: normal; line-height: normal; =
>> orphans: 2; text-align: auto; text-indent: 0px; text-transform:  
>> none; =
>> white-space: normal; widows: 2; word-spacing: 0px; =
>> -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical- 
>> spacing: =
>> 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size- 
>> adjust: =
>> auto; -webkit-text-stroke-width: 0; "><div style=3D"word-wrap: =
>> break-word; -webkit-nbsp-mode: space; -webkit-line-break: =
>> after-white-space; "><span class=3D"Apple-style-span" =
>> style=3D"border-collapse: separate; -webkit-border-horizontal- 
>> spacing: =
>> 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); =
>> font-family: Helvetica; font-size: 12px; font-style: normal; =
>> font-variant: normal; font-weight: normal; letter-spacing: normal; =
>> line-height: normal; -webkit-text-decorations-in-effect: none; =
>> text-indent: 0px; -webkit-text-size-adjust: auto; text-transform:  
>> none; =
>> orphans: 2; white-space: normal; widows: 2; word-spacing: 0px;  
>> "><div =
>> style=3D"word-wrap: break-word; -webkit-nbsp-mode: space; =
>> -webkit-line-break: after-white-space; "><span class=3D"Apple-style- 
>> span" =
>> style=3D"border-collapse: separate; -webkit-border-horizontal- 
>> spacing: =
>> 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); =
>> font-family: Helvetica; font-size: 12px; font-style: normal; =
>> font-variant: normal; font-weight: normal; letter-spacing: normal; =
>> line-height: normal; -webkit-text-decorations-in-effect: none; =
>> text-indent: 0px; -webkit-text-size-adjust: auto; text-transform:  
>> none; =
>> orphans: 2; white-space: normal; widows: 2; word-spacing: 0px;  
>> "><span =
>> class=3D"Apple-style-span" style=3D"border-collapse: separate; =
>> -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical- 
>> spacing: =
>> 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =
>> font-style: normal; font-variant: normal; font-weight: normal; =
>> letter-spacing: normal; line-height: normal; =
>> -webkit-text-decorations-in-effect: none; text-indent: 0px; =
>> -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =
>> white-space: normal; widows: 2; word-spacing: 0px; "><span =
>> class=3D"Apple-style-span" style=3D"border-collapse: separate; =
>> -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical- 
>> spacing: =
>> 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =
>> font-style: normal; font-variant: normal; font-weight: normal; =
>> letter-spacing: normal; line-height: normal; =
>> -webkit-text-decorations-in-effect: none; text-indent: 0px; =
>> -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =
>> white-space: normal; widows: 2; word-spacing: 0px; "><span =
>> class=3D"Apple-style-span" style=3D"border-collapse: separate; =
>> -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical- 
>> spacing: =
>> 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =
>> font-style: normal; font-variant: normal; font-weight: normal; =
>> letter-spacing: normal; line-height: normal; =
>> -webkit-text-decorations-in-effect: none; text-indent: 0px; =
>> -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =
>> white-space: normal; widows: 2; word-spacing: 0px; "><span =
>> class=3D"Apple-style-span" style=3D"border-collapse: separate; =
>> -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical- 
>> spacing: =
>> 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =
>> font-style: normal; font-variant: normal; font-weight: normal; =
>> letter-spacing: normal; line-height: normal; =
>> -webkit-text-decorations-in-effect: none; text-indent: 0px; =
>> -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =
>> white-space: normal; widows: 2; word-spacing: 0px; "><span =
>> class=3D"Apple-style-span" style=3D"border-collapse: separate; =
>> -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical- 
>> spacing: =
>> 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =
>> font-style: normal; font-variant: normal; font-weight: normal; =
>> letter-spacing: normal; line-height: normal; =
>> -webkit-text-decorations-in-effect: none; text-indent: 0px; =
>> -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =
>> white-space: normal; widows: 2; word-spacing: 0px; "><span =
>> class=3D"Apple-style-span" style=3D"border-collapse: separate; =
>> -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical- 
>> spacing: =
>> 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =
>> font-style: normal; font-variant: normal; font-weight: normal; =
>> letter-spacing: normal; line-height: normal; =
>> -webkit-text-decorations-in-effect: none; text-indent: 0px; =
>> -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =
>> white-space: normal; widows: 2; word-spacing: 0px; "><span =
>> class=3D"Apple-style-span" style=3D"border-collapse: separate; =
>> -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical- 
>> spacing: =
>> 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; =
>> font-style: normal; font-variant: normal; font-weight: normal; =
>> letter-spacing: normal; line-height: normal; =
>> -webkit-text-decorations-in-effect: none; text-indent: 0px; =
>> -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; =
>> white-space: normal; widows: 2; word-spacing: 0px; "><div><span =
>> class=3D"Apple-style-span" style=3D"font-size: medium;"><font =
>> class=3D"Apple-style-span" color=3D"#0000FF" face=3D"'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=3D"Apple-style-span" color=3D"#0000FF" face=3D"'Gill  
>> Sans'"><span =
>> class=3D"Apple-style-span" style=3D"font-size: =
>> medium;"><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=3D"Apple-interchange-newline"><blockquote type=3D"cite"><span =
>> class=3D"Apple-style-span" style=3D"border-collapse: separate;  
>> color: =
>> rgb(0, 0, 0); font-family: Helvetica; font-size: medium; font- 
>> style: =
>> normal; font-variant: normal; font-weight: normal; letter-spacing: =
>> normal; line-height: normal; orphans: 2; text-align: auto; text- 
>> indent: =
>> 0px; text-transform: none; white-space: normal; widows: 2; word- 
>> spacing: =
>> 0px; -webkit-border-horizontal-spacing: 0px; =
>> -webkit-border-vertical-spacing: 0px; =
>> -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: =
>> auto; -webkit-text-stroke-width: 0px; "><div class=3D"hmmessage" =
>> style=3D"font-size: 10pt; font-family: Verdana; ">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=3D"Apple-converted-space"> </span><br> and a number  
>> of =
>> waiters, zero or non-zero<span =
>> class=3D"Apple-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=3D"Apple-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=3D"http://www.cs.wustl.edu/~schmidt/win32-cv-1.html">http://www.cs.wu 
>> =
>> stl.edu/~schmidt/win32-cv-1.html</a><br> "3.3. The Generation  
>> Count =
>> Solution"<br><br> <br>also:<br><a =
>> href=3D"http://www.cs.wustl.edu/~schmidt/win32-cv-1.html">http://www.cs.wu 
>> =
>> stl.edu/~schmidt/win32-cv-1.html</a><br>3.2. The SetEvent =
>> Solution<br>Evaluating the SetEvent Solution<br>Incorrectness -- 
>> <span =
>> class=3D"Apple-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>=
>>
>> --Apple-Mail-96--321618545--
>>
>> <ImplementingCVs.pdf>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20091020/6ccfa2d0/attachment-0002.html>