Java concurrency in practice: non-blocking synchronization

Previously we discussed the opportunities to synchronize our thread modifying the shared resource using locks. But we also have a non-blocking way to solve some cases (not all of them to be honest). And it could work much more effective than locks. Let’s discover the non-blocking synchronization approach.

Compare-and-Swap algorithm

The Compare-and-Swap (CAS) algorithm is a fundamental technique used in concurrent programming and multi-threaded applications to perform atomic updates on shared variables. It works under the hood of all the Atomic abstractions in java.

The basic idea behind CAS is to perform the following steps atomically:

1. Read the current value of a shared variable.
2. Compare it to an expected value.
3. If the current value matches the expected value, update the variable with a new value.
4. If the current value doesn’t match the expected value, do nothing or retry the operation.

Example from jdk:

public final int getAndAddInt(Object o, long offset, int delta) {
    int v;
    do {
        v = getIntVolatile(o, offset);
    } while (!weakCompareAndSetInt(o, offset, v, v + delta));
    return v;
}

History

Java 1.5 (2004):

The introduction of the java.util.concurrent package brought significant enhancements to Java's concurrency support. This release included the first set of atomic classes, such as AtomicInteger, AtomicLong, and AtomicReference, which provided atomic operations on basic data types.

Java 9 (2017)
New methods were added to the Atomic types. For example: weakCompareAndSetPlain , compareAndExchange , compareAndExchangeAcquire…

Functionality

AtomicBoolean:

AtomicBoolean: Provides atomic operations for boolean variables. Interesting fact: the internal type of Atomic Boolean stored in the volotile int field. This is because int is the smallest type CAS operations can be implemented across different machine types.

get(): Returns the current value of the AtomicBoolean as a boolean.

set(boolean newValue): Sets the value of the AtomicBoolean to the specified newValue.

getAndSet(boolean newValue): Sets the value of the AtomicBoolean to the specified newValue and returns the previous value.

compareAndSet(boolean expect, boolean update): Atomically compares the current value of the AtomicBoolean with the expect value. If they match, it updates the value to update. The method returns true if the update was successful, indicating that the value was changed; otherwise, it returns false.

NOTE: the class other methods such as weakCompareAndSetPlain but they are out of scope our CAS operations and have more rare use cases.

Example:

import java.util.concurrent.atomic.AtomicBoolean;

public class AtomicBooleanExample {
    public static void main(String[] args) {
        AtomicBoolean flag = new AtomicBoolean(true);

        // Reading the value
        boolean currentFlag = flag.get();
        System.out.println("Current Flag: " + currentFlag);

        // Updating the value
        flag.set(false);
        System.out.println("Updated Flag: " + flag.get());

        // Compare and set
        boolean success = flag.compareAndSet(false, true);
        System.out.println("Compare and Set Success: " + success);
        System.out.println("Updated Flag: " + flag.get());

        // Get and Set (returns the previous value)
        boolean previousValue = flag.getAndSet(false);
        System.out.println("Previous Value: " + previousValue);
        System.out.println("Updated Flag: " + flag.get());
    }
}

AtomicInteger:

AtomicInteger: Provides atomic operations for int variables. Has the same methods as AtomicBooean plus:

getAndIncrement(): Atomically increments the current value by 1 and returns the previous value.

getAndDecrement(): Atomically decrements the current value by 1 and returns the previous value.

getAndAdd(int delta): Atomically adds the specified delta to the current value and returns the previous value.

incrementAndGet(): Atomically increments the current value by 1 and returns the updated value.

decrementAndGet(): Atomically decrements the current value by 1 and returns the updated value.

addAndGet(int delta): Atomically adds the specified delta to the current value and returns the updated value.

getAndAccumulate(int x, IntBinaryOperator accumulatorFunction): Atomically applies the specified accumulator function to the current value and the x value. Returns the previous value before the accumulation.

accumulateAndGet(int x, IntBinaryOperator accumulatorFunction): Atomically applies the specified accumulator function to the current value and the x value. Returns the updated value after the accumulation.

Example:

import java.util.concurrent.atomic.AtomicInteger;

