Моделирование канала связи с контролем конфликтов одновременности

1. Имитационное моделирование системы массового обслуживания

1.1 Анализ динамики функционирования СМО

1.2 Формализация модели СМО средствами GPSS World

1.3 Имитационное моделирование СМО в среде GPSS World

2. Анализ и оптимизация системы массового обслуживания

2.1 Формализация модели СМО для задач анализа и оптимизации

2.2 Модификация имитационной модели

2.3 Реализация модельных экспериментов и анализ результатов

Выводы

1. Имитационное моделирование системы массового обслуживания

1.1 Анализ динамики функционирования СМО

Целью данного курсового проекта является моделирование и анализ канала связи с контролем конфликтов одновременности. Структурная схема заданной СМО приведена на рисунке 1.

Во входной буфер канала связи поступают пакеты данных переменного размера. В буфере размещается только один пакет; если буфер занят — очередной пакет теряется.

На схеме (см. рисунок 1) представлены следующие устройства:

— NAKвходной буфер, в котором может размещаться только 1 пакет;

— S1- Sn-устройства канала в которых обрабатываются пакеты (n-количество устройств позволяющее передавать параллельно любое количество пакетов).

На схеме обозначен выход пакетов из системы:

— V1- вывод из системы обработанных пакетов.

— V2- вывод пакетов, которые не были обработаны.

На вход системы поступают пакеты переменной длины трех типов.

Вероятности поступления пакетов каждого типа составляют: 1 — 0.3; 2 — 0.32; 3 — 0.38. Пакеты передаются по каналу связи. Канал связи может параллельно передавать любое количество пакетов, но между передачами, то есть с момента передачи одного пакета до начала передачи другого пакета, должен иметь место перерыв не менее минимально допустимого интервала для данной пары пакетов с учетом типа. Если это ограничение не выполняется — имеет место конфликт одновременности. Минимально допустимый интервал для всех по-парных возможных сочетаний типов пакетов приведен в таблице 1.

Таблица 1 — Интервалы времени задержек минимально допустимых для каждой пары типов

Конфликт одновременности разрешается задержкой начала передачи конфликтного пакета на 1±0.2 сек. Если после первой задержки конфликт не устраняетсязадержка передачи повторяется по тому же правилу необходимое число раз. Время передачи пакета по каналу зависит от его размера, и распределено по заданному закону.

Характеристики объектов СМО представлены в таблице 2.

Таблица 2 -Интенсивности и законы распределения времени поступления передачи и размеров пакетов в СМО

Примечания: * - четная величина. ** - в расчет на 1 бит.

Выполним классификацию устройств заданной СМО.

Классификационное обозначение СМО имеет вид A/B/C/D/E, где буквенные позиции имеют следующий смысл:

A — обозначение закона распределения времени поступления заявок входного потока (обозначение М соответствует экспоненциальному закону распределения, Г — гамма-распределению, N — нормальному распределению, R — равномерному распределению, D — постоянному времени обслуживания, G — произвольному или неизвестному закону распределения, Gr — групповому (пакетному) поступлению заявок на обслуживание);

B — обозначение закона распределения времени обслуживания в устройствах (используются те же обозначения, что и для распределения времени поступления заявок);

C — число обслуживающих приборов (для одноканальной СМО равно 1, для многоканальной — числу каналов);

D — число мест в очереди (для неограниченных очередей данное обозначение опускается);

E — дисциплина обслуживания (для дисциплины FIFO данное обозначение опускается, также используются обозначения LIFO и RANDOM).

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

Заданный канал передачи пакетов является неоднородным, все его устройства обладают одинаковым законом распределения (экспоненциальным) но типы пакетов разные. От размера пакета зависит время его обработки. Классификационное обозначение заданной СМО: G/M/11 (Примечание — тип распределения времени поступления заявок на вход устройств не определен, так как заявки поступают на входы этих устройств с разными интенсивностями и задержками из-за конфликтов).

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

Пакеты, сгенерированные по экспоненциальному закону (=0.25) поступают в систему. Типы пакетов задаются функцией распределения пакетов по типам: 1 — 0.3; 2 — 0.32; 3 — 0.38.Размер пакетов задается функцией по равномерному закону распределения. Пакеты поступают в буфер канала, в буфере может находиться только 1 пакет; если буфер занят очередной пакет теряется. Запускается отсчет времени, это не обходимо для определения перерыва между передачами. Выполняются проверки на превышение ограничения для каждой пары пакетов. Если это ограничение не выполняется — имеет место конфликт одновременности. Он разрешается задержкой конфликтного пакета на 1±0.2 секунды (задержка будет повторяться необходимое число раз). Из буфера пакет передается к одному из свободных устройств канала. Нахождение пакета в устройстве зависит от его размера. После обработки пакет поступает на выход.

Таким образом, возможные варианты прохождения пакетом СМО:

— пакет входит в буфер обрабатывается без ожидания и выходит;

— пакет входит в буфер, случается конфликт одновременности, после задержки на необходимое время пакет обрабатывается и выходит;

— пакет не входит в буфер (из-за занятости) и удаляется из системы.

1.2 Формализация модели СМО средствами GPSS

имитационный модель gpss формализация cmo

