Имитационная модель СМО

 Введение 

Имитационная модель СМО представляет собой алгоритм, отражающий поведение СМО, т.е. отражающий изменения состояния СМО во времени при заданных потоках заявок, поступающих на входы системы. Параметры входных потоков заявок - внешние параметры СМО. Выходными параметрами являются величины, характеризующие свойства системы - качество ее функционирования. Примеры выходных параметров:  производительность СМО - среднее число заявок, обслуживаемых в единицу времени; коэффициенты загрузки оборудования - отношение времен обслуживания к общему времени в каждом ОА;  среднее время обслуживания одной заявки. Основное свойство ОА, учитываемое в модели СМО, - это затраты времени на обслуживание, поэтому внутренними параметрами в модели СМО являются величины, характеризующие это свойство ОА. Обычно время обслуживания рассматривается как случайная величина и в качестве внутренних параметров фигурируют параметры законов распределения этой величины.  
      Имитационное моделирование позволяет исследовать СМО при различных  типах входных потоков и интенсивностях поступления заявок на входы, при вариациях параметров ОА, при различных дисциплинах обслуживания заявок. Дисциплина обслуживания - правило, по которому заявки поступают из очередей на обслуживание. Величина, характеризующее право на первоочередное обслуживание, называется приоритетом. В моделях СМО заявки, приходящие на вход занятого ОА, образуют очереди, отдельные для заявок каждого приоритета. При освобождении  ОА на обслуживание принимается заявка из непустой очереди с наиболее высоким приоритетом.  
      Основной тип ОА - устройства, именно в них происходит обработка транзактов с затратами времени. К ОА относятся также накопители (памяти), отображающие средства хранения обрабатываемых деталей в производствееных линиях или обрабатываемых данных в вычислительных системах. Накопители характеризуются не временами обслуживания заявок, а емкостью - максимально возможным количеством одновременно находящихся в накопителе заявок.  
       К элементам имитационных моделей СМО кроме ОА относят также узлы и источники заявок. Связи ОА между собой реализуют узлы, т.е. характерезуют правила, по которым заявки направляются к тому или иному ОА.  
       Для описания моделей СМО при их исследовании на ЭВМ разработаны специальные языки имитационного моделирования. Существуют общецелевые языки, ориентированные на описание широкого класса СМО в различных предметных областях, и специализированные языки, предназначенные для анализа систем определенного типа. Примером общецелевых языков служит широко распространенный  язык  GPSS, примером специализированного языка - язык МПЛ/ВС моделирования вычислительных систем.

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

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

В ходе проверки достоверности модели необходимо ответить на следующие вопросы:

• Позволяет  ли модель решить поставленные задачи моделирования?

• Насколько  полна предложенная схема модели?

• Отражает ли она фактическую последовательность развития процессов в реальной системе?

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

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

Результатом этапа  является проверенное формальное описание исследуемой системы на выбранном  языке формализации. Моделирование систем может происходить в различных языках программирование, что значительно усложняет этапы моделирования, для того чтобы облегчить создание моделей прибегают к специализированным средам разработки имитационных моделей систем различной сложности, таким как например: MatLab (Simulink), Simula, Simscript, GPSS и другие.

В данной курсовой работе построение и исследование модели будет

производиться в языке моделирования GPSS, а математическая часть рассчитана на языке высокого уровня Delphi 2010 так как это высоко интегрированная компьютерная среда моделирования общего назначения. А также это мощный инструмент моделирования покрывающий и дискретное и непрерывное компьютерное моделирование, с высоким уровнем взаимодействия и визуализации. Для данной работы этот программный продукт подходит полностью, как для быстрого изучения , так и для реализации поставленной задачи.

 

1 Анализ технического задания

 

В курсовой работе требуется разработать имитационную модель вычислительной системы.(Вариант №28).

Информационно- поисковая библиографическая система  построена на базе двух ЭВМ и имеет  один терминал для ввода и вывода информации. Первая ЭВМ обеспечивает поиск литературы по научно- техническим  проблемам (вероятность обращения  к ней -0,7), а вторая – по медицинским (вероятность обращения к ней -0,3). Пользователи обращаются к услугам системы каждые 5±2 минуты. Если в очереди к терминалу ожидают 10 пользователей, то вновь прибывшие пользователи получают  отказ в обслуживании. Поиск информации на первой ЭВМ продолжается 6±4 минуты, а на второй 3±2 минуты. Для установления связи с нужной ЭВМ и передачи текста запроса пользователи тратят 2±1минуту. Вывод результатов поиска происходит за 1 минуту.

Смоделировать процесс работы системы за 8 часов. Определить среднюю и максимальную длину очереди к терминалу, а так же коэффициенты загрузки технических средств системы. Как изменится параметры очереди к терминалу, если будет установлен еще один терминал?  

В ходе курсовой работы необходимо исследовать  следующие вопросы:

• Разработка Q- схемы модели;
• Разработка сети Петри модели;
• Разработка графа состояния системы;
• Выбор и обоснование алгоритмов;
• Описание математической модели;
• Описание инструментария;
• Описание пользовательского интерфейса;
• Описание результатов моделирования;

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

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

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

 

2 Выбор и обоснование алгоритмов решения задачи

 

Для моделирования  системы в языке GPSS, необходимо выполнить следующие решение алгоритмов, таких как:

• Разработка графа состояния системы;
• Разработка Q- схемы модели;
• Разработка сети Петри модели;

 

1. Разработка графа состояния системы

 

Рассмотрим построение графа состояния модели:

Рассматриваемая система относится к СМО. Построим граф состояний системы. Состояния  системы могут быть следующими:

S0- свободен первый канал;

S1- первый канал занят;

S2- очередь;

S3- свободен второй канал;

S4- второй канал занят;

S5- очередь;

S6- свободен третий канал(вводим для терминала);

S7- третий канал занят;

S8- очередь;

Получим граф состояния :

Данная система  состоит из трех фаз, каждая фаза является одно канальной системой с ожиданием.

2. Разработка Q-схемы модели:

 

При обслуживание заявок можно выделить две основные составляющие: ожидание, обслуживание заявок. Это можно отобразить в  виде некоторого прибора П_i состоящего из канала и некоторого накопителя с определенной емкостью.

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

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

 

 

3. Разработка сети Петри модели:

 

• это двудольный (направленный граф);
• это аппарат для моделирования динамических систем (процессов). В основном (асинхронных, параллельных процессов). Асинхронный- это процесс в котором имеется временная независимость одного процесса от другого.

Сеть Петри  определяется, как четверка множеств < P,T,I,O>,

где Р- множество  вершин (позиций) ;

Т- множество  переходов;

I,O- множество входных и выходных функций.

Позициям вершинам –О, соответствуют переходы I. Функции I соответствуют дуги, которые идут от позиций к переходам. Функции О, которые идут от перехода к позиции.

Ниже приведена  сеть Петри, для исследуемой модели:

Опишем сеть Петри

p0 – Ожидание к терминалу;

p1 – Источник ЭВМ1;

p2- Источник ЭВМ2;

p3 – Идет обработка, ЭВМ 1 занята;

p4 – ЭВМ 1 свободна;

p5 – Идет обработка ЭВМ2;

p6 – ЭВМ 2 свободна;

p7 – Очередь ЭВМ1;

p8 – ЭВМ 1 занята;

p9 – Очередь ЭВМ2;

p10 – ЭВМ 1 занята;

p11 – ЭВМ 2 занята;

p12 – Очередь заявок либо к ЭВМ 1, либо к ЭВМ 2;

p13 – Вывод результата.

Опишем переходы:

t0 – время начала работы терминала;

t1, t3, t5, t7– происходит запись в накопитель;

t2, t4, t6, t8 – происходит поступление информации на обработку в канал;

t9 – Завершение работы вывод результата.

 

3 Описание математической модели

 

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

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

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

Математическое  представление одноканальной системы с ожиданиями:

   λ              λ            λ             λ

      

μ 2μ  …   

  μ               μ            μ             μ

 

S0-Система свободна, заявок нет

S1-одна заявка под обслуживанием очереди нет

S2-одна заявка под обслуживанием одна заявка в очереди

Sm+1- одна заявка под обслуживанием m мест в очереди занято

Где

p_i – вероятность наступления i- го события.

- интенсивность потока

- средние число заявок обслуживаемых в единицу времени.

А – абсолютная пропускная способность

q – относительная пропускная способность

Ротк – вероятность  отказа

- среднее значение занятых мест в очереди

- среднее время ожидания заявки в очереди

- время нахождения заявки в системе

 

Математическое  представление многоканальной системы с ожиданиями:

   λ              λ            λ             λ             λ            λ           λ

      

μ 2μ  …                                   …

  μ               μ            μ             μ             μ            μ         μ

 

S0-Система свободна, заявок нет

S1-1 канал занят очереди нет

S2-2 канала занято очереди нет

Sn- все каналы заняты очереди нет

Sn+1- все каналы заняты 1 место в очереди занято

Sn+m- все каналы заняты m заявок в очереди

 

