- •Введение
- •Этапы большого пути
- •Библиотеки для параллельного и распределенного программирования
- •Новый единый стандарт спецификаций unix
- •Для кого написана эта книга
- •Среды разработки
- •Дополнительный материал Диаграммы uml
- •Профили программы
- •Параграфы
- •Тестирование кода и его надежность
- •Ждем ваших отзывов!
- •Благодарности
- •Преимущества параллельного программирования
- •Что такое параллелизм
- •Два основных подхода к достижению параллельности
- •Преимущества параллельного программирования
- •Простейшая модель параллельного программирования (pram)
- •Простейшая классификация схем параллелизма
- •Преимущества распределенного программирования
- •Простейшие модели распределенного программирования
- •Мультиагентные распределенные системы
- •Минимальные требования
- •Декомпозиция
- •Синхронизация
- •Базовые уровни программного параллелизма
- •Параллелизм на уровне инструкций
- •Параллелизм на уровне подпрограмм
- •Параллелизм на уровне объектов
- •Параллелизм на уровне приложений
- •Стандарт mpi
- •Pvm: стандарт для кластерного программирования
- •Стандарт corba
- •Реализации библиотек на основе стандартов
- •Среды для параллельного и распределенного программирования
- •Проблемы параллельного и распределенного программирования
- •Кардинальное изменение парадигмы
- •Проблемы координации
- •Проблема №3: взаимоблокировка
- •Проблема №4: трудности организации связи
- •Отказы оборудования и поведение по
- •Негативные последствия излишнего параллелизма и распределения
- •Выбор архитектуры
- •Различные методы тестирования и отладки
- •Связь между параллельным и распределенным проектами
- •Определение процесса
- •Два вида процессов
- •Блок управления процессами
- •Анатомия процесса
- •Состояния процессов
- •Планирование процессов
- •Стратегия планирования
- •Использование утилиты ps
- •Установка и получение приоритета процесса
- •Переключение контекста
- •Создание процесса
- •Отношения между родительскими и сыновними процессами
- •Утилита pstree
- •Использование системной функции fork()
- •Использование семейства системных функций exec
- •Функции execl ()
- •Функции execv ()
- •Определение ограничений для функций exec ()
- •Чтение и установка переменных среды
- •Использование posix-функций для порождения процессов
- •Идентификация родительских и сыновних процессов с помощью функций управления процессами
- •Завершение процесса
- •Ресурсы процессов
- •§ 3.1 • Граф распределения ресурсов ,
- •Типы ресурсов
- •Posix-функции для установки ограничений доступа к ресурсам
- •Асинхронные и синхронные процессы
- •Функция wait ()
- •Разбиение программы на задачи
- •Линии видимого контура
- •Определение потока
- •Контекстные требования потока
- •Сравнение потоков и процессов
- •Различия между потоками и процессами
- •Потоки, управляющие другими потоками
- •Преимущества использования потоков
- •Переключение контекста при низкой (ограниченной) доступности процессора
- •Возможности повышения производительности приложения
- •Простая схема взаимодействия между параллельно выполняющимися потоками
- •Упрощение структуры программы
- •Недостатки использования потоков
- •Потоки могут легко разрушить адресное пространство процесса
- •Один поток может ликвидировать целую программу
- •Потоки не могут многократно использоваться другими программами
- •Анатомия потока
- •Атрибуты потока
- •Планирование потоков
- •Состояния потоков
- •Планирование потоков и область конкуренции
- •Стратегия планирования и приоритет
- •Изменение приоритета потоков
- •Ресурсы потоков
- •Модели создания и функционирования потоков
- •Модель делегирования
- •Модель с равноправными узлами
- •Модель конвейера
- •Модель «изготовитель-потребитель»
- •Модели spmd и мрмd для потоков
- •Введение в библиотеку Pthread
- •Анатомия простой многопоточной программы
- •Компиляция и компоновка многопоточных программ
- •Создание потоков
- •Получение идентификатора потока
- •Присоединение потоков
- •Создание открепленных потоков
- •Использование объекта атрибутов
- •Создание открепленных потоков с помощью объекта атрибутов
- •Управление потоками
- •Завершение потоков
- •Точки аннулирования потоков
- •Очистка перед завершением
- •Управление стеком потока
- •Установка атрибутов планирования и свойств потоков
- •Установка области конкуренции потока
- •Использование функции sysconf ()
- •Управление критическими разделами
- •Безопасность использования потоков и библиотек
- •Разбиение программы на несколько потоков
- •Использование модели делегирования
- •Использование модели сети с равноправными узлами
- •Использование модели конвейера
- •Использование модели «изготовитель-потребитель»
- •Создание многопоточных объектов
- •Синхронизация параллельно выполняемых задач
- •Координация порядка выполнения потоков
- •Взаимоотношения между синхронизируемыми задачами
- •Отношения типа старт-старт (cc)
- •Отношения типа финиш-старт (фс)
- •Отношения типа старт-финиш (сф)
- •Отношения типа финиш-финиш (фф)
- •Синхронизация доступа к данным
- •Модель ррам
- •Параллельный и исключающий доступ к памяти
- •Что такое семафоры
- •Операции по управлению семафором
- •Мьютексные семафоры
- •Использование мьютексного атрибутного объекта
- •Использование мьютексных семафоров для управления критическими разделами
- •Блокировки для чтения и записи
- •Использование блокировок чтения-записи для реализации стратегии доступа
- •Условные переменные
- •Использование условных переменных для управления отношениями синхронизации
- •Объектно-ориентированный подход к синхронизации
- •Классические модели параллелизма, поддерживаемые системой pvm
- •Выполнение pvm-программы в виде двоичного файла
- •Запуск pvm-программ c помощью pvm-консоли
- •Запуск pvm-программ c помощью xpvm
- •Требования к pvm-программам
- •Методы использования pvm-задач
- •§ 6.1. Обозначение сочетаний
- •6.3. Базовые меха н измы pvm 233
- •Базовые механизмы pvm
- •Функции управления процессами
- •6.3. Базовые меха н измы pvm 235
- •Упаковка и отправка сообщений
- •6.3. Базовые механизмы pvm 237
- •Доступ к стандартному входному потоку (stdin) и стандартному выходному потоку (stdout) со стороны pvm-задач
- •Получение доступа к стандартному выходному потоку (cout) из сыновней задачи
- •Обработка ошибок, исключительных ситуаций и надежность программного обеспечения
- •Надежность программного обеспечения
- •Отказы в программных и аппаратных компонентах
- •Определение дефектов в зависимости от спецификаций по
- •Обработка ошибок или обработка исключительных ситуаций?
- •Надежность по: простой план
- •План а: модель возобновления, план б: модель завершения
- •Использование объектов отображения для обработки ошибок
- •Классы исключений
- •Классы runtime__error
- •Классы logic_error
- •Выведение новых классов исключений
- •Защита классов исключений от исключительныхситуаций
- •Диаграммы событий, логические выражения и логические схемы
- •Распределенное объектно-ориентированное программирование
- •Декомпозиция задачи и инкапсуляция ее решения
- •Взаимодействие между распределенными объектами
- •Синхронизация взаимодействия локальных и удаленных объектов
- •Обработка ошибок и исключений в распределенной среде
- •Доступ к объектам из других адресных пространств
- •Брокеры объектных запросов (orb)
- •Язык описания интерфейсов (idl):более «пристальный» взгляд на corba-объекты
- •Анатомия базовой corba-программы потребителя
- •Анатомия базовой corba-программы изготовителя
- •Базовый npoeкт corba-приложения
- •Получение ior-ссылки для удаленных объектов
- •Служба имен
- •§ 8.1. Семантические сети
- •Использование службы имен и создание именных контекстов
- •Служба имен «потребитель-клиент»
- •Подробнее об объектных адаптерах
- •Хранилища реализаций и интерфейсов
- •Простые pacnpeделенные Web-службы, использующие corba-спецификацию
- •Маклерская служба
- •Парадигма «клиент-сервер»
- •Реализация моделей spmd и mpmd с помощью шаблонов и mpi-программирования
- •Декомпозиция работ для mpi-интерфейса
- •Дифференциация задач по рангу
- •Группирование задач по коммуникаторам
- •Анатомия mpi-задачи
- •Использование шаблонных функций для представления mpi-задач
- •Реализация шаблонов и модельБрмо (типы данных)
- •Использование полиморфизмадля реализации mpmd-модели
- •Введение mpmd-модели c помощью функций -объектов
- •Как упростить взаимодействие между mpi-задачами
- •Визуализация проектов параллельных и распределенных систем
- •Визуализация структур
- •Классы и объекты
- •Отображение информации об атрибутах и операциях класса
- •Организация атрибутов и операций
- •Шаблонные классы
- •Отношения между классами и объектами
- •Интерфейсные классы
- •Организация интерактивных объектов
- •Отображение параллельного поведения
- •Сотрудничество объектов
- •Процессы и потоки
- •Отображение нескольких потоков выполнения и взаимодействия между ними
- •Последовательность передачи сообщений между объектами
- •Деятельность объектов
- •Конечные автоматы
- •Параллельные подсостояния
- •Распределенные объекты
- •Визуализация всей системы
- •Визуализация развертывания систем
- •Архитектура системы
- •Проектирование компонентов для поддержки параллелизма
- •Как воспользоваться преимуществами интерфейсных классов
- •Подробнее об объектно-ориентированном взаимном исключении и интерфейсных классах
- •«Полуширокие» интерфейсы
- •Поддержка потокового представления
- •Перегрузка операторов "«" и "»" для pvm-потоков данных
- •Пользовательские классы, создаваемые для обработки pvm-потоков данных
- •Объектно-ориентированные каналы и fifo-очереди как базовые элементы низкого уровня
- •Связь каналов c iostream-объектами с помощью дескрипторов файлов
- •18 Cerr « «Ошибка при создании канала " « endl;
- •Доступ к анонимным каналам c использованием итератора ostream_iterator
- •Fifo-очереди (именованные каналы),
- •Интерфейсные fifo-классы
- •Каркасные классы
- •Реализация агентно-ориентированных архитектур
- •Что такое агенты
- •Агенты: исходное определение
- •Типы агентов
- •В чем состоит разница между объектами и агентами
- •Понятие об агентно-ориентированном программировании
- •§ 12:1 Дедукция, индукция и абдукция
- •Роль агентов в распределенном программировании
- •Агенты и параллельное программирование
- •Базовые компоненты агентов
- •Когнитивные структуры данных
- •Методы рассуждений
- •Типы данных предположений и структуры убеждений
- •Класс агента
- •Цикл активизации агента
- •Простая автономность
- •12.6. Резюме
- •Реализация технологии «классной доски» с использованием pvm-средств, потоков и компонентов
- •Модель «классной доски»
- •Методы структурирования «классной доски»
- •Анатомия источника знаний
- •Стратегии управления для «классной доски»
- •Реализация модели «классной доски» с помощью corba-объектов
- •Пример использования corba-объекта «классной доски»
- •Реализация интерфейсного класса black_board
- •Порождение источников знаний в конструкторе «классной доски»
- •Порождение источников знаний с помощью pvm-задач
- •Связь «классной доски» и источников знаний
- •Активизация источников знаний с помощью posix-функции spawn()
- •Реализация модели «классной доски» с помощью глобальных объектов
- •Активизация источников знаний с помощью потоков
- •Приложение a
- •Диаграммы классов и объектов
- •Диаграммы сотрудничества
- •Диаграммы последовательностей
- •A.2.3. Диаграммы видов деятельности
- •A.3. Диаграммы состояний
- •A.4. Диаграммы пакетов
- •Приложение б 26
Проблема №3: взаимоблокировка
Взаимоблокировка — это еще одна «ловушка», связанная с ожиданием. Для демонстрации взаимоблокировки предположим, что в нашей программе поддержки электронного банка три задачи работают не с одним, а с двумя счетами. Вспомним, что задача А получает запросы от задачи В на снятие денег со счета, а от задачи С — запросы на вложение денег на депозит. Задачи А, В и С могут выполняться параллельно. Однако задачи В и С могут обновлять одновременно только один счет. Задача А предоставляет доступ задач В и С к нужному счету по принципу «первым пришел — первым обслужен». Предположим также, что задача В имеет монопольный доступ к счету 1, а задача С — монопольный доступ к счету 2. При этом задаче В для выполнения соответствующей обработки также нужен доступ к счету 2 и задаче С — доступ к счету 1. Задача В удерживает счет 1, ожидая, пока задача С не освободит счет 2. Аналогично задача С удерживает счет 2, ожидая, пока задача В не освободит счет 1. Тем самым задачи В и С рискуют попасть в тупиковую ситуацию , которую в данном случае можно назвать взаимоблокировкой (deadlock). Ситуация взаимоблокировки между задачами В и С схематично показана на рис. 2.3.
Форма взаимоблокировки в данном случае объясняется наличием параллельно выполняемых задач, имеющих доступ к совместно используемым данным, которые им разрешено обновлять. Здесь возможна ситуация, когда каждая из задач будет ожидать до тех пор, пока другая не освободит доступ к общим данным (общими данными здесь являются счет 1 и счет 2). Обе задачи имеют доступ к обоим счетам. Может случиться так,
вместо получения доступа одной задачи к двум счетам, каждая задача получит доступ одному из счетов. Поскольку задача В не может освободить счет 1, пока не получит К туп к счету 2, а задача С не может освободить счет 2, пока не получит доступ к счету 1, программа обслуживания счетов электронного банка будет оставаться заблокированной. Обратите внимание на то, что задачи В и С могут ввести в состояние бесконечной отсрочки и другие задачи (если таковые имеются в системе). Если другие задачи ожидают получения доступа к счетам 1 или 2, а задачи В и С «скованы» взаимоблокировкой, то те другие задачи будут ожидать условия, которое никогда не выполнится. При координации параллельно выполняемых задач необходимо помнить, что взаимоблокировка и бесконечная отсрочка — это самые опасные преграды, которые нужно предусмотреть и избежать.
Проблема №4: трудности организации связи
Многие распространенные параллельные среды (например, кластеры) зачастую состоят из гетерогенных компьютерных сетей. Гетерогенные компьютерные сети— это системы, которые состоят из компьютеров различных типов, работающих в общем случае под управлением различных операционных систем и использующих различные сетевые протоколы. Их процессоры могут иметь различную архитектуру, обрабатывать слова различной длины и использовать различные машинные языки. Помимо разных операционных систем, компьютеры могут различаться используемыми стратегиями планирования и системами приоритетов. Хуже того, все системы могут различаться параметрами передачи данных. Это делает обработку ошибок и исключительных ситуаций (исключений) особенно трудной. Неоднородность системы может усугубляться и другими различиями. Например, может возникнуть необходимость организации совместного использования данных программами, написанными на различных языках или разработанных с использованием различных моделей ПО. Ведь общее системное решение может быть реализовано по частям, написанным на языках Fortran, С++ и J ava . Это вносит проблемы межъязыковой связи. И даже если распределенная или параллельная среда не является гетерогенной, остается проблема взаимодействия между несколькими процессами или потоками. Поскольку каждый процесс имеет собственное адресное пространство, то для совместного использования переменных, параметров и значений, возвращаемых функциями, необходимо применять технологию межпроцессного взаимодействия (interprocess communication — IPC), или МПВ-технологию. И хотя реализация МПВ-методов необязательно является самой трудной частью разработки системы ПО, тем не менее они образуют дополнительный уровень проектирования, тестирования и отладки в создании системы.
POSIX-спецификация поддерживает пять базовых механизмов, используемых для реализации взаимодействия между процессами:
• файлы со средствами блокировки и разблокировки;
• каналы (неименованные, именованные и FIFO-очереди);
• общая память и сообщения;
• сокеты;
• семафоры.
Каждый из этих механизмов имеет достоинства, недостатки, ловушки и тупики, которые проектировщики и разработчики ПО должны обязательно учитывать, если хотят создать надежную и эффективную связь между несколькими процессами. Организовать взаимодействие между несколькими потоками (которые иногда называются облегченными процессами) обычно проще, чем между процессами, так как потоки используют общее адресное пространство. Это означает, что каждый поток в программе может легко передавать параметры, принимать значения, возвращаемые функциями, и получать доступ к глобальным данным. Но если взаимодействие процессов или потоков не спроектировано должным образом, возникают такие проблемы, как взаимоблокировки, бесконечные отсрочки и другие ситуации «гонки» данных. Необходимо отметить, что перечисленные выше проблемы характерны как для распределенного, так и для параллельного программирования.
Несмотря на то что системы с исключительно параллельной обработкой отличаются от систем с исключительно распределенной обработкой, мы намеренно не проводили границу между проблемами координации в распределенных и параллельных системах. Частично мы можем объяснить это некоторым перекрытием существующих проблем, и частично тем, что некоторые решения проблем в одной области часто применимы к проблемам в другой. Но главная причина нашего «обобщенного» подхода состоит в том, что в последнее время гибридные (параллельно-распределенные) системы становятся нормой. Современное положение в параллельном способе обработке данных определяют кластеры и сетки. Причудливые кластерные конфигурации составляют из готовых продуктов. Такие архитектуры включают множество компьютеров со многими процессорами, а однопроцессорные системы уже уходят в прошлое. В будущем предполагается, что чисто распределенные системы будут встраиваться в виде компьютеров с несколькими процессорами. Это означает, что на практике проектировщик или разработчик ПО будет теперь все чаще сталкиваться с проблемами распределения и параллелизма. Вот потому-то мы и рассматриваем все эти проблемы в одном пространстве. В табл. 2.1 представлены комбинации параллельного и распределенного программирования с различными конфигурациями аппаратного обеспечения.
В табл. 2.1 обратите внимание на то, что существуют конфигурации, в которых параллелизм достигается за счет использования нескольких компьютеров. В этом случае подходит применение библиотеки PVM. И точно так же существуют конфигурации, в которых распределение может быть достигнуто лишь на одном компьютере за счет разбиения логики ПО на несколько процессов или потоков. Именно факт использования множества процессов или потоков говорит о том, что работа программы носит «распределенный» характер. Комбинации параллельного и распределенного программирования, представленные в табл. 2.1, подразумевают, что проблемы конфигурации, обычно присущие распределенному программированию, могут возникнуть в ситуациях, обусловленных параллельным программированием, и, наоборот, проблемы конфигурации, обычно связанные с параллельным программированием, могут возникнуть в ситуациях, обусловленных распределенным программированием.
Таблица2.1. Комбинации параллельного и распределенного программирования с различными конфигурациями аппаратного обеспечения
Независимо от используемой конфигурации аппаратных средств, существует два базовых механизма, обеспечивающих взаимодействие нескольких задач: общая память и средства передачи сообщений. Для эффективного использования механизма общей памяти программисту необходимо предусмотреть решение проблем «гонки» Данных, взаимоблокировки и бесконечных отсрочек. Схема передачи сообщений Должна предполагать возникновение таких «накладок», как прерывистые передачи, бессмысленные (искаженные), утерянные, ошибочные, слишком длинные, просроченные (с нарушением сроков), преждевременные сообщения и т.п. Эффективное использование обоих механизмов подробно рассматривается ниже в этой книге.