Моделирование систем массового обслуживания (работа 1)

Методика построения программной модели

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

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


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

В БП (буферной памяти) сообщения записываются «в навал» и выбираются по одному в обслуживающий аппарат по принципу FIFO/LIFO. Длительность обработки одного сообщения в ОА (обслуживающий аппарат) в общем случае может быть случайной, но закон обработки всегда должен быть задан. Т.к. быстродействие ОА ограничено, то на входе системы в БП возможно сложение данных, ожидающих обработку.

ПБССт - программный блок сбора статистики.

Блок синхронизации необходим, чтобы система заработала.

Моделирование потока сообщений.

Поток сообщений обычно моделируется моментами появления очередного сообщения в потоке. Текущий момент времени появления очередного сообщения:

где T>i>> >– интервал времени между появлением i-го и (i-1)-го сообщения.

Процедура.

обращение к процедуре выражения случайного числа Rnd

Вид распределения

Выражение

равномерное на [a,b]

нормальное

экспоненциальное

Эрланга

Моделирование работы Обслуживающего Аппарата.

Программа – имитатор работы ОА представляет собой комплекс, вырабатывающий случайные отрезки времени, соответствующие длительностям обслуживания требований. Например, если требования от источника обрабатываются в ОА по нормальному закону с параметрами Mx и x, то длительность обработки i-ого требования:

Схема алгоритма имитатора.

R>i> – случайное число с равномерным законом распределения

Т>ОБР> – время обработки очередного сообщения

T – время освобождения ОА

XM – Мат ожидание для заданного закона обратки

DX – СКО для заданного закона обратоки

Моделирование работы абонента

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

Моделирование работы буферной памяти

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

запись


нет

чтение

переполнение

(в блок стат)

нет (в БС)


да

нет

нет

да

да

да

да

нет

нет


P

массив сообщений

LM

объем буферной памяти

WYB

признак обращения к буф. памяти

= 1 – режим выборки сообщений

= 0 – режим записи

NPOS

номер последнего сообщения, поступившего в память

NP

число сообщений в памяти

NPER

номер первого сообщения в памяти

POLN

признак переполнения памяти

= 1 – нет свободных ячеек

PUST

признак отсутствия сообщений

= 1 – в памяти нет сообщений

NPOS

= NPOS + 1, если NPOS < LM

= NPOS – LM + 1, иначе

NPER

= NPER – 1, если NPER < 1

= NPER – LM + 1, иначе

X

ячейка для сообщения

Разработка программы сбора статистики

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

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

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

Коэффициент загрузки ОА определяется как отношение времени работы ОА к общему времени моделирования.

Разработка управляющей программы имитационной модели

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

    принцип t

    событийный принцип

Принцип t.

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

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

Событийный принцип

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

t>11>, t>12> – моменты появления сообщений на выходе генератора (источника информации)

b>1> – интервал времени обслуживания первого сообщения

t>3 >>n> – момент сбора статистики

t>41> – момент окончания моделирования

Методика реализации событийной модели

    Для всех активных блоков (блоков, порождающих события) заводя свой элемент в одномерном массиве – списке будущих событий.

    В качестве подготовительной операции в список будущих событий SBS заносят время ближайшего события от любого активного блока. Активизируя программу-имитатор, ИИ вырабатывает псевдослучайную величину a>0>>, >определяющую момент появления первого сообщения t>11>. Эту величину заносят в список будущих событий.

Активизируя программу-имитатор, ОА вырабатывает псевдослучайную величину b>0>, определяющую момент времени t>21>, которую также заносят в SBS.

Момент времени t>31> (1ый сбор статистики) определяется равным стандартному шагу сбора t>СТАТ>, и заносится в SBS

В SBS заносится t>41> – время окончания моделирования.

Подготовительная часть на этом закончена и начинается протяжка модельного времени.

    В SBS определяется минимально числовое значение и его номер.

    Реализуется событие, порождаемое блоком с соответствующим номером, т.е. модельное время = t>11>. Далее реализуется событие с номером 1, связанное с появлением нового сообщения в ИИ. Реализация этого события заключается в том, что само сообщение записывается в память, а с помощью имитатора ИИ, вырабатывается момент появления следующего события t>12>. Это время помещается в соответствующую ячейку SBS место t>11>.

Затем вновь организуется поиск минимального элемента в SBS. Для данного примера реализуется событие 3, после чего выражение момента времени t>32> – новое время сбора статистики. Так до тех пор, пока минимально время не станет равным t>41>.

