Операционные системы. Управление ресурсами
Взаимное исключение через общие переменные
Следующая группа решений базируется на непрерываемости памяти. Представляя эти алгоритмы, мы в основном следуем первоисточнику [7] и приводим в качестве примеров как правильные, так и неправильные или неудачные варианты решений.
Почти все примеры мы даем для двух процессов с номерами 0 и 1, их нетрудно обобщить на произвольное число процессов.
Вариант 1: общая переменная исключения.
Введем булевскую переменную mutEx, которая должна получать значение true (1), если вхождение в критическую секцию запрещено, или false (0), если вхождение разрешено. Попытка организовать "скобки критической секции" представлена следующим программным кодом:
1 static char mutEx = 0; 2 void csBegin ( void ) { 3 while ( mutEx ); 4 mutEx = 1; 5 } 6 void csEnd ( void ) { 7 mutEx = 0; 8 }
При вхождении в функцию csBegin процесс попадает в цикл ожидания (строка 3), в котором находится до тех пор, пока состояние переменной исключения не разрешит ему войти в критическую секцию. Выйдя из этого цикла, процесс устанавливает эту переменную в 1, запрещая тем самым другим процессам входить в их критические секции. Процесс, который выполнялся в критической секции, при выходе из последней сбрасывает переменную исключения в 0, разрешая этим другим процессам входить в их критические секции.
Это решение базируется на непрерываемости доступа к памяти - к переменной mutEx, но оно является НЕПРАВИЛЬНЫМ. Рассмотрим такой случай. Пусть процесс A вошел в свою критическую секцию и установил mutEx=1. Пока процесс A выполняется внутри своей критической секции, два других процесса - B и C также подошли к своим критическим секциям и обратились к функции csBegin. Поскольку переменная mutEx установлена в 1, процессы B и C зацикливаются в строке 3 кода функции csBegin. Когда процесс A выйдет из своей критической секции и установит mutEx=0, другой процесс, например B, выйдет из цикла строки 3, но имеется вероятность того, что прежде, чем процесс B успеет выполнить строку 4 кода и этим запретить вход в критическую секцию другим процессам, выйдет из цикла строки 3 и процесс C.
Таким образом, два процесса - B и C входят в критическую секцию, задача взаимного исключения не выполняется.
Хотя это решение и не выполняет взаимного исключения, оно может быть приемлемо для решения некоторых частных задач. Например, граф синхронизации, представленный на Рис.8.1, может быть обеспечен, если мы введем массив done, каждый элемент которого свяжем с определенным событием. События пронумерованы и номер события является параметром функции, сигнализирующей о завершении события - finish и функции ожидания события - waitFor:
1 static char done[9] = {0,0,0,0,0,0,0,0,0}; 2 void finish ( int event ) { 3 done[event] = 1; 4 } 5 void waitFor ( int event ) { 6 while ( ! done[event] ); 7 }
Теперь работа процессов может быть синхронизирована таким образом (функциями типа WorkX() представлена работа, выполняемая процессом X):
1 processA() { 2 /* работа процесса A */ 3 workA(); 4 /* отметка о завершении процесса A */ 5 finish(0); 6 } 7 processB() { 8 /* ожидание завершения процесса A */ 9 waitFor(0); 10 /* работа процесса B */ 11 workB(); 12 /* отметка о завершении процесса B */ 13 finish(1); 14 } 15 . . . 16 processE() { 17 /* ожидание завершения процесса B */ 18 waitFor(1); 19 /* ожидание завершения процесса D */ 20 waitFor(3); 21 /* работа процесса E */ 22 workE(); 23 /* отметка о завершении процесса E */ 24 finish(4); 25 } 26 . . .
Можно сократить запись, например, так (используя естественную последовательность, заложенную в строках графа):
1 processABC() { 2 workA(); finish(0); 3 workB(); finish(1); 4 workC(); finish(2); 5 } 6 processDEF() { 7 waitFor(0); workD(); finish(3); 8 waitFor(1); workE(); finish(4); 9 waitFor(2); workF(); finish(5); 10 } 11 processGHI() { 12 waitFor(3); workG(); finish(6); 13 waitFor(4); workH(); finish(7); 14 waitFor(5); workI(); finish(8); 15 }
или иным образом (запишите самостоятельно) - с использованием последовательности в столбцах.
Вариант 2: переменная-переключатель
Введем общую переменную right, значением ее будет номер процесса, который имеет право входить в критическую секцию.
Реализация " скобок критической секции" для двух процессов с номерами 0 и будет следующей:
1 static int right = 0; 2 void csBegin ( int proc ) { 3 while ( right != proc ); 4 } 5 void csEnd( int proc ) { 6 if ( proc == 0) right = 1; 7 else right = 0; 8 }
Процесс, вызвавший функцию csBegin, зацикливается до тех пор, пока не получит права на вход. Разрешение входа производится другим процессом при выходе его из своей критической секции.
Данный алгоритм обеспечивает разделение процессов 0 и 1. Два процесса могут одновременно войти в функцию csBegin, но при этом они только читают переменную right. Одновременное вхождение двух процессов в функцию csEnd невозможно. При обобщении алгоритма на большее число процессов первый процесс переключает право на второй, второй - на третий и т.д., последний - на первый. Если процессы используют разные группы разделяемых данных, то каждая группа может быть защищена своим переключателем, таким образом, не запрещается одновременный доступ к разным разделяемым данным. Это делает политику более либеральной, но при наличии двух и более групп разделяемых данных возможно возникновение тупика, так как группа разделяемых данных - тот же монопольный ресурс. Для предотвращения тупика возможно введение иерархии ресурсов, как было описано в главе 5.
Существенный недостаток этого алгоритма - в том, что он жестко определяет порядок, в котором процессы входят в критическую секцию. В нашем примере для двух процессов процессы 0 и 1 могут входить в нее только поочередно. Если предположить, что скорости процессов существенно разные, например, процессу 0 требуется вдвое чаще входить в критическую секцию, чем процессу 1, то частота вхождения процесса 0 снизится до частоты процесса 1, причем, снижение скорости процесса 0 будет обеспечиваться за счет занятого ожидания в строке 3. Таким образом, не выполняется пункт 3 условия правильности решения: если один из процессов остановится вне своей критической секции, то он заблокирует все остальные процессы.
Вариант 3: неальтернативные переключатели.
Введем для каждого процесса свою переменную, отражающую его нахождение в критической секции. Эти переменные сведены у нас в массив inside. Элемент массива inside[i] имеет значение 1, если i-й процесс находится в критической секции, и 0 - в противном случае.
Для примеров этого варианта введем функцию, определяющую номер процесса-конкурента:
int other (int proc ) { if ( proc == 0 ) return 1; else return 0; }
Первое решение в этом варианте:
1 static char inside[2] = { 0,0 }; 2 void csBegin ( int proc ) { 3 int competitor; /* конкурент */ 4 competitor = other ( proc ); 5 while ( inside[competitor] ); 6 inside[proc] = 1; 7 } 8 void csEnd (int proc ) { 9 inside[proc] = 0; 10 }
Здесь и во всех последующих решениях параметр proc функций csBegin и csEnd - номер процесса, желающего войти в свою критическую секцию или выйти из нее.
Процесс находится в занятом ожидании (строка 5) до тех пор, пока его конкурент находится в своей критической секции. Когда конкурент снимает свой признак пребывания в критической секции, наш процесс устанавливает свой признак (строка 6) и, таким образом, запрещает вход в секцию конкуренту.
Решение, однако, не гарантирует взаимного исключения. Возможен случай, когда два процесса одновременно выполнят каждый строку 5 своего кода и, следовательно, войдут в свои критические секции одновременно.
В следующем решении мы меняем местами установку своего признака входа и проверку признака конкурента:
1 static char inside[2] = { 0,0 }; 2 void csBegin ( int proc ) { 3 int competitor; 4 competitor = other ( proc ); 5 inside[proc] = 1; 6 while ( inside[competitor] ); 7 } 8 void csEnd (int proc ) { 9 inside[proc] = 0; 10 }
Теперь процессы не могут одновременно войти в критические секции. Но возникает другая опасность: если процессы одновременно выполнят строку 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), то происходит возврат из функции, то есть, процесс входит в критическую секцию независимо от того, кому принадлежало преимущественное право на вход.
Если же в строке 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).
Алгоритм Питерсона
Более компактная и изящная модификация алгоритма Деккера известна, как алгоритм Питерсона. Вот его вариант для двух процессов:
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 по первой части условия.
Общие положительные свойства алгоритмов, основывающихся на неальтернативных переключателях (Деккера и Питерсона), следующие:
- они корректны как для одно-, так и для многопроцессорных систем;
- они либеральны, так как позволяют более быстрым процессам входить в свои критические секции чаще, чем медленным;
- они не ограничивают количество обслуживаемых ими процессов;
- они позволяют процессам сколь угодно долго задерживаться вне своей критической секции.
Но:
- решения непросты для понимания и ошибиться в их реализации очень легко;
- процессы используют занятое ожидание при входе в критическую секцию.
