В.Ш. Кауфман - Языки программирования - концепции и принципы (1990) (1160787), страница 28

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 28)

программирования, а главное - серию языковых средств, применяемых для

решения этих проблем: семафоры, сигналы, мониторы, рандеву, каналы, а также

связанные с ними языковые конструкты.

Итак, нужно описать два процесса-соисполнителя, один из которых

(поставщик) вырабатывает некоторое сообщение и поставляет его потребителю,

который, в свою очередь, получает сообщение и потребляет его в соответствии

с назначением (которое нас не интересует).

Вопрос о том, что значит "вырабатывает" и "потребляет" нас также в

этой задаче не интересует, поскольку касается в каждом случае только одного

из процессов и, следовательно, укладывается в знакомые рамки

последовательного программирования. Зато вопрос о том, как понимать

"поставляет" сообщение и "получает" сообщение, касается самой сути

взаимодействия наших соисполнителей.

Различным вариантам уточнения этих двух слов и будет посвящена серия

наших попыток решить задачу. После некоторых колебаний выбран скорее

исторический, чем логический порядок изучения возможных подходов к ее

решению. Хотя, усвоив предыдущий материал, читатель подготовлен к восприятию

современных решений, полезно проникнуться проблемами первопроходцев, тем

более что рассматриваемые при этом средства так называемого "нулевого

уровня" (семафоры и сигналы) используются и в современных языках (например,

в Смолтоке).

Необходимость уточнения смысла слов "поставляет" и "получает" вызвана

тем, что они подразумевают некоторый способ взаимодействия (в остальном

совершенно независимо работающих) процессов. Во всяком случае это не может

быть вызов обычных процедур "поставлять" и "получать" в соответствующем

процессе хотя бы потому, что выполнение таких процедур (по самому их смыслу)

предполагает определенное состояние готовности внешней для процесса среды.

Если в этой среде нет ничего, кроме процесса-партнера (о состоянии которого

в общем случае ничего не известно - ведь он работает асинхронно), то

взаимодействие просто невозможно. Итак, следует сконструировать внешнюю

среду, допускающую взаимодействие асинхронных процессов.

Первое, что приходит в голову человеку, привыкшему к последовательному

программированию - считать процессы-исполнители работающими в общем внешнем

контексте (среде), где им доступны общие переменные. Рассмотрим

соответствующие решения.

Итак, первый вариант взаимодействия - через общие переменные. Точнее

говоря, будем считать, что поставщик и потребитель программ обмениваются

сообщениями через некоторый общий (доступный обоим партнерам) буфер,

способный хранить ограниченное число сообщений. Подробности устройства

буфера нас пока не интересуют. Однако ясно, что, если не принять

дополнительных мер, состояние буфера будет столь же непредсказуемо, как и

состояние процесса-партнера. Поэтому вся проблема в том, как избежать этой

непредсказуемости.

Представим некоторую начальную детализацию наших процессов и общего

контекста. Будем писать в уже опробованном "адовском" стиле.

package общий is

. . .

b : буфер;

procedure поставить (X : in сообщение);

procedure получить (X : out сообщение);

. . .

end общий;

with общий; use общий; with общий; use общий;

task поставщик is; task потребитель is;

. . . . . .

loop; loop;

. . . . . .

выработать (X); получить (X);

поставить (X); потребить (X);

. . . . . .

end loop; end loop;

end поставщик; end потребитель;

Если считать, что процедуры "поставить" и "получить" соответственно

заполняют и освобождают буфер b, то очевидно, что наша программа правильно

работать не будет! Как уже сказано, состояние буфера непредсказуемо. В

частности, нельзя заносить сообщения в полный буфер и нельзя выбирать

сообщения из пустого буфера. Поэтому нужны две функции "полон" и "пуст",

сообщающие о состоянии буфера.

Но теперь будет непредсказуемой связь между значением такой функции и

реальным состоянием буфера - ведь оно может изменяться сколь угодно быстро

из-за асинхронных действий партнеров. Итак, нужна определенная синхронизация

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

Именно, состояние буфера не должно изменяться другим партнером, пока

первый партнер узнает состояние буфера, принимает решение о посылке или

выборке сообщения и выполняет это решение.

Важно понимать, что такая синхронизация может быть выполнена только с

помощью средств, поставляемых внешним контекстом (внешней средой). Например,

люди применяют для синхронизации с партнерами часы, видят партнеров,

чувствуют и т.п.

Эти внешние средства должны удовлетворять определенным требованиям,

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

не должен иметь возможность мешать другому партнеру воспользоваться

средством синхронизации. Это важнейшее требование корректности можно

обеспечивать по-разному. Основной принцип - монополизация доступа к

соответствующему средству. Другими словами, если процесс обладает правом

пользоваться средством синхронизации, то в период, когда он им реально

пользуется, внешняя среда гарантирует его монополию на это средство, точнее

на пользование этим средством в определенной роли (в этот же период тем же

средством в другой роли может пользоваться партнер, как в случае рандеву и

каналов - см. ниже).

Принцип монопольного доступа можно интерпретировать и так, что весь акт

доступа считается неделимым, выполняемым мгновенно с точки зрения

внутреннего времени процессов, что не позволяет другому процессу вмешиваться

в исполнение этого акта. [Одно из назначений синхронизации - обеспечить

монопольный доступ к общим переменным. Как видим, это возможно лишь за счет

монопольного доступа к базовым средствам синхронизации].

6.2. Семафоры Дейкстры

