Листинг 7.5. Взаимное исключениес помощью операции проверки и установки

var common, local 1, lосаl2 : integer; begin common:=0: parbegin

ПР1: while true do begin local1:=1:

while local 1=1 do TS(local1, common); CS1; { критическая секция процесса ПР1 } common:=0;

PR1; { ПР1 после критической секции } end and

ПР2: while true do begin local2:=1:

while local2=1 do TS(local2,common); CS2: { критическая секция процесса ПР2 } common:=0;

PR2; { ПР2 после критической секции } end

parend end.

Предположим, что первым хочет войти в свою критическую секцию процесс ПР1. В этом случае значение local1 сначала установится в единицу, а после цикла про­верки с помощью команды TS(locall,common) — в нуль. При этом значение common станет равным единице. Процесс ПР1 войдет в свою критическую секцию. После выполнения критической секции переменная common примет значение, равное нулю, что даст возможность второму процессу ПР2 войти в свою критическую сек­цию.

222________ Глава 7. Организация параллельных взаимодействующих вычислений

Безусловно, мы предполагаем, что в компьютере реализована блокировка памяти, то есть операция common := 0 неделима. Команда проверки и установки значитель­но упрощает решение проблемы критических секций. Главная черта этой коман­ды — ее неделимость.

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

В микропроцессорах архитектуры ia32, с которыми мы теперь сталкиваемся по­стоянно, работая на персональных компьютерах, имеются специальные команды ВТС, BTS, BTR, которые как раз и являются вариантами реализации команды провер­ки и установки. Рассмотрим одну из них — BTS.

Команда BTS (Bit Test and Reset — проверка и установка бита) является двухадрес­ной [20]. По этой команде процессор сохраняет значение бита из первого операнда со смещением, указанным вторым операндом, во флаге CF (Carry Flag — флаг пе­реноса) регистра флагов, а затем устанавливает указанный бит в 1. Значение ин­декса выбираемого бита может быть представлено постоянным непосредственным значением в команде BTS или значением в общем регистре. В этой команде исполь­зуется только 8-разрядное непосредственное значение. Значение этого операнда берется по модулю 32, таким образом, смещение битов находится в диапазоне от 0 до 31. Это позволяет выбрать любой бит внутри регистра. Для битовых строк в памяти это поле непосредственного значения дает только смещение внутри слова или двойного слова.

С учетом изложенного можно привести фрагмент кода, в котором данная команда используется для решения проблемы взаимного исключения (листинг 7.6).

Листинг 7.6.Фрагмент программы с критической секцией на ассемблере

Однако здесь следует заметить, что некоторые ассемблеры поддерживают значе­ния битовых смещений больше 31, используя поле непосредственного значения

¹ Располагается в слоне состояния программы.

Средства синхронизации и связи взаимодействующих процессов_______________ 223

в комбинации с полем смещения операнда в памяти. В этом случае младшие 3 или 5 битов (3 — для 16-разрядных операндов, 5 — для 32-разрядных операндов), оп­ределяющие смещение бита (второй операнд команды), сохраняются в поле не­посредственного операнда, а старшие биты сдвигаются и комбинируются с полем смещения. Процессор же игнорирует ненулевые значения старших битов поля вто­рого операнда [20]. При доступе к памяти процессор обращается к четырем байтам (для 32-разрядного операнда), начинающимся по полученному следующим обра­зом адресу:

Effective Address + (4 х (BitOffset DIV 32))

Либо (для 16-разрядного операнда) процессор обращается к двум байтам, начина­ющимся по адресу:

Effective Address + (2 х (BitOffset DIV 16))

Такое обращение происходит, даже если необходим доступ только к одному байту. Поэтому избегайте ссылок к областям памяти, близким к «пустым» адресным про­странствам. В частности, избегайте ссылок на распределенные в памяти регистры ввода-вывода. Вместо этого используйте команду M0V для загрузки и сохранения значений по таким адресам и регистровую форму команды BTS для работы с дан­ными.

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

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

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

224________ Глава 7. Организация параллельных взаимодействующих вычислений

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