Методы имитационного моделирования дискретных процессов на основе теории массового обслуживания: моделирование последовательно-паралле

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

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

    С позиции моделирования процесса массового обслуживания ситуации, когда образуются очереди заявок (требований) на обслуживание, возникают следующим образом. Поступив в обслуживающую систему, требование присоединяется к очереди других (ранее поступивших) требований. Канал обслуживания выбирает требование из находящихся в очереди, с тем чтобы приступить к его обслуживанию. После завершения процедуры обслуживания очередного требования канал обслуживания приступает к обслуживанию следующего требования, если таковое имеется в блоке ожидания. [2]

    Приоритет – это некоторые «привилегии» заявки на ее обслуживание.  Приоритет может быть как абсолютным — когда заявка с более высоким приоритетом «вытесняет» из-под обслуживания заявку с низшим, так и относительным — когда начатое обслуживание доводится до конца, а заявка с более высоким приоритетом имеет лишь право на лучшее место в очереди.[3]

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

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

    Последовательно-параллельная организация каналов облуживания – это сочетание последовательной и параллельной организации каналов. [5]

2. Имитационное моделирование средствами GPSS.

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

         Сложные функции моделирующего алгоритма могут быть реализованы

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

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

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

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

    GPSS (General Purpose Simulation System) – общецелевая система моделирования сложных систем, разработанная Джеффри Гордоном. Первоначально разрабатывалась и поддерживалась компанией IBM. В настоящее время имеются версии различных разработчиков. GPSS World – самая современная версия GPSS для персональных ЭВМ и ОС Windows. Разработана компанией Minuteman Software.

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

    Использование GPSS World дает возможность оценить эффект конструкторских решений в чрезвычайно сложных системах реального мира.

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

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

    GPSS World был разработан с целью решить все эти проблемы. GPSS World является объектно-ориентированным языком. Его возможности визуального представления информации позволяют наблюдать и фиксировать внутренние механизмы функционирования моделей. Его интерактивность позволяет одновременно исследовать и управлять процессами моделирования.

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

    GPSS World сочетает в себе функции дискретного и непрерывного моделирования. Возможность перехода из дискретной фазы моделирования в непрерывную фазу и обратно обеспечивает тесную связь с непрерывным моделированием. В непрерывной фазе могут быть установлены пороговые значения, управляющие созданием транзактов в дискретной фазе.[7]

К основным объектам GPSS относятся:

1. Транзакты. Транзакт – некоторое сообщение (заявка, требование на обслуживание), которое поступает извне на вход системы и подлежит обработке. Транзакт – обязательный элемент GPSS модели.

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

Структура простейшей модели GPSS имеет вид:

Блоки GENERATE и TERMINATE имеют особый статус: первый имеет только выход; второй - только вход. Блок GENERATE создает транзакты, блок TERMINATE их уничтожает.

Формат блока:

<метка> БЛОК <А>, <В>, <С>, …; comment (комментарии с использованием символов кириллицы не допустимы).

3. Устройства. Устройства делятся на одноканальные и многоканальные. Формируются в GPSS программе с помощью блоков: SEIZE, RELEASE (одноканальные); ENTER, LEAVE (многоканальные).

4. Очереди. Очередь возникает в случае задержки в продвижении транзакта, или в его обработке. Для сбора и регистрации статистики об очередях в GPSS используют блоки: QUEUE, DEPART.

3. Выбор модели и средств реализации задачи управления.

    Рассматриваемая задача решается с использованием модели массового обслуживания средствами GPSS Word.

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

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

5. Реализация задачи на GPSS Word.

    Представим схематически рассматриваемую систему обслуживания:

Текст программы:

GENERATE 6,5,,,40

ME1 QUEUE PREB

QUEUE BR1

QUEUE BR2

TRANSFER BOTH,MET1,MET2

MET1 SEIZE K1

DEPART BR1

ADVANCE 7,2

RELEASE K1

TRANSFER ,MET3

MET2 SEIZE K2

DEPART BR2

ADVANCE 6,3

RELEASE K2

MET3 QUEUE BR3

SEIZE K3

DEPART BR3

ADVANCE 6,1

RELEASE K3

TRANSFER .5,MET4,MET5

MET4 QUEUE BR4

SEIZE K4

DEPART BR4

ADVANCE 8,2                           

RELEASE K4

TRANSFER ,OUT1

MET5 TRANSFER .6,MET6,MET7

MET6 QUEUE BR6

SEIZE K6

DEPART BR6

ADVANCE 8,5                           

RELEASE K6

TRANSFER ,OUT1

MET7 QUEUE BR5

SEIZE K5

DEPART BR5

ADVANCE 5,2             

RELEASE K5

TRANSFER ,OUT1

GENERATE 15,2,,,20

TRANSFER ,ME1

OUT1 DEPART PREB

TERMINATE 1

START 100

Отчет по работе программы:

              GPSS World Simulation Report - РГР Наташа.85.1

                   Saturday, May 19, 2007 16:54:39 

           START TIME           END TIME  BLOCKS  FACILITIES  STORAGES

                0.000                      609.398            43                6                    0

LABEL         LOC  BLOCK TYPE     ENTRY COUNT CURRENT COUNT   RETRY

                     1    GENERATE           105                           0                    0

ME1            2    QUEUE                   145                           0                    0

                     3    QUEUE                   145                           0                     0

                     4    QUEUE                   145                           0                     0

                     5    TRANSFER            145                           0                    0

MET1          6    SEIZE                       70                           0                   0

                     7    DEPART                   70                           0                     0

                     8    ADVANCE               70                           1                      0

                     9    RELEASE                 69                           0                      0

                    10    TRANSFER             69                           0                     0

MET2        11    SEIZE                       75                           0                      0

                    12    DEPART                  75                           0                      0