[concurrency-interest] transferring queued threads

tom strickland mr.tom.strickland at gmail.com
Thu Apr 16 08:42:36 EDT 2009

Thanks Endre, Christian for your replies and I'm sorry that I've been late
in replying.

Perhaps I should have been more explicit in my original scenario. It may be
that I'm too close to the problem to see an obvious solution, but I don't
think that the proposed solution will work.

Here's a more detailed description of the problem:
This is a communications system in which 2 parties can be in a communication
session with each other - think of it as an IM session or a phone call.

Alice and Bob are in a call.
Alice and Carol are also in a call.
Alice's calls are being coordinated by a service. One function offered by
this service is "transfer", whereby the service hooks Bob and Carol together
and drops Alice out of the loop.

These calls have moderately complex state machines that are guarded by
locks. Triggers can come into these state machines from either end of a call
and must acquire the lock to protect memory state and to prevent races on
the state machines.
Each user has a state machine for their side of the call and each call has
its own higher-level state machine. To simplify modelling, the two users and
call operate under a single lock, so that a trigger into one user's state
machine flows across the call and state machines atomically, without having
to worry about races from other triggers.

My problem is this:
Alice and Bob have a call that is protected by a single lock L(B)
Alice and Carol have a call that is protected by a single lock L(C)
We need to end up with Bob and Carol in a call without running into a
deadlock between the two locks.

If I switch both calls to having to acquire both locks, in order, perhaps
there is a race.
Let's say that the transfer trigger comes in and acquires L(B). The system
realises that this is a transfer and acquires L(C) so that it has control of
both calls locks and thus can be sure that nothing else will race over the
state machines. After this, all triggers to the call Alice-Bob will have to
acquire locks L(B) and L(C) in that order. Similarly, all triggers to
Alice-Carol will have to acquire both locks, in the same order. The problem
is that there is a race in which a thread can start to wait for L(C) while
this changeover is happening and be left waiting for L(C) without knowing
that it should have acquired L(B) first.
Sequence for two threads, labelled tB and tC:
tB   transfer trigger comes in
tB   acquire L(B)
tB   acquire L(C)
tC   trigger arrives, starts waiting for L(C)
tB   sets Alice-Carol call to need to acquire both L(B) and L(C) from now on
tB   does stuff to set off the transfer and then releases L(C) and L(B)
tC   acquires L(C), but has not acquired L(B)

Again, I have some thoughts on how to solve this, but I'm worried that I'm
missing the point or overcomplicating matters in the statement of my
problem. Am I missing something obvious?



2009/4/14 Endre Stølsvik <Online at stolsvik.com>

> On Mon, Apr 6, 2009 at 21:00, Christian Vest Hansen
> <karmazilla at gmail.com> wrote:
> > Have a lock for each entity; L(A), L(B), L(C) etc. such that each
> > entity at any given point in time has exactly one lock. These locks
> > have a universal and immutable ordering to them (like
> > System.identityHashCode, for instance).
> System.identityHashCode can give you the same result for two different
> objects, and you'd not be guaranteed a single order on the two
> different threads. Use a long sequencer (in addition!).
> Endre.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20090416/aa7869b8/attachment.html>

More information about the Concurrency-interest mailing list