• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Compare And Swap Implementation

 
Ranch Hand
Posts: 595
6
jQuery Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

I am trying to understanding the simplest working of compare and swap mechanism.

I have written a small code for this:

Does this represent the actual working of CAS, or is there anything essential that I am missing?
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

s ravi chandran wrote:
Does this represent the actual working of CAS, or is there anything essential that I am missing?



Well... you did implement a method that does "compare and swap", so, I guess you implemented CAS.... but...

Anyway, in general, when discussing CAS operations, it is based on the CAS instruction provided by the processor. The "S" in CAS could either mean "set" or "swap", but no matter, as either can be used to build upon. This instruction is atomic, across all processors/cores, and deals with the processor caches too.  With Java, access to the underlying processor's CAS instruction is provided by the Atomic variable support, in the java.util.concurrent.atomic package. And provided as compare and set.


So... Yes, you did implement "compare and swap", but what is the context here? Most engineering discussions around CAS are related to the processor / atomic / optimistic programming nature of it -- and not just a method that does a compare and swap.

Henry
 
s ravi chandran
Ranch Hand
Posts: 595
6
jQuery Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, my focus was to understand basic working on CAS. It does provide great use case for lock free design.

Do the atomic collections do something at low level ( OS/machine level)  to provide the same functionality?
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

s ravi chandran wrote:Well, my focus was to understand basic working on CAS. It does provide great use case for lock free design.



Oh... If the goal is lock free design, then "no", you did not implement CAS. Your method isn't atomic. Your method isn't thread safe. And of course, can't be used as the basis for a lock free algorithm.

Henry
 
s ravi chandran
Ranch Hand
Posts: 595
6
jQuery Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for the response.

What all are the criteria for a lock free CAS design?

If I synchronize it, then it would loose the actual requirement.

Using volatile field would work?
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
As already mentioned, the atomic classes that are in the java.util.concurrent.atomic package, does this for you. It is implemented to access the CAS instruction of the underlying processor, and used to protect volatile variables. With these classes, you should have the CAS functionality that you need to build a lock free algorithm.

Henry
 
s ravi chandran
Ranch Hand
Posts: 595
6
jQuery Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks. I will check the implementations for CAS in atomic package.
 
s ravi chandran
Ranch Hand
Posts: 595
6
jQuery Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here is the method I found in AtomicInteger class.

From my own experience of using off heap objects, I get that here we are using Unsafe to access direct memory location. given the offset value for any datatype, we directly match it with expected value and then overwrite the value with new update.

So, here accessing and matching of memory is the main difference between my code and actual java implementation. Did I get that right?
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

s ravi chandran wrote:
So, here accessing and matching of memory is the main difference between my code and actual java implementation. Did I get that right?



The core Java library, will eventually make a native method call, which in turn calls C/assembly code that executes the CAS instruction. This processor instruction is guaranteed to be atomic, across all processors/cores, and deal with memory and processor caches.

Your code, is pure Java, and simply compiles to Java byte codes... At runtime, regardless of interpretation or JIT compilation, it doesn't do the CAS instruction.  It isn't atomic. It isn't thread safe. etc.

Henry
 
s ravi chandran
Ranch Hand
Posts: 595
6
jQuery Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks. I got the logic behind this concept.
 
reply
    Bookmark Topic Watch Topic
  • New Topic