Hi Torsten,
Torsten Anders writes:
> Dear Kevin,
>
> On 24.05.2006, at 22:41, Kevin Glynn wrote:
> > Torsten Anders writes:
> >> On 24.05.2006, at 20:04, Himanshu Neema wrote
> >>> Let me know if it can be still improved/corrected.
> >>
> >> You may consider making the OrderedDictionary thread-save using a
> >> lock.
> >
> > It should be possible to avoid using locks, e.g. my version used
> > Dictionary.condExchange to make the put routine thread-safe.
>
> Could you please explain why your version (see below your definition of
> Put) is thread-save? You have two stateful operations (one on the
> dictionary one on the counter cell) which are not atomic. Would it not
> be possible to access the OrderedDictionary in a non-consistent state
> between these two operations?
>
It is safe because the first condExchange puts an unbound variable in
the dictionary, any concurrent thread that needs the value will block
until the atomic Cell.exchange generates a sequence number.
> proc {Put D Key Item}
> NewSeq
> _#OldSeq = {Dictionary.condExchange D Key _#unit $ Item#NewSeq}
At this point the dictionary stores Item#<Unbound Var> at position Key
(condExchange is atomic of course). From this point on any operation
that needs Key's sequence number will block on <Unbound Var>.
There are two possibilities, either Key is new (and OldSeq == unit)
or Key was already in the dictionary and OldSeq is the previous
sequence number.
> in
> if OldSeq == unit then NewCounter in
OldSeq may still be unbound if a concurrent thread has just inserted
this entry, but it will eventually be resolved.
> %% Key is new
> {Cell.exchange Counter NewSeq NewCounter} %% or, NewSeq = Counter
> := NewCounter
> NewCounter = NewSeq + 1
Now the thread atomically grabs a unique sequence number and binds it
to the <Unbound Var>.
> else
> NewSeq = OldSeq
> end
> end
>
> Thank you!
>
It would be better to use a read-only variable for NewSeq, and we
could just implement dictionary.condExchange and write put, get,
condGet, exchange on top of it.
Hope that helps
k
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
