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

УСТАНОВКА»

Операция «ПРОВЕРКА И УСТАНОВКА» является, как и блокировка памяти, одним из аппаратных средств решения задачи критического интервала. Данная операция реализована на многих компьютерах. Так, в знаменитой 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В

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

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

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

⇐ Предыдущая 27 28 29 30 313233 34 35 36 Следующая ⇒