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

Не должно возникать ситуации, при которой процесс,находящийся вне своей критической секции, блокируетисполнение другого процесса.2. Недолжноотносительноделатьсяникакихпредположенийвзаимныхскоростейисполнения15процессов, а также относительноколичества искоростей работы процессоров в системе.Далее мы рассмотрим различные механизмы организациивзаимного исключения для синхронизации доступа к разделяемымресурсам и обсудим достоинства, недостатки и области примененияэтих подходов.3.1 Способы реализации взаимного исключения.3.1.1 Запрещение прерываний и специальные инструкции.Простейшее умозаключение, которое, на первый взгляд,решает проблему синхронизации доступа к критическим ресурсам,заключается в следующем: некорректная работа с разделяемымиресурсами возникает в том случае, если переключение процессовпроисходит в тот момент, когда выполняющийся процесс началработу с разделяемым ресурсом, но не закончил ее, т.е. находится всвоей критической секции.

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

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

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

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

Одним из первых программных решений являетсяалгоритм Петерсона.Алгоритм Петерсона для случая 2х процессов представлен наРис. 4.17int first_process() {for(;;) {flag[0] = 1;turn = 1;while (flag[1] && turn) {/* waiting */};/* critical section */flag[0] = 0;}}int second_process() {for(;;) {flag[1] = 1;turn = 1;while (flag[0] && (!turn)){/* waiting */};/* critical section */flag[1] = 0;}}Рис. 4 Алгоритм ПетерсонаЭлементы массива flag символизируют собой желаниесоответствующего процесса попасть в критическую секцию.Каждый из процессов видит все элементы массива flag, номодифицирует только «свой» элемент. Переменная turnустанавливает очередность прохождения критической секции приобоюдном желании процессов вступить в нее.

Благодаря тому, чтокаждый из процессов прежде всего устанавливает флаг очередностив пользу другого процесса, исключается ситуация «монополизации»ресурса одним из процессов и вечного блокирования второго.3.1.3 Активное ожидание.Общим недостатком рассмотренных выше решений являетсято, что процесс, желающий получить доступ к занятому ресурсу,блокируется в состоянии так называемого активного ожидания (ванглоязычной литературе – busy waiting), т.е.

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

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

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

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

При выходе посетитель возвращает тележку на2Оригинальные обозначения P и V, данные Дейкстрой и получившие широкоераспространение в литературе, являются сокращениями голландских слов proberen – проверитьи verhogen – увеличить19место, увеличивая тележек на 1 – это аналог операции up. Теперьпредставим себе, что очередной посетитель обнаруживает, чтосвободных тележек нет – он вынужден блокироваться на входе вожидании появления тележки.

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

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

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