Алгоритм Питерсона
Алгоритм Питерсона
Более компактная и изящная модификация алгоритма Деккера известна, как алгоритм Питерсона. Вот его вариант для двух процессов: 1 static int right; 2 static char wish[2] = { 0,0 }; 3 void csBegin ( int proc ) { 4 int competitor; 5 if ( proc == 0 ) competitor = 1; 6 else competitor = 0; 7 wish[proc] = 1; 8 right = competitor; 9 while ( wish[competitor] && ( right == competitor ); 10 } 11 void csEnd ( int proc ) { 12 wish[proc] = 0; 13 }
При входе в критическую секцию процесс заявляет о своем "желании" (строка 7) и отказывается от своего преимущественного права (строка 8). Процесс будет ожидать, если его конкурент заявил свое "желание" и имеет преимущественное право (строка 9). Если нет интереса конкурента или если независимо от интереса конкурента наш процесс имеет преимущественное право, то наш процесс входит в критическую секцию. Если наш процесс отказался от своего права в строке 8, то как же это право может к нему вернуться? Право нашего процесса может быть восстановлено конкурентом, когда последний тоже войдет в функцию csBegin своего кода и выполнит строку 8. При выходе из критической секции процесс просто снимает свой интерес, и тогда его конкурент, возможно, ожидающий в строке 8, получает возможность выхода из цикла строки 9 по первой части условия.
Общие положительные свойства алгоритмов, основывающихся на неальтернативных переключателях (Деккера и Питерсона), следующие:
- они корректны как для одно-, так и для многопроцессорных систем;
- они либеральны, так как позволяют более быстрым процессам входить в свои критические секции чаще, чем медленным;
- они не ограничивают количество обслуживаемых ими процессов;
- они позволяют процессам сколь угодно долго задерживаться вне своей критической секции.
Но:
- решения непросты для понимания и ошибиться в их реализации очень легко;
- процессы используют занятое ожидание при входе в критическую секцию.
