Распараллеливание: поиск образца в файле
В главе 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; сигнализировать о заполнении буфера; } ос;
