[concurrency-interest] Concurrent Bidirectional Map

Martin Buchholz martinrb at google.com
Mon Nov 23 00:28:58 EST 2009


On Sun, Nov 22, 2009 at 20:25, Norman Elton <normelton at gmail.com> wrote:
>> Suppose
>> thread 1 is trying to set k -> v1
>> while
>> thread 2 is trying to set k -> v2
>>
>> Because the updates of the two maps are independent,
>> and you can't control the scheduler, there is a risk of
>> ending up with
>> k -> v1
>> in the first map, and
>> v2 -> k
>> in the reverse map
>> in the quiescent state.
>
> I've synchronized the put() methods in both directions back to a
> single lock object, so one thread would block while the other
> completes its update. Correct me if I'm wrong, this is definitely my
> knowledge of the inner workings synchronization starts to get fuzzy.

OK, I think you're mostly fine.
An observer might be able to see an "impossible"
sequence, but users are unlikely to care.

E.g. Perhaps it's an invariant that some key is
only ever modified by having its value incremented,
perhaps by calls to replace(key, value, value+1).
but another thread can observe apparent violations
of monotonicity
k -> 0
k -> 1
reverse map 0 -> k

Martin


More information about the Concurrency-interest mailing list