[concurrency-interest] transferring queued threads

David Holmes davidcholmes at aapt.net.au
Tue Apr 21 06:13:28 EDT 2009


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
  -----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



      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/20090421/df011cbe/attachment-0001.html>


More information about the Concurrency-interest mailing list