Философские аспекты моделирования

Объектом называется всё то, на что направлена человеческая деятельность.

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

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

Современные научные гипотезы создаются как правило по аналогии проверенным на практике положениям. Таким образом, аналогия связывает гипотезу с экспериментом.

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

Модель – объект - заместитель объекта оригинала, обеспечивающий изучение некоторых свойств оригинала.

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

Классификация видов моделирования

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

Детерминированное Стохастическое

Статическое Динамическое

Дискретное Непрерывное

Дискретно-непрерывное

Математическое Физическое

Аналитическое Имитационное В реальном масштабе времени

Комбинированное В нереальном масштабе времени

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

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

    Статическое служит для описания сложной системы в конкретный момент времени.

    Динамическое отражает поведение системы во времени.

    Дискретное моделирование используется для описания процессов, происходящих в дискретные моменты времени.

    Непрерывное используется для описание непрерывных во времени процессов.

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

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

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

Аналитические модели могут быть исследованы тремя способами:

    Аналитическим. Получение в общем виде зависимости выходных характеристик от исходных.

    Численным. Нельзя решить сложные уравнения в общем виде. Результаты получают для конкретных начальных данных.

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

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

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

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

Технические средства математического моделирования

Цифровая техника

Цифровая техника является дискретной. Основная проблема – быстродействие (не догнать реальное время) слишком сложен механизм.

Аналоговая техника.

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

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

В общем случае под АВМ понимаем совокупность электрических элементов, организованных с систему, позволяющих изоморфно моделировать динамику изучаемого объекта. Функциональные блоки АВМ должны реализовывать весь комплекс арифметико-логических операций.

АВМ делятся по мощности (степень дифференциальных уравнений):

    малые ( n  10 )

    средние ( 10  n  20 )

    большие ( n  20 )

П. У.




Система

масштабирования

Система

управления

Система

коммутации



Операционные блоки

Линейные

Нелинейные


Система управления

(контроля)

Блок операционных

усилителей


Гибридные ВМ

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

Подклассы гибридных ВМ:

    АВМ с цифровыми методами численного анализа

    АВМ, программируемые с помощью ЦВМ

    АВМ с цифровым управлением и логикой

    А

    ЦВМ

    ВМ с цифровыми элементами (цифровые вольтметры, память)

    ЦВМ с аналоговыми арифметическими устройствами

    ЦВМ, допускающие программирование аналогового типа.

ЦАП АЦП


В

схема

согласования

АВМ накладывают и складывают сигналы.

А

АВМ

ВМ  система сопряжения АВМ –ЦВМ.

ЦВМ  электрическая система согласования

Сравнительная характеристика АВМ и ЦВМ

Показатель

АВМ

ЦВМ

Тип информации

Непрерывный

Дискретный

Изменение значений

Величиной напряжения

Числовым значением

Базовые операции

Арифметические операции и интегрирование

Арифметические операции

Принцип вычисления

Высокопараллельный

Последовательно-параллельный

Режим реального времени

Без ограничений

Ограничен

Динамическое изменение решаемой задачи

Посредством системы коммутации

В диалоговом режиме

Требования к пользователю

Профессиональные знания, методика моделирования

Знание основ ПО ЭВМ

Уровень формализации задачи

Ограничен моделью решаемой задачи

Высокий

Способность к решению логических задач

Ограничена

Высокая

Точность

Ограничена (10-4)

Ограничена разрядностью (10-40)

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

1 … 10-4

Зависит от разрядности

10-40 … 1040

Класс решаемых задач

Алгебраические и дифф. уравнения.

Любые

Специальные функции

Ограниченный набор

Неограниченный набор

Уровень миниатюризации

Ограничен

Высокий

Сфера применения

Ограничена

Практически любая

Пользовательский интерфейс

Низкий уровень

Высочайший уровень

Основные понятия теории моделирования

Пусть задана сложная дискретная система S.

S

V

Y

X


As

Множество входных параметров

Множество внутренних параметров

Внешнее воздействие

Множество выходных параметров

Закон функционирования некоторой сложной системы в общем виде:

A>s> – алгоритм функционирования – метод преобразования экзогенных характеристик в эндогенные (независимые в зависимые).

Система также имеет множество состояний в определенные моменты времени:

Начальное состояние:

Под математической моделью реальной системы понимается конечной множество переменных x(t), h(t), v(t) вместе с математическими связями между ними и характеристиками выходных параметров системы y(t).

Типовые математические схемы.

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

