Н.В. Вдовикина, И.В. Машечкин, А.Н. Терехин, А.Н. Томилин - Операционные системы - взаимодействие процессов (2008), страница 6

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

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

раз навсегдазаданной при создании ящика), но и динамической; в последнемслучае для установленияи разрыва связи используютсядополнительные примитивы (connect/disconnect). Кроме того,поскольку почтовый ящик является самостоятельным объектом,необходимо наличие примитивов создания и удаления ящика(create/destroy).Длина сообщенияНемаловажным аспектом является формат сообщений.

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

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

Каждый изфилософов некоторое время размышляет, затем берет две вилки(одну в правую руку, другую в левую) и ест спагетти, затем кладетвилки обратно на стол и опять размышляет и так далее. Каждый изних ведет себя независимо от других, однако вилок запасено ровностолько, сколько философов, хотя для еды каждому из них нужнодве. Таким образом, философы должны совместно использоватьимеющиеся у них вилки (ресурсы). Задача состоит в том, чтобынайти алгоритм, который позволит философам организовать доступк вилкам таким образом, чтобы каждый имел возможностьнасытиться, и никто не умер с голоду.Рассмотрим простейшее решение, использующее семафоры.Когда один из философов хочет есть, он берет вилку слева от себя,если она в наличии, а затем - вилку справа от себя. Закончив есть, онвозвращает обе вилки на свои места. Данный алгоритм может бытьпредставлен следующим способом:#define N 5/* число философов*/void philosopher (int i)до 4*//* i – номер философа от 025{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;/* семафор для критической секции */26semaphore 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);/* проверить может ли правый сосед сейчас есть*/27up(&mutex);/* выход из критической секции */}void test(i)/* i : номер философа от 0 до N-1 */{if (state[i] == HUNGRY && state[LEFT] != EATING &&state[RIGHT] != EATING){state[i] = EATING;up (&s[i]);}}2.2.2 Задача «читателей и писателей»Другой классической задачей синхронизации доступа кресурсам является задача «читателей и писателей» [2],иллюстрирующая широко распространенную модель совместногодоступа к данным.

Представьте себе ситуацию, например, в системерезервирования билетов, когда множество конкурирующихпроцессов хотят читать и обновлять одни и те же данные. Несколькопроцессов могут читать данные одновременно, но когда одинпроцесс начинает записывать данные (обновлять базу данныхпроданных билетов), ни один другой процесс не должен иметьдоступ к данным, даже для чтения.

Возникает вопрос, какспланировать работу такой системы? Одно из решений представленониже:typedef int semaphore;/* тип данных «семафор» */semaphore mutex = 1;/* контроль за доступом к «rc»(разделямый ресурс) */semaphore db = 1;/* контроль за доступом к базеданных */int rc = 0;/* кол-во процессов читающих илипишущих */void reader (void){while (TRUE)/* бесконечный цикл */{28down(&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, тем29самым блокируя эксклюзивный доступ к базе, который нужен длязаписи.

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

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