[M3devel] condition variables/win32

[Randy Coleburn]

Jay:
 
I have written and extensively tested a number of modules using threading.  
 
For example, I have a nice multi-reader, single-writer lock implementation, a gatekeeper implementation, an object-database implementation, etc.  All of these are built on top of the thread primitives in Modula-3.
 
So there is no need to reinvent the wheel here.  If you need to see some of the code for these, let me know.  Perhaps I can contribute some of these to the community.
 
At this point, do we have any concrete example of a failure in the Win32 threading implementation, other than something mysterious with Juno?
 
Regards,
Randy

>>> Jay K <jay.krell at cornell.edu> 10/8/2009 9:32 AM >>>
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

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/20091008/a69d2e84/attachment-0002.html>