Dijkstra's 1965 mutual exclusion algorithm in Java

Dijkstra1965.java

import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * Mutual exclusion without locks, as first discovered by Dijkstra in 1965.
 *
 * <p>The code is so strange because the point of this class is to not use any
 * of the synchronisation primitives nor any of the concurrency utilities in the
 * library.
 *
 * @see "Solution of a problem in concurrent programming control" by EW
 *         Dijkstra, Communications of the ACM 8, Number 9 (September, 1965).
 */
public class Dijkstra1965 {
    private static final int NCOMPUTERS = 8;

    /**
     * A "computer" in Dijkstra's terms, that is, for our purposes, code
     * that requires access to the critical section, run in a separate thread.
     * Also contains the shared (global) state that makes coordination possible.
     */
    private static class Computer implements Runnable {
        /**
         * The "critical section" is this {@code Runnable}. We use it to verify
         * that the mutual exclusion property always holds.
         */
        private static final Runnable criticalSection = new Runnable() {
            // This lock only used to verify the mutual exclusion property.
            private final Lock lock = new ReentrantLock();
            private long count;

            @Override
            public void run() {
                if (lock.tryLock()) {
                    try {
                        if ((++count % 100L) == 0L) {
                            System.out.printf(
                                    "%d times inside critical section (%s)%n",
                                    count, Thread.currentThread().getName());
                        }
                        Thread.yield();
                    } finally {
                        lock.unlock();
                    }
                } else {
                    throw new IllegalStateException("mutex violation");
                }
            }
        };

        private static volatile boolean[] spinning = new boolean[NCOMPUTERS];
        private static volatile boolean[] ready = new boolean[NCOMPUTERS];

        // The initial value of "k" is, in Dijkstra's words, "immaterial".
        private static volatile int candidate =
                ThreadLocalRandom.current().nextInt(NCOMPUTERS);

        private final int id;

        private Computer(int id) {
            this.id = id;
        }

        @Override
        public void run() {
            // The self-assignment statements in the code below are *critical*.
            // Declaring an array "volatile" only makes the array reference
            // volatile, not the array elements. That is why each write to an
            // array element is followed by a self-assignment to the volatile
            // array reference: that way only can we be sure
            // happens-before/synchronisation properties of the updated array
            // element are as we expect. (Normally AtomicXxxArray would be used
            // to obtain volatile semantics for array elements.)
            spin:
            while (true) {
                spinning[id] = true;
                spinning = spinning;

                while (candidate != id) {
                    ready[id] = false;
                    ready = ready;
                    if (!spinning[candidate]) {
                        candidate = id;
                    }
                }

                ready[id] = true;
                ready = ready;
                for (int i = 0; i < ready.length; i++) {
                    if (i != id && ready[i]) {
                        continue spin;
                    }
                }

                // Critical section is only run by one computer at a time.
                criticalSection.run();

                ready[id] = false;
                ready = ready;
                spinning[id] = false;
                spinning = spinning;
            }
        }
    }

    /** Main method, spins indefinitely. */
    public static void main(String[] args) {
        for (int i = 0; i < NCOMPUTERS; i++) {
            new Thread(new Computer(i)).start();
        }
    }
}