[M3devel] condition variables/win32

[jay.krell at cornell.edu]

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/af529884/attachment-0001.html>