Многоканальная СМО с ожиданием (М/М/m)

В системе имеется m каналов обслуживания и очередь с числом мест n, с каждого из которых заявка может поступать на любой освободившийся канал. Все потоки заявок, циркулирующие в системе – простейшие, с экспоненциальным законом распределения интервалов времени. Интенсивность входящего потока - l заявок/ед.вр, интенсивность потока обслуживания m заявок/ед.вр. Дисциплины ожидания и обслуживания бесприоритетные. Заявка, поступившая на вход системы назначается на обслуживание, если хотя бы один из m каналов свободен. Если каналы обслуживания заняты, заявка поступает в очередь и ждёт начала обслуживания. Если все n мест в очереди заняты, заявка получает отказ и уходит из системы не обслуженной. Как и прежде, будем связывать состояние системы с числом находящихся в ней заявок, т.е.:

Z₀ – состояние простоя (нет заявок, каналы простаивают, очередь отсутствует);

Z₁ – в системе одна заявка, её обслуживает один канал, остальные (m-1) каналов свободны; очереди нет;

…..

Z_m – очереди ещё нет, в СМО m заявок, все каналы заняты обслуживанием;

Z_m+1 – все m каналов обслуживания заняты и одна заявка находится в очереди;

…..

Z_m+n – все m каналов обслуживания заняты и все n мест в очереди заняты;

В состоянии Z_m+n система не способна принять ни одной заявки, все вновь пришедшие заявки получат отказ.

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

Граф состояний системы показан на рис.3.8.

l l..... l l..... l

.........

m 2m mm mm mm

Рис.3.8.

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

Данная модель относится к модели «Размножения и гибели», поэтому для определения вероятностей состояния системы можно использовать формулы Эрланга:

; 1≤k≤m;

; k>m;

.

Характеристиками данной системы являются:

1) вероятность отказа – это вероятность того, что пришедшая в систему заявка получит отказ, т.е. это вероятность состояния Z_m+n: ;

2) вероятность обслуживания или относительная пропускная способность: ;

3) абсолютная пропускная способность или интенсивность потока обслуживания: ;

4) средняя длина очереди:

5) среднее время ожидания заявки в очереди – t_ож. Для определения t_ож необходимо рассмотреть всевозможные гипотезы о том, в каком состоянии застанет систему вновь прибывшая заявка и сколько времени ей придётся ждать обслуживания с учётом бесприоритетных дисциплин ожидания и обслуживания. В частности, если заявка застанет систему в одном из состояний Z₀, Z₁,… Z_m-1, когда очередь и каналы свободны, ей не придётся ждать начала обслуживания и t_ож =0. Если заявка застает систему в состоянии Z_m, когда все каналы заняты обслуживанием, заявка занимает первое место в очереди и ждёт окончания обслуживания в одном из каналов.

Суммарный поток обслуживания при полностью загруженных каналах складывается из m простейших потоков обслуживания с одинаковой для всех каналов интенсивностью m, следовательно, суммарный поток имеет интенсивность mm. Время ожидания заявки в среднем равно , причём, вероятность этого события P_m. Если вновь пришедшая заявка застаёт систему в состоянии Z_m+1, она занимает второе место в очереди и будет ждать в среднем единиц времени. В состоянии Z_m+n-1, когда СМО ещё может принять заявку, время ожидания заявки равно

В состоянии Z_{m + n} заявка получает отказ и время ожидания равно нулю t _ож=0. Среднее время ожидания можно найти по формуле математического ожидания для дискретной случайной величины:

6). - среднее время пребывания заявки в системе;

7) - среднее число заявок в системе;

8) среднее число занятых каналов:..

Если принять длину очереди неограниченной , любая заявка, поступившая на вход системы, рано или поздно будет обслужена («Чистая» СМО).

Предельные вероятности состояний:

(k=1,2,…,m);

(l=1,2,…, );

.

Установившийся режим в такой системе существует, если ,

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

При и формулы для характеристик существенно упрощаются:

.

В «чистой» СМО потери отсутствуют, поэтому P_об=1, l_об=l, Р_отк=0;

- среднее время ожидания ;

- среднее время обслуживания ;

- среднее время пребывания заявки в системе ;

- средняя длина очереди ;

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

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

3.2.3.СМО с «нетерпеливыми» заявками

На практике часто встречаются СМО, в которых заявки могут уйти из системы, не дождавшись начала обслуживания или во время обслуживания, если время пребывания в системе превышает некоторую величину τ _доп (заявка находится в СМО до тех пор, пока τ _доп > t _ож или τ _доп > t _с).

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

