Тема 1 Общие сведения о случайных процессах Лекция 1 Методы статистического моделирования систем

Работа добавлена на сайт samzan.net:

Тема № 1 «Общие сведения о случайных процессах»

Лекция № 1 «Методы статистического моделирования систем»

Цель лекции.

а) учебная цель:

Целью является формирование у слушателей целостного представления о принципах применения элементов теории вероятностей при моделировании сетевых процессов – элемента систем массового обслуживания.

План лекции

1.  Метод статистического моделирования систем
2.  Случайные процессы и их классификация

1.  Метод статистического моделирования систем

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

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

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

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

Различают две области применения метода статистического моделирования:

- для изучения стохастических систем;

- для решения детерминированных задач.

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

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

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

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

Можно выделить следующие этапы моделирования случайных величин:

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

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

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

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

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

1.   Случайные процессы и их классификация

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

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

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

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

Непрерывный случайный процесс характеризуется тем, что t и х являются непрерывными величинами (рис. 1,а). Таким процессом, например, является шум на выходе радиоприемного устройства.

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

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

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

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

Рис. 1

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

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

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

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

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

1.  Что называется случайным процессом?
2.  Назовите области статистического моделирования?
3.  Назовите этапы моделирования случайных величин?

Тема № 1 «Общие сведения о случайных процессах»

Лекция № 2 «Способы описания случайных процессов»

Цель лекции.

а) учебная цель:

Целью является формирование у слушателей целостного представления о принципах применения элементов теории вероятностей при моделировании сетевых процессов – элемента систем массового обслуживания.

План лекции

1.  Способы описания случайных процессов
2.  Эргодическое свойство стационарных процессов

1.  Способы описания случайных процессов.

Существуют два способа представления случайных процессов.

1.  Случайный процесс представляется в виде совокупности или ансамбля всех своих возможных реализаций. То, какая конкретно реализация будет наблюдаться в испытании, является случайным событием. На рис. 1,а показан случайный процесс £(t), в ансамбль которого входят три реализации x1(t), x2(t), x3(t), наблюдаемые в испытании с определенными вероятностями.
2.  Случайный процесс  рассматривается как n-мерная случайная величина или n-мерный вектор (,,...,), каждая проекция которого является отсчетом случайного процесса в моменты времени t1, t2, ..., t  (рис. 1,б). Эти проекции вектора или отсчеты процесса будем называть сечениями случайного процесса:

   (2.1)

Сечения (1.1) являются случайными величинами, так как из-за случайного выбора реализации их конкретные значения до опыта неизвестны. На рис. 1. пунктиром показан возможный ход случайного процесса и соответственно случайные величины ,,..., на осях возможных значений

Рис. 1

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

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

В соответствии с этим n-мерая функция распределения случайного процесса  определится выражением

 (2.2)

Выражение (2.2) показывает, что в общем случае  зависит от 2n аргументов: от n наперед заданных возможных значений сечений () и от п моментов времени (t1, t2, ..., t), в которых эти сечения берутся. Вероятностный смысл выражения (2.2) поясняется рис. 3,а. для n=3: функция  определяет вероятность того, что реализация  случайного процесса  пройдет ниже заданных значений  в моменты времени t1, t2, ..., t.

Многомерная плотность вероятности по определению равна частной производной n-го порядка от  по возможным значениям

  (2.3)

Плотность вероятности n-го порядка в общем случае также зависит от тех же 2n аргументов. Вероятностный смысл выражения (2.3) поясняется рис. 2б, для n=3. Плотность вероятности умноженная на dz1,dz2,dz3, определяет вероятность прохождения реализации x(t) процесса  через dx1, dx2 , dx3, находящихся в сечениях t1, t2, t3 у значений x1, x2, x3.

Рис. 2

Произведение двумерной плотности вероятности на dx1dx2  характеризует вероятность того, что реализация x(t) случайного процесса в моменты времени t1, t2 пройдет через интервалы . Это означает, что двумерная плотность вероятности содержит сведения о связи между двумя сечениями случайного процесса, проведенными в моменты tj и t2.

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

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

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

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

    (2.4)

 (2. 5)

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

 (2.6)

не изменится, если все отсчеты времени сместить на одну и ту же величину:

 (2.7)

Если выбрать , то n-мерная плотность вероятности не будет зависеть от начала отсчета времени

 (2.8)

