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

_______________________________Глава 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) и во входных протоколах критических секций.


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

---

---