Tuesday, March 22, 2011

Problem with Peterson's mutual exclusion algorithm on multi-core

This is my Java program for mutual exclusion using Peterson's algorithm. This algorithm can works effectively on single-core machines but it turns wrong when running on multi-core systems. The reason is that multi-core processors re-order instructions for improving performance. In this example, mutual exclusion might be violated because the reordering between 2 instructions "in[id] = true;" and "turn = other();".

/* Prove: Peterson algorithm for mutual exclusion does not work for multi-processor
Precondition: 2 threads updating a shared variable "sum" in the critical region, sum = 0
Postcondition: sum = 2
However, sum can be 0 or 1 or 2.
*/

public class Peterson implements Runnable {

private static boolean[] in = { false, false };
private static volatile int turn = -1;
private static volatile int sum=0;
public static void main(String[] args) {
new Thread(new Peterson(0), "Thread - 0").start();
new Thread(new Peterson(1), "Thread - 1").start();
System.out.println(sum); //expected 2
}

private final int id;

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

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

@Override
public void run() {
for (int i=0;i < 1; i++)
{
in[id] = true;
turn = other();
while (in[other()] && turn == other()) {
//System.out.println("[" + id + "] - Waiting...");
}

sum++;

in[id] = false;
}
}
}

Below is my experimental result running on a 48-core machine.

Number of runs: 1 000 000
sum=0: 116556
sum=1: 882538
sum=2: 906

As we can see, our expected result (sum=2) only only holds in 906 runs (~0.1%).

This problem is known widely in the multi-core community. Mine is just a toy experiment to demonstrate the danger of applying sequential algorithms to solve parallel problems.

Labels: , , ,

0 Comments:

Post a Comment

<< Home