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

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

Например, допустим, что в СМО поступает М типов простейших потоков с интенсивностями и длительности обслуживания заявок каждого потока имеют математические ожидания и дисперсии . системе используется смешанная дисциплина диспетчеризации с тремя классами: 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. Для каких систем используются методы приближенной оценки характеристик?

Литература

45.

46.

47.

48.

49.

Лекция 11. НЕСТАЦИОНАРНЫЕ РЕЖИМЫ ФУНКЦИОНИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ (2 часа)

План

1. Нестационарные режимы функционирования вычислительных
систем

2. Характеристики вычислительных систем как стохастических сетей

1. Нестационарные режимы функционирования
вычислительных систем

Переходные процессы. До сих пор рассматривались характе­ристики ВС в стационарном установившемся режиме. Однако на практике не менее важным является анализ нестационарных режимов. Значения выходных характеристик в нестационарных режимах функционирования ВС можно определить для одних систем путем численного решения уравнений Колмогорова (9) задавая в них интенсивности как функции времени для других систем — в результате непрерывной или диффузион­ной аппроксимации процессов.

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

Рис. 12. Временная диаграмма по­ведения системы в режиме перегрузки

Рис. 11. График зависимости сред­него времени ожидания от текущего времени в переходном режиме

В работе приводятся результаты анализа переходных процессов для системы M/G/1. Интенсивность входящего пуассо-новского потока принималась равной 0,95 заявок в минуту, а среднее время обслуживания v =1 мин. Коэффициент загрузки р = 0,95. Рассматривались следующие распределения длитель­ности обслуживания:

1) экспоненциальное распределение

2) нормированное распределение Эрланга 8-го порядка со средним, равным восьми,

3) комбинация экспоненциального распределения со средним значением 4 и распределения Эрланга 4-го порядка со средним зна­чением 2/3

Зависимости среднего времени ожидания заявок в очереди в течение переходного процесса для этих случаев показаны на рис. 11. Установившиеся значения соответственно равны 19; 10,69 и 35,2 мин. Если принять длительность переходного про­цесса равной бремени, в течение которого среднее время ожидания достигает 0,8 от установившегося значения, то для этих случаев она соответственно составит 15,2; 8,55 и 28,2 ч. За эти времена система успевает обслужить 867, 487 или 1605 заявок. Можно утверждать, что ВС с суточным циклом никогда не работают практически в установившемся режиме при большой загрузке. Этот вывод можно распространить на ВС с большей длительностью цикла, если они имеют соответственно меньшие интенсивности поступления и обслуживания заявок.

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

Рассмотрим этот режим на упрощенном примере (рис. 12). Предположим, что в одноканальную систему поступает одномерный поток заявок с интенсивностью . Заявки обслуживаются в порядке поступления с постоянной интенсивностью

В начальный момент t₀ коэффициент загрузки р < 1. В системе. имеются заявки, накопление которых обусловлено случайным характером их поступления и обслуживания.

Затем интенсивность поступления заявок начинает расти, достигая максимального значения. С момента t₁ становится р > 1 и увеличивается число заявок в системе. При максимальном число заявок n(t) растет линейно, стремясь к бесконечности. Но в связи с тем, что в момент t₂ интенсивность поступления начинает уменьшаться, рост n(t) замедляется и достигает максимума в момент t₃ при р = 1.

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

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

2. Характеристики вычислительных систем
как стохастических сетей

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

1) число СМО, образующих сеть (S₁, S₂,..., S_n);

2) число каналов каждой СМО (т₁..., m _n);

3) матрица вероятностей передач Р = [p_ij], где р_ij — вероятность того, что заявка, покидающая систему S_i, поступает в систему S_j (i, j =0,1,...n);

4) интенсивность источника заявок S₀ в разомкнутой сети или число М заявок в замкнутой сети;

5) средние длительности обслуживания заявок в системах S₁,...S_n.

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

1,..., n. (1)

Из этой системы уравнений находятся соотношения интенсивностей потоков и в виде

(2)

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

Для замкнутой сети принимается .

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

(3)

где

(4)

(5)

(6)

Вероятность состояния замкнутой сети Р (M₁,..., M_n), характеризующая вероятность того, что в системе S₁ находится М₁ заявок,

и т. д., вычисляется по формуле

(7)

где — символ суммирования по всем возможным состояниям, для которых

(8)

По вероятностям состояний определяются характеристики сети.

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

(9)

среднее число в системе

(10)

а среднее время ожидания в очереди , и пребывания в системе u_j определяется по формулам Литтла из (9) и (10). Тогда характеристики сети в целом: среднее число заявок во всех очередях

