Н.В. Вдовикина, А.В. Казунин, И.В. Машечкин, А.Н. Терехин - Системное программное обеспечение - взаимодействие процессов (2002), страница 4

receive(source, message)

Как и семафоры, и в отличие от мониторов, эти примитивы являются системными вызовами, а не конструкциями языка.

Рассмотрим основные особенности, которыми может обладать та или иная система обмена сообщениями.

Синхронизация.

Сам смысл обмена сообщениями предполагает определенную синхронизацию между процессом-отправителем и процессом-получателем, так как сообщение не может быть получено до того, как оно послано. Возникает вопрос, что происходит, если один процесс хочет получить сообщение, а другой его не отослал, и наоборот, если один процесс отсылает сообщение, а другой не собирается его получать. Здесь есть две возможности. Как операция посылки сообщения, так операция приема могут быть блокирующими и неблокирующими. Для операции send это означает, что либо процесс-отправитель может блокироваться до тех пор, пока получатель не вызовет receive, либо выполнение процесса может продолжаться далее независимо от наличия получателя. Для операции receive подобная ситуация возникает, когда эта операция вызвана раньше, чем сообщение было послано – в этом случае она может либо блокироваться до получения сообщения, либо возвращать управление сразу же.

В зависимости от целей использования механизма сообщений могут быть полезны различные комбинации этих условий:

• Блокирующий send и блокирующий receive – эта схема известна под названием «схемы рандеву». Она не требует буферизации сообщений и часто используется для синхронизации процессов

• Неблокирующий send и блокирующий receive – такая схема очень распространена в системах клиент/сервер: серверный процесс блокируется в ожидании очередного запроса для обработки, в то время как клиент, пославший запрос серверу, может продолжать выполняться, не ожидая окончания обработки своего запроса

• Также весьма распространена схема, когда обе операции являются неблокирующими – в этом случае оба процесса могут продолжать выполнение, не дожидаясь окончания коммуникации

Важно понимать, что в случае, если send является неблокирующим, процесс-отправитель не может знать, получено ли его сообщение. В этом случае, если требуется организовать гарантированную доставку сообщений, необходимо, чтобы процессы обменивались сообщениями-подтверждениями. Проблема потери сообщений встает также, если используется блокирующий receive – в этом случае процесс-получатель может оказаться заблокированным навечно. Поэтому в такую схему часто добавляется дополнительный примитив, позволяющий процессу-получателю проверить, есть ли для него сообщение, но не блокироваться, если его нет.

Адресация.

Другая важная проблема – организовать адресацию сообщений. Одно из решений – так называемая прямая адресация, при которой каждому из процессов присваивается некоторый идентификатор, и сообщения адресуются этим идентификаторам. При этом процесс-получатель может указать явно идентификатор отправителя, от которого он желает получить сообщение, либо получать сообщения от любого отправителя.

Иное решение заключается в том, чтобы предоставить специальную структуру данных – почтовый ящик, или очередь сообщений, которая по сути своей является буфером, рассчитанным на определенное количество сообщений. В этом случае сообщения адресуются не процессам, а почтовым ящикам, при этом один и тот же ящик может использоваться и несколькими отправителями, и несколькими получателями. Такая схема, называемая косвенной адресацией, обеспечивает дополнительную гибкость. Заметим, что связь между процессом-получателем или отправителем и почтовым ящиком может быть не только статической (т.е. раз навсегда заданной при создании ящика), но и динамической; в последнем случае для установления и разрыва связи используются дополнительные примитивы (connect/disconnect). Кроме того, поскольку почтовый ящик является самостоятельным объектом, необходимо наличие примитивов создания и удаления ящика (create/destroy).

Длина сообщения.

Немаловажным аспектом является формат сообщений. В той или иной системе могут допускаться как сообщения фиксированной длины, так и переменной. В последнем случае в заголовке сообщения, помимо отправителя и получателя, должна указываться длина сообщения. Выбор того или иного варианта зависит от целей, которые преследует система обмена сообщениями, и от предполагаемой архитектуры ВС. Так, если предполагается возможность передачи больших объемов данных, то сообщения с переменной длиной будут более гибким решением и позволят сократить накладные расходы на большое количество коротких сообщений, где значительную часть занимает сам заголовок. С другой стороны, если обмен происходит между процессами на одной машине, немаловажную роль играет эффективность. Здесь, возможно, было бы уместно ограничить длину сообщения, с тем, чтобы использовать для их передачи системные буфера с быстрым доступом.

