[M3devel] condition variables/win32

[jay.krell at cornell.edu]

Also it may be possible/easy to remove the need to create the thread  
in Modula-3, though dllmain could also address that.

  - Jay (phone)

On Oct 20, 2009, at 6:04 PM, jayk123 at hotmail.com wrote:

> Also removing our giant lock would be good either way, if possible.
>
>  - Jay (phone)
>
> On Oct 20, 2009, at 5:58 PM, jayk123 at hotmail.com wrote:
>
>> Something doesn't add up. I'll have to reread.  The paper I think  
>> assumes one mutex per condition, also clearly is talking about "our  
>> library". I'll need to compare the paper and the library. Could be  
>> the paper is wrong. A lot of literature here depends on atomic  
>> SignalAndWait but the docs just changed and no longer claim  
>> atomicity.
>>
>>  - Jay (phone)
>>
>> On Oct 20, 2009, at 2:05 PM, Tony Hosking <hosking at cs.purdue.edu>  
>> wrote:
>>
>>> 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/4a689bbe/attachment-0002.html>