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

       

Барьерная синхронизация


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

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

while   (true)   { со   [i  =  1  to n]

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

код решения задачи i; ос }

К сожалению, этот подход весьма неэффективен, поскольку оператор со порождает п процессов на каждой итерации. Создать и уничтожить процессы намного дороже, чем реали­зовать их синхронизацию. Поэтому альтернативная структура алгоритма делает его намного эффективнее — процессы создаются один раз в начале вычислений, а потом синхронизиру­ются в конце каждой итерации.

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

код решения задачи i; ожидание завершения всех п задач; } }

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

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


3.4.1. Разделяемый счетчик

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

(3.11)   int count =  0;

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

код реализации задачи  i; (count = count +  1;) (await   (count  == n);) } }



Оператор await можно реализовать циклом с активным ожиданием. При наличии недели­мой инструкции типа fa ("извлечь и сложить"), определенной в разделе 3.3, этот барьер можно реализовать следующим образом.

FA(count,!) ;

while   (count   != n)   skip;

Однако данный код не вполне соответствует поставленной задаче. Сложность состоит втом, что значением count должен быть 0 в начале каждой итерации, т.е. count нужно об­нулять каждый раз, когда все процессы пройдут барьер. Более того, она должна иметь значе­ние о перед тем, как любой из процессов вновь попытается ее увеличить.

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

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

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


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

3.4.2. Флаги и управляющие процессы

Один из способов избежать конфликтов обращения к памяти — реализовать счетчик count с помощью n переменных, значения которых прибавляются к одному и тому же зна­чению. Пусть, например, есть массив целых arrive [l:n] с нулевыми начальными значе­ниями. Заменим операцию увеличения счетчика count в программе (3.11) присваиванием arrive [ i ] = 1. Тогда глобальным инвариантом станет такой предикат, count == (arrive[l] + ... + arrivefn])

Если элементы массива arrive хранятся в разных строках кэш-памяти (для их бескон­фликтной записи процессами), то конфликтов обращения к памяти не будет.

В программе (3.11) осталось реализовать оператор await и обнулить элементы массива arrive в конце каждой итерации. Оператор await можно было бы записать в таком виде.

(await   ((arrivefl]   +   ...   + arrivetn])   == n);)

lo в таком случае снова возникают конфликты обращения к памяти, причем это решение акже неэффективно, поскольку сумму элементов arrive [ i ] теперь постоянно вычисляет каждый ожидающий процесс Worker.

Обе проблемы — конфликтов обращения к памяти и обнуления массива — можно ре-иить, используя дополнительный набор разделяемых значений и еще один процесс, Соог-Jinator. Пусть каждый процесс Worker вместо того, чтобы суммировать элементы массива irrive, ждет, пока не станет истинным единственное логическое значение. Пусть соп-:inue[l:n] — дополнительный массив целых с нулевыми начальными значениями. После того как Worker [ i ] присвоит 1 элементу arrive [ i ], он должен ждать, пока значением пе­ременной continue [ i ] не станет 1.

(3.12)   arrive [i]   =  1;



(await   (continueti]   ==  1);)

Процесс Coordinator ожидает, пока все элементы массива arrive не станут равны 1, за­тем присваивает значение 1 всем элементам массива continue.

(313) for   [i  =  1  to n]   (await   (arrive[i]   ==  1);) for   [i   =   1   to  n]   continueti]   =   1;

Операторы await в (3.12) и (3.13) можно реализовать в виде циклов while, поскольку каждый из них ссылается только на одну разделяемую переменную. В процессе Coordina­tor для ожидания установки всех элементов arrive можно использовать оператор for. По­скольку для продолжения процессов Worker должны быть установлены все элементы ar­rive, процесс Coordinator может проверять их в любом порядке. Конфликтов обращения к памяти теперь не будет, поскольку процессы ожидают изменения различных переменных, каждая из которых может храниться в своей строке кэш-памяти.

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

Переменные arrive и continue в программах (3.12) и (3.13) являются примерами так называемого флага (флажка). Его устанавливает (поднимает) один процесс, чтобы сообщить другому о выполнении условия синхронизации. Дополним программы (3.12) и (3.13) кодом, который сбрасывает флаги (присваивая им значение 0) для подготовки к следующей итера­ции. При этом используются два основных правила.

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

Первое правило гарантирует, что флаг не будет сброшен, пока процесс не определит, что он установлен. В соответствии с этим правилом в (3.12) флаг continue [ i] должен сбрасывать­ся процессом Worker [ i], а обнулять все элементы массива arrive в (3.13) должен Coordi­nator. В соответствии со вторым правилом один процесс не устанавливает флаг, пока он не сброшен другим. В противном случае, если другой синхронизируемый процесс в дальнейшем ожидает повторной установки флага, возможна взаимная блокировка.


В (3.13) это означает, что Coordinator должен сбросить arrive [i] перед установкой continue [i]. Coordi­nator может сделать это, выполнив еще один оператор for после первого for в (3.13). Co­ordinator может также сбросить arrive [i] сразу после того, как дождался его установки. Добавив код сброса флагов, получим барьер с управляющим (листинг 3.12).



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

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

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

рабочий процесс выполняется на отдельном процессоре, то все они подойдут к барьеру при­мерно в одно время. Таким образом, все флаги arrive будут установлены практически одно­временно. Однако процесс Coordinator проверяет флаги в цикле, по очереди ожидая, когда каждый из них будет установлен.

Обе проблемы можно преодолеть, объединив действия управляющего и рабочих процессов так, чтобы каждый рабочий процесс был одновременно и управляющим. Организуем рабочие процессы вдерево (рис. 3.1). Сигнал о том, что процесс по­дошел к барьеру (флаг arrive[i]), отсылается вверх по дереву, а сигнал о разрешении продолже­ния выполнения (флаг continue [i])— вниз. Узел рабочего процесса ждет, когда к барьеру по­дойдут его сыновья, после чего сообщает роди­тельскому узлу о том, что он тоже подошел к барьеру.


