Файл: А. В. Гордеев А. Ю. Молчанов системное программное обеспечение электронный вариант книги издательства Питер СанктПетербург Челябинск юургу каф. Автоматика и управление 2002 2 Предисловие Настоящий учебник.pdf

294
Листинг 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 примет значение,

295
равное нулю, что даст возможность второму процессу ПР2 войти в свой критиче- ский интервал.
Безусловно, мы предполагаем, что в компьютере предусмотрена блокировка памяти, то есть операция common:=0 неделима. Команда «ПРОВЕРКА И УСТА-
НОВКА» значительно упрощает решение проблемы критических интервалов.
Главное свойство этой команды – её неделимость.
Основной недостаток использования операций типа «ПРОВЕРКА И УСТА-
НОВКА» состоит в следующем: находясь в цикле проверки переменной common,
процессы впустую потребляют время центрального процессора и другие ресурсы.
Действительно, если предположить, что произошло прерывание процесса ПР1 во время выполнения своего критического интервала в соответствии с некоторой дис- циплиной обслуживания и начал выполняться процесс ПР2, то он войдет в цикл проверки, впустую тратя процессорное время. В этом случае до тех пор, пока дис- петчер супервизора не поставит на выполнение процесс ПР1 и не даст ему закон- читься, процесс ПР2 не сможет войти в свой критический интервал.
В микропроцессорах i80386 и старше, с которыми мы теперь сталкиваемся по- стоянно, есть специальные команды: ВТС, BTS, BTR, которые как раз и являются вариантами реализации команды типа «ПРОВЕРКА И УСТАНОВКА». Рассмотрим одну из них – BTS.
Команда BTS (bit test and reset – проверка бита и установка) является двухад- ресной [48]. По этой команде процессор сохраняет значение бита из первого опе- ранда со смещением, указанным вторым операндом, во флаге CF
1
регистра флагов,
а затем устанавливает указанный бит в 1. Значение индекса выбираемого бита мо- жет быть представлено постоянным непосредственным значением в команде BTS
или значением в общем регистре. В этой команде используется только 8-битное непосредственное значение. Значение этого операнда берется по модулю 32, таким образом, смещение битов находится в диапазоне от 0 до 31. Это позволяет выби- рать любой бит внутри регистра. Для битовых строк в памяти это поле непосредст- венного значения даёт только смещение внутри слова или двойного слова.
1
CF (carry flag) – флаг переноса. Располагается в слове состояния программы. Для процессоров i80x86 этот регистр
– управляющий регистр CR0.

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

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

298
ключ, не вернёт его. Таким образом, каждый процесс, входящий в критический ин- тервал, должен вначале проверить, доступен ли ключ, и если это так, то сделать его недоступным для других процессов. Причем самым главным является то, что эти два действия должны быть неделимыми, чтобы два или более процессов не могли одновременно получить доступ к ключу. Более того, проверку того, можно ли вой- ти в критический интервал, лучше всего выполнять не самим конкурирующим процессам, так как это приводит к активному ожиданию, а возложить эту функцию на операционную систему. Таким образом, мы подошли к одному из самых глав- ных механизмов решения проблемы взаимного исключения – семафорам Дейкст- ры.
Семафорные примитивы Дейкстры
Понятие семафорных механизмов было введено Дейкстрой [27]. Семафор –
переменная специального типа, которая доступна параллельным процессам для проведения над ней только двух операций: «закрытия» и «открытия», названных соответственно Р- и V-операциями. Эти операции являются примитивами относи- тельно семафора, который указывается в качестве параметра операций. Здесь се- мафор выполняет роль вспомогательного критического ресурса, так как операции Р
и V неделимы при своём выполнении и взаимно исключают друг друга.
Семафорный механизм работает по схеме, в которой сначала исследуется со- стояние критического ресурса, идентифицируемое значением семафора, а затем уже осуществляется допуск к критическому ресурсу или отказ от него на некоторое время. При отказе доступа к критическому ресурсу используется режим «пассивно- го ожидания». Поэтому в состав механизма включаются средства формирования и обслуживания очереди ожидающих процессов. Эти средства реализуются суперви- зором операционной системы. Необходимо отметить, что в силу взаимного исклю- чения примитивов попытка в различных параллельных процессах одновременно выполнить примитив над одним и тем же семафором приведет к тому, что она бу- дет успешной только для одного процесса. Все остальные процессы будут взаимно исключены на время выполнения примитива. Основным достоинством использова- ния семафорных операций является отсутствие состояния «активного ожидания»,

