Основы многопоточного и распределенного программирования

       

Критические секции: решения со справедливой стратегией


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

В данном разделе представлены три решения задачи критической секции со справедливой стратегией планирования: алгоритмы разрыва узла, поликлиники и билета. Они зависят только от справедливой в слабом смысле стратегии планирования, например, от кругового (round-robin) планирования, при котором каждый процесс периодически получает возмож­ность выполнения, а условия задержки, став истинными, остаются таковыми. Алгоритм раз­рыва узла достаточно прост для двух процессов и не зависит от специальных машинных инст­рукций, но сложен для n процессов. Алгоритм билета прост для любого числа процессов, но требует специальной инструкции "извлечь и сложить". Алгоритм поликлиники — это вари­ант алгоритма билета, для которого не нужны специальные машинные инструкции. Поэтому он более сложен (хотя и проще, чем алгоритм разрыва узла для n процессов).

3.3.1. Алгоритм разрыва узла

Рассмотрим решение задачи критической секции для двух процессов (листинг 3.1). Его недостаток в том, что оно не решает, какой из процессов, пытающихся войти в критическую секцию, туда действительно попадет. Например, один процесс может войти в критическую

96                                                Часть 1. Программирование с разделяемыми переменными


секцию, выполнить ее, затем вернуться к протоколу входа и снова успешно войти в критиче­ скую секцию. Чтобы решение было справедливым, должна соблюдаться очередность входа в критическую секцию, если несколько процессоров пытаются туда войти.

Алгоритм разрыва узла (также называемый алгоритмом Питерсона) — это вариант прото­кола критической секции (см. листинг 3.1), который "разрывает узел", когда два процесса пытаются войти в критическую секцию. Для этого используется дополнительная переменная, которая фиксирует, какой из процессов вошел в критическую секцию последним.

Чтобы пояснить алгоритм разрыва узла, вернемся к крупномодульной программе в листин­ге 3.1. Сейчас цель — реализовать условные неделимые действия в протоколах входа с использо­ванием только простых переменных и последовательных операторов. Для начала рассмотрим реализацию оператора await, в которой сначала выполняется цикл, пока не будет снята блоки­ровка, а затем присваивание. Протокол входа процесса CS1 должен выглядеть следующим образом.

while   (in2)   skip; inl   =   true;

Протокол входа процесса CS2 аналогичен:

while   (inl)   skip; in2   =   true;

Соответствующий протокол выхода процесса CS1 должен присвоить значение "ложь" пере­менной inl, aCS2 —переменной in2.

В этом "решении" есть проблема — два действия в протоколе входа не выполняются неде-•лимым образом, поэтому не обеспечено взаимное исключение. Например, желательным посту­словием для цикла задержки в процессе CS1 является in2 == false. К сожалению, на него влияет операция присваивания in2 = true;, поскольку оба процесса, вычислив свои условия задержки примерно в одно и то же время, могут обнаружить, что оба условия выполняются.

Когда завершается цикл while, каждый из процессов должен быть уверен в том, что дру­гой не находится в критической секции. Поэтому рассмотрим протоколы входа с обратным порядком следования операторов. Для процесса CS1:

inl  =   true; while   (in2)   skip;





Аналогично и для CS2:

in2   =  true; while   (inl)   skip;

Но этим проблема не решается. Взаимное исключение гарантируется, но появляется возможность взаимной блокировки: если обе переменные inl и in2 истинны, то ни один из циклов ожидания не завершится. Однако есть простой способ избежать взаимной блокировки — использовать до­полнительную переменную, чтобы "разорвать узел", если приостановлены оба процесса.

Пусть last — целочисленная переменная, которая показывает, какой из процессов CS1 и CS2 начал выполнять протокол входа последним. Если оба процесса пытаются войти в кри­тические секции, т.е. inl и in2 истинны, выполнение последнего из них приостанавливает­ся. Это приводит к крупномодульному решению, показанному в листинге 3.5.

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

Предположим, процесс CS1 вычисляет свое условие задержки и обнаруживает, что оно истинно. Если CS1 обнаружил, что in2 ложна, то теперь in2 может быть истинной. Но в этом случае процесс CS2 только что присвоил переменной last значение 2; следовательно, условие задержки остается истинным, если даже значение переменной in2 изменилось. Если



