ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.04.2021
Просмотров: 268
Скачиваний: 1
188
Глава 5. Синхронизация параллельно выполняемых задач
5.1.4. Отношения типа старт-финиш (СФ)
Отношения типа
стартфиниш
можно считать обратным вариантом отношений
типа финишстарт. В отношениях синхронизации типа стартфиниш одна задача не
может начаться до тех пор, пока не завершится другая. Задача A не может начать вы
полнение до тех пор, пока задача B не финиширует или не завершит выполнение оп
ределенной операции. Если процесс A считывает данные из канала, связанного
с процессом B, то процесс B должен записать данные в канал, прежде чем процесс A
начнет считывать из него данные. Процесс B должен завершить по крайней мере одну
операцию, записав в канал один элемент, прежде чем начнет действовать процесс A.
Потоки, действующие по принципу “производительпотребитель”, — это еще один
пример взаимоотношений типа финишстарт. Потоки, обслуживающие сортировку
и поиск элементов в списке (см. рис. 5.1), также демонстрируют этот тип отношений.
Прежде чем начнут действовать потоки, реализующие поиск, должен завершить свою
работу поток сортировки. Во всех этих случаях один поток или процесс должен за
вершить свою операцию, прежде чем другой попытается выполнить свою задачу. Ес
ли работа потоков не будет скоординирована, глобальная цель потока, процесса или
приложения достигнута не будет или же будут получены ошибочные результаты.
Отношения типа стартфиниш обычно предполагают существование информаци
онной зависимости между задачами. При информационной зависимости для кор
ректной работы потоков или процессов необходимо обеспечить межпоточное или
межпроцессное взаимодействие. Например, поток поиска данных в списке сгенери
рует некорректные результаты, если не будет выполнена сортировка списка. И поток
“потребитель” не получит файлы для обработки, если поток“производитель” не под
готовит их для потребителя.
5.1.5. Отношения типа финиш-финиш (ФФ)
В отношениях синхронизации типа
финишфиниш
одна задача не может завер
шиться до тех пор, пока не завершится другая, т.е. задача A не может финишировать
до задачи B. Этот тип отношений можно применить к описанию отношений между
родительскими и сыновними процессами, которые рассматривались в главе 3. Роди
тельский процесс должен ожидать до тех пор, пока не завершатся все сыновние про
цессы, и только потом сможет завершиться сам. Если описанная последовательность
нарушится, и родительский процесс финиширует раньше своих потомков, то эти за
вершенные сыновние процессы перейдут в зомбированное состояние. Родительские
процессы не должны завершаться (выходить из системы в данном случае) до тех пор,
пока не выполнятся до конца их сыновние процессы. Для родительских процессов
это достигается за счет вызова функции
wait()
для каждого из своих сыновних про
цессов либо ожидания деблокировки (освобождения) мьютекса или условной пере
менной, что может быть осуществлено сыновними потоками. Еще одним примером
отношений типа финишфиниш может служить модель “управляющийрабочий”. За
дача управляющего потока — делегировать работу рабочим потокам. Для управляюще
го крайне нежелательно завершить работу раньше рабочих. В этом случае не были бы
обработаны новые запросы к системе, не имели работы существующие потоки и не
создавались новые. Если управляющий поток является основным потоком процесса,
и он завершается, то процесс должен завершиться вместе со всеми рабочими потока
5.2. Синхронизация доступа к данным
189
ми. Если в модели равноправных потоков поток A динамически создает объект, пере
даваемый потоку B, и поток A затем завершается, то вместе с ним разрушается и соз
данный им объект. Если это произойдет до того, как поток B получит возможность
использовать этот объект, возникнет ошибка сегментации или нарушится доступ
к данным. Чтобы предотвратить возникновение этого типа ошибок, завершение по
токов синхронизируется с помощью функции
pthread_join()
. Обращение к этой
функции заставляет вызывающий поток ожидать до тех пор, пока не финиширует за
данный поток. Таким образом и создается синхронизация типа финишфиниш.
5.2. Синхронизация доступа к данным
Существует разница между данными, разделяемыми между процессами, и данны
ми, разделяемыми между потоками. Потоки совместно используют одно и то же ад
ресное пространство, в то время как процессы имеют отдельные адресные простран
ства. Если существуют два процесса A и B, то данные, объявленные в процессе A, не
доступны процессу B, и наоборот. Следовательно, один из методов, используемых
процессами для разделения данных, состоит в создании блока памяти, отображаемого
затем на адресное пространство процессов, которые должны разделять память. Дру
гой подход предполагает создание блока памяти, существующего вне адресного про
странства обоих процессов. К типам механизмов межпроцессного взаимодействия
(МПВ) относятся каналы, файлы и передача сообщений.
Именно блок памяти, разделяемый между потоками внутри одного и того же ад
ресного пространства, и блок памяти, разделяемый между процессами вне обоих ад
ресных пространств, требует синхронизации данных. Память, разделяемая между по
токами и процессами, показана на рис. 5.3.
Синхронизация данных необходима для управления состоянием “гонок”, а также
для того, чтобы позволить параллельным потокам или процессам безопасно получить
доступ к блоку памяти. Синхронизация данных позволяет управлять считыванием
и модификацией данных в блоке памяти. В многопоточной среде параллельный дос
туп к общей памяти, глобальным переменным и файлам обязательно должен быть
синхронизирован. Что касается программного кода задачи, то синхронизация данных
необходима в тех его блоках, где делается попытка получить доступ к блоку памяти,
глобальным переменным или файлам, разделяемым с другими параллельно выпол
няемыми процессами или потоками. Такие блоки кода называются
критическими раз
делами
. В качестве критического раздела может выступать любой блок кода, который
изменяет позицию файлового указателя, записывает данные в файл, закрывает файл
и считывает или устанавливает глобальные переменные либо структуры данных. Вы
деление таких задач, которые выполняют чтение или запись данных, является одним
из этапов управления параллельным доступом к совместно используемой памяти.
5.2.1. Модель
PRAM
Модель PRAM (Parallel RandomAccess Machine — машина с параллельным произ
вольным доступом) — это упрощенная модель с
N
процессорами, обозначаемыми P
1
,
P
2
, P
3
, ... P
n
, которые разделяют одну глобальную память. Все процессоры одновре
менно получают доступ для чтения и записи к совместно используемой глобальной
190
Глава 5. Синхронизация параллельно выполняемых задач
памяти. Каждый из этих теоретических процессоров может получить доступ к разде
ляемой глобальной памяти в течение одного
непрерываемого
интервала времени. Мо
дель PRAM включает алгоритмы параллельного, а также исключающего чтения и за
писи. Алгоритмы параллельного чтения позволяют нескольким процессорам одно
временно использовать одну и ту же область памяти без какого бы то ни было
искажения данных. Алгоритмы параллельной записи позволяют нескольким процес
сорам записывать данные в разделяемую область памяти. Алгоритмы исключающего
чтения используются для получения гарантии того, что никакие два процессора нико
гда не будут считывать информацию из одной и той же области памяти одновремен
но. Алгоритмы исключающей записи гарантируют, что никакие два процессора нико
гда не будут записывать данные в одну и ту же область памяти одновременно. Модель
PRAM можно использовать для определения характера параллельного доступа к об
щей памяти со стороны нескольких задач.
Рис. 5.3.
Память, разделяемая между потоками и процессами
5.2. Синхронизация доступа к данным
191
5.2.1.1. Параллельный и исключающий доступ к памяти
Алгоритмы параллельного и исключающего чтения и записи можно скомбиниро
вать и получить следующие типы объединенных алгоритмов, которые можно реали
зовать для организации доступа к данным:
•
исключающее чтение и исключающая запись (
e
xclusive
r
ead and
e
xclusive
w
rite — EREW);
•
параллельное чтение и исключающая запись (
c
oncurrent
r
ead and
e
xclusive
w
rite — CREW);
•
исключающее чтение и параллельная запись (
e
xclusive
r
ead and
c
oncurrent
w
rite — ERCW);
•
параллельное чтение и параллельная запись (
c
oncurrent
r
ead and
c
oncurrent
w
rite — CRCW).
Эти алгоритмы можно рассматривать как стратегии доступа, реализуемые задача
ми, которые совместно используют данные (рис. 5.4). Алгоритм EREW подразумевает
последовательный доступ к разделяемой памяти, т.е. к общей памяти в любой момент
времени может получить доступ только одна задача. Примером стратегии доступа
EREW может служить вариант реализации модели потоков “производитель
потребитель”, рассмотренный в главе 4. Доступ к очереди, содержащей имена фай
лов, может быть ограничен исключающей записью “изготовителя” и исключающим
чтением “потребителя”. В любой момент времени доступ к очереди может быть раз
решен только для одной задачи. Стратегия CREW позволяет множественный доступ
для чтения общей памяти и исключающий доступ для записи в нее данных. Это озна
чает отсутствие ограничений на количество задач, которые могут одновременно чи
тать разделяемую память, но записывать в нее данные может только одна задача. При
этом параллельное чтение может происходить одновременно с записью данных в об
щую память. При использовании этой стратегии доступа все читающие задачи могут
прочитать различные значения, поскольку во время чтения значения из общей памя
ти записывающая задача может его модифицировать. Стратегия доступа ERCW — это
прямая противоположность стратегии CREW. При использовании стратегии ERCW
разрешены параллельные записи в общую память, но лишь одна задача может читать
ее в любой момент времени. Стратегия доступа CRCW позволяет множеству задач вы
полнять параллельное чтение и запись.
Для этих четырех типов алгоритмов требуются различные уровни и типы синхро
низации. Их диапазон довольно широк: от стратегии доступа, реализация которой
требует минимальной синхронизации, до стратегии доступа, реализация которой
требует максимальной синхронизации. Наша задача — реализовать эти стратегии,
поддерживая целостность данных и удовлетворительную производительность систе
мы. EREW — самая простая для реализации стратегия, поскольку она предполагает, по
сути, только последовательную обработку. На первый взгляд самой простой может
показаться стратегия CRCW, но она таит в себе массу трудностей. А ведь это только
кажется, что если к памяти можно получить доступ без ограничений, то в ней и речь
не идет о какой бы то ни было стратегии. Все как раз наоборот: CRCW — самая труд
ная для реализации стратегия, которая требует максимальной синхронизации.
192
Глава 5. Синхронизация параллельно выполняемых задач
Чтение
Разделяемая
память
Поток В
Запись
Чтение
Поток А
Разделяемая
память
Поток А
Поток В
Запись
Разделяемая
память
Поток А
Поток В
Запись
Чтение
Поток D
Запись
Чтение
Разделяемая
память
Поток А
Поток B
Запись
Чтение
Поток D
Запись
Чтение
Разделяемая
память
Поток А
Поток B
Запись
Чтение
Поток С
Поток D
Запись
Чтение
блокируется
EREW (исключающее чтение и исключающая запись)
ERCW (исключающее чтение и параллельная запись)
CREW (параллельное чтение и исключающая запись)
CRCW (параллельное чтение и параллельная запись)
Поток С
Поток С
Рис. 5.4.
Стратегии доступа
EREW
,
CREW
,
ERCW
и
CRCW