Рассмотрим два вида средств синхронизации - (двоичные) семафоры и

(двоичные) сигналы.

Их основное назначение отражено в названии: семафоры применяют для

синхронизации прохождений процессами своих так называемых "критических

участков" - вполне аналогично тому, как синхронизируют движение поездов,

поднимая и опуская семафоры и обозначая тем самым занятость железнодорожного

перегона.

Поезд допускается на перегон, если путь свободен (семафор поднят

(открыт)), поезд ждет своей очереди, если путь занят (семафор опущен

(закрыт)), и, наконец, семафор закрывается, как только поезд выходит на

перегон (занимает путь); семафор открывается, когда поезд покидает перегон

(освобождает путь).

Внешняя среда, обеспечивающая управление процессами и семафорами,

должна обеспечивать приостановку и активизацию процессов, организацию их

очереди к семафору и, конечно, монопольный доступ к семафорам (неделимость

действий с семафорами).

Все эти возможности Дейкстра предложил концентрировать в двух

операциях:

оградить(S) и освободить(S)

для объекта S типа "семафор", принимающего два значения ("свободен" и

"занят"). Семантика этих операций такова:

Оградить(S): if S=свободен then S:=занят else

[приостановить текущий процесс и поставить

его в очередь(S)].

Освободить(S): if пуста (очередь(S))

then S:=свободен

else [возобновить процесс,

первый в очереди(S)].

Семантика семафоров приспособлена к такой дисциплине программирования,

когда "критический участок" любого процесса предваряется операцией

"оградить" и завершается операцией "освободить". Тем самым процесс, желающий

монопольно распоряжаться некоторым ресурсом, охраняемым семафором S, с одной

стороны, первой операцией "закрывает за собой дверь" и не дает другим

процессам себе мешать, а завершив свои дела, второй операцией "открывает

дверь" для других желающих.

Тем самым по отношению к общим (разделяемым) ресурсам реализуется режим

взаимного исключения с развязкой - на своих критических участках процессы

взаимно исключают доступ партнеров к ресурсу, а не остальных участках

совершенно развязаны - никак не ограничивают действий партнеров. Понятно,

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

заводить свой семафор.

В нашем случае такой ресурс один - буфер. Поэтому достаточно одного

семафора (критические участки выделены):

package общий is

. . .

b : буфер; -- буфер сообщений.

S : семафор; -- с ним связаны соответстсвующие операции

procedure поставить...;

procedure получить...;

end общий;

with общий; use общий; with общий; use общий;

task поставщик is; task потребитель is;

loop; loop;

выработать (X); оградить (S); |

оградить (S); | получить (X); |

поставить (X); | освободить (S); |

освободить (S); | потребить (X);

end loop; end loop;

end поставщик; end потребитель;

Теперь партнеры не мешают друг другу в период доступа к буферу и

вежливо уступают доступ, когда он им не нужен. Однако программа все равно не

будет работать корректно! Партнеры не следят за состоянием буфера. Не следят

сами и не помогают следить соседу.

Можно было бы воспользоваться функциями "полон" и "пуст", сообщающими о

состоянии буфера. Например, так (пишем только внутренние циклы)

loop loop

выработать (X); оградить (S);

оградить (S); while пуст loop

while полон loop ждать;

ждать; -- фиксированное время end loop;

end loop; получить (X);

поставить (X); освободить (S);

освободить (S); потребить (X);

end loop; end loop;

Однако и такое решение неприемлемо и не будет работать. Вложенные циклы

с ожиданием могут долго работать ... в монопольном режиме! Например, если

буфер полон, то бессмысленно ждать внутри критического участка, пока он

освободится - ведь партнеру буфер недоступен, так как семафор закрыт! Это

пример тупика.

Следует писать

while полон loop while пуст loop

освободить (S); освободить (S);

ждать; ждать;

оградить (S); оградить (S);

end loop; end loop;

Теперь программа будет работать. Ее недостаток в том, что внутренние

циклы нерационально расходуют активное время процессора - это особенно

неприятно при реализации всей системы на единственном физическом процессоре.

Циклов активного ожидания в таком случае стараются избегать.

6.3. Сигналы

Избежать циклов активного ожидания можно, заменив его пассивным

ожиданием (без занятия процессора), организуемым с помощью средств

синхронизации, называемых сигналами.

Сигнал Е - это объект типа "сигнал", принимающий значения "есть" и

"нет". Аналогично семафору с ним связана очередь процессов "ждущих сигнала

Е", и две операции, послать(Е) и ждать(Е), управляющие этой очередью.

Семантика этих операций такова:

послать(Е):

if пуста(очередь(Е)) then Е:=есть;

else [возобновить первый ("ждущий") процесс в очереди(Е)];

ждать(Е):

if Е=есть then Е:=нет;

else [приостановить текущий процесс и поместить его

(последним) в очередь (Е)].

Как видим, семантика сигналов двойственна семантике семафоров (послать

= освободить, а ждать = оградить).

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

процесса ограждать критические участки от возможного влияния других

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

процессов. С помощью сигналов партнеры могут сообщать информацию о событиях,

становящихся им известными. С другой стороны, они могут пассивно (в очереди)

ждать наступления этих событий.

В нашем примере таких событий два: неполнота и непустота буфера.

Поэтому нужны два сигнала - непуст и неполон. Заметив, что цикл ожидания

становится ненужным (ожидание обеспечивает средства синхронизации - за это и

боролись!), напишем (теперь уже окончательную) схему нашей программы

полностью.

Характеристики

Список файлов книги