Таким образом, для стационарного процесса одномерная плотность вероятности вообще не зависит от времени, а двумерная плотность зависит не в отдельности от t1 и t2 , а от их разности

   (2.9)

 (2.10)

В свою очередь, из выражения (1.9) и (1.10) вытекает, что математическое ожидание и дисперсия стационарного процесса не за висят от времени, а корреляционная функция зависит от :

    (2.11)

    (2.12)

 (2.13)

Из (2.11), (2.12) и (2.13) следует, что математическое ожидание  постоянно и поэтому для стационарного процесса характеризует постоянную составляющую процесса; постоянность  характеризует то, что в каждой точке времени t средняя удельная мощность флюктуации (то есть мощность переменной составляющей) одна и та же; зависимость  от  означает, что для стационарного процесса не важно, в каких точках t1 и t2 берутся сечения, важна разность между ними .

Если условие (2.7) не выполняется, то случайный процесс называется нестационарным. Иногда о стационарности судят только по выполнению равенств (2.9), (2.10) и, соответственно, (2.11), (2.12), (2.13). Говорят, что, если выполняются равенства (2.9) и (2.10), то процесс является стационарным, не интересуясь при этом, выполняется условие (2.7) или нет. Такой подход дает более широкое толкование стационарности.

1.  Эргодическое свойство стационарных процессов

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

Пусть имеется одна длинная реализация x(t) случайного процесса (t). Эта реализация определена на интервале

Найдем среднее значение этой реализации путем ее усреднения во времени на достаточно большом интервале:

    (2.14)

где черта сверху означает усреднение по времени, среднее значение  является постоянной величиной, не зависящей от t.

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

   (2.15)

(2.16)

По своему физическому смыслу величины (2.14), (2.15), (2.16) являются числовыми характеристиками, совпадающими со средним значением, дисперсией и корреляционной функцией процесса (t). Однако они получены в результате усреднения во времени одной длинной реализации x(t) или функции от нее.

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

Таким образом, для эргодического стационарного процесса справедливы равенства:

,

             (2.17)

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

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

1.  Назовите способы представления случайных процессов?
2.  Какой случайный процесс называется стационарным?
3.  Какой случайный процесс называется нестационарным?
4.  Какой случайный процесс называется эргодическим?

Тема № 2 «Сетевое моделирование процессов»

Лекция № 3 «Назначение сетевого моделирования»

Цель лекции.

а) учебная цель:

Целью является формирование у слушателей целостного представления о принципах применения элементов теории вероятностей при моделировании сетевых процессов – элемента систем массового обслуживания.

План лекции

1.  Сетевое моделирование
2.  Классификация сетевых моделей
3.  Правила построение сетевых моделей

1.  Сетевое моделирование

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

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

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

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

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

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

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

Фиктивная операция - операция, на осуществление которой не требуется никаких затрат.

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

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

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

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

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

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

1.  Классификация сетевых моделей

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

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

Рис. 2.

1.  Правила построение сетевых моделей

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

К основным правилам, которыми следует руководствоваться при построении сетевых моделей, относятся следующие.

Для каждой вершины сети номер любой предшествующей ей вершины должен быть меньше ее собственного номера.

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

3. В сети не должно быть петель, контуров и кратных дуг.

4. В сети должны быть только одна исходная и одна завершающая вершины.

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

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

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

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

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

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

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

составление перечня операций;

составление матрицы смежности;

заполнение таблицы слоев;

нумерация вершин и построение сетевого графика.

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

1.  Что такое сетевая модель?
2.  Назовите основные правила построения сетевых моделей?
3.  Назовите основные этапы построения сетевых моделей?

Тема № 2 «Сетевое моделирование процессов»

Лекция № 4 «Анализ сетевых моделей»

Цель лекции.

а) учебная цель:

Целью является формирование у слушателей целостного представления о принципах применения элементов теории вероятностей при моделировании сетевых процессов – элемента систем массового обслуживания.

План лекции

1.  Оценивание продолжительности операций
2.  Параметры сетевой модели

1. Оценивание продолжительности операций

Основу анализа сетевой модели составляет расчет значений ее параметров.

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