Поскольку условие окончания задержки не обязательно вычислять неделимым обра­зом, каждый оператор await можно заменить циклом while, который повторяется, пока условие окончания задержки ложно. Таким образом, получаем мелкомодульный алгоритм разрыва узла (листинг 3.6).

В этой программе решается проблема критических секций для двух процессов. Такую же основную идею можно использовать для решения задачи при любом числе процессов.


В част­ности, для каждого из п процессов протокол входа должен состоять из цикла, который прохо­дит п-1 этапов. На каждом этапе используются экземпляры алгоритма разрыва узла для двух процессов, чтобы определить, какие процессы проходят на следующий этап. Если гарантиру­ется, что все п-1 этапов может пройти не более, чем один процесс, то в критической секции одновременно будет находиться не больше одного процесса.

Пусть in[l:n] и last[l:n] — целочисленные массивы. Значение элемента in[i] по­казывает, какой этап выполняет процесс CS [i]. Значение last [ j ] показывает, какой про­цесс последним начал выполнять этап j. Эти переменные используются, как показано в лис­тинге 3.7. Внешний цикл for выполняется п-1 раз. Внутренний цикл for процесса CS[i] проверяет все остальные процессы. Процесс CS [ i ] ждет, если некоторый другой процесс на­ходится на этапе с равным или большим номером этапа, а процесс CS[i] был последним процессом, достигшим этапа j. Как только этапа j достигнет еще один процесс, или все про­цессы "перед" процессом CS [ i ] выйдут из своих критических секций, процесс CS [ i ] полу­чит возможность выполняться на следующем этапе. Таким образом, не более п-1 процессов могут пройти первый этап, п-2 — второй и так далее. Это гарантирует, что пройти все n эта­пов и выполнять свою критическую секцию процессы могут только по одному.



Глава 3. Блокировки и барьеры

3.3.2. Алгоритм билета

Алгоритм разрыва узла для n процессов весьма сложен и неясен, и отчасти потому, что не оче­видно обобщение алгоритма для двух процессов на случай n процессов. Построим более прозрач­ное решение задачи критической секции для n процессов, иллюстрирующее, как для упорядочения процессов используются целочисленные счетчики. Это решение называется алгоритмом билета, поскольку основано на вытягивании билетов (номеров) и последующего ожидания очереди.

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


Затем посетитель ждет, пока обслужат всех людей, получивших меньшие номера. Этот алгоритм реализован с помощью автомата для выдачи но­меров и счетчика, отображающего номер обслуживаемого посетителя. Если за счетчиком сле­дит один работник, посетители обслуживаются по одному в порядке прибытия. Описанную идею можно использовать и для реализации справедливого протокола критической секции.

Пусть number и next — целые переменные с начальными значениями 1, a turn[1:n] — массив целых с начальными значениями 0. Чтобы войти в критическую секцию, процесс cs [i ] сначала присваивает элементу turn [ i ] текущее значение number и увеличивает зна­чение number на 1. Чтобы процессы (посетители) получали уникальные номера, эти дейст­вия должны выполняться неделимым образом. После этого процесс cs [ i ] ожидает, пока значение next не станет равным полученному им номеру. При завершении критической секции процесс CS [ i ] увеличивает на 1 значение next, снова в неделимом действии.

Описанный протокол реализован в алгоритме, приведенном в листинге 3.8. Поскольку значения number и next считываются и увеличиваются в неделимых действиях, следующий предикат будет глобальным инвариантом.

TICKET:   next  >  0  л   (VI:   1  <=  i  <= n:

(CS[i]   в своей критической секции)  =>  (turn[i]   == next)   л (turn[i]   >0)   =>   (V  j :   I  <=  j   <= n,   j   !=  i:

turnfi]    !=  turnfj])   )

Последняя строка гласит, что ненулевые значения элементов массива turn уникальны. Следова­тельно, только один turn [ i ] может быть равен next, т.е. только один процесс может находиться в критической секции. Отсюда же следует отсутствие взаимоблокировок и ненужных задержек. Этот алгоритм гарантирует возможность входа при стратегии планирования, справедливой в сла­бом смысле, поскольку условие окончания задержки, ставшее истинным, таким и остается.

Листинг 3.8. Алгоритм билета: крупномодульное решение

