Подтвердить что ты не робот

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

Никто здесь не обеспечил правильную/безопасную реализацию этого алгоритма в Java. Я не уверен, как должно работать John W, так как оно получило недостающие части (а именно, объявления 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. Игнорируя объявления, здесь мы имеем шесть действий:

  • Записать в x
  • A напишите на y
  • Чтение из x
  • Запись в z
  • Чтение из y
  • A напишите в w

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

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

Фактически, поток A может записывать в переменную x, а затем в переменную y, устанавливая связь между этими двумя действиями в потоке A. Однако связь Thread B может читать x и y, и для B можно получить новое значение y до, появится новое значение x. Спектр говорит:

Более конкретно, если два действия делиться случаем-до отношений, они не обязательно должны появляться произошло в этом порядке код, с которым они не происходит-до отношения.

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

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

synchronises-with - это более сильное условие, чем это происходит раньше, и поскольку before-before является транзитивным, если Thread A хочет, чтобы Thread B увидел его записи в x и y, ему просто нужно записать в изменчивый переменная 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 прекратился. T2 может выполнить это путем вызова 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 и обновить их вместо использования логического массива.

Ответ 2

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

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

В частности:

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

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

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

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

Ответ 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;
    }
}

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

Ответ 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
   }
 }

Ответ 5

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