public class AtomicIntegerExample {
    public static void main(String[] args) {
        AtomicInteger atomicInt = new AtomicInteger(0);

        // Increment by 1
        int incrementedValue = atomicInt.incrementAndGet();
        System.out.println("Incremented: " + incrementedValue);

        // Decrement by 1
        int decrementedValue = atomicInt.decrementAndGet();
        System.out.println("Decremented: " + decrementedValue);

        // Add a specific value
        int addedValue = atomicInt.addAndGet(10);
        System.out.println("Added: " + addedValue);

        // Compare and set
        boolean compareAndSetResult = atomicInt.compareAndSet(10, 20);
        System.out.println("Compare and Set Result: " + compareAndSetResult);
        System.out.println("Updated Value: " + atomicInt.get());

        // Get and set
        int previousValue = atomicInt.getAndSet(5);
        System.out.println("Previous Value: " + previousValue);
        System.out.println("Updated Value: " + atomicInt.get());


        // Define an accumulator function that multiplies the current value by the operand
        IntBinaryOperator accumulator = (currentValue, operand) -> currentValue * operand;

        // Using getAndAccumulate to multiply the current value by 5
        int previousValue = atomicInt.getAndAccumulate(5, accumulator);
        System.out.println("Previous Value: " + previousValue);
        System.out.println("Updated Value: " + atomicInt.get());

        // Using accumulateAndGet to multiply the current value by 3
        int updatedValue = atomicInt.accumulateAndGet(3, accumulator);
        System.out.println("Updated Value: " + updatedValue);
    }
}

AtomicIntegerArray:

AtomicIntegerArray: Provides atomic operations for arrays of int variables. It has the same methods as AtomicInteger but has an “index” in its signature. You can not change the size of the array after the AtomicIntegerArray was created.

Example:

public class AtomicIntegerArrayExample {
    public static void main(String[] args) {
        final int arrayLength = 5;
        AtomicIntegerArray atomicIntArray = new AtomicIntegerArray(arrayLength);

        Runnable incrementTask = () -> {
            for (int i = 0; i < arrayLength; i++) {
                int previousValue = atomicIntArray.getAndIncrement(i);
                System.out.println("Incremented index " + i + ": " + previousValue + " to " + (previousValue + 1));
            }
        };

        Thread thread1 = new Thread(incrementTask);
        Thread thread2 = new Thread(incrementTask);

        thread1.start();
        thread2.start();

        try {
            thread1.join();
            thread2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("Final Array: " + atomicIntArray.toString());
    }
}

AtomicLong and AtomicLongArray:

AtomicLong: Provides atomic operations for long variables. AtomicLongArray: Provides atomic operations for arrays of long variables. The implementation in the same as for atomic integer so no need to explain them one more time.

AtomicReference:

AtomicReference: Provides atomic operations for reference variables. It has the same methods as atomic boolean, but provides us ability to make atomic operations on our own class.

Example:

import java.util.concurrent.atomic.AtomicReference;

class Person {
    private String name;

