4.1.3. Примитивы событийной синхронизации процессов

Мы уже знаем, что существуют следующие понятия:

1. Критический ресурс - разделяемый ресурс, с которым могут работать несколько параллельных процессов;

2. Критический участок - участок программы процесса, в котором описаны действия с критическим ресурсом;

3. Режим взаимного исключения - режим выполнения критического участка без передачи управления от одного процесса к другому.

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

Пример: N - Счет в центральном банке. С двух терминалов делается попытка его изменить.

Ожидаем результат: N = N + S1 + S2;

Можем получить: N = N + S1; или N = N + S2.

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

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

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

Существуют аппаратные и программные способы решения этой проблемы в зависимости от логического уровня, на котором рассматривается эта проблема.

Дадим их краткий обзор.

1. Запрет прерываний

2. Маскирование прерываний только от таймера

3. Использование флага занятости ресурса

1. Первое средство, которое напрашивается само собой - запрет прерываний на входе критического участка и разрешение прерываний на выходе из него.

P1: P2:

cli cli

Критический участок; Критический участок;

sti sti

Этот способ имеет следующие недостатки:

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

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

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

2. Третий способ. Устанавливается флаг занятости ресурса.

Например:

Flag = 0 - ресурс свободен;

Flag = 1 - ресурс занят.

Процесс перед входом в критический участок проверяет значение флага. Если флаг равен нулю, то процесс устанавливает флаг в состояние 1 (занят) и входит в критический участок. Если флаг равен единице, то процесс снова переходит на проверку значения флага.

При выходе из критического участка процесс устанавливает флаг в состояние 0 (свободен).

Вариант без метки:

M: if (Flag == 1) goto M; while (Flag == 1) ;

Flag = 1;

Критический участок;

Flag = 0;

Оказывается, что этот способ не снимает проблемы. «Откомпилируем» предыдущий код:

M: cmp Flag,1

jz M

mov Flag, 1

Критический участок;

mov Flag, 0

Предположим, что Flag = 0 и передача управления происходит сразу же за инструкцией

cmp Flag,1

и второй процесс выполняет инструкцию cmp Flag,1. Для обоих процессов Flag окажется равным нулю и они оба войдут в критический участок.

Это происходит потому, что Flag сам является критическим ресурсом и доступ к нему надо организовывать в режиме взаимного исключения:

M1 : cli или M1 : sti

cmp Flag,1 cli

jnz M2 cmp Flag,1

sti jz M1

jmp M1 mov Flag,1

M2 : mov Flag,1 sti

sti Критический участок;

Критический участок; mov Flag,0

mov Flag,0

Третий вариант с инструкцией «обменять» - xchg:

mov ax,1

M: xchg ax,Flag

Cmp ax,1

jz M

Критический участок;

mov Flag,0

Если Flag = 0, то Flag установится в 1, а ax установится в 0, и процесс войдет в критический участок.

Если Flag = 1, то он останется в 1 и ax останется в 1, и процесс перейдет на метку М, т.е. будет ждать установки Flag в 0.

Чтение и установка флага производятся за одну инструкцию, а это - неделимое действие по определению.

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

Вводя в программе префикс LOCK, можно обеспечить блокировку магистрали при выполнении некоторых других инструкций: INC, DEC, ADD, SUB, AND, OR.

Загрузка TSS осуществляется при блокировке магистрали.

Выводы по третьему способу обеспечения взаимного исключения

1. Способ имеет достоинство, состоящее в том, что критический участок с флагом имеет маленькую и фиксированную длину.

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

3. Способ не избавляет от «активного ожидания» – цикла опроса флага до его освобождения.

4. Способ, как и два предыдущих иллюстрирует общую структуру участка программы, работающего с критическим ресурсом – это наличие логических скобок - вход в критический участок и выход из критического участка:

Вход;

Критический участок;

Выход;

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

Семафоры как примитивы ядра и средство синхронизации

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

Так появились двоичный и общий семафор Дейкстры.

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

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

Вход:

Запрет_прерываний;

if (Flag == Занят) {

Встать в очередь;

ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

}

Flag = Занят;

Разрешение_прерываний;

Выход:

Запрет_прерываний;

Flag = Свободен;

if (Очередь не пуста) {

Перевести первый процесс из этой очереди

в очередь готовых процессов;

ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

}

Разрешение_прерываний;

Особенности семафора:

1. Вставая в очередь семафора до освобождения ресурса, процесс разгружает процессор;

2. На каждый ресурс нужен свой семафор, а значит, своя очередь, поэтому в ядре и много очередей;

3. Семафор - это тоже разделяемый ресурс, а значит, действия с ним должны выполняться в режиме взаимного исключения; более того, если рассматривать семафор как примитив ядра, вместо операции Запрет_прерываний необходимо ставить операции ПРОЛОГ, КОНТРОЛЬ.

4. Использование семафора обеспечивает возможность безостановочной работы процессов, не требующих ресурсов.