[concurrency-interest] Composite compare-and-swap based on two values

David Holmes davidcholmes at aapt.net.au
Tue Sep 6 06:51:20 EDT 2011


You can not compose CAS operations to get atomic updates to multiple variables. A DCAS would solve your problem but we don't have one :) AtomicStampedReference (as mentioned by Daniel) is a very restricted form of DCAS and in fact is implemented by locking in the JDK.

You either need a mutual exclusion mechanism that is applied to all variables (eg locking), or you need a protocol that allows optimistic updates and can account for conflicts/contention. Or you encode both variables into a single atomic variable.

I must admit though that I don't really understand the semantics of your reset() operation, and I'm unclear why the value and the boundary can be modified independently.

David Holmes

  -----Original Message-----
  From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Oleksiy Khilkevich
  Sent: Tuesday, 6 September 2011 8:14 PM
  To: Concurrency-interest at cs.oswego.edu
  Subject: [concurrency-interest] Composite compare-and-swap based on twovalues


  Hi Concurrency Champs


  I'm implementing non-blocking cyclic counter mostly for learning purposes, and faced the following problem, which i'm not sure how to solve.


  The method in question implements the following 


      /**
       * Sets counter value to initial (boundary) value
       * @return true if counter value was changed
       */
      boolean reset();


  The implementation I'm not sure about


      @Override
      public boolean reset() {
          for (;;) {
              int curValue = value.get();
              int curBoundary = boundary.get();
              if (curValue == curBoundary) return false;


              // TODO: if boundary and value were not changed, set the value to boundary


              return true;
          }
      }


  Here I have two values which are both AtomicIntegers and which may change - value can be incremented or decremented by another thread, and boundary can be changed too. 


  I'm not quite sure how to do this without introducing critical sections. In general the question refers to any shared state change based on values of several other shared states.


  What is the correct way to implement such operation atomically without critical sections? IS it possible to build composite CAS operations based on AtomicInteger#compareAndSet ?


  Thank you and kindly waiting for your ideas
  Oleksiy

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20110906/46befdb2/attachment-0001.html>


More information about the Concurrency-interest mailing list