Параллельное и распределенное программирование на С++ - Хьюз Камерон

Координация порядка выполнения потоков

Предположим, у нас есть три параллельно выполняющихся потока — А, В и С. Все они участвуют в обработке списка. Список необходимо отсортировать, выполнить в нем операции поиска и вывода результатов. Каждому потоку назначается отдельная задача. Так, поток А должен отобразить результаты поиска, В — отсортировать список, а С — провести поиск. Сначала список необходимо отсортировать, затем выполнить несколько параллельных операций поиска, а уж потом отобразить результаты. Если задачи, выполняемые потоками, не синхронизировать надлежащим образом, то поток А может попытаться отобразить еще не сгенерированные результаты, что нарушит постусловие, или выхо д ное условие (postcondition), процесса. Предусловием, или вхо д ным условием (precondition), з д есь является необходимость получения отсортированно г о списка до выполнения в нем поиска. Поиск в неотсортированном списке может дать неверные результаты. Поэтому для этих трех потоков необходимо обеспечить синхронизацию задач, которая приводит в исполнение постусловия и предусловия ло г ических процессов. UML-диаграмма видов деятельности для этого процесса представлена на рис. 5 .1.

Сначала поток В должен отсортировать список, затем эстафета управления передается «мно г оканальному» поиску, порождаемому потоком С. И только после завершения поисковых работ по всем направлениям поток А отображает результаты поиска.

Взаимоотношения между синхронизируемыми задачами

Существует четыре основных типа отношений синхронизации между любыми двумя потоками в одном процессе или между любыми двумя процессами в одном приложении: старт-старт (CC), финиш-старт (ФС), старт-финиш (СФ) и финиш-финиш (ФФ). С помощью этих основных типов отношений можно охарактеризовать координацию задач между потоками и процессами. UML-диаграмма видов деятельности для каждого типа отношений синхронизации показана на рис. 5.2.

Рис. 5.1. Диаграмма видов деятельности для задач сортировки списка, поиска и отображения результатов поиска

Отношения типа старт-старт (CC)

В отношениях синхронизации типа старт-старт одна задача не может начаться до тех пор, пока не начнется другая. Одна задача может начаться раньше другой, нo не позже. Предположим, у нас есть программа, которая реализует инкарнацию (воплощение). Инкарнация «материализуется» в виде говорящей головы, созданной, разумеется, компьютерной программой. Инкарнация обеспечивает своего рода «одушевление» программ. Программа, которая реализует «одушевление», имеет несколько потоков. Здесь нас в первую очередь интересует поток А, который «отвечает» за анимацию результата, и поток В, который управляет звуком, или голосом, говорящей головы. Мы хотим создать иллюзию синхронизации звука и движений рта. В идеале они должны происходить абсолютно одновременно. При наличии нескольких процессоров оба потока могут начинаться одновременно. Эти потоки связаны отношением типа старт - старт. В соответствии с условиями временной синхронизации допускается, чтобы поток А начинался немного раньше потока В (именно немного — иначе будет нарушена иллюзия одновременности), но поток В не может начаться раньше потока А. Голос должен ожидать анимацию, а не наоборот. Совершенно нежелательно услышать голос до того, как зашевелятся губы (если это не синхронное озвучивание).

Рис. 5.2. Возможные отношения синхронизации между задачами А и В

Отношения типа финиш-старт (ФС)

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

Отношения типа старт-финиш (СФ)

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

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

Отношения типа финиш-финиш (ФФ)

В отношениях синхронизации типа финиш-финиш одна за д ача не может завершиться до тех пор, пока не завершится другая, т.е. задача А не может финишировать до задачи В. Этот тип отношений можно применить к описанию отношений между родительскими и сыновними процессами, которые рассматривались в главе 3. Родительский процесс должен ожидать до тех пор, пока не завершатся все сыновние процессы, и только потом сможет завершиться сам. Если описанная последовательность нарушится, и родительский процесс финиширует раньше своих потомков, то эти завершенные сыновние процессы перейдут в зомбированное состояние. Родительские процессы не должны завершаться (выходить из системы в данном случае) до тех пор, пока не выполнятся до конца их сыновние процессы. Для родительских процессов это достигается за счет вызова функции wait() для каждого из своих сыновних процессов либо ожидания деблокировки (освобождения) мьютекса или условной переменной, что может быть осуществлено сыновними потоками. Еще одним примером отношений типа финиш-финиш может служить модель «управляющий-рабочий». Задача управляющего потока — делегировать работу рабочим потокам. Для управляющего крайне нежелательно завершить работу раньше рабочих. В этом случае не были бы обработаны новые запросы к системе, не имели работы существующие потоки и не создавались новые. Если управляющий поток является основным потоком процесса, и он завершается, то процесс должен завершиться вместе со всеми рабочими потоками. Если в модели равноправных потоков поток А динамически создает объект, передаваемый потоку В, и поток А затем завершается, то вместе с ним разрушается и созданный им объект. Если это произойдет до того, как поток В получит возможность использовать этот объект, возникнет ошибка сегментации или нарушится доступ к данным Чтобы предотвратить возникновение этого типа ошибок, завершение потоков синхронизируется с помощью функции pthread_join(). Обращение к этой функции заставляет вызывающий поток ожидать до тех пор, пока не финиширует заданный поток. Таким образом и создается синхронизация типа финиш-финиш.