Основы теории массового обслуживания

Москва
Горячая линия - Телеком
2013

УДК 621.391 
ББК 22.18я73 
      К27 
Р е ц е н з е н т :  Заслуженный работник связи Российской Федерации,  
канд. техн. наук, профессор  А. П. Пшеничников 

Карташевский В. Г. 
К27  Основы теории массового обслуживания. Учебник для 
вузов. – М.: Горячая линия–Телеком, 2013. – 130 с: ил. 
ISBN 978-5-9912-0346-3. 

Освещены основы теории массового обслуживания, знание которых необходимо для современного представления о 
процессах обслуживания сообщений в телекоммуникационных и вычислительных сетях. Рассмотрены потоки заявок 
на обслуживание, при условии, что структура потока носит 
случайный характер. Особое внимание уделено пуассоновскому потоку событий. Рассмотрены потоки, обладающие 
свойствами самоподобия. Проанализирована работа устройств массового обслуживания (в обозначении Кендалла) 
типа М/М/1,  M/G/1,  G/M/1 и их модификаций. Рассмотрены системы с относительными приоритетами обслуживания. Рассмотрено интегральное уравнение Линдли. Приведены основные сведения о сетях массового обслуживания. 
Для студентов вузов, обучающихся по направлению 
210700 – «Инфокоммуникационные технологии и системы 
связи».  

22.18я73 

Адрес издательства в Интернет WWW.TECHBOOK.RU 
 
Учебное издание 

Карташевский  Вячеслав Григорьевич 

Основы теории массового обслуживания  

Учебник для вузов 

Редактор  Ю. Н. Чернышов 
Компьютерная верстка  Ю. Н. Чернышова 
Обложка художника  О. В. Карповой 

 

Подписано к печати 15.06.13.  Формат 60×88 1/16. Усл. печ. л. 8,125.  Изд. № 13346.  Тираж 500 экз. (1-й завод 100 экз.) 

ISBN 978-5-9912-0346-3                              ©  В. Г. Карташевский, 2013 
                                 ©  Издательство «Горячая линия–Телеком», 2013 

Введение

Ежедневно мы сталкиваемся с ситуациями, в которых появляется потребность в массовом обслуживании. Самым простым примером такой ситуации является очередь в магазине или на остановке
автобуса, которая появляется из-за того, что у тех, кто занимается
обслуживанием, нет возможности обслужить всех сразу. Не случайно в публикациях на английском языке теорию массового обслуживания называют теорией очередей. Если бы речь шла, в основном,
об очередях в магазине и на остановке автобуса, то, вероятно, теория
массового обслуживания не получила бы серьезного современного
развития.
Но мы живем в век инфокоммуникационных технологий, которые становятся одним из основных ресурсов развития ведущих стран мира. Именно потребности развития этих технологий
вызвали необходимость совершенствования теории массового обслуживания, которая на сегодняшний день способна дать адекватный
анализ работы и методы проектирования телекоммуникационных и
вычислительных сетей, всевозможных сетевых и вычислительных
устройств, а также информационных технологий.
Современные вычислительные и телекоммуникационные сети
обеспечивают пользователям широкий набор услуг, включая передачу голосовых и факсимильных сообщений, электронную почту,
работу с удаленными базами данных в реальном времени, интерактивное телевидение, службу новостей и массу других услуг. Все это
стало возможным благодаря развитию методов и технологий цифровой обработки сигналов и сообщений, которые на сегодняшний день
характеризуются передачей любых сообщений в цифровой «пакетной» форме. Любые устройства обработки пакетов, какую бы технологическую задачу они не решали, должны наилучшим образом реализовать обработку пакетов от различных пользователей, так как
при современных объемах и скоростях передачи информации всегда
возникает очередь из пакетов, пришедших на обработку. Понятие
«наилучшим образом» расшифровывается в теории массового обслуживания очень просто — с минимальными временными затратами
и минимальной вероятностью отказа в обслуживании.
Методы теории массового обслуживания позволяют решать раз

Введение

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

Рис. В.1. Основные элементы системы массового обслуживания

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

Введение
5

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

Рис. В.2. Полнодоступное и
неполнодоступное включение

