Analytical model of distributed computing

Full Text

Развитие систем промышленной автоматизации, телекоммуникаций, электронной коммерции, Интернета вещей, в которых отдельные элементы приложений должны быть распределены по сети и где уже находится огромное количество программных компонент типа Active-X, JavaBean, вызывает необходимость использования технологий создания и реализации распределенных приложений. Программные компоненты (ПК) распределённого по сети приложения, реализующего соответствующий бизнес-процесс, взаимодействуют друг с другом, создавая единый программный код. Основой такого взаимодействия в среде разнообразных аппаратных и программных платформ является, например, технология распределённых вычислений CORBA (Common Object Request Architecture) (см. рисунок 1 и [1-3]). Ядром технологии CORBA, обеспечивающим взаимодействие распределенных по сети ПК, является логическая шина ORB (Object RequestBroker) - брокер объектных запросов. ORB формирует механизмы выполнения и реализации запросов взаимодействующих ПК: поиск ПК разрабатываемого приложения, обмен необходимыми данными, объединение требуемых ресурсов, формирование распределенной системы, создание распределенного бизнес-приложения. Процесс-клиент инициирует операцию и через подсистему обмена производит вызов сообщения. ORB, используя широковещательную рассылку, находит требуемые ПК, активирует их, передает запрос и параметры, вызывает запрашиваемый метод и посредством брокера объектных запросов передает результаты вызываемому клиенту. При этом возникает необходимость количественной оценки данных алгоритмов интеграции ПК, исследования влияния процессов их взаимодействия на характеристики системы в целом. Задача исследования заключается в разработке и оценке моделей и методов построения системы интеграции ПК распределенных приложений на основе технологии CORBA [4-6]. Модели и методы системы интеграции программных компонент Модель взаимодействия ПК можно представить в виде замкнутой стохастической сети с центральным обслуживающим узлом (см. рисунок 2 и [1]). Брокер ORB формально представлен корневым узлом сети М, остальные М, остальные М () -1M узлов - компонентами физически распределенного по сети приложения, реализующего соответствующий бизнес-процесс. В такой системе ПК, связанные зависящими от соответствующих бизнес-процессов правилами, циркулируют между узлами сети, используя в качестве посредника центральный узел-брокер ORB. При этом переходные вероятности заявок класса можно описать следующей матрицей: ( ) ,1,1 ,1,2 ,1, ,2,1 ,2,2 ,2, , ,1 , ,2 , , ... ... . ... ... ... ... ... r r rM r r rMj ri r M r M rMM P P P P P P Pn P P P = (1) Здесь ( ) j ri Pn - вероятности перехода, j in - число заявок, перешедших из узла i в узел j. Считается, что в данной модели в каждом i-м узле сети время обслуживания распределено по экспоненциальному закону с параметром , iµ а взаимодействие ПК описывается многомерным случайным процессом ( ) ( ) { ( ) ( )} 12 , ,..., . R N t n t n t n t = Рисунок 1. Архитектура распределенных объектов технологии CORBA Рисунок 2. Формальная модель системы взаимодействия ПК Будем также считать, что интенсивность обработки запросов на обслуживание осуществляется в порядке поступления (FCFS) и не зависит от R. Процессоры узлов сети ORB независимы друг от друга, а вероятность того, что обработке подлежит к заявок класса r, равна P(k), где k), где k () Pk = ( ) ( ) ( ) 1122 , nn P k P k P k=  k = ( ) 12 , ,..., , n k k k i k = ( ) 12 , ,..., . i i ir k k k= Учитывая, что полученное распределение количества заявок в очередях процессоров представлено как произведение ( ) , i i r Pk и в сети создаётся пуассоновский поток реализованных запросов, данная сеть ORB соответствует требованием сети Джексона и может быть представлена в мультипликативном виде [3] 1 12 1 1 ( ) ( , ,..., ) , )(M Ri i P n G n n n Z n - == ∏ (2) где () Pn - вероятность нахождения узла в со - вероятность нахождения узла в со - стоянии n, ( ) 1 2. , ,..., , M n n n n = 1 2 () , ikN i R ki i PGn =  µ =  µ  ∑∏ (3) ( ) ( ) 1 ! 1 !1 ,ir R ni i i ir r r ir i R nZn l nR = = = µ ∏ ∏ (4) ( ) 1 , M ir ir ij i l l P r = =∑ 1, , iM = 1, . rR = (5) Отсюда согласно выводам, изложенным в [3; 9], получаем следующие показатели: - пропускную способность брокера ORB для заявки r-го класса ( ) ( ) 1 ( , ) , R k N ir ir R i R r i i n i n n P n N n n= λ = µ ∑ (6) - число заявок класса r в ORB r в ORB r ( ) ( ) 1 ,, R R N ir R i R R r n L N P n N n = = ∑ (7) - среднее время ожидания заявки r-го класса ( ) ( ) 11 .iRir r ir LN TN M +-  = (8) На практике значения данных показателей зависят от загрузки системы в момент поступления заявки. Очевидно, что возможно состояние ORB, блокирующее очередной вызов. В этом случае осуществляется его N-кратное повторение до соN-кратное повторение до соN стояний обслуживания или отказа. Вероятность успешного вызова ( ) ( ) ( ) ( ) ( ) ( )( )( ) 1 1 1 1 2 1 1 1 . óñï áëê îòê îòê îòê áëê N P N P P P P N P - = - - - - -   Вероятность отказа от вызова ( ) ( ) ( ) ( )( ) ( ) ( ) 11 1 2 1 1 . îòê áëê îòê îòê îòê N P N P P P P N = - × × - - - Исходя из результатов, полученных в (1), можно записать 1 11 ( ) (1 )(1 (1 ( ))),óñï áëê áëê îòê Ni i ij P N P P P j - = = = - + - ∑∏ 1 11 ( ) ( (1) ( ( 1) (1 ( )))). îòê áëê îòê áëê îòê îòê Ni i ij P N P P P P i P j - = = = + + + - ∑∏ Улучшения данных показателей можно добиться путем снижения системных затрат, связанных с процессами взаимодействия между ПК и ORB. Считаем, что распределенная система включает d процессорных модулей, а реализация d процессорных модулей, а реализация d бизнес-процесса обеспечивается совокупностью nd > ПК. В [1; 9; 13] показано, что эффективность реализации распределенного приложения связана с решением трех основных задач: - разделение n ПК на d групп таким образом, d групп таким образом, d чтобы в каждой из групп находились ПК с наибольшими частотами взаимодействия; - построение правил реализации запросов, устраняющих блокировки и тупиковые ситуации; - снижение системных затрат на интеграцию распределенных по сети ПК. При решении первой задачи предположим, что для взаимодействующих ПК i f и j f известна частота взаимных запросов. Разбиваем все n ПК на d групп d групп d Φ={ } 12 , ,..., , d F F F так, что 11 , nd ii ii fF = = =  ,kl FF = ∅ . kl ≠ При одновременном обращении вызовов к различным ПК, размещенным на одном из процессорных модулей, возникает конфликт. Частота возникновения конфликтов k C на k-м ПМ ( ) , ,,k ij C P i j =∑ а суммарная частота конфликтов в системе ( ) 1 1 , ,. dd k k k i j C C P i j = = = = ∑ ∑∑ Уменьшить значение C можно путём цикличеC можно путём цикличеC ских переносов ÏÊi из группы k в группу l; k, . ld ∈ При этом изменение C определяем по форC определяем по форC муле (5): ( ) ( ) ( ) ( ) ,, , , . ÏÌ ÏÌ k l i j C P i j P j i P i j P j i ∈ ∈ ∆ = + -   -+   ∑ ∑ 310 Мочалов В.П., Линец Г.И., Братченко Н.Ю., Говорова С.В. «Инфокоммуникационные технологии» Том 17, № 3, 2019, с. 307-313 Последовательное выполнение одинаково построенных шагов завершается, когда любой перенос ÏÊi из группы k в группу l не изменяет l не изменяет l . C∆ Вычисление C ∆ можем произвести удобным рекуррентным методом. Введем систему операторов R ={ } , 1, , 1, ,it R i n t d = = означающих перенос ÏÊi в классе . td ∈ Тогда ( ) ( ) ( ), it itC R C ∆ ϕ = ϕ - ϕ где ( ) it ∆ϕ - изменение частоты конфликтов. Обозначим через ( )iq it ∆ϕ приращение ( ) it ∆ϕ при переходе к разбиению ( ) . iq RR ϕ∈ Тогда ( ) ( ) ( ),iq it it iq it R ∆ ϕ = ∆ -∆ ϕ 1, ; in = 1, ; qd = ( ) ( ) ( ). iq it iq it it R ∆ ϕ = ∆ ϕ +∆ ϕ Данный рекуррентный метод позволяет произвести рациональное распределение n ПК по d ПМ, снизить непроизводительные затраты при реализации запросов на услуги связи. Вторая задача, связанная с построением расписания обработки запросов, сводится к нахождению такой последовательности их реализации, которая минимизирует общее время выполнения задания. Очевидно, что устранение блокировки запросов возможно при выполнении условия [5; 7] 1 , jiij p p L L t t Z Z + - > - 1, , Lk = где ip t - требование p i-го типа; 1 j pt + - требование ( 1) p+ j-го типа; , i LZ j LZ - время обслуживания требований процессором L; { } max . ij ij L L l Z Z = - Тогда подход к решению задачи сводится к следующему. Если (X следующему. Если (X следующему. Если ( , X, X U) - ориентированный U) - ориентированный U симметричный граф, в котором Х-множество Х-множество Х типов заявок, U-множество дуг, то необходимо U-множество дуг, то необходимо U выделить контур, связывающий требуемые вершины только один раз, при этом сумма длин дуг должна быть минимальной [8; 10; 11]. ,0 min, r ij ij ij lx = →∑ 00 , rr ij i ij xn = = =∑∑ 0, , ir = 0, . jr = Третья задача, связанная с минимизацией системных затрат интеграции распределенных по сети ПК, сводится к снижению частоты обмена данными между ПК и брокером ORB. Решение задачи производится за счет разбиения множества ПК на независимые фрагменты и обеспечения взаимодействия между данными фрагментами и ORB [12; 14; 15]. Данная фрагментация описывается матрицами , ,1 nm ik ik VV= = и ,1 ,nij ij Ll= = где 1, , 0, åñëèÏÊ âïðîòèâíîìñëó÷àå, jk ikV ∈ϕ =   1, , 0, . åñëèÏÊ âïðîòèâíîìñëó÷àå ik ijl ∈ϕ =   Если число выполнений i-го ПК равно , im а запрос к j-му ПК происходит с вероятностью ,ijP то число запросов из ÏÊi к ÏÊj будет равно 11 , nn i ij ik kj mpV = = ∑∑ где ik V - идентификатор наличия только тех ПК, которые входят в k-й фрагмент. Тогда среднее k-й фрагмент. Тогда среднее k число межфрагментных запросов при условии вхождения каждого ПК в состав только одного фрагмента соответствует ( ) 111 1 min. nnn i ij ik jk kij C mPV V = = = = -→ ∑∑∑ Данная задача решается стандартными средствами пакета программ Mathematica. Заключение Представленные формальные подходы к решению задачи интеграции программных компонент распределенного по сети приложения на основе брокера объектных запросов технологии распределенных вычислений CORBA, система функциональных моделей исследования алгоритмов взаимодействия элементов данной системы позволяют принимать обоснованные решения при построении распределенных систем. Решение задачи интеграции программных компонент сведено к реализации трех основных алгоритмов: рационального распределения программных компонент по процессорным модулям системы, построения расписания выполнения параллельных процессов минимальной длины, минимизации непроизводительных затрат, связанных с процессами обмена данными. Предложен комплекс аналитических моделей исследования системы интеграции распределенных приложений, позволяющий проводить количественную оценку алгоритмов взаимодействия ее элементов, оценивать влияние процессов взаимодействия на характеристики системы в целом. Работа выполнена при финансовой поддержке РФФИ в рамках научного проекта № 19-07-00856/19.

About the authors

V. P Mochalov

Department of Infocommunications, North-Caucasus Federal University

Stavropol, Russian Federation

G. I Linets

Department of Infocommunications, North-Caucasus Federal University

Stavropol, Russian Federation

N. Yu Bratchenko

Department of Infocommunications, North-Caucasus Federal University

Stavropol, Russian Federation

S. V Govorova

Department of Infocommunications, North-Caucasus Federal University

Stavropol, Russian Federation

References

Supplementary files