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




Взаимное исключение через общие переменные - часть 6


Если же в строке 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-му процессу, который используется как абстрактный "другой" процесс.


Содержание  Назад  Вперед