Содержание:

Введение

В системе передачи данных осуществляется передача пакетов данных из пункта А в пункт С через транспортный пункт В. В пункт А пакеты поступают за время 10±5мс, где они буферируются в накопителе емкостью 20 пакетов и передаются по одной из двух линий АВ-1 или АВ-2 за время равное соответственно 20 мс и 20±5мс. В пункте В они вновь буферируются в накопителе емкостью 25 пакетов и передаются по одной из двух линий ВС-1 или ВС-2 за время равное соответственно 25±3мс и 25мс, причем пакеты из линии АВ-1 направляются в линию ВС-1, а пакеты из линии АВ-2 направляются в линию ВС-2. Чтобы избежать переполнения, в пункте В для емкости накопителя установлено его пороговое значение в 20 пакетов, по достижении которого подключается резервное оборудование, которое позволяет снизить время передачи по линиям ВС-1 и ВС-2 до 15мс.

Необходимо смоделировать процесс передачи в этой системе 500 пакетов и определить

–вероятность подключения резервной аппаратуры,

–характеристики очереди в пункте В.

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

Требуется:

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

1. Основная часть

1.1 Обзор подходов

Системы массового обслуживания (СМО) представляют собой системы специфического вида. Основой СМО является определенное число обслуживающих устройств — каналы обслуживания. Роль каналов в реальности могут выполнять приборы, операторы, продавцы, линии связи и пр.

Предназначение СМО состоит в обслуживании потока заявок (требований), представляющих последовательность событий, поступающих нерегулярно и в заранее неизвестные и случайные моменты вре¬мени. Само обслуживание заявок также имеет непостоянный характер, происходит в случайные промежутки времени и зависит от многих и даже неизвестных причин. Случайный характер потока заявок и вре¬мени их обслуживания обусловливает неравномерность загрузки СМО: на входе могут накапливаться необслуженные заявки (перегрузка СМО) либо заявок нет или их меньше, чем свободных каналов (недогрузка СМО). Структура систем массового обслуживания показана схематически на рис.1. В СМО поступает поток заявок; часть из них принимается на обслуживание в каналы, часть ждет в очереди на обслуживание, часть покидает систему необслуженными.

Рис. 1

Основными элементами СМО являются:

1. входной поток заявок;
2. очередь;
3. каналы обслуживания;
4. выходной поток заявок (обслуженные заявки).

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

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

По дисциплине обслуживания различаются три класса СМО.

1. СМО с отказами (нулевое ожидание или явные потери). «Отказная» заявка вновь поступает в систему, чтобы ее обслужили (например, вызов абонента через АТС).
2. СМО с ожиданием (неограниченное ожидание или очередь). При занятости всех каналов заявка поступает в очередь и в конце концов будет выполнена (торговля, сферы бытового и медицинского обслуживания).
3. СМО смешанного типа (ограниченное ожидание). Имеется ограничение на длину очереди (сервис по обслуживанию автомобилей). Другой вид ограниченного ожидания - ограничение на время пребывания заявки в СМО (ПВО, особые условия обслуживания в банке).

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

1.2 Обоснование выбора

Т. к. по условию задачи имеется одна линия и очередь покупателей ограниченна, мы имеем дело с одноканальной системой массового обслуживания с ограниченной очередью. СМО содержит один обслуживающий канал. На вход поступает простейший поток заявок с интенсивностью λ. Если заявка застала обслуживающий канал занятым, то она встает в очередь и ожидает начала обслуживания. Число мест в очереди ограничено и равно m. Если заявка застала обслуживающий канал занятым и в очереди нет свободных мест, то она покидает систему необслуженной. Время обслуживания заявки есть случайная величина, которая подчиняется экспоненциальному закону распределения с параметром μ. Среднее время обслуживания одной заявки t_обсл=1/μ.

2. Аналитическая модель

Граф состояний многоканальной системы массового обслуживания имеет вид, показанный на рис. 2.

Рис. 2. Граф состояний системы

