Министерство образования и науки российской федерации обнинский институт атомной энергетики – филиал icon

Министерство образования и науки российской федерации обнинский институт атомной энергетики – филиал


Скачать 24.09 Kb.
НазваниеМинистерство образования и науки российской федерации обнинский институт атомной энергетики – филиал
Размер24.09 Kb.
ТипЛабораторная работа

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

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

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

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

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


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

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


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

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





Выполнил:
студент группы ВТ3-С08
Азаров А.И.

Проверил:
профессор
Перегуда А.И.


ОБНИНСК 2012

^ Цель работы:


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


^ Краткая теория

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

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

f:\media\image5.png

Где 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)

f:\media\image16.png

Пустьf:\media\image17.png— вероятность направления вновь поступившей заявки в узел их

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

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

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

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

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

f:\media\image22.png


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

f:\media\image23.png

являющаяся сужением матрицf:\media\image24.pngна множествоf:\media\image25.pngвнутренних узлов.

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

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


Результаты:

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

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

На графиках отображается среднее время ожидания заявки в очереди и среднее, минимальное и максимальное число заявок состоящих в очереди.

Рис. 1. Главное окно моего программного обеспечения



Рис. 2. Результаты моделирования


Вывод:

Был изучен метод моделирования открытой марковской системы массового обслуживания. Были получены её характеристики и необходимые оценки.

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

Похожие:

Министерство образования и науки российской федерации обнинский институт атомной энергетики – филиал iconМинистерство образования и науки российской федерации обнинский институт атомной энергетики филиал
Тема
Министерство образования и науки российской федерации обнинский институт атомной энергетики – филиал iconМинистерство образования и науки российской федерации обнинский институт атомной энергетики – филиал
Федерального государственного автономного образовательного учреждения высшего профессионального образования
Министерство образования и науки российской федерации обнинский институт атомной энергетики – филиал iconМинистерство образования и науки российской федерации обнинский институт атомной энергетики – филиал
Федерального государственного автономного образовательного учреждения высшего профессионального образования
Министерство образования и науки российской федерации обнинский институт атомной энергетики – филиал iconМинистерство образования и науки российской федерации обнинский институт атомной энергетики
Федерального государственного автономного образовательного учреждения высшего профессионального образования
Министерство образования и науки российской федерации обнинский институт атомной энергетики – филиал iconМинистерство образования и науки российской федерации бийский технологический институт (филиал)
Руководитель от вуза / / подпись Ф. И. О
Министерство образования и науки российской федерации обнинский институт атомной энергетики – филиал iconОбнинский институт атомной энергетики социально-экономический факультет Кафедра психологии Рег. № Теория потребностей и самоактуализирующейся личности А. Маслоу

Министерство образования и науки российской федерации обнинский институт атомной энергетики – филиал iconМинистерство образования и науки российской федерации (минобрнауки россии) прика з
Положения о Министерстве образования и науки Российской Федерации, утверждённого постановлением Правительства Российской Федерации...
Министерство образования и науки российской федерации обнинский институт атомной энергетики – филиал iconМинистерство образования и науки российской федерации (минобрнауки россии) приказ
О признании утратившими силу некоторых приказов Министерства образования Российской Федерации и Министерства образования и науки...
Министерство образования и науки российской федерации обнинский институт атомной энергетики – филиал iconМинистерство образования и науки российской федерации пресс-служба
Выборы Уполномоченного по правам студентов проводятся по инициативе Всероссийского студенческого форума, поддержанной Министром образования...
Министерство образования и науки российской федерации обнинский институт атомной энергетики – филиал iconМинистерство образования и науки российской федерации омский филиал федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Высшая школа народных искусств (институт)»
Омский филиал федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Высшая...
Министерство образования и науки российской федерации обнинский институт атомной энергетики – филиал iconМинистерство образования и науки российской федерации (минобрнауки россии) приказ
Министерством юстиции Российской Федерации 13 марта 2008 г., регистрационный №11332), в редакции приказа Министерства образования...
Вы можете разместить ссылку на наш сайт:
Документы


При копировании материала укажите ссылку ©ignorik.ru 2015

контакты
Документы