моделирование систем массового обслуживания (СМО)

Постановка задачи. В некоторое цифровое устройство через 3±1 мин. поступают задания длиной 600±200 Кбайт. Скорость ввода, вывода и обработки заданий – 100 Кбайт/сек. Задания проходят последовательно ввод, обработку и вывод, буферируясь перед каждой операцией. После вывода 5% заданий оказываются выполненными неправильно вследствие сбоев и возвращаются на ввод. Для ускорения обработки задания в очередях располагаются по возрастанию их длины, т. е. короткие задания обслуживают в первую очередь.
Смоделировать работу устройства в течение 3 ч. Определить необходимую емкость буферов и функцию распределения времени обслуживания заданий (построить гистограмму).
Выбор методов решения задачиМетоды моделирования можно классифицировать на три основные группы: аналитические, численные и имитационные.
Аналитические методы моделирования. Аналитические методы позволяют получить характеристики системы как некоторые функции параметров ее функционирования. Таким образом, аналитическая модель представляет собой систему уравнений, при решении которой получают параметры, необходимые для расчета выходных характеристик системы (среднее время обработки задания, пропускную способность и т.д.). Аналитические методы дают точные значения характеристик системы, но применяются для решения только узкого класса задач. Причины этого заключается в следующем. Во-первых, вследствие сложности большинства реальных систем их законченное математическое описание (модель) либо не существует, либо еще не разработаны аналитические методы решения созданной математической модели. Во-вторых, при выводе формул, на которых основываются аналитические методы, принимаются определенные допущения, которые не всегда соответствуют реальной системе. В этом случае от применения аналитических методов приходится отказываться.
Численные методы моделирования. Численные методы предполагают преобразование модели к уравнениям, решение которых возможно методами вычислительной математики. Класс задач, решаемых этими методами, значительно шире. В результате применения численных методов получают приближенные значения (оценки) выходных характеристик системы с заданной точностью.
Имитационные методы моделирования. С развитием вычислительной техники широкое применение получили имитационные методы моделирования для анализа систем, преобладающими в которых являются стохастические воздействия.
Суть имитационного моделирования (ИМ) заключается в имитации процесса функционирования системы во времени, с соблюдением таких же соотношений длительности операций как в системе оригинале. При этом имитируются элементарные явления, составляющие процесс, сохраняется их логическая структура, последовательность протекания во времени. В результате применения ИМ получают оценки выходных характеристик системы, которые необходимы при решении задач анализа, управления и проектирования.
 
Классификация системыПри определении любой системы обслуживания для сокращенной записи используется следующая система кодировки, в которой на месте букв ставится соответствующая характеристика СМО (табл. 1):
A | B | C | D | E
Таблица 1. Характеристики СМО
А Закон распределения интервала времени между поступлением заявок M – экспоненциальный
E – Эрланга
H – гиперэкспоненциальный
Г – гамма-распределение
D – детерминированное распределение
G – произвольное распределение
В Закон распределения времени обслуживания в приборах СМО С Число обслуживающих приборов 1 – для одноканальных систем
l – для многоканальных систем
D Число мест в очереди. Если число мест не ограничено, то поле можно опустить. r либо n – для конечного числа мест
Е Дисциплина обслуживания. По умолчанию LIFO – в этом случае поле может опускаться FIFO, LIFO, RANDOM

В нашем случае, опираясь на задание можно классифицировать систему как
G | G | 1 |RANDOM – СМО с несколькими приборами, бесконечной очередью, произвольными законами распределения времени между поступлением заявок и времени обслуживания, дисциплина обслуживания RANDOM.
Построение концептуальной схемы модели и ее формализация Прежде чем начать моделирование системы необходимо определиться с тем, какие элементы входят в её состав. Согласно условию задания можно составить схему для визуальной представления поставленной задачи (Рис.1).
И
С
Т
О
Ч
Н
И
К
Очередь 1
Устройство 1
Оч.2
Ус. 2
Оч.3
Ус. 3
П
Р
И
Ё
М
Н
И
К
Ошибки
И
С
Т
О
Ч
Н
И
К
Очередь 1
Устройство 1
Оч.2
Ус. 2
Оч.3
Ус. 3
П
Р
И
Ё
М
Н
И
К
Ошибки

Рисунок 1. Концептуальная схема.
Формализуем ранее полученную концептуальную схему в схему символики Q-схем (Рис.2):
6802755500824500Н1
И
К1
Н2
К2
Н3
К3
Н1
И
К1
Н2
К2
Н3
К3

Рисунок 2. Q-схема моделируемой системы
На схеме: И – источник; К – канал; Н – накопитель.
Источник И имитирует процесс поступления заданий на накопитель. Из накопителя они попадают на каналы К1, К2, К3 которые моделируют устройства ввода, обработки и вывода.
Блок-диаграмма в символике блоков GPSSМодели систем на GPSS могут быть первично описаны в виде блок-диаграмм. Блок-диаграмма представляет собой набор символов с характерными очертанием блоков, соединенных между собой линиями. Вид каждого из блоков стандартен. Модель строится следующим образом. Из допустимого множества блоков выбирают необходимые и далее выстраивают их в диаграмму для того, чтобы в процессе функционирования модели они взаимодействовали друг с другом. Использование блоков при построении моделей зависит от логических схем работы реальных систем, моделируемых на ЭВМ. При этом отдельные элементы модели и модель в целом имеют достаточно различимое подобие. Оно может быть также усилено разработчиком за счет более продуманного на этапе разработки разделения исследуемого объекта и модели на сегменты.
Конфигурация блок-диаграммы отражает направления, по которым происходит движение перемещающихся элементов – транзактов. Работа модели заключается в перемещении транзактов от блоков к блокам.
В самом начале моделирования в модели нет ни одного транзакта. В процессе моделирования транзакты входят в модель в определенные моменты времени в соответствии с теми логическими потребностями, которые возникают в моделируемой системе. Подобным образом транзакты покидают модель в определенные моменты времени в зависимости от специфики моделирования. Блок-диаграмма системы показана на рисунке 3, а описание блоков в табл. 2.

Рисунок 3. Блок-диаграмма системы в символике блоков GPSS.
Таблица 2 – Описание блоков
Наименование блока Графическое изображение блока Назначение блока
GENERATE Генерирует через каждые A единиц времени с модификатором B и задержкой C, транзакты в количестве D, с приоритетом E и форматом F
SEIZE Обеспечивает вхождение транзакта в устройство А
RELEASE Освобождает устройство А
ADVANCE Задерживает транзакт на время A с модификатором B
TERMINATE Уничтожает А транзактов
Код модели на языке имитационного моделирования GPSSTab TABLE M1,12,1,15;таблица
GENERATE 180,60;поток заданий
ASSIGN Raz,(UNIFORM(1,400,800));получение размера в Кбайт
PRIORITY (800-P$Raz);вычисление приоритета , чем больше размер тем меньше приоритет
Ret QUEUE BufVvod;буферизация перед вводом
SEIZE Vvod;занимаем ввод
DEPART BufVvod;освобождение буфера
ADVANCE (P$Raz/100);ввод
RELEASE Vvod;освобождаем ввод
QUEUE BufObr;буферизация перед обработкой
SEIZE Obr;занимаем обработку
DEPART BufObr;освобождение буфера
ADVANCE (P$Raz/100);обработка
RELEASE Obr;освобождение обработки
QUEUE BufVivod;буферизация перед выводом
SEIZE Vivod;занимаем вывод
DEPART BufVivod;освобождение буфера
ADVANCE (P$Raz/100);вывод
RELEASE Vivod;освобождаем вывод
TRANSFER .05,,Ret;5% возвращаем обратно
TABULATE Tab;получение распределения времени
TERMINATE;выход обработанных заданий
GENERATE 10800;моделируем 3 часа = 10800 сек
TERMINATE 1;завершение
START 1 ;карта начала
Результаты моделирования GPSS World Simulation Report - Untitled Model 1.1.1
Sunday, March 14, 2021 01:15:57
START TIME END TIME BLOCKS FACILITIES STORAGES
0.000 10800.000 23 3 0
NAME VALUE
BUFOBR 10004.000
BUFVIVOD 10006.000
BUFVVOD 10002.000
OBR 10005.000
RAZ 10001.000
RET 4.000
TAB 10000.000
VIVOD 10007.000
VVOD 10003.000
LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY
1 GENERATE 62 0 0
2 ASSIGN 62 0 0
3 PRIORITY 62 0 0
RET 4 QUEUE 64 0 0
5 SEIZE 64 0 0
6 DEPART 64 0 0
7 ADVANCE 64 0 0
8 RELEASE 64 0 0
9 QUEUE 64 0 0
10 SEIZE 64 0 0
11 DEPART 64 0 0
12 ADVANCE 64 0 0
13 RELEASE 64 0 0
14 QUEUE 64 0 0
15 SEIZE 64 0 0
16 DEPART 64 0 0
17 ADVANCE 64 0 0
18 RELEASE 64 0 0
19 TRANSFER 64 0 0
20 TABULATE 62 0 0
21 TERMINATE 62 0 0
22 GENERATE 1 0 0
23 TERMINATE 1 0 0
FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY
VVOD 64 0.036 6.058 1 0 0 0 0 0
OBR 64 0.036 6.058 1 0 0 0 0 0
VIVOD 64 0.036 6.058 1 0 0 0 0 0
QUEUE MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME AVE.(-0) RETRY
BUFVVOD 1 0 64 64 0.000 0.000 0.000 0
BUFOBR 1 0 64 64 0.000 0.000 0.000 0
BUFVIVOD 1 0 64 64 0.000 0.000 0.000 0
TABLE MEAN STD.DEV. RANGE RETRY FREQUENCY CUM.%
TAB 18.761 5.194 0
12.000 - 13.000 5 8.06
13.000 - 14.000 8 20.97
14.000 - 15.000 6 30.65
15.000 - 16.000 2 33.87
16.000 - 17.000 4 40.32
17.000 - 18.000 1 41.94
18.000 - 19.000 4 48.39
19.000 - 20.000 5 56.45
20.000 - 21.000 8 69.35
21.000 - 22.000 5 77.42
22.000 - 23.000 6 87.10
23.000 - 24.000 6 96.77
24.000 - 25.000 0 96.77
25.000 - _ 2 100.00
Анализ результатовFACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY
VVOD 64 0.036 6.058 1 0 0 0 0 0
OBR 64 0.036 6.058 1 0 0 0 0 0
VIVOD 64 0.036 6.058 1 0 0 0 0 0
Коэффициент загрузки цифрового устройства: 0,036=3,6
Поступило заданий: 62
Обработано дважды: 2 задания
Максимальный размер очереди буферов:1

