ХАРАКТЕРИСТИКИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ Исполнитель

ХАРАКТЕРИСТИКИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

План

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

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

3. Методы приближённой оценки характеристик  вычислительных систем

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

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

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

Поток обслуживания тоже будем считать простейшим с интенсивностью . В соответствии с символикой, принятой в теории массового обслуживания, такая система обозначается М/М/1.

Выделим состояния СМО по числу заявок, находящихся в системе:

z₀ — прибор свободен, очереди нет;

z₁ — прибор занят (обслуживает заявку), очереди нет;

z₂ — прибор занят, одна заявка в очереди;

z_k — прибор занят, (k — 1) заявок стоит в очереди.

Рис. 5. Граф состояний СМО

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

Коэффициент загрузки. Предельная вероятность состояния

                                                     (1)

Обозначая  получаем

                            .                                   (2)

Ряд в этой формуле представляет собой геометрическую прогрессию. Известно, что при ρ < 1 ряд сходится. Сумма членов прогрессии при этом равна 1/(1 — ρ), откуда            

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

Это означает, что отношение

                                                                                                     (3)

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

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

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

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

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

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

{spoiler=Подробнее}.

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

                                                                                   (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)

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

                                                                             (31)

Системы с приоритетными дисциплинами диспетчеризации.

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

Например, допустим, что в СМО поступает М типов простейших потоков с интенсивностями  и длительности обслуживания заявок каждого потока имеют математические ожидания  и дисперсии . системе используется смешанная дисциплина диспетчеризации с тремя классами: 1) заявкам типов 1,..., M₁ присвоены абсолютные приоритеты по отношению к заявкам второго и третьего классов; 2) заявкам типов M₁+1,..., M₁+M₂ — относительные приоритеты по отно­шению к заявкам третьего класса; 3) заявки типов M₁+M₂++1,..., M обслуживаются в порядке поступления. Среднее время ожидания заявок различных типов определяется из выра­жения:

                                         (32)

где         

Из формулы (32) могут быть получены как частные случаи

характеристики систем с абсолютными (, относи­тельными (М₁ = M₃ = 0) и смешанными приоритетами с двумя классами заявок: с абсолютными и относительными приорите­тами (М₃ = 0), с абсолютными приоритетами и без приоритетов (М₂ = 0), с относительными приоритетами и без приоритетов (M₁ = 0).

3. Методы приближённой оценки характеристик
вычислительных систем

Оценка при большой нагрузке. Аналитические зависимости, позволяющие определить параметры распределений выходных характеристик, имеются только для ограниченного круга систем. У более широкого круга систем могут быть вычислены средние значения в стационарном установившемся режиме. Однако оста­ется ряд систем и режимов, для которых отсутствуют точные фор­мулы даже по определению средних значений. К таким системам относятся, в первую очередь, системы с произвольными распреде­лениями периодов поступления и длительностей обслуживания заявок. Это системы G/G/1 и G/G/m. При отсутствии точных зависи­мостей приходится довольствоваться приближенными оценками.

Одним из методов приближений является оценка характери­стик при близких к единице значениях коэффициента загрузки, как наиболее важных с практических позиций. В частности, для системы G/G/1 время ожидания заявки в очереди распределено по экспоненциальному закону и среднее время ожидания можно опре­делить по следующей формуле:

                                                                           (33)

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

Используя зависимость (10) и формулы Литтла, можно вы­числить средние значения других характеристик.

Определение границ. При значениях 0  ρ < 1 для оценки характеристик используется несколько различных подходов опре­деления верхней и нижней границ, в пределах которых находится истинное значение той или иной характеристики. Например, для системы G/G/1 приводятся следующие формулы расчета гра­ниц среднего времени ожидания заявки в очереди:

                     (24)

где v,  — коэффициенты вариации периодов поступления и длительностей обслуживания заявок соответственно.

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

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

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

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

Когда Х (f) становится значительно больше единицы, на ос­новании закона больших чисел можно ожидать лишь небольшого относительного отклонения этой величины от ее среднего значения

Рис. 6. Временная диаграмма процессов поступления и ухода заявок с непрерывной аппроксима­цией зависимостей количества зая­вок от времени  М [х(t)]= На этом основывается  приближение первого порядка, которое за­ключается в замене вероят­ностного процесса его сред­ним значением, зависящим от времени, т. е. детерминированным процессом  . Это отно­сится и к процессу ухода заявок . Тогда число заявок в сис­теме тоже представляет собой детерминированную непрерывную функцию времени:

                                                                                       (35)

Функции  и определяются из зависимостей:

                                                                                                                                         (36)

                                                                                 (37)

—число поступивших и покинувших систему заявок к нулевому моменту времени.

Диффузионная аппроксимация. Непрерывное приближение яв­ляется довольно грубым, поскольку не учитывает случайный характер процессов поступления и ухода заявок. По методу диф­фузионной аппроксимации непрерывное приближение усовершен­ствуется путем учета флуктуаций относительно среднего значения. С этой целью случайный процесс (42) заменяется марковским процессом диффузионного типа х (/) с непрерывным временем и непрерывным множеством состояний. Диффузионный процесс определяется  коэффициентом сноса

и коэффициентом диффузии

Эти коэффициенты выражаются через параметры исходной модели. Для системы G/G/1 считается, что при больших t рас­пределение Х (t) является приближенно нормальным с математи­ческим ожиданием  и дисперсией  и распределение Y (f) тоже приближенно нормальное с математическим ожиданием  и дисперсией . Тогда коэффициент сноса

                                                                                             (38)

 и коэффициент диффузии

                                                                               (39)

В связи с тем, что процесс п (t) не может принимать отрица­тельных значений, для аппроксимирующего процесса х (t) зада­ется граничное условие, удерживающее его траекторию на неотри­цательной полуоси. Например, при достижении х (t) =0 совер­шается скачок в целочисленные точки положительной полуоси, выполняемый с заданным распределением вероятностей после экспоненциальной задержки в нуле.

Применение диффузионной аппроксимации дает возможность получения оценок различных характеристик СМО. В частности, для системы G/G/1 средняя длина очереди в стационарном режиме определяется  по формуле

                                                                         (40)

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

Контрольные вопросы

1. Одноканальная СМО для описания ВС.
2. Как определяется коэффицент загрузки ВС?
3. Как определяется число заявок в СМО?
4. Как определяется длина очереди в СМО?
5. Как определяется время реакции в СМО?
6. Формулы Литтла.
7. Многоканальная СМО для описания ВС.
8. Основные характеристки многоканальной СМО.
9. Для каких систем используются методы приближенной оценки характеристик?{/spoilers}