<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 12pt;
font-family:Calibri
}
--></style></head>
<body class='hmmessage'><div dir='ltr'>That question was meant for the other bug.<BR> <BR>Can this one be fixed by rechecking if tickets is positive before decrementing it?<BR>This seems like a big problem in Schmidt's code.<BR> <BR>I'm nervous about merging the locks, but maybe.<BR>In particular, I'm the multiple release/acquires in service of the condition variable, also releasing/acquiring the user variable.<BR>Though I realize that is actually necessarily part of what gets done.<BR>Schmidt clearly did not merge the locks, and the Java version does.<BR>The Java version also has its own simple and not-terrible critical section.<BR>The Java version also disappeared in newer releases and I didn't track down what happened to it.<BR> <BR> - Jay<br><br> <BR><div><hr id="stopSpelling">From: jay.krell@cornell.edu<br>To: rodney.m.bates@acm.org<br>CC: m3devel@elegosoft.com<br>Subject: RE: [M3devel] purported condition variable problems on Win32?<br>Date: Thu, 21 Jul 2016 06:35:41 +0000<br><br>
<style><!--
.ExternalClass .ecxhmmessage P {
padding:0px;
}
.ExternalClass body.ecxhmmessage {
font-size:12pt;
font-family:Calibri;
}
--></style>
<div dir="ltr">Am I understanding this?<br> There are some waiters. <br> There is a broadcast ("wake all"). Some waiters are woken. <br> There are more waiters. <br> There is a signal ("wake one"). <br> There is a chance that some of the original waiters will remain waiting while the later waiters are not. <br> That is, the signaled threads kind of steal the wake intended by the broadcast. <br> <br> <br>Is this unfairness or incorrectness?<br>It feels like unfairness.<br>It feels like condition variables are specified fairly weakly.<br> <br> <br> - Jay<br><br> <br><div>> Date: Wed, 20 Jul 2016 11:43:27 -0500<br>> From: rodney_bates@lcwb.coop<br>> To: jay.krell@cornell.edu; rodney.m.bates@acm.org<br>> CC: m3devel@elegosoft.com<br>> Subject: Re: [M3devel] purported condition variable problems on Win32?<br>> <br>> In looking at ThreadWin32.m3 more, I think I see a significant bug.<br>> <br>> This gets confusing, since there are Modula-3 waits, signals,<br>> etc. and similar concepts in Win32, but which are not the<br>> same. I am going the try to put "M3-" and "Win-" prefixes on<br>> things to make this clearer. I cartainly need to do this<br>> for my own benefit, if for nobody else.<br>> <br>> Suppose two threads are both M3-waiting in Wait(m,c,...), further<br>> Win-waiting on c.waitEvent in WaitForMultipleObjects at :301.<br>> c.tickets = 0, and c.waiters = 2.<br>> <br>> Now, (M3-)Signal (c) happens. This does (Win-)SetEvent(c.waitEvent),<br>> which will allow both the waiters to Win-wakeup sometime soon.<br>> Before releasing c.lock, Signal increments c.tickets to 1 (supposedly<br>> to eventually allow only one waiter to M3-wakeup) and increments<br>> c.counter, setting things up so that the waitDone expression at :308<br>> will be TRUE for the waiting threads, the next time they evaluate it.<br>> <br>> Each waiter in turn Win-wakes, gets c.lock, sets waitDone TRUE,<br>> releases c.lock, and tries to acquire m. The problem arises<br>> because the second waiter can get to these steps before the first<br>> can acquire m, acquire c.lock, and DEC(c.tickets) at :322. The<br>> second to reach :308 will find c.tickets # 0, as did the first,<br>> and proceed.<br>> <br>> Each will eventually, do a M3-wake. If this were Posix condition<br>> variables, this would be wrong, because Posix says only one<br>> waiter proceeds. For M3, it's OK, if unnecessary, because M3<br>> says one or more waiters proceed. However, each will, in the<br>> process, get to :322, and DEC(c.tickets). Signal only provided<br>> one ticket, but the waiters have taken two. c.tickets goes<br>> negative.<br>> <br>> After this, when some thread can do another (M3-)Wait, and some<br>> other does another (M3-)Signal, c.tickets increments only back to<br>> zero, which means the new waiter will not M3-wake, even though it<br>> should.<br>> <br>> <br>> I am going to try to construct a test case that will force<br>> this scenario.<br>> <br>> See more below:<br>> <br>> <br>> On 07/18/2016 08:53 PM, Jay wrote:<br>> > I wrote this version. Right, based on Schmidt. I also found similar code in Java. There are comments as to both of these in the code.<br>> ><br>> > Otherwise previous version I think had a very large lock.<br>> ><br>> > Changing the < to !=, is that really ok? I get that 32bit overflow is possible.<br>> ><br>> > We can change to a 64bit counter if < is required. That really can't rollover. I.e. Even a 64bit cycle counter can't rollover, and this would advance much slower.<br>> ><br>> > I guess you are saying it would be unfair, which is ok.<br>> ><br>> > There is pattern called "directed notification" or such that might be preferable? It has a certain significant inefficiency though, like creating an event per notify. I think it is what boost's condition variable are using.<br>> ><br>> > I'll check on the unused event.<br>> ><br>> > - Jay<br>> ><br>> >> On Jul 18, 2016, at 7:25 AM, "Rodney M. Bates" <rodney_bates@lcwb.coop> wrote:<br>> >><br>> >><br>> >><br>> >><br>> >><br>> >> I spent some time looking over the signal part of ThreadWin32.m3. A few<br>> >> comments:<br>> >><br>> >> This looks like a very direct implementation of Schmidts' generation count<br>> >> algorithm, with a number of important little details additionally taken care<br>> >> of.<br>> >><br>> >> On small difference is at line 308 (B, below) where Schmidt does<br>> >> c.counter>count instead of #. Usually, this would make no difference,<br>> >> since counter only increases, but on a long-running program, it could<br>> >> overflow. If this happened,as it often does, as silent wrap-around to<br>> >> FIRST(INTEGER), some threads could be trapped for an extremely long<br>> >> time, waiting for counter come back around greater than their count. As<br>> >> coded in ThreadWin32, they would be allowed to proceed normally.<br>> >><br>> >> The only glitch would be that, if there were simultaneously waiting threads<br>> >> separated by NUMBER(INTEGER) truly different generations (but the same value<br>> >> of c.counter), the recent ones could unfairly proceed along with the<br>> >> extremely old ones. That seems extremely less likely than the<br>> >> mere existence of an overflow.<br>> >><br>> >> Both type Condition and type Activation have a field waitEvent: HANDLE.<br>> >> Condition.waitEvent is extensively used, but Activation.waitEvent is<br>> >> only created at :537 and deleted at :554, but never used in any real<br>> >> way. It could be deleted.<br>> >><br>> >> As for this code:<br>> >><br>> >> EnterCriticalSection(conditionLock);<br>> >><br>> >> (* Capture the value of the counter before we start waiting.<br>> >> * We will not stop waiting until the counter changes.<br>> >> * That is, we will not stop waiting until a signal<br>> >> * comes in after we start waiting.<br>> >> *)<br>> >><br>> >> count := c.counter;<br>> >> INC(c.waiters);<br>> >><br>> >> LeaveCriticalSection(conditionLock);<br>> >> m.release(); (* can this be moved to before taking conditionLock? *)<br>> >><br>> >> No, it is important to sample and save c.counter in the order threads wait.<br>> >> Retaining m until this is done ensures this. Otherwise, some other thread<br>> >> that waited later could have altered c.counter before this one gets conditionLock<br>> >> and saves its copy of c.counter.<br>> >><br>> >> I have made several comment changes to ThreadWin32.m3 that would have made<br>> >> it easier to vet. I will commit these, but only comments. It is either<br>> >> very difficult or impossible for me to test or even recompile this module,<br>> >> and, especially as fragile as this kind of code is, I don't want to commit<br>> >> any substantive changes untested and uncompiled.<br>> >><br>> >> More below:<br>> >><br>> >>> On 07/07/2016 04:24 AM, Jay K wrote:<br>> >>> So...I do NOT understand all of this.<br>> >>><br>> >>><br>> >>> However, comparing the three implementations<br>> >>> and attempting to understand ours,<br>> >>> I am struck by the following<br>> >>><br>> >>> - Our broadcast seems ok, but<br>> >>> - our signal seems to wake everyone,<br>> >>> and then...they race a bit,<br>> >>> one will decide it is last, and<br>> >>> reset the event, but every prior waiter<br>> >>> is still woken.<br>> >>> Why not merge the following chunks:<br>> >><br>> >> I don't think this will work. It is important that, once a thread has decided,<br>> >> at A, that it can fairly proceed, it is guaranteed to be the next thread to proceed<br>> >> (i.e, to return from [Alert]Wait), before it decrements c.tickets at C, and, thus,<br>> >> if it is also the last of its generation to proceed, resets c.waitevent. This<br>> >> is ensured by its having already reacquired m first, preventing any other thread<br>> >> from returning from its Wait yet.<br>> <br>> I was wrong about this. There is already no fairness being enforced here. Even with<br>> only one ticked, all waiters Win-wake at :301, the order they get c.lock at :307 is<br>> arbitrary anyway. There is no benefit in trying to control the order they reacquire m.<br>> c.counter has nothing to do with fairness. What it does is prevent Win-awakened waiters<br>> that waited after the most recent Signal/Broadcast from M3-waking, a correctness issue.<br>> <br>> Merging, as you proposed, is probably close to the fix for this bug.<br>> <br>> <br>> >><br>> >> And it can't attempt to acquire m while already holding conditionLock, because this would<br>> >> invite deadlock, since, elsewhere, a thread can try to acquire conditionLock while<br>> >> already holding m, at line 265.<br>> >><br>> >>><br>> >>><br>> >>> WHILE (NOT alerted) AND (NOT waitDone) DO<br>> >>> .<br>> >>> .<br>> >>> .<br>> >>> 1<br>> >>> EnterCriticalSection(conditionLock);<br>> >>> waitDone := (c.tickets # 0 AND c.counter # count);<br>> >> A:---------^<br>> >> B:--------------------------------------------------^<br>> >>> LeaveCriticalSection(conditionLock);<br>> >>> END; (* WHILE *)<br>> >>> IF waitDone THEN<br>> >>> alerted := FALSE;<br>> >>> END;<br>> >>> m.acquire();<br>> >>> 2<br>> >>> EnterCriticalSection(conditionLock);<br>> >>> DEC(c.waiters);<br>> >>> IF waitDone THEN esp. here.<br>> >>> DEC(c.tickets);<br>> >><br>> >> C:---------------^<br>> >>> lastWaiter := (c.tickets = 0);<br>> >>> END;<br>> >>> LeaveCriticalSection(conditionLock);<br>> >>><br>> >>><br>> >>> That is, if we decrement tickets earlier<br>> >>> within the first critical section,<br>> >>> while we will still wake everyone,<br>> >>> only one will decide waitDone and the rest will keep looping.<br>> >>> A downside of this, perhaps, is that waking all for Broadcast<br>> >>> might be a little slower.<br>> >>> but more so, in both the "ptw32" (pthreads for win32) and Boost threads<br>> >>> implementations, they seem to deal with this differently than us,<br>> >>> and they each do about the same thing -- they use a counted semaphore.<br>> >>> In the boost case, it appears they duplicate the semaphore for every<br>> >>> notification generation, which seems expensive.<br>> >>><br>> >>> Perhaps if they can guarantee some lifetimes, they don't need to duplicate it.<br>> >>> Or they can do their own reference counting?<br>> >>> jdk7 seems to looke like jdk6.<br>> >>> The code is gone in jdk8 and I can't easily find the delete in history.<br>> >>> The lock merging jdk does probably helps here too.<br>> >>> In fact they merge #1 and #2 above as a result.<br>> >>> But they still initially wake all threads for signal, not just broadcast.<br>> >>> There is also the problem that all the event waits<br>> >>> are followed by EnterCriticalSection (or jdk facsimile).<br>> >>> - Jay<br>> >>><br>> >>><br>> >>><br>> >>><br>> >>> -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------!<br>> --!<br>> >> ---<br>> >>> From: jay.krell@cornell.edu<br>> >>> To: m3devel@elegosoft.com<br>> >>> Subject: RE: [M3devel] purported condition variable problems on Win32?<br>> >>> Date: Tue, 5 Jul 2016 08:26:36 +0000<br>> >>><br>> >>> Here is another implementation to consider:<br>> >>><br>> >>> https://github.com/boostorg/thread/blob/develop/include/boost/thread/win32/condition_variable.hpp<br>> >>><br>> >>> - Jay<br>> >>><br>> >>><br>> >>> -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------!<br>> --!<br>> >> ---<br>> >>> From: jay.krell@cornell.edu<br>> >>> To: m3devel@elegosoft.com<br>> >>> Date: Tue, 5 Jul 2016 08:19:23 +0000<br>> >>> Subject: [M3devel] purported condition variable problems on Win32?<br>> >>><br>> >>> https://sourceforge.net/p/pthreads4w/code/ci/master/tree/README.CV<br>> >>><br>> >>> vs.<br>> >>><br>> >>> http://www.cs.wustl.edu/~schmidt/win32-cv-1.html<br>> >>> vs.<br>> >>> https://modula3.elegosoft.com/cgi-bin/cvsweb.cgi/cm3/m3-libs/m3core/src/thread/WIN32/ThreadWin32.m3?rev=1.210.2.1;content-type=text%2Fplain<br>> >>> I wrote this:<br>> >>> PROCEDURE XWait(m: Mutex; c: Condition; act: Activation;<br>> >>> alertable: BOOLEAN) RAISES {Alerted} =<br>> >>> (* LL = m on entry and exit, but not for the duration<br>> >>> * see C:\src\jdk-6u14-ea-src-b05-jrl-23_apr_2009\hotspot\agent\src\os\win32\Monitor.cpp<br>> >>> * NOTE that they merge the user lock and the condition lock.<br>> >>> * http://www.cs.wustl.edu/~schmidt/win32-cv-1.html<br>> >>> * "3.3. The Generation Count Solution"<br>> >>> *)<br>> >>><br>> >>> Do we have the problems described in README.CV?<br>> >>><br>> >>> I haven't looked through the ACE code to see<br>> >>> to what extent they resemble solution 3.3, or if they<br>> >>> changed as a result of this discussion -- which I admit I don't understand<br>> >>> and haven't read closely.<br>> >>><br>> >>><br>> >>> Spurious wakeups are ok, though should be minimized.<br>> >>><br>> >>> I'd still rather not drop pre-Vista support but I realize it becomes more interesting as time advances.<br>> >>><br>> >>> Thank you,<br>> >>> - Jay<br>> >>><br>> >>> _______________________________________________ M3devel mailing list M3devel@elegosoft.com https://m3lists.elegosoft.com/mailman/listinfo/m3devel<br>> >>><br>> >>><br>> >>> _______________________________________________<br>> >>> M3devel mailing list<br>> >>> M3devel@elegosoft.com<br>> >>> https://m3lists.elegosoft.com/mailman/listinfo/m3devel<br>> >><br>> >> --<br>> >> Rodney Bates<br>> >> rodney.m.bates@acm.org<br>> >><br>> >><br>> ><br>> <br>> -- <br>> Rodney Bates<br>> rodney.m.bates@acm.org<br></div> </div></div> </div></body>
</html>