В качестве программного обеспечения моделирования заданием на курсовое проектирование задана среда GPSS World, предназначенная для имитационного вероятностного моделирования систем с дискретными и непрерывными процессами. Для моделирования в GPSS World используются динамические и статические объекты. Динамическими объектами являются заявки, которые создаются в определенных точках модели, продвигаются планировщиком через операторы, а затем уничтожаются. С каждой заявкой связаны параметры, номера или имена которых используются для ссылок на значения, присвоенные параметрам. Заявкам может присваиваться приоритет. Приоритет определяет предпочтение, которое получает заявка, когда она и другие заявки претендуют на один и тот же ресурс. Статические объекты в GPSS World представлены объектами операционной, аппаратной, вычислительной, статистической, запоминающей и группирующей категорий. Каждому объекту соответствуют атрибуты, описывающие его состояние в данный момент времени. Они доступны для использования в процессе моделирования и называются стандартными числовыми атрибутами (СЧА). Исходя из задания на курсовое проектирование с использованием имитационного моделирования в среде GPSS World, необходимо смоделировать канал связи с контролем конфликтов одновременности, построить гистограммы времени пребывания сообщений каждого типа, а также определить следующие характеристики функционирования СМО:

1. Среднее время пакетов каждого типа в системе;

2. Среднеквадратическое отклонение времени пребывания пакетов каждого типа в системе;

3. Среднеквадратическое отклонение времени пребывания пакетов в буфере;

4. Коэффициент использования буфера;

5. Среднее время пребывания пакета в буфере;

6. Коэффициент использования канала;

7. Вероятность возникновения конфликта одновременности;

8. Вероятность потери пакета из-за занятости буфера.

Характеристики функционирования 1. — 5. являются первичными параметрами имитационного моделирования в среде GPSS World, то есть представляют собой СЧА и определяются автоматически встроенными средствами GPSS.

Характеристика первичных параметров моделирования канала связи с конфликтом одновременности приведена в таблице 3.

Характеристики функционирования 6. -8. являются вторичными параметрами. Их оценка с использованием GPSS World может быть осуществлена с использованием первичных параметров программно или расчетно, по результатам статистического моделирования.

Таблица 3 — Первичные параметры моделирования

Вторичными параметрами, подлежащими определению программно или расчетно через первичные параметры (СЧА), согласно заданию на имитационное моделирование канала связи с контролем конфликтов одновременности являются следующие характеристики функционирования:

— коэффициент использования канала;

— вероятность возникновения конфликта одновременности

— вероятность потери пакета из-за занятости буфера.

Введем формулы расчета вторичных параметров моделирования.

Коэффициент использования канала рассчитывается как отношение времени использования канала к общему модельному времени. Нужно учесть то, что канал содержит N устройств, поэтому время использования будет равно времени, в течение которого в устройствах канала находился хоть один пакет. Также время использования канала можно представить как разность между модельным временем и временем простоя канала (временя, в течение которого в канале ни одно устройство не было занято обслуживанием).

Коэффициент использования канала равен:

(1)

где — коэффициент использования канала;

t_мод — время моделирования;

t_{простоя}— время простоя канала.

Согласно теории вероятностей, если некоторое случайное событие, А наступает как следствие какого-либо из n_А событий при общем числе n возможных событий (несовместимых и равновероятных), то вероятностью события, А называют число

.

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

Вероятность возникновения конфликта одновременности равна числу конфликтов к общему числу проверок:

где Р _{конфликта} — вероятность возникновения конфликта;

N_{конфликтов} — количество конфликтов, возникших за время моделирования;

N_{пр_пакетов}— общее количество проверок.

Вероятность потери пакета из-за занятости буфера равна числу потерянных пакетов к общему числу пакетов прошедших через буфер:

где Р_потерь — вероятность потери пакета из-за занятости буфера;

N_{потер_пакетов}— количество пакетов, которое было потеряно из-за занятости буфера;

N_{пакетов}— общее количество пакетов, которые вошли в СМО.

1.3 Имитационное моделирование СМО в среде GPSS World

Рассмотрим принципиальные особенности реализации имитационной вероятностной модели СМО с контролем конфликтов одновременности в среде GPSS World.

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

Таблица 4 — Сохраняемые ячейки программной реализации

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

— размеру пакета;

— типу пакета;

— абсолютное время моделирования (время вхождения в канал; время вхождения в буфер).

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

Таблица 5 — Сохраняемые параметры пакетов

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

Характеристика булевых переменных приведена в таблице 6.

Таблица 6 — Булевы переменные

Кроме этого, в программной реализации имитационной вероятностной модели СМО с контролем конфликтов одновременности имеются следующие особенности:

— для сбора данных о времени пребывания пакетов каждого типа в СМО использованы статистические таблицы с именами Tab1, Tab2 и Tab3 соответственно;

— для сбора данных о времени пребывания пакетов в буфере использована статистическая таблица с именем TBUF;

— для задания типов пакетов использована дискретная функция распределения вероятностей с именами tipe, реализованная в соответствии с исходными данными о вероятностях поступления пакетов каждого типа во входном потоке;

— для задания размеров пакетов использована дискретная функция распределения вероятностей с именами size, реализованная в соответствии с исходными данными о законе распределения пакетов каждого размера во входном потоке;

— для моделирования буфера, ограниченного по количеству мест, использован накопитель с именем NAK;

