Общие программные переменные

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

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

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

Никаких конфликтов не возникает, если параллельно выполняемые программы используют исключительно различные переменные или, по меньшей мере, удовлетворяют условию Бернштейна, согласно которое программная переменная, которая в одной из параллельно выполняемых программ встречается в левой части оператора присваивания, не встречается в других параллельно выполняемых программах. Впрочем, программы, которые удовлетворяют этому условию и не используют операторы посылки/приема, не могут обмениваться сообщениями. Чтобы сделать возможным доступ к общим переменным из параллельно выполняющихся программ, но при этом предотвратить одновременные доступы к одной и той же переменной, а эти доступы соответствующим образом координировать, используются охраняемые критические области.

Пусть Е - булевское выражение, a S - оператор или последовательность операторов. Если S может содержать чреватые конфликтами действия, то следует писать охраняемую критического область в виде await Е then S endwait, чтобы выразить, что оператор S должен выполняться только при условии Е и при взаимном исключении других охраняемых критических областей.
Условие Е называется стражем, а оператор 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.

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

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

Особые общие переменные являются семафорами

- они служат исключительно для синхронизации процессов. Различают булевские и целочисленные семафоры. Целочисленный семафор s вводится в потребление с помощью объявления sema nat х: == n.

Это равносильно объявлению программной переменной типа nat, с точностью до следующих ограничений на использование. Семафор s разрешается использовать только с помощью вызовов процедур P(s) и V(s), а не какими-либо присваиваниями или опросами. Процедуры Р и V определяются следующим образом:

proc Р = (sema nat

х) : await х > 0 then х : = х - I endwait,

proc V = (sema nat х): await true then x : = x + I endwait.

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

При критических областях взаимные исключения дополнительно проверяются с помощью простого синтаксического условия (общие переменные встречаются только в охраняемых критических областях). В противоположность этому при недисциплинированном использовании семафоров проверка взаимных исключений для доступа к общим переменным представляет собой трудный семантический вопрос, так как обеспечение взаимного исключения может зависеть от сложных логических отношений программы. Булевские семафоры вводятся с помощью объявления sema bool s := b и изменяются с помощью следующих процедур:

proc Р = ( sema bool s ) : await s then s := false endwait,

proc V = ( sema bool s ) : await true then s := true endwait.

При использовании семафоров в незавершающихся программах ставится вопрос о справедливости выполнения операций над семафорами. При V - операциях можно без ограничений требовать, чтобы каждый вызов завершался успешно, однако это не имеет места для Р - операций. Вызовы Р - операций могут приводить к ситуациям ожидания, если значение семафора есть 0, или false. Если одновременно ожидают многие Р - вызовы семафора, то после выполнения V - вызова продолжается один Р - вызов. Выбор подлежащего продолжению вызова происходит недетерминированно. При этом без предположения справедливости может случиться, что определенный Р - вызов никогда не будет продолжаться, хотя постоянно выполняются V - вызовы, поскольку всегда будут выбираться для продолжения другие ожидающие Р - вызовы.

В этом случае говорят о старвации

(«морении голодом», бесконечном ожидании; англ. starvation) вызова и соответствующей программы. Старвация имеет место, когда вызов (и соответственно, программа) должен ждать бесконечно долго, хотя все снова и снова возникают возможности продолжить выполнение программы. Если в (бесконечном) ходе работы старвации не возникает, то ход работы называется справедливым. В случае семафоров справедливые ходы работы могут быть реализованы путем введения очередей ожидания. К этому мы вернемся в следующей главе.

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

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

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

monitor EV

var queue m q; signal nonempty;

proc send == (m x) : q := stock(q, x); nonempty.signal;

proc receive = (var m y):

if isempty(q) then nonempty.wait fi;

q,y:==rest(q),first(q)

q := emptyqueue;

var m x, z := xq, zq;

while b(x) do EV.receive(x);

сonsume (x)

od

while b(z) do produce_next(z);

EV.send(z)

od

Сигнал nonempty при этом соответствует булевской переменной, причем nonempty.signal соответствует nonempty:=true; nonempty.wait соответствует nonempty:=false; await nonempty then пор endwait.

Взаимные исключения доступа к переменным монитора обеспечиваются концепцией монитора.А именно: при мониторах предполагается, что каждая из процедур при взаимных исключениях выполняется до тех пор, пока процедура успешно завершится или же по сигналу наступит ситуация ожидания.

Содержание раздела