Состояния СМО представляются следующим образом:

S₀– канал обслуживания свободен,

S₁– канал обслуживания занят, но очереди нет,

S₂– канал обслуживания занят, в очереди одна заявка,

S_k+1– канал обслуживания занят, в очереди k заявок,

S_m+1– канал обслуживания занят, все m мест в очереди заняты.

Показатели эффективности СМО
Показатели эффективности обычно формируются на основе полученных из расчетов значений вероятностей состояний системы:

1.Вероятность того, что поступающее в систему требование откажется присоединяться к очереди и теряется, (Р_отк).

2.Среднее количество требований, ожидающих начала обслуживания

3.Относительная (q) и абсолютная (А) пропускные способности системы

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

5. Общее количество требований, находящихся в системе (М)

Показатели эффективности работы СМО:

1) вероятность отказа Ротк (вероятность того, что заявка покинет СМО необслуженной, т.е. предельная вероятность состояния S1) Ротк =Р₁;

2) относительная пропускная способность Q (отношение среднего числа обслуживаемых в единицу времени заявок к среднему числу поступивших за это время заявок)

Q=1–Ротк;

3) абсолютная пропускная способность А (среднее число заявок, которое СМО может обслужить в единицу времени) - А=λQ.

3. Имитационная модель

GPSS World предназначена для имитационного моделирования систем с дискретными и непрерывными процессами. Языком моделирования в ней является язык GPSS, улучшенный встроенным языком программирования низкого уровня PLUS. Язык GPSS построен в предположении, что модель сложной системы можно представить совокупностью элементов и логических правил их взаимодействия в процессе функционирования моделируемой системы. Набор абстрактных элементов, называемых объектами, небольшой. Также набор логических правил ограничен и может быть описан стандартными операциями. Комплекс программ, описывающих функционирование объектов и выполняющих логические операции, является основой для создания программной модели.

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

1. создание или уничтожение транзактов;
2. изменение числового атрибута объекта;
3. задержка транзакта на определенный период времени;
4. изменение маршрута движения транзакта в модели. Версия GPSS, реализованная в системе GPSSWorld, содержит 53 типа блоков.

В зависимости от назначения блоки подразделяются на несколько групп.

1. Блоки, осуществляющие модификацию атрибутов транзактов:
   • генерирование и уничтожение транзактов GENERATE, SPLIT, TERMINATE, ASSEMBLE;
   • временная задержка ADVANCE;
   • синхронизация движения двух MATCH и нескольких GATHER транзактов;
   • изменение приоритета транзакта PRIORITY;
   • изменение параметров транзактов ASSIGN, INDEX, MARK, PLUS.
2. Блоки, изменяющие последовательность движения транзактов (блоки передачи управления):DISPLACE, TRANSFER, LOOP, TEST, GATE.
3. Блоки, связанные с группирующей категорией: ADOPT, ALTER, EXAMINE, JOIN, REMOVE, SCAN.
4. Блоки, описывающие объекты аппаратной категории:
   • одноканальные устройства (технические средства) SEIZE, RELEASE, PREEMPT, RETURN,FUNAVAIL, FAVAIL;
   • многоканальные устройства (памяти) ENTER, LEAVE, SAVAIL, SUNAVAIL;
   • ключи (логические переключатели) LOGIC.
5. Блоки, сохраняющие необходимые значения для дальнейшего использования: SAVEVALUE,MSAVEVALUE.
6. Блоки для получения статистических результатов:
   • Очереди QUEUE, DEPART;
   • Таблицы TABULATE.
7. Блоки для организации списка пользователя: LINK, UNLINK.
8. Блоки для организации ввода-вывода:
9. Специальные блоки: BUFFER, COUNT, EXECUTE, INTEGRATION, SELECT, TRACE,UNTRACE.

3.1. Листинг моделей

;ГЕНЕРАЦИЯ ПАКЕТОВ

GENERATE 10,5 ;поступление пакетов через 5-15 мс или 10+/-5

