[M3devel] Yet another bug in Win-32 generation count threads

Rodney M. Bates rodney_bates at lcwb.coop
Wed Jul 20 20:00:28 CEST 2016


The more I look at this generation count approach to implementing
Modula-3 condition variables on top of what Windows has, the less
I like it.  It's very hard to understand, but as I get closer,
I think I see yet another bug.

Assume ticket counting is fixed.

There are several waiting threads, say 5.  c.waiters = 5 and
c.counter = 0.  A M3-Broadcast happens.  It does
(Win-)SetEvent(c.waitEvent), sets c.counter := 1, and
c.tickets := 5, making all the waiters eligible to get
past the waitDone test, which they start doing.  From the
abstract M3-condition variable point of view, all have
already been released from the Condition variable, but
have some cleanup to do inside (M3-)Wait.

One by one, they proceed, say 3 of them.  Two waiters
remain, c.waiters = c.tickets = 2, and all have counts
that make them eligible for waitDone.

Now, two more waiters do M3-Waits.  c.counter still = 1, and
their local counts = 1, making them ineligible to get
past waitDone.  Then a M3-Signal happens.  c.counter
gets incremented to 2, so all all 4 waiters are now eligible
to pass that test.  c.tickets gets increased to 3, supposedly
so the two that were broadcast-released and one of the new
ones can proceed.

But it is randomly possible that both the new ones get
released (which would be OK), taking two of the tickets,
one of the older ones get released, taking the last ticket,
and the remaining is stuck waiting when it should not, for
lack of a ticket.

-- 
Rodney Bates
rodney.m.bates at acm.org


More information about the M3devel mailing list