[concurrency-interest] transferring queued threads

tom strickland mr.tom.strickland at gmail.com
Tue Apr 21 10:14:43 EDT 2009


Hi David,

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

> Hi Tom,
> I don't think your protocol is quite right, or perhaps is overly
> complicated:
> > To change a call lock:
> > 1. Acquire the new call lock.
> Ok.
>
> > 2. Get the existing call lock, using the data lock.
> Don't think you need to lock to do this. But the field should probably be
> volatile because it will be protected by different locks at different
> times.


I think I agree that there is probably no need for the data lock: any data
is kept in a data store, which is thread-safe with respect to reads and
writes. The internals of the lock will be thread-safe and so no extra sync
is needed for memory safety.

> 3. Acquire the existing call lock.
> Ok.
>
> > 4. Change the entity's reference to the call-lock to point to the new
>
>    lock, using the data lock.
> Again you don't need a data-lock here, but you do need to check if the
> call-lock you just acquired is still the right call-lock. If not then
> release it and acquire the current call-lock - repeat as necessary
>

OK.


> > 5. Release the old call lock.
> Ok.
>
> > To acquire a call-lock:
> > 1. Get the call lock from the entity's data store, using the data lock.
> > 2. Acquire the call lock.
> > 3. Once acquired, get the call lock again from the entity's data store,
> >     using the data lock.
> > 4. Compare the two values for the lock.
> >   a. If the lock has changed, release the old lock and acquire the new
> >       one.
> >   b. If the lock has not changed, proceed.
>
> Again no need for the data-lock here as far as I can see. AScquire the
> call-lock then check if it is still the call-lock. If not, drop it, repeat
> the process.
>
> The reference to the call-lock is protected by the call-lock itself. But
> this means that you will need an initial call-lock to bootstrap the
> process.


That's great. The bootstrap shouldn't be a problem and this solution seems
straightforward - I understand it and will be able to communicate it to my
colleagues. This is preferable to messing around with AQS!

Thanks,

Tom

David
>
> -----Original Message-----
> From: concurrency-interest-bounces at cs.oswego.edu
> [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of tom
> strickland
> Sent: Tuesday, 21 April 2009 11:28 PM
> To: concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] transferring queued threads
>
>
> Thanks for your replies Christian & David.
> I like the sound of the suggested approach, so if I can summarise to check
> that I've got everything:
>
> The data remains under a data lock per entity that does not change. The
> state machines involved in a call are protected by a call lock, which is
> accessed through the data lock and may change. To change a call lock:
> 1. Acquire the new call lock.
> 2. Get the existing call lock, using the data lock.
> 3. Acquire the existing call lock.
> 4. Change the entity's reference to the call-lock to point to the new lock,
> using the data lock.
> 5. Release the old call lock.
>
> To acquire a call-lock:
> 1. Get the call lock from the entity's data store, using the data lock.
> 2. Acquire the call lock.
> 3. Once acquired, get the call lock again from the entity's data store,
> using the data lock.
> 4. Compare the two values for the lock.
>   a. If the lock has changed, release the old lock and acquire the new one.
>   b. If the lock has not changed, proceed.
>
> The locks will have to be explicit locks, to enable the hand-over-hand
> approach of changeover.
>
> Only Alice can initiate such a change of call-lock and it can only come
> from
> one of Alice's calls at a time, so I am not too worried about two threads
> deadlocking by attempting this simultaneously. To address the points at the
> end of David's comments, only Alice can cause Bob to be shunted off his
> call
> and she cannot deadlock herself. The communicating-this-to-Bob bit is part
> of the communications protocol itself and is straightforward, although it
> would be polite to tell Bob that he was going to be shunted :-)
>
> Thanks,
>
> Tom
>
>
> 2009/4/21 David Holmes <davidcholmes at aapt.net.au>
>
> Tom,
>
> You could use AQS to devise something that waits for two conditions but it
> is non-trivial to say the least. You could also just check to see after
> acquiring a call-lock whether it is still the call-lock as described ie not
> use AQS but just two normal Locks. Requiring you to hold the current
> call-lock to change the call-lock should address race conditions, but you
> may need to ensure you release the local lock before-hand to avoid
> deadlocks.
>
> It really depends on the details of the use cases here - eg who has the
> right to shunt Bob off his call with Alice, and how is this communicated to
> Bob?
>
> David Holmes
>
>
> 2009/4/21 Christian Vest Hansen <karmazilla at gmail.com>
>
> >
>
> > What about this: once a thread changes the call lock, it releases the
> > old one. Then, any thread that acquires the call lock must then
> > immediately check that it is still the current active call lock and if
> > not, it must be released again and the thread must start waiting on
> > the new lock.
>
> -----Original Message-----
> From: tom strickland [mailto:mr.tom.strickland at gmail.com]
> Sent: Monday, 20 April 2009 11:29 PM
> To: dholmes at ieee.org
> Cc: concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] transferring queued threads
>
>
> 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
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20090421/e1fe425e/attachment.html>


More information about the Concurrency-interest mailing list