Процессы и синхронизация

_______________________________Глава 2

Процессы и синхронизация

Параллельным программам присуща более высокая сложность по сравнению с последова­тельными. Они соотносятся с последовательными программами, как шахматы с шашками или бридж с "дураком": и те и другие интересны, но первые гораздо интеллектуальнее последних.

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

В предыдущей главе были представлены процессы и синхронизация, а также приведены примеры их использования. Здесь они рассматриваются подробнее. В разделе 2.1 кратко опи­сывается семантика (смысл) параллельных программ и представлены пять основных поня­тий: состояние программы, неделимое действие, история, свойства безопасности и живуче­сти. В разделах 2.2 и 2.3 эти понятия поясняются двумя примерами — поиск шаблона в файле и поиск в массиве максимального значения. Изучаются также способы распараллеливания программ, рассматривается необходимость неделимых действий и синхронизации. В разде­ле 2.4 определяются неделимые действия (примитивы) и вводится оператор await как сред­ство выражения примитивов и синхронизации. В разделе 2.5 показано, как программировать синхронизацию, которая встречается в программах типа "производитель-потребитель".

В разделе 2.6 представлен краткий обзор аксиоматической семантики последовательных и па­раллельных программ. Новая фундаментальная проблема, возникающая в параллельных програм­мах, — это возможность взаимного влияния (вмешательства). В разделе 2.7 описаны четыре метода его устранения: непересекающиеся множества переменных, ослабленные утверждения, гло­бальные инварианты и синхронизация. Наконец, в разделе 2.8 показано, как доказывать выпол­нение свойств безопасности, и определены стратегии планирования и понятие справедливости.

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

Производители и потребители: каналы ОС Unix

Процесс-производитель выполняет вычисления и выводит поток результатов. Процесс-потребитель вводит и анализирует поток значений. Многие программы в той или иной форме являются производителями и/или потребителями. Сочетание становится особенно интерес­ным, если производители и потребители объединены в конвейер — последовательность процес­сов, в которой каждый из них потребляет данные выхода предшественника и производит дан­ные для последующего процесса. Классическим примером являются конвейеры в операцион­ной системе Unix, рассматриваемые здесь. Другие примеры приводятся в последующих главах.

Обычно прикладной процесс в ОС Unix считывает данные из стандартного файла ввода stdin и записывает в стандартный файл вывода stdout. Обычно файл ввода — это клавиатура термина­ла, с которого вызвано приложение, а файл вывода — дисплей этого терминала. Но одной из наи­более мощных функций, предложенных в ОС Unix, была возможность привязки стандартных "устройств" ввода-вывода к различным типам файлов. В частности, файлы stdin и/или stdout могут быть связаны с файлом данных или с "файлом" особого типа, который называется каналом.

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

Прикладная программа в ОС Unix только читает данные из файла stdin, не заботясь о том, откуда в действительности они туда попали. Если файл stdin связан с клавиатурой, на вход по­ступают символы, набранные на клавиатуре. Если файл stdin связан с определенным файлом, вводится последовательность символов из этого файла. Если файл stdin связан с каналом, то вводится последовательность символов, записанных в этот канал.
Аналогично приложение вы­полняет запись в файл s tdout, не заботясь о том, куда в действительности поступают данные.

1.7. Клиенты и серверы: файловые системы                                                                                33

Каналы ОС Unix обычно определяются с помощью одного из командных языков, напри­мер csh (С shell — "оболочка С"). В частности, печатные страницы оригинала этой книги создавались с помощью команды на языке csh, похожей на следующую:

sed  -f  Script  $*   |   tbl   |eqn   |   groff Macros  -

Этот конвейер содержит четыре команды: 1) sed, потоковый текстовый редактор; 2) tbl, процессор таблиц; 3) eqn, процессор уравнений и 4) groff, программа, создающая данные в формате Postscript из исходных файлов в формате troff. Каждая пара команд разделена вертикальной чертой, обозначающей канал в С shell.



На рис. 1.5 показана структура этого конвейера. Каждая команда является процессом-. фильтром. Вход фильтра sed образован файлом редактирующих команд (Script) и аргумен­тами командной строки ($*), которыми в данном случае являются соответствующие исход­ные файлы текста книги. Выход редактора sed передается программе tbl, направляющей свои выходные данные программе egn, а та передает свой выход программе groff. Фильтр groff читает файл Macros для этой книги, считывает и обрабатывает свой стандартный вход, а затем отсылает выход на принтер в офисе автора.

Каждый поток на рис. 1.5 реализован связанным буфером: синхронизированной очередью значений типа FIFO. Процесс-производитель ожидает (при необходимости), пока в буфере появится свободное место, затем добавляет в конец буфера новую строку. Процесс-потребитель ожидает (при необходимости), пока в буфере не появится строка данных, затем забирает ее. В части 1 показано, как реализовать такие буферы с использованием разделяемых переменных и различных примитивов синхронизации (флагов, семафоров и мониторов). В части 2 представлены каналы взаимодействия и примитивы пересылки сообщений send (отослать) и receive (получить).Затем будет показано, как с их использованием програм­мируются фильтры, а с помощью буферов реализуются каналы и передача сообщений.

Распараллеливающие компиляторы

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

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

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

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

Распараллеливающие компиляторы постоянно совершенствуются и в настоящее время вполне пригодны для создания эффективных параллельных программ с разделяемыми пере­менными. Особенно это касается научных программ, содержащих много циклов и длитель­ных вычислений. Однако создать хорошую программу с обменом сообщениями гораздо сложнее, поскольку всегда существует много вариантов структуры программы и взаимодейст­вия, как было показано в главе 11. Кроме того, некоторые сложные последовательные алго­ритмы трудно распараллелить, например, многосеточные методы или метод Барнса—Хата.

12.2.1. Анализ зависимости

Предположим, что последовательная программа содержит два оператора S, и S2, причем S, находится перед S2. Говорят, что между двумя операторами существует зависимость по

Глава 12. Языки, компиляторы, библиотеки и инструментальные средства                       459

данным, если они считывают или записывают данные в общей области памяти так, что поря­док их выполнения нельзя изменять. Существует три основных типа зависимости по данным."

1. Потоковая зависимость. Оператор S2

потоково зависит от S,, если S2 считывает из ячей­ки, в которую записывает S,. (Такая зависимость еще называется истинной.)

2. Антизависимость. Оператор S2 является антизависимым относительно St, если S2

запи­сывает в ячейку, из которой 5, считывает.

3. Зависимость по выходу. Оператор S2 зависит по выходу от Slt

если оператор S2

записыва­ет данные в ту же ячейку памяти, что и S,.

Будем просто говорить, что S3 зависит от St, если это зависимость по данным; тип зависимо­сти не важен.

В качестве примера рассмотрим следующую последовательность операторов.

Оператор S2 потоково зависит от St, поскольку считывает а. Оператор S, антизависим относи­тельно S2, поскольку он записывает а; .5", также зависит по выходу от S,, поскольку они оба за­писывают а.


Наконец, оператор S, потоково зависит от S3, поскольку считывает а. (St также потоково зависит от St, но St

должен выполняться перед S}.) Вследствие этих зависимостей операторы должны выполняться в порядке, указанном в списке; изменение порядка операто­ров приведет к изменению результатов.

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

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



В каждой итерации внешнего цикла S2 зависит от -У,, a S3 зависит и от «У,, и от S2. Внутренний цикл состоит из одного оператора, поэтому никакой зависимости в этом цикле нет. Однако внутренний цикл приводит к зависимости S2 от самого себя, поскольку S2

и считывает, и записы­вает sum. Аналогично и внешний цикл создает зависимость: S2 зависит от S}, поскольку значе­ние, записанное в х [ i ] на одной итерации внешнего цикла, считывается на всех последующих.

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

460                                                      Часть 3 Синхронное параллельное программирование



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



Есть п вложенных циклов и, соответственно, п индексных переменных. Нижние и верхние границы п индексных переменных определяются функциями 1J

и и;. Наиболее глубоко вло­женный цикл состоит из двух операторов, содержащих ссылки на элементы n-мерного мас­сива а; первый оператор записывает в а, второй — считывает из а. Вызовы функций f, и д: в этих операторах содержат в качестве своих аргументов индексные переменные; функции воз­вращают значения индексов.

Итак, возникает следующий вопрос о зависимости в данном цикле: существуют ли значения индексных переменных, при которых f, = g,, f 2 = g2 и т.д.? Ответ определяет, зависит 52

от 5, на одной и той же итерации цикла или между операторами есть зависимости, создаваемые циклом.

Проверку зависимости можно представить в виде специальной системы линейных урав­нений и неравенств следующего вида.



Коэффициенты в матрицах А, и А, определяются функциями f и g в программе, а значения в векторах Ь, и Ь2 — границами для индексных переменных. Решением первого уравнения явля­ется присваивание значений индексным переменным, при котором ссылки массива перекры­ваются. Второе уравнение (в действительности система неравенств) обеспечивает, что значения индексных переменных находятся внутри границ, определяемых функциями 1 и и. Решение дан­ной задачи похоже на решение двух систем линейных уравнений, рассмотренное в разделе 11.3, однако имеет два принципиальных отличия: 1) решение должно быть вектором целых, а не дейст­вительных чисел, 2) второе выражение имеет соотношение "меньше или равно". Именно эти отли­чия приводят к тому, что проблема становится NP-трудной, даже если индексные выражения яв­ляются линейными функциями и не содержат указателей. (Проверка зависимости при этих ус­ловиях эквивалентна частному случаю задачи целочисленного линейного программирования.)



Хотя проверка зависимости является сложной (а в худшем случае — неразрешимой) задачей, существуют эффективные проверки, применимые в некоторых частных случаях. В действитель­ности почти для всех циклов, встречающихся на практике, можно определить, перекрываются ли две ссылки в массив. Например, эффективные проверки существуют для ситуации, при ко­торой все границы циклов являются константами, или границы внутренних циклов зависят только от границ внешних циклов. Цикл прямого хода в методе исключений Гаусса, приведенный выше, удовлетворяет данным ограничениям: границы для i — константы, одна граница для j — константа, а другая зависит от значения i. Но если компилятор не может определить, отличаются ли две ссылки на элементы массива, то он пессимистически предполагает, что зависимость есть.

12.2.2. Преобразования программ

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

В первом примере предположим, что функция f не имеет побочного эффекта, и рассмот­рим следующий вложенный цикл.



i еперь можно распараллелить внешний цикл, используя оператор со.

Перестановка циклов — это один из видов преобразования программ, используемых в рас­параллеливании. Ниже рассматриваются еще несколько полезных преобразований: локали­зация, расширение скаляра, распределение цикла, слияние циклов, развертка и сжатие, раз­вертка цикла, разделение на полосы, разделение на блоки, а также перекос цикла (рис. 12.1). Они помогают выявлять параллельность, устранять зависимости и оптимизировать использо­вание памяти. Рассмотрим их.

Перестановка циклов      Внешний и внутренний циклы меняются местами

Локализация                   Каждому процессу дается копия переменной

Расширение скаляра        Скаляр заменяется элементом массива

Распределение цикла       Один цикл расщепляется на два отдельных цикла



Слияние циклов               Два цикла объединяются в один

Развертка и сжатие       Комбинируются перестановка циклов, разделение на полосы и развертка

Развертка цикла             Тело цикла повторяется и выполняется меньше итераций

Разделение на полосы       Итерации одного цикла разделяются на два вложенных цикла Разделение на блоки        Область итераций разбивается на прямоугольные блоки

Перекос цикла                 Границы цикла изменяются,  чтобы выделить параллельность

фронта волны

Рис. 12.1. Преобразования программ, используемые параллельными компиляторами

Рассмотрим стандартную последовательную программу вычисления матричного произве­дения с двух квадратных матриц а и b размером пхп.

for   [i  =  1  to n] for   [j  =  1  to n]   {

27 Для задания параллельных циклов в этой книге используется оператор со. В других языках ис­пользуются подобные операторы, например parallel do или for all.



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

Другой способ распараллелить программу умножения матриц — применить расширение скаляра. Одиночная переменная заменяется элементом массива. В данном случае можно из­менить переменную sum на с [ i, j ]. Это преобразование также позволяет избавиться от по­следнего оператора присваивания и получить следующую программу.



Два внешних цикла больше не создают зависимости, поэтому теперь можно распараллелить цикл по 1, выполнить перестановку циклов и распараллелить цикл по j или распараллелить оба цикла.2* Наиболее глубоко вложенный цикл в данной программе зависит от инициализации мас­сива с [ i, э ].


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



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



28 В данном примере локализация была бы эффективнее, чем замена скаляра. Во-первых, sum могла бы сохраняться в регистре Во-вторых, ссылки на с [ i, э 1 в полученном коде могут привести к ложному разделению переменных и, как следствие, к слишком непроизводительному использованию кэша.





Глава 12. Языки, компиляторы, библиотеки и инструментальные средства                        465

Каждое новое значение а зависит от двух значений, вычисленных в предыдущих итерациях, и от двух значений, которые не обновляются до следующих итераций. На рис. 12.2, а показа­ны эти зависимости; пунктирными линиями обозначены волновые фронты.



466                                                      Часть 3. Синхронное параллельное программирование

Распараллеливание: поиск образца в файле

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

Рассмотрим задачу поиска всех экземпляров шаблона pattern в файле filename. Пере­менная pattern— это заданная строка; переменная filename— имя файла. Эта задача без труда разрешима в ОС Unix на командном уровне с помощью одной из команд семейства дгер, например:

дгер pattern  filename

В результате создается один процесс. Он выполняет нечто подобное следующей последова­тельной программе.

string  line;

прочитать строку ввода из stdin в line; while   (!EOF)   {     #  EOF  -  это конец файла искать pattern e line; if   (pattern есть в line)

' Игра слов: "exhaustive" означает как "исчерпывающий", так и "истощающий", "изнуритель­ный". — Прим. перев.

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

вывести line;

прочитать следующую строку ввода', }

Теперь желательно выяснить два основных вопроса: можно ли распараллелить эту програм­му? Если да, то как?

Основное требование для возможности распараллеливания любой программы состоит в том, что она должна содержать независимые части, как это описано в разделе 1.4. Две части взаимно зависимы, если каждая из них порождает результаты, необходимые для другой; это возможно, только если они считывают и записывают разделяемые переменные. Следователь­но, две части программы независимы, если они не выполняют чтение и запись одних и тех же переменных. Более точное определение таково.

(2.1) Независимость параллельных процессов. Пусть множество чтения части программы — это переменные, которые она считывает, но не изменяет. Пусть множество записи части программы — это переменные, в которые она записывает (и, возможно, читает их). Две части программы являются независимыми, если пересечение их множеств записи пусто.

Чтение или запись любой переменной неделимо. Это относится как к простым переменным (таким как целые), которые записываются в отдельные слова памяти, так и к отдельным эле­ментам массивов или структур (записей).

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

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

прочитать входную строку из stdin в line; while   ('EOF)    {

со искать pattern в line; if   (pattern есть в line)

вывести line;

/ /  прочитать следующую строку ввода и записать ее в line; ос; }

Отметим, что первая ветвь оператора со является последовательностью операторов. Но неза­висимы ли эти два процесса программы? Ответ — нет, поскольку первый читает line, а дру­гой записывает в нее. Поэтому, если второй процесс выполняется быстрее первого, он будет перезаписывать строку до того, как ее успеет проверить первый процесс.



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

Глава 2. Процессы и синхронизация                                                                                             53

string  linel,   Iine2;

прочитать строку ввода из stdin в linel;

while   (!EOF)   {

со искать pattern в linel; if   (pattern есть в linel)

вывести  linel;

/ /  прочитать следующую строку ввода и записать ее в I ine2 ; ос; }

Теперь эти два процесса работают с разными строками, записанными в переменные linel Hline2. Следовательно, процессы могут выполняться параллельно. Но правильна ли эта программа? Ясно, что нет, поскольку первый процесс все время ищет в linel, тогда как вто­рой постоянно записывает в Iine2, которая никогда не рассматривается.

Решение относительно простое: поменяем роли строк данных в конце каждого цикла, чтобы первый процесс всегда проверял последнюю прочитанную из файла строку, а второй процесс всегда записывал в другую переменную. Этому соответствует следующая программа. string linel,   Iine2; прочитать строку ввода из  stdin e  linel; while   (!EOF)   {

со искать pattern в linel; if   (pattern есть в linel)

вывести  linel;

/ /  прочитать следующую строку ввода в 1 ine2; ос;

linel  =  Iine2;        ч }

Здесь в конце каждого цикла и после завершения каждого процесса содержимое Iine2 копи­руется в linel. Процессы внутри оператора со теперь независимы, но их действия связаны из-за последнего оператора цикла, который копирует Iine2 в linel.

Параллельная программа, приведенная выше, верна, но совершенно неэффективна. Во-первых, в последней строке цикла содержимое переменной Iine2 копируется в переменную linel. Это последовательное действие отсутствует в первой программе, и в общем случае оно требует копирования огромного количества символов, а это — накладные расходы.


Во-вторых, в теле цикла содержится оператор со, а это означает, что при каждом повторении цикла while будут создаваться, выполняться и уничтожаться по два процесса. "Копирование" можно сделать намного эффективнее, использовав массив с двумя строками. Индексы в каждом из процессов должны указывать на различные строки массива, а послед­няя строка определяется просто обменом значений индексов. Однако и в этом случае созда­вать процессы весьма накладно, поскольку создание и уничтожение процесса занимает на­много больше времени, чем вызов процедуры, и еще больше, чем выполнение линейного участка кода (за подробностями обращайтесь к главе 6).

Итак, мы подошли к последнему вопросу этого раздела. Существует ли еще один путь распараллеливания программы, позволяющий не использовать оператор со внутри цикла? Как вы наверняка уже догадались, ответ — да. В частности, вместо использования оператора со внутри цикла while, можно поместить циклы while в каждую ветвь оператора со. В лис­тинге 2.1 показано решение, использующее этот метод. Данная программа является примером схемы типа "производитель-потребитель", представленной в разделе 1.6. Здесь первый процесс является производителем, а второй — потребителем. Они взаимодействуют с помощью разде­ляемой переменной buffer. Отметим, что объявления переменных linel и Iine2 теперь ста­ли локальными для процессов, поскольку строки уже не разделяются процессами.

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

Стиль программы, приведенной в листинге 2.1, называется "while внутри со", в отличие от стиля "со внутри while", использованного в предыдущих программах этого раздела. Пре­имущество стиля "while внутри со" состоит в том, что процессы создаются только однажды, а не при каждом повторении цикла. Недостатком является необходимость использовать два буфера и программировать синхронизацию. Операторы, предшествующие обращению к раз­деляемому буферу buffer и следующие за ним, указывают тип необходимой синхронизации.В разделе 2.5 будет показано, как программируется эта синхронизация, но сначала нужно подробно рассмотреть вопросы синхронизации в целом и неделимые действия в частности.

string buffer;   #  содержит одну строку ввода

bool  done =  false;   #используется для  сигнализации о завершении со  #  процесс  1:   найти шаблоны string linel; while   (true)   {

ожидать заполнения буфера или значения true переменной done ;

if   (done)   break;

linel = buffer;

сигнализировать, что буфер пуст;

искать pattern в linel;

if   (pattern есть в linel)

напечатать  linel; }

//  #  процесс  2:   прочитать  новые  строки string Iine2; while   (true)    {

прочитать следующую строку ввода в Iine2 ; if   (EOF)    {done  =   true;   break;   } ожидать опустошения буфера buffer  =  Iine2; сигнализировать о заполнении буфера; } ос;

Распределение ресурсов и планирование

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

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

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

4.5.1. Постановка задачи и общая схема решения

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

Если опустить представление элементов ресурса, то общая схема операций request и release такова.

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

Эту общую схему решения можно реализовать с помощью метода передачи эстафеты (раздел 4.4). Операция request имеет вид обычного оператора await, поэтому реализуется следующим фрагментом программы.



Операция release тоже имеет вид простого неделимого действия и реализуется таким фраг­ментом программы.



Как и раньше, семафор е управляет входом в критическую секцию, а фрагмент кода SIGNAL запускает на выполнение приостановленные процессы (если ожидающий запрос может быть удовлетворен) или снимает блокировку семафора входа с помощью операции V (е). Код DELAY в операции request аналогичен фрагментам кода в начале протоколов входа процес­сов читателей и писателей (см. листинги 4.11 и 4.12). Он запоминает, что появился новый за­прос, который должен быть приостановлен, снимает блокировку с семафора входа с помо­щью операции V (е) и блокирует запрашивающий процесс на семафоре задержки.



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

Глава 4. Семафоры                                                                                                                         151

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

4.5.2. Распределение ресурсов по схеме "кратчайшее задание"

"Кратчайшее задание" (КЗ, Shortest-Job-Next — SJN) — это стратегия распределения ресурсов, которая встречается во многих разновидностях и используется для разных типов ресурсов. Предположим, что разделяемый ресурс состоит из одного элемента (общий слу­чай нескольких элементов рассмотрен в конце данного раздела). Тогда стратегия КЗ опре­деляется следующим образом.

(4.3) Распределение ресурсов по схеме "кратчайшее задание". Несколько процессов соперни­чают в использовании одного разделяемого ресурса. Процесс запрашивает ресурс, вы­полняя операцию request (time, id), где целочисленный параметр time определя­ет длительность использования ресурса этим процессом, а целое число id идентифи­цирует запрашивающий процесс. Если в момент выполнения операции request ресурс свободен, он выделяется для процесса немедленно, иначе процесс приостанав­ливается. После использования ресурса процесс освобождает его, выполняя операцию release. Освобожденный ресурс распределяется приостановленному процессу (если такой есть) с наименьшим значением параметра time. Если у нескольких процессов значения time равны, то ресурс отдается тому из них, кто дольше всех ждал.

Стратегию КЗ можно использовать, например, для распределения процессоров (параметр time будет означать время выполнения), для вывода файлов на принтер (time — время печа­ти) или для обслуживания удаленной передачи файлов по протоколу ftp (time — предпола­гаемое время передачи файла).



Стратегия КЗ привлекательна, поскольку минимизирует общие затраты времени на вы­полнение задачи. Вместе с тем, ей присуще несправедливое планирование: процесс может быть приостановлен навсегда, если существует непрерывный поток запросов с меньшим вре­менем использования ресурса. (Такая несправедливость крайне маловероятна на практике, если только ресурс не перегружен.) Если несправедливость нежелательна, то можно слегка изменить стратегию КЗ, чтобы предпочтение отдавалось процессам, ожидающим слишком долго. Этот метод называется выдержкой, или старением (aging).

Если процесс выполняет запрос и ресурс свободен, то этот запрос может быть удовлетворен немедленно, поскольку других ожидающих запросов нет. Таким образом, стратегия КЗ "вступает в игру", только если есть несколько ожидающих запросов. Ресурс один, поэтому для хранения сведений о его доступности достаточно одной переменной. Пусть free — логическая переменная, которая истинна, когда ресурс доступен, и ложна, когда он занят. Для реализации стратегии КЗ нужно запоминать и упорядочивать ожидающие запросы. Пусть pairs — набор записей вида (time, id), упорядоченных по значениям поля time. Если две записи имеют одинаковые значения поля time, то они остаются во множестве pairs в порядке их появления. В соответствии с этим определением следующий предикат должен быть глобальным инвариантом. SJN: (pairs — упорядоченный набор) л (free => (pairs == 0) )

Расшифруем: набор pairs упорядочен, а если ресурс свободен, то pairs — пустое множест­во. Вначале free истинна, а множество pairs пусто, так что предикат SJN выполняется.

Без учета стратегии КЗ запрос может быть удовлетворен, как только ресурс станет доступ­ным. Отсюда получим следующее крупномодульное решение.



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

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


Из второй части предиката SJN следует, что если пере­менная free истинна во время выполнения процессом операции request, то множество pairs пусто. Следовательно, приведенного выше условия достаточно для определения, мо­жет ли запрос удовлетворяться немедленно. Параметр time играет роль, только если запрос должен быть отложен — т.е. если переменная free ложна. На основе этих соображений мож­но реализовать операцию request таким образом.



В операции request предполагается, что операции Р над семафором входа е обслуживаются в порядке их появления, т.е. по правилу "первым пришел— первым обслужен". Если этого нет, то порядок обработки запросов может не соответствовать стратегии КЗ.

Осталось воплотить стратегию распределения ресурсов КЗ. Для этого используем множе­ство pairs и семафоры, реализующие фрагменты кода SIGNAL и DELAY. Если запрос не мо­жет быть удовлетворен, его следует сохранить, чтобы к нему можно было вернуться после ос­вобождения ресурса. Таким образом, во фрагменте кода DELA Yпроцесс должен:

•    вставить параметры запроса в набор pairs;

•    освободить управление критической секцией, выполнив операцию V (е);

•    остановиться на семафоре до удовлетворения запроса.

Если после освобождения ресурса множество pairs не пусто, то в соответствии со стратегией КЗ только один процесс должен получить ресурс. Таким образом, если есть приостановлен­ный процесс, который теперь может продолжить работу, он должен получить сигнал с помо­щью операции V для семафора задержки.

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



Предположим, что ресурс используют п процессов. Пусть b[n] — массив семафоров, ка­ ждый элемент которого имеет начальное значение 0. Будем считать, что значения идентифи­каторов процессов id уникальны и находятся в пределах от 0 до п-1. Тогда процесс id при­останавливается на семафоре b[id]. Дополнив операции request и release соответст­вующей обработкой множества pairs и массива Ь, получим решение задачи распределения ресурсов по схеме КЗ (листинг4.13).

В листинге 4.13 предполагается, что операция вставки помещает пару параметров в такое место последовательности pairs, которое сохраняет истинность первой части предиката SJN. Следовательно, предикат SJN действительно является инвариантом вне операций re­quest и release, т.е. он является истинным непосредственно после каждой операции Р(е) и перед каждой V (е). Если есть ожидающие запросы, т.е. множество pairs не пусто, опера­тор if кода выработки сигнала в операции release запускает только один процесс

Глава 4. Семафоры                                                                                                                         153

"Эстафетная палочка" переходит к этому процессу, а он присваивает переменной free зна­чение ложь. Этим гарантируется истинность второй части предиката SJN, когда множество pairs не пусто. Поскольку ресурс один, остальные запросы не могут быть удовлетворены, так что сигнальный код операции regues t состоит из одной операции V (е).



Элементы массива семафоров b в листинге 4.13 являются примером так называемых част­ных семафоров.

(4.4)   Частный семафор. Семафор s называется частным, если операцию Р над ним выпол­няет только один процесс.

Когда процесс в листинге 4.13 должен быть приостановлен, он выполняет операцию Р (b [ id]) для блокировки на собственном элементе массива Ь.

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


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

Решение в листинге 4.13 легко обобщить для использования ресурсов, состоящих из не­скольких элементов. В этой ситуации каждый элемент может быть свободен или занят, а опе­рации request и release должны использовать параметр amount, определяющий требуе­мое количество элементов ресурса. Изменим решение в листинге 4.13 следующим образом:

•    булеву переменную free заменим целочисленной переменной avail для хранения количества доступных элементов;

•    в операции request проверим условие amount <= avail. Если оно истинно, выде­лим amount элементов ресурса. Если нет, запомним, сколько элементов ресурса за­прошены перед приостановкой процесса;

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

• в операции release увеличим значение avail на amount, после чего определим, можно ли удовлетворить запрос самого старого из отложенных процессов с минималь­ным значением параметра time. Если да — запустим его. Если нет, выполним V (е).

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

Реализация языковых механизмов

______________________________Глава 10

Реализация языковых механизмов

В данной главе представлены способы реализации различных языковых механизмов, опи­санных в главах 7 и 8: асинхронной и синхронной передачи сообщений, удаленного вызова процедур (RPC) и рандеву. Сначала показано, как реализовать асинхронную передачу сооб­щений с помощью ядра. Затем асинхронная передача сообщений используется для реализа­ции синхронной передачи сообщений и защищенного взаимодействия. Далее демонстриру­ется реализация RPC с помощью ядра, рандеву с помощью асинхронной передачи сообщений и, наконец, рандеву (и совместно используемые примитивы) в ядре.

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

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

Реализация мониторов с помощью семафоров

В предыдущем разделе было описано, как реализовать мониторы с помощью ядра. Здесь показано, как реализовать их, используя семафоры. Это может понадобиться по двум прими-

Глава 6. Реализация                                                                                                                       227

нам: 1) библиотека программирования поддерживает семафоры и не поддерживает монито­ры, или 2) язык программирования обеспечивает семафоры и не обеспечивает мониторы. Так или иначе, описываемое решение иллюстрирует еще одно применение семафоров.

Вновь используем семантику мониторов, определенную в разделе 5.1. Следовательно, нужно реализовать взаимное исключение процедур монитора и условную синхронизацию между ними. В частности, нужно разработать: 1) код входа, который выполняется после вызо­ва процедуры монитора из процесса, но перед началом выполнения тела процедуры; 2) код вы­хода, выполняемый перед выходом процесса из тела процедуры; 3) код, реализующий операции wait, signal и другие операции с условными переменными. Для простоты предположим, что есть только одна условная переменная; разработанный ниже код несложно обобщить на случай нескольких условных переменных, используя массивы очередей задержки и счетчиков.

Для реализации исключения в мониторах используем по одному входному семафору на монитор. Пусть е — семафор, связанный с монитором М. Поскольку семафор е должен ис­пользоваться для получения взаимного исключения, он инициализируется значением 1, и его значение всегда должно быть или 0 или 1. Цель протокола входа каждой процедуры монитора М — обеспечить исключительный доступ к м. Как всегда, для этого используется операция Р (е). Аналогично протокол выхода каждой процедуры снимает блокировку мо­нитора, поэтому реализуется операцией V (е).

Выполнение операции wait(cv) снимает блокировку монитора и задерживает выпол­няемый процесс на условной переменной cv. Процесс продолжает работу в мониторе после получения сигнала и нового исключительного доступа к монитору.

Реализация мониторов в ядре

Мониторы тоже легко реализуются в ядре; в данном разделе показано, как это сделать. Их можно также моделировать с помощью семафоров; этому посвящен следующий раздел. Бло­кировки и условные переменные в таких библиотеках, как Pthreads, и таких языках програм­мирования, как Java, реализованы аналогично описанному здесь ядру.

Используем семантику мониторов, определенную в главе 5. В частности, процедуры выпол­няются со взаимным исключением, а условная синхронизация использует дисциплину "сигнализировать и продолжить". Постоянные переменные мониторов хранятся в области па­мяти, доступной всем процессам, вызывающим процедуры монитора. Код, реализующий про­цедуры, может храниться в разделяемой памяти или копироваться в локальную память каждого процессора, который выполняет процессы, использующие монитор. Наконец, постоянные пе­ременные инициализируются перед вызовом процедур. Для этого, например, можно выделять и инициализировать постоянные переменные перед созданием процессов, обращающихся к ним. (Или можно выполнять код инициализации при первом вызове процедуры монитора. Но этот способ менее эффективен, поскольку при каждом вызове придется проверять, первый ли он.)

Для реализации мониторов нужно добавить к ядру примитивы входа в монитор, выхода из него и операций с условными переменными. Нужны также примитивы для создания дескрипторов ка­ждого монитора и каждой условной переменной (если они не создаются при инициализации ядра); эти примитивы здесь не показаны, поскольку аналогичны примитиву createSem в листинге 6.4.

Каждый дескриптор монитора mName содержит блокировку mLock и входную очередь де­скрипторов процессов, ожидающих входа (или повторного входа) в монитор. Блокировка ис­пользуется, чтобы обеспечить взаимное исключение. Если она установлена, в мониторе вы­полняется только один процесс, иначе — ни одного.

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

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

Оператор wait (cv) реализован с помощью вызова примитива ядра wait (mName, cName), а оператор signal(cv) — примитива ядра signal (mName, cName). В обоих примитивах mName — это "имя" монитора (его индекс или адрес дескриптора), в котором вызывается при­митив, a cName — индекс или адрес дескриптора соответствующей условной переменной. Опе­ратор wait приостанавливает выполнение процесса на указанной условной переменной, за­тем либо запускает процесс из очереди входа в монитор, либо снимает блокировку монитора. Выполнение процедуры signal заключается в проверке очереди условной переменной. Если очередь пуста, то выполняется просто выход из примитива, иначе дескриптор из начала оче­реди условной переменной перемещается в конец очереди входа в монитор.

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


Поскольку процесс, вызвавший примитив wait, выходит из монитора, прими-

Несложно реализовать остальные операции с условными переменными. Например, для реализации empty (cv) достаточно проверить, есть ли элементы в очереди ожидания на cv. В действительности, если очередь задержки доступна процессам напрямую, для реализации операции empty не обязательно использовать примитив ядра. Причина в том, что выполняе­мый процесс уже заблокировал монитор, поэтому другие процессы не могут изменить содер­жание очереди условной переменной. Реализация операции empty без блокировки позволяет избежать затрат на вызов супервизора и возврат из него.

