Mario Frazili Mario Frazili - 1 month ago 20
Java Question

Implement Peterson Lock in Java

I'm trying to implement Peterson's algorithm in Java, and have created the following for the moment

public class Peterson {
private volatile boolean[] flag = new boolean[2];
private volatile int victim;

public void lock(int id)
{
//System.out.println(id);
int i = id;
int j = 1 - id;
flag[i] = true;
victim = i;
while (flag[j] && victim == i) {};
}

public void unlock(int id)
{
flag[id] = false;
}
}


I got the following code to test the lock ...

class Counter {
private int value;

public Counter(int c) {
value = c;
}

public int get()
{
return value;
}

public int getAndIncrement() {
return value++;
}
}


class Thread1 implements Runnable {
private Counter c;
private int id;
private List<Integer> values;
private Peterson lock;

public Thread1(Counter c, int id, List<Integer> values, Peterson l) {
this.c = c;
this.id = id;
this.values = values;
this.lock = l;
}

public void run() {

while (true)
{
lock.lock(id);
try {
try {

if (c.get() > 20000)
return;

int n = c.getAndIncrement();
values.add(n);
} catch (Exception e) {
e.printStackTrace();
}
}
finally {
lock.unlock(id);
}
}
}
}

public class Tmp {

public static void main(String[] args) throws IOException {

Counter c = new Counter(1);
Thread[] t = new Thread[2];
List<Integer> values = new ArrayList<Integer>();
Peterson l = new Peterson();

for (int i = 0; i < t.length; ++i) {
t[i] = new Thread(new Thread1(c, i, values, l));
t[i].start();
}

System.out.println(values.size());
}
}


and although I expect
System.out.println(values.size());
to print
20000
It print on each run different numbers. Why is this? What did I do wrong?

Answer

you don't create a memory barrier when you unlock to guarantee the happens before

add a volatile boolean barr and write true to it in unlock and change the while in the lock to while (barr && flag[j] && victim == i) {};

that and you don't wait on the threads you created

for (int i = 0; i < t.length; ++i)  {
    t[i] = new Thread(new Thread1(c, i, values, l));
    t[i].start();
}

for (int i = 0; i < t.length; ++i)  {
    try{
        t[i].join();
    }catch(InterruptedException e){
        Thread.currentThread().interrupt();//don't expect it but good practice to handle anyway
    }
}