— неоднократно использовали оператор MARKc записью в параметр активного пакета абсолютного время моделирования при входе пакета в буфер; во время начала обработки пакета; во время выхода пакета из буфера. Так как эти данные сразу записываются в ячейки можно несколько раз использовать один и тот же параметр активного пакета.

Листинг программной реализации имитационной вероятностной модели СМО с контролем конфликтов одновременности в среде GPSS World имеет следующий вид.

ЗАДАНИЕ ТАБЛИЦ:

Tab1 TABLEM1,0,15,15 ;таблица для 1-го типа по времени пребывания пакетов в системе

Tab2 TABLEM1,0,15,18 ;таблица для 2-го типа по времени пребывания пакетов в системе

Tab3 TABLEM1,0,15,15 ;таблица для 3-го типа по времени пребывания пакетов в системе

TBUFTABLEP16,0,0.2,40 ;таблица для определения среднего времени нахождения в буфере ЗАДАНИЕ ФУНКЦИЙ:

функция распределения вероятности по 3-ем типам

0.3,1/0.62,2/1,3 ;вероятности каждого типа

Size FUNCTIONR N2, D9 ;функция генерации размера пакета

0,12/0.125,14/0.250,16/0.375,18/0.5,20/0.625,22/0.75,24/0.875,26/1,28 ;значения вероятностей ЗАДАНИЕ БУЛЕВЫХ ПЕРЕМКННЫХ И СОХРАНЯЕМЫХ ЯЧЕЕК

PROV1 BVARIABLEP11' ;булева функция проверяет равенство 11 параметра заявки 1-му типу

PROV2 BVARIABLEP11'E'2; булева функция проверяет равенство 11 параметра заявки 2-му типу

PROV3 BVARIABLEP11'E'3; булева функция проверяет равенство 11 параметра заявки 3-му типу

PROV5 BVARIABLEF1'OR'F2'OR'F3'OR'F4'OR'F5'OR'F6'OR'F7'OR'F8'OR'F9'OR'F10'OR'F11 ;булева функция проверки на занятость всех устройств, если занято хоть одно устройство то равна 1 иначе 0

INITIALX31,0 ;ячейка хранит время входа в канал предыдущего пакета

INITIALX32,0 ;ячейка хранит время входа в буфер текущего пакета

INITIALX34,0 ;ячейка хранит тип предыдущего пакета

INITIALX35,0 ;ячейка хранит тип текущего пакета

INITIALX37,0 ;ячейка хранит разность между входом в канал предыдущего пакета и входом в буфер текущего

INITIALX40,0 ;ячейка хранит время входа в буфер активного пакета

INITIALX51,0 ;ячейка хранит общее время простоя канала

INITIALX52,0 ;ячейка хранит время завершения простоя канала

INITIALX53,0 ;ячейка хранит время начала простоя канала БЛОК ГЕНЕРАЦИИ ЗАВОК:

NAKSTORAGE 1 ;буфер для хранения 1 пакета

GENERATE (Exponential (1,0,4)) ;эксплненциальный закон распределения генерации пакетов

ASSIGN 10,(FN$size); запись типа в 10-ый параметр заявки

ASSIGN 11,(FN$tipe); запись размера в 11-ый параметр заявки

GATESNFNAK, OUT; если буфер занят, то заявка удаляется из системы

ENTERNAK; помещение заявки в буфер

MARK 15; запись в 15 параметр заявки значения времени входа в буфер

SAVEVALUE 40, P15; запись в ячейку 32 времени вхождения в буфер

TESTEX34,0,STEP1; если значение ячейки Х34 не равно нулю, то заявка отправится в блок проверок

TRANSFER, STEP2; иначе заявка отправится в канал без проверок на задержку, т.к. она первая в системе БЛОК ПРОВЕРКИ:

STEP1 MARK 12; записываем в параметр 12 активной заявки значение времени перед проверкой

SAVEVALUE 32, P12; запись в ячейку 32 значения времени

SAVEVALUE 35, P11; запись в ячейку 35 значения типа активной заявки

SAVEVALUE 37,(X32-X31); запись в ячейку 37 значения разности времени между входом в канал предыдущего пакета и входом в буфер текущего

TESTEBV$PROV1,0,T1; определение типа активного пакета

TESTEBV$PROV2,0,T2; определение типа активного пакета

TESTEBV$PROV3,0,T3; определение типа активного пакета

T1 TESTEX34,1,MET12; сравниваем значение ячейки 34(которая хранит значение типа предыдущего пакета)

TESTGEX37,3.5,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 1 1 при недостатке конфликт

TRANSFER, STEP2; иначе передаем пакет в канал связи

MET12 TESTEX34,2,MET13; сравниваем значение ячейки 34(которая хранит значение типа предыдущего пакета)

TESTGEX37,4.2,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 1 2 при недостатке конфликт

TRANSFER, STEP2; иначе передаем пакет в канал связи

MET13 TESTGEX37,3.8,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 1 3 при недостатке конфликт

TRANSFER, STEP2; иначе передаем пакет в канал связи

T2 TESTEX34,1,MET22; сравниваем значение ячейки 34(которая хранит значение типа предыдущего пакета)

TESTGEX37,5,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 2 1 при недостатке конфликт

TRANSFER, STEP2; иначе передаем пакет в канал связи

