Взаимное исключение
Причиной неправильной работы программ, показанных на рис.2.2, является то, что они обе совместно используют указатель конец и элемент, на который он указывает, т. е. происходит разделение этих переменных между двумя процессами. Для правильной работы первый и второй операторы присваивания в каждой программе не должны выполняться между исполнениями аналогичных операторов другой программы. Ясно, что существует некоторая особенность в том участке (интервале) каждой программы, который содержит эти операторы. Она заключается в требовании, чтобы два процесса не могли одновременно исполняться на этих интервалах. Дейкстра впервые предложил концепцию таких критических интервалов, каждый из которых содержит в себе требование взаимного исключения по отношению к конкретной переменной.
При написании взаимодействующих параллельных программ можно использовать такие конструкции языка, которые c каждым критическим интервалом связывают некоторую разделяемую переменную. Такая переменная описывается с помощью служебного слова shared. При программировании критического интервала осуществляется явное обращение к разделяемой переменной.
shared переменная
region переменная do оператор
Рис. 2.2. Неконтролируемый доступ к разделяемым переменным;
(а) -исполнение процессов, (б) - определение процессов.
Рис.2.3. Реализация взаимного исключения с помощью критических интервалов; (а) - исполнение процессов, (б) - определение процессов.
На рис.2.3 приведены программы управления очередью, в которых определены критические интервалы. Вообще говоря, критический интервал не является последовательностью операторов программы, он является последовательностью действий, которые выполняются этими операторами. Следовательно, несколько процессов, которые являются экземплярами выполнения одной и той же программы, могут выполнять критические интервалы, базирующиеся на одной и той же последовательности операторов программы. Так, из программы, изображенной на рис.2.4, можно образовать несколько процессов, которые будут осуществлять запись информации в базу.
Рис.2.4. Взаимное исключение конкурирующих программ ЗАПИСЬ.
данных, взаимно исключая друг друга. Когда некоторый процесс выполнил операторы, определяющие критический интервал, говорят, что процесс находится в критическом интервале независимо от того, исполняется он в данный момент или нет.
На критический интервал, связанный с переменной, разделяемой несколькими процессами, налагаются три требования:
1. В любой момент времени только один процесс может находиться внутри критического интервала.
2. Ни один процесс не может оставаться внутри критического интервала бесконечно долго.
3. Ни один процесс не должен ждать бесконечно долго входа в критический интервал. В частности, никакой процесс, бесконечно долго находящийся вне критического интервала (что допустимо), не может задерживать выполнение других процессов, ожидающих входа в критический интервал. Критические интервалы могут вкладываться друг в друга, например:
region x do begin ... region у do ... end
но, если это сделано недостаточно аккуратно, то может привести к нарушению требования 2. Если другой процесс выполняет
region y do begin ... region x do ... end
то процессы могут войти в свои внешние критические интервалы почти в одно и то же время и оказаться в состоянии, когда ни один из них не сможет войти в свой внутренний критический интервал.
Рис. 2.5. Первая неправильная реализация взаимного исключения.
Теперь, когда рассмотрены использование критических интервалов и требования, которым они должны удовлетворять, следует обсудить их реализацию. Любая реализация в конечном счете должна основываться на взаимном исключении, обеспечиваемом техническими средствами. Все ЭВМ имеют основную форму взаимного исключения, называемую блокированием памяти. Это средство запрещает одновременное исполнение двух команд, которые обращаются к одной и •ой же ячейке памяти. Если в этой ячейке памяти хранится значение разделяемой переменной, то во время исполнения данной команды получить доступ к ней может только один процесс. Блокирование памяти предотвращает одновременный доступ, но не предотвращает чередование доступов. Таким образом, если критические интервалы исчерпываются одной командой обращения к оперативной памяти, данного средства может быть достаточно для непосредственной реализации критических интервалов.
Если критические интервалы требуют более одного обращения к памяти, их все же можно реализовать, используя блокировку памяти. Переменные, чья целостность гарантируется блокировкой памяти, указывают, какой процесс может войти в свой критический интервал. Однако не так просто правильно установить и проверить эти переменные.
На рис.2.5 показана первая попытка. С каждым из процессов ПР1 и ПР2 связана переменная, которая может принимать значение true, когда процесс находится в критическом интервале, и false - в противном случае. Прежде чем войти в критический интервал, процесс ПР1 проверяет переменную вкринт2, чтобы убедиться, что доступ разрешен, и затем устанавливает вкринт1 в true, чтобы предотвратить вход процесса ПР2 в свой критический интервал. Причина, по которой эта программа может неправильно работать, состоит в том, что между проверкой вкринт2 процессом ПР1 и последующей установкой им вкринт1 параллельно выполняющийся процесс ПР2 , поняв, что вкринт1 имеет значение false, может установить вкринт2 в true и войти в свой критический интервал одновременно с процессом ПР1.
Можно усилить взаимное исключение, если в процессе-ПР1 выполнять проверку вкринт2 после установки вкринт1 в true и тем самым предотвращать вход ПР2 в свой критический интервал. Полученная в результате программа показана на рис. 2.6. К сожалению, она имеет недостатки. Процессы могут одновременно установить свои переменные в true и войти в бесконечный цикл. Это противоречит требованию, что ни один процесс не должен бесконечно долго ждать входа в свой критический интервал.
Пользуясь только блокировкой памяти, написать правильную реализацию критических интервалов очень трудно. Впервые решение было предложено Дж. Деккером. И его, более современные решения сложны и неэффективны, особенно когда они обобщаются с двух на n процессов, поэтому для реализации критических интервалов- требуется другой подход.
Рис.2.6. Вторая неправильная реализация взаимного исключения.
Вместо того, чтобы связывать с каждым процессом свою собственную переменную, можно со всем множеством критических интервалов связать одну переменную. Ее можно рассматривать как некоторый ключ. Вначале доступ к критическому интервалу открыт. Однако перед входом в свой критический интервал процесс забирает ключ и тем самым блокирует другие процессы. Покидая критический интервал, процесс открывает доступ, возвращая ключ на место. Если процесс, который хочет войти в свой критический интервал, видит отсутствие ключа, он ждет, пока процесс, имеющий ключ, не вернет его. Таким образом каждый процесс, входящий в критический интервал, должен вначале проверить, доступен ли ключ, и если это так, то сделать его недоступным для других процессов. Эти два действия должны быть неделимы, чтобы два или более процессов не могли одновременно получить доступ к ключу. Рассмотренная выше аппаратная блокировка памяти обеспечивает неделимость любого отдельного обращения к памяти, но не пары различных обращений.
Другим аппаратным средством реализации взаимного исключения являются неделимые команды, осуществляющие проверку переменной (или ключа) и присваивание ей значения. Примером является команда проверить-и-установить (TS) в ЭВМ IBM/360. В одном цикле обращения к памяти она выбирает разряд из некоторого байта памяти, помещает его в признак результата и записывает в байт фиксированное число (все единицы). Можно считать, что TS - это процедура-функция, которая имеет один логический параметр (разряд памяти) и которая вырабатывает логическое значение (в признаке результата). Таким образом, TS(x) вырабатывает признак результата на базе значения х и устанавливает х в false. Между двумя действиями командыTS нe может выполняться никакая другая операция, например проверка х другим процессом. Чтобы использовать TS, свяжем с критическим интервалом логическую переменную s, которая имеет значение true, если ни один процесс не находится в данном критическом интервале. Каждый из n конкурирующих процессов ПРi имеет локальную переменную разрешено, которая равна true, если ПРi разрешено войти в критический интервал.
На рис.2.7 приведена параллельная программа для n процессов. Прежде чем войти в свой критический интервал, процесс PRi проверяет переменную s, выполняя для этого команду TS Если в критическом интервале нет ни одного процесса, то s равна true и разрешено принимает значение true, что позволяет процессу ПРi продолжить исполнение. После того как ПРi покинет критический интервал, он устанавливает s в true, позволяя другому процессу (или даже
Рис.2.7. Взаимное исключение, использующее команду проверить-и-уста-новить.
самому себе) войти в критический интервал. С другой стороны, если некоторый процесс ПPk находится в критическом интервале, s равна false и процесс ПРi в цикле проверяет s до тех пор, пока ПР1k не установит s в true. Независимо от того, имела ли s значение false перед проверкой, присваивание ей значения false означает, что в соответствующий критический интервал нельзя входить либо потому, что ПРi только что вошел в него, либо потому, что еще до этого вход в критический интервал был запрещен.
Аппаратную блокировку памяти и проверку-и-установку можно использовать для реализации критических интервалов, хотя при этом и возникают некоторые трудности. Например, если процесс, использующий программу, приведенную на рис. 2.7, исполняется медленно, то он может никогда не добраться до проверки переменной s, если всякий раз перед этим в критический интервал входит некоторый более быстрый процесс и устанавливает s в false. Этой ситуации можно избежать, используя несколько переменных. Однако если имеется более двух процессов, то решение становится довольно сложным,
Даже если упомянутые выше проблемы решены, существуют серьезные препятствия для использования этих двух механизмов, Реализация критических интервалов с помощью блокировки памяти или использования команды проверить-и-установить обеспечивает взаимное исключение за счет того, что процессы вынуждены находиться в циклах ожидания, впустую потребляя ресурсы. Такое состояние называется активным ожиданием. В этом случае непроизводительно используется не только процессор, но и ресурс, так как процесс, находящийся в состоянии ожидания, может удерживать тот самый ресурс, крайне необходимый процессу, завершения которого ждут. Более того, проверка, можно ли войти в критический интервал, выполняется конкурирующими процессами, в то время как правильнее было бы возложить ее на операционную систему.
Чтобы избавиться от перечисленных трудностей, Дейкстра ввел две операции, названные Р и V. Эти операции работают с переменной, которая совместно используется параллельными процессами и называется семафором, по названию устройства, регулирующего движение поездов на участке железной дороги. В наиболее простом варианте семафор может принимать два значения. Представление его значений двоичными числами 1 или 0, а не с помощью true и false, позволяет более естественно связать большую величину 1 c открытым семафором, который разрешает поезду двигатьcя, а меньшую величину 0 с закрытым семафором, которое запрещает движение. Семафор такого типа обычно называют двоичным.
С каждым семафором связывается список (не обязательно очередь) процессов, ожидающих разрешения пройти семафор. Операционная система может выполнять три действия над процессами. Она может назначить для исполнения готовый процесс. Она может заблокировать исполняющийся процесс и поместить его в список, связанный с конкретным семафором. Она может деблокировать процесс, тем самым переводя его в готовое к исполнению состояние и позволяя ему когда-нибудь возобновить исполнение. Находясь в списке заблокированных, ожидающий процесс не проверяет семафор непрерывно, как в случае активного ожидания. Вместо него на процессоре может исполняться другой процесс.
Операции Р и V выполняются операционной системой в ответ на запрос, выданный некоторым процессом и содержащий имя семафора в качестве параметра. По операциям Р V выполняются следующие действия:
При этом не определяется, какой из нескольких ожидающих процессов будет деблокирован. При доказательстве корректности программ, использующих операции Р и V, необходимо показать, что программа работает правильно при деблокировании любого процесса. Как только это сделано, детали выбора процесса больше не влияют на программирование параллельных процессов.
Кроме того, возможна также ситуация, когда одна операция V деблокирует процесс X, а затем вторая операция V деблокирует процесс У, но процессу У процессор выделяется раньше, чем процессу X.
Рис.2.9. Управление очередью с использованием семафоров: (а) - исполнение процессов. (6) - определение процессов
Процессы управления очередью (рис.2.9 и программу ЗАПИСЬ, обеспечивающую взаимное исключение, можно реализовать, используя операции Р и V так, как это показано нa рис.2.9 и 2.10. Каждая пара процессов осуществляет взаимное исключение критических интервалов, используя двоичный семафор взаимискл. Начальное значение этого семафора устанавливается в 1. Предположим, что в первой паре процессов процесс ПООС первым выполняет операцию Р. Тогда операционная система закрывает семафор взаимискл и ПООС входит в свой критический интервал. Если CBB выполняет операцию Р в то время, когда ПООС находится в своем критическом интервале, то операционная система блокирует CBB и заставляет его ждать открытия семафора взаимискл. Когда ПООС покидает критический интервал, он выполняет операцию V и операционная система деблокирует процесс, ожидающий семафор взаимискл. Если CBB - единственный такой процесс, то он становится готовым к исполнению. То же самое происходит и со второй парой процессов.
Взаимное исключение для n произвольных процессов приведено на рис. 2.11, Сравнение этой программы с программой на рис.2.7 показывает, что переменную, которая проверялась с помощью команды TS, можно рассматривать как двоичный семафор, значение true которого соответствует 1. Очевидно, что из-за активного ожидания для работы с семафором команда проверить-и-установить подходит меньше, чем операцииР и V.
Рис.2.10. Взаимное исключение конкурирующих программ ЗАПИСЬ с использованием семафора
Рис. 2.11. Обобщенное взаимное исключение с использованием операций Р у V.
