Конспект установочных лекций по комплексному курсу Информатика, Теория информации



Общие программные переменные - часть 2


Условие Е называется стражем, а оператор S - критической областью.

Упомянутая охраняемая критическая область выполняется следующим образом. Осуществляется ожидание до тех пор, пока не будет достигнуто состояние, в котором выражение Е дает значение true

и никакие другие параллельно протекающие процессы не выполняют как раз критическую область (взаимное исключение). Выполнение критической области состоит тогда в выполнении оператора S, причем параллельно выполняющиеся программы при их вступлении в критическую область должны ожидать завершения выполнения оператора S. Если состояние, в котором Е дает значение true, никогда не наступает, то выполнение охраняемой критической области не завершается, т. е. возникает локальный тупик. Таким образом, действия по выполнению охраняемой критической области соответствуют в ходе выполнения программы событиям, которые никогда не являются параллельными. Обеспечение взаимных исключений требует при выполнении программы наличия вышестоящего координирующего процесса.

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

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

await true then z := I endwait || await true then z := 2 endwait ||

допускает выполнение

await true then z := I endwait; await true then z := 2 endwait

с конечным состоянием z = 2, а также выполнение

await true then z :== 2 endwait; await true then z := I endwait

с конечным состоянием z = 1.

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

Буферизованные посылки/приемы сообщений можно понимать как использование особой вычислительной структуры (а именно структуры очереди) в форме общих переменных.




Содержание  Назад  Вперед