Investigation of input flow for the GRID-system withadaptive providing of computing resources.pdf Внимание к теории массового обслуживания в значительной степени обуслов-лено необходимостью применения результатов этой теории к важным практиче-ским задачам, возникающим в связи с бурным развитием систем коммуникаций,эволюцией информационно-вычислительных комплексов, развитием автоматизи-рованных систем управления.Производительность вычислительных сетей связана с временными аспектамифункционирования. При оценке производительности первостепенное значениеимеет продолжительность вычислительных процессов. Случайный характер про-цессов формирования, обработки и передачи данных обуславливает необходи-мость применения стохастических моделей, в качестве которых широко исполь-зуются модели, представляющие собой системы и сети массового обслуживанияразличных классов.Следуя необходимости создания адекватных моделей различных явлений исистем, многие исследователи разработали схемы потоков событий, при помощикоторых можно учитывать различные реальные факторы и, в частности, зависи-мость между поступающими требованиями. Д. Кокс [1] рассмотрел потоки одно-родных событий, интенсивность которых зависит от состояний управляющего по-током процесса. Позже были даны общие определения такого потока [2-4]. Од-ним из наиболее распространенных частных случаев марковских входящих пото-ков (МАР-потоков) является марковский модулированный пуассоновский потоксобытий (ММРР-поток). Исследованию ММРР-потока посвящены работы зару-бежных и российских ученых [5, 6].Как правило, все работы посвящены методам исследования процесса, характе-ризующего число наступивших событий в потоке за некоторое время. В то жевремя для решения практических задач представляет интерес исследование сово-купности потоков различной интенсивности, определяемых состояниями управ-ляющей цепи Маркова. Очевидно, что для оптимального функционирования вы-числительных систем необходимо учитывать интенсивность входящих задач ипредоставлять возможности для их быстрой обработки. То есть потоки заявокбольшей интенсивности должны обслуживаться быстрее. Если для обслуживаниязаявок, поступивших на разных уровнях интенсивности, применяются различныеблоки серверов, то актуальной является также задача исследования проекций вхо-дящего ММРР-потока на каждый из таких блоков.1. Постановка задачиПусть имеется GRID-система [7] - система распределенных вычислений наоснове кластеров, где в качестве серверов используются обычные рабочие стан-ции либо серверы, выполняющие повседневные задачи, не связанные с распреде-ленными вычислениями. Таким образом, серверы выделяют под GRID-задачилишь часть своих вычислительных ресурсов. Рассматривается ситуация, когда за-дачи в этой системе поступают на обработку с изменяющейся интенсивностью.Чтобы оптимизировать исполнение поступающих задач в условиях переменнойинтенсивности, владелец GRID-системы принял решение настроить всю системутаким образом, что при возрастании интенсивности поступления серверы будутвыделять больше вычислительных ресурсов для исполнения GRID-задач, чтобыне создавать задержек в их выполнении. При уменьшении интенсивности поступ-ления серверы уменьшают выделенные под GRID-задачи вычислительные ресур-сы, чтобы возвратиться к решению повседневных задач.Построим математическую модель описанной задачи в виде бесконечно-линейной системы массового обслуживания (СМО), на вход которой поступаетпоток событий с изменяющейся интенсивностью. Будем представлять его в видеMMPP-потока [6] с K состояниями, каждое из которых определяет собственнуюинтенсивность событий ( ƒs( s=1,K). Переходы между состояниями управляющейцепи задаются матрицей инфинитезимальных характеристик Q = ||qij||.Основной целью исследования является получение вероятностных характери-стик входящего потока. Отдельный интерес представляет проекция входящего по-тока на каждый из уровней интенсивности. Это актуально для случая, когда заяв-ки, поступившие при разных интенсивностях (состояниях управляющей цепивходящего потока), обслуживаются на разных группах серверов, имеющих раз-личную, заранее настроенную производительность обслуживания. В этом случаедля одной такой группы ситуация будет выглядеть так, что пока управляющаяцепь находится в соответствующем состоянии, заявки поступают в этот блок сопределенной интенсивностью, когда же состояние управляющей цепи меняется,заявки начинают поступать в другие блоки, а на входе данного блока наступаетвремя «тишины».2. Входящий потокДля начала получим характеристики входящего потока всей системы. Пустьk(t) - состояние управляющей цепи входящего MMPP-потока в момент времени t,n1(t), …, nK(t) - количество событий входящего потока, произошедших на каждомиз K уровней интенсивности за время t. Рассмотрим многомерный случайныйпроцесс {k(t), n1(t),…, nK(t)}. Обозначим через P(k, n1,…, nK, t) = P{k(t) = k,n1(t) = n1, …, nK(t) = nK}. Для этой функции можно записать следующее выражение:1 11 11( , ,..., , ) ( , ,..., , )(1 )(1 )( , ,..., 1,..., , ) ( , ,..., , ) ( ).K K k kkKk K k K kkPkn n t t Pkn n t t q tP k n n n t t P n n t q ƒ t o tƒ=ƒ+ ƒ = − ƒ ƒ + ƒ ++ − ƒ ƒ + ƒ ƒ ƒ + ƒВыполнив несложные преобразования и перейдя к пределу при ƒt  0, получим11 1 11( , ,..., , )( , ,..., , ) ( , ,..., 1,..., , ) ( , ,..., , )KKK k k K k K kkP k n n ttP k n n t P k n n n t P n n t qƒƒ=ƒ== − ƒ + − ƒ + ƒ ƒ .Воспользуемся методом производящих (характеристических) функций [6]. Дляэтого умножим левую и правую части полученного уравнения на eju1n1 ⋅...⋅ejuKnK ,где j = −1 , а u1,…,uK - некоторые переменные, и просуммируем по n1,…,nK от 0до . Введя обозначение1 111 10 0( , ,..., , ) ... ... K K ( , ,..., , )Kju n ju nK Kn nH k u u t e e P k n n t = ==ƒ ƒ ⋅ ⋅ ,получим уравнение относительно функции H(k,u1,…,uK,t):11 11( , ,..., , )( , ,..., , )( k 1) ( , ,..., , )KK juK k K kH k u u tH k u u t e H u u t qt ƒƒ== − ƒ + ƒ ƒ . (1)Обозначим через H(u1,…,uK,t) вектор-строку, состоящую из компонентH(1,u1,…,uK,t),…, H(K,u1,…,uK,t). Пусть { } 11,( ,..., ) diag ( jus 1)K ss Ku u e=B = − ƒ +Q . Тогда(1) в матричном виде запишется следующим образом:11 1( ,..., , )K ( ,..., , ) ( ,..., )K Ku u tu u t u ut=HH B .Решение этого уравнения записывается с помощью матричной экспоненты [8]H(u1,...,uK,t) = Rexp{B(u1,...,uK)t}, (2)где элементы вектор-строки R = {R(1),…,R(K)} находятся из начальных условийR(k)=H(k,u1,...,uK ,0)=P{k(0) = k}.3. Проекция входящего потокаРассмотрим теперь проекцию входящего потока на блок одной интенсивности,пусть это будет блок номер s. Положим в уравнении (1) все u1,…,uK, кроме us,равными нулю. Будем использовать обозначение H(k,us,t) = H(k,0,…,0,us,0,…,0,t).Тогда уравнение (1) перепишется в виде= − ƒ + ƒ ƒ для k = s;1( , , )( , , )Kss kH k u tH u t qt ƒƒ== ƒ ƒ для k  s;или в матричном виде( , )s ( , ) ( )s s su tu t ut=HH B ,где H(us,t) - вектор-строка с компонентами H(k,us,t),k =1,K , а элементы матри-цы Bs(us) равны элементам матрицы Q за исключением элемента bss, который ра-вен (jus 1)e − ƒs +qss .Решение этого уравнения имеет видH(us,t)=Rexp{Bs(us)t}.Введем обозначение{ }1( , ) ( , , ) ( , ) Rexp ( )Ks s s s skh u t H k u t u t u t==ƒ =H E= B E,где E - вектор-столбец, состоящий из единиц. Тогда, учитывая, что0( , , ) s s ( , , )sju ns snH k u t e P k n t== ƒи, следовательно,( , , ) 1 ( , , )2jusnsP k ns t e H k ust dusƒ−−ƒ=ƒ  ,получаем( , ) 1 ( , )2jusnsP ns t e h ust dusƒ−−ƒ=ƒ  . (3)Здесь P(ns,t) = P{ns(t) = ns} - вероятность того, что за время t в систему поступилоns заявок с интенсивностью ƒs.4. Основные вероятностные характеристикиПолучим первый момент этого распределения. Продифференцируем (1) по us иположим все ui =0,i=1,K. Учитывая, что11... 0 0( , ,..., , )( , , ) ( , , )K sKs ss u u nH k u u tj nPkn t jmkstu= = = == = ƒ ,получим1( , , ) ( ) ( , , )Kk km k s t R k m s t qt ƒƒ== ƒ + ƒ ƒ для k = s; (4)1( , , ) ( , , )Kkm k s t m stqt ƒƒ== ƒ ƒ для k  s.Здесь функция m(k,s,t) имеет смысл среднего числа заявок уровня s, поступившихза интервал длины t, в то время, когда состояние управляющей цепи равно k. То-гда1( , ) ( , , )Kkm s t m k s t== ƒ есть среднее число заявок уровня s, поступивших за ин-тервал времени длины t (первый момент). Суммируя уравнения системы (4), (5) иучитывая, что10Kkkqƒ=ƒ = , получаем дифференциальное уравнение относительноэтой функции:( , ) ( ) sdm s t R sdt= ƒ .С учетом начального условия m(s,0) = 0 это уравнение имеет следующее ре-шение:m(s,t)=R(s)ƒst. (6)Найдем второй начальный момент распределения (3). Продифференцируем (1)по us и ui, где s и i - некоторые числа из диапазона от 1 до K. Учтем, что121 2 2 22 2... 0 0( , ,..., , )( , , ) ( , , )K sKs ss u u nH k u u tj nPkn t jm kstu= = = == = ƒи121 2 2... 0 0 0( , ,..., , )( , , , ) ( , , , )K s iKs i s is i u u n nH k u u tj nnPknnt jrksitu u = = = = == =  ƒ ƒ для s  i .Здесь функции m2(k,s,t) и r(k,s,i,t) имеют смысл соответственно второго начально-го момента и смешанного момента для числа заявок, поступивших за время t науровнях интенсивности s и i при условии, что управляющая цепь находилась в со-стоянии k. В результате получаем следующие системы дифференциальных урав-нений. Относительно второго момента:221( , , )2 ( , , ) ( ) ( , , )Kk k km k s tm k s t R k m s t qt ƒƒ== ƒ + ƒ + ƒ ƒ для k = s; (7)221( , , )( , , )Kkm k s tm stqt ƒƒ== ƒ ƒ для k  s. (8)Относительно смешанного момента:1( , , , ) ( , , ) ( , , ) ( , , , )Kk k kr k s i t m k s t m k i t r s i t qt ƒƒ== ƒ + ƒ + ƒ ƒ для k = s; (9)1( , , , ) ( , , , )Kkr k s i t r sitqt ƒƒ== ƒ ƒ для k  s. (10)Функция 2 21( , ) ( , , )Kkm s t m k s t== ƒ - это второй начальный момент распределениявероятностей (3) числа заявок, пришедших на уровне интенсивности s за время t, аr s i t r k s i t== ƒ - смешанный момент числа заявок, пришедших за время tна уровнях интенсивности s и i. Суммируя (7), (8) и (9), (10) по k от 1 до K, полу-чаем дифференциальные уравнения относительно этих искомых функций:2( , )2 ( , ) s ( ) sm s tm s t R st= ƒ + ƒ; (11)( , , ) [ ( , ) ( , )] sr s i t m s t m i tt= + ƒ. (12)Здесь функции m(s,t) определяются из (6). Решения этих уравнений при началь-ных условиях m2(s,0) = 0 и r(s,i,0) = 0 могут быть легко получены для каждого ча-стного случая.ЗаключениеТаким образом, в работе проведено исследование входящего потока для моде-ли GRID-системы с адаптируемым выделением вычислительных ресурсов, пред-ставленной в виде системы массового обслуживания с входящим MMPP-потокоми блоками обслуживания различной производительности. Получено выражениедля характеристической функции (2) многомерного распределения числа заявок,поступивших на каждом из уровней интенсивности, распределение вероятностей(3) числа заявок одного уровня, а также первый момент (6) и общий вид системобыкновенных дифференциальных уравнений для вычисления второго начально-го (11) и смешанного (12) моментов этого распределения. Полученные результатымогут быть использованы на практике при построении GRID-систем с соответст-вующей инфраструктурой.

Скачать электронную версию публикации