Время τ _доп ‑ допустимое время пребывания заявки в системе. Предполагается, что поток уходов является простейшим со средним τ _доп. Т.к. для простейшего потока исчерпывающей характеристикой является интенсивность, для потока уходов “нетерпеливых” заявок

можно ввести интенсивность ν =. Заявки могут уходить как из

очереди, если t _ож > τ _доп, так и из каналов обслуживания, если t _ож ≤ τ _доп. Обычно считается, что интенсивности этих уходов одинаковы и

составляют ν _ож = ν _об = ν = . В качестве базовой модели для СМО
с «нетерпеливыми» заявками выберем M/M/m с ожиданием. Процессы в системе определяются входящим потоком заявок с интенсивностью λ, потоком обслуживания с интенсивностью μ, потоком уходов из очереди с интенсивностью ν _ож из каналов обслуживания с интенсивностью ν _об.

Граф системы показан на рисунке 3.9.

…

…

λ λ λ λ λ

…

…

1(μ + ν _об) 2(μ + ν _об) m (μ + ν _об) m (μ + ν _об)+1 ν _ож m (μ + ν _об)+ nν _ож

Рис.3.9.

Переходы из состояний, соответствующих отсутствию очереди, в соседние слева состояния происходят под воздействием двух независимых потоков событий: потока обслуживания с интенсивностью μ и потока ухода «нетерпеливых» заявок с интенсивностью ν _об. Т.к. процессы в различных каналах обслуживания независимы, суммарная интенсивность переходов связана с числом занятых каналов и равна k (μ + ν _об). Интенсивность переходов при наличии очереди складывается из 2-х составляющих:

суммарной интенсивности переходов за счет потоков обслуживания и уходов заявок из каналов ‑ m (μ + ν _об) и суммарной интенсивности переходов за счет независимых уходов «нетерпеливых» заявок из очереди и пропорциональной длине очереди n.

Т.к. граф на рис.3.9. – модель «размножения и гибели», используются формулы Эрланга для нахождения вероятностей состояний:

Если привести интенсивность уходов из очереди и из каналов к интенсивности обслуживания:

Вероятность P ₀, определяемая из условия нормировки,

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

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

Вероятность отказов можно определить как вероятность состояния Z_{m + n} :

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

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

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

- заявка может покинуть систему, находясь в очереди

(прерывания обслуживания не допускается)

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

3.2.3.Замкнутые СМО

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

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

Z система имеет M терминалов T ₁, T ₂, …, T _M (рис.3.10), за каждым из которых находится пользователь, формирующий запросы на решение задач. После того, как один пользователь сформировал запрос, он не может более формировать запросы до тех пор, пока не получит ответ на свой вопрос. Причем, время, необходимое пользователю для формирования запроса, считается распределенным экспоненциально с математическим ожиданием T, что позволяет рассматривать пользователя как источник заявок с интенсивностью

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

Обслуживание пользователей производится m каналами (m ≤ M), которые являются универсальными каналами обслуживания с известным математическим ожиданием длительности обслуживания и интенсивностью µ. В системе имеется n‑ местная очередь, в которую поступают заявки, заставшие каналы обслуживания занятыми (n = M - m).

Граф переходов замкнутой СМО приведен на рис.3.11. Состояния системы определяются так:

…

	T1
		T2
		TM

…

Рис.3.10.

Z ₀ – заявок нет, ЭВМ простаивают, следовательно, интенсивность входящего потока равна Mλ;

Z ₁ – одна заявка на обслуживании, очередь пуста; т.е. пользователь, пославший запрос, ждет ответа, следовательно, интенсивность потока заявок равна (M -1) λ;

...

Z _m – m пользователей отправили запрос, очереди еще нет, все каналы заняты; интенсивность потока заявок ‑ (M - m) λ;

Z _m+1 – (m +1) пользователь сформировал запрос, 1 заявка в очереди; интенсивность потока заявок – [ M -(m -1)] λ;

...

Z _m+n – все M пользователей сформировали запрос, система полностью загружена, интенсивность входящего потока равна 0.

…

…

Mλ (M -1) λ [ M -(m -1)] λ (M - m) λ λ

…

…

μ 2 μ mμ mμ mμ

Рис.3.11.

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

Для случая, когда имеется очередь:

Характеристики данной системы:

1) поскольку система является замкнутой, то все заявки обслуживаются и

2) вероятность обслуживания ‑

3) абсолютная пропускная способность рассматривается как суммарная производительность каналов обслуживания –

