Тема 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. Как решается задача читателей и писателей при помощи семафоров?