17 Синхронизация
параллельных вычислительных процессов. Пример алгоритма USER-MAKER с
буфером на одну запись.
Для процессов,
совместно выполняющих общую работу, недостаточно, что они взаимно исключают
друг друга при работе с разделяемыми переменными, им необходимо еще и
передавать друг другу информацию. Минимальной единицей передаваемой информации
может быть простой временной сигнал. В этом случае действует следующее правило:
процессу предоставляется возможность ждать, пока другой не сообщит о
"свершении" определенного события.
В качестве примера возьмем пару
процессов: Pr1 - производитель; Pr2 - потребитель. Пусть Pr1 создает записи по
одной за кt, а Pr2 использует их по одной за кt.
Произведенная,
но еще не затребованная запись помещается в буфер размером в одну запись.
Процессы должны быть синхронизированы так, чтобы между любыми двумя
последовательными записями в буфер, выполнялось в точности одно чтение и
наоборот.
Pr1 -пишет
i-ую (первую запись) в буфер и совершает событие - НАЧАЛО - это событие
позволяет потребителю начать обработку записи.
Pr2 - читает
i-ую запись из буфера и совершает событие - КОНЕЦ - это позволяет производителю
(Pr1) записать в буфер i+1 запись.
Специально
предусматривать взаимное исключение при доступе к буферу нет необходимости,
т.к. в данном случае оно обеспечивается синхронизацией. Итак - семафор может
быть синхронизатором, координирующим производство и потребление ресурсов.
Процесс, потребляя ресурс, выполняет P-операцию над связанным с ресурсом
семафором (т.е. Р(S)), что означает изменение значения S в меньшую сторону.
Процесс производит ресурс, выполняя V(S)- операцию над тем же семафором.
Алгоритм "Производитель-Потребитель" с буфером
на одну запись
Введем переменные (семафоры):
ПУСТО = 1 - сигнал для производителя "поместить в буфер
запись"
ПОЛНО = 1 - сигнал для потребителя "читать запись"
|
ПУСТО
|
ПОЛНО
|
Состояния
|
|
0
|
0
|
Какой-то процесс находится в CS
|
|
0
|
1
|
Потребитель может войти в CS, буфер полон
|
|
1
|
0
|
Производитель может войти в CS, буфер пуст
|
|
1
|
1
|
Не определено
|
Описание (определение) процессов
"Производитель-Потребитель" с буфером на одну запись
|
Pr1
(производитель)
DO (TRUE)
Подготовить «ЗАПИСЬ»
P(ПУСТО)
(ждать, пока ПУСТО станет=1)
Запись в буфер
V(ПОЛНО)
OD
|
Pr2
(потребитель)
DO (TRUE)
P(ПОЛНО)
(ждать, пока ПОЛНО станет=1)
Читать из буфера
V(ПУСТО)
Использовать «ЗАПИСЬ»
OD(TRUE)
|
Алгоритм исполнения процессов
"Производитель-Потребитель" с буфером на одну запись:
GLB буфер (глобальная переменная)
Semaphore ПОЛНО, ПУСТО
ПОЛНО = 0
ПУСТО = 1
CO BEGIN (Corporation Begin)
CO{
Вызвать "Производитель";
Вызвать "Потребитель"
СО}
COEND
Временная диаграмма синхронизации
процессов Производитель - Потребитель" с буфером на одну запись.