TEST L Q1,25,met1 ;если очередь на передачу меньше 25 то вниз, иначе на метку met1

;ПЕРЕДАЧА от A к B

QUEUE 1 ;занять очередь на передачу от A к B

TRANSFER BOTH,metAB2 ;

;Линия AB1

SEIZE AB1 ;занять устройство - линию AB1

DEPART 1 ;выйти из очереди

ASSIGN 1,1 ;в первый параметр транзакта записать 1

ADVANCE 20 ;передача по линий АВ1 - за время 20 мс

RELEASE AB1 ;освободить устройство - линию AB1

TRANSFER ,met2 ;перейти к пердачи от B к C

;Линия AB2

metAB2 SEIZE AB2 ;занять устройство - линию AB2

DEPART 1 ;выйти из очереди

ASSIGN 1,2 ;в первый параметр транзакта записать 2

ADVANCE 20,5 ;передача по линий АВ2 - за время 15-25 мс

RELEASE AB2 ;освободить устройство - линию AB1

;ПЕРЕДАЧА от B к C

met2 TEST L Q2,20,met3 ;если очередь на передачу меньше 20 то вниз, иначе на метку met3

QUEUE 2 ;занять очередь на передачу от B к C

TEST E P1,1,metBC2 ;проверить 1й параметр транзакта. Если =1 то вниз, иначе к метке metBC2

;Линия BC1

SEIZE BC1 ;занять устройство - линию СB1

DEPART 2 ;выйти из очереди

TEST L Q2,15,RezervBC1 ;если очередь на передачу меньше 20 то вниз, иначе RezervBC1

ADVANCE 20,3 ;передача по линии ВС1 (за 20 ± 3 мс)

savevalue countStandartMode+,1 ;счетчик использования стандартного режима передачи

RELEASE BC1 ;освободить устройство - линию СB1

TERMINATE

RezervBC1 ADVANCE 15 ;резервная аппаратура, время передачи снижается до 15 мс.

savevalue countRezervMode+,1 ;счетчик использования резервного режима передачи

RELEASE BC1 ;освободить устройство - линию СB1

TERMINATE

;Линия BC2

metBC2 SEIZE BC2

DEPART 2

TEST L Q2,15,RezervBC2

ADVANCE 25 ;передача по линии ВС1 (за 25 мс)

savevalue countStandartMode+,1

RELEASE BC2

TERMINATE

RezervBC2 ADVANCE 15 ;резервная аппаратура, время передачи снижается до 15 мс.

savevalue countRezervMode+,1

RELEASE BC2

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),500

;когда сумма переменных станет = 500 транзакт пройдет вниз, иначе проверка продолжится

SAVEVALUE VeroyatnostRezerva,(x$countRezervMode/(x$countStandartMode+x$countRezervMode)) ;вероятность использования резерва

TERMINATE 1

start 1

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

GPSS World Simulation Report - 20.3.1

Thursday, January 12, 2017 22:58:34

START TIME END TIME BLOCKS FACILITIES STORAGES

0.000 5207.234 48 4 0

NAME VALUE

AB1 10005.000

AB2 10004.000

BC1 10007.000

BC2 10006.000

COUNTFULLBUFFERA 10002.000

COUNTFULLBUFFERB 10003.000

COUNTREZERVMODE 10001.000

COUNTSTANDARTMODE 10000.000

MET1 41.000

MET2 16.000

MET3 43.000

METAB2 11.000

METBC2 30.000

REZERVBC1 26.000

REZERVBC2 37.000

VEROYATNOSTREZERVA 10008.000

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY

1 GENERATE 522 0 0

2 TEST 522 0 0

3 QUEUE 522 0 0

4 TRANSFER 522 3 0

5 SEIZE 260 0 0

6 DEPART 260 0 0

7 ASSIGN 260 0 0

8 ADVANCE 260 1 0

9 RELEASE 259 0 0

10 TRANSFER 259 0 0

METAB2 11 SEIZE 259 0 0

12 DEPART 259 0 0

