Лекции по "Схемотехнике"

1. Аналитические модели, проблемы построения, достоинства.

Аналит-кие методы исслед-я ВС сводятся к построению матем-ких моделей, описывающих физ-кие св-ва элементов системы матем-ми объектами и отн-ями между ними. При испол-ии аналит-их методов оператор , устанавл-щий зав-сть м/у харак-ми и параметрами системы, представляется совок-ью матем-их выражений. В таких моделях, называемых аналитическими, зав-сть м/у харак-ми и параметрами м.б. представлена в явной форме в виде выражения , решенных отн-но искомых величин, или в неявной форме в виде урав-ий , связывающих харак-ки и параметры.

Св-ва элементов  и систем удается представить  в аналит-ой форме, если принимаются опред-ные допущения о св-вах и поведении описываемых объектов: незав-сть одних факторов от других, линейность нек-ых зав-стей, мгновенность переходов м/у состояниями и т.д. Если допущения соотв-ют реальности, модель хорошо воспр-ит завис-ть м/у харак-ми и параметрами.

Проблемы  построения:

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

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

(+):

1. Зависимости, полученные аналитическими методами, являются строго доказанными и их достоверность не вызывает сомнений (с учетом принятых при выводе допущений). Поэтому аналитические зависимости используются в качестве своеобразных эталонов, с которыми сопоставляются результаты, получаемые другими методами.
2. Аналитические модели имеют большую познавательную ценность. Аналитические зависимости определяют характеристики для всей области значений параметров и несут в себе информацию о поведении соответствующих систем при любых сочетаниях параметров. На основе аналитических моделей легко определяются экстремальные и предельные значения характеристик и оцениваются эффекты от изменения параметров.
3. Аналитические модели характеризуются малыми объемами вычислений.

 

 

 

 

 

 

 

 

 

 

2. Простейший и Пуассоновский потоки.

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

У простейшего потока интервалы времени между двумя последовательными заявками – независимые случайные величины с функцией распределения:  

Такое распределение называется экспоненциальным (показательным) и  имеет плотность     

математическое ожидание длины интервала 

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

Простейшие потоки заявок обладают следующими особенностями:

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

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

3. Интервал времени между произвольным моментом времени и моментом поступления очередной заявки имеет экспоненциальное распределение с таким же математическим ожиданием , что и интервал времени между 2мя последовательными заявками.

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

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

Пуассоновский поток. Пуассоновским потоком называется ординарный поток заявок с отсутствием последействия, у которого число заявок, поступивших в систему за промежуток времени , распределено по закону Пуассона:

  , где  - вероятность того, что за время в систему поступит точно заявок; - интенсивность потока заявок.

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

Распределение Пуассона дискретно. Стационарный пуассоновский  поток является простейшим. В распределении  Пуассона длительности интервалов между 2мя последовательными заявками –  это случайные величины с экспоненциальным распределением.

 

 

 

 

 

 

 

 

 

 

3. Вероятностные модели процессов. Определение и описание марковской модели.

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

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

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

Марковские  модели.

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

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

Рис. Пример графа состояний

Описание  Марковской модели. Для описания поведения системы в виде Марковской модели следует определить понятие состояния системы; выявить все состояния, в которых может находиться система; указать, в каком состоянии находится система в начальный момент; построить граф состояний, т.е. изобразить все состояния и возможные переходы из состояния в состояние – стрелками, соединяющими состояния (на рис. выделено 5 состояний); разметить граф, т.е. для каждого перехода указать интенсивность потока событий, переводящих систему из состояния в состояние :

       

где - вероятность перехода из состояния в состояние за время от до .

Для стационарных Марковских процессов интенсивности  переходов не зависят от времени: , тогда .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Марковская цепь (МЦ). Определение цепи в непрерывном и дискретном времени.

В классе марковских процессов выделяют процессы с дискретными  состояниями, называемые МЦ. Когда мн-во состояний процесса конечно, марковскую цепь называют конечной. Конечная МЦ м.б. определена в непрерывном или дискретном времени. В 1ом случае переходы процесса из одного состояния в другое связываются с произвольными моментами времени и цепь называют непрерывной; во 2ом – только в фиксированные моменты времени, обозначаемые порядковыми номерами и цепь называется дискретной.

Дискретная МЦ определяется:

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

МЦ м.б. представлена графом, вершины которого соответствуют  состояниям цепи, а дуги ненулевым  вероятностям переходов. На рис. (а) представлен граф МЦ, имеющей 5 состояний и вектор начальных вероятностей . Вероятности переходов показаны на дугах графа. Рис.Графы МЦ:а – дискретная,б – непрерывная

 

 

 

5. Поглощающие и эргодические цепи, их использование.

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

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

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

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

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

6. Однородная непрерывная марковская цепь, вероятности состояний, уравнения равновесия.

Однородная  непрерывная марковская цепь – это  марковская цепь, поведение которой  в любое время характеризуется  одним законом. Определим интенсивность  переходов по формуле: q_ii=lim_(∆t→0)(p_ii(∆t)-1)/∆t, и по формуле: q_ij=lim_(∆t→0)p_ij(∆t)/∆t, где q_ij(∆t) – вероятность перехода процесса из состояния s_i в состояние s_j за время ∆t. Теперь составим матрицу интенсивности переходов: , ; ∑^k_j=1q_ij=0, i=1,…,k.

Вероятность состояний (финальное распределение) α={α1,…,αk} (находится вследствие решения системы уравнений равновесия), где α1,…, αк – вероятность пребывания процесса в состояниях s1,…,sk.

Уравнения равновесия:

,     ;

. 

Учитывается, что  в каждом состоянии входящий поток  равен исходящему потоку.