Реализация алгоритма взаимного исключения Burns и Lynch в Java: могут ли быть проблемы из-за переупорядочения команд?
Я нашел довольно простой алгоритм взаимного исключения из n-процессов на странице 4 (836) в следующей статье:
"Взаимное исключение с использованием неделимого чтения и записи" Бернса и Линча
program Process_i;
type flag = (down, up);
shared var F : array [1..N] of flag;
var j : 1..N;
begin
while true do begin
1: F[i] := down;
2: remainder; (* remainder region *)
3: F[i] := down;
4: for j := 1 to i-1 do
if F[j] = up then goto 3;
5: F[i] := up;
6: for j := 1 to i-1 do
if F[j] = up then goto 3;
7: for j := i+1 to N do
if F[j] = up then goto 7;
8: critical; (* critical region *)
end
end.
Мне это нравится, потому что его минимальное использование памяти и goto должны позволить мне реализовать его в методе enterCriticalRegion() он возвращает логическое значение, указывающее, удалось ли процессу получить блокировку (т. е. достигла строки 8) или же он нажал один из переходов, и ему нужно повторить попытку позже, а не в ожидании занятости. (Справедливость и голод не являются проблемой в моем случае)
Я попытался реализовать это на Java и протестировать, имея несколько потоков, пытающихся быстро войти в критическую область (выглядит долго, но в основном это комментарии):
import java.util.concurrent.atomic.AtomicInteger;
public class BurnsME {
// Variable to count processes in critical section (for verification)
private static AtomicInteger criticalCount = new AtomicInteger(0);
// shared var F : array [1..N] of flag;
private static final boolean[] F = new boolean[10000];
// Some process-local variables
private final int processID;
private boolean atLine7;
public BurnsME(int processID) {
this.processID = processID;
this.atLine7 = false;
}
/**
* Try to enter critical region.
*
* @return T - success; F - failure, need to try again later
*/
public boolean enterCriticalRegion() {
// Burns Lynch Algorithm
// Mutual Exclusion Using Indivisible Reads and Writes, p. 836
if (!atLine7) {
// 3: F[i] down
F[processID] = false;
// 4: for j:=1 to i-1 do if F[j] = up goto 3
for (int process=0; process<processID; process++)
if (F[process]) return false;
// 5: F[i] = up
F[processID] = true;
// 6: for j:=1 to i-1 do if F[j] = up goto 3
for (int process=0; process<processID; process++)
if (F[process]) return false;
atLine7 = true;
}
// 7: for j:=i+1 to N do if F[j] = up goto 7
for (int process=processID+1; process<F.length; process++)
if (F[process]) return false;
// Verify mutual exclusion
if (criticalCount.incrementAndGet()>1) {
System.err.println("TWO PROCESSES ENTERED CRITICAL SECTION!");
System.exit(1);
}
// 8: critical region
return true;
}
/**
* Leave critical region and allow next process in
*/
public void leaveCriticalRegion() {
// Reset state
atLine7 = false;
criticalCount.decrementAndGet();
// Release critical region lock
// 1: F[i] = down
F[processID] = false;
}
//===============================================================================
// Test Code
private static final int THREADS = 50;
public static void main(String[] args) {
System.out.println("Launching "+THREADS+" threads...");
for (int i=0; i<THREADS; i++) {
final int threadID = i;
new Thread() {
@Override
public void run() {
BurnsME mutex = new BurnsME(threadID);
while (true) {
if (mutex.enterCriticalRegion()) {
System.out.println(threadID+" in critical region");
mutex.leaveCriticalRegion();
}
}
}
}.start();
}
while (true);
}
}
По какой-то причине проверка взаимного исключения (через AtomicInteger) не проходит через несколько секунд, и программа завершает работу с сообщением TWO PROCESSES ENTERED CRITICAL SECTION!,
И алгоритм, и моя реализация настолько просты, что я немного озадачен, почему он не работает.
Что-то не так с алгоритмом Бернса / Линча (сомневаетесь)? Или я где-то совершил глупую ошибку, которую просто не вижу? Или это вызвано переупорядочением инструкций Java? Последнее кажется мне несколько маловероятным, поскольку за каждым заданием следует потенциальный return и, следовательно, не должны меняться местами, нет? Или доступ к массиву в Java не является потокобезопасным?
В сторону:
Вот как я визуализирую алгоритм Бернса и Линча (может помочь обдумать проблему):
Я процесс, и я стою где-то в ряд с другими людьми (процессами). Когда я хочу войти в критический раздел, я делаю следующее:
- 3/4: Я смотрю налево и держу руку внизу, пока кто-то там поднимает руку.
- 5: Если никто слева от меня не поднял руку, я подниму свою
- 6: я снова проверяю, поднял ли кто-нибудь слева от меня свою руку. Если так, я кладу обратно и начинаю заново. В противном случае, я держу руку вверх.
- 7: Все справа от меня идут первыми, поэтому я смотрю направо и жду, пока не увижу руки вверх.
- 8: Как только никто справа от меня не поднимает руку, я могу войти в критическую секцию.
- 1: Когда я закончу, я положу руку обратно вниз.
Мне кажется твердым... Не уверен, почему это не должно работать надежно...
1 ответ
В модели памяти Java вы не можете гарантировать, что запись в F[i] будет видна другому Потоку, читающему ее позже.
Стандартное решение для такой проблемы видимости состоит в том, чтобы объявить переменную общего доступа как volatile, но в этом случае F является массивом, и запись / чтение в F[i] не изменяет значение F.
Невозможно объявить "массив летучих...", но можно объявить F как AtomicIntegerArray и использовать compareAndSet для атомарного изменения содержимого массива, не беспокоясь о видимости потока.