Системы бывают полнодоступные и неполнодоступные (обслуживающие приборы или каналы доступны любому требованию — это полнодоступное включение). Полнодоступность и неполнодоступность иллюстрируется рис. В.2.
Если использовать аналогии с телефонной связью, то, например, линия «a»
доступна абонентам А и В, линия «c» доступна абонентам А и D, а
линия «e» доступна абонентам А, В, С, D, т. е. всем абонентам.
Важным фактором, определяющим работу системы массового
обслуживания, является способ обслуживания. Различают следующие способы: в порядке поступления (FIFO), в обратном порядке
(LIFO), случайным образом, обслуживание по приоритетам и ряд
других. Возможно объединение очередей, взаимодействие очередей
и т. д.
Способ обслуживания тесно связан с поведением заявки на обслуживание — отказ становиться в очередь, использование априорной информации, уход из очереди до начала обслуживания (соглашение между заявками) и т. д.
Обозначенный на рис. В.1 выходящий поток как элемент системы массового обслуживания важен, так как сам может быть входящим потоком для другой системы. Характеристики выходящего
потока зависят от характеристик входящего потока и времени обслуживания. Анализ выходящего потока позволяет найти характеристики обслуживающих приборов.
В заключение подчеркнем еще раз, что под качеством обслуживания в теории массового обслуживания понимается не то, как
хорошо выполнена технологическая операция (бритьё, качество ремонта и др.), а как хорошо организовано обслуживание, насколько
полно загружены приборы, не создаётся ли большая очередь, велик
ли уход необслуженных требований.

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

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

1.1. Определение вероятности и основные
соотношения
Основным понятием теории вероятностей является случайное
событие A, которое может произойти или не произойти в какомто эксперименте. Частость наступления события A определяется
следующим образом:

P(A) = k

m,
(1.1)

где k — число испытаний, соответствующих появлению события A;
m — число всех проведенных испытаний.
При m → ∞ понятие частости отождествляется с понятием вероятности с сохранением того же обозначения. Из определения
(1.1) следует

0 ⩽ P(A) ⩽ 1.
(1.2)

Если P(A) = 0, то событие A называют невозможным. При
P(A) = 1 событие A называют достоверным.
Рассмотрим группу событий A1, A2, ..., An. События, принадлежащие одной группе, называют однородными. События A1, A2, ...,
An называют независимыми, если появление одного их них не связано с появлением другого. События A1, A2, ...An называют несовместимыми, если появление одного их них исключает появление
другого.

Математические понятия теории массового обслуживания
7

Группу событий называют полной, если при реализации опыта
одно из событий произойдет обязательно. Поэтому

n
∑

i=1
P(Ai) = 1.
(1.3)

Если события Ai, i = 1, 2, ...n, несовместимы, то вероятность
наступления любого события определяется формулой

P(A1 или A2 или ... или An) =

n
∑

i=1
P(Ai).

Вместо союза «или» в математике принято использовать знак
∪. Поэтому предыдущая формула записывается в виде

P(A1 ∪ A2 ∪ ... ∪ An) =

n
∑

i=1
P(Ai).
(1.4)

Если события Ai, i = 1, 2, ...n, независимы, то вероятность совместного наступления событий Ai определяется как

P(A1 и A2 и ... и An) = P(A1 ∩ A2 ∩ ... ∩ An) =

n
∏

i=1
P(Ai).
(1.5)

В выражении (1.5) вместо союза «и» использован знак ∩.
Если события Ai, i = 1, 2, ...n, независимы, но совместимы, то
вероятность наступления одного (любого) события вычисляется по
формуле

P(A1 ∪ A2 ∪ ... ∪ An) = 1 −

n
∏

