ПРОГРАММИРОВАНИЕ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ.docx

ПРОГРАММИРОВАНИЕ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ*

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

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

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

Анимация в кинофильмах. Конечно, было бы неверным связывать начало современной анимации с одним- единственным кинофильмом, однако многие считают фильм Звездные войны (Lucasfilm, 1977) началом современной волны компьютерной анимации в кинематографе. В настоящее время технология, использовавшаяся при создании таких классических мультфильмов Уолта Диснея, как Спящая красавица и Фантазия,  и предусматривающая  созда- ние многочисленных, сделанных вручную кадров, заменена технологиями компьютерной анимации, требующими применения современных многопроцессорных компьютерных систем. Кинозритель может согласиться, что примеры, описанные в начале этого раздела (бегущие антилопы и марширующие полчища муравьев), вовсе не являются наду- манными. Это – примеры из реальных кинофильмов, которые созданы с использованием компьютерных технологий (хотя и не обязательно так, как это описано в тексте, поскольку, в отличие от компьютерных игр, анимация в кино-

фильмах может быть разработана прежде, чем будет выполнена). Существуют ссылки на Web-страницы, посвящен-  ные анимации в кинофильмах. В частности, заинтересованный читатель может посетить следующие Web-узлы: http://www.lucasfilm.com, http://www.disney.go.com, http://www.pixar.com и http://www.pdi.com. Особенный интерес пред- ставляют Web-узлы http://www.antz.com и http://www.dreamworksgames.com.

Каждый из языков программирования стремится реализовать парадигму параллельной обработки со своей точки зре- ния, выраженной с помощью собственной терминологии. Например, то, что мы неформально называем запуском, в языке Ada именуется задачей (task), а в языке Java – потоком (thread). Таким образом, в программе на языке Ada одновременные действия осуществляются путем создания нескольких задач, тогда как программа на языке Java создает несколько потоков. В любом случае результатом является порождение нескольких процессов, которые выполняются так же, как и процессы под управлением многозадачной операционной системы. Поэтому далее мы договоримся ссылаться и на запущенную програм- му, и на задачу, и на поток как на процесс.

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

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

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

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

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

Один из способов решения этой проблемы заключается в описании подобных процессов в программе таким образом, что возможность их доступа к совместно используемым данным исключается до тех пор, пока работа с ними не станет безо- пасной. (Этот подход описан в разделе 3.4, где та часть процесса, которая имеет доступ к совместно используемым данным, была названа критической областью.) Опыт показал, что этот подход имеет недостаток, связанный с распределением задачи организации взаимно исключающего доступа между различными частями программы. В этом случае ошибка в описании любого из процессов, имеющих доступ к совместно используемым данным, способна вызвать повреждение всей системы в целом. По этой причине многие считают, что лучше объединять сами данные и средства контроля доступа к ним в единое целое. Такой управляющий механизм часто называют монитором (data monitor). Коротко говоря, в этом случае ответствен- ность за исключение множественного доступа к данным налагается не на процесс, который стремится получить доступ, а на те данные, к которым необходим доступ. В результате контроль над доступом к данным сосредоточивается в одном месте программы, а не распыляется среди множества ее сегментов³.

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

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

Вопросы для самопроверки

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

2.  Опишите два метода организации взаимно исключающего доступа к данным.

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

Скачано с www.znanio.ru