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

       

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


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


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