Операцию signal также можно реализовать более эффективно, чем показано в листин­ге 6.5. Например, процедура signal может всегда перемещать дескриптор из начала соответст­вующей очереди задержки в конец соответствующей очереди входа. Затем процедура signal в программе должна транслироваться в код, который проверяет очередь задержки и вызывает процедуру ядра mSignal, только если очередь пуста. После таких изменений отсутствуют затра­ты на вход в ядро и выход из него, когда операция signal ни на что не влияет. Независимо от реализации signal операция signal_all реализуется примитивом ядра, который перемещает все дескрипторы из указанной очереди задержки в конец списка готовых к выполнению.

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

Приоритетный оператор wait реализуется аналогично неприоритетному. Отличие состо­ит лишь в том, что дескриптор выполняемого процесса должен быть вставлен в соответст­вующую позицию очереди задержки. Чтобы сохранять упорядоченность очереди, необходимо знать ранги ожидающих процессов. Логично хранить ранг процесса вместе с его дескрипто­ром, что делает реализацию функции minrank тривиальной. Фактически minrank, как и empty, можно реализовать без входа в ядро, поскольку минимальный ранг можно прочи­тать непосредственно из выполняемого процесса.



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

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

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


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

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

Реализация семафоров в ядре

Поскольку операции с семафорами являются частным случаем операторов await, их можно реализовать с помощью активного ожидания и методов из главы 3. Но единственная причина, по которой это может понадобиться, — потребность в написании параллельных программ с помо­щью семафоров, а не низкоуровневых циклических блокировок и флагов. Поэтому просто пока­жем, как добавить семафоры к ядру, описанному в предыдущих разделах. Для этого необходимо дополнить ядро дескрипторами семафоров и тремя дополнительными примитивами: createSem, Psem и Vsem. (Библиотеки наподобие Pthreads реализованы аналогично, но выполняются на ос­нове операционной системы, поэтому используются с помощью обычных вызовов процедур и включают программные обработчики сигналов, а не аппаратные обработчики прерываний.)

Дескриптор семафора содержит значение одного семафора; его инициализация происхо­дит при вызове процедуры createSem. Примитивы Psem и Vsem реализуют операции Р и V. Предполагается, что все семафоры являются обычными. Сначала покажем, как добавить се­мафоры к однопроцессорному ядру из раздела 6.1, а затем — как изменить полученное ядро, чтобы оно поддерживало мультипроцессоры, как в разделе 6.2.

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

После добавления к ядру семафоров у процесса появляется еще одно возможное состоя­ние: заблокированный на семафоре Процесс переходит в это состояние, когда ждет заверше­ния операции Р. Чтобы отслеживать заблокированные процессы, каждый дескриптор сема­фора содержит связанный список дескрипторов процессов, заблокированных на этом сема­форе. На отдельном процессоре выполняется только один процесс, который не входит ни в один из списков, дескрипторы всех остальных процессов находятся в списке либо готовых к работе, либо ожидающих, либо заблокированных на семафоре процессов.

Для каждого объявления семафора в параллельной программе вырабатывается один вызов примитива createSem; в качестве его аргумента передается начальное значение семафора Примитив createSem находит пустой дескриптор семафора, инициализирует значение се­мафора и список заблокированных процессов и возвращает "имя" дескриптора. Обычно этим именем является адрес дескриптора или его индекс в таблице адресов.

Созданный семафор используется с помощью вызовов примитивов Psem и Vsem, которые яв ляются процедурами ядра, реализующими операции Р и V. Обе процедуры имеют один аргумент -имя дескриптора семафора. Примитив Psem проверяет значение в дескрипторе. Если значение по ложительно, оно уменьшается на единицу, иначе дескриптор выполняемого процесса вставляете в список блокировки семафора. Аналогично процедура Vsem проверяет список блокировки деск риптора семафора. Если он пуст, значение семафора увеличивается, иначе из списка блокировю дескриптора семафора удаляется один дескриптор процесса и вставляется в список готовых к рабо те. Обычно списки заблокированных процессов реализуются в виде очереди с последовательно стью обработки FIFO, поскольку тогда гарантируется справедливость семафорных операций

В листинге 6.4 даны схемы перечисленных примитивов, которые нужно добавить к одно' процессорному ядру (см. листинг 6.1). Здесь также в конце каждого примитива вызываете! процедура dispatcher; она работает так же, как и раньше.

Для простоты реализации семафорных примитивов в листинге 6.4 дескрипторы семафо­ров повторно не используются. Если семафоры создаются один раз, этого достаточно. Однако обычно дескрипторы семафоров, как и дескрипторы процессов, приходится использовать по­вторно. Для того чтобы ядро поддерживало повторное использование дескрипторов семафо­ров, можно добавить примитив destroySem; он должен вызываться процессом, когда сема­фор больше не нужен. Другой подход — записывать в дескрипторы процессов имена всех соз-



Однопроцессорную реализацию примитивов семафора (см.


листинг 6.4) можно расши­ рить для мультипроцессора так же, как описано в разделе 6.2 и показано в листинге 6.3. Здесь также необходимо блокировать разделяемые структуры данных, поэтому для каждого деск­риптора семафора используется отдельная блокировка. Дескриптор семафора блокируется в процедурах Psem и Vsem непосредственно перед доступом; блокировка снимается, как только исчезает потребность в дескрипторе. Блокировки устанавливаются и снимаются с по­мощью активного ожидания (см. решения задачи критической секции).

Вопросы, которые обсуждались в конце раздела 6.2, возникают и при реализации семафоров в многопроцессорном ядре. Например, процесс может требовать выполнения на определенном про­цессоре или на том же, на котором он выполнялся последний раз; может понадобиться совмест­ное планирование процессов на одном процессоре. Чтобы выполнить эти требования или избе­жать конфликтов из-за разделяемого списка готовых к выполнению процессов, процессоры должны использовать отдельные списки готовых к работе процессов. В этой ситуации процесс, запускаясь примитивом Vsem, помещается в соответствующий список готовых к работе. Для этого примитиву Vsem нужно либо блокировать удаленный список готовых к работе, либо инфор­мировать другой процессор и позволить ему поместить разблокированный процесс в его список го­товых к работе. При первом подходе нужна удаленная блокировка, при втором — использование механизма типа прерываний процессора для обмена сообщениями между процессорами.

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

Семафоры

Глава 4 Семафоры

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

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

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

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

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

Сеточные вычисления

Дифференциальные уравнения в частных производных (partial differential equations — PDE) применяются для моделирования разнообразных физических систем: прогноза погоды, обтекания крыла потоком воздуха, турбулентности в жидкостях и т.д. Некоторые простые PDE можно решить прямыми методами, но обычно нужно найти приближенное решение уравнения на конечном множестве точек, применяя итерационные численные методы. В этом разделе показано, как решить одно конкретное PDE — двухмерное уравнение Лапласа — с помощью сеточных вычислений по так называемому методу конечных разностей. Но при решении других PDE и в других приложениях сеточных вычислений, например, при обработке изображений, используется такая же техника программирования.

Для решения уравнения Лапласа существует несколько итерационных методов: Якоби, Гаусса—Зейделя, последовательная сверхрелаксация (successive over-relaxation — SOR) и многосеточный. Вначале будет показано, как запрограммировать метод итераций Якоби (с помощью разделяемых переменных и передачи сообщений), поскольку он наиболее прост и легко распараллеливается. Затем покажем, как программируются другие методы, сходя­щиеся гораздо быстрее. Их алгоритмы сложнее, но схемы взаимодействия и синхронизации в параллельных программах для них аналогичны.

11.1.2. Метод последовательных итераций Якоби

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

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

real  gridfOin+l,0:n+l],   new[0:n+l,0:n+l];

Границы обеих матриц инициализируются соответствующими граничными условиями, а внутренние точки — некоторым начальным значением, например 0. (В первом из последую­щих алгоритмов граничные значения в матрице new не нужны, но они понадобятся позже.)

Здесь maxdif f имеет действительный тип, iters — целый (это счетчик числа фаз обновле­ния). В программе предполагается, что массивы хранятся в памяти машины по строкам; если же массивы хранятся по столбцам (как в Фортране), то в циклах for сначала должны быть итерации по j, а затем по 1.

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

В первом цикле for присваивания выполняются п2 раз в каждой фазе обновлений. Сум­мирование оставим без изменений, а деление на 4 заменим умножением на 0.25. Такая за­мена повысит производительность, поскольку умножение выполняется быстрее, чем деление. Очевидно, что данная операция выполняется много раз, поэтому улучшение будет заметным. Такая оптимизация называется сокращением мощности, поскольку заменяет "мощное" (дорогое) действие более слабым (дешевым). (В действительности для целых значений деле­ние на 4 можно заменить еще более слабым действием — смещением вправо на 2.)

Рассмотрим часть кода, в которой вычисляется максимальная разность. Эта часть выпол­няется на каждой итерации цикла while, но только один раз приводит к выходу из цикла. Намного эффективней заменить цикл while конечным циклом, в котором итерации выпол­няются определенное количество раз. По существу, iters и maxdif f меняются ролями. Вместо того, чтобы подсчитывать число итераций и использовать maxdif f для завершения вычислений, iters теперь используется для управления количеством итераций. Тогда мак­симальная разность будет вычисляться только один раз после главного цикла вычислений. После проведения этой и первой оптимизаций программа примет следующий вид.





412                                                         Часть 3. Синхронное параллельное программирование

Развертывание цикла само по себе мало влияет на рост производительности, но часто позволяет применить другие оптимизации.21



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

В листинге 11.1 представлена оптимизированная программа для метода итераций Якоби. Проведены четыре оптимизации исходного кода: 1) деление заменено умножением; 2) для за­вершения вычислений использовано конечное число итераций, а максимальная разность вы­числяется только один раз; 3) две матрицы скомбинированы в одну с дополнительным изме­рением, что избавляет от копирования матриц; 4) цикл развернут дважды и его тело перепи­сано, поскольку дополнительный индекс и операторы изменения ролей матриц не нужны. В действительности в данной задаче можно было бы перейти от второй оптимизации прямо к четвертой. Однако третья оптимизация часто полезна.



Глава 11. Научные вычисления                                                                                                      413

11.1.3. Метод итераций Якоби с разделяемыми переменными

Рассмотрим, как распараллелить метод итераций Якоби. В листинге 3.16 был приведен пример программы, параллельной по данным. В ней на одну точку сетки приходился один процесс, что дает степень параллельности, максимально возможную для данной задачи. Хотя программа эффективно работала бы на синхронном мультипроцессоре (SIMD-машине), в ней слишком много процессов, чтобы она могла эффективно выполняться на обычном MIMD-мультипроцессоре. Дело в том, что каждый процесс выполняет очень мало работы, поэтому во времени выполнения программы будут преобладать накладные расходы на пере­ключение контекста. Кроме того, каждому процессу нужен свой собственный стек, поэтому, если сетка велика, программа может не поместиться в памяти. Следовательно, производи­тельность параллельной программы окажется гораздо хуже, чем последовательной.



