Определение цепи Маркова

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

∑ P_lj(t_k) = l для всех i = ],.., n, t_k e Θ.

4. X = X{t_k)=[x_s(t_k).., x_N(t_k)] - вектор-строка распределения вероятностей нахождения FMC в соответствующих состояниях в момент t_k, то есть х, (t_k) - это внроятность того, что в момент t _k система находится в

состоянии S/ При этом ∑ x_i (t_k) = 1, t_k € Θ

По теореме об умножении вероятностей и с учетом освоенного свойства марковского процесса получим:

x_j (t_k+1) = ∑ p_k (t_k) x_i (t_k), i= 1, …n. (3.3)

где p_ij (t_k) выступают в роли условных вероятностей перехода в состояние Sj при условии, что система находится в состоянии S_i.

Нетрудно видеть, что правая часть формулы определяет произведение вектора-строки X(t_k) на матрицу P{t_k) и в векторной форме эквивалентна следующей записи динамического процесса:

Цепь называется однородной, если р_j не зависит от времени. В этом случае Р - числовая матрица. Если вектор X(t_k ) задан, то для однородной цепи Маркова из рекуррентной формулы (3.4) следует цепочка выражений:

X(t₁)= X(t_o)-P,

X(t₂)=x(t_l)-P = X(t₀).P²

…

X (t_k) = X(t_о)P^к (3-5)

где P^k- k-я степень матрицы Р.

Цепь Маркова можно представить как динамическую систему - вероятностный автомат с обратной связью (рис. 3.1). На рисунке прямоугольник 1 означает задержку сигналов
состояния на 1 такт._____________

Матрицы Р, порождающие цепи Маркова, т.е. такие у которых все элементы 0 < p_tj ≤ 1, а их суммы по столбцам равны единице для всех строк

n

∑ p_ij = 1, i=1,..., n,

j=1

называют стохастическими. Свойства этих матриц хорош! изучены [14], и мы в дальнейшем будем использовать известные факты без доказательств.

Отметим также, что, помимо аналитических методе исследования поведения FMC, большие возможности дает метод статистического моделирования [1]. Созданию и исследование программ статистического моделирования цепей Маркова» посвящена одна из работ лабораторного практикум! приведенных в конце книги.

3.2. Модель вычислительной системы

как цепь Маркова

Основные понятия, связанные с моделированием I основе цепей Маркова, рассмотрим на примере простейшей модели, в которой ВС рассматривается как конечный автомат, состоящий из центрального процессора (CPU) F_o и нескольких внешних устройств F₁,..., F₄. Центральный процессор производит вычисления, а внешние устройства осуществляют файловый обмен, например, как показано на рисунке 3.2.

В частности, предполагается наличие следующих Серийных устройств:

F₁- накопитель на жестком магнитном диске;

F₂ - накопитель на гибком магнитном диске;

F₃ - устройство печати;

F₄ - клавиатура.

Система работает по следующим правилам. Вначале запускается процессор, который может либо производить вычисления, либо управлять только одним устройством. Устройства, F₁, F₂, F₃ , окончив работу, возвращают управление процессору. Если же управление переходит к клавиатуре (F₄), Цикл автоматической работы заканчивается и система останавливается в ожидании команды с клавиатуры. Система решает некоторую типовую задачу, однако ее ход может быть разным в зависимости от данных. Модель, которую мы будем рассматривать, не отражает сущности выполняемых операций, а имеет дело с временными интервалами, в течение которых работают устройства, входящие в ВС. Эти временные интервалы являются случайными величинами. Модель должна удовлетворять следующим требованиям.

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

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

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

4. Принимается, что достаточная адекватность модели, реальному вычислительному процессу достигается при совпадении первых моментов одноименных характеристик - математического ожидания и дисперсии.

Будем рассматривать вычислительный процесс какпоследовательность этапов счета и файлового обмена (рис. 3.3).

Здесь с_j - трудоемкость (продолжительность) счета на j-м этапе, j=1, 2,...;

а_ij- продолжительность обмена с i -м периферийным устройством на j-м этапе, i=1, 2, 3.

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