Параметры, описывающие временные соотношения между событиями и операциями в сетевой модели, а также затраты времени на выполнение операций, называются временными параметрами. Исходными для определения всех временных параметров служит продолжительность (длительность) операции, обозначаемая t. для операции <i, j>. Продолжительность любой операции до окончания ее выполнения является величиной неизвестной, а следовательно, случайной. Наиболее полно случайная величина характеризуется законом распределения. Точные законы распределения продолжительностей операций, входящих в моделируемый комплекс, также обычно неизвестны. Поэтому на практике используют аппроксимирующие законы, которые стараются подобрать таким образом, чтобы один и тот же закон распределения, различаясь только числовыми характеристиками, с точностью, достаточной для целей моделирования, аппроксимировал законы распределения продолжительностей всех операций, входящих в комплекс.

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

В общем случае формула плотности бета-распределения случайной величины x, заданной на интервале (0,1], имеет следующий вид:

                      (1)

где  B(p, q) - бета-функция, определяемая выражением

                               (2)

где r(z) - гамма-функция, определяемая по формуле

                                             (3)

Известно, что для целых z функция r(z) определяется выражением

                                                   (4)

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

Величины p и q называются параметрами закона распределения (1). Если для аппроксимации реальных распределений продолжительностей операций используют бета-распределение, то поступают следующим образом Полагают, что продолжительность tj произвольной операции есть заданная на интервале

случайная величина, наиболее вероятное значение которой равно m, т. е.

Введя параметры а = p - 1, у = q - 1 и задавая линейное преобразование случайной величины x в случайную величину tj выражением

2. Параметры сетевой модели

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

В сетевом моделировании используются следующие виды путей: между вершинами, предшествующий вершине, последующий за вершиной, полный.

Путь между вершинами - путь, исходящий из одной рассматриваемой вершины и входящий в другую рассматриваемую вершину.

Путь между вершинами i и j обычно обозначают символом L.

Путь, предшествующий вершине - путь между исходной и рассматриваемой вершинами.

При обозначении исходной вершины символом I путь, предшествующий вершине i, обозначается символом IIr

Путь, последующий за вершиной - путь между рассматриваемой и завершающей вершинами.

При обозначении завершающей вершины символом C путь, последующий за вершиной i, обозначается символом L;C.

Полный путь - это путь между исходной и завершающей вершинами.

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

Критический путь - полный путь, имеющий в сетевой модели наибольшую продолжительность.

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

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

1. Продолжительность t(LtJ) пути Lx. между вершинами i и j

где rlk - операция </, k>; t(rlk) - продолжительность операции </, k>.

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

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

1.  Что такое сетевая модель?
2.  Что такое критический путь?
3.  Что такое подкритический путь?

Тема № 3 «Модели и свойства элементарных систем массового обслуживания»

Лекция № 5 «Понятие системы массового обслуживания»

Цель лекции.

а) учебная цель:

Целью является формирование у слушателей целостного представления о принципах применения элементов теории вероятностей при моделировании сетевых процессов – элемента систем массового обслуживания.

План лекции

1.  Понятие системы массового обслуживания
2.  Классификация систем массового обслуживания.
3.  Простейший поток событий и его свойства

1.  Понятие системы массового обслуживания.

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

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

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

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

1.  Вероятность явной или условной потери сообщения
2.  Среднее время задержки сообщения
3.  Средняя длинна очереди
4.  Вероятность потери поступившего вызова
5.  Интенсивность обслуженной нагрузки и др.

При исследовании СМО могут решаться:

1.  задачи анализа СМО - определение характеристик качества обслуживания в зависимости от параметров и свойств входящего потока сообщений, параметров и структуры системы обслуживания и дисциплины обслуживания;
2.  задачи параметрического синтеза - определение параметров системы обслуживания при ее заданной структуре в зависимости от параметров и свойств потока сообщений, дисциплины и качества обслуживания.
3.  задачи синтеза структуры системы с оптимизацией ее параметров таким образом, чтобы при заданных потоках, дисциплине и качестве обслуживания  стоимость   СМО   была  минимальной,  либо   были минимальными потери вызовов при заданных потоках, дисциплине и стоимости системы.

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

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

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

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

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

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

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

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

Как одноканальные СМО, так и многоканальные СМО делятся на СМО с отказами и СМО с очередью (ожиданием).

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

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

СМО с очередью различаются по принципу построения (дисциплине) очереди.

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

Случайный выбор заявки из очереди;

Выбор заявки из очереди в зависимости от её приоритета;