MET22 TESTEX34,2,MET23; сравниваем значение ячейки 34(которая хранит значение типа предыдущего пакета)

TESTGEX37,4,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 2 2 при недостатке конфликт

TRANSFER, STEP2; иначе передаем пакет в канал связи

MET23 TESTGEX37,4.8,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 2 3 при недостатке конфликт

TRANSFER, STEP2; иначе передаем пакет в канал связи

T3 TESTEX34,1,MET32; сравниваем значение ячейки 34(которая хранит значение типа предыдущего пакета)

TESTGEX37,5.7,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 3 1 при недостатке конфликт

TRANSFER, STEP2; иначе передаем пакет в канал связи

MET32 TESTEX34,2,MET33; сравниваем значение ячейки 34(которая хранит значение типа предыдущего пакета)

TESTGEX37,4,CONFLICT; сравнение времени обслуживания с заданным для каждой пары типов 3 2 при недостатке конфликт

TRANSFER, STEP2; иначе передаем пакет в канал связи

MET33 TESTGEX37,5.5,CONFLICT ;сравнение времени обслуживания с заданным для каждой пары типов 3 3 при недостатке конфликт

TRANSFER, STEP2; иначе передаем пакет в канал связи БЛОК КАНАЛА

STEP2 MARK 12; запись в параметр 12 активного пакета значения времени вхождения в канал

SAVEVALUE 34, P11; запись в ячейку 34 значения типа пакета

SAVEVALUE 31, P12; запись в ячейку 31 значения времени начала обработки пакета

ASSIGN 9,1

TESTEBV$PROV5,0,MET1; проверка, свободен ли канал

SAVEVALUE 52, P12; если канал свободен записываем в ячейку 52 время завершения простоя канала

SAVEVALUE 51+,(X52-X53); запись в ячейку 51 значения разности времени конца и начала простоя канала

TRANSFER, MET1

INCASSIGN 9+, 1; если устройство было занято то проверка следующего

TRANSFER, MET1

MET1 GATENUP9, INC; проверка свободно ли устройствоPi

SEIZE P9; проверка свободно ли устройство

LEAVENAK; выход пакета из буфера

MARK 15; присвоение 15 параметру заявки значения времени, когда пакет вышел из буфера

ASSIGN 16,(P15-X40); присвоение 16 параметру пакета значения разности времени между входом активного пакета в буфер и выходом из буфера

ADVANCE (Exponential (1,0,P10)) ;реализация экспоненциального закона для обработки заявки в зависимости от размера

RELEASE P9; освобождение уст-ва

TRANSFER, STEP3; перехд к выходной очереди БЛОК КОНФЛИКТА:

CONFLICTADVANCE 1,0.2 ;задержка пакета

TRANSFER, STEP1; возвращение пакета после задержки БЛОК ВЫХОДА

STEP3 TESTEBV$PROV5,0,MET2; провекрка при выходе пакета из канала все устройства свободны

SAVEVALUE 53, P12; если да записываем время начала простоя канала в ячейку 53

TRANSFER, MET2; возвращение пакета в систему

MET2 TABULATETBUF; оператор занесения в таблицу для определения времени нахождения в буфере

TESTEBV$PROV1,0,PT1; определение типа активного пакета: сравниваем значение 11 параметра пакета с возможными значениями типов

TESTEBV$PROV2,0,PT2; сравниваем значение 11 параметра пакета с возможными значениями типов

TESTEBV$PROV3,0,PT3; сравниваем значение 11 параметра пакета с возможными значениями типов

PT1 TABULATE Tab1; оператор занесения в таблицу для типа 1

TRANSFER, QUIT; выход пакета из статистического анализа

PT2 TABULATE Tab2; оператор занесения в таблицу для типа 2

TRANSFER, QUIT; выход пакета из статистического анализа

PT3 TABULATE Tab3; оператор занесения в таблицу для типа 3

TRANSFER, QUIT; выход пакета из статистического анализа

QUITTRANSFER, OUT_OK;выход из системы обработанного пакета

OUT_OKTERMINATE 1; выход из системы обработанного пакета

OUTTERMINATE0; удаление пакета из системы

START50000

Результаты эксперимента по моделированию процесса обслуживания пакетов в заданной СМО с контролем конфликтов одновременности, время моделирования для которой равно 309 640 секунд, были получены в виде полного стандартного отчета GPSS World Simulation Report, приведенного ниже.

1. Общая информация о результатах работы модели:

START TIME END TIME BLOCKS FACILITIES STORAGES

0.0 309 640.750 76 11 1

2. Информация о блоках:

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY

1. GENERATE 77 417 0 0

2. ASSIGN 77 417 0 0

3. ASSIGN 77 417 0 0

4. GATE 77 417 0 0

5. ENTER 50 003 0 0

6. MARK 50 003 0 0

7. SAVEVALUE 50 003 0 0

8. TEST 50 003 0 0

9. TRANSFER 1 0 0

STEP1 10. MARK 160 331 0 0

11. SAVEVALUE 160 331 0 0

12. SAVEVALUE 160 331 0 0

13. SAVEVALUE 160 331 0 0

14. TEST 160 331 0 0

15. TEST 119 915 0 0

16. TEST 67 985 0 0

T1 17. TEST 40 416 0 0

18. TEST 10 976 0 0

19. TRANSFER 4475 0 0