4) для определения среднего числа заявок находящихся в системе, используется условие равенства в установившемся режиме интенсивности выходящего потока и потока заявок на входе системы:

5) средняя длина очереди ‑

6) для нахождения среднего времени ожидания выдвигаются гипотезы о значении времени ожидания поступившей заявки в различных состояниях системы. Для математического

ожидания

В состояниях от Z ₀ до Z _m-1 вновь прибывшая заявка немедленно назначается на

обслуживание и В В состоянии Z _m заявка ожидает обслуживания в течении

течении времени Для произвольного состояния это время

равно

Таким образом:

7) среднее время нахождения заявки в системе:

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

8) среднее число занятых каналов можно найти как математическое ожидание числа занятых каналов –

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

Методы исследования СМО с простейшими потоками заявок позволяют исследовать достаточно разнообразные СМО. Однако, эти методы являются недостаточными при исследованиях СМО с приоритетными дисциплинами, т.к. эквивалентные схемы «размножения и гибели» имеют большую размерность, и исследованиях реальных СМО, в которых потоки обслуживания отличается от простейших. Для СМО с простейшими потоками для определения характеристик достаточно знать состояния системы, связанные с числом заявок в текущий момент времени. В случае отказа от простейшего типа потоков этой характеристики становится недостаточно, т.к. процессы в СМО становятся немарковскими и не будут обладать свойством отсутствия последствия и необходимо знать временную характеристику , как время прошедшее с начала обслуживания до характерного для данной системы состояния, называемого особым состоянием. Таким образом при произвольном потоке обслуживания состояния системы описываются совокупностью двух переменных . Особые состояния можно задавать по-разному. Если в качестве особого состояния выбрать моменты окончания обслуживания заявки, , т.к. обслуживание новой заявки только начинается, и для задания характеристик системы достаточно знать число заявок поступивших в систему за время от t_i до t_i+1:

где - число заявок на момент времени ;

- число заявок, поступивших в систему за время от t_i до t_i+1. Такая модель удобна для описания систем, в которых характеристики связаны с числом заявок, например требуется определить среднею длину очереди и т.п.

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

Графическая иллюстрация чередования переходов занятости и простоя показана на рис. 3.12.

В момент времени t=1 поступает заявка и приносит работу , т.е. время необходимое для ее обслуживания. До поступления заявки система была свободна и . При поступлении заявки незавершенная работа изменяется скачком до , и начинается обслуживание заявки, при этом незавершенная работа убывает и через время становится равной нулю и начинается период простоя. В момент t=2 поступает заявка и начинается новый период занятости.

Рис.3.12.

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

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

3.3.1.Многомерные СМО

Рассмотрим СМО с произвольным потоком обслуживания. В системе циркулирует М типов заявок, упорядоченных в порядке убывания приоритета N, причем N=M. Заявка имеет наивысший приоритет, если N минимально, с ростом N приоритет заявки уменьшается. Будем считать, что заявки назначаются на обслуживание в порядке поступления их в систему и рассмотрим характеристики системы, относящиеся как к суммарному входящему потоку, так и к каждому типу заявок:

1) среднее время ожидания заявки:

;

(так как рассматриваемая система не имеет потерь, то можно использовать формулу Литтла); здесь - вероятность того, что поступившая в произвольный момент времени заявка относится к i- тому типу;

2) среднее время пребывания заявки в системе:

;

3) средняя длина очереди:

;

4) среднее число заявок в систему:

,

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

(так как рассматриваемая СМО не имеет потерь, среднее число каналов количественно совпадает с приведенной интенсивностью потока заявок i- того типа. );

5) Среднее число занятых каналов:

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

6) .

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

3.3.2.Многомерные СМО с бесприоритетными дисциплинами

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

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

; .

Исследуем свойства такой системы. Для произвольной заявки i- того типа, поступившей в систему вероятность застать систему занятой по значению равна суммарной приведенной интенсивности входящего потока R.

Рассмотрим время ожидания произвольной заявки i- того типа, поступившей в систему и заставшей ее занятой, с вероятностью .

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

Итак,

,

где – суммарное время, необходимое каналу для обслуживание заявок j- того типа, поступивших в систему до рассматриваемого момента и находящихся в очереди;

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

Усредним обе части равенства по времени:

;

Для обслуживания всех находящихся в очереди заявок j- того типа каналу обслуживания требуется время

;

(для СМО без потерь средняя длина очереди заявок j- того типа связана со средним временем ожидания заявок того же типа ). Тогда

;

откуда