Предположим, что есть PR процессоров, и размерность сетки п намного больше PR. Что­ бы параллельная программа была эффективной, желательно распределить вычисления между процессорами поровну. Для данной задачи сделать это несложно, поскольку для обновления каждой точки сетки нужно одно и то же количество работы. Следовательно, можно использо­вать PR процессов так, чтобы каждый из них отвечал за одно и то же число точек сетки. Мож­но разделить сетку на PR прямоугольных блоков или прямоугольных полос. Используем по­лосы, поскольку для них немного проще написать программу. Вероятно также, что использо­вание полос более эффективно, поскольку при длинных полосах локальность данных выше, чем при коротких блоках, что оптимизирует использование кэша данных.

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

В листинге 11.2 приведена параллельная программа для метода итераций Якоби с разделяе­мыми переменными. Использован стиль "одна программа— много данных" (single program, multiple data — SPMD): каждый процесс выполняет один и тот же код, но обрабатывает различ­ные части данных. Здесь каждый рабочий процесс сначала инициализирует свои полосы, вклю­чая границы, в двух матрицах. Тело каждого рабочего процесса основано на программе в лис­тинге 11.1. Барьерная синхронизация происходит с помощью разделяемой процедуры, реали­зующей один из алгоритмов в разделе 3.4. Для достижения максимальной эффективности можно применить симметричный барьер, например, барьер с распространением.





Листинг 11.2 также иллюстрирует эффективный способ вычисления максимальной разно­сти во всех парах окончательных значений в точках сетки.


Каждый рабочий процесс вычисля­ ет максимальную разность для точек в своей полосе, используя локальную переменную ту-dif f, а затем сохраняет полученное значение в массиве максимальных разностей. После вто­рого барьера каждый рабочий процесс может параллельно вычислить максимальное значение в maxdif f [ * ] (все эти вычисления можно также проводить только в одном рабочем процес­се). Локальные переменные в каждом процессе позволяют избежать использования критиче­ских секций для защиты доступа к единственной глобальной переменной, а также конфлик­тов в кэше, которые могли бы возникнуть из-за ложного разделения массива maxdif f.

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

11.1.4. Метод итераций Якоби с передачей сообщений

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

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

Начав с программы в листинге 11.2, вновь используем PR рабочих процессов, обновляю­щих каждый раз полосу точек сетки. Распределим массивы grid и new так, чтобы полосы были локальными для соответствующих рабочих процессов.


Также нужно продублировать строки на краях полос, поскольку рабочие не могут считывать данные, размещенные в других процессах. Таким образом, каждому процессу нужно хранить точки не только своей полосы, но и границ соседних полос. Каждый процесс выполняет последовательность фаз обновле­ния; после каждого обновления он обменивается краями своей полосы с соседями. Такая схема обмена соответствует алгоритму пульсации (см. раздел 9.2). Обмены заменяют точки барьерной синхронизации в листинге 11.2.                                                                                i

Глава 11. Научные вычисления                                                                                                415

Нужно также распределить вычисление максимальной разности после того, как каждый процесс завершит обновление в своей полосе сетки. Как и в листинге J 1.2, каждый процесс просто вычисляет максимальную разность в своей полосе. Затем выбирается один процесс, который собирает все полученные значения. Все это можно запрограммировать, используя либо сообщения, передаваемые от процесса к процессу, либо коллективное взаимодейст­вие, как в MPI (раздел 7.8).

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

if   (w >  1)     send up[w-l](new[l,*]);

if   (w <  PR)   send down[w+1](new[HEIGHT,*]);

if   (w <  PR)   receive up[w](new[HEIGHT+l,*]);

if   (w > 1)     receive down[w](new[0,*]);

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





416                                                      Часть 3. Синхронное параллельное программирование

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

Программу в листинге 11.3 можно оптимизировать. Во-первых, для данной программы и многих других сеточных вычислений нужно проводить обмен краями после каждой фазы об­новлений. Здесь, например, можно обменивать края после каждой второй фазы обновлений. Это вызовет "скачки" значений в точках на краях, но, поскольку алгоритм сходится, он все рав­но будет давать правильный результат. Во-вторых, можно перепрограммировать оставшийся обмен так, чтобы между отправкой и получением сообщений выполнялись локальные вычисле­ния. Например, можно реализовать взаимодействие, при котором каждый рабочий: 1) отправляет свои края соседям; 2) обновляет внутренние точки своей полосы; 3) получает края от соседей; 4) обновляет края своей полосы. Такой подход значительно повысит вероятность того, что края от соседей придут раньше, чем они нужны, и, следовательно, задержки операций получения не будет. В листинге 11.4 представлена оптимизированная программа. Предлагаем читателю срав­нить производительность и результаты последних двух программ с передачей сообщений.



Глава 11. Научные вычисления                                                                                                417

11.1.5. Последовательная сверхрелаксация по методу "красное-черное"

Метод итераций Якоби сходится очень медленно, поскольку для того, чтобы значения неко­торой точки повлияли на значения удаленных от нее точек, нужно длительное время. Например, нужны п/2 фаз обновлений, чтобы влияние граничных значений сетки дошло до ее центра.

Схема Гаусса—Зейделя (GS) сходится намного быстрее и к тому же использует меньше памяти.


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



Переменная omega называется параметром релаксации; ее значение выбирается из диапазо­на 0 < omega < 2. Если omega равна 1, то метод SOR сводится к методу Гаусса—Зейделя. Ес­ли ее значение равно 0.5, новое значение точки сетки есть половина среднего значения ее соседей плюс половина ее старого значения. Выбор подходящего значения omega зависит от решаемого дифференциального уравнения в частных производных и граничных условий.

Хотя методы GS и SOR сходятся быстрее, чем метод итераций Якоби„ и требуют вдвое меньше памяти, непосредственно распараллелить их непросто, поскольку при обновлении точ­ки используются как старые, так и новые значения. Другими словами, методы GS и SOR позво­ляют обновлять точки на месте именно потому, что применяется последовательный порядок об­новлений. (В циклах этих двух алгоритмов присутствует так называемая зависимость по данным. Их можно распараллелить, используя волновые фронты. Оба вопроса обсуждаются в разделе 12.2.)

К счастью, GS и SOR можно распараллелить, слегка изменив сами алгоритмы (их сходи­мость сохранится). Сначала покрасим точки в красный и черный цвет, как клетки шахматной доски. Начав с верхней левой точки, окрасим точки через одну красным цветом, а остальные — черным. Таким образом, у красных точек будут только черные соседи, а у чер­ных — только красные. Заменим единый цикл в фазе обновлений двумя вложенными: в пер­вом обновляются значения красных точек, а во втором — черных.

Теперь схему "красное-черное" можно распараллелить: у красных точек все соседи только черного цвета, а у черных — красного. Следовательно, все красные точки можно обновлять параллельно, поскольку их значения зависят только от старых значений черных точек.


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

В листинге 11.5 приведена параллельная программа для метода "красное-черное" по схе­ме Гаусса—Зейделя, использующая разделяемые переменные. (Последовательная сверхрелак­сация отличается только выражением для обновления точек.) Вновь предположим, что есть PR рабочих процессов и п кратно PR. Разделим сетку на горизонтальные полосы и назначим каждому процессу по одной полосе.



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

Метод "красное-черное" можно запрограммировать, используя передачу сообщений. Программа будет иметь такую же структуру, как и соответствующая программа для метода

Глава 11. Научные вычисления                                                                                                      419

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

Мы предположили, что отдельные точки окрашены в красный или черный цвет.


В резуль­тате i и j пошагово увеличиваются на два во всех циклах обновлений. Это приводит к слабо­му использованию кэша: в каждой фазе обновлений доступна вся полоса целиком, но из двух соседних точек читается или записывается только одна.22 Можно повысить производитель­ность, окрашивая блоки точек, как квадраты на шахматной доске, состоящие из множеств то­чек. Еще лучше окрасить полосы точек. Например, разделить каждую полосу рабочего попо­лам (по горизонтали) и закрасить верхнюю половину красным цветом, а нижнюю — черным. В листинге 11.5 каждый рабочий многократно обновляет сначала красные, затем черные точ­ки, и после каждой фазы обновлений установлен барьер. В каждой фазе обновлений доступна только половина всех точек (каждая и читается, и записывается).

11.1.6. Многосеточные методы

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

Предсказание погоды является типичным приложением такого рода. Процесс моделиро­вания погоды начинается с текущих условий (температура, давление, скорость ветра и т.п.), а затем для предсказания будущих условий проходит по временным шагам. Предположим, нужно сделать прогноз для континентальных США (без Аляски), используя сетку с разреше­нием в одну милю. Тогда понадобятся около 3000 х 1500 (4,5 миллиона) точек и вычисления такого масштаба на каждом временном шаге! Чтобы учесть значительное влияние океанов, нужна еще большая сетка. Однако с сеткой такого размера прогноз может безнадежно опо­здать! Используя более грубую сетку с разрешением, скажем, 10 миль, вычисления можно бу­дет завершить достаточно быстро, но, возможно, "потеряв" локальные возмущения.



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

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

•    Начать с точной сетки и обновить точки путем нескольких итераций, применив один из методов релаксации (Якоби, Гаусса—Зейделя, последовательной сверхрелаксации).

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

22

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



Глава 11. Научные вычисления                                                                                                     421

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



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

fine[i,j]   = coarse[x,у];

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

fine[i-l,j]   =   (fine[1-2,3]   +  fine[i,j])   *   0.5;

Наконец обновить остальные точки точной сетки (в столбцах, состоящих только из точек на рис. 11.2), присвоив каждой из них среднее арифметическое значений в соседних точках ее строки. Одно присвоение имеет такой вид.

fine[i-l,3-U   =   (fine[i-l,j-2]   +  fine[i-l,j])   *  0.5;

Таким образом, значение в точке, расположенной в той же строке, что и точки грубой сетки, равно среднему арифметическому значений в ближайших точках грубой сетки, а в точке, рас­положенной в другой строке, — среднему значений, соседствующих по горизонтали, т.е. чет­верти суммы значений в четырех ближайших точках грубой сетки.

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

На рис. 11.3 показаны три общие многосеточные схемы, в которых используются четыре различных размера сеток. Если расстояние между точками самой точной сетки равно А, то расстояние между точками других сеток — 2h, 4h и 8h (рис. 11.3). V-цикл в общем виде имеет несколько уровней: вначале на самой точной сетке выполняем несколько итераций, перехо­дим к более грубой сетке, снова выполняем несколько итераций, и так до тех пор, пока не окажемся на самой грубой сетке. На ней решим задачу. Затем интерполируем полученное решение на более точною сетку, выполним несколько итераций, и так далее, пока не прове­дем несколько итераций на самой точной сетке.



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

В полном многосеточном методе различные сетки используются столько же раз, сколько ив W-цикле, но при этом достигаются более точные результаты. В нем перед тем, как впер­вые использовать самую точную сетку, несколько раз выполняются вычисления на более гру­бых сетках, поэтому начальные значения для самой точной сетки оказываются правильнее. Полный многосеточный метод основан на рекуррентной последовательности шагов: 1) создаем начальное приближение к решению на самой грубой сетке, затем вычисляем на ней точное решение; 2) переходим к более точной сетке, выполняем на ней несколько итера­ций, возвращаемся к более грубой сетке и вновь находим на ней точное решение; 3) повторяем этот процесс, каждый раз поднимаясь на один уровень выше, пока не окажемся на самой точной сетке, после чего проходим полный V-цикл.

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



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

