Основные концепции моделирования на gpss
| Вид материала | Документы |
- Использование системы моделирования gpss world для сравнения различных реализаций системы, 21.47kb.
- Сравнение качества генерирования случайных чисел в системах имитационного моделирования, 22.53kb.
- От последовательного моделирования в системе gpss\World к распределённому моделированию, 98.79kb.
- Программа курса «Основы математического моделирования» Осень 2007, 25.35kb.
- Тесты псевдослучайных последовательностей, 234.9kb.
- 1. Основные понятия теории моделирования, 279.51kb.
- 1. Введение. Основные понятия моделирования Общая характеристика проблем моделирования., 38.29kb.
- Задачи : 1 дать понятие математической модели, раскрыть суть метода математического, 187.03kb.
- Т. И. Алиев Учебно-исследовательская работа И1 Исследование, 295.14kb.
- Вопросы вступительного экзамена в магистратуру по специальности, 24.96kb.
Объяснение рис. 13.6. Состояния цепей
Фаза ввода (от строки 1 к строке 2). Первым действием интерпретатора является ввод модели. До фазы ввода цепи текущих и будущих событий пусты (строка 1). В течение фазы ввода интерпретатор проверяет каждую прочитываемую карту, определяя, не является ли она картой GENERATE.
При чтении этой карты интерпретатор сразу же "воспринимает" блок GENERATE для установления времени прихода транзакта в этот блок. Для этого интерпретатор сначала должен определить значение модельного времени прихода. Если задано время смещения транзакта операндом С блока, то сначала время прихода устанавливается в значение, равное значению операнда С. В противном случае разыгрывается случайное значение в соответствии с распределением интервалов прихода, определенным операндами А и В блока GENERATE. Времени прихода присваивается разыгранное значение. Далее интепретатор выбирает транзакт из вершины пассивного буфера и помещает его в цепь будущих событий с целью ввести в модель через блок GENERATE в заданный момент прихода.
Если время прихода равно нулю (либо значение операнда С равно нулю, либо разыгранное в соответствии с распределением значение интервала равно нулю), то оно автоматически заменяется интерпретатором на единицу. Это означает, что нет возможности ввести транзакт через блок GENERATE в момент модельного времени, равный нулю. Самое раннее значение = 1. Заметим, что наш транзакт еще находится на пути в модель, пребывая в цепи будущих событий. Он пока не находится ни в одном из блоков.
В модели на рис.13.5 (предыдущая страница) при чтении блока 1 GENERATE на фазе ввода модели разыгрывается число из выборки с распределением 18 - 6. Первым разыгранным значением, как следует из табл.13.1, является 14. Интерпретатор выбирает транзакт 1 из пассивного буфера и помещает его в цепь будущих событий (ЦБС), планируя вход в блок 1 в момент времени, равный 14. В течение фазы ввода также читается блок 8 GENERATE. В этом блоке задается детерминированное значение времени - 480. Интерпретатор из пассивного буфера достает транзакт 2 и помещает его в ЦБС, планируя вход транзакта в блок 8 в момент времени, равный 480. Поскольку интерпретатор располагает транзакты в ЦБС в соответствии с временем движения, транзакт 2 ставится следом за транзактом 1.
После чтения блока 9 TERMINATE стоит карта START. Читая эту карту, интерпретатор определяет значение ее операнда А и помещает копию этого значения в счетчик завершений. Фаза ввода для нас закончена. Проверка цепи будущих событий в заключение фазы ввода (строка 2, рис. 13.6) показывает, что в ней находятся два транзакта, по одному для каждого из блоков GENERATE в модели. Транзакт 1 изображает первого клиента, идущего в парикмахерскую. Он появится в парикмахерской в момент модельного времени, равный 14. Планируемый вход транзакта 1 в блок 1 аналогичен приходу клиента к двери парикмахерской.
Транзакт 2 символизирует собой таймер, направляющийся в модель для того, чтобы завершить моделирование. Когда таймер модельного времени достигнет значения 480, транзакт-таймер, наконец, придет и, войдя в блок TERMINATE (блок 9), вызовет завершение моделирования. Напомним, что в качестве третьего элемента выступает номер блока, в котором находится транзакт. Но транзакты 1 и 2 не входят ни в один из блоков модели. Они еще находятся на пути в модель, поэтому на месте номера блока стоит слово "НЕТ".
Блок-схема на рис.13.7 описывает рассмотренные нами особенности фазы ввода. Вся логика работы интерпретатора на фазе ввода, представленная в блок-схеме, хорошо понятна из приведенного выше описания.
Рис. 13.7.
Как показано на рис.13.7, когда фаза ввода завершается интерпретатор переходит к фазе коррекции таймера. После первой коррекции выполняется первый раз фаза просмотра. Затем фаза коррекции таймера выполняется второй раз, фаза просмотра выполняется второй раз и т.д.
Первое выполнение корректировки таймера (от строки 2 к строке 3). Интерпретатор устанавливает таймер в значение 14 - значение времени движения транзакта (транзакт 1), находящегося в начале цепи будущих событий в строке 2. Затем он перемещает транзакт 1 в пустую прежде цепь текущих событий. Следующий транзакт (транзакт 2) в ЦБС имеет значение времени движения, отличное от 14. Следовательно, первое выполнение фазы коррекции таймера закончено.
Заметим, что в строке 3 на рис.13.6 цепь текущих событий (ЦТС) содержит лишь один единственный транзакт, описанный как [1, КМР, НЕТ, 0, 1]. Время входа в пятипозиционной записи обозначено как КМР, т.е. "Как можно раньше". Все транзакты в ЦТС в позиции "время движения" имеют запись КМР. Это объясняется тем, что они "хотели" бы войти в следующий блок сейчас же (т.е. в текущие значения модельного времени), или, если вход в следующий блок закрыт, то как можно раньше. Текущий блок для этого транзакта по-прежнему содержит запись "HET", поскольку транзакт все еще не вошел ни в один из блоков модели. Он займет какой-либо блок только после того, как отработает фаза просмотра. После завершения первого выполнения фазы коррекции таймера сразу же начинается выполнение фазы просмотра.
Первое выполнение фазы просмотра (от строки 3 к строке 4). Выбрав транзакт 1 из начала третьей строки ЦТС, интерпретатор двигает его в блок 1 (блок GENERATE), затем проверяет, может ли транзакт 1 быть перемещен в следующий блок - блок 2 QUEUE. Блок QUEUE не запрещает вход, поэтому попытка входа будет успешной.
Теперь, поскольку транзакт может уйти из блока GENERATE, интерпретатор временно приостанавливает его продвижение и планирует приход следующего транзакта в блок GENERATE. Второй розыгрыш числа в соответствии с распределением 18 ± 6 интервалов прихода дает значение 13 (см. табл.13.1). Транзакт выбирается из вершины пассивного буфера (транзакт 3) и помещается в цепь будущих событий с запланированным временем входа в блок 1, равным "текущее + 13", т. е. 27. Напомним, что для определения времени прихода следующего транзакта разыгранное значение интервала прихода прибавляется к текущему значению таймера.
Что касается блока GENERATE, то здесь необходимо сделать два замечания:
1. Интерпретатор не планирует следующий приход в блок GENERATE до тех пор, пока предыдущий транзакт не сделает успешную попытку войти в следующий блок. Если следующим является блок, который может запретить вход (например, блок SEIZE), то планирование будет иметь место спустя некоторое время после входа транзакта в блок GENERATE.
2. Интерпретатор прерывает движение транзакта, выходящего из блока GENERATE, на время планирования входа его последователя. После завершения планирования движение транзакта возобновляется.
Выполнение этих двух условий в виде блок-схемы показано на рис. 13.8. После завершения планирования транзакт 1 вызывает выполнение подпрограммы блока QUEUE. Из блока QUEUE интерпретатор перемещает транзакт в блоки SEIZE, DEPART и ADVANCE. В блоке ADVANCE (блок 5) определяется время задержки в соответствии с распределением 16 ± 4. По табл. 13.2 находим, что первым разыгранным значением является 18. Следовательно, транзакт 1 выводится из ЦТС и помещается в ЦБС. Планируется переход из блока 5 в блок 6 (блок RELEASE) в момент времени "текущий + 18, т.е. в момент времени 32.
Рис.13.8. Фрагмент блок-схемы,показывающий логику работы интерпретатора при выходе
транзакта из блока GENERATE и планировании прихода его последователя.
Теперь, поскольку транзакт 1 вызвал выполнение подпрограммы блока SEIZE при своем движении, интерпретатор заново просматривает цепь текущих событий. Цепь пуста. Следовательно, следующим шагом будет выполнение фазы коррекции таймера.
Отметим, что транзакты цепи будущих событий в строке 4, если рассматривать их слева направо, имеют смысловые значения, записанные в табл.13.3.
Таблица 13.3. Смысловые значения транзактов в цепи будущих событий (строка 4, рис.13.6).
| Смысловые значение транзактов в цепи будущих событий | ||
| Номер транзакта | Смысловое значение | |
| 3 | Второй клиент идет в парикмахерскую | |
| 1 | Первый клиент стрижется | |
| 2 | Транзакт-таймер | |
(от строки 4 к строке 5). Интерпретатор продвигает таймер к значению 27 - времени движения транзакта (транзакт 3), находящегося в начале строки 4 цепи будущих событий. Далее он перемещает транзакт из ЦБС в прежде пустую ЦТС. Следующий транзакт в ЦБС (транзакт 1) имеет время движения, отличное от 27. Следовательно, второе выполнение фазы коррекции таймера завершается. Начинается следующее выполнение просмотра.
Второе выполнение фазы просмотра (от строки 5 к строке 6). Взяв транзакт 3 из начала строки 5 цепи текущих событий, интерпретатор двигает его в блок 1 (блок GENERATE), затем определяет, можно ли сразу переместить его в блок 2. Временно приостановив обработку транзакта 3, интерпретатор планирует приход следующего транзакта в блок 1 (GENERATE). В соответствии с интервалом прихода 17 (третье разыгранное значение из распределения 18 - 6 в табл. 13.1) транзакт 4 выбирается из вершины пассивного буфера и помещается в ЦБС; планируется его вход в блок 1 в момент времени 44. Она занимает в ЦБС положение между транзактом 1 и 2 в соответствии с принципом упорядочения в ЦБС.
Интерпретатор возобновляет движение транзакта 3, завершая его выполнением подпрограммы блока QUEUE. Здесь транзакт безуспешно пытается выйти из блока QUEUE и войти в блок SEIZE. Устройство JOE находится в состоянии "занято", поэтому вход в этот блок запрещен. Интерпретатор оставляет транзакт 3 в блоке QUEUE и в ЦТС, планируя войти в блок 3 "Как можно раньше". Далее интерпретатор должен продолжать работу со следующим транзактом в строке 5 цепи текущих событий. Но такого транзакта не существует. Поэтому следующим шагом является выполнение фазы коррекции таймера. Заметим, что таймер все равно надо было бы продвинуть, даже если бы цепь текущих событий была не пустой.
Отметим, что транзакты в строке 6 на рис.13.6 имеют смысл, указанный в табл. 13.4.
Таблица 13.4. Смысловые значения транзактов в цепях текущих и будущих событий (строка 6, рис. 13.6).
| Смысловые значение транзактов в цепях текущих и будущих событий | ||
| Цепь | Номер транзакта | Распределение времени обслуживания, мин |
| ЦТС | 3 | Второй клиент ждет в очереди |
| ЦБС | 1 | Первый клиент стрижется |
| ЦБС | 4 | Третий клиент идет в парикмахерскую |
| ЦБС | 2 | Тразакт-таймер |
Третье выполнение фазы коррекции таймера (от строки 6 к строке 7). Интерпретатор продвигает значение модельного времени к 32 - времени движения транзакта (транзакт 1), стоящего первым в строке 6 цепи будущих событий. Далее он перемещает транзакт 1 в цепь текущих событий, где тот занимает место последнего элемента среди элементов того же приоритетного класса. Отметим, что в строке 7 в ЦТС транзакт 1 располагается за транзактом 3 (транзакт 3 уже стоит в цепи текущих событий в начале третьего выполнения фазы коррекции таймера).
ТЕМА № 13
"Первый пример использования цепей текущих и будущих событий"
Следующий транзакт ЦБС (транзакт 4) имеет значение времени движения, отличное от 32. Следовательно, выполняется следующая фаза просмотра. При этом транзакты, находящиеся в строке 7 цепи текущих событий, имеют смысл, указанный в табл. 13.5.
Таблица 13.5. Смысловые значения транзактов в цепи текущих событий.
| Смысловые значения транзактов в цепи текущих событих | |
| Номер транзакта | Смысловое значение |
| 3 | Второй клиент ждет в очереди |
| 1 | Первый клиент только что закончил завершил стрижку |
Третье выполнение фазы просмотра (от строки 7 к строке 8). Выбрав транзакт 3 из начала строки 7 ЦТС, интерпретатор терпит неудачу в попытке ввести транзакт в блок 3 (SEIZE) и вывести его из блока 2. Во входе в блок 3 отказано, поскольку прибор все еще не освободился. Поэтому транзакт 3 остается в блоке QUEUE и в ЦТС, причем планируется его вход в блок 3 "как можно раньше". Переходим к следующему транзакту строки 7 ЦТС (транзакту 1). Интерпретатор перемещает его из блока 5 в блок 6 (RELEASE) и далее из блока 6 в блок 7 (TERMINATE), где он выводится из модели и возвращается в вершину пассивного буфера.
Теперь, поскольку транзакт 1 вызвал выполнение подпрограммы блока RELEASE, интепретатор вновь просматривает цепь текущих событий. Снова выбирается транзакт 3, и он снова пытается выйти из блока 2 и войти в блок 3. На этот раз попытка оказывается успешной.
Выполнение последовательности SEIZE-ADVANCE-RELEASE вызывает необходимость зедержать транзакт на 12 единиц времени в соответствии с распределением 16 ± 4 (второе значение из табл.13.2). Транзакт 3 помещается в ЦБС; планируется вывести его из блока 5 и поместить в блок 6 в момент времени "текущий + 12" или 44. Заметим, что в ЦБС транзакт 3 попадает в один узел с транзактом 4, который также имеет время движения, равное 44. Поскольку транзакт 4 уже находится в ЦБС, транзакт 3 помещается позади него. Напомним, что если в ЦБС возникает узел времени, то входящий транзакт попадает в цепь как последний элемент среди транзактов того же значения времени движения.
Поскольку транзакт 3 вызвал выполнение блока SEIZE, интерпретатор заново просматривает цепь текущих событий. На этот раз цепь пуста. Поэтому на следующем этапе необходимо выполнить фазу коррекции таймера. В это время транзакты в цепи будущих событий в строке 8 имеют смысл, указанный в табл. 13.6.
Таблица 13.6.
| Смысловые значения транзактов в цепи будущих событих | |
| Номер транзакта | Смысловое значение |
| 3 | Второй клиент стрижется |
| 4 | Третий клиент едет в парикмахерскую |
| 2 | Транзакт-таймер |
Четвертое выполнение фазы коррекции таймера (от строки 8 к строке 9). Интерпретатор продвигает время к значению 44 - времени движения транзакта (транзакта 4), стоящего первым в строке 8 цепи будущих событий. Затем он перемещает транзакт 4 из ЦБС в ранее пустую ЦТС. Следующий транзакт в ЦБС (транзакт 3) также имеет значение времени движения, равное 44. Он также перемещается в цепь текущих событий, где помещается за транзактом 4 в качестве последнего элемента внутри своего класса приоритетов. Следующий транзакт в цепи будущих событий (транзакт 2) имеет время движения, отличное от 44. Таким образом, четвертая коррекция таймера завершается.
Прежде чем продолжить, давайте снова посмотрим, какой смысл придается двум транзактам, стоящим в строке 9 цепи текущих событий (табл. 13.7).
Таблица 13.7. Смысловые значения транзактов в цепи текущих событий.
| Смысловые значения транзактов в цепи текущих событих | |
| Номер транзакта | Смысловое значение |
| 4 | Третий клиент только что пришел в парикмахерскую |
| 3 | Второй клиент только что закончил стрижку |
Четвертое выполнение фазы просмотра (от строки 9 к строке 10). Выбрав транзакт 4, стоящий в начале строки 9 ЦТС, интерпретатор помещает его в блок 1, далее определяет, можно ли его переместить из блока 1 в блок 2. Временно прекратив обработку транзакта 4, интерпретатор планирует время прихода его последователя в блок 1 (GENERATE). Транзакт 1 выбирается из вершины транзактов пассивного буфера и помещается в цепь будущих событий, причем планируется время входа в блок 1 в момент времени "текущий + 15", т.е. 59 (в соответствии с табл.13.1, четвертое значение для распределения 18 ± 6 равно 15).
Заметим, что это снова транзакт 1, который вернулся в модель из пассивного буфера. Транзакт, который прежде уже был в модели и символизировал собой первого клиента, теперь вернулся "в игру", символизируя четвертого клиента того же дня.
В качестве конкретного примера одновременных событий в GPSS рассмотрим пример моделирования 2А и соответствующие состояния цепей, показанные на рис. 13.6. В строке 9 на рис.13.6 в цепи текущих событий мы видим два события, запланированных на одно и то же модельное время 44. Первым из этих событий, [4,КМР,НЕТ, 0,1], является приход клиента в парикмахерскую. Вторым из этих событий, [3,КМР,5,0,6], является завершение обслуживания клиента, находящегося в кресле парикмахера. На самом деле следующий клиент входит в дверь как раз в момент, когда обслуживаемый клиент поднимается из кресла парикмахера.
Посмотрим теперь, как эта реальная ситуация моделируется в примере 2А. При просмотре цепи текущих событий интерпретатор GPSS сначала обнаруживает транзакт 4. Транзакт 4 последовательно входит в блок GENERATE, затем в блок QUEUE и должен там задержаться. Фактически, интерпретатор осуществляет вход следующего клиента в дверь и присоединяет его к очереди. Далее, продолжая просмотр цепи текущих событий, интерпретатор выбирает транзакт 3. Этот транзакт вводится в блоки RELEASE и TERMINATE, что означает "клиент уходит из парикмахерской". Здесь, следовательно, произошли два события - приход клиента и завершение обслуживания. Последовательность обработки была: приход клиента, а затем завершение обслуживания просто потому, что транзакт 4 оказался впереди транзакта 3 в цепи текущих событий. Если бы относительная последовательность этих двух событий в ЦТС оказалась инверсной, то и обработка этих событий была бы инверсной.
Конечно, в этой точке система еще не окончательно изменяет свое состояние в момент модельного времени 44. Сейчас возникло условие, при котором произошло событие "перевод состояния парикмахера в положение свободно". Поскольку как часть завершения обслуживания выполняется обработка блока RELEASE, интерпретатор заново просматривает цепь текущих событий. В результате интерпретатор снова выбирает транзакт 4, продвигая его в тот же момент модельного времени через блоки SEIZE и DEPART и вводя его в блок ADVANCE. Следовательно, произойдет событие "занятия". На этом и завершатся действия в момент времени 44.
Должно быть ясно, что когда возникают временные узлы в примере моделирования 2А, то последовательность, в которой обрабатываются вовлеченные события, зависит от случая. Однако и не требуется никакого формального контроля в этой простой модели, поскольку интерпретатор заново просматривает ЦТС после обработки блока RELEASE. Если бы это было не так, модель была бы неверной, так как хотя и существовали бы в момент времени 44 ожидающий клиент и освободившийся парикмахер, никакие действия не были бы предприняты для того, чтобы клиент перешел на обслуживание к парикмахеру. Интерпретатор, следовательно, построен таким образом, что в этой модели ему безразлична последовательность возникновения одновременных событий.
В примере моделирования 2А легко поменять условия таким образом, что последовательность, в которой будут записаны состояния в цепях на рис.13.6 в момент времени 44, станет небезразличной. Предположим, что прибывающий клиент решает остаться только в том случае, если он немедленно может начать обслуживаться у парикмахера, и что модель модифицируется таким образом, чтобы учесть это предположение (отметим, что мы еще не изучили способа, как это сделать).
В этом случае, если приход возникнет раньше события завершения, пришедший клиент не останется на обслуживание, а если последовательность событий будет обратной, останется. При таких условиях очень важно разработать модель таким образом, чтобы в случае возникновения временных узлов завершение обслуживания всегда происходило раньше прихода заявки. Очевидно, что именно такой будет последовательность событий, если принять меры к тому, чтобы обеспечить условие расположения транзакта "завершение обслуживания" ближе к началу ЦТС, чем транзакт "приход заявки".
Уже упоминалось, что относительное расположение транзактов в ЦТС определяется уровнем приоритетов. Если бы транзакт "завершение обслуживания" имел более высокий приоритет, чем транзакт "приход заявки", то имела бы место желаемая последовательность обработки событий. Позднее мы увидим, каким образом может устанавливаться уровень приоритетов для того, чтобы избежать проблем, которые возникли бы в связи с временными узлами.