Такая приостановка (прерывание) процессов в критических интервалах времени до выполнения требумых условий их продолжения называется синхронизацией асинхронных параллельных вычислительных процессов.

Для синхронизации применяются специальные синхропримитивы:

1)  Семафоры;

2)  Мониторы;

3)  Сентинелы;

4)  Условные критические интервалы;

5)  Управляющие выражения, которые вводятся в алгоритмические языки программирования, например оператор “Событие” в PL/1, операторы Delay (задержка) и Cond (Continue) (продолжение) в параллельном языке Паскаль. Исполнение синхропримитивов поддерживается специальным программным модулем ядра МОС – монитором синхронизации либо организуется устройством управления процессора, как в отечественной суперЭВМ “Эльбрус”.

Рассмотрим основные принципы организации синхронизации на примере семафоров. Метод семафоров предложен американским ученым Дейкстра в 1965 году, но подобный механизм синхронизации применялся ещё раньше в отечественных ЭВМ: “БЭСМ6” и “Эльбрус1”.

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

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

НЕ нашли? Не то? Что вы ищете?

Над целочисленной переменной S переменной семафора определены 2 операции:

–  P(S) – Wait (S): ждать,

–  V(S) – Signal(S): сигнал.

P(S) – операция закрытия семафора.

V(S) – операция его открытия.

В результате операции P(S) значение семафора S уменьшится на единицу:

S¢ считается значением аргумента следущего предиката условного перехода:

–  Если новое значение S¢³0, то семафор открыт, и процесс, обратившийся в его ячейку, продолжает работу; флаг принудительно устанавливается в положение «открыт»;

–  Если S¢<0, семафор закрыт, и процесс приостанавливается (прерывается, блокируется по семафору S), а его имя заносится в очередь на ожидание разблокирования, идентифицированную именем семафора S; флаг – в положении “закрыт”.

Операция V(S) открытия семафора и разблокирования процесса всегда выполняется другим незаблокированным процессом. По операции V(S) значение семафора S увеличивается на единицу:

и затем проверяется следующее логическое условие:

–  Если S¢£0, то семафор S открывается, и один из ожидающих в очереди процессов разблокируется в соответствии с дисциплиной обслуживания очереди либо по FIFO, либо по LIFO, либо по приоритету;

–  Если S¢>0, то никаких действий не выполняется, так как при этом старое значение семафора было S³0, и поэтому заблокированные по этому семафору процессы отсутствуют, т. е. признак семафора был, и остается “открыт” или обязательно “открывается”.

Рассмотрим два харакиерных примера введения операций над семафорами в программы процессов.

3.3.3.1. Задание отношений

предшествования.

Отношения предшествования между параллельными процессами можно отобразить на специальном графе, вершины которого соответствуют процессам, направленные дуги показывают фиксированную последовательность их выполнения, а расположение вершин по уровням (ярусам) дополнительно фиксирует требуемую их последовательность.

 

Дугам присваиваются имена соответствующих семафоров. В данном примере необходимо вводить 3 семафора: S13, S23, S34. Процессы Р1 и Р2 не блокируются. Процесс Р3 должен блокироваться до тех пор, пока оба входных процесса и Р1 и Р2 не закончатся и не откроют оба семафора S13 и S23. Процесс Р4 заблокирован до окончания процесса Р3 и открытия семафора S34. В соответствии с этим графом операции Р и V расставляются в начале и в конце участков программ: П1, П2, П3, П4 этих процессов.

Р1 : П1; V(S13)

P2 : П2; V(S23)

P3 : P(S13), P(S23); П3; V(S34)

P4 : P(S34); П4.

Правильность срабатывания семафоров зависит от выбора начальных их целочисленных значений. В данном случае целесообразно выбрать нулевые начальные значения: S13(0)= S23(0)= S34(0)=0. Тогда, в случае если процессы Р3 и Р4 войдут в критический интервал раньше своих предшественников Р1 и Р2, они не начнутся из-за признаков закрытых семафоров или будут прерваны и заблокированы начальными операциями Р(S):

Эти три семафора закроются, если они оказались открытыми, а имена процессов будут занесены в очереди ожидания разблокирования: Р3 – в две очереди под именами S13 и S23, Р4 – в очередь под именем S34. В дальнейшем процессы Р3 и Р4 не будут многократно повторять операции Р(S) и попыток начать свою работу, пока их не разблокируют другие процессы. Они прерываются и освобождают процессоры для других процессов. Позже завершившиеся процессы Р1 и Р2 выполняют свои заключительные операции V(S):

открывают оба семафора S13 и S23 и разблокируют процесс Р3, а тот затем по окончании и выполнении операции V(S34):

открывает семафор S34 и разблокирует процесс Р4.

Если порядок входа процессов в критический интервал соответствует графу отношений предшествования, то при выбранных начальных условиях вначале будут выполнены операции:

по результатам которых открыты S13 и

S23 и никаких действий не выполняется,

но они своими значениями подготавливают необходимые условия для окончательного открытия семафоров S13 и S23 следующими операциями Р(S):

Семафоры S13 и S23 окончательно открываются.

Аналогично по окончании процесса Р3 операция

своим результатом подготавливает условие для окончательного открытия семафора S34, а следующая операция

окончательно открывает семафор S34.

3.3.3.2. Взаимоисключение процессов.

Если какой-либо ресурс занят процессом, то новый процесс, затребовавший этот же ресурс, должен быть заблокирован до окончания работы с ресурсом первого процесса, а разблокируется первым по его финишной операции V(S), вносимой в конце его процедуры работы с ресурсом. Исключаются непроизводительные потери машинного времени на выполнение вторым процессом многократных попыток завладеть занятым ресурсом, и тем самым освобождается один из процессоров для обслуживания других программ.

Характерный пример – организация работы нескольких процессов с одним «почтовым ящиком» (буфером обмена информацией). Рассмотрим простой случай, когда с обменным буфером работают только два процесса, каждый из которых в одном критическом интервале является поставщиком сообщения другому процессу, а в другом интервале может стать потребителем чужого сообщения. В первом варианте взаимодействия процесс называют передатчиком (писателем), а во втором – приемником (читателем). На жаргоне системных программистов эта задача сх синхронизации называется проблемой «читателей и писателей». Пусть в данный момент времени процесс А – писатель, а процесс В – читатель. «Почтовый ящик» имеет ограниченную ёмкость на S10 слов сообщения. Условная схема «почтового ящика»:

 

Для синхронизации работы процессов А и В вводят три семафора, целочисленные значения которых соответствуют:

S1 – число свободных мест в буфере : S1£S10;

S2 – число накопленных в буфере сообщений;

S3 – двоичный семафор (0 или 1) для взаимоисключения двух процессов.

Очевидно, что S1+ S2= S10.

Выберем следующие начальные значения семафоров:

Чтобы записать сообщение в буфер процесс-писатель А должен выполнить следующую последовательность операций:

Р(S1), Р(S3); записать сообщение в буфер; V(S2), V(S3).

Если буфер свободен, то

Семафоры процессу А открыты. Во время его работы с буфером, до выполнения заключительной операции V(S3), значение семафора S¢3=0 и поэтому он закрыт для других процессов как по признаку “закрыт”, так и по их окончательной операции . По окончании работы с буфером процесс А выполняет операцию открывает S3 по признаку «открыт» и подготавливает условие для возможного открытия семафора S3 другим процессом по операции Р(S3), а также операцией V(S2)=0+1=1 отмечает, что в буфере на одно сообщение стало больше, и подготавливает условия для открытия S2.

Процесс-читатель B для считывания сообщение из буфера; V(S1), V(S3).

Если в буфере есть сообщение для процесса В (S2>0) и с буфером не работает другой процесс (по признаку S3=1), то по входным операциям:

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4