int number  =  1,   next  =   1,   turn[l:n]   =   ( [n]   0);



И глобальный инвариант — предикат  TICKET  (см.   текст)

process CS[i  =  1  to n]   { while   (true)   {

(turn[i)   = number;  number = number + 1;) (await   (turnfi]   == next);) критическая секция; (next = next + 1;) некритическая секция; } _}__________________________________________________________________________________

В отличие от алгоритма разрыва узла, алгоритм билета имеет потенциальный недостаток, об­щий для алгоритмов, использующих увеличение счетчиков: значения number и next не ограниче-

100                                               Часть 1. Программирование с разделяемыми переменными

ны. Если алгоритм билета выполнять достаточно долго, увеличение счетчиков приведет к арифме­тическому переполнению. Однако на практике это крайне маловероятно и не является проблемой.

Алгоритм в листинге 3.8 содержит три крупномодульных действия. Оператор await легко реализуется циклом с активным ожиданием, поскольку в булевом выражении использована только одна разделяемая переменная. Последнее неделимое действие, увеличение next, можно реализовать с помощью обычных инструкций загрузки и сохранения, поскольку в лю­бой момент времени только один процесс выполняет протокол выхода. К сожалению, первое неделимое действие (чтение значения number и его увеличение) реализовать непросто.

У некоторых машин есть инструкции, которые возвращают старое значение переменной и увеличивают или уменьшают ее в одном неделимом действии. Эти инструкции выполняют именно то, что нужно для реализации алгоритма билета. В качестве примера приведем инст­рукцию "извлечь и сложить" (Fetch-and-Add — FA), которая работает следующим образом.



Для машин, не имеющих инструкции типа "извлечь и сложить", необходим другой метод. Главное требование алгоритма билета — каждый процесс должен получить уникальный но­мер. Если у машины есть инструкция неделимого увеличения, первый шаг протокола входа можно реализовать так:

turn[i]   =  number;   (number  =  number  +  1;)



Переменная number гарантированно увеличивается правильно, но процессы могут не полу­чить уникальных номеров. Например, каждый из процессов может выполнить первое при­сваивание примерно в одно и то же время и получить один и тот же номер! Поэтому важно, чтобы оба присваивания выполнялись в одном неделимом действии.

Нам уже известны два других способа решения задачи критической секции: циклические блокировки и алгоритм разрыва узла. Чтобы обеспечить неделимость получения номеров, можно воспользоваться любым из них. Например, пусть CSenter — протокол входа критиче­ской секции, a CSexit— соответствующий протокол выхода. Тогда в программе 3.9 инструк­цию "извлечь и сложить" можно заменить следующей последовательностью.

(3.10) CSenter, turn[i]   = number;   number = number+1; CSexif,

Такой подход выглядит необычным, но на практике он работает хорошо, особенно если для реализации протоколов входа и выхода доступна инструкция типа "проверить-установить". При использовании инструкции "проверить-установить" процессы получают номера не обя­зательно в соответствии с порядком, в котором они пытаются это сделать, и теоретически процесс может зациклиться навсегда. Но с очень высокой вероятностью каждый процесс по­лучит номер, и большинство номеров будут выбраны по порядку. Причина в том, что крити-

Глава 3 Блокировки и барьеры                                                                                         101

ческая секция в (3.10) очень коротка, и процесс не должен задерживаться в протоколе входа CSenter. Основной источник задержек в алгоритме билета — это ожидание, пока значение пе­ременной next не станет равно значению turn [ i ].

3.3.3. Алгоритм поликлиники

Алгоритм билета можно непосредственно реализовать на машинах, имеющих операцию типа "извлечь и сложить". Если такая инструкция недоступна, можно промоделировать часть алгоритма билета, в которой происходит получение номера с использованием (3.10).


Но для этого нужен еще один протокол критической секции, и решение не обязательно будет обла­дать свойством справедливости. Здесь представлен алгоритм поликлиники, подобный алго­ритму билета. Он обеспечивает справедливость планирования и не требует специальных ма­шинных инструкций. Естественно, он сложнее, чем алгоритм билета (см. листинг 3.9).

