Моделирование динамики систем на основе цепи Маркова с дискретным временем

    ^j=1

4. X = X(t_k) = [х₁(t_k),…,x_N(t_k)] - вектор-строка распределения вероятностей нахождения FMС в соответствующих состояниях в момент t_k, то есть x_l(t_k) - это вероятность того, что в момент t_k система находится в состоянии S_i. При этом

    _n

    ∑ x_i(t_k) =l,  t_k ϵ Θ.

    ⁱ⁼¹

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

                 _n

    x_j(t_k+1) = ∑ p_ij(t_k)x_i(t_k) ,  i=1,..,n.   (3)

          ⁱ⁼¹

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

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

    X(t_k+1)=X(t_k)P(t_k).   (4)

    5. Х₀ = X(t_k) = [x₁(t₀), x₂(t₀),...x_n(t₀)] - распределение вероятностей нахождения FMC в начальный момент времени t=t_0. Задание вектора X{t₀) позволяет последовательно вычислять векторы X(t_k) (k=1,2,..).

    Последовательность  состояний  S(t₀),S(t₁),...,S(t_k) называется конечной цепью Маркова.

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

    X(t₁)=X(t₀)P.

    X(t₂)=X(t₁)P=X(t₀)P².

    …

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

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

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

    

    Рис. 1

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

  _n

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

ⁱ⁼¹

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

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

Модель  вычислительной системы  как цепь Маркова

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

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

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

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

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

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

    

    Рис. 2.

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

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

 

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

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

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

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

    X(t₀)=[x₀ x₁ x₂ x₃ x₄] = [1 0 0 0 0],

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

 

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

    Из  состояний S₁,S₂,S₃ процесс с вероятностью 1 возвращается в S₀. Достигнув состояния S₄, процесс навсегда остается в нем. Такое состояние называется поглощающим.

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

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

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

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

    Трудоёмкость алгоритма определяет, в частности, среднее число обращений к файлам.

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

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

    Значение p_h определяет долю переходов в состояние S_h по отношению к всевозможным переходам из состояния S₀ в состояния S₁,...,S₄. Эта доля равна в среднем N_h/N где N_h - среднее число переходов в состояние S_h. 

    Следовательно, р_h = N_h/N, h=1,...,3, р₄=1/N. 

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

    С_ср = С₀N, откуда С₀ = С_срN.

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

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

          Классификация состояний цепей  Маркова

    Введем  классификацию состояний цепи Маркова. Множество всех состояний может быть разбито на непересекающиеся подмножества, или классы: невозвратные и эргодические. Их свойства определяются следующим образом. Если процесс покинул класс первого типа, он никогда в него не возвращается. Если процесс попал в класс состояний второго типа, то он никогда его не покидает. Невозвратное множества мы будем обозначать Т, а эргодическое - Ť. При этом их объединение = S, а пересечение – пустое множество. Если эргодическое множество содержи только одно состояние, то это состояние называется поглощающим. Для такого состояния S, элемент переходной матрицы p_ij должен быть равен 1, следовательно, все остальные элементы соответствующей строки равны 0. Цепь, все эргодические состояния которой являются поглощающими, называется поглощающей цепью.

    Для цепи Маркова с N состояниями, в которой имеют® как невозвратные, так и эргодические множества, структура матрицы вероятностей переходов имеет канонический вид 

(9) 

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

    n-s - количество состояний в эргодическом множестве.

    Матрица W размерности (n-s)x(n-s) определяет динамику эргодических состояний. Поскольку из множества Ť невозможно выйти, то матрица 0 размерности sx(n-s) состоит из нулей.