Strange behavior of volatile array

Question

I know it means the reference to the array is volatile not the items in the array if you declare an array volatile.

I am learning mutex algorithm, so I write some test code:

public class MutualExclusion {
    static final int N = 10;
    static final int M = 100000;

    volatile static int count = 0;

    public static void main(String[] args) {
        Thread[] threads = new Thread[N];
        for (int i = 0; i < N; i++) {
            Thread t = new Worker(i);
            threads[i] = t;
            t.start();
        }
        for (Thread t: threads) {
            try {
                t.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        if (count != N * M) {
            System.out.println("count (" + count + ") != N * M (" + String.valueOf(N * M) + ")");
        }
    }

    static class Worker extends Thread {
        int id;
        Worker(int  id) {
            this.id = id;
        }

        @Override
        public void run() {
            for (int i = 0; i < M; i++) {
                this.lock();
                // critical section
                count++;
                if (i % 1000 == 0) {
                    System.out.println(this.getName() + ": " + count);
                }
                this.unlock();
            }
        }


        void lock() {
            filterLock();
        }

        void unlock() {
            filterUnlock();
        }

        static volatile int level[] = new int[N];
        static volatile int lastToEnter[] = new int[N - 1];

        void filterLock() {
            for (int i = 0; i < (N - 1); i++) {
                level[this.id] = i;
                lastToEnter[i] = this.id;
                outer:
                while (lastToEnter[i] == this.id) {
                    for (int k = 0; k < N; k++ ) {
                        if (k != this.id && level[k] >= i) {
                            continue outer;
                        }
                    }
                    break;
                }
            }
        }

        void filterUnlock() {
            level[this.id] = -1;
        }
    }
}

In my first implementation of filter algorithm, I missed volatile for variable level and lastToEnter, not surprisingly, the program went into a infinite loop. After I added the missing volatile, the program can end as expected.

As I said in beginning, a volatile array doesn't mean items in the array are volatile, so why can the program end as expected after I added the missing volatile?

I asked myself this question when I was implementing another mutex algorithm which still doesn't run correctly after I added volatile keyword. I have to use a trick (Java volatile array?) to make items in the array looks like being volatile: (code below can be pasted into Worker class directly)

volatile static boolean[] b = new boolean[N];
volatile static boolean[] c = new boolean[N];
volatile static int k = 0;

void dijkstraLock() {
    b[this.id] = false;
    outer:
    for (;;) {
        if (k == this.id) {
            c[this.id] = false;

            c = c; // IMPORTANT! the trick

            for (int i = 0; i < N; i++) {
                if (i != this.id && !c[i]) {
                    continue outer;
                }
            }
            break;
        } else {
            c[this.id] = true;
            if (b[k]) {
                k = this.id;
            }
        }
    }
}

void dijkstraUnlock() {
    b[this.id] = true;
    c[this.id] = true;
}

Answer 1

Volatile arrays in Java do not contain volatile elements - but if you access them via the array reference (which is volatile) you will get a volatile read. For instance, in the code above:

static volatile int lastToEnter[] = new int[N - 1];

is a volatile write, whereas

lastToEnter[i] = this.id;

is not. however, the evaluating of the array value - such as:

lastToEnter[i] == this.id

is a volatile read - you first read the reference to the array which is volatile, and only then access the i'th element to evaluate its value.

I suspect this is the reason your execution succeeds once the array is declared as volatile.