Глава_1 (Методическое пособие по Операционным системам), страница 5

На рис. 2.16 целая переменная turn, изначально равная 0, отслеживает, чья очередь входить в критическую область. Вначале процесс 0 проверяет значение turn, считывает 0 и входит в критическую область. Процесс 1 также проверяет зна­чение turn, считывает 0 и после этого входит в цикл, непрерывно проверяя, когда же значение turn будет равно 1. Постоянная проверка значения переменной в ожи­дании некоторого значения называется активным ожиданием. Подобного спосо­ба следует избегать, поскольку он является бесцельной тратой времени процес­сора. Активное ожидание используется только в случае, когда есть уверенность в небольшом времени ожидания. Блокировка, использующая активное ожидание, называется спин-блокировкой.

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

Неожиданно процесс 0 завершает работу вне критической области и возвраща­ется к началу цикла. Но войти в критическую область он не может, поскольку зна­чение turn равно 1 и процесс 1 находится вне критической области. Процесс 0 за­виснет в своем цикле while, ожидая, пока процесс 1 изменит значение turn на 0. Получается, что метод поочередного доступа к критической области не слишком удачен, если один процесс существенно медленнее другого.

Эта ситуация нарушает третье из сформулированных нами условий: один процecc блокирован другим, не находящимся в критической области. Возвратимся к примеру с каталогом спулера: если заменить критическую область процедурой счи­тывания и записи в каталог спулера, процесс 0 не сможет послать файл на печать, поскольку процесс 1 занят чем-то другим.

Фактически этот метод требует, чтобы два процесса попадали в критические области строго по очереди. Ни один из них не сможет попасть в критическую область (например, послать файл на печать) два раза подряд. Хотя этот алгоритм и исключает состояния состязания, его нельзя рассматривать всерьез, поскольку он нарушает третье условие успешной работы двух параллельных процессов с совместно используемыми данными,

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

Датский математик Деккер (Т. Dekker) был первым, кто разработал программное решение проблемы взаимного исключения, не требующее строгого чередования, Подробное изложение алгоритма можно найти в (46],

В 1981 году Петерсон (G. L. Peterson) разработал существенно более простой алгоритм взаимного исключения. С этого момента алгоритм Деккера стал считать­ся устаревшим. Алгоритм Петерсона, представленный в листинге 2. 1 , состоит из двух процедур, написанных на ANSI С, что предполагает необходимость прототи­пов для всех определяемых и используемых функций. В целях экономии места мы не будем приводить прототипы для этого и последующих примеров.

Листинг 2. 1 . Решение Петерсона для взаимного исключения

#define FALSE 0

#define TRUE 1

#define N 2 /* Количество процессов */

int turn: /* Чья сейчас очередь? */

int interested [N]; /* Все переменные изначально равны 0 (FALSE) */

void enter_region (int process); /* Процесс 0 или 1 */

{

int other; /* Номер второго процесса */

other= 1 – process; /* Противоположный процесс */

interested [process] =TRUE; /* Индикатор интереса*/

turn=process; /* Установка флага*/

while (turn == process && interested[other] == TRUE) /* Пустой оператор */;

}

void leave_region (int process) /* process; процесс, покидающий критическую область */