Синхронизация: поиск максимального элемента массива

Рассмотрим другую задачу, которая требует синхронизации процессов. Она состоит в по­иске максимального элемента массива а [п]. Предположим, что п положительно и все эле­менты массива — положительные целые числа.

Поиск максимального элемента в массиве а — это пример задачи накопления (сведения). В данном случае сохраняется (накапливается) максимальный из просмотренных элементов, или, иными словами, все значения сводятся к их максимуму. Пусть m — переменная для хра­нения максимального значения. Цель программы в логике предикатов можно описать так. (V  j:   1<=  j   <=  n:   m >=  a[j]) (3  j:   1<=   j   <=  n:   m = =  a[j]).

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

Глава 2. Процессы и синхронизация                                                                                             55

Для решения данной задачи можно использовать такую последовательную программу.

int m =   0;

for   [i   =   0   to n-1]    { if   (a[i]   > m)

m =  a [ i ] ; }

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

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

int m = 0,-co [i = О to n-1] if (a[i] > m) m = a [ i ] ;

Эта программа некорректна, поскольку процессы не являются независимыми: каждый из них и читает, и записывает переменную т. В частности, допустим, что все процессы выполняются с одинаковой скоростью, и, следовательно, каждый из них сравнивает свой элемент массива а [ i ] с переменной m в одно и то же время.
Все процессы определят, что неравенство выпол­няется (поскольку все элементы массива а больше начального значения переменной т, рав­ного нулю). Следовательно, все процессы попытаются обновить значение переменной т. Ап­паратное обеспечение памяти будет выполнять обновление в порядке некоторой очереди, по­скольку запись элемента в память— неделимая операция. Окончательным значением переменной m будет значение а [ i ], присвоенное ей последним процессом.

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

int m =  0; со   [i  =  0  to n-1] (if   <a[i]   > m) m =  a [ i ] ;}

Угловые скобки в этом фрагменте кода указывают, что каждый оператор i f выполняется как неделимая операция, т.е. проверяет текущее значение m и в соответствии с условием обновля­ет его в одном, неделимом действии. (Подробно нотация с угловыми скобками будет описана в следующем разделе.)

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

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

int m =   0 ; со   [i  =  0  to n-1] if   (a[i]   > m) (m = a[i];>

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

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


И хотя здесь ука­зано, что обновление m является неделимой операцией, фактически это осуществляется ап­паратным обеспечением памяти.

Итак, как же лучше всего решить эту задачу? Выход состоит в сочетании последних двух программ. Можно безопасно выполнять параллельные сравнения, поскольку это действия, ко­торые только читают переменные. Но необходимо обеспечить, чтобы при завершении програм­мы значение m действительно было максимальным. Это достигается в следующей программе.

int m =  0;

со   [i  =  0  to n-1]

if   (a[i]   > m)          #проверка  значения m

{if   (a[i]   > m)     # перепроверка значения m m =  a [ i ] ; >

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

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

Синхронизация типа "производитель-потребитель"

В последнем решении раздела 2.2 для задачи поиска шаблонов в файле использованы про­цесс-производитель и процесс-потребитель. Производитель постоянно считывает строки ввода, определяет, какие из них содержат искомый шаблон, и передает их процессу-потребителю. За­тем потребитель выводит строки, полученные от производителя. Взаимодействие между произ­водителем и потребителем обеспечивается с помощью разделяемой переменной buffer. Метод синхронизации доступа к буферу остался неопределенным, и теперь его можно описать.

Здесь решается более простая задача типа "производитель-потребитель": копирование всех элементов массива от производителя к потребителю. Адаптация этого решения к кон-, кретной задаче из раздела 2.2 оставляется читателю (см. упражнения в конце этой главы).

Даны два процесса: Producer (производитель) и Consumer (потребитель). Процесс Pro­ducer имеет локальный массив целых чисел a [n]; Consumer — b [n]. Предполагается, что массив а инициализирован. Цель — скопировать его содержимое в массив Ь. Поскольку про­цессы не разделяют массивы, для их взаимодействия нужны разделяемые переменные. Пусть переменная buf — это одиночная разделяемая целочисленная переменная, которая будет служить буфером взаимодействия.

Процессы Producer и Consumer должны получать доступ к переменной buf по очереди. Сначала Producer помещает первый элемент массива а в переменную buf, затем Consumer извлекает ее, потом Producer помещает в переменную buf следующий элемент массива а и так далее. Пусть разделяемые переменные рис будут счетчиками числа помещенных и из­влеченных элементов, соответственно. Их начальные значения — 0. Тогда условия синхрони­зации процессов Producer и Consumer могут быть записаны в следующем виде: PC: с <= р <= с+1

Значения переменных сир могут отличаться не больше, чем на 1; это значит, что Producer поместил в буфер максимум на один элемент больше, чем Consumer извлек. Код этих двух процессов приведен в листинге 2.2.

Процессы Producer и Consumer используют переменные рис (см. листинг 2.2) для син­хронизации доступа к буферу buf. Операторы await применяются для приостановки процес­сов до тех пор, пока буфер не станет полным или пустым. Если истинно условие р == с, буфер пуст (последний помещенный в него элемент был извлечен), а если р > с — заполнен.

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

Синхронное параллельное программирование

Часть 3

Синхронное параллельное программирование

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

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

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

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

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

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

20 В дальнейшем, если речь не идет о других видах параллелизма, слово "синхронные" иногда опуска­ется. — Прим ред.

404                                                      Часть 3 Синхронное параллельное программирование

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

В программах использованы языковые механизмы и методы программирования, описан­ные в частях 1 и 2. В главе 12 рассмотрены дополнительные языки, компиляторы, библиотеки и инструментарий для высокопроизводительных параллельных вычислений. Отдельные темы посвящены библиотеке ОрепМР для параллелизма с разделенной памятью, распараллели­вающим компиляторам, параллельным по данным, и функциональным языкам, абстрактным моделям, языку программирования High-Performance Fortran (HPF) и инструментальной системе Глобус для научных метавычислений.

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

Ускорение и эффективность

Как уже отмечалось, главная цель параллельного программирования — решить задачу бы­стрее. Уточним эту цель. Производительность программы определяется общим временем ее выполнения (работы). Пусть для решения некоторой задачи с помощью последовательной программы, выполняемой на одном процессоре, нужно время Т,, а с помощью параллельной программы, выполняемой на.р процессорах, — Тр. Тогда ускорение (speedup — S) параллельной программы определяется как 5= TJTp.



Например, пусть время работы последовательной программы равно 600 с, а время выпол­нения параллельной программы на 10 процессорах— 60с. Тогда ускорение параллельной программы равно 10. Такое ускорение называется линейным (или идеальным), поскольку программа на 10 процессорах работает в 10 раз быстрее. Обычно ускорение программы, вы­полняемой на р процессорах, оказывается меньше р. Такое ускорение называется менее, чем линейным (subhnear). Иногда ускорение оказывается более, чем линейным (superlinear), т.е. больше р; так бывает, когда данных в программе так много, что они не умещаются в кэш од­ного процессора, но после разделения их можно разместить в кэшах р процессоров.

Двойником ускорения является эффективность (Efficiency — Е) — мера того, насколько хорошо параллельная программа использует дополнительные процессоры. Она определяется следующим образом.

E=S/p=T,/(p*Tp)

Если программа имеет линейное ускорение, ее эффективность равна 1,0. Эффективность меньше 1,0 означает, что ускорение менее, чем линейное, а больше — что ускорение более, чем линейное.

Ускорение и эффективность относительны. Они зависят от количества процессоров, раз­мера задачи и используемого алгоритма. Например, часто эффективность параллельной программы с ростом числа процессоров снижается; например, при малом числе процессоров эффективность может быть близка к 1,0 и уменьшаться с ростом/». Аналогично параллельная программа может быть весьма эффективной при решении задач больших (но не малых) раз­меров. Говорят, что параллельная программа масштабируема, если ее эффективность посто­янна в широком диапазоне количеств процессоров и размеров задач. Наконец, ускорение и эффективность зависят от используемого алгоритма — параллельная программа может оказаться эффективной для одного последовательного алгоритма и неэффективной для другого. Поэтому лучшей мерой будет абсолютная эффективность (или абсолютное ускорение), для которой Tt — время работы программы по наилучшему из известных последовательных алгоритмов.



Ускорение и эффективность зависят от общего времени выполнения. Обычно программа имеет три фазы — ввод данных, вычисления, вывод данных. Предположим, что в последова­тельной программе фазы ввода и вывода данных занимают по 10% от времени выполнения, а фаза вычислений — остальные 80%. Предположим также, что фазам ввода и вывода прису-



В нашем примере доля фазы вычислений, которую можно распараллелить, равна 80 96, или 0,8. Следовательно, если ускорение этой фазы бесконечно, то общее ускорение все равно ос­танется равным 1/(1—0,8), т.е. 5. Однако общее ускорение на/? процессорах в действительно­сти меньше. Например, если ускорение вычислительной фазы на 10 процессорах равно 10, то общее ускорение — 1/(0,2+0,8/10), или приблизительно 3,57.

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

Накладные расходы и дополнительные проблемы

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



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

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

406                                                      Часть 3. Синхронное параллельное программирование

стоит в том, чтобы распараллелить вычисления и назначить процессам процессоры так, что­бы сбалансировать вычислительную нагрузку. Пусть Гсотр

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

Кроме последовательных компонентов, у параллельной программы есть еще три источни­ка накладных расходов: 1) создание процессов и их диспетчеризация, 2) взаимодействие и 3) синхронизация. Их нельзя исключить, поэтому вторая проблема — минимизировать их. К сожалению, накладные расходы взаимозависимы, и уменьшение одного может привести к увеличению других.

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


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

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

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


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

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

Часть 3 Синхронное параллельное программирование                                                      407

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

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


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

Глава 11 Научные вычисления

Существует два традиционных метода научных исследований — теория и эксперимент. Например, теоретическая физика занимается построением моделей, объясняющих физиче­ские явления, а экспериментальная физика — их изучением, часто для того, чтобы подтвер­дить или опровергнуть гипотезы. Теперь появился третий тип исследований — численное мо­делирование, в котором явления имитируются с помощью компьютеров, причем основной во­прос— "Что будет, если...?". Например, физик, применяющий численное моделирование, может написать программу, моделирующую эволюцию звезд или слияние ядер.

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

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

В данной главе представлены примеры сеточных, точечных и матричных вычислений. Для каждого метода описаны возможные алгоритмы и разработана последовательная программа. Затем составлены параллельные программы, сначала с помощью разделяемых переменных, а затем — передачи сообщений. Также показано, как оптимизировать программы, чтобы по­высить их производительность.

Синтаксис и семантика

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

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

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

