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

David Holmes davidcholmes at aapt.net.au
Tue Sep 6 17:48:06 EDT 2011


Sorry - yes I was mixing AtomicMarkableReference and AtomicStampedreference. AtomicStampedReference does present itself in a form similar to DCAS.

Good luck.

David
  -----Original Message-----
  From: Oleksiy Khilkevich [mailto:oleksiy.khilkevich at gmail.com]
  Sent: Tuesday, 6 September 2011 10:46 PM
  To: dholmes at ieee.org
  Cc: Concurrency-interest at cs.oswego.edu
  Subject: Re: [concurrency-interest] Composite compare-and-swap based on two values


  I guess you mean AtomicMarkableReference. stamped one indeed provides the versioning that can help - it stores the int as a stamp. I think it's quite possible to emulate DCAS with help of these classes.


  Regarding the reset() i'm just trying to stick to the contract i've imposed on it (so it return true if the counter value was really reset). Without requirement to return change status, i'd not bother at all 


  But surprisingly to provide more information out of reset() i faced this interesting issue. The drawback is the performance drop on reset() due to possible contention, but i expect value to be changed magnitudes more frequently than boundary, so performance should not be a problem.


  TBH, I can't even imagine the practical case when i'd need reset() at all, I am very short on useful and realistic concurrency examples. If anybody has a treasure chest of such examples, I'd be infinitely grateful.


  But since reset() it's there, I now can't ignore it :)


  Oleksiy


  2011/9/6 David Holmes <davidcholmes at aapt.net.au>

    DCAS is double-compare-and-swap. It allows you to atomically check and update two independent memory locations. No current hardware that I know supports it. It makes some lock-free algorithms trivial to implement in theory.

    AtomicStampedReference is a special variant of storing two logical values in one variable, but if I recall correctly the second variable here is limited to 1-bit - a mark or stamp bit. This could be implemented by using the unused address bits to hold the stamp/mark while the variable holds the actual data. But in the JDK it is just doned with locking. Some lock free algorthims are based on having this kind of composite variable.

    But based on your description of the counter and the boundary it isn't clear to me that reset() needs to be atomic, as the boundary or value could change the instant after you set them anyway.

    Cheers,
    David
      -----Original Message-----
      From: Oleksiy Khilkevich [mailto:oleksiy.khilkevich at gmail.com]
      Sent: Tuesday, 6 September 2011 10:07 PM
      To: dholmes at ieee.org; Concurrency-interest at cs.oswego.edu
      Subject: Re: [concurrency-interest] Composite compare-and-swap based on two values


      It just happens on occasion :)


      2011/9/6 Oleksiy Khilkevich <oleksiy.khilkevich at gmail.com>

        Hi David and folks


        2011/9/6 David Holmes <davidcholmes at aapt.net.au>

          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.

        Can you tell in more detail about DCAS concept? Maybe some relevant link? Google is not of much help unfortunately. I'll try to figure AtomicStampedReference in the meantime.

         
          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 thought about encoding the state in a single variable as well, but I was also looking for some general approach to such case. Single-state variable is not very scalable.  

          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.

        The cyclic counter is supposed to incrementally decrease its value from some boundary till zero and set it value again to boundary, in my implementation, the boundary is supposed to be adjustable, so you can increase or decrease counter value space in thread-safe manner. the reset() is supposed to reset the counter value to it's boundary.


        I plan to reuse this interface further to implement work schedulers and few similar things on top of it in my further journey through java.util.concurrent.*


        I've attached the interface so you have an idea about it.


        @Viktor: no, am looking into it, transactional memory is somewhere deep inside my learning backlog :o)

        Thanks for all your answers
        Oleksiy



          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/20110907/aaca6eaf/attachment.html>


More information about the Concurrency-interest mailing list