Критические секции: решения со справедливой стратегией
Решения задачи критической секции с циклической блокировкой обеспечивают взаимное исключение, отсутствие взаимных блокировок, активных тупиков и нежелательных пауз. Однако для обеспечения свойства возможности входа (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; некритическая секция; } _}_______________________________________________________________________________