Получена система линейных алгебраических уравнений относительно , (i= 1,2,…, M). Вычитая последнее из уравнений этой системы (i=M) из (М- 1) первых уравнений, получим . Отсюда следует, что бесприоритетные дисциплины обслуживания уравнивают времена ожидания заявок разных типов:

,

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

.

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

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

.

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

.

Если выразить второй начальный момент через дисперсию, математическое ожидание и коэффициент вариации, то

,

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

.

Среднее время ожидания заявки в очереди минимально для регулярного потока обслуживаний заявок всех типов ( и увеличивается по мере роста дисперсии длительности обслуживания. Для простейшего потока (ν_k = 1) среднее время ожидания максимально.

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

Время пребывания (время реакции) заявки i- того типа в системе складывается из время ожидания и времени обслуживания . Т.к. при бесприоритетных дисциплинах ожидания и обслуживания время ожидания не зависит от типа заявки среднее время пребывания

.

При одинаковых средних временах ожидания заявки разных типов будут иметь разные времена пребывания в системе.

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

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

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

Дисциплиной обслуживания с относительными приоритетами называется приоритетная дисциплина без прерывания обслуживания. Относительные приоритеты заявок учитываются в момент выбора для назначения на обслуживание. В момент выбора сравниваются приоритеты заявок, находящихся в состоянии ожидания, и канал обслуживания предоставляется первой заявке в непустой очереди с наиболее высоким приоритетом, например, с приоритетом 4. Если в процессе обслуживания этой заявки в системе появляются новые заявки с приоритетами 5,2,1, то ни одна из них, даже обладающая более высоким приоритетом, не нарушит начатого процесса обслуживания заявки с приоритетом 4.

Рис.3.13

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

,

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

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

Усредняя обе части равенства аналогично бесприоритетным дисциплинам, получим:

;

откуда

;

где - суммарная приведенная интенсивность потока заявок с приоритетами k и выше.

Среднее время ожидания заявки с высшим приоритетом k= 1:

.

Это соотношение используется для отыскания :

;

.

Подставив значение , получим среднее время ожидания задержанной заявки k -го приоритета:

;

где - суммарная приведенная интенсивность потока заявок с приоритетами (k- 1) и выше.

Учитывая вероятность занятости системы в момент поступления в нее очередной заявки, получаем среднее время ожидания произвольной заявки k- го приоритета:

.

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

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

3.3.4.Многомерные СМО с абсолютными приоритетами

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

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

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

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

1) от начала - повторное обслуживание;

2) от момента прерывания - дообслуживание;

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

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

,

где - среднее время ожидания начала обслуживания;

- среднее время ожидания в прерванном состоянии.

Рис.3.14

Первую составляющую можно рассматривать как среднее время ожидания задержанной заявки самого низкого приоритета в системе с относительными приоритетами, на вход которой поступает k потоков заявок с приоритетами 1,2,…, k. Действительно, т.к. в исходной системе заявки k- го приоритета прерывают обслуживание заявок с приоритетами k+1, k+2, …, M, то последние не оказывают влияния на время ожидания задержанной заявки k- того приоритета; в расчет должны приниматься только заявки с приоритетом k и выше.

Таким образом,

,

где .

Для определения второй составляющей будем рассуждать следующим образом. Составляющая времени ожидания связана с процессом обслуживания, который в системе без потерь не зависит от того, в каком состоянии, занятом или свободном по отношению к заявкам k-го приоритета застала рассматриваемая заявка систему в момент поступления. Поэтому время будет одинаковым как для задержанной заявки, так и для заявки, заставшей систему свободной (по отношению к заявкам k- го приоритета) и немедленно поставленной на обслуживание. За время обслуживания заявки k- того приоритета в систему поступит в среднем заявок с более высоким приоритетом i, i= 1,…, k- 1, которые будут обслуживаться раньше рассматриваемой заявки и потребуют время, в среднем равное:

.

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

.

За это время в систему поступят еще заявок с более высоким приоритетом i, (i= 1,…, k- 1), чем k:

,

требующие время обслуживания

.

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

и т.д.

Для l -го шага справедливо соотношение

.

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

.

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

.

Для сравнения можно привести качественное соотношение времени ожидания при трех различных дисциплин обслуживания (рис.3.15).

Рис.3.15

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

.

Контрольные вопросы к разделу

1. Как определяется марковская модель с дискретными состояниями и непрерывным временем?

2. Для чего предназначены уравнения Колмогорова и как они строятся?

3. Какая модель называется моделью «размножения и гибели»? Формулы Эрланга.

4. Какие характеристики имеет одноканальная СМО с отказами?