Выбор заявки в зависимости от порядка её поступления в очередь.

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

СМО с очередью делятся также на СМО с неограниченным ожиданием и СМО с ограниченным ожиданием.

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

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

Для систем массового обслуживания существенными, характеристиками, определяющими процессы в СМО, являются:

— тип входящего потока заявок (простейший, нестационарный пуассоновский и т. д.);

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

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

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

М — показательное распределение (Marcovian)

D — постоянная величина (Determinate)

G — произвольное распределение (General).

1.  Простейший поток событий и его свойства.

Поток событий называется простейшим потоком событий, если он обладает следующими свойствами стационарности, отсутствия последействия и ординарности:

1.  Поток событий называется стационарным, если вероятность появления одного или нескольких событий на участке времени длины T зависит только от длины T этого участка и не зависит от того, в каком месте оси времени этот участок располагается.
2.  Поток событий называется потоком с отсутствием последействия (без последействия), если события, составляющие поток, появляются в случайные моменты времени независимо друг от друга.
3.  Поток событий называется ординарным, если события, составляющие поток, происходят поодиночке, а не парами, тройками и т.д.

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

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

Замечание. Простейший поток событий обладает постоянной интенсивностью.

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

1.  Что называется потоком заявок?
2.  Как классифицируются системы массового обслуживании?
3.  Что называется принципом построения очереди?
4.  Какой поток событий называется простейшим?
5.  Какой поток событий называется стационарным?

Тема № 3 «Модели и свойства элементарных систем массового обслуживания»

Лекция № 6 «Структура системы массового обслуживания»

Цель лекции.

а) учебная цель:

Целью является формирование у слушателей целостного представления о принципах применения элементов теории вероятностей при моделировании сетевых процессов – элемента систем массового обслуживания.

План лекции.

1.  Структура и состав элементов системы массового обслуживания
2.  Источники и потоки заявок

1. Структура и состав элементов системы массового обслуживания.

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

Принципиальная структура СМО приведена на рис. 1.

Рис. 1. Схема системы массового обслуживания

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

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

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

2. Источники и потоки заявок.

Под источником понимается любой объект, генерирующий заявки на обслуживание. На объекте АСУ это может быть оператор автоматизированного рабочего места, программа, выполняемая в ЭВМ КСА, некоторый источник прерываний (таймер, схема или программа контроля и т. д.). Различают два вида источников:

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

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

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

Поток заявок, поступающих из источника на вход накопителя СМО, представляет последовательность событий (zn tn), где zn— заявка с номером п, п = 1, 2, 3,..., tn — момент ее возникновения. В теории СМО моменты t1 t2,... возникновения заявок zi, рассматриваются как случайные моменты времени, поэтому поток заявок определяется как случайный процесс, задаваемый функцией распределения интервалов времени между соседними заявками

Предполагается, что каждый интервал n представляет случайную величину, описываемую функцией распределения

где t — независимая переменная.

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

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

                                                                         (4.1)

где  — параметр, называемый интенсивностью потока заявок.

Для простейшего потока, описываемого распределением (4.1), интервалы  между соседними моментами заявок представляют независимые, случайные величины, подчиненные показательному закону   распределения с плотностью

                                                                         (4.2)

Математическое ожидание и дисперсия для распределения (4.2) равны:

Простейший поток, помимо стационарности, обладает следующими свойствами:

— отсутствием последействия, проявляющего в том, что длина интервала  до момента поступления следующей заявки не зависит от того, поступила или нет заявка в рассматриваемый начальный момент времени;

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

Рассмотрим указанные свойства более подробно. Образно говоря, отсутствие последствия показательно распределенного интервала времени состоит в том, что «возраст» интервала никак не влияет на величину оставшегося времени его «жизни». Пусть заявка поступила в момент t= 0. Распределение длины интервала до поступления следующей заявки описывается выражением

Пусть, далее, с момента t = 0 прошло То секунд и не поступило ни одной заявки.  Возникает вопрос: «Какова вероятность того, что следующая заявка поступит через t секунд, считая  от момента Т0?». На основании теоремы о произведении вероятностей здесь имеем

                        (4.3)

Назовем величину интервала  длительностью «жизни» интервала, величину То — «возрастом» интервала, а разность -То — остаточным временем жизни интервала. Соотношение (4.3) выражает тот факт, что для интервала, длительность жизни которого распределена по показательному закону, остаточное время жизни интервала -То  имеет то же самое распределение.

