Код алгоритма:
#define FALSE 0
#define N 10
int turn[N];
int stage[N + 1];
void enterRegion(int process)
{
for (int i = 1; i <= N - 1; i++) // перебор стадий
{
stage[process] = i;
turn[i] = process;
for (int j = 1; j <= N; j++) // "опрос" остальных процессов
{
if (j == process)
continue;
while (stage[j] >= i && turn[i] == process);
}
}
}
void leaveRegion(int process)
{
stage[process] = FALSE;
}
Для простоты и улучшения читабельности кода не будем рассматривать процесс с индексом 0, так же не будем рассматривать стадию с индексом 0, точнее стадия с индексом 0 будет своеобразным "стартом".А теперь немного теории.
Алгоритм Петерсона для N процессов по сути тот же самый, что и для случая двух процессов, однако перед входом в критическую процесс должен преодолеть (n-1) стадий, т.н. "состязания". Количество стадий равно (n-1), потому что на каждой стадии будет оставаться хотя бы один процесс, а остальные будут переходить на следующую стадию, т.е. не более (n-j) процессов могут покинуть стадию под номером j. В конце концов у нас останется только два процесса, один из которых пройдет в критическую секцию. Два процесса будут как раз на (n-1)-й стадии. Преодоление каждой стадии напоминает версию для двух процессов, где один из процессов временно устраняется.
stage[process] - номер стадии, в которой находится процесс с идентификатором process
turn[i] = process - идентификатор процесса process, зашедшего последним в стадию под номером i
Рассмотрим поведение процессов на рисунке.
Пусть поочередно все 4 процесса попали на первую стадию. Пусть последним оказался процесс 1.
Происходит "опрос" остальных процессов на наличие их на той же самой стадии, где находится работающий процесс, либо на стадиях с бОльшим номером. Пусть вследствие прерываний до цикла, где происходит опрос, добрался процесс 2. В этом случае условие
while (stage[j] >= i && turn[i] == process)не выполнится.
Несмотря на то, что на данной стадии кроме процесса 2 имеются еще процессы, процесс 2 НЕ является последним перешедшим на данную стадию (мы условились, что последним будет процесс 1). Стало быть процесс 2 проходит на следующую стадию. И если так случится, что прерываний не будет, и его никто не "догонит", то процесс 2 благополучно войдет в критическую секцию, затем выйдет из нее, присвоит переменной interested[process] значение FALSE, что будет означать что данный процесс находится на стадии 0, т.е. на "старте", ну или на самой "низшей" стадии.
Если же переключению процессов случаются примерно через равные промежутки времени, то всегда для последнего процесса, зашедшего на данную стадию, условие
while (stage[j] >= i && turn[i] == process)не будет выполняться по той простой причине, что он последний: (turn[i] == process).
Таким образом на последующую стадию переходит на один процесс меньше, и так пока не останется двух процессов, после чего один из двух войдет в критическую секцию. Второй из двух войдет в критическую секцию после выхода первого, потому что (stage[j] >= i) будет равно FALSE. А если второго процесса кто либо "догонит", тем не менее (turn[i] == process) будет равно FALSE, и процесс все равно войдет в критическую секцию.
