Операционные системы. Управление ресурсами

Алгоритм Деккера



Алгоритм Деккера

Эффективное и универсальное решение проблемы взаимного исключения носит название алгоритма Деккера и выглядит для двух процессов таким образом: 1 static int right = 0; 2 static char wish[2] = { 0,0 }; 3 void csBegin ( int proc ) { 4 int competitor; 5 competitor = other ( proc ); 6 while (1) { 7 wish[proc] = 1; 8 do { 9 if ( ! wish[competitor] ) return; 10 } 11 while ( right != competitor ); 12 wish[proc] = 0; 13 while ( right == competitor ); 14 } 15 } 16 void csEnd ( int proc ) { 17 right = other ( proc ); 18 wish[proc] = 0; 19 }

Алгоритм предусматривает, во-первых, общую переменную right для представления номера процесса, который имеет преимущественное (но не абсолютное) право на вход в критическую секцию. Во-вторых, массив wish, каждый элемент которого соответствует одному из процессов и представляет "желание" процесса войти в критическую секцию. Процесс заявляет о своем "желании" войти в секцию (строка 7). Если при этом выясняется, что процесс-конкурент не выставил своего "желания" (строка 9), то происходит возврат из функции, то есть, процесс входит в критическую секцию независимо от того, кому принадлежало преимущественное право на вход. Если же в строке 9 выясняется, что конкурент тоже выставил "желание", то проверяется право на вход (строка 10). Если право принадлежит нашему процессу, то повторяется проверка "желания" конкурента (строки 8 - 10), пока оно не будет отменено. Конкурент вынужден будет отменить свое "желание", потому что он в этой ситуации перейдет к строке 11, где процесс, не имеющий преимущественного права, должен это сделать. После отмены своего желания процесс ждет, пока преимущественное право не вернется к нему (строка 12), а затем вновь повторяет заявление "желания" и т.д. (строки 6 - 13). Таким образом, процесс в функции csBegin либо повторяет цикл 7 - 14, либо выходит из функции и входит в критическую секцию (10).

При выходе из критической секции (функция csEnd) процесс передает преимущественное право входа конкуренту (строка 16) и отказывается от своего желания (строка 17).

По собственному опыту признаем, что понимание этого алгоритма дается не очень просто. Рекомендуем для лучшего его понимания записать в две колонки две копии функции csBegin, соответствующие двум процессам, и промоделировать ход их параллельного выполнения с разными скоростями и разными сдвигами в фазах выполнения между процессами.

Приведем также обобщение алгоритма Деккера на N процессов: 1 static char wish[N+1] = { 0, ..., 0 }; 2 static char claimant[N+1] = { 0, ..., 0 }; 3 static int right = N; 4 void csBegin ( int proc ) { 5 int i; 6 clainmant[proc] = 1; 7 do { 8 while ( right != proc) { 9 wish[proc] = 0; 10 if(!clainmant[right]) right=proc; 11 } 12 wish[proc] = 1; 13 for (i = 0; i<N; i++ ) 14 if ((i!=proc) && wish[i]) break; 15 } 16 while (i<N); 17 } 18 void csEnd ( int proc ) { 19 right = N; 20 wish[proc] = clainmant[proc] = 0; 21 }

Ограничимся здесь только общими замечаниями к этому алгоритму. Процессы нумеруются от 0 до N-1. Мы вводим два массива для переменных состояния, размеры массивов на 1 больше числа процессов. Последние элементы каждого из массивов соответствуют несуществующему N-му процессу, который используется как абстрактный "другой" процесс. Понятие "конкурент" здесь заменяется понятием "претендент" (clainmant). Процесс становится претендентом, входя в функцию csBegin (строка 6). В отличие от "желания", "претензия" процесса не снимается до тех пор, пока она не будет удовлетворена (строка 18). Если преимущественное право на вход в критическую секцию принадлежит другому процессу, но этот другой процесс не является претендентом, то наш процесс забирает это право себе (строки 7 - 11). При выполнении этих действий наш процесс, однако, отказывается от своего "желания", давая тем самым возможность участвовать в состязании за захват секции другим процессам (строка 9). Получив право, процесс заявляет о своем "желании" (строка 12). В последующем цикле for проверяются "желания" других процессов (строки 13 - 14). Если есть другие "желающие" то повторяется получение права и т.д. (строки 7 - 15). Если же в цикле for другие желающие не выявлены (строка 15), наш процесс входит в критическую секцию. При выходе из секции процесс сбрасывает свои "претензию" и "желание" (строка 18) и передает право несуществующему N-му процессу (строка 19).



Содержание раздела