Классические задачи синхронизации процессов отражают разные модели взаимодействия и демонстрируют использование механизма семафоров для организации такого взаимодействия.
Обедающие философы (Рис. 86). Пускай существует круглый стол, за которым сидит группа философов: они пришли пообщаться и покушать. Кушают они спагетти, которое находится в общей миске, стоящей в центре стола. Для приема пищи они пользуются двумя вилками: одна в левой руке, другая — в правой. Вилки располагаются по одной между каждыми двумя философами. Любой философ может взять обе вилки, покушать, затем положить вилки на стол, после этого вилки может взять его сосед и повторить эти действия. Если мы организуем работу таким образом, что любой философ, желающий поесть, берет сначала левую вилку, затем правую, после чего начинает кушать, то в какой-то момент может возникнуть ситуация тупика (когда каждый возьмет по одной левой вилке, а правая будет захвачена соседом).
Рис. 86. Обещающие философы.
Итак, данная задача иллюстрирует модель доступа равноправных процессов к общему ресурсу, и ставится вопрос, как организовать корректную работу такой системы.
Рассмотрим элементарное решение данной задачи.
#define N 5
void Philosopher(int i)
{
while(TRUE)
{
Think();
/* взятие левой вилки */
TakeFork(i);
/* взятие правой вилки */
TakeFork((i + 1) % N);
Eat();
/* освобождение левой вилки */
PutFork(i);
/* освобождение правой вилки */
PutFork((i + 1) % N);
}
}
Как было показано выше, в данном случае возможно появление ситуации, когда произойдет взаимоблокировка философов. Рассмотрим иное решение.
/* количество философов */
#define N 5
/* Номера левого и правого */
#define LEFT (i-1)%N
#define RIGHT (i+1)%N
/* состояния философов:
«думает»,
«желает поесть»,
«кушает»
*/
#define THINKING 0
#define HUNGRY 1
#define EATING 2
/* переопределяем тип СЕМАФОР */
typedef int semaphore;
/*
массив состояний каждого из философов, инициализированный нулями
*/
int state[N];
/* семафор для доступа в критическую секцию */
semaphore mutex = 1;
/*
массив семафоров по одному на каждого из философов,
инициализированный нулями
*/
semaphore s[N];
/* Процесс-философ (i = 0..N) */
void Philosopher(int i)
{
while(TRUE)
{
Think();
TakeForks(i);
Eat();
PutForks(i);
}
}
/* получение вилок */
void TakeForks(int i)
{
/* вход в критическую секцию */
down(&mutex);
state[i] = HUNGRY;
Test(i);
/* выход из критической секции */
up(&mutex);
down(&s[i]);
}
/* освобождение вилок */
void PutForks(int i)
{
/* вход в критическую секцию */
down(&mutex);
state[i] = THINKING;
Test(LEFT);
Test(RIGHT);
/* выход из критической секции */
up(&mutex);
}
void Test(int i)
{
if(state[i] == HUNGRY &&
state[LEFT]!= EATING &&
state[RIGHT]!= EATING)
{
state[i] = EATING;
up(&s[i]);
}
}
В этом решении каждый философ живет по аналогичному циклическому распорядку: размышляет некоторое время, затем берет вилки, кушает, кладет вилки. Рассмотрим процедуру получения вилок (TakeForks). Опускается семафор mutex, который используется для синхронизации входа в критическую секцию. Внутри критической секции меняем состояние философа (помечаем его состоянием «голоден»). Затем предпринимается попытка начать есть (вызывается функция Test). Функция Test проверяет, что если i-ый философ голоден, а его соседи в данный момент не едят (т.е. правая и левая вилки свободны), то этот философ начинает прием пищи (состояние EATING), а его семафор поднимается (заметим, что изначально этот семафор инициализирован нулем). После этого мы возвращаемся обратно в функцию TakeForks, в которой далее происходит выход из критической секции (подымаем семафор mutex), а затем опускаем семафор этого философа. Если внутри функции Test философу удалось начать прием пищи, то семафор поднят, и операция down обнулит его, не блокируясь. Если же функция Test не изменит состояние философа, а также не поднимет его семафор, то операция down в этой точке заблокируется до тех пор, пока оба соседа не освободят вилки.
Внутри функции освобождения вилок PutForks первым делом происходит опускание семафора mutex, происходит вход в критическую секцию. Затем меняется статус философа (на статус THINKING), после чего проверяем его соседей: если любой из них был заблокирован лишь из-за того, что наш i-ый философ забрал его вилку, то мы его разблокируем, и он начинает прием пищи. После этого происходит выход из критической секции путем подъема семафора mutex.
Заметим, что использование механизма взаимоисключающего нахождения внутри критической секции (за счет семафора mutex) гарантирует, что не возникнет ситуация, когда два процесса, соответствующие соседним философам, будут так спланированы на обработку на процессоре, что функция Test в каждом из них проработает и разрешит каждому из них начать прием пищи (что, конечно же, является ошибкой). Если же этого механизма не будет, то возможно, что один их процессов-соседей входит в Test, делает проверку на возможность начала приема пищи. Проверка дает истинное значение, управление переходит к первой команде внутри if-блока. После этого происходит смена процесса на процессоре, управление получает сосед этого философа. Тот тоже делает проверку внутри функции Test, и также получает положительный ответ, и управление переходит к первой инструкции if-блока. Дальнейшая работа будет некорректной.
Задача «читателей и писателей». Представим произвольную систему резервирования ресурса. Например, это может быть система резервирования места в гостинице. В данной системе существует два типа процессов для работы с информацией. Одни процессы могут читать информацию, а другие — ее изменять, корректировать. Соответственно, возникает все тот же вопрос, как организовать корректную совместную работу этих процессов. Это означает, что в любой момент времени читать данные могут любое количество процессов-читателей, но если процесс-писатель начал свою работу, то все остальные процессы (и читатели, и писатели) будут блокированы на входе в систему.
Рассмотрим модельную реализацию данной задачи при выбранной следующей стратегии: будем считать, что наиболее приоритетными являются читающие процессы. Т.е. процесс-писатель будет ожидать момента, когда все желающие процессы-читатели окончат свои действия в системе и покинут ее.
/* переопределение типа семафор */
typedef int semaphore;
/* семафор для доступа в критическую секцию */
semaphore mutex = 1;
/* семафор для доступа к хранилищу данных */
semaphore db = 1;
/* количество читателей внутри хранилища */
int rc = 0;
/* процесс-читатель */
void Reader(void)
{
while(true)
{
down(&mutex);
rc = rc + 1;
if(rc == 1)
down(&db);
up(&mutex);
ReadDataBase();
down(&mutex);
rc = rc – 1;
if(rc == 0)
up(&db);
up(&mutex);
UseDataRead();
}
}
/* процесс-писатель */
void Writer(void)
{
while(TRUE)
{
ThinkUpData();
down(&db);
WriteDataBase();
up(&db);
}
}
В приведенном решении процесс-читатель в каждом цикле своей работы входит в критическую секцию (за счет опускания семафора mutex), увеличивает счетчик читателей, находящихся в хранилище, на 1. Затем проверяет, что если он является первым читателем (т.е. в данный момент он единственный клиент в хранилище), то опускает семафор db, тем самым, препятствуя писателем войти в систему, если они того пожелают. Если же семафор db уже был опущен, то это означает, что в данный момент в хранилище присутствует писатель, и этот первый читатель заблокируется на этой операции, ожидая выхода писателя из системы. (Заметим, что это блокировка происходит внутри критической секции, поэтому остальные читатели будут блокироваться на опускании семафора mutex.) После этого происходит выход из критической секции (подымаем семафор mutex), чтение информации из хранилища. Затем производятся обратные действия по выходу из хранилища, которые также происходят внутри критической секции. Итак, на выходе мы уменьшаем число читателей в хранилище, и если этот читатель является последним клиентом в библиотеке, то происходит поднятие семафора db, разрешая работу писателям (которые к этому моменту могли быть заблокированы на входе). В конце цикла работы читатель обрабатывает полученные данные из хранилища, после чего цикл повторяется.
Писатель в начале каждого цикла своей работы подготавливает данные для сохранения, затем пытается войти в хранилище, опуская семафор db. Если в хранилище кто-то есть, то он будет ожидать, пока последний клиент (независимо, читатель это или писатель) не покинет его. После этого он производит корректировку данных в хранилище и покидает его, поднимая семафор db.
Заметим, что в данном решении если хотя бы один читатель находится внутри системы, то любой следующий читатель беспрепятственно в нее попадет, писатель же будет ожидать, когда все посетители покинут хранилище, т.е. реализована стратегия приоритетности читателя перед писателем.
Данная задача иллюстрирует модель доступа к общему ресурсу процессов, имеющих разные приоритеты.
Задача о «спящем парикмахере». Представим себе парикмахерскую, в которой имеется единственно рабочее кресло и единственный цирюльник. В парикмахерской есть комната ожидания, в которой стоят N кресел, на которых могут сидеть клиенты, ожидающие своей очереди. Если свободных кресел нет, то вновь приходящие клиенты сразу же покидают заведение. Когда посетителей нет, парикмахер может сидеть в своем кресле и дремать.
Данная задача является иллюстрацией модели клиент-сервер с ограничением на длину очереди клиентов.
Рассмотрим реализацию данной модели.
/* количество стульев в комнате ожидания */
#define CHAIRS 5
/* переопределение типа СЕМАФОР */
typedef int semaphore;
/* наличие посетителей, ожидающих парикмахера */
semaphore customers = 0;
/*
количество парикмахеров, ожидающих посетителей (0 или 1)
*/
semaphore barbers = 0;
/* семафор для доступа в критическую секцию */
semaphore mutex = 1;
/* количество ожидающих посетителей */
int waiting = 0;
/* Брадобрей */
void Barber(void)
{
while(TRUE)
{
down(&customers);
down(&mutex);
waiting = waiting – 1;
up(&barbers);
up(&mutex);
CutHair();
}
}
/* Посетитель */
void Customer(void)
{
down(&mutex);
if(waiting < CHAIRS)
{
waiting = waiting + 1;
up(&customers);
up(&mutex);
down(&barbers);
GetHaircut();
}
else
{
up(&mutex);
}
}
Процесс-парикмахер первым делом опускает семафор customers, уменьшив тем самым количество ожидающих посетителей на 1. Если в комнате ожидания никого нет, то он «засыпает» в своем кресле, пока не появится клиент, который его разбудит. Затем парикмахер входит в критическую секцию, уменьшает счетчик ожидающих клиентов, поднимает семафор barbers, сигнализируя клиенту о своей готовности его обслужить, а потом выходит из критической секции. После описанных действий он начинает стричь волосы посетителю.
Посетитель парикмахерской входит в критическую секцию. Находясь в ней, он первым делом проверяет, есть ли свободные места в зале ожидания. Если нет, то он просто уходит (покидает критическую секцию, поднимая семафор mutex). Иначе он увеличивает счетчик ожидающих процессов и поднимает семафор customers. Если же этот посетитель является единственным в данный момент клиентом брадобрея, то он этим действием разбудит брадобрея. После этого он выходит из критической секции и «захватывает» брадобрея (опуская семафор barbers). Если же этот семафор опущен, то клиент будет дожидаться, когда брадобрей его поднимет, известив тем самым, что готов к работе. В конце клиент обслуживается (GetHaircut).