Тема 10. Классические проблемы межпроцессного взаимодействия
Проблема производителя и потребителя
Проблема производителя и потребителя, также известная как проблема ограниченного буфера, состоит в следующем. Два процесса совместно используют буфер ограниченного размера. Один из них, производитель, помещает данные в этот буфер, а другой, потребитель, считывает их оттуда.
Условия синхронизации:
- производитель должен ждать, если буфер полон;
- потребитель должен ждать, если буфер пуст;
- операции с буфером – критические секции, т.е. работать с буфером может только один процесс.
Ниже приведено решение проблемы производителя и потребителя с использованием семафоров.
#define N 100 /* количество сегментов в буфере */
typedef int semaphore;
semaphore mutex = 1; /* контроль доступа в КС */
semaphore empty = N; /* число пустых сегментов буфера */
semaphore full = 0; /* число полных сегментов буфера */
void producer(void)
{
int item;
while (TRUE) {
item = produce_item();/*создать данные, помещаемые в буфер */
wait(&empty); /* уменьшить счетчик пустых сегментов буфера */
wait(&mutex); /* вход в критическую область */
insert_item(item); /* поместить в буфер новый элемент */
signal(&mutex); /* выход из критической области */
signal(full); /*увеличить счетчик полных сегментов буфера*/
}
}
void consumer(void);
{
int item;
while (TRUE) {
wait(&full); /* уменьшить число полных сегментов буфера */
wait(&mutex); /* вход в критическую область */
item = remove_item(); /* удалить элемент из буфера */
signal(&mutex); /* выход из критичекой области */
signal(&empty); /*увеличить счетчик пустых сегментов буфера*/
consume_item(item); /* обработка элемента */
}
}
Здесь семафор mutex используется для реализации взаимного исключения, то есть для исключения одновременного обращения к буферу двух процессов. Остальные семафоры использованы для синхронизации. Семафоры full и empty необходимы, чтобы гарантировать, что производитель прекращает работу, когда буфер полон, а потребитель прекращает работу, когда буфер пуст.
Можно обобщить задачу на случай m производителей и n потребителей.
Задача о читателях и писателях
Это одна из задач синхронизации, описывающих доступ процессов к разделяемой базе данных. Процессы подразделяются на две категории: читатели никогда не модифицируют базу данных; писатели читают и модифицируют базу данных.
Правила синхронизации следующие:
- читатели могут работать параллельно, если никто из писателей не модифицирует базу данных;
- модифицировать базу может только один писатель и когда никто не читает из базы данных;
- переменные состояния может просматривать и менять только один процесс;
Ниже приведена схема решения данной задачи.
| Читатель | Писатель |
| Ждать, пока закончит работу писатель (если кто-то пишет) | Ждать, пока закончат работу все читатели (если кто-то читает) |
| Читать из базы данных | Модифицировать базу данных |
| При необходимости разбудить ожидающего писателя | При необходимости разбудить ожидающих читателей |
Задача об обедающих философах
Моделирует использование общих ресурсов несколькими процессами. Суть задачи такова. Пять философов сидят за круглым столом. На столе пять тарелок с макаронами и пять вилок по одной между тарелками. Предполагается, что есть надо двумя вилками сразу. Поведение каждого из философов таково: думает – хочет есть (пытается взять две вилки) – ест.
Ограничения:
- философ должен ждать, пока не освободятся две вилки рядом с ним;
- модификация переменных состояния должно выполняться в критической секции.
Задача о спящем парикмахере
Моделирует обслуживание потока запросов по очереди. Клиенты приходят в парикмахерскую и встают в очередь. Парикмахер приглашает и обслуживает клиентов по одному.
Ограничения:
- клиент должен ждать, если есть очередь или парикмахер занят обслуживанием;
- парикмахер спит, если нет клиентов;
- первый клиент будит парикмахера.
Задача о железнодорожном перегоне
Моделирует обмен по полудуплексному каналу связи. Поезда движутся по одноколейному участку дороги в двух направлениях. Необходимо организовать движение таким образом, чтобы избежать столкновения.
Ограничения:
- поезд, подходящий к одноколейному участку дороги должен остановиться, если по нему движется поезд во встречном направлении;
- модификация переменных состояния должно выполняться в критической секции.
Вопросы для самоконтроля
1. Приведите решение задачи производителей и потребителей при помощи семафоров.
2. Какие условия обычно связаны с задачей читателей и писателей?
3. Как решается задача читателей и писателей при помощи семафоров?