MET12 20. TEST 29 440 0 0

21. TEST 14 135 0 0

22. TRANSFER 4788 0 0

MET13 23. TEST 15 305 0 0

24. TRANSFER 5770 0 0

T2 25. TEST 51 930 0 0

26. TEST 17 271 0 0

27. TRANSFER 4921 0 0

MET22 28. TEST 34 659 0 0

29. TEST 14 078 0 0

30. TRANSFER 5084 0 0

MET23 31. TEST 20 581 0 0

32. TRANSFER 6037 0 0

T3 33. TEST 67 985 0 0

34. TEST 22 786 0 0

35. TRANSFER 5636 0 0

MET32 36. TEST 45 199 0 0

37. TEST 17 364 0 0

38. TRANSFER 6171 0 0

MET33 39. TEST 27 835 0 0

40. TRANSFER 7119 0 0

STEP2 41. MARK 50 002 0 0

42. SAVEVALUE 50 002 0 0

43. SAVEVALUE 50 002 0 0

44. ASSIGN 50 002 0 0

45. TEST 50 002 0 0

46. SAVEVALUE 1121 0 0

47. SAVEVALUE 1121 0 0

48. TRANSFER 1121 0 0

INC 49. ASSIGN 93 311 0 0

50. TRANSFER 93 311 0 0

MET1 51. GATE 143 313 0 0

52. SEIZE 50 002 0 0

53. LEAVE 50 002 0 0

54. MARK 50 002 0 0

55. ASSIGN 50 002 0 0

56. ADVANCE 50 002 2 0

57. RELEASE 50 000 0 0

58. TRANSFER 50 000 0 0

CONFLICT 59. ADVANCE 110 330 1 0

60. TRANSFER 110 329 0 0

STEP3 61. TEST 50 000 0 0

62. SAVEVALUE 1120 0 0

63. TRANSFER 1120 0 0

MET2 64. TABULATE 50 000 0 0

65. TEST 50 000 0 0

66. TEST 34 968 0 0

67. TEST 18 926 0 0

PT1 68. TABULATE 15 032 0 0

69. TRANSFER 15 032 0 0

PT2 70. TABULATE 16 042 0 0

71. TRANSFER 16 042 0 0

PT3 72. TABULATE 18 926 0 0

73. TRANSFER 18 926 0 0

QUIT 74. TRANSFER 50 000 0 0

OUT_OK 75. TERMINATE 50 000 0 0

OUT 76. TERMINATE 27 414 0 0

3. Информация об объектах типа «устройство»:

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

1. 12 583 0.846 20.807 1 77 407 0 0 0 0

2. 11 488 0.773 20.844 1 77 412 0 0 0 0

3. 9859 0.662 20.780 1 0 0 0 0 0

4. 7514 0.512 21.118 1 0 0 0 0 0

5. 4834 0.339 21.709 1 0 0 0 0 0

6. 2472 0.168 21.086 1 0 0 0 0 0

7. 952 0.063 20.594 1 0 0 0 0 0

8. 255 0.018 21.922 1 0 0 0 0 0

9. 36 0.002 20.869 1 0 0 0 0 0

10. 8 0.000 15.767 1 0 0 0 0 0

11. 1 0.000 19.777 1 0 0 0 0 0

4. Информация об ограниченной очереди:

STORAGE CAP. REM. MIN. MAX. ENTRIES AVL. AVE.C. UTIL. RETRY DELAY

NAK 1 0 0 1 50 003 1 0.356 0.356 0 0

5. Информация о сохраняемых величинах (ячейках):

SAVEVALUE RETRY VALUE

31 0 309 636.979

32 0 309 640.741

34 0 1.000

35 0 2.000

37 0 3.762

40 0 309 637.999

51 0 20 893.893

52 0 308 971.151

53 0 308 954.534

Определение характеристик времени пребывания пакетов каждого типа в СМО с контролем конфликтов одновременности включает в себя построение гистограмм времени пребывания, определение среднего времени пребывания и среднеквадратического отклонения времени пребывания.

Гистограмма времени пребывания пакетов типа 1,2 и 3 в СМО с контролем конфликтов одновременности, полученная путем табулирования времени пребывания пакетов за время моделирования с использованием статистических таблиц Tab1, Tab2 и Tab3приведена на рисунках2 — 4 соответственно. Больше 40% пакетов всех типов обслужены меньше чем за 15 секунд — это пакеты маленьких размеров, которые прошли буфер без задержки или с наименьшим числом конфликтов.

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

Фрагмент стандартного отчета GPSS World Simulation Report

TABLE MEAN STD.DEV. RANGE RETRY FREQUENCY CUM.%

TAB1 22.449 21.641

Рисунок 2 — Гистограмма времени пребывания в СМО пакетов типа 1

Фрагмент стандартного отчета GPSS World Simulation Report TAB2 23.521 22.517

Рисунок 3 — Гистограмма времени пребывания в СМО пакетов типа 2

Фрагмент стандартного отчета GPSS World Simulation Report TAB3 23.433 21.851

Рисунок 4 — Гистограмма времени пребывания в СМО пакетов типа 3

Результаты анализа гистограмм, представленных на рисунках 2−4, занесены в таблицу 7.

Таблица 7 — Результаты анализа гистограмм времен пребывания пакетов в СМО

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

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

Фрагмент стандартного отчета GPSS World Simulation Report TBUF 2.207 1.918

Рисунок 5 — Гистограмма времени пребывания пакетов в буфере Из анализа данных, представленных на рисунке 5, следует, что среднее время ожидания пакета в буфере составляет 2.207 секунды (выводится в графе MEAN статистической таблицы), а среднеквадратическое отклонение времени ожидания — 1.918 секунды (выводится в графе STD.DEV. статистической таблицы). При этом только 32.41% заявок (16 205 из числа вошедших в буфер) будут обслужены без ожидания. Такая форма гистограммы обусловлена характером процесса решения конфликта одновременности, который задерживает пакет в буфере.

Результаты анализа функционирования накопителя, занесены в таблицу 9.

Таблица 9 -Результаты анализа функционирования накопителя

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

Коэффициент использования канала, рассчитан по формуле (1), составляет:

Где =309 640.750, общее время моделирования (источник данных: графа стандартного отчета END TIME);

=20 893.893, время простоя канала (источник данных: графа стандартного отчета 51блока SAVEVALUE).

Вероятность возникновения конфликта одновременности P_{конфликта}, рассчитанная по формуле (2), составляет:

Где =110 330,общее количество конфликтов, равно количеству срабатываний оператора задержки пакетов для решения конфликта одновременности;

=160 331, количество пакетов, которые проходили проверку на возможность конфликта, равно количеству пакетов, направленных к меткеSTEP1.

Вероятность потери пакета из-за занятости буфера P_потерь, рассчитанная по формуле (3), составляет:

Где =27 414,общее количество потерянных пакетов, равно количеству срабатываний оператора выхода необработанных пакетов;

=50 000, количество пакетов, сгенерированных за время моделирования.

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

Таблица 10 -Результаты анализа вторичных параметров СМО

2 Анализ и оптимизация системы массового обслуживания

2.1 Формализация модели СМО для задач анализа и оптимизации В качестве дополнительных задач анализа и оптимизации функционирования СМО с контролем конфликтов одновременности заданием на курсовое проектирование определены следующие задачи:

1) построить гистограмму распределения суммарного времени задержки передачи пакетов в процессе решения конфликтов одновременности;

2) определить вероятность возникновения конфликта одновременности для пары пакетов каждого типа;

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

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

(4)

где Р* _{конфликта} — вероятность возникновения конфликта для пары типов;

N*_{конфликтов} — количество конфликтов, возникших за время моделирования для пары типов;

N*_{пр_пакетов}— общее количество проверок для пары типов.

Проверкой правильности решения второй задачи анализа является расчет общей суммы проверок для каждой пары типов и расчет суммы конфликтов для каждой пары типов. Эта сумма очевидно должна быть равна общему количеству проверок и общему количеству конфликтов. Общее количество конфликтов, равно количеству срабатываний оператора задержки пакетов для решения конфликта одновременности. Количество пакетов, которые проходили проверку на возможность конфликта, равно количеству пакетов, направленных к меткеSTEP1 и вошедших в оператор.

2.2 Модификация имитационной модели Рассмотрим принципиальные особенности модификаций исходной имитационной вероятностной модели СМО с контролем конфликтов одновременности в среде GPSS World, реализованных для решения задач анализа и оптимизации.

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

Введение

новых таблиц потребовало модификации для задания таблицы программной реализации вероятностной модели СМО с контролем конфликтов одновременности в среде GPSS World, а также реализации регистрации времени задержки пакета в процессе разрешения конфликта одновременности. Реализации дополнительной идентификации пакетов по флагу конфликта для проверки условий входа пакетов в оператор табулирования времени, для того чтобы выводить статистику только для тех пакетов которые задерживались из-за конфликта одновременности.

Модифицированные фрагменты имитационной вероятностной модели СМО с контролем конфликтов одновременности и описание их функционирования, использованные для решения первой задачи анализа, в среде GPSS World:

1. Объявление таблицы, где будем табулировать 25 параметр пакета (блок задания таблиц):

Time TABLE (P25), 0,0.2,40 ;таблица для времени задержек пакетов во время решения конфликта

2. В блоке входа в систему присвоение каждому пакету (параметр 20) после входа в систему флаг конфликта 0 (0 — неконфликтный пакет, 1 — конфликтный):

ASSIGN 20,0 ;присвоение 20 параметру пакета 0 (флаг конфликта)

3. После выхода пакета из буфера и входа в канал (блок входа в канал) — проверка (по 20 параметру пакета), был ли пакет конфликтным, если да заносим значение времени задержки в таблицу:

STEP2 TESTEP20,1,STR8; проверка если пакет конфликтный

TABULATE Time; занесение результатов в таблицу

4. Изменение блока конфликта для статистического анализа включает: проверку; перевод флага конфликта; определение времени начала и конца задержи в процессе разрешения конфликта; вычисление разности с записью в параметр 25 активного пакета (работает как счетчик):

MET4 TESTEP20,0,MET5 ;проверка флага конфликта если 0 конфликтный пакет пришел 1-й раз

ASSIGN 20,1; флаг переводим в 1

MET5 MARK 28; начало отсчета задержки

ADVANCE 1,0.2; задержка пакета

MARK 29; конец отсчета

ASSIGN 25+,(P29-P28); разность = задержки