Рисунок 4 - Гистограмма распределения времени обслуживания заданий.
Время обслуживания: 18,761±5,194 сек.
9. Временная диаграммаВвод:

Рисунок 5 – временная диаграмма устройства ввода.
Обработка:

Рисунок 6 – временная диаграмма устройства обработки.
Вывод:

Рисунок 7 – временная диаграмма устройства вывода.
ЗаключениеВ данной работе, согласно заданию, была рассмотрена система, которая представляет некоторое цифровое устройство. В ходе анализа системы была построена концептуальная и Q-схема системы. Дальнейшая формализация модели системы позволила построить блок-диаграмму в символике блоков языка имитационного моделирования GPSS и код модели на языке GPSS. В результате проведя имитационное моделирование разработанной модели были получены результаты характеристики системы, такие как распределение времени обслуживания.
Список использованных источниковАвдеев, В. Компьютерное моделирование цифровых устройств / В. Авдеев. - М.: ДМК, 2012. - 360 с.
Бархатов, В.П. Компьютерное моделирование в системе Mathсad. Учебное пособие / В.П. Бархатов. - М.: Финансы и статистика, 2006. - 144 с.
Башкин, В.А. Численное моделирование динамики вязкого совершенного газа / В.А. Башкин, И.В. Егоров. - М.: Физматлит, 2012. - 372 с.
Бегун, П.И. Моделирование в биомеханике. / П.И. Бегун. - М.: Высшая школа, 2004. - 390 с.
Воробьев, С.Н. Статистическое моделирование информационных систем: Учебное пособиеЧ. 1 / С.Н. Воробьев. - СПб.: ГУАП, 2010. - 152 с.
Вьюненко, Л.Ф. Имитационное моделирование: Учебник и практикум для академического бакалавриата / Л.Ф. Вьюненко, М.В. Михайлов, Т.Н. Первозванская. - Люберцы: Юрайт, 2016. - 283 с.
Голубева, Н.В. Математическое моделирование систем и процессов: Учебное пособие / Н.В. Голубева. - СПб.: Лань, 2013. - 192 с.
Гончаренко, И. Антенны КВ и УКВ. Часть 1. Компьютерное моделирование. / И. Гончаренко. - М.: РадиоСофт, 2004. - 128 с.
Долганова, О.И. Моделирование бизнес-процессов: Учебник и практикум для академического бакалавриата / О.И. Долганова, Е.В. Виноградова, А.М. Лобанова. - Люберцы: Юрайт, 2016. - 289 с.
Емельянов, С.В. Информационные технологии и вычислительные системы: Интернет-технологии. Математическое моделирование. Системы управления. Компьютерная графика / С.В. Емельянов. - М.: Ленанд, 2012. - 96 с.