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

       

О языках программирования в курсе “Информатика”


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

Коммуникация через обмен сообщениями.

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

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

Каналы для обмена сообщениями типа m объявляются аналогично объявлению программных переменных:

channel m c

Среда передачи сообщений, которая служит для установления связи между отправителем и получателем, носит название канал.

В процедурном языке действия пересылки по каналу с выражаются с помощью оператора send E on c, где Е - любое выражение типа m; с - имя канала.

В дополнении к этому действие приема сообщения выражается оператором receive x on c, где х - идентификатор программной переменной.

Если к моменту выполнения действия приема еще отсутствует посланная информация, то процесс ожидает момента поступления сообщения.

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

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


channel m с;

var m x, var m z := x0, z0;

while b(x) do receive x on c;



consume (x)

od

while b(z) do produce_next(z);

send z on с

od

Здесь consume и poduce_next - заданные процедуры, a b - булевская функция. операторов.

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

(1)

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

(2)   рандеву («рукопожатие»): посылающий процесс ждет, пока принимающий процесс будет готов к приему сообщения. Обмен информацией имеет место в событии, после чего оба процесса продолжают свою работу. Обмен сообщениями соответствует общему событию.

В случае (1) говорят об асинхронной,

а в случае (2) - о синхронной передаче. Р

Для обсуждения различных концепций обмена сообщениями введем две синтаксические формы. В дальнейшем будем использовать операторы send Е on с и соответственно receive x on с для асинхронного обмена сообщениями с неявными буферами. Будем писать Е | с для синхронного действия посылки х ? с для синхронного действия приема при обмене сообщениями через рандеву.

При этом соглашении пример производитель/потребитель в нотации рандеву может быть записан следующим образом:

channel m c;

var m x, var m x:=х0, x0

while b(x) do x ? c;

consume (x)

od

while b(x) do produce next(x);

z ^ c

od

Для задачи производитель/потребитель интерпретация рандеву допускает по сути дела только единственный ход работы. Неявные буферы допускают значительно больший параллелизм, чем синхронный обмен сообщениями.

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

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

(1)   Каждый свободный от тупиков ход работы программы р' есть линеаризация хода работы р, причем действия посылки/приема сообщений могут толковаться как одно действие.

(2)   Определенные ходы работы р и их линеаризации исключаются как ходы работы р'.

(3)   Р' возможно, приведет к тупикам, которые исключены для Р.

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


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