5. Какие характеристики имеет многоканальная СМО с отказами?

6. Как определяется средняя длина очереди в М/M/1 с ожиданием?

7. Как определяется среднее время ожидания заявки в M/M/m?

8. Какие характеристики имеет «чистая» СМО M/M/1 и M/M/m?

9. Какие особенности функционирования имеет СМО с «нетерпеливыми» заявками?

10. Чем отличается замкнутая СМО? Ее характеристики.

11. Какими методами исследуются СМС с произвольными потоками заявок?

12. Как взаимосвязаны характеристики, относящиеся к суммарному и частным потокам многомерных СМО?

13. Как определяется время ожидания в бесприоритетной СМО M/G/1?

14. Как определяется время ожидания заявки в СМО с относительными приоритетами?

15. Как определяется время ожидания заявки в СМО с абсолютными приоритетами

Задания к самостоятельной работе

1. Имеется замкнутая СМО,имеющая два канала обслуживания со средней длительностью обслуживания 50сек.Число источников заявок равно 6, интенсивность потока заявок от одного источника ll = 10 с^-1, число мест в очереди – 4. Определить финальные (предельные) вероятности всех возможных состояний системы, среднее число занятых каналов и среднее время ожидания заявок в очереди.

2. Имеется одноканальная СМО разомкнутого типа без потерь с бесприоритетными дисциплинами ожидания и обслуживания в порядке поступления заявок в систему. Заявки образуют три входящих потока с интенсивностями l₁ =5с^-1, l₂ =15с^-1, l₃=10с^-1, упорядоченных по степени понижения приоритета. Потоки обслуживания заявок 1-го и 3-го типов – простейшие с интенсивностями m₁ =25с^-1, m₃=50с^-1, поток обслуживания заявок 2-го типа – регулярный с интенсивностью m₂ =30с^-1. Число приоритетов равно числу типов заявок.

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

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

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

5. Имеется мультипроцессорная система разомкнутого типа, состоящая из трех одинаковых процессоров.. Система обслуживает поток заявок, поступающих с интенсивностью l =4с^-1.Средняя трудоемкость выполнения алгоритма 5000 опер. Заявка, поступившая в систему хотя бы при наличии одного свободного процессора,немедленно назначается на обслуживание. Если все три процессора заняты обслуживанием, заявка размещается в очереди. Считая систему марковской, найти финальные вероятности и основные показатели качества, если производительность процессора составляет 60000опер¤ с

6. Техническое обслуживание вычислительных средств в ИВЦ, имеющем 4 ЭВМ, осуществляется двумя специалистами. Известно, что среднее время безотказной работы одной ЭВМ равно 2усл.ед. времени, среднее время восстановления ЭВМ равно 0,4 усл.ед. времени. Потоки отказов и восстановления считаются простейшими.

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

7. Цифровая управляющая система, в которой процессор – единственный ресурс, необходимый для решения задач, обрабатывает 3 прикладные программы со средней трудоемкостью 1000опер с,5000опер с,10000опер с. Программы задаются с интенсивностями l₁ =15 с^-1, l₂ =1,5с^-1, l₃ =2,5с^-1.

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

8. В вычислительную систему поступает непрерывный поток сообщений, которые записываются в буферную память объемом n сообщений. Если очередное сообщение застает буферную память полностью занятой, оно считается потерянным. Все сообщения, извлекаемые из буферной памяти, последовательно обрабатываются одним процессором. Модели процессов, протекающих в системе, считаются марковскими. Интенсивность поступления потока сообщений l = 1 сообщение в условную ед. времени, среднее время обработки информации равно 4 усл. ед. времени.

Построить концептуальную и математическую модели системы и рассчитать емкость буферной памяти при условии, что вероятность потери сообщения не превышает Р_отк=0,15.

Список литературы

1.Вентцель Е.С. Исследование операций задачи, принципы, методология;М., Наука1980.

2. Новиков О.А., Петухов С.И. Прикладные вопросы теории массового обслуживания, -М., Сов. Радио, 1969.

3. Клейнрок Л. Теория массового обслуживания. –М., Машиностроение, 1979.

4. Крайников А.И. и др. Вероятностные методы в вычислительной технике.- М., Высшая школа,1986.

5. Ивченко Т.И. и др. Теория массового обслуживания. М., Высшая школа, 1982.

6. Лифшиц А.Л. Мальц Э.А. Статистическое моделирование систем массового обслуживания. М., Сов. Радио, 1978.

7. Альянах Т. Моделирование вычислительных систем

Заключение

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

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

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