BC/NW 2011; №2 (19):2.2

 

О МОДЕЛИ ВЫПОЛНЕНИЯ АСИНХРОННО ВЗАИМОДЕЙСТВУЮЩИХ ПОСЛЕДОВАТЕЛЬНЫХ ПРОЦЕССОВ

Мороховец Ю.Е., Шполянский М.И.

(Национальный исследовательский университет «МЭИ», Россия)

 

При исследовании вычислительных систем задачи, решаемые системами, принято представлять в виде связных ориентированных графов. На рис. 1 в качестве примера показан граф задачи, включающей восемь подзадач st₀, …, st₇., соответствующих его вершинам, и шестнадцать потоков данных ds₀, …, ds₁₅, являющихся результатом информационного взаимодействие подзадач, соответствующих дугам графа.

Рис. 1. Пример графа задачи

 

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

В случае циклических графов, подзадачи могут ассоциироваться с последовательными процессами, имеющими конечное множество состояний, в котором выделены начальное состояние и непустое подмножество заключительных состояний. Решение подзадачи в этом случае связывается с выполнением процесса – его переходом из начального в одно из заключительных состояний. При переходе из состояния в состояние, процесс-подзадача преобразует блоки данных входных потоков в блоки данных выходных потоков, однако в этих преобразованиях участвуют не все входные и выходные потоки, а их подмножества, возможно и не собственные. Решение задачи успешно завершается, когда оказываются выполненными все ее процессы-подзадачи. Факт успешного завершения задачи в этом случае не является очевидным. Особенности графа задачи, порядок следования и свойства преобразований, реализуемых процессами, могут привести к их взаимной блокировке и, как следствие, к нерезультативному прекращению решения задачи.

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

Адресное пространство, в котором выполняются процессы, является объединением пространств отдельных процессов, которые (пространства) могут полностью пересекаться – общая память, пересекаться частично – разделенная память и  не пересекаться вовсе – распределенная память [1]. По нашему мнению практический интерес представляет вариант, когда адресные пространства процессов либо пересекаются полностью, либо не пересекаются вовсе или, другими словами, множество процессов разбито на подмножества, причем адресные пространства процессов одного подмножества пересекаются полностью, а разных – не пересекаются вовсе. Этот вариант структуры адресного пространства можно назвать агрегированной памятью, а подмножества процессов, имеющих общее адресное пространство – вычислительными агрегатами.

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

Внутриагрегатные связи, которые будем называть сильными, позволяют передавать блоки данных от процесса к процессу при помощи пассивных буферов. Запись блоков в пассивный буфер ограниченного размера выполняет процесс-источник данных, а чтение из буфера – процесс-приемник данных. При этом, как запись блока в буфер, так и его чтение оттуда могут осуществляться практически мгновенно, изменением соответствующей ссылки на блок данных и инкрементом/декрементом семафоров буфера.

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

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

Рис. 2. Пример агрегации процессов

 

При разработке программ процессов программист может не различать сильные и слабые связи, оперируя общим понятием связь. Такая виртуальная связь может рассматриваться как FIFO-очередь ограниченного размера, с которой работают вычислительные процессы, используя унифицированный коммуникационный интерфейс. Этот интерфейс включает небольшое число примитивных операций, обеспечивающих доступ к хвостовым и головным блокам очереди, добавление первых в очередь и удаление последних из очереди связи. Определим коммуникационный интерфейс процессов, имеющий классическую реализацию посредством общих семафоров Дейкстры [3].

Входные связи:

?xc₁, …, xc_m – оператор проверки наличия блоков в очередях входных связей xc₁, …, xc_m. Если все указанные входные связи не пусты, то переход к следующему оператору программы, иначе ожидание добавления блоков данных в очереди связей. Головные блоки данных проверенных связей могут использоваться операторами программы, следующим за оператором ?;

^xc – ссылка на головной блок входной связи xc. Эта ссылка обеспечивает доступ к данным головного блока по чтению;

!x₁, …, x_m –  оператор удаления головных блоков из очередей входных связей xc₁, …, xc_m. После выполнения этого оператора, некоторые (а возможно и все) указанные в нем входные связи могут оказаться пустыми. Для работы с ними необходимо сделать проверку – выполнить оператор ?.

