Queuing systems with heterogeneous servers and state-dependent jump priorities informatics and programming.pdf Одно из основных допущений при разработке математических моделей процессов обработки запросов в системах телетрафика состоит в том, что серверы являются идентичными по всем показателям, т.е. считается, что все серверы имеют одинаковую скорость, их надежностные показатели идентичны, а также совпадают их стоимости эксплуатации. Однако это допущение плохо соотносится с реальной ситуацией, так как в процессе расширения существующих компьютерных и коммуникационных систем приходится одновременно использовать гетерогенные серверы (heterogeneous servers; HS). Серверы с различными скоростями особенно часто встречаются в системах, где в процессе обработки запросов участвуют не машины, а люди, в частности в колл-центрах. Достаточно подробный обзор работ, посвященных исследованию моделей систем с HS, можно найти в монографии [1]. Важное направление исследований составляют работы, в которых рассматриваются проблемы организации доступа запросов к гетерогенным серверам [2-5]. Среди них наиболее актуальными являются рандомизированный доступ (randomized access), упорядоченный доступ (ordered entry) и доступ, основанный на схеме «первым используется быстрый сервер» (fast server first). В ранних работах изучались модели систем обслуживания с HS при наличии идентичных заявок, а модели систем обслуживания с HS и разнотипными заявками недостаточно исследованы. Однако очевидно, что для повышения экономической эффективности работы системы с HS следует выделить высокоприоритетные (h-заявки) и низкоприоритетные заявки (l-заявки) и организовать обработку h-заявок в высокоскоростных серверах f-серверах), а медленные серверы (s-серверы) назначить для обслуживания l-заявок. В последние годы изучались модели систем обслуживания с HS и без буфера для ожидания разнотипных заявок [6-8]. Так, в работе [6] рассмотрена модель системы с HS, в которой серверы для обслуживания заявок высокого и низкого приоритетов являются сепаратными, при этом в случаях занятости всех серверов в соответствующих группах допускается обслуживание поступившей заявки в другой группе. Считается, что вероятности переназначения заявок зависят от числа занятых серверов в соответствующей группе. Модели систем обслуживания с HS и общими и раздельными очередями разнотипных заявок изучены в работах [7] и [8]. В работе [7] исследована модель системы с двумя гетерогенными серверами и предложена рандомизированная ^политика включения медленного сервера, согласно которой при достижении длины очереди заявок величины N медленный сервер включается с определенной вероятностью, а с дополнительной вероятностью он остается в спящем режиме. Первой публикацией, посвященной изучению моделей систем с HS и конечными и / или бесконечными очередями разнотипных заявок при наличии скачкообразных приоритетов (Jump Priorities, JP), была работа [8]. При использовании этих приоритетов за счет введения зависящих от состояния системы JP можно организовать переход l-заявки в очередь h-заявок. Введение таких приоритетов позволяет избежать нежелательной ситуации «старения» l-заявок в очереди. При этом, конечно, следует учитывать ограничения, предъявляемые к качеству обслуживания h-заявок, так как переходы l-заявок в очередь h-заявок приводят к ухудшению качества обслуживания h-заявок. В работе [8] показана актуальность изучения систем с зависящими от состояния системы скачкообразными приоритетами, при этом зависимость JP от состояния может быть учтена различными способами. В указанной работе изучена модель, в которой JP зависят от разности текущего числа разнотипных заявок в системе: если разность числа разнотипных заявок в системе превышает определенное пороговое значение, то одна l-заявка с некоторой вероятностью может переходить в очередь h-заявок, т.е. в указанной схеме определения JP имеется только одна степень свободы. В [6] решены различные задачи оптимизации введенных приоритетов. В данной работе предложена новая схема определения скачкообразных приоритетов в системах обслуживания с HS: переход l-заявки в очередь h-заявок зависит от наличия конкретного числа заявок каждого типа. Иными словами, здесь, в отличие от работы [8], имеются две степени свободы, т.е. за счет выбора двух параметров можно управлять показателями качества функционирования системы. Изучены модели систем с гетерегенными серверами и скачкообразными приоритетами, при этом рассматриваются модели с раздельными очередями разнотипных заявок и общим бесконечным буфером. 1. Описание моделей и постановка задачи Изучаемая система содержит два гетерогенных сервера: быстрый f-сервер) и медленный (s-сервер). Эти серверы обслуживают потоки заявок двух типов - высокоприоритетные (h-заявки) и низкоприоритетные (l-заявки). При этом h-заявки всегда обслуживаются в /-сервере, а l-заявки могут быть обслужены в обоих серверах. Оба потока заявок являются пуассоновскими с интенсивностями Xh и Xi для h-заявок и l-заявок соответственно. Времена обслуживания заявок в обоих серверах являются случайными величинами (с.в.) с показательной функцией распределения (ф.р.), при этом средние времена обслуживания в f-сервере и s-сервере равны р-1 и р-1 соответственно. Скорость обслуживания f-сервера больше, чем скорость обслуживания s-сервера, т.е. рf > р. В модели с конечными очередями предполагается, что для ожидания заявок в очереди имеются раздельные буферы конечных размеров, при этом максимальные количества h-заявок и l-заявок в системе равны Kh и Kl. Это означает, что размер буфера для h-заявок (h-буфер) равен Kh -1, а соответствующий буфер для l-заявок (l-буфер) имеет размерность Kl -1. В модели с общей очередью разнотипные заявки ожидают в общем буфере неограниченного размера. Здесь рандомизированные скачкообразные приоритеты, которые зависят от состояния системы, определяются следующим образом. Введенные рандомизированные JP зависят от текущего состояния системы, при этом состояние системы в каждый момент времени задается двумерным вектором (h, l), где компоненты h и l указывают на число h-запросов и l-запросов в системе соответственно. Для определения указанных приоритетов вводятся два пороговых параметра: r , 1 ri Ki, и rh, 1 rh Kh . - Поступающие h-заявки всегда присоединяются к h-буферу, если там имеется свободное место; иначе эти заявки теряются с вероятностью 1. - Если в момент поступления l-заявки число заявок такого типа в системе меньше параметра г/, то независимо от числа h-заявок в системе эта l-заявка присоединяется к l-буферу. - Если в момент поступления l-заявки число заявок такого типа в системе не меньше параметра rl и при этом число h-заявок меньше порогового параметра rh, то одна из l-заявок (для определенности считается, что l-заявка, стоящая в начале очереди) согласно схеме Бернулли либо с вероятностью а присоединяется к h-буферу, либо поступившая l-заявка с вероятностью 1 - а переходит в конец очереди l-буфера, если там имеется свободное место. - Если в момент поступления l-заявки число заявок такого типа в системе не меньше параметра rl и число h-заявок не меньше порогового параметра rh, то поступившая l-заявка с вероятностью 1 присоединяется к l-буферу, если там имеется свободное место; иначе поступившая l-заявка теряется с вероятностью 1. - Если в момент поступления /-заявки соответствующий буфер полностью заполнен и число h-заявок меньше указанного выше порогового параметра га, то /-заявка, стоящая в начале очереди, либо с вероятностью а присоединяется к h-буферу, либо поступившая /-заявка теряется с вероятностью 1 - а. Следовательно, в предложенной схеме рандомизированные JP определяются так: а, если l > rt, h < rh, 0 в других случаях. Если в соотношении (1) принять, что а = 1, то получаются детерминированные JP, т.е. каждый раз, когда в момент поступления /-заявки выполняется условие l >r ,h rl } , (3) которое геометрически задается с помощью прямоугольника с вершинами в точках (0, r +1), (rf -1,r +1), (0,K), (rf -1,K) (см. рис.1). Введенные рандомизированные JP определяются в точках внутри этого прямоугольника. Интенсивность перехода из состояния (пн, n ) е E в состояние (пн, n'L) е E обозначим через q((h,l),(h',l')) . Переходы между состояниями возможны лишь в моменты поступления разнотипных заявок и в моменты завершения их обслуживания. Исходя из этого заключаем, что указанные величины определяются из следующих соображений. - Если в момент поступления h-заявки система находится в состоянии (h, l) е E, где h < KA, то система переходит в состояние (h +1, l) е E с интенсивностью Xh . - Если в момент поступления /-заявки система находится в состоянии (h, l) е E - E , где l < K, то система переходит в состояние (h, l +1) е E с интенсивностью X. - Если в момент поступления /-заявки система находится в состоянии (h, l) е Ea, где l < K , то система переходит в состояние (h, l +1) е E с интенсивностью Х;а . - Если в момент поступления /-заявки система находится в состоянии (h, l) е Ea , где l < K , то система переходит в состояние (h +1,l) е E с интенсивностью \\ (1 - а). - Если в момент завершения обслуживания h-заявки система находится в состоянии (h, l) е E, где h > 0 , то система переходит в состояние (h - 1, l) е E с интенсивностью . - Если в момент завершения обслуживания /-заявки система находится в состоянии (h,l), где l > 0, то система переходит в состояние (h, l - 1) с интенсивностью . Из вышеизложенного заключаем, что искомые величины определяются следующим образом: случаи (h, l) е E - Ea : Xh, q((h, l ),(h', l')) =0, h = h-1,l =l, если l >0, h =h,l =l; (4) случаи (h, l) е Ea : q((h, l ),(h', l')) = 0, h = h -1,l = l, если l > 0, h = h,l = l. (5) Из соотношений (4) и (5) заключаем, что построенная конечная 2D MC является неприводимой, т.е. при любых положительных значениях исходных параметров системы в ней существует стационарный режим (см. рис. 1). Пусть p (h,l) обозначает вероятность состояния (h,l)е E . Эти вероятности находятся в результате решения соответствующей системы уравнений равновесия (СУР), которая составляется на основе соотношений (4), (5). Из-за очевидности составления явный вид этой СУР здесь не приводится. После нахождения стационарных вероятностей состояний изучаемой 2D MC можно вычислить искомые характеристики системы. Так, h-заявки теряются лишь тогда, когда в моменты их поступления в системе уже имеется Kh заявок данного типа, т.е. вероятность потери h-заявок (PBh) определяется следующим образом: Kl PBh = ^Р (Kh, l). (6) l=0 Для вычисления вероятности потери l-заявок следует рассматривать состояния типа (h, Kl), при этом необходимо различать два случая: (1) 0 < h < rh ; (2) < h < Kh . Если в момент поступления l-заявки имеет место случай (1), то она теряется с вероятностью 1 -а, а в случае (2) эта заявка теряется с вероятностью 1. Таким образом, вероятность потери l-заявок (PBj) определяется следующим образом: PB, = (1 -а) V p (h, Kt )+Ep (h, Kt). (7) h =0 h=rh Скачки l-заявок в h-буфер происходят в моменты поступления l-заявок с вероятностью а, если в эти моменты система находится в состоянии (h, l)е Ea . Иными словами, средняя интенсивность скачков l-заявок в h-буфер (RJlh) вычисляется как RJih =Xiа Е Е Р (h, l). l=rl +1h=0 Средние количества h-заявок (Nh) и l-заявок (Nt) в системе определяются как математические ожидания соответствующих с.в., т.е. Nh = §h Xp (h, l), h=1l=0 Nl Ep(h,l). l=1h=0 Средние времена ожидания в очереди h-заявок (Wh) и l-заявок (Wt) вычисляются из модифицированной формулы Литтла: Wx = Nx/Xx (1 - PBx ) , x e{h, lJ. Отметим, что указанная выше СУР для стационарных вероятностей состояний изучаемой 2D MC представляет собой систему линейных алгебраических уравнений размерности (Kh+1)(Kl+1), и поскольку изучаемая 2D MC является неприводимой, то при любых положительных значениях исходных параметров она всегда имеет единственное решение. Для решения СУР могут быть использованы известные численные методы линейной алгебры, которые реализованы в доступных пакетах прикладных программ. Ниже описан разработанный приближенный метод нахождения стационарных вероятностей состояний для моделей высокой размерности, т.е. когда величина KhKl имеет большое значение. Такой подход ранее использован в работе [8]. Как и в работе [8], принимается допущение о том, что интенсивность h-запросов намного больше, чем интенсивность l-запросов, и рассматривается следующее расщепление ПС (1): Kl E = U El , ЕЛ\\Е, =0, l1 * l2, (12) l=0 1 2 гдеE, = {(h,l) e E: h = 0Kh J ,l = 0K Принятие допущения о том, что Xh >> Xz позволяет корректно использовать подход, основанный на принципах фазового укрупнения состояний 2D MC, так как при выполнении этого допущения в расщеплении (12) интенсивности переходов между состояниями внутри классов El,l =1, Kl, намного превосходят интенсивности переходов между состояниями из разных классов (см. рис. 1). Далее все состояния внутри каждого класса El объединяются в одно укрупненное состояние Q = {< l >:l = 0,Kl}. При- < l >, и, таким образом, определяется множество укрупненных состояний ближенные значения вероятностей состояний p (h, l), (h, l)e E исходной модели определяются [8]: p(h, I) = Pl (h)n(< I >) , (13) где p (h) - вероятность состояния (h, l) внутри расщепленной модели с пространством состояний E, а я(< l >) - вероятность укрупненного состояния < l > e Q . При вычислении вероятностей состояний внутри расщепленных моделей необходимо различать следующие случаи: 1) 0 < l < ц; 2) ц +1 < l < KL . В первом случае вероятности состояний внутри всех расщепленных моделей с пространством состояний E ,0 < l < Г, совпадают с вероятностями состояний классической модели одноканальной СМО с ограниченным буфером M(Xh) / M (цF )/1/Kh (см. рис. 1), т.е. Pl(h) = vh (1 -v)/(1 -vK-1), h = 0,Кл, (14) где v = X h/ц f . Во втором случае вероятности состояний внутри всех расщепленных моделей с пространством состояний E , r < l < K , совпадают с вероятностями состояний одномерного процесса размножения-гибели с переменными интенсивностями (см. рис. 1), т.е. Pl (h )=< если 0 < h< rh, если rh - 1 < h < Kh , (15) где Pl (0) находится из условия нормировки, т.е. Kh 2 Pl (h ) = 1. h=0 Используя соотношения (4), (5), (14) и (15), после определенных математических выкладок находим, что интенсивности переходов между укрупненными состояниями вычисляются следующим образом: q(< l >, < h >) ~ Xl, если 0 < l1 < r, l2 = l1 -1, если r -1 < l1 < KL, l2 = l1 -1, если l2 = l1 -1, (16) где Xl = X f(1 -a) z'pli (h)+§ Pli (h) . C h=0 1 h=rh * ' ) Таким образом, из (16) находим вероятности укрупненных состояний: 0Zл(< 0 >), если 0 < l < r, л(< l >) = ), если rl- 1 < l < Kl, (17) где 0 = X Jцs, и вероятность л(< 0 >) находится из условия нормировки, т.е. Kl 2 я(< l >)=1. l=0 С учетом соотношений (14)-(17) из (13) определяются приближенные значения вероятностей состояний исходной 2D MC, и далее после определенных математических преобразований находятся следующие явные формулы для вычисления характеристик (6)-(10) системы с раздельными очередями: rl Kl pbh "p (Kh)Ел()+Pr+i Ел(); (18) l=0l=rl +1 < rh -1 Kh > pbl «4) (1 -a)£pKl (h)+£pk (h) ; (19) V h=0 h=rh 7 (rh -1 > ( Kl l rjlh ~^ia ZX (h)• Z4) ; (20) Vh=07Vl=rl +17 KhKl Nh -Z hZp, (h H); h=1l=0 (21) Kl N «z 14< l >). l=1 (22) Замечание 1. При выводе формул (18) и (20) существенным образом учитывается, что pr (h) = pr (h),0 < l’,1"< r и pz,(h) = pr (h),r +1 < 1',1"< Kl для любого h = 0,1,...,Kh. Приближенные значения средних времен ожидания в очереди разнотипных заявок определяются из (11), (18), (19), (21) и (22). Теперь рассмотрим систему с бесконечным размером буфера. В данной модели все допущения предыдущей модели остаются без изменений, однако здесь невозможны потери заявок. Это означает, что скачкообразные приоритеты определяются по формуле (1) и пространство состояний модели определяется аналогично (2). При этом здесь учитывается, что K = КА = • Элементы производящей матрицы полученной бесконечномерной 2D MC определяются из соотношений (4) и (5). Существование стационарного режима устанавливается ниже. В отличие от модели с конечными буферами здесь не удается использовать СУР для стационарных вероятностей состояний, поэтому следует разработать альтернативный метод. Использование метода двумерных производящих функций для данной модели сталкивается с известными техническими и методологическими трудностями, и потому этот подход также не является эффективным. Вместе с тем предложенный выше подход может быть использован и для данной модели. Поскольку он подробно изложен выше, то его применение описывается кратко. Аналогично (12) рассматривается расщепление исходного пространства состояний и вычисляется стационарное распределение внутри классов E,l= 0,1, 2,... В случае 0 r, где p ( 0 ) находится из условия нормировки, т.е. Pi (0 )= С X 1 +--а X.. rh 7 1 -v 7 Используя соотношения (4), (5), (23) и (24) находим, что в данной модели интенсивности переходов между укрупненными состояниями вычисляются по формуле (16), где указанный там параметр X, i > r, здесь определяется как ( rh -1 A Xi = XZ 1 -a^Pi (h) . V h=0 7 Следовательно, стационарные вероятности укрупненых состояний существуют, если выполняется условие у < 1 , где у = Х/ц . Если последнее условие выполняется, то вероятности укрупненных состояний вычисляются аналогично формуле (17), где во второй строке условие r +1 i K заменяется условием i > r . Кроме того, здесь я(< 0 >) определяется так: 7 < к л(< 0 >) = Еуi + £/ Ii =0 k kXi 7 -1 уri 1 -у 7 Объединяя условия v) i=1 уr‘+1 (1 + rt (1 - у))Л + (1 -у)2 (28) Приближенные значения средних времен ожидания в очереди разнотипных заявок определяются из классической формулы Литтла с использованием (27) и (28). Отметим, что в формулу (27) входит бесконечный ряд, и, к сожалению, не удается найти явную формулу для вычисления его суммы. Однако эту сумму можно вычислить приближенно. Для этого покажем, что ряд сходится. Действительно, из (27) заключаем, что ад Nh Е hmax {р0 (h), Рг, +1 (h)} • h=1 Отсюда следует, что если max {р0 (h), рГ/+1 (h )} = p0 (h) ад то мажорантный ряд Е hp0(h) сходитh=1 ад ся, так как Е hp0 (h )=v/0 -v); h=1 ад Если max {p0 ( h), pr/+1 ( h)} = pr/+1 ( h), то мажорантный ряд Е hpr+1 ( h) h=1 также сходится, так как Е hpri+1 (h) = рп+1 (0А ^*+х'а h=1iiIh=0 k ад Е1 Иными словами, ряд в правой части формулы (27) всегда сходится, так как соответствующие мажорантные ряды сходятся. Потому для ее суммы можно использовать метод отсечения хвоста ряда, т.е. верхнюю границу суммы можно заменить достаточно большой (конечной) величиной, далее ее нужно постепенно увеличивать, и эту процедуру следует продолжать до тех пор, пока значения соответствующей суммы практически перестают изменяться. 3. Численные результаты Основной целью проводимых здесь численных экспериментов является изучение зависимостей характеристик системы от значений вводимых параметров скачкообразных приоритетов rh и rl, а также решение задачи нахождения оптимальных значений этих параметров относительно выбранного критерия качества работы системы (из-за ограниченности объема работы результаты, которые показывают высокую точность разработанных приближенных формул, здесь не приводятся. Отметим, что аналогичные показатели соответствуют результатам, полученным в работах [6-11]). Сначала рассмотрим результаты для модели с конечными очередями. На рис. 2-5 показаны зависимости характеристик системы от параметра rl при фиксированных значениях параметра rh, где символ «х» соответствует случаю rh = 5, а символ «◊» - rh = 10. Исходные параметры системы выбирались следующими: Xh = 30, Xl = 15, цf = 35, ц = 10,а = 0,5, Kh = 20, Kl = 35. Рис. 2. Зависимость вероятности потери h-заявок (а) и /-заявок (b) от параметра ri в модели с конечными буферами Fig. 2. Dependence of the probability of losing h-orders (a) and l-orders (b) on the parameter rl in the model with finite buffers Рис. 3. Зависимость среднего числа h-заявок (а) и /-заявок (b) от параметра г/ в модели с конечными буферами Fig. 3. Dependence of the average number of h-requests (a) and /-requests (b) on the parameter r/ in the model with finite buffers Рис. 4. Зависимость среднего времени ожидания в очереди A-заявок (а) и /-заявок (b) от параметра rl в модели с конечными буферами Fig. 4. Dependence of the average waiting time in the queue of A-customers (a) and /-customers (b) on the parameter r/ in the model with finite buffers Рис. 5. Зависимость средней интенсивности скачков /-заявок в A-буфер от параметра r/ в модели с конечными буферами Fig. 5. Dependence of the average intensity of jumps of /-orders into the A-buffer on the parameter r/ in the model with finite buffers Видно, что функция PB является невозрастающей, при этом ее значения растут с ростом значений параметра rA. (см. рис. 2, а) Этого следовало ожидать, так как с ростом значений параметра r/ /-заявки реже переходят в A-буфер, и тем самым увеличиваются шансы A-заявок для доступа в свой буфер. Также ожидаемым является тот факт, что с ростом значений параметра rA вероятность потери A-заявок растет, так как с ростом указанного параметра растут шансы поступления /-заявок в A-буфер, и тем самым уменьшаются шансы A-заявок для доступа в свой буфер. Обратная картина наблюдается для функции PBl , т.е. эта функция является неубывающей, при этом ее значения уменьшаются с ростом значений параметра rA (см. рис. 2, b). Такое поведение этой функции также является логичным, так как с ростом значений параметра r/ уменьшаются шансы заявок данного типа для доступа в A-буфер, и тем самым уменьшаются их шансы для доступа в свой буфер. Заметим, что с ростом значений параметра rA вероятность потери /-заявок уменьшается, так как с ростом указанного параметра растут шансы /-заявок для доступа в A-буфер, и тем самым увеличиваются шансы заявок данного типа для доступа в систему (либо в свой буфер, либо в A-буфер). Функция NA является невозрастающей (см. рис. 3, а), так как с ростом параметра r/ уменьшается интенсивность перехода /-заявок в A-буфер, и тем самым уменьшается среднее число A-заявок в системе. При этом значения этой функции растут с ростом параметра rh, так как с ростом этого параметра растет интенсивность перехода /-заявок в h-буфер, и потому растет среднее число h-заявок в системе. Здесь, как и выше, обратная картина наблюдается для функции Nl, так как с ростом параметра п уменьшается интенсивность перехода /-заявок в h-буфер, и тем самым увеличивается среднее число /-заявок в системе. При этом значения этой функции уменьшаются с ростом параметра rh, так как с ростом этого параметра растет интенсивность перехода /-заявок в h-буфер, и потому уменьшается среднее число /-заявок в системе. Функция Wh является невозрастающей, так как с ростом параметра r/ уменьшается число h-заявок в системе, при этом уменьшается вероятность их потери (см. формулы (11)); ее значения растут с ростом параметра rh, так как с ростом этого параметра растут шансы /-заявок на переход в h-буфер, и тем самым увеличивается время ожидания в очереди h-заявок (см. рис. 4, а). Поскольку с ростом параметра г/ уменьшаются шансы /-заявок для перехода в h-буфер, то функция Wh является неубывающей, ее значения уменьшаются с ростом параметра rh, так как в связи с ростом интенсивности переходов /-заявок в h-буфер уменьшается время ожидания в очереди /-заявок (см. рис. 4, b). Функция RJ lh является невозрастающей, так как с ростом параметра r/ уменьшается интенсивность перехода /-заявок в h-буфер, при этом ее значения растут с ростом параметра rh, так как с ростом этого параметра растут шансы /-заявок на переход в h-буфер (см. рис. 5). Рассмотрим результаты для модели с бесконечной очередью. Соответствующие графики показаны на рис. 6. Здесь исходные параметры системы выбираются так: \\h= 45, \\= 15, = 60, = 15, а = 0,5. Как и выше, представлены зависимости характеристик системы от параметра r/ при фиксированных значениях параметра гк, символ «х» соответствует случаю rh = 5, а символ «◊» - rh = 10; параметр r/ принимает значения в интервале [1, 35]. Как и в случае модели с конечными сепаратными буферами, здесь также функция Nh является невозрастающей (см. рис. 6, а), а функция N/ строго возрастает относительно изменения параметра r/ (см. рис. 6, b). При этом с ростом параметра r/ значения функции Nh при различных значениях параметра rh почти сопадают, а значения функции N/ при различных значениях параметра rh существенным образом отличаются друг от друга при больших значениях параметра r/. В данной модели функция RJlh также является невозрастающей, так как с ростом параметра r/ уменьшается интенсивность изменения приоритета /-заявок, при этом ее значения растут с ростом параметра rh, так как с ростом этого параметра растут шансы изменения приоритета /-заявок; здесь с ростом параметра r/ значения функции RJ при различных значениях параметра rh почти сопадают (см. рис. 6, c). Характеры изменения указанных функций объясняются аналогично модели с конечными сепаратными буферами. Рис. 6. Зависимость средннее число h-заявок (а), /-заявок (b) и средней интенсивности скачков /-заявок в h-буфер (с) от параметра п в модели с бесконечным буфером Fig. 6. Dependence of the average number of h-customers (a), /-customers (b) and the average intensity of jumps of /-customers into the h-buffer (с) on the parameter r/ in the model with an infinite buffer В конце данного раздела отметим, что все показатели качества обслуживания системы имеют монотонный характер относительно параметров введенных скачкообразных приоритетов. Эти факты позволяют нам сформулировать и решить различные задачи по их улучшению. Так, например, можно найти такие значения указанных параметров, чтобы минимизировать вероятности потери заявок определенного типа (или взвешенной суммы вероятностей потери разнотипных заявок) при заданных ограничениях на другие показатели. Для конкретности изложения здесь рассматривается задача минимизации суммарных штрафов (Total Cost, TC), связанных с функционированием системы с сепаратными конечными буферами. Предположим, что размеры буферов, а также нагрузочные параметры системы являются фиксированными величинами. Параметрами оптимизации являются пороговые параметры rh и rl. В стационарном режиме суммарные штрафы определяются следующим образом: TC(rh,rl ) = cJPRJ (rh,rl )+XhclhPBh (rh,rl )+XlcllPBl (rh,rl )+cwhNh (rh,rl )+cwlNl (rh,rl ), (29) где cJP - цена одного скачка из /-очереди в h-очередь; clh (/-запроса); cwh (cwl) - цена единицы времени пребывания в системе одного h-запроса (/-запроса). (еи) - штрафы за потери одного h-запроса Следовательно, задача оптимизации записывается так: (rh* , rl* ) =arg min TC(rh,rl ). (30) (rh,rl) Поскольку множество допустимых решений является дискретным и конечным, то при любых значениях входных параметров задача (30) имеет решение. В таблице приводятся результаты решения задачи (30) для моделей обеих типов со следующими исходными данными: " = 25," = 35, = 30, = 20, а = 0,7. Коэффициенты в выражении функционала (29) выбирались так же, как в работе [6]: cJP = 0,5, clh = 3, cll = 2, cwh = 0,7, cwl = 0, 2. Решения задачи (30); TC - минимальное значение TC K, Kt) (г* r ) TC PBh PBi Nh N/ Wh W/ RJ (10, 10) (9, 10) 18,159 0,031 0,149 3,289 8,690 0,127 0,211 10,472 (10, 15) (9, 15) 18,152 0,031 0,149 3,289 13,669 0,127 0,332 10,451 (10, 20) (9, 20) 18,175 0,031 0,149 3,289 18,667 0,127 0,454 10,449 (15, 10) (12, 10) 15,403 0,011 0,147 4,085 8,690 0,162 0,211 8,159 (15, 15) (12,15) 15,399 0,011 0,147 4,085 13,669 0,162 0,332 8,143 (15, 20) (12, 20) 15,422 0,011 0,147 4,085 18,667 0,162 0,454 8,142 (20, 10) (15, 10) 13,976 0,004 0,142 4,533 8,690 0,181 0,213 7,051 (20, 15) (15,15) 13,973 0,004 0,142 4,533 13,669 0,181 0,335 7,037 (20, 20) (15,20) 13,996 0,004 0,142 4,533 18,667 0,181 0,458 7,036 Анализ результатов оптимального решения задачи (30) позволяет сделать следующие выводы (эти выводы относятся исключительно к выбранным ранее исходным данным). - Значение параметра rl* = Kl, при этом даже двукратное увеличение объема буфера для * /-заявок не влияет ни на оптимальное значение параметра r , ни на оптимальное значение суммарных штрафов; вместе с тем увеличение объема буфера для h-заявок приводит к существенному уменьшению (более 20%) оптимального значения суммарных штрафов. - Значение вероятности потери /-заявок почти не зависит от объемов буферов, однако значения вероятности потери h-заявок существенным образом уменьшаются с ростом объема буфера для таких заявок. - Среднее число h-заявок меньше 30% от всего объема h-буфера, однако соответствующий показатель для /-заявок составляет более 80%. - Среднее время ожидания в очереди h-заявок почти не зависит от объема буфера для /-заявок, однако соответствующий показатель для /-заявок зависит от размеров обоих буферов. При этом, как ожидалось, с ростом объема l-буфера этот показатель растет существенным образом, т.е. двукратное увеличение l-буфера приводит к почти двукратному увеличению этого показателя. - Значения функции RJ почти не зависят от объема буфера для l-заявок. Этот факт объясняется тем, что в оптимальном решении rz = K, т.е скачки l-заявок в h-буфер происходят лишь тогда, когда l-буфер является полностью заполненым. Заключение Предложены марковские модели систем обслуживания с гетерогенными серверами и конечными раздельными очередями разнотипных заявок, а также с общим буфером бесконечного размера при наличии зависящих от состояния системы скачкообразных приоритетов. Определена новая схема назначения рандомизированных скачкообразных приоритетов, которые зависят от текущего состояния системы. Переход заявки низкого приоритета к очереди заявок высокого приоритета осуществляется согласно схеме Бернулли лишь тогда, когда в момент поступления заявки низкого приоритета число заявок данного приоритета выше определенной величины и при этом число заявок высокого приоритета меньше заданной величины. Показано, что математическими моделями изучаемых систем являются двумерные цепи Маркова, и предложены алгоритмы построения производящих матриц этих цепей. Разработаны точный и приближенный методы расчета стационарных вероятностей состояний изучаемых цепей и получены формулы для вычисления характеристик системы. Решена задача нахождения оптимальных значений параметров введенных скачкообразных приоритетов для минимизации суммарных штрафов системы.

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