TRANSFER, STEP1; возвращение пакета после задержки При решении второй задачи анализа для дополнительных проверок на возможную пару типов использованы булевы переменные, также переназначен 12 параметр пакета, в который теперь записывалась пара типов для каждого пакета. Характеристика использованных булевых переменных представлена в таблице 11.

Таблица 11- Булевы переменные модификации модели, реализованной для решения второй задачи анализа

Для сохранения количества проверок и количества пакетов для каждой пары типов, были использованы сохраняемые ячейки GPSS. Также вычисление и запись значения вероятностей возникновения конфликтов одновременности для каждой пары пакетов производился в ячейки. Характеристика использованных сохраняемых ячеек GPSS приведена в таблице 12 (начальное значение всех используемых ячеек равно 0).

Таблица 12 — Сохраняемые ячейки модификации модели, реализованной для решения второй задачи анализа

Введение

новых ячеек и булевых переменных потребовало модификации блока задания булевых переменных и сохраняемых ячеек в программной реализации вероятностной модели СМО с контролем конфликтов одновременности в среде GPSS World, а необходимость организации сохранения соответствующих значений количества в заданные ячейки — модификации блока проверок и блока конфликтов. Модификация состояла во введение учета количества пакетов прошедших проверки и количество конфликтных пакетов для каждой пары типов. Для этого был использован оператор SAVEVALUE, увеличивающий значение соответствующей ячейки на 1для подсчета количества.

Модифицированные фрагменты имитационной вероятностной модели многопоточной СМО с отказами доступа входных очередей, использованной для решения второй задачи анализа, в среде GPSS World имеют следующий вид:

ЗАДАНИЕ БУЛЕВЫХ ПЕРЕМКННЫХ И СОХРАНЯЕМЫХ ЯЧЕЕК:

PROV1 BVARIABLEP11'E'1; булева функция проверяет равенство 11 параметра пакета заданному типу

PROV2 BVARIABLEP11'E'2; булева функция проверяет равенство 11 параметра пакета заданному типу

PROV3 BVARIABLEP11'E'3; булева функция проверяет равенство 11 параметра пакета заданному типу

PROV11 BVARIABLEP12'E'11; булевая функция проверяет равенство 12 параметра пакета заданной паре типов для 1 1

PROV12 BVARIABLE P12'E'12; для 1 2

PROV13 BVARIABLE P12'E'13; для 1 3

PROV21 BVARIABLE P12'E'21; для 2 1

PROV22 BVARIABLE P12'E'22; для 2 2

PROV23 BVARIABLE P12'E'23; для 2 3

PROV31 BVARIABLE P12'E'31; для 3 1

PROV32 BVARIABLE P12'E'32; для 3 2

PROV33 BVARIABLE P12'E'33; для 3 3

INITIALX31,0; ячейка хранит время входа в канал предыдущего пакета

INITIALX32,0; ячейка хранит время входа в буфер текущего пакета

INITIALX34,0; ячейка хранит тип предыдущего пакета

INITIALX35,0; ячейка хранит тип текущего пакета

INITIALX37,0; ячейка хранит разность между входом в канал предыдущего пакета и входом в буфер текущего

INITIALX11,0; счетчик количества конфликтов для пары типов 1 1

INITIAL X12,0; для 1 2

INITIAL X13,0; для 1 3

INITIAL X21,0; для 2 1

INITIAL X22,0; для 2 2

INITIAL X23,0; для 2 3

INITIAL X41,0; для 3 1

INITIAL X42,0; для 3 2

INITIALX43,0; для 3 3

INITIALX17,0; счетчик количества проверок на конфликт для пары типов 1 1

INITIAL X18,0; для 1 2

INITIAL X19,0; для 1 3

INITIAL X27,0; для 2 1

INITIAL X28,0; для 2 2

INITIAL X29,0; для 2 3

INITIAL X47,0; для 3 1

INITIAL X48,0; для 3 2

INITIAL X49,0; для 3 3

INITIALX14,0; ячейка для хранения вероятности наступления конфликта для пары 1 1

INITIAL X15,0; для 1 2

INITIAL X16,0; для 1 3

INITIAL X24,0; для 2 1

INITIAL X25,0; для 2 2

INITIAL X26,0; для 2 3

INITIAL X44,0; для 3 1

INITIAL X45,0; для 3 2

INITIAL X46,0; для 3 3

CONFLICTTESTEBV$PROV11,0,T11 ;проверка пакет какой пары типов пришел для 1 1

TEST E BV$PROV12,0,T12; для 1 2

TEST E BV$PROV13,0,T13; для 1 3

TEST E BV$PROV21,0,T21; для 2 1

TEST E BV$PROV22,0,T22; для 2 2

TEST E BV$PROV23,0,T23; для 2 3

TEST E BV$PROV31,0,T31; для 3 1

TEST E BV$PROV32,0,T32; для 3 2

TEST E BV$PROV33,0,T33; для 3 3

T11 SAVEVALUE 11+, 1; пополняем счетчик количества конфликтов для пары типов 1 1

TRANSFER, MET4; возвращаем пакет в систему

T12 SAVEVALUE 12+, 1; пополняем счетчик количества конфликтов для пары типов 1 2

TRANSFER, MET4; возвращаем пакет в систему