Рассматриваемое свойство показательного распределения объясняется замечательным свойством показательной функции exp(-t) состоящей в том, что любой ее «хвост» имеет с точностью до постоянного множителя форму самой функции, сдвинутой на соответствующую величину вправо по оси абсцисс. Действительно, пусть длина интервала имеет показательное распределение f(t)=exp(-t), а возраст равен Tо. Для того чтобы определить распределение остаточного времени интервала, нужно рассмотреть значения функции f(t) для t>T0.

Разделим все ординаты «хвоста» функции exp(-t), для t>T0 на площадь этого хвоста  равную, очевидно, вероятности Р[>T0]. Эта операция тождественна операции вычисления условного распределения путем деления вероятности совместного события (Т0< <t + To) на вероятность условия, т. о. события (>T0). Получающая в результате деления функция

представляет точную копию исходной функции f(t), но сдвинутую из нулевой точки вправо на Tо единиц времени, т. е. функцию

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

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

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

1.  Назовите основные элементы системы массового обслуживания?
2.  Назовите типы источников заявок в СМО?
3.  Какими свойствами обладает простейший поток заявок?

Тема № 3 «Модели и свойства элементарных систем массового обслуживания»

Лекция № 7 «Процессы в системах массового обслуживания»

Цель лекции.

а) учебная цель:

Целью является формирование у слушателей целостного представления о принципах применения элементов теории вероятностей при моделировании сетевых процессов – элемента систем массового обслуживания.

План лекции.

1.  Длительность обслуживания заявок
2.  Характеристики процессов в СМО

1.  Длительность обслуживания заявок.

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

Пусть плотность распределения длительности обслуживания описывается произвольным законом распределения fоб(t) с математическим ожиданием М [об] = об. Для исследования и описания процессов в СМО необходимо иметь функцию fоб(t) в аналитическом виде. С этой целью функция fоб(t), если она найдена экспериментально, аппроксимируется некоторым типовым законом распределения.

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

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

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

1.   Характеристики процессов в СМО.

СМО типа М | М | 1 представляет разомкнутую одноканальную систему массового обслуживания с «чистым» ожиданием,. т.е. с неограниченной длиной очереди. На вход системы поступает простейший поток заявок. Пусть его интенсивность равна,  заявок в секунду. Время обслуживания об распределено по показательному закону со средним значением .

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

— вероятностью р{п), п = 0, 1, 2, что в системе находится ровно п заявок;

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

— средними значениями времени ожидания , времени обслуживания , времени пребывания .

Представляет интерес среднее значение случайной величины

nо6 = п — nоч,

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

где - загрузка системы.

Таким образом, среднее число заявок, находящихся в СМО М|М|1 на обслуживании, численно равно загрузке .

Система М|G|1 представляет собой одноканальную СМО с пуассоновским входным потоком и произвольным (общим) распределением времени обслуживания. Считаются заданными следующие параметры системы:

— интенсивность  входного пуассоновского потока заявок:

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

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

Центральным вопросом исследования свойств СМО М | G \ 1 является определение среднего времени ожидания  по характеристикам . В основе решения задачи лежит анализ свойств случайной величины Y — оставшегося времени обслуживания заявки, уже находящейся на обслуживании, на момент прихода в систему новой заявки.

Пусть в канале СМО протекает процесс обслуживания заявок со средним временем обслуживания . В произвольный момент времени tn на вход СМО поступает заявка zn и застает канал СМО занятым обслуживанием некоторой заявки zi  i<n, поступившей ранее. Спрашивается, чему должно быть равно среднее время дообслуживания заявки zi? На первый взгляд кажется, что среднее время дообслуживания должно бить равно /2. Оказывается такой ответ неверен. Предположим, что время обслуживания распределено по показательному закону со средним значением . Благодаря свойству отсутствия последействия, время дообслуживания заявки zi, застигнутой на обслуживании заявкой zn, не зависит от того, сколько времени уже протекает обслуживание zi и распределено так же, как и полная длительность ее обслуживания. В этом случае среднее время дообслуживания заявки zi будет равно среднему времени ее обслуживания , а не 0,5 !

