Листинг 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, используя поле непосредственного значения
1 Располагается в слоне состояния программы.
Средства синхронизации и связи взаимодействующих процессов_______________ 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. Организация параллельных взаимодействующих вычислений
рующих критических секций связать одну переменную, которую Дейкстра предложил рассматривать как некоторый «ключ». Вначале доступ к критической секции открыт. Однако перед входом в свою критическую секцию процесс забирает ключ и тем самым блокирует другие процессы. Покидая критическую секцию, процесс открывает доступ, возвращая ключ на место. Если процесс, который хочет войти в свою критическую секцию, обнаруживает отсутствие ключа, он должен быть переведен в состояние блокирования до тех пор, пока процесс, имеющий ключ, не вернет его. Таким образом, каждый процесс, входящий в критическую секцию, должен вначале проверить, доступен ли ключ, и если это так, то сделать его недоступным для других процессов. Причем самым главным должно быть то, что эти два действия должны быть неделимыми, чтобы два или более процессов не могли одновременно получить доступ к ключу. Более того, проверку возможности входа в критическую секцию лучше всего выполнять не самим конкурирующим процессам, так как это приводит к активному ожиданию, а возложить эту функцию на операционную систему. Таким образом, мы подошли к одному из самых главных механизмов решения проблемы взаимного исключения — семафорам Дейкстры.
Дата добавления: 2016-09-20; просмотров: 626;