Билеты (Graur) (1114774), страница 16
Текст из файла (страница 16)
Положив N = 1, получим реализацию взаимногоисключения. Семафор, начальное (и максимальное) значение которого равно 1,называется двоичным семафором (так как имеет только 2 состояния: 0 и 1).Использование двоичного семафора для организации взаимного исключенияпроиллюстрировано на Рис. 6.процесс 1int semaphore;…down(semaphore);/*критическая секцияпроцесса 1 */…up(semaphore);…процесс 2int semaphore;…down(semaphore);/*критическая секцияпроцесса 2 */…up(semaphore);…Рис. 6 Взаимное исключение с использованием семафораСемафоры представляют собой мощное средство синхронизации, однакопрограммирование с использованием семафоров является достаточно тяжелойзадачей, причем незаметная на первый взгляд логическая ошибка может привести кобразованию тупиковых ситуаций или нарушению условий синхронизации.С целью облегчить написание корректных программ были предложены болеевысокоуровневые средства синхронизации, которые мы рассмотрим далее.Мониторы.Идея монитора была впервые сформулирована в 1974 г.
Хоаром. В отличие отдругих средств, монитор представляет собой языковую конструкцию, т.е. некотороесредство, предоставляемое языком программирования и поддерживаемоекомпилятором. Монитор представляет собой совокупность процедур и структурданных, объединенных в программный модуль специального типа. Постулируютсятри основных свойства монитора:1. Структуры данных, входящие в монитор, могут быть доступны толькодля процедур, входящих в этот монитор (таким образом, мониторпредставляет собой некоторый аналог объекта в объектноориентированных языках и реализует инкапсуляцию данных)2. Процесс «входит» в монитор путем вызова одной из его процедур3.
В любой момент времени внутри монитора может находиться не болееодного процесса. Если процесс пытается попасть в монитор, в которомуже находится другой процесс, он блокируется. Таким образом, чтобызащитить разделяемые структуры данных, их достаточно поместитьвнутрь монитора вместе с процедурами, представляющимикритические секции для их обработки.Подчеркнем,чтомониторпредставляетсобойконструкциюязыкапрограммирования, и следовательно, компилятору известно о том, что входящие внего процедуры и данные имеют особую семантику, поэтому первое условиеможет проверяться еще на этапе компиляции. Кроме того, код для процедурмонитора тоже может генерироваться особым образом, чтобы удовлетворялосьтретье условие.
Поскольку организация взаимного исключения в данном случаевозлагается на компилятор, количество программных ошибок, связанных сорганизацией взаимного исключения, сводится к минимуму.Дополнительная синхронизация: переменные-условия.Помимо обычных структур данных, мониторы могут включать в себя специальныепеременные-условия, на которых определены операции wait и signal. Онииспользуются для синхронизации. Если процесс, находящийся внутри монитора(т.е. исполняющий одну из его процедур), обнаруживает, что логически он неможет продолжать выполнение, пока не выполнится определенное условие(например, буфер для записи данных переполнился), он вызывает операцию waitнад определенной переменной-условием. При этом его дальнейшее выполнениеблокируется, и это позволяет другому процессу, ожидающему входа в монитор,попасть в него. В дальнейшем, если этот другой процесс произведет некоторыедействия, которые приведут к изменению обстоятельств (в нашем примере –считает часть данных из буфера), он должен вызвать для соответствующейпеременной-условия операцию signal, что позволит разблокировать ожидающийпроцесс.
Тонкость заключается в том, что разблокированный процесс, как и тот,кто его разблокировал, должен оказаться внутри монитора, но нахождение двухпроцессов внутри монитора одновременно невозможно по определению. Хоарпостулировал, что в этом случае процесс, вызвавший signal, приостанавливается.Хансен в своей модификации мониторов в 1975 г. предложил более простоедополнительное условие: вызов signal должен быть самым последним внутрипроцедуры монитора, чтобы процесс немедленно после его выполнения покинулмонитор. Заметим, что переменные-условия используются в мониторах не дляорганизации взаимного исключения (оно постулируется самим определениеммонитора), а для дополнительной синхронизации процессов.
В нашем примереразделяемый ресурс – буфер для чтения/записи охраняется от одновременногодоступа по чтению и по записи самим монитором, а переменная-условиепредохраняет пишущий процесс от затирания ранее записанных данных.Несомненным достоинством мониторов является то, что взаимное исключениездесь организуется автоматически, что существенно упрощает программирование иснижает вероятность ошибок. Недостатком же является то, что, как ужеговорилось, монитор – это языковая конструкция. Следовательно, если языкпрограммирования не содержит таких конструкций (а для большинствараспространенных языком это так и есть), программист не может еювоспользоваться.
В то же время семафоры, например, являются средством ОС, иесли соответствующая ОС поддерживает семафоры, программист может ихиспользовать независимо от того, на каком языке он пишет программы. Мониторыреализованы в некоторых языках программирования, таких как Concurrent Euclid,Concurrent Pascal, Modula-2, Modula-3, однако эти языки не слишкомраспространены.Обмен сообщениями.Общей проблемой и для мониторов, и для семафоров является то, что ихреализация существенно опирается на предположение, что мы имеем дело либо соднопроцессорной системой, либо с многопроцессорной системой, где всепроцессоры имеют доступ к общей памяти.
Однако в случае распределеннойсистемы, где каждый процессор имеет прямой доступ только к своей памяти, такиесредства не подходят. Более общим средством, решающим проблемусинхронизации как для однопроцессорных систем и систем с общей памятью, так идля распределенных, является обмен сообщениями.Обмен сообщениями представляет собой средство, которое может бытьиспользовано как для синхронизации, в частности для организации взаимногоисключения, так и для обмена информацией между взаимосвязанными процессами,выполняющими общую работу. Рассмотрим общую концепцию обменасообщениями. Основная функциональность реализуется двумя примитивами,реализующими, соответственно, посылку и прием сообщения:send(destination, message)receive(source, message)Как и семафоры, и в отличие от мониторов, эти примитивы являются системнымивызовами, а не конструкциями языка.Рассмотрим основные особенности, которыми может обладать та или иная системаобмена сообщениями.Синхронизация.Сам смысл обмена сообщениями предполагает определенную синхронизациюмежду процессом-отправителем и процессом-получателем, так как сообщение неможет быть получено до того, как оно послано.
Возникает вопрос, что происходит,если один процесс хочет получить сообщение, а другой его не отослал, и наоборот,если один процесс отсылает сообщение, а другой не собирается его получать. Здесьесть две возможности. Как операция посылки сообщения, так операция приемамогут быть блокирующими и неблокирующими. Для операции send этоозначает, что либо процесс-отправитель может блокироваться до тех пор, покаполучатель не вызовет receive, либо выполнение процесса может продолжатьсядалее независимо от наличия получателя.
Для операции receive подобнаяситуация возникает, когда эта операция вызвана раньше, чем сообщение былопослано – в этом случае она может либо блокироваться до получения сообщения,либо возвращать управление сразу же.В зависимости от целей использования механизма сообщений могут быть полезныразличные комбинации этих условий: Блокирующий send и блокирующий receive – эта схема известнапод названием «схемы рандеву». Она не требует буферизациисообщений и часто используется для синхронизации процессов Неблокирующий send и блокирующий receive – такая схемаочень распространена в системах клиент/сервер: серверный процессблокируется в ожидании очередного запроса для обработки, в товремя как клиент, пославший запрос серверу, может продолжатьвыполняться, не ожидая окончания обработки своего запроса Также весьма распространена схема, когда обе операции являютсянеблокирующими – в этом случае оба процесса могут продолжатьвыполнение, не дожидаясь окончания коммуникацииВажно понимать, что в случае, если send является неблокирующим, процессотправитель не может знать, получено ли его сообщение.
В этом случае, еслитребуется организовать гарантированную доставку сообщений, необходимо, чтобыпроцессы обменивались сообщениями-подтверждениями. Проблема потерисообщений встает также, если используется блокирующий receive – в этомслучае процесс-получатель может оказаться заблокированным навечно. Поэтому втакую схему часто добавляется дополнительный примитив, позволяющийпроцессу-получателю проверить, есть ли для него сообщение, но не блокироваться,если его нет.Адресация.Другая важная проблема – организовать адресацию сообщений. Одно из решений –так называемая прямая адресация, при которой каждому из процессовприсваивается некоторый идентификатор, и сообщения адресуются этимидентификаторам.
При этом процесс-получатель может указать явноидентификатор отправителя, от которого он желает получить сообщение, либополучать сообщения от любого отправителя.Иное решение заключается в том, чтобы предоставить специальную структуруданных – почтовый ящик, или очередь сообщений, которая по сути своейявляется буфером, рассчитанным на определенное количество сообщений.
В этомслучае сообщения адресуются не процессам, а почтовым ящикам, при этом один итот же ящик может использоваться и несколькими отправителями, и несколькимиполучателями. Такая схема, называемая косвенной адресацией, обеспечиваетдополнительную гибкость. Заметим, что связь между процессом-получателем илиотправителем и почтовым ящиком может быть не только статической (т.е. разнавсегда заданной при создании ящика), но и динамической; в последнем случаедля установления и разрыва связи используются дополнительные примитивы(connect/disconnect). Кроме того, поскольку почтовый ящик являетсясамостоятельным объектом, необходимо наличие примитивов создания и удаленияящика (create/destroy).Длина сообщения.Немаловажным аспектом является формат сообщений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