По алгоритму билета каждый посетитель получает уникальный номер и ожидает, пока зна­чение next не станет равным этому номеру. Алгоритм поликлиники использует другой подход. Входя, посетитель смотрит на всех остальных и выбирает номер, который больше любого дру­гого. Все посетители должны ждать, пока назовут их номер. Как и в алгоритме билета, следую­щим обслуживается посетитель с наименьшим номером. Отличие состоит в том, что для опреде­ления очередности обслуживания посетители сверяются друг с другом, а не с общим счетчиком.

Как и в алгоритме билета, пусть turn [ 1: п] — массив целых с начальными значениями 0. Чтобы войти в критическую секцию, процесс CS [ i ] сначала присваивает переменной turn [ i ] значение, которое на 1 больше, чем максимальное среди текущих значений элемен­тов массива turn. Затем CS [ i ] ожидает, пока значение turn [ i ] не станет наименьшим сре­ди ненулевых элементов массива turn. Таким образом, инвариант алгоритма поликлиники выражается следующим предикатом.

CLINIC:    (V   i:    I   <=   i   <=  n:

(CS[i]   в своей критической секции)   =>   (turn[i]   >  0)   л (turn[i]    >   0)    =>   (V   j:    1<=   j   <=   n,    d    '=   i:

turntj]   ==  0  v  turn[i]   <  turn[j])   )

Выходя из критической секции, процесс CS [ i ] присваивает turn [ i ] значение 0.

В листинге 3.10 показан крупномодульный вариант алгоритма поликлиники, соблюдаю­щий поставленные условия. Первое неделимое действие обеспечивает уникальность всех не­нулевых значений элементов массива turn. Оператор for гарантирует, что следствие преди­ката CLINIC истинно, когда процесс Р [ i ] выполняет свою критическую секцию.


Этот алго­ ритм удовлетворяет условию взаимного исключения, поскольку одновременно не могут быть истинными условия turn [ i ] i=0 для всех i и CLINIC. Ненулевые значения элементов массива turn уникальны и, как обычно, предполагается, что каждый процесс в конце концов выходит из своей критической секции, поэтому взаимных блокировок нет. Отсутствуют также излишние задержки процессов, поскольку сразу после выхода процесса CS [ i ] из критической секции turn[i] получает значение 0. Наконец, алгоритм поликлиники гарантирует воз­можность входа в критическую секцию, если планирование справедливо в слабом смысле, поскольку ставшее истинным условие окончания задержки остается таковым. (Значения элементов массива turn в алгоритме поликлиники могут быть как угодно велики, но значе­ния элементов массива turn продолжают возрастать, только если всегда есть хотя бы один процесс, пытающийся войти в критическую секцию. Однако на практике это маловероятно.)

Алгоритм поликлиники в листинге 3.10 нельзя непосредственно реализовать на совре­менных машинах. Чтобы присвоить переменной turn [ i ], необходимо найти максимальное из n значений, а оператор await дважды обращается к разделяемой переменной turn [ j ]. Эти операции можно было бы реализовать неделимым образом, используя еще один прото­кол критической секции, например, алгоритм разрыва узла, но это слишком неэффективно. К счастью, есть более простой выход.

102                                               Часть 1. Программирование с разделяемыми переменными

Листинг 3.10. Алгоритм поликлиники: крупномодульное решение

int  turn[l:n]   =   ([n]   0);

i#  глобальный инвариант — предикат  CLINIC  (си.   текст)

process CS[i =  1  to n]   { while   (true)   {

(turn[i]   = max(turn[l:n])   +  1;} for   [j   =  1  to n st j   !=  i]

(await   (turn[j]   ==  0 or turn[i]   <  turn[j]);) критическая секция -, turn[i]   =  0; некритическая секция -, } }____________________________________________________________________________________



Если необходимо синхронизировать n процессов, полезно сначала разработать решение для двух процессов, а затем обобщить его (так мы поступили с алгоритмом разрыва узла). Итак, рассмотрим следующий протокол входа для процесса csi.

turnl =  turn2  + 1;

while   (turn2   !=  0 and turnl  > turn2)   skip;

Аналогичен и следующий протокол входа для процесса CS2.

turn2   =   turnl  +  1;

while   (turnl   !=  0  and turn2  > turnl)   skip,-

Каждый процесс присваивает значение своей переменной turn в соответствии с оптимизиро­ванным вариантом (ЗЛО), а операторы await реализованы в виде цикла с активным ожиданием.

