автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Анализ процесса инверсионного обслуживания с прерыванием в системе ограниченной емкости с распределениями фазового типа

Р Г 6 ^^ДАРСТВЕННЫЙ КОМИТЕТ РОССШСКОИ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНЖ)

I У поп

РОССИЙСКИЙ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ

На правах рукописи ПАВЛОВА Ольга Игоревна

УДК 519.21

АНАЛИЗ ПРОЦЕССА ИНВЕРСИОННОГО ОБСЛУЖИВАНИЯ С ПРЕРЫВАНИЯМИ В СИСТЕМЕ ОГРАНИЧЕННОЙ ЕМКОСТИ С РАСПРЕДЕЛЕНИЯМИ ФАЗОВОГО ТИПА

(05.13.17 - теоретические основы информатики)

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1993

габота выполнена на кафедре теории вероятностей и математической статистики Российского университета дружбы народов

Научный руководитель -доктор технических наук, профессор П.П. Бочаров

Официальные оппоненты: доктор физико-математических наук, профессор В.В. Рыков кандидат физико-математических наук, И.А. Соколов

Московский государственный университет имени М.В.Ломоносова

в 15 час. 00 мин. на заседании спец ь I

К 053.22.28 в Российском университете дружбы народов.

Адрес: 117923, Москва, ул.Орджоникидзе, 3, факультет физико-математических и естественных наук, ауд.

С диссертацией можно ознакомиться в научной библиотеке Российского университета дружбы народов по адресу: 117198, Москва, ул. Миклухо-Маклая, д.6.

Ведущая организация:

Защита диссертации состоится

Автореферат разослан

1993 г.

Ученый секретарь специализированного совета кандидат физико-математических нау!

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Характерной особенностью вычислительных систем, функционирующих в режиме разделения времени, является наличие специальных алгоритмов диспетчеризации, которые позволяют уменьшать время пребывания в системе коротких заданий за счет задержи в очереди перед процессором незавершенных длинных. Анализ характеристик производительности вычислительных сетей и систем, сетей связи с пакетной коммутацией, многопроцессорных ЭВМ и ряда других технических систем, функционирующих на основе принципа разделения времени (СРВ), сводится к исследованию систем массового обслуживания (СМО), специальные алгоритмы диспетчеризации в которых моделируются при помощи так называемых дисциплин разделения времени, в частности, дисциплиной обслуживания в обратном порядке с прерываниями.

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

Целью диссертационной работы является:

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

2. Разработка на основе полученных теоретических результатов комплекса программ для анализа стационарных показателей производительности однолинейных СМО фазового типа с ограниченным накопителем при различных дисциплинах обслуживания в обратном порядке с прерываниями.

Результаты, выносимые на защиту, определяются поставленной целью и состоят в следующем:

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

2. Для анализа стационарных характеристик однолинейной СМО конечной емкости с распределениями фазового типа при дисциплине обслуживания LCPS с прерываниями входящего потока и обслуживания разработаны методы ее анализа и получено геометрическое представление распределения очереди, а также выведены выражения для основных показателей производительности СМО.

3. На основе полученных теоретических результатов разработаны комплексы программ для расчета показателей производительности однолинейных СМО конечной емкости при дисциплинах ЪСРЗ с прерываниями.

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

Обоснованность научных положений. Полученные в диссертации" результаты полностью обоснованы строгими математическими доказательствами и проведенным численным анализом.

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

при анализе стационарных характеристик однолинейных СМО конечной емкости при инверсионном обслуживании с прерываниями за счет использования распределений фазового типа учтена априорная неизвестность интервалов между поступлениями заявок в систему и длительностей их обслуживания;

получены аналитические выражения для основных показателей производительности однолинейных СМО конечной емкости с распределениями фазового типа и дисциплиной обслуживания в обратном порядке с прерываниями при повторном обслуживании прерванной заявки и при ее дообслуживании;

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

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

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

те дружбы народов.

Реализация результатов работы. Исследование систем массового обслуживания с распределениями фазового типа при дисциплинах оСслукивания в обратном порядке с прерываниями проводилось в рамках НИР "Разработка математических методов и алгоритмов анализа мультипроцессорных вычислительных систем, локальных и интегральных информационно-вычислительных сетей" (государственный регистрационный номер 01.9.10 033110), которая выполнялась в соответствии с координационными планами АН СССР.

Апробация работы. Материалы диссертационной работы докладывались на IV Международном семинаре по теории телетрафика и компьютерному моделированию (Москва, 1993), Всесоюзной научно-технической конференции: Микросистема-92 (Томск, 1992), IV Всесоюзном совещании по распределенным вычислительным системам массового обслуживания (Душанбе, 1991), VII, VIII, IX Белорусской зимней школе-семинаре по теории массового обслуживания (Гродно, 1991; Брест, 1992; Минск, 1993), XXVI, XXVII, XXVIII научных конференциях факультета физико-математических и естественных наук Российского университета дружбы народов (РУДН) (Москва, 1991, 1992, 1993), а также на научном семинаре кафедры теории вероятностей и математической статистики РУДН.

Публикации. По материалам диссертационной работы опубликовано" Э^работ, из них 2 в центральной печати.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. Содержит 150 страниц текста и список литературы из 67 наименований .

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматривается СМО фазового типа, состоящая из одного прибора и накопителя конечной емкости г (1 í г í fflj.

На систему поступает рекуррентный поток заявок с функцией распределения (<М?) А(х) фазового типа,

А(х) = 1 - атеАх1, х>0, ат1=1, допускающей неприводимое РН-представление (а,А) порядка I.

Здесь 1 - единичный вектор столбец.

Длительности обслуживания заявок являются независимыми в совокупности случайными величинами с общей ФР В(х) фазового типа,

В(х) = 1 - ртеш1, xzO, рт1=1,

допускающей также неприводимое РН - представление ф,М) порядка т. Дисциплина обслуживания заявок LCFS PRR (La3t Соке First Served Preemptive Resume Repetition) предполагает, что каждой вновь поступившей заявке дается высший абсолютный приоритет, а б очереди размещаются прерванные заявки, причем на первом месте стоит последняя прерванная заявка. При повторном попадании на обслуживание прерванные заявки обслуживаются заново .

Заявка, заставшая в момент поступления накопитель системы полностью занятым, либо погадает систему и вновь на нее не поступает (режим А), либо прерывает обслуживание заявки, находящейся на приборе, при этом систему покидает прерванная заявка (режим В).

В дальнейшем такая СМО кодируется как РН/РН/1/г/LCFS PRR,

В §2 строится математическая модель данной системы.

Рассмотрим сначала случай СМО, функционирующей в режиме А. Стохастическое поведение рассматриваемой системы описывается однородным марковским процессом (МП) X(t),t£0, над

г+ 1

множеством состояний X = U X , где

к=0 R

Xk=((l,kJ)A=T7T.J=i7m}t k-T^F+j.

Здесь для произвольного момента времени t состояние (1,0) соответствует случаю, когда система полностью свободна и процесс генерации заявки находится на фиктивной фазе i, а состояние (i,P.,J) отражает ситуацию, когда в системе имеется к заявок, а процессы генерации и обслуживания заявок находятся на фазах I и J соответственно.

В сделанных предположениях существуют предельные вероятности р = Ilm P(X(t)=x>, xtX, строго положительные, не

х t-co

зависящие от начального распределения и совпадающие со стационарными вероятностями. Введем векторы

рт0 = (pi0, i=l ,1), pTh = (pi_k_J, 1=1,1, J =hm), k=1,r+1,

рт= (р\, Ь=0,г-И). Координаты вектора р являются единственным решением следующей системы уравнений равновесия (СУР):

Р^-О7, (1)

с условием нормировки рт~1 = К

где матрица А, порядка 1+1т(г+1), является блочной трехдиа-гональной.

В §3 получено решение СУР (1) в явной матрично-геометри-ческой форме с точностью до постоянного вектора, определяемого из системы линейных алгебраических уравнений. Положим

„ , —^ * * (У -> -»

Л = - ЛФМ-!ат®и.рт, М - - Л©М + А»1вТ, К = Л®М +\аг®Г. !У0= - (Л»р!Г)М~', РУ = ЛМ~1, Пг= -(Аате>1рт)м~',

г --- М-Л)(1©/), V = (1+2 О?*1-' + йгл№г-г1У )7.

С г , . О О Г

Здесь А.=-Л/, р,=-М7, У®7 - кронекерово произведение матриц и и 7 и 1/®У=г7»Г+1»У - кронекерова сумма этих матриц.

Теорема 1.1. Стационарное распределение {рй,й-0,г+/} для СМО РН/РНЛ/г/ЬСРБ РНЙ представляется в виде

т

Рк

о о ^

э^уТ""'^, й=Гг7,

где р определяется как единственное решение системы уравнений

гг пХ р0° 0 •

р Тои = 1.

В случав режима В результаты теоремы 1.1 сохраняются при

й» (У ""^гр

условии, что матрица М определяется как М = Л<&М + Ш

В §4 предлагается другой подход к решению СУР (1), основанный на иь-разложении матрицы интенсивностей переходов процесса Х[1). В результате применения этого метода найдено эквивалентное представление стационарного распределения очереди в неявной мультипликативной форме с точностью до постоянного множителя, который определяется из условия нормировки.

В п. 4.1 данного параграфа приводится вероятностная интерпретация метода иъ-разлокения инфинитезимальной матрицы. В этом же пункте с помощью метода иь-разложения найдено решение с точностью до постоянного множителя некоторого класса систем линейных алгебраических уравнений типа СУР с матрицей коэффициентов специального вида.

В п.4.2 на основании результатов, полученных в п.4.1, найдено другое представление стационарного распределения очереди для рассматриваемой СМО. Введем обозначения

г -ртд'1Н, к=г+1, / = ] -

к -пт ,гг - I, к-г,;,

1 1 к к

где

Н =■ (ат& 1)(А ® ИГ', И - Т + Н(к ® I),

пк " (а1 ® ® МГ> с = * 1 к=г+Т7о,

а векторы а^ связаны с векторами рекуррентными формулами

аг+/ г аТ' а1 = ® (4)

Кроме того, положим, /к = с~1(1-е 1), к=17г.

Теорема 1.2. Стационарное распределение (р , дляСМО ?Н|РН|1|г|ЬСРЗ РН представшею в виде г -отЕл",' к=0,

рЫ ^ ------Г5;

1 1=1 1 в

где постоянная определяется из условия нормировки.

В случае режима В формулы (5) остаются справедливыми,

пои этом 7 . - -с"',/1 ,.

•г+; г+1 г+1

В этом же параграфе на основании результатов п.4.1 доказано, что при фиксированном к=0,г координаты вектора а& (выражения (4)) представляют собой вероятности, определяющие фазу, на которой находится генерируемая заявка в момент окончания обслуживания заявки на приборе при условии, что в этот момент в системе имелось к заявок.

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

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

Рассмотрим некоторую заявку, в момент 10 поступления которой в системе имелось к заявок, и пусть - время пребывания этой заявки в СМО. Функционирование СМО с момента ^ до момента ухода этой заявки из системы описывается

однородным обрывающимся МП £ € И^г^х^, над мно-

з

жеством состояний X = II Х.(к,п), где

п=0

Х(к,п)={(1,к^,п) | ь-ТД, J =7.и, п^О,а}, з=г-к.

Здесь ■- (1,кЛ,п ) означает, что помимо к заявок,

имевшихся в системе в момент времени to-0, к моменту времени £ <: в систему поступит п новых заявок, при этом

текущие фазы генерации и обслуживания будут равны I и J соответственно.

Пусть Ок - матрица интенсивностей переходов процесса )■ Отметим, что матрица С является блочной трехдиаго-нальной и полностью определяется через исходные параметры СМО. Обозначим через %(1,0) и %(1,к,3) начальные вероятности состояний процесса и введем векторы

-г-

%о,А = Ш1,0),1=ТД), %т к=А(%(1,кЛ)Л^ТД, ]=~Пт). Дли векторов тс^ А , й=07г получены следующие выражения:

-»г \.а

X~1pl(XaT»1ÇiT), к = ?,г.

где X интенсивность входящего потока А, 1=-атА 11. Положим далее

v0lk)=%k^A/(1-%), (6)

где тс - вероятность потери заявки, тс - »1) .

Теорема 1.3. Начальные моменты vm порядка m, m ¿1, времени пребывания заявки в системе РН/РН/1/г/LCFS PRR определяются как

у = Е (7)

m Л=0 m

при этом векторы удовлетворяют следующему рекуррентному

уравнению:

uT(k)G. = -mvT ЛЬ), m >1. (8)

га R m- /

В работе предложен алгоритм нахождения решения системы уравнений (3), в основе которого лежит подход использованный при решении СУР (1) (теорема 1.2).

В §б данной главы получено явное выражение для стационарной ФР D(t) интервалов между выходами заявок из системы, а также ее преобразование Лапласа (ПЛ).

Обозначим через % (1,к) вероятность того, что в момент окончания обслуживания t+O в СМО имеется к заявок, а процесс генерации находится на фазе Í и положим

iíhtD=(X( í-%))'1pTk+í (T«|i ), ñ=D7r -

Введем обозначения Q(s )=з"1 l-ísl-h уЧ, т (s )--- з~ ' (I&pT)Z~1 (з)( 1<ш ),

(ç(3)-=-s~1 (I»^T)Z'1 (з)(Х»1 ), r(3)=-(aT*pT)Z~' (з)(1щ), (9)

р(3) = -far®p T)Z~' (8)(\&1 ), Z(3)=A<t>N-3T»I.

Теорема 1.4. Преобразование Лапласа ФР D(t) имеет вид

Kd к

д(з)= £ %l _ l.(s), (Ю)

где

ôfc(8) =

fc=0

д(з.Ю (a), k=0,

а величины С (з) определяются следующими выражениями:

1-рп(а) —

0п(з)=и(п)г(а) 1_р(9) + рп(з)р(з), п=0,г.

Здесь ргя; - гфеобразование Лапласа-Стильтьеса (ГШС) ФР В(х).

На основании теоремы 1.4 найдено выражение для среднего значения <5? интервалов между выходами заявок из системы.

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

Во второй главе рассматривается СМО РН/РН/1/г, описанная в главе 1, при дисциплине ЬСРБ РН ( РИ - РгеетрНуе йевше). Отличие этой дисциплины от дисциплины ЬСРБ РНЯ состоит в том, что прерванные заявки при повторном попадании на обслуживание дообслуживаются. Как и в главе 1, исследуются два режима поведения СМО в момент, когда поступающая заявка застает все г мест для ожидания занятыми: либо она теряется и в дальнейшем не оказывает влияния на функционирование СМО (резким А), либо прерывает обслуживание заявки, находящейся на приборе, при этом систему покидает прерванная заявка (режим В К

В §1 приведено математическое описание данной СМО, функционирование которой описывается однородным МП

г+ 1

над множеством состояний Х= и X

где

XQ= { fi,О) | 1=1,1 ),

Хк - C(t,JrJs....,JA)\l=TTï, Je=T,m, з=Т7?г, }, k=T7rïT.

Здесь для произвольного момента времени t состояние (1,0) соответствует случаю, когда система пуста и процесс генерации заявки находится на фиктивной фазе I, а состояние {l,J1,J?,'--,Jk) отражает ситуацию, когда в системе имеется к заявок, процессы генерации и обслуживания находятся на фазах I,

j соответственно, а J2,J3.___,Jh соответствуют номерам фаз,

на которых были прерваны находящиеся в очереди заявки.

Очевидно, что все состояния процесса X(t) сообщаются. Следовательно, существует

lim P(X(t)=x) = р , х zX,

t-oo -с

при этом вероятности р отличны от нуля и совпадают со стационарными.

Упорядочим вероятности рх в векторы

Ро = (Pw i=T7i)>

pI ■= (р. , , , , l=l7l, J=T7m, з-Т/к), к=1 ,г+1.

Обозначим далее через А матрицу интенсивностей переходов процесса Х(1), которая в данном случае также имеет блочный трехдиагональный вид.

К матрице А, порядка 1+1т(тг~1-1)/(т-1), применимы результаты, полученные в п.4.1 главы 1. На основании этих результатов стационарное распределите очереди представимо в неявной тензорно-мультипликативной форме. Приведем сначала этот результат для случая режима А поведения СМО при переполнении ее накопителя.

Введем обозначения

"ГЦ

где матрицы Нк, Qk и имеют вид

Нк = Гс§»ГЯЛ®МГ', Qk = -Нк(Ш), Yk = I-Qk, ter+1,1, а векторы ак связаны с векторами рекуррентным образом: аг+1 - а' «л = fe-r^. (11)

Кроме того, положим

/1= Р.=Т7г+1.

Теорема 2.1. Стационарное распределение (рк, &=0,г+1) для СМО РН|РН|í|г|LGFS PR представляется в виде

-@хт0 Л-', ~к=0, рт = j - k-1 - __ (12)

где постоянная g определяется из условия нормировки. Здесь и далее приняты следующие обозначения :

Un » U, --U&U . .»U , U&nV~U 2 7, °i=» 101

В случае режима В векторы pfc стационарных вероятностей состояний СМО определяются также выражениями (12), при этом

вектор 7r+í имеет следующий вид:

7Г = - е~'бгЯ ,,

'г+1 г г+1'

где с =.- í-prOr+í/.

С помощью результатов, полученных в п.4.1 главы 1, доказано, что компоненты вектора afc, U=W¡r, (выражения (11)), можно интерпретировать как вероятности. С физической точки зрения они имеют тот же смысл, что и компоненты вектора afe, определяемого выражениями (4).

В заключение §2 получены выражения для вероятности простоя СМО, коэффициента использования обслуживающего прибора, начальных моментов числа заявок в системе и в очереди, вероятности потерь заявок.

В §3 данной главы предложен алгоритм нахождения начальных моментов времени пребывания заявок в системе, в стационарном режиме ее функционирования. Данный алгоритм получен на основе метода, развитого в главе 1 при получении аналогичных характеристик для СМО РН/РН/1/г/lCFS PRR.

Для исследуемой СМО доказано, что начальные моменты v порядка п, тл1, времени пребывания заявок в системе РН/РН/1/г/LCFS PR можно определить на основе теоремы 1.3 (выражения (Т) и (8)) с новой матрицей которая также,

как и в главе 1, определяется через исходные параметры СМО. Векторы тсь , участвущие в обозначениях (6), в этом случае определяются следующим образом:

С \~1р0(\ ат&рт), к^О,

%Ъ.А= 1 Л ~ ---

Х~'р (X а к=1,г+1.

Для решения системы уравнений (8) с новой матрицей £? в данном параграфе используется тот же алгоритм, что и при нахождении стационарного распределения очереди (теорема 2.1).

В §4 для данной СМО найден явный вид стационарной ФР ва) интервалов между выходами заявок из системы, а также ее ПЛ.

Пусть % (1,0) - стационарная вероятность того, что в момент t +0 окончания обслуживания заявки система была пуста и процесс генерации находился на фазе I, а состояние соответствует случаю, когда в момент времени ^ +0 в СМО имелось к заявок, а процессы генерации и обслуживания находились на фазах С и J соответственно.

Введем векторы %^ (%п(1,0), 1=771) и

в=(%0( ). 1= Т7Т, ,т). Для этих векторов получены следующие выражения: 1

т

1 _

РТк+1(1^1*к~11), й=/,г.

где %=Х~'р (Х&г+11) - вероятность потерь.

Выражения для ШГ б(з) ФР БИХ в этом случае записываются в виде (10), при этом вектор 8(э), и функции р(з) и г(з) определяются выражениями (9), а векторы 7(а) и Щз) имеют вид

7('з; - (8)(1ць), ф(з) = - а'1 £~1(з)(Хъ1),

где, как и прежде, 1(а)=кт-з1»1.

На основании выражения, получешшого для Ш1 б(з), найдена формула для среднего значения интервалов между выходами заявок из СМО.

В §5 проводится численное исследование показателей производительности данной СМО для конкретных распределений

А(х) и В(х). В ходе этого исследования, в частности, установлено, что из двух дисциплин обслуживания LCFS PR и LÖFS PRR с точки зрения вероятности потерь и среднего числа заявок в системе предпочтительней является дисциплина LCFS PR, если коэффициет вариации ФР В(х) меньше 1, и дисциплина LCFS FRR в противном случае.

В третьей главе исследуется СМО фазового типа с накопителем емкости г , 0<г<«>, в предположениях, сделанных относительно вида $F А(х) интервалов между поступлениями заявок в систему и В(х) времени обслуживания, в главе 1.

В §1 данной главы предполагается, что заявки обслуживаются в соответствии с дисциплиной LCFS PRR, описанной в главе 1, с дополнительным условием, что в момент окончания обслуживания происходит прерывание процесса поступления заявки, который мгновенно начинается заново. В случае переполнения накопителя системы будем считать, что вновь поступающие заявки теряются и не оказывают влияние на функционирование СМО.

Кратко обозначим эту дисциплину как I PRR - S LCFS PRR (Input PRR - Service LCFS PRR).

Функционирование рассматриваемой системы описывается однородным МП Y(t), tzO, пространство состояний которого совпадает с пространством состояний X процесса X(t), t^O, вве-деного в главе 1.

Предельные вероятности состояний системы

р - Ilm PCY(t)=x}, х е X,

х t-ЮО

существуют в силу сообщаемости состояний процесса Y(t) , не зависят от начального распределения и совпадают со стационарными вероятностями.

Ниже мы будем использовать векторы р , &=0,г+/, для стационарного распределения, определяемые также, как и в главе 1.

Далее обозначим через А - матрицу интенсивностей переходов процесса Y(t). Матрица А ив данном случае является блочной трехдиагональной матрицей порядка l+lm(r+1l.

Введем обозначения

Т* ••-- -fü'^E, -f = -c~1hT, где матрицы D и H имеют вид

D - Г г Н(Х&1), H - Сат®1ЯЛ®МГ',

а вектор Н и число с определяются как —» ->

П = Гаг®р гЯЛ®МГ7,

СО 00

с - / + /г гл.»?; = / ваша) /- / лата).

о о

Положим также

(•V

р - -ут(\»1) = С~1(1-С).

На основании результата, полученного в п.4.1 главы 1 для ЦЪ-разложения некоторого класса матриц интенсивностей переходов специального вида,доказана следующая

Теорема 3.1. Стационарное распределение (р , к=07г+Т) для СМО РН/РН/1/г с дисциплиной I РИН-Б ЬСРБ РНЙ представляется в виде

т

Р1

' р ШТк 1, к=о,

рп\рк~11т, к=1,г, (14)

Р,-ЛРГ тТ. ,

"о эо'

3о'"г ч

где р0 определяется из условия нормировки .

Пусть Рк=Рк 1 - стационарная вероятность наличия к заявок в системе. Тогда из (14) получаем, что

Р0Р0Рк к = 1,г,

р0ррг, к=г+1,

где р=Ц1~1, р0 - Хс~1°$(!-Аа))(1-Ва )№, ц~7=-ргГГ' 1.

о

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

X п- р

\ = р~ (1'Р0) + РоКРГ(1~ -р-*-

го гО

В §2 для рассматриваемой в этой главе СМО РН/РН/1/г ис-

следуется случай, при котором обслуживание заявок происходит в соответствии с дисциплиной LCFS PR (глава 2), при этом учитывается, что заявка, покидающая СМО, прерывает процесс генерации заявки, который мгновенно начинается заново. В этом случае также будем предполагать, что в случае переполнения системы вновь поступающие заявки теряются.

Такую дисциплину обслуживания кратко будем кодировать как I PRR - S LCFS PR.

Стохастическое поведение данной системы описывается однородным МП Z(t), tW, над пространством состояний X, совпадающим с пространством состояний процесса X(t), t^O, определенным в главе В предположениях, сделанных относительно ФР А(х) и В(х) все состояния процесса Z(t) сообщаются между собой. Следовательно, существует предельное распределение

р = lim P(Z(t )=х), xtX,

причем р > О для всех х X, не зависят от начального распределения процесса Z(t} и совпадают со стационарными вероятностями .

Упорядочил вероятности рх в векторы, аналогичные векто-

рам р к=0,г+1, введенным в главе 2. л ->

Векторы рк определяются в этом случае на основе метода блочного Ш-разложения матрицы интенсивностей переходов процесса Z(t), изложенного в п.4.1 главы 1.

Теорема 3.2. Стационарное распределение [ръ, к=0,г+1} состояний СМО РН1РН11!г с дисциплиной I РНН - Б ЪСгЗ РН имеет вид

т

" -р ЫТА й=0,

(15)

т

где р определяется из условия нормировки, ар-- 7 (\»1).

Стационарные вероятности наличия й заявок

в системе на основании выражений (15) определяются следующим образом:

Рк=Р0РРк 1> Ь=1,г+1, где р= р1 1 .

В этом же параграфе на основе стационарного распределения рк, k^O,r+J получены выражения для основных показателей производительности СМО: вероятности простоя системы, коэффициета использования обслуживающего прибора, начальных моментов числа заявок в СМО и в очереди, пропускной способности системы, вероятности потерь. Так, например, пропускная способность X в этом случае определяется следующим выражением:

А.0 = цС 1~р0), а для вероятности потерь тс - получаем:

тс =---— .

V-(1~P0)+

Завершается третья глава численными расчетами стационарных показателей исследованных СМО, выполненными с помощью программы, составленной на основе полученных аналитических результатов. Проведенное численное исследование показало, что из двух дисциплин I PRR - S LOFS FRR и LCFS FRR (I FRR - S LCFS РП и LCFS PR) с точки зрения вероятности потерь и среднего числа заявок в системе предпочтительней является дисциплина I PRR - S LCFS FRR (I PRR - S LCFS PRj, если ФР входящего потока ФР А(х) имеет коэффициент вариации больше 1, и дисциплина LCFS PRR (LCFS PR)- в противном случае.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

1. Выведены формулы для расчета стационарного распределения конечных очередей фазового типа при инверсионном обслуживании с прерываниями в случае повторного обслуживания прерванной заявки и в случае ее дообслуживания.

2. Получено геометрическое представление стационарного распределения конечной очереди фазового типа при инворсион-

\

ном обслуживании с прерываниями входящего потока и обслуживания в случае различных вариантов обслуживания прерванной заявки.

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

4. На основе полученных аналитических результатов разработаны комплексы программ для расчета стационарных характеристик однолинейных СМО конечной емкости с распределениями фазового типа при инверсионном обслуживании с прерываниями и рассмотрены примеры численного исследования этих систем.

Основные результаты диссертации отражены в следующих опубликованных работах:

1. Бочаров П.П., Павлова О.И. Матрично-геометрическое решение для стационарного распределения очереди при дисциплине LCPS с прерываниями и распределениями фазового типа // Тезисы докладов 7-ой Белорусской школы-семинара по теории массового обслуживания. Минск: БГУ, 1991 .-С.78.

2. Бочаров П.П., Павлова О.И. Анализ очереди с распределениями фазового типа и дисциплиной LCF5 PRR // Тезисы докладов IV Всесоюзного совещания по распределенным вычислительным системам массового обслуживания. М: Изд.ГПНТБ, 1991. _С.193-195.

3. Бочаров П.П., Павлова О.И. Матрично-геометрическое распределение очереди при дисциплине LOFS с прерываниями и распределениями фазового типа // Автоматика и телемеханика. - 1991.- C.II2-I22.

4. Бочаров П.П., Нава С., Павлова О.И. Стационарное распределение конечной очереди фазового типа с инверсионной дисциплиной обслуживания с прерываниями // Тезисы докладов IY Международного семинара по теории телетрафика и компьютерному моделированию.- М. Изд. ИППМИ РАН.- 19Э2.

- С. 14-21.

5. Бочаров П.П., Павлова О.И. Анализ очереди с распределениями фазового типа и инверсионной дисциплиной обслуживания с прерываниями // Автоматика и телемеханика. -

1992.-N11.- С.83-92.

6. Бочаров П.П., Павлова О.И. Анализ очереди фазового типа с прерываниями входящего потока и обслуживания // Микро-система-92: Материалы Всесоюзной научно-технической конференции. Томск: Изд-во Томск.ун-та.- I992.-G.CS.

7. Бочаров П.П., Павлова О.И. Анализ системы массового обслуживания с распределениями фазового типа, зависящими

от состояния очереди и дисциплиной ЬСР5 с прерываниями // Тезисы докладов 8-ой Белорусской школы-семинара по теории массового обслуживания. Минск: БГУ, 1992.-С.85.

3. Бочаров П.П., Павлова О.И. Выходящий поток для конечной очереди фозофого типа при дисциплине ЪС?Б с прерываниями // Тезисы докладов 9-ой Белорусской школы-семинара по теории массового обслуживания. Минск: БГУ, 19ЭЗ.

Э. Павлова О.И. О выходящем потоке для конечной очереди фазового типа при дисциплине ЬСРБ с прерываниями и дооб-олуживанием /7 Тезисы докладов XXIX Научной конференции факультета физико-математических и естественных наук.-М.:Изд. РУДН, 1993.