[Q] Has SharedQueue a very subtle bug?

goran.hultgren at bluefish.se goran.hultgren at bluefish.se
Mon Apr 15 09:26:28 UTC 2002

Ok, a few conclusions:

1. The "move buffer down optimization"-code in #peek should probably be
moved to #next or #nextPut as proposed by Lex. Seems more logical.
2. Scott's addition of #critical: to SharedQueue seems useful in some
cases. Should have proper comments to explain how it can be used.
3. I have a tiny improvement of #makeRoomAtEnd - currently it grows with
a constant size using #, (unecessary copying) - doubling size using
replaceFrom:to:with:startingAt: seems much better (as
OrderedCollection>>grow does).
4. We should always assume that Process switching can occur between any
two given bytecodes. (even if reality might be different).
5. Currently #flush does not "nil out" the current contents, hinders GC.
Easily fixable.

...and then we come to #isEmpty and #size.

Scott A Crosby <crosby at qwes.math.cmu.edu> wrote:
> And you can't get an *accurate* size outside the lock on the semaphore.
> #peek below just means that we run a risk of an inaccurate and possibly
> corrupt size. If #size also got #accessProtect, we'd still have this
> inaccuracy...
> For example, what should the value of 'a' be after this runs?
> ``
> q Sharedqueue new.
> a Array new: 2.
> [[ q nextPut: 1 ; next ] repeatForever] fork.
> [[ a at: q size put: (a at: q size)+1] repeatForever] fork.
> "Now run both of them for a minute."
> ''

This is obviously pseudo code but rewritten as:

| q a p1 p2 |
q := SharedQueue new.
a := (Array new: 3) at: 1 put: 0; at: 2 put: 0; yourself
p1 _ [[ q nextPut: 1; next] repeat] fork.
p2 _ [[ a at: q size + 1 put: (a at: q size + 1) + 1] repeat] fork.
(Delay forSeconds: 60) wait.
p1 terminate. p2 terminate.
a inspect

a at: 1 should give us "how many times size answered 1" etc.

I am not sure what the code was meant to show, Scott? Could you explain?
And it does seem "buggy" to me since you call #size twice in each loop
which could give you different answers... Or was that your point?

When changed to:
p2 _ [[ s _ q size + 1. a at: s put: (a at: s) + 1] repeat] fork.

b _ Bag new.
p2 _ [[ b add: q size] repeat] fork.

I get for these three variations:
#(11148677 11270965 nil)
#(18471587 21643005 nil)
a Dictionary(0->1181866 1->1302894 )

But I don't know what that was supposed to show.

Anyway, if we would protect #size and #isEmpty then those methods could
not be used inside Scott's #critical: (since they would block) and they
still would not be "safe" when used from the outside without #critical:
because there can still be Processes queued up at the readSemaphore or
"just released" from it and just about to get into the accessProtect
semaphore, or already queued up at the accessProtect semaphore.
Translated to english this means that the queue can have readers "queued
up" so naive code like:

q isEmpty not ifTrue:[q next]

...could block because it might be empty after all - the other readers
beat us to it. In short - #size and #isEmpty should be heavily commented
so that people don't get fooled by them.

Actaully, when I come to think of it #nextOrNil is probably pretty buggy
too. Since it doesn't wait on the readSemaphore it just might go
straight by one or more other readers and steal the next object from
them. This could actually make the queue empty and then we would get a
'Error in SharedQueue synchronization' in #next.

Perhaps we should remove #nextOrNil: altogether and rely on #peek

Hrmph, this class is full of fleas! :-)

regards, Göran

More information about the Squeak-dev mailing list