Конспект установочных лекций по комплексному курсу Информатика, Теория информации
О языках программирования в курсе “Информатика”
Для распределенных систем особое значение имеют действия, которые служат для обмена информацией (коммуникация и координация) между разделенными (параллельно) компонентами системы. Языки программирования, для описания процессов, содержат в частности, операторы для обмена сообщениями между параллельно выполняющимися программами.
Коммуникация через обмен сообщениями.
Обмен сообщениями между двумя компонентами в параллельно работающей системе может достигаться с помощью двух дополнительных действий: отправления и получения. В одном процессе отправления/получения могут быть задействованы многие партнеры, однако часто ограничиваются системами, в которых для каждого пересылаемого в системе сообщения существует единственный отправитель и один адресат.
Важным аспектом при обмене сообщениями является концепция адресации получателя. При посылке сообщения, во всяком случае, должен быть специфицирован получатель или круг возможных получателей. Аналогично и для получения. Существуют самые различные способы адресации сообщений. Например, для адресации могут использоваться имена (метки) выполняющихся программ.
Каналы для обмена сообщениями типа 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) Р' возможно, приведет к тупикам, которые исключены для Р.
Неявные буферы реже приводят к тупикам, однако, требуется больше места в памяти для промежуточного хранения сообщений.
