Параллельное и распределенное программирование на С++

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

Синхронизация

Декомпозиция работ, как уже было отмечено выше, определяет, что должны делать разные части ПО. Когда множество компонентов ПО работают в рамках одной задачи, их функционирование необходимо координировать. Определенный компонент должен «уметь» определить, когда достигается решение всей задачи. Необходимо также скоординировать порядок выполнения компонентов. При этом возникает множество вопросов. Все ли части ПО должны одновременно приступать к работе или только некоторые, а остальные могут находиться пока в состоянии ожидания? Каким двум (или больше) компонентам необходим доступ к одному и тому же ресурсу? Кто имеет право получить его первым? Если некоторые части ПО завершат свою работу гораздо раньше других, то нужно ли им «поручать» новую работу? Кто должен давать новую работу в таких случаях? ДСС (декомпозиция, связь и синхронизация) — это тот минимум вопросов, которые необходимо решить, приступая к параллельному или распределенному программированию. Помимо сути проблем, составляющих ДСС, важно также рассмотреть их привязку. Существует несколько уровней параллелизма в разработке приложений, и в каждом из них ДСС-составляющие применяются по-разному.

Базовые уровни программного параллелизма

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

• инструкций;

• подпрограмм (функций или процедур);

• объектов;

• приложений.

Параллелизм на уровне инструкций

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

На рис. 1.3 компонент (А + В) можно вычислить одновременно с компонентом (С - D) • Этот вид параллелизма обычно поддерживается директивами компилятора и не попадает под управление С++-программиста.

Рис. 1.3. Декомпозиция одной инструкции

Параллелизм на уровне подпрограмм

ДСС структуру программы можно представить в виде ряда функций, т.е. сумма работ, из которых состоит программное решение, разбивается на некоторое количество функций. Если эти функции распределить по потокам, то каждую функцию в этом случае можно выполнить на отдельном процессоре, и, если в вашем распоряжении будет достаточно процессоров, то все функции смогут выполняться одновременно. Подробнее потоки описываются в главе 4.

Параллелизм на уровне объектов

ДСС-структуру программного решения можно распределить между объектами. Каждый объект можно назначить отдельному потоку или процессу. Используя стандарт CORBA (Common Object Request Broker Architecture — технология построения распределенных объектных приложений), все объекты можно назначить различным компьютерам одной сети или различным компьютерам различных сетей. Более детально технология CORBA рассматривается в главе 8. Объекты, реализованные в различных потоках или процессах, могут выполнять свои методы параллельно.

Параллелизм на уровне приложений

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

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

Отсутствие языковой поддержки параллелизма в С++

Язык С++ не содержит никаких синтаксических примитивов для параллелизма. С++-стандарт ISO также отмалчивается на тему многопоточности. В языке С++ не предусмотрено никаких средств, чтобы указать, что заданные инструкции должны выполняться параллельно. Включение встроенных средств параллелизма в других языках представляется как их особое достоинство. Бьерн Страуструп, создатель языка С++, имел свое мнение на этот счет:

Можно организовать поддержку параллелизма средствами библиотек, которые будут приближаться к встроенным средствам параллелизма как по эффективности, так и по удобству применения. Опираясь на такие библиотеки, можно поддерживать различные модели, а не только одну, как при использования встроенных средств параллелизма. Я полагаю, что большинство программистов согласятся со мной, что именно такое направление (создание набора библиотек поддержки параллелизма) позволит решить проблемы переносимости, используя тонкий слой интерфейсных классов.

Более того, Страуструп говорит: « Я считаю, что параллелизм в С++ должен быть представлен библиотеками, а не как языковое средство» . Авторы этой книги находят позицию Страуструпа и его рекомендации по реализации параллелизма в качестве библиотечного средства наиболее подходящими с практической точки зрения. В настоящей книге рассмотрен только этот вариант, и такой выбор объясняется доступностью высококачественных библиотек, которые успешно можно использовать для решения задач параллельного и распределенного программирования. Библиотеки, которые мы используем для усиления языка С++ с этой целью, реализуют национальные и международные стандарты и используются тысячами С++-программистов во всем мире.

Варианты реализации параллелизма с помощью С++

Несмотря на существование специальных версий языка С++, предусматривающих «встроенные» средства параллельной обработки данных, мы представляем методы реализации параллелизма с использованием стандарта ISO (International Organization for Standardization — Международная организация по стандартизации) для С++. Мы находим библиотечный подход к параллелизму (при котором используются как системные, так и пользовательские библиотеки) наиболее гибким. Системные библиотеки предоставляются средой операционной системы. Например, поточно-ориентированная библиотека POSIX (Portable Operating System Interface — интерфейс переносимой операционной системы) содержит набор системных функций, которые в сочетании с языковыми средствами С++ успешно используются для поддержки параллелизма. Библиотека POSIX Threads является частью нового единого стандарта спецификаций UNIX (Single UNIX Specifications Standard) и включена в набор стандартов IEEE, описывающих интерфейсы ОС для UNIX (IEEE Std. 1003.1-2001). Создание нового единого стандарта спецификаций UNIX финансируется организацией Open Group, а его разработка поручена организации Austin Common Standards Revision Group. В соответствии с документами Open Group новый единый стандарт спецификаций UNIX:

