[concurrency-interest] transferring queued threads

tom strickland mr.tom.strickland at gmail.com
Tue Apr 21 13:11:01 EDT 2009


Hi Greg, David,
We do need a data lock elsewhere, but we do not need it here. It was a
mistake to use it in the first place. We need a data lock to ensure safe
publication of mutable objects in the data store (which is really a
session). The data store's get/set/remove operations are thread-safe and so
a data lock is not needed to access immutable objects or objects whose
internal values are thread-safe, such as an explicit lock from j.u.c.

As for the call-locks and changing them: calls exist in sets of calls. A
call must always have a lock and that lock may change. Calls exist in sets
and a call's lock can only be changed by another call in that set. At a
given point in time, only one call in the set may do this, so there should
be no no chance of deadlock and no need for any additional protection.

Thanks,

Tom

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

> 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
> > >
> > >
> >
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20090421/84d381ac/attachment-0001.html>


More information about the Concurrency-interest mailing list