    public Person(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

public class AtomicReferenceExample {
    public static void main(String[] args) {
        AtomicReference<Person> atomicPerson = new AtomicReference<>(new Person("Alice"));

        // Get the current person
        Person currentPerson = atomicPerson.get();
        System.out.println("Current Person: " + currentPerson.getName());

        // Set a new person atomically
        atomicPerson.set(new Person("Bob"));
        System.out.println("Updated Person: " + atomicPerson.get().getName());

        // Compare and set a new person if the current person is Alice
        boolean success = atomicPerson.compareAndSet(new Person("Alice"), new Person("Charlie"));
        System.out.println("Compare and Set Success: " + success);
        System.out.println("Updated Person: " + atomicPerson.get().getName());

        // Get and Set a new person
        Person previousPerson = atomicPerson.getAndSet(new Person("David"));
        System.out.println("Previous Person: " + previousPerson.getName());
        System.out.println("Updated Person: " + atomicPerson.get().getName());
    }
}

AtomicMarkableReference:

• AtomicMarkableReference: Provides atomic operations for markable reference variables. The primary difference between AtomicReference and AtomicMarkableReference is the presence of the “mark” boolean in the latter. Internally it saves a Pair.of(value, mark).

Example:

import java.util.concurrent.atomic.AtomicMarkableReference;

public class AtomicMarkableReferenceExample {
    public static void main(String[] args) {
        AtomicMarkableReference<String> ref = new AtomicMarkableReference<>("Initial", false);

        System.out.println("Current Reference: " + ref.getReference());
        System.out.println("Current Mark: " + ref.isMarked());

        // Set a new reference with a mark
        ref.set("Updated", true);
        System.out.println("Updated Reference: " + ref.getReference());
        System.out.println("Updated Mark: " + ref.isMarked());

        // Compare and set reference and mark
        boolean success = ref.compareAndSet("Updated", "NewValue", true, false);
        System.out.println("Compare and Set Success: " + success);
        System.out.println("Updated Reference: " + ref.getReference());
        System.out.println("Updated Mark: " + ref.isMarked());
    }
}

AtomicStampedReference:

• AtomicStampedReference: Provides atomic operations for stamped reference variables. Same as AtomicMarkableReference but here we have an integer as “additional information” instead of boolean.

Example:

import java.util.concurrent.atomic.AtomicStampedReference;

public class AtomicStampedReferenceExample {
    public static void main(String[] args) {
        AtomicStampedReference<String> ref = new AtomicStampedReference<>("Initial", 0);

        System.out.println("Current Reference: " + ref.getReference());
        System.out.println("Current Stamp: " + ref.getStamp());

        // Set a new reference with a new stamp
        ref.set("Updated", 1);
        System.out.println("Updated Reference: " + ref.getReference());
        System.out.println("Updated Stamp: " + ref.getStamp());

        // Compare and set reference and stamp
        boolean success = ref.compareAndSet("Updated", "NewValue", 1, 2);
        System.out.println("Compare and Set Success: " + success);
        System.out.println("Updated Reference: " + ref.getReference());
        System.out.println("Updated Stamp: " + ref.getStamp());
    }
}

AtomicReferenceArray:

AtomicReferenceArray: Provides atomic operations for arrays of reference variables. The logic is the same as for AtomicIntegerArray and AtomicLongArray

Examples of usage

We will modify our in-memory db from the previous article to provide the same logic in non-blocking manner using Atomic classes.

UserRecord:

public class UserRecord {
    private final AtomicInteger balance = new AtomicInteger();
    //other user fields...

    public void updateBalance(int amount) {

        try {
            int expectedValue = balance.get();
            if (expectedValue + amount < 0) {
                return;
            }

            Thread.sleep(10000);

            while (!this.balance.compareAndSet(expectedValue, expectedValue + amount)) {
                expectedValue = this.balance.get();
                if (expectedValue + amount < 0) {
                    System.out.println("Balance update was ignored");
                    return;
                }
            }
            System.out.println("Actual balance: " + balance.get());
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }

    public int getBalance() {
        return balance.get();
    }
}

So, now we are use Atomic integer to make non-blocking atomic operations on our balance field. The logic stay the same: we check the balance and ignore modification if it less than 0. Then we perform some “time consuming logic” and modify the balance. But now we use compareAndSet method to make a balance change. To prevent parallel modifications we try to change the value until our expected value becomes actual (means no one modified it in parallel thread) and then try to update it if the future balance is going to be positive.

We tried both cases with parallel negative and possitive updates from the previous article. The logs output looks like this:

Accepted connection from /0:0:0:0:0:0:0:1
Accepted connection from /0:0:0:0:0:0:0:1
Actual balance: 15
Actual balance: 30
Accepted connection from /0:0:0:0:0:0:0:1
Accepted connection from /0:0:0:0:0:0:0:1
Actual balance: 15
Actual balance: 0
Accepted connection from /0:0:0:0:0:0:0:1
Actual balance: 15
Accepted connection from /0:0:0:0:0:0:0:1
Accepted connection from /0:0:0:0:0:0:0:1
Actual balance: 0
Balance update was ignored

Let’s take a look at threads:

We can see, that two worker thread “make their work”, the monitoring thread(Thread-0) is running and continuously get the balance. No waitings on monitor, no locks.

Summary:

Atomic types may give us a great opportunity to build efficient, non-blocking synchronization. We should consider the fact, that implementation may become a much more complex, so, in the cases, where locks are not the reason of bad performance — we would suggest to start with more simple and understandable approaches. There is still no drama to use synchronized blocks if they are works for you ;)

Links:

Sources with examples: https://github.com/sIvanovKonstantyn/java-concurrency

Other articles of this series:

Java concurrency in practice: threads

Java concurrency in practice: Executors

Java concurrency in practice: synchronization and locks

Java concurrency in practice: virtual threads