научная статья по теме СИСТЕМА МАССОВОГО ОБСЛУЖИВАНИЯ С ОТРИЦАТЕЛЬНЫМИ ЗАЯВКАМИ И БУНКЕРОМ ДЛЯ ВЫТЕСНЕННЫХ ЗАЯВОК В ДИСКРЕТНОМ ВРЕМЕНИ Автоматика. Вычислительная техника

Текст научной статьи на тему «СИСТЕМА МАССОВОГО ОБСЛУЖИВАНИЯ С ОТРИЦАТЕЛЬНЫМИ ЗАЯВКАМИ И БУНКЕРОМ ДЛЯ ВЫТЕСНЕННЫХ ЗАЯВОК В ДИСКРЕТНОМ ВРЕМЕНИ»

Автоматика и телемеханика, № 12, 2009

PACS 02.50.-r

© 2009 г. А.В. ПЕЧИНКИН, д-р физ.-мат. наук (Институт проблем информатики РАН, Москва), Р.В. РАЗУМЧИК (Российский университет дружбы народов, Москва)

СИСТЕМА МАССОВОГО ОБСЛУЖИВАНИЯ С ОТРИЦАТЕЛЬНЫМИ ЗАЯВКАМИ И БУНКЕРОМ ДЛЯ ВЫТЕСНЕННЫХ ЗАЯВОК В ДИСКРЕТНОМ ВРЕМЕНИ1

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

1. Введение

После введения Е. Геленбе понятия отрицательной заявки начался период интенсивного изучения систем массового обслуживания (СМО) и сетей массового обслуживания (СеМО) с отрицательными заявками, или С-систем и С-сетей, функционирующих в непрерывном времени (подробный обзор публикаций в этом направлении вплоть до 2003 г. приведен в [1], хотя работы по С-системам и С-сетям публикуются и в настоящее время). Следом стали появляться работы, посвященные изучению СМО с отрицательными заявками, функционирующими в дискретном времени (см., например, [2-4]). Напомним, что отличие отрицательной заявки от положительной состоит в том, что при поступлении в систему она либо уничтожает положительную заявку, если таковая имеется, либо превращает положительную заявку в заявку другого типа (например, отрицательную или паразитную, засоряющую сеть).

В [5] рассматривается несколько отличная от предложенных ранее постанова задачи. Исследуется одноканальная СМО М/М/ 1/х> с отрицательными заявками, накопителем неограниченной емкости для поступающих в систему (положительных) заявок и дополнительным бункером также неограниченной емкости для вытесненных заявок. Новизна постановки заключается в том, что отрицательная заявка не убивает, а вытесняет одну из положительных заявок из очереди в накопителе и помещает ее в бункер. Заявки из накопителя обслуживаются с относительным приоритетом по отношению к заявкам из бункера. Прерывание обслуживания не допускается.

1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты № 08-07-00152 и № 09-07-12032).

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

В настоящей работе изучается СМО Сеот/Сеот/ 1/го, аналогичная рассмотренной в [5], но функционирующая в дискретном времени. Получены соотношения, позволяющие вычислять как совместное, так и маргинальные стационарные распределения числа заявок в накопителе и в бункере.

2. Описание системы

Рассмотрим функционирующую в дискретном времени однолинейную систему массового обслуживания с накопителем неограниченной емкости, входящими геометрическими потоками обычных (вероятность поступления на такте равна а) и отрицательных (вероятность поступления на такте равна с) заявок и с геометрическим распределением времени обслуживания (вероятность окончания обслуживания на такте равна Ъ). Далее для сокращения записи положим а = 1 — а, 6=1 — 6, с =1 — с.

Дискретное время измеряется в фиксированных интервалах (тактах). Величину такта положим равной к, к > 0, единиц времени и будем считать, что все возможные измерения в системе происходят в моменты времени пк, п = 1,2,... Очевидно, что если к = 1, то величина такта совпадает с единицей времени.

В качестве п-го такта рассмотрим полуинтервал ((п — 1)к,пк]. Примем, что все изменения состояния СМО происходят в конце такта (в момент пк) в следующем порядке: если на этом такте завершилось обслуживание заявки на приборе (с вероятностью 6), то она покидает систему и на прибор из накопителя или если накопитель пуст, то из бункера сразу же поступает следующая заявка; затем (с вероятностью а) поступает обычная заявка и если прибор занят, то помещается в накопитель, а если прибор свободен, то сразу же начинает обслуживаться; наконец, в систему (с вероятностью с) поступает отрицательная заявка, которая выбивает обычную заявку из накопителя и перемещает ее в бункер. Если отрицательная заявка в момент поступления в СМО застает накопитель пустым, то она тут же покидает систему, не оказывая на нее никакого воздействия.

Функционирование рассматриваемой системы можно описать однородной цепью Маркова (ЦМ) п ^ 0} с множеством состояний X = Хо и Х\, где Хо = {0},

Х\ = {(к,т), к ^ 0, т ^ 0}. Состояние (0) на п-м шаге соответствует полностью свободной системе после окончания п-го такта (т.е. на интервале времени (пк, (п+1)к)), состояние (к, т) - после окончания п-го такта (на интервале времени (пк, (п + 1)к)) прибор занят, а в накопителе и в бункере находится к и т заявок соответственно.

Целью дальнейшего анализа является вычисление основных стационарных характеристик, связанных с числом заявок в данной системе.

3. Система уравнений равновесия

