Курсовая_Моделирование (538756), страница 3
Текст из файла (страница 3)
(Q-СХЕМЫ)
Особенности непрерывно-стохастического подхода рассмотрим на примере использования в качестве типовых математических схем систем массового обслуживания, которые будем называть Q-схемами. Системы массового обслуживания представляют собой класс математических схем, разработанных в теории массового обслуживания и различных приложениях для формализации процессов функционирования систем, которые по своей сути являются процессами обслуживания.
В качестве процесса обслуживания могут быть представлены различные по своей физической природе процессы функционирования экономических, производственных, технических и других систем, например потоки поставок продукции некоторому предприятию, потоки деталей и комплектующих изделий на сборочном конвейере цеха, заявки на обработку информации ЭВМ от удаленных терминалов и т. д. При этом характерным для работы таких объектов является случайное появление заявок (требований) на обслуживание и завершение обслуживания в случайные моменты времени, т. е. стохастический характер процесса их функционирования.
В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки.
Прибор обслуживания заявок
Это можно изобразить в виде некоторого i-гo прибора обслуживания (рисунок), состоящего из накопителя заявок
, в котором может одновременно находиться
заявок, где
— емкость i-гo накопителя и канала обслуживания заявок (или просто канала)
. На каждый элемент прибора обслуживания
поступают потоки событий: в накопитель
— поток заявок
, на канал
— поток обслуживаний
.
Потоком событий называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных событий. Поток событий называется однородным, если он характеризуется только моментами поступления этих событий (вызывающими моментами) и задается. Mомент наступления i-го события — неотрицательное вещественное число. Однородный поток событий также может быть задан в виде последовательности промежутков времени между i-м и (п-1)-м событиями, которая однозначно связана с последовательностью поступления заявок.
При моделировании различных систем применительно к элементарному каналу обслуживания можно считать, что поток заявок
, т. е. интервалы времени между моментами появления заявок на входе
образует подмножество неуправляемых переменных, а поток обслуживания U, т. е. интервалы времени между началом и окончанием обслуживания заявки, образует подмножество управляемых переменных.
Заявки, обслуженные каналом и заявки, покинувшие прибор
по различным причинам не обслуженными (например, из-за переполнения накопителя
, образуют выходной поток
, т. е. интервалы времени между моментами выхода заявок образуют подмножество выходных переменных.
Процесс функционирования прибора обслуживания можно представить как процесс изменения состояний его элементов во времени z(t). Переход в новое состояние означает изменение количества заявок, которые в нем находятся (в канале
и в накопителе
).
В практике моделирования систем, имеющих более сложные структурные связи и алгоритмы поведения, для формализации используются не отдельные приборы обслуживания, а Q-схемы, образуемые композицией многих элементарных приборов обслуживания (сети массового обслуживания).
Для того, чтобы осуществить процесс моделирования полученной Q-схемы используют различные языки имитационного моделирования. Одним из таких языков является язык имитационного моделирования GPSS (см. приложение 1)
Моделирование Q-схем с фазовой структурой
Если приборы массового обслуживания и их параллельные композиции соединены последовательно, то имеет место многофазное обслуживание (многофазная Q-схема). Таким образом, для задания Q-схемы необходимо использовать оператор сопряжения R, отражающий взаимосвязь элементов структуры (каналов и накопителей) между собой.
Связи между элементами Q-схемы изображают в виде стрелок (линий потока, отражающих направление движения заявок). Различают разомкнутые и замкнутые Q-схемы. В разомкнутой Q-схеме выходной поток обслуженных заявок не может снова поступить на какой-либо элемент, т. е. обратная связь отсутствует, а в замкнутых Q-схемах имеются обратные связи, по которым заявки двигаются в направлении, обратном движению вход-выход.
Собственными (внутренними) параметрами Q-схемы будут являться количество фаз, количество каналов в каждой фазе, количество накопителей каждой фазы, емкость i-гo накопителя. Следует отметить, что в теории массового обслуживания в зависимости от емкости накопителя применяют следующую терминологию для систем массового обслуживания: системы с потерями, т. е. имеется только канал обслуживания системы с ожиданием, (т. е. очередь заявок не ограничивается) и системы смешанного типа (с ограниченной емкостью накопителя). Всю совокупность собственных параметров Q-схемы обозначим как подмножество Н.
Для задания Q-схемы также необходимо описать алгоритмы ее функционирования, которые определяют набор правил поведения заявок в системе в различных неоднозначных ситуациях. В зависимости от места возникновения таких ситуаций различают алгоритмы (дисциплины) ожидания заявок в накопителе Н, и обслуживания заявок каналом каждого элементарного обслуживающего прибора
Q-схемы. Неоднородность заявок, отражающая процесс в той или иной реальной системе, учитывается с помощью введения классов приоритетов.
В зависимости от динамики приоритетов в Q-схемах различают статические и динамические приоритеты. Статические приоритеты назначаются заранее и не зависят от состояний Q-схемы, т. е. они являются фиксированными в пределах решения конкретной задачи моделирования. Динамические приоритеты возникают при моделировании в зависимости от возникающих ситуаций. Исходя из правил выбора заявок из накопителя на обслуживание каналом
можно выделить относительные и абсолютные приоритеты. Относительный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель
ожидает окончания обслуживания предшествующей заявки каналом
и только после этого занимает канал. Абсолютный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель
прерывает обслуживание каналом
заявки с более низким приоритетом и сама занимает канал (при этом вытесненная из
заявка может либо покинуть систему, либо может быть снова записана на какое-то место в
).
При рассмотрении алгоритмов функционирования приборов обслуживания (каналов
и накопителей Н) необходимо также задать набор правил, по которым заявки покидают
и
для
— либо правила переполнения, по которым заявки в зависимости от заполнения
покидают систему, либо правила ухода, связанные с истечением времени ожидания заявки в
для
— правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале
или не допускаются до обслуживания каналом
, т. е. правила блокировок канала. При этом различают блокировки
по выходу и по входу. Такие блокировки отражают наличие управляющих связей в Q-схеме, регулирующих поток заявок в зависимости от состояний Q-схемы. Весь набор возможных алгоритмов поведения заявок в Q-схеме можно представить в виде некоторого оператора алгоритмов поведения заявок.
Таким образом, Q-схема, описывающая процесс функционирования системы массового обслуживания любой сложности, однозначно задается в виде Q= (W, U, H, Z, R, А).
При ряде упрощающих предположений относительно подмножеств входящих потоков W, потоков обслуживания U (выполнение условий стационарности, ординарности и ограниченного последействия) оператора сопряжения элементов структуры R (однофазное одноканальное обслуживание в разомкнутой системе), подмножества собственных параметров Н (обслуживание с бесконечной емкостью накопителя), оператора алгоритмов обслуживания заявок А (бес приоритетное обслуживание без прерываний и блокировок) для оценки вероятностно-временных характеристик можно использовать аналитический аппарат, разработанный в теории массового обслуживания.
Математическое обеспечение и ресурсные возможности современных ЭВМ позволяют достаточно эффективно провести моделирование различных систем, формализуемых в виде Q-схем, используя либо пакеты прикладных программ, созданные на базе алгоритмических языков общего назначения, либо специализированные языки имитационного моделирования. Пример Q-схемы общего вида
На рисунке представлена трехфазная Q-схема (L =3) с блокировкой каналов по выходу в 1-й и 2-й фазах обслуживания (пунктирные линии на рисунке). В качестве выходящих потоков такой Q-схемы могут быть рассмотрены поток потерянных заявок из и поток обслуженных заявок из
(
на рисунке).