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

Question

Я искал информацию по алгоритму Петерсона , но наткнулся на ссылки, в которых говорится, что он не удовлетворяет голоду, а только тупику. Это правда? и если да, то может кто-нибудь объяснить, почему это не так?

Алгоритм Петерсона:

flag[0]   = 0;
flag[1]   = 0;
turn;

P0: flag[0] = 1;                                       
    turn = 1;                                               
    while (flag[1] == 1 && turn == 1)                        
    {                                                       
           // busy wait                                             
    }                                                                                      
    // critical section                                     
       ...                                                     
    // end of critical section                              
    flag[0] = 0;   

P1: flag[1] = 1;                                       
    turn = 0;                                               
    while (flag[0] == 1 && turn == 0)                        
    {                                                       
           // busy wait                                             
    }                                                                                      
    // critical section                                     
       ...                                                     
    // end of critical section                              
    flag[1] = 0;

Алгоритм использует две переменные, flag и turn. Значение флага 1 указывает, что процесс хочет войти в критическую секцию. Переменная turn содержит идентификатор процесса, чей это оборот. Вход в критическую секцию предоставляется для процесса P0, если P1 не хочет входить в свою критическую секцию или если P1 присвоил приоритет P0, установив поворот на 0.

Answer 1

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

Судя по всему, в первоначальной работе Петерсона был алгоритм для 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).

Answer 2

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

Когда процессы 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 и, следовательно, не выше lelel j), по крайней мере, один процесс должен быть заблокирован слишком высоко или процесс в критическом разделе не освобождает критическая секция.

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

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

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

Answer 3

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