S={S₀, S₁, S₂, S₃, S₄}.

Здесь S₀ - состояние, соответствующее работе CPU;

S_i - состояние обмена с i-м устройством (i=1, 2, 3);

S₄ - состояние ожидания (окончание вычислительного процесса).

Состояния являются функциями времени: S_i=S_i(t), причемсмена состояний происходит в случайные моменты t₀, t₁, …, t_m. В рассматриваемой модели нам не важны значения интервалов времени между моментами смены состояний ВС. Эти моменты будут рассматриваться как последовательные такты работы ВС и обозначаться целыми числами. Таким образом, в дальнейшем время считается дискретным.

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

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

X(t₀)=[x₀ x_l x₂ x₃ x₄]=[10000],

а матрица вероятностей переходов не зависит от времени:

Из этой матрицы видно, что из состояния S₀ процесс с вероятностями р₁, р_2, p₃, p₄ переходит, соответственно, в состояния S₁, S₂,..., S₄, при этом р₁+р₂+р₃+р₄=1.

Из состояний S₁, S₂, S₃ процесс с вероятностью 1 возвращается в S₀. Достигнув состояния S₄, процесс навсегда остается в нем. Такое состояние называется поглощающим. Граф смены состояний рассматриваемой цепи имеет вид представленный на рисунке 3.4 а. Динамика смены состояний системы может быть представлена также обыкновенной сетью Петри со случайным срабатыванием переходов t₁₁ —t_4l (рис. 3.4 б) \

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

Пусть С₀- средняя трудоемкость этапа счета (среднее число процессорных операций или соответствующее процессорное время);

C₁, C₂, C₃ - средняя трудоемкость операций файлового обмена в байтах (или, если известна скорость обмена каналов, 1 среднее время обмена).

Значения вероятностей p₁, p₂, p₃, p₄ предопределяют ход вычислительного процесса. Эти значения вычисляются следующим образом.

Трудоемкость алгоритма определяет, в частности среднее число N₁, N₂, N₃ обращений к файлам F₁, F₂, F₃. Следовательно, среднее число переходов из состояния S_o в состояния S₁, S₂, S₃ должно быть N₁+N₂+N₃. Один раз процесс переходит в поглощающее состояние S₄. Таким образом, вычислительный процесс должен выходить из состояния S₀ в среднем

3

N=∑ N_h+1 раз. (3.7)

h=1

Значение p_h определяет долю переходов в состояние S_h по отношению к всевозможным переходам

N_h

из состояния S₀ в состояния S₁,..., S₄. Эта доля равна в среднем ———, где N_h- среднее число

N

переходов в состояние S_h. N_k 1

Следовательно, p_k = —, h = l..3, p₄. = —.

N N

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

C_cp = C₀-N = C₀(∑ N_h+l)

C_ср

ОткудаС₀=—. (3.8) (3.8) ∑ N_h + 1

Трудоемкость конечного этапа вычислительного процесса представляет собой случайную величину со средним значением C_h, h = 0, l,..., n.

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

Обратная задача - вычисление средних величин N_i по заданным вероятностям, рассматривается в п. 3.4.

Вернемся к примеру. Воспользовавшись основнойформулой пересчета вероятностей (3.4), выпишем векторы вероятностей в несколько последовательных моментов. Итак.

Обратим внимание, что сумма вероятностей нахождения системы во всех состояниях (т.е. сумма элементов вектора X{t_k)) на каждом шаге остается равной единице.

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

X{t_k) = X(t₀)P^k.

Выпишем степени матрицы Р:

Обратим внимание на то, что n-я строка матрицы Р^к определяет вероятности распределения состояний системы в k -й момент времени при X(t_o)= [0,..., 1,..., 0], где единица стоит на п-м месте, а все остальные элементы нули, т.е. при старте системы из состояния S_n.

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

1. Наблюдается периодичность поведения системы с периодом, равным 2. Так, в четные такты вероятность работы процессора больше 0, а в нечетные - нулевая. Вероятности работы периферийных устройств больше 0 в нечетные моменты, а в четные равны нулю.

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

Рассмотрим теперь некоторые вопросы теории цепей Маркова.