[concurrency-interest] transferring queued threads

tom strickland mr.tom.strickland at gmail.com
Mon Apr 20 09:29:12 EDT 2009


After more thought, I thought I'd ask if I could just shift threads from
lock-to-lock, as follows:

Each entity has its own data lock that does not change. It also has a second
"call" lock that can change. Thus, a call from Alice that turns into a call
between Alice and Bob will use a single call lock. All traffic between Alice
and Bob uses this lock to all serialise operations on the state machines for
Alice, Bob and their call. If Bob is to be shunted into a different call
with Carol, then a new lock will be created for that call. The problem is
that there may be races here. So, could the following approach work and what
would be the best starting point for implementing it?

1. Any thread that has acquired a call lock will be allowed to proceed to
completion. To change the call lock, a thread must first acquire it.
2. Any thread that is waiting to acquire the call lock (because it is
already owned by another thread) is essentially waiting for one of two
conditions:
   a. the lock has been acquired by the waiting thread
   b. the lock has changed and the waiting thread must go and wait on this
new changed lock

This seems feasible to me, but I am unsure of how to wait for two
conditions. Is this a situation where the AbstractQueuedSynchronizer would
prove useful? I don't think that I've missed anything subtle, but this
approach is using one lock to get/set the value of the current lock (a data
lock) and a separate lock, that may change, to coordinate actions and I
could easily have missed something.

Thanks,

Tom

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/20090420/df750c28/attachment.html>


More information about the Concurrency-interest mailing list