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

Лабораторная работа № 5

Стохастические сетевые модели вычислительных систем

Цель работы. Изучение стохастических сетевых моделей вычислительных систем (ВС) и выполнение расчета основных характеристик экспоненциальной стохастической сети.

Теоретическая часть

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

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

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

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

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

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

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

Определение параметров стохастической сети

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

1) число n систем массового обслуживания образующих сеть;

2) число каналов К₁,..,К_n входящих в СМО S₁,..,S_n;

3) матрица вероятности передач , где ;

4) интенсивность l₀источника заявок S₀;

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

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

Пример 1. Разомкнутая сеть содержит 4 СМО и источник входящего потока заявок S₀ с интенсивностью их обслуживания l₀. Матрица вероятности передач имеет следующий вид:

	S₀	S₁	S₂	S₃	S₄
S₀		1
S₁	0.1		0.3		0.6
S₂		0.3		0.7
S₃		0.2			0.8
S₄		0.5		0.1

Вероятности Р_ij определяют порядок циркуляции заявок в сети и соотношения между интенсивностями потоков заявок, циркулирующих в сети. Если все заявки, обслуженные системой S_j поступают в систему S_i, то Р_ij = 1. Если система S_j не связана по выходу с системой S_i , то P_ij = 0. Интенсивность потока, входящего в любую S_i систему сети, определяется суммой интенсивностей потоков, поступающих в нее из других S_j систем.

(1)

Эти выражения представляют собой систему алгебраических уравнений n+1-го порядка, характеризующих сеть, откуда нетрудно определить коэффициенты передачи a_jСМО по формуле:

l_j= a_jl₀ (2)

и по заданной интенсивности источника заявок l₀. Подставляя значение l₀=2c^-1 и вероятности передач в (1), получим систему уравнений:

откуда l₁=20 с^-1; l₂=14.82 с^-1; l₃=12.59 с^-1; l₄=22.06 с^-1

Используя найденные значения l_i в формулу (2), найдем значения коэффициентов передач: a₁=10; a₂=7.41; a₃=6.3; a₄=11.03.

Структурная схема сети на основе матрицы коэффициентов передач имеет вид:

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

Здесь целесообразно остановиться на рассмотрении характеристики стационарного режима разомкнутых экспоненциальных стохастических сетей. Существование стационарного режима разомкнутой сети связано с существованием стационарных режимов в ее СМО. Для системы S_i стационарный режим существует, если загрузка r_i системы меньше единицы, т.е. r_i= (l_iu_i/ K_i) < 1 (3)

где l_iu_i= k_i - среднее число занятых каналов: К_i - общее число каналов в СМО.

После ряда преобразований с учетом (2) можно записать условие существования стационарного режима в разомкнутой сети:

l₀ < min(K_i/a_iu_i,..., K_n/a_nu_n) (4)

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

где М_i - количество заявок, находящихся в системе S_i:

b_i - находиться из условия b_i= l_iu_i

Для одноканальной СМО: p₀_i = 1 - r_i

Пример 2. Используя ранее полученные результаты, определим характеристики сети при К₁ = 3, К₂ = 2, К₃ = 2, К₄ = 3 и средней длительности обслуживания заявок в канале u_i=0.1 с.

В рассматриваемой сети существует стационарный режим, так как

Загрузка систем S₁,..,S₄ и среднее число занятых каналов соответственно равны:

Подставляя полученные значения в (5), определим вероятности простоя каждой СМО сети:

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

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

(6)

l₁ = 0.85; l₂= 1.9; l₃ = 1.8: l₄ = 2.7.

Среднее число заявок в системе S_i :

m_i = l_i + b _i (7)

m1 = 0.85 +2 = 2.85;

m2 = 1.9 + 1.5 = 3.4;

m3 = 1.8 + 1.3 = 3.1;

m4 = 2.7 + 2.2 = 4.9.

Среднее время ожидания заявки в очереди системы S_i:

w _i = l_i / l _i (8)

w₁ = 0.85/20 = 0.04 c;

w₂= 1.9/14.82 = 0.13 с:

w₃ = 1.8/12.59 = 0.14 с;

w₄ = 2.7/22.06 = 0.12 с.

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

u_i = m_i / l _i (9)

из (8) и (9) следует возможность определения u_i = w_i+ u_i.

u₁ = 0.04 + 0.1 = 0.14 c;