Семафор объявляется так: sem s ;

По умолчанию начальным значением является 0, но семафор можно инициализировать лю­бым положительным значением, например:

sem lock =  1; Массивы семафоров можно объявлять и при необходимости инициализировать обычным образом:

sem  forks[5]   =   ([5]   1);

Если бы в этой декларации не было инициализации, то начальным значением каждого сема­фора в массиве forks был 0.

После объявления и инициализации семафор можно обрабатывать только с помощью операций р и V. Каждая из них является неделимым действием с одним аргументом. Пусть s — семафор. Тогда операции р (s) и V (s) определяются следующим образом.

P(s):   (await   (s>0)s=s-l;> V(s) :   (s   =   s   +   1;>

Операция V увеличивает значение s на единицу неделимым образом. Операция Р уменьшает значение s, но, чтобы после вычитания значение s не стало отрицательным, она сначала ожидает, пока s не станет положительным.

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

Обычный семафор может принимать любые неотрицательные значения, двоичный семафор — только значения 1 или 0. Это значит, что операция V для двоичного семафора может быть вы­полнена, только когда его значение 0. (Операцию V для двоичного семафора можно опреде­лить как ожидание, пока значение семафора станет меньше 1, и затем его увеличение на 1.)
Поскольку операции с семафором определяются в терминах операторов await, их фор­мальная семантика следует непосредственно из применения правила оператора await (см. раздел 2.6). Правила вывода для операций Р и V получаются непосредственно из правила опе­ратора await, примененного к конкретным операторам в определении Р и V.
Свойства справедливости для операций с семафорами тоже следуют из их определения с по­мощью оператора await. Используем терминологию раздела 2.8. Если условие s > 0 стано­вится и далее остается истинным, выполнение операции Р (s) завершится при справедливой в слабом смысле стратегии планирования. Если условие s > 0 становится истинным бесконеч­но часто, то выполнение операции Р (s) завершится при справедливой в сильном смысле стра­тегии планирования. Операция V для обычного семафора является безусловным неделимым действием, поэтому она завершится, если стратегия планирования безусловно справедлива.
Как будет показано в главе 6, при реализации семафоров обычно обеспечивается, что, ес­ли процессы приостанавливаются, выполняя операции р, они возобновляются в том же по-
' Буквы Р и V взяты от голландских слов (это описано в исторической справке в конце главы). Мож­но считать, что буква Р связана со словом "пропустить" (pass), а форма буквы V, расширяющаяся к вер­ху, обозначает увеличение значения. Некоторые авторы вместо Р и V используют названия wait и sig­nal, но здесь эти команды оставлены для главы о мониторах.
Глава 4 Семафоры                                                                                                                         133


рядке, в котором были приостановлены. Следовательно, процесс, ожидающий выполнения операции р, сможет в конце концов продолжить работу, если другие процессы выполнят со­ответствующее число операций V.
4.2. Основные задачи и методы
Семафоры непосредственно поддерживают реализацию взаимного исключения, необходи­мого, например, в задаче критической секции. Кроме того, они обеспечивают поддержку про­стых форм условной синхронизации, где они используются для сигнализации о событиях. Для решения более сложных задач эти два способа применения семафоров можно комбинировать.
В данном разделе иллюстрируется применение семафоров для взаимного исключения и ус­ловной синхронизации на примере решения четырех задач: критических секций, барьеров, про­изводителей и потребителей, ограниченных (кольцевых) буферов. В решении последних двух задач применяется метод, разделенных двоичных семафоров. В дальнейших разделах показано, как использовать представленные здесь методы для решения более сложных задач синхронизации.
4.2.1. Критические секции: взаимное исключение
Напомним, что в задаче критической секции каждый из п процессов многократно выпол­няет критическую секцию кода, в которой требуется исключительный доступ к некоторому разделяемому ресурсу, а затем некритическую секцию кода, в которой он работает только слокальными объектами. Каждому процессу, находящемуся в своей критической секции, нужен взаимоисключающий доступ к разделяемому ресурсу.
Семафоры были придуманы отчасти, чтобы облегчить решение задачи критической сек­ции В листинге 3.2 представлено решение, использующее переменные для блокировки, в ко­тором переменная lock имеет значение "истина", когда ни один процесс не находится в сво­ей критической секции, и значение "ложь" в противном случае. Пусть значение "истина" представлено как 1, а "ложь" — как 0. Тогда процесс перед входом в критическую секцию должен подождать, пока значение переменной lock не станет равным 1, и присвоить ей значе­ние 0.


Выходя из критической секции, процесс должен присвоить переменной lock значение 1.
Именно эти операции и поддерживаются семафорами. Пусть mutex — семафор с началь­ным значением 1. Выполнение операции Р (mutex) — это то же, что и ожидание, пока зна­чение переменной lock не станет равным 1, и последующее присвоение ей значения 0. Ана­логично выполнение операции V (mutex) — это то же, что присвоение lock значения 1 (при условии, что это можно сделать, только когда она имеет значение 0). Эти рассуждения приво­дят к решению задачи критической секции, показанному в листинге 4.1.

134                                               Часть 1 Программирование с разделяемыми переменными
4.2.2. Барьеры: сигнализирующие события
В разделе 3.4 барьерная синхронизация была представлена в качестве средства синхрони­зации алгоритмов, параллельных по данным (раздел 3.5). В реализациях барьеров с активным ожиданием использованы переменные-флаги, которые устанавливаются приходящими к барьеру процессами и сбрасываются покидающими его. Как при решении задачи критиче­ской секции, семафоры облегчают реализацию барьерной синхронизации. Основная идея — использовать семафор в качестве флага синхронизации. Выполняя операцию V, процесс ус­танавливает флаг, а при операции Р — ждет установки флага и сбрасывает его. (Если каждому процессу параллельной программы выделен собственный процессор, то задержки на барьерах должны быть реализованы с помощью циклов активного ожидания, а не блокировки процес­сов. Таким образом, желательна реализация семафоров с активным ожиданием.)
Вначале рассмотрим задачу реализации барьера для двух процессов. Напомним, что необ­ходимо выполнить два требования. Во-первых, ни один процесс не должен перейти барьер, пока к нему не подошли оба процесса. Во-вторых, барьер должен допускать многократное использование, поскольку обычно одни и те же процессы синхронизируются после каждого этапа вычислений. Для решения задачи критической секции достаточно лишь одного сема­фора для блокировки, поскольку нужно просто определить, находится ли процесс в критиче­ской секции.


Но при барьерной синхронизации необходимы два семафора в качестве сигна­лов, чтобы знать, приходит процесс к барьеру или уходит от него.
Сигнализирующий семафор s — это семафор с нулевым (как правило) начальным значени­ем. Процесс сигнализирует о событии, выполняя операцию V (s); другие процессы ожидают события, выполняя Р (s). Для двухпроцессного барьера два существенных события состоят втом, что процессы прибывают к барьеру. Следовательно, поставленную задачу можно ре­шить с помощью двух семафоров arrivel и arrive2. Каждый процесс сообщает о своем прибытии к барьеру, выполняя операцию V для своего семафора, и затем ожидает прибытия другого процесса, выполняя для его семафора операцию р. Это решение приведено в лис­тинге 4.2. Поскольку барьерная синхронизация симметрична, процессы действуют одинаково — каждый из них просто сигнализирует о прибытии и ожидает на других семафо­рах. Используемые таким образом семафоры похожи на флаговые переменные, поэтому их применение должно следовать принципам синхронизации флагами (3.14).

Глава 4. Семафоры                                                                                                                         135
прибытии, выполняя операцию V(arrive[i]), а затем ожидает прибытия остальных про­цессов, выполняя Р для их элементов массива arrive. В отличие от ситуации с переменны­ми-флагами здесь нужен только один массив семафоров arrive, поскольку действие опера­ции V "запоминается", тогда как значение флаговой переменной может быть перезаписано.
Семафоры можно использовать и в качестве сигнальных флагов в реализации барьерной синхронизации для п процессов с управляющим процессом (см. листинг 3.12) или комбини­рующим деревом (см. листинг 3.13). Операции V запоминаются, поэтому используется мень­ше семафоров, чем флаговых переменных. В управляющем процессе Coordinator (см. лис­тинг 3.12), например, нужен всего один семафор.
4.2.3. Производители и потребители: разделенные двоичные семафоры


В данном разделе вновь рассматривается задача о производителях и потребителях, постав­ленная в разделе 1.6 и пересмотренная в разделе 2.5. Там предполагалось, что есть только один про­изводитель и один потребитель. Здесь рассматривается общий случай, когда есть несколько произ­водителей и несколько потребителей. Приводимое ниже решение демонстрирует еще одно приме­нение семафоров в качестве сигнальных флагов и знакомит с важным понятием разделенного двоичного семафора, обеспечивающего еще один способ защиты критических секций кода.
В задаче о производителях и потребителях производители посылают сообщения, получае­мые потребителями. Процессы общаются с помощью разделяемого буфера, управляемого двумя операциями: deposit (поместить) и fetch (извлечь). Выполняя операцию deposit, производители помещают сообщения в буфер; потребители получают сообщения с помощью операции fetch. Чтобы сообщения не перезаписывались и каждое из них могло быть полу­чено только один раз, выполнение операций deposit и fetch должно чередоваться, причем первой должна быть deposit.
Запрограммировать необходимое чередование операций можно с помощью семафоров. Такие семафоры используются либо для сообщения о том, что процессы достигают критиче­ских точек выполнения, либо для отображения состояния разделяемых переменных. Здесь критические точки выполнения— это начало и окончание операций deposit и fetch. Соот­ветствующие изменения разделяемого буфера состоят в том, что он заполняется или опустоша­ется. Поскольку производителей и потребителей может быть много, проще связать семафор с каждым из двух возможных состояний буфера, а не с точками выполнения процессов.
Пусть empty (пустой) и full (полный) — два семафора, отображающие состояние буфе­ра. В начальном состоянии буфер пуст, поэтому семафор empty имеет значение 1 (т.е. про­изошло событие "опустошить буфер"), a full — 0. Перед выполнением операции deposit производитель сначала ожидает опустошения буфера.


Когда производитель помещает в буфер сообщение, буфер становится заполненным. И, наоборот, перед выполнением операции fetch потребитель сначала ожидает заполнения буфера, а затем опустошает его. Процесс ожидает события, выполняя операцию Р для соответствующего семафора, и сообщает о собы­тии, выполняя V. Полученное таким образом решение показано в листинге 4.3.
Переменные empty и full в листинге 4.3 являются двоичными семафорами. Вместе они образуют так называемый разделенный двоичный семафор, поскольку в любой момент времени только один из них может иметь значение 1. Термин "разделенный двоичный семафор" объ­ясняется тем, что переменные empty и full могут рассматриваться как единый двоичный семафор, разделенный на две части. В общем случае разделенный двоичный семафор может быть образован любым числом двоичных семафоров.
Роль разделенных двоичных семафоров особенно важна в реализации взаимного исклю­чения. Предположим, что один из двоичных семафоров инициализирован значением 1
136                                               Часть 1. Программирование с разделяемыми переменными
(соответственно, остальные имеют значение 0). Допустим, что в процессах, использующих семафоры, каждая выполняемая ветвь начинается операцией Р для одного из семафоров и заканчивается операцией V (для одного из семафоров). Тогда все операторы между Р и бли­жайшей V выполняются со взаимным исключением, т.е. если процесс находится между опе­рациями Р и V, то все семафоры равны 0, и, следовательно, ни один процесс не сможет за­вершить операцию Р, пока первый процесс не выполнит V.

Решение задачи производителей и потребителей (см. листинг 4.3) иллюстрирует именно такое применение семафоров. Каждый процесс-производитель Producer попеременно вы­полняет операции Р (empty) и V(full), а каждый процесс-потребитель Consumer — P(full) и V(empty). В разделе4.4 это свойство разделенного двоичного семафора будет использовано для создания общего метода реализации операторов await.


4.2.4. Кольцевые буферы: учет ресурсов
Из последнего примера видно, как синхронизировать доступ к одному буферу обмена. Если данные производятся и потребляются примерно с одинаковой частотой, то процессу не прихо­дится долго ждать доступа к буферу. Однако обычно потребитель и производитель работают нерав­номерно. Например, производитель может быстро создать сразу несколько элементов, а затем долго вычислять до следующей серии элементов. В таких случаях увеличение емкости буфера мо­жет существенно повысить производительность программы, уменьшая число блокировок процес­сов. (Это пример классического противоречия между временем вычислений и объемом памяти.)
Здесь решается так называемая задача о кольцевом буфере, который используется в качест­ве многоэлементного коммуникационного буфера. Решение основано на решении задачи из предыдущего раздела. Оно также демонстрирует применение обычных семафоров в качестве счетчиков ресурсов.
Предположим пока, что есть только один производитель и только один потребитель. Про­изводитель помещает сообщения в разделяемый буфер, потребитель извлекает их оттуда. Бу­фер содержит очередь уже помещенных, но еще не извлеченных сообщений. Эта очередь мо-
Глава 4 Семафоры                                                                                                                         137
жет быть представлена связанным списком или массивом. Здесь используется массив, более простой для программирования. Итак, представим буфер массивом buf [n], где п > 1. Пусть переменная front является индексом первого сообщения очереди, a rear — индек­сом первой пустой ячейки после сообщения в конце очереди. Вначале переменные front и rear имеют одинаковые значения, скажем, 0.
При таком представлении буфера производитель помещает в него сообщение со значени­ем data, выполнив следующие действия:
buf[rear]   = data;   rear =   (rear+1)   % n;
Аналогично потребитель извлекает сообщение в свою локальную переменную result, вы­полняя действия:


result  =  buf[front];   front  =   (front+1)   %  n;
Оператор взятия остатка (%) используется для того, чтобы значения переменных front и rear всегда были в пределах от о до п-1. Очередь буферизованных сообщений хранится в ячейках от buf [front] до buf [rear] (не включительно). Переменная buf интерпретируется как коль­цевой массив, в котором за buf [п-1] следует buf [0]. Вот пример конфигурации массива buf.

Затемненные ячейки заполнены, белые — пусты.
Если используется только один буфер (как в задаче "производитель—потребитель"), то выпол­нение операций deposit и fetch должно чередоваться. При наличии нескольких буферов опера­цию deposit можно выполнить, если есть пустая ячейка, a fetch — если сохранено хотя бы одно сообщение. Фактически, если есть пустая ячейка и сохраненное сообщение, операции deposit и fetch могут выполняться одновременно, поскольку обращаются к разным ячейкам и, следова­тельно, не влияют друг на друга. Однако требования синхронизации для одноэлементного и коль­цевого буфера одинаковы. В частности, операции Р и V применяются одним и тем же образом. Единственное отличие состоит в том, что семафор empty инициализируется значением n, а не 1, поскольку в начальном состоянии есть n пустых ячеек. Решение показано в листинге 4.4.

138                                               Часть 1. Программирование с разделяемыми переменными
V(empty);
}
_}________________________________________________________________________________
В листинге 4.4 семафоры играют роль счетчиков ресурсов: каждый учитывает количество элементов ресурса: empty — число пустых ячеек буфера, a full — заполненных. Когда ни один процесс не выполняет deposit или fetch, сумма значений обоих семафоров равна общему числу ячеек п. Семафоры, учитывающие ресурсы, полезны в случаях, когда процессы конкури­руют за доступ к таким многоэлементным ресурсам, как ячейки буфера или блоки памяти.
В программе (см. листинг 4.4) предполагалось, что есть только один производитель и один потребитель.


