Добавлен: 29.10.2018
Просмотров: 48021
Скачиваний: 190
2.3. Взаимодействие процессов
151
Блокирующие переменные
В качестве второй попытки рассмотрим программное решение, в котором используется
одна общая (блокирующая) переменная, исходное значение которой равно нулю. Когда
процессу требуется войти в свою критическую область, сначала он проверяет значение
блокирующей переменной. Если оно равно 0, процесс устанавливает его в 1 и входит
в критическую область. Если значение уже равно 1, процесс просто ждет, пока оно не
станет равно нулю. Таким образом, нулевое значение показывает, что ни один из про-
цессов не находится в своей критической области, а единица — что какой-то процесс
находится в своей критической области.
К сожалению, реализация этой идеи приводит к точно такому же фатальному исходу,
который мы уже видели в примере с каталогом спулера. Предположим, что один про-
цесс считывает значение блокирующей переменной и видит, что оно равно нулю. Перед
тем как он сможет установить значение в единицу, планировщик запускает другой про-
цесс, который устанавливает значение в единицу. Когда возобновляется выполнение
первого процесса, он также установит значение блокирующей переменной в единицу,
и два процесса одновременно окажутся в своих критических областях.
Может показаться, что эту проблему можно обойти, считывая сначала значение бло-
кирующей переменной, а затем проверяя ее значение повторно, прежде чем сохранить
в ней новое значение, но на самом деле это не поможет. Состязание возникнет в том
случае, если второй процесс изменит значение блокирующей переменной сразу же по-
сле того, как первый процесс завершит повторную проверку ее значения.
Строгое чередование
Третий подход к решению проблемы взаимных исключений показан на рис. 2.17. Этот
программный фрагмент, как почти все фрагменты, приводимые в этой книге, написан
на языке C. Выбор пал именно на этот язык, поскольку настоящие операционные
системы почти всегда пишутся на C (изредка на C++) и практически никогда не пи-
шутся на Java, Pyton или Haskell. Мощность, эффективность и предсказуемость языка
С — именно те характеристики, которые крайне необходимы для написания операци-
онных систем. Java, к примеру, не является предсказуемым языком, поскольку в самый
неподходящий момент у него может закончиться свободная память и возникнуть по-
требность в вызове сборщика мусора для очистки памяти. Для C это не свойственно,
поскольку в этом языке нет сборщика мусора. Количественное сравнение C, C++, Java
и четырех других языков приведено в работе Пречелда (Precheld, 2000).
Рис. 2.17. Предлагаемое решение проблемы критической области: а — процесс 0;
б — процесс 1. В обоих случаях следует убедиться, что в коде присутствует точка с запятой,
завершающая оператор while
152
Глава 2. Процессы и потоки
Изначально целочисленная переменная turn, показанная на рис. 2.17, равна нулю
и отслеживает, чья настала очередь входить в критическую область и проверять или
обновлять общую память. Сначала процесс 0 проверяет значение turn, определяет, что
оно равно нулю, и входит в критическую область. Процесс 1 также определяет, что зна-
чение этой переменной равно нулю, из-за чего находится в коротком цикле, постоянно
проверяя, когда turn получит значение 1. Постоянная проверка значения переменной,
пока она не приобретет какое-нибудь значение, называется активным ожиданием.
Как правило, этого ожидания следует избегать, поскольку оно тратит впустую время
центрального процессора. Активное ожидание используется только в том случае, если
есть основание полагать, что оно будет недолгим. Блокировка, использующая активное
ожидание, называется спин-блокировкой.
Когда процесс 0 выходит из критической области, он устанавливает значение пере-
менной turn в 1, разрешая процессу 1 войти в его критическую область. Предположим,
что процесс 1 быстро выходит из своей критической области, в результате чего оба
процесса находятся вне своих критических областей, а переменная turn установлена
в 0. Теперь процесс 0 быстро завершает свой полный цикл, выходит из критической
области и устанавливает значение turn в 1. В этот момент значение turn равно 1 и оба
процесса выполняются вне своих критических областей.
Внезапно процесс 0 завершает работу вне своей критической области и возвращается
к началу цикла. К сожалению, в данный момент ему не разрешено войти в его критиче-
скую область, поскольку переменная turn имеет значение 1 и процесс 1 занят работой
вне своей критической области. Процесс 0 зависает в своем цикле while до тех пор, пока
процесс 1 не установит значение turn в 0. Иначе говоря, когда один процесс работает
существенно медленнее другого, поочередная организация вхождения в критическую
область вряд ли подойдет.
Эта ситуация нарушает сформулированное ранее третье условие: процесс 0 оказывается
заблокированным тем процессом, который не находится в своей критической области.
Вернемся к ранее рассмотренному каталогу спулера. Если в такой ситуации мы свяжем
критическую область с чтением или записью в каталог спулера, процессу 0 будет запре-
щено распечатать следующий файл, поскольку процесс 1 будет занят чем-нибудь другим.
Фактически это решение требует, чтобы, к примеру, при помещении файлов в каталог
спулера два процесса входили в свои критические области, строго чередуясь друг с дру-
гом. Ни одному из них не разрешено поместить файл в спулер два раза подряд. Хотя
этот алгоритм позволяет предотвращать любые состязательные ситуации, его нельзя
рассматривать в качестве серьезного кандидата на решение проблемы, поскольку он
нарушает третье условие.
Алгоритм Петерсона
Используя сочетание идеи очередности с идеей блокирующих и предупреждающих
переменных, голландский математик Деккер (T. Dekker) стал первым, кто придумал
программное решение проблемы взаимного исключения, не требующее четкой очеред-
ности. Обсуждение алгоритма Деккера приведено в книге Дейкстры (Dijkstra, 1965).
В 1981 году Петерсон придумал гораздо более простой способ достижения взаимного
исключения, которое перевело решение Деккера в разряд устаревших. Алгоритм Пе-
терсона показан в листинге 2.2. Этот алгоритм состоит из двух процедур, написанных
на ANSI C, а это значит, что для всех определенных и используемых функций должны
2.3. Взаимодействие процессов
153
быть предоставлены функции-прототипы. Но в целях экономии места мы не будем
показывать прототипы ни в этом, ни в последующих примерах.
Листинг 2.2. Решение Петерсона, позволяющее добиться взаимного исключения
#define FALSE 0
#define TRUE 1
#define N 2 /* количество процессов */
int turn; /* чья очередь? */
int interested[N]; /* все исходные значения равны 0 (FALSE) */
void enter_region(int process); /* process имеет значение 0 или 1 */
{
int other; /* номер другого процесса */
other = 1 − process; /* противостоящий процесс */
interested[process] = TRUE; /* демонстрация заинтересованности */
turn = process; /* установка флажка */
while (turn == process && interested[other] == TRUE)/* цикл без инструкции
*/;
}
void leave_region(int process) /* процесс, покидающий критическую область */
{
interested[process] = FALSE; /* признак выхода из критической области */ }
Перед использованием общих переменных (то есть перед входом в свою критическую
область) каждый процесс вызывает функцию enter_region, передавая ей в качестве
аргумента свой собственный номер процесса, 0 или 1. Этот вызов заставляет процесс
ждать, если потребуется, безопасного входа в критическую область. После завершения
работы с общими переменными процесс, чтобы показать это и разрешить вход другому
процессу, если ему это требуется, вызывает функцию leave_region.
Рассмотрим работу алгоритма. Изначально ни один из процессов не находится в крити-
ческой области. Затем процесс 0 вызывает функцию enter_region. Он демонстрирует свою
заинтересованность, устанавливая свой элемент массива и присваивая переменной turn
значение 0. Поскольку процесс 1 заинтересованности во входе в критическую область
не проявил, функция enter_region тотчас же возвращает управление. Теперь, если про-
цесс 1 вызовет функцию enter_region, он зависнет до тех пор, пока interested[0] не получит
значение FALSE, а это произойдет только в том случае, если процесс 0 вызовет функцию
leave_region, чтобы выйти из критической области.
Теперь рассмотрим случай, когда оба процесса практически одновременно вызывают
функцию enter_region. Оба они будут сохранять свой номер процесса в переменной
turn. В расчет берется последнее сохранение, поскольку первое будет переписано
и утрачено. Предположим, что процесс 1 сохранил свой номер последним и turn имеет
значение 1. Когда оба процесса доберутся до оператора while, процесс 0 не выполнит
его ни одного раза и войдет в свою критическую область. Процесс 1 войдет в цикл и не
будет входить в свою критическую область до тех пор, пока процесс 0 не выйдет из
своей критической области.
Команда TSL
А теперь давайте рассмотрим предложение, для реализации которого требуется не-
большая помощь со стороны оборудования. Некоторые компьютеры, в особенности те,
154
Глава 2. Процессы и потоки
которые разрабатывались с прицелом на работу нескольких процессов, располагают
командой
TSL RX,LOCK
(TSL — Test and Set Lock, то есть проверь и установи блокировку), которая работает
следующим образом. Она считывает содержимое слова памяти lock в регистр RX, а по
адресу памяти, отведенному для lock, записывает ненулевое значение. При этом гаран-
тируются неделимость операций чтения слова и сохранение в нем нового значения —
никакой другой процесс не может получить доступ к слову в памяти, пока команда не
завершит свою работу. Центральный процессор, выполняющий команду TSL, блокирует
шину памяти, запрещая другим центральным процессорам доступ к памяти до тех пор,
пока не будет выполнена эта команда.
Следует заметить, что блокировка шины памяти существенно отличается от запрета
на прерывания. Если при выполнении чтения слова памяти с последующей записью
в него запретить прерывания, ничто не помешает второму центральному процессору,
подключенному к шине памяти, получить доступ к слову между чтением и записью.
Получается, что запрет прерываний на процессоре 1 не оказывает абсолютно ника-
кого воздействия на процессор 2. Перекрыть процессору 2 доступ к памяти, пока
процессор 1 не завершит выполнение команды, можно только одним способом — за-
блокировав шину, а для этого требуется специальное оборудование (в основном для
этого используется линия шины, сигнал на которой блокирует шину, исключая к ней
доступ всех процессоров, кроме того, который ее заблокировал).
Чтобы задействовать команду TSL, мы воспользуемся общей переменной lock, позво-
ляющей скоординировать доступ к общей памяти. Когда lock имеет значение 0, любой
процесс, используя команду TSL, может установить ее значение в 1, а затем производить
операции чтения или записи с общей памятью. Когда процесс завершит эти операции,
он возвращает переменной lock значение 0, используя обычную команду move.
Как же воспользоваться этой командой для предотвращения одновременного входа
двух процессов в их критические области? Решение продемонстрировано в листин-
ге 2.3. В нем показана подпрограмма, состоящая из четырех команд, написанная на
вымышленном (но типовом) языке ассемблера. Первая команда копирует прежнее
значение переменной lock в регистр, а затем присваивает ей значение 1. Затем преж-
нее значение сравнивается с нулем. Если оно ненулевое, значит, блокировка уже
была установлена, поэтому программа просто возвращается в самое начало и по-
вторно проверяет значение переменной. Рано или поздно это значение превратится
в 0 (когда процесс, находившийся в своей критической области, завершит в ней
работу и произойдет выход из подпрограммы с установкой блокировки). Снятие
блокировки осуществляется довольно просто: программе достаточно присвоить
переменной lock нулевое значение. Для этого не нужны никакие специальные
команды синхронизации.
Теперь суть одного из решений проблемы критических областей прояснилась. Перед
входом в свою критическую область процесс вызывает функцию enter_region, которая
входит в цикл активного ожидания, пока не будет снята блокировка, затем она уста-
навливает блокировку и возвращает управление. Завершив работу в критической об-
ласти, процесс вызывает функцию leave_region, которая присваивает переменной lock
нулевое значение. Как и во всех решениях проблемы критических областей, чтобы
этот способ заработал, процессы должны своевременно вызывать функции enter_region
2.3. Взаимодействие процессов
155
и leave_region. Если какой-нибудь из процессов не выполнит это условие, взаимное ис-
ключение не сработает. Иными словами, критические области работают, только если
процессы взаимодействуют.
Листинг 2.3. Вход и выход из критической области
с использованием команды TSL
enter region:
TSL REGISTER,LOCK | копирование lock в регистр с присвоением ей 1
CMP REGISTER,#0 | было ли значение lock нулевым?
JNE enter_region | если оно было ненулевым, значит, блокировка
| уже установлена и нужно войти в цикл
RET | возврат управления вызывающей программе;
| вход в критическую область осуществлен
leave region:
MOVE LOCK,#0 | присвоение переменной lock нулевого значения
RET | возврат управления вызывающей программе
Альтернативой команде TSL служит команда XCHG, осуществляющая атомарный
обмен содержимого двух областей памяти, например регистра и слова памяти. Можно
заметить, что код, показанный в листинге 2.4, практически такой же, как и в решении
с использованием команды TSL. Команда XCHG используется для низкоуровневой
синхронизации всеми центральными процессорами семейства Intel x86.
Листинг 2.4. Вход и выход из критической области
с использованием команды XCHG
Enter_region:
MOVE REGISTER,#1 | помещение 1 в регистр
XCHG REGISTER,LOCK | обмен содержимого регистра и переменной lock
CMP REGISTER,#0 | было ли значение lock нулевым?
JNE enter_region | если оно было ненулевым, значит, блокировка
| уже установлена и нужно войти в цикл
RET | возврат управления вызывающей программе;
| вход в критическую область осуществлен
leave region:
MOVE LOCK,#0 | присвоение переменной lock нулевого значения
RET | возврат управления вызывающей программе
2.3.4. Приостановка и активизация
И алгоритм Петерсона, и решение, использующее команду TSL или XCHG, вполне ра-
ботоспособны, но у них есть один недостаток — необходимость пребывания в режиме
активного ожидания. По сути эти решения сводятся к следующему: когда процессу
требуется войти в критическую область, он проверяет, разрешен ли этот вход. Если
вход запрещен, процесс просто входит в короткий цикл, ожидая разрешения.
Этот подход не только приводит к пустой трате процессорного времени, но и может
иметь совершенно неожиданные эффекты. Рассмотрим компьютер с двумя процес-
сами: H с высокой степенью приоритета и L с низкой степенью приоритета. Правила
планирования их работы предусматривают, что H выполняется сразу же после входа
в состояние готовности. В определенный момент, когда L находится в критической