i=1
(1 − P(Ai).
(1.6)

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

P(A1 ∩ A2) = P(A1)P(A2 | A1) = P(A2)P(A1 | A2).
(1.7)

В формуле (1.7): P(A1), P(A2) — априорные (до опыта), безусловные вероятности наступления событий A1 и A2, а P(A1 | A2) и
P(A2 | A1) — апостериорные (после опыта) вероятности наступления событий A1 и A2. Это так называемые условные вероятности,
так как, например, P(A1 | A2) понимается как вероятность наступления события A1 при условии, что событие A2 уже произошло.
Из (1.7) следует

P(A1 | A2) = P(A1)P(A2 | A1)

P(A2)
.
(1.8)

(Аналогичная формула справедлива и для P(A2 | A1).)

Р а з д е л 1

Когда события A1 и A2 независимы, априорные и апостериорные вероятности равны

P(A1 | A2) = P(A1);
P(A2 | A1) = P(A2).
(1.9)

Поэтому
P(A1 ∩ A2) = P(A1)P(A2).
(1.10)

Выражение (1.10) служит определением независимости двух случайных событий A1 и A2.
Наличие зависимости между событиями A1 и A2 характеризуется тем, что разность

P(A1 ∩ A2) − P(A1)P(A2)

отлична от нуля.
B качестве количественной меры зависимости
между событиями принимается величина, пропорциональная этой
разности.
Эту величину называют коэффициентом корреляции
между событиями A1 и A2 и определяют как

RA1A2 =
P(A1 ∩ A2) − P(A1)P(A2)
√

P(A1)P(A2)(1 − P(A1))(1 − P(A2))
.
(1.11)

Когда события A1 и A2 независимы, то RA1A2 = 0, но равенство нулю коэффициента корреляции не означает независимости событий.
Иногда необходимо определить вероятность события B, появляющегося с одним из n взаимно несовместимых событий A1, A2, ..., An,
составляющих полную группу событий. Заметим, что события B и
Ai, i = 1, 2, ..., n, неоднородны. Так как любые две комбинации событий B ∩ Ai и B ∩ Aj (i ̸= j) несовместимы, то согласно (1.4)

P(B) =

n
∑

i=1
P(B ∩ Ai).
(1.12)

Но
P(B ∩ Ai) = P(Ai)P(B | Ai).
(1.13)

Следовательно,

P(B) =

n
∑

i=1
P(Ai)P(B | Ai).
(1.14)

Формула (1.14) называется формулой полной вероятности.

1.2. Биномиальная формула

Рассмотрим последовательность независимых испытаний (так
называемую схему Бернулли).

Математические понятия теории массового обслуживания
9

Производится N независимых испытаний. Вероятность появления события A при каждом испытании равна p.
Вероятность непоявления события A равна q = 1 − p. Найдем вероятность того,
что после N испытаний событие A появится ровно k раз (k ⩽ N).
Пусть Ak — событие, состоящее в том, что после N независимых
испытаний событие A появится k раз. Выдвинем гипотезу (сделаем
предположение), что событие B1 заключается в том, что событие A
появляется при k первых испытаниях и не появляется при N − k
последующих.
Тогда

P(Ak ∩ B1) = pp · · · p
k раз

qq · · · q
(N−k) раз

= pkqN−k.

Гипотеза B2 будет состоять в том, что событие A не появляется
при первом испытании, затем появляется k раз подряд и снова не
появляется при остальных (N − k − 1) испытаниях. Теперь

P(Ak ∩ B2) = q pp · · · p
k раз

qq · · · q
(N−k−1) раз

= pkqN−k.

Очевидно, что при любой гипотезе Bi относительно порядка
появления события A, независимо от перестановки сомножителей,
результат для P(Ak ∩ Bi) будет равен pkqN−k. Число гипотез Bi,
очевидно, будет равно числу сочетаний из N элементов по k, т. е.

Ck
N =
N!

k!(N − k)!.
(1.15)

Так как гипотезы B1, B2, . . . BCk
N несовместимы, то по формуле полной вероятности (1.14) получаем

P(Ak) =

Ck
N
∑

i=1
P(Ak ∩ Bi) = Ck
NpkqN−k.
(1.16)

Нетрудно видеть, что вероятность P(Ak) равна коэффициенту при
xk в разложении бинома (q +px)N по степеням x. Поэтому формулу
(1.16) называют биномиальной.

Совокупность событий Ak составляет полную группу взаимно
несовместимых событий. Поэтому

N
∑

k=0
P(Ak) = 1.

Р а з д е л 1

1.3. Функции распределения

Естественным обобщением понятия события является понятие
случайной величины. Случайные величины бывают непрерывные
и дискретные.
К понятию дискретной случайной величины можно прийти, если поставить во взаимно однозначное соответствие каждому событию некоторое действительное число xk, k = 1, 2, . . . n, где n — возможное число событий. Вероятность Pk того, что дискретная случайная величина xk примет одно из возможных значений, равна вероятности появления случайного события, соответствующего этому
значению. Полный набор Pk этих вероятностей характеризует закон распределения вероятностей дискретной случайной величины.
Аналитическим выражением закона распределения являются функции распределения, которые могут быть функциями целочисленного или непрерывного аргумента.
Для любой случайной величины ξ интегральная функция распределения Fξ(x) может быть введена в виде

Fξ(x) = P(ξ ⩽ x).
(1.17)

Функция Fξ(x) показывает, как зависит от выбранного порогового
уровня x вероятность того, что значения случайной величины не
превосходят этот уровень.
Основные свойства Fξ(x):

1.
lim
x→−∞ Fξ(x) = Fξ(−∞) = P(ξ ⩽ −∞) = 0;
(1.18)

2.
lim
x→∞ Fξ(x) = Fξ(∞) = P(ξ ⩽ ∞) = 1;
(1.19)

3. Если x2 ⩾ x1, то Fξ(x2) ⩾ Fξ(x1).
(1.20)

Данные три свойства необходимы и достаточны для того, чтобы любая функция F(·)(x), удовлетворяющая этим условиям, была
интегральной функцией распределения случайной величины.
Очевидно,

P(x1 < ξ ⩽ x2) = Fξ(x2) − Fξ(x1).
(1.21)

Так как P(x1 < ξ ⩽ x2) неотрицательна, то при x2 ⩾ x1 всегда
Fξ(x2) ⩾ Fξ(x1), т. е. интегральная функция является неубывающей
функцией.
Для дискретной случайной величины вероятность того, что
случайная величина примет значение xk,

Pk = P(ξ = xk) = Fξ(xk) − Fξ(xk−1).
(1.22)