Это гарантировало неделимое выполнение операций deposit и fetch. Теперь предположим, что есть несколько процессов-производителей. При наличии хотя бы двух сво­бодных ячеек два из них могли бы выполнить операцию deposit одновременно. Но тогда оба попытались бы поместить свои сообщения в одну и ту же ячейку! (Если бы они присваивали но­вое значение ячейке buf [rear] до увеличения значения переменной rear.) Аналогично, если есть несколько потребителей, два из них одновременно могут выполнить fetch и получить од­но и то же сообщение. Таким образом, deposit и fetch становятся критическими секциями. Одинаковые операции должны выполняться со взаимным исключением, но разные могут вы­полняться одновременно, поскольку при работе семафоров empty и full производители и по­требители обращаются к разным ячейкам буфера. Необходимое исключение можно реализо­вать, используя решение задачи критической секции (см. листинг 4.1) с отдельными семафора­ми для защиты каждой критической секции. Законченное решение приведено в листинге 4.5.

Глава 4. Семафоры                                                                                                                                 139
Итак, отдельно решены две задачи синхронизации — сначала между одним производите­лем и одним потребителем, затем между несколькими производителями и несколькими по­требителями. В результате оказалось легко объединить решения двух подзадач для получения полного решения задачи. Такая же идея будет использована в решении задачи о читателях и писателях в разделе 4.3. Таким образом, везде, где присутствуют несколько типов синхро­низации, полезно реализовать их отдельно и затем объединить решения.

Словарь

Словарь

Активная блокировка (Spin Lock)

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

Активное (занятое) ожидание (Busy Waiting)

Реализация синхронизации, в которой процесс многократно выполняет цикл, ожидая, что некоторое булево условие в станет истинным. Обычно это программируется как while (! В) skip;. Если процесс находится в состоянии занятого ожидания, говорят так­же, что он зациклен (spinning).

Алгоритм "зонд-эхо" (Probe/Echo Algorithm)

Парадигма взаимодействия процессов в распределенных программах. Зонд используется для рассылки информации от одного процесса всем остальным, а эхо — для сбора информации.

Алгоритм передачи маркера (Token-Passing Algorithm)

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

Алгоритм пульсации (Heartbeat Algorithm)

Парадигма взаимодействия процессов в распределенных программах. Каждый процесс пе­риодически выполняет три фазы: 1) передает сообщения другим процессам, 2) принимает со­общения от других процессов, 3) выполняет вычисления с локальными данными и данными, полученными в сообщениях.

Алгоритм рассылки (Broadcast Algorithm)

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

Балансировка нагрузки (Load Balancing)

Назначение каждому процессу (и процессору) в параллельной программе приблизительно одинакового количества работы.

Барьер (Barrier)

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

Безусловное неделимое действие (Unconditional Atomic Action)

Неделимое действие, не имеющее условия задержки. Программируется как <S;> и может быть реализовано одной машинной командой.







Словарь                                                                                                                                    493

Переключение контекста (Context Switch)

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

Покрывающее условие (Covering Condition)

Механизм синхронизации, используемый с мониторами. Процесс передает сигнал условной переменной, когда можно продолжить выполнение ожидающих процессов. Условие, связан­ное с этой переменной, "покрывает" настоящие условия, которых ожидают процессы.

Постусловие (Postcondition)

Условие, истинное после выполнения оператора.

Поток (Thread)

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

Предусловие (Precondition)

Условие, истинное перед выполнением оператора.

Программа, параллельная по данным (Data Parallel Program)

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

Программа, параллельная по задачам (Task Parallel Program)

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

Программа типа "клиент-сервер" (Client/Server Program)

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



Процесс-фильтр (Filter Process)

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

Распределенная программа (Distributed Program)

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

Распределенная разделяемая память (Distributed Shared Memory — DSM)

Программная реализация разделяемого адресного пространства на мультипроцессоре с рас­пределенной памятью или на сети процессоров.

494                                                                                                                               Словарь

Рекурсивный параллелизм (Recursive Parallelism)

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

Свойство безопасности (Safety Property)

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

Свойство живучести (Liveness Property)

Свойство программы, утверждающее, что нечто надлежащее в конце концов произойдет, т.е. программа в конце концов достигнет "хорошего" состояния. Примерами данного свойства являются завершение и возможный вход в критическую секцию.

Свойство "не более одного" (At-Most-Once Property)

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


Такой оператор присваивания выполняется неделимым образом.

Симметричный мультипроцессор (Symmetric Multiprocessor — SMP)

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

Синхронизация (Synchronization)

Взаимодействие между процессами, управляющее порядком их выполнения; см. также Вза­имное исключение и Условная синхронизация.

Синхронная параллельная программа (Parallel Program)

Программа, в которой каждый процесс выполняется на своем собственном процессоре, т.е. процессы выполняются параллельно. (Вместе с тем, этот термин иногда употребляется по от­ношению к любой "многопроцессной" программе.)

Состояние гонок (Race Condition)

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

Состояние программы (State of a Program)

Значения всех переменных программы в некоторый момент времени.

Справедливость (Fairness)

Свойство диспетчера или алгоритма, гарантирующее, что каждый отложенный процесс полу­чит шанс на продолжение: см. также Стратегия планирования.

Словарь                                                                                                                             495

Стратегия планирования (Scheduling Policy)

Алгоритм, по которому определяется очередность действий, т.е. порядок выполнения процес­сов. Стратегия планирования бывает: а) безусловно справедливой, если безусловные неделимые действия в конце концов выполняются; б) справедливой в слабом смысле, если условные недели­мые действия в конце концов выполняются после того, как условие задержки стало и остается истинным, в) справедливой в сильном смысле, если условные неделимые действия в конце концов выполняются в ситуации, в которой условие задержки бывает истинным бесконечно часто.



Схема доказательства (Proof Outline)

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

Тройка (Triple)

Формула логики программирования вида { Р } S { Q }, где Р и Q — предикаты, as — список операторов. Интерпретация тройки следующая: если выполнение S начинается в со­стоянии, удовлетворяющем Р, и заканчивается, то заключительное состояние удовлетворяет Q.

Ускорение (Speedup)

Отношение т;/Тр, где т,— время выполнения последовательной программы на одном про­цессоре, тр — параллельной программы на р процессорах.

Условная синхронизация (Condition Synchronization)

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

Условное неделимое действие (Conditional Atomic Action)

Неделимое действие, которое должно быть отложено, пока некоторое булево условие в не станет истинным. Обычно оно программируется как <awai t (В) S; >.

Утверждение (Assertion)

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

Частичная корректность (Partial Correctness)

Свойство программы вычислять желаемый результат при условии, что она завершается.

Ядро (Kernel)

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

---

---