<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.2800.1625" name=GENERATOR></HEAD>
<BODY>
<DIV><FONT face="Courier New" color=#0000ff size=2><SPAN 
class=971420510-21042009>Tom,</SPAN></FONT></DIV>
<DIV><FONT face="Courier New" color=#0000ff size=2><SPAN 
class=971420510-21042009></SPAN></FONT>&nbsp;</DIV>
<DIV><FONT face="Courier New" color=#0000ff size=2><SPAN 
class=971420510-21042009>You could use AQS to devise something that waits for 
two conditions but it is non-trivial to say the least. </SPAN></FONT><FONT 
face="Courier New" color=#0000ff size=2><SPAN class=971420510-21042009>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.</SPAN></FONT></DIV>
<DIV><FONT face="Courier New" color=#0000ff size=2><SPAN 
class=971420510-21042009></SPAN></FONT>&nbsp;</DIV>
<DIV><FONT face="Courier New" color=#0000ff size=2><SPAN 
class=971420510-21042009>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?</SPAN></FONT></DIV>
<DIV><FONT face="Courier New" color=#0000ff size=2><SPAN 
class=971420510-21042009></SPAN></FONT>&nbsp;</DIV>
<DIV><FONT face="Courier New" color=#0000ff size=2><SPAN 
class=971420510-21042009>David Holmes</SPAN></FONT></DIV>
<BLOCKQUOTE 
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #0000ff 2px solid">
  <DIV class=OutlookMessageHeader dir=ltr align=left><FONT face=Tahoma 
  size=2>-----Original Message-----<BR><B>From:</B> tom strickland 
  [mailto:mr.tom.strickland@gmail.com]<BR><B>Sent:</B> Monday, 20 April 2009 
  11:29 PM<BR><B>To:</B> dholmes@ieee.org<BR><B>Cc:</B> 
  concurrency-interest@cs.oswego.edu<BR><B>Subject:</B> Re: 
  [concurrency-interest] transferring queued threads<BR><BR></FONT></DIV>After 
  more thought, I thought I'd ask if I could just shift threads from 
  lock-to-lock, as follows:<BR><BR>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?<BR><BR>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.<BR>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:<BR>&nbsp;&nbsp; a. the lock has been acquired by the waiting 
  thread<BR>&nbsp;&nbsp; b. the lock has changed and the waiting thread must go 
  and wait on this new changed lock<BR><BR>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.<BR><BR>Thanks,<BR><BR>Tom<BR><BR>
  <DIV class=gmail_quote>2009/4/16 David Holmes <SPAN dir=ltr>&lt;<A 
  href="mailto:davidcholmes@aapt.net.au">davidcholmes@aapt.net.au</A>&gt;</SPAN><BR>
  <BLOCKQUOTE class=gmail_quote 
  style="PADDING-LEFT: 1ex; MARGIN: 0pt 0pt 0pt 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid">
    <DIV>
    <DIV><FONT face="Courier New" color=#0000ff size=2><SPAN>Hi 
    Tom,</SPAN></FONT></DIV>
    <DIV><FONT face="Courier New" color=#0000ff 
    size=2><SPAN></SPAN></FONT>&nbsp;</DIV>
    <DIV><FONT face="Courier New" color=#0000ff size=2><SPAN>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&nbsp;objects. Acquiring multiple locks is the main way of extending the 
    independent use of locks - with ordering to avoid 
    deadlocks.</SPAN></FONT></DIV>
    <DIV><FONT face="Courier New" color=#0000ff 
    size=2><SPAN></SPAN></FONT>&nbsp;</DIV>
    <DIV><FONT face="Courier New" color=#0000ff size=2><SPAN>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.</SPAN></FONT></DIV>
    <DIV><FONT face="Courier New" color=#0000ff 
    size=2><SPAN></SPAN></FONT>&nbsp;</DIV>
    <DIV><FONT face="Courier New" color=#0000ff size=2><SPAN>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.</SPAN></FONT></DIV>
    <DIV><FONT face="Courier New" color=#0000ff 
    size=2><SPAN></SPAN></FONT>&nbsp;</DIV>
    <DIV><FONT face="Courier New" color=#0000ff 
    size=2><SPAN>Cheers,</SPAN></FONT></DIV>
    <DIV><FONT face="Courier New" color=#0000ff size=2><SPAN>David 
    Holmes</SPAN></FONT></DIV>
    <BLOCKQUOTE 
    style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: rgb(0,0,255) 2px solid">
      <DIV dir=ltr align=left><FONT face=Tahoma size=2>
      <DIV class=im>-----Original Message-----<BR><B>From:</B> <A 
      href="mailto:concurrency-interest-bounces@cs.oswego.edu" 
      target=_blank>concurrency-interest-bounces@cs.oswego.edu</A> [mailto:<A 
      href="mailto:concurrency-interest-bounces@cs.oswego.edu" 
      target=_blank>concurrency-interest-bounces@cs.oswego.edu</A>]<B>On Behalf 
      Of </B>tom strickland<BR><B>Sent:</B> Thursday, 16 April 2009 10:43 
      PM<BR><B>To:</B> Endre Stølsvik<BR><B>Cc:</B> <A 
      href="mailto:concurrency-interest@cs.oswego.edu" 
      target=_blank>concurrency-interest@cs.oswego.edu</A><BR></DIV>
      <DIV class=im><B>Subject:</B> Re: [concurrency-interest] transferring 
      queued threads<BR><BR></DIV></FONT></DIV>
      <DIV>
      <DIV></DIV>
      <DIV class=h5>Thanks Endre, Christian for your replies and I'm sorry that 
      I've been late in replying.<BR><BR>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.<BR><BR>Here's a more detailed description of the 
      problem:<BR>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.<BR><BR>Alice and Bob are in a call.<BR>Alice and Carol are 
      also in a call.<BR>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.<BR><BR>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.<BR>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.<BR><BR>My problem is this:<BR>Alice and Bob have a call that is 
      protected by a single lock L(B)<BR>Alice and Carol have a call that is 
      protected by a single lock L(C)<BR>We need to end up with Bob and Carol in 
      a call without running into a deadlock between the two locks.<BR><BR>If I 
      switch both calls to having to acquire both locks, in order, perhaps there 
      is a race.<BR>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.<BR>Sequence for two threads, labelled tB and tC:<BR>tB&nbsp;&nbsp; 
      transfer trigger comes in<BR>tB&nbsp;&nbsp; acquire L(B)<BR>tB&nbsp;&nbsp; 
      acquire L(C)<BR>tC&nbsp;&nbsp; trigger arrives, starts waiting for 
      L(C)<BR>tB&nbsp;&nbsp; sets Alice-Carol call to need to acquire both L(B) 
      and L(C) from now on<BR>tB&nbsp;&nbsp; does stuff to set off the transfer 
      and then releases L(C) and L(B)<BR>tC&nbsp;&nbsp; acquires L(C), but has 
      not acquired L(B)<BR><BR><BR>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?<BR><BR>Thanks,<BR><BR>Tom<BR><BR><BR>
      <DIV class=gmail_quote>2009/4/14 Endre Stølsvik <SPAN dir=ltr>&lt;<A 
      href="mailto:Online@stolsvik.com" 
      target=_blank>Online@stolsvik.com</A>&gt;</SPAN><BR>
      <BLOCKQUOTE class=gmail_quote 
      style="PADDING-LEFT: 1ex; MARGIN: 0pt 0pt 0pt 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid">
        <DIV>On Mon, Apr 6, 2009 at 21:00, Christian Vest Hansen<BR>&lt;<A 
        href="mailto:karmazilla@gmail.com" 
        target=_blank>karmazilla@gmail.com</A>&gt; wrote:<BR>&gt; Have a lock 
        for each entity; L(A), L(B), L(C) etc. such that each<BR>&gt; entity at 
        any given point in time has exactly one lock. These locks<BR>&gt; have a 
        universal and immutable ordering to them (like<BR>&gt; 
        System.identityHashCode, for 
        instance).<BR><BR></DIV>System.identityHashCode can give you the same 
        result for two different<BR>objects, and you'd not be guaranteed a 
        single order on the two<BR>different threads. Use a long sequencer (in 
        addition!).<BR><FONT 
      color=#888888><BR>Endre.<BR></FONT></BLOCKQUOTE></DIV><BR></DIV></DIV></BLOCKQUOTE></DIV></BLOCKQUOTE></DIV><BR></BLOCKQUOTE></BODY></HTML>