Удовлетворяет ли алгоритм Петерсона голодание?

Как подозревает Бен Джексон, проблема в обобщенном алгоритме. Стандартный двухпроцессный алгоритм Петерсона удовлетворяет свойству отсутствия голодания.

Судя по всему, в исходной статье Петерсона действительно был алгоритм для N процессоров. Вот скетч, который я только что написал на языке, похожем на C++, который предположительно представляет собой этот алгоритм:

// Shared resources
int pos[N], step[N];

// Individual process code
void process(int i) {
    int j;
    for( j = 0; j < N-1; j++ ) {
        pos[i] = j;
        step[j] = i;
        while( step[j] == i and some_pos_is_big(i, j) )
            ; // busy wait
    }
    // insert critical section here!
    pos[i] = 0;
}

bool some_pos_is_big(int i, int j) {
    int k;
    for( k = 0; k < N-1; k++ )
        if( k != i and pos[k] >= j )
            return true;
    }
    return false;
}

Вот сценарий взаимоблокировки с N = 3:

• Процесс 0 запускается первым, устанавливает pos[0] = 0 и step[0] = 0 и затем ждет.
• Процесс 2 начинается следующим, устанавливает pos[2] = 0 и step[0] = 2 и затем ждет.
• Процесс 1 запускается последним, устанавливает pos[1] = 0 и step[0] = 1 и ждет.
• Процесс 2 первым замечает изменение step[0] и поэтому устанавливает j = 1, pos[2] = 1 и step[1] = 2.
• Процессы 0 и 1 заблокированы, потому что pos[2] большой.
• Процесс 2 не заблокирован, поэтому он устанавливает j = 2. Это выходит из цикла for и входит в критическую секцию. После завершения ставит pos[2] = 0, но тут же снова начинает конкурировать за критическую секцию, тем самым устанавливая step[0] = 2 и ожидая.
• Процесс 1 первым замечает изменение в step[0] и продолжается так же, как и процесс 2.
• ...
• Процессы 1 и 2 по очереди опережают процесс 0.

Ссылки. Все подробности взяты из статьи Алагарсами «Некоторые мифы об известных алгоритмах взаимного исключения. . По-видимому, Блок и Ву предложили модифицированный алгоритм в «более эффективном обобщении алгоритма взаимного исключения Петерсона", который соответствует принципу отсутствия голодания, который Алагарсами позже улучшил в "Алгоритм взаимного исключения с оптимально ограниченными обходами" (путем получения оптимальной границы голодания N-1).

Rex ошибается в ситуации взаимоблокировки.
(в качестве примечания: правильным термином будет сценарий голодания, поскольку для взаимоблокировки требуется как минимум два потока, которые должны «застрять», см. Википедию: тупик и голодание)

Когда процессы 2 и 1 переходят на уровень 0, шаг [0] устанавливается либо на 1, либо на 2, что делает условие продвижения процесса 0 ложным, поскольку step[0] == 0 ложно.

Алгоритм Петерсона для 2 процессов немного проще и действительно защищает от голодания.

Алгоритм Петерсона для n процессов намного сложнее

Чтобы возникла ситуация, когда процесс голодает, условие step[j] == i and some_pos_is_big(i, j) должно быть всегда истинным. Это означает, что ни один другой процесс не переходит на тот же уровень (что сделало бы step[j] == i ложным) и что по крайней мере один процесс всегда находится на том же уровне или на более высоком уровне, что и i (чтобы гарантировать, что some_pos_is_big(i, j) остается истинным).

Более того, только один процесс может быть заблокирован на этом уровне j. Если бы два были заблокированы, то для одного из них step[j] == i было бы ложным и, следовательно, не было бы заблокировано. Это означает, что ни один процесс не может войти на один и тот же уровень, и всегда должен быть процесс на уровне выше.

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

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

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

И поэтому алгоритм Петерсона для n процессов защищает от голодания!

Я подозреваю, что комментарий о голодании касается некоего обобщенного алгоритма N-процесса Петерсона. Можно сконструировать версию N-процесса с ограниченным ожиданием, но, не имея конкретного для обсуждения, мы не можем сказать, почему это конкретное обобщение может быть подвержено голоданию.

Быстрый Google обнаружил эту статью, которая включает псевдокод. Как видите, обобщенная версия намного сложнее (и дороже).