<html>
  <head>
    <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    ACK/NAK? I only meant that data packets arrive concurrently, but get
    consumed in order.<br>
    <br>
    You could see NAK as false returned from tryAcquire by the producer,
    but that is not the point. In the original thesis the sequencer is
    used to control access to the receive buffer.<br>
    <br>
    <br>
    Alex<br>
    <br>
    <br>
    <div class="moz-cite-prefix">On 22/12/2014 22:21, DT wrote:<br>
    </div>
    <blockquote
      cite="mid:64849A49-4320-49A5-811F-842B4FA1A5B6@flyingtroika.com"
      type="cite">
      <meta http-equiv="content-type" content="text/html; charset=utf-8">
      <div>I think if the sequencer is used it would mean that both ACK/
        NAK type of responses should be used and sequence has to be
        restarted . Restarting is ok but to deal with both ACK/NAK could
        bring extra complexity during contention.</div>
      <div><br>
      </div>
      <div>Thanks,</div>
      <div>Dmitry<br>
        <br>
        Sent from my iPhone</div>
      <div><br>
        On Dec 18, 2014, at 1:02 PM, Oleksandr Otenko <<a
          moz-do-not-send="true"
          href="mailto:oleksandr.otenko@oracle.com">oleksandr.otenko@oracle.com</a>>
        wrote:<br>
        <br>
      </div>
      <blockquote type="cite">
        <div>
          <meta content="text/html; charset=utf-8"
            http-equiv="Content-Type">
          Yes, no one said it is a good idea to always do that. When it
          is contended, most of the threads will wake up to only go back
          to sleep.<br>
          <br>
          The pattern you are after is usually called sequencer. You can
          see it used in TCP. I am not sure why it wasn't implemented in
          j.u.c. - maybe not that popular.<br>
          <br>
          The best solution will be lock-like, but the waiter nodes will
          contain the value they are waiting for - so only the specific
          threads get woken up. The solution with concurrent map is very
          similar, only with larger overhead from storing the index the
          thread is waiting for.<br>
          <br>
          <br>
          Alex<br>
          <br>
          <br>
          <div class="moz-cite-prefix">On 18/12/2014 20:21, Hanson Char
            wrote:<br>
          </div>
          <blockquote
