How java AtomicReference works under the hood

Question

How java AtomicReference works under the hood? I tried looking over the code but is based on sun.misc.Unsafe so probably another question is how Unsafe works?

Answer 1

Some important elementary facts are as follows. 1> Different threads can only contend for instance and static member variables in the heap space. 2> Volatile read or write are completely atomic and serialized/happens before and only done from memory. By saying this I mean that any read will follow the previous write in memory. And any write will follow the previous read from memory. So any thread working with a volatile will always see the most up-to-date value. AtomicReference uses this property of volatile.

Following are some of the source code of AtomicReference. AtomicReference refers to an object reference. This reference is a volatile member variable in the AtomicReference instance as below.

private volatile V value;

get() simply returns the latest value of the variable (as volatiles do in a "happens before" manner).

public final V get()

Following is the most important method of AtomicReference.

public final boolean  compareAndSet(V expect, V update) {
        return unsafe.compareAndSwapObject(this, valueOffset, expect, update);
}

The compareAndSet(expect,update) method calls the compareAndSwapObject() method of the unsafe class of Java. This method call of unsafe invokes the native call, which invokes a single instruction to the processor. "expect" and "update" each reference an object.

If and only if the AtomicReference instance member variable "value" refers to the same object is referred to by "expect", "update" is assigned to this instance variable now, and "true" is returned. Or else, false is returned. The whole thing is done atomically. No other thread can intercept in between. As this is a single processor operation (magic of modern computer architecture), it's often faster than using a synchronized block. But remember that when multiple variables need to be updated atomically, AtomicReference won't help.

I would like to add a full fledged running code, which can be run in eclipse. It would clear many confusion. Here 22 users (MyTh threads) are trying to book 20 seats. Following is the code snippet followed by the full code.

Code snippet where 22 users are trying to book 20 seats.

for (int i = 0; i < 20; i++) {// 20 seats
            seats.add(new AtomicReference<Integer>());
        }
        Thread[] ths = new Thread[22];// 22 users
        for (int i = 0; i < ths.length; i++) {
            ths[i] = new MyTh(seats, i);
            ths[i].start();
        }

Following is the full running code.

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;

public class Solution {

    static List<AtomicReference<Integer>> seats;// Movie seats numbered as per
                                                // list index

    public static void main(String[] args) throws InterruptedException {
        // TODO Auto-generated method stub
        seats = new ArrayList<>();
        for (int i = 0; i < 20; i++) {// 20 seats
            seats.add(new AtomicReference<Integer>());
        }
        Thread[] ths = new Thread[22];// 22 users
        for (int i = 0; i < ths.length; i++) {
            ths[i] = new MyTh(seats, i);
            ths[i].start();
        }
        for (Thread t : ths) {
            t.join();
        }
        for (AtomicReference<Integer> seat : seats) {
            System.out.print(" " + seat.get());
        }
    }

    /**
     * id is the id of the user
     * 
     * @author sankbane
     *
     */
    static class MyTh extends Thread {// each thread is a user
        static AtomicInteger full = new AtomicInteger(0);
        List<AtomicReference<Integer>> l;//seats
        int id;//id of the users
        int seats;

        public MyTh(List<AtomicReference<Integer>> list, int userId) {
            l = list;
            this.id = userId;
            seats = list.size();
        }

        @Override
        public void run() {
            boolean reserved = false;
            try {
                while (!reserved && full.get() < seats) {
                    Thread.sleep(50);
                    int r = ThreadLocalRandom.current().nextInt(0, seats);// excludes
                                                                            // seats
                                                                            //
                    AtomicReference<Integer> el = l.get(r);
                    reserved = el.compareAndSet(null, id);// null means no user
                                                            // has reserved this
                                                            // seat
                    if (reserved)
                        full.getAndIncrement();
                }
                if (!reserved && full.get() == seats)
                    System.out.println("user " + id + " did not get a seat");
            } catch (InterruptedException ie) {
                // log it
            }
        }
    }

}    

Answer 2

AtomicReference has two fields:-
* value, which is the reference * valueOffset, which is the position of value in bytes from 'this', i.e. the AtomicReference
In compareAndSwap(expected, updated), the object at this-location + valueOffset is compared using == semantics with "expected", and if ==, then updated with "updated".
This is a single hardware instruction, and thus guaranteed to update or fail with false return atomically.
Read Unsafe source code from openJDK.

Answer 3

This is specific to the current implementation and can change but isn't necessarily documents

How java AtomicReference works under the hood

There are two operations. Single read/writes or atomic swaps.

1. Single read/writes are simple volatile loads or stores.
2. The atomic swaps need processor level instructions. The most common implementations are Compare and Swap (CAS) found on sparc-TSO, x86, and ia64 and LL/SC found on arm, ppc and alpha. I am sure there are more that I am missing out but this gives you an idea of the scope.

another question is how Unsafe works?

Unsafe works via native methods leveraging processor instructions.

Sources:

http://gee.cs.oswego.edu/dl/jmm/cookbook.html