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

Поскольку организация взаимного исключения в данномслучае возлагается на компилятор, количество программныхошибок, связанных с организацией взаимного исключения, сводитсяк минимуму.Дополнительная синхронизация: переменные-условия.Помимо обычных структур данных, мониторы могут включатьв себя специальные переменные-условия, на которых определеныоперации wait и signal.

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

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

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

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

Мониторы реализованы внекоторых языках программирования, таких как Concurrent Euclid,Concurrent Pascal, Modula-2, Modula-3, однако эти языки не слишкомраспространены.3.1.6 Обмен сообщениями.Общей проблемой и для мониторов, и для семафоров являетсято, что их реализация существенно опирается на предположение, чтомы имеем дело либо с однопроцессорной системой, либо смногопроцессорной системой, где все процессоры имеют доступ кобщей памяти. Однако в случае распределенной системы, гдекаждый процессор имеет прямой доступ только к своей памяти,такие средства не подходят.

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

Рассмотрим общую концепцию обмена сообщениями.Основная функциональность реализуется двумя примитивами,реализующими, соответственно, посылку и прием сообщения:send(destination, message)receive(source, message)Как и семафоры, и в отличие от мониторов, эти примитивыявляются системными вызовами, а не конструкциями языка.Рассмотрим основные особенности, которыми может обладатьта или иная система обмена сообщениями.Синхронизация.Сам смысл обмена сообщениями предполагает определеннуюсинхронизацию между процессом-отправителем и процессомполучателем, так как сообщение не может быть получено до того,как оно послано.

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

Для операции receive подобная ситуация возникает,когда эта операция вызвана раньше, чем сообщение было послано –в этом случае она может либо блокироваться до получениясообщения, либо возвращать управление сразу же.В зависимости от целей использования механизма сообщениймогут быть полезны различные комбинации этих условий: Блокирующий send и блокирующий receive – эта схемаизвестна под названием «схемы рандеву». Она нетребует буферизации сообщений и часто используетсядля синхронизации процессов Неблокирующий send и блокирующий receive – такаясхема очень распространена в системах клиент/сервер:серверный процесс блокируется в ожидании очередногозапроса для обработки, в то время как клиент,23пославший запрос серверу, может продолжатьвыполняться, не ожидая окончания обработки своегозапроса Также весьма распространена схема, когда обе операцииявляются неблокирующими – в этом случае обапроцесса могут продолжать выполнение, не дожидаясьокончания коммуникацииВажно понимать, что в случае, если send являетсянеблокирующим, процесс-отправитель не может знать, получено лиего сообщение.

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

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

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

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

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

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

Каждый изних ведет себя независимо от других, однако вилок запасено ровностолько, сколько философов, хотя для еды каждому из них нужнодве. Таким образом, философы должны совместно использовать25имеющиеся у них вилки (ресурсы). Задача состоит в том, чтобынайти алгоритм, который позволит философам организовать доступк вилкам таким образом, чтобы каждый имел возможностьнасытиться, и никто не умер с голоду.Рассмотрим простейшее решение, использующее семафоры.Когда один из философов хочет есть, он берет вилку слева от себя,если она в наличии, а затем - вилку справа от себя. Закончив есть, онвозвращает обе вилки на свои места. Данный алгоритм может бытьпредставлен следующим способом:#define N 5/* число философов*/void philosopher (int i)до 4*//* i – номер философа от 0{while (TRUE){think();/*философ думает*/take_fork(i);/*берет левую вилку*/take_fork((i+1)%N);/*берет правую вилку*/eat();/*ест*/put_fork(i);вилку*//*кладет обратно левуюput_fork((i+1)%N);правую вилку *//*кладетобратно}}Функция take_fork() описывает поведение философа по захватувилки: он ждет, пока указанная вилка не освободится, и забирает ее.На первый взгляд, все просто, однако, данное решение можетпривести к тупиковой ситуации.