процесс функционирования

системы

типовая математическая

схема

обозначение

Непрерывно-детерминированный подход

стандартные ДУ

D-схема

Дискретно-детерминированный подход

конечные автоматы

F-схема

Дискретно-стохастический подход

вероятностные автоматы

P-схема

Непрерывно-стохастический подход

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

Q-схема

Обобщенные (универсальный)

агрегативная система

A-схема

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

Формализация и алгоритмизация процесса функционирования системы

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

Основные требования, предъявляемые к модели:

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

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

    Компьютерная реализация модели должна соответствовать имеющимся технически ресурсам.

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

Основные этапы моделирования больших систем

    Построение концептуальной (описательной) модели некоторой системы и её формализация

    Алгоритмизация модели и её программная реализация

    Получение и интерпретация результатов моделирования

На первом этапе формулируется модель и строится её формальная схема. Основное назначение данного этапа – переход от содержательного описания объекта к его математической модели. Это наиболее ответственный и наименее формализованный этап. Исходный материал данного этапа – содержательное описание объекта.

    Проведение границ между системой и внешней средой.

    Исследование моделируемого объекта с точки зрения выделения основных составляющих процесса функционирования системы (по отношению к целям моделирования)

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

    Основные элементы модели группируются в блоки. Блоки I-ой группы представляют собой имитатор воздействия внешней среды. Блоки II-ой групп являются собственно моделью функционирования. Блоки III-ей группы носят вспомогательный характер для реализации I-ой и II-ой групп и для фиксации результатов моделирования.

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

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

    Разработка схемы моделирующего алгоритма.

    Разработка схемы программы.

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

    Этап программирования модели (программирование и отладка).

    Проверка достоверности модели на различных работающих тестовых примерах.

    Составление технической документации (логические схемы, схемы программ, спецификации)

На третьем этапе (получение и интерпретация результатов) компьютер используется для проведения рабочих расчетов по готовой программе модели. Результат этих расчетов позволяет проанализировать и сделать выводы о характеристиках процесса функционирования моделируемой системы.

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

    Проведение рабочих расчетов (контрольная калибровка модели)

    Статистическая обработка результатов расчетов.

    Интерпретация результатов моделирования, подведение итогов

    Составление технической документации.

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

Три основных класса ошибок:

    Ошибка формализации – недостаточно подробное описание модели

    Ошибка решения – некорректный или слишком упрощенный метод построения модели

    Ошибка задания параметров.

Проверка адекватности модели.

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

Считается, что модель адекватна с системой, если вероятность того, что отклонение параметров y не превышает некоторой предельной величины  больше допустимой вероятности.

На практике использование данного критерия невозможно, т.к.:

    Для проектирования или моделирования системы отсутствует информация о выходной характеристики y.

    Как правило, система оценивается не по одной, а по множеству характеристик

    Характеристики могут быть случайными величинами или функциями.

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

Выдвигаются следующие виды проверки:

    Проверка моделируемых элементов

    Проверка внешних воздействий

    Проверка концептуальной модели

    Проверка формализованной математической модели

    Проверка программной модели

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

Если модель неадекватна объекту, то выдвигаются следующие типы изменения:

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

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

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

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

Схема взаимодействия технических этапов моделирования


Вычислительные системы как объект моделирования

Уровни проектирования:

    Системное проектирование

Цель – определение производительности. Вычислительная система рассматривается целиком. Отдельные её элементы – ЦП, память и т.д.

ВС := <ЦП, ОП, …><ОС>

    Функционально-логический уровень проектирования

      Подуровень регистровых передач.

Исследование команды.

      Логическое проектирование.

Исследование на уровне логических элементов.

    Схемотехнический уровень.

Вопросы конкретной реализации (например, как искажается сигнал).

    Конструкторский уровень.

Оптимизация размещений (например, теплообмен).

Проектирование происходит сверху вниз.

Моделирование на системном уровне.

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

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

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

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

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

рабочая нагрузка




производи-

тельность



Индекс производительности – описатель, который используется для представления производительности системы. Различают количественные и качественные индексы производительности.

Качественные:

    легкость использования системы

    мощность системы команд

Количественные:

    пропускная способность – объем информации, обрабатываемый в единицу времени.

    время ответа (реакции) – время между предъявлением системе входных данных и появлением соответствующей выходной информации.

    коэффициент использования оборудования – отношение времени использования указанной части оборудования в течение заданного интервала времени к длительности этого интервала.

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

