Стохастическая сетевая модель. Граф передач и матрица вероятностей передач. Экспоненциальная стохастическая сетевая модель

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

В конфигурации стохастической сети отражаются:

а) структура вычислительной системы;

б) последовательность выполняемых вычислительных этапов обработки информации.

Для простейших сетей в теории массового обслуживания принято:

а) входной поток l является простейшим;

б) длительность обслуживания n подчиняется экспоненциальному закону:

,

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

В качестве примера рассмотрим следующую вычислительную систему (рис.1.8), в которую входят следующие подсистемы: S₁ - процессор; S₂ – быстродействующее ВУ (например, накопитель на магнитных дисках (НМД)); S₃ – быстродействующее ВУ (например, накопитель на магнитных лентах (НМЛ)); S₄ - группа однотипных медленно действующих ВУ(например, принтеры); S₅ - канал передачи данных.

Рис. 1.8

В такой стохастической сети предполагается, что отсутствует последействие. Это означает, что все последующие события могут зависеть только от текущего события и не зависят от предшествующих событий. Такой процесс называется марковским. Он характеризуется множеством состояний S₁ . . . S₅ и матрицей вероятностей перехода в эти состояния. Вычислительный процесс всегда начинается с момента поступления заявки в процессор (состояние S₁). Инициализация обращения к любому из устройств осуществляется только процессором. Связи между отдельными СМО устанавливаются в результате анализа порядка следования этапов обработки заявок. Для отображения вычислительного процесса используется направленный граф передач. Вершины графа соответствуют состояниям вычислительного процесса S₁ , S₂, … S_n, а дуги между вершинами указывают на связи между отдельными СМО (переход системы из одного состояния в другое). Дуги взвешиваются вероятностями перехода. Если система может перейти из одного состояния в одно из нескольких состояний, то возникает необходимость оценки вероятностей переходов. При этом строится матрица вероятностей передач.

Этап – процесс, завершающийся выходом заявки из процессора.

Пусть имеем систему, модель которой в укрупненном представлении имеет вид, представленный на рис.1.9, где: S₁ –процессор; S₂, S₃ – быстродействующие устройства; S₄ – медленнодействующее устройство (например, принтер); S₅ – селекторный канал; S₀ – источник запросов.

 

Рис. 1.9

Граф вероятностей передач и матрица вероятностей передач представлены на рис. 1.10.

 

Рис. 1.10

Здесь указаны вероятности перехода p_ji из j -ой подсистемы в i-ю. S₀ - источник заявок (генератор заявок) в системе. Таким образам, число подсистем в системе (n+1), и размерность матрицы вероятностей передач соответственно тоже (n+1).

Рассмотрим, как оценивается вероятность перехода p_ji из j -ой подсистемы в i -ю. Для этого возьмём две вершины графа S_j и S_i (рис.1.11) и тогда p_ji можно определить в виде

,

где - весь суммарный (средний) поток, который исходит из подсистемы S_j; - средний поток заявок, который из подсистемы S_j поступает в S_i; входной и выходной потоки равны.

_i

Рис.1.11

 

Рассмотрим простейший пример расчета для системы на рис.1.9. Пусть S₂ и S₃ - внешние накопители. Имеется N файлов, которые распределены между накопителями S₂ и S₃. К каждому файлу при решении средней задачи должно быть осуществлено D_j обращений (j = 1, N). При каждом полном решении задачи на выходе системы появляется обслуженный запрос, который направляется к S₀. Пусть также к внешнему устройству S₄ при обслуживании средней задачи осуществляется d обращений.

Общее количество обращений к файлам D определяется в виде

D =

На выходе S₁ заявка появляется (D + d + 1) раз.

Матрица вероятностей передач имеет вид, представленный на рис. 1.12.

Рис.1.12.

Значения вероятностей передач определяются в следующем виде:

P₀₁ = 1; P₂₅ = 1; P₃₅ = 1; P₅₁ = 1; P₄₁ = 1;

P₁₀ = ; P₁₄ = ; P₁₂ = ; P₁₃ = .

Суммы вероятностей передач по строкам должны удовлетворять соотношению

P₁₀ + P₁₂+P₁₃+P₁₄ =1.

§1.6. Разомкнутые и замкнутые стохастические сети. Параметры стохастических сетей

Для описания вычислительных систем используют следующие понятия:

а) разомкнутые стохастические сети (информационные системы оперативной обработки запросов, продажа железнодорожных билетов и т.п.);

б) замкнутые стохастические сети (работа вычислительной системы в многозадачном (пакетном) режиме). Эти системы не имеют чётко определённого входного потока запросов l; в данном случае источник запросов представляется как фиктивный в связи между выходом и входом.

 

 

Рис. 1.16

Параметры стохастических сетей (исходные данные для расчёта исследуемой вычислительной системы):

1. Число СМО (S₁, S₂, . . . ,S_n ) - (n + 1).

2. Число каналов K₁, K₂, . . . ,K_n в подсистемах S₁, S₂, . . . ,S_n.

3. Матрица вероятностей передач P=[p_ji ]; .

4. l₀ - средняя интенсивность источника заявок для разомкнутых сетей.

5. M - коэффициент многозадачности для замкнутых сетей.

6. n₁, n₂, . . . ,n_n - длительности обслуживания, характеризующие задержки в подсистемах S₁, S₂, . . . ,S_n.