Файл: syncro.pdf

СИНХРОНИЗАЦИЯ

ПАРАЛЛЕЛЬНО

ВЫПОЛНЯЕМЫХ

ЗАДАЧ

В этой главе...

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

5.2. Синхронизация доступа к данным

5.3. Что такое семафоры

5.4. Объектно-ориентированный подход к синхронизации

5.5. Резюме

184

Глава 5. Синхронизация параллельно выполняемых задач

5

Отношение этих механизмов ко времени требует тщательного изучения. 

<

...

>

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

класса входных сигналов,

получение которого

ожидается статистически...

— Ноберт Винер (

Norbert Wiener

)

, 

Кибернетика

о всех компьютерных системах ресурсы ограничены. Ведь любой объем памя
ти конечен, как и количество устройств вводавывода, портов, аппаратных
прерываний и процессоров. Если в среде ограниченных аппаратных ресурсов

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

ресурсами данных

 подразумеваются объекты, системные данные

В

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

185

(например, переменные сред

ы

), файлы, глобально определенные переменные и струк

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

Синхронизация также необходима для координации порядка выполнения парал

лельных задач. Примером может служить модель “изготовительпотребитель”, кото
рая рассмотрена в главе 4. “Изготовитель” обязательно начинает выполняться до
“потребителя”, но не обязательно завершается до него. Подобные задачи нуждаются
в синхронизации. Синхронизация данных (

синхронизация доступа к данным

) и задач

(

синхронизация последовательностей инструкций

) — два типа синхронизации, которые

необходимо обеспечить при выполнении нескольких параллельных задач.

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

Предположим, у нас есть три параллельно выполняющихся потока — A, B и C.

Все они участвуют в обработке списка. Список необходимо отсортировать, выпол
нить в нем операции поиска и вывода результатов. Каждому потоку назначается от
дельная задача. Так, поток A должен отобразить результаты поиска, B — отсортиро
вать список, а C — провести поиск. Сначала список необходимо отсортировать, за
тем выполнить несколько параллельных операций поиска, а уж потом отобразить
результаты. Если задачи, выполняемые потоками, не синхронизировать надлежа
щим образом, то поток A может попытаться отобразить еще не сгенерированные
результаты, что нарушит 

постусловие

, или выходное условие (postcondition), про

цесса. 

Предусловием

, или входным условием (precondition), здесь является необхо

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

Сначала поток B должен отсортировать список, затем эстафета управления переда

ется “многоканальному” поиску, порождаемому потоком C. И только после завершения
поисковых работ по всем направлениям поток A отображает результаты поиска.

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

задачами

Существует четыре основных типа отношений синхронизации между любыми

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

186

Глава 5. Синхронизация параллельно выполняемых задач

Поток A

Поток B

Поток C

Поиск значения 1

Сортировка

списка

Отображение

результатов

поиска 

Поиск значения 2

Поиск значения n

...

[Отсортированный

список]

[Неотсортированный

список]

Рис. 5.1.

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

результатов поиска

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

В отношениях синхронизации типа 

стартстарт

 одна задача не может начаться до

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

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

187

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

о

й синхронизации допускается, чтобы

поток A начинался немного раньше потока B (именно немного — иначе будет нарушена
иллюзия одновременности), но поток B не может начаться раньше потока A. Голос
должен ожидать анимацию, а не наоборот. Совершенно нежелательно услышать голос
до того, как зашевелятся губы (если это не синхронное озвучивание).

<< сигнал >>

Поток A

Поток B

Поток A

Поток B

<< сигнал >>

Поток A

Поток B

<< сигнал >>

Поток A 

заблокирован

Поток A

Поток B

<< сигнал >>

СТАРТ-СТАРТ

ФИНИШ-ФИНИШ

ФИНИШ-СТАРТ

СТАРТ-ФИНИШ

Поток B заблокирован

Поток A 

заблокирован

Поток B заблокирован

Рис. 5.2.

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

A 

и 

B

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

В отношениях синхронизации типа 

финишстарт

 задача A не может завершиться

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