Saturday, August 15, 2015

Implement AtomicInteger in java



http://gaohow.com/blog/article?id=1
The magic part of atomic data structure is performed by Unsafe, which was born for people who miss C language.
In the implementation of AtomicInteger, Line A gets an Unsafe Object, and Line B get the offset of the variable "value" in its dwelling class AtomicInteger using unsafe.
Keyword "volatile" in Line C makes sure the variable acts like synchronized. It also means every thread needs to read it from memory rather than from its thread cache, and every modification will be flushed into memory immediately.
// setup to use Unsafe.compareAndSwapInt for updates
private static final Unsafe unsafe = Unsafe.getUnsafe();  //Line A
private static final long valueOffset;

static {
    try {
        valueOffset = unsafe.objectFieldOffset
            (AtomicInteger.class.getDeclaredField("value"));  //Line B
    } catch (Exception ex) { throw new Error(ex); }
}

private volatile int value;  //Line C
Unsafe directly works on low level memory storage of the data. The CAS operation of AtomaticInteger is done by Unsafe.compareAndSwapInt.
* Atomically sets the value to the given updated value * if the current value {@code ==} the expected value. public final boolean compareAndSet(int expect, int update) { return unsafe.compareAndSwapInt(this, valueOffset, expect, update); }
Besides compareAndSet, Unsafe has the other two functions with the same purpose compareAndSwapLong, compareAndSwapObject. Theoretically, you can use compareAndSwapObject to implement any data structure.

Access Unsafe

To be safe, Java makes Unsafe unavailable for direct access. If you run the following code you will get an exception.
Unsafe unsafe = Unsafe.getUnsafe();
This reason is in the implementation of getUnsafe.
@CallerSensitive
public static Unsafe getUnsafe() {
    Class var0 = Reflection.getCallerClass();
    if(!VM.isSystemDomainLoader(var0.getClassLoader())) {
        throw new SecurityException("Unsafe");
    } else {
        return theUnsafe;
    }
}
When the JVM is started, three class loaders are used:[3][4]

    Bootstrap class loader
    Extensions class loader
    System class loader

The bootstrap class loader loads the core Java libraries[5] located in the <JAVA_HOME>/jre/lib directory. This class loader, which is part of the core JVM, is written in native code.

The extensions class loader loads the code in the extensions directories (<JAVA_HOME>/jre/lib/ext,[6] or any other directory specified by the java.ext.dirs system property). It is implemented by the sun.misc.Launcher$ExtClassLoader class.

The system class loader loads code found on java.class.path, which maps to the CLASSPATH environment variable. This is implemented by the sun.misc.Launcher$AppClassLoader class.
As our classes is not loaded by bootstrap class loader, so the exception is thrown. However, we can use Reflection to bypass the security mechanism.
Constructor<Unsafe> constructor = Unsafe.class.getDeclaredConstructor();
constructor.setAccessible(true);
Unsafe unsafe = constructor.newInstance();
public class AtomicIntegerArray { private static Unsafe unsafe; private static long BASE; private static long SHIFT; private static int SCALE; //just for demonstration static { try { Constructor<Unsafe> constructor = Unsafe.class.getDeclaredConstructor(); constructor.setAccessible(true); unsafe = constructor.newInstance(); Class<?> k = int[].class; BASE = unsafe.arrayBaseOffset(k); //Line A SCALE = unsafe.arrayIndexScale(k); //Line B SHIFT = 31 - Integer.numberOfLeadingZeros(SCALE); } catch (NoSuchMethodException e) { e.printStackTrace(); } catch (InvocationTargetException e) { e.printStackTrace(); } catch (InstantiationException e) { e.printStackTrace(); } catch (IllegalAccessException e) { e.printStackTrace(); } } private volatile int[] values; public AtomicIntegerArray(int size) { if (size <= 0) { throw new IllegalArgumentException("Array size should be greater than 0."); } values = new int[size]; } public boolean compareAndSet(int index, int expect, int update) { //((long)index << SHIFT) equals index * SCALE return unsafe.compareAndSwapInt(values, ((long)index << SHIFT) + BASE, expect, update); //Line C } public int getAndSet(int index, int v) { return unsafe.getAndSetInt(values, ((long)index << SHIFT) + BASE, v); } public int get(int i) { return values[i]; } @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("["); for (int i: values) { builder.append(i); builder.append(", "); } builder.setLength(builder.length() - 2); builder.append("]"); return builder.toString(); } }
JavaMadeSoEasy.com: Implementation of custom/own AtomicInteger in java
JDK impl: use Unsafe.compareAndSwapInt for updates
public class AtomicInteger extends Number implements java.io.Serializable {
    private static final long serialVersionUID = 6214790243416807050L;

    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
      try {
        valueOffset = unsafe.objectFieldOffset
            (AtomicInteger.class.getDeclaredField("value"));
      } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;
    public AtomicInteger(int initialValue) {
        value = initialValue;
    }
    public AtomicInteger() {
    }
    public final int get() {
        return value;
    }