{

interested[process]= FALSE;/* Индикатор выхода из критической области */

J

Прежде чем обратиться к совместно используемым переменным (то есть перед тем, как войти в критическую область), процесс вызывает процедуру enter_region со своим номером (0 или 1) в качестве параметра. Поэтому процессу при необходимо­сти придется подождать, прежде чем входить в критическую область. После выхода из критической области процесс вызывает процедуру leave_region, чтобы обозначить свой выход и тем самым разрешить другому процессу вход в критическую область.

Рассмотрим работу алгоритма более подробно. Исходно оба процесса находят­ся вне критических областей, Процесс 0 вызывает enter_region, задает элементы массива и устанавливает переменную turn равной 0. Поскольку процесс 1 не заин­тересован в попадании в критическую область, процедура возвращается. Теперь, если процесс 1 вызовет enter_region, ему придется подождать, пока interested [0] примет значение FALSE, а это произойдет только в тот момент, когда процесс 0 вызовет процедуру leave_region, чтобы покинуть критическую область.

Представьте, что оба процесса вызвали enter_region практически одновремен­но. Оба сохранят свои номера в turn. Сохранится номер того процесса, который был вторым, а предыдущий номер будет утерян. Предположим, что вторым был процесс 1, так что значение turn равно 1. Когда оба процесса дойдут до опера­тора while, процесс 0 войдет в критическую область, а процесс 1 останется в цикле и будет ждать, пока процесс 0 выйдет из критической области.

Команда TSL

Рассмотрим решение, требующее участия аппаратного обеспечения. Многие ком­пьютеры, особенно разработанные с расчетом на несколько процессоров, имеют

команду

TSL RX,LOCK

(Test and Set Lock — проверить и заблокировать), которая действует следующим образом. В регистр RX считывается содержимое слова памяти lock, а в ячейке памя­ти lock сохраняется некоторое ненулевое значение. Гарантируется, что операция считывания слова и сохранения неделима - другой процесс не может обратиться к слову в памяти, пока команда не выполнена. Процессор, выполняющий коман­ду TSL, блокирует шину памяти, чтобы остальные процессоры не могли обратить­ся к памяти.

Воспользуемся командой TSL. Пусть совместно используемая переменная lock управляет доступом к разделенной памяти. Если значение переменной lock рав­но 0, любой процесс может изменить его на 1 и обратиться к разделенной памяти, и затем изменить его обратно на 0, пользуясь обычной командой move.

Как использовать эту команду для взаимного исключения? Решение приведе­но в листинге 2.2. Здесь представлена подпрограмма из четырех команд, написан­ная на фиктивном (но типичном) ассемблере. Первая команда копирует старое значение lock в регистр и затем устанавливает значение переменной равное 1. Потом старое значение сравнивается с нулем. Если оно ненулевое, значит, блокировка уже была установлена и проверка начинается сначала. Рано или поздно значение окажется нулевым (это означает, что процесс, находившийся в критической области, вышел из нее), и подпрограмма возвращается, установив блокировку.

Программа просто помещает 0 в переменную lock. Специальной команды процес­сора не требуется.

Листинг 2.2. Вход и выход из критической области с помощью команды TSL

enter region;

TSL REGISTER.LOCK | значение lock копируется в регистр, значение переменной

устанавливается равным 1

GMP REGISTERED,#0 | Старое значение lock сравнивается с нулем
JNE enter_region | Если оно ненулевое, значит, блокировка уже была установлена.
поэтому цикл завершается

RET | Возврат к вызывающей программе, процесс вошел в критическую

область

leave_region;

MOVE LOCK,#0 | Сохранение 0 в переменной lock

RET

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

Примитивы межпроцессного взаимодействия

Оба решения — Петерсона и с использованием команды TSL — корректны, но они обладают одним и тем же недостатком: использованием активного ожидания. В сущ­ности, оба они реализуют следующий алгоритм; перед входом в критическую область процесс проверяет, можно ли это сделать. Если нельзя, процесс входит в тугой цикл, ожидая возможности войти в критическую область.

Этот алгоритм не только бесцельно расходует время процессора, но, кроме это­го, он может иметь некоторые неожиданные последствия. Рассмотрим два процес­са: H- с высоким приоритетом, и L- с низким приоритетом. Правила планирования в этом случае таковы, что процесс Н запускается немедленно, как только он ока­зывается в состоянии ожидания. В какой-то момент, когда процесс L находится в критической области, процесс Н оказывается в состоянии ожидания (например, он закончил операцию ввода-вывода). Процесс H попадает в состояние активного ожидания, но поскольку процессу L во время работающего процесса Н никогда не будет предоставлено процессорное время, у процесса L не будет возможности вый­ти из критической области, и процесс H навсегда останется в цикле. Эту ситуацию иногда называют проблемой инверсии приоритета.

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

Проблема производителя и потребителя

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

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

Это решение кажется достаточно простым, но оно приводит к состояниям со- стязания, как и пример с каталогом спулера. Нам нужна переменная count для от- слеживания количества элементов в буфере. Если максимальное число элементов, хранящихся в буфере, равно N, программа производителя должна проверить, не равно ли N значение count прежде, чем поместить в буфер следующую порцию данных. Если значение count равно N, то производитель уходит в состояние ожидания; в противном случае производитель помещает данные в буфер и увеличивает значение count.

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