Ветвящиеся процессы в теории массового обслуживания тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

йЗИСТЕРСТВО НАУК'!, ВЫС111Е.4 ¡ШИ ¡1 ТЕХШЛЗСКО:! ШШ РОССИЛСКОЛ ФВДЕРА1Ш

Р Г 8 юффСШ ГОСУДАРСТВЕНШЛ ЖЧйЕРСЯШ' 3.Ломоносова

Механико-члатекатическиЗ сакультет

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

ГР1ЕВШН Сергей Алексеевич

УДК 519.21Ь

ЗЕГВЯЕКЕСЯ ПРОЦЕССЫ В Ш>Ш МССОБОГО ОБСЛУЖИВАНИЯ /01.01.05 - теория вероятностей я математическая статистика/

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора ,!изико-катег/дт:;чэских наук

Москва - 1393

Работа заполнена в Московском государственном университете т. К.3.Ломоносова.

Официальные оппоненты:

член-корреспондент РАН, доктор физико-гятегатических наук, профессор

Б.Л.Севастьянов

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

В.В.Калашников

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

А.В.Печинкин

Бегущая организация ¿'¡атеьатический институт им,В.А.Стек-лова РАН.

Защита диссертации'состоится 13 пая 1994 г.

з 16 час. (5 или. на заседании специализированного Совета Д.053.05.04 по математике при Московском государственном университете ж. К.й.Локоносова по адресу:

119899, ГСП, Москва, Ленинские горы, МГУ, лсеханико-катеиатический факультет, аудитория 16-24.

С диссертацией можно ознакомиться в библиотеке механико-катекатического факультета ¡¿ГУ (14 этан, Главнее здание).

Автореферат^разослан 13 апреля ' 1994 г.

¿ченыл секретарь специализированного Совета Л.053.05.04 , доктор *изико-[ч'дте!.:атическис наук, профессор

ОЕАЛ ХШКГЖСТИКА РАШШ

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

Глубоко разработанная, эта теория позволяет не только находить стационарные характеристики различных С'/Ю, но и исследовать их асимптотическое поведение при различных предположениях . В частности, этот подход позволяет получать предельные теоремы в условиях больяоЯ нагрузки /когда нагрузка стремится к I/ и для перегруженных систем /когда нагрузка больше I/. Зообше, ложно констатировать, что применение ветвящихся процессов позволяет репить иного важных и интересных задач в теории кассовго обслуживания, большинство из которых не когут быть исследованы с локошьэ других -подходов.

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

Методика исследования. При исследовании, покимо теории ветвящихся процессов, использовал-сь теория регенпрмруэдях процессов, теория случайных г.'ер, теория правильно кешгкдихся фун-КЦ2*.

г

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

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

найдены стационарные характеристики различных систем кассового обслуживания типа hVg/i/ps и следующими

дисциплинами обслуживания: случайной, с повторны;»,и вызовами и несколькими типами требований, с дисциплиной обслуживания первым требования с наименьшей остаточной длиной sept , с равномерны!/., обобщенным разделением процессора и их модификациями;

проведено исследование систем иассовго обслуживания в условиях большой нагрузки;

изучен случай перегруженных систем, когда нагрузка больше I ;

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

Апробация. (Материалы диссертации докладывались:

на 5-ой международной Вильнюсской конференции по теории вероятностей и математической статистике./I98S/;

на 1-ом Всемирном конгрессе по ветвящемся процессам /Варна, 1293/;

на советско-шведском симпозиуме по ветвящемся процессам /Киев, 1990/;

на семинаре в университете г.Ольборг, Дания /1992/; на семинаре в университете г.Гетеборг, Швеция /1992/; на семинаре "Избранные задачи теории вероятностей" Г.ТУ

под руководством В.М.Круглова, В.X.Золотарева, В.В.Калашникова;

на семинаре "Вероятностные методы в технике" МГУ под руководством Б.З.Гнеденко, Ю.К.Беляева, А.Я.Соловьева;

на семинаре "Вероятностные методы в дискретной математике" Математического института им. В.А.Стеклова под руководством Б.А.Севастьянова, В. 5.Колчина, А.М.Зубкова.

Публикации. Основное содержание диссертации опубликовано в 10 статьях, приведенных в конце автореферата.

Объем диссертации. Диссертация состоит из введения, 4 глав и списка цитированной литературы. Работа изложена на 267 страницах. Список литературы содержит 65 наименований.

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

По-видимому, первые применения теории ветвящихся процессов к теории кассового обслуживания содержатся в статьях 1 2

Borel- , Kendall . В этих работах показано, каким

образом результаты об общем количестве потомков в ветвящемся процессе могут быть использованы для исследования продолжительности периода занятости б системе ы/о/1 . Позднее эта

Borel E. Sur l'emploi du thecreme de Bernoulli pour faciliter le calcul d'une infinite des coefficients. Application au problème de l'attente a un guichet.- C.H. de l'Acadenie

des scencea, 1952, v.214, p.452-456. 2

. Kendall D.G. Some problems in the theory of queues.-J. Roy. Statist. Soc., 1951, B13, p.151-185.

1-4 5

связь была обобщена Neuts , De Иеуег, Teugels

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

Оказывается, однако, что связь между теорией ветвящихся

процессов и теорией кассового обслуживания гораздо теснее и

<

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

1. Heuts И. The queue with loiason input and general service times, treated аз a branching process.- Duke Math. J.,

1969, v.36, p.215-232. 2

. Neuts Л. Two servers in series, treated in terns of a Markov renewal branching process.- Adv.Appl.Probab., 1970, v.2, p.110-149.

Keuts ii. A queue subject to extraneous phase changes.-

Adv. Appl. Probab., 1971, v.3, p.78-119.

4 ^

. Keute M. The Jiiarkov renewal branching process.- Lecture

notes in econom. and mathemat. systems, 1974, v.98, p.1-21.

De Иеуег A., Teugels J. On the asymptotic behavior of the distributions of the busy period and service time in Ji/G/1.- J.Appl.Probab., 1980, v. 17, p.802-813.

данно;! диссертации.

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

Кроме Формулировок и доказательства базисных теорем о связи СМО и ветвяаихся процессов, в этой главе рассматривается поведение систем обслуживания в стационарном режиме, когда нагрузка j5 < 1

Значительное внимание в первой главе уделено различным видам разделения процессора, г.е. ситуации, когда обслуживающий прибор /процессор/ шкет одновременно обслуживать несколько требований. Простеллий я наиболее важный частный случай называется дисциплиной равномерного разделения процессора PS (Processor Sharing) , которая является одной ?з основных в теории компьютерных и коьмуш'кащтоннцх систем. ]рн згой дисциплине все А/ требованил, стоящих в очереди, заслуживаются одновременно с интенсивностью 1/А/ . Тре-SoBaKiïH поступа-лт в систем группао через показательно рас-¡ределенные времена со средни: . Производящую функцию гасла требований в каждо" группе обозначим f(s) . Каждое тре-!ован::е х характеризуется своей длиной , т.е. вредней, которое требуется для обслуживания JX при .условии, :то процессор обслуживал бк только это требование /с интенсив-

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

одинаково распределенными для всех требования JC . 3 ходе обслуживания состояние требования зс в момент Т задается обслуженной длиной Vx (Т) /количеством обслуживания, которое х получило вплоть до момента Т / и необслуженно" длиной ~ ^^ • Таким образом, полное описание состояния СМО в момент Т" включает в себя знание длины очереди QCt") и знание величин

для каждого из требований i ••■ ■> присутствующих в этот комент в системе.

Есть большое количество работ /см. обзор Yashkov1 /, изучающих систему m/g/1/ps , однако, до работ ав-

тора диссертации, практически ничего не было известно о случае группового поступления mk/g/i/ps . . Изучению последней системы посвадгн §4 главы I. Использованный при этом кетод сведения к ветвящимся процессам срабатывает и в гораздо более общей ситуации, для так называемой дисциплины обобщенного разделения процессора gps . Поэтому изложение в главе i начинается именно с системы mz/g/i/gps.

Дисциплина gps возникает, если км захотим рас-

смотреть консервативную /т.е. с единичной производительностью процессора/ СМО, в которой интенсивность обслуживания требования эс. монет зависеть от обслуженной длины Vx (Т). Есгествекный путь сделать это состоит в следующем. Пусть интенсивность обслуживания требования £=!,..., QCT)

1. Xashkov S. Processor-sharing queues: some progress in analysis.- Queueing Systems, 1987, v.2, p.1-17.

равна

ФСТ)

А^С^сn)/ JZ Ax.(Vx.(T)\

где Ах. (•), J = i,..., QCT) независимые и одинаково распределенные случайные процессы. Эту дисциплину обслуживания

мы обозначим GPS . Подчеркнем, что 2-х,- и ^с-(')

i J

могут быть зависимы.

Дисциплина ps является простейшим частным случаем дисциплины cps с функцией Лх^р= ^ (j} £ СО,

Сред'л других частных случаев отметим дисциплину dps (Discriminatory Processor Sharing)ранее изучавшуюся, например, В Payolle et al.1 и систему M/G/1/SRPT , О кото-

рой будет говориться подробнее ниже.

При рассмотрении системы ux/g/1/gps главны:.!

объектом изучения является введенная автором величина Q ^ ("0} которая определяется следующим образом

Случайные процессы (р^ предполагаются независимыми и одинаково распределенными для всех требований ОС /и удовлетворяющими некоторым техническим условиям/. Суммирование проводится по Есем требованиям X. , пришедшим в СКО не позднее момента Т . Как следует из следующего замечания,

Fayolle Q., Hitrani X,, Iasnogorodski R. Sharing a processor among many job classes.- J.Aasoc.Comput.iiach., 1980, v.27, p.519-532.

знание Q^ С"1*) Для различных процессов /называемых

характеристиками/ полностью описивает состояние СМО в ыокент Ерекени Т"

Если £ обозначает число требований, чьи об-

служенные длины принадлежат множеству ß, В С (0} &Q*), то 1Тт{'] !.-.о>:ет рассматриваться как случайная мера. Для любой неслучайной функции ^ : С О, —> СО,<Х>), а(-)£ 3) СО, со") [/окно определить характеристику

оо

о

Аналогично, если' = t^ ^СтНб]>

оо

ТО QfCT)= ^(^гг^(^) , где

О ^

Таким образок, зная Q^CT) ,-можно найти преобразование Лапласа случайных мер Uj- и UV , описывающих состояние СМО в момент Т .

Для изучения Q^ вводится ветвящимся процесс

Кра\ша-У.ода-Ягерса t посчитанный с помощью характе-

ристики /Ol'.. Jagers, Nerman1 относительно ТаККХ

процессов/. Характеристики ij> и связаны опреде-

ленным образом. Аналогично, по процессу А определяется характеристика С . Вводится также модификация рассматриваемого процесса Крампа-^ода-Ягерса, в которой про-

. Jagers P., Nerman 0. The growth and composition of branching populations.- Adv.Appl.Probab., 1984, v.16, p.221-259.

исходит иммиграция новых част ни в случае вырождения процесса.

В §2 главы I доказывается следующая основная ."•еорека о системе мх/с/1/срз.

Теорема 2.1. Систему 11Х/С/1/СР5 и соответствующий

Еетвящийся процесс можно определить на одном вероятностном

10 Ч Л "У

пространстве так, что > Т ^ О,

где СТ) однозначно определяется из уравнения

О

В §2 сформулировано таюге аналогичное утверждение и для виртуального времени ожидания.

Основываясь на этой связи, в §3 главы I найдена преобразования Лапласа стационарных распределений и виртуального времени ожидания К/^ /требования 0 , имеющего длину Еф / в терминах соответствующих ветвящихся процессов. Чтобы продемонстрировать характер получающихся результатов приведем следующую теоре^. ,

Теорема 3.1. Если нагрузка , то ^ (Т)

Т-» со я

• со

где 91*;-*, «О я Еехр

3 §4 главы I разработанная техника применяется к системе м^/в/!/РЭ . Следует ответить, что несмотря на обилие работ,

посЕЯзеннкх системе и/g/i/ps , случай группового

поступления практически ^никогда не рассматривался. Он значительно сложнее к это видно y>:.e ка примере нахождения средних значений Е Q и Е W0 . С^оркулируем соответствующее утверждение. 0бозначм.с через Bit)- PC 2 i~t),

i

туккшго распределения длины требования j^Lt)- A-f ^ jj (i~

о

РО

(i)

Теорема 4.2. Предположим, что J><i} f < OQ и что система HX/G/1/PS находится в стационарном ре-

жиме. Тогда

ос .

о

2о СО 0 0 ■ d

Б §5 главы I ветвящиеся процессы применяются для решения одно» задачи, поставленной /но не решенной/ в Disney et al.1

Disney R., Klutke G.t Kiessler P. Interoutput times in processor sharing queues with feedback.- Queueing Systems, 1988, v.3, p.363-376.

Расскотрик систему а/о/1/РБ с мгновенно;.] обратной

связью, в которо!? каждое требование в момент завершения обслуживания /назовем это событие выходом/ с вероятностью р мгновенно возвращается на обслуживающий прибор. Требуется ка2?и распределение промежутка времени 3) между дв.умя последовательными выходами в стационарном режиме.

Предполагая, что в момент О СЖ) находятся в равновесии, обозначим через 3? момент первого после 0 выхода. Стандартное применение теории регенерации показывает, что

9

РСзе^СЕЗ))'"1 $РО»и)<Ь и

поэтому можно искать

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

оО

Теорема 5.1. Пусть Р= Да (¿-р}"^ «= \(1"

■ <*> о

= а1 Тогда

*

со

^е"итР(зе>т)<1т = уи-р -

-1 Г Т -<Д+ч)ч |

-I

о

о

о

/

Разлнчкые дисциплины обслуживания могут быть получены как предельные частные случав дисциплины gps . Рассмотрим, напг;".:ер, последовательность функций ^(О- СО,1*^)"* C0,00")f V = ¿,2,... таких, что (TiV^C^)-»^ У-» од для любых фиксированных Т^ > Т^ > 0 и пусть с::сге:.:а jíx/g/ i/gps задается функцией (Т) -

= (¿-у) i (Те. ПО, i)). Тогда в пределе при У-*00 получается C.V.O, в которой в ка_~дш: момент времени обслуживается то требование, которое имеет наименьшую остаточку» длину /это требование единственно, если дополнительно предположить, что функция распределения В> непрерывна/. Эта дисциплина обслуживания называется srpt (Shortest Remaining Processing Time). Она была введена

в 1966 г. в работе schräge, Miller1 к представляет значительный интерес, так как известно, что она обеспечивает кинжальную длину очереди в классе всех консервативных дисциплин обслуживания. Однако, само стационарное распределение длины очереди не било известно до самого последнего времени, несмотря на усилия предпринимаете в этом направлении. Поскольку в §3 главк I было найдено стационарное распределение

Qf для сксте:.:ы ux/g/1/gps с произвольной

1ункцие/. Д , то устре:ляя /V-» оо , ш имеем право с.-идать получения аналогичного результата для системы ax/g/i/sr?t. Эта идея реализована низе, в Теореме

6.1, которая была приведена без доказательства в работе

1. Schräge L., Miller L. The queue ii/S/1 with the shortest remaining processing time discipline.- Operat.Res., 1966, v.14, p.670-684.

-гз-

1 2 Grishechki.ii , а в работе 0г1зЬесЬк1п содер-

жится ее доказательство. Одноврег/.еяно, независимо и другим методом эта же проблематика была исследована в работе ЗсЬаззЪеггег3 . В ней было получено стационарное рас-

пределение случайной керы • дяя системы а/в/т/зятт.

Наш результат более об'ди''-:, так как :.:н рассматриваем групповое поступление и ф^СО- это более обаяй объект чем •

Теодег.'а 5.1. Предположим, что _р < 1 , функция распределения 6 непрерывна и характеристика f удовлетворяет .условиям /а/, /б/, /г/ из §2. Тогда (¡^(Т) ф^ 7" -» оС и для любого фиксированного и 1 О

РО _

о

где функция 0 < ^ < со Это единственное /в клас-

се неубывающих, непрерывных функций/ решение уравнения

1. Grishechkin S.A. On connection between the theory of branching processes and queueing theory.- Proceedings of the 5th Vilnius Conference on probability' theory and mathematical statistics, 1989, v.1, p.455-462.

2

. Grishechkin S.A. On a relationship between processor-sharing queues and Cruap-Mode-Jagers branching processes.-Adv.Appl.Probab., 1992, v.24, p.653-69S.

Schassberger R. The steady-state appearance of the M/G/1 queue under the discipline of shortest remaining processing time.- Adv.Appl.Probab., 1990, v.22, p.456-479.

t .

o

„.AxpÍA

о

X

а

+ ^(cpo^cU-v 1

a *

0.3 (è, ' м) = Л E i(j< ^(-ц^-*))-

f¡ / -

• e,xp Ja ^(f h]-

5унк1ия 0< Ф ^ 1, ^ 0 представ-

ляет собой единственное ренение уравнения

к 1 + ^ехр^Л о

В §7 глава I ветЕЯ"лиРся пропзссы применяете.-! к изучении еве 4 моделей СКО. Последняя из этих моделей наиболее общая. •Это система вида ых/а/1/пт с повторными вызоззуи и И

типами требований, описываемая олодуэдин образом. В соответствии с пуассоновсккм потоко;/. с параметром А з СУП постугла т группы требованл;'. П возколшых типов. Количество требозанид в одной группе ^ - ( ■■■ > ) , где ~ число требовании I -го типа, задается производныеП рункцие:'!

= ^Кслл в момент прихода гру.-зг тробозан:?:; обслуниваиск:: прибор свободен, то случа;';-кэ выбирается очно из требований типа £ л лто гребовани-3 поступает ;:а обслуякзаки-з. Гйрп предполагается незл •

зисимыуз я одинаково распределенными для разных групп и ^ - Ь 0 л.н., где 1К обозначает вектор, имешич I та к -зн месте. И.чдчз, если прибор заияг, го все требования пз группы ярзсееданяатся к очереди. Каждое требования типа I ::з очереди нелвяедш от других •¡члбовании через .-склза-•гзльаэ распределенные времена со среднем ^Ч• прочерке?, кч о^х'боднлея ли обслуживалиприбор, и та;; до тех пор, по-.41 не ¡'опадет на обслуживание. Функция распрецеления дяитзль-

г

кости обслуживания требования с -го типа равна •

Описанная модель является некого более общей, чем при-1 2

веденная в работах Ки11сагп1 , РаПп , где пред-

полагалось, что -р($")= с± ^СЬ^) ¡^-^(Оз

О, С* t ..ЛСп- Iй Н (О - э'го некоторые вероятностные производящие функции. В этих работах были найдены математическое ожидание и дасперсия длины очереди /в стационарном режиме/ и дальнейшее исследование представлялось весьма сложным.

Если (2=1 , то получается система Лс/1/М с повторными вызовами и одним типом требований, изучению которой были посвящены многочисленные работы /см. обзоры Тешр1е^п, Уш^3, раИп4 /. Однако до работ автора

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

1. Kulkaxni V.G. Expected waiting times in a multiclass

batch arrival retrial queue.- J.Appl.Probab., 1986, v.23,

p. 144-154.

2

. Pelin G. On a multiclass batch arrival retrial queue.-Adv. Appl. Probab., 1988, v.20, p.483-487.

3. Templeton J., Yang T. A survey on retrial queues.-

Queueing Systems, 1987, v.2, p.201-2335 1989, v.4, p.94. *• ialin G. A survey on retrial queues.- Queueing Systems, 1990, v.7, p.127-168.

Если,сохраняя постоянны.™ остальные параметры СМО, устремить K=i,...,n к бесконечности так, что отношение fc JJ^j будет-стрег/кться к некоторой константе /обозначим ее С\, /с^ / для любых ¿, j , то получается система с динамическими приоритетами, введенная в работах Гришечнин*, Gavet, Morrison2, Gaver, Morrison, Silveria3. В этом случае в момент освобождения обслуживающего прибора вероятность того, что на него поступит какое-то конкретное требование Í -го типа относится к аналогичной вероятности для j -го типа, как • Иными словами, если в . этот момент в очереди находится QK К = 1,..., п требований К -го типа, то вероятность поступления на обслуживающий прибор любого требования L -го типа равна Л/(/<!<?i<-T) + Qn.irr)).

__ Если n = 1 , то описанная дисциплина обслуживания сеодится к классической случайной дисциплине SIRO , при которой выбор на обслуживание осуществляется равновероятно из Есех требований, стоящих в очереди.

Гришечкин С.А. Об исследовании систем массового обслуживания

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

Докл. АН СССР, 1ЭЬ8, т.300, Я, с.23-26.

2

. Gaver D., Morrison J. Heavy-traffic analysis of raultitype queueing under probabilistically load-preferential service order.- SIA4 J.Appl.iiath., 1991, v.51, p.1134-1149.

Gaver D., Morrison J., Silveria R. Service-adaptive jnultitype repairman problems.- SIAU J.Appl.iiath., 1993. v.53, p.459-470.

Яеречлслзкнам ОНО соответствуют слеауяцие типы ветвящихся процессов. Системе m^/q/i/siro отвечает марковски:: гетвяиг.г^ся пронгсс, в котором частник «иву? показательно распределенное время ¡1 затем делятся в соответствии с производящей функцией His)- )г 0 A SC^jV

о

Системе с динамическими приоритетами соответствует марковски:: ветвянцШся процесс с И типами требований. Наконец, системе с повторными вызовами и Г1 типами требовании отвечает марковский' ветвящиеся произсс с п ткпаки требований и шштрапией. В зтсм процессе частот С -го типа живет показательное время со средним и затем делится на

случайное число потомсов с производящей функцией

V:; (S^,,.., S^)- dB-(ij\'(¿л,-шграц::г. новых частиц

, О

ПРОИСХОДИТ группы.-!! В ЗООТЗбТСГСЗйа С цуассоаовск'.-й! потоком с ::нтеас?вкост135 А , прл этом количество ^мигрантов в однэ;! груше зяаается проазвоак»я.! функциел =

г Т A(f(svi)4 . / aoislf...)S„) = e ^ "le 1

l-o

J §7 гга.тзи I показано, как*?, сбразсм сслоснле характеристика ухазднннх CV.0 вырйхготсч в терминах соогдзтзгеуквдх ветветхся цроцессоа. D частност::, найлегш прсзсн.азовн>;ип: Лапласа дтанч очереди и виртуального времени отдания для системы с поэторнами вызовами к несколькиг«: типами ?рй.5ова-

яяй в стационарною pezswe. Sra преобразования Лапласа вщ&же-нн через яроизЕодздуэ £ункшнз стационарного распределения числа частиц в ветвящемся процессе с шкагранхей.

Случай, когда нагрузка у ^ £ носит название' большой нагрузки к занижает Е2з:ное место б теорки кассового обслуживания: 2то объясняется прежде всего практическими причинами -стремлением загрузить G.VÍ0 до предела ее зозмоаностеЗ. Стандартная постановка задачи о большей нагрузке следующая - рассматривается, например, длина очереди Q г, стационарном режиме при нагрузке у < i , а затем устремляется pfi Требуется получить соответствующую предельную теорему для Q. Именно такого типа результаты выводятся во второй главе диссертации.

у-

б §1 рассматривается система а /g/1/gps и до-

казываются предельные теоремы для виртуального Бременя ожидания \(/q и величины QV" , Отметим, *?то эти результаты остаются новыми н недосткжкми другими методами и в частных случаях система A'ü/V&ís - для сг.стек вида

aX/G/vps, ü/g/1/dps.

Сформулируем соответству-сдие результаты'. Предположим, что в сготзмз гденяетск только интенсивность входного потока А так, что A t (f«> г.де ' f =

= — fcs>| , WdSíx). полон®, = Í-Plo

'as: W J -r

o

7. станем писать Q^ , q , чтобь: подчеркнуть зависк-

KOCT5 от кагрузк::.

Тестзема I.I. Пусть 4-О ц предположим, что выполнены

следушие условия: )(2)

*/Г<

оо

б/ ь

в/ ^«-(^е^^^^оо,

г/

о О <3

д/ Случайные величины

равномерно

интегрируемы для любого "¿0 "> 0.

е/ 1ункции Е С СО, , 1 в СО,^непосредственно

интегрируемы по Риыану. Тогда

I X1 (£ш)) Сх) . ' *

Теорема 1.2. Пусть О и предаюлонкк, что выполнены следующие условия:

а/ га)<»с. 6/

в/ гш<ъо.

г/ Случайные величины си), t6Co,¿Л равномерно интегрируемы для лобого > О.

д/ Функция ЕС(-£), /ГО,со) непосредственно интегрируема по Ваалу. .

Гогда

где -2 - эхо случайная величина, независящая от А^ с р(^ч) = е~ч, ч^о.

В §2 главы 2 рассматривается система вида 01/с/1/рз в условиях большоЛ нагрузки. Ута система задается распределением времени Дп (-1 между последовательными гриходами требований и распределением ВС' ) длины требования. Изменяя

масштаб времени, г.:ожно считать, что ^ ^ йб^) -1.

о

Большая нагрузка будет тогда соответствовать ситуации, когда оО

г СО.

«л считаем также, что

со оо

/это стандартные предположения при исследовании систем вида

ОО 00

01/С/1 / и обозначим ~

о 0

Несмотря на то, что есть много работ, посвященных дис-

цшшгае разделения процессора, ми знаем только две, касающихся системы GI/G/1/PS . Baccelli, Towsley1 доказали, что времена ожидания в такой системе являются ассо-

2

пипрованными и sengupta предло:кил некоторую аппрок-

симацию для времени ожидания в системе gi/g/1/ps. Ко эта работа Sengupta не является математически строго": и, более того, его аппроксимация не является точной в условиях большой нагрузки. Как следует из доказанной в диссертации Теоремы 2.2, эта аппроксимация точна лишь в случае, когда о! - 2. или § - 2.

Сформулируем основные результаты §2 главы 2. Пусть и Wn (£0~) - это длина очереди я время ожидания в стационарном режиме.

Теотема 2.1 Справедливо соотношение теорема 2.2. Справедливо соотношение

1. Bacoelli P., Towsley D. The customer response times in the processor sharing queue are associated.- Queueing System 3, 1990, v.7, p.269-232.

2

. Sengupta B. An approximation for the sojourn-time distribution for the GI/G/1 processor-sharing queue.- Stoch. Models, 1992, v.8, p.35-57.

В §3 главы 2 получены предельные теоремы для системы ир/а/т/п? с повторными вызовами и несколькими типа-

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

5ормулировка предельной теоремы достаточно громоздка, поэтому мы приведем ее здесь в упрощенной фзрме. Пусть

^у это число требований £ -го типа в стационарном режиме, а - виртуальное время ожидания требования

I -го типа. Предполагается, что интенсивность входного потока Л. меняется так, что рТ:1 и что конечны вторые моменты, соогвегствуэдке распределениям и производящей функции f (5^,.., $„ ).

Теорема 3.1. Пусть уТ 1 . Тогда для любых =

= ¡г

Д f¿4'

3-1

и+к) \ но;

где С, 3 - некоторые явно выписываемые константы.

В главе 3 рассматриваются перегруженные (i < J> < ооCtiO. Несмотря на есэ естественность -роблешгнки, такяе СД;о практически не изучались ранее /за ксклэченкем нескольких простых результатов/. Va счптаек, что причины этого в следующем: на герЕый взгляд кажется, что трудно наИти матакатически интересные задачи в это:: случае. Еапржер, для систеш M/G/1 с дисциплиной Р1Ю (First in First Out) тривиальные

рассуждения в духе закона с5ольших чисел показывают, что Q СтО/Т-» (]>-1)/£11,п.н., Т-э со . mo:ího получить результат и типа центральной предельно.? теоремы для Q СТ) / что лишь не.мюгта сложнее/ и, казалось бы, вся проблематика на этой исчерпывается.

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

сложную, например PS , делает задачу об определении асимптотики QO") неожиданно очень сложной. В этом случае предел Q СТ)/Т, Т-* 00 будет иным чек для дисциплины PIFO и доказательство этого факта опирается на глубокие теореш теории надкритических ветвящихся процессов. Во-вторых, привлечение ветвящихся процессов позволяет резко разнообразить всю проблематику: оказывается, что можно ставить много интересных задач даже для классических систем. Чтобы показать это, сформулируем один результат из §1 главы 3, касающийся системы

itVG/VSIRO.

Поскольку для случайной дисциплины sieo длина очереди QÍT) та .те, что я для дисциплины pifo , то Исследование ее асимптотики тривиально. Ясно, однако, что в боль-

шо:: момент времени Т разные требования провели в очереди различное время - возникает, так называемое, "распределение возрастов". Чтобы -¡оркализовать ситуации, обозначим через Q (Т, сТ) число тех из стоящих в момент Т в очереди требований, которые пришли в систему до г.омента СТ} 0< С< i. Стабилизируется ли "распределение возрастов", т.е. стремится ли . Q (Т, сТ) / Q СТ) к пределу /и какому/ при Т ОО ? Для дисциплины PIPO эта задача, опять-таки, тривиальна, но для случайно:' дисциплины она гораздо сложнее. Как показано в Теореме 1.2 главы 3

Jl Cj>-i)

QCT, СТ)/9СТ)-» с /т.н. , 7~-»t>o.

В §1 приведены и другие теоремы относительно системы ¿íx/g/i/siho.

В "2 главы 3 расс;/лтркв2ется система U^/G/i/RT с повторными вызовами и несколькими типами требований. Обозначим через Q¿ СТ, сТ) число требований типа i , стоящих в очереди в момент Т и пришедших в систему не позднее момента с,Т . Следующая теорема составляет главное содержание §2 главы 3.

Теооема 2Л.- Пусть Í < $> < со, Тогда

/г I/ tu) н-d

^Z^ie^-Dtvj

T iri

01

при , гле V- = ^/(/Чу^О, ) = 1>'~> П

и • если выделенное требо-

вание 0 имеет тип I . Число ^ совпадает с максимальным корнем уравнения

(I

х

3 §3 главы 3 рассматривается система М /с/ч/РБ. Срорг/улируем несколько результатов из эгоД части диссертации.

Теопруд 3.1. ¡Заполнено соотпошонлс

<}СТ) /Т } П.и., Т"-* «х>,

где значение ^ определяется из уравнения

о

(О

Теосела 3.2. Пусть 9 а (т) /соответственно ф (Т) / обозначает число требований, присутствующих в СИ) в момент времени "Г и имеэаих обслуженную /соответственно необслужен-нуч/ длину, заклэченкуэ в интервале С03о,~] . тогда при у—> 00 справедливы соотношения

^Ч-п/дсг) п.«.

о

ОО

Теозема 3.3. Выполнено соотношение

Чсг)/т£ и.,

Теотзема 3.4. Для лабой константы 0 < с < 1

С}ст,ст)/с?ст)-> f")л ^ и-п.н.т->оо.

В §3 доказаны к другие теоремы о системе ¿РусЛ/рэ.

Четвертый параграф главы 3 посвящен рассмотрения перегруженных систем вида . Подход и результаты сходны с г рпз еденной в 53. 3 частности, доказаны аналоги сформулированных вкге теорем 3.1-3.4..

В §1 главк 4 рассматривается система вида М^/¿1/1/НИ с круговым доступом, В этой системе обслуживающее устройство /процессор/ обслуживает вначале некоторый фиксированный кусок длительности Д первого стоящего з очереди требования, затем кусок д второго требования и так далее до последнего у;з требований в очереди. Затем процессор возвращается в начало очереди и процесс 'обслуживания продолжается аналогичным

образом. Новые требования, приходящие в систему, становятся в конец очереди. Предельный переход приводит к сис-

теме аХ/Л/1/РЗ.

Обозначил через Д, Л^,^) время нужное для обслуживая;^ выделенного требования с длиной и Л , при условии, что в начальный момент времени в СкО присутствовало еще Ы~ - ^^Х ДРУГИХ требований. При этом предполагается, что

Д/^ требовании стоят б очереди перед выделенным требованием, а - за ни,;. Рассматривается задача об описании предельного поведения ^(пд} Л^, Л^) при У-> "¡О и /::ли/ П ео .

В §1 осуществлена редукция к ветвящаяся процессам Галь-тона-Ватсона и описан весь возмогшей спектр предельных теорем, соответствующих случаям, когда нагрузка у < 1, или у £.

В заключительно;.'! §2 главы 4 диссертации рассматриваются различные, эффекта связанные с понятием нерегулярности в теории ветвящихся процессов. Зетвя.аи':ся процесс называется нерегулярный, если в нем в конечнил момент времени с положительной вероятности образуется бесконечное число частиц. Оказывается, что с точки зрения теории массового обслуживания это свойство эквивалентно тому, что требования, приходящие в СУЮ, могут ждать окончания обслуживания бесконечно долго. На основания этой связи в §2 выведено необходимое и достаточное условие конечност:: времени огддания для системы вида мх/с/1/31Ю. В частности,, показано, что изменение скорости обслуживания в любое фиксированное часло раз не влияет на регулярность СГ.Ю. Это делает неозсданным следующий эжект: рассмотрим две регу-

лярные СШ типа ¿/а/1/э1Ю с одной и той хе интенснвно-

сть'о входных потоков, ко разными распределениями В^ к

длин требоваяи". Объединим оба потока требовали!: в один, но

и увеличил: в 2 раза скорость обслуживания требований. Оказы-.

гастся, что когко подвести такоЗ гшимер функций В . и 6. ,

• 1 л

что. эта новая скстека будет нерегулярно"! несмотря на то, что обе первоначальные систекы являлись регулярными.

3 52 доказана так™е одна предельная теорема, связанная с необходимость*) исследовать ветвящиеся процессы близкие к нерегулярным. Рассматривается система с дгумя ти-

па:»::' требований. Требования 1-го.типа имеют относительный приоритет по сравнению с требованиями 2-го типа /т.е. не прерывают их обслуживание/, а внутри кавдого типа обслуживание осуществляется в соответствии с дисциплинок эио. Опознана: через интенсивность поступления требований

I -го типа, а через - их среднюю длину- Пас интере-

сует поведение Бремени ожидания для требований 2-го типа, если А f ^ 11 . Пусть в начальный момент времени есть требования только 2-го типа /это не ограничивает общности/ в количестве У + 1 атук, и одно из них выделено. Обозначим \1/п время ояшшкия впделешш.-. требованием начала об-

V, N

слугивания. Справедливо следующее предельное соотношение, доказанное в Теореме 2.3 главы 4 диссертации:

Р [ а (1+ \0О - а V < у] $ ^

где

РАЕОТЫ ПО TZ,:3 ДМССЕРГАЩй.

1. Гриаечкик С.Л. О регулярности ветвящихся процессов с несколькими типами частад.- Теория Езроятн. и ее примен., 1986, г.21, с.2?о-2о$.

2. Гспиечкпн С.А. Об исследовании систем .'.ассозого обслуживания с дисциплино '. случайного выбора ие-годам1-! ветвящихся процессов.-Лохл. ilH СССР, 1988, т.300, 1Я, с.23-26.

3. Грпаечкин С.А. Одноканальнне системы с круговым доступом или разделением процессора и ветвящиеся процессы.- Уатемат. Заметки, ISoB, т.44, М, с.433-44«.

4. Григаечкин С.А. Ветвящиеся процессы, близкие к нерегулярным, .1 и их применение к очередяк с приоритета1.'!;.- Пробл. устойчивости стохаст. ),':оделе!:, 1969, с.34-42.

5. Грншечкин С.А. Ветвящиеся процессы и системы с повторными вызовами или случайной дисипалино:"'.- Теория вероятн. и ее . примен., 1990, т.35, Л?1, с.Зь-50. *

6. Гришечкин С.А. ЬетЕялиеся процессы Кракпа-аода-Нгерса как метод исследования систем л/0/1 с разделением процессора.- Теория зероятн. и ее примем., 1991, т.36, Н, с.19-35. ?. Гришечкик С.А. Об использовании ве-твядихся процессов для нахотдения стационарных распределении в теории массового обслуживания.- Теория взроятн. к ее г.римен., 1991, т.36, Ш, C.t-iC—■iOo.

8. Grishechkin S.A. On a relationship between processor-sharing queues and Crump-Jode-Jagers branching processes.-Adv. Appl. Probab., 1992, v.24, p.653-698. < -

9. Grishechkin S.A. jiulticlass batch arrival retrial queues analyzed as branching processes with Immigration.- Queueing Systems, 1992, v.11, p.395-418.

10. Grishechkin S.A. On connection between the theory of branching processes and queueing theory.- Proceedings of the 5th Vilnius Conference on probability theory and mathematical statistics, 1989. v.1, p.455-462.