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.
/* 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: multi-core, multi-processor, mutual exclusion, peterson
0 Comments:
Post a Comment
<< Home