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



         

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


Новое решение:

1 static char inside[2] = { 0,0 }; 2 void csBegin ( int proc ) { 3 int competitor; 4 competitor = other ( proc ); 5 do { 6 inside[proc] = 1; 7 if ( inside[competitor] ) inside[proc] = 0; 8 } while ( ! inside[proc] ); 9 } 10 void csEnd (int proc ) { 11 inside[proc] = 0; 12 }

Процесс устанавливает свой признак вхождения (строка 6). Но если он обнаруживает, что признак вхождения конкурента тоже установлен (строка 7), то он свой признак сбрасывает. Эти действия будут повторяться до тех пор, пока наш процесс не сохранит свой признак взведенным (строка 8), а это возможно только в том случае, если признак конкурента сброшен.

Это решение не может быть принято вот по какой причине. Возможно такое соотношение скоростей процессов, при котором они будут одновременно выполнять строку 7 - и одновременно сбрасывать свои признаки. Такая "чрезмерная уступчивость" процессов приведет к бесконечному откладыванию решения о входе в критическую секцию.

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

Эффективное и универсальное решение проблемы взаимного исключения носит название алгоритма Деккера и выглядит для двух процессов таким образом:

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), то происходит возврат из функции, то есть, процесс входит в критическую секцию независимо от того, кому принадлежало преимущественное право на вход.


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