ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.10.2020
Просмотров: 12412
Скачиваний: 247
n
∑
i=1
P
ij
= 1, т.е. сумма переходов вероятностей каждой строки матрицы перехода всегда равна
единице.
Сделав соответствующие преобразования выражений (17.65) и (17.66), получим матрицу перехода
стационарной системы за Z шагов:
M(Z) = [M(1)]
z
.(17.67)
Пример.
Задана матрица перехода системы за один шаг
M(2) =
(
)
=
(
)
.
P
11
(1) P
12
(1)
0,5 0,5
P
21
(1) P
22
(1)=
0,6 0,4
Требуется определить матрицу перехода ИСМО из i-го в j-е состояние за три шага (Z=3).
Запишем матрицу перехода за три шага в соответствии с выражением (17.67):
M(3)=[M(1)]
3
=
(
)
.
0,545 0,455
0,546 0,454
Определим вероятности перехода системы за три шага: из 1-го в 1-е состояние Р
11
=(3)=0,545; из 1-
го во 2-е состояние P
12
(3)=0,455; из 2-го в 1-е состояние P
21
(3)=0,546; из 2-го во 2-е состояние P
22
(3)=0,454.
С учетом того, что
n
∑
j=1
P
ij
= 1, проверим правильность вычислений:
2
∑
j=1
P
1j
=
2
∑
j=1
P
2j
=0,545+0,455=0,546+0,454=1. Следовательно, вероятность и матрица перехода определены
верно.
Таким образом, изложенный метод анализа ИСМО с использованием цепей Маркова позволяет
определять вероятности ее переходов из одних состояний в другие (за конечное число шагов), зная
которые можно рассчитывать другие характеристики эффективности и качества функционирования
ИСМО.
413
::
::
::
17.5.
Методика расчета однотерминальной ИСМО
Рассмотрим однокомпьютерную или многокомпьютерную (одно- или многопроцессорную)
информационную систему, решающую задачи или отвечающую на вопросы многих пользователей в
режиме непосредственного доступа, пакетном режиме, в режиме разделения времени или в
реальном масштабе времени. Выделим из указанных ИСМО однотерминальные и
многотерминальные системы.
413
Однотерминальной ИСМО назовем одно- или многокомпьютерную систему, работающую в одном из
указанных выше режимов, состоящую из одного или нескольких скомплексированных или
нескомплексированных ПК, одного терминала, связанного с ЦЯ системы только по удаленному или
только по локальному каналу связи. Многотерминальная ИСМО - это однокомпьютерная,
многопроцессорная или многокомпьютерная система, соединенная через мультиплексоры передачи
данных, каналообразующую аппаратуру, каналы связи и удаленные терминалы со многими
пользователями и работающая в режиме разделения времени или в реальном масштабе времени.
В связи с тем, что однотерминальные и многотерминальные ИСМО - это системы настоящего и
будущего Интернет, дадим методику расчета именно этих систем. В соответствии с классификацией,
приведенной в табл. 3.1, рассчитаем основные вероятностные характеристики ИСМО класса:
P|M|m|n=
{
on - line
при п = 1, 2, ...
}
. (17.68)
off-line
при и =0
В соответствии с условием (17.68) на вход такой системы поступает пуассоновский поток
информации с плотностью λ, а на ее выходе имеется экспоненциальное распределение времени
обслуживания с плотностью μ. Система может состоять из одного или нескольких ПК; она работает
по принципу
off-line
при =0, т.е. локальные терминал и канал связи (ЛТКС) или по принципу
on-line,
при
п=1.
Обработка вводов (вопросов) является многофазовой.
Примем следующее символьно-логическое обозначение состояний ИСМО с целью облегчения
исследований и расчета ее основных вероятностных характеристик.
Пусть С
0
- ИСМО исправна и свободна (не загружена), т.е. ни по одной задаче информация не
введена в систему; С
1
- ИСМО загружена, решается (обрабатывается один вопрос) одна задача; С
2
-
ИСМО загружена, информация одной задачи подготовлена и сформирована для запуска на
решение; С
3
- ИСМО загружена, информация двух задач подготовлена и сформирована для запуска
на решение и т. д.; С
n
- ИСМО загружена, информация (n-1) задач подготовлена и сформирована
для запуска на решение.
Схема размеченного графа указанных состояний однотерминальной ИВСМО приведена на рис. 17.1.
Каждому состоянию поставим в соответствие вероятность того, что система будет в данный
(фиксированный) момент времени именно в указанном состоянии, т. е.
C
0
(t)→P
0
(t),
(17.69)
C
1
(t)→ P
1
(t);...; C
n
(t)→P
n
(t).
Переход из состояния С
i
в С
j
(i≤j) вызывается входным потоком информации с интенсивностью λ
ij,
С
0
→ C
1
→λ
01
(17.70)
C
1
→C
2
→λ
12
;...;C
n-1
→C
n
→λ
n-1,n
.
414
Соответственно, переход ИСМО из состояния С
i
в С
j
(i>j) происходит с интенсивностью μ
ij
моментов
времени завершения (обслуживания) решения задач:
C
1
→C
0
→μ
10
;
(17.71)
С
2
→С
1
μ
21
;...; С
n
→C
n-1
→μ
n,n-1
.
Предположим, что в определенный момент времени t
0
в ИСМО находится
п
запросов, что
соответствует принятому обозначению C
n
(t
0
). Пусть в фиксированный момент времени Δt в ИСМО
поступил еще один запрос. Этому состоянию будет соответствовать обозначение C
n+1
(t
0
+Δt). Если
за такой же момент времени Δt завершено решение одной из задач (вопросов), то состояние ИСМО
примет обозначение C
n-1
(t
0
+Δt). Следовательно, марковскую последовательность процессов
изменения состояний ИСМО, определяемых увеличением числа задач путем поступления
информации по соответствующему закону распределения и уменьшения количества задач в системе
путем выдачи пользователям результатов (ответов) решения, можно записать в виде марковских
цепей соответственно увеличения и уменьшения вопросов (задач) в ИСМО:
С
n
→ (t
0
)→C
n+1
(t
0
+Δt); Δt→0;
(17.72)
C
n
(t
0
)→C
n-1
(t
0
+Δt); Δt→0.
Для марковских последовательностей состояний увеличения и уменьшения (17.72) запишем
вероятность перехода ИСМО соответственно в состояние увеличения и уменьшения:
P
n
{C
n
(t
0
)→C
n+1
(t
0
+Δt)}=μ
n,n+1
Δt+0(Δt);
(17.73)
P
n+1
{C
n+1
(t
0
)→C
n
(t
0
+Δt)}=μ
n+1,n
Δt+0(Δt).
Вероятность того, что в момент Δt в ИСМО не поступит ни одной задачи, примет вид
P
n
{C
n
(t
0
)-/
→
C
n+1
(t
0
+Δt)}=1-μ
n,n+1
Δt+0(Δt). (17.74)
Таким образом, в процессе функционирования ИСМО может находиться в (n+i)-м состоянии с
соответствующими ему вероятностями P
0
(t), P
1
(t), P
2
(t), ..., P
n
(t) P
n+1
(t), i =1,k, сумма которых
всегда равна единице и которые можно определить, задавая интенсивности входных потоков
информации λ
ij
и выходных потоков обслуженных вопросов (задач) μ
ij
. Подробный вывод
дифференциальных уравнений Колмогорова-Эрланга, по которым легко определяются все
вероятности любых состояний, изложен в специальной литературе. Однако для стационарного
состояния можно предложить более простой способ расчета вероятностей состояний ИСМО на
основе использования
Рис.17.1.Схема размеченного марковcкого графа состояний однотерминальной ИСМО
415
теории размеченных графов. С этой целью вернемся к рис. 17.1, на котором представлена
марковская цепь последовательностей состояний ИСМО в виде размеченного графа,
квадраты которого представляют состояния и их вероятности в соответствии с системой
(17.69), а стрелки - соответственно входные и выходные потоки, переводящие ИСМО в
состояние увеличения или уменьшения номеров последовательности марковской цепи в
соответствии с системами (17.70) и (17.71). Исключив зависимости состояний и
вероятностей от времени, примем установившееся состояние функционирования ИСМО,
которое можно описать линейными однородными алгебраическими уравнениями на основе
использования размеченного графа. В соответствии с системой (17.69) и графом
марковской цепи установившегося режима ИСМО запишем линейное алгебраическое
уравнение, сбалансированное по нулю, для состояния С
0
:
Р
0
λ
00
+ P
1
μ
10
- P
0
λ
00
- P
0
λ
01
= 0.(17.75)
Аналогично запишем сбалансированные уравнения соответственно для состояний С
1
, С
2
, С
3
, ..., С
n-1
,
С
n
размеченного графа ИСМО:
Р
0
λ
01
+ P
1
λ
11
+P
2
μ
21
-P
1
μ
10
-P
1
λ
11
-P
1
λ
12
=0;
(17.76)
P
1
λ
12
+P
2
λ
22
+P
3
μ
32
-P
2
μ
21
-P
2
λ
22
-P
2
λ
23
=0;
P
2
λ
23
+P
3
λ
33
+P
4
μ
43
-P
3
μ
32
-P
3
λ
33
-P
3
λ
34
=0;
.................
P
n-1
λ
n-2,n-1
+P
n-1
λ
n-1,n-1
+P
n
μ
n,n-1
-P
n-1
μ
n-1,n-2
-
-P
n-1
λ
n-1,n-1
-P
n-1
λ
n-1,n
=0.
Так как в стационарном режиме работы ИСМО λ
ii
всех состояний равны нулю, сделав
соответствующие преобразования, выражения (17.75) и (17.76) перепишем в виде одной системы из
n+1 уравнений с
п
неизвестными Р
i
, коэффициентами которых являются λ
ij
и μ
ij
:
λ
01
P
0
+0-μ
10
P
1
-0=0;
(17.77)
λ
01
P
0
+μ
21
P
2
-μ
10
P
1
-λ
12
P
1
=0;
λ
12
P
1
+μ
32
P
3
-μ
21
P
2
-λ
23
P
2
=0;
λ
23
P
2
+μ
43
P
4
-μ
32
P
3
-λ
34
P
3
=0;
........................
λ
n-2,n-1
P
n-2
+μ
n,n-1
P
n
-μ
n-1,n-2
P
n-1
-
-λ
n-1,n
P
n-1
= 0.
Решив систему (17.77) и учитывая, что
n
∑
i=0
P
i
= 1, определим вероятность первоначального состояния ИСМО:
P
0
=1/
n
∑
k=0
k
∏
j=1
(λ
j-1,j
/μ
j,j-1
).(17.78)
Зная вероятность Р
0
и подставляя ее в каждое из уравнений (17.77), находим все остальные
вероятности состояний ИСМО, представленных в виде размеченного
416
графа на рис. 17.1. Если интенсивности λ
ij
, переводящие ИСМО в состояния увеличения
(i<j), и интенсивности обслуживания (решения) задач μ
ij
, переводящие систему в состояния
уменьшения (i>j) при стационарном режиме работы последней, принять постоянными, то
общую формулу для вычисления всех P
i
можно записать в виде:
P
i
=
i
∏
k=1
η
k
[
n
∑
k=0
k
∏
i=1
η
j
]
-1
.(17.79)