13 ASSIGN 259 0 0

14 ADVANCE 259 1 0

15 RELEASE 258 0 0

MET2 16 TEST 517 0 0

17 QUEUE 517 0 0

18 TEST 517 15 0

19 SEIZE 259 0 0

20 DEPART 259 0 0

21 TEST 259 0 0

22 ADVANCE 97 0 0

23 SAVEVALUE 97 0 0

24 RELEASE 97 0 0

25 TERMINATE 97 0 0

REZERVBC1 26 ADVANCE 162 1 0

27 SAVEVALUE 161 0 0

28 RELEASE 161 0 0

29 TERMINATE 161 0 0

METBC2 30 SEIZE 243 1 0

31 DEPART 242 0 0

32 TEST 242 0 0

33 ADVANCE 154 0 0

34 SAVEVALUE 154 0 0

35 RELEASE 154 0 0

36 TERMINATE 154 0 0

REZERVBC2 37 ADVANCE 88 0 0

38 SAVEVALUE 88 0 0

39 RELEASE 88 0 0

40 TERMINATE 88 0 0

MET1 41 SAVEVALUE 0 0 0

42 TERMINATE 0 0 0

MET3 43 SAVEVALUE 0 0 0

44 TERMINATE 0 0 0

45 GENERATE 1 0 0

46 TEST 1 0 0

47 SAVEVALUE 1 0 0

48 TERMINATE 1 0 0

FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY

AB2 259 0.996 20.024 1 520 0 0 3 0

AB1 260 0.995 19.927 1 519 0 0 3 0

BC2 243 0.993 21.276 1 488 0 0 0 15

BC1 259 0.832 16.721 1 517 0 0 0 0

QUEUE MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME AVE.(-0) RETRY

1 7 3 522 5 3.415 34.062 34.392 0

2 17 16 517 182 12.428 125.178 193.184 0

SAVEVALUE RETRY VALUE

COUNTSTANDARTMODE 0 251.000

COUNTREZERVMODE 0 249.000

COUNTFULLBUFFERA 0 0

COUNTFULLBUFFERB 0 0

VEROYATNOSTREZERVA 0 0.498

CEC XN PRI M1 ASSEM CURRENT NEXT PARAMETER VALUE

488 0 4846.864 488 30 31 1 2.000

FEC XN PRI BDT ASSEM CURRENT NEXT PARAMETER VALUE

524 0 5212.584 524 0 1

517 0 5221.201 517 26 27 1 1.000

520 0 5225.885 520 14 15 1 2.000

519 0 5226.201 519 8 9 1 1.000

4. Анализ результатов

С целью проверки корректности построенных моделей проведем сравнение математических ожиданий некоторых случайных величин и результатов моделирования.

Случайная величина	Мат. ожидание	Результаты моделирования
Количество пакетов	500	500
Среднее время	B*(I2*(I1+I3)/2+(1-I2)*(I3+I4)/2)) +(1-B)( I6*(I5+I7)/2+(1-I6)*(I7+I8)/2)) = 21,6871	19,486

Различия между расчетными и полученными в результате моделирования значениями не превышают 4%, что, в некотором смысле, позволяет надеяться на корректность построенной модели.

Следует отметить, что из-за того, что количество порождаемых заявок значительно превосходит возможности канала по их обработке, канал практически всё время занят обработкой (коэффициент использования 0,096-0,097). Из-за этого решения о подключении резервной аппаратуры делается на основании увеличения загрузки канала В.

Заключение.

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

Список литературы

1. Шрайбер Т.Дж. Моделирование на GPSS, пер. с англ. М.Машиностроение. 1980г. 592с.
2. Кудрявцев Е. М. К88 GPSS World. Основы имитационного моделирования различных систем. – М.: ДМК Пресс, 2004. – 320 с.
3. Справочное руководство по GPSS WORLD
4. А. И. Васильев Имитационное моделирование информационных и вычислительных систем с использованием GPSS , Владивосток, 2004