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

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

Для организации взаимного исключения на многопроцессорной системе с общей памятью могут использоваться специальные машинные инструкции. Примером такой инструкции может служить TSL – test and set lock, реализующая чтение ячейки памяти и запись нового значения в ту же ячейку как единую операцию. При этом гарантируется, что совокупность операций чтения и записи ячейки памяти является неделимой, т.е. доступ к ячейке памяти со стороны других процессоров блокируется на все время исполнения инструкции. Вариацией этой идеи является специальная инструкция exchange, которая меняет местами содержимое регистра и ячейки памяти. Здесь опять гарантируется, что на все время выполнения инструкции доступ к ячейке памяти блокируется.

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

3.1.2Алгоритм Петерсона.

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

Алгоритм Петерсона для случая 2х процессов представлен на Рис. 4.

Рис. 4 Алгоритм Петерсона

Элементы массива flag символизируют собой желание соответствующего процесса попасть в критическую секцию. Каждый из процессов видит все элементы массива flag, но модифицирует только «свой» элемент. Переменная turn устанавливает очередность прохождения критической секции при обоюдном желании процессов вступить в нее. Благодаря тому, что каждый из процессов прежде всего устанавливает флаг очередности в пользу другого процесса, исключается ситуация «монополизации» ресурса одним из процессов и вечного блокирования второго.

3.1.3Активное ожидание.

Общим недостатком рассмотренных выше решений является то, что процесс, желающий получить доступ к занятому ресурсу, блокируется в состоянии так называемого активного ожидания (в англоязычной литературе – busy waiting), т.е. в цикле постоянно проверяет, не наступило ли условие, при котором он сможет войти в критическую секцию. Использование активного ожидания приводит к бесполезному расходованию процессорного времени и как следствие, снижению общей производительности системы. Кроме того, при некоторых стратегиях планирования времени ЦП в целом корректный алгоритм с активным ожиданием может привести к тупику. Примером может служить стратегия планирования с приоритетами, когда процесс, имеющий больший приоритет, загружается на выполнение и переходит в состояние активного ожидания, в то время как процесс с меньшим приоритетом захватил необходимый ресурс, но был выгружен до того, как освободил его. Поскольку процесс с большим приоритетом не блокирован, а готов к продолжению выполнения, переключение процессов не происходит, и процесс, владеющий ресурсом, никогда не сможет его освободить.

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

3.1.4Семафоры.

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

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

Рис. 5 Взаимное исключение с использованием семафора

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

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

3.1.5Мониторы.

Идея монитора была впервые сформулирована в 1974 г. Хоаром. В отличие от других средств, монитор представляет собой языковую конструкцию, т.е. некоторое средство, предоставляемое языком программирования и поддерживаемое компилятором. Монитор представляет собой совокупность процедур и структур данных, объединенных в программный модуль специального типа. Постулируются три основных свойства монитора:

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

2. Процесс «входит» в монитор путем вызова одной из его процедур

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

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

Дополнительная синхронизация: переменные-условия.

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

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

3.1.6Обмен сообщениями.

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

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

send(destination, message)