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

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

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

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

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

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

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

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

,

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

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

Рис. 1.8

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

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

Рис. 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; входной и выходной потоки равны.

Рис.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. Разомкнутые и замкнутые стохастические сети. Параметры стохастических сетей