Обозначим через р = а/6 загрузку рассматриваемой СМО. Поскольку, как нетрудно видеть, ЦМ {7п, п ^ 0} неприводима, то, применяя стандартные методы, можно показать, что условие р < 1 является необходимым и достаточным для существования стационарного режима функционирования. Далее будем считать, что это условие выполнено.

Пусть ро - стационарная вероятность того, что после окончания очередного такта в системе (в том числе и на приборе) отсутствуют заявки (ЦМ находится в состоя-

нии (0)), а pkm, к,m ^ 0, - стационарная вероятность того, что после окончания очередного такта на приборе обслуживается заявка и, кроме того, в накопителе и в бункере есть еще к и m заявок соответственно (ЦМ находится в состоянии [к, m)). Стационарные вероятности ро и ркт будем называть стационарными вероятностями по тактам.

Отметим, что приводимые далее соотношения будут иметь несколько более простой вид, если рассматривать ЦМ не по тактам, а по «фиктивным мгновенным» моментам перед возможным поступлением в СМО новой (положительной) заявки, но после смены заявок на приборе или полного освобождения системы (если на приборе окончилось обслуживание заявки). Стационарные вероятности состояний по этим моментам, аналогичные определенным выше, будем обозначать через рО и рект, к, m ^ 0. Поскольку р§ представляет собой ничто иное, как стационарную вероятность поступающей заявке застать систему (в том числе прибор) свободной, а р^то -стационарную вероятность застать прибор занятым, а в накопителе и в буфере к и m заявок соответственно, то далее будем называть эти вероятности стационарными вероятностями по моментам поступления заявок.

Стационарные вероятности рО и р%т, к, m ^ 0, связаны со стационарными вероятностями ро и pkm, к, m ^ 0, следующими соотношениями:

(1) Ро=аро,

(2) роо = аро +ïïpo0,

(3) рко = acpfc_i,o +âcpfco> к ^ 1,

(4) рош = асро,то_1+âpom+âcpijTO_1, m ^ 1,

(5) ркт = асрек_1т + acpekm_i + Шрект + âcp£+i,TO-i, к,т^1.

Не выписывая матрицы переходных вероятностей, приведем систему уравнений равновесия (СУР) для стационарных вероятностей рО и p%m, к, m ^ 0:

(6) dbpo=âbpo0,

(7) (аЪ + âb)poo = аЪр\0 + abpg + аЪр^,

(8) (ab + ab + abc+ abc)pk0 = abcpk_10 + abcpk+10, к ^ 1,

(9) (al + аЬ)рдт = âbplm+l + âbpelm + abcp\m_x + + аЬсрд т_1 + (abc + âbc)p'{ m_1, m ^ 1,

(10) (ab + âb + abc + abc)pekm = abcpekTO_1 + â6c^+2m_1 +

+ âbcpl+l m + abcpl_l m + (abc + âbc)pfc+l TO_1, fc,m ^ 1. К этим уравнениям необходимо добавить условие нормировки

(11) рО pkm = 1-

k,m=О

4. Стационарное распределение общего числа заявок в системе

Наиболее просто для данной СМО вычисляется {рП, п ^ 0} - стационарное распределение общего числа заявок в системе, включая заявки, находящиеся в накопителе, на приборе и в бункере, где

рвп =53 рkm^ п > 1-fc+m=n —1

Действительно, из уравнений (6)—(10) после несложных выкладок имеем:

О =-abpl+äbpl+1, п = 0,1, 0 = -(ab + äb)pen + äbpl_i +äbpen+1,

откуда получаем с учетом условия нормировки (11):

(12) реп = önpl, п > 1, где 6 = ab/ab, а

(13) р0е = 1 - S.

Следовательно, стационарное распределение общего числа заявок по моментам поступления является геометрическим.

Из (1)—(5), (12) и (13) нетрудно найти стационарные вероятности по тактам:

Ро = t1 - p),

Рп= Pkm = =Ön(l - р), п ^ 1.

fc+m=n —1

Приведем среднее стационарное значение М общего числа заявок в системе по моментам поступления:

(14) М = ——. К ' 1-й

Впрочем, полученные в этом разделе результаты имеют очевидный физический смысл, поскольку с точки зрения общего числа заявок в системе рассматриваемая СМО совпадает с обычной СМО Geom/Geom/1/x> без отрицательных заявок.

5. Рекуррентный алгоритм вычисления двумерного стационарного распределения вероятностей состояний

В этом разделе будет получен рекуррентный алгоритм вычисления совместного стационарного распределения числа заявок в накопителе и бункере (по моментам поступления в систему). Положим

f(z) = abcz2 — (ab + ab + abc + abc)z + abc. Рассмотрим уравнение

/ (z) = о

и обозначим через zi^ его корни:

(ab + ab + abc + abc) \ (ab + ab + abc + abc)2 — 4abcabc (15) =--'

Поскольку

/(0) = abc > 0, /(1) = —с < 0, то 0 < zi < 1 < z2.

Таким образом, функция /(г) может быть представлена в виде произведения

¡(г) = аЬс(г - - г2),

где г1)2 определяются формулой (15). Введем производящие функции (ПФ)

Рт(г) = £Р%т*к, М < 1, т > 0.

к=1

Теперь сформулируем теорему, позволяющую рекуррентно вычислять двумерное стационарное распределение вероятностей состояний.

Теорема 1. Стационарные вероятности рОт и ПФ Рт(г), т ^ 0, удовлетворяют соотношениям:

(16) рОо = ¿(1 — 6),

(17) рп=6рт-р%а,

(19)

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком