Компьютерное моделирование систем массового обслуживания

ВОЕННАЯ АКАДЕМИЯ ВОЙСКОВОЙ ПРОТИВОЗДУШНОЙ ОБОРОНЫ ВООРУЖЕННЫХ СИЛ РОССИЙСКОЙ ФЕДЕРАЦИИ ИМЕНИ МАРШАЛА СОВЕТСКОГО СОЮЗА А.М. ВАСИЛЕВСКОГО

Кафедра «Программное обеспечение и автоматизированные системы»

Факультет «Радиотехника и информационные технологии»

Курсовая работа

Дисциплина: «Моделирование систем»

Тема: «Компьютерное моделирование систем массового обслуживания»

Пояснительная записка

ВА ВПВО.230102.24 ПЗ

Выполнила:

студентка

Силаева Л.В.

уч. группа 5ЗП

Руководитель:

Денисова И.А

г. Смоленск 2010 г.

Аннотация

При использовании языка (системы) имитационного моделирования дискретных систем GPSS/PC, позволяющий автоматизировать при моделировании систем процесс программирования моделей, производится определение работы ЭВМ по обслуживанию поступающих на них заявок. Произведено моделирование системы, сделаны соответствующие выводы по ее работе.

Введение

Сущность машинного моделирования системы состоит в проведении на ЭВМ эксперимента с моделью этой системы, что способствует уменьшению риска провала эксперимента, проводимого непосредственно опытным путем. Тем самым уменьшая экономические затраты, а так же повышая безопасность персонала при сложном эксперименте, если нет уверенности в положительном исходе последнего. В настоящее время метод машинного моделирования нашел широкое применение при разработке обеспечивающих и функциональных подсистем различных интегрированных АСУ, автоматизированных подсистем научных исследований и комплексных испытаний, систем автоматизации проектирования и т.д. При этом независимо от объекта можно выделить следующие основные этапы моделирования: построение концептуальной модели системы и ее формализация; алгоритмизация модели системы и ее машинная реализация; получение результатов машинного моделирования и их интерпретация.

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

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

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

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

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

Язык GPSS построен в предположении, что моделью сложной дискретной системы является описание ее элементов и логических правил их взаимодействия в процессе функционирования моделируемой системы. Далее предполагается, что для определенного класса моделируемых систем можно выделить небольшой набор абстрактных элементов, называемых объектами. Причем набор логических правил также ограничен и может быть описан небольшим числом стандартных операций. Комплекс программ, описывающих функционирование объектов и выполняющих логические операции, является основой для создания программной модели системы данного класса. Эта идея и была реализована при разработке языка GPSS. На персональных компьютерах (ПК) язык GPSS реализован в рамках пакета прикладных программ GPSS/PC. Основной модуль пакета представляет собой интегрированную среду, включающую помимо транслятора со входного языка средства ввода и редактирования текста модели, ее отладки и наблюдения за процессом моделирования, графические средства отображения атрибутов модели, а также средства накопления результатов моделирования в базе данных и их статистической обработки. Кроме основного модуля, в состав пакета входит модуль создания стандартного отчета GPSS/PC.

Для решения поставленной задачи использовались следующие литературные и электронные источники: Советов Б.Я., Яковлев С.А. Моделирование систем, Советов Б.Я., Яковлев С.А. Моделирование систем. Практикум, Л.А. Воробейчиков, Г.К. Сосновиков Основы моделирование на GPSS.

1. Построение концептуальной модели

1.1 Постановка задачи

Вычислительная система включает три ЭВМ. В систему в среднем через 30 с поступают задания, которые попадают в очередь на обработку к первой ЭВМ, где они обрабатываются около 30 с. После этого задание поступает одновременно во вторую и третью ЭВМ. Вторая ЭВМ может обработать задание за 14±5 с, а третья - за 16±1с. Окончание обработки задания на любой ЭВМ означает снятие ее с решения с той и другой машины. В свободное время вторая и третья ЭВМ заняты обработкой фоновых задач.

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

1.2 Описание моделируемой системы

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

Примем за единицу модельного времени 1с., следовательно, при моделировании 4 часов работы системы, время моделирования будет равно 14400 с.

1.3 Основные понятия и определения

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

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

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

Система S - целенаправленное множество взаимосвязанных элементов любой природы.

Внешняя среда Е - множество существующих вне системы элементов любой природы, оказывающих влияние на систему или находящихся под ее воздействием.

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

Транзакты (сообщения) - это динамические объекты GPSS/PC.Они создаются в определенных точках модели, продвигаются интерпретатором через блоки, а затем уничтожаются. Сообщения являются аналогами единиц - потоков в реальной системе S.Сообщения могут представлять собой различные элементы даже в одной системе S.

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

В GPSS/PC многоканальные устройства представляют собой объекты типа «оборудование» для параллельной обработки, они могут быть использованы несколькими транзактами (сообщениями) одновременно. Многоканальные устройства используются для представления физического оборудования, например, зрительного зала театра, стоянка автомобилей и, в некоторых случаях основной памяти в системах для обработки данных. Пользователь определяет емкость каждого многоканального устройства, используемого в модели, а интерпретатор ведет учет числа единиц многоканальных устройств, занятых в каждый момент времени. Если сообщение пытается занять больше единиц многоканального устройства, чем свободно в данный момент, обработка этого сообщения задерживается до того момента, пока в многоканальном устройстве освободится достаточный объем. Программа автоматически ведет подсчет числа транзактов, входящих в многоканальное устройство, а также определяет среднее число единиц многоканальных устройств, занятых одним сообщением, и среднее время пребывания транзакта (сообщения) в многоканальном устройстве. Эти статистические данные выдаются в конце счета и позволяют определить, насколько эффективно используются в системе объекты параллельной обработки и достаточна ли их емкость.

Структура программы на GPSS/PC базируется на блок-диаграмме, согласно которой осуществляется продвижение транзактов. С реальными объектами в моделирующей системе GPSS связана совокупность блоков, имеющих специальное обозначение и формат описания (записи).

Устройства в системе GPSS/PC формируются с помощью блоков SEIZE, RELEASE, PREEMPT, RETURN. Наличие в модели устройств позволяет автоматически регистрировать статистическую информацию. Устройства моделируют реальные объекты, в которых может происходить обработка транзактов (сообщений). В GPSS предусмотрена возможность прерывания устройств. Имеются средства логической проверки состояния устройств (свободно, занято, прервано, не прервано). Захват (на обработку) и освобождение устройства моделируются соответственно блоками SEIZE и RELEASE. Прерывание устройства моделирует блок PREEMPT, снятие прерывания - блок RETURN. Проверка состояния устройства осуществляется блоком GATE.

Если в системе S может происходить задержка в прохождении сообщения или задержка в его обработке, то тогда возникает очередь. Для сбора и регистрации статистики об очередях в моделирующей системе ставят блоки QUEUE и DEPART. При входе сообщения (транзакта) в блок QUEUE текущая длинна очереди получает приращение. Уход сообщения из очереди отображается блоком DEPART.

Для сбора статистических данных и их регистрации используют таблицы, которые моделируются блоком TABULATE и оператором TABLE. Занесение интересующей информации в таблицу осуществляется блоком TABULATE в момент входа очередного транзакта в этот блок. Описание структуры таблицы и типа заносимых данных (стандартизированных самой системой GPSS) осуществляется оператором TABLE.

1.4 Q- схема модели

nac1 ЭВМ2

nac2 ЭВМ3

Рис. 1

Из данной схемы (рис. 1) следует, что задания поступают от какого либо источника (им может быть пользователь, программа, процесс и т.д.) на первую ЭВМ. Далее после обработки задания одновременно отправляются на вторую и третью ЭВМ, но так как перед ними образуются очереди, то сначала они попадают в накопители, а затем уже на соответствующие ЭВМ. Затем, после обработки, они следуют к клапанам, стоящим после третьей и второй ЭВМ. Клапан ЭВМ2 связан с ЭВМ3, это означает что клапан закрыт пока не будет снята с решения задача с ЭВМ3. И соответственно клапан ЭВМ3 связан с ЭВМ2, то есть клапан закрыт пока не будет снята с решения задача с ЭВМ2. И затем уже решенные задачи движутся к выходу из системы.

1.5 Структурная схема

Фоновые

задачи

Фоновые

задачи

Рис. 2

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

2. Алгоритмизация модели

2.1 Листинг программы

generate 14400 // генерирование 4 часов работы системы

terminate 1

savevalue KOL,0 //инициализация переменной KOL

savevalue K1,0 // инициализация переменной K1

savevalue K2,0 // инициализация переменной K2

savevalue K3,0 // инициализация переменной K3

time1 table ft$1,25,1,6 //инициализация таблицы time1

time2 table ft$2,10,1,6 //инициализация таблицы time2

time3 table ft$3,13,1,5 //инициализация таблицы time3

generate(exponential(1,0,30)) //генерирование заявок

savevalue KOL+,1 //сохранение количества сгенерированных

заявок

seize 1 //занятие устройства 1(ЭВМ1)

advance (exponential(2,0,30)) //задержка заявки в устройстве на обработку

savevalue K1+,1 //сохранение количества заявок обработанных в

ЭВМ1

tabulate time1 //вывод функции распределения времени

обработки заявок в ЭВМ1

release 1 //освобождение ЭВМ1

split 1,pcc3 //переход от ЭВМ1 к ЭВМ2 и ЭВМ3

pcc2 queue 2 //занятие очереди перед ЭВМ2

seize 2 //занятие ЭВМ2

advance 14,5 //обработка заявки в ЭВМ2

savevalue K2+,1 //сохранение количества заявок обработанных в

ЭВМ2

tabulate time2 //вывод функции распределения времени

обработки заявок в ЭВМ2

release 2 //освобождение ЭВМ2

gate U 3,out //проверка занятости ЭВМ3

preempt 3,,out,,RE //прерывание ЭВМ3,переход по метке out

pcc3 queue 3 //занятие очереди перед ЭВМ3

seize 3 //занятие ЭВМ3

advance 16,1 //задержка заявки на обработку

savevalue K3+,1 //сохранение количества заявок обработанных в

ЭВМ3

tabulate time3 //вывод функции распределения времени

обработки

//заявок в ЭВМ3

release 3 //освобождение ЭВМ3

gate U 2,out //проверка занятости ЭВМ2

preempt 2,,out,,RE //прерывание ЭВМ2,переход по метке out

out assemble 2 //уничтожает транзакты

start 1 //начальное значение счетчика завершений

Переменные:

KOL - количества сгенерированных заявок

К1 - количества заявок обработанных в ЭВМ1

К2 - количества заявок обработанных в ЭВМ2

К3 - количества заявок обработанных в ЭВМ3

2.2 Блок-диаграмма

Kol,0

K1,0

K2,0

K3,0

K1+,1

Рис. 3



Рис. 4

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

Для анализа моделирования необходимо выбрать метку Command верхнем поле стандартного окна программы GPSS/PC и выбрать Create Simulation. Пред пользователем открывается окно журнала:

12/28/09 13:40:44 Model Translation Begun.

12/28/09 13:40:44 Ready.

12/28/09 13:40:44 Simulation in Progress.

12/28/09 13:40:44 The Simulation has ended. Clock is 14400.000000.

12/28/09 13:40:44 Reporting in model kurs2342.34.1 - REPORT Window.

и окно с отчетом, который представлен в приложении.

В результате моделирования были получены следующие данные, которые приведены в стандартном отчете пакета GPSS, по данным отчета можно сделать следующие выводы:

1. Модельное время начала START =0, конца END_TIME =14400, количество блоков в модели BLOCKS=33, количество устройств FACIL=6, количество МКУ STORAG=0.

START TIME END TIME BLOCKS FACILITIES STORAGES

0.0 14400.000 33 6 0

2. Необходимая емкость накопителей=1, т.к. заявки поступают на ЭВМ1 через 30с., и обрабатываются в ней за то же время. А в ЭВМ2 и ЭВМ3 эти же заявки дорабатываются еще быстрее, отсюда можно сделать вывод, надобности в накопителях перед ЭВМ нет, при данных условиях задачи.

3. Коэффициенты загрузки ЭВМ: ЭВМ1=0,924; ЭВМ2=0,369; ЭВМ3=0,705;

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

1 442 0.924 30.103 1 881 0 0 0 5

2 638 0.369 8.323 1 0 0 0 0 0

3 929 0.705 10.933 1 0 0 0 0 0

4. Функции распределения времени обслуживания заданий:

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

TIME1 0.000 0.000 0

_ - 25.000 441 100.00

TIME2 0.000 0.000 0

_ - 10.000 244 100.00

TIME3 0.000 0.000 0

_ - 13.000 441 100.00

Для ЭВМ1 в функции распределения времени обслуживания заданий есть только 1 интервал времени 25-30, куда попадают все заявки, т.к. среднее время обработки заявки на ЭВМ1 = 30с. Следовательно можно сделать вывод, что на выполнение каждой заявки ей требуется время от 25 до 30 с.

Накопленная частота в % - определяет процент выполненных заявок от их общего количества к данному интервалу времени.

Производительность ЭВМ2 и ЭВМ3 по выполнению фоновых задач можно определить как:

· Сумму времени простоя разделить на время выполнения 1 фоновой задачи.

ЭВМ2: время простоя =(30-14,5)*244=3782., время выполнения 1 фоновой задачи =120 с.

Количество решенных фоновых задач = 3782/120=31 задач

ЭВМ3: время простоя =(30-16,1)*441=6129,9с., время выполнения 1 фоновой задачи =120 с.

Количество решенных фоновых задач = 6129,9/120=51 задач

Заключение

В результате машинного моделирования системы были получены следующие результаты работы трех ЭВМ по обработке заданий, поступающих от какого либо источника (им может быть пользователь, программа, процесс и т.д.) в течение 4 часов:

Количество обработанных заявок = 447.

Коэффициенты загрузки ЭВМ: ЭВМ1=0,924; ЭВМ2=0,369; ЭВМ3=0,705.

Количество решенных фоновых задач - 82.

Необходимая емкость накопителей перед всем ЭВМ - 1.

По результатам моделирования работы системы ЭВМ, можно предложить следующие улучшения: при данных условия задачи можно исключить накопители перед всеми ЭВМ, ЭВМ3 так же можно исключить, если отсутствует необходимость в решении фоновых задач или их количество невелико (по результатам моделирования не превышает 20 задач/час), т.к. с этой работой может вполне справиться ЭВМ2.

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

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

1. Советов Б.Я., Яковлев С.А. Моделирование систем / Учеб. пособие для вузов по спец. «Автоматизир. системы обработки информ. и упр.». - М.: Высш. шк., 1999. - 224 с.

2. Советов Б.Я., Яковлев С.А. Моделирование систем. Практикум: Учеб. пособие для вузов по спец. «Автоматизир. системы обработки информ. и упр.». - М.: Высш. шк., 1999. - 224 с.

3. Л.А. Воробейчиков, Г.К. Сосновиков Основы моделирование на GPSS/PC: Методические указания по моделированию систем и сетей связи на GPSS/PC для слушателей по спец. «ФПКП» часть 1/МИС. - М., 1993. - Ил. 24, список лит. 8 назв. (www.education.ru/referat/pintref/id_20423_1.html).

Приложение

GPSS World Simulation Report - model kurs2342.34.1

Monday, December 28, 2009 13:40:44

START TIME END TIME BLOCKS FACILITIES STORAGES

0.000 14400.000 33 6 0

NAME VALUE

K1 10004.000

K2 10005.000

K3 10006.000

KOL 10003.000

OUT 33.000

PCC2 15.000

PCC3 24.000

TIME1 10000.000

TIME2 10001.000

TIME3 10002.000

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY

1 GENERATE 1 0 0

2 TERMINATE 1 0 0

3 SAVEVALUE 0 0 0

4 SAVEVALUE 0 0 0

5 SAVEVALUE 0 0 0

6 SAVEVALUE 0 0 0

7 GENERATE 447 0 0

8 SAVEVALUE 447 5 0

9 SEIZE 442 0 0

10 ADVANCE 442 1 0

11 SAVEVALUE 441 0 0

12 TABULATE 441 0 0

13 RELEASE 441 0 0

14 SPLIT 441 0 0

PCC2 15 QUEUE 441 0 0

16 SEIZE 441 0 0

17 ADVANCE 441 0 0

18 SAVEVALUE 244 0 0

19 TABULATE 244 0 0

20 RELEASE 244 0 0

21 GATE 244 0 0

22 PREEMPT 244 0 0

23 RETURN 244 0 0

PCC3 24 QUEUE 685 0 0

25 SEIZE 685 0 0

26 ADVANCE 685 0 0

27 SAVEVALUE 441 0 0

28 TABULATE 441 0 0

29 RELEASE 441 0 0

30 GATE 441 0 0

31 PREEMPT 197 0 0

32 RETURN 197 0 0

OUT 33 ASSEMBLE 882 0 0

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

1 442 0.924 30.103 1 881 0 0 0 5

2 638 0.369 8.323 1 0 0 0 0 0

3 929 0.705 10.933 1 0 0 0 0 0

TIME1 0 0.000 0.000 1 0 0 0 0 0

TIME2 0 0.000 0.000 1 0 0 0 0 0

TIME3 0 0.000 0.000 1 0 0 0 0 0

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

2 441 441 441 0 207.208 6765.965 6765.965 0

3 685 685 685 0 321.685 6762.425 6762.425 0

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

TIME1 0.000 0.000 0

_ - 25.000 441 100.00

TIME2 0.000 0.000 0

_ - 10.000 244 100.00

TIME3 0.000 0.000 0

_ - 13.000 441 100.00

SAVEVALUE RETRY VALUE

KOL 0 447.000

K1 0 441.000

K2 0 244.000

K3 0 441.000

FEC XN PRI BDT ASSEM CURRENT NEXT PARAMETER VALUE

881 0 14411.092 881 10 11

890 0 14469.355 890 0 7

891 0 28800.000 891 0 1