T13 SAVEVALUE 13+, 1; пополняем счетчик количества конфликтов для пары типов 1 3

TRANSFER, MET4; возвращаем пакет в систему

T21 SAVEVALUE 21+, 1; пополняем счетчик количества конфликтов для пары типов 2 1

TRANSFER, MET4; возвращаем пакет в систему

T22 SAVEVALUE 22+, 1; пополняем счетчик количества конфликтов для пары типов 2 2

TRANSFER, MET4; возвращаем пакет в систему

T23 SAVEVALUE 23+, 1; пополняем счетчик количества конфликтов для пары типов 2 3

TRANSFER, MET4; возвращаем пакет в систему

T31 SAVEVALUE 41+, 1; пополняем счетчик количества конфликтов для пары типов 3 1

TRANSFER, MET4; возвращаем пакет в систему

T32 SAVEVALUE 42+, 1; пополняем счетчик количества конфликтов для пары типов 3 2

TRANSFER, MET4; возвращаем пакет в систему

T33 SAVEVALUE 43+, 1; пополняем счетчик количества конфликтов для пары типов 3 3

TRANSFER, MET4; возвращаем пакет в систему

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

Рисунок 6 — Гистограмма суммарного времени задержки передачи пакетов в процессе разрешения конфликтов одновременности Из анализа данных, представленных на рисунке 6, следует, что среднее времени задержки передачи пакетов в процессе разрешения конфликтов одновременности составляет 3.265 секунд (выводится в графе MEAN статистической таблицы), а среднеквадратическое отклонение времени пребывания — 1.411 секунд (выводится в графе STD.DEV. статистической таблицы).

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

Результаты эксперимента, осуществленного для решения второй задачи анализа, состоящего в определении вероятности возникновения конфликта для пары пакетов каждого типа в СМО с контролем конфликтов одновременности были получены в виде полного стандартного отчета GPSS World Simulation Report. Фрагмент стандартного отчета, содержащий информацию о сохраняемых ячейках, приведен ниже.

SAVEVALUE RETRY VALUE

11 0 6501.000

12 0 9347.000

13 0 9535.000

14 0 0.592

15 0 0.661

16 0 0.623

17 0 10 976.000

18 0 14 135.000

19 0 15 305.000

21 0 12 349.000

22 0 8994.000

23 0 14 544.000

24 0 0.715

25 0 0.639

26 0 0.707

27 0 17 270.000

28 0 14 078.000

29 0 20 581.000

31 0 309 636.979

32 0 309 639.847

34 0 1.000

35 0 2.000

37 0 2.868

41 0 17 150.000

42 0 11 193.000

43 0 20 716.000

44 0 0.753

45 0 0.645

46 0 0.744

47 0 22 786.000

48 0 17 364.000

49 0 27 835.000

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

Таблица 13 — Вероятности возникновения конфликтов одновременности для пары пакетов каждого типа

Выводы В результате курсового проектирования по теме «Моделирование канала связи с контролем конфликтов одновременности» решены следующие задачи и получены результаты:

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

2. Осуществлена формализация модели СМО средствами GPSSWorld. Определены способы получения средствами GPSSWorld характеристик функционирования СМО, отнесенных к первичным параметрам моделирования и являющихся СЧА. Введены формулы расчета по результатам статистического моделирования характеристик функционирования СМО, являющихся вторичными параметрами, а именно:

— коэффициент использования канала;

— вероятность возникновения конфликта одновременности;

— вероятность потери пакета из-за занятости буфера;

1. Осуществлена реализация имитационной вероятностной модели СМО с контролем конфликтов одновременности в среде GPSS World. Принципиальными особенностями реализации является использование:

— сохраняемых ячеек GPSS для хранения значения типа предыдущего пакета, времени входа в буфер, разности между входом в буфер и началом обслуживания;

— идентификации пакета по типу, размеру с сохранением в параметры пакета № 10 и № 11 соответствующих целочисленных значений, а также его время пребывания в буфере параметр № 16;

2. Проведен эксперимент по моделированию процесса обслуживания заявок в СМО часов с получением результатов в виде полного стандартного отчета GPSS World Simulation Report. По результатам эксперимента определены все характеристики функционирования СМО по части 1 задания на курсовое проектирование.

Во второй части курсового проекта:

1. В соответствии с заданием на решение дополнительных задач анализа и оптимизации функционирования СМО с контролем конфликтов одновременности выбраны способы решения и осуществлена дополнительная формализация модели, а именно выведена формула определения вероятности возникновения конфликта одновременности для пары пакетов каждого типа;

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

3. Решена вторая задача анализа — определение вероятности возникновения конфликта одновременности для пары пакетов каждого типа. Особенностью модификации имитационной модели является использование ячеек GPSS для сохранения количества проверок на возможность конфликта и количества конфликтов для пары пакетов каждого типа, а также в ячейки были записаны значения вероятностей;

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

Таблица 16

1. Советов Б. Я., Яковлев С. А. Моделирование систем. Учебник для вузов. -М.:Высш. шк., 2005.-343c.

2. Тарасик В. П. Математическое моделирование технических систем. -Мн.: Дизайн ПРО, 2004.-640c.

3. Боев В. Д. Моделирование систем. Инструментальные средства GPSS World: Учебное пособие. -СПБ.: БХВ-Петербург, 2004.-348c.