[concurrency-interest] transferring queued threads

David Holmes davidcholmes at aapt.net.au
Tue Apr 21 10:55:48 EDT 2009


Hi Gregg,

Honestly I'm not too clear on the details here, it just seemed that a
data-lock (ie the lock on an individual object) would not be necessary to
guard the reference to the call-lock, and that it wouldn't anyway because
the attempt to change the call-lock would always have to come through the
same object, which doesn't seem right.

The call-lock is required to guard access to multi-party actions, but I'm
not clear on the exact protocols.

David

> -----Original Message-----
> From: Gregg Wonderly [mailto:gregg at cytetech.com]
> Sent: Wednesday, 22 April 2009 12:28 AM
> To: dholmes at IEEE.org
> Cc: tom strickland; concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] transferring queued threads
>
>
>
> It sounds like the data-lock is being used to manage the
> life-cycle of the
> call-lock.  But, it also sounds like the call can be
> shunted/interrupted/dropped
> at any moment, so it's not clear that there is any predictable
> life-cycle of any
> call.  David, are you seeing this too, and suggesting that the
> data lock is not
> necessary because of this?  It seems that if you just need to
> make sure that
> only one such call exists, that the single object with a single
> lock, is in fact
> okay to me.
>
> Gregg Wonderly
>
> David Holmes wrote:
> > 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.
> >
> >> 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
> >
> >> 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.
> >
> > 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
> >
> >
> > _______________________________________________
> > Concurrency-interest mailing list
> > Concurrency-interest at cs.oswego.edu
> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> >
> >
>




More information about the Concurrency-interest mailing list