В базовой последовательной модели программирования инструкции компьютерной программы выполняются поочередно. Программа выглядит как кулинарный рецепт, в соответствии с которым для каждого действия компьютера задан порядок и объемы используемых «ингредиентов». Разработчик программы разбивает основную задачу ПО на коллекцию подзадач. Все задачи выполняются по порядку, и каждая из них должна ожидать своей очереди. Все программы имеют начало, середину и конец. Разработчик представляет каждую программу в виде линейной последовательности задач. Эти задачи необязательно должны находиться в одном файле, но их следует связать между собой так, чтобы, если первая задача по какой-то причине не завершила свою работу, то вторая вообще не начинала выполнение. Другими словами, каждая задача, прежде чем приступить к своей работе, должна ожидать до тех пор, пока не получит результатов выполнения предыдущей. В последовательной модели зачастую устанавливается последовательная зависимость задач. Это означает, что задаче А необходимы результаты выполнения задачи В, а задаче В нужны результаты выполнения задачи С, которой требуется что-то от задачи D и т.д. Если при выполнении задачи В по какой-то причине произойдет сбой, задачи С и D никогда не п риступят к работе. В таком последовательном мире разработчик привычно ориентирует ПО сначала на выполнение действия 1, затем — действия 2, за которым должно следовать действие 3 и т.д. Подобная последовательная модель настолько закрепилась в процессе проектирования и разработки ПО, что многие программисты считают ее незыблемой и не допускают мысли о возможности иного положения вещей. Решение каждой проблемы, разработка каждого алгоритма и планирование каждой структуры данных — все это делалось с мыслью о последовательном доступе компьютера к каждой инструкции или ячейке данных.
Кардинальное изменение парадигмы
В мире параллельного программирования все обстоит по-другому. Здесь сразу несколько инструкций могут выполняться в один и тот же момент времени. Одна инструкция разбивается на несколько мелких частей, которые будут выполняться одновременно. Программа разбивается на множество параллельных задач. Программа может состоять из сотен или даже тысяч выполняющихся одновременно подпрограмм. В мире параллельного программирования последовательность и местоположение составляющих ПО не всегда предсказуемы. Несколько задач могут одновременно начать выполнение на любом процессоре без какой бы то ни было гарантии того, что задачи закреплены за определенными процессорами, или такая-то задача завершится первой, или все они завершатся в таком-то порядке. Помимо параллельного выполнения задач, здесь возможно параллельное выполнение частей (подзадач) одной задачи. В некоторых конфигурациях не исключена возможность выполнения подзадач на различных процессорах или даже различных компьютерах. На рис. 2.1 показаны три уровня параллелизма, которые могут присутствовать в одной компьютерной программе.
| #img_4.png Рис. 2.1. Три уровня параллелизма, которые возможны в одной компьютерной программе |
Модель программы, показанная на рис. 2.1, отражает кардинальное изменение парадигмы программирования, которая была характерна для «раннего» сознания программистов и разработчиков. Здесь отображены три уровня параллелизма и их распределение по нескольким процессорам. Сочетание этих трех уровней с базовыми параллельными конфигурациями процессоров показано на рис. 2.2.
| #img_5.png Рис. 2.2. Три уровня параллелизма в сочетании с конфигурациями процессоров базовыми параллельными |
Обратите внимание на то, что несколько задач может выполняться на одном процессоре даже при наличии в компьютере нескольких процессоров. Такая ситуация создается системными стратегиями планирования. На длительность выполнения задач, подзадач и инструкций оказывают влияние и выбранные стратегии планирования, и приоритеты процессов, и приоритеты потоков, и быстродействие устройств ввода-вывода. На рис. 2.2 следует обратить внимание на различные архитектуры, которые программист должен учитывать при переходе от последовательной модели программирования к параллельной. Основное различие в моделях состоит в переходе от строго упорядоченной последовательности задач к лишь частично упорядоченной (или вовсе неупорядоченной) коллекции задач. Параллелизм превращает ранее известные величины (порядок выполнения, время выполнения и место выполнения) в неизвестные. Любая комбинация этих неизвестных величин является причиной изменения значений программы, причем зачастую непредсказуемым образом.
Проблемы координации
Если программа содержит подпрограммы, которые могут выполняться параллельно, и эти подпрограммы совместно используют некоторые файлы, устройства или области памяти, то неизбежно возникают проблемы координации. Предположим, у нас есть программа поддержки электронного банка, которая позволяет снимать деньги со счета и класть их на депозит. Допустим, что эта программа разделена на три задачи (обозначим их А, В и С), которые могут выполняться параллельно.
Задача А получает запросы от задачи В на выполнение операций снятия денег со счета. Задача А также получает запросы от задачи С положить деньги на депозит. За-Дача А принимает запросы и обрабатывает их по принципу «первым пришел — первым обслужен». Предположим, на счете имеется 1000 долл., при этом задача С требует положить на депозит 100 долл., а задача В желает снять со счета 1100 долл. Что произойдет, если обе задачи В и С попытаются обновить один и тот же счет одновременно?
Каким будет остаток на счете? Очевидно, остаток на счете в каждый момент времени не может иметь более одного значения. Задача А применительно к счету должна выполнять одновременно только одну транзакцию, т.е. мы сталкиваемся с проблемой координации задач. Если запрос задачи В будет выполнен на какую-то долю секунды быстрее, чем запрос задачи С, то счет приобретет отрицательный баланс. Но если задача С получит первой право на обновление счета, то этого не произойдет. Таким образом, остаток на счете зависит от того, какой задаче (В или С) первой удастся сделать запрос к задаче А. Более того, мы можем выполнять задачи В и С несколько раз с одними и теми же значениями, и при этом иногда запрос задачи В будет произведен на какую-то долю секунды быстрее, чем запрос задачи С, а иногда — наоборот. Очевидно, что необходимо организовать надлежащую координацию действий.
Для координации задач, выполняемых параллельно, требуется обеспечить связь между ними и синхронизацию их работы. При некорректной связи или синхронизации обычно возникает четыре типа проблем.
Проблема №
1
: «гонка» данных
Если несколько задач одновременно попытаются изменить некоторую общую область данных, а конечное значение данных при этом будет зависеть от того, какая задача обратится к этой области первой, возникнет ситуация, которую называют состоянием «гонок» (race condition). В случае, когда несколько задач попытаются обновить один и тот же ресурс данных, такое состояние «гонок» называют «гонкой»данных (data race). Какая задача в нашей программе поддержки электронного банка первой получит доступ к остатку на счете, определяется результатом работы планировщика задач операционной системы, состоянием процессоров, временем ожидания и случайными причинами. В такой ситуации создается состояние «гонок». И какое значение в этом случае должен сообщать банк в качестве реального остатка на счете?
Итак, несмотря на то, что мы хотели бы, чтобы наша программа позволяла одновременно обрабатывать множество операций по снятию денег со счета и вложению их на депозит, нам нужно координировать эти задачи в случае, если окажется, что операции снятия и вложения денег должны быть применены к одному и тому же счету. Всякий раз когда задачи одновременно используют модифицируемый ресурс, к ресурсному доступу этих задач должны быть применены определенные правила и стратегии. Например, в нашей программе поддержки банковских операций со счетами мы могли бы всегда выполнять любые операции по вложению денег до выполнения каких бы то ни было операций по их снятию. Мы могли бы установить правило, в соответствии с которым доступ к счету одновременно могла получать только одна транзакция. И если окажется, что к одному и тому же счету одновременно обращается сразу несколько транзакций, их необходимо задержать, организовать их выполнение в соответствии с некоторым правилом очередности, а затем предоставлять им доступ к счету по одной (в порядке очереди). Такие правила организации позволяют добиться надлежащей синхронизации действий.
Проблема №
2:
бесконечная отсрочка
Такое планирование, при котором одна или несколько задач должны ожидать до тех пор, пока не произойдет некоторое событие или не создадутся определенные условия, м ожет оказаться довольно непростым для реализации. Во-первых, ожидаемое событие или условие должно отличаться регулярностью. Во-вторых, между задачами следует наладить связи. Если одна или несколько задач ожидают сеанса связи до своего выполнения, то в случае, если ожидаемый сеанс связи не состоится, состоится слишком поздно или не полностью, эти задачи могут так никогда и не выполниться. И точно так же, если ожидаемое событие или условие, которое (по нашему мнению) должно произойти (или наступить), но в действительности не происходит (или не наступает), то приостановленные нами задачи будут вечно находиться в состоянии ожидания. Если мы приостановим одну или несколько задач до наступления события (или условия), которое никогда не произойдет, возникнет ситуация, называемая бесконечной отсрочкой (indefinite postponement). Возвращаясь к нашему примеру электронного банка, предположим, что, если мы установим правила, предписывающие всем задачам снятия денег со счета находиться в состоянии ожидания до тех пор, пока не будут выполнены все задачи вложения денег на счет, то задачи снятия денег рискуют стать бесконечно отсроченными.
Мы исходили из предположения о гарантированном существовании задач вложения денег на счет. Но если ни один из запросов на пополнение счетов не поступит, то что тогда заставит выполниться задачи снятия денег? И, наоборот, что, если будут без конца поступать запросы на пополнение одного и того же счета? Ведь тогда не сможет «пробиться» к счету ни один из запросов на снятие денег. Такая ситуация также может вызвать бесконечную отсрочку задач снятия денег.
Бесконечная отсрочка возникает при отсутствии задач вложения денег на счет или их постоянном поступлении. Необходимо также предусмотреть ситуацию, когда запросы на вложение денег поступают корректно, но нам не удается надлежащим образом организовать связь между событиями и задачами. По мере того как мы будем пытаться скоординировать доступ параллельных задач к некоторому общему ресурсу данных, следует предусмотреть все ситуации, в которых возможно создание бесконечной отсрочки. Методы, позволяющие избежать бесконечных отсрочек, рассматриваются в главе 5.
Проблема №3: взаимоблокировка
Взаимоблокировка — это еще одна «ловушка», связанная с ожиданием. Для демонстрации взаимоблокировки предположим, что в нашей программе поддержки электронного банка три задачи работают не с одним, а с двумя счетами. Вспомним, что задача А получает запросы от задачи В на снятие денег со счета, а от задачи С — запросы на вложение денег на депозит. Задачи А, В и С могут выполняться параллельно. Однако задачи В и С могут обновлять одновременно только один счет. Задача А предоставляет доступ задач В и С к нужному счету по принципу «первым пришел — первым обслужен». Предположим также, что задача В имеет монопольный доступ к счету 1, а задача С — монопольный доступ к счету 2. При этом задаче В для выполнения соответствующей обработки также нужен доступ к счету 2 и задаче С — доступ к счету 1. Задача В удерживает счет 1, ожидая, пока задача С не освободит счет 2. Аналогично задача С удерживает счет 2, ожидая, пока задача В не освободит счет 1. Тем самым задачи В и С рискуют попасть в тупиковую ситуацию , которую в данном случае можно назвать взаимоблокировкой (deadlock). Ситуация взаимоблокировки между задачами В и С схематично показана на рис. 2.3.
Форма взаимоблокировки в данном случае объясняется наличием параллельно выполняемых задач, имеющих доступ к совместно используемым данным, которые им разрешено обновлять. Здесь возможна ситуация, когда каждая из задач будет ожидать до тех пор, пока другая не освободит доступ к общим данным (общими данными здесь являются счет 1 и счет 2). Обе задачи имеют доступ к обоим счетам. Может случиться так,
вместо получения доступа одной задачи к двум счетам, каждая задача получит доступ одному из счетов. Поскольку задача В не может освободить счет 1, пока не получит К туп к счету 2, а задача С не может освободить счет 2, пока не получит доступ к счету 1, программа обслуживания счетов электронного банка будет оставаться заблокированной. Обратите внимание на то, что задачи В и С могут ввести в состояние бесконечной отсрочки и другие задачи (если таковые имеются в системе). Если другие задачи ожидают получения доступа к счетам 1 или 2, а задачи В и С «скованы» взаимоблокировкой, то те другие задачи будут ожидать условия, которое никогда не выполнится. При координации параллельно выполняемых задач необходимо помнить, что взаимоблокировка и бесконечная отсрочка — это самые опасные преграды, которые нужно предусмотреть и избежать.
| #img_6.png Рис. 2.3. Ситуация взаимоблокировки между задачами В и С |
Проблема №4: трудности организации связи
Многие распространенные параллельные среды (например, кластеры) зачастую состоят из гетерогенных компьютерных сетей. Гетерогенные компьютерные сети— это системы, которые состоят из компьютеров различных типов, работающих в общем случае под управлением различных операционных систем и использующих различные сетевые протоколы. Их процессоры могут иметь различную архитектуру, обрабатывать слова различной длины и использовать различные машинные языки. Помимо разных операционных систем, компьютеры могут различаться используемыми стратегиями планирования и системами приоритетов. Хуже того, все системы могут различаться параметрами передачи данных. Это делает обработку ошибок и исключительных ситуаций (исключений) особенно трудной. Неоднородность системы может усугубляться и другими различиями. Например, может возникнуть необходимость организации совместного использования данных программами, написанными на различных языках или разработанных с использованием различных моделей ПО. Ведь общее системное решение может быть реализовано по частям, написанным на языках Fortran, С++ и J ava . Это вносит проблемы межъязыковой связи. И даже если распределенная или параллельная среда не является гетерогенной, остается проблема взаимодействия между несколькими процессами или потоками. Поскольку каждый процесс имеет собственное адресное пространство, то для совместного использования переменных, параметров и значений, возвращаемых функциями, необходимо применять технологию межпроцессного взаимодействия (interprocess communication — IPC), или МПВ-технологию. И хотя реализация МПВ-методов необязательно является самой трудной частью разработки системы ПО, тем не менее они образуют дополнительный уровень проектирования, тестирования и отладки в создании системы.
POSIX-спецификация поддерживает пять базовых механизмов, используемых для реализации взаимодействия между процессами:
• файлы со средствами блокировки и разблокировки;
• каналы (неименованные, именованные и FIFO-очереди);
• общая память и сообщения;
• сокеты;
• семафоры.
Каждый из этих механизмов имеет достоинства, недостатки, ловушки и тупики, которые проектировщики и разработчики ПО должны обязательно учитывать, если хотят создать надежную и эффективную связь между несколькими процессами. Организовать взаимодействие между несколькими потоками (которые иногда называются облегченными процессами) обычно проще, чем между процессами, так как потоки используют общее адресное пространство. Это означает, что каждый поток в программе может легко передавать параметры, принимать значения, возвращаемые функциями, и получать доступ к глобальным данным. Но если взаимодействие процессов или потоков не спроектировано должным образом, возникают такие проблемы, как взаимоблокировки, бесконечные отсрочки и другие ситуации «гонки» данных. Необходимо отметить, что перечисленные выше проблемы характерны как для распределенного, так и для параллельного программирования.
Несмотря на то что системы с исключительно параллельной обработкой отличаются от систем с исключительно распределенной обработкой, мы намеренно не проводили границу между проблемами координации в распределенных и параллельных системах. Частично мы можем объяснить это некоторым перекрытием существующих проблем, и частично тем, что некоторые решения проблем в одной области часто применимы к проблемам в другой. Но главная причина нашего «обобщенного» подхода состоит в том, что в последнее время гибридные (параллельно-распределенные) системы становятся нормой. Современное положение в параллельном способе обработке данных определяют кластеры и сетки. Причудливые кластерные конфигурации составляют из готовых продуктов. Такие архитектуры включают множество компьютеров со многими процессорами, а однопроцессорные системы уже уходят в прошлое. В будущем предполагается, что чисто распределенные системы будут встраиваться в виде компьютеров с несколькими процессорами. Это означает, что на практике проектировщик или разработчик ПО будет теперь все чаще сталкиваться с проблемами распределения и параллелизма. Вот потому-то мы и рассматриваем все эти проблемы в одном пространстве. В табл. 2.1 представлены комбинации параллельного и распределенного программирования с различными конфигурациями аппаратного обеспечения.
В табл. 2.1 обратите внимание на то, что существуют конфигурации, в которых параллелизм достигается за счет использования нескольких компьютеров. В этом случае подходит применение библиотеки PVM. И точно так же существуют конфигурации, в которых распределение может быть достигнуто лишь на одном компьютере за счет разбиения логики ПО на несколько процессов или потоков. Именно факт использования множества процессов или потоков говорит о том, что работа программы носит «распределенный» характер. Комбинации параллельного и распределенного программирования, представленные в табл. 2.1, подразумевают, что проблемы конфигурации, обычно присущие распределенному программированию, могут возникнуть в ситуациях, обусловленных параллельным программированием, и, наоборот, проблемы конфигурации, обычно связанные с параллельным программированием, могут возникнуть в ситуациях, обусловленных распределенным программированием.
Таблица2.1. Комбинации параллельного и распределенного программирования с различными конфигурациями аппаратного обеспечения
| Один компьютер | Множество компьютеров | |
| Параллельное программирование | Оснащен множеством процессоров. Использует логическое разбиение на несколько потоков или процессов. Потоки или процессы могут выполняться на различных процессорах. Для координации задач требуется МПВ-технология | Использует такие библиотеки, как PVM. Требует организации взаимодействия посредством передачи сообщений, что обычно связано с распределенным программированием |
| Распределенное программирование | Наличие нескольких процессоров не является обязательным. Логика ПО может быть разбита на несколько процессов или потоков. Для координации задач требуется МПВ-технология | Реализуется с помощью сокетов и таких компонентов, как CORBA ORB (Object Request Broker — брокер объектных запросов). Может использовать тип взаимодействия, который обычно связан с параллельным программированием |
Независимо от используемой конфигурации аппаратных средств, существует два базовых механизма, обеспечивающих взаимодействие нескольких задач: общая память и средства передачи сообщений. Для эффективного использования механизма общей памяти программисту необходимо предусмотреть решение проблем «гонки» Данных, взаимоблокировки и бесконечных отсрочек. Схема передачи сообщений Должна предполагать возникновение таких «накладок», как прерывистые передачи, бессмысленные (искаженные), утерянные, ошибочные, слишком длинные, просроченные (с нарушением сроков), преждевременные сообщения и т.п. Эффективное использование обоих механизмов подробно рассматривается ниже в этой книге.
Отказы оборудования и поведение ПО
При совместной работе множества процессоров над решением некоторой задачи возможен отказ одного или нескольких процессоров. Каким в этом случае должно быть поведение ПО? Программа должна остановиться или возможно перераспределение работы? Что случится, если при использовании мультикомпьютерной системы канал связи между несколькими компьютерами временно выйдет из строя? Что произойдет, если поток данных будет настолько медленным, что процессы на каждом конце связи превысят выделенный им лимит времени? Как ПО должно реагировать на подобные ситуации? Если, предположим, во время работы системы, состоящей из 50 компьютеров, совместно работающих над решением некоторой проблемы, произойдет отказ двух компьютеров, то должны ли остальные 48 взять на себя их функции? Если в нашей программе электронного банка при одновременном выполнении задач по снятию и вложению денег на счет две задачи попадут в ситуацию взаимоблокировки, то нужно ли прекратить работу серверной задачи? И что тогда делать с заблокированными задачами? А как быть, если задачи по снятию и вложению денег на счет будут работать надлежащим образом, но по какой-то причине будет «парализована» серверная задача? Следует ли в этом случае прекратить выполнение всех «повисших» задач по снятию и вложению денег на счет? Что делать с частичными отказами или прерывистой работой? Подобные вопросы обычно не возникают при работе последовательных программ в одно-компьютерных средах. Иногда отказ системы является следствием административной политики или стратегии безопасности. Например, предположим, что система содержит 1000 подпрограмм, и некоторым из них требуется доступ к файлу для записи в него информации, но они по какой-то причине не могут его получить. В результате возможны взаимоблокировка, бесконечная отсрочка или частичный отказ. А как быть, если некоторые подпрограммы блокируются из-за отсутствия у них прав доступа к нужным ресурсам? Должна ли в таких случаях «вырубаться» вся система целиком? Насколько можно доверять обработанной информации, если в системе произошли сбои в оборудовании, отказ каналов связи или их работа была прерывистой? Тем не менее эти ситуации очень даже характерны (можно сказать, являются нормой) для распределенных или параллельных сред. В этой книге мы рассмотрим ряд архитектурных решений и технологий программирования, которые позволят программному обеспечению системы справляться с подобными ситуациями.
Негативные последствия излишнего параллелизма и распределения
При внедрении технологии параллелизма всегда существует некоторая «точка насыщения», по «ту сторону» которой затраты на управление множеством процессоров превышают эффект от увеличения быстродействия и других достоинств параллелизма. Старая поговорка «процессоров никогда не бывает много» попросту не соответствует истине. Затраты на организацию взаимодействия между компьютерами или обеспечение синхронизации процессоров выливаются «в копеечку». Сложность синхронизации или уровень связи между процессорами может потребовать таких затрат вычислительных ресурсов, что они отрицательно скажутся на производительности задач, совместно выполняющих общую работу. Как узнать, на сколько процессов, задач или потоков следует разделить программу? И, вообще, существует ли оптимальное количество процессоров для любой заданной параллельной программы? В какой «точке» увеличение процессоров или компьютеров в системе приведет к замедлению ее работы, а не к ускорению? Нетрудно предположить, что рассматриваемые числа зависят от конкретной программы. В некоторых областях имитационного моделирования максимальное число процессоров может достигать нескольких тысяч, в то время как в коммерческих приложениях можно ограничиться несколькими сотнями. Для ряда клиент-серверных конфигураций зачастую оптимальное количество составляет восемь процессоров, а добавление девятого уже способно ухудшить работу сервера.
Всегда необходимо отличать работу и ресурсы, задействованные в управлении параллельными аппаратными средствами, от работы, направленной на управление параллельно выполняемыми процессами и потоками в ПО. Предел числа программных процессов может быть достигнут задолго до того, как будет достигнуто оптимальное количество процессоров или компьютеров. И точно так же можно наблюдать снижение эффективности оборудования еще до достижения оптимального количества параллельно выполняемых задач.
Выбор архитектуры
Существует множество архитектурных решений, которые поддерживают параллелизм. Архитектурное решение можно считать корректным, если оно соответствует декомпозиции работ (work breakdown structure — WBR) программного обеспечения (ДР ПО). Параллельные и распределенные архитектуры могут быть самыми разнообразными. В то время как некоторые распределенные архитектуры прекрасно работают в Web-среде, они практически обречены на неудачу в среде с реальным масштабом времени. Например, распределенные архитектуры, которые рассчитаны на длинные временные задержки, вполне приемлемы для Web-среды и совершенно неприемлемы для многих сред реального времени. Достаточно сравнить распределенную обработку данных в Web-ориентированной системе функционирования электронной почты с распределенной обработкой данных в банкоматах, или автоматических кассовых машинах (automated teller machine— ATM). Задержка (время ожидания), которая присутствует во многих почтовых Web-системах, была бы попросту губительной для таких систем реального времени, как банкоматы. Одни распределенные архитектуры (имеются в виду некоторые асинхронные модели) справляются с временными задержками лучше, чем другие. Кроме того, необходимо самым серьезным образом подходить к выбору соответствующих архитектур параллельной обработки данных. Например, методы векторной обработки данных наилучшим образом подходят для решения определенных математических задач и проблем имитационного моделирования, но они совершенно неэффективны в применении к мультиагентным алгоритмам планирования. Распространенные архитектуры ПО, которые поддерживают параллельное и распределенное программирование, показаны в табл. 2.2.
Четыре базовые модели, перечисленные в табл. 2.2, и их вариации обеспечивают основу для всех параллельных типов архитектур (т.е. объектно-ориентированного, агентно-ориентированного и «классной доски»), которые рассматриваются в этой книге. Разработчикам ПО необходимо подробно ознакомиться с каждой из этих моделей и их приложением к параллельному и распределенному программированию. Мы считаем своим долгом предоставить читателю введение в эти модели и дать библиографические сведения по материалам, которые позволят найти о них более детальную информацию. В каждой работе или при решении проблемы лучше всего искать естественный или присущий им параллелизм, а выбранный тип архитектуры Должен максимально соответствовать этому естественному параллелизму . Например, параллелизм в решении, возможно, лучше описывать с помощью симметричной модели, или модели сети с равноправными узлами (peer-to-peer model), в которой все сотрудники (исполнители) считаются равноправными, в отличие от несимметричной Модели «управляющий/рабочий», в которой существует главный (ведущий) процесс, Управляющий всеми остальными процессами как подчиненными.
| Модель | Архитектура | Распределенное программирование | Параллельное программирование |
| Модель ведущего узла, именуемая также: | Главный узел управляет задачами, т.е. контролирует их выполнение и передает работу подчиненным задачам | Ѵ | Ѵ |
| • главный/подчиненный; | |||
| • управляющий/рабочий; | |||
| • клиент/сервер | |||
| Модель равноправных узлов | Все задачи, в основном, имеют одинаковый ранг, и работа между ними распределяется равномерно | Ѵ | |
| Векторная или конвейерная (поточная)обработка | Один исполнительный узел соответствует каждому элементу массива (вектора) или шагу конвейера | Ѵ | Ѵ |
| Дерево с родительскими и дочерними элементами | Динамически генерируемые исполнители в отношении типа «родитель/потомок». Этот тип архитектуры полезно использовать в алгоритмах следующих типов: | Ѵ | Ѵ |
| • рекурсия; | |||
| • «разделяй и властвуй»; •И/ИЛИ | |||
| • древовидная обработка | |||
Различные методы тестирования и отладки
При тестировании последовательной программы разработчик может отследить ее логику в пошаговом режиме. Если он будет начинать тестирование с одних и тех же данных при условии, что система каждый раз будет пребывать в одном и том же состоянии, то результаты выполнения программы или ее логические цепочки будут вполне предсказуемыми. Программист может отыскать ошибки в программе, используя соответствующие входные данные и исходное состояние программы, путем проверки ее логики в пошаговом режиме. Тестирование и отладка в последовательной модели зависят от степени предсказуемости начального и текущего состояний программы, определяемых заданными входными данными.
С параллельным и распределенным программированием все обстоит иначе. Здесь трудно воспроизвести точный контекст параллельных или распределенных задач из-за разных стратегий планирования, применяемых в операционной системе, динамически меняющейся рабочей нагрузки, квантов процессорного времени, приоритетов процессов и потоков, временных задержек при их взаимодействии и собственно выполнении, а также различных случайных изменений ситуаций, характерных для параллельных или распределенных контекстов. Чтобы воспроизвести точное состояние в котором находилась среда при тестировании и отладке, необходимо воссоздать каждую задачу, выполнением которой была занята операционная система. При этом должен быть известен режим планирования процессорного времени и точно воспроизведены состояние виртуальной памяти и переключение контекстов. Кроме того, следует воссоздать условия возникновения прерываний и формирования сигналов, а в некоторых случаях — даже рабочую нагрузку сети. При этом нужно понимать, что и сами средства тестирования и отладки оказывают немалое влияние на состояние среды. Это означает, что создание одинаковой последовательности событий для тестирования и отладки зачастую невозможно. Необходимость воссоздания всех перечисленных выше условий обусловлено тем, что они позволяют определить, какие процессы или потоки следует выполнять и на каких именно процессорах. Смешанное выполнение процессов и потоков (в некоторой неудачной «пропорции») часто является причиной возникновения взаимоблокировок, бесконечных отсрочек, «гонки» данных и других проблем. И хотя некоторые из этих проблем встречаются и в последовательном программировании, они не в силах зачеркнуть допущения, сделанные при построении последовательной модели. Тот уровень предсказуемости, который имеет место в последовательной модели, недоступен для параллельного программирования. Это заставляет разработчика овладевать новыми тактическими приемами для тестирования и отладки параллельных и распределенных программ, а также требует от него поиска новых способов доказательства корректности его программ .
Связь между параллельным и распределенным проектами
При создании документации на проектирование параллельного или распределенного ПО необходимо описать декомпозицию работ и их синхронизацию, а также взаимодействие между задачами, объектами, процессами и потоками. При этом проектировщики должны тесно контактировать с разработчиками, а разработчики — с теми, кто будет поддерживать систему и заниматься ее администрированием. В идеале это взаимодействие должно осуществляться по действующим стандартам. Однако найти единый язык, понятный всем сторонам и позволяющий четко представить мультипарадигматическую природу всех этих систем, — трудно достижимая цель. Мы остановили свой выбор на языке UML (Unified Modeling Language — унифицированный язык моделирования). В табл. 2.3 перечислено семь UML-диаграмм, которые часто используются при создании многопоточных, параллельных или распределенных программ.
Семь диаграмм, перечисленных в табл. 2.3, представляют собой лишь подмножество диаграмм, которые предусмотрены языком UML, но они наиболее всего подходят к тому, что мы хотим подчеркнуть в наших проектах параллельного ПО. В частности, UML-диаграмм деятельности, развертывания и состояний весьма полезны для описания взаимодействующего поведения параллельной и распределенной подсистем обработки данных. Поскольку UML — это фактический стандарт, используемый при создании взаимодействующих объектно-ориентированных и агентно-ориентированных проектов, при изложении материала в этой книге мы опираемся именно на него. Описание обозначений и символов, используемых в перечисленных выше диаграммах, содержится в приложении А.
Таблица 2.3. UML-диаграммы, используемые при создании многопоточных, параллельных или распределенных программ
Диаграмма (видов) деятельности - разновидность диаграммы состояний, в которой большинство состояний (или все) представляют виды деятельности, а большинство переходов (или все) активизируются при выполнении некоторого действия в исходных состояниях
Диаграмма взаимодействия - Тип диаграммы, которая отображает взаимодействие между объектами. Взаимодействия описываются в виде сообщений, которыми они обмениваются. К диаграммам взаимодействия относятся диаграммы сотрудничества, диаграммы последовательностей и диаграммы (видов)деятельности
Диаграмма (параллельных) состояний - Диаграмма, которая показывает последовательность преобразований объекта в процессе его реакции на события. При использовании диаграммы параллельных состояний эти преобразования могут происходить в течение одного и того же интервала времени
Диаграмма последовательностей - Диаграмма взаимодействия, в которой отображается организация структуры объектов, принимающих или отправляющих сообщения (с акцентом на упорядочении сообщений по времени)
Диаграмма сотрудничества - Диаграмма взаимодействия, в которой отображается организация структуры объектов, принимающих или отправляющих сообщения (с акцентом на структурной организации)
Диаграмма развертывания (внедрения) - Диаграмма, которая показывает динамическую конфигурацию узлов обработки, аппаратных средств и программных компонентов в системе
Диаграмма компонентов - Диаграмма взаимодействия, в которой отображается организация физических модулей программного кода (пакетов) в системе и зависимости между ними
Резюме
При создании параллельного и распределенного ПО разработчиков ожидает множество проблем. Поэтому при проектировании ПО им необходимо искать новые архитектурные подходы и технологии. Многие фундаментальные допущения, которых придерживались разработчики при построении последовательных моделей программирования, совершенно неприемлемы в области создания параллельного и распределенного ПО. В программах, включающих элементы параллелизма, программисты чаще всего сталкиваются со следующими четырьмя проблемами координации: «гонка» данных, бесконечная отсрочка, взаимоблокировка и проблемы синхронизации при взаимодействии задач. Наличие параллелизма и распределения оказывает огромное влияние на все аспекты жизненного цикла разработки ПО: начиная эскизным проектом и заканчивая тестированием готовой системы и подготовкой документации. В этой книге мы представляем архитектурные подходы к решению многих упомянутых проблем, используя преимущества мультипарадигматических средств языка С++, которые позволяют справиться со сложностью параллельных и распределенных программ.