Основные задачи:

    Определение принципов организации ВС.

    Выбор архитектуры, уточнение функций ВС и их разделение на подфункции, реализация аппаратным и программным путем.

    Разработка структурной схемы – определение состава устройств и способов их взаимодействий.

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

Непрерывно-стохастические модели (Q-схемы).

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

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

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

Поток событий называется однородным, если он характеризуется только моментами поступления этих событий (вызывающими моментами) и задается следующей последовательностью:

,

где t>n> – момент поступления n-ого события.

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

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

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

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

Для ординарного потока среднее число сообщений за интервал времени t равно P>1 >(t, t), тогда

- интенсивность ординарного потока.

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

В любом элементарном акте обслуживания можно выделить 2 основные составляющие:

    собственно, обслуживание

    ожидание обслуживания заявки



U>i>

Y>i>




Н>i>

K>i>

W>i>

П>i>


K – канал, Н – накопитель, П – прибор обслуживания

В i-ом приборе обслуживания имеем:

    w>i> – поток заявок т.е. интервалы времени между моментами появления заявок (вызывающие моменты) на входе канала Ki.

    u>i> – поток обслуживания – интервалы времени между началом и окончанием обслуживания заявок.

Заявки, обслуженные каналом, и заявки, покинувшие i-ый прибор не обслуженными, образуют выходной поток Yi, т.е. интервалы времени между моментами выхода заявок.

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

где Z – заявка, L – емкость накопителя

В практике моделирование элементарные Q-схемы обычно объединяются. При этом, если каналы различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание, а если последовательно – то многофазное. Следовательно, для задания Q-схемы необходимо использовать некоторый оператор - R-оператор сопряжения, отражающий взаимосвязь элементов структуры между собой.

Различают разомкнутые и замкнутые Q-схемы. В разомкнутых схемах выходной поток не может попасть на вход, а в замкнутых схемах количество заявок постоянно.

Собственными внутренними параметрами Q-схемы будут являться:

    Количество фаз

    Количество каналов в каждой фазе

    Количество накопителей в каждой фазе

    Емкость i-ого накопителя

В зависимости от емкости накопителя в теории массового обслуживания принято:

    Емкость 0 – система с потерями.

    Емкость  - система с ожиданием

    Емкость конечна – система смешанного типа

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

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

Q = (W, U, R, H, Z, A)

    W - подмножеством входных потоков

    U - подмножеством потоков обслуживания

    H - подмножеством собственных параметров

    R - оператором сопряжения элементов структуры

    Z - множеством состояний элементов системы

    A - оператором алгоритмов обслуживания заявок

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

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

Случайный процесс, протекающий в некоторой системе называется Марковским случайным процессом, если он обладает следующим свойством: для каждого момента времени t>0> вероятность любого состояния системы в будущем (при t > t>0>) зависит только от состояния системы в настоящем и не зависит от того, когда и каким образом система пришла в это состояние.

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

,

где p(t) – вероятность попадания в какое-либо состояние

 - множество определенных коэффициентов

Для стационарного потока:

- базисная модель

- интерфейсная модель

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

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

Методика вывода уравнений Колмогорова

-интенсивность перехода

1. Найдем вероятность того, что в момент времени t система

находится в состоянии S1. Придадим t малое приращение t и

определим, что система в момент времени t+t находится в состоянии S1.

2. Найдем вероятность того, что система находится в состоянии S2:

    Найдем вероятность того, что система находится в состоянии S3:

    Найдем вероятность того, что система находится в состоянии S4:

В результате получаем систему уравнений Колмогорова:

Интегрирование данной системы даст искомые вероятности состояний, как функций времени. Начальные условия берутся в зависимости от того, какого было начальное состояние системы. Если при t=0 система находится в состоянии S1, то начальные условия будут p>1>=1, p>2>= p>3>= p>4>=0. Кроме этого, к системе добавляются условия нормировки:

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

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

    Если стрелка направлена «из» состояния, соответствующий член имеет знак “-“, если «в» состояние, то знак “+”.

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

Пример.

Рассмотрим многоканальную СМО с отказами. Состояние системы характеризуется по числу занятых каналов, т.е. по числу заявок.

S0 – все каналы свободны

S1 – занят один канал, остальные свободны

Sk – занято k каналов, остальные свободны

Sn – заняты все n каналов.




2

3

n

k

(k+1)


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

Предельные вероятности состояний p>0>> >и p>n> характеризую установившийся режим работы системы массового обслуживания при t .

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

