Деревянко А.С., Солощук М.Н. Операционные системы.Часть I. Построение и функционирование операционных систем
Подождите немного. Документ загружается.
251
Это решение базируется на непрерываемости доступа к памяти – к
переменной 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
2
3
4
5
6
static char done[9]
= {0,0,0,0,0,0,0,0,0};
void finish ( int event ) {
done[event] = 1;
}
void waitFor ( int event ) {
252
7
8
while ( ! done[event] );
}
Теперь работа процессов может быть синхронизирована таким
образом (функциями типа workX() представлена работа, выполняемая
процессом X):
processA() {
/* работа процесса A */
workA();
/* отметка о завершении процесса A */
finish(0);
}
processB() {
/* ожидание завершения процесса A */
waitFor(0);
/* работа процесса B */
workB();
/* отметка о завершении процесса B */
finish(1);
}
. . .
processE() {
/* ожидание завершения процесса B */
waitFor(1);
/* ожидание завершения процесса D */
waitFor(3);
/* работа процесса E */
workE();
/* отметка о завершении процесса E */
253
finish(4);
}
. . .
Можно сократить запись, например, так (используя естественную
последовательность, заложенную в строках графа):
processABC() {
workA(); finish(0);
workB(); finish(1);
workC(); finish(2);
}
processDEF() {
waitFor(0); workD(); finish(3);
waitFor(1); workE(); finish(4);
waitFor(2); workF(); finish(5);
}
processGHI() {
waitFor(3); workG(); finish(6);
waitFor(4); workH(); finish(7);
waitFor(5); workI(); finish(8);
}
или иным образом (запишите самостоятельно) – с использованием
последовательности в столбцах.
ВАРИАНТ 2: ПЕРЕМЕННАЯ-ПЕРЕКЛЮЧАТЕЛЬ
Введем общую переменную right, значением ее будет номер
процесса, который имеет право входить в критическую секцию.
254
Реализация "скобок критической секции" для двух процессов с номерами 0
и будет следующей:
1
2
3
4
5
6
7
8
static int right = 0;
void csBegin ( int proc ) {
while ( right != proc );
}
void csEnd( int proc ) {
if ( proc == 0) right = 1;
else right = 0;
}
Процесс, вызвавший функцию csBegin, зацикливается до тех пор,
пока не получит права на вход. Разрешение входа производится другим
процессом при выходе его из своей критической секции.
Данный алгоритм обеспечивает разделение процессов 0 и 1. Два
процесса могут одновременно войти в функцию csBegin, но при этом
они только читают переменную right. Одновременное вхождение двух
процессов в функцию csEnd невозможно. При обобщении алгоритма на
большее число процессов первый процесс переключает право на второй,
второй – на третий и т.д., последний – на первый. Если процессы
используют разные группы разделяемых данных, то каждая группа может
быть защищена своим переключателем, таким образом, не запрещается
одновременный доступ к разным разделяемым данным. Это делает
политику более либеральной, но при наличии двух и более групп
разделяемых данных возможно возникновение тупика, так как группа
разделяемых данных – тот же монопольный ресурс. Для предотвращения
тупика возможно введение иерархии ресурсов, как было описано в главе 5.
255
Существенный недостаток этого алгоритма в том, что он жестко
определяет порядок, в котором процессы входят в критическую секцию. В
нашем примере для двух процессов процессы 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
2
3
static char inside[2] = { 0,0 };
void csBegin ( int proc ) {
int competitor; /* конкурент */
256
4
5
6
7
8
9
10
competitor = other ( proc );
while ( inside[competitor] );
inside[proc] = 1;
}
void csEnd (int proc ) {
inside[proc] = 0;
}
Здесь и во всех последующих решениях параметр proc функций
csBegin и csEnd – номер процесса, желающего войти в свою
критическую секцию или выйти из нее.
Процесс находится в занятом ожидании (строка 5) до тех пор, пока
его конкурент находится в своей критической секции. Когда конкурент
снимает свой признак пребывания в критической секции, наш процесс
устанавливает свой признак (строка 6) и таким образом запрещает вход в
секцию конкуренту.
Решение, однако, не гарантирует взаимного исключения. Возможен
случай, когда два процесса одновременно выполнят каждый строку 5
своего кода и, следовательно, войдут в свои критические секции
одновременно.
В следующем решении мы меняем местами установку своего
признака входа и проверку признака конкурента:
1
2
3
4
5
static char inside[2] = { 0,0 };
void csBegin ( int proc ) {
int competitor;
competitor = other ( proc );
inside[proc] = 1;
257
6
7
8
9
10
while ( inside[competitor] );
}
void csEnd (int proc ) {
inside[proc] = 0;
}
Теперь процессы не могут одновременно войти в критические секции.
Но возникает другая опасность: если процессы одновременно выполнят
строку 5, то они заблокируют друг друга, так как оба процесса уже
установят свои признаки, но будут зациклены в занятом ожидании,
выйти из которого им не разрешит установленный признак конкурента.
Новое решение:
1
2
3
4
5
6
7
8
9
10
11
12
static char inside[2] = { 0,0 };
void csBegin ( int proc ) {
int competitor;
competitor = other ( proc );
do {
inside[proc] = 1;
if ( inside[competitor] ) inside[proc] = 0;
} while ( ! inside[proc] );
}
void csEnd (int proc ) {
inside[proc] = 0;
}
Процесс устанавливает свой признак вхождения (строка 6). Но если он
обнаруживает, что признак вхождения конкурента тоже установлен
(строка 7), то он свой признак сбрасывает. Эти действия будут
258
повторяться до тех пор, пока наш процесс не сохранит свой признак
взведенным (строка 8), а это возможно только в том случае, если
признак конкурента сброшен.
Это решение не может быть принято вот по какой причине.
Возможно такое соотношение скоростей процессов, при котором они
будут одновременно выполнять строку 7, и одновременно сбрасывать свои
признаки. Такая "чрезмерная уступчивость" процессов приведет к
бесконечному откладыванию решения о входе в критическую секцию.
АЛГОРИТМ ДЕККЕРА
Эффективное и универсальное решение проблемы взаимного
исключения носит название алгоритма Деккера и выглядит для двух
процессов таким образом:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int right = 0;
static char wish[2] = { 0,0 };
void csBegin ( int proc ) {
int competitor;
competitor = other ( proc );
while (1) {
wish[proc] = 1;
do {
if ( ! wish[competitor] ) return;
}
while ( right != competitor );
wish[proc] = 0;
while ( right == competitor );
}
259
15
16
17
18
19
}
void csEnd ( int proc ) {
right = other ( proc );
wish[proc] = 0;
}
Алгоритм предусматривает, во-первых, общую переменную right
для представления номера процесса, который имеет преимущественное (но
не абсолютное) право на вход в критическую секцию. Во-вторых, массив
wish, каждый элемент которого соответствует одному из процессов и
представляет "желание" процесса войти в критическую секцию. Процесс
заявляет о своем "желании" войти в секцию (строка 7). Если при этом
выясняется, что процесс-конкурент не выставил своего "желания" (строка
9), то происходит возврат из функции, т.е. процесс входит в критическую
секцию независимо от того, кому принадлежало преимущественное право
на вход. Если же в строке 9 выясняется, что конкурент тоже выставил
"желание", то проверяется право на вход (строка 10). Если право
принадлежит нашему процессу, то повторяется проверка "желания"
конкурента (строки 8 - 10), пока оно не будет отменено. Конкурент
вынужден будет отменить свое "желание", потому что он в этой ситуации
перейдет к строке 11, где процесс, не имеющий преимущественного права,
должен это сделать. После отмены своего желания процесс ждет, пока
преимущественное право не вернется к нему (строка 12), а затем вновь
повторяет заявление "желания" и т.д. (строки 6 - 13). Таким образом,
процесс в функции csBegin либо повторяет цикл 7 - 14, либо выходит из
функции и входит в критическую секцию (10).
При выходе из критической секции (функция csEnd) процесс
передает преимущественное право входа конкуренту (строка 16) и
отказывается от своего желания (строка 17).
260
По собственному опыту признаем, что понимание этого алгоритма
дается не очень просто. Рекомендуем для лучшего его понимания записать
в две колонки две копии функции csBegin, соответствующие двум
процессам, и промоделировать ход их параллельного выполнения с
разными скоростями и разными сдвигами в фазах выполнения между
процессами.
Приведем также обобщение алгоритма Деккера на N процессов:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static char wish[N+1] = { 0, ..., 0 };
static char claimant[N+1] = { 0, ..., 0 };
static int right = N;
void csBegin ( int proc ) {
int i;
clainmant[proc] = 1;
do {
while ( right != proc) {
wish[proc] = 0;
if(!clainmant[right]) right=proc;
}
wish[proc] = 1;
for (i = 0; i<N; i++ )
if ((i!=proc) && wish[i]) break;
}
while (i<N);
}
void csEnd ( int proc ) {
right = N;
wish[proc] = clainmant[proc] = 0;
}