Служит мерой загрузки СМО и является коэффициентом загрузки. Тогда коэффициент простоя

Число заявок в СМО. Вероятности состояний z₁ ,..., z_k,... определяются из общей формулы размножения и гибели:

Определим среднее число заявок в системе п. В текущий момент времени в системе может быть 0, 1, 2,.... k,... заявок с вероятностями p₀, p₁, p₂,…, p_k… Математическое ожида­ние количества заявок равно

Подставим значение р_k и р₀, исключив первое слагаемое, равное нулю:

Вынесем за знак суммы ρ (1 — р):

Но — это производная по от :

.

Меняя местами операции дифференцирования и суммирования, получим

(4)

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

п = ρ/(1 - р). (5)

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

(6)

Зависимость средней длины очереди от коэффициента загрузки изображена на рис. 2. При ρ > 0,6—0,7 очередь стремительно увеличивается и при ρ 1 уходит в бесконечность. У детерминированной системы коэффициенты вариации интенсивностей потоков заявок и обслуживания равны нулю, при ρ < 1 очередь отсутствует, а при ρ 1 — уходит в бесконечность. Для систем, которые имеют промежуточные коэффициенты вариации 0 <v < 1, зависимости средней длины очереди от коэффициента загрузки лежат в области, заштрихованной на рис. 2.

Время реакции. Для определения среднего времени реакции рассмотрим поток заявок, прибывающих в СМО, и поток заявок, покидающих систему. Если в системе устанавливается предельный стационарный режим при ρ<1, то среднее число заявок, прибывающих в единицу времени, равно среднему числу заявок, покидающих ее: оба потока имеют интенсивность .

Рис. 2. Зависимость средней длины очереди от коэффициента загрузки для простейшей СМО

Рис. 3. Временная диаграмма процессов поступления и ухода заявок

Обозначим через Х (t) число заявок, поступивших в СМО до момента времени t, а через Y (t) — число заявок, покинувших СМО до момента t. Та и. другая функции являются случайными и меняются скачком — увеличиваются на единицу в моменты прихода или ухода заявок (рис. 3).

Очевидно, что для любого момента времени t разность функций п (t)=Х (t) — Y (t) есть число заявок, находящихся в СМО. Рассмотрим большой промежуток времени Т и вычислим среднее число заявок, находящихся в системе:

Интеграл изображен в виде заштрихованной фигуры на рис. 3. Она состоит из прямоугольников, каждый из которых имеет высоту, равную единице, и основание, равное времени пребывания в системе i-й заявки t_i:

где сумма распространяется на все заявки, поступившие в систему за время Т.

Разделим правую и левую части на Т.

Разделим и умножим правую часть на :

Произведение ,—это среднее количество заявок, пришедших за время Т. Если разделить сумму всех времен t_i на среднее число заявок, то получится среднее время пребывания заявки в системе, т. е. среднее время реакции и:

(7)

Это формула Литтла: для каждой СМО при любом характере потока заявок и при любом распределении времени обслуживания среднее время реакции равняется среднему числу заявок в системе, деленному на интенсивность потока заявок. Отсюда получается:

(8)

Вторая формула Литтла связывает среднее время пребывания заявки в очереди и среднее число заявок в очереди подобным соотношением:

(9)

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

(10)

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

При ρ > 1 в системе не устанавливается стационарный режим. В пределе длина очереди, а значит, и времена ожидания и реакции стремятся к бесконечности.

2. Характеристики вычислительных систем как сложных
систем массового обслуживания

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

где — средняя длительность обслуживания заявок типа i. Суммарная загрузка прибора со стороны всех потоков

(11)

Рис. 4. Граф состояний многоканальной СМО

Условие существования стационарного режима: Р < 1. Остальные характеристики обслуживания n_i, l_i, u_i, определяются для каждого i-гo потока в отдельности по формулам (5)— (9).

Средние времена ожидания _ср и реакции u_ср по одной заявке из суммарного потока в системе связаны со средними количествами заявок в очереди и в системе следующими соотношениями:

(12)

(13)

где — суммарная интенсивность потоков; — вероятность того, что поступившая заявка является заявкой i-гo типа;

l_cp — средняя длина очереди заявок всех типов; n _ср — среднее число заявок всех типов в системе.

Многоканальная СМО. Предположим, что система имеет т обслуживающих каналов с одинаковой интенсивностью обслуживания , при общем простейшем потоке заявок с интенсивностью . Такая система условно обозначается М/М/т. Граф состояний этой системы (рис. 4) подобен графу одноканальной СМО. Интенсивности перехода в соседнее правое состояние определяются, как и у одноканальной СМО, интенсивностью входного потока: с приходом очередной заявки система переходит в следующее правое состояние. Иначе обстоит дело с интенсивностями у нижних стрелок. Пусть система находится в состоянии z₁ — работает один канал. Он производит обслуживании в единицу времени. Тогда . Представим, что система находится в состоянии z₂. Для перехода в состояние z₁ надо, чтобы закончил обслуживание первый или второй канал. Значит, суммарная интенсивность их обслуживания Суммарный поток обслуживания k каналами имеет интенсивность k . При k т интенсивность обслуживания сохраняется т . Получается модель размножения и гибели. Делая выкладки, как для одноканальной СМО, получим

Средняя длина очереди

(14)

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

получим среднее число заявок в системе:

(15)

По формулам Литтла определяется среднее время пребывания заявки в очереди:

(16)

и в системе — время реакции:

(17)

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

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

(18)

где — математическое ожидание длительности обслуживания М [ ]; k — параметр распределения (k 1); Г (k) — гамма-функция.

Дисперсия гамма-распределения

(19)

При k = 1 гамма-распределение вырождается в экспоненциальное. В пределе при k это распределение становится детерминированным с постоянной длительностью обслуживания . Параметр распределения k может быть определен по математическому ожиданию и дисперсии:

(20)

Рис. 5. Нормированное распределение Эрланга

При целочисленном k Г (k) = (k— 1)!. Тогда из уравнения (18)имеем

, (21)

Это плотность нормированного распределения Эрланга k- го порядка. Вид распределения изображен на рис. 5. В данном распределении в отличие от потока Эрланга математическое ожидание не зависит от k и при k это распределение стремится к детерминированному, а не к нормальному.

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

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

(26)

среднее число заявок в системе

(27)

Последние два выражения называются формулами Поллачека—Хинчина. Средние времена пребывания заявок в очереди и в системе определяются по формулам Литтла.

Для системы M/G/1 могут быть аналитически определены дисперсии выходных характеристик. Подобные формулы известны также для случая многомерного простейшего потока заявок.

Системы с отказами. Предположим, что на ВС, представленную как m-канальная СМО, поступает простейший поток заявок с интенсивностью К. Поток обслуживания имеет произвольный закон распределения с интенсивностью р. Это система M/G/m. При этом очередная заявка, поступившая в систему, когда все каналы заняты, покидает ее без обслуживания. Это означает, что очереди в системе отсутствуют. Характеристиками такой системы могут служить пропускная способность, вероятность обслуживания и среднее число занятых каналов. Данная система соответствует модели размножения и гибели. На основании формул (13) и (14) (лекция 9) можно вывести вероятность того, что в СМО находится т заявок, т. е. все каналы заняты:

(28)

Вероятность того, что очередная заявка будет обслужена,

(29)

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

(30)