    public final void set(int newValue) {
        value = newValue;
    }
    public final void lazySet(int newValue) {
        unsafe.putOrderedInt(this, valueOffset, newValue);
    }
    public final int getAndSet(int newValue) {
        for (;;) {
            int current = get();
            if (compareAndSet(current, newValue))
                return current;
        }
    }
    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }

    /**
     * Atomically sets the value to the given updated value
     * if the current value {@code ==} the expected value.
     *
     * <p>May <a href="package-summary.html#Spurious">fail spuriously</a>
     * and does not provide ordering guarantees, so is only rarely an
     * appropriate alternative to {@code compareAndSet}.
     *
     * @param expect the expected value
     * @param update the new value
     * @return true if successful.
     */
    public final boolean weakCompareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }
    public final int getAndIncrement() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return current;
        }
    }
    public final int getAndDecrement() {
        for (;;) {
            int current = get();
            int next = current - 1;
            if (compareAndSet(current, next))
                return current;
        }
    }
    public final int getAndAdd(int delta) {
        for (;;) {
            int current = get();
            int next = current + delta;
            if (compareAndSet(current, next))
                return current;
        }
    }
    public final int incrementAndGet() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return next;
        }
    }
    public final int decrementAndGet() {
        for (;;) {
            int current = get();
            int next = current - 1;
            if (compareAndSet(current, next))
                return next;
        }
    }
    public final int addAndGet(int delta) {
        for (;;) {
            int current = get();
            int next = current + delta;
            if (compareAndSet(current, next))
                return next;
        }
    }

    public int intValue() {
        return get();
    }

    public long longValue() {
        return (long)get();
    }

    public float floatValue() {
        return (float)get();
    }

    public double doubleValue() {
        return (double)get();
    }

}
http://baptiste-wicht.com/posts/2010/09/java-concurrency-atomic-variables.html
public void increment(AtomicInteger integer){
    while(true){
        int current = integer.get();
        int next = current + 1;

        if(integer.compareAndSet(current, next)){
            return;
        }
    }
}
This seems to be complicated, but this is the cost of non-blocking algorithms. When we detect collision, we retry until the operation succeeded. This is the common schema for non-blocking algorithms.


X. Use synchronized
class AtomicIntegerCustom{
   int currentValue;
   int previousValue;
  
   //AtomicintCustom constructors >
   /**
   * Creates a new AtomicInteger and is initialized to 0.
   */
   public AtomicIntegerCustom(){
          currentValue=0;
   }
  
   /**
   * Creates a new AtomicIntegerCustom and is initialized to specified initialValue.
   * @param initialValue
   */
   public AtomicIntegerCustom(int initialValue){
          currentValue=initialValue;
   }
  
   //AtomicIntegerCustom  important Methods >
   /**
   * method returns the current value
   *
   */
   public synchronized int get(){
          return currentValue;
   }
  
   /**
   * Sets to newValue.
   */
   public synchronized void set(int newValue){
          currentValue=newValue;
   }
  
   /**
   * Sets to newValue and returns the old value.
   */
   public synchronized int getAndSet(int newValue){
          previousValue=currentValue;
          currentValue=newValue;
          return previousValue;
   }
  
   /**
   * Compare with expect, if equal, set to update and return true.
   */
   public synchronized boolean compareAndSet(int expect, int update){
          if(currentValue == expect){
                 currentValue=update;
                 return true;
          }
          else
                 return false;
   }
  
   //Addition methods >
   /**
   * adds value to the current value. And return updated value.
   */
   public synchronized int addAndGet(int value){
          return currentValue+=value;
   }
  
   /**
   * increments current value by 1. And return updated value.
   */
   public synchronized int incrementAndGet(){
          return ++currentValue;
   }
  
   /**
   * Method return current value. And adds value to the current value.
   */
   public synchronized int getAndAdd(int value){
          previousValue=currentValue;
          currentValue+=value;
          return previousValue;
   }
  
   /**
   * Method return current value. And increments current value by 1.
   *
   */
   public synchronized int getAndIncrement(){
          return currentValue++;
   }
  
   //Subtraction methods >
   /**
   * decrements current value by 1. And return updated value.
   */
   public synchronized int decrementAndGet(){
          return --currentValue;
   }
  
   /**
   * Method return current value. And decrements current value by 1.
   */
   public synchronized int getAndDecrement(){
          return currentValue--;
   }
  
   @Override
   public String toString() {
          return "AtomicIntegerCustom = " + currentValue ;
   }  
}

Read full article from JavaMadeSoEasy.com: Implementation of custom/own AtomicInteger in java

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts