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




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


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

- они служат исключительно для синхронизации процессов. Различают булевские и целочисленные семафоры. Целочисленный семафор 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 - вызовы, поскольку всегда будут выбираться для продолжения другие ожидающие Р - вызовы.


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