[M3devel] condition variables/win32
jay.krell at cornell.edu
jay.krell at cornell.edu
Wed Oct 21 03:04:27 CEST 2009
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/49a2c9ce/attachment-0002.html>
More information about the M3devel
mailing list