Алгоритм Peterson в Java?
Есть ли реализация в качестве примера алгоритма Peterson для взаимного исключения в Java?
5 ответов
Здесь никто не предоставил правильную / безопасную реализацию этого алгоритма на Java. Я не уверен, как должно работать решение Джона В., поскольку в нем отсутствуют части (а именно объявления ThreadLocals и объяснение того, что должно быть в его массиве - примитивные логические не имеют 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 - Запись в
y - Чтение из
x - Запись в
z - Чтение из
y - Запись в
w
Поскольку все они появляются в одном потоке, JLS сообщает, что эти чтения и записи гарантированно демонстрируют следующий порядок: каждое действие n выше (поскольку действия выполняются в одном потоке) имеет отношение «происходит до» со всеми действиями m , m > n .
А как же разные темы? Для обычного доступа к полям между потоками не устанавливаются отношения «происходит до». Это означает, что поток A может увеличивать общую переменную, а поток B может читать эту переменную, но не видит новое значение . При выполнении программы в JVM распространение записи потока A могло быть переупорядочено так, чтобы происходило после чтения потока B.
Фактически, поток A может писать в переменную x , а затем в переменную y , устанавливая связь «происходит раньше» между этими двумя действиями в потоке A. Но поток B может читать x и y , и B может получить новое значение y перед новым значением x . В спецификации говорится:
Более конкретно, если два действия поделитесь отношениями, которые произошли раньше, они не обязательно должны появляться случиться в таком порядке с любым код, с которым они не разделяют случается до отношений.
Как это исправить? Для обычного доступа к полям достаточно ключевого слова volatile :
Запись в изменчивую переменную (§8.3.1.4) v синхронизируется со всеми последующие чтения v любым потоком (где последующий определяется в соответствии с в порядок синхронизации).
synchronizes-with является более сильным условием, чем произошло-раньше, и, поскольку происходит-раньше, является транзитивным, если поток A хочет, чтобы поток B видел его записи в x и y , ему просто нужно записать в изменчивую переменную z после записи x и y .Поток B должен прочитать из z перед чтением x и y , и он гарантированно увидит новые значения x и и .
В решении Габриэля мы видим такую закономерность: запись происходит в в , которая не будет видна другим потокам, но затем запись происходит в очередь , поэтому другие потоки гарантированно увидят обе записи, пока они сначала читают по очереди .
К сожалению, условие цикла while является обратным: чтобы гарантировать, что поток не видит устаревшие данные для в , цикл while должен читать из сначала поверните :
// ...
while (turn == other() && in[other()]) {
// ...
С этим исправим, большая часть остального решения в порядке: в критическом разделе нас не заботит устаревание данных, потому что, ну, мы находимся в критическом разделе! Единственный другой недостаток проявляется в конце: Runnable устанавливает в [id] на новое значение и завершает работу. Будет ли гарантировано, что другой поток увидит новое значение в [id] ? В спецификации указано «нет»:
Последнее действие в потоке T1. синхронизируется - с любым действием в другой поток T2, который обнаруживает, что T1 закончился. Т2 может выполнить это путем вызова T1.isAlive () или T1.join ().
Так как же это исправить? Просто добавьте еще одну запись в поворот в конце метода:
// ...
in[id] = false;
turn = other();
}
// ...
Поскольку мы изменили порядок цикла while, другой поток гарантированно увидит новое ложное значение в [id] , потому что запись в в [id] происходит - до того, как произойдет запись в поворот - до того, как произойдет чтение из поворота - перед чтением из ] в [id] .
Излишне говорить, что без метрической тонны комментариев этот метод является хрупким, и кто-то может прийти и что-то изменить и незаметно нарушить правильность.Недостаточно просто объявить массив volatile : как объяснил в этом потоке Билл Пью (один из ведущих исследователей модели памяти Java), объявляя энергозависимый массив делает обновления ссылки на массив видимыми для других потоков. Обновления элементов массива не обязательно видимы (отсюда и все циклы, через которые нам пришлось пройти, используя другую переменную volatile для защиты доступа к элементам массива).
Если вы хотите, чтобы ваш код был ясным и кратким, оставьте его таким, какой он есть, и измените в на AtomicIntegerArray (используйте 0 для false, 1 для true; там не является AtomicBooleanArray). Этот класс действует как массив, все элементы которого изменчивы , и поэтому прекрасно решит все наши проблемы. В качестве альтернативы вы можете просто объявить две изменчивые переменные, логическое in0 и логическое in1 , и обновить их вместо использования логического массива.
Если у вас нет особой потребности в агорифме Петерсона (что было бы странно при работе на языке высокого уровня, таком как Java), я предлагаю вам взглянуть на средства синхронизации, встроенные в язык .
Например, в этой книге вы можете найти главу «Условия гонки и Взаимное исключение »в Java полезно: http://java.sun.com/developer/Books/performance2/chap3.pdf
В частности:
Java предоставляет встроенную поддержку ожидая этого «изменения состояния» через понятие условия. Условие это немного неправильное название, однако, потому что это полностью зависит от пользователя действительно ли условие произошел. Кроме того, условие не обязательно быть истинным или ложный. Чтобы использовать условия, необходимо познакомиться с тремя ключевыми методами класса Object:
• wait (): Это используется для ожидания условия. Вызывается, когда в данный момент заблокирован удерживается в течение определенного (общего) объект.
• notify (): этот метод используется для уведомления одного потока о том, что состояние (возможно) изменилось. Опять же, этот метод вызывается, когда замок в настоящее время удерживается на конкретный объект. Только один нить может быть разбужена в результате этот звонок.
• notifyAll (): этот метод используется для уведомления нескольких потоков что условие имеет (возможно) измененный. Все запущенные потоки во время вызова этого метода будет быть уведомленным.
Я не смог найти его в Интернете, поэтому решил попробуйте написать это:
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;
}
}
Не стесняйтесь комментировать, это будет оценено :)
Вам следует ознакомиться с книгой "Искусство программирования для многопроцессорных систем". В ней очень подробно рассматриваются различные реализации блокировок (как спиновых, так и блокирующих). Он также рассматривает различные другие типы параллельных алгоритмов (например, skip list). Вот фрагмент из его книги об алгоритме Peterson Lock
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
}
}
Классы AtomicBoolean и Atomic *, хотя и не являются алгоритмом патерсона, используют для обновления общих данных подход безблокирующих циклов занятости. Они могут соответствовать вашим требованиям.