Реализовать Петерсон Лок в Java - PullRequest
Новая
       29

Реализовать Петерсон Лок в Java

3 голосов
/ 24 августа 2011

Я пытаюсь реализовать алгоритм Петерсона в Java и на данный момент создал следующее: 

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

Я получил следующий код для проверки блокировки ... 

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

и хотя я ожидаю, что System.out.println(values.size()); напечатает 20000 На каждом прогоне печатаются разные числа.Почему это?Что я сделал не так?

Ответы [ 4 ]

1 голос
/ 24 августа 2011

вы не создаете барьер памяти при разблокировке, чтобы гарантировать, что произойдет до

добавьте volatile boolean barr и напишите true в нем для разблокировки и измените время нахождения в замке на while (barr && flag[j] && victim == i) {};

это, и вы не ждете на темы, которые вы создали 

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
    }
}
0 голосов
/ 20 октября 2016

Это не работает, потому что вы сделали ссылку на массив изменчивой, а не содержимое (как уже указывалось). Но вы всегда можете обернуть изменяемое поле в классе и создать массив этого.

0 голосов
/ 24 августа 2011

Как отмечали другие ребята, у Java нет изменчивого чтения / записи для элементов массива.

Вы можете использовать AtomicIntegerArray с get() и set() с изменчивыми эффектами.

0 голосов
/ 24 августа 2011

Полагаю, это потому, что метод lock() в классе Lock не является атомарным. В частности, этот код изменяет два адреса памяти и затем проверяет состояние, используя оба из них без блокировки: 

public void lock(int id)
{
    ...
    flag[i] = true;
    victim = i;
    while (flag[j] && victim == i) {};
}

Будет ли алгоритм работать, если два потока чередуются при выполнении 

    flag[i] = true;
    victim = i;

Во-вторых, потому что private volatile boolean[] flag = new boolean[2] помечает ссылку на массив как переменную, а не содержимое массива.

...