Объяснение полученного парадокса состоит в том, что вероятности встречи заявки zn с другими заявками в интервале их обслуживания в канале СМО неравнозначны. Ясно, что у нлямкн zn больше шансов застать на обслуживании в СМО м.чяику zi, имеющую «большую» длительность обслуживания.

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

Интервал времени обслуживания заявки zi застигаемой на обслуживании заявкой zn назовем «отобранным интервалом». Введем понятия длительность жизни Т, возраста То и остаточного времени жизни Y отобранного интервала (рис. 1).

Рис. 1

Отобранный интервал описывается выражением:

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

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

где  — время ожидания завершения обслуживания некоторой заявки zi уже находящейся на обслуживании в момент прихода заявки zn

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

Выполним операцию математического ожидания:

Диаграмма характеристик СМО М | G \ 1:

Рис. 2

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

1.  Какова длительность обслуживания заявок?
2.   Чем характеризуются системы массового обслуживания?
3.  Какими свойствами обладает простейший поток заявок?

Тема № 3 «Модели и свойства элементарных систем массового обслуживания»

Лекция № 8 «Характеристики дисциплин обслуживания заявок»

Цель лекции.

а) учебная цель:

Целью является формирование у слушателей целостного представления о принципах применения элементов теории вероятностей при моделировании сетевых процессов – элемента систем массового обслуживания.

План лекции.

1.  Модель системы обслуживания
2.  Характеристики процессов обслуживания
3.  Характеристики дисциплин обслуживания

1. Модель системы обслуживания.

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

Рис.1

Управление обработкой заявок производится следующим образом. При поступлении очередной заявки на вход системы программа—диспетчер инициирует прерывание в процессоре, в результате которого запускается программа приема и постановки заявки в соответствующую очередь Oi на исполнение заявки. Физически каждая очередь Оi состоит из совокупности ячеек оперативной памяти процессора, в которых размещаются данные (коды) поступающих заявок. Отбор заявок на обслуживание из очередей Oi производится программой-диспетчером в порядке поступления заявок.

Пусть на вход системы поступают М пуассоновских потоков заявок с интенсивностями  На входе системы из этих потоков формируется один суммарный поток с интенсивностью:

Свойства канала обслуживания (т. е. процессора и соответствующей обрабатывающей программы) описываются двумя наборами характеристик:

1) величиной среднего времени обслуживания заявки типа i

2) величиной второго начального момента времени обслуживания заявки i-го типа:

Таким образом, модель рассматриваемой системы обслуживания полностью описывается набором  параметров  для i = 1…M. Эти характеристики указаны в левой части; диаграммы рис. 2.

Рис. 2.

2. Характеристики процессов обслуживания.

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

При среднем времени обслуживания заявки i-ro типа, равном , и интенсивности потока заявок этого типа Хг загрузка процессора i-м типом заявок равна . Тогда общая загрузка процессора потоками заявок всех типов будет равна

Условие существования стационарного режима в рассматриваемой СМО состоит в выполнении неравенства R<1,0.

Получим выражение для среднего времени ожидания заявок в очереди. Допустим, что в произвольный момент времени в очереди уже находятся  l1,..., lМ  заявок типа 1, 2,.... М и поступила заявка zi типа i. Тогда время ожидания заявки zi складывается из следующих компонент:

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

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

Найдем выражение для М [0]. В системе М\G\1 среднее время дообслуживания заявки равно:

а среднее время ожидания вновь пришедшей заявкой завершения обслуживания равно:

Отсюда следует, что среднее время ожидания заявкой zi дообслуживания любой заявки должно быть равно взвешенной сумме средних времен дообслуживания:

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

где —средняя длина очереди заявок k-ro типа. Здесь, используя соотношение

получаем

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

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

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

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

Данное соотношение в теории CMO носит название закона сохранения суммарного времени ожидания (заявок в очереди).

3. Характеристики дисциплин обслуживания.  

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

Схема организации обработки заявок с относительными приоритетами приведена на рис. 3. Пусть на вход системы обработки поступает поток из Р типов заявок с интенснвностями , Заявкам типа zp присвоены приоритеты 1, 2,..., Р в порядке убывания, т. е. большему приоритету соответствует меньшее значение р. Заявка zp, поступившая в систему, становится в очередь Ор заявок типа zp. Таким образом, для каждого типа заявок существует своя очередь, где заявки размещаются в порядке поступления. После завершения процессором обслуживания очередной заявки управление передается программе-диспетчеру, которая выбирает первую заявку из очереди с наибольшим приоритетом. Выбранная заявка захватывает процессор на все время обслуживания.

