Блокировки и барьеры
_______________________________Глава 3
Блокировки и барьеры
Напомним, что в параллельных программах используются два основных типа синхронизации: взаимное исключение и условная синхронизация. В этой главе рассмотрены критические секции и барьеры, показывающие, как программировать эти типы синхронизации. Задача критической секции связана с программной реализацией неделимых действий; эта задача возникает в большинстве параллельных программ. Барьер — это точка синхронизации, оторой должны достигнуть все процессы перед тем, как продолжится выполнение одного из их. Барьеры необходимы во многих синхронных параллельных программах.
Взаимное исключение обычно реализуется посредством блокировок, которые защищают ритические секции кода. В разделе 3.1 определена задача критической секции и представле-ю крупномодульное решение, использующее оператор await для реализации блокировки. i разделе 3.2 разработаны мелкомодульные решения с использованием так называемых цик-ических блокировок (spin lock). В разделе 3.3 представлены три решения со справедливой тратегией: алгоритмы разрыва узла, билета и поликлиники. Эти разные решения иллюстри->уют различные подходы к решению данной задачи и имеют разные быстродействия и свой-:тва справедливости. Решения задачи критической секции также важны, поскольку их можно (спользовать для реализации операторов await и, следовательно, произвольных неделимых действий. Как это сделать, показано в конце раздела 3.2.
Во второй половине данной главы представлены три способа выполнения параллельных вычислений: барьерная синхронизация, алгоритмы, параллельные по данным, и так называемый портфель задач. Как было отмечено ранее, многие задачи можно решить синхронными итерационными алгоритмами, в которых несколько идентичных процессов итеративно обрабатывают разделяемый массив. Алгоритмы этого типа называются алгоритмами, параллельными по данным, поскольку разделяемые данные обрабатываются параллельно и синхронно.
В таком алгоритме каждая итерация обычно зависит от результатов предыдущей итерации. Следовательно, в конце итерации более быстрый процесс должен ожидать более медленные, чтобы начать следующую итерацию. Такой тип точки синхронизации называется барьером. В разделе 3.4 описываются различные способы реализации барьерной синхронизации и обсуждается согласование их быстродействия. В разделе 3.5 приведено несколько примеров алгоритмов, параллельных по данным и использующих барьеры, а также кратко описана архитектура синхронных мультипроцессоров (SIMD-машин), которые специально приспособлены для реализации алгоритмов, параллельных по данным. Поскольку SIMD-машины выполняют инструкции в блокированном шаге на каждом процессоре, они автоматически реализуют барьеры после каждой машинной инструкции.
В разделе 3.6 представлен другой полезный метод выполнения параллельных вычислений, называемый портфелем задач. Этот подход можно использовать для реализации рекурсивного параллелизма и итерационного параллелизма при фиксированном числе независимых задач. Важное свойство парадигмы "портфель задач" состоит в том, что она облегчает сбалансированную загрузку, т.е. гарантирует, что все процессоры выполняют примерно равные объемы работы. В парадигме "портфель задач" использованы блокировки для реализации "портфеля" ибарьероподобная синхронизация для определения того, что вычисления окончены.
В программах этой главы используется активное ожидание — реализация синхронизации, при которой процесс циклически проверяет некоторое условие до тех пор, пока оно не станет
88 Часть 1. Программирование с разделяемыми переменными
истинным. Достоинство синхронизации с активным ожиданием состоит в том, что для ее реализации достаточно машинных инструкций современных процессоров. Активное ожидание неэффективно при разделении процессора несколькими процессами (когда их выполнение перемежается), но, когда каждый процесс выполняется на отдельном процессоре, оно эффективно.
Многие годы для высокопроизводительных научных вычислений использовались большие мультипроцессоры. В настоящее время на рабочих станциях и даже на персональных компьютерах становятся обычными небольшие мультипроцессоры (с двумя-четырьмя ЦПУ). Как будет показано в разделе 6.2, в ядре операционных систем для мультипроцессоров используется синхронизация с активным ожиданием. Более того, синхронизацию с активным ожиданием использует само аппаратное обеспечение — например, при передаче данных по шинам памяти и локальным сетям.
Библиотеки программ для мультипроцессорных машин включают процедуры для блокировок и иногда для барьеров. Эти библиотечные процедуры реализуются с помощью методов, описанных в данной главе. Две такие библиотеки представлены в конце главы 4 (Pthreads) и главе 12 (ОрепМР).
3.1. Задача критической секции
Задача критической секции — это одна из классических задач параллельного программирования. Она стала первой всесторонне изученной проблемой, но интерес к ней не угасает, '• поскольку критические секции кода есть в большинстве параллельных программ. Кроме того, решение этой задачи можно использовать для реализации произвольных операторов await. В данном разделе задача определена и разработано ее крупномодульное решение. В следующих двух разделах построены мелкомодульные решения, иллюстрирующие различные способы решения этой задачи с использованием разных типов машинных инструкций.
В задаче критической секции n процессов многократно выполняют сначала критическую, а затем некритическую секцию кода. Критической секции предшествует протокол входа, а следует за ней протокол выхода. Таким образом, предполагается, что процесс имеет следующий вид: process CS[i = 1 to n] { while (true) { протокол входа; критическая секция; протокол выхода; некритическая секция; } }
Каждая критическая секция является последовательностью операторов, имеющих доступ к некоторому разделяемому объекту. Каждая некритическая секция — это еще одна последовательность операторов.
Предполагается, что процесс, вошедший в критическую секцию, обязательно когда- нибудь из нее выйдет; таким образом, процесс может завершиться только вне критической секции. Наша задача— разработать протоколы входа и выхода, которые удовлетворяют следующим четырем свойствам.
(3.1) Взаимное исключение. В любой момент времени только один процесс может выполнять свою критическую секцию.
(3.2) Отсутствие взаимной блокировки (живая блокировка). Если несколько процессов пытаются войти в свои критические секции, хотя бы один это осуществит.
(3.3) Отсутствие излишних задержек. Если один процесс пытается войти в свою критическую секцию, а другие выполняют свои некритические секции или завершены, первому процессу разрешается вход в критическую секцию.
(3.4) Возможность входа. Процесс, который пытается войти в критическую секцию, когда-нибудь это сделает.
Глава 3 Блокировки и барьеры
Первые три свойства являются свойствами безопасности, четвертое — свойством живучести. Для взаимного исключения плохим является состояние, когда два процесса находятся в своих критических секциях. Для отсутствия взаимной блокировки плохим является состояние, когда все процессы ожидают входа, но ни один не может этого сделать. (В решении с активным ожиданием это называется отсутствием живой блокировки, поскольку процессы работают, но навсегда зациклены.) Для отсутствия излишних задержек плохим является состояние, когда один-единственный процесс, пытающийся войти в критическую секцию, не может этого сделать, даже если все остальные процессы находятся вне критических секций. Возможность входа является свойством живучести, поскольку зависит от стратегии планирования (об этом ниже).
Тривиальный способ решения задачи критической секции состоит в ограничении каждой критической секции угловыми скобками, т.е. в использовании безусловных операторов await. Из семантики угловых скобок сразу следует условие (3.2) — взаимное исключение.
Другие три свойства будут удовлетворяться при безусловно справедливой стратегии планирования, поскольку она гарантирует, что процесс, который пытается выполнить неделимое действие, соответствующее его критической секции, в конце концов это сделает, независимо от действий других процессов. Однако при таком "решении" возникает вопрос о том, как реализовать угловые скобки.
Все четыре указанных свойства важны, однако наиболее существенным является взаимное исключение. Таким образом, сначала мы сосредоточимся на нем, а затем узнаем, как обеспечить выполнение остальных. Для описания свойства взаимного исключения необходимо определить, находится ли процесс в своей критической секции. Чтобы упростить запись, построим решение для двух процессов, CS1 и CS2; оно легко обобщается для п процессов.
Пусть inl и in2 — логические переменные с начальным значением "ложь". Когда процесс CS1 (CS2) находится в своей критической секции, переменной inl (in2) присваивается значение "истина". Плохое состояние, которого мы будем стараться избежать, — если и inl, и in2 имеют значение "истина". Таким образом, нам нужно, чтобы для любого состояния выполнялось отрицание условия плохого состояния.
MUTEX: -i(inl л in2)
Как сказано в разделе 2.7, предикат MUTEXдолжен быть глобальным инвариантом. Для этого он должен выполняться в начальном состоянии и после каждого присваивания переменным ml и in2. В частности, перед тем, как процесс CS1 войдет в критическую секцию, сделав тем самым inl истинной, он должен убедиться, что in2 ложна. Это можно реализовать с помощью следующего условного неделимого действия.
(await (>in2) inl = true;)
Процессы симметричны, поэтому во входном протоколе процесса CS2 используется аналогичное условное неделимое действие. При выходе из критической секции задерживаться ни к чему, поэтому защищать операторы, которые присваивают переменным inl и in2 значение "ложь", нет необходимости.
Решение показано в листинге 3.1. По построению программа удовлетворяет условию взаимного исключения. Взаимная блокировка здесь не возникнет: если бы каждый процесс был заблокирован в своем протоколе входа, то обе переменные, и inl, и in2, были бы истинными, а это противоречит тому, что в данной точке кода обе они ложны. Излишних задержек также нет, поскольку один процесс блокируется, только если другой находится в критической секции, поэтому нежелательные паузы при выполнении программы не возникают. (Все эти свойства программ можно доказать формально, использовав метод исключения конфигураций, представленный в разделе 2\8.)
Наконец, рассмотрим свойство живучести: процесс, который пытается войти в критическую секцию, в конце концов сможет это сделать. Если процесс CS1 пытается войти, но не может, то переменная in2 истинна, и процесс CS2 находится в критической секции. По предположению процесс в конце концов выходит из критической секции, поэтому переменная in2 когда-нибудь станет ложной, а переменная защиты входа процесса CS1 — истинной.
90 Часть 1. Программирование с разделяемыми переменными
Если процессу csi вход все еще не разрешен, это значит, что либо диспетчер несправедлив, либо процесс CS2 снова достиг входа в критическую секцию. В последнем случае описанный выше сценарий повторяется, так что когда-нибудь переменная in2 станет ложной. Таким образом, либо переменная in2 становится ложной бесконечно часто, либо процесс CS2 завершается, и переменная in2 принимает значение "ложь" и остается в таком состоянии. Для того чтобы процесс CS2 в любом случае входил в критическую секцию, нужно обеспечить справедливую в сильном смысле стратегию планирования. (Аргументы для процесса CS2 симметричны.) Напомним, однако, что справедливая в сильном смысле стратегия планирования непрактична, и вернемся к этому вопросу в разделе 3.3.
3.2. Критические секции: активные блокировки
В крупномодульном решении, приведенном в листинге 3.1, используются две переменные. При обобщении данного решения для n процессов понадобятся п переменных. Однако существует только два интересующих нас состояния: или некоторый процесс находится в своей критической секции, или ни одного там нет. Независимо от числа процессов, для того, чтобы различить эти два состояния, достаточно одной переменной.
Пусть lock — логическая переменная, которая показывает, находится ли процесс в критической секции, т.е. lock истинна, когда одна из inl или in2 истинна, в противном случае lock ложна. Таким образом, получим следующее условие:
lock == (inl v in2)
Используя lock вместо inl и in2, можно реализовать протоколы входа и выхода программы 3.1 так, как показано в листинге 3.2.
Преимущество протоколов входа и выхода, показанных в листинге 3.2, по отношению к протоколам в листинге 3.1 состоит в том, что их можно использовать для решения задачи критической секции при любом числе процессов. Все они будут разделять переменную lock и выполнять одни и те же протоколы.
3.2.1. "Проверить-установить"
Использование переменной lock вместо inl и 1п2, показанное в листинге 3.2, очень важно, поскольку почти у всех машин, особенно у мультипроцессоров, есть специальная инструкция для реализации условных неделимых действий. Здесь применяется инструкция, называемая "проверить-установить".8 В следующем разделе будет использована еще одна подобная инструкция — "извлечь и сложить". Дополнительные инструкции описываются в упражнениях.
Инструкция "проверить-установить" (test and set — TS) в качестве аргумента получает разделяемую переменную lock и возвращает логическое значение. В неделимом действии инструкция TS считывает и сохраняет значение переменной lock, присваивает ей значение "истина", а затем возвращает сохраненное предыдущее значение переменной lock. Результат действия инструкции TS описывается следующей функцией:
(36) bool TS(bool lock) {
{ bool initial = lock; /* сохранить начальное значение */ lock = true; /* установить lock */
return initial; ) /* возвратить начальное значение */ }
Используя инструкцию TS, можно реализовать крупномодульный вариант программы 3.2 по алгоритму, приведенному в листинге 3.3. Условные неделимые действия в программе 3.2 заменяются циклами. Циклы не завершаются, пока переменная lock не станет ложной, т.е. инструкция TS возвращает значение "ложь". Поскольку все процессы выполняют одни и те же протоколы, приведенное решение работает при любом числе процессов. Использование блокирующей переменной, как в листинге 3.3, обычно называется циклической блокировкой (spin lock), поскольку процесс постоянно повторяет цикл, ожидая снятия блокировки.
Программа в листинге 3.3 имеет следующие свойства. Взаимное исключение (3 2) обеспечено если несколько процессов пытаются войти в критическую секцию, только один из них первым изменит значение переменной lock сложного на истинное, следовательно, только один из
1 Напомним, что термин "установить" (без указания значения) обычно применяется в смысле "присвоитьзначение true (или 1)", а "сбросить" — "присвоить false (или 0)". — Прим. ред.
92 Часть 1 Программирование с разделяемыми переменными
процессов успешно завершит свой входной протокол и войдет в критическую секцию. Отсутствие взаимной блокировки (3.3) следует из того, что, если оба процесса находятся в своих входных протоколах, то lock ложна, и, следовательно, один из процессов войдет в свою критическую секцию. Нежелательные задержки (3.4) не возникают, поскольку, если оба процесса находятся вне своих критических секций, lock ложна, и, следовательно, один из процессов может успешно войти в критическую секцию, если другой выполняет некритическую секцию или был завершен.
С другой стороны, выполнение свойства возможности входа (,3.5) не гарантируется.
Если используется справедливая в сильном смысле стратегия планирования, то попытки процесса войти в критическую секцию завершатся успехом, поскольку переменная lock бесконечно часто будет принимать значение "ложь". При справедливой в слабом смысле стратегии планирования, которая встречается чаще всего, процесс может навсегда зациклиться в протоколе входа. Однако это может случиться, только если другие процессы все время успешно входят в свои критические секции, чего на практике быть не должно. Следовательно, решение в листинге 3.3 должно удовлетворять условию справедливой стратегии планирования.
Решение задачи критической секции, аналогичное приведенному в листинге 3.3, может быть реализовано на любой машине, если у нее есть инструкция, проверяющая и изменяющая разделяемую переменную в одном неделимом действии. Например, в некоторых машинах есть инструкция инкремента (увеличения), которая увеличивает целое значение переменной и устанавливает код условия, указывающий, положительно ли значение результата. Используя эту инструкцию, можно построить протокол входа, основанный на переходе от нуля к единице. В упражнениях рассмотрены несколько типичных инструкций такого рода (Это любимый вопрос экзаменаторов1)
Построенное решение с циклической блокировкой и те решения, которые вы, возможно, составите сами, обладают свойством, которое стоит запомнить.
(3.7) Протоколы выхода в решении с циклической блокировкой. В решении задачи критической секции с циклической блокировкой протокол выхода должен просто присваивать разделяемым переменным их начальные значения.
В начальным состоянии (см. листинг 3.1) обе переменные inl и in2 ложны, как и переменная lock (см. листинги 3.2 и 3.3).
3.2.2. "Проверить-проверить-установить"
Хотя решение в листинге 3.3 верно, эксперименты на мультипроцессорных машинах показывают его низкую производительность, если несколько процессов соревнуются за доступ к критической секции. Причина в том, что каждый приостановленный процесс непрерывно обращается к разделяемой переменной lock.
Эта "горячая точка" вызывает
Глава 3. Блокировки и барьеры 93.
конфликт при обращении к памяти, который снижает производительность модулей памяти и шин, связывающих процессор и память.
К тому же инструкция TS при каждом вызове записывает значение в lock, даже если оно не изменяется. Поскольку в мультипроцессорных машинах с разделяемой памятью для уменьшения числа обращений к основной памяти используются кэши, ts выполняется гораздо дольше, чем простое чтение значения разделяемой переменной. (Когда переменная записывается одним из процессоров, ее копии нужно обновить или сделать недействительными в кэшах других процессоров.)
Затраты на обновление содержимого кэш-памяти и конфликты при обращении к памяти можно сократить, изменив протокол входа. Вместо того, чтобы выполнять цикл, пока инструкция TS не возвратит значение "истина", можно использовать следующий протокол.
Этот протокол называется "проверить-проверить-установить", поскольку процесс просто проверяет lock до тех пор, пока не появится возможность выполнения TS. В двух дополнительных циклах lock просто проверяется, так что ее значение можно прочесть из кэш-памяти, не влияя на другие процессоры. Таким образом, конфликты при обращении к памяти сокращаются, но не исчезают. Если флажок блокировки lock сброшен, то как минимум один, а возможно, и все приостановленные процессы могут выполнить инструкцию TS, хотя продолжаться будет только один из них. Ниже мы опишем способы дальнейшего сокращения конфликтов обращения к памяти.
В листинге 3.4 представлено полное решение задачи критической секции, использующее входной протокол "проверить-проверить-установить". Как и ранее, протокол выхода просто очищает переменную lock.
3.2.3. Реализация операторов await
Любое решение задачи критической секции можно использовать для реализации безусловного неделимого действия (S; >, скрывая внутренние контрольные точки от других процессов.
Пусть CSenter — входной протокол критической секции, a CSexit — соответствующий выходной. Тогда действие (S;} можно реализовать так:
CSenter,
S; CSexit;
94 Часть 1. Программирование с разделяемыми переменными
Здесь предполагается, что все секции кода процессов, которые изменяют или ссылаются на переменные, изменяемые в S (или изменяют переменные, на которые ссылается S), защищены аналогичными входными и выходными протоколами. В сущности, скобки ( и) заменены процедурами CSenter и CSexit.
Приведенный выше образец кода можно использовать в качестве "кирпичика" для реализации операторов (await (В) S;). Напомним, что условное неделимое действие приостанавливает процесс, пока условие в не станет истинным, после чего выполняется S. Когда начинается выполнение S, условие в должно быть истинным. Чтобы обеспечить неделимость всего действия, можно использовать протокол критической секции, скрывая промежуточные состояния в в. Для циклической проверки условия в, пока оно не станет истинным, можно использовать следующий цикл.
CSenter,
while (!B) { ??? }
S;
CSexit;
Здесь предполагается, что критические секции всех процессов, изменяющих переменные, используемые в в или S, или использующих переменные, изменяемые в S, защищены такими же протоколами входа и выхода.
Остается выяснить, как реализовать тело цикла, указанного выше. Если тело выполняется, значит, условие в было ложным. Следовательно, единственный способ сделать условие в истинным — изменить в другом процессе значения переменных, входящих в это условие. Предполагается, что все операторы, изменяющие эти переменные, находятся в критических секциях, поэтому, ожидая, пока условие в выполнится, нужно выйти из критической секции. Но для обеспечения неделимости вычисления в и выполнения S перед повторным вычислением условия в необходимо вновь войти в критическую секцию. Возможным уточнением указанного выше протокола может быть следующее.
(3.8) CSenter;
while (!B) { CSexit; CSenter, }
S;
CSexit;
Данная реализация сохраняет семантику условных неделимых действий при условии, что протоколы критических секций гарантируют взаимное исключение. Если используемая стратегия планирования справедлива в слабом смысле, то процесс, выполняющий (3.8), в конце концов завершит цикл при условии, что в когда-нибудь станет (и останется) истинным. Если стратегия планирования справедлива в сильном смысле, цикл завершится, если условие в становится истинным бесконечно часто.
Программа (3.8) верна, но не эффективна, поскольку процесс, выполняющий ее, повторяет "жесткий" цикл, постоянно выходя из критической секции и входя в нее, но не может продвинуться дальше, пока какой-нибудь другой процесс не изменит переменных в условии в. Это приводит к конфликту обращения к памяти, поскольку каждый приостановленный процесс постоянно обращается к переменным, используемым в протоколах критической секции и условии в.
Чтобы сократить количество конфликтов обращения к памяти, процесс перед повторной попыткой войти в критическую секцию должен делать паузу. Пусть Delay — некоторый код, замедляющий выполнение процесса. Тогда программу (3.8) можно заменить следующим протоколом, реализующим условное неделимое действие.
(3.9) CSenter;
while С.В) { CSexit; Delay; CSenter, }
S;
CSexit;
Глава 3 Блокировки и барьеры 95
Кодом Delay может быть, например, пустой цикл, который выполняется случайное число раз. (Во избежание конфликтов памяти в цикле в коде Delay следует использовать только локальные переменные.) Этот тип протокола "отхода" ("back-off") полезен и в самих протоколах CSenter; например, его можно использовать вместо skip в цикле задержки простого протокола "проверить-установить" (см. листинг 3.3).
Если S состоит из одного оператора skip, протокол (3.9) можно упростить, опустив S.
Если условие В удовлетворяет свойству "не больше одного" (2.2), то оператор (await (В);) можно реализовать в следующем виде, while ('В) skip;
Как упоминалось в начале этой главы, синхронизация с активным ожиданием часто применяется в аппаратном обеспечении. Фактически протокол, аналогичный (3.9), используется для синхронизации доступа в локальных сетях Ethernet. Чтобы передать сообщение, контроллер Ethernet отправляет его в сеть и следит, не возник ли при передаче конфликт с сообщениями, отправленными примерно в это же время другими контроллерами. Если конфликт не обнаружен, то считается, что передача завершилась успешно. В противном случае контроллер делает небольшую паузу, а затем повторяет передачу сообщения. Чтобы избежать состояния гонок, в котором два контроллера постоянно конфликтуют из-за того, что делают одинаковые паузы, их длительность выбирается случайным образом из интервала, который удваивается при каждом возникновении конфликта. Такой протокол называется двоичным экспоненциальным протоколом отхода. Эксперименты показывают, что протокол такого типа полезен также в (3.9) и во входных протоколах критических секций.