u₂ = 0.13 + 0.1 = 0.23 с;

u₃ = 0.14 + 0.I = 0.24 c;

u₄ = 0.12 + 0.1 = 0.22 с.

Из выражений (6),(7),(8) и (9) находим характеристики сети в целом.

Среднее число заявок, стоящих на очереди в сети:

(10)

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

(11)

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

(12)

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

(13)

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

ЗАДАНИЕ

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

Определению подлежат следующие характеристики стационарного режима разомкнутой стохастической сети:

а) загрузка каждой СМО (r_i);

б) среднее число занятых каналов каждой СМО (b_i);

в) вероятности состояния сети (p₀_i)

г) средние длины очередей заявок, ожидающих обслуживания в СМО;

д) среднее число заявок m₁ ..m_i , пребывающих в каждой из систем сети;

е) средние времена пребывания u₁..u_i заявок в системах S₁ ..S_i ;

ж) характеристики сети в целом.

В соответствии с заданным вариантом решения задачи произвести численное определение Р₁_i..Р₅_i. Составить матрицу вероятности передач, дополнив некоторые клетки матрицы значениями Р_ji так, чтобы выполнялось условие

Варианты заданий

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

Выбор элементов Р_ij матрицы вероятностей производится в соответствии с таблицей (индекс j - указывает номер строки, а индекс i - номер столбца матрицы вероятностей). Для каждого варианта в таблице приведена строчка из пяти элементов вероятностей:

Р₁_k ; Р₂₁ ; Р₃_m ; Р₄_n ; Р₅_g.

Численные значения указанных элементов определяют по формулам:

Р₁_k=1/N1; Р₂₁=1/N₂; Р₃_m=1/N₃; Р₄_n=1/N₄; Р₅_g=1/N₅

где N₁ - число букв фамилии;

N₂- число букв имени;

N₃- число букв отчества;

N₄ = N₁+N₂; N₅=N₁+N₃.

Значение вероятности Р₀₁ принимается равным единице. Значение Р₀₀,Р₀₂,P₀₃,P₀₄ равны нулю. Значения u₁ приведены в таблице (считается, что все СМО имеют одинаковую среднюю длительность обслуживания заявок, т.е. u₁ = u₂ = u₃ = u₄ =u₅).

таблица

