Синхронизация процессов посредством операции «ПРОВЕРКА И

УСТАНОВКА»

Операция «ПРОВЕРКА И УСТАНОВКА» является, как и блокировка памяти, одним из аппаратных средств решения задачи критического интервала. Данная операция реализована на многих компьютерах. Так, в знаменитой IBM 360 (370) эта команда называлась TS (test and set). Команда TS является двухадресной (двухоперандной). Её действие заключается в том, что процессор присваивает значение второго операнда первому, после чего второму операнду присваивается значение, равное единице. Команда TS является неделимой операцией, то есть между ее началом и концом не могут выполняться никакие другие команды.

Чтобы использовать команду TS для решения проблемы критического интерва­ла, свяжем с ней переменную common, которая будет общей для всех процессов, использующих некоторый критический ресурс. Данная переменная будет принимать единичное значение, если какой-либо из взаимодействующих процессов находится в своем критическом интервале. С каждым процессом связана своя локальная переменная, которая принимает значение, равное единице, если дан­ный процесс хочет войти в свой критический интервал. Операция TS будет при­сваивать значение common локальной переменной и устанавливать common в единицу. Программа решения проблемы критического интервала на примере двух парал­лельных процессов приведена в листинге 6.5.

Листинг 6.5. Взаимное исключение с помощью операции «ПРОВЕРКА И УСТАНОВКА»

var common, local1, lосаl2 : integer;

begin

common:=0;

parbegin

ПР1: while true do

begin

local1:=1;

white local1=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 сначала установится в единицу, а после цик­ла проверки с помощью команды ТS(lосаl1, common) – в ноль. При этом значение common станет равным единице. Процесс ПР1 войдет в свой критический интервал. После выполнения этого критического интервала common примет значение, равное нулю, что даст возможность второму процессу ПР2 войти в свой критический интервал.

Безусловно, мы предполагаем, что в компьютере предусмотрена блокировка па­мяти, то есть операция common:=0 неделима. Команда «ПРОВЕРКА И УСТАНОВ­КА» значительно упрощает решение проблемы критических интервалов. Главное свойство этой команды – её неделимость.

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

В микропроцессорах i80386 и старше, с которыми мы теперь сталкиваемся постоянно, есть специальные команды: ВТС, BTS, BTR, которые как раз и являют­ся вариантами реализации команды типа «ПРОВЕРКА И УСТАНОВКА». Рас­смотрим одну из них – BTS.

Команда BTS (bit test and reset – проверка бита и установка) является двухадресной [48]. По этой команде процессор сохраняет значение бита из первого операнда со смещением, указанным вторым операндом, во флаге CF1 регистра флагов, а затем устанавливает указанный бит в 1. Значение индекса выбираемого бита может быть представлено постоянным непосредственным значением в ко­манде BTS или значением в общем регистре. В этой команде используется толь­ко 8-битное непосредственное значение. Значение этого операнда берется по мо­дулю 32, таким образом, смещение битов находится в диапазоне от 0 до 31. Это позволяет выбирать любой бит внутри регистра. Для битовых строк в памяти это поле непосредственного значения даёт только смещение внутри слова или двойного слова.

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

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

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

для размера операнда 32 бита, или к двум байтам, начинающимся по адресу

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

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

Листинг 6.6. Фрагмент программы на ассемблере с критическим интервалом

L: BTC M,1

JC L

. ü

. ý критическая секция

. þ

AND М, 0В

.

.

Несмотря на то, что и алгоритм Деккера, основанный только на блокировке памяти, и операция «ПРОВЕРКА И УСТАНОВКА» пригодны для реализации взаимного исключения, оба эти приёма очень неэффективны. Всякий раз, когда один из процессов выполняет свой критический интервал, любой другой про­цесс, который пытается войти в свою критическую секцию, попадает в цикл про­верки соответствующих переменных-флагов, регламентирующих доступ к кри­тическим переменным. При таком неопределенном пребывании в цикле, которое называется активным ожиданием, напрасно расходуется процессорное время, поскольку процесс имеет доступ к тем общим переменным, которые и определя­ют возможность или невозможность входа в критическую секцию. При этом процесс занимает ценное время центрального процессора, на самом деле ничего реально не выполняя. Как результат, мы имеем общее замедление вычислитель­ной системы процессами, которые реально не выполняют никакой полезной ра­боты.

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

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