В заключение отметим еще раз, что механизм обмена сообщениями является мощным и гибким средством синхронизации, пригодным для использования как на однопроцессорных системах и системах с общей памятью, так и в распределенных ВС. Однако, по сравнению с семафорами и мониторами, он, как правило, является менее быстрым.

3.2Классические задачи синхронизации процессов.

3.2.1«Обедающие философы»

Рассмотрим одну из классических задач, демонстрирующих проблему разделения доступа к критическим ресурсам – «задачу об обедающих философах» [2]. Данная задача иллюстрирует ситуацию, когда процессы конкурируют за право исключительного доступа к ограниченному числу ресурсов. Пять философов собираются за круглым столом, перед каждым из них стоит блюдо со спагетти, и между каждыми двумя соседями лежит вилка. Каждый из философов некоторое время размышляет, затем берет две вилки (одну в правую руку, другую в левую) и ест спагетти, затем кладет вилки обратно на стол и опять размышляет и так далее. Каждый из них ведет себя независимо от других, однако вилок запасено ровно столько, сколько философов, хотя для еды каждому из них нужно две. Таким образом, философы должны совместно использовать имеющиеся у них вилки (ресурсы). Задача состоит в том, чтобы найти алгоритм, который позволит философам организовать доступ к вилкам таким образом, чтобы каждый имел возможность насытиться, и никто не умер с голоду.

Рассмотрим простейшее решение, использующее семафоры. Когда один из философов хочет есть, он берет вилку слева от себя, если она в наличии, а затем - вилку справа от себя. Закончив есть, он возвращает обе вилки на свои места. Данный алгоритм может быть представлен следующим способом:

#define N 5 /* число философов*/

void philosopher (int i) /* i – номер философа от 0 до 4*/

{

while (TRUE)

{

think(); /*философ думает*/

take_fork(i); /*берет левую вилку*/

take_fork((i+1)%N); /*берет правую вилку*/

eat(); /*ест*/

put_fork(i); /*кладет обратно левую вилку*/

put_fork((i+1)%N); /* кладет обратно правую вилку */

}

}

Функция take_fork() описывает поведение философа по захвату вилки: он ждет, пока указанная вилка не освободится, и забирает ее.

На первый взгляд, все просто, однако, данное решение может привести к тупиковой ситуации. Что произойдет, если все философы захотят есть в одно и то же время? Каждый из них получит доступ к своей левой вилке и будет находиться в состоянии ожидания второй вилки до бесконечности.

Другим решением может быть алгоритм, который обеспечивает доступ к вилкам только четырем из пяти философов. Тогда всегда среди четырех философов по крайней мере один будет иметь доступ к двум вилкам. Данное решение не имеет тупиковой ситуации. Алгоритм решения может быть представлен следующим образом:

# define N 5 /* количество философов */

# define LEFT (i-1)%N /* номер легого соседа для i-ого философа */

# define RIGHT (i+1)%N /* номер правого соседа для i-ого философа*/

# 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[i] = HUNGRY; /*записываем, что i-ый философ голоден */

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]);

}

}

3.2.2Задача «читателей и писателей»

Другой классической задачей синхронизации доступа к ресурсам является задача «читателей и писателей» [2], иллюстрирующая широко распространенную модель совместного доступа к данным. Представьте себе ситуацию, например, в системе резервирования билетов, когда множество конкурирующих процессов хотят читать и обновлять одни и те же данные. Несколько процессов могут читать данные одновременно, но когда один процесс начинает записывать данные (обновлять базу данных проданных билетов), ни один другой процесс не должен иметь доступ к данным, даже для чтения. Возникает вопрос, как спланировать работу такой системы? Одно из решений представлено ниже:

typedef int semaphore; /* тип данных «семафор» */

semaphore mutex = 1; /* контроль за доступом к «rc» (разделямый ресурс) */

semaphore db = 1; /* контроль за доступом к базе данных */

int rc = 0; /* кол-во процессов читающих или пишущих */

void reader (void)

{

while (TRUE) /* бесконечный цикл */

{

down(&mutex); /* получить эксклюзивный доступ к «rc»*/

rc = rc + 1; /* еще одним читателем больше */

if (rc == 1) down(&db); /* если это первый читатель, нужно заблокировать эксклюзивный доступ к базе */

up(&mutex); /*освободить ресурс rc */

read_data_base(); /* доступ к данным */

down(&mutex); /*получить эксклюзивный доступ к «rc»*/

rc = rc - 1: /* теперь одним читателем меньше */

if (rc == 0) up(&db); /*если это был последний читатель, разблокировать эксклюзивный доступ к базе данных */

up(&mutex); /*освободить разделяемый ресурс rc */

use_data_read(); /* некритическая секция */

}

}

