Peterson algorithm in Java?

Question

Is there example implementation of Peterson algorithm for mutual exclusion in Java?

Answer 1

No one here has provided a correct/safe implementation of this algorithm in Java. I'm not sure how John W's solution is supposed to work since it's got pieces missing (namely the declarations of the ThreadLocals and an explanation of what is supposed to be in his array—primitive booleans don't have get() and set()).

Chapter 17 of the Java Language Specification explains the Java memory model. Of particular interest is Section 17.4.5, which describes the happens-before order. It's pretty easy to think about within a single thread. Consider the snippet:

int x, y, z, w;
x = 0;
y = 5;

z = x;
w = y;

Everyone will agree that at the end of this snippet, both x and z are equal to 0 and both y and w are equal to 5. Ignoring the declarations, we have six actions here:

1. A write to x
2. A write to y
3. A read from x
4. A write to z
5. A read from y
6. A write to w

Because they all appear in the same thread, the JLS says that these reads and writes are guaranteed to exhibit this ordering: each action n above (because the actions are in a single thread) has a happens-before relationship with all actions m, m > n.

But what about different threads? For normal field accesses, there are no happens-before relationships established between threads. This means a Thread A could increment a shared variable and Thread B might read that variable but not see the new value. In the program's execution in the JVM, the propagation of Thread A's write may have been reordered to happen after Thread B's read.

In fact, Thread A could write to a variable x, and then to a variable y, establishing a happens-before relationship between those two actions within Thread A. But Thread B may read x and y and it is legal for B to get the new value of y before the new value of x appears. The spec says:

More specifically, if two actions share a happens-before relationship, they do not necessarily have to appear to have happened in that order to any code with which they do not share a happens-before relationship.

How do we fix this? For normal field accesses, the volatile keyword is enough:

A write to a volatile variable (§8.3.1.4) v synchronizes-with all subsequent reads of v by any thread (where subsequent is defined according to the synchronization order).

synchronizes-with is a stronger condition than happens-before, and since happens-before is transitive, if Thread A wants Thread B to see its writes to x and y, it just needs to write to a volatile variable z after writing x and y. Thread B needs to read from z before reading x and y and it will be guaranteed to see the new values of x and y.

In Gabriel's solution, we see this pattern: a write occurs to in, which would not be visible to other threads, but then a write occurs to turn, so other threads are guaranteed to see both writes as long as they read turn first.

Unfortunately, the while loop's conditional is backwards: to guarantee a thread does not see stale data for in, the while loop should read from turn first:

    // ...
    while (turn == other() && in[other()]) {
        // ...

With this fix in mind, most of the rest of the solution is ok: in the critical section, we don't care about staleness of data because, well, we're in the critical section! The only other flaw comes at the end: the Runnable sets in[id] to a new value and exits. Will the other Thread be guaranteed to see the new value of in[id]? The spec says no:

The final action in a thread T1 synchronizes-with any action in another thread T2 that detects that T1 has terminated. T2 may accomplish this by calling T1.isAlive() or T1.join().

So how do we fix it? Just add another write to turn at the end of the method:

    // ...
    in[id] = false;
    turn = other();
}
// ...

Since we reordered the while loop, the other thread will be guaranteed to see the new false value of in[id] because the write to in[id] happens-before the write to turn happens-before the read from turn happens-before the read from in[id].

Needless to say, without a metric ton of comments, this method is brittle and someone could come along and change something and subtly break the correctness. Just declaring the array volatile is not good enough: as explained in this thread by Bill Pugh (one of the lead researchers for the Java memory model), declaring an array volatile makes updates to the array reference visible to other threads. Updates to array elements are not necessarily visible (hence all the loops we just had to jump through by using another volatile variable to guard access to the array elements).

If you want your code to be clear and concise, keep it the way it is and change in to be an AtomicIntegerArray (use 0 for false, 1 for true; there is no AtomicBooleanArray). This class acts like an array whose elements are all volatile, and so will solve all our problems nicely. Alternatively, you could just declare two volatile variables, boolean in0 and boolean in1, and update them instead of using a boolean array.

Answer 2

Unless you have some specific need for Peterson's agorithm (which would be strange when working in a high level language like Java), I suggest you take a look at the synchronization facilities built in to the language.

For example, you may find this book chapter on "Race Conditions and Mutual Exclusion" in Java useful: http://java.sun.com/developer/Books/performance2/chap3.pdf

In particlar:

Java provides built-in support awaiting this “change in state” via the notion of a condition. A condition is a bit of a misnomer, however, because it is entirely up to the user whether or not a condition actually occurred. Furthermore, a condition need not be specifically true or false. To use conditions, one must become familiar with three key methods of the Object class:

• wait(): This method is used to await a condition. It is called when a lock is presently being held for a particular (shared) object.

• notify(): This method is used to notify a single thread that a condition has (possibly) changed. Again, this method is called when a lock is presently being held for a particular object. Only a single thread can be awakened as a result of this call.

• notifyAll(): This method is used to notify multiple threads that a condition has (possibly) changed. All threads that are running at the time this method is called will be notified.

Answer 3

I could not find one on the web myself, so I decided to try writing it:

public class Peterson implements Runnable {

    private static boolean[] in = { false, false };
    private static volatile int turn = -1;

    public static void main(String[] args) {
        new Thread(new Peterson(0), "Thread - 0").start();
        new Thread(new Peterson(1), "Thread - 1").start();
    }

    private final int id;

    public Peterson(int i) {
        id = i;
    }

    private int other() {
        return id == 0 ? 1 : 0;
    }

    @Override
    public void run() {
        in[id] = true;
        turn = other();
        while (in[other()] && turn == other()) {
            System.out.println("[" + id + "] - Waiting...");
        }
        System.out.println("[" + id + "] - Working ("
                + ((!in[other()]) ? "other done" : "my turn") + ")");
        in[id] = false;
    }
}

Feel free to comment, it will be appreciated:)

Answer 4

You should really check out the book The Art of Multiprocessor Programming. He in great detail goes over different lock implementations (both spin, and blocking). He also goes over different other types of concurrent algorithms (skip list for instance). Here is a snippet from his book on the Peterson Lock algorithm

Class Peterson implements Lock{
   private final boolean []flag = new boolean[2];
   private volatile int victim;

   public void lock(){
        int i = ThreadID.get(); // ThreadID is a ThreadLocal field
        int j= 1 - i;
        flag[i] = true;    // I'm Interested
        victim = i;        // You go first
        while(flag[j] && victim == i){}; //wait
   }
   public void unlock(){
       int i = ThreadID.get();
       flag[i] = false;      //Not interested anymore
   }
 }

Answer 5

While not the paterson algo, the AtomicBoolean and Atomic* classes use the approach of lockless, busy loops to update shared data. They may suit your requirements.