cite="mid:CABWgujbEz8eZno_0xF_rf2G7=b2LF-7r1qOpa5Ktzt34cCy4-Q@mail.gmail.com"
            type="cite">
            <div dir="ltr">Less overhead and simpler are a nice
              properties, even though at the expense of having to wake
              up all waiting threads just to find out the one with the
              right order to execute.  Still, this seems like a good
              tradeoff.
              <div><br>
              </div>
              <div>Thanks,</div>
              <div>Hanson</div>
            </div>
            <div class="gmail_extra"><br>
              <div class="gmail_quote">On Wed, Dec 17, 2014 at 11:43 PM,
                Peter Levart <span dir="ltr"><<a
                    moz-do-not-send="true"
                    href="mailto:peter.levart@gmail.com" target="_blank">peter.levart@gmail.com</a>></span>
                wrote:
                <blockquote class="gmail_quote" style="margin:0 0 0
                  .8ex;border-left:1px #ccc solid;padding-left:1ex"><span
                    class="">On 12/17/2014 08:15 PM, Oleksandr Otenko
                    wrote:<br>
                    <blockquote class="gmail_quote" style="margin:0 0 0
                      .8ex;border-left:1px #ccc solid;padding-left:1ex">
                      No, there is no difference. Peter didn't spot your
                      entire method is synchronized, so spurious wakeup
                      won't make progress until the owner of the lock
                      exits the method.<br>
                      <br>
                      You could split the synchronization into two
                      blocks - one encompassing the wait loop, the other
                      in the finally block; but it may make no
                      difference.<br>
                      <br>
                      Alex<br>
                    </blockquote>
                    <br>
                  </span> You're right, Alex. I'm so infected with
                  park/unpark virus that I missed that ;-)<br>
                  <br>
                  Peter<br>
                  <br>
                  <blockquote class="gmail_quote" style="margin:0 0 0
                    .8ex;border-left:1px #ccc solid;padding-left:1ex"><span
                      class=""> <br>
                      On 17/12/2014 18:36, suman shil wrote:<br>
                    </span>
                    <blockquote class="gmail_quote" style="margin:0 0 0
                      .8ex;border-left:1px #ccc solid;padding-left:1ex"><span
                        class=""> Thanks peter for your reply. You are
                        right. I should have incremented
                        currentAllowedOrder in finally block.<br>
                        <br>
                        Suman<br>
                      </span>
                      ------------------------------------------------------------------------<br>
                      *From:* Peter Levart <<a moz-do-not-send="true"
                        href="mailto:peter.levart@gmail.com"
                        target="_blank">peter.levart@gmail.com</a>><br>
                      *To:* suman shil <<a moz-do-not-send="true"
                        href="mailto:suman_krec@yahoo.com"
                        target="_blank">suman_krec@yahoo.com</a>>;
                      Oleksandr Otenko <<a moz-do-not-send="true"
                        href="mailto:oleksandr.otenko@oracle.com"
                        target="_blank">oleksandr.otenko@oracle.com</a>>;

                      Concurrency-interest <<a moz-do-not-send="true"
                        href="mailto:concurrency-interest@cs.oswego.edu"
                        target="_blank">concurrency-interest@cs.oswego.edu</a>><br>
                      *Sent:* Wednesday, December 17, 2014 11:54 PM<br>
                      *Subject:* Re: [concurrency-interest] Enforcing
                      ordered execution of critical sections?<span
                        class=""><br>
                        <br>
                        On 12/17/2014 06:46 PM, suman shil wrote:<br>
                        <blockquote class="gmail_quote" style="margin:0
                          0 0 .8ex;border-left:1px #ccc
                          solid;padding-left:1ex"> Thanks for your
                          response. Will notifyAll() instead of notify()
                          solve the problem?<br>
                        </blockquote>
                        <br>
                        It will, but you should also account for
                        "spurious" wake-ups. You should increment
                        currentAllowedOrder only after return from
                        callable.call (in finally block just before
                        notifyAll()).<br>
                        <br>
                        Otherwise a nice solution - with minimal state,
                        providing that not many threads meet at the same
                        time...<br>
                        <br>
                        Regards, Peter<br>
                        <br>
                      </span>
                      <blockquote class="gmail_quote" style="margin:0 0
                        0 .8ex;border-left:1px #ccc
                        solid;padding-left:1ex"> RegardsSuman<br>
                               From: Oleksandr Otenko<<a
                          moz-do-not-send="true"
                          href="mailto:oleksandr.otenko@oracle.com"
                          target="_blank">oleksandr.otenko@oracle.com</a>>

                        <mailto:<a moz-do-not-send="true"
                          href="mailto:oleksandr.otenko@oracle.com"
                          target="_blank">oleksandr.otenko@oracle.com</a>><br>
                          To: suman shil<<a moz-do-not-send="true"
                          href="mailto:suman_krec@yahoo.com"
                          target="_blank">suman_krec@yahoo.com</a>>
                        <mailto:<a moz-do-not-send="true"
                          href="mailto:suman_krec@yahoo.com"
                          target="_blank">suman_krec@yahoo.com</a>>;
                        Concurrency-interest<<a
                          moz-do-not-send="true"
                          href="mailto:concurrency-interest@cs.oswego.edu"
                          target="_blank">concurrency-interest@cs.oswego.edu</a>>

                        <mailto:<a moz-do-not-send="true"
                          href="mailto:concurrency-interest@cs.oswego.edu"
                          target="_blank">concurrency-interest@cs.oswego.edu</a>> 

                          Sent: Wednesday, December 17, 2014 9:55 PM<span
                          class=""><br>
                            Subject: Re: [concurrency-interest]
                          Enforcing ordered execution of critical
                          sections?<br>
                                There is no guarantee you'll ever hand
                          over the control to the right thread upon
                          notify()<br>
                              Alex<br>
                          <br>
                          On 17/12/2014 14:07, suman shil wrote:<br>
                                Hi, Following is my solution to solve
                          this problem. Please let me know if I am
                          missing something.<br>
                             public class OrderedExecutor {  private int
                          currentAllowedOrder = 0;  private int
                          maxLength = 0;  public OrderedExecutor(int n) 
                          {          this.maxLength = n;  } public
                          synchronized Object
                          execCriticalSectionInOrder( int order,
                          Callable<Object> callable)             
                                             throws Exception  { if
                          (order >= maxLength)  {  throw new
                          Exception("Exceeds maximum order "+
                          maxLength);  }    while(order !=
                          currentAllowedOrder)  {  wait();  }    try  {
                          currentAllowedOrder = currentAllowedOrder+1; 
                          return callable.call();  }  finally  { 
                          notify();  }  } }<br>
                             Regards Suman<br>
                        </span>        From: Peter Levart<<a
                          moz-do-not-send="true"
                          href="mailto:peter.levart@gmail.com"
                          target="_blank">peter.levart@gmail.com</a>>
                        <mailto:<a moz-do-not-send="true"
                          href="mailto:peter.levart@gmail.com"
                          target="_blank">peter.levart@gmail.com</a>><br>
                          To: Hanson Char<<a moz-do-not-send="true"
                          href="mailto:hanson.char@gmail.com"
                          target="_blank">hanson.char@gmail.com</a>>
                        <mailto:<a moz-do-not-send="true"
                          href="mailto:hanson.char@gmail.com"
                          target="_blank">hanson.char@gmail.com</a>> 
                          Cc: concurrency-interest<<a
                          moz-do-not-send="true"
                          href="mailto:concurrency-interest@cs.oswego.edu"
                          target="_blank">concurrency-interest@cs.oswego.edu</a>>

                        <mailto:<a moz-do-not-send="true"
                          href="mailto:concurrency-interest@cs.oswego.edu"
                          target="_blank">concurrency-interest@cs.oswego.edu</a>> 

                          Sent: Sunday, December 14, 2014 11:01 PM<span
                          class=""><br>
                            Subject: Re: [concurrency-interest]
                          Enforcing ordered execution of critical
                          sections?<br>
                                    On 12/14/2014 06:11 PM, Hanson Char
                          wrote:<br>
                               Hi Peter,<br>
                             Thanks for this proposed idea of using
                          LockSupport. This begs the question: which one
                          would you choose if you had all three
                          (correct) implementation available? 
                          (Semaphore, CountDownLatch, or LockSupport)?<br>
                             Regards, Hanson<br>
                              The Semaphore/CountDownLatch variants are
                          equivalent if you don't need re-use. So any
                          would do. They lack invalid-use detection.
                          What happens if they are not used as intended?
                          Semaphore variant acts differently than
                          CountDownLatch variant. The low-level variant
                          I  proposed detects invalid usage. So I would
                          probably use this one. But the low level
                          variant is harder to reason about it's
                          correctness. I think it is correct, but you
                          should show it to somebody else to confirm
                          this.<br>
                              Another question is whether you actually
                          need this kind of synchronizer. Maybe if you
                          explained what you are trying to achieve,
                          somebody could have an idea how to do that
                          even more elegantly...<br>
                              Regards, Peter<br>
                        </span>
                        <div>
                          <div class="h5">              On Sun, Dec 14,
                            2014 at 9:01 AM, Peter Levart<<a
                              moz-do-not-send="true"
                              href="mailto:peter.levart@gmail.com"
                              target="_blank">peter.levart@gmail.com</a>>

                            <mailto:<a moz-do-not-send="true"
                              href="mailto:peter.levart@gmail.com"
                              target="_blank">peter.levart@gmail.com</a>> 

                            wrote:<br>
                               Hi Hanson,<br>
                                This one is more low-level, but catches
                            some invalid usages and is more
                            resource-friendly:<br>
                                  public class OrderedExecutor {<br>
                                    public <T> T
                            execCriticalSectionInOrder(<br>
                                      final int order,<br>
                                      final Supplier<T>
                            criticalSection<br>
                                  ) throws InterruptedException {<br>
                                      if (order < 0) {<br>
                                           throw new
                            IllegalArgumentException("'order' should be
                            >= 0");<br>
                                      }<br>
                                      if (order > 0) {<br>
                                          waitForDone(order - 1);<br>
                                      }<br>
                                      try {<br>
                                          return criticalSection.get();<br>
                                      } finally {<br>
                                          notifyDone(order);<br>
                                      }<br>
                                  }<br>
                                    private static final Object DONE =
                            new Object();<br>
                                  private final
                            ConcurrentMap<Integer, Object> signals
                            = new ConcurrentHashMap<>();<br>
                                    private void waitForDone(int order)
                            throws InterruptedException {<br>
                                      Object sig =
                            signals.putIfAbsent(order,
                            Thread.currentThread());<br>
                                      if (sig != null && sig !=
                            DONE) {<br>
                                          throw new
                            IllegalStateException();<br>
                                      }<br>
                                      while (sig != DONE) {<br>
                                          LockSupport.park();<br>
                                          if (Thread.interrupted()) {<br>
                                              throw new
                            InterruptedException();<br>
                                          }<br>
                                          sig = signals.get(order);<br>
                                      }<br>
                                  }<br>
                                    private void notifyDone(int order) {<br>
                                      Object sig =
                            signals.putIfAbsent(order, DONE);<br>
                                      if (sig instanceof Thread) {<br>
                                          if (!signals.replace(order,
                            sig, DONE)) {<br>
                                              throw new
                            IllegalStateException();<br>
                                          }<br>
                                          LockSupport.unpark((Thread)
                            sig);<br>
                                      } else if (sig != null) {<br>
                                          throw new
                            IllegalStateException();<br>
                                      }<br>
                                  }<br>
                              }<br>
                                  Regards, Peter<br>
                                On 12/14/2014 05:08 PM, Peter Levart
                            wrote:<br>
                                   On 12/14/2014 04:20 PM, Hanson Char
                            wrote:<br>
                                 Hi Peter,<br>
                               Thanks for the suggestion, and sorry
                            about not being clear about one important 
                            detail: "n" is not known a priori when
                            constructing an OrderedExecutor.  Does this
                            mean the use of CountDownLatch is ruled out?<br>
                                If you know at least the upper bound of
                            'n', it can be used with such 'n'. Otherwise
                            something that dynamically re-sizes the
                            array could be devised. Or you could simply
                            use a ConcurrentHashMap instead of array
                            where keys are 'order' values:<br>
                                  public class OrderedExecutor<T>
                            {<br>
                                    private final
                            ConcurrentMap<Integer, CountDownLatch>
                            latches = new ConcurrentHashMap<>();<br>
                                    public T
                            execCriticalSectionInOrder(final int order,<br>
                                                                     
                            final Supplier<T> criticalSection)
                            throws InterruptedException {<br>
                                      if (order > 0) {<br>
                                          latches.computeIfAbsent(order
                            - 1, o -> new CountDownLatch(1)).await();<br>
                                      }<br>
                                      try {<br>
                                          return criticalSection.get();<br>
                                      } finally {<br>
                                          latches.computeIfAbsent(order,
                            o -> new CountDownLatch(1)).countDown();<br>
                                      }<br>
                                  }<br>
                              }<br>
                                  Regards, Peter<br>
                                      You guessed right: it's a one-shot
                            object for a particular OrderedExecutor 
                            instance, and "order" must be called indeed
                            at most once.<br>
                               Regards, Hanson<br>
                          </div>
                        </div>
                        <span class="">   On Sun, Dec 14, 2014 at 2:21
                          AM, Peter Levart<<a moz-do-not-send="true"
                            href="mailto:peter.levart@gmail.com"
                            target="_blank">peter.levart@gmail.com</a>>

                          <mailto:<a moz-do-not-send="true"
                            href="mailto:peter.levart@gmail.com"
                            target="_blank">peter.levart@gmail.com</a>> 

                          wrote:<br>
                             Hi Hanson,<br>
                              I don't think anything like that readily
                          exists  in java.lang.concurrent, but what you
                          describe should be possible to  achieve with
                          composition of existing primitives.  You
                          haven't given any additional hints to what
                          your OrderedExecutor  should behave like.
                          Should it be a one-shot object (like
                          CountDownLatch) or a re-usable one (like
                          CyclicBarrier)? Will
                          execCriticalSectionInOrder() for a particular
                          OrderedExecutor instance and 'order' value be
                          called at most once? If yes (and I think that
                          only a one-shot object  makes sense here), an
                          array of CountDownLatch(es) could be used:<br>
                              public class OrderedExecutor<T> {<br>
                                private final CountDownLatch[] latches;<br>
                                  public OrderedExecutor(int n) {<br>
                                    if (n < 1) throw new
                          IllegalArgumentException("'n'  should be >=
                          1");<br>
                                    latches = new CountDownLatch[n - 1];<br>
                                    for (int i = 0; i <
                          latches.length; i++) {<br>
                                        latches[i] = new
                          CountDownLatch(1);<br>
                                    }<br>
                                }<br>
                                  public T
                          execCriticalSectionInOrder(final int order,<br>
                                                                   
                           final Supplier<T> criticalSection)
                          throws InterruptedException {<br>
                                    if (order < 0 || order >
                          latches.length)<br>
                                        throw new
                          IllegalArgumentException("'order' should be
                          [0..." +  latches.length + "]");<br>
                                    if (order > 0) {<br>
                                        latches[order - 1].await();<br>
                                    }<br>
                                    try {<br>
                                        return criticalSection.get();<br>
                                    } finally {<br>
                                        if (order < latches.length) {<br>
                                            latches[order].countDown();<br>
                                        }<br>
                                    }<br>
                                }<br>
                            }<br>
                                Regards, Peter<br>
                              On 12/14/2014 05:26 AM, Hanson Char wrote:<br>
                        </span>         Hi, I am looking for a construct
                        that can  be used to efficiently enforce 
                        ordered execution of multiple critical sections,
                        each calling from a  different thread. The
                        calling threads may run in  parallel and may
                        call the execution method out of order. The 
                        perceived construct would therefore be
                        responsible for re-ordering the execution of
                        those threads, so that their critical  sections
                        (and only the critical section) will be executed
                        in order. Would something  like the following
                        API already exist? /** * Used to enforce ordered
                        execution of critical sections calling from
                        multiple *  threads, parking and unparking the 
                        threads as necessary. */ public class
                        OrderedExecutor<T> { /** * Executes a
                        critical section at most once with the given
                        order, parking * and  unparking the current
                        thread as  necessary so that all critical *
                        sections executed  by different threads using
                        this  executor take place in * the order from 1
                        to n  consecutively. */ public T
                        execCriticalSectionInOrder<br>
                        (  final int order, final Callable<T>
                        criticalSection) throws InterruptedException; }
                        Regards, Hanson
                        _______________________________________________Concurrency-interest
                        mailing <a moz-do-not-send="true"
                          href="mailto:listConcurrency-interest@cs.oswego.edu"
                          target="_blank">listConcurrency-interest@cs.oswego.edu</a>
                        <mailto:<a moz-do-not-send="true"
                          href="mailto:Concurrency-interest@cs.oswego.edu"
                          target="_blank">Concurrency-interest@cs.oswego.edu</a>>

                        <a moz-do-not-send="true"
                          href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest"
                          target="_blank">http://cs.oswego.edu/mailman/listinfo/concurrency-interest</a>
                        _______________________________________________<br>
                          Concurrency-interest mailing list<br>
                          <a moz-do-not-send="true"
                          href="mailto:Concurrency-interest@cs.oswego.edu"
                          target="_blank">Concurrency-interest@cs.oswego.edu</a>
                        <mailto:<a moz-do-not-send="true"
                          href="mailto:Concurrency-interest@cs.oswego.edu"
                          target="_blank">Concurrency-interest@cs.oswego.edu</a>><span
                          class=""><br>
                            <a moz-do-not-send="true"
                            href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest"
                            target="_blank">http://cs.oswego.edu/mailman/listinfo/concurrency-interest</a><br>
_______________________________________________<br>
                          Concurrency-interest mailing list<br>
                        </span><a moz-do-not-send="true"
                          href="mailto:Concurrency-interest@cs.oswego.edu"
                          target="_blank">Concurrency-interest@cs.oswego.edu</a>
                        <mailto:<a moz-do-not-send="true"
                          href="mailto:Concurrency-interest@cs.oswego.edu"
                          target="_blank">Concurrency-interest@cs.oswego.edu</a>><span
                          class=""><br>
                          <a moz-do-not-send="true"
                            href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest"
                            target="_blank">http://cs.oswego.edu/mailman/listinfo/concurrency-interest</a><br>
                          <br>
                          <br>
                          <br>
                          <br>
                          <br>
_______________________________________________<br>
                          Concurrency-interest mailing list<br>
                        </span><a moz-do-not-send="true"
                          href="mailto:Concurrency-interest@cs.oswego.edu"
                          target="_blank">Concurrency-interest@cs.oswego.edu</a>
                        <mailto:<a moz-do-not-send="true"
                          href="mailto:Concurrency-interest@cs.oswego.edu"
                          target="_blank">Concurrency-interest@cs.oswego.edu</a>><br>
                        <a moz-do-not-send="true"
                          href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest"
                          target="_blank">http://cs.oswego.edu/mailman/listinfo/concurrency-interest</a><br>
                      </blockquote>
                      <br>
                      <br>
                      <br>
                    </blockquote>
                    <br>
                    <br>
                  </blockquote>
                  <div class="HOEnZb">
                    <div class="h5"> <br>
                      _______________________________________________<br>
                      Concurrency-interest mailing list<br>
                      <a moz-do-not-send="true"
                        href="mailto:Concurrency-interest@cs.oswego.edu"
                        target="_blank">Concurrency-interest@cs.oswego.edu</a><br>
                      <a moz-do-not-send="true"
                        href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest"
                        target="_blank">http://cs.oswego.edu/mailman/listinfo/concurrency-interest</a><br>
                    </div>
                  </div>
                </blockquote>
              </div>
            </div>
          </blockquote>
          <br>
        </div>
      </blockquote>
      <blockquote type="cite">
        <div><span>_______________________________________________</span><br>
          <span>Concurrency-interest mailing list</span><br>
          <span><a moz-do-not-send="true"
              href="mailto:Concurrency-interest@cs.oswego.edu">Concurrency-interest@cs.oswego.edu</a></span><br>
          <span><a moz-do-not-send="true"
              href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest">http://cs.oswego.edu/mailman/listinfo/concurrency-interest</a></span><br>
        </div>
      </blockquote>
    </blockquote>
    <br>
  </body>
</html>