• предоставляет разработчикам ПО единый набор API-функций, которые должны поддерживаться каждой UNIX-системой;

• смещает акцент с несовместимых реализаций систем UNIX на соответствие единому набору функций API;

• представляет собой кодификацию и юридическую стандартизацию общего ядра системы UNIX;

• в качестве основной цели преследует достижение переносимости исходного кода приложения.

Новый единый стандарт спецификаций UNIX, версия 3, включает стандарт IEEE Std. 1003.1-2001 и спецификации Open Group Base Specifications Issue 6. Стандарты IEEE POSIX в настоящее время представляют собой часть единой спецификации UNIX, и наоборот. Сейчас действует единый международный стандарт для интерфейса переносимой операционной системы. С++-разработчикам это только на руку, поскольку данный стандарт содержит API-функции, которые позволяют создавать потоки и процессы. За исключением параллелизма на уровне инструкций, единственным способом достижения параллелизма с помощью С++ является разбиение программы на потоки или процессы. Именно эти средства и предоставляет новый стандарт. Разработчик может использовать:

• библиотеку POSIX Threads (или Pthreads);

• POSIX-версию spawn ();

• семейство функций exec ().

Все эти средства поддерживаются системными API-функциями и системными библиотеками. Если операционная система отвечает 3-й версии нового единого стандарта UNIX, то С++-разработчику будут доступны эти API-функции (они рассматриваются в главах З и 4 и используются во многих примерах этой книги). Помимо библиотек системного уровня, для поддержки параллелизма в С++ могут применяться такие библиотеки пользовательского уровня, как MPI (Message Passing Interface — интерфейс для передачи сообщений), PVM (Parallel Virtual Machine — параллельная виртуальная машина) и CORBA (Common Object Request Broker Architecture — технология построения распределенных объектных приложений).

Стандарт MPI

Интерфейс MPI — стандартная спецификация на передачу сообщений — был разработан с целью достижения высокой производительности на компьютерах с массовым параллелизмом и кластерах рабочих станций (рабочая станция — это сетевой компьютер, использующий ресурсы сервера). В этой книге используется MPICH-реализация стандарта MPI. MPICH — это свободно распространяемая переносимая реализация интерфейса MPI. MPICH предоставляет С++-программисту набор API-функций и библиотек, которые поддерживают параллельное программирование. Интерфейс MPI особенно полезен для программирования моделей SPMD (Single-Program, Multiple Data - одна программа , несколько потоков данных) и MPMD (Multiple-Program, Multiple-Data — множество программ, множество потоков данных). Авторы этой книги используют MPICH-реализацию библиотеки MPI для 32-узлового Linux-ориентированного кластера и 8-узлового кластера, управляемого операционными системами Linux и Solaris. И хотя в С++ нет встроенных примитивов параллельного программирования, С++-программист может воспользоваться средствами обеспечения параллелизма, предоставляемыми библиотекой MPICH. В этом и состоит одно из достоинств языка С++, которое заключается в его фантастической гибкости.

PVM: стандарт для кластерного программирования

Программный пакет PVM позволяет связывать гетерогенную (неоднородную) коллекцию компьютеров в сеть для использования ее в качестве единого мощного параллельного компьютера. Общая цель PVM-системы — получить возможность совместно использовать коллекцию компьютеров для организации одновременной или параллельной обработки данных. Реализация библиотеки PVM поддерживает:

• гетерогенность по компьютерам, сетям и приложениям;

• подробно разработанную модель передачи сообщений;

• обработку данных на основе выполнения процессов;

• мультипроцессорную обработку данных (MPP, SMP) [5];

• «полупрозрачный» доступ к оборудованию (т.е. приложения могут либо игнорировать, либо использовать преимущества различий в аппаратных средствах);

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

PVM — это самая простая (по использованию) и наиболее гибкая среда, доступная для решения задач параллельного программирования, которые требуют применения различных типов компьютеров, работающих под управлением различных операционных систем. PVM-библиотека особенно полезна для объединения в сеть нескольких однопроцессорных систем с целью образования виртуальной машины с параллельно работающими процессорами. Методы использования библиотеки PVM в С++-коде мы рассмотрим в главе 6. PVM — это фактический стандарт для реализации гетерогенных кластеров, который легко доступен и широко распространен. PVM прекрасно поддерживает модели параллельного программирования MPMD (MIMD) и SPMD (SIMD). Авторы этой книги для решения небольших и средних по объему задач параллельного программирования используют PVM-библиoтeкy, а для более сложных и объемных — MPI-библиотеку. Обе библиотеки PVM и MPI можно успешно сочетать с С++ для программирования кластеров.

Стандарт CORBA

CORBA— это стандарт для распределенного кроссплатформенного объектно-ориентированного программирования. Выше упоминалось о применении CORBA для поддержки параллелизма, поскольку реализации стандарта CORBA можно использовать для разработки мультиагентных систем. Мультиагентные системы предлагают важные сетевые модели распределенного программирования с равноправными узлами (peer-to_peer). В мультиагентных системах работа может быть организована параллельно. Это одна из областей, в которых параллельное и распределенное программирование перекрываются. Несмотря на то что агенты выполняются на различных компьютерах, это происходит в течение одного и того же промежутка времени, т.е. агенты совместно работают над общей проблемой. Стандарт CORBA обеспечивает открытую, независимую от изготовителя архитектуру и инфраструктуру, которую компьютерные приложения используют для совместного функционирования в сети. Используя стандартный протокол IIOР (Internet InterORB Protocol — протокол, определяющий передачу сообщений между сетевыми объектами по TCP/IP), CORBA-ориентированная программа (созданная любым производителем на любом языке программирования, выполняемая практически на любом компьютере под управлением любой операционной системы в любой сети) может взаимодействовать с другой CORBA-ориентированной программой (созданной тем же или другим производителем на любом другом языке программирования, выполняемой практически на любом компьютере под управлением любой операционной системы в любой сети). В этой книге мы используем MICO-реализацию стандарта CORBA. MICO— свободно распространяемая и полностью соответствующая требованиям реализация стандарта CORBA, которая поддерживает язык С++.

Реализации библиотек на основе стандартов

Библиотеки MPICH, PVM, MICO и POSIX Threads реализованы на основе стандартов. Это означает, что разработчики ПО могут быть уверены, что эти реализации широко доступны и переносимы с одной платформы на другую. Эти библиотеки используются многими разработчиками ПО во всем мире. Библиотеку POSIX Threads можно использовать с С++ для реализации многопоточного программирования. Если программа выполняется на компьютере с несколькими процессорами, то каждый поток может выполняться на отдельном процессоре, что позволяет говорить о реальной параллельности программирования. Если же компьютер содержит только один процессор, то иллюзия параллелизма обеспечивается за счет процесса переключения контекстов. Библиотека POSIX Threads позволяет реализовать, возможно, самый простой способ введения параллелизма в С++-программу. Если для использования библиотек MPICH, PVM и MICO необходимо предварительно побеспокоиться об их установке, то в отношении библиотеки POSIX Threads это излишне, поскольку среда любой операционной системы, которая согласована с POSIX-стандартом или новой спецификацией UNDC (версия 3), оснащена реализацией библиотеки POSIX Threads. Все библиотеки предлагают модели параллелизма, которые имеют незначительные различия. В табл. 1.2 показано, как каждую библиотеку можно использовать с С++.

Таблица 1.2. Использование библиотек MPICH, PVM, MICO и POSIX Threads с С++

MPICH  Поддерживает крупномасштабное сложное программирование кластеров. Предпочтительно используется для модели SPMD. Также поддерживает SMP-, MPP- и многопользовательские конфигурации

PVM Поддерживает кластерное программирование гетерогенных сред. Легко

используется для однопользовательских (мелко- и среднемасштабных) ._____кластерных приложений. Также поддерживает МРР-конфигурации .

MICO Поддерживает и распределенное, и параллельное программирование.

Содержит эффективные средства поддержки агентно-ориентированного и мультиагентного программирования

POSIX Поддерживает параллельную обработку данных в одном приложении на

уровне функций или объектов. Позволяет воспользоваться преимуществами SMP- и МРР-конфигурации

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

Среды для параллельного и распределенного программирования

Наиболее распространенными средами для параллельного и распределенного программирования являются кластеры, SMP- и МРР-компьютеры.

Кластеры — это коллекции, состоящие из нескольких компьютеров, объединенных сетью для создания единой логической системы. С точки зрения приложения такая группа компьютеров выглядит как один виртуальный компьютер. Под MPP-конфигурацией (Massively Parallel Processors — процессоры с массовым параллелизмом) понимается один компьютер, содержащий сотни процессоров, а под SMP-конфигурацией (symmetric multiprocessor — симметричный мультипроцессор) — единая система, в которой тесно связанные процессоры совместно используют общую память и информационный канал. SMP-процессоры разделяют общие ресурсы и являются объектами управления одной операционной системы. Поскольку эта книга представляет собой введение в параллельное и распределенное программирование, нас будут интересовать небольшие кластеры, состоящие из 8-32 процессоров, и многопроцессорные компьютеры с двумя-четырьмя процессорами. И хотя многие рассматриваемые здесь методы можно использовать в MPP- или больших SMP-средах, мы в основном уделяем внимание системам среднего масштаба.

