Многоканальные системы с динамическим приоритетом
Запропоновано алгоритм розрахунку багатоканальних систем з динамічним пріоритетом, що лінійно зростає з часом очікування. Наведено результати роботи алгоритму. The algorithm is proposed to compute mean waiting times in multi-channel queuing system with priorities linearly increasing during waiting t...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2009 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/210376 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Многоканальные системы с динамическим приоритетом / Ю.И. Рыжиков // Проблемы управления и информатики. — 2009. — № 4. — С. 106-110. — Бібліогр.: 14 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860218496505348096 |
|---|---|
| author | Рыжиков, Ю.И. |
| author_facet | Рыжиков, Ю.И. |
| citation_txt | Многоканальные системы с динамическим приоритетом / Ю.И. Рыжиков // Проблемы управления и информатики. — 2009. — № 4. — С. 106-110. — Бібліогр.: 14 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Запропоновано алгоритм розрахунку багатоканальних систем з динамічним пріоритетом, що лінійно зростає з часом очікування. Наведено результати роботи алгоритму.
The algorithm is proposed to compute mean waiting times in multi-channel queuing system with priorities linearly increasing during waiting time. Numerical results are presented.
|
| first_indexed | 2025-12-07T21:25:20Z |
| format | Article |
| fulltext |
© Ю.И. РЫЖИКОВ, 2009
106 ISSN 0572-2691
УДК 519.872
Ю.И. Рыжиков
МНОГОКАНАЛЬНЫЕ СИСТЕМЫ
С ДИНАМИЧЕСКИМ ПРИОРИТЕТОМ
Постановка задачи. Задачи управления сложными техническими комплек-
сами в реальном времени обычно требуют использования многомашинных или
многопроцессорных систем как из соображений производительности, так и
с учетом требований надежности и организации технического обслуживания. Раз-
личия в важности задач, их трудоемкости и требованиях к оперативности решения
приводят к необходимости введения приоритетных дисциплин обслуживания,
сложность анализа которых резко возрастает при переходе к многоканальным си-
стемам. Такие задачи обычно решаются лишь в простейшем (экспоненциальном)
случае, причем средние длительности обслуживания предполагались различными
буквально в единичных работах [1–4]. Решение (методом производящих функций)
оказывалось весьма громоздким и неконструктивным.
А.Д. Хомоненко [5] предложил рассчитывать фазовую аппроксимацию си-
стемы с абсолютным приоритетом и двумя классами заявок с экспоненциальным
обслуживанием итерационным методом Такахаси–Таками [6–8]. Отказ от замены
показательными законами распределений длительности обслуживания суще-
ственно усложняет диаграммы переходов. Еще сложнее анализ многоканальных
систем в случае относительных приоритетов. Здесь редуцированная схема требует
учета трех потоков — данного ( j-го) и двух объединенных высших и низших при-
оритетов соответственно. Заметим, что при группировании типов заявок необхо-
дим переход к средневзвешенному распределению обслуживания, которое при
различных экспоненциальных составляющих аппроксимировать показательным
законом с приемлемой погрешностью нельзя. Практическую ценность могут
иметь только алгоритмы, обобщенные в указанных направлениях. Добавим к это-
му, что все попытки создания реально применимых методик, учитывающих нахо-
дящиеся в каналах и в очередях количества заявок каждого вида, заведомо обре-
чены на неудачу в связи с непомерным разрастанием размерности пространства
состояний. В [9] автору удалось получить алгоритмы приближенного расчета по-
добных систем для относительного приоритета и абсолютного (прерывающего)
с дообслуживанием, так что проблему расчета многоканальных приоритетных си-
стем со статическим приоритетом в первом приближении (на уровне средних зна-
чений) можно считать решенной.
Реальные процессы обслуживания, естественно, требуют их подстройки под
реальную ситуацию. Простейшая форма такой подстройки — динамический при-
оритет. В этом случае диспетчерский приоритет каждой заявки растет как извест-
ная функция времени ее ожидания, что исключает непомерно большие задержки
даже для заявок низкоприоритетных классов. В частности, эта форма приоритета
представляется наиболее целесообразной в социальной сфере. Задачи расчета од-
ноканальной системы с динамическим приоритетом решались в [10, 11], причем в
обоих случаях были допущены ошибки (разные), исправленные в [12]. В данной
статье делается попытка объединить методы [9, 12] для расчета многоканальных
систем с динамическим приоритетом по времени ожидания. Точность расчетов
иллюстрируется сопоставлением с результатами имитационного моделирования.
Компоненты задержки. Рассмотрим простейший вариант поставленной за-
дачи — расчет средних времен ожидания без прерывания начатого обслуживания
Проблемы управления и информатики, 2009, № 4 107
при линейном росте диспетчерских приоритетов с угловыми коэффициентами
},{ j .21 k Среднее время ожидания j-заявки будет суммой четырех
средних:
2/2,
1
0 ii
k
i
bS
— завершение ближайшего начатого обслуживания;
ii
j
i
iii
j
i
wbwS
1
1,
1
1 — ожидание обслуживания ранее пришедших за-
явок приоритетов ji ,1 (их j-заявка обгонять не может);
2S — ожидание обслуживания заявок приоритетов ,1,1 ji которые при-
были после меченой j-заявки и успевают ее обогнать;
3S — ожидание обслуживания ранее пришедших заявок типов ,,1 kji
которые j-заявка обгонять может, но не успевает.
Для определения 2S и 3S рассмотрим графики возрастания диспетчерских
приоритетов, где началу координат соответствует момент прихода в систему ме-
ченой j-заявки (рис. 1).
0
i j
j
Wj
t
i
Ti
0
i j
j
Wj
t
i
Ti
а б
Рис. 1
Из предельного условия (рис. 1, а) равенства динамических приоритетов
в момент jW выбора j-заявки на обслуживание находим ,)( jjiij WTW от-
куда следует выражение для критического момента поступления i-заявки
)./1( jjji WT Заявка типа i, пришедшая не более чем на iT позже меченой,
успевает ее обогнать. Математическое ожидание числа i-заявок, обогнавших ме-
ченую, составит );/1( ijji w для получения времени их обработки найден-
ное число заявок должно быть умножено на ./1, nbi Значит,
.)/1(/)/1(
1
1
1,
1
1
2 i
j
i
ijjii
j
i
ijj wnbwS
В свою очередь, меченая заявка сама может обгонять ранее пришедшие (типов
i j ) , которые имеют по отношению к ней опережение меньше iT (рис. 1, б).
Очевидно, ,)( jjjii WWT откуда ).1/( ijji WT Ожидаемая длитель-
ность обработки системой прибывших за это время низкоприоритетных заявок
равна
).1/()1/(
11
1,
ij
k
ji
ijij
k
ji
ii
j w
n
b
w
108 ISSN 0572-2691
Общая ожидаемая задержка по заявкам этих типов составит .
1
ii
k
ji
w
Таким об-
разом, дополнительная задержка j-заявок из-за менее приоритетных
).1/(
11
3
iji
k
ji
jii
k
ji
wwS
Объединяя найденные составляющие в условие баланса объема работы, имеем
k
ji
ijij
k
ji
ii
j
i
ijij
j
i
iij wwwwSw
11
1
11
0 ).1/()/1(
Далее,
k
i
iij
k
i
jjiijj
ji ji
iijiiji
k
ji
j
i
iji
RR
11
1
1
1
.///
/)1/()/1(
Теперь условие баланса можно переписать в форме
k
i
k
i
iijjiij RwwSw
1 1
0 ./
Итоговая формула
k
i
iij
k
i
ii
j
R
wS
w
1
1
0
/1
оказывается неожиданно простой. Она исправляет ошибки, допущенные в [10, c. 158]
и [11, с. 103] и, в отличие от названных источников и [13], не требует рекуррент-
ного счета. Отметим в заключение, что коэффициенты }{ j фактически входят в
эту формулу через их отношения, так что один из них можно выбрать произволь-
но (например, положить ).11 Осталось найти эффективные способы вычисле-
ния 0S и .
1
k
i
iiw
Инвариант Клейнрока. В работе [10] утверждается, что в классе консерва-
тивных дисциплин обслуживания, реализация которых не задает системе допол-
нительной работы, интересующая нас сумма ii
k
i
w
1
инвариантна. Автор с по-
мощью надежно отлаженных программ для одноканальных моделей убедился
в строгой справедливости этого инварианта для относительных приоритетов и
очень малой погрешности — для приоритета с прерыванием и дообслуживанием
(погрешность была нулевой для показательных распределений времени обслужи-
вания, а для прочих не превышала десятых долей процента). Имитационное моде-
лирование подтвердило это и для n-канальных систем. На этом основании считаем
,
1
RWwii
k
i
где R — суммарный коэффициент загрузки, а W — среднее время
ожидания, которое можно подсчитать для средневзвешенных трудоемкостей за-
явок с помощью известного [7, 9] алгоритма анализа модели nHM // 2 .
Проблемы управления и информатики, 2009, № 4 109
Среднее время до ближайшего обслуживания. Попробуем найти .0S Вы-
числим средневзвешенные моменты распределения длительности обслуживания
k
i
jiij bb
1
, ,/ .3,1j Здесь }{ , jib — j-е моменты распределения длительно-
сти обслуживания i-заявки, а — суммарная интенсивность потока заявок. По
этим моментам найдем средневзвешенные моменты остаточной длительности
обслуживания ],)1[(/
~
11 bjbb jj ,2,1j и аппроксимируем распределение
остаточной длительности законом Вейбулла с дополнительной функцией распреде-
ления (ДФР) .)/(exp)( TttF Моменты этого распределения
),/1(/ jTf j
j .,2,1 j При обслуживании без прерывания среднее вре-
мя ожидания вновь прибывшей заявкой ближайшего завершения обслуживания
.)]([)( 1
n
n tFtF Интересующий нас результат .)(
0
dttFW n
Применяя эти формулы к ДФР Вейбулла, приходим к распределению того же
типа с пересчитанным параметром nTTn / и прежней . Соответственно инте-
ресующее нас среднее время ожидания завершения ближайшего обслуживания в
n-канальной системе
)./11()/()( /1 nTnW
Легко убедиться, что при переходе к n каналам уменьшение среднего времени
ожидания .)(/)1( /1 nnWW Ожидание завершения текущего обслуживания
имеет место с вероятностью
1
0
,1
n
i
ip где }{ ip — вероятности наличия в си-
стеме i заявок, определяемые расчетом вышеупомянутой модели .// 2 nHM
Итак, .1
1
0
/1
1
0
n
i
i
n
p
b
S
Сопоставление результатов. Предложенная расчетная схема была запро-
граммированы на Фортране 77 для потока заявок трех типов. Обслуживание
предполагалось регулярным с длительностями 2, 3 и 6; скорости роста приорите-
тов 1, 0,7 и 0,5; доли заявок по типам 0,0968, 0,2581, 0,6451. Суммарная интенсив-
ность потока задавалась выражением 0,155n, что обеспечивало коэффициент за-
грузки 0,75. Необходимые расчеты бесприоритетных и одноканальных приоритет-
ных систем выполнялись на расширенной и переведенной на Фортран версии
пакета МОСТ [14]. В качестве эталонных использовались результаты имитационно-
го моделирования многоканальных систем при 200 тыс. наблюдений по заявкам
высшего приоритета. Результаты раcчета систем с динамическим приоритетом со-
ответственно для 31 ww приведены в таблице (программа Dynpr1 обеспечивает
расчет одноканальной системы согласно [9], Dynprn — многоканальной системы
по обсуждаемому здесь алгоритму, Dynimit — ее имитационное моделирование).
Таблица
n Dynpr1 Dynprn Dynimit
1 4,8685 6,5313 8,4568 4,8677 6,5301 8,4552 5,2695 6,6767 8,4722
2 — — — 2,2660 3,0399 3,9360 2,3992 2,9578 3,6959
3 — — — 1,4084 1,8894 2,4464 1,4521 1,7857 2,2065
Результаты аналитических методик для одноканального случая практически
совпадают (разница объясняется погрешностями выравнивания моментов распре-
110 ISSN 0572-2691
делением Вейбулла и гиперэкспоненциальной аппроксимацией при обсчете моде-
ли ).1// 2HM Согласованность аналитических методик с имитационной моделью
с учетом статистических погрешностей последней и неидеальности датчиков слу-
чайных чисел следует признать вполне удовлетворительной.
Ю.І. Рижиков
БАГАТОКАНАЛЬНІ СИСТЕМИ
З ДИНАМІЧНИМ ПРІОРИТЕТОМ
Запропоновано алгоритм розрахунку багатоканальних систем з динамічним
пріоритетом, що лінійно зростає з часом очікування. Наведено результати ро-
боти алгоритму.
Ryzhikov Yu.I.
MULTI-CHANNEL QUEUING SYSTEMS
WITH DYNAMIC PRIORITY
The algorithm is proposed to compute mean waiting times in multi-channel queuing
system with priorities linearly increasing during waiting time. Numerical results are
presented.
1. Лысенкова В.Т. Исследование многолинейных систем массового обслуживания с ограни-
ченным накопителем и приоритетами : Автореф. … канд. дис. — М. : Ин-т проблем пере-
дачи информации. — 1973. — 16 с.
2. Томашевский В. Л. Многоканальные приоритетные системы массового обслуживания : Ав-
тореф. … канд. дис. — М. : МГУ, 1986. —14 с.
3. Gail H.R., Hantler S.L., Taylor B.A. Analysis of a non-preemptive priority multiserver queue //
Advances in Appl. Prob. — 1988. — 20. — P. 852.
4. Miller D.R. Steady-state algorithmic analysis of M / M / c two priority queues with heterogeneous
rates // Applied Probability — Computer Science: the Interface. — Boston : Birkhauser, 1982. —
2. — P. 207–222.
5. Хомоненко А.Д. Вероятностный анализ приоритетного обслуживания с прерываниями в
многопроцессорных системах // Автоматика и вычислительная техника. — 1990. — № 2. —
C. 55–61.
6. Рыжиков Ю.И. Алгоритм расчета многоканальной системы с эрланговским обслуживани-
ем // Автоматика и телемеханика. — 1980. — № 5. — С. 30–37.
7. Рыжиков Ю.И., Хомоненко А.Д. Итеративный метод расчета многоканальных систем с
произвольным распределением времени обслуживания // Проблемы управления и теории
информации. — 1980. — № 3. — С. 32–38.
8. Takahashi Y., Takami Y. A numerical method for the steady-state probabilities of a GI / G / c
queuing system in a general class // J. of the Oper. Res. Soc. of Japan. — 1976. — 19, N 2. —
P. 147–157.
9. Рыжиков Ю.И. Средние времена ожидания и пребывания в многоканальных приоритетных
системах // Информационно-управляющие системы. — 2006. — № 6 (25). — С. 43–49.
10. Клейнрок Л. Вычислительные системы с очередями / Пер. с англ. — М. : Мир, 1979. —
600 с.
11. Основы теории вычислительных систем / Под ред. С.А. Майорова. — М. : Высш. шк.,
1978. — 408 с.
12. Рыжиков Ю.И. Компьютерное моделирование систем с очередями: Курс лекций. — СПб. :
ВКА им. А.Ф. Можайского, 2007. — 164 с.
13. Балыбердин В.А. Методы анализа мультипрограммных систем. — М. : Радио и связь,
1992. — 152 с.
14. Рыжиков Ю.И. Руководство по расчету систем с очередями на базе пакета МОСТ/FPS1:
Уч.-метод. пособие. — СПб. : ВКА им. А.Ф. Можайского, 2007. — 92 с.
Получено 05.05.2009
Статья представлена к публикации членом редколлегии Юсуповым Р.М.
|
| id | nasplib_isofts_kiev_ua-123456789-210376 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-17T12:03:47Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Рыжиков, Ю.И. 2025-12-06T15:09:28Z 2009 Многоканальные системы с динамическим приоритетом / Ю.И. Рыжиков // Проблемы управления и информатики. — 2009. — № 4. — С. 106-110. — Бібліогр.: 14 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210376 519.872 10.1615/JAutomatInfScien.v41.i8.50 Запропоновано алгоритм розрахунку багатоканальних систем з динамічним пріоритетом, що лінійно зростає з часом очікування. Наведено результати роботи алгоритму. The algorithm is proposed to compute mean waiting times in multi-channel queuing system with priorities linearly increasing during waiting time. Numerical results are presented. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки информации Многоканальные системы с динамическим приоритетом Багатоканальні системи з динамічним пріоритетом Multi-channel queuing systems with dynamic priority Article published earlier |
| spellingShingle | Многоканальные системы с динамическим приоритетом Рыжиков, Ю.И. Методы обработки информации |
| title | Многоканальные системы с динамическим приоритетом |
| title_alt | Багатоканальні системи з динамічним пріоритетом Multi-channel queuing systems with dynamic priority |
| title_full | Многоканальные системы с динамическим приоритетом |
| title_fullStr | Многоканальные системы с динамическим приоритетом |
| title_full_unstemmed | Многоканальные системы с динамическим приоритетом |
| title_short | Многоканальные системы с динамическим приоритетом |
| title_sort | многоканальные системы с динамическим приоритетом |
| topic | Методы обработки информации |
| topic_facet | Методы обработки информации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/210376 |
| work_keys_str_mv | AT ryžikovûi mnogokanalʹnyesistemysdinamičeskimprioritetom AT ryžikovûi bagatokanalʹnísistemizdinamíčnimpríoritetom AT ryžikovûi multichannelqueuingsystemswithdynamicpriority |