Адрес источника (Sourse Address, SA) – адрес отправителя кадра. Первый бит всегда 0-й. 4 страница

на основе модели характеристик Y = F(X), соответствующих новым значениям X параметров системы.

 

10.2 Модели и методы их исследования

 

10.2.1 Модели

Для представления явления функционирования различных систем, и, в частности, вычислительных, человечество не придумало больше ничего оригинального, чем построение моделей. Модель – предмет, воспроизводящий другой предмет, схема или математическое описание устройства какого-либо физического объекта или процесса, адекватно представляющий объект исследования. Различают два вида моделей: физическую или абстрактную.

В теории вычислительных систем используют преимущественно абстрактные модели – описания объекта исследования на некотором языке. Абстрактность проявляется в том, что компонентами модели являются не физические элементы устройства, а понятия, чаще всего математические. В связи с последними утверждениями модель называют математической. Она имеет форму математической зависимости типа: Y=F(X), где Y={y₁, …, y_M} и X={x₁, …, x_N} – соответственно характеристики и параметры моделируемой и параметры моделируемой системы, а F – a функция, воспроизводимая моделью.

Модели создаются с целью прогнозирования производительности, надежности и других характеристик Y={y₁, …, y_M} вычислительной системы. А состав параметров X={x₁, …, x_N} отражает аспекты организации системы, изучение влияния которых на ее функционирование составляет цель исследования, производимого с помощью модели. Область изменения параметров x_n Є x_n*, n = 1, …, N – называется также областью определения модели. Чем обширнее область определения модели, состав характеристик и параметров, тем универсальнее модель в отношении решаемых с ее использованием задач. Кроме этого важно определить для модели допустимые погрешности оценки характеристик и точность задания параметров. Приводят, например, такие соображения в этом отношении. Если изменения характеристик в пределах 10% несущественны для выбора варианта построения системы, то точность определения характеристик должна составлять ±5%.

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

стик системы. На практике высокая точность воспроизведения характеристик оказывается в пределах малой окрестности какой-либо точки, и только высококачественные модели позволяют обеспечить схождение характеристик в широком диапазоне изменения аргументов x₁, …, x_N, хотя объективно, шансов для этого мало.

Другим важным свойством модели является ее сложность. Сложность определяется сложностью и размерностью вычислений значений характеристик. Под размерностью имеют в виду число величин параметров и количество определяющих модель характеристик. Так, например, если модель описывается двумя характеристиками, зависящими от 5 параметров, а модель - двумя характеристиками, зависящими от 10 параметров, то размерность модели равна 7, а размерность модели -12, и, следовательно, модель рассматривается как более сложная. Сложность вычислений, например, характеристики , оценивается числом операций, приходящихся на одну реализацию функции . В обычном представлении – это число операций, приходящееся на выполнение одной команды программы. Сложность вычислений связана с затратами ресурсов ЭВМ, таких как процессорное время, объем памяти для хранения информации модели, то есть в конечном итоге пропорциональна сложности самой модели. А сложность модели, в свою очередь, определяется сложностью системы.

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

- статистическая выборка , определяющая случайную величину набором значений, имевших место в некоторой реализации случайного процесса;

- закон распределения случайной величины;

- математическое ожидание и дисперсия;

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

 

10.2.2 Марковские методы исследования моделей

 

В начале 900-х годов русский математик А.А. Марков исследовал (а затем и опубликовал результаты) процессы, в которых проявляются зависимости между случайными событиями, требующие при их изучении и количественном анализе вероятностного подхода. Любая система, в том числе и вычислительная, постоянно меняет свои состояния, переходя тем или иным способом в случайные промежутки времени из одного в другое. Сущность процесса заключается в том, что состояние в данный, рассматриваемый момент, полностью суммирует всю предшествующую историю процесса, влияющую на будущее течение этого процесса (рис. 10.2). Последовательность переходов образует цепь событий.

Аналитически марковское свойство определяется записью в виде:

 

, (10.2)

 

означающее, что переход процесса в следующее состояние зависит только от того, в каком состоянии он находится в настоящее время и не зависит от того, в каких состояниях он уже находился, а сам переход характеризуется некоторым значением вероятности его реализации (осуществления).

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

Представим, что мы наблюдаем, процесс со стороны и в момент времени знаем состояние системы и все, что было в прошлом, то есть на отрезке времени . А что случиться с системой в будущем? Точно предсказать мы не можем, так как процесс случайный, но с какой-то долей уверенности мы можем определить вероятность того, что через некоторое время t система окажется в состоянии или сохранит состояние

Таким образом, если процесс марковский, то предсказывать можно, но, только учитывая настоящее состояние системы , забыв всю предысторию. Само состояние зависит от прошлого, но как только оно достигнуто (как толькослучилось новое событие), о прошлом можно забыть. Эту ситуацию формулируют следующим образом «будущее зависит от прошлого только через настоящее».

 

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

В исследованиях различных процессов в вычислительных системах большое значение имеют марковские процессы с дискретным состоянием и непрерывным временем. Процесс с непрерывным временем – это такой, у которого моменты возможных переходов из одного состояния в другое не фиксированы заранее, а неопределенны, случайны, то есть переход может в принципе осуществиться в любой случайный момент времени. Дискретные состояния отмечаются целочисленной последовательностью 0, 1, 2 … Марковские модели поведения системы представляются совокупностями состояний, в которых она может оказаться и вероятностями переходов в эти состояния. Модель изображается в виде графа, вершины которого соответствуют состояниям системы, а ребра (дуги) – переходам между состояниями. Такое представление получило название марковской цепи. Как уже было отмечено выше, цепи могут быть дискретными и непрерывными.

Дискретная марковская цепь определяется:

- множеством состояний ;

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

 

(10.3)

 

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

- вектором начальных вероятностей (начальных распределений) , определяющим вероятности пребывания системы на -том шаге.

На рисунке 10.3 показан граф марковской цепи, определяющий 4 состояния системы , которому соответствует матрица вероятностей переходов.

s₁ s₂ s₃ s₄

 

Решение матричного уравнения сводится к решению системы четырех уравнений:

(10.4)

с учетом условия, называемого нормированием

, (10.5)

и свидетельствующего о том, что всегда существует линейная зависимость между одним уравнением и другими. Для нашего примера получены следующие результаты:

По результатам решения наглядно видно, что распределение вероятностей состояний имеет стационарный характер, то есть распределение вероятностей процессов «нечувствительно» к изменениям времени для любых значений аргументов.

В общем случае процесс можно интерпретировать так, что начальное состояние какой-то системы (устройства) определяется вектором начальных вероятностей . Следующее состояние определяется i -той строкой матрицы вероятностей переходов P – процесс переходит в состояние с вероятностью . Из состояния процесс переходит в состояние с вероятностью и т.д. В результате n шагов процесс попадает в состояния с вероятностями , соответственно.

Для теории вычислительных

систем интерес представляют поглощающие и эргодические марковские цепи.

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

Рисунок 10.4 иллюстрирует граф марковской поглощающей цепи. Поглощающее состояние цепи отмечено как , с вероятностями попадания в него .

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

 

(10.6)

 

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

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

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

- вероятности пребывания процесса в состояниях ;

- относительные частоты попадания процесса в состояния ;

- доля времени, которую процесс проводит в каждом из состояний.

В качестве дополнительных характеристик эргодических цепей используются математическое ожидание, и дисперсия времени (числа шагов) первого попадания в состояние из состояния и предельная корреляция (в пределах от -1 до +1) числа попаданий в состояния и , то есть взаимозависимость числа попаданий и сопутствующих этому процессу условий.

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

Кроме отмеченной выше задачи, эргодические цепи используются для моделирования взаимодействия устройств вычислительной системы с задачами, поступающими в нее на обработку.

 

10.2.3Потоки событий

Потоком событий называется последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени. Например, поток схода снежных лавин с гор весной, поток вызовов на телефонной станции и т.д. Этот процесс можно наглядно изобразить в виде ряда точек на оси времени 0-t, причем положение их совершенно случайно.

Важной характеристикой потока событий является его интенсивность λ – среднее число событий, приходящееся на единицу времени. Интенсивность может быть как постоянной величиной, так и переменной, зависящей от времени t.

Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: стационарен (неизменяем во времени и все требования, в конце концов, будут обслужены), ординарен (обычный, рядовой) и без последствия (будущее совершенно не связано с прошлым). Название простейший сопоставлено с тем, что процессы, связанные с такими потоками, имеют наиболее простое математическое описание.

Для простейшего потока с интенсивностью интервал между событиями имеет, так называемое, показательное распределение (см. рис. 10.6)

с плотностью

( >0) (10.7)

 

Эту зависимость (это событие) можно прокомментировать следующим образом. Пока в системе задач не так много интенсивность их обработки высока, тоесть промежутки между обработками задачи не очень большие - интенсивность интервалов высока (см. график). Но со временем система начинает «захлебываться», задачи обрабатываются (решаются) дольше, число промежутков между задачами становится все меньше - их интенсивность уменьшается, и этот процесс подчиняется, как мы видим, экспоненциальному закону. Величина в формуле (9.7) называется параметром показательного закона. Если интервал между событиями меньше или равен , то интервал называют коротким.

, (10.8)

Для простейшего потока характерно, что короткие интервалы между событиями более вероятны, чем длинные; около 63% промежутков времени между событиями имеют длину меньше средней, равной 1/ λ. Таким образом, предположение о действии на вычислительную систему простейшего потока заявок создает более тяжелые условия для ее работы, чем при других потоках, что позволяет считать результаты анализа вычислительной системы для простейших потоков заявок более надежными.

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

, (10.9)

 

то есть для простейшего потока элемент вероятности равен интенсивности потока, умноженной на длину элементарного участка времени. Например, на рисунке 10.5 выбран на оси 0-t простейший (элементарный) участок времени ∆t.

Элемент вероятности события из-за отсутствия последействия совершенно не зависит от того, сколько событий и когда появились ранее.

 

10.2.4 Уравнения Колмогорова

 

Теория вычислительных систем широко использует различный математический аппарат. Например, при анализе марковских цепей используются системы дифференциальных уравнений, названных по фамилии автора уравнениями Колмогорова. Для иллюстрации конкретного применения этого математического аппарата рассмотрим ситуацию, связанную с возможными состояниями некоторого технического устройства. Пусть в исходной позиции находится техническое устройство, состоящее из двух узлов, каждый из которых может в случайный момент времени выйти из строя, после чего немедленно начинается ремонт узла, продолжающийся заранее неизвестное, случайное время.

Можно обозначить следующие возможные состояния такого устройства:

S0 – оба узла исправны;

S1 – первый узел ремонтируется, второй исправен;

S2 – второй узел ремонтируется, первый исправен;

S3 – оба узла ремонтируются.

При анализе случайных процессов с дискретными состояниями удобно пользоваться графическим представлением этих процессов в виде графов, в которых состояния системы изображаются окружностями, а возможные переходы из состояния в состояние – соединяющими окружности стрел-

ками (дугами), как показано на следующем рисунке 10.7. Стрелка, направленная от кружка, обозначенного как S0 к кружку с обозначением S1, означает, что в системе произошел отказ первого узла; стрелка обратного направления, из S1 в S0 означает, что ремонт первого узла закончен и система вернулась в первоначальное состояние. Обозначения остальных стрелок аналогично. Обозначим через интенсивность ремонта i-го узла.

Вероятностью i-го состояния называется вероятность Pi (t) того, что в момент времени t система будет находиться в состоянии Si. Очевидно, что для любого момента сумма всех вероятностей состояний равна единице:

(10.10)

Имея в своем распоряжении размеченный граф состояний, можно найти все вероятности состояний Pi(t) как функции времени. Для этого составляются и решаются уравнения Колмогорова – особого вида дифференциальные уравнения, в которых неизвестными функциями являются вероятности состояний.

Попытаемся составить подобные уравнения для нашей условной системы и ее состояний. Положим, что в момент времени t система будет находиться в состоянии S0, а вероятность возникновения этого состояния P0(t). Через некоторое, очень малое, приращение времени, равное Δt система остается в том же состоянии S0, а вероятность этого события будет при этом равна P0 (t + Δt).

Произойти это может тремя способами: либо в момент времени t система уже была в состоянии S0, а за время Δt не вышла из него; либо в момент времени t система была в состоянии S1, а за время Δt перешла из него в состояние S0; либо в момент t система была в состоянии S2, а за время Δt перешла из него в S0.

В первом случае, вероятность нахождения системы в состоянии S0 в момент времени t равна P0(t). Суммарный поток событий, выводящий систему из состояния S0, будет простейший, с интенсивностью (λ1 + λ2), а вероятность того, что система за время Δt выйдет из состояния S0, равна (λ1 + λ2) Δt. Тогда вероятность невыхода системы из состояния S0 за время Δt будет равна 1 - (λ1 + λ2)Δt. Отсюда вероятность первого случая будет равна P0(t) [1 - (λ1 + λ2)Δt].

Вероятность второго варианта будет равна μ1Δt P1(t), третьего варианта - μ2Δt P2(t).

Складывая вероятности всех вариантов, получим

 

(10.11)

 

Раскроем квадратные скобки, перенесем P0(t) в левую часть и разделим обе части на Δt:

(10.12)

 

Если в этом выражении Δt будет стремиться к нулю, то получим уравнение вида:

 

(10.13)

 

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

В соответствии с правилом составления уравнений Колмогорова для рассматриваемой системы, уравнения будут выглядеть следующим образом:

,

 

,

(10.14)

,

 

.

 

Чтобы решить эти уравнения и найти вероятности состояний, в которых может оказаться система, необходимо задаться некоторыми начальными условиями.

Например, что будет происходить с вероятностями состояний, если t будет стремиться к бесконечности? Будут ли Pi(t) стремиться к каким-то пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний.