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

РОССИЙСКАЯ АКАДЕМИЯ НАУК Институт проблем управления

им. В.А.Трапезникова ОД

1 Г** , I

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

ТАТАШЕВ Александр Геннадьевич

СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ СО СПЕЦИАЛЬНЫМИ ДИСЦИПЛИНАМИ

Специальность 05.13.01 Управление в технических

системах

АВТОРЕФЕРАТ

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

Москва 2000

Работа выполнена, в Московском государственном автомобильно-дорожном институте (техническом университете)

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

наук, профессор В.В. Калашников

-доктор физико-математических наук, профессор В.А. Каштанов

-доктор физико-математических наук, прфессор В.Г. Ушаков

Ведущая организация: Институт проблем

информатики РАН

Защита, состоится "_" _ 2000 года в_

час. на заседании Диссертационного Совета Д 002.68.03 при Институте проблем управления РАН: 117806, Москва, ул. Профсоюзная, 65.

С диссертацией можно ознакомиться в библиотеке Института проблем управления им. В.А.Трапезникова РАН Автореферат разослан "_" _2000 г.

Ученый секретарь Диссертационного Совета

кандидат технических наук С.А.Власов

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

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

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

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

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

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

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

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

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

Структура диссертации. Диссертация состоит из введения, пяти глав и заключения. Главы делятся на параграфы. Некоторые параграфы разбиты на пункты. Объем диссертации — 220 с.

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

Публикации. Основные результаты диссертации опубликованы в [1-22].

Апробация результатов. Результаты диссертации докладывались на Всесоюзных совещаниях по распределенным системам массового обслуживания в 1990 и 1991 гг., на Всесоюзной научной сессии НТОРЭС им. А.С.Попова в 1988 г., на Белорусских зимних школах-семинарах по теории массового обслуживания в 1986, 1990, 1991 и 1993 гг., на Научно-методических и научно-исследовательских конференциях МАДИ(ТУ) в 1997 и 1999 гг.

Содержание диссертации

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

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

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

В параграфе 1.1 рассматривается одноканальная система массового обслуживания с ожиданием, в которую поступает пуассоновский поток групп требований, имеющий интенсивность А,-, где г — число требований в системе. Вероятность того, что в группе, заставшей в момент своего поступления г требований, содержится к требований, равна Предполагается, что существует число Дг, для которого Шк% = 0 при всех к иг, таких, что

Ы-1

k+i > ./V, и, таким образом, X] = 1. В силу этого усло-

к=1

вия число требований в системе не может превысить N.

N-3

Пусть Г^; = X] и < 0- Длительность обслуживания

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

Доказано следующее утверждение. Стационарные вероятности состояний рассматриваемой системы массовогс

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

N-1

=Ь Р] \jUiN-jj,

3=О

где Р,- — вероятность того, что в системе находится I требований, г = 0,1,."... ТУ.

N

Константа Р0 определяется из условия £ Р, = 1.

г=0

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

1-ЖЛ0 Р' - Аф(\{) (РоЛоП°'+

з=1

В параграфе 1.3 изучается система, отличающаяся от рассматриваемой в параграфе 1.1 тем, что в ней прерванное требование впоследствии обслуживается с прежней длительностью.

Получена следующая формула для вероятностей состояний системы:

Р{ = с1^Х3Р^: г = 1,...,ЛГ,

3=0

\ 6, г" = N.

Данная формула верна при выполнении следующего условия эргодичности: /?(—А,-) < оо при всех г = 1,..., N — 1 и Ь < оо.

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

В параграфе 1.5 рассматривается одноканальная система массового обслуживания с ожиданием, в которую поступает пуассоновский поток групп требований, име-

ющей интенсивность А. С вероятностью шп, поступившая группа состоит из п требований. Пусть к — среднее число

оо

требований в группе: Л = £ ипп. Время обслуживания

п=1

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

Найдены стационарные вероятности состояний рассматриваемой системы массового обслуживания.

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

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

Если распределение длины требования является "молодеющим" (величина В'(х)/(1 — В(х)) убывает по х), то вероятность того, что число требования в системе с дисциплиной ПРП превышает заданную величину, не больше аналогичной вероятности при других дисциплинах, не использующих информацию об остаточных длинах требований. Таким образом, полученная в параграфе 1.5 формула для вероятностей состояний рассматриваемой системы может использоваться для нахождения верхней оценки вероятности превышения заданной величины числом требований, находящихся в системе с дисциплиной ПРП, при неординарном пуассоновском входном потоке и "молодеющем" распределении длины требования.

В соответствии с результатами, полученными в параграфе 1.5, при выполнении условия эргодичности р — АкЬ < 1 производящая функция стационарного распределения числа требований, находящихся в системе

оо

(<?(.г) = Яп2п] Яп — вероятность того, что в системе

П=1

находится п требований), определяется формулой

Ф) - т-^—у-,

1 - ру?(г)

00 I-

где ф) = £ (1{к)гк-к=1

к 7 00

ад = 1ь1 ~ В(х)]к[В(х)ГЫх-,

о п=к

— число сочетаний из тг элементов по к: Сп = п\/[к\(п - к)\].

Для среднего числа Ь требований в рассматриваемой системе массового обслуживания имеем

Л °г 00 "

1 Р I 71=1 к= 1

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

При выполнении условия эргодичности р = АЛЬ < 1 производящая функция стационарного распределения числа требований в системе, рассматриваемой в параграфе 1.6. вычисляется по приведенной выше формуле для системы, рассматриваемой в параграфе 1.5, с той разницей, что значение ¿(к) определяется по формуле

1 °9 оо п

ад = гь/ Х>"£Сп[1- в(х)Пв(х)г< ¿х.

д п—к г=к

Для среднего числа Ь требований в системе, рассматриваемой в параграфе 1.6, получена формула

ЛОО и «

» оо п гг

ь = —- / £ Ц, £ к £ с;[1 - в(хтв(х)ГЧх.

^ Р --1 и—л .-—и

В параграфе 1.7 рассматривается одноканальная система массового обслуживания, в которую поступают пу-ассоновские потоки групп требований, имеющие переменную интенсивность. Группы требований имеют различные типы. Требования также различаются по типам. Тип группы характеризуется числом содержащихся в ней требований каждого типа и порядком обслуживания внутри группы. Группы требований обслуживаются в порядке, обратном их поступлению, с прерыванием. Интенсивность потока групп каждого типа зависит от состояния системы, характеризующегося числами находящихся в системе требований различных типов. Распределение времени обслуживания требования зависит от типа требования. Число требований в системе не может превышать фиксированного значения. Это обеспечивается тем, что в каждом состоянии системы интенсивность потока групп требований, размер которых превышает число мест ожидания, равна нулю.

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

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

ваемого требования.

В параграфе 2.1 рассматривается одноканальная система массового обслуживания, в которую поступает пуас-соновский поток требований с переменной интенсивностью, причем — значение интенсивности потока, когда в системе находится к требований. Длина (время, необходимое для обслуживания) требования имеет распределение В{х) со средним значением Ъ < со. В системе имеется N > 1 мест ожидания. Если требование поступило, когда все места ожидания заняты и в системе менее ТУ + 1 требований, то длина поступившего требования сравнивается с остаточной длиной требования, обслуживаемого на приборе. Если длина поступившего требования меньше остаточной длины обслуживаемого, то поступившее требование занимает прибор, вытесняя обслуживавшееся в очередь на первое место. Если некоторое требование поступило в систему в момент, когда в ней уже находилось к < N + 1 требований, и длина поступившего требования не меньше остаточной длины обслуживаемого требования, то с вероятностью а^ (0 < а* < 1) поступившее требование становится в начало очереди, а требование, находящееся на приборе, продолжает обслуживаться. С дополнительной вероятностью поступившее требование занимает прибор, а обслуживавшееся требование становится на первое место очереди. Требование, обслуживание которого прервано, впоследствии дообслуживается. Пусть Рк — стационарная вероятность того, что в системе находится к требований.

Доказано следующее утверждение. Стационарные вероятности состояний системы ..., Рдг рекуррентно вы-

ражаются через значение Ро по формуле

РоХ0и при ах = О,

при 0 < ах < 1,

Рк-г^Хк^щ-

ВД =

-Хк-^к-х! Рк-1(у)с1у о

при ак = 0, к = 2,..., Ы,

1 (Ь)Лл: —ж _

и

о

при 0 < < 1, А: = 2,..., ЛГ,

и

= ^(Ь)Л^и - Ллгадг J

N+1

Константа Ро определяется из условия £ -Рк = 1-

к=0

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

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

о

В параграфе 2.3 исследуется система массового обслуживания, в которую поступает пуассоновский поток требований с переменной интенсивностью, причем Л^ — значение, принимаемое интенсивностью потока, когда число требований в системе равно к. Длина требования имеет произвольное распределение со средним значением Ь < со. Если в системе находится к < N требований, то каждое из них обслуживается со скоростью 1/к. Если число требований в системе достигло величины N + 1, то требование, имеющее наименьшую остаточную длину, начинает обслуживаться со скоростью 1, а обслуживание остальных требований приостанавливается. При этом поступающие требования теряются. Как только число требований в системе вновь станет меньше Аг + 1, находящиеся в ней требования вновь обслуживаются с одинаковыми скоростями, составляющими в сумме 1. Пусть Рк — стационарная вероятность того, что в системе находится к требований, к = 0,1,..., Лг; рк = Ак-\Ь, к - 1,..., /V; р = рн.

Получены следующие формулы:

к

Рк = Ро П РЬ 1 < к < N - 1,

N-1

Рм+1 =

ЛГ-1

(М — !)!(/? — 1) П Р;

'=0

к=1 ¿=1

N к

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

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

В параграфе 2.5 рассматривается одноканальная система массового обслуживания без мест ожидания, в ко-

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

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

77 = 1-

__ СО со оо ^

ОО Л » г

-[1 + Е / У .. . ¿А(гп_х) У П(1-

П-1 0 0 0 ¿=1

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

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

В параграфе 3.1 исследуется одноканальная система массового обслуживания с одним местом ожидания, в которую поступают N пуассоновских потоков требований различных приоритетов. Интенсивность потока ¡-го приоритета равна Х{, i = 1,..., N. Приоритет тем выше, чем меньше его номер. Длина требования г-го приоритета имеет распределение Д-(ж) с конечным средним Ь,- и пре-

оо

образованием Лапласа-Стилтьеса = / е~5геШ,(г). Есл:

о

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

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

В частном случае, когда и; = и>,- = 0, требования одного приоритета обслуживаются в порядке поступления. Если и,- = ад,- = 1, то'требования одного приоритета обслуживаются в обратном порядке с прерыванием. Если и,- = 1 и го,- = 0, то среди двух требований одного приоритета преимуществом пользуется требование с меньшей остаточной длиной.

Пусть Р(0) — стационарная вероятность того, что в системе нет требований; Р(1,г,г) — стационарная вероятность того, что обслуживается требование j-гo приоритета с остаточной длиной, меньшей х, а место ожидания свободно; Р( 1, г) = Р(1,г,оо); Р(2,^', г,ж) — стационарная вероятность того, что обслуживается требование ,7-го приоритета, длина которого меньше х, а место ожидания занято требованием г-го приоритета; Р(2, г) =

N

— Р(2,г, оо); А,- = ]С : Л, — суммарная интенсивность потоков требований приоритетов не выше г;

х

щ(х) = (Л,- - \{и>{)х + - и,-) J В,-(у) ¿у,

о

¿=1

-(А,(1-г;г-)Д-(х) + Л1+1)Р(1,г).

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

рассматриваемой системы массового обслуживания через значение Р(0) :

' Адг(Р(0) Ь

+ £ 1Р(1,Л)!(1-В„(у))<1у, ¿=1 о

1 ) ^ ? ^ / = если г = Л^, у^ = ги^ = 1,

/9,-(у)ев<(аг)-а,Ч

о

иначе,

Р(2, г, г, ж) =

X

о

+(1 — г>г\В,(у))(Р(1, г) — Р(1, г, у))] о?у,

с

Р(2, ¿г» = XjP(l,i) /(1 - в,ЫИг/+

о

х

о

l<j<i<N, Р{2Л,1,х) = 0, 1 < » < ^ < ЛГ, Р(1,0 =

Ajv(P(0) + V P(l,j))bN, если i = N, i=i

VN = WN = 1,

р(о)+32 p{i,j)

--_ если i _ N

1 — u/дг V '' '

U^V = 1, ^ЛГ ф 1,

t —1 СО

J=1 0 _

jr(Ai(l-vi)B1(j,)+Al4i)e-0i(»)iiy

, иначе.

P(2,»,0 = А,-У- Д(у))Р(1,г\у)+ 0

+(1 - u,-5,-(y))(P(l, 0 - P(l, t, y))] ¿y, г" = 1,..., iV,

oo

P(2,i,0 = AjbjP(l,i) + (P(l,_;) — P(l,j,y))dy,

о

1 <j<i<N. Константа P(0) определяется из условия нормировки

t=l j=1 i=j При Vi — Wi ф 1,

г—1

P( 1,0 =

At(l - Д(А,. - At^))(P(0) + EP(1,J))

i=i

A, (l - г;,) A (A, - А,-и,-) + At-+1 '

В параграфе 3.2 получены формулы для стационарных вероятностег! состояний системы масового обслуживания, отличающейся от рассматриваемой в параграфе 3.1 тем,

о

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

ЧТО — ХЮ{.

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

В параграфе 3.4 рассматривается система массового обслуживания, в которую поступают N пуассоновских потоков требований различных типов. Интенсивность потока требований г-го типа равна А,-, г = 1,..., N. Будем говорить, что приоритет требования г-го типа выше приоритета требования ]-то типа, если г < ]. Время обслуживания требования г-го типа имеет распределение В{(х) с конечным средним 6,- и преобразованием Лапласа-Стилтьеса /Зг(й). В системе имеется М > 1 мест ожидания. Если требование поступило, когда все места ожидания заняты, то это требование теряется. Если в момент поступления треования прибор занят и в системе находится менее М+1 требований, то либо поступившее требование сразу занимает прибор (если его приоритет выше приоритета обслуживаемого требования), вытесняя обслуживавшееся требование на первое место очереди, либо (если приоритет поступившего требования не выше приоритета обслуживаемого) поступившее требование само становится в начало очереди, а требование, находящееся на приборе, продолжает обслуживаться. Остальные требования, находящиеся в очереди, перемещаются на одно место назад. Требование, обслуживание которого прервано, впоследствии

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

Пусть ¿1, ¿2,..., ik, х) — стационарная вероят-

ность того, что в системе массового обслуживания находится к требований, причем обслуживается требование i'i;-ro типа, на первом месте очереди находится требование ¿2-го типа, ... , на (к — 1)-м месте очереди находится

требование г'^-го типа; P(k,i\,. .. ,ik) = Р(к, гi,. .., ik, оо);

N

А,- = J2 Xj : Аг- — суммарная интенсивность потоков типов i=>

3 = i,..., N-

q{k,i,i) =

= А,(1 - ßi(Ai)) £ P(k,j, i, ¿з, • • •, ik)+ j=i

+АiP(k - 1, г, г3,. • • ,ik)~

00

-XiAi J Р(к - 1, i, ..., ik, у)е~А'Чу,

о

г' = l,...,iV, fc = 2,...,M; q(k,i,j) = = Xi{l-ßi(ki))(P{k-\,j,iZl...,ik) +

г—1

+ 3,...,ik)) + r=l ■

+Х3Р(к - l,i,i3,...,ik)-

oo

-XjAi J P(k - l,i,i3,...,ik,y)e-Aiydy, о

1 < i < j < N, к = 2,...,N-, q(k,i,j) =

>■=1

1 <j<i<N, k = 2,...tM.

Получены следующие формулы, позволяющие последовательно выразить стационарные вероятности состояний рассматриваемой системы массового обслуживания через значение Р(0) :

p(i, ¿, х) = J [а4(1 - адхр(о) + £ p(i,i))-

о J=1

-(А iBi{y) + Л,+1)Р(1, г = 1,..., JV,

Р(/г,г,г,г3,... =

х t'-i = J[А{(1 - Д (у)) £ i, i, г'з,..., 0 i=1

-(А,-Д (у) + A,-+x)jP(ä, г, г, г3,..., +

+А,-(Р(А; - 1, г, ¿з,.. .,ik)~ — Р(к — 1, г, г'з,..., ik, у))]ел'(х_у^у, . г = = 2,...,М,

P(k,i,j,iz,...,ik,x) =

= J[A,(l - Вг(у))(Р(к - 1, j,t3l -. .,¿fc)+ о

í-1 r=1

-(А,Д(г/) + Aj+i)P(k, i,j, ¿3,.. •, »*)+ +Aj(P(¿ - 1, i, ¿3,. ..,ik)-

1 < г < j < N, к = 2,..., M, P(k,i,j,i3, ...,ik,x) = i-1

- Д-М) S r>-?> • • •, »*)"

r=l

-(Л,- Д(у) + Лf+1)P(fc, i, j, ¿3, • -., ú)]^'0^ dy, 1 < i < » < ЛГ, к = 2,..., M,

P(M + 1,г,г,г'з, ...,¿Aí+1,x) =

г

= А,- J(Р(М, г, г'з,..., г'м+х)-о

-Р(М, г, г'з,..., г'л/+1, у)) ¿у, г = 1,..., ÍV, Р(М + 1,г, j, г'з,. ..,¿M+i,x) =

X

= f [А,(1 - Д(у))Р(М, j, ¿3, ■ • •, ¿M+i)+ о

+Аj(P(M, г, г3,..., г'м+i) — -Р(М,г, г3,..., í'jif+i,!/))] ¿y,

= /wi

1 <i<j<N\ At(l-A(A,))(P(0)+EP(l,j))

P(1'° = AtA(A¿) + A.-+1 '

г = 1,... , Лг,)

A¿A(A¿) + Л.-+1' ¿ = 1,...,АГ, j = l,...,N, k = 2

P(M + l,i,i,i3,...,tAf+i) =

oo

= A¿ J{P(M,i

,i3,...,iM+i) - P(M,i,i3,. . . , ÍAf+1, y)) cít/,

o

■ i = 1,..., JV,

P(Af + l,í,j,¿3,...,tM+i) = = Afb¿P(M, j,i3,...,tAf+i)+

oo

+Aj J(P(M, i

-P(M, i, ¿3,..., г'м+ь y)) ¿y, 1 < i < j < N. Константа P(0) определяется из условия нормировки

Af+l JV JV

£ ib.=

k~0 ¿i=l Ifc = l

o

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

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

Получены формулы для стационарных вероятностей состояний системы.

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

В параграфе 3.8 получены формулы для стационарных вероятностей состояний системы массового обслуживания, отличающейся от системы, исследуемой в параграфе 3.6, тем, что в ней обслуживаемое требование

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

В главе 4 рассматриваются некоторые системы массового обслуживания с переменным входным потоком.

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

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

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

В главе 5 предполагается, что в одноканальную си-

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

Для рассматриваемой системы массового обслуживания найдено преобразование Лапласа-Стилтьеса стационарного распределения времени пребывания в системе требования заданного типа (параграф 5.1) и производящие функции нестационарного и стационарного распределений чисел требований различных типов, находящихся в системе (параграф 5.2).

Основные результаты работы

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

2. Найдено стационарное распределение числа тре-

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

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

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

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

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

1. Таташев А.Г. Многоканальная система массового обслуживания с потерей кратчайших требований// Автомат. и телемех. - 1991. - N 7. - С. 187 -189.

2. Таташев А.Г. Одна система массового обслуживания с инвариантной дисциплиной// Автомат, и телемех. -1992. - N 7. - С. 92 - 96.

3. Таташев А.Г. Система массового обслуживания с переменной интенсивностью входного потока// Автомат, и телемех. - 1995. - N 12 - С. 78 - 84.

4. Таташев А.Г. Одна инверсионная дисциплина обслуживания в одноканальной системе с разнотипными заявками/ / Автомат, и телемех. - 1999. - N 7. -С. 177 - 181.

5. Таташев А.Г. Одна система массового обслуживания с инвариантными вероятностями состояний// Кибер-нет. и системн. анализ. - 1993. - N 5. - С. 183 - 186.

6. Таташев А.Г. Система массового обслуживания GI\Hji\1\0 с потерей заявки максимальной длины// Ки-бернет. и системн. анализ. - 1994. - N 2. - С. 180 - 182.

7. Таташев А.Г. Система массового обслуживания с групповым поступлением и инверсионной дисциплиной// Кибернет. и системн. анализ. - 1995. - N 6. - С. 163 - 165.

8. Таташев А.Г. Одноканальная система массового обслуживания с потерей заявки наибольшей длины// Кибернет. и системн. анализ. - 1997. - N 3. - С. 187 - 188.

9. Таташев А.Г. Приоритетная дисциплина обслуживания в системе М]у|£?лг|1|1// Кибернет. и системн. анализ. - 1999. - N 5. - С. 181 - 184.

10. Печинкин A.B., Таташев А.Г. Обобщение дисциплины преимущественного разделения процессора// Изв.

АН ССР. Техн. кибернет. - 1981. - N 4. - С. 120 - 125.

11. Таташев А.Г. Одна дисциплина обслуживания с разделением процессора// Автомат, и вычисл. техн. -1993. - N 6. - С. 27 - 32.

12. Таташев А.Г. Одна инверсионная дисциплина обслуживания в системе с групповым поступлением// Автомат. и вычисл. техн. - 1995. - N 1 - С. 53 - 59.

13. Таташев А.Г. Система инверсионного обслуживания с прерыванием группового поступления заявок// Автомат. и вычисл. техн. - 1996. - N 5. - С. 57 - 65.

14. Таташев А.Г. Одноканальная система с инвариантной дисциплиной обслуживания// Техника средств связи. -Сер. СС. - 1986. - Вып.2. - С. 11 - 15.

15. Таташев А.Г. СМО с инвариантной дисциплиной// Техника средств связи. - 1990. - Сер.СС. - Вып.4. - 1991. - С. 58 - 61.

16. Таташев А.Г. Одна инвариантная система мас-совго обслуживания// В кн.: III Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания (4-7 декабря 1990 г.). Тезисы докладов. - М., 1990. - С. 185 - 187.

17. Таташев А.Г. Одна система массового обслуживания с инвариантной дисциплиной// В кн.: IV Всесоюзное совещение по распределенным системам массового обслуживания (22-27 апреля 1991 г. Душанбе). Тезисы докладов. - М., 1991. - С. 225 - 227.

18. Таташев А.Г. Инверсионная дисциплина обслуживания в одноканальной системе с вероятностными приоритетами/^ кн.: XLIII Всесоюзная сессия, посвященная Дню радио (НТОРЭС им. A.C. Попова). Тезисы докладов. -4.1. -М., 1988. - С. 55.

19. Таташев А.Г. Одноканальная система массового обслуживания с инвариантной дисциплиной// В кн.: Применение математических методов и вычислительной техники при решении народнохозяйственных задач. Тезисы доклалов. - Гомель, 1986. - С. 67 - 68.

20. Таташев А.Г. Многоканальная система массового обслуживания с потерями кратчайших заявок// В кн.: Математические методы исследования сетей связи и сетей ЭВМ// Тезисы докладов. Витебск, январь-февраль 1990. -Минск, 1990. - С. 133 - 134.

21. Таташев А.Г. Система обслуживания (?|М|1|0 с потерей заявки максимальной длины// В кн.: Белорусское научно-техническое совещание "Сети связи и сети ЭВМ как модели массового обслуживания" (Гродно, январь-февраль 1991). Тезисы докладов. - Минск. - 1991. - С. 120.

22. Таташев А.Г. Система массового обслуживания С?/|#я|1|0 с потерей заявки максимальной длины// В кн.: Математические методы исследования систем и сетей массового обслуживания. Тезисы'докладов 9-й Белорусской зимней школы-семинара по теории массового обслуживания/ Минск, февраль, 1993. - Минск, 1993. - С. 95.

Тир. 100. Зак.51. ИПУ.

1. Введение.

Глава 1. Системы с групповым поступлением требований и инверсионным обслуживанием с прерыванием.

1.1. Система с обслуживанием прерванного требования заново с новой длительностью.

1.2. Система с потерей прерванного требования.

1.3. Система с обслуживанием прерванного требования заново с прежней длительностью.

1.4. Система с возможным прерыванием требования.

1.5. Система с разделением процессора требованиями одной группы.

1.6. Система с обслуживанием первым кратчайшего требования внутри группы.

1.7. Система с разнотипными требованиями.

Глава 2. Системы с дисциплинами, учитывающими остаточные времена обслуживания требований.

2.1. Инвариантная инверсионная дисциплина обслуживания с вероятностным приоритетом и конечным числом мест ожидания.

2.2. Инвариантная инверсионная дисциплина с вероятностным приоритетом и бесконечным числом мест ожидания.

2.3. Одна инвариантная дисциплина обслуживания.

2.4. Многоканальная система с потерей требования наименьшей длины.

2.5. Система с потерей требования максимальной длины.

Глава 3. Некоторые системы массового обслуживания с разнотипными требованиями.

3.1. Система с одним местом ожидания и приоритетной дисциплиной с дообслуживанием прерванного требования.

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

3.3. Система с одним местом ожидания и приоритетной дисциплиной с потерей прерваннного требования.

3.4. Система с одной инверсионной дисциплиной и дообслуживанием прерванного требования.

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

3.6. Система с требованиями двух типов и одной инверсионной дисциплиной с дообслуживанием прерванного требования.

3.7. Система с требованиями двух типов и одной инверсионной дисциплиной с обслуживанием прерванного требования заново.

3.8. Система с одной инверсионной дисциплиной обслуживания с прерыванием требований двух типов.

Глава 4. Некоторые системы массового обслуживания с переменным входным потоком.

4.1. Система с инверсионной дисциплиной.

4.2. Система с обслуживаниям требований в порядке поступления.

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

5.1. Вычисление стационарного распределения времени пребывания требования в системе.

5.2. Вычисление нестационарных и стационарных вероятностей состояний системы.

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

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

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

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

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

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

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

Другой работой, посвященной оптимизационным вопросам теории массового обслуживания, является обзор [32].

Возможные применения результатов теории массового обслуживания при разработке и анализе вычислительных систем коллективного пользования, систем и сетей связи описываются в монографиях [7,11,12,15,58].

Как отмечается в [5], как информационно-вычислительные системы, так и автоматические системы управления, состоят из множества связанных между собой пунктов, оснащенных вычислительными машинами, где информация собирается, обрабатывается и передается далее. В таких сетевых структурах можно выделить по функциональному признаку последовательные уровни иерархии: от низшего уровня, на котором вычислительные машины непосредственно связаны с первичными источниками информации и объектами управления, до высшего, где на основе сводной информации вырабатываются наиболее общие решения. Но если даже рассмотреть отдельный пункт (узел) в такой сетевой структуре, то окажется, что на вычислительную машину в ней поступают разнородные потоки заявок на решение задач разной важности (срочности) и длительности (объема). Чтобы упорядочить работу вычислительной машины в такой ситуации, вводят систему приоритетов (динамическую или статическую) в обслуживании различных задач. Современные вычислительные средства в зависимости от характера поставленных задач могут решать их в различных режимах: запрос-ответ, пакетной обработки, разделения времени при коллективном пользовании, мультипрограммном. Этим режимам в той или иной степени соответствуют различные модели систем массового обслуживания, позволяющие рассчитывать такие показатели работы вычислительной машины, как загрузка памяти и процессора, задержки и потери информации, и оценивать эффективность и надежность принятых решений. В [5] при обосновании использования систем массового обслуживания с соответствующими дисциплинами в качестве моделей функционирования узла сети связи с коммутацией сообщений отмечается, в частности, следующее. Такая сеть представляет собой совокупность узлов коммутаций сообщений, некоторые из которых непосредственно соединены между собой ориентированными каналами связи. Узел сети вместе с набором сообщений, ожидающих в этом узле и претендующих на передачу по одному и тому же исходящему из узла каналу, может рассматриваться как одноканальная система массового обслуживания, а время, затрачиваемое сетью на перемещение от узла-источника в узел-адресат, называемое временем доставки сообщения, складывается из отрезков времени пребывания данного сообщения в системах массового обслуживания всех узлов, посещаемых им при перемещении по сети. Обеспечение требуемой гарантии доставки сообщений адресатам в заданные сроки зачастую зависит от дисциплины обслуживания, принятой в системах массового обслуживания на узлах. Необходимость в использовании приоритетных или других специальных дисциплин обслуживания сообщений на узлах сети возникает тогда, когда соотношение между пропускной способностью сети и интенсивностью потока движущейся по ней информации неблагоприятно в такой степени, что обслуживание в порядке поступления не может обеспечить для всех категорий срочности требуемую гарантию своевременной доставки.

В [15, 58] рассматриваются проблемы эффективного использования вычислтельных ресурсов в реальном масштабе времени. Приводятся основные характеристики различных методов организации вычислительного процесса. Даются рекомендации по применению различных методов и дисциплин организации вычислительного процесса и принципы оценки их эффективности.

В [58] отмечается, что в последнее время получило интенсивное развитие новое направление теории массового обслуживания, связанное с исследованием систем с дисциплинами обслуживания, отображающими существенные особенности алгоритмов диспетчеризации современных ЭВМ с разделением времени в узлах сетей передачи данных и вычислительных сетей. Важную роль среди таких систем обслуживания играют так называемые системы с разделением процессора, которым посвящен обзор [60]. Как отмечено в [15], практическое значение математической реализации, используемой в моделях разделения процессора, состоит в том, что она отражает существенную особенность вычислительной системы с разделением времени (если под требованием понимать отдельные задания пользователя) или мультиплексных узлов коммутации пакетов (если требованием является сообщение или сегмент) — замедление обслуживания каждого требования, пропорциональное их общему числу в текущий момент.

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

В [58] исследуются математические модели вычислительных систем с разделением времени, анализируемые в терминах теории массового обслуживания. Эти модели описывают функционирование алгоритмов диспетчеризации в современных ЭВМ, узлах сетей связи с пакетной коммутацией и других технических систем, оперативно разделяющих ресурсы процессора между заданиями многих пользователей. Как отмечается в [58], под режимом разделения времени понимается такая форма организации функционирования ЭВМ, при которой осуществляется оперативное предоставление ресурсов ЭВМ (времени процессора, памяти, каналов связи и др.) большому количеству одновременно работающих за терминалами пользователей, соединенных с системой каналами связи. К основным достоинствам системы с разделением времени можно отнести возможность коллективного пользования одной ЭВМ несколькими пользователями, быстрое получение ответа на короткие задания и значительное повышение эффективности взаимодействия с ЭВМ. Выполнение функций планирования порядка, в котором выполняются задания пользователей, возлагаются на составную часть операционной системы-алгоритм планирования (называемый также планировщиком или алгоритмом диспетчеризации), который устанавливает динамически изменяющуюся очередность заданий. Алгоритм планирования формирует очереди работ к процессору, выбирает задание для исполнения и согласно определенным правилам вычисляет для него квант времени процессора. При этом анализируются такие данные, как ранее использованное заданием время процессора, занимаемый им объем памяти, число активных заданий, приоритет, и т.д. В [58] анализируются методы организации вычислительного процесса в сетях ЭВМ, использующие следующие дисциплины обслуживания: инверсионные дисциплины; дисциплины равномерного и преимущественного разделения процессора; дисциплина обслуживания первым требования с наименьшей остаточной длиной и др.

Методам построения моделей массового обслуживания посвящена монография [9].

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

Системы массового обслуживания с инверсионными дисциплинами с прерыванием изучались, например, в [2,3,19,23,25,29,67]. При этом в [2,3,23,25] рассматривались системы с ординарным входящим потоком, а в [19,29,67] предполагалось, что обслуживание возобновляется с того места, где оно было прервано. В [29,67] считалось, что прерывание требования, находящегося на приборе, происходит при каждом поступлении новой группы требований, а в [19], что такое прерывание происходит с некоторой вероятностью, зависящей от числа требований в поступившей группе, остаточного времени находящегося на приборе требования и времени, необходимого для обслуживания каждого из поступивших требований.

Для повышения эффективности обслуживания в информационно-вычислительных системах могут использоваться дисциплины, которые уменьшают средние задержки путем предоставления приоритета "коротким" заданиям перед "длинными". При одной из таких дисциплин в текущий момент времени обслуживается требование с наименьшей остаточной длиной [65]. Другая дисциплина, предоставляющая преимущество требованиям с меньшими остаточными длинами, рассмотрена в работе [21]. Эта дисциплина является в определенном смысле промежуточной между инверсионной дисциплиной с прерыванием и инверсионной дисциплиной без прерывания. При дисциплине, рассмотренной в [21], вытеснение обслуживаемого требования вновь поступившим происходит лишь в случае, если длина поступившего требования меньше остаточной длины обслуживаемого. Изучение системы обслуживания с такой дисциплиной позволило получить оценку характеристик системы, в которой принята дисциплина обслуживания требования с наименьшей остаточной длиной. При дисциплине, рассматривавшейся в [21], в случае, если поступило требование, длина которого меньше остаточной длины требования, находящегося на обслуживании, поступившее требование занимает прибор, а обслуживаемое требование перемещается на первое место очереди. Если длина поступившего требования больше остаточной длины обслуживаемого, то, наоборот, поступившее требование становится первым в очередь, а требование, находящееся на приборе, продолжает обслуживаться. Доказано, что стационарное распределение числа требований в данной системе не зависит от распределения длины требования, если не изменяется среднее значение этого распределения.

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

Отметим, что результат, найденный в [21], является обобщением одного из результатов [26]. В [26] при рассмотрении системы массового обслуживания М\С\1\к с обслуживанием требования с наименьшей остаточной длиной было обнаружено, что в случае, когда место ожидания единственно, стационарные вероятности сотояний системы не зависят от распределения длины требования при фиксированном среднем (для системы М|(7|1|1 дисциплина обслуживания требования с наименьшей остаточной длиной и дисциплина, рассматривавшаяся в [21], как легко видеть, тождественны).

Система обслуживания, инвариантность которой установлена в [21], не принадлежит к описанному в [58] классу систем с инвариантными вероятностями состоянии относительно распределения длины требования при фиксированном среднем, сохраняющих на выходе пуассоновский поток. К этому классу, в частности, относятся следующие дисциплины: дисциплина "равномерного разделения процессора", т.е. дисциплина, при которой все находящиеся в системе требования обслуживаются одновременно с одинаковыми скоростями, составляющими в сумме 1; дисциплина обслуживания требований в обратном порядке с прерыванием и дообслуживанием. Инвариатными в смысле независимости распределения числа требований в системе относительно распределения длины требования при фиксированном среднем являются также системы массового обслуживания М|С7|оо и М\С\п\1. Некотрые другие системы массового обслуживания, инвариантные в рассматриваемом смысле, описаны в [6,10], где перечислен также ряд других работ, касающихся данного вопроса. Отметим, что до того, как в [21] был установлен факт инвариантности рассмотренной в этой работе системы, не были известны инвариантные системы массового обслуживания, не сохраняющие на выходе пуассоновский поток (для системы М|(7|п|0 пуассоновским является поток покидающих систему требований, образуемый обслуженными и потерянными требованиями). Кроме того, число требований в системе, рассматривавшейся в [21], распределено так, как для соответствующей системы М|1}|1 с обслуживанием в порядке поступления. В отличие от этого, для каждой из инвариантных систем, известных прежде, распределение числа требований совпадает с распределением числа требований в соответствующей системе с обслуживанием в порядке поступления и экспоненциальным распределением длины требования.

В упоминавшейся выше работе [67] рассматривалась система с неординарным пуассоновским потоком и инверсионной дисциплиной обслуживания, при которой требования одной группы обслуживаются в случайном порядке. Показано, что в этой системе распределение числа требований также не зависит от распределения времени обслуживания при фиксированном среднем. Инвариантность системы, рассмотренной в [67], следует также из результатов работы [19], где, в соответствии со сказанным выше, исследовалась система несколько более общего вида. Система обслуживания, рассматривавшаяся в [67], представляет собой обобщение инвариантной системы М\0\1 с инверсионной дисциплиной с прерыванием. Другие упомянутые выше инвариантные системы (в частности, системы М\С|оо и М|(7|п|0, система М|С|1 с системой разделения процессора) перестают быть инвариантными, если пуассоновский входящий поток заменить на неординарный пуассоновский.

Системы массового обслуживания с прямым или инверсионным порядком обслуживания, в которых интенсивность входящего потока зависит от суммарного объема требований, рассматривались, например, в [6,23-25,55-57,68].

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

Если величина кванта пренебрежимо мала, то можно считать, что задания обслуживаются процессором одновременно, но с уменьшенными скоростями. Дисциплина, при которой требования обслуживаются одновременно, но с уменьшенными скоростями, составляющими в сумме 1, называемая дисциплиной равномерного (справедливого) разделения процессора, была введена в рассмотрение в [62].

Если распределение длины требования является "молодеющим", т.е. требованию предстоит обслуживаться в вероятностном смысле тем дольше, чем больше времени оно уже обслуживалось, то целесообразно использовать введенную в рассмотрение в [66] дисциплину многоуровневого понижения приоритета. При этой дисциплине требованию предоставляется тем более высокий приоритет, тем меньше квантов обслуживания это требование уже получило. Предельным случаем такой дисциплины при бесконечно малой величине кванта времени является дисциплина "преимущественного (приоритетного) разделения процессора" требованиями с наименьшей обслуженной длиной. При этой дисциплине приоритет требования тем выше, чем меньше его обслуженная длина. Если в некоторый момент времени имеется сразу несколько требований, характеризующихся наименьшей обслуженной длиной, то никакое из этих требований не может использовать всю производительность системы, так как через сколь угодно малый промежуток времени значение обслуженной длины этого требования перестало бы быть минимальным. В связи с этим данная дисциплина обслуживания предусматривает одновременное обслуживание требований с наименьшей обслуженной длиной с одинаковыми скоростями, составляющими в сумме 1. В [61] получено выражение для преобразования Лапласа-Стилтьеса стационарного распределения времени пребывания требования в системе массового обслуживания М|(7|1 с дисциплиной преимущественного разделения процессора требованиями с наименьшей обслуженной длиной. В [22] найдено выражение для производящей функции числа требований в этой системе. В [59] получено аналогичное выражение для соответствующей системы с групповым поступлением. В [20,58] исследовалось нестационарное распределение числа требований в системе М|С|1 с дисциплиной преимущественного разделения процессора. Обзор литературы по системам массового обслуживания с "разделением процессора" содержится в [60].

В работе [21] введен метод, в соответствии с которым в множестве состояний процессора, описывающего функционирование системы обслуживания, выделяется некоторое подмножество и процесс рассматривается только на тех интервалах времени, когда он принимает значения из этого подмножества. При этом условное стационарное распределение исходного процесса при условии попадания его в выделенное подмножество состояний совпадает со стационарным распределением процесса, рассматриваемого на выделенных интервалах времени. Более подробно этот метод описан в [4]. Данный метод использовался в ряде других работ (в частности, в [17-19, 23-25, 28-31]). В соответствии с одной из модификаций этого метода рассматривается совокупность вспомогательных систем массового обслуживания, каждая из которых отличается от предыдущей тем, что допустимое число находящихся в системе требований увеличивается на единицу. Случайный процесс, описывающий функционирование рассматриваемой системы массового обслуживания, рассматривается лишь на тех интервалах времени, на которых число требований не превышает заданное значение.

Существует ряд естественно возникающих вопросов, которые в литературе по системам обслуживания со специальными дисциплинами не рассматривались или не были окончательно решены. Для одних типов систем не известны методы, которые позволяли бы получить более или менее пригодные для практических расчетов формулы. Для других классов систем со специальными дисциплинами методы исследования, учитывающие специфику этих систем, разработаны относительно недавно и остается не завершенной работа по совершенствованию этих методов и расширению области их применения (в частности, для исследования систем, представляющих прикладной интерес). Классом систем, для которых была разработана специальная методика, является класс систем массового обслуживания "типа" инверсионного. Для этого класса в [21] был предложен упоминавшийся выше специальный метод исследования, основанный на выделении интервалов времени, на которых рассматривается процесс, и "выкидывании" интервалов времени, которые на данном шаге исключаются из рассмотрения. С помощью этого метода (будем называть его методом Печинкина) первоначально были рассмотрены некоторые системы обслуживания, в каждой из которых поступившее требование в зависимости от его длины и остаточной длины обслуживаемого требования либо сразу занимает прибор, вытесняя обслуживаемое требование на первое место очереди, либо само становится в начало очереди. Данный метод применим к широкому классу систем обслуживания. Результаты диссертации позволили сделать класс систем, к которым применим этот метод, существенно более разнообразным и включить в этот класс ряд важных в прикладном отношении типов систем обслуживания.

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

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

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

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

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

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

В параграфах 1.1-1.3 исследуются системы с групповым поступлением, в которых прерванные требования либо впоследствии обслуживаются заново с новой длительностью (параграф 1.1), либо теряются (параграф 1.2), либо обслуживаются заново с прежней длительностью (параграф 1.3). Ранее из инверсионных систем обслуживания с групповым поступлением изучалась система с дообслуживанием прерванного требования с того места, где произошло прерывание. В параграфе 1.4 рассматривается система обслуживания, отличающаяся от исследуемой в параграфе 1.1 тем, что прерывание обслуживаемого требования поступившим происходит лишь с определенной вероятностью. В параграфах 1.1, 1.2 и 1.4 используется первоначальная модификация метода Печинкина, предусматривающая составление и решение уравнений равновесия. Для вычисления стационарных вероятностей состояний системы, рассматриваемой в параграфе 1.3, возникает необходимость использования другого подхода. Данная задача решена с помощью непосредственного вычисления среднего суммарного времени пребывания системы в каждом состоянии за период занятости.

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

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

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

Для систем массового обслуживания, рассматриваемых в параграфах 2.1-2.4 установлен факт инвариантности состояний при фиксированном среднем времени обслуживания. Ранее известные системы обслуживания, инвариантные в данном смысле, обладали следующими свойствами. При пуассо-новском входящем потоке требований поток требований, покидающих систему, также является пуассоновским. Стационарное распределение числа требований в системе является таким же, как в соответствующей системе с обслуживанием в порядке поступления и экспоненциальном распределении времени обслуживания. Инвариантностью другого типа обладает система, исследованная в [21], с дисциплиной обслуживания, при которой поступившее требование либо сразу занимает прибор, вытесняя обслуживавшееся на первое место (если его длина меньше остаточной длины обслуживаемого требования), либо само становится в начало очереди (если длина поступившего требования превышает остаточную длину обслуживаемого). Эта система не сохраняет на выходе пуассо-новский поток, а распределение находящихся в ней требований совпадает с распределением числа требований в соответствующей системе М|£)|1 с обслуживанием в порядке поступления. Как следует из результатов главы 2 диссертации, существует целый класс систем обслуживания с новым типом инвариантности. Принадлежащие к этому классу системы обслуживания, исследованные в параграфах 2.1-2.4, не сохраняют на выходе пуассоновский поток, а стационарное распределение числа требований в этих системах не совпадает со стационарным распределением числа требований в соответствующих системах в порядке поступления, вообще говоря, ни при экспоненциальном, ни при постоянном времени обслуживания. Установленный факт инвариантности вероятностей состояний соответствующих систем обслуживания можно использовать для получения удобных формул, полезных, в частности, для оценок характеристик неинвариантных систем обслуживания, которые могут рассматриваться как модели функционирования реальных систем. В частности, полученные в параграфе 2.3 формулы дают удобные оценки для стационарных вероятностей состояний системы с дисциплиной обслуживания требо-ваеия с наименьшей остаточной длиной и соответствующем числом мест ожидания, а формула для вероятности потери требования в системе, рассматриваемой в параграфе 2.4, дает верхнюю оценку для вероятности потери требования в многоканальной системе без мест ожидания с произвольным правилом выбора требования, подлежащего потере.

Метод Печинкина используется в параграфах 2.1-2.3. При этом новой является модификация этого метода, примененная к системе обслуживания, которая рассматривается в параграфе 2.3. В данной систем одновременно могут обслуживаться несколько требований, причем, в отличие, например, от системы, рассматриваемой в параграфе 1.5, моменты поступления одновременно обслуживаемых требований различны. В рассматриваемой в параграфе 2.3 системе одновременно обслуживаются с постоянной суммарной скоростью все находящиеся в системе требования за исключением ситуации, когда число требований в системе достигает максимального допустимого значения. В последнем случае обслуживается требование с наименьшей остаточной длиной. При используемом в параграфе 2.3 подходе функционирование рассматриваемой системы на определенных интервалах времени сравнивается с функционированием двух специально подобранных систем. В одной из этих систем при достижении числом требований заданного значения новые поступающие требования теряются, а во второй одновременно может обслуживаться неограниченное число требований, причем суммарная скорость обслуживания требований зависит от числа обслуживаемых требований. Аналогичным образом, метод, в соответствии с которым рассматриваемая система обслуживания сравнивается с соответствующей бесконечноканальной системой, использован при исследовании многоканальной системы с ожиданием, в которой теряются требования с наименьшими остаточными длинами. Идеи параграфов 2.3 и 2.4 могут использоваться и для вычисления характеристик других систем обслуживания. Например, можно исследовать систему, отличающуюся от рассматриваемой в параграфе 2.3 тем, что ее производительность зависит от числа находящихся в системе требований, или рассмотреть систему с дисциплиной равномерного разделения процессора с ограничением на число одновременно обслуживаемых требований, в которой при достижении числом требований максимального допустимого числа теряются требования с наименьшей остаточной длиной.

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

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

Как и для большинства других систем обслуживания, исследуемых в диссертации, для систем, изучаемых в главе 3, используется метод Печинкина. Системы, рассматриваемые в главе 3, обладают той отличительной особенностью, что в каждой из этих систем имеются требования нескольких типов и в связи с этим дискретная компонента соответствующего случайного процесса оказывается многомерной. Для систем обслуживания такого вида рассматриваемая методика ранее не применялась. Не для всякой системы обслуживания данного вида удается найти процедуру, позволяющую рекуррентно выражать в явном виде значения вероятностей состояний системы через значения вероятностей, вычисленных на предыдущих шагах. В главе 3 выявлен класс систем обслуживания, для которых удается упорядочить множество состояний системы так, что получение такой процедуры оказывается возможным. Этот класс включает в себя ряд систем, представляющих прикладнои интерес.

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

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

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

В параграфах 3.1-3.3 рассматриваются системы Мдг|(7лг|1|1 с приоритетными дисциплинами обслуживания с дообслужи-ванием (параграф 3.1), с обслуживанием заново (параграф 3.2) и с потерей (параграф 3.3) прерванного требования. В параграфе 3.4 исследуется инверсионная система обслуживания с прерыванием более приоритетного требования менее приоритетным и дообслуживанием прерванного требования. В параграфе 3.5 рассматривается аналогичная система с обслуживанием прерванного требования заново. В параграфах 3.6-3.8 изучаются инверсионные системы обслуживания с двумя типами требований. В системе, рассматриваемой в параграфе 3.6 прерывание требований одного типа не разрешено, прерванные требования другого типа впоследствии дообслужива-ются. В параграфе 3.7 расматривается аналогичная система, но предполагается, что прерванные требования обслуживаются заново. В параграфе 3.8 предполагается, что прерванные требования первого типа дообслуживаются, а прерванные требования второго типа обслуживаются заново.

В главе 4 исследуются системы массового обслуживания с входящим потоком, зависящим от состояния системы. Как и при исследовании систем, рассмотренных в главах 1 и 3, и большинства систем, рассмотренных в главе 2, используется метод, в соответствии с которым случайный процесс, описывающий функционирование системы рассматривается на интервалах времени, на которых данный процесс находится в выделенном множестве состояний. При этом показано, что для исследуемых в главе 4 этот метод удобно сочетать с методом, в соответствии с которым вычисляется суммарное время пребывания системы обслуживания в фиксированном множестве состояний за период занятости. Такой подход сходен с используемым в параграфах 1.3, 1.5-1.7, но структура случайного процесса, описывающего функционирование системы, усложняется за счет необходимости учитывать остаточные длины всех находящихся в системе требований.

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

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

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

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

Для рассматриваемой системы массового обслуживания найдено преобразование Лапласа-Стилтьеса стационарного распределения времени пребывания в системе требования заданного типа (параграф 5.1) и производящие функции нестационарного и стационарного распределений чисел требований различных типов, находящихся в системе (параграф 5.2).

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

Основное содержание диссертационной работы изложено в

27, 33-54]. количество печатных работ, содержащих результаты диссертационной работы - 23. Результаты диссертации докладывались на Всесоюзных совещаниях по распределенным системам массового обслуживания в 1990 и 1991 гг., на Всесоюзной научной сессии НТОРЭС им. А.С.Попова в 1988 г., на Белорусских зимних школах семинарах по теории массового обслуживания в 1986, 1990, 1991 и 1993 гг., на научно-методических и научно-исследовательских конференциях МАДИ (ТУ) в 1997 и 1999 гг.

Заключение

1. Разработаны модификации метода исследования систем обслуживания, предложенного A.B. Печинкиным. Благодаря этим модификациям класс систем обслуживания, к которым применим данный метод, значительно расширен. С помощью этого метода стало возможным исследовать новые типы систем обслуживания со специальными дисциплинами, важные с теоретическом и прикладном отношении.

2. Для ряда систем массового обслуживания установлен факт инвариантности стационарных вероятностей состояний системы в смысле независимости этих вероятностей от распределения времени обслуживания при фиксированном среднем. Эти системы обслуживания составляют новый класс инвариантных систем.

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

- системы с неординарным пуассоновским потоком и различными инверсионными дисциплинами;

- системы с дисциплинами, учитывающими длину поступившего и остаточную длину обслуживаемого требования;

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

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

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

1. Башарин Г.П., Бочаров П.П. Анализ очередей в вычислительных сетях. Теория и методы расчета. М.: Наука, 1987. -335 с.

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

3. Бочаров П.П., Павлова О.И., Печинкин A.B. Стационарные характеристики конечной очереди при инверсионном обслуживании/ / Вестник Российского университета дружбы народов. Сер. Прикл. мат. и информатика. - 1994. - N 1 - С. 62 -82.

4. Бочаров П.П., Печинкин A.B. Теория массового обслуживания// Изд-во РУДН, 1995. 528 с.

5. Бронштейн О.И., Духовный И.М. Модели приоритетного обслуживания в информационно-вычислительных системах// М.: Наука, 1976. 220 с.

6. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1987, - 336 с.

7. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988. - 192 с.

8. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания. М.: Высшая школа, 1982. - 256 с.

9. Калашников В.В., Рачев С.Т. Математические методы построения моделей обслуживания. М.: Высшая школа, 1988. -312 с.

10. Кениг Д., Штойян Д., Методы теории массового обслуживания. М.: Наука, 1987. - 128 с.

11. Клейнрок JI. Вычислительные системы с очередями. М.: Мир, 1979. 600 с.

12. Клейнрок JI. Коммуникационные сети. М.: Наука, 1970. 200 с.

13. Клейнрок JI. Теория массового обслуживания. М.: Машиностроение, 1979. - 432 с.

14. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. Наука, 1975. - 360 с.

15. Липаев В.В., Яшков С.Ф. Эффективность методов организации вычислительного процесса в АСУ. М.: Статистика, 1975. - 255 с.

16. Матвеев В.Ф., Ушаков В.Г. Системы массового обслуживания. М.: Изд-во МГУ, 1984. - 240 с.

17. Нагоненко В.А. О характеристиках одной нестандартной системы массового обслуживания I// Изв. АН СССР. Техническая кибернетика. 1981. - N 1. - С. 187 - 195.

18. Нагоненко В.А. О характеристиках одной нестандартной системы массового обслуживания II// Изв. АН СССР. Техническая кибернетика. 1981. - N3.-C. 91-99.

19. Печинкин А.В. Инверсионный порядок обслуживания с вероятностным приоритетом в системе обслуживания с неординарным потоком// Математ. исследования. Сер. Вероятность и приложения (1989). - Т. 109. - С. 83 - 94.

20. Печинкин А.В. Нестационарные характеристики системы массового массового с дисциплиной преимущественного разделения процессора// Математ. исследования. Сер. Вероятность и приложения (1990). - Т. 110. - С. 84 - 87.

21. Печинкин А.В. Об одной инвариантной системе массового обслуживания// Matemat. Operatonsforsch. und Statist. -Ser. Optimisation. 1983. - N 3. - S. 433 - 444.

22. Печинкин А.В. О стационарных вероятностях в системе с дисциплиной преимущественного разделения процессора// Изв. АН СССР. Техническая кибернетика. 1980. - N 5. - С. 73 - 77.

23. Печинкин А.В. Система обслуживания с дисциплиной LIFO и ограничением на суммарный объем требований// Вестник Российского университета дружбы народов. 1996. - N 2. -С. 85 - 99.

24. Печинкин А.В. СистемаМAP\G\l\n с дисциплиной LIFOс прерыванием и ограничением на суммарный объем требований// Автоматика и телемеханика. 1999. - N 12. - С. 114 -120.

25. Печинкин A.B. Система MI/G/1/п с дисциплиной LIFO и ограничением на суммарный объем требований// Автоматика и телемеханика. 1998. - N 4. - С. 106 - 116.

26. Печинкин A.B., Соловьев А.Д., Яшков С.Ф. О системе обслуживания первым требования с минимальной остаточной длиной// Изв. АН СССР. Техническая кибернетика. 1979. -N5.-С. 51-58.

27. Печинкин A.B., Таташев А.Г. Обобщение дисциплины преимущественного разделения процессора// Изв. АН СССР. Техническая кибернетика. 1981. - N 4. - С. 120 - 125.

28. Печинкина O.A. Стационарное распределение времени пребывания в системе Mk/G/l с инверсионной вероятностной дисциплиной обслуживания// Вестник Российского университета дружбы народов. Сер. Прикл. мат. и информатика. -1996. -N 1. - С. 94-112.

29. Печинкина O.A. Стационарное распределение очереди в системе с дисциплиной LIFO и групповым поступением требований// Вестник Российского университета дружбы народов. Сер. прикл. мат. и информатика. - 1996. - N 2. -С. 100 - 109.

30. Печинкина O.A. Стационарное распределение очереди в системе Mk/G/l с инверсионной вероятностной дисциплиной обслуживания// Автоматика и телемеханика. 1996. - N -7. -С. 105 - 114.

31. Печинкина O.A. Стационарные вероятности состояний в системе MAP\G\1 с инверсионной вероятностной дисциплиной обслуживания// Автоматика и телемеханика. 2000. -N 1. - С. 98 - 104.

32. Рыков В.В. Управляемые СМО// Итоги науки и техники. Сер. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. - 1974. - Т. 12.

33. Таташев А.Г. Инверсионная дисциплина обслуживанияв одноканальной системе с вероятностным приоритетом// В кн.: XLIII Всесоюзная научная сессия, посвященная Дню радио (НТОРЭС им. A.C. Попова). Тезисы докладов. Ч. 1. - М., 1988. - С. 55.

34. Таташев А.Г. Многоканальная система массового обслуживания с потерями кратчайших заявок// В кн.: Математические методы исследования сетей связи и сетей ЭВМ. Тезисы докладов. Витебск, январь февраль 1990. - С. 133 - 144.

35. Таташев А.Г. Многоканальная система массового обслуживания с потерями кратчайших требований// Автоматика и телемеханика. 1991. - N 7. - 187 - 189.

36. Таташев А.Г. Одна дисциплина обслуживания с разделением процессора// Автоматика и вычислительн. техника. -1993. N 6. - С. 27 - 32.

37. Таташев А.Г. Одна инвариантная система массового обслуживания// В кн.: III Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания (4-7 сентября 1990 г.). Тезисы докладов. М., 1990. - С. 185 - 187.

38. Таташев А.Г. Одна инверсионная дисциплина обслуживания в одноканальной системе с разнотипными заявками// Автоматика и телемеханика. 1999. - N 7. - С. 171 - 181.

39. Таташев А.Г. Одна инверсионная дисциплина обслуживания с групповым поступлением// Автоматика и вычислительн. техника. 1995. - N 1. - С. 53 - 59.

40. Таташев А.Г. Одна система массового обслуживания с инвариантной дисциплиной// Автоматика и телемеханика. -1992. N 7. - С. 92 - 96.

41. Таташев А.Г. Одна система массового обслуживания с инвариантной дисциплиной// В. кн.: IV Всесоюзное совещание по распределенным системам массового обслуживания 22 -27 апреля 1991 г. Душанбе. Тезисы докладов. М., 1991. -С. 225 - 227.

42. Таташев А.Г. Одна система массового обслуживания с инвариантными вероятностями состояний// Кибернетика исистемный анализ. 1993. - N 5. - С. 183 - 186.

43. Таташев А.Г. Одноканальная система массового обслуживания с инвариантной дисциплиной// В кн: Применение математических методов и вычислительной техники при решении народнохозяйственных задач. Тезисы докладов. Гомель, 1986. - С. 67 - 68.

44. Таташев А.Г. Одноканальная система массового обслуживания с потерей заявки наибольшей длины// Кибернетика и системн. анализ. 1997. - N 3. -С. 187 - 188.

45. Таташев А.Г. Одноканальная система с инверсионной дисциплиной обслуживания// Техника средств связи. Сер. Системы связи. - 1986. - Вып. 2. - С. 11 - 15.

46. Таташев А.Г. Одноканальная система с инверсионной дисциплиной обслуживания с разнотипными заявками// Ки-бернет. и системн. анализ. 2000. - N 3. - С. 170 - 174.

47. Таташев А.Г. Приоритетная дисциплина в системе Mn\Gn\1\1// Кибернет. и системн. анализ. 1999. - N 5. -С. 181 - 184.

48. Таташев А.Г. Система инверсионного обслуживания с прерыванием группового поступления заявок// Автоматика и вычислительн. техника. 1996. - N 5. - С. 57 - 65.

49. Таташев А.Г. Система массового обслуживания с групповым поступлением заявок// Кибернетика и системн. анализ. 1995. - N 6. - С. 163 - 165.

50. Таташев А.Г. Система массового обслуживания с переменной интенсивностью входного потока// Автоматика и телемеханика. 1995. - N 12. - С. 78 - 84.

51. Таташев А.Г. Система массового обслуживания GI\Hr\1\0 с потерей заявки максимальной длины// В кн.: Тезисы докладов 9-й Белорусской зимней школы-семинара по теории массового обслуживания/ Минск, 1993. С. 95.

52. Таташев А.Г. Система массового обслуживания GI\Hr\1\0 с потерей заявки максимальной длины// Кибернетика и системн. анализ. 1994. - N 2. - С. 188 - 182.

53. Таташев А.Г. Система обслуживания GI\M\1\0 с потерей заявки максимальной длины// В кн. Белорусское научно-техническое совещание "Сети связи и сети ЭВМ как модели массового обслуживания" (Гродно, январь 1991). С. 119.

54. Таташев А.Г. СМО с инвариантной дисциплиной// Техника средств связи. Сер. Системы связи. - 1991. - Вып. 6. -С. 29 - 33.

55. Тихоненко О.М. Определение характеристик суммарного объема требований в однолинейных системах обслуживания с абсолютным приоритетом// Автомат, и телемех. -1999. N 8. - С. 181-188.

56. Тихоненко О.М. Распределение суммарного объема в однолинейной системе с экспоненциальным обслуживанием и рекуррентным входным потоком// Автомат, и телемех. 1999. -N 7. - С. 80-84.

57. Тихоненко О.М. Системы обслуживания требования случайной длины с ограничениями / / Автоматика и телемеханика. 1989. - N 9. - С. 159 - 162.

58. Яшков С.Ф. Анализ очередей в ЭВМ. М.: Радио и связь, 1989. - 216 с.

59. Яшков С.Ф. Анализ системы с приоритетным разделением процессора// Автоматика и вычислительная техника. -1984. N 3. - С. 29 - 38.

60. Яшков С.Ф. Математические вопросы теории систем обслуживания с разделением процессора// Итоги науки и техники. Сер. Теория вероятностей. Математическая статистика. Теор. кибернетика. - ВИНИТИ. - Т. 29. - 1990. - С. 3-82.

61. Яшков С.Ф. О дисциплине преимущественного разделения процессора требованиями с наименьшей обслуженной длиной/ / Техника средств связи. Сер. АСУ. - 1978. - Вып. 2. -С. 51-61.

62. Kleinrock L. Time-sharing systems: a theoretical treatment// Assos. Comput. Mash. 1967. - V. 14. - N 2. - P. 242 - 251.

63. Kooper R., Nico Shun-Chen. Benes formula for M\G\1 —

64. FIFO explained by preemptive-resume LIFO// J. of Applied Probability. 1986. - V. 23. - N 2. - P. 550 -554.

65. Olivier G. Kostenminimale Prioritäten in Wartesystemen vom Typ M\G\1// Elektronische Rechenanlagen 1972. - B. 14. -N 6. - S. 262 - 271.

66. Schräge L. A proof of optimality of the shortest remaining time discipline// Operations Research, 1968. N 3. - P. 687 -690.

67. Schräge L. The queue M\G\1 with feedback to lower priority queues// Management Science. 1967. - V. 13. - N 7. - P. 466 -474.

68. Van Dijk N.M. A LCFS finite model with batch input and non-exponential service// Stochast. Prosseses and their Ap-plicat. 1989. - V. 33. - N 1. -P. 123 - 129.

69. Van Dijk N.M. Queueing systems with restricted workload. An explicit solution// J. of Applied Probability. 1990. - V. 27. -N 2. - P. 393 - 400.