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

284
Обеспечение взаимоисключения является одной из ключевых проблем парал- лельного программирования. При этом можно перечислить следующие требования к критическим секциям [37, 92]:
♦ в любой момент времени только один процесс должен находиться в своей критической секции;
♦ ни один процесс не должен находиться в своей критической секции беско- нечно долго;
♦ ни один процесс не должен ждать бесконечно долго входа в свой критиче- ский интервал. В частности:
• никакой процесс, бесконечно долго находящийся вне своей критической секции (что допустимо), не должен задерживать выполнение других процессов,
ожидающих входа в свои критические секции. Другими словами, процесс, рабо- тающий вне своей критической секции, не должен блокировать критическую сек- цию другого процесса;
• если два процесса хотят войти в свои критические интервалы, то принятие решения о том, кто первым войдет в критическую секцию, не должно откладывать- ся бесконечно долго;
♦ если процесс, находящийся в своём критическом интервале, завершается либо естественным, либо аварийным путем, то режим взаимоисключения должен быть отменён, с тем чтобы другие процессы получили возможность входить в свои критические секции.
Было предложено несколько способов решения этой проблемы – программные и аппаратные; частные, низкоуровневые и глобальные, высокоуровневые; преду- сматривающие свободное взаимодействие между процессами и требующие строго- го соблюдения жёстких протоколов.
Средства синхронизации и связи при
проектировании взаимодействующих
вычислительных процессов
Все известные средства для решения проблемы взаимного исключения осно- ваны на использовании специально введённых аппаратных возможностей, к кото-

285
рым относятся блокировка памяти, специальные команды типа «проверка и уста- новка» и управление системой прерываний, позволяющее организовать такие ме- ханизмы, как семафорные операции, мониторы, почтовые ящики и др. С помощью перечисленных средств можно разрабатывать взаимодействующие процессы, при исполнении которых будут корректно решаться все задачи, связанные с проблемой критических интервалов. Рассмотрим эти средства в порядке их появления, а зна- чит, по мере их усложнения, перехода к функциям операционной системы и увели- чения предоставляемых ими удобств для пользователя. При этом будем опираться на далеко не новую, но все же ещё достаточно актуальную работу Дейкстры
1
[28].
Использование блокировки памяти при синхронизации параллельных процессов
Все вычислительные машины и системы (в том числе и с многопортовыми блоками оперативной памяти) имеют такое средство для организации взаимного исключения, как блокировка памяти. Это средство запрещает одновременное ис- полнение двух (и более) команд, которые обращаются к одной и той же ячейке па- мяти. Поскольку в некоторой ячейке памяти хранится значение разделяемой пере- менной, то получить доступ к ней может только один процесс, несмотря на воз- можное совмещение выполнения команд во времени на различных процессорах
(или на одном процессоре, но с конвейерной организацией параллельного выпол- нения команд).
Механизм блокировки памяти предотвращает одновременный доступ к разде- ляемой переменной, но не предотвращает чередование доступа. Таким образом, ес- ли критические интервалы исчерпываются одной командой обращения к памяти,
данного средства может быть достаточно для непосредственной реализации взаим- ного исключения. Если же критические секции требуют более одного обращения к памяти, то задача становится сложной, но алгоритмически разрешимой. Рассмот- рим различные попытки использования механизма блокировки памяти для органи- зации взаимного исключения при выполнении критических интервалов и покажем
1
На наш взгляд, эта работа Дейкстры очень полезна с методической точки зрения. Она позволяет понять наиболее тонкие моменты в этой проблематике.

286
некоторые важные моменты, пренебрежение которыми приводит к неприемлемым или даже ошибочным решениям.
Возможные проблемы при организации взаимного исключения посредством использования только блокировки памяти
Пусть имеются два (или более) циклических процесса, в которых есть абст- рактные критические секции, то есть каждый из процессов состоит из двух частей:
некоторого критического интервала и оставшейся части кода, в которой нет работы с общими (критическими) переменными. Пусть эти два процесса асинхронно раз- деляют во времени единственный процессор либо выполняются на отдельных про- цессорах, каждый из которых имеет доступ к некоторой общей области памяти, с которой и работают критические секции. Проиллюстрируем эту ситуацию с помо- щью рис. 6.4.

287
Begin перекл := 1: {при перекл=1 в CS находится процесс ПР1 }
Parbegin
While true do
Begin while перекл = 2 do begin end;
CS1: { Критическая секция процесса ПР1 }
перекл := 2;
PR1; { оставшаяся часть процесса ПР1 }
End
And
While true do
Begin while перекл = 1 do begin end;
CS2; { Критическая секция процесса ПР2 }
перекл := 1;
PR2; { оставшаяся, часть процесса ПР2}
End
Parend
End.
Здесь и далее конструкция следующего типа parbegin...S11; S12; ... ; S1N
1
and... S21; S22; ... ; S2N
2
and... SK1; SK2; ... ; SKN
1k parend.
означает параллельность К описываемых последовательных процессов. Кон- струкция из операторов S11; S12; ... ; S1N1 выполняется оператор за оператором, о чём свидетельствует наличие точки с запятой между операторами.
Конструкция while true do

288
begin S1; S2; SN end означает, что каждый процесс может выполняться неопределённое время.
Конструкция типа begin end означает «пустой» оператор.
Итак, решение, представленное в листинге 6.1, обеспечивает взаимное исклю- чение в работе критических интервалов. Однако если бы часть программы PR1 бы- ла намного длиннее, чем программа PR2, или если бы процесс ПР1 был заблокиро- ван в секции PR1, или если бы процессор для ПР2 был с большим быстро- действием, то процесс ПР2 вскоре вынужден был бы ждать (и, может быть, чрез- вычайно долго) входа в свою критическую секцию CS2, хотя процесс ПР1 и был бы вне CS1. То есть при таком решении один процесс вне своей критической сек- ции может помещать вхождению другого в свою критическую секцию.
Попробуем устранить это блокирование с помощью использования двух об- щих переключателей, которые используются как флаги для указания, находится ли соответствующий процесс вне своей критической секции.
Пусть с каждым из процессов ПР1 и ПР2 будет связана переменная, по смыслу являющаяся переключателем, которая принимает значение true, когда процесс на- ходится в своем критическом интервале, и false – в противном случае. Прежде чем войти в свой критический интервал, процесс проверяет значение переключателя другого процесса. Если это значение равно true, процессу не разрешается входить в свой критический интервал. В противном случае процесс «включает» свой собст- венный переключатель и входит в критический интервал. Этот алгоритм взаимного исключения представлен в листинге 6.2.
Данный алгоритм не гарантирует полного выполнения условия нахождения только одного процесса внутри критического интервала. Отсутствие гарантий свя- зано с различными, в общем случае, скоростями развития процессов. Поэтому, на- пример, между проверкой значения переменной перекл2 процессом ПР1 и после- дующей установкой им значения переменной перекл1 параллельно выполняющий- ся процесс ПР2 может установить перекл2 в значение true, так как перекл1 ещё не успел установиться в значение true. Отсюда следует, что оба процесса могут войти одновременно в свои критические интервалы.

289
Листинг 6.2. Второй вариант попытки реализации взаимного исключения
Var перекл1,перекл2: boolean;
begin перекл1=false;
перекл2:=false;
parbegin while true do begin while перекл2 do begin end;
перекл1:=true;
CS1 (* Критический Интервал процесса ПР1 *)
перекл1:=false;
PR1 (* процесс ПР1 после критического интервала *)
end and while true do begin while перекл1 do begin end;
перекл2:=true;
(* Критический интервал процесса ПР2 *)
перекл2:=false;
(* процесс ПР2 после критического интервала *)
end parend end.
Следующий (третий) вариант решения этой задачи (листинг 6.3) усиливает взаимное исключение, так как в процессе ПР1 проверка значения переменной пе-

290
рекл2 выполняется после установки переменной перекл1 в значение true (анало- гично для ПР2).
Листинг 6.3. Третий вариант попытки реализации взаимного исключения var перекл1, перекл2 : boolean;
begin перекл1:=false; перекл2:=false;
parbegin
ПР1: while true do begin перекл1:=true;
while перекл2 do begin end;
CS1 {Критический интервал процесса ПР1 }
перекл1:=false;
PR1 { ПР1 после критического интервала }
end and
ПР2: while true do begin перекл2:=true;
while перекл1 do begin end;
CS2 { Критический интервал процесса ПР2 }
перекл2:=false;
PR2 { ПР2 после критического интервала }
end parend end.
Алгоритм, приведенный в листинге 6.3, также имеет свои недостатки. Дейст- вительно, возможна ситуация, когда оба процесса одновременно установят свои переключатели в значение true и войдут в бесконечный цикл. В этом случае будет

291
нарушено требование отсутствия бесконечного ожидания входа в свой критиче- ский интервал. Предположив, что скорости исполнения процессов произвольны,
мы получили такую последовательность событий, при которой процессы вообще перестанут нормально выполняться.
Рассмотренные попытки решить проблему критических интервалов иллюст- рируют некоторые тонкости, лежащие в основе этой проблемы.
Последний вариант решения задачи взаимного исключения, использующий только блокировку памяти, который мы рассмотрим, – это известный алгоритм,
предложенный математиком Деккером.
Алгоритм Деккера
Алгоритм Деккера основан на использовании трёх переменных (листинг 6.4):
перекл1, перекл2 и ОЧЕРЕДЬ. Пусть по-прежнему переменная перекл1=true тогда,
когда процесс ПР1 хочет войти в свой критический интервал (для ПР2 аналогично),
а значение переменной ОЧЕРЕДЬ указывает, чьё сейчас право сделать попытку входа, при условии, что оба процесса хотят выполнить свои критические интерва- лы.
Листинг 6.4. Алгоритм Деккера label 1, 2;
var перекл1, перекл2: boolean;
ОЧЕРЕДЬ : Integer;
Begin перекл1=false; перекл2:=false;
ОЧЕРЕДЬ:=1;
parbegin while true do begin перекл1:=true;
1:
if nepeкл2=true then if ОЧЕРЕДЬ=1 then go to 1
else begin перекл1:=false;
while ОЧЕРЕДЬ=2 do

292
begin end end else begin
CS1 { Критический интервал ПР1 }
ОЧЕРЕДЬ:=2; перекл1:=false end end and while true do begin перекл2:=1;
2: if перекл1=true then if ОЧЕРЕДЬ=2 then go to 2
else begin перекл2:=false;
while ОЧЕРЕДЬ=1 do begin end end else begin
CS2 { Критический интервал ПР2 }
ОЧЕРЕДЬ:=1; перекл2=false end end parend end.
Если перекл2=true и переклl=fa1se, то выполняется критический интервал процесса ПР2 независимо от значения переменной ОЧЕРЕДЬ. Аналогично для случая перекл2=fa1se и перекл1=true.
Если же оба процесса хотят выполнить свои критические интервалы, то есть перекл2=true и перекл1=true, то выполняется критический интервал того процесса,
на который указывало значение переменной ОЧЕРЕДЬ, независимо от скоростей развития обоих процессов. Использование переменной ОЧЕРЕДЬ совместно с пе-

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