[concurrency-interest] transferring queued threads

tom strickland mr.tom.strickland at gmail.com
Fri Apr 17 12:11:04 EDT 2009

Wonderful! That's very helpful.

Thanks to everyone for the feedback.


2009/4/16 David Holmes <davidcholmes at aapt.net.au>

>  Hi Tom,
> This kind of scenario does arise whenever you have entities that most of
> the time have to handle their exclusion constraints (locking) independently,
> but then at times have to co-operate to provide atomic operations across
> sets of objects. Acquiring multiple locks is the main way of extending the
> independent use of locks - with ordering to avoid deadlocks.
> What you describe is a little different in that an operation that initially
> needs only a single lock, may turn into an operation that requires multiple
> locks. In that case all I can suggest is that after acquiring l(c) the code
> checks if that was sufficient, and if not it grabs l(b) - perhaps releasing
> l(c) first to maintain ordering.
> It really all depends on interaction between the different actions as to
> how best to partition the locking and what strategies to try and use. I
> don't think you are missing anything obvious.
> Cheers,
> David Holmes
> -----Original Message-----
> *From:* concurrency-interest-bounces at cs.oswego.edu [mailto:
> concurrency-interest-bounces at cs.oswego.edu]*On Behalf Of *tom strickland
> *Sent:* Thursday, 16 April 2009 10:43 PM
> *To:* Endre Stølsvik
> *Cc:* concurrency-interest at cs.oswego.edu
> *Subject:* Re: [concurrency-interest] transferring queued threads
> 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?
> Thanks,
> Tom
> 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/20090417/542e2af1/attachment.html>

More information about the Concurrency-interest mailing list