Процессы и синхронизация
_______________________________Глава 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 действительно является инвариантом вне операций request и 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 (потребитель). Процесс Producer имеет локальный массив целых чисел 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 и signal, но здесь эти команды оставлены для главы о мониторах.
Глава 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)
Набор структур данных и примитивных операций (непрерываемых процедур), который управляет процессами, распределяет их между процессорами и реализует взаимодействие высокого уровня и синхронизацию операций типа семафоров или обмен сообщениями.