299
что может существенно повысить эффективность работы мультипрограммной вы- числительной системы.
В настоящее время на практике используется много различных видов сема- форных механизмов [75]. Варьируемыми параметрами, которые отличают различ- ные виды примитивов, являются начальное значение и диапазон изменения значе- ний семафора, логика действий семафорных операций, количество семафоров, дос- тупных для обработки при исполнении отдельного примитива.
Обобщенный смысл примитива P(S)
1
состоит в проверке текущего значения семафора S, и если оно не меньше нуля, то осуществляется переход к следующей за примитивом операции. В противном случае процесс снимается на некоторое время с выполнения и переводится в состояние «пассивного ожидания». Находясь в списке заблокированных, ожидающий процесс не проверяет семафор непрерыв- но, как в случае активного ожидания. Вместо него на процессоре может исполнять- ся другой процесс, который реально совершает полезную работу.
Операция V(S)
2
связана с увеличением значения семафора на единицу и пере- водом одного или нескольких процессов в состояние готовности к центральному процессору.
Отметим еще раз, что операции Р и V выполняются операционной системой в ответ на запрос, выданный некоторым процессом и содержащий имя семафора в качестве параметра.
Рассмотрим первый вариант алгоритма работы семафорных операций, кото- рый представлен в листинге 6.7.
Допустимыми значениями семафоров являются только целые числа. Двоич- ным семафором будем называть семафор, максимально возможное значение кото- рого будет равно единице. В противном случае семафоры называют N-ичными.
Есть реализации, в которых семафорные переменные не могут быть отрицатель- ными, а есть и такие, где отрицательное значение указывает на длину очереди про- цессов, стоящих в состоянии ожидания открытия семафора.
1
Р – от голландского Proberen – проверить.
2
V – от голландского Verhogen – увеличить.

300

301
begin
P(S);
CS2 { Критический интервал процесса ПР2 }
V(S)
end parend end.
Семафор S имеет начальное значение, равное 1. Если процессы ПР1 и ПР2
попытаются одновременно выполнить примитив P(S), то это удастся успешно сде- лать только одному из них. Предположим, это сделал процесс ПР2, тогда он за- крывает семафор S, после чего выполняется его критический интервал. Процесс
ПР1 в рассматриваемой ситуации будет заблокирован на семафоре S. Тем самым будет гарантировано взаимное исключение.
После выполнения примитива V(S) процессом ПР2 семафор S открывается,
указывая на возможность захвата каким-либо процессом освободившегося крити- ческого ресурса. При этом производится перевод процесса ПР1 из заблокирован- ного состояния в состояние готовности.
На уровне реализации возможно одно из двух решений в отношении процес- сов, которые переводятся из очереди ожидания в очередь готовности при выполне- нии примитива V:
♦ процесс при его активизации (выборка из очереди готовности) вновь пыта- ется выполнить примитив Р, считая предыдущую попытку неуспешной;
♦ процесс при помещении его и очередь готовности отмечается как успешно выполнивший примитив Р. Тогда при его активизации управление будет передано не на повторное выполнение примитива Р, а на команду, следующую за ним. Рас- смотрим первый способ реализации. Пусть процесс ПР2 в некоторый момент вре- мени выполняет операцию P(S). Тогда семафор S становится равным нулю. Пусть далее процесс ПР1 пытается выполнить операцию P(S). Процесс ПР1 в этом слу- чае «засыпает» на семафоре S, так как значение семафора S равнялось нулю, а те- перь станет равным (-1). После выполнения критического интервала процесс ПР2