Зная все вероятности состояний p>0>> >, … , p>n>> , >можно найти характеристики СМО:

    вероятность отказа – вероятность того, что все n каналов заняты

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

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

Полученные соотношения могут рассматриваться как базисная модель оценки характеристик производительности системы. Входящий в эту модель параметр = 1 / t>ОБРАБОТКИ>, является усредненной характеристикой пользователя. Параметр является функцией технических характеристик компьютера и решаемых задач.

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

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

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

Идея метода: вместо того, чтобы описывать случайное явление с помощью аналитической зависимости производится «розыгрыш», т.е. происходит моделирование случайного явления с помощью некоторой процедуры, дающей случайный результат. Произведя такой розыгрыш n раз, получаем статистический материал, т.е. множество реализаций случайного явления, которое потом можно обработать обычными методами математической статистики. Метод Монте-Карло предложил Фон-Нейман в 1948 году, как метод численного решения некоторых математических задач.

Суть метода:

        Вводим в некотором единичном квадрате любую поверхность S.

        Любым получаем 2 числа x>i>, y>i>, подчиняющиеся равномерному закону распределения случайной величины на интервале [0, 1].

        Полагаем, что одно число определяет координату x, второе – координату y

        Анализируем принадлежность точки (x, y) фигуре. Если принадлежит, то увеличиваем значение счетчика на 1.

        Повторяем n раз процедуру генерации 2х случайных чисел с заданным законом распределения и проверку принадлежности точки поверхности S.

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

Фон-Нейман доказал, что погрешность .

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

К недостаткам относится большой объем требуемых вычислений, равный количеству обращений к модели. Поэтому вопрос выбора величины n имеет важнейшее значение. Уменьшая n – повышаем экономичность расчетов, но одновременно ухудшаем их точность.

Способы получения последовательностей случайных чисел

На практике используются 3 основных способа генерации случайных чисел:

    аппаратный (физический)

    табличный (файловый)

    алгоритмический (программный)

Аппаратный способ.

Случайные числа вырабатываются специальной электронной приставкой (генератором случайных чисел). Реализация этого способа не требует дополнительных вычислительных операций по выбору случайных чисел. Необходимо только оперативное обращение к ВУ.

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

Простейшие алгоритмы генерации последовательности псевдослучайных чисел

Одним из первых способов получения является выделение значения дробной части у многочлена первой степени:

Если n пробегает значения натурального ряда числе, то поведение y>n> выглядит весьма хаотично.

К. Якоби доказал, что при рациональном коэффициенте a множество y конечно, а при иррациональном – бесконечно и всюду плотно в интервале [0, 1].

Критерий равномерности распределения любой функции: свойство эргамичности – среднее по реализациям псевдослучайное число равно среднему по всему их множеству с вероятностью 1.

    1946 год, Фон Нейман.

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

    Лемер.

. Для подборов коэффициентов k, c, m были потрачены десятки лет. Подбор почти иррациональных чисел ничего не дает.

    Разумнее ввести вычисления с целыми числами.

при c = 0 и m = 2n наибольший период достигается при k=3+8i или k=5+8i и при нечетном начальном числе.

Для имитации равномерного распределения на [a, b] используется обратное преобразование функции плотности вероятности.

где R – равномерно распределенное псевдослучайное число на [0, 1].

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

Метод основан на том, что случайная величина x принимает значения, равные корню уравнения

, имеет плотность распределения f(x). R – случайная величина, равномерно распределенная на [0, 1].

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

Распределение Пуассона относится к числу дискретных (переменная может принимать лишь целочисленные значения, включая 0, с математическим ожиданием и дисперсией  > 0). Для генерации Пуассоновских переменных можно использовать метод точек, в основе которого лежит генерируемое случайное значение R>i> , равномерно распределенное на [0, 1], до тех пор, пока не станет справедливым

При получении случайной величины, функция распределения которой не позволяет найти решение уравнения

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

Воспользуемся этим методом, чтобы сгенерировать случайную величину с законом распределения Эрланга. Распределение Эрланга характеризуется параметрами  и k.

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

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

Случайная величина X имеющая нормальное распределение с математическим ожиданием M>X> и среднеквадратичным отклонением >X> может быть получена по следующей формуле:

Для сокращения вычислений на практике принимаю N=12, что дает вполне относительно хорошее приближение к нормальному распределению.

Немарковские случайные процессы, сводящиеся к марковским

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

    Метод разложения случайного процесса на фазы (метод псевдосостояний)

    Метод вложенных цепей Маркова

Метод псевдосостояний

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

Условие статистической эквивалентности реального состояния и соответствующих ему фиктивных состояний в каждом конкретном случае выбирается по-разному. В качестве одного из критериев эквивалентности можно принять следующее условие:

, где >i>> экв>() – эквивалентная интенсивность перехода в i-той группе переходов, заменяемой реальный переход обладающей интенсивностью >i>().

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

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

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

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

Пример.

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

Система S может принимать два состояния:

S0 – устройство исправно

S

1 – устройство отказало и восстанавливается


S

S>0>

0  S1 – Пуассоновский поток

S

S>1>

1  S0 – поток Эрланга

Представим случайное время восстановления в виде суммы 3х интервалов, распределенных по показательному закону с интенсивностью :

S1 заменяем эквивалентной цепочкой из трех псевдосостояний.

S>0>

S>11>

S>12>

S>13>

Последние 2 уравнения являются условием нормировки и условием эквивалентности замены состояния S1 псевдосостояниями.

Метод вложенных цепей Маркова.

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

Частным случаем вложенных цепей Маркова, являются полумарковские случайные процессы. Случайный процесс с конечным или счетным множеством состояний называется полумарковским, если заданны вероятности перехода системы из одного состояния в другое и распределение времени пребывания процесса в каждом состоянии (в виде функции распределения F(t) или в виде плотности распределения f(t))

Классификация систем массового обслуживания

В общем случае СМО классифицируется по следующим признакам:

    закону распределения входного потока

    числу обслуживающих приборов

    закону распределения времени обслуживания в обслуживающих приборах

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

    дисциплине обслуживания

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

A | B | C | D | E

A

Закон распределения интервалов времени между поступлением заявок.

M – экспоненциальный

E – Эрланга

H – гиперэкспоненциальный

Г – гамма-распределение

D – детерминированное распределение

G – произвольное распределение
B

Закон распределения времени обслуживания в приборах СМО.
C

Число обслуживающих приборов.

1 – для одноканальных систем

l – для многоканальных систем
D

Число мест в очереди. Если число мест не ограничено, то поле можно опустить.

r либо n – для конечного числа мест

E

Дисциплина обслуживания. По умолчанию LIFO – в этом случае поле может опускаться.
FIFO, LIFO, RANDOM

Примеры.

M | M | 1

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

E | H | l | r | LIFO

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

G | G | l

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

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

    Одноканальная СМО с ожиданием.

    один обслуживающий прибор с бесконечной очередью

    является наиболее распространенной при моделировании

    может заменить практически любой узел вычислительной системы или ЛВС

    Одноканальная СМО с потерями.

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

    если число заявок превышает число мест в очереди, то лишние заявки теряются

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

    Многоканальная СМО с ожиданием.

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

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

    Многоканальная СМО с потерями.

    несколько параллельно работающих обслуживающих приборов с общей очередью, число мест в которой ограничено

    часто используется, как и (2), при исследовании каналов связи

    Одноканальная СМО с групповым поступлением заявок

    один обслуживающий прибор с бесконечной очередью

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

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

    Одноканальная СМО с групповым обслуживанием заявок

    один обслуживающий прибор с бесконечной очередью

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

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

Наименование
Обозначение
Схема

Одноканальная с ожиданием

G | G | 1

Одноканальная с потерями

G | G | 1 | r

Многоканальная с ожиданием

G | G | l

Многоканальная с потерями

G | G | l | r

Одноканальная с групповым поступлением заявок

Gr | G | 1

r

Одноканальная с групповым обслуживанием заявок

G | Gr | 1

r

Вычислительные сети в целом могут быть представлены в виде СМО. Различают следующие типы сетей:

    Открытые

    Замкнутые

    Смешанные

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

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


S1, S2 – моделируют работу узлов коммутации

S3, S4 – моделируют работу серверов

S5, S6 – моделируют работу межузловых каналов

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

Замкнутой называется СМО с множеством узлов m без источника и стока, в которой циркулирует постоянное число заявок.

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

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

S01, S02 – группа абонентских терминалов

S7, S8 – каналы связи с абонентами

S1, S2 – узлы коммутации

S3, S4 – серверы

S5, S6 – каналы межузловой связи


Абоненты с терминалов посылают запросы, которые по каналам связи поступают на узлы коммутатора, а оттуда на обработку на свой или соседний сервер.

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

Схема представленная на рисунке находится на месте S01 и S02.

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

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

1