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;
}

Have you considered that you can just be lucky? Just because your code runs correctly once, or even that it runs correctly all the time on your particular machine, doesn't mean that its guaranteed to run correctly all the time. One difference with the Dijkstra lock code is that you're writing to the volatile int `count` in your main loop, which creates a momentary happens-before relationship between threads at every loop iteration (note that you're updating `count` incorrectly , since `count++` is not atomic) — Erwin Bolwidt, Jun 04 '17 at 03:47
@ErwinBolwidt I also thought that code runs correctly can just be lucky, however, I run the code multiple times to confirm this. Without `volatile`,`filterLock` will go into infinite loop very soon after execution which is very different than the situation with `volatile` keyword. I am intended to use `count++` because mutex algorithm (if implemented correctly) can ensure there is only one thread is executing critical section code. — YON, Jun 04 '17 at 04:26

score 1 · Answer 1 · answered Jun 04 '17 at 15:11

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.

answered Jun 04 '17 at 15:11

Assafs

3,257
4
26
39

2

Why is a volatile read so special? The dijkstra lock that the OP posted also uses volatile reads and yet without the `c = c;` trick, it doesn't work. A volatile read by itself has no effect in the Java Memory Model - it only sets up a happens-before relationship between two threads if the volatile read follows a volatile *write* by another thread - **to the array itself**, not to a an element inside it. – Erwin Bolwidt Jun 04 '17 at 16:05
I understand your point. You suggest that a series of volatile reads - since the threads access the array in volatile reads throughout the code - does not force the threads to have any relationship? – Assafs Jun 04 '17 at 16:17
1

not according to the Java Memory Model. The thing is that actual implementations of a JVM may be less strict, so some code may run correctly even if it is not correctly synchronized according to the JMM. But then the next version of the JVM comes along, or Intel provides a nice new feature for parallelization that new JVM's use, and then suddenly code that worked before may start to fail. – Erwin Bolwidt Jun 05 '17 at 01:12

Strange behavior of volatile array

1 Answers1