[M3devel] condition variables/win32
Randy Coleburn
rcoleburn at scires.com
Tue Oct 20 18:23:04 CEST 2009
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 ( 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 ( 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--
CONFIDENTIALITY NOTICE: This email and any attachments are intended solely for the use of the named recipient(s). This e-mail may contain confidential and/or proprietary information of Scientific Research Corporation. If you are not a named recipient, you are prohibited from making any use of the information in the email and attachments. If you believe you have received this email in error, please notify the sender immediately and permanently delete the email, any attachments, and all copies thereof from any drives or storage media and destroy any printouts of the email or attachments.
EXPORT COMPLIANCE NOTICE: This email and any attachments may contain technical data subject to U.S export restrictions under the International Traffic in Arms Regulations (ITAR) or the Export Administration Regulations (EAR). Export or transfer of this technical data and/or related information to any foreign person(s) or entity(ies), either within the U.S. or outside of the U.S., may require export authorization by the appropriate U.S. Government agency prior to export or transfer. In addition, technical data may not be exported or transferred to certain countries or specified designated nationals identified by U.S. embargo controls without prior export authorization. By accepting this email and any attachments, all recipients confirm that they understand and will comply with all applicable ITAR, EAR and embargo compliance requirements.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20091020/fdc26e90/attachment-0002.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ImplementingCVs.pdf
Type: application/pdf
Size: 155564 bytes
Desc: not available
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20091020/fdc26e90/attachment-0002.pdf>
More information about the M3devel
mailing list