gc and synchronization, Weak Array..

Peter Smet peter.smet at flinders.edu.au
Mon May 10 23:32:53 UTC 1999


Bob,

Thanks for this very detailed reply. Very helpful stuff - I've added some
comments below


On Mon, 10 May 1999 09:22:36 +0930 "Peter Smet" <peter.smet at flinders.edu.au>
wrote:
>10 May Peter Smet gc and synchronization, Weak Array..
>
>
>The disadvantage of publish subscribe is that you must explicitly
deregister
>objects from the mechanism for them to be garbage collected.
>I have tried to get around this by using  weakKeyDictionaries to hold both
>the publishers and the subscribers. If there are no remaining references to
>either the publisher or the subscriber, these will be garbage collected,
and
>no events will be passed to these deceased objects.

Well, that depends on the meaning of "deceased". There will be some window
of time between the last strong reference to an object disappearing and the
next GC which will finalize that object out of existence. During that
interval, you could access the weakly-held key and send a message to it when
it probably no longer has any real interest in said message. That's just
part of the package and hopefully such objects will not react adversely
(other than wasting some processor cycles).


That problem I can live with - not having to worry about explicit
deallocation is a tradeoff for some
"dead" objects getting events they are no longer interested in.....

>
>The problem is that any key in a WKDict can be garbage collected and
>set to nil, by the gc thread. Naturally, this can break just about any code
>accessing the WKDict.

I'm not sure what needs to break. Checking for <nil> should avoid such
problems (see example further down).


  I probably should have put some more context to the problem. There is in
effect a two dimensional
 array of WKDicts. The first has the publishers as its keys. Each of its
values holds a WKDict holding
 as its keys all the subscribers for that particular publisher. The
subscriber dict links to further structs like
  events keys, and messages to send. You get the idea....   So I can test
the publishers
  dict by - publishers at: thisObject. Then follows a bunch of methods, each
digging deeper into
  the data structure, and finally sending a message to the intended
receiver. While these messages
 are executing the publisher or the subscriber key can dissapear from its
dictionary.
  The problem may also be that in my threading tests, the WKDicts are
getting an incoming stream of new  Objects with no strong references, so the
arrays are continually being resized. Perhaps the problems
  are due to array resizing during concurrent access.

>
>To guard against the gc, WKDicts are held by class WeakArray. It looks like
>this class will warn each WKDict if one or more of it's keys are set to
nil.
>How
>is this done? I think WeakArray is warned of a loss by the VM, via the
>Finalization Semaphore. Is this right? WeakArray waits on the Finalization
>Semaphore but never signals it - so I guess the VM does the signalling?

Right. One clue to figuring this out is to observe how FinalizationSemaphore
is initialized:

FinalizationSemaphore := Smalltalk specialObjectsArray at: 42.

the "specialObjectsArray" contains those objects that the VM needs to know
about. If you look at ObjectMemory>>finalizeReference:, you will see where
this starts and you can follow it from there.

self signalFinalization: oop

leads to:

signalFinalization: weakReferenceOop
"If it is not there already, record the given semaphore index in the list of
semaphores to be signaled at the next convenient moment. Set the
interruptCheckCounter to zero to force a real interrupt check as soon as
possible."

interruptCheckCounter _ 0.
pendingFinalizationSignals _ pendingFinalizationSignals + 1.

and in Interpreter>>checkForInterrupts, we see:

"signal any pending finalizations"
pendingFinalizationSignals > 0 ifTrue:[
sema _ self splObj: TheFinalizationSemaphore.
(self fetchClassOf: sema) = (self splObj: ClassSemaphore)
ifTrue:[self synchronousSignal: sema].
pendingFinalizationSignals _ 0.
].

where the special object 41 (counting from 0, 42 if you start at 1) is
signalled.

>So in essence, one must guarantee that any WKDict instance will not
>receive any messages immediately after Finalization Semaphore signals,
>and it's finalizeValues method is invoked. It seems to me that any
>message that is part of a process with higher priority than the
>finalizationProcess
>in class WeakArray will break this guarantee. Random synchronization
>problems will occur.
>
>This is a tough nut to crack. Should all methods in WKDict be mutually
>exclusive? That way, no method can conflict with a call to finalizeValues.
>This is just as dangerous, since putting 'finalizeValues' into a blocking
>wait state (because another method in WKDict has been invoked)
>will still not prevent the gc from setting any one of the Dict's keys to
>nil....
>
>The thread problems can be reduced to this:
>Any complex procedure in WKD must be run atomically, but
>you must respond immediately to the FinalizationSemaphore by
>invoking finalizeValues. You cannot respond immediately if
>you are running complex procedures atomically.

I don't think that one must necessarily "respond immediately to the
FinalizationSemaphore". If the user of the WKD can tolerate a key of nil,
then I'm not sure there is any need for immediacy here. Let's suppose you
have a WKD representing the subscribers to a particular event. The keys
would be the subscribers (weakly-held) and the values would be the action(s)
to be taken. If the event were triggered, then something like the following
would happen:

subscriberWKD keysDo: [ :k | k ifNotNil: [k doWhateverWith: (subscriberWKD
at: k)]].

You may see a *lot* of nil keys here, but you can just ignore these. You may
also see some keys which are no longer strongly-held elsewhere. These will
be collected in the next GC, but for now they still exist and you will just
send them a notification since you cannot tell if they are in the
soon-to-be-collected category. So, I don't see any particular urgency to
#finalizeValues for the WKD.


    I guess then it comes down to, "well, how long do I have?". The problem
with threads is that you can
    test for a condition like notNil, but you are not guaranteed that the
condition will hold while you execute
    your conditional code (particularly if the conditional code is long,
complex, or itself has semaphore
    wait states). Betrand Meyer, the creator of Eiffel, had exactly this
problem while trying to integrate
    preCondition clauses with concurrency. Someone may put the gc in a
higher priority thread, or simply
    make it more efficient, and suddenly your code no longer works. Dolphin
Smalltalk even has methods
    where a weak reference is made temporarily strong (with the "beStrong"
selector) to avoid the
    above mentioned problem......

So, if there is not a problem with finalization being delayed a bit, then
making the the methods accessing a WKD exclusive with the finalization would
seem like a good idea. Such protection is a good idea whenever multiple
processes at different priorities may access the same data. Remember: the
Collection protocol is not advertised to be process-safe. One way to
accomplish this would be to put a Semaphore in an instance variable in
WeakKeyDictionary (or perhaps in a subclass, ProcessSafeWeakKeyDictionary)
and use this for *all* accesses, including finalization. Another way, again
in a subclass, would be to no-op the #finalizeValues method and instead rely
on the normal accesses to do the same thing periodically (say every nth time
#at:put: #add:, etc are sent). You could tweak "n" to trade-off wasted space
in the dictionary vs. processor time to clean it up.


    I think the way to go is to make synchronization wrappers. That way, all
dicts, identityDicts, and WKDicts      can be made process safe at the same
time, since they implement the same protocol.

>I looked at Class WeakRegistry to see how it deals with these problems,
>but I suspect it has the same problems with threads and the gc....

WeakRegistry is the only user of WeakKeyDictionary (the instance variable
'valueDictionary') in the base image and all references to this variable are
protected, so the only conflict would be with the finalization of this WKD
which doesn't use the same protection. See above.

>Any insights into making WKDict process-safe greatly appreciated...
>
>Peter
>

Cheers,
Bob


Thanks for these helpful comments. I will keep hacking, put in some tests
for nil, and let you know how I get on...


Peter





More information about the Squeak-dev mailing list