Лабораторная работа №3
ОПРЕДЕЛЕНИЕ ХАРАКТЕРИСТИК РАЗОМКНУТЫХ СТОХАСТИЧЕСКИХ СЕТЕЙ
1. Цель работы
Исследование методов моделирования вычислительных систем при различных режимах обработки данных на основе аппарата разомкнутых стохастических сетей. В результате выполнения работы студент знакомится с принципами построения математических моделей ВС на основе использования теории массового обслуживания и получает навыки по расчету основных характеристик вычислительного процесса и параметров основных блоков ВС.
2. Задание
2.1. Изучить основные параметры и характеристики разомкнутых стохастических сетей.
2.2. Исследовать характеристики модели ЭВМ общего назначения при различных параметрах потока заявок.
2.3. Исследовать основные факторы, влияющие на характеристики состояния разомкнутой стохастической сети, и связь этих характеристик с параметрами моделируемых устройств и характеристиками потока заявок.
3. Рабочее место
Работы выполняются на ПЭВМ. При выполнении работы используется программный комплекс для исследования моделей систем обработки данных.
4. Теоретическая часть
4.1. Моделирование вычислительных сетей с помощью
стохастических сетей
Любую вычислительную сеть можно рассматривать как совокупность устройств, процессы функционирования которых являются процессами массового обслуживания. Отдельные функциональные элементы ВС, такие как процессор, оперативная память, устройство ввода-вывода и др., представляются в виде соответствующих систем массового обслуживания (СМО) . Совокупность взаимосвязанных СМО называется стохастической сетью. Конфигурация стохастической сети отражает как структуру ВС, так и последовательность этапов вычислительного процесса в пределах этой структуры.
Среди СМО различают одноканальные и многоканальные системы. Одноканальная СМО характеризуется наличием только одного канала (прибора) и очередью поступающих заявок. Многоканальная СМО содержит K однотипных каналов, среднее время обслуживания заявок в каждом из которых обязательно одинаковое. Из поступающих заявок в многоканальной СМО образуется одна очередь, из которой заявки могут обслуживаться в любом свободном канале системы. Примером одноканальной СМО может служить подсистема «процессор — оперативная память», а мультиплексный канал с подключенными к нему устройствами ввода-вывода представляются в виде многоканальной СМО.
Для описания ВС используют разомкнутые и замкнутые стохастические сети. Данная лабораторная работа посвящается разомкнутым стохастическим сетям.
Для разомкнутой сети характерно, что интенсивность источника заявок не зависит от состояния сети. Источник входящего потока заявок рассматривается как СМО с бесконечным числом заявок. Разомкнутые сети применяются в качестве моделей систем, в которых может находится на обработке переменное число заявок, например систем с разделением времени.
Рис. 3.1. Пример разомкнутой стохастической сети
Для простоты счета характеристик сетей делают допущение, что входящие потоки являются простейшими и длительности обслуживания запросов в различных системах сети распределены по экспоненциальному закону. Такие сети называются экспоненциальными стохастическими сетями.
На рис.3.1. показан пример замкнутой стохастической сети, характеристики которой определяются в данной лабораторной работе. Изображенная сеть моделирует ВС, состоящую из центрального ядра (процессор – оперативная память) — , двух селекторных каналов — и одного мультиплексорного канала . Многоканальная система моделирует работу мультиплексорного канала с K устройствами ввода-вывода (УВВ). Каждая СМО имеет свою очередь заявок на обслуживание неограниченной длины.
4.2. Параметры разомкнутых стохастических сетей и условия стационарного режима
Разомкнутая стохастическая сеть определяется следующей совокупностью параметров:
1. Числом n систем массового обслуживания .
2. Числом каналов (обслуживающих приборов) входящих в системы . Для одноканальных систем .
3. Матрицей вероятностей передач , где – вероятность передачи заявки из системы в систему .
4. Интенсивностью входного потока заявок от внешнего источника заявок .
5. Средней длительностью обслуживания заявок в системах сети .
Порядок циркуляции заявок в сети отображается с помощью направленного графа передач. Вершины такого графа соответствуют СМО, а дуги задают связи между ними. Каждой дуге ставится в соответствие вероятность перехода . Для разомкнутой сети, показанной на рис.3.1., граф передачи изображен на рис.3.2. Поскольку предполагается, что ВС работает без потерь, то должно соблюдаться равенство и сумма вероятностей всех переходов должна равняться единице . Это означает, что сумма вероятностей переходов каждой строки матрицы переходов P равна единице.
В дальнейшем будем рассматривать стационарный режим разомкнутых экспоненциальных стохастических сетей.
В стационарном режиме вероятностные характеристики сети не изменяются во времени. На практике допущение о стационарности можно распространить лишь на ограниченные по продолжительности периоды работы ВС. Каждый период заканчивается изменением каких-то исходных условий: характера решаемых задач, числа взаимодействующих с системой пользователей, коэффициента мультипрограммирования, конфигурации ВС и т.п. Существование стационарного режима разомкнутой сети связано с существованием стационарных режимов в ее системах. Условие существования стационарного режима в отдельной системе массового обслуживания определяется числовыми значениями загрузки. Под загрузкой одноканальной системы понимается относительная доля времени, в течение которого канал занят обслуживанием поступающих требований. Значение определяется произведением , где
— интенсивность входящего потока;
— среднее время обслуживания заявок в системе .
Для многоканальной СМО со средним временем обслуживания в одном канале произведение определяет не загрузку системы, а среднее число занятых каналов . Для нахождения загрузки каждого из каналов многоканальной системы нужно разделить среднее число занятых каналов на общее число каналов в системе . Таким образом, как для одноканальной, так и для многоканальной системы загрузка определяется в виде
(3.1)
Для системы стационарный режим существует, если загрузка системы меньше единицы
(3.2)
Поскольку , (где – коэффициент передачи для системы , который определяет среднее число этапов обслуживания в системе обслуживания в расчете на одну заявку, поступающую от внешнего источника причем ), то путем постановки этого выражения в формулу (3.2) и некоторых преобразований получаем следующее неравенство
, (3.3)
Данное неравенство налагает ограничения сверху на интенсивность потока, поступающего в сеть. Следовательно, стационарный режим будет существовать в разомкнутой сети, если выполняется условие
, (3.4)
4.3. Состояние сети и вероятности состояний
При определении характеристик сети используется понятие ее состояния. Под состоянием сети понимается вектор ( ), характеризующих распределение заявок, находящихся в сети, среди систем . Состояние ( ) соответствует случаю, когда в системе находится заявок, в системе находится заявок и в системе — заявок.
В стационарном режиме вероятность состояния разомкнутой экспоненциальной сети определяется произведением вероятностей состояний составляющих сеть систем, причем вероятности состояний систем определяются для случая, когда каждая из систем функционирует независимо. Пусть – вероятность того, что в системе находится заявок. Тогда вероятность состояния сети определяется как:
, (3.5)
Правая часть этого равенства получена путем некоторых преобразований исходного уравнения. Для выражения (3.5) составляющая
, (3.6)
определяет среднее число занятых каналов СМО. Через параметр обозначена следующая зависимость
, (3.7)
Выражение (3.8) характеризует вероятность того, что многоканальная СМО свободна от обслуживания заявок. Для одноканальной СМО . Уравнение (3.5) используется для расчета вероятностей состояний сети.
4.4. Характеристики систем в сети
На основе вероятностей состояний определяются все остальные характеристики сети: средние длины очередей заявок , ожидающих обслуживания в системах ; среднее число заявок , пребывающих в каждой из систем сети; средние времена ожидания и средние времена пребывания заявок в системах .
Для нахождения характеристик и многоканальных систем в теории массового обслуживания получены следующие формулы:
а) среднее число заявок, ожидающих обслуживание в системе , т.е. средняя длина очереди:
; (3.9)
б) среднее число заявок в системе равно сумме средней длины очереди и среднего числа занятых каналов:
; (3.10)
в) среднее время ожидания заявки в очереди:
; (3.11)
г) среднее время пребывания заявки в системе:
; (3.12)
4.5. Характеристики сети
Теперь необходимо определить характеристики сети в целом:
а) среднее число заявок, ожидающих обслуживания в сети:
; (3.13)
б) среднее число заявок, пребывающих в сети:
; (3.14)
Каждая заявка поступает на обслуживание в систему сети в среднем раз. Поэтому среднее время ожидания (пребывания — u) заявки в сети равно сумме взвешенных по коэффициентам передачи средних времен ожиданий (пребывания — ) заявок в каждой из систем :
; (3.15)
; (3.16)
Для одноканальных СМО формулы (3.9) – (3.12) значительно упрощаются, так как , , .
Пример расчета характеристик разомкнутых сетей представлен в программе моделирования стохастических сетей.
Таблица 3.1
Исходные данные для расчета характеристик разомкнутых сетей
№ варианта
1 0,2 0,2 0,15 0,1 0,2 0,22 0,28 0,3 0,1 5
2 0,45 0,2 0,15 0,12 0,12 0,27 0,3 0,38 0,1 6
3 0,6 0,2 0,2 0,18 0,25 0,1 0,15 0,5 0,3 15
4 0,8 0,3 0,2 0,2 0,05 0,45 0,21 0,29 0,05 20
5 0,1 0,3 0,3 0,2 0,01 0,38 0,15 0,46 0,01 10
6 0,6 0,3 0,2 0,16 0,1 0,5 0,3 0,1 0,1 5
7 0,4 0,2 0,1 0,08 0,28 0,3 0,22 0,2 0,6 20
8 0,2 0,15 0,15 0,08 0,4 0,15 0,15 0,3 0,3 10
9 0,2 0,2 0,15 0,1 0,1 0,32 0,25 0,33 0,15 5
10 0,4 1,1 0,45 0,1 0,4 0,27 0,2 0,13 0,031 3
11 0,6 0,8 0,1 0,14 0,25 0,4 0,23 0,12 0,1 10
12 0,9 0,3 0,1 0,2 0,2 0,3 0,25 0,25 0,1 5
13 0,8 0,2 0,3 0,1 0,3 0,2 0,15 0,35 0,2 12
14 0,7 0,3 0,2 0,16 0,05 0,27 0,45 0,23 0,01 5
15 0,1 0,9 0,1 0,18 0,07 0,23 0,43 0,27 0,3 20
16 0,7 0,15 0,15 0,08 0,4 0,05 0,25 0,3 0,4 17
17 0,14 0,3 0,3 0,2 0,01 0,38 0,15 0,46 0,009 4
18 0,2 0,3 0,2 0,16 0,1 0,5 0,3 0,1 0,3 19
19 0,5 0,2 0,1 0,03 0,38 0,35 0,12 0,15 0,6 14
20 0,7 0,25 0,45 0,09 0,4 0,13 0,15 0,32 0,4 12
21 0,7 1,1 0,1 0,1 0,5 0,1 0,2 0,2 0,1 10
22 0,5 0,2 0,15 0,8 0,4 0,2 0,2 0,2 0,6 15
23 0,8 0,2 0,45 0,008 0,3 0,1 0,2 0,4 0,3 20
24 0,2 0,4 0,25 0,2 0,05 0,25 0,1 0,6 0,1 5
25 0,4 1,1 0,3 0,09 0,15 0,15 0,2 0,5 0,3 12
5. Порядок выполнения работы
5.1. Изучить теоретический материал по разомкнутым стохастическим сетям.
5.2. Определить свои исходные данные для расчета характеристик разомкнутой стохастической сети (рис.3.1.) (в соответствии с вариантом из табл.3.1.).
5.3. С помощью программы моделирования стохастических сетей рассчитать характеристики разомкнутой сети и систем этой сети:
— среднее число заявок, ожидающих обслуживания в сети;
— среднее число заявок, пребывающих в сети;
— среднее время ожидания заявок в очереди;
— среднее время пребывания заявки в системе;
— среднее время ожидания заявок в сети;
— среднее время пребывания заявок в сети;
— среднюю длину очереди заявок в системе;
— среднюю длину очереди заявок в сети.
Результаты оформить в виде таблиц.
5.4. Определить, существует ли стационарный режим для рассматриваемой сети.
5.5. Изменяя исходные данные относительно заданных, провести с помощью указанной выше программы эксперименты по определению зависимостей времени ожидания W (пребывания U) заявки в сети:
— от числа каналов в многоканальной СМО;
— от длительности обслуживания заявок многоканальной СМО;
— о длительности обслуживания СМО, моделирующей центральное ядро.
Результаты оформить в виде таблиц и графиков.
5.6. Сделать выводы по полученным графикам и занести их в отчет.
6. Отчет
6.1. Исходные данные для расчета характеристик разомкнутой стохастической сети.
6.2. Рисунок расчитываемой замкнутой стохастической сети (см. рис.3.1).
6.3. Матрица вероятностей передач сети.
6.4. Таблица характеристик систем сети.
6.5. Таблица характеристик сети.
6.6. Таблицы и графики полученных зависимостей.
6.7. Выводы по графикам.
7. Контрольные вопросы.
7.1. Что такое экспоненциальные стохастические сети?
7.2. Какими параметрами оценивается стохастическая сеть?
7.3. Что такое разомкнутая стохастическая сеть, и в каких случаях ее используют для моделирования вычислительного процесса?
7.4. Что такое стационарный режим для разомкнутой сети?
7.5. Какими характеристиками описываются системы в стохастической разомкнутой сети и на основании чего они расчитываются?
7.6. Какими характеристиками описывается стохастическая разомкнутая сеть?
7.7. Каким образом отображаются параметры моделируемых устройств на характеристики систем в исследуемой модели?
