Описание системы массового обслуживания
В математических моделях (ММ) сложных объектов, представленных в виде систем массового обслуживания (СМО), фигурируют средства обслуживания, называемые обслуживающими аппаратами (ОА), и обслуживаемые заявки, называемые транзактами. Так, в моделях систем обработки и передачи данных ОА отображают микропроцессоры и линии связи, а транзакты - поступающие на обработку заявки и пакеты данных.
Состояние СМО характеризуется состояниями ОА, транзактов и очередей к ОА. Состояние ОА описывается двоичной переменной, которая может принимать значения "занят" или "свободен". Переменная, характеризующая состояние транзакта, может иметь значения "обслуживания" или "ожидания". Состояние очереди характеризуется количеством находящихся в ней транзактов.
Имитационная модель СМО представляет собой алгоритм, отражающий поведение СМО, т.е. отражающий изменения состояния СМО во времени при заданных потоках заявок, поступающих на входы системы. Параметры входных потоков заявок - внешние параметры СМО. Выходными параметрами являются величины, характеризующие свойства системы - качество ее функционирования. Примеры выходных параметров: производительность СМО - среднее число заявок, обслуживаемых в единицу времени; коэффициенты загрузки оборудования - отношение времен обслуживания к общему времени в каждом ОА; среднее время обслуживания одной заявки. Основное свойство ОА, учитываемое в модели СМО, - это затраты времени на обслуживание, поэтому внутренними параметрами в модели СМО являются величины, характеризующие это свойство ОА. Обычно время обслуживания рассматривается, как случайная величина и в качестве внутренних параметров фигурируют параметры законов распределения этой величины.
Имитационное моделирование позволяет исследовать СМО при различных типах входных потоков и интенсивностях поступления заявок на входы, при вариациях параметров ОА, при различных дисциплинах обслуживания заявок. Дисциплина обслуживания - правило, по которому заявки поступают из очередей на обслуживание. Величина, характеризующая право на первоочередное обслуживание, называется приоритетом. В моделях СМО заявки, приходящие на вход занятого ОА, образуют очереди, отдельные для заявок каждого приоритета. При освобождении ОА на обслуживание принимается заявка из непустой очереди с наиболее высоким приоритетом.
Основной тип ОА - устройства, именно в них происходит обработка транзактов с затратами времени. К ОА относятся также накопители (памяти), отображающие средства хранения обрабатываемых данных в вычислительных системах. Накопители характеризуются не временами обслуживания заявок, а емкостью - максимально возможным количеством одновременно находящихся в накопителе заявок.
К элементам имитационных моделей СМО кроме ОА относят также узлы и источники заявок. Связи ОА между собой реализуют узлы, т.е. характеризуют правила, по которым заявки направляются к тому или иному ОА.
Для описания моделей СМО при их исследовании на ЭВМ разработаны специальные языки имитационного моделирования. Существуют общецелевые языки, ориентирован-ные на описание широкого класса СМО в различных предметных областях, и специали-зированные языки, предназначенные для анализа систем определенного типа. Примером общецелевых языков служит широко распространенный язык GPSS.
Для описания имитационной модели на языке GPSS полезно представить ее в виде схемы, на которой отображаются элементы СМО - устройства, накопители, узлы и источники. Описание на языке GPSS есть совокупность операторов (блоков), характеризующих процессы обработки заявок. Имеются операторы и для отображения возникновения заявок, задержки их в ОА, занятия памяти, выхода из СМО, изменения параметров заявок (например, приоритетов), вывода на печать накопленной информации, характеризующей загрузку устройств, заполненность очередей и т.п.
Пути продвижения заявок между ОА отображаются последовательностью операторов в описании модели на языке GPSS специальными операторами передачи управления (перехода). Для моделирования используется событийный метод. Соблюдение правильной временной последовательности имитации событий в СМО обеспечивается интерпретато-ром GPSS World - программной системой, реализующий алгоритмы имитационного моделирования.
Построение структурной схемы модели
Имеется система передачи данных, состоящая из:
• 3-х пунктов A,B и C
• 5-х линий AB1, AB2, AB3, BC1 и BC2
Система передачи данных обеспечивает передачу пакетов данных из пункта A в пункт C через промежуточный пункт B. В пункт А пакеты поступают через 8±4мс. Там они буферизуются и передаются по линии АВ1, AB2, AB3. В пункте В они буферизуются и передаются по линии BC1, а при достижении порогового значения в пункте А по линии ВС2.
Требуется смоделировать прохождение через систему 1000 пакетов данных и определить характеристики очередей в пунктах А и В и вероятность использования линии ВС2. Определить максимально возможную интенсивность входного потока пакетов данных, при котором система работает без потерь.
Описание сети в виде системы массового обслуживания.
В данной модели системы передачи данных, представляем:
пункты – статистические объекты типа очередь;
линии – аппаратные объекты типа прибор;
пакеты данных – транзакты.
За единицу модельного времени (е.м.в.) принята 1мс.
Формализация и алгоритмизация модели.
Формально схема модели имеет вытянутый вид с некоторым количеством узлов (переходов). Это делается для реализации передачи пакетов по четырем линиям и моделирования сбоев в них.
Алгоритм.
1. Генерация транзакта через 8±4 е.м.в.
2. если очередь на передачу меньше 25 то вниз, иначе в пункт 37
3. занять очередь 1 на передачу от A к B
4. равновероятная передача заявок: АВ1–переход в пункт 5;АВ2 – переход в пункт 10; AB3 – переход в пункт 15
5. занять устройство - линию AB1
6. выйти из очереди 1
7. передача по линий АВ1 - за время 23+/-6 мс
8. освободить устройство - линию AB1
9. перейти к передаче от B к C
10. занять устройство - линию AB2
11. выйти из очереди 1
12. передача по линий АВ2 - за время 34+/-8 мс
13. освободить устройство - линию AB2
14. перейти к передаче от B к C
15. занять устройство - линию AB3
16. выйти из очереди 1
17. передача по линий АВ2 - за время 25+/-2 мс
18. освободить устройство - линию AB3
19. перейти к передаче от B к C
20. если очередь на передачу меньше 20 то вниз, иначе в пункт 38
21. занять очередь на передачу от B к C
22. если очередь на передачу меньше 12 то вниз, иначе в пункт 26
23. занять очередь на передачу от B к C
24. если очередь>12 то переход в пункт 26
25. занять очередь на передачу от B к C
26. равновероятная передача заявок :BC1–переход в пункт 27;BC2– переход в пункт 32;
27. занять устройство - линию BС1
28. выйти из очереди 2
29. передача по линии ВС1 - за время 8+/-4 мс
30. задействовать счетчик использования стандартного режима передачи
31. освободить устройство - линию BС1
32. занять устройство - линию BС2
33. выйти из очереди 2
34. передача по линии ВС2 - за время 8+/-4 мс
35. задействовать счетчик использования не стандартного режима передачи
36. освободить устройство - линию BС2
37. задействовать счетчик отказов на постановку в очередь на передачу AB
38. задействовать счетчик отказов на постановку в очередь на передачу BС
39. повторение всех пунктов до тех пор пока не пройдут 1000 транзактов.
Блок схема:
Имитационный эксперимент.
Текст программы.
;ГЕНЕРАЦИЯ ПАКЕТОВ
GENERATE 8,4 ;поступление пакетов
TEST L Q1,25,met1 ;если очередь на передачу меньше 25 то вниз, иначе на метку met1
;ПЕРЕДАЧА от A к B
QUEUE 1 ;занять очередь на передачу от A к B
TRANSFER ALL,metAB1,metAB2,5 ;передача по каналам AB1 и AB2
;Линия AB1
metAB1 SEIZE AB1 ;занять устройство - линию AB1
DEPART 1 ;выйти из очереди
ADVANCE 23,6 ;передача по линий АВ1
RELEASE AB1 ;освободить устройство - линию AB1
TRANSFER ,met2 ;перейти к передаче от B к C
;Линия AB2
metAB2 SEIZE AB2 ;занять устройство - линию AB2
DEPART 1 ;выйти из очереди
ADVANCE 34,8 ;передача по линий АВ2
RELEASE AB2 ;освободить устройство - линию AB2
TRANSFER ,met2 ;перейти к передаче от B к C
;Линия AB3
metAB3 SEIZE AB3 ;занять устройство - линию AB3
DEPART 1 ;выйти из очереди
ADVANCE 25,2 ;передача по линий АВ3
RELEASE AB2 ;освободить устройство - линию AB3
TRANSFER ,met2 ;перейти к передаче от B к C
;ПЕРЕДАЧА от B к C
met2 TEST L Q2,20,met3 ;если очередь на передачу меньше 20 то вниз, иначе на метку met3
QUEUE 2 ;занять очередь на передачу от B к C
TEST L Q1,12,met5 ;если очередь на передачу меньше 18 то вниз, иначе на метку met5
TRANSFER ,metBC1 ; передача по каналам BC1
met5 TRANSFER BOTH,metBC1,metBC2 ;передача по каналам BC1,BC2
;Линия BC1
metBC1 SEIZE BC1 ;занять устройство - линию BС1
DEPART 2 ;выйти из очереди
ADVANCE 8,4 ;передача по линии ВС1
Savevalue countStandartMode+,1 ;счетчик использования стандартного режима передачи
RELEASE BC1 ;освободить устройство - линию BС1
TERMINATE
;Линия BC2
metBC2 SEIZE BC2 ;занять устройство - линию BС2
DEPART 2 ;выйти из очереди
ADVANCE 8,4 ;передача по линии ВС2
Savevalue countSRezervMode+,1 ;счетчик использования не стандартного режима передачи
RELEASE BC2 ;освободить устройство - линию BС2
TERMINATE
met1 savevalue countFullBufferA+,1 ;счетчик отказов на постановку в очередь на передачу AB
TERMINATE
met3 savevalue countFullBufferB+,1 ;счетчик отказов на постановку в очередь на передачу BС
TERMINATE
;ЗАВЕРШАЮЩИЙ ТРАНЗАКТ
GENERATE ,,,1 ;генерация только одного транзакта
TEST E (x$countStandartMode+x$countRezervMode+x$countFullBufferA+x$countFullBufferB),1000 ;когда сумма переменных станет = 1000 транзакт пройдет вниз, иначе проверка продолжится
SAVEVALUE VeroyatnostRezerva,(x$countRezervMode/(x$countStandartMode+x$countRezervMode)) ;вероянтость использования резерва
TERMINATE 1
start 1
Листинг результатов моделирования
GPSS World Simulation Report - Kursovoi.4.1
Monday, June 01, 2009 00:03:08
START TIME END TIME BLOCKS FACILITIES STORAGES
0.000 9674.700 44 4 0
NAME VALUE
AB1 10004.000
AB2 10005.000
AB3 UNSPECIFIED
BC1 10006.000
BC2 10007.000
COUNTFULLBUFFERA 10002.000
COUNTFULLBUFFERB 10003.000
COUNTREZERVMODE 10001.000
COUNTSREZERVMODE 10008.000
COUNTSTANDARTMODE 10000.000
MET1 37.000
MET2 20.000
MET3 39.000
MET5 24.000
METAB1 5.000
METAB2 10.000
METAB3 15.000
METBC1 25.000
METBC2 31.000
VEROYATNOSTREZERVA 10009.000
LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY
1 GENERATE 1219 0 0
2 TEST 1219 0 0
3 QUEUE 734 0 0
4 TRANSFER 734 25 0
METAB1 5 SEIZE 425 0 0
6 DEPART 425 0 0
7 ADVANCE 425 1 0
8 RELEASE 424 0 0
9 TRANSFER 424 0 0
METAB2 10 SEIZE 284 0 0
11 DEPART 284 0 0
12 ADVANCE 284 1 0
13 RELEASE 283 0 0
14 TRANSFER 283 0 0
METAB3 15 SEIZE 0 0 0
16 DEPART 0 0 0
17 ADVANCE 0 0 0
18 RELEASE 0 0 0
19 TRANSFER 0 0 0
MET2 20 TEST 707 0 0
21 QUEUE 707 0 0
22 TEST 707 0 0
23 TRANSFER 11 0 0
MET5 24 TRANSFER 696 0 0
METBC1 25 SEIZE 515 0 0
26 DEPART 515 0 0
27 ADVANCE 515 0 0
28 SAVEVALUE 515 0 0
29 RELEASE 515 0 0
30 TERMINATE 515 0 0
METBC2 31 SEIZE 192 0 0
32 DEPART 192 0 0
33 ADVANCE 192 0 0
34 SAVEVALUE 192 0 0
35 RELEASE 192 0 0
36 TERMINATE 192 0 0
MET1 37 SAVEVALUE 485 0 0
38 TERMINATE 485 0 0
MET3 39 SAVEVALUE 0 0 0
40 TERMINATE 0 0 0
41 GENERATE 1 0 0
42 TEST 1 0 0
43 SAVEVALUE 1 0 0
44 TERMINATE 1 0 0
FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY
AB1 425 0.999 22.739 1 1174 0 0 25 0
AB2 284 0.998 33.992 1 1173 0 0 25 0
BC1 515 0.430 8.070 1 0 0 0 0 0
BC2 192 0.163 8.208 1 0 0 0 0 0
QUEUE MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME AVE.(-0) RETRY
1 25 25 734 2 24.005 316.398 317.263 0
2 1 0 707 703 0.001 0.020 3.475 0
SAVEVALUE RETRY VALUE
COUNTSTANDARTMODE 0 515.000
COUNTREZERVMODE 0 0
COUNTFULLBUFFERA 0 485.000
COUNTFULLBUFFERB 0 0
COUNTSREZERVMODE 0 192.000
VEROYATNOSTREZERVA 0 0
FEC XN PRI BDT ASSEM CURRENT NEXT PARAMETER VALUE
1174 0 9676.501 1174 7 8
1173 0 9682.252 1173 12 13
1221 0 9686.254 1221 0 1
|
Главная
Каталог файлов