№ п/п	Элементы матрицы вероятностей передач	l_o c^-1	V_i	K₁K₂K₃K₄K₅
1 2 3 4 5 6 7 8 9 10	P₁₂ P₂₃ P₃₁ P₄₂ P₅₃ P₁₃ P₂₃ P₃₂ P₄₂ P₅₄ P₁₄ P₂₁ P₃₁ P₄₂ P₅₃ P₁₃ P₂₃ P₃₁ P₄₂ P₅₃ P₁₄ P₂₃ P₃₁ P₄₂ P₅₃ P₁₅ P₂₃ P₃₁ P₄₂ P₅₃ P₁₂ P₂₁ P₃₁ P₄₂ P₅₄ P₁₃ P₂₁ P₃₁ P₄₂ P₅₄ P₁₄ P₂₁ P₃₂ P₄₂ P₅₄ P₁₅ P₂₁ P₃₁ P₄₂ P₅₄	1 1 1 1 1 1 1 1 1 1	3.0 3.0 3.0 3.0 3.0 3.0 3.0 3.0 3.0 3.0	1 2 1 3 2 2 1 1 4 2 3 1 4 2 1 4 1 1 2 3 1 1 2 3 4 1 1 3 2 4 1 1 4 3 2 1 1 2 2 4 1 1 2 2 3 1 1 4 2 2
11 12 13 14 15 16 17 18 19 20	P₁₂ P₂₄ P₃₁ P₄₂ P₅₄ P₁₃ P₂₄ P₃₁ P₄₂ P₅₄ P₁₄ P₂₄ P₃₁ P₄₂ P₅₄ P₁₅ P₂₄ P₃₁ P₄₂ P₅₄ P₁₂ P₂₅ P₃₁ P₄₂ P₅₄ P₁₃ P₂₅ P₃₁ P₄₂ P₅₄ P₁₄ P₂₅ P₃₁ P₄₂ P₅₄ P₁₅ P₂₅ P₃₁ P₄₂ P₅₄ P₁₂ P₂₁ P₃₂ P₄₂ P₅₄ P₁₃ P₂₁ P₃₂ P₄₂ P₅₄	1 1 1 1 1 2 2 2 2 2	3.0 3.0 3.0 3.0 3.0 2.5 2.5 2.5 2.5 2.5	1 1 3 2 2 1 1 2 4 2 1 1 2 3 2 1 1 3 3 4 1 1 3 3 2 1 1 3 4 3 1 1 3 2 3 1 1 4 3 3 1 1 2 3 3 1 2 1 3 4
21 23 24 25 26 27 28 29 30	P₁₄ P₂₁ P₃₂ P₄₂ P₅₄ P₁₂ P₂₃ P₃₂ P₄₂ P₅₄ P₁₃ P₂₃ P₃₂ P₄₂ P₅₄ P₁₄ P₂₃ P₃₂ P₄₂ P₅₄ P₁₅ P₂₃ P₃₂ P₄₂ P₅₄ P₁₂ P₂₄ P₃₂ P₄₂ P₅₄ P₁₃ P₂₄ P₃₂ P₄₂ P₅₄ P₁₄ P₂₄ P₃₂ P₄₂ P₅₄ P₁₅ P₂₄ P₃₂ P₄₂ P₅₄	2 2 2 2 2 2 2 2 2	2.5 2.5 2.5 2.5 2.5 2.5 2.5 2.5 2.5	1 3 1 2 4 1 2 1 4 3 1 3 1 4 2 1 4 1 3 2 1 2 1 3 3 1 3 1 2 2 1 3 1 4 3 1 2 3 1 4 1 3 2 1 4
31 32 33 34 35 36 37 38 39 40	P₁₂ P₂₅ P₃₂ P₄₂ P₅₄ P₁₃ P₂₅ P₃₂ P₄₂ P₅₄ P₁₄ P₂₅ P₃₂ P₄₂ P₅₄ P₁₅ P₂₅ P₃₂ P₄₂ P₅₄ P₁₂ P₂₁ P₃₄ P₄₂ P₅₄ P₁₃ P₂₁ P₃₄ P₄₂ P₅₄ P₁₄ P₂₁ P₃₄ P₄₂ P₅₄ P₁₅ P₂₁ P₃₄ P₄₂ P₅₄ P₁₂ P₂₃ P₃₄ P₄₂ P₅₄ P₁₃ P₂₃ P₃₄ P₄₂ P₅₄	2.5 2.5 2.5 2.5 2.5 2.5 2.5 2.5 2.5 2.5	2 2 2 2 2 2 2 2 2 2	1 2 2 1 4 1 3 3 1 4 1 3 3 1 3 1 2 2 1 3 1 2 2 1 3 1 3 3 1 2 1 2 2 1 2 1 3 3 1 2 1 3 3 4 1 1 2 2 4 1
41 42 43 44 45 46 47 48 49 50	P₁₄ P₂₃ P₃₄ P₄₂ P₅₄ P₁₅ P₂₃ P₃₄ P₄₂ P₅₄ P₁₂ P₂₄ P₃₄ P₄₂ P₅₄ P₁₃ P₂₄ P₃₄ P₄₂ P₅₄ P₁₄ P₂₄ P₃₄ P₄₂ P₅₄ P₁₅ P₂₄ P₃₄ P₄₂ P₅₄ P₁₂ P₂₅ P₃₄ P₄₂ P₅₄ P₁₃ P₂₅ P₃₄ P₄₂ P₅₄ P₁₄ P₂₅ P₃₄ P₄₂ P₅₄ P₁₅ P₂₅ P₃₄ P₄₂ P₅₄	2.5 2.5 2.5 2.5 2.5 3 3 3 3 3	2 2 2 2 2 1.5 1.5 1.5 1.5 1.5	1 3 3 2 1 1 2 2 3 1 1 2 2 4 1 1 3 3 2 1 1 3 3 4 1 1 4 4 2 1 1 4 4 3 1 2 2 2 3 2 3 1 1 3 4 2 1 1 3 4
51 52 53 54 55 56 57 58 59 60	P₁₂ P₂₁ P₃₅ P₄₂ P₅₁ P₁₃ P₂₁ P₃₅ P₄₂ P₅₁ P₁₄ P₂₁ P₃₅ P₄₂ P₅₁ P₁₅ P₂₁ P₃₅ P₄₂ P₅₁ P₁₂ P₂₃ P₃₅ P₄₂ P₅₁ P₁₃ P₂₃ P₃₅ P₄₂ P₅₁ P₁₄ P₂₃ P₃₅ P₄₂ P₅₁ P₁₅ P₂₃ P₃₅ P₄₂ P₅₁ P₁₂ P₂₄ P₃₅ P₄₂ P₅₁ P₁₃ P₂₄ P₃₅ P₄₂ P₅₁	3 3 3 3 3 3 3 3 3 3	1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5	3 1 1 3 2 2 1 1 4 2 2 1 1 4 3 2 1 1 3 3 3 1 1 4 3 3 1 1 4 2 3 2 1 1 2 3 4 2 2 3 3 4 1 1 2 3 2 1 1 3
61 62 63 64 65 66 67 68 69 70	P₁₄ P₂₄ P₃₅ P₄₅ P₅₁ P₁₅ P₂₄ P₃₅ P₄₅ P₅₁ P₁₂ P₂₅ P₃₅ P₄₅ P₅₁ P₁₃ P₂₅ P₃₅ P₄₅ P₅₁ P₁₄ P₂₅ P₃₅ P₄₅ P₅₁ P₁₅ P₂₅ P₃₅ P₄₅ P₅₂ P₁₂ P₂₁ P₃₁ P₄₅ P₅₂ P₁₃ P₂₁ P₃₁ P₄₅ P₅₂ P₁₄ P₂₁ P₃₁ P₄₅ P₅₂ P₁₅ P₂₁ P₃₁ P₄₅ P₅₂	3.5 3.5 3.5 3.5 3.5 3.5 3.5 3.5 3.5 3.5	1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0	4 2 1 1 2 4 3 1 1 2 3 3 1 1 2 4 3 1 1 3 4 2 1 1 3 4 1 2 3 1 4 1 3 2 1 4 1 2 2 1 3 1 2 3 1 3 1 3 2 1
71 72 73 74 75 76 77 78 79 80	P₁₂ P₂₃ P₃₁ P₄₅ P₅₂ P₁₃ P₂₃ P₃₁ P₄₅ P₅₂ P₁₄ P₂₃ P₃₁ P₄₅ P₅₂ P₁₅ P₂₃ P₃₁ P₄₅ P₅₂ P₁₂ P₂₄ P₃₁ P₄₃ P₅₂ P₁₃ P₂₄ P₃₁ P₄₃ P₅₂ P₁₄ P₂₄ P₃₁ P₄₃ P₅₂ P₁₅ P₂₄ P₃₁ P₄₃ P₅₃ P₁₂ P₂₅ P₃₁ P₄₃ P₅₃ P₁₃ P₂₅ P₃₁ P₄₃ P₅₃	3.5 3.5 3.5 3.5 4 4 4 4 4 4	1.0 1.0 1.0 1.0 0.5 0.5 0.5 0.5 0.5 0.5	3 1 2 2 1 2 1 2 3 1 2 1 3 2 1 2 1 3 3 1 2 3 4 1 1 3 2 4 1 1 4 3 2 1 1 2 2 4 1 1 2 2 3 1 1 4 2 2 1 1
81 82 83 84 85 86 87 88 89 90	P₁₄ P₂₅ P₃₁ P₄₃ P₅₃ P₁₅ P₂₅ P₃₁ P₄₃ P₅₃ P₁₂ P₂₁ P₃₂ P₄₃ P₅₃ P₁₃ P₂₁ P₃₂ P₄₃ P₅₃ P₁₄ P₂₁ P₃₂ P₄₃ P₅₃ P₁₅ P₂₁ P₃₂ P₄₃ P₅₃ P₁₂ P₂₃ P₃₂ P₄₃ P₅₃ P₁₃ P₂₃ P₃₂ P₄₃ P₅₃ P₁₄ P₂₃ P₃₂ P₄₃ P₅₃ P₁₅ P₂₃ P₃₂ P₄₃ P₅₃	4 4 4 4 4 4 4 4 4 4	0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5	3 2 2 1 1 2 4 2 1 1 2 3 2 1 1 3 3 4 1 1 3 3 2 1 1 3 4 3 1 1 3 2 3 1 1 4 3 3 1 1 2 3 3 1 1 3 4 1 2 1

Дата добавления: 2021-07-19; просмотров: 155; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!