(11)

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

(12)

среднее время ожидания в очередях

(13)

среднее время реакции сети

(14)

Вычисление характеристик замкнутой сети. Для любой S_j СМО сети средняя длина очереди

(15)

среднее число заявок в СМО

(16)

средние времена ожидания и пребывания u_j вычисляются по формулам Литтла. Среднее время цикла сети, т. е. интервал времени между двумя последовательными выходами одной и той же заявки из СМО S_i составляет Uj = M/ _j.

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

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

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

1. Основные подходы исследования характеристик ВС в нестационарном режиме.

2. Исследование характеристик в режиме перегрузок.

3. Описание стохастической сети применительно к ВС.

4. Определение вероятности состояний.

5. Определение характеристик разомкнутой и замкнутой сети.

Литература

50.

51.

52.

53.

54.

Лекция 12. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ (2 часа)

План

1. Процедура имитационного моделирования

2. Обобщенные алгоритмы имитационного моделирования

1. Процедура имитационного моделирования

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

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

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

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

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

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

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

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

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

где — случайные величины с известными функциями распределения.

Для решения задач такого вида применяется следующий алгоритм:

1) по каждой из величин производится случайное испытание, в результате которого определяется некоторое конкретное значение случайной величины (способы проведения случайного испытания описаны ниже);

2) используя найденные величины, определяется одно частное значение y_i по вышеприведенной зависимости;

3) предыдущие операции повторяются N раз, в результате чего определяется N значений случайной величины у;

4) на основании N значений величины у находится ее эмпирическая функция распределения.

Имитация функционирования системы. Предположим, что ВС состоит из процессора 1 с основной памятью, устройства ввода 4, печатающего устройства 2 и монитора 3. Через устройство ввода поступает поток заданий X₁. Процессор обрабатывает задания и результаты обработки выдает на печатающее устройство (принтер). Одновременно с этим ВС используется, например, как информационно-справочная система. Оператор-пользователь, работающий за монитором, посылает в систему запросы X₂, которые обрабатываются процессором, и ответы выводятся на монитор. Процессор работает в двух программном режиме: в одном разделе обрабатываются задания X₁, в другом, с более высоким относительным приоритетом, — запросы Х₂.

Представим данную ВС в упрощенном варианте в виде стохастической сети из четырех СМО. Потоки заданий и запросов будем называть потоками заявок. Считаем потоки X₁ и X₂ независимыми. Известны функции распределения периодов следования заявок и и длительностей обслуживания Т_1k и Т_2k заявок k-м устройством. Требуется определить времена загрузки каждого устройстваи времена реакции по каждому из потоков.

Рис. 1. Временная диаграмма функционирования ВС

В начале определяется момент поступления в систему первой заявки потока Х₁ по результатам случайного испытания в соответствии с функцией распределения периода следования заявок. На рис. 1 это момент времени (здесь и далее верхний индекс обозначает порядковый номер заявки данного потока). То же самое делается для потока Х₂. На рис. 2 момент поступления первой заявки потока . Затем находится минимальное время, т.е. наиболее раннее событие. В примере— это время t₁. Для первой заявки потока X₁ определяется путем случайного испытания время обслуживания устройством ввода T¹₁₄ и отмечается момент окончания обслуживания На рисунке показан ступенькой переход устройства 4 в состояние «занято». Одновременно определяется момент поступления следующей заявки потока .

Следующее минимальное время — это момент поступления заявки потока X₂-t₂. Для этой заявки находится время обслуживания на мониторе T¹₂₃ и отмечается время окончания обслуживания . Определяется момент поступления второй заявки потока . Снова выбирается минимальное время— это t_з. В этот момент заявка потока Х₂ начинает обрабатываться процессором. По результату случайного испытания определяется время ее обслуживания T¹₂₃ и отмечается момент окончания обслуживания. Следующее минимальное время t₄ — момент завершения обслуживания заявки потока X₁ устройством 4. С этого момента заявка может начать обрабатываться процессором, но он занят обслуживанием заявки потока Х₂. Тогда заявка потока X₁ переходит в состояние ожидания, становится в очередь.

В следующий минимальный момент времени t₅ освобождается процессор. С этого момента процессор начинает обрабатывать заявку потока X₁, а заявка потока X₂ переходит на обслуживание монитором, т. е. ответ на запрос пользователя передается из основной памяти в буферный накопитель монитора. Далее определяются соответствующие времена обслуживания и отмечаются моменты времени . В момент t₆ полностью завершается обработка первой заявки потока Х₂. По разности времен t₆ и t₂ вычисляется время реакции по этой заявке:

Следующий минимальный момент времени t₇ — это поступление второй заявки потока Х₂. Определяется время поступления очередной заявки этого потока . Затем вычисляется время обслуживания второй заявки на мониторе Т²₂₃ и отмечается момент после чего заявка становится в очередь, так как процессор занят. Эта заявка поступает на обслуживание в процессор только после его освобождения в момент времени t₉. В этот же момент заявка потока Х₁ начинает обслуживаться принтер. Определяются времена обслуживания Т²₂₁ и T¹₁₂ по результатам случайных испытаний и отмечаются моменты окончания обслуживания . В момент времени t₁₀ завершается полное обслуживание первой заявки потока X₁. Разность между этим моментом и моментом времени t₁дает первое значение времени реакции по потоку .

Вторая заявка потока Х₂ в момент t₁₁ поступает с процессора на- монитор и обслуживается им в течение времени Т²₂₃, которое завершается в момент Снова определяется очередное минимальное время. Это время — t₁₂ когда в систему поступает вторая заявка из потока Х₁. Тогда вычисляется время поступления третьей заявки потока Вторая заявка обслуживается устройством ввода в течение времени Т²₁₄ (момент завершения — ) и процессором — T²₁₁ (момент завершения — ). В момент t₁₃состояние системы не изменяется, но вычисляется второе значение времени реакции по потоку Х₂:

В момент времени t₁₅ систему поступает третья заявка потока Х₂. Определяется момент поступления четвертой заявки потока (предполагается, что пользователь может посылать запросы, не дожидаясь ответов на предыдущие запросы). Третья заявка обслуживается монитором в течение времени T³₂₃, но с момента окончания обслуживания ( ) переходит в состояние ожидания, так как занят процессор.

Следующее минимальное время t₁₇, — это время поступления четвертой заявки потока Х₂. После ее обслуживания монитором (момент завершения ) она также переходит в ожидание, т. е. образуется очередь из двух заявок. После освобождения процессора в момент t₁₉ начнется обслуживание процессором третьей заявки потока X₂, а затем с момента — монитором. По завершении этого обслуживания () можно будет вычислить третье значение времени реакции по потоку X₂:

С момента времени t₁₉ принтер начнет обслуживание второй заявки потока X₁ и завершит его к моменту , после чего определяется второе значение времени реакции по потоку X₁:

Указанные процедуры выполняются до истечения времени моделирования. В результате получается некоторое количество (выборка) случайных значений времен реакции {u₁} и {u₂} по первому и второму потокам. По этим значениям могут быть определены эмпирические функции распределения и вычислены количественные вероятностные характеристики времен реакции. В процессе моделирования можно суммировать продолжительности занятости каждого устройства обслуживанием всех потоков. Например, на рис. 1 занятость процессора 1 выделена заштрихованными ступеньками. Если результаты суммирования разделить на время моделирования, то получатся коэффициенты загрузки устройств.

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

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

2. Обобщенные алгоритмы имитационного моделирования

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

Рис. 3. Алгоритм моделирования по принципу особых состояний

Процесс имитации функционирования системы развивался во времени с использованием управляющих последовательностей, определяемых по функциям распределения вероятностей исходных данных путем проведения случайных испытаний. В качестве управляющих последовательностей использовались в примере последовательности значений периодов следования заявок по каждому i -му потоку { } и длительностей обслуживания заявок i -го потока k-м устройством {T _ik }. Моменты наступления будущих событий определялись по простым рекуррентным соотношениям. Эта особенность дает возможность построить простой циклический алгоритм моделирования, который сводится к следующим действиям:

1) определяется событие с минимальным временем — наиболее раннее событие;

2) модельному времени присваивается значение времени наступления наиболее раннего события;

3) определяется тип события;

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

5) перечисленные действия повторяются до истечения времени моделирования.

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

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

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

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

Рис. 3. Алгоритм моделирования по принципу временных приращений

Алгоритм моделирования по принципу . Укрупненная схема моделирующего алгоритма, который реализует принцип постоянного приращения модельного времени (принцип ), представлена на рис. 3. Как и в предыдущем алгоритме, вначале инициализируется программа, в частности, вводятся значения z _i(t₀), i= 1,...,n, которые характеризуют состояние системы в n -мерном фазовом пространстве состояний в начальный момент времени t₀. Модельное время устанавливается t = t₀ = 0.

Основные операции, с помощью которых имитируется функционирование системы, выполняются в цикле. Функционирование системы отслеживается по последовательной смене состояний Z_i (t). Для этого модельному времени дается некоторое приращение . Затем по вектору текущих состояний определяются новые состояния z_i (t + ), которые становятся текущими. Для определения новых состояний по текущим в формализованном описании системы должны существовать необходимые математические зависимости. Такой цикл продолжается до тех пор, пока текущее модельное время меньше заданного времени моделирования Т, m.

По ходу имитации измеряются, фиксируются и обрабатываются требуемые выходные характеристики. При t завершается обработка измерений и выводятся результаты моделирования.

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

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

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

1. Общее определение имитационного моделирования.

2. Имитация фукнционирования ВС.

3. Алгоритм моделирование по принципу особых состояний.

4. Алгоритм моделирования по принципу временных приращений.

Литература

55.

56.

57.

58.

59.

Лекция 13. МЕТОДЫ ИССЛЕДОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ
СИСТЕМ (2 часа)

План

1. Методы определения характеристик вычислительных систем

2. Метод повторных экспериментов

3. Методы генерации случайных величин и последовательностей

1. Методы определения характеристик
вычислительных систем

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

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

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

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

(1)

где — коэффициент загрузки k-го устройства; — среднее время обслуживания одной заявки k-м устройством; N_ok— количество обслуженных устройством заявок за время моделирования Т_т

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

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

(2)

где m_n-1 — математическое ожидание, вычисленное по предыдущим п — 1 измерениям.

Дисперсия для n -го измерения:

(3)

где — дисперсия, вычисленная по предыдущим п — 1 измерениям. Вначале дисперсия принимается равной нулю.

При большом количестве измерений эти оценки являются состоятельными и несмещенными.

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

(4)

Рис. 1. Временная диаграмма изменения длины очереди

где i — номер очередного изменения состояния очереди (занесения заявки в очередь или исключения из очереди) (рис. 1); N— количество изменений состояния очереди; _i; — интервал времени от (i- 1)-го до 1-го изменения состояния; l_i — число заявок в очереди в интервале

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

(5)

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

Формулы (4) и (5) приводят к виду, удобному для вы­числения путем наращивания итогов.

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

Перед началом моделирования задаются предположительные границы изменения интересующей выходной характеристики y, т. е. нижний y_H и верхний y_B пределы, и указывается число ин­тервалов гистограммы N_g. По этим данным вычисляется интервал

Затем в процессе моделирования по мере появления измерений характеристики у, определяется число попаданий этой случайной величины в i -й интервал гистограммы R _i; и подсчитывается общее число измерений N. По полученным данным вычисляется относи­тельная частота по каждому интервалу:

Этих данных достаточно для построения гистограммы относи­тельных частот: на оси абсцисс откладываются пределы изменения анализируемой характеристики у; весь диапазон изменения под­разделяется на заданное число интервалов; над каждым t-м интервалом проводится отрезок, параллельный оси абсцисс, на расстоянии, равном G _i от оси абсцисс (рис. 2).

Рис. 2. Гистограмма относитель­ных частот

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

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

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

(6)

где p_i — определенная из выбранного теоретического распределе­ния вероятность попадания случайной величины в i -й интервал.

Из теоремы Пирсона следует, что для любой функции распре­деления F(у) случайной величины у при N распределение величины имеет вид

(7)

где z — значение случайной величины k = Ng —(r +1) — число степеней свободы распределения хи-квадрат; r — количе­ство параметров теоретического закона распределения; Г (k/2) — гамма-функция.

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

2. Метод повторных экспериментов

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

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

(8)

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

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

(9)

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

(10)

которая соответствует любому сочетанию моментов времени t_r на интервале (О, Т) при произвольном N_r, в том числе при . Исходя из этих предпосылок, при исследовании стоха­стических систем необходимо получать для каждой выходной характеристики совокупности N_i реализации, причем по каждой реализации следует измерять значения no N_r сечениям (отсчетам), как это показано на рис. 3. Таким способом могут быть получены вероятностные оценки выходных характеристик, если они являются нестационарными или стационарными неэргодическими процессами.

Рис. 7. Реализации нестационарного случайного процесса

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

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

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

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

Период моделирования Т_m по каждому эксперименту разделяется на N_r сечений. Интервал времени моделирования между двумя соседними сечениями будем называть прогоном. В каждом эксперименте для фиксированных моментов времени определяются численные значения выходных характеристик.

По каждому i-му сечению для всех выходных характеристик может определяться эмпирическая многомерная функция или плотность распределения, оцениваться математическое ожидание m_y(t_r), корреляционная функция или дисперсия D_y (t_r) по всей совокупности N_i реализации.

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

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

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