XYZ CODE: CasNumberRange.java

CasNumberRange.java

import java.util.Random;
import java.util.concurrent.atomic.*;

/**
 * CasNumberRange
 * <p/>
 * Preserving multivariable invariants using CAS
 */
//ThreadSafe
public class CasNumberRange {
    //Immutable
    private static class IntPair {
        // INVARIANT: lower <= upper
        final int lower;
        final int upper;

        public IntPair(int lower, int upper) {
            this.lower = lower;
            this.upper = upper;
        }
    }

    private final AtomicReference<IntPair> values =
            new AtomicReference<IntPair>(new IntPair(0, 0));

    public int getLower() {
        return values.get().lower;
    }

    public int getUpper() {
        return values.get().upper;
    }

    public void setLower(int i) {
        while (true) {
            IntPair oldv = values.get();
            if (i > oldv.upper)
                throw new IllegalArgumentException("Can't set lower to " + i + " > upper");
            IntPair newv = new IntPair(i, oldv.upper);
            if (values.compareAndSet(oldv, newv))
                return;
            else
                System.out.print("x");
        }
    }

    public void setUpper(int i) {
        while (true) {
            IntPair oldv = values.get();
            if (i < oldv.lower)
                throw new IllegalArgumentException("Can't set upper to " + i + " < lower");
            IntPair newv = new IntPair(oldv.lower, i);
            if (values.compareAndSet(oldv, newv))
                return;
            else
                System.out.print(".");
        }
    }

    public static void main(String[] args) {
        int totalThreads = 10000;
        CasNumberRange cnr = new CasNumberRange();
        Thread[] ts = new Thread[totalThreads];
        Random rd = new Random();
        for(int i = 0; i < totalThreads; i++) {
            int ii = i;
            ts[i] = new Thread(() -> {
                cnr.getUpper();
                cnr.setLower(ii-1);
                try {
                    Thread.sleep(rd.nextInt(500));
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                cnr.getLower();
                cnr.setUpper(ii+1);
            });
        }
        for(int i = 0; i < totalThreads; i++) {
            ts[i].start();
        }
        for(int i = 0; i < totalThreads; i++) {
            try {
                ts[i].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        System.out.println(cnr.getLower() + "," + cnr.getUpper());
    }
}

The CasNumberRange class demonstrates how to use AtomicReference and an immutable data holder (IntPair) to preserve a multi-variable invariant — specifically, ensuring that lower <= upper — in a thread-safe and nonblocking way. Both setLower() and setUpper() methods use a CAS loop to atomically update the shared IntPair reference, checking the invariant before constructing and attempting to swap in a new IntPair. If another thread modifies the value concurrently, the CAS fails, and the operation retries. This technique avoids locking while maintaining consistency across multiple fields. The main method launches 10,000 threads that concurrently read and update the bounds, illustrating the effectiveness and scalability of using CAS to guard compound state invariants without locks.

XYZ CODE

CasNumberRange.java

No comments:

Post a Comment