2_laboratornaya_rabota_po_Peregude

20 Февраль 2014 →

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ОБНИНСКИЙ ИНСТИТУТ АТОМНОЙ ЭНЕРГЕТИКИ – филиал

Федерального государственного автономного образовательного учреждения высшего профессионального образования

«Национальный исследовательский ядерный университет «МИФИ»

(ИАТЭ НИЯУ МИФИ)

Факультет Кибернетики

Кафедра Компьютерных Систем, Сетей и Технологий

Лабораторная работа № 2.

«Моделирование открытой марковской сети массового обслуживания методом Монте-Карло»

Выполнил:

Азаркин И.П. Группа ВТ-3-С08Проверил: проф. Перегуда А.И.

Обнинск

2013

Цель работы:

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

Теоретическая часть

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

Узел сети i представляет собой систему массового обслуживания из ci {1, 2, …} идентичных приборов и накопителя заявок емкости ri {1, 2, …} заявок. Примем, что 1 ci ∞, ri - ∞, i – 1,M. Поскольку все заявки одного типа, то быстродействие прибора в узле i полностью описывает Bi(x), x 0, - функция распределения длительности обслуживания заявки в этом узле, а для экспоненциального узла i

Где 1/i, 0 1/i — средняя длительность обслуживания в узле i, i 1,M.

Нужно также задать дисциплину обслуживания, т.е. порядок обработки заявки в узле от момента ее поступления в узел до момента ухода из узла. Для определенности примем, что дисциплина обслуживания во всех узлах — «пришедший первым обслуживается первым» (FCFS).

Сделаем также следующие три естественных предположения:

Приборы узла не могут простаивать, когда в очереди этого узла имеются заявки;

Заявки не покидают узел необслуженными;

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

Эти три предположения часто называют законом сохранения работы.

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

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

Сеть состоит из множества M = {1, 2, …, M} узлов, в которых размещены обслуживающие приборы и накопители заявок. Пусть узел 0 описывает «внешнюю среду», с которой взаимодействует сеть, а M0 = M{0} - расширенное множество узлов. С физической точки зрения узел 0 можно разделить на два: узел a, объединяющий все источники заявок, и узел b, объединяющий все стоки, так что Mab - M{a}{b} - также расширенное множество узлов. Иногда через 0 обозначают узел a, а через M +1 —узел-сток b.

Сеть без источников и стоков называется замкнутой, в противном случае — разомкнутой. Если все заявки одного типа, то есть называется однородной, в противном случае — неоднородной.

Примем, что на открытую сеть из внешней среды поступает пуассоновский поток с постоянной интенсивностью λ0. Пусть θij — вероятность того, что после завершения обслуживания в узле и независимо от ее предшествующей траектории заявка мгновенно переходит в узел j, j M0. i, i M.

Рассмотрим открытую сеть со стохастической маршрутной матрицей

T = (1, …, M)

Пусть— вероятность направления вновь поступившей заявки в узел их

физических соображений. Тогда T = (1, …, M), . j, j – 1,M, a θ00 - 0

соответствующий стохастический вектор.

Пусть далее θi0 – 1 - - вероятность ухода некоторой заявки из сети сразу после завершения ее обслуживания в узле i, i = 1,M, а вектор соответствующий неотрицательный вектор.

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

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

Здесь все векторы — M-мерные столбцы, а переходами между внутренними узлами сети управляет подматрица

являющаяся сужением матрицна множествовнутренних узлов.

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

Блуждание заявки по открытой сети начинается в момент ее поступления из источника в некоторый узел i0, для которого i0 0, может проходить, причем неоднократно, через любые узлы из множества Mi, а затем заканчивается на шаге n в момент ухода из узла in, для которого in 0, в сток b. Все маршруты имеют вид i0, i1, …, in, где i0, i1, …, in M.

Выполнение работы:

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

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

Работа консольного приложения (Рис.1):

Рис.1 Работа открытой системы.

Из данного приложения видно, что происходит поступление заявок в динамическом режиме на 4 обрабатывающих блока. На экран выводятся, очереди с количеством заявок и время для каждой заявки до конца обслуживания ее в определенном блоке. В программе имеются ограничение на кол-во заявок в очереди = 5 заявок, остальные получают отказ. После обработки заявки в определенном блоке она имеет несколько вариантов дальнейшей «жизни». За счет случайного распределения, заявка получает несколько вероятностей связанных с тем или иным путем в системе (направления по блокам). (Рис.2)

Блок 1

λ"

Блок 3

Блок 2

Блок 4

λ

Рис.2 Схема работы открытой системы.

Вывод:

В ходе выполнения лабораторной работы были изучены:

- Метод моделирования открытой марковской системы массового обслуживания.

- Моделирование работы и характеристик системы.

- Создание динамического программного обеспечения, реализующего открытую систему массового обслуживания.




See also:
Для студента
Похожие записи

Комментарии закрыты.