Глава_1 (1085730), страница 9
Текст из файла (страница 9)
Рис. 2.18. Время обеда на факультете философии
В листинге 2.10 представлено очевидное решение проблемы. Процедура take_ fork ждет, пока указанная вилка не освободится, и берет ее. К сожалению, это решение неверно — представьте себе, что все пять философов возьмут одновременно свои левые вилки. Каждый останется без правой вилки, и произойдет взаимоблокировка.
Листинг 2.10. Неверное решение проблемы обедающих философов
#define N 5 /* Количество философов */
void philosospher (int i) /* 1 - номер философа, от 0 до 4 */
{
while(TRUE) {
think (); /* Философ размышляет */
take_fork (i); /* Берет левую вилку */
take fork ((i+1) % N); /* Берет правую вилку */
eat () ; /* Спагетти, ням-ням */
put_fork(i); /* Кладет на стол левую илку
put_fork((I + 1)%N);
}}
Можно изменить программу так, чтобы после получения левой вилки проверялась доступность правой. Если правая вилка недоступна, философ отдает левую обратно, ждет некоторое время и повторяет весь процесс. Этот подход также не будет работать, хотя и по другой причине. Если не повезет, все пять философов могут начать процесс одновременно, взять левую вилку, обнаружить отсутствие правой, положить левую обратно на стол, одновременно взять левую вилку, и так до бесконечности. Ситуация, в которой все программы продолжают работать сколь угодно долго, но не могут добиться хоть какого-то прогресса, называется зависанием процесса (по-английски starvation, буквально «умирание от голода». Этот термин применяется даже в том случае, когда проблема возникает не в итальянском или китайском ресторане, а на компьютерах).
Вы можете подумать: «Если философы будут размышлять в течение некоторого случайно выбранного промежутка времени после неудачной попытки взять правую вилку, вероятность того, что все процессы будут продолжать топтаться на месте хотя бы в течение часа, невелика». Это правильно, и для большинства приложений повторение попытки спустя некоторое время не является проблемой. Например, в локальной сети Ethernet в ситуации, когда два компьютера посылают пакеты одновременно, каждый должен подождать случайно заданное время и повторить попытку — на практике это решение хорошо работает. Тем не менее в некоторых приложениях предпочтительным является другое решение, работающее всегда и не зависящее от случайных чисел (например, в приложении для обеспечения безопасности на атомных электростанциях).
В листинг 2.10 можно внести улучшение, исключающее взаимоблокировку и зависание процесса: защитить пять операторов, следующих за запросом think, бинарным семафором. Тогда философ должен будет выполнить операцию down на переменной mutex прежде, чем потянуться к вилкам. А после возврата вилок на место ему следует выполнить операцию up на переменной mutex. С теоретической точки зрения решение вполне подходит. С точки зрения практики возникают проблемы с эффективностью: в каждый момент времени может есть спагетти только один философ. Но вилок пять, поэтому необходимо разрешить есть в каждый момент времени двум философам.
Решение, представленное в листинге 2.11, исключает взаимоблокировку и позволяет реализовать максимально возможный параллелизм для любого числа философов. Здесь используется массив state для отслеживания душевного состояния каждого философа: он либо ест, либо размышляет, либо голодает (пытаясь получить вилки). Философ может начать есть, только если ни один из его соседей не ест. Соседи философа с номером i определяются макросами LEFT и RIGHT (то есть если i = 2, то LEFT - 1 и RIGHT= 3).
Листинг 2.11. Решение задачи обедающих философов
#define N 5 /* Количество философов */
#define LEFT (i+N,l)%N /* Номер левого соседа философа с номером i */
#define RIGHT (i+1)%N /* Номер правого соседа философа с номером 1 */
#define THINKING 0 /* Философ размышляет */
#define HUNGRY 1 /* Философ пытается получить вилки */
#define EATING 2 /* Философ ест */
typedef int semaphore; /* Семафоры - особый вид целочисленных переменных */
int state[N]; /* Массив для отслеживания состояния каждого философа */
semaphore mutex = 1; /* Взаимное исключение для критических областей */
semaphore s[N]; /* Каждому философу по семафору */
void philosopher (int i) /* i - номер философа, от 0 до N-1 */
{
while (TRUE) { /* Повторять до бесконечности */
think (); /* Философ размышляет */
take_forks (i); /* Получает две вилки или блокируется */
eat (); /* Спагетти, ням-ням */
put_forks (i); . /* Кладет на стол обе вилки */
} }
void take_forks(int i) /* i - номер философа, от 0 до N-1*/
{
down(&mutex); /* Вход в критическую область */
state[1] = HUNGRY; /* Фиксация наличия голодного философа */
test(i): /* Попытка получить две вилки */
up(&mutex); /* Выход из критической области */
down(&s[i]); /* Блокировка, если вилок не досталось */
void put_forks(i) /* i - номер философа, от 0 до N-1*/
{
down(&mutex); /* Вход в критическую область */
state[i] = THINKING; /* Философ перестал есть */
test(LEFT); /* Проверить, может ли есть сосед слева */
test(RIGHT): /* Проверить, может ли есть сосед справа */
up(&mutex): /* Выход из критической области */
}
void test(i) /* i - номер философа, от 0 до N-1*/
{
if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) { state [i] = EATING;
up(&s[i]); } }
В программе используется массив семафоров, по одному на философа, чтобы блокировать голодных философов, если их вилки заняты. Обратите внимание, что каждый процесс запускает процедуру philosopher в качестве своей основной программы, но остальные процедуры take_forks, put_forks и test являются обычными процедурами, а не отдельными процессами.
Проблема читателей и писателей
Проблема обедающих философов полезна для моделирования процессов, соревнующихся за монопольный доступ к ограниченному количеству ресурсов, например к устройствам ввода-вывода. Другой известной задачей является проблема читателей и писателей , моделирующая доступ к базе данных. Представьте себе базу данных бронирования билетов на самолет, к которой пытается получить доступ множество процессов. Можно разрешить одновременное считывание данных из базы, но если процесс записывает информацию в базу, доступ остальных процессов должен быть прекращен, даже доступ на чтение. Как запрограммировать читателей и писателей? Одно из решений представлено в листинге 2.12.
Листинг 2.12. Решение проблемы читателей и писателей
typedef int semaphore; /* Воспользуйтесь своим воображением */
semaphore mutex = 1; /* Контроль доступа к rс */
semaphore db = 1: /* Контроль доступа к базе данных */
int rс = 0; /* Количество процессов, читающих или желающих читать */
void reader(void) {
while (TRUE) { Повторять до бесконечности */
down(&mutex) ; /* Получение монопольного доступа к гс */
гс = rc+1; /* Одним читающим процессом больше */
if (гс ==1) down(&db); /* Если этот читающий процесс - первый... */
up(&mutex); /* Отказ от монопольного доступа к гс */
read_data_base(); /* Доступ к данным */
down( &mutex ); /* Получение монопольного доступа к гс */
rc = rc-1 ; /* Одним читающим процессом меньше */
if (rc == 0) up(&db); /* Если этот читающий процесс - последний..
up (&mutex); /* Отказ от монопольного доступа к гс */
use_data_read (); /* Вне критической области */
} }
void writer (void)
{
while (TRUE) {
think_up_data (); /* Вне критической области */
down(&db); /* Получение монопольного доступа */
write_data_base();/* Запись данных */
up(&db); /* Отказ от монопольного доступа */
} }
Первый читающий процесс выполняет операцию down на семафоре db, чтобы получить доступ к базе. Последующие читатели просто увеличивают значение счетчика rс. По мере ухода читателей из базы значение счетчика уменьшается, и последний читающий процесс выполняет на семафоре db операцию up, позволяя блокированному пишущему процессу получить доступ к базе.
В этом решении один момент требует комментариев. Представьте, что в то время как один читатель уже пользуется базой, другой читатель запрашивает доступ к базе. Доступ разрешается, поскольку читающие процессы друг другу не мешают. Доступ разрешается и третьему, и последующим читателям.
Затем доступ запрашивает пишущий процесс. Запрос отклонен, поскольку пишущим процессам необходим монопольный доступ, и пишущий процесс приостанавливается. Пока в базе есть хотя бы один активный читающий процесс, доступ остальным читателям разрешается, а они все приходят и приходят. Если, предположим, новый читающий процесс запрашивает доступ каждые 2 с, а провести в базе ему надо 5 с, то пишущий процесс никогда в базу не попадет.
Чтобы избежать такой ситуации, нужно немного изменить программу: если пишущий процесс ждет доступа к базе, новый читающий процесс доступа не получает, а становится в очередь за пишущим процессом. Теперь пишущему процессу нужно подождать, пока базу покинут уже находящиеся в ней читающие процессы, но не нужно пропускать вперед читающие процессы, пришедшие к базе после него. Недостаток этого решения заключается в снижении производительности, вызванном уменьшением конкуренции. В [78] представлено решение, в котором пишущим процессам предоставляется более высокий приоритет.
Проблема спящего брадобрея
Действие еще одной классической проблемной ситуации межпроцессного взаимодействия разворачивается в парикмахерской. В парикмахерской есть один брадобрей, его кресло и п стульев для посетителей. Если желающих воспользоваться его услугами нет, брадобрей сидит в своем кресле и спит . Если в парикмахерскую приходит клиент, он должен разбудить брадобрея. Если клиент приходит и видит, что брадобрей занят, он либо садится на стул (если есть место), либо уходит (если места нет). Необходимо запрограммировать брадобрея и посетителей так, чтобы избежать состояния состязания. У этой задачи существует много аналогов в сфере массового обслуживания, например информационная служба, обрабатывающая одновременно ограниченное количество запросов, с компьютеризированной системой ожидания для запросов.
В предлагаемом решении используются три семафора: customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается — он уже не ждет); barbers, количество брадобреев (0 или 1), простаивающих в ожидании клиента, и mutex для реализации взаимного исключения. Также используется переменная waiting, предназначенная для подсчета ожидающих посетителей.
Она является копией переменной customers. Присутствие в программе этой переменной связано с тем фактом, что прочитать текущее значение семафора невозможно. В этом решении посетитель, заглядывающий в парикмахерскую, должен сосчитать количество ожидающих посетителей. Если посетителей меньше, чем стульев, новый посетитель остается, в противном случае он уходит.
Решение представлено в листинге 2.13. Когда брадобрей приходит утром на работу, он выполняет процедуру barber, блокируясь на семафоре customers, поскольку значение семафора равно 0. Затем брадобрей засыпает и спит, пока не придет первый клиент.
Листинг 2.13. Решение проблемы спящего брадобрея
#define CHAIRS 5 /* Количество стульев для посетителей */
typedef int semaphore; /* Догадайтесь сами */
semaphore customers = 0; /* Количество ожидающих посетителей */
semaphore barbers = 0; /* Количество брадобреев, ждущих клиентов */
semaphore mutex = 1; /* Для взаимного исключения */
int waiting = 0; /* Ожидающие (не обслуживаемые) посетители */
void barber(void) {
while (TRUE) {
down(&customers); /* Если посетителей нет, уйти в состояние ожидания */
down(&mutex); /* Запрос доступа к waiting */
waiting = waiting - 1; /* Уменьшение числа ожидающих посетителей */
up(&barbers); /* Один брадобрей готов к работе */
up(&mutex) ; /* Отказ от доступа к waiting */
cut_hair (); /* Клиента обслуживают (вне критической области)*/
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
