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

Question

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

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

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; 

Алгоритм использует две переменные, флаг и повернуть. Значение флага 1 означает, что процесс хочет войти в критический раздел. Переменный поворот содержит идентификатор процесса, в котором он находится. Вход в критическую секцию предоставляется для процесса 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.

Ссылки. Все данные получены из статьи «Some myths about famous mutual exclusion algorithms» от Alagarsamy.По-видимому, Block и Woo предложили модифицированный алгоритм в «A more efficient generalization of Peterson's mutual exclusion algorithm», который не удовлетворяет голода, который позже улучшил Alagarsamy в «A mutual exclusion algorithm with optimally bounded bypasses» (путем получения оптимальной вероятности голодания N-1).

Answer 2

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

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

Answer 3

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

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

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

Петерсона алгоритм п процессов является гораздо более сложным

Чтобы иметь ситуацию, когда процесс голодает условие 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 процессов защищает от голода!