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

Основная идея всех этих подходов в том, чтобыблокировать ожидающий процесс, вместо того, чтобы оставлять егов состоянии активного ожидания, а затем, при наступлениивозможности использования нужного ресурса, разблокировать одиниз ранее заблокированных процессов. Для этого, однако, требуетсяопределенная поддержка со стороны ОС, так как именно в ееведении находится переключение состояний процессов.2.1.4 СемафорыПервый из таких подходов был предложен Дейкстрой в 1965 г.Дейкстра предложил новый тип данных, именуемый семафором.Семафор представляет собой переменную целого типа, над которой18определены две операции: down(P) и up(V).1 Операция downпроверяет значение семафора, и если оно больше нуля, тоуменьшает его на 1.

Если же это не так, процесс блокируется,причем операция down считается незавершенной. Важно отметить,что вся операция является неделимой, т.е. проверка значения, егоуменьшение и, возможно, блокирование процесса производятся какодно атомарное действие, которое не может быть прервано.Операция up увеличивает значение семафора на 1. При этом, если всистеме присутствуют процессы, блокированные ранее привыполнении down на этом семафоре, ОС разблокирует один из них стем, чтобы он завершил выполнение операции down, т.е.

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

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

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

Положив N = 1, получимреализацию взаимного исключения. Семафор,начальное (имаксимальное) значение которого равно 1, называется двоичнымсемафором (так как имеет только 2 состояния: 0 и 1). ИспользованиеОригинальные обозначения P и V, данные Дейкстрой и получившие широкоераспространение в литературе, являются сокращениями голландских слов proberen – проверитьи verhogen – увеличить. В англоязычной литературе общепринятыми являются такжеследующие названия операций над семафором: wait, test или lock (аналоги down) и post, unlockили signal (аналоги up).119двоичного семафора для организации взаимного исключенияпроиллюстрировано на Рис.

5.процесс 1int semaphore;…down(semaphore);/*критическая секцияпроцесса 1 */…up(semaphore);…процесс 2int semaphore;…down(semaphore);/*критическая секцияпроцесса 2 */…up(semaphore);…Рис. 5 Взаимное исключение с использованием семафораСемафорыпредставляютсобоймощноесредствосинхронизации, однако программирование с использованиемсемафоров является достаточно тяжелой задачей, причем незаметнаяна первый взгляд логическая ошибка может привести к образованиютупиковых ситуаций или нарушению условий синхронизации.С целью облегчить написание корректных программ былипредложены более высокоуровневые средства синхронизации,которые мы рассмотрим далее.2.1.5 МониторыИдея монитора была впервые сформулирована в 1974 г.Хоаром. В отличие от других средств, монитор представляет собойязыковую конструкцию, т.е. некоторое средство, предоставляемоеязыком программирования и поддерживаемое компилятором.Монитор представляет собой совокупность процедур и структурданных, объединенных в программный модуль специального типа.Постулируются три основных свойства монитора:1.

Структуры данных, входящие в монитор, могут бытьдоступны только для процедур, входящих в этотмонитор (таким образом, монитор представляет собойнекоторый аналог объекта в объектно-ориентированныхязыках и реализует инкапсуляцию данных)2. Процесс «входит» в монитор путем вызова одной из егопроцедур3. В любой момент времени внутри монитора можетнаходиться не более одного процесса. Если процесспытается попасть в монитор, в котором уже находитсядругой процесс, он блокируется.

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

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

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

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

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

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

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