close

Вход

Забыли?

вход по аккаунту

?

лаб2

код для вставкиСкачать
Практическое занятие №2
Моделирование входящих и выходящих потоков
ОДНОКАНАЛЬНАЯ СМО С ОЧЕРЕДЬЮ КАК ОБЪЕКТ МОДЕЛИРОВАНИЯ
Рассмотрим порт с одним причалом (прибор), обслуживающий промысловые суда(заявки). Суда приходят, ждут очереди (если это необходимо), обрабатываются по принципу "первый пришел-первым обслужен" и уходят. Схематично такая простейшая СМО изображена на рисунке 1. Она характеризуется двумя независимыми случайными величинами: интервалом времени между последовательными моментами прихода заявок и длительностью времени обслуживания.
Рисунок 1 - Система массового обслуживания с одним каналом и очередью
Предметом исследования такой СМО может быть, например, определение максимальной длины очереди загрузки прибора, вероятности отказа, что в условиях АСУ необходимо для принятия решений по управлению. Поставим цель - построить алгоритм, моделирующий работу порта, при этом последовательно выделим и опишем отдельные типовые процедуры, из которых затем соберем как из унифицированных блоков весь алгоритм. Разработку выполним при условиях: 1) интервал прибытия и время обслуживания - целочисленные случайные величины с равномерным законом распределения; 2) все заявки необходимо обслужить независимо от длины очереди; 3) в начальный момент очередь пуста, а прибор не занят; 4) моделирование завершается по истечении заданного модельного времени; 5) должны быть получены интересующие нас показатели эффективности СМО. Ниже приводятся процедуры, из которых формируется алгоритм этой СМО.
1. Процедура "Таймер модельного времени" (планирование основных событий). Поскольку в модели события возникают в хронологической последовательности на временной оси, то введем таймер модельного времени как одну из процедур и специальную переменную для фиксации текущего времени. При моделировании СМО совершаются некоторые события: прибытие заявки, начало и завершение обслуживания. Их следует зафиксировать и учесть их воздействие на текущее состояние системы. Кроме того, важно определить как имитировать возникновение событий и корректировать состояние СМО.
События на временной оси возникают либо в данный момент, либо в будущем, т. е. при еще не достигнутом значении модельного времени. Положим, что в СМО произошло событие "Поступлению заявки", тогда необходимо запланировать время прибытия следующей заявки, для чего нужно во-первых, разыграть случайное число и интерпретировать его как интервал времени до прихода следующей заявки и, во-вторых, прибавить значение этого интервала к текущему значению таймера модельного времени. В итоге получаем планируемое время прихода очередной заявки. Обратим внимание, что имитационная модель "знает", когда появится очередная заявка, в реальной же системе это не известно. Рассмотрим событие "Завершение обслуживания". Если известно начало обслуживания, то процесс "предсказания" времени его завершения аналогичен планированию прихода очередной заявки: разыгрывается случайная величина и ее значение прибавляется к текущему значению таймера модельного времени. Рисунок 2 иллюстрирует примеры планирования прихода первой (а) и очередной (б) заявок, а также завершение обслуживания (в).
Рисунок 2 - Планирование событий в СМО
Рассмотренные два события называются основными, поскольку их возникновение заранее планируемо, в противоположность вспомогательным ("Постановка и выход из очереди", "Начало обслуживания"). В таблице 1 сведены итоги исследования одноканальной СМО с точки зрения реализации основных событий и отработки вызываемых ими действий, при этом опущены операции по сбору и выводу статистики.
Таблица 1 Основное событиеВызываемое действиеПриход заявки1. Планирование очередного прихода
2. Проверка состояния прибора. Прибор свободен?
НЕТ: заявка встает в очередь
ДА: заявка встает на обслуживание (это вызывает переход прибора в состояние "Занят" и планирование окончания обслуживания)Окончание обслуживанияПроверка состояния очереди. Очередь пуста?
НЕТ: заявка встает на обслуживание (это вызывает продвижение заявок в очереди и планирование окончания обслуживания)
ДА: переход прибора в состояние "Свободен" Если приход и окончание обслуживания заявок запланированы и известно текущее значение таймера, то следующим очевидным шагом является "Увеличение значения таймера".
2.Процедура "Таймер модельного времени" (увеличение значения). Возникает вопрос: на какую величину увеличивать значение таймера? Возможны два основных пути: изменить значение точно на выбранную заранее разработчиком единицу модельного времени (например, на одну минуту) или сразу передвинуть значение до времени ближайшего запланированного основного события. Иными словами, шаг
приращения значений таймера либо фиксируется, либо является переменным. Очевидно, что второй путь предпочтительнее и в дальнейшем будет использоваться.
3.Процедура "Найти ближайшее событие". Ближайшее событие можно определить как первое в списке, упорядоченном по возрастанию времени свершения.
4.Процедура "Завершить моделирование". Для остановки процесса моделирования введем в модель псевдособытие "Завершение моделирования". Для нашей СМО это может быть сигнал окончания очередной смены. Тогда поступление этого события необходимо планировать. Например, моделировать работу порта в течение смены, т. е. восьми часов. Кроме этого потребуется проверка того, является ли событие "Завершение моделирования" следующим ближайшим событием.
5.Процедура "Разыграть значение целочисленной равномерно распределенной случайной величины". Процедура преобразует случайные числа, равномерно распределенные на интервале [0, 1], в целочисленные случайные величины с равномерным на интервале [А, В] распределением и может быть организована по одному из известных алгоритмов. В результате получаем необходимые для моделирования значения интервалов между приходами заявки и время их обслуживания.
6.Процедура "Обработать временные узлы". Временные узлы наступают, когда два или более событий происходят в одно и то же значение модельного времени (например, "Приход заявки" и "Завершение обслуживания"). Анализ показывает, что для нашей СМО последовательность обработки во временных узлах безразлична, хотя предпочтительнее обрабатывать первым событие "Завершение обслуживания".
Таким образом, рассмотрены процедуры, из которых формируется алгоритм одноканальной СМО. Соберем их в единую модель.
АЛГОРИТМ, МОДЕЛИРУЮЩИЙ РАБОТУ СМО
Укрупненный алгоритм изображен на рисунке З а ниже даны комментарии отдельных блоков. В блоке 1 устанавливаются начальные значения таймера модельного времени, состояние прибора "Свободно" и планируется время прихода первой заявки.
Логическая схема прихода заявки (блок 5) включает в себя процедуры 1 и 5, а также действия, указанные в таблице 1. Логическая схема конца обслуживания (блок 6) построена из аналогичных процедур и также отрабатывает соответствующие действия из таблицы 1. В блоке 7 фиксируются показатели эффективности СМО.
Рассмотренные процедуры и анализ моделирующего алгоритма показывают средства, необходимые для включения в специализированный язык моделирования СМО. Основные из них: встроенные генераторы случайных чисел, равномерно
распределенных на интервале [0, 1]; средства моделирования последовательностей случайных величин, подчиняющихся теоретическим законам распределения: пуассоновскому, равномерному, нормальному, экспоненциальному и др.; встроенный таймер модельного времени; автоматическая проверка состояния очереди после завершения обслуживания; автоматическое продвижение таймера до времени ближайшего события; автоматическая передача управления на часть модели, содержащую логическую схему обработки ближайшего события; средства автоматического сбора статистических данных в местах модели, интересующих разработчика; автоматическая распечатка собранных статистических данных.
Рисунок 3 - Моделирующий алгоритм одноканальной СМО
Все эти средства включены в специализированный язык моделирования СМО - GPSS, что значительно облегчает разработку моделей. Например, для реализации моделирующего алгоритма одноканальный СМО потребуется всего 12 операторов GPSS. Эквивалентная процедурная модель, например на ФОРТРАНе, будет содержать не менее 60 операторов. Запись на GPSS очень компактна, что, естественно, позволяет с большей тщательностью прорабатывать модель.
ПОНЯТИЕ TPAH3AKTA, БЛОКА, ТАЙМЕРА И БЛОК-СХЕМЫ
Рассмотрение конкретной СМО, например порта, показывает, что одни объекты "неподвижны", т. е. их пространственное положение зафиксировано (причалы, холодильники, подъездные и крановые пути и др.), а другие имеют возможность перемещаться относительно неподвижных, т. е. изменять свое пространственное положение (суда, грузы, вагоны, краны и др.). Таким образом, в СМО можно выделить множество статических и динамических объектов. Этот же подход сохранен в GPSS, и, как правило, первой группе объектов соответствуют блоки, а второй - транзакты. Тогда работа GPSS-интерпретатора состоит в перемещении транзактов от блоков к блокам.
Первоначально в GPSS-модели нет транзактов, но они могут быть введены и выведены в определенные моменты с учетом специфики моделируемой СМО. В модели одновременно может находиться много транзактов, но в один момент двигается только один транзакт.
Транзакт начинает движение, выходя из некоторого истока, проходит определенные блоки и заканчивает перемещение в стоке, т. е. "исчезает" из модели. Входя в блок, он вызывает соответствующую подпрограмму, которая отрабатывает, и транзакт переходит в следующий блок. Перемещение происходит до тех пор, пока либо транзакт не войдет в блок задержки, либо блок "отказывается" принять транзакт (тогда он остается в предыдущем блоке), либо транзакт не попадет в сток. Если возникло одно из этих условий, начинает перемещение другой транзакт и моделирование продолжается. Следовательно, прогон модели заключается в последовательном обращении к подпрограммам вследствие входа перемещающихся транзактов в определенные блоки.
Транзакт как объект GPSS - это абстракция, которой разработчик модели придает определенный смысл, т. е. устанавливает его соответствие с объектами реальной системы. Очевидно, что такая аналогия присутствует только в памяти человека и совершенно "безразлична" интерпретатору GPSS.
Можно провести следующую аналогию между объектами реальных систем и транзактами: в вычислительной системе транзактом может являться программа, в морском порту - судно, в универмаге - покупатель, на складе - заявка, на автомобильном шоссе - машина.
Блоки, соответствующие статическим объектам CMО, характеризуются местоположением, выполняемой операцией и операндами.
Местоположение в модели обозначается порядковой нумерацией: 1,2 и т. д. (процедура присваивания номера выполняется интерпретатором автоматически при вводе модели в ЭВМ). Кроме этого, можно метить блоки. Символическое имя (метка) состоит не более чем из пяти алфавитно-цифровых символов, причем первые три (обязательные) - буквы.
Операции - это глаголы, обозначающие функциональное назначение блоков: GENERATE (генерировать), TERMINATE (завершать), SEIZE (занять), RELEASE (освободить), QUEUE (встать в очередь), DEPART (покинуть очередь) и др. При подготовке модели можно указывать и сокращенное четырехбуквенное название операций: GENE, TERM и т. п., однако есть исключения.
Блоки содержат операнды - аргументы, используемые при обращении к соответствующим подпрограммам. Операнды обозначаются символами А, В, С, D, Е, F и G и в зависимости от блока их число различно, но не более семи.
Соответственно можно провести следующие аналогии между объектами реальных систем и блоками: в вычислительной системе объектом, обозначаемым блоком, может быть ЭВМ, в морском порту - причал, в универмаге - касса, на складе - стеллаж, на автомобильном шоссе - автостоянка.
Интерпретатор GPSS автоматически обслуживает таймер модельного времени. В начале моделирования интерпретатор планирует время прихода первого транзакта и устанавливает таймер в это значение. Транзакт входит в модель и в этот же момент продвигается интерпретатором через все возможные блоки. Ничего другого в текущий момент не происходит. Далее интерпретатор продвигает таймер до значения времени следующего (или следующих) запланированного события. Опять перемещаются транзакты, вновь продвигается таймер и т. д. Так корректируется модельное время.
Пример 1. Покажем, как изменяется модельное время для морского порта с одним причалом (таблица 2).
Когда приходит первое судно (транзакт входит в модель), таймер устанавливается в значение 2, и судно без ожидания идет на обслуживание (транзакт продвигается от блока к блоку, пока не попадет в блок задержки, что соответствует времени обработки судна). Никакие события далее не происходят до момента времени, равного 70. Таймер устанавливается в значение 70, приходит второе судно (следующий транзакт входит в модель). Судно ожидает освобождения причала (транзакту не разрешается войти в блок, обозначающий причал). В момент времени 70 никаких событий больше нет и таймер продвигается в значение 90, когда очередное судно приходит в порт (очередной транзакт входит в модель) и т. д.
Таблица 2
Последо-ватель-ность событийСобытияВремя завершения событияФактическое, часы-минутыМодельное,
мин1Начало смены8-0002Первое судно прибыло и идет на обработку8-32323Приходит второе судно9-10704Приходит третье судно9-30905Первое судно обслужено10-121326Второе судно идет на обработку10-121327Приходит четвертое судно11-00180 Заканчивая рассмотрение таймера, отметим, что он регистрирует лишь целые значения, а единицу модельного времени выбирает разработчик. Когда значение таймера продвигается в очередную точку, происходит задержка на время коррекции состояния модели. В реальной системе такой задержки не существует.
МОДЕЛИРОВАНИЕ ВХОДЯЩИХ И ВЫХОДЯЩИХ ПОТОКОВ
Истокам и стокам СМО в GPSS соответствуют блоки GENERATE (генерировать) и TERMINATE (завершить) соответственно. Через GENERATE транзакты поступают в модель, т. е. моделируется входящий поток. Таких блоков в одной модели может быть несколько. Когда транзакт входит через блок GENERATE, интерпретатор планирует время прихода следующего разыгрыванием случайного числа в соответствии с распределением интервала поступления и прибавляет его к текущему значению таймера. При достижении этого времени следующий транзакт вводится в модель и т. д.
Общий вид блока: GENERATE А, В, С, D, Е. В таблице 3 приведены операнды и их значения для базисного GPSS. Графическое изображение блока представлено на рисунке 4.
Рисунок 4 - Графическое изображение блока GENERATE
В данном параграфе рассмотрим моделирование входящих потоков только с равномерным законом распределения интервалов прибытия заявок.
Таблица 3
ОперандЗначениеЗначение по умолчаниюAСредний интервал времениНольBПоловина поля допуска равномерно распределенного интервалаНольCСмещение интерваловСмещение отсутствуетDОграничительБесконечностьEУровень приоритетаНоль Пример 2. Имитировать входящий поток с равномерным распределением интервалов между заявками на отрезке [18, 24].
Рабочая формула:
xi = 18+(24-18)ξi,
где xi - случайная, равномерно распределенная величина на интервале [18, 24];
ξi - псевдослучайные числа, ξi [0,1]. Для реализации на Фортране потребуется восемь операторов для
ξi и четыре для xi. В GPSS достаточно записать GENERATE 21, 3.
Положим, что в интервале [18, 24] были разыграны следующие значения: 19, 20, 20. Тогда первый транзакт войдет в модель в момент времени 19, второй - 39, третий - 59. Напомним, что таймер GPSS регистрирует только целые значения.
Пример 3. Транзакты должны поступать в модель точно через 2 единицы времени. Тогда запишем GENERATE 2.
Операнд С используется как для ускорения, так и для замедления прихода первого транзакта. Операнд D указывает число транзактов, которые могут войти в модель через этот блок, затем он перестает быть активным. Операнд Е устанавливает для транзакта уровень приоритета задаваемого числами от 0 до 127. Чем больше число, тем выше приоритет.
Пример 4. Имитировать входящий поток из 30 заявок 2-го уровня приоритета. Интервалы между приходами имеют равномерное распределение, т. е. 10±3 мин. Первая заявка должна прийти спустя 32 мин.
Такой входящий поток моделируется следующим образом:
GENERATE 10, 3, 32, 30, 2.
Для удаления транзактов из модели, т. е. для имитации выходящих потоков, в GPSS используется блок TERMINATE. Он всегда разрешает транзакту выйти, а количество TERMINATE в модели не ограничено. Общий вид блока: TERMINATE А. Операнд А задает величину, вычитаемую из счетчика завершений каждый раз при входе транзакта в блок TERMINATE. По умолчанию операнд А равен нулю. Графическое изображение блока TERMINATE приведено на рисунке 5.
Рисунок 5 - Графическое изображение блока TERMINATE
В счетчик завершений интерпретатор заносит целое положительное число из поля операндов оператора START (начать). При моделировании транзакты попадают в блоки TERMINATE и содержимое счетчика уменьшается. При достижении им нулевого значения моделирование в GPSS завершается.
Пример 5. Выполнить моделирование поведения вычислительной системы для 50 заявок.
Для завершения моделирования после выхода 50-й заявки через TERMINATE в счетчик завершений необходимо занести 50:
˳
˳
˳
TERMINATE 1,
START50
Пример 6. Разработчик принял за единицу модельного времени 1 мин. Завершить моделирование через 7 часов.
Для этого нужно включить в модель сегмент:
GENERATE 420
TERMINATE 1
а в счетчик завершений занести единицу START 1.
Во всех других блоках TERMINATE, если они есть в программе, операнд А не указывается. В момент времени 420 транзакт входит в блок GENERATE и сразу же перейдет в блок TERMINATE, из счетчика завершений вычитается единица и моделирование завершается. Таким образом имитируются "часы" в GPSS.
Пример создания модели идеализированного морского порта
Рассмотрим модель идеализированного морского порта. Пусть суда заходят в порт каждые 10 - 11 минут. Суда не задерживаются в порту и тут же покидают его. Промоделируем работу порта на протяжении 2х часов.
В качестве единицы модельного времени выберем 30 секунд. Таким образом удастся получить целочисленные значения интервалов модельного времени.
Произведем пересчет единиц времени:
время прихода судна - 600 - 660 секунд или 20 - 22 интервала в 30 секунд
время работы порта - 7200 секунд или 240 интервалов в 30 секунд.
Таблицу соответствий приведенной модели представлена ниже (Таблица 4).
Таблица 4 - Таблица соответствия
Реальный объектОбъект GPSSWНаименованиесуднотранзакттаймертранзакт
На рисунке 6 представлена блок-схема модели.
Текст имитационной модели
GENERATE21,1
TERMINATE0
GENERATE240
TERMINATE 1
Результаты моделирования
GPSS World Simulation Report - Untitled Model 1.2.3
Tuesday, February 18, 2011 19:03:42 START TIME END TIME BLOCKS FACILITIES STORAGES
0.000 240.000 4 0 0
LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY
1 GENERATE 11 0 0
2 TERMINATE 11 0 0
3 GENERATE 1 0 0
4 TERMINATE 1 0 0
FEC XN PRI BDT ASSEM CURRENT NEXT PARAMETER VALUE
13 0 253.930 13 0 1
14 0 480.000 14 0 3
Из результатов моделирования следует, что за 2 часа порт покинуло 11 судов.
ЗАДАНИЕ
Суда заходят в порт в интервале времени A минут и тут же покидают его. Промоделировать работу порта на протяжении B часов. Узнать количество судов, покинувших порт.
ВариантАВ117-182230-3110312-163,548-91520-221263-51719-228814-169944-45201037-396112-431213-1541316-2051440-44101523-27121615-18417181920
ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
1. Ознакомиться с методическими указаниями.
2. Спроектировать и реализовать модель работы идеализированного морского порта с использованием средств GPSSW согласно варианту.
3. Выполнить модельный эксперимент
4. Проанализировать результаты моделирования и выяснить какое количество судов покинуло порт за указанное время
СОДАРЖАНИЕ ОТЧЕТА
1. Одноканальная СМО с очередью как объект моделирования
2. Алгоритм, моделирующий работу СМО
3. Понятие транзакта, блока, таймера и блок-схемы
4. Моделирование входящих и выходящих потоков
5. Блок-схема модели
6. Распечатка набранного текста GPSS-модели и результатов моделирования.
7. Анализ и интерпретация результатов моделирования
1
Автор
rinya_3103
Документ
Категория
Без категории
Просмотров
258
Размер файла
138 Кб
Теги
лаб2
1/--страниц
Пожаловаться на содержимое документа