Резюме

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

Проблемы параллельного и распределенного программирования

«Стремление обозначать точные значения любой физической величины (температура, плотность, напряженность потенциального поля или что-либо еще...) есть не что иное как смелая экстраполяция.»

Эрвин Шредингер (Erwin Shrodinger), Causality and Wave Mechanics

В базовой последовательной модели программирования инструкции компьютерной программы выполняются поочередно. Программа выглядит как кулинарный рецепт, в соответствии с которым для каждого действия компьютера задан порядок и объемы используемых «ингредиентов». Разработчик программы разбивает основную задачу ПО на коллекцию подзадач. Все задачи выполняются по порядку, и каждая из них должна ожидать своей очереди. Все программы имеют начало, середину и конец. Разработчик представляет каждую программу в виде линейной последовательности задач. Эти задачи необязательно должны находиться в одном файле, но их следует связать между собой так, чтобы, если первая задача по какой-то причине не завершила свою работу, то вторая вообще не начинала выполнение. Другими словами, каждая задача, прежде чем приступить к своей работе, должна ожидать до тех пор, пока не получит результатов выполнения предыдущей. В последовательной модели зачастую устанавливается последовательная зависимость задач. Это означает, что задаче А необходимы результаты выполнения задачи В, а задаче В нужны результаты выполнения задачи С, которой требуется что-то от задачи D и т.д. Если при выполнении задачи В по какой-то причине произойдет сбой, задачи С и D никогда не п риступят к работе. В таком последовательном мире разработчик привычно ориентирует ПО сначала на выполнение действия 1, затем — действия 2, за которым должно следовать действие 3 и т.д. Подобная последовательная модель настолько закрепилась в процессе проектирования и разработки ПО, что многие программисты считают ее незыблемой и не допускают мысли о возможности иного положения вещей. Решение каждой проблемы, разработка каждого алгоритма и планирование каждой структуры данных — все это делалось с мыслью о последовательном доступе компьютера к каждой инструкции или ячейке данных.

Кардинальное изменение парадигмы

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

Рис. 2.1. Три уровня параллелизма, которые возможны в одной компьютерной программе

Модель программы, показанная на рис. 2.1, отражает кардинальное изменение парадигмы программирования, которая была характерна для «раннего» сознания программистов и разработчиков. Здесь отображены три уровня параллелизма и их распределение по нескольким процессорам. Сочетание этих трех уровней с базовыми параллельными конфигурациями процессоров показано на рис. 2.2.

Рис. 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, а задачи В и С «скованы» взаимоблокировкой, то те другие задачи будут ожидать условия, которое никогда не выполнится. При координации параллельно выполняемых задач необходимо помнить, что взаимоблокировка и бесконечная отсрочка — это самые опасные преграды, которые нужно предусмотреть и избежать.

Рис. 2.3. Ситуация взаимоблокировки между задачами В и С

Проблема №4: трудности организации связи

Многие распространенные параллельные среды (например, кластеры) зачастую состоят из гетерогенных компьютерных сетей. Гетерогенные компьютерные сети— это системы, которые состоят из компьютеров различных типов, работающих в общем случае под управлением различных операционных систем и использующих различные сетевые протоколы. Их процессоры могут иметь различную архитектуру, обрабатывать слова различной длины и использовать различные машинные языки. Помимо разных операционных систем, компьютеры могут различаться используемыми стратегиями планирования и системами приоритетов. Хуже того, все системы могут различаться параметрами передачи данных. Это делает обработку ошибок и исключительных ситуаций (исключений) особенно трудной. Неоднородность системы может усугубляться и другими различиями. Например, может возникнуть необходимость организации совместного использования данных программами, написанными на различных языках или разработанных с использованием различных моделей ПО. Ведь общее системное решение может быть реализовано по частям, написанным на языках Fortran, С++ и J ava . Это вносит проблемы межъязыковой связи. И даже если распределенная или параллельная среда не является гетерогенной, остается проблема взаимодействия между несколькими процессами или потоками. Поскольку каждый процесс имеет собственное адресное пространство, то для совместного использования переменных, параметров и значений, возвращаемых функциями, необходимо применять технологию межпроцессного взаимодействия (interprocess communication — IPC), или МПВ-технологию. И хотя реализация МПВ-методов необязательно является самой трудной частью разработки системы ПО, тем не менее они образуют дополнительный уровень проектирования, тестирования и отладки в создании системы.