Потоки требований

12 13 14 15 16 17 18

Тема 2 Теоретические основы проектирования ИС

Лекция 8

Контрольные вопросы к лекции 7

1. Какие цели ставятся при формировании концептуального проекта?

2. Что определяется при концептуальном проектировании?

3. Какие факторы влияют на реализуемость проекта?

4. Кто должен писать техническое задание на проектирование системы и каково его содержание?

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

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

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

Потоки требований имеют такие свойства, как стационарность, ординарность и отсутствие последействия.

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

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

Свойство отсутствия последействия означает независимость вероятностных характеристик потока от предыдущих событий. Иными словами, вероятность поступления k требований в промежуток [ t₁,t₂ ] зависит от числа, времени поступления и длительности обслуживания требований до момента t₁.

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

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

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

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

Простейшие потоки. Если поток требований обладает свойствами стационарности, ординарности и отсутствия последствия, то такой поток называется простейшим (или пуассоновским) потоком требований.

Вероятность поступления k требований за промежуток времени t в пуассоновском потоке определяется из выражения

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

(при t>0),

где - величина, обратная среднему значению интервала Т.

Математическое ожидание, дисперсия и среднеквадратическое отклонение промежутка T:

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

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

Решение. Примем за единицу времени 5 мин. В задаче требуется найти

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

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

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

Тогда вероятность наступления k требований для рассматриваемого вида потока будет

Пример Рассмотрим простейший поток с нестационарным параметром, изменяющийся по закону . Параметр является периодическим, его период равен 1/3. Найти вероятность отсутствия требований на отрезке [1,5].

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

, тогда .

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

Вероятность поступления k требований для потока с возможной неординарностью с учетом вероятности p_m нахождения m требований в пакете

, при

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

Вероятность поступления требований k за данный промежуток времени t для потока с возможным последействием будет выглядеть следующим образом

где - функция Пальма-Хинчина.

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

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

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

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

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

Закон распределения случайной величины Т называется законом Эрланга n -го порядка и имеет плотность

(при t>0).

Математическое ожидание, дисперсия и среднее квадратическое отклонение случайной величины Т соответственно равны:

; ; .

Для потоков Эрланга n-го порядка вероятность поступления k требований за промежуток времени t равняется

для k >0. При k =0 .

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

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

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

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

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