3. Операция «Проверка и установка».
Операция «Проверка и установка» является одним из аппаратных средств решения задачи критического интервала. Данная операция реализована на многих компьютерах. Машинная операция «Проверка и установка» значительно упрощает решение проблемы критического участка посредством блокировки памяти. К операции «Проверка и установка» обращаются с двумя параметрами: Локальный и Общий. Операция берет значение параметра Общий и присваивает его переменной Локальный, а затем устанавливает в переменной Общий значение 1. Главное свойство этой операции – ее неделимость. Когда процесс выполняет операцию «проверка и установка», никаких действий не может произойти между ее началом и концом.
Листинг 5. Взаимное исключение с помощью операции «Проверка и Установка».
Var
ЛОКАЛЬНЫЙ_1, ЛОКАЛЬНЫЙ_2, ОБЩИЙ: integer;
Begin
ОБЩИЙ := 0;
parbegin
ПРОЦЕСС 1:
begin
while (true) do
begin
ЛОКАЛЬНЫЙ_1 := 1;
while (ЛОКАЛЬНЫЙ1=1) do
begin
проверка и установка (ЛОКАЛЬНЫЙ_1, ОБЩИЙ)
end;
критический участок 1;
ОБЩИЙ :=0;
оставшаяся часть процесса 1
end
end;
ПРОЦЕСС 2:
begin
while (true) do
begin
ЛОКАЛЬНЫЙ_2 := 1;
while (ЛОКАЛЬНЫЙ2=1) do
begin
проверка и установка (ЛОКАЛЬНЫЙ2, ОБЩИЙ)
end;
критический участок 2;
ОБЩИЙ :=0;
оставшаяся часть процесса 2
end
end;
ParEnd
end
Переменная Общий разделяется между процессами, которые подлежат синхронизации по отношению к некоторому критическому ресурсу. У каждого процесса есть своя собственная переменная Локальный. Если Общий = 1, это значит, что какой-то процесс находится в своем критическом участке. Начальное значение переменной Общий равно 0. В Листинге 5 приведено решение проблемы взаимного исключения для двух процессов, использующее операцию «Проверка и установка». В этом решении предполагается, что в машине предусмотрена блокировка памяти, т. е. операция Общий := 0 неделима.
Данная операция была реализована на многих машинах. Так, например в IBM 360 (370) имелась команда специальная TS (test and set) для использования операции «Проверка и установка». TS – это двухадресная команда, действие которой заключается в том, что процессор присваивает значение второго операнда первому, после чего второму операнду присваивается значение, равное единице. Команда TS является неделимой операцией, то есть между ее началом и концом не могут выполняться никакие другие команды.
Чтобы использовать команду TS для решения проблемы критического интервала, свяжем с ней переменную common, которая будет общей для всех процессов, использующих некоторый критический ресурс. Данная переменная будет принимать единичное значение, если какой-либо из взаимодействующих процессов находится в своем критическом интервале. С каждым процессом связана своя локальная переменная, которая принимает значение, равное единице, если данный процесс хочет войти в свой критический интервал. Операция TS будет присваивать значение common локальной переменной и устанавливать common в единицу. Программа решения проблемы критического интервала на примере двух параллельных процессов приведена в листинге 6.
Предположим, что первым захочет войти в свой критический интервал процесс ПР1. В этом случае значение locall сначала установится в единицу, а после цикла проверки с помощью команды TS(locall, common) – в ноль. При этом значение common станет равным единице. Процесс ПР1 войдет в свой критический интервал. После выполнения этого критического интервала common примет значение, равное нулю, что даст возможность второму процессу ПР2 войти в свой критический интервал.
Листинг 6. Взаимное исключение с помощью операции «Проверка и Установка».
Var
Common, Local_1, Local_2: Integer;
Begin
Common:=0;
ParBegin
PR1: While true do
Begin
Local_1:=1;
while Local_1=1 do TS(Local_1, Common);
CS_1; {Критический интервал процесса PR_1}
Common:=0
PR_1; {PR_1 после критического интервала}
End;
And;
PR2: While true do
Begin
Local_2:=1;
while Local_2=1 do TS(Local_2, Common);
CS2_; {Критический интервал процесса PR_2}
Common:=0
PR_2; {PR_2 после критического интервала}
End;
ParEnd;
End;
В микропроцессорах i80386 и старше, также есть специальные команды: ВТС, BTS, ВТК, которые являются вариантами реализации команды типа «Проверка и установка». Рассмотрим одну из них – BTS.
Команда BTS (bit test and reset – проверка бита и установка) является двухадресной [___]. По этой команде процессор сохраняет значение бита из первого операнда со смещением, указанным вторым операндом, во флаге CF1 регистра флагов, а затем устанавливает указанный бит в 1. Значение индекса выбираемого бита может быть представлено постоянным непосредственным значением в команде BTS или значением в общем регистре. В этой команде используется только 8-битное непосредственное значение. Значение этого операнда берется по модулю 32, таким образом, смещение битов находится в диапазоне от 0 до 31. Это позволяет выбирать любой бит внутри регистра. Для битовых строк в памяти это поле непосредственного значения дает только смещение внутри слова или двойного слова.
С учетом изложенного можно привести фрагмент текста, в котором используется данная команда для решения проблемы взаимного исключения (листинг 6.6).
Однако здесь следует заметить, что некоторые ассемблеры поддерживают значения битовых смещений больше 31, используя поле непосредственного значения в комбинации с полем смещения операнда в памяти. В этом случае ассемблером младшие 3 или 5 битов (3 – для 16-битных операндов, 5 – для 32-битных операндов) смещения бита (второй операнд команды) сохраняются в поле непосредственного операнда, а старшие биты сдвигаются и комбинируются с полем смещения. Процессор же игнорирует ненулевые значения старших битов поля второго операнда [___]. При доступе к памяти процессор обращается к четырем байтам, начинающимся по полученному следующим образом адресу
Effective Address + (4 * (BitOffset DIV 32))
для размера операнда 32 бита, или к двум байтам, начинающимся по адресу
Effective Address + (2 * (BitOffset DIV 16))
для 16-битного размера операнда. Такое обращение происходит, даже если необходим доступ только к одиночному байту. Поэтому избегайте ссылок к областям памяти, близким к «пустым» адресным пространствам. В частности, избегайте ссылок на распределенные в памяти регистры ввода/вывода. Вместо этого используйте команду MOV для загрузки и сохранения значений по таким адресам и регистровую форму команды BTS для работы с данными.