Параллельная обработка - алгоритм Петерсона

Question

Для тех, кто не знаком, алгоритм Петерсона используется для координации процессов:

int No_Of_Processes; // Number of processes
int turn; // Whose turn is it?
int interested[No_Of_Processes]; // All values initially FALSE

void enter_region(int process) {
int other; // number of the other process

other = 1 - process; // the opposite process
interested[process] = TRUE; // this process is interested
turn = process; // set flag
while(turn == process && interested[other] == TRUE); // wait
}

void leave_region(int process) {
interested[process] = FALSE; // process leaves critical region
}

Мой вопрос: может ли этот алгоритм привести к тупику?

Answer 1

Нет, тупик невозможен. Единственное место, которое вы ждете, это while loop. И переменные process не разделяются между потоками, и они разные, но переменная turn является общей. Поэтому невозможно получить условие true для turn == process для более чем одного потока в каждый момент времени. Но в любом случае ваше решение не является правильным, алгоритм Петерсона предназначен только для двух параллельных потоков, а не для любого No_Of_Processes, как в вашем коде. В оригинальном алгоритме для N процессов возможны взаимоблокировки ссылка .