Выходные связи:

?yc₁, …, yc_n – оператор проверки наличия мест в очередях выходных связей yc₁, …, yc_n. Если все указанные выходные связи не переполнены, то переход к следующему оператору программы, иначе ожидание удаления блоков данных из очередей связей yc₁, …, yc_n. Хвостовые блоки данных проверенных связей могут формироваться операторами программы, следующим за оператором ?;

^yc – ссылка на хвостовой блок выходной связи yc. Эта ссылка обеспечивает доступ к данным хвостового блока по записи;

!yc₁, …, yc_n – оператор добавления хвостовых блоков в очереди выходных связей yc₁, …, yc_n. После выполнения этого оператора, некоторые (а возможно и все) указанные в нем выходные связи могут оказаться переполненными. Для работы с ними необходимо сделать проверку – выполнить оператор ?.

В списках параметров операторов ?, ! могут одновременно присутствовать как имена входных, так и имена выходных связей. Семантика операторов для входных и выходных связей в этом случае не меняется.

Для примера рассмотрим задачу распределенного умножения матрицы A размерностью 44 на матрицу B той же размерности. Строки матрицы-множимого вводятся процессами p₀-p₃, причем номер строки совпадает с номером процесса. Матрица-множитель B вводятся по столбцам процессами p₀-p₃ и вместе со столбцами вводятся их номера, в общем случае не совпадающие с номерами процессов. Матрица результат выводится по строкам процессами p₀-p₃.

Процессы работают по одной и той же программе, имеющей вид:

#include ”device_class.h”       //классы устройств ввода-вывода

const int N=4;                  //размер матриц A, B и C (N>1)

typedef double vector[N];       //тип вектор

typedef struct num_vector{      //тип нумерованный вектор

          int num;

          vector vec;

        };

/*** функция, вычисляющая значение элемента матрицы C

int Cij(vector a,b){

  double sum=0.0;

  for(int k=0;k<N;k++)

    sum=sum+a[k]*b[k];

  return sum;

};                              //конец функции Cij

/*** шаблон получения строки матрицы C процессами p0-p3

templet line_prod(in x out y){  //x – входная, y – выходная связь

  num_vector x,y;               //тип входной и выходной связей

  device dvAB,dvC;              //устройства ввода-вывода

  vector A_line,C_line;         //строки A_line, C_line

  num_vector B_coln;            //нумерованный столбец B_coln

  int k=0;                      //k счетчик циклов

  dvAB.read(A_line);            //ввод строки матрицы A

  dvB.read(B_coln);             //ввод нумерован. столбца матрицы B

  C_line[B_coln.nom]=Cij(A_line,B_coln.vec);

  while(++k<N){                 //цикл по столбцам матрицы B

    ?y;                         //проверка выходной связи y

    ^y=B_coln;                  //выдача столбца

    !y;                         //добавление столб в очередь связи y

    ?x;                         //проверка входной связи x

    C_line[^x.num]=Cij(A_line,^x.vec);

    !x;                         //удаление столб из очереди связи x

    }

  dvC.write(C_line);            //вывод строки матрицы С

}

Последовательность операторов  ?x; C_line[^x.num]=Cij(A_line,^x.vec); !x  может быть заменена операторами ?!x; C_line[^x.num]=Cij(A_line,^x.vec) в предположении, что x – вход (входная переменная) процесса, а конструкция  ?!x  обеспечивает проверку наличия блоков данных в очереди связи, ассоциированной с входом x, прием головного блока очереди в x и удаление этого блока из очереди. Аналогично, операторы  ?y; ^y=B_coln; !y  могут быть заменены операторами  y=B_coln; ?!y  в предположении, что y – выход (выходная переменная) процесса, а конструкция  ?!y  обеспечивает проверку наличия мест в очереди связи, ассоциированной с выходом y, выдачу блока даных из y в связь и добавление его к очереди связи.

ЛИТЕРАТУРА

1.     Таненбаум Э., ван Стеен М. Распределенные системы. Принципы и парадигмы. – СПб.: Питер, 2003. – 877 с.

2.     Хоар Ч. Взаимодействующие последовательные процессы. – М.: Мир. – 1989. – 264 с.

3.     Дейкстра Э.  Взаимодействие последовательных процессов. В кн.: