Приоритетные модели с гиперэкспоненциальными потоками

Ушаков, Андрей Владимирович

Приоритетные модели с гиперэкспоненциальными потоками тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

Ушаков, Андрей Владимирович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.05 КОД ВАК РФ

Диссертация по математике на тему «Приоритетные модели с гиперэкспоненциальными потоками»

Автореферат диссертации на тему "Приоритетные модели с гиперэкспоненциальными потоками"

На правах рукописи

Ушаков Андрей Владимирович

ПРИОРИТЕТНЫЕ МОДЕЛИ С ГИПЕРЭКСПОНЕНЦИАЛЬНЫМИ ПОТОКАМИ

01.01.05 - Теория вероятностей и математическая статистика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 6 СЕН 2013

Москва - 2013

005533817

Работа выполнена в Учреждении Российской академии наук Институт проблем информатики РАН.

Научный руководитель: доктор физико-математических наук,

профессор

Королев Виктор Юрьевич

Официальные оппоненты: доктор физико-математических наук,

профессор

Афанасьева Лариса Григорьевна

кандидат физико-математических наук, Зарядов Иван Сергеевич

Ведущая организация: Нижегородский государственный

университет им. Н.И. Лобачевского

Защита состоится 18 октября 2013 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru/.

Автореферат разослан «-/<7 »сЕЬТЛ £РЛ2013 г.

Ученый секретарь

диссертационного совета В. А. Костенко

Общая характеристика работы

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

Первые работы, в которых был проведен содержательный математический анализ характеристик систем массового обслуживания с приоритетами, появились в конце 50-х - начале 60-х годов XX века. В них рассматривались либо одноканальные системы с пуассоновскими входящими потоками, либо марковские системы с относительным и абсолютным приоритетом с дообслуживанием прерванного требования. В дальнейших исследованиях наибольшее внимание уделялось именно однолинейным приоритетным системам с пуассоновскими входящими потоками. К концу 60-х - началу 70-х годов была создана стройная теория таких систем, и появились две монографии 1 и 2, в которых были систематизированы и обобщены исследования в этом направлении. Методы, используемые в этих монографиях, содержат общие идеи: введение вспомогательных дополнительных компонент к исследуемому случайному процессу так, чтобы расширенный процесс стал марковским, и использование регенерирующих свойств полученного процесса. Второе свойство позволяет свести изучение процесса на всей временной оси к его изучению на системе вложенных промежутков занятости различных типов, во время которых обслуживаются только требования определенных приоритетов. В результате, исследование процесса (например, длины очереди) сводится к изучению аналогичного процесса в системе с меньшим числом приоритетных классов и, в конце концов, к систе-

1 Джейсуол Н.К. Очереди с приоритетами. М., Мир, 1973, 280 с.

2 Гнеденко Б.В. и др. Приоритетные системы обслуживания. М., изд-во Моск. ун-та, 1973, 448 с.

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

1)при использовании этого метода алгоритмы нахождения распределения исследуемого процесса содержат большой объем (существенно растущий с ростом числа различных приоритетных классов) информации о распределениях на вложенных промежутках занятости, которая не представляет самостоятельного интереса;

2)метод не применим для ряда важных приоритетных дисциплин, для которых нарушается регенерирующая структура процессов обслуживания. В частности, к таким дисциплинам относятся дисциплина приоритета более длинной очереди, дисциплина случайного выбора очереди и др;

3)и главное - возникают серьезные затруднения с распространением этого метода на системы с непуассоновскими входящими потоками.

В конце 70-х годов появились работы 3 и 4, в которых метод дополнительных компонент был модифицирован для анализа приоритетных систем с эрлан-говскими и гиперэкспоненциальными потоками. В 90-х годах метод был еще более усовершенствован и применен в исследовании систем с рекуррентными потоками. Однако, этим методом удавалось исследовать только распределение длины очереди (и частично периода занятости) в двух разновидностях приоритетных дисциплин без прерывания обслуживания: относительный приоритет и чередование приоритетов. В исследовании систем с различными разновидностями абсолютного приоритета применить его не удавалось. Кроме того, остались

3 Ушаков В.Г. Система обслуживания с эрланговским входящим потоком и относительным приоритетом. Теория вероятн. и ее примен., 1977, т. XXII, вып. 4, с. 860-866.

4 Ушаков В.Г. Однолинейная система обслуживания с относительным приоритетом. Известия АН СССР. Техн. кибер. 1978, № 1, с. 76-80.

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

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

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

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

Задачи диссертационной работы Для достижения поставленной цели необходимо решение следующих задач:

1)разработка методов анализа систем массового обслуживания с гиперэкспоненциальным входящим потоком и различными разновидностями абсолютного приоритета;

2)изучение основных характеристик приоритетных систем массового обслуживания: вектора длин очередей из требований каждого приоритета, виртуальных времен ожидания начала обслуживания, различных промежутков занятости системы;

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

системы;

Методы исследования. В диссертации используются

1)методы теории вероятностей и теории случайных процессов: методы теории марковских процессов, метод дополнительных компонент при исследовании немарковских процессов, метод характеристических функций;

2)методы теории функций комплексного переменного и функционального анализа;

3)методы линейной алгебры;

4)методы теории дифференциальных и интегральных уравнений, в том числе асимптотического анализа решений этих уравнений.

Научная новизна. Представленные в диссертации результаты являются новыми, получены автором самостоятельно и состоят в следующем:

1) разработаны методы анализа одноканальных приоритетных систем массового обслуживания с абсолютным приоритетом. Найдено совместное распределение длин очередей из приоритетных и неприоритетных требований в нестационарном режиме для двух разновидностей абсолютного приоритета: с потерей и обслуживанием заново прерванного требования;

2)найдены преобразования Лапласа-Стилтьеса длительностей различных промежутков занятости системы с относительным приоритетом;

3)найдено преобразование Лапласа виртуального времени ожидания начала обслуживания в нестационарном режиме в системе с относительным приоритетом и двумя дисциплинами обслуживания требований одного приоритета: FIFO (прямой порядок обслуживания) и LIFO (инверсионный порядок обслуживания);

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

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

Апробация работы. Результаты работы докладывались и обсуждались

на научно-исследовательских семинарах "Теория риска и смежные вопросы" (факультет ВМК МГУ им. М.В. Ломоносова), "Аналитические методы в теории массового обслуживания "(факультет ВМК МГУ им. М.В. Ломоносова), XXIX и XXX (2011, 2012 гг.) международных семинарах по проблемам устойчивости стохастических моделей, на V и VI (2011, 2012 гг.) международных рабочих семинарах "Прикладные задачи теории вероятностей и математической статистики, связанные с моделированием информационных систем".

Публикации. Результаты диссертации опубликованы в семи работах, список которых приведен в конце автореферата. Первые пять из них опубликованы в журналах, входящих в список ВАК "Перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора и кандидата наук".

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

Краткое содержание работы.

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

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

Вторая глава посвящена исследованию системы с абсолютным приоритетом и двумя классами требований. Требования первого класса имеют приоритет перед требованиями второго класса. Длительности обслуживания — независимые в совокупности и не зависящие от входящего потока случайные величины с функцией распределения В^х) для требований г—го класса. Входящий

поток требований — рекуррентный, определяемый плотностью распределения интервалов между поступлениями требований вида

, Ч I Е с)а] ехР (—«з®) , X > О,

а(х) = <

О , х < О,

где а,- ф а,] при г ф j, ц > 0, ^ ^ = 1- Поступившее требование направляется

г=1

в г—й приоритетный класс с вероятностью р*, г = 1,2, независимо от остальных требований. Обозначим

Щ = (ь1{1),ь2(г)), Р(711,п2,г) = Р(£1(«) = пъь2(г) = п2),

где Ь^) — количество требований г—го приоритетного класса в системе в момент времени г = 1,2,

Пусть ^1(^1,2:2),..., 22) корни многочлена ЛГ ЛГ

а») - (Р121+Р2-2) XI П^+

¿=1 хф]

<*к (-21, г2) = П (21, ^2) - № (-21, -г2)), = г\к\г2, з) - единственное решение

гфк

уравнения г\ = & (в - г2)), фк(г2, в) = ^ 5), г2, в) ,

N N

Гк{*2, в) = ги;(г2, з) • с(а;р2г2 • Д(/х*(0, г2) + аД г=1 т

N N

еь(-г2) в) = ¿г(г2, в) • Ц(М°> г2) + а,-) • ед, (=1

= в), = ¿¿¿(0, &(«)),

л / , \\

_Л«_

где £1(5),..., Сл-(в) - решения уравнения N N

П (1 - г^АК« - №(0, г2))) + П (1 - г?р2{з - №(0, г2))) х г=1 ¿=1

„ 1 - Д(д - ^(0, г2)) еДгг, я) _ р з-щ{ 0,г2) а0,г2)

Для системы с абсолютным приоритетом и обслуживанием заново прерванного требования справедлива следующая теорема:

Теорема 1. Функция р(г 1, г2, в) определяется по формуле

** " ' 1 - 01(8 - Цк(21, ъ))

( ( р(«1, 22, з) = РоМ + 9 53 ( :

3=1 \ к=1 ^

М^ь Зг) + а,- 5 - ^(о, г2) ^(0, г2) + щ ) I '

где

(1 ~ ¿1 ~ г2))) оцДгь г2) {к) _

; 71 —

= П ъ) ~ Ф&2, з)) • Ят(г2) з),

ЛГ / N {к)

V ^ А»к(0, аа) + а^ в-^(О.га)

лт дг

П (1 - ^-1/32(5 - /1,(0, г2))) + 5] П (1 - 22%(з - щ(0, г2))) х

,(=1 .7=1

- п (1 •- «Г'АС - МО, •))) .) - £ '"^Й""-

1фк у

а) • Г](г2,з) - е,(г2,а) ■ гк{г2,з) _ 1 \ 1 - ъх02 (« - ^(0, гг)) ' а,(0, '

а функции роj(s) определяются из системы линейных уравнений

i=i

( N \ N П W>mk(s) + а„)

(s + щ). «,„(.) - ■ т=1Шаи_а()

\ " /

х ai ■ Poi(s) = 5>ar Wki(s), A; = 1,...,7V.

i=i

Аналогичная теорема доказана и для системы с абсолютным приоритетом и потерей прерванного требования.

В третьей главе рассматривается система обслуживания аналогичная системе главы 2, но уже с произвольным числом приоритетных классов требований и относительным приоритетом. Объектом исследования является виртуальное время ожидания начала обслуживания при двух дисциплинах обслуживания требований одного класса: FIFO и LIFO. Пусть - виртуальное время ожидания для требований г-го приоритетного класса в момент времени t при дисциплине FIFO, wf*\t), i = 1,..., г, - виртуальное время ожидания в момент времени t для требований г-го приоритетного класса при дисциплине FIFO, при условии, что после t требования в систему больше не поступают;

<W) =

v) = J e'^W^is, t)dt, i = 1,..., r, j = 1,.. ■, N, к = 0,1,

Функции uj\j\s, v) определяются по формулам

«__SL---S—-p0j(v) - £ }-M?±.Pmj{v)+

3 v-s + cij v — s + üi ¿-r'v — s + aj

J J m=14-1 J

m=i+1 N / i

+ _Cj, • ak ■ v) ■ + SPm Ь

V S + fc=l \m=l m=i+l /

где

^ с а- ^ * г \ \ ^

1 - Е^^ ЕрМ*) + £ Н ■ £ * ^ =

\ 3=1 3 \т=1 т=г+1 // к-1

С,^ Л ЧРоАУ) V П - /? МЧУ

.7=1 ■' 3=1 ■> т=г+1 ¿=1 1 ^

а функции Р(у(г>)

и Ртз(^) удовлетворяют системам линейных уравнений: .¡V , , N

^ г; - а,Р(и) + а, " и « - а|г(«) + а,-'

ак Рок(у) = Е

Я ЛГ

ел

^ ^ • К + и - аь-М)

п ((а* + V - а^(у)){а, + V - а1г(у)))

х к

(ак + у - аф)) ■ П(а„г(у) - а1г(у)) ■ П(а* - щ)' ~ '"''

Пф1

N П (Ы + ац{у))(а, + у- ац(у)))

ат+1к = УЗ Ыу) ■ —--;-7-тт-X

^ (ак + у- а,г(у))

х ЦСа,,«(«/) - а^у))'1 ■ Д(ак - а,-)-1, к = 1,..., ЛГ, г = г - 1,..., 0.

Пф1 ,у к

Здесь

лм = (1 - А «ы>- (Е - «М*

ощ(у), I = 1,..., ТУ, - решения уравнения

¿=1 Ь в + \т=1 т=Ш /

аналитические в области Re и > 0, z-j (з) = Pj(ctki{s)),

nU*) = К (4%), • ■ •, А), 1, • ■ •, l) , №(s) = ttciztfis),*£>(«), 1, .. ., 1).

Справедлива следующая теорема

Теорема 1. При дисциплине FIFO = и для г ^ 1

tyd) (s t) _ f" у* TT + TT c a ,,

v=l k=1 ' P^ ^

чф]

Я ПОЛНО

^ (/£>(«) + a.) • ac(4fc)(S),..., 1,..., 1)

\m=l m=i+l /

Аналогичные результаты получены для дисциплины LIFO.

В четвертой главе исследуется поведение виртуального времени ожидания в системе с относительным приоритетом и дисциплиной FIFO, когда загрузка системы приближается к критической. Рассматривается последовательность систем обслуживания (схема серий), параметры которых зависят от номера системы п в последовательности. Предельные теоремы получены в двух случаях: 1)существуют вторые моменты длительностей обслуживания; 2) существуют моменты длительностей обслуживания порядка 1 < 7 < 2. Приведем результаты, относящиеся к первому случаю (для сокращения записи зависимость параметров от номера п будем опускать, запись lim будет означать lim).

п—юо

Положим

а - I 1 J , pki = а • Y^Pißib Рк2 = а- ^РгАг,

\i=i / ¿=1 <=1

N N

Рг2 V4 —2 Х-"4 —1 Рк = 1 ~Рк1, Р = Рт, и = —- + 0- ¿^СЗа] ■

3=1 1=1

ги^) — виртуальное время ожидания для требований г-го приоритетного класса в момент времени

Предположим, что

1) существуют первые два момента длительностей обслуживания требований всех приоритетов, причем, справедливы разложения:

где

0„(s2)

ßi(s) = l-ßaS + -ßi2s2 + on(s2), О при s —> 0 равномерно по п;

2) для любого п ^ 1 рт 1 < 1;

3) существуют пределы liracj = с), Нто,- = а], j = 1, ...,N, lim ßik = ßik> к = i = linipi = p\, i = l,...,r, limpr_n < 1, lim/9rl = 1.

Положим и* — lim и, к = х.

2 и*

Теорема. При п —> +оо существует предел limP (p5w (itp~a) < x) =

\/2иЧ~1 к

л/2^

1 — 7Г 2

1 - e"2fc, а > 2.

e 2 dy, а < 2,

о~2к

J е^Л/Ч- J e-^dy

, а = 2,

Список публикаций по теме диссертации

1. Ушаков A.B. О виртуальном времени ожидания в системе с относительным приоритетом и гиперэкспоненциальным входящим потоком. Информатика и ее применения, 2012, т. 6, вып.1, с. 2-6.

2. Ушаков A.B. Анализ системы обслуживания с гиперэкспоненциальным входящим потоком в условиях критической загрузки. Информатика и ее применения, 2012, т. 6, вып.З, с. 117-121.

3. Ушаков A.B. О длине очереди в системе HM\G\l\oo с абсолютным прио-

ритетом и потерей прерванного требования. Вестник ТвГУ. Прикл. мат.,

2012, вып. 32 , с 7-15.

4. Ушаков А.В., Ушаков В.Г. О длине очереди в системе с абсолютным приоритетом и гиперэкспоненциальным входящим потоком. Вестник Моск. ун-та. Сер. 15, Вычисл. матем. и киберн., 2012, № 1, с. 27-34.

5. Ушаков А.В., Ушаков В.Г. Предельное распределение времени ожидания при критической загрузке в системе с относительным приоритетом. Вестник Моск. ун-та. Сер. 15, Вычисл. матем. и киберн., 2012, № 4, с. 11-16.

6. Ushakov A.V. The heavy traffic limiting distribution of the waiting time in a priority queue with hyperexponential input stream. XXX International seminar on stability problems for stochastic models, Book of abstracts, Moscow, Institute of Informatics Problems, 2012, p. 93-94.

7. Ushakov A.V.,Ushakov V.G. On a queue length in queueing system with preemptive loss priority. XXIX International seminar on stability problems for stochastic models, Book of abstracts, Moscow, Institute of Informatics Problems, 2011, p. 88-89.

Напечатано с готового оригинал-макета

Подписано в печать 04.09.2013 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 272.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Ушаков, Андрей Владимирович, Москва

Российская академия наук Институт проблем информатики

на правах рукописи

04201361553

Ушаков Андрей Владимирович

Приоритетные модели с гиперэкспоненциальными потоками

( 01.01.05 - теория вероятностей и математическая статистика)

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

Научный руководитель — доктор физико-математических наук, профессор Королев В.Ю.

Москва 2013

Содержание

Введение 3

1 Описание модели 12

1.1. Гиперэкспоненциальный поток..................................12

1.2. Дисциплины обслуживания......................................15

1.3. Вероятностно-временные характеристики......................18

2 Длина очереди в системе с абсолютным приоритетом 23

2.1. Описание системы..............................................23

2.2. Основные обозначения и определения........................24

2.3. Предварительные результаты..................................25

2.4. Распределение длины очереди в системе с обслуживанием заново прерванного требования................................28

2.5. Распределение длины очереди в системе с потерей прерванного требования..................................................41

3 Виртуальное время ожидания в системе с относительным приоритетом 53

3.1. Описание системы..............................................53

3.2. Основные обозначения и определения........................54

3.3. Вспомогательные результаты..................................55

3.4. Основные результаты ..........................................59

4 Предельное распределение виртуального времени ожида-

ния в условиях критической загрузки 63

4.1. Описание системы................................................63

4.2. Основные обозначения и предположения......................64

4.3. Предварительные результаты..................................66

4.4. Предельная теорема при условии существования вторых моментов длительностей обслуживания........................67

4.5. Предельная теорема при условии существования моментов длительностей обслуживания порядка 1<7<2............75

Список литературы..................................................82

Введение

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

Первые работы, в которых был проведен содержательный математический анализ характеристик систем массового обслуживания с приоритетами, появились в конце 50-х, начале 60-х годов XX века ([42, 50, 51, 52, 57, 58, 59, 61, 63, 70]). В них рассматривались либо одноканаль-ные системы с пуассоновскими входящими потоками, либо марковские системы с относительным и абсолютным приоритетом с дообслуживани-

см прерванного требования. В дальнейших исследованиях наибольшее внимание было уделено именно однолинейным приоритетным системам с пуассоновскими входящими потоками. К концу 60-х, началу 70-х годов была создана стройная теория таких систем и появились две монографии ([7, 16]), в которых были систематизированы и обобщены исследования в этом направлении. Методы, используемые в этих монографиях, содержат общие идеи: введение вспомогательных дополнительных компонент к исследуемому случайному процессу так, чтобы расширенный процесс стал марковским и использование регенерирующих свойств полученного процесса. Второе свойство позволяет свести изучение процесса на всей временной оси к его изучению на системе вложенных промежутках занятости различных типов, во время которых обслуживаются только требования определенных приоритетов. В результате исследование процесса (например длины очереди) сводится к изучению аналогичного процесса в системе с меньшим числом приоритетных классов и, в конце концов, к системе без приоритетов. Основное отличие методов в этих монографиях состоит в том, что в [16] выводятся системы дифференциальных уравнений в частных производных для распределения исследуемого процесса, которые затем решаются с помощью различных интегральных преобразований (производящих функций, преобразований Лапласа и Лапласа-Стилтьеса). В |7] используется вероятностная трактовка указанных интегральных преобразований и преобразования искомых распределений находятся из вероятностных соображений без составления промежуточных дифференциальных уравнений. В дальнейшем этот метод был усовершенствован и применен к анализу широкого класса однолинейных

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

1) при использовании этого метода алгоритмы нахождения распределения исследуемого процесса содержат большой объем (существенно растущий с ростом числа различных приоритетных классов) информации о распределениях на вложенных промежутках занятости, которая самостоятельного интереса не представляет;

2) этот метод не применим для ряда важных приоритетных дисциплин, для которых нарушается регенерирующая структура процессов обслуживания. В частности, к таким дисциплинам относятся дисциплина приоритета более длинной очереди (см. [45]), дисциплина случайного выбора очереди и др;

3) и, главное, возникают серьезные затруднения с распространением этого метода на системы с неиуассоновскими входящими потоками (см., например, [60, 64, 65, 66, 21, 22]).

В конце 70-х годов появились работы ]9, 20, 34, 35, 36], в которых метод дополнительных компонент был модифицирован для анализа приоритетных систем с эрланговскими и гнперэкспоненциальными потоками. В 90-х годах этот метод был еще более усовершенствован и применен при исследовании систем с рекуррентными потоками ([39, 40, 73]). Однако этим методом удавалось исследовать только распределение длины очереди (и частично периода занятости) в двух разновидностях приоритетных дисциплин без прерывания обслуживания: относительный приоритет и

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

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

При исследовании систем массового обслуживания в условиях критической загрузки в основном используются три метода:

1) первый метод состоит в использовании общих предельных теорем для функцноналов от сумм случайных величин (см. [4, 25, 49, 55, 56]). Чтобы использовать этот метод необходимо представить изучаемый случайный процесс как функционал от суммы случайных величин с достаточно хорошими свойствами. Для рассматриваемых

в диссертации систем обслуживания для длины очереди и виртуального времени ожидания такого представления пока получить не удалось;

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

3) третий метод (который и использован в данной работе) заключается в использовании информации о допредельном распределении изучаемой характеристики. Для рассматриваемых в диссертации систем обслуживания допредельное распределение виртуального времени ожидания задается через преобразования Лапласа и Лапласа-Стилтьеса, поэтому для нахождения предельного распределения используется модификация метода характеристических функций. Его применение сводится к изучению асимптотики решений систем функциональных и интегральных уравнений. Ранее для различных классов однолинейных приоритетных систем такой метод использовался в работах [1, 2, 10, 11, 12, 14, 15, 18, 19, 26, 27]).

Объект исследования. Объектом исследования являются однока-нальные системы массового обслуживания с неограниченным числом

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

Задачи диссертационной работы Для достижения поставленной цели необходимо решение следующих задач:

1) разработка методов анализа систем массового обслуживания с гиперэкспоненциальным входящим потоком и различными разновидностями абсолютного приоритета;

2) изучение основных характеристик приоритетных систем массового обслуживания: вектора длин очередей из требований каждого приоритета, виртуальных времен ожидания начала обслуживания, различных промежутков занятости системы;

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

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

Методы исследования. В диссертации используются

1) различные методы теории вероятностей и теории случайных процессов: методы теории марковских процессов, метод дополнительных компонент при исследовании немарковских процессов, метод характеристических функций;

2) методы теории функций комплексного переменного и функционального анализа;

3) методы линейной алгебры;

4) методы теории дифференциальных и интегральных уравнений, в том числе асимптотического анализа решений этих уравнений.

2) найдены преобразования Лапласа-Стилтьеса длительностей различных промежутков занятости системы с относительным приоритетом;

бованпй одного приоритета: FIFO (прямой порядок обслуживания) и LIFO (инверсионный порядок обслуживания);

4) получены предельные распределения виртуального времени ожидания при дисциплине FIFO, различных соотношениях скоростей стремления времени к бесконечности и загрузки к единице и различных моментных ограничениях на время обслуживания;

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

Апробация работы. Результаты работы докладывались и обсуждались на научно-исследовательских семинарах "Теория риска и смежные вопросы "(факультет ВМК МГУ им. М.В. Ломоносова), "Аналитические методы в теории массового обслуживания11 (факультет ВМК МГУ им. М.В. Ломоносова), XXIX и XXX (2011, 2012 гг.) международных семинарах по проблемам устойчивости стохастических моделей, на V и VI (2011, 2012 гг.) международных рабочих семинарах "Прикладные задачи теории вероятностей и математической статистики, связанные с моделированием информационных систем11.

Публикации. Результаты диссертации опубликованы в семи работах [29]—[33], [71], [72], из них первые пять - в журналах, входящих в список

ВАК "Перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора и кандидата наук".

Глава 1

Описание модели

В этой главе будут приведены описания и основные свойства элементов рассматриваемых в работе моделей: входящих потоков, дисциплин обслуживания, вероятностно-временных характеристик.

1.1. Гиперэкспоненциальный поток.

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

Рекуррентным называется поток, у которого интервалы времени между последовательными поступлениями требований являются независимыми и одинаково распределенными случайными величинами. Функцию распределения интервалов между поступлениями будем называть функцией распределения потока и обозначать А^). Соответствующую плотность распределения (если она существует) обозначим а(£).

Рекуррентный поток называется гиперэкспоненциальным, если

Л/ , , -ехр(-а^)) , х^О,

А(х) = { 3=1

О , ж<0,

, Еедехр(-а^) , х^О, а{х) — ^ 3=1

О , ж < О,

где аг- ф а^ при г ф с^ > О, сг = 1-

г=1

Математическое ожидание и дисперсия интервалов между поступле-

ниями требований в гиперэкспоненциальном потоке равны /11 = ]Г] с.-бь"1

3=1

N _ /М \2

и а2 = 2 с,а •2 — см,1 1 соответственно. Отсюда находим, что ¿=1 /

коэффициент вариации га = — равен

т —

-1\2

£ асз 1 - а -

1 + -.-

Таким образом, коэффициент вариации гиперэкспоненциального потока всегда больше 1. Более того, для любых заданных ¡1\ > 0 и о ^ /¿1 существует гиперэкспоненциальный поток второго порядка (т.е. поток с N = 2) такой, что у него будут математическое ожидание и дисперсия интервалов между поступлениями требований равные ¡1\ и а2 соответственно. Действительно, положим х = а^"1, у = а^1- Тогда

сх + (1 - с)у =

2сх2 + 2(1 - с)у2 - (сх + (1 - с)у)2 = а2. Отсюда

/(1 — с)(<т2 — с(а2 -

Х = 2С '

Если взять 0 < с <-, то х > 0, у > 0. Таким образом, используя

0- + /Л1

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

Интерес к потокам с коэффициентом вариации больше единицы обусловлен тем, что часто при моделировании технических систем реальные потоки заменяют пуассоновскими (для которых коэффициент вариации равен 1). Но большинство важных характеристик функционирования системы (длины очередей, времена задержек, вероятности потери требований и т.п.) существенно зависят не только от ннтенсивностей потоков и математических ожиданий времен обслуживания, но и от моментов более высоких порядков. В частности, во многих разновидностях систем обслуживания математические ожидания длин очередей и времен задержек (при одной и той же загрузке системы) увеличиваются при увеличении коэффициента вариации входящего потока. Следовательно, замена реальн