Рис. 3.

Примерный вид зависимости времени обслуживания для дисциплины с относительными приоритетами (ДОП) приведен на рис. 4. Здесь же показано, что для дисциплины обслуживания без приоритетов (ДБП) время обслуживания одинаково для заявок всех типов.

Рис. 4.

Однако в соответствии с законом сохранения времени ожидания суммарное время ожидания для обоих дисциплин одинаково.

Диаграмма характеристик дисциплины обслуживания с относительными приоритетами представлена на рис. 5.

Рис. 5.

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

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

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

Эффект от введения дисциплины ДСП иллюстрируется рис. 7, где приведена зависимость времени ожидания от приоритета для ДСП с тремя классами приоритетов. На этом рисунке пунктиром показан характер аналогичных зависимостей для дисциплин ДБП, ДОП и ДАП.

Рис. 6.                                                               Рис. 7.

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

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

1.  Назовите свойства канала обслуживания?
2.  Назовите характеристики процесса обслуживания?
3.  Назовите характеристики дисциплины обслуживания?

ЛИТЕРАТУРА

а) основная

1.  Барышева, В.К. Теория вероятностей: Учебное пособие / В.К. Барышева, Ю.И. Галанов, Е.Т. Ивлев, Е.Г. Пахомова.- Томск: Изд-во ТПУ, 2009. - 131 с. [Электронный ресурс] //– Режим доступа: http://window.edu.ru/window_catalog/files/r74676/Teor_ver.pdf

б) дополнительная

1.  Положинцев, Б.И. Теория вероятностей и математическая статистика: Учебное пособие / Б.И. Положинцев.- СПб.: Изд-во Политехн. ун-та, 2010. - 95 с. [Электронный ресурс] //– Режим доступа: http://window.edu.ru/window_catalog/files/r75165/PBI.pdf

Периодическая литература

1.  Информационно-измерительные системы. Радиотехника. Изд. Стандартов.

Internet-ресурсы

	http://ibooks.ru/	Электронно-библиотечная система  ibooks.ru (Айбукс-ру)
	http://www.knigafund.ru/	Электронно-библиотечная система "КнигаФонд"
	http://www.gelios-arv.ru	Издательство "Гелиос АРВ"
	www.jurnalik.ru	бесплатные русскоязычные журналы
	http://www. bnti.ru.	Бюро научно-технической информации
	www.osp.ru	Журнал «Открытые системы»

1. тематического моделирования и информационной безопасности Согласовано
2. РЕФЕРАТ дисертації на здобуття наукового ступеню кандидата юридичних наук Харків ~ Дисер.
3. Лучановская СОШ Томского района Проект это мечта творческое дело цель к которой мы будем с
4. Реферативная работа Выбранные места из переписки с друзьями
5. Введение. Можно ли развить умственные способности Несомненно Знаю многие будут удивлены узнав что IQ мож
6. реферат доклад выпускную квалификационную работу.html
7. 1 Зарождение биржевой торговли реальными товарами возникновение понятия биржи 1
8. Лабораторная работа 70 ИССЛЕДОВАНИЕ ТЕМПЕРАТУРНОЙ ЗАВИСИМОСТИ СОПРОТИВЛЕНИЯ МЕТАЛЛОВ И ПОЛУПРОВОДНИКО
9. Бизнес-план производства технического углерода (сажи) (и газообразного водорода)
10. Развитие чувства времени у детей старшего дошкольного возраста
11. ИО Сентябрь Октябрь 2 9 16 23
12. доклад ради которого сюда съехались ученые всех стран
13. Se o tende d TL onde podro opter entre outrs informcoes ou Lisbo crt
14. Нижегородский государственный университет им1
15. зуд а не сыпь. Зуд бывает различным в течение дня но он обычно усиливается вечером и ночью
16. Программирование системы уравнений
17. Статья 1 Отношения регулируемые настоящим Федеральным законом 1
18. всего лишь одна из многих функций маркетинга причем зачастую не самая существенная
19. на тему- ldquo;Перериванняrdquo; Виконав- студент групи СКСс11 Липовий Р
20. Суматранские барбусы альбиносы

Материалы собраны группой SamZan и находятся в свободном доступе