void writer (void)

{

while(TRUE) /* бесконечный цикл */

{

think_up_data(); /* некритическая секция */

down(&db); /* получить эксклюзивный доступ к данным*/

write_data_base(); /* записать данные */

up(&db); /* отдать эксклюзивный доступ */

}

}

В этом примере, первый процесс, обратившийся к базе данных по чтению, осуществляет операцию down() над семафором db, тем самым блокируя эксклюзивный доступ к базе, который нужен для записи. Число процессов, осуществляющих чтение в данный момент, определяется переменной rc (обратите внимание! Так как переменная rc является разделяемым ресурсом – ее изменяют все процессы, обращающиеся к базе данных по чтению – то доступ к ней охраняется семафором mutex). Когда читающий процесс заканчивает свою работу, он уменьшает значение rc на единицу. Если он является последним читателем, он также совершает операцию up над семафором db, тем самым разрешая заблокированному писателю, если таковой имелся, получить эксклюзивный доступ к базе для записи.

Надо заметить, что приведенный алгоритм дает преимущество при доступе к базе данных процессам-читателям, так как процесс, ожидающий доступа по записи, будет ждать до тех пор, пока все читающие процессы не окончат работу, и если в это время появляется новый читающий процесс, он тоже беспрепятственно получит доступ. Это может привести к неприятной ситуации в том случае, если в фазе, когда ресурс доступен по чтению, и имеется ожидающий процесс-писатель, будут появляться новые и новые читающие процессы. К примеру, представим себе, что новый читающий процесс появляется каждую секунду и чтение длится в среднем 2 секунды. Количество читающих процессов в этом случае будет приблизительно константным, и процесс-писатель никогда не получит доступ к данным.

Чтобы этого избежать, можно модифицировать алгоритм таким образом, чтобы в случае, если имеется хотя бы один ожидающий процесс-писатель, новые процессы-читатели не получали доступа к ресурсу, а ожидали, когда процесс-писатель обновит данные. В этой ситуации процесс-писатель должен будет ожидать окончания работы с ресурсом только тех читателей, которые получили доступ раньше, чем он его запросил. Однако, обратная сторона данного решения в том, что оно несколько снижает производительность процессов-читателей, так как вынуждает их ждать в тот момент, когда ресурс не занят в эксклюзивном режиме.

3.2.3Задача о «спящем парикмахере»

Еще одна классическая задача на синхронизацию процессов – это так называемая «задача о спящем парикмахере» [2]. Рассмотрим парикмахерскую, в которой работает один парикмахер, имеется одно кресло для стрижки и несколько кресел в приемной для посетителей, ожидающих своей очереди. Если в парикмахерской нет посетителей, парикмахер засыпает прямо на своем рабочем месте. Появившийся посетитель должен его разбудить, в результате чего парикмахер приступает к работе. Если в процессе стрижки появляются новые посетители, они должны либо подождать своей очереди, либо покинуть парикмахерскую, если в приемной нет свободного кресла для ожидания. Задача состоит в том, чтобы корректно запрограммировать поведение парикмахера и посетителей.

Одно из возможных решений этой задачи представлено ниже. Процедура barber() описывает поведение парикмахера (она включает в себя бесконечный цикл – ожидание клиентов и стрижку). Процедура customer() описывает поведение посетителя. Несмотря на кажущуюся простоту задачи, понадобится целых 3 семафора: customers – подсчитывает количество посетителей, ожидающих в очереди, barbers – обозначает количество свободных парикмахеров (в случае одного парикмахера его значения либо 0, либо 1) и mutex – используется для синхронизации доступа к разделяемой переменной waiting. Переменная waiting, как и семафор customers, содержит количество посетителей, ожидающих в очереди, она используется в программе для того, чтобы иметь возможность проверить, имеется ли свободное кресло для ожидания, и при этом не заблокировать процесс, если кресла не окажется. Заметим, что как и в предыдущем примере, эта переменная является разделяемым ресурсом, и доступ к ней охраняется семафором mutex. Это необходимо, так как для обычной переменной, в отличие от семафора, чтение и последующее изменение не являются неделимой операцией.

#define CHAIRS 5