Проблема этого "решения" в том, что ни операторы присваивания, ни циклы while не выпол­няются неделимым образом. Следовательно, процессы могут начать выполнение своих протоколов входа приблизительно одновременно, и оба присвоят переменным turnl и turn2 значение 1. Ес­ли это случится, оба процесса окажутся в своих критических секциях в одно и то же время.

Частично решить эту проблему можно по аналогии с алгоритмом 3.6: если обе перемен­ные turnl и turn2 имеют значения 1, то один из процессов должен выполняться, а другой — приостанавливаться. Например, пусть выполняется процесс с меньшим номером; тогда в условии цикла задержки процесса CS2 изменим второй конъюнкт: turn2 >= turnl.

К сожалению, оба процесса все еще могут одновременно оказаться в критической секции. Допустим, что процесс csi считывает значение turn2 и получает 0. Процесс CS2 начинает выполнять свой протокол входа, определяет, что переменная turnl все еще имеет значение О, присваивает turn2 значение 1 и входит в критическую секцию. В этот момент CS1 может продолжить выполнение своего протокола входа, присвоить turnl значение 1 и затем войти в критическую секцию, поскольку переменные turnl и turn2 имеют значение 1, и процесс CS1 в этом случае получает преимущество. Такая ситуация называется состоянием гонок, поскольку процесс CS1 "обгоняет" CS2 и не учитывает, что процесс CS2 изменил переменную turn2.



Чтобы избежать состояния гонок, необходимо, чтобы каждый процесс присваивал своей пере­менной turn значение 1 (или любое отличное от нуля) в самом начале протокола входа. После этого процесс должен проверить значение переменной turn других процессов и переприсвоить значение своей переменной, т.е. протокол входа процесса CS1 выглядит следующим образом.

turnl  =   1;   turnl  =   turn2   +  1;

while   (turn2   !=  0 and turnl > turn2)   skip;

Протокол входа процесса CS2 аналогичен.

turn2  =  1;   turn2   =  turnl  +  1;

while   (turnl   !=  0 and turn2  >=  turnl)   skip,-

Глава 3. Блокировки и барьеры                                                                                                   103

Теперь один процесс не может выйти из цикла whi 1е, пока другой не закончит начатое ранее присваивание turn. В этом решении процессу CS1 отдается преимущество перед CS2, когда у обоих процессов ненулевые значения переменной turn.

Протоколы входа процессов несимметричны, поскольку условие задержки второго цикла слегка отличается. Однако их можно записать и в симметричном виде. Пусть (а,Ь) и (с, d) — пары целых чисел. Определим отношение сравнения для них таким образом:

(a,b)   >   (c,d)   == true,     если а > с или а == с и b > d ==  false,   иначе

Теперь можно переписать условие turnl > turn2 процесса CS1 в виде (turnl,!) > (turn2,2), аусловие turn2 >= turnl в процессе CS2 — (turn2, 2) > (turnl,!).

Достоинство симметричной записи в том, что теперь алгоритм поликлиники для двух процессов легко обобщить на случай п процессов (листинг 3.11). Каждый из процессов сна­чала показывает, что он собирается войти в критическую секцию, присваивая своей перемен­ной turn значение 1. Затем он находит максимальное значение из всех turn [ i ] и прибавля­ет к нему 1. Наконец, процесс запускает цикл for и, как в крупномодульном решении, ожи­дает своей очереди. Отметим, что максимальное значение массива определяется считыванием всех его элементов и выбором наибольшего.Эти действия не являются неделимыми, поэтому точный результат не гарантируется. Однако, если несколько процессов получают одно и то же значение, они упорядочиваются в соответствии с правилом, описанным выше.

Листинг 3.11. Алгоритм поликлиники: мелкомодульное решение

mt  turn[l:n]   =   ([n]    0);

process CS[i  =  1  to n]   { while   (true)   {

turn[i]   =   1;   turn[i]   = max(turn[1:n])+1; for   [j   =   1   to n  st  j    '=  i] while   (turntj]    '=  0  and

(turn[i],i)   >   (turn[j],j))   skip; критическая секция; turn[i]   =  0; некритическая секция; } _}_______________________________________________________________________________


Содержание раздела