Алгоритм Петерсона в Java?

Question

Есть ли пример реализации алгоритма Петерсона для взаимного исключения в Java?

Answer 1

Никто здесь не предоставил правильную / безопасную реализацию этого алгоритма в Java. Я не уверен, как должно работать решение Джона В., поскольку в нем отсутствуют части (а именно объявления ThreadLocals и объяснение того, что должно быть в его массиве - примитив booleans не имеет get() и set()).

Глава 17 Спецификации языка Java объясняет модель памяти Java. Особый интерес представляет Раздел 17.4.5 , в котором описан порядок произойдет до . Это довольно легко думать в одном потоке. Рассмотрим фрагмент:

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

z = x;
w = y;

Все согласятся, что в конце этого фрагмента и x, и z равны 0, а оба y и w равны 5. Игнорируя декларации, у нас есть шесть действий здесь:

1. A написать x
2. A написать y
3. чтение из x
4. A написать z
5. чтение из y
6. A написать w

Поскольку все они появляются в одном и том же потоке, JLS говорит, что эти операции чтения и записи гарантированно демонстрируют этот порядок: каждое действие n выше (поскольку действия находятся в одном потоке) имеет событие -перед связью со всеми действиями м , м > n .

А как насчет разных тем? Для обычного доступа к полю между потоками не установлено отношений «до того». Это означает, что поток A может увеличивать общую переменную, а поток B может читать эту переменную, но не видит новое значение . При выполнении программы в JVM распространение записи потока A могло быть переупорядочено, чтобы происходить после чтения потока B.

На самом деле поток A может записывать в переменную x, а затем в переменную y, устанавливая отношения между событиями до и после этих двух действий в потоке A. Но поток B может читать x и y, и B может получить новое значение y до того, как появится новое значение x. В спецификации сказано:

Точнее, если два действия делиться отношениями до и они не обязательно должны появляться произошло в таком порядке с любым код, с которым они не разделяют Отношения до того.

Как мы можем это исправить? Для обычного доступа к полю достаточно ключевого слова volatile:

Запись в переменную переменной (§8.3.1.4) v синхронизируется со всеми последующие чтения v любым потоком (где последующее определяется согласно в порядке синхронизации).

синхронизируется с - это более сильное условие, чем происходит раньше, и, поскольку происходит до того, как переходное состояние, если поток А хочет, чтобы поток Б видел свои записи в x и y, он просто необходимо записать в переменную volatile z после записи x и y. Поток B должен прочитать из z перед чтением x и y, и он будет гарантированно видеть новые значения x и y.

В решении Габриэля мы видим такой шаблон: запись происходит в in, которая не будет видна другим потокам, но затем происходит запись в turn, поэтому другие потоки гарантированно будут видеть обе записи как долго как они читают turn сначала.

К сожалению, условие цикла while обратное: чтобы гарантировать, что поток не видит устаревшие данные для in, цикл while должен прочитать сначала из turn:

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

С учетом этого исправления большая часть остального решения в порядке: в критическом разделе мы не заботимся о устаревании данных, потому что мы в критическом разделе! Единственный другой недостаток в конце: Runnable устанавливает in[id] на новое значение и завершает работу. Будет ли гарантированно другой поток видеть новое значение in[id]? Спецификация говорит нет:

Последнее действие в потоке T1 синхронизируется с любым действием в другой поток T2, который обнаруживает, что T1 часкак прекращено. Т2 может выполнить это путем вызова T1.isAlive () или T1.join ().

Так как нам это исправить? Просто добавьте еще одну запись в turn в конце метода:

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

Поскольку мы переупорядочили цикл while, другой поток гарантированно увидит новое ложное значение in[id], потому что запись в in[id] происходит - до записи в turn - до чтения из turn происходит - до чтения с in[id].

Само собой разумеется, без метрики тонна комментариев, этот метод является хрупким, и кто-то может прийти и изменить что-то и слегка нарушить правильность. Просто объявить массив volatile недостаточно: как объяснил в этой теме Билл Пью (один из ведущих исследователей для модели памяти Java), объявив массив volatile делает обновления массива ссылкой видимыми для других потоков. Обновления элементов массива не обязательно видны (следовательно, все циклы, через которые нам пришлось пройти, используя другую переменную volatile для защиты доступа к элементам массива).

Если вы хотите, чтобы ваш код был четким и лаконичным, оставьте его таким, какой он есть, и измените in на AtomicIntegerArray (используйте 0 для false, 1 для true; AtomicBooleanArray нет) , Этот класс действует как массив, все элементы которого volatile, и поэтому хорошо решит все наши проблемы. В качестве альтернативы, вы можете просто объявить две переменные переменной boolean in0 и boolean in1 и обновить их вместо использования логического массива.

Answer 2

Если у вас нет особой потребности в агорифме Петерсона (что было бы странно при работе на языке высокого уровня, таком как Java), я предлагаю вам взглянуть на средства синхронизации, встроенные в язык.

Например, вы можете найти эту главу книги "Условия гонки и Взаимное исключение "в Java полезно: http://java.sun.com/developer/Books/performance2/chap3.pdf

В частности:

Java обеспечивает встроенную поддержку в ожидании этого «изменения в состоянии» через понятие условия. Условие немного неправильный, однако, потому что это полностью зависит от пользователя действительно ли условие на самом деле произошло. Кроме того, условие не должно быть конкретно правдой или ложный. Чтобы использовать условия, нужно познакомиться с тремя ключевыми методами Класс объекта:

• wait (): это Метод используется для ожидания условия. Вызывается, когда в данный момент блокировка удерживается для определенного (общего) объект.

• notify (): этот метод используется для уведомления одного потока, что состояние (возможно) изменилось. Опять же, этот метод вызывается, когда замок в настоящее время удерживается конкретный объект. Только один поток может быть разбужен в результате этот звонок.

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

Answer 3

Я не смог найти его в Интернете, поэтому решил попробовать написать:

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

Не стесняйтесь комментировать, это будет оценено :)

Answer 4

Вы действительно должны почитать книгу Искусство многопроцессорного программирования. Он очень подробно рассматривает различные реализации блокировки (как вращения, так и блокировки). Он также рассматривает различные другие типы параллельных алгоритмов (например, список пропусков). Вот фрагмент из его книги об алгоритме Питерсона Лока

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

Хотя это и не алгоритм Патерсона, классы AtomicBoolean и Atomic * используют подход циклов занятости без блокировки для обновления общих данных.Они могут удовлетворить ваши требования.