Когда все сыновья корневого узла подошли к барьеру, это значит, что все осталь­ные рабочие узлы тоже подошли к барьеру. Тогда корневой узел может сообщить сыновьям, что они могут продолжить выполнение. Те, в свою очередь, разрешают продолжить выполне­ние своим сыновьям, и так далее. Специфические действия, которые должен выполнить узел каждого вида, описаны в листинге 3.13. Операторы await в данном случае можно реализо­вать в виде циклов активного ожидания.





Реализация, приведенная в листинге 3.13, называется барьером с объединяющим деревом, поскольку каждый процесс объединяет результаты работы своих сыновних процессов и от­правляет родительскому. Этот барьер использует столько же переменных, сколько и "центра­лизованная" версия с управляющим процессом, но он намного эффективнее при больших п, поскольку высота дерева пропорциональна Iog2n.

Объединяющее дерево можно сделать еще эффективнее, если корневой узел будет отправлять единственное сообщение, которое разрешает продолжать работу всем остальным узлам. Например, узлы могут ждать, пока корневой узел не установит флаг continue. Сбрасывать флаг continue можно двумя способами. Первый способ — применить двойную буферизацию, т.е. использовать два флага продолжения и переключаться между ними. Второй способ — изменять смысл флага продолжения, т.е. на четных циклах ждать, когда его значением станет 1, а на нечетных — 0.

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

3.4.3. Симметричные барьеры

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


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

Симметричный барьер для n процессов строится из пар простых двухпроцессных барье­ров. Чтобы создать двухпроцессный барьер, можно использовать метод "управляющий-рабочий", но тогда действия двух процессов будут различаться. Вместо этого можно создать полностью симметричный барьер. Пусть каждый процесс при достижении им барьера уста­навливает собственный флаг. Если w [ i ] и w [ j ] — два процесса, то симметричный барьер для них реализуется следующим образом.



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

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

Пусть Worker [I :n] — массив процессов. Если n является степенью 2, то процессы можно объединить по схеме, показанной на рис. 3.2. Этот тип барьеров называется барьером-бабочкой (butterfly barrier) из-за схемы связей, аналогичной схеме соединений в преобразовании Фурье, которая похожа на бабочку. Как видно из рисунка, барьер-бабочка состоит из Iog2n уровней. На разных уровнях процесс синхронизируется с разными процессами.


На уровне s процесс син­хронизируется с процессом на расстоянии 2"\ Когда каждый процесс прошел через все уровни, до барьера дошли все процессы и могут быть продолжены. Дело в том, что каждый процесс пря­мо или косвенно синхронизируется со всеми остальными. (Если число n не является степе­нью 2, то барьер-бабочку можно построить, используя наименьшую степень 2, которая больше п. Отсутствующие процессы заменяются существующими, хотя это и не очень эффективно.)

Другая схема соединений показана на рис. 3.3. Она лучше, Поскольку может быть использо­вана при любых n (не только степенях 2). Здесь также несколько уровней, и на уровне s рабочий процесс синхронизируется с процессом на расстоянии 2*~'. На каждом двухпроцессном барьере



В реализации барьера для п процессов, независимо от используемой схемы соединений, важно избежать состояния гонок, которое может возникнуть при использовании нескольких экземпляров базового двухпроцессного барьера. Рассмотрим барьер-бабочку (см. рис. 3.2). Предположим, что есть только один массив переменных-флагов и они используются, как указано в(3.15). Пусть процесс1 приходит к первому уровню и устанавливает флаг ar­rive [1]. Пусть процесс 2 — медленный, и еще не достиг первого уровня, а процессы 3 и 4 дошли до первого уровня барьера, установили флаги, сбросили их друг у друга и прошли на второй уровень. На втором уровне процесс 3 должен синхронизироваться с процессом 1, по­этому он ожидает установки флага arrive [1]. Флаг уже установлен, поэтому процесс 3 сбрасывает флаг arrive [1] и переходит на уровень 3, хотя этот флаг был установлен для процесса 2. Таким образом, в результате работы сети некоторые процессы пройдут барьер раньше, чем должны, а другие будут вечно ожидать перехода на следующий уровень. Та же проблема может возникнуть и при использовании барьера с распространением (см. рис. 3.3).

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


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

Если флаги целочисленные, их можно использовать как возрастающие счетчики, которые

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

каждого флага— 0. Каждый раз, когда рабочий процесс i приходит на новый уровень

ьера, он увеличивает значение счетчика arrive [i]. Затем рабочий процесс i определяет

мер процесса-партнера j на текущем уровне и ожидает, пока значение arrive [ j ] не ста­нет, как минимум, таким же, как значение arrive [ i ]. Это описывается следующим кодом.

# код барьера для рабочего процесса i for [s = 1 to num_stages] {

arrive[i]   =  arrive[i]   +  1;

определить соседа j  на уровне s

while (arrivefj] < arrive[i]) skip; }

Таким способом рабочий процесс i убеждается, что процесс j зашел, как минимум, так же далеко. Описанный подход к использованию возрастающих счетчиков и уровней позволяет избе-жагь состояния гонок, избавляет от необходимости для процесса ожидать переустановку соб-юнного флага (первая строка кода (3.15)) и переустанавливать флаг другого процесса последняя строка кода(3.15)). Таким образом, каждый уровень каждого барьера— это всего и строки кода. Единственный недостаток этого способа — счетчики все время возрастают, по­этому теоретически возможно их переполнение. Однако на практике это крайне маловероятно.

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

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


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