Где

p_i – вероятность наступления i- го события.

- интенсивность потока

- средние число заявок обслуживаемых в единицу времени.

А – абсолютная пропускная способность

q – относительная пропускная способность

Ротк – вероятность  отказа

- среднее значение занятых мест в очереди

- среднее время ожидания заявки в очереди

- время нахождения заявки в системе

Для облегчения математического расчета системы воспользуемся средой программирования CodeGear RAD Studio 2010, программу для расчета заданной системы:

Листинг программы  представлен в приложении А

 

Рисунок 3.1 – Окно программы

Результаты произведенных вычислений:

**********Первая  Фаза**********

ro=0,600

p0=0,434

p1=0,260

p2=0,156

p3=0,094

Pотк=0,056

Pобс=0,944

A=0,047

r=0,512

t|=10,243

t|=22,243

**********Вторая  Фаза**********

ro=1,333

p0=0,256

p1=0,341

p2=0,228

p3=0,101

p4=0,045

p5=0,020

p6=0,009

Pотк=0,009

Pобс=0,991

k=0,512

r=0,112

Tожид=1,106

Тобсл=8,250

Tсист=9,356

**********Третья Фаза**********

ro=0,700

p0=0,361

p1=0,252

p2=0,177

p3=0,124

Pотк=0,087

Pобс=0,913

A=0,213

r=0,684

t|=2,931

t|=5,931

= 3,581

 

 

4 Описание инструментария

Как было приведенно выше для проектирования данной модели выбран имитационный язык программирования GPSS, тогда для реализации в нем программы необходимы  следующие операторы:               

      GENERATE A,B,C,D,E

С помощью операндов A и B, задаваемых как вещественные или целые  положительные числа ( возможно, выражения), определяется равномерное распределение интервалов при генерации заявок. Интервалы между заявками могут быть от A-B до A+B включительно. Плотность вероятности в интервале равна 1/(2*B).

TERMINATE  A 

 

Моделирование  задержки  заявки ведет блок ADVANCE, который имеет 1 или 2 параметра. Блок очень похож на GENERATE и его параметры А и В имеют тот же смысл. Они определяют интервал задержки заявки. Здесь так же, если B является ссылкой на функцию, то интервал задержки определяется как произведение A на B. Общая форма блока:                

     ADVANCE A,B

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

В случае устройств, занятие устройства отображается блоком  

SEIZE A

а освобождение устройства отображается блоком

RELEASE A

Здесь  A – это номер или метка (имя) устройства.

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

Эти номер или  имя устройства в блоках SEIZE и RELEASE должны быть одинаковыми. Устройство перестанет быть занятым, когда занявшая его  заявка. пройдет через блок  RELEASE этого устройства.

МЕТ STOREGE A,B

Емкость накопителя описывает параметром А(№ устройства), В- емкость.

ENTER A,B

Для фиксации входа  транзакта в память

А-указывается  № памяти

В-число единиц памяти занимаемым транзактом

LEAVE

Выход из транзакта

GATE R  A,B

Оператор условного  перехода. R- условие.

TABLE A,B,C,D

Таблица. А- аргумент таблицы. В- верхняя граница нижнего интервала. В-ширина интервала.D- число интервала.

TABULATE A,B

Обращение к таблице

А- имя таблице

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

 

5 Описание пользовательского интерфейса

 

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

Рисунок 5.1 – Рабочая область языка GPSS.

Программирование  происходит в специализированном текстовом  редакторе самого языка, он вызывается командой File-new-modal.

Операторы языка  вызываются командой Edit-insert gpss bloks, вид операторов приведен ниже

Рисунок 5.3 – Операторы языка GPSS

Запуск модели осуществляется командой command-create simulation-start1.

Для пошагового изучения модели используется команда window- simulation window-blocs window.

 

6 Описание результатов  моделирования

Исходный код  программы, представлен в приложении Б

Описание полученной модели:

Окно статистики состоит из под разделов, содержащих стандартную статистику об объектах GPSS. Описание начинается с заголовка,

GPSS World Simulation Report - ЮЛЯ.54.1

Содержит имя  файла (курсовой), затем указывается  дата и время моделирования: Wednesday, November 10, 2010 03:33:52

Затем идет информация о времени моделирования, о числе  блоков, устройств , и многоканальных устройств

START TIME           END TIME  BLOCKS  FACILITIES  STORAGES

                0.000           2880.000    41        5          0

- START TIME - абсолютное  системное время в момент начала  моделирования. Оно эквивалентно абсолютному системному времени, после последнего применения операторов RESET или CLEAR;

