В ряде случаев бывает необходимо, чтобы параллельные процессы обменивались информацией между собой, передавая друг другу данные и сообщая о событиях. Не исключены ситуации, когда 2 и более процесса обращаются к 1 ресурсу и необходимо установить порядок использования ресурса. Так возникает задача синхронизации.
Разделяемый ресурс – ресурс, доступный всем взаимодействующим процессам. (аппарат. обеспечение – принтеры, каналы связи, дисковые накопители; программное обеспечение – модули, библиотеки; информационное обеспечение - БД).
Критическая секция – участок программы, в которой производится обращение к разделяемому ресурсу. Дисциплина доступа задается так, что в каждый момент времени в критической секции может находиться не более 1 выполняющегося процесса – механизм взаимного исключения.
«Гонки» - это ситуация, при которой несколько процессов одновременно получают доступ к общему ресурсу. Результат непредсказуем и определяется соотношением скоростей выполнения процессов.
Блокировка – соответствует ситуации, когда группа процессов не может продолжать выполнение, ожидая сообщения об освобождении критической секции. Поскольку критическая секция в данный момент пуста, сообщение не поступит никогда.
Ситуация отталкивания – процессы заняты только тем, что пересылают друг другу сообщения об освобождении критической секции, но при этом не продолжает выполнение.
Барьер – способ координации выполнения нескольких процессов, при котором каждый из них должен достигнуть некоторой заданной программной точки прежде чем всем процессам было позволено продолжать выполнение.
Семафор Дейкстра – механизм управления доступом к общему ресурсу и предотвращения блокировок и отталкивания. Механизм семафора Дейкстра включает в себя переменную особого типа, семафор, и 2 операции P и V. Аргументом этих операций является переменная типа семафор. Состояние семафора представляется целым неотрицательным числом. Состояние 0 и 1 – бинарный семафор. Выполнение операций P и V не может быть прервано ни на какой фазе, так гарантируется целостность состояния семафора.
Операция Р:
1. если значение сем. не 0, то оно уменьшается на 1.
2. если состояние сем.=0, то операция Р не завершается до тех пор, пока какой-либо другой процесс не увеличит значение семафора с помощью операции V. После чего операция Р продолжается.
Операция V: увеличение значения семафора на1. Оп. Р выполняется перед входом в критическую секцию, оп. V – при выходе. Р всегда раньше V.
6. Параллельная форма алгоритма. Ярус, высота и ширина параллельной формы алгоритма. Максимальная параллельная форма. Схема сдваивания.
Пусть операция алгоритмов разбита на группы, упорядоченные так, что каждая операция любой группы зависит от начальных данных алгоритма, либо от результатов выполнения операций, находящихся в предыдущих группах. Представление алгоритма в подобной форме называется параллельной формой алгоритма. Каждая группа операций называется ярусом параллельной формы. Число групп называется высотой параллельной формы, а максимальное число операций в ярусе – шириной параллельной формы.
Если известна параллельная форма алгоритма, то сам алгоритм можно реализовать на параллельной вычислительной системе по шагам, последовательно ярус за ярусом.
Упрощающее предположение:
1.количество процессов в принципе не ограничено
2.коммуникационная сеть организована таким образом, что алгоритм может быть выполнен за время пропорциональное высоте параллельной формы.
Для одной и той же задачи можно получить несколько параллельных форм, которые различаются как шириной, так и высотой, поскольку время выполнения алгоритма пропорционально высоте параллельной формы, особое значение приобретает форма минимальной высоты. Такие формы называют максимальными формами, а их высота называется высотой алгоритма.
Пример. (а1а2+а3а4)(а5а6+а7а8)
Данные а1 а2 а3 а4 а5 а6 а7 а8
Ярус 1 а1а2 а3а4 а5а6 а7а8
Ярус 2 а1а2+а3а4 а5а6+аа7а8
Ярус 3 (а1а2+а3а4)(а5а6+а7а8)
Высота = 3, ширина = 4.
Это максимальная форма для данной задачи. Плоха форма тем, что все 4 процессора задействованы только на первом ярусе. Начиная со второго яруса процессоры постепенно освобождаются и простаиваются.
Поставим задачу разработки формы, в которой процессоры будут загружены более равномерно.
Данные а1 а2 а3 а4 а5 а6 а7 а8
Ярус 1 а1а2 а3а4
Ярус 2 а5а6 а7а8
Ярус 3 а1а2+а3а4 а5а6+аа7а8
Ярус 4 (а1а2+а3а4)(а5а6+а7а8)
Эта форма хороша тем, что для ее реализации потребуется всего 2 процессора, оба из которых, за исключением последнего яруса, будут загружены.
Данные а1 а2 а3 а4 а5 а6 а7 а8
Ярус 1 а1а2 а3а4
Ярус 2 а1а2+а3а4 а5а6
Ярус 3 а7а8
Ярус 4 а5а6+а7а8
Ярус 5 (а1а2+а3а4)(а5а6+а7а8)
Эта форма наименее удачна, поскольку высота у нее максимальна из 3-х рассмотренных примеров, а процессоры загружены не равномерно.
В общем случае построение параллельных форм с заданными свойствами являются не простой задачей.
Схема сдваивания.
Требуется вычислить:
Данные а1 а2 а3 а4 а5 а6 а7 а8
Ярус 1 а1а2
Ярус 2 (а1а2)*а3
Ярус 3 (а1а2а3)*а4
…………………………………..
Ярус 7 (а1а2а3а4а5а6а7)*а8
Схема исключительно не эффективна. Более эффективен вариант реализованный по так называемой схеме сдваивания.
Данные а1 а2 а3 а4 а5 а6 а7 а8
Ярус 1 а1а2 а3а4 а5а6 а7а8
Ярус 2 (а1а2)(а3а4) (а5а6)(а7а8)
Ярус 3 (а1а2а3а4)(а5а6а7а8)
Для выполнения каждой операции из m-го яруса берутся два результата операций (m-1) яруса, n – количество входных данных.
Преимущество: высота и ширена формы предсказуемы. Высота , -округление до ближайшего целого. Ширина .
При использовании схемы сдваивания загруженность процессоров как правило уменьшается от яруса к ярусу.
, 
-округление до ближайшего целого. Ширина 
.