Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Языковые средства для параллельных ходов работы
Текстуальная нотация программ (в противоположность графическому представлению в виде блок-схем или сетям Петри) по существу является линейной. Несмотря на эту линейность нотации, она позволяет текстуально описывать параллельные процессы. Одну из таких возможностей предлагает параллельная композиция программ.
Через рекурсивные вызовы процедур, которые содержат параллельные композиции, могут быть сформулированы системы со сколь угодно многими параллельно выполняющимися программами (неограниченная параллельность).
Наряду с этой структурированной (ориентированной на скобку) возможностью определения параллельного выполнения в некоторых языках программирования имеются операторы, позволяющие динамически создавать семейство параллельных процессов. Для этого используется специальный оператор, который напоминает оператор вызова процедуры, но здесь при выполнении вызова не ожидают окончания выполнения процедуры. Более того, после начала выполнения процедуры параллельно этому продолжается выполнение «главной программы» (происходит расщеплении потока управления).
Пример (образование параллельных процессов). Пусть р - описание программы (или обозначение для такого описания), а х - идентификатор некоторого процесса (новый экземпляр выполнения программы). Оператор start р name х порождает процесс, соответствующий заданному описанию р. Процесс использует индивидуальное имя х, данное булевское выражению terminate х значения true называет на то, что процесс, обозначенный через х, уже закончен. Пока процесс протекает, булевское выражение дает значение false. С помощью terminate х процесс, обозначенный через х (и все индуцированные им процессы), заканчивается. Чтобы ввести обозначения (переменные) для самостоятельно выполняющихся программных единиц, используется объявление process х.
Тем самым объявляется переменная х, при содействии которой позднее может быть указана ссылка на ход выполнения программы с помощью start... name х.
Программа, которая запускается в работу параллельно своему собственное выполнению (возникающий процесс обозначается через х), может быть сформулирована с помощью приведенных выше операторов следующим образом:
process х;
ргос р =: ... ; {объявление процедуры}
start р name х ; {начать параллельно протекающий процесс}
if terminated х then {cбop, если процесс не заканчивается}
else terminate х
Пример (поиск в дереве). Пусть заданы тип
node вершин и тип tree
двоичных деревьев с помощью объявления
sort tree = empty j cons(tree left, node
root, tree right).
Пусть задано двоичное дерево t, в котором надо проверить, встречается ли определенная вершина i. В программе будем использовать процедуру suche с заголовком процедуры proc suche = (tree t, node i, var bool z), которая результирующей переменной z присваивает значение true, если в двоичном дереве t имеется вершина, помеченная через i, и значение false в противном случае. Последовательная программа, которая решает поставленную задачу, выглядит следующим образом:
proc suche = (tree t, node i, var bool z):
if isempty(t)
then if root(t) == i then z := true
else var bool zl, zr; suche(left(t), i, zl); suche(right(t), i, zr); z :== zl v zr
else z := false
Вызов процедуры suche(t, i, z) создает каскад параллельно выполняемых вызовов процедуры suche, по одному на каждую вершину. После того как выполнение всех вызовов будет завершено, переменная z содержит искомый результат.