- END TIME - абсолютное  время, когда счетчик завершений  принимает значение 0;

- BLOCKS - количество блоков, использованных в текущей модели, к моменту завершения моделирования;

- FACILITIES - количество устройств, использованных в модели, к моменту завершения моделирования;

- STORAGES - количество многоканальных  устройств, использованных в текущей модели к моменту завершения моделирования.

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

  NAME                       VALUE 

          MET1                            6.000

          MET2                           13.000

          MET3                           20.000

          MET_ERROR1                     27.000

          MET_ERROR2                     31.000

          MET_ERROR3                     35.000

          MET_EXIT                       39.000

          MET_EXITK1                     11.000

          MET_EXITK2                     18.000

          MET_EXITK3                     25.000

          MET_VOZVRAT1                   10.000

          MET_VOZVRAT2                   17.000

          MET_VOZVRAT3                   24.000

          TT                          10000.000

 Здесь NAME – это имя метки, а VALUE  - это её числовое значение.

Далее описываются  блоки текущей модели, например в  следующем виде:

LABEL              LOC  BLOCK TYPE     ENTRY COUNT CURRENT COUNT RETRY

                    1    GENERATE            10             0       0

                    2    SEIZE               10             0       0

                    3    ADVANCE             10             0       0

                    4    RELEASE             10             0       0

                    5    TRANSFER            10             0       0

MET1                6    GATE                10             0       0

                    7    SEIZE                4             0       0

                    8    ADVANCE              4             0       0

                    9    TRANSFER             4             0       0

MET_VOZVRAT1       10    ADVANCE              1             0       0

MET_EXITK1         11    RELEASE              4             0       0

                   12    TRANSFER             4             0       0

MET2               13    GATE                 6             0       0

                   14    SEIZE                2             0       0

                   15    ADVANCE              2             0       0

                   16    TRANSFER             2             0       0

MET_VOZVRAT2       17    ADVANCE              2             0       0

MET_EXITK2         18    RELEASE              2             0       0

                   19    TRANSFER             2             0       0

MET3               20    GATE                 4             0       0

                   21    SEIZE                4             0       0

                   22    ADVANCE              4             0       0

                   23    TRANSFER             4             0       0

MET_VOZVRAT3       24    ADVANCE              1             0       0

MET_EXITK3         25    RELEASE              4             0       0

                   26    TRANSFER             4             0       0

MET_ERROR1         27    SEIZE                1             0       0

                   28    ADVANCE              1             0       0

                   29    RELEASE              1             0       0

                   30   TRANSFER             1             0       0

MET_ERROR2         31    SEIZE                2             0       0

                   32    ADVANCE              2             0       0

                   33    RELEASE              2             0       0

                   34    TRANSFER             2             0       0

MET_ERROR3         35    SEIZE                1             0       0

                   36    ADVANCE              1             0       0

                   37    RELEASE              1             0       0

                   38    TRANSFER             1             0       0

MET_EXIT           39    TERMINATE           10             0       0

                   40    GENERATE             1             0       0

                   41    TERMINATE            1             0       0

 

 Здесь поле LABEL  определяет   метку  блока, поле LOC определяет имя или номер этого блока. Поле BLOCK TYPE определяет

тип блока GPSS World.

Поле ENTRY COUNT определяет количество заявок, вошедших в данный блок, после последнего выполнения блоков RESET или CLEAR, или с начала работы программы.

Поле CURRENT COUNT определяет количество заявок, находящихся в данном блоке в конце моделирования.

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

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

 VISIO1           20.252   10.509                           0

                                  10.000  -  _                       4   100.00

VISIO2           29.079   10.703                           0

                                  20.000  -       22.000             1    50.00

                                  22.000  -       24.000             0    50.00

                                  24.000  -       26.000             0    50.00

                                  26.000  -       28.000             0    50.00

                                  28.000  -       30.000             0    50.00

                                  30.000  -       32.000             0    50.00

                                  32.000  -       34.000             0    50.00

                                  34.000  -       36.000             0    50.00

                                  36.000  -  _                       1   100.00

VISIO3           25.445    0.000                           0

                                       _  -       30.000             1   100.00

VISIO4           43.385    0.000                           0

                                  42.000  -       44.000             1   100.00

Поле TABLE определяет имя или номер объекта типа "таблица" или "Q-таблица".

Поле MEAN определяет среднее взвешенное значение табулируемого аргумента. Значение преобразовывается в формат двойной точности при выводе в файл статистики.

Поле STD.DEV определяет взвешенное среднеквадратичное отклонение.