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

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 2

    Пример 3.1

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

Рис. 3.1. Структура модели

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

    Пусть система содержит  терминалов,  селекторных каналов и  процессоров.

    Если принять допущение, что время решения задачи в процессоре, время обмена информацией между оперативной и внешней памятью и время обдумывания задачи пользователем (время между соседними запросами одного пользователя) представляют собой независимые СВ, имеющие экспоненциальные распределения, то изменение состояния системы во времени может быть описано марковским случайным процессом. В такой модели среднее время реакции M[ ] является функцией параметров .

    При этом первые моменты ФР указанных случайных величин равны соответственно:

 , , .

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

    Тогда число заявок на фазе процессоров равно .

    Граф переходов модели для частного случая и структура фрагмента графа переходов (показаны только исходящие дуги) для общего случая изображены на рис. 3.2.

а)

    Рис. 3.2. Граф переходов (a) и структура фрагмента графа (b)

    (записаны только исходящие интенсивности) Здесь обозначено:

. Исходя из структуры графа переходов, в соответствии с общим правилом можно записать систему линейных алгебраических уравнений (СЛАУ) относительно компонент стационарного распределения вероятностей состояния системы. Написать решение этой системы в явном виде не удается, поэтому в процедуре расчета выходных параметров, осуществляемого с помощью ЭВМ, был предусмотрен блок формирования матрицы коэффициентов системы уравнений и обращение к стандартной программе решения СЛАУ методом Гаусса. Имея значения  компонент стационарного распределения, можно вычислить среднее количество заявок на терминальной фазе , а также среднее время реакции системы

(3.1)


(3.2)

    СЛАУ относительно стационарных вероятностей состояния, а также соотношения (3.1) и (3.2) могут рассматриваться как базисная модель оценки характеристик производительности КТС.

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

1 Чтобы убедиться, что вы поняли, как строится граф, попробуйте его построить, взяв за состояние не (i, j)= (число заявок на фазе терминалов, число заявок на фазе каналов), а

(i, j)= (число заявок на фазе каналов, число заявок на фазе процессоров).

Нарисуйте интенсивности и запишите их для общего случая

2 Попробуйте записать уравнения для какого-то конкретного состояния (i,j).

Представите мне – Вам кружок.

Но считать так плохо, даже если найдем подходящий софт для решения СЛАУ. Допустим, 50 терминалов. Не очень большая система. Треугольный граф 51х51/2 + мелочи ≅ 1350 уравнений с таким же количеством переменных, в сумме равных единице. Анализировать эти переменные (где там узкие места) – отдельная проблема.

Нужны изменения методики инженерного анализа. Аналогичная ситуация и в других инженерных отраслях (см., например, Н.Н. Моисеев, Математические задачи системного анализа, второе изд., гл. 8, Некоторые проблемы автоматизации проектирования, в которой предлагается схема декомпозиции при автоматизированном проектировании сложных систем).

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

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

    Рассмотрим вариант реализации метода агрегирования на примере модели примера 3.1, представленной на рис. 3.1, с использованием параметра связи.

    Пример 3.2. Для модели, структура которой представлена на рис. 3.1, получить расчетные соотношения для выходных параметров в явном виде (не обращаясь к стандартной программе решения системы линейных алгебраических уравнений). Для этого рассмотрим две агрегированные модели, АМ1 и АМ2.

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

    Рис. 3.3. Структура модели АМ1 (a) и граф переходов (б)

    Поскольку процесс относится к классу ПРГ, решение системы уравнений относительно стационарных вероятностей записывается в явном виде:

(3.3)

(3.4)

(3.5)

(3.6)

    Следует отметить, что для расчета , и  по формулам (3.4) - (3.6) кроме  и  необходимо иметь значение параметра связи . Для его нахождения используется вторая агрегированная модель, АМ2.

    Модель АМ2. В модели АМ2 укрупненно представлена фаза терминалов. Ее влияние отражается с помощью обобщенного параметра , представляющего собой среднее число заявок в системе «процессоры-каналы». В качестве состояния в момент  берется  - число заявок на процессорной фазе. Структура модели АМ2 и граф переходов изображены на рис. 3.4 (а) и (б).

Обозначим

(3.7)

    Рис. 3.4. Структура модели АМ2 (a) и граф переходов (б)

    Расчетные соотношения таковы:

(3.8)
(3.9)

    Если обозначить через π_n компоненту стационарного распределения вероятностей числа заявок на процессорной фазе, то

…

       Ошибка в формуле! Как исправить?

(3.10)








(3.11)

    Для анализа АМ2, кроме , надо знать .

В рассмотренном варианте метода декомпозиции параметрами связи между агрегированными моделями АМ1 и АМ2 являются  и .

    Таким образом, система уравнений (3.3) – (3.11) должна решаться совместно. Совокупность соотношений (3.3), (3.4) в сущности, представляет собой уравнение

(3.12)

    Совокупность соотношений (3.8) - (3.11) в сущности, представляет собой уравнение

(3.13)

    Подставляя (3.13) в (3.12), получаем уравнение

где .

(3.14)
(3.15)

    Уравнение (3.14) можно решать, например, методом половинного деления или методом перебора с переменным шагом, или методом простой итерации, взяв в качестве отрезка, на котором находится корень, отрезок

    При  для решения уравнения (3.14) методом половинного деления потребуется 5 раз вычислить значение функции  . Нетрудно видеть, что это составляет порядка 10³ - 10⁴ операций, что соответствует долям секунды (время одновариантного анализа) даже при использовании средних ЭВМ 70-х годов прошлого века. Поэтому такая декомпозиция легко допускает построение зависимостей выходных характеристик от параметров системы (многовариантный анализ).

    В рассмотренном варианте метода декомпозиции параметрами связи между агрегированными моделями АМ1 и АМ2 являются  и .

Итак. простая итерация. Nср⁰ = N/2. Подставляем в модель АМ2. Полученное  подставляем в модель АМ1. Получаем Nср¹. После их сравнения подставляем Nср¹ в модель АМ2. Получаем новое . При их близких значениях

Еще пара моделей – и все.

До свидания

Познавательные статьи:



Техника нижней прямой подачи мяча

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

Стандарт Порядок надевания противочумного костюма

Общеразвивающие упражнения без предметов