ОСНОВЫ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ

Теория массового обслуживания изучает системы массового обслужива- ния (СМО) и сети массового обслуживания (СеМО). Рассматриваемые в этом разделе модели и математические схемы относятся к классу непрерывно- стохастических, т.е. это Q – схемы.

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

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

Совокупность взаимосвязанных СМО называется сетью массового об-

служивания (стохастической сетью).

Основными задачами, которые решаются в рамках теории массового об-

служивания, являются задачи:

анализа, т. е. определение количественных характеристик СМО и СеМО

при заданной структуре и заданных параметрах элементов структуры;

синтеза оптимальной структуры СМО или СеМО при заданных характери-

стиках и ограничениях на параметры элементов структуры.

Обобщенная структурная схема СМО.

Параметры и характеристики

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

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

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

Рис. 3.6. Обобщенная структурная схема СМО

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

полнение процессорами рассматривается как обслуживание заявок, поступаю- щих в ВС. Системные управляющие программы осуществляют управление прохождением заявок через ВС (диспетчирование) и исполняются, как прави- ло, одним из процессоров. Обычно выделяют две основные системные управ- ляющие программы: «Диспетчер 1» (Д1) и «Диспетчер 2» (Д2), реализующие, соответственно, дисциплины ожидания и обслуживания.

Система работает следующим образом.

Появление на входе СМО заявки инициирует выполнение программы Д1, которая распознает приоритет поступившей заявки и ставит ее в соответст- вующую очередь Оi, реализованную в специально зарезервированной области памяти. Д2 анализирует состояние очередей О1, О2, ..., ОNи состояние каналов K1, K2, ..., Km(процессоров). При наличии свободного канала Д2 выбирает за- явку, имеющую преимущественное право на обслуживание, и инициирует со- ответствующий канал и необходимую прикладную программу. Инициирование происходит в моменты окончания исполнения прикладных программ и про- граммы Д1.

Параметры входящего потока

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

f(t) = le(-lt). (3.18)

Привлекательность простейшего потока объясняется рядом обстоя- тельств. Допущение о простейшем потоке заявок позволяет получать аналити- ческие зависимости характеристик СМО от параметров входящего потока, что затруднительно для других видов потока заявок.

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

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

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

M

l = е li. (3.19)

i =1

Степень важности заявок может быть различной. По этому признаку за- явки делят на классы, каждому классу присваивается приоритет К ( K = 1, N), причем наивысшим приоритетом обладают заявки первого класса, с увеличе- нием К приоритет заявки падает.

Различают «терпеливые» заявки, т. е. такие, на время пребывания кото-

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

Параметры структуры СМО

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

Производительность канала обслуживания обратна длительности обслу- живания заявки, равной промежутку времени, необходимому каналу обслужи- вания для обслуживания заявки. В общем случае это случайная величина с функцией распределения F(tоб), плотностью распределения f(tоб)и математиче-

ским ожиданием

tоб.

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

f(tоб) = me(-mtоб) .(3.20)

Если в момент появления заявки на входе СМО хотя бы один канал сво-

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

разделена на несколько очередей по числу различаемых системой приоритетов, для каждой из которых должно быть указано число мест ni,( i = 1, N). На число мест в очереди часто накладывается ограничение. Это может быть сделано как

для каждой очереди в отдельности, так и для всей совокупности очередей в це-

лом. При этом возможны конфликтные ситуации, решением которых является отказ системы принять заявку.

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