Модели вычислительных систем, основанные на концепции состояния - цепи Маркова

                                                                     Содержание

Введение2

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

1.1.Определение цепей Маркова5

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

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

     1.4. Оценка длительности пребывания процесса в множестве невозвратных состояний………...8

     1.5. Исследование динамики цепей Маркова при большом числе шагов………………………...11

 

 2. Практическая часть………………………………...…………………………………………………13

     2.1.  Граф состояний. Матрица переходных вероятностей……...…………………………………13

             2.2. Переходные вектора и график полученные теоретически……………………………………13

              

             2.3. Алгоритм имитационного моделирования динамики ЦМ….………………………………...19

              

             2.4. Результат работы программы……………..………………………..…………………………..20

     2.5. Структурирование матрицы P, и выделение подмножеств T и T~……….…………………28

     2.6. Сравнение теоретически полученной матрицы N с результатом работы программы……..30                              

     2.7. Матрица дисперсий  D и оценка среднеквадратичного отклонения трудоемкости………...30

     2.8. Оценка предельных вероятностей пребывания процесса во множестве Ť…….…..…….…31

  Вывод…………………………………………………………………………………………………..32

  Литература ……………………………………………...……………………………………………..32

  Приложения   ……………………………………………………………………………………….....33

 

 

 

 

 

 

Введение.

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

1. Освоить основные положения  теории конечных цепей Маркова  с дискретным временем.

2. Научится составлять  ЦМ для моделирования вычислительных  систем и анализа динамики  их функционирования.

3. Провести имитационное  моделирование динамики ЦМ.

4. Провести расчет характеристик  производительности вычислительных  систем.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

Формальное определение. Конечная цепь Мария (FiniteMarkovChain - FMC) - это набор элементов:

FMC = {Θ, S, P, X, X₀}.  (1)

Рассмотрим элементы определения (1).

1. Θ - множество моментов времени. Мы будем рассматривать как множество дискретных моментов времени Θ={t_o,t₁,...,t_k,...}, так и непрерывное время,Θ=R, где R -  множество рациональных чисел. 
2. S= {S1,...,S_n}– конечное множество состояний. В каждый момент времени t_k система может находиться только в одном из состоянийS_i. Этот факт мы будем обозначать так:

S(t_k)=S_i, t_kпринадлежит Θ, S_iпринадлежит S

3. P(t_k) = || p_ij(t_k) || - матрица переходных вероятностей.

Состояния в системе изменяются со временем случайным образом. Каждый элемент матрицы p_ij(t_k) показывает вероятность того, что если FMC в моментt_k находилось в состоянии S_i, то в момент t_k+1 она окажется в состоянии S_j:

p_ij(t_k) = Pr{S(t_k+1)=S_j  |  S(t_k)=S_i}.  (2)

При этом основное свойство Марковских процессов состоит в том, что вероятности перехода из S_i в S_j не зависят от предыдущих состояний системы.

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

_n

∑p_ij(t_k) =l для всехi=1,..,n,  t_k ϵ Θ.

^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 такт.

 

 

 

 

 

 

 

 

 

X(t_k+1)

X(t_k)

X(t₀)

P(t_k)

 

1

Рис. 1. Вероятностный автомат с обратной связью

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

_n

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

ⁱ⁼¹

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

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

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

F₀

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],

 

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

 

0	р1	р2	р3	р4
1	0	0	0	0
1	0	0	0	0
1	0	0	0	0
0	0	0	0	1

 

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

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

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

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

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

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

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

Следовательно, среднее число переходов  из состояния S₀ в состояния 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 могут быть, определены экспериментально путем анализа протоколов функционирования вычислительной системы при многократном решении рассматриваемой задачи.

 

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

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