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

       

Приложения и стили программирования


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

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

•    оконные системы на персональных компьютерах или рабочих станциях;

•    многопроцессорные операционные системы и системы с разделением времени;

•    системы реального времени, управляющие электростанциями, космическими аппара­тами и т.д.

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

•    файловые серверы в сети;

•    системы баз данных для банков, заказа авиабилетов и т.д.;

•    Web-серверы сети Internet;

26                                                                   Глава 1. Обзор области параллельных вычислений

•    предпринимательские системы, объединяющие компоненты производства;

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

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

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



•    научные вычисления, которые моделируют и имитируют такие явления, как глобальный климат, эволюция солнечной системы или результат действия нового лекарства;

•    графика и обработка изображений, включая создание спецэффектов в кино;

•    крупные комбинаторные или оптимизационные задачи, например, планирование авиаперелетов или экономическое моделирование.

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



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

Существует немало параллельных программных приложений, однако в них используется лишь небольшое число моделей решений, или парадигм. В частности, существует пять основ­ных парадигм: 1) итеративный параллелизм, 2) рекурсивный параллелизм, 3) "производители и потребители" (конвейеры), 4) "клиенты и серверы", 5) взаимодействующие равные. С ис­пользованием одной или нескольких из этих парадигм и программируются приложения.

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

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


Рекурсия часто применяется в императивных языках программирова­ния, особенно при реализации алгоритмов типа "разделяй и властвуй" или "перебор с воз-

1 4. Итеративный параллелизм: умножение матриц                                                               27

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

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

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

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

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


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