Размещено на http://www.allbest.ru/

Лабораторная работа № 1. Имитационное моделирование функционирования системы

1. Цель работы

Изучение методов моделирования на ЭВМ однородных и неоднородных систем массового обслуживания (СМО).

2. Общие теоретические сведения

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

Рис. 1. Структура СМО

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

Процессы массового обслуживания типичны для связи (телефон, телеграф, почта), транспорта, производственных процессов (ремонт и обслуживание оборудования, сборочные линии), преобразования информации в ЭВМ и т.п.

В любом случае составными элементами процесса массового обслуживания являются:

* входящий поток;

* очередь;

* система пунктов обслуживания;

* выходящий поток.

Независимо от конкретной природы и характера объектов их называют требованиями (или заявками). Входящий поток требований рассматривается как последовательность событий, происходящих одно за другим в случайные моменты времени. Распределение входящего потока в основном обуславливает характер процесса массового обслуживания.

Различают потоки однородных и неоднородных событий. Однородный поток событий характеризуется только моментами наступления этих событий (вызывающими моментами) и задается последовательностью , где t_n -- момент наступления п-го события -- неотрицательное вещественное число. Однородный поток также может быть задан в виде последовательности {_n} промежутков времени между n-м и (n-1)-м событиями, которая однозначно связана с последовательностью вызывающих моментов { t_n }, где т.е. .

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

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

Требования могут выполняться

* в порядке поступления (операции на конвейере);

* с приоритетом;

* в случайном порядке (отбор образцов для статистического анализа);

* в порядке первого очередного поступления при освободившемся канале обслуживания (прием вызова телефонной станцией).

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

Существуют различные методы реализации СМО (например, с помощью Q-схем). В программе GPSS реализован метод, основанный на использовании визуальных элементов, когда построение модели СМО выполняется путем ее конструирования из некоторых стандартных подсистем, позволяющих создавать достаточно сложные системы.

2. Язык GPSS

Этот язык с 1968 года входит в математическое обеспечение машин фирмы IBM, один из наиболее популярных языков ИМ.

Общие сведения.

GPSS составлен из объектов и операций (логических правил). Объекты делятся на семь классов:

динамические (ДО);

аппаратно-ориентированные (АО);

статические (СО);

операционные (ОО);

вычислительные (ВО);

запоминающие (ЗО);

группирующие (ГО).

До -- элементы потока обслуживания заявки или "транзакты". Они создаются и уничтожаются, с каждым транзактом может быть связано некоторое число "параметров"

АО -- соответствуют элементам оборудования, которые управляются ДО.

К ним относятся:

накопители;

устройства;

логические переключатели.

СО:

очереди;

таблицы.

ЗО:

ячейки;

матрицы ячеек.

ГО:

группы;

списки.

ВО:

арифметические и булевы переменные;

функции.

Каждой очереди соответствует перечень транзактов, задержанных ы какой-либо точке системы и запись длительности этих задержек: T_з={_iз}.

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

ОО - блоки - формируют логику системы, давая транзактам указания, куда идти дальше.

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

Если транзакты заблокированы, то симулятор продвинет их тогда, когда изменятся блокирующие правила. Симулятор моделирует часы, их показания в любой момент времени называют абсолютным временем. Относительное время показывает текущее время в модели. При помощи специальной операции относительное время может устанавливаться в нуль и последующий счёт времени будет производиться от этой точки. Другой операцией в нуль могут устанавливаться оба значения времени. Все времена в модели изображаются целыми числами. Симулятор рассчитывает схему по принципу ближайшего события. Центральной задачей симулятора является просмотр и проверка всех возможных событий. Транзакты входят в цепи. Существует пять видов цепей:

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

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

Цепь прерванных событий.

Цепь парных транзактов - в текущий момент времени имеют статус парности (ожидают прибытия синхронизирующих транзактов).

Цепь пользователя включает транзакты, которые пользователь удалили из цепи текущих транзактов.

Цепь текущих событий организуется в порядке убывания приоритетов транзактов и в порядке очерёдности поступления.

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

Программа на GPSS создаётся в текстовом редакторе в определённом формате. Формат ввода содержит 3 различные поля: поле метки (позиции 5-9), поле операции (позиции 13-23) и поле переменных (позиции 26-80). Поле переменных содержит подполя, которые обозначены A, B, C, D, …,H. Последующие отделяются от предыдущих запятыми. Пропущенное значение в поле переменных выделяется запятыми (кроме конца поля).

Каждый из объектов требует определённого числа ячеек ОЗУ, в которых во время моделирования хранятся атрибуты объекта (АТО). АТО, к которым может обращаться программист, называются стандартными числовыми атрибутами (СЧА). Все СЧА имеют одно- или 2-х буквенные мнемонические обозначения. Мнемонические обозначения указывают на тип СЧА, а целочисленное значение - на конкретный СЧА.

Номера блоков можно определять символическими обозначениями. При этом обозначение должно включать от 3-х до 5-ти знаков, отличных от пробела, первые три из которых должны быть буквами. Эти ограничения необходимы для того, чтобы избежать смешивания атрибутов системы и символов. Дополнительным ограничением является недопустимость таких специальных знаков, как "-", "+", " " и т.д.

Если в полях А, В, С блока представлены стандартные числовые атрибуты N_j или W_j, то необходимо, чтобы номер блока был представлен в качестве аргумента. Если этот номер блока определяется символически, то такое представление должно быть отличным от мнемонических обозначений, указанных СЧА (N или W). В префикса символического имени используется знак доллара $. Пользователь может относительную адресацию. В символической записи CROSSn символ CROSS указывает на нужный блок, а число n-на номер блока, отсчитываемого от номера блока CROSS. При косвенной адресации предполагается, что нужный аргумент представлен некоторым параметром. Последний обозначается *, за которой следует целое число. Например, S*10 соответствует текущему значению накопителя, номер которого задан параметром 10 (буква S - означает накопитель). Косвенная адресация неприменима только для СЧА С1, М1, RN_n.

2.1 Аппаратно - ориентированные блоки.

К группе АО - блоков относятся:

SEIZE - блок занятия прибора;

RELEASE - освобождение прибора;

PREEMT - захват устройства;

RETURN - возврат захваченного прибора старому транзакту;

ENTER - вход в устройство (накопитель);

LEAVE - выход из накопитель;

LOGIG - изменение логических переключателей.

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

Для управления ключами используется оператор LOGIG. Предусмотрено три режима изменения состояния ключа: сброс в "0", установка в "1", инвертированное изменение состояния ключа на противоположное.

2.2 Динамически - ориентированные блоки.

В процесс моделирования транзакты создаются, порождают другие транзакты, собираются и уничтожаются. Каждому сообщению соответствует набор параметров, количество которых может быть установлено до 100. По умолчанию количество параметров принимается равным 12. Сообщениям можно присваивать приоритет от 0 до 127. По умолчанию приоритет равен 0. С динамической категорией объектов связаны блоки, которые можно разделить на пять групп: задержки, создания и уничтожения, изменения маршрутов, синхронизация, изменения атрибутов сообщений.

Группы: задержки: ADVANCE;

создания: GENERATE;

уничтожения: TERMINATE, SPLIT, ASSEMBLE;

изменения маршрутов: TRANSFER, LOOP, GATE, TEST;

синхронизации: MATCH, GATHER;

изменения атрибутов сообщений: ASSIGN, INDEX, MARK, PRIORITY.

Функции блоков:

ADVANCE - задержка транзактов;

GENERATE - генерации;

TERMINATE - уничтожения;

SPLIT - расщепления;

ASSEMBLE - соединения;

TRANSFER - передачи;

LOOP -организации цикла;

GATE - проверка состояния;

TEST - сравнения атрибутов;

MATCH - синхронизации;

GATHER - сбора;

ASSIGN - изменений значений параметров;

INDEX - увеличение индекса;

MARK -;

PRIORITY - изменение приоритета;

2.3 Вычислительная категория

В вычислительной категории используются объекты 3-х видов: арифметические, логические, и функции. Арифметические объекты описываются блоком variable в режиме целых чисел и FVARIABLE в режиме с плавающей точкой. Название карты описывают арифметические действия над СЧА. Аргументы и результаты рассматриваются как целые числа. При вычислении используются операции: +, -, *, / (с отбрасыванием остатка, d - деление по модулю (остаток считается положительным). Допускается использование не более 5-ти скобок.

FVARIABLE - описывает арифметические сочетания различных СЧА, вычисляемых в режиме с плавающей запятой. От аргументов и промежуточных результатов не берётся целая часть, а только от конечного результата.

Блок - BVARIABLE - логическое высказывание, состоящее из некоторой совокупности СЧА и логических атрибутов. При вычислении используется 3 типа операторов: логические, условные и булевы, например, 2 BVARIABLE М1 'LE' P6.

Функции описываются с помощью блока FUNCTION в виде совокупности диапазонов, например:

3 FUNCTION RN1,C5

0,0/.35,11/.42,1.7/.75,2.2/1.0,3.8

2.4 Статическая категория

К ней относятся блоки:

QUEUE - для занятия очереди;

DEPART - для освобождения из очереди;

TABULATE - для регистрации частоты попадания заданного СЧА;

TABLE - для вывода характеристик таблицы;

SAVEVALUE - для сохранения информации в специальных ячейках ОЗУ;

MSAVEVALUE - для сохранения информации в ячейках ОЗУ;

MATRIX - для описания матрицы;

INITIAL - для присвоения ячейкам и матрицам начальных значений.

2.5 Группирующая категория

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

2.6 Специальные типы блоков

Они используются для составления сложных моделей. К ним относятся блоки вывода статистики (PRINT, TRACE, UNTRACE), изменения модели (EXECUTE, CHANGE) блоки BUFFER и HELP, а так же блоки управления группами транзактов (JOIN, REMOVE, EXAMINE, SCAN, ALTER).

Блок BUFFER даёт возможность для немедленного прекращения обработки транзакта и возврата к началу списка текущих событий.

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

JOIN - для включения транзакта или числового значения в группу.

REMOVE - обратная функция JOIN.

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

SCAN - для анализа получения значений атрибутов транзактов и изменения их пути.

ALTER - для изменения значений атрибутов транзактов из группы.

2.7 Примеры решения задач моделирования на GPSS

Пример 1. Моделирование непрерывной случайной величины распределённой по экспоненциальному закону с = 0.1.

10 SIMULATE

20 EXPON FUNCTION RN1, C24

30 0.0/.1,.104/.2,.222/.3,.365/.4,.509/.5,.69

.6,.915/.7,1.2/.75,1.38/.8,1.6/.84,1.83/.88,2.12

.9,2.3/.92,2.52/.94,2.81/.95,2.99/.96,3.2/.97,3.5

.98,3.9/.99,4.6/.995,5.3/.995,6.2/.999,7.01.9997,8.0

40 GENERATE 10,FN$EXPON

50 MARK1

60 TABULATE XTIME

70 TERMINATE 1

80 XTIME TABLE P1,0,2,100

90 START 200

100 END

Модель включает 4 блока, выполняющие следующие функции:

40 - генерирование транзакта;

50 - присвоение параметру 1 транзакта значения, равного текущему значению часового времени;

60 - уничтожение транзакта;

10 - признак, необходимый для прогона модели;

20 - описание функции (EXPON - метка, RN1 - генератор случайной функции, число пар координат-24);

30 - задание значений пар координат функции;

80 - определение таблицы; XTIME - метка, табулируемой величиной является Р1 значение параметров последовательных транзактов, верхний предел первого интервала равен 0, ширина интервала - 2, общее число интервалов - 100;

90 - признак ввода данных, необходимый для выполнения моделирования; прогон модели должен завершится после прохождения через неё 200 транзактов;

100 - признак конца программы.

Пример 2. Составить модель композиции двух случайных величин X₁ и X₂ имеющих экспоненциальные распределения с параметрами ₁ и ₂ (Х= X₁ + X₂), удовлетворяющих обобщённому закону Эрланга 1-ого порядка:

g(t)= ₁₂(e^-1- e^-2)/(₁-₂).

Рис. 10.1. К задаче моделирования композиции 2-х случайных величин.

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

10 SIMULAT

20 EXPON FUNCTION RN1, C24

30 0.0/.1,.104/.2,.222/.3,.365/.4,.509/.5,.69

.6,.915/.7,1.2/.75,1.38/.8,1.6/.84,1.83/.88,2.12

.9,2.3/.92,2.52/.94,2.81/.95,2.99/.96,3.2/.97,3.5

.98,3.9/.99,4.6/.995,5.3/.995,6.2/.999,7.01.9997,8.0

40 GENERATE 0,0,,1

50 ASSIGN 1,K500

60 INPUT ADVANCE 10,FN$EXPON

70 ADVANCE 20, FN$EXPON

80 TABULATE XTIME

90 LOOP 1,INPUT

100 TERMINATE 1

110 XTIME TABLE M1,0,5,100

120 START 1

130 END.

Функции блоков:

40 - генерирование 1-ого транзакта в момент времени t=0;

50 - присвоение параметру 1 значения, равного 500;

60 - моделирование экспоненциального распределённых временных интервалов с параметром ₁;

70 - моделирование экспоненциального распределённых временных интервалов с параметром ₂;

80 - формирование таблиц частот XTIME для суммарных интервалов;

90 - контроль числа прохождений транзактов через сегмент блоков, начинающийся с блока INPUT;

100 - уничтожение транзакта.

Пример 3. Моделирование однолинейной системы с пуассоновским входящим потоком с параметром = 0.1 1/сек. И экспоненциальным временем обслуживания с параметром = 0.2 1/сек.

10 SIMULATE

20 LINE EQU 1

30 EXPON FUNCTION RN1,C24

40 0.0/.1,.104/.2,.222/.3,.365/.4,.509/.5,.69

.6,.915/.7,1.2/.75,1.38/.8,1.6/.84,1.83/.88,2.12

.9,2.3/.92,2.52/.94,2.81/.95,2.99/.96,3.2/.97,3.5

.98,3.9/.99,4.6/.995,5.3/.995,6.2/.999,7.01.9997,8.0

50 GENERATE 10, FN$EXPON

60 ASSIGN 1,LINE

70 QUEUE O1

80 SEIZE LINE

90 DEPART O1

100 ADVANCE 5,FN$EXPON

110 RELEASE LINE

120 TABULATE XTIME

130 TERMINATE 1

140 XTIME TABLE M1,0,10,100

150 START 500

160 END.

9 блоков: 50 - генерирование транзактов;

60 - назначение параметру 1 транзакта номера, соответствующего прибору LINE;

70 - вхождение транзакта в очередь на прибор;

80 - занятие прибора;

90 - выход из очереди;

100 - моделирование обслуживания;

110 - освобождения прибора;

120 - формирование таблицы частот XTIME для времени прохождения транзакта;

130 - уничтожение транзакта;

20 - назначение величины 1 переменной LINE.

Пример 4. Моделирование работы однолинейной системы, имеющей 3 Пуассоновских потока требований с относительными приоритетами и параметрами ₁=0.01 1/сек., ₂=0.04 1/сек., ₃=0.05 1/сек. Экспоненциальный закон обслуживания ₁=0.2 1/сек.

10 SIMULATE

20 LINE EQU 1

30 EX FUNCTION

40 0.0/.1,.104/.2,.222/.3,.365/.4,.509/.5,.69

.6,.915/.7,1.2/.75,1.38/.8,1.6/.84,1.83/.88,2.12

.9,2.3/.92,2.52/.94,2.81/.95,2.99/.96,3.2/.97,3.5

.98,3.9/.99,4.6/.995,5.3/.995,6.2/.999,7.01.9997,8.0

50 GENERATE 100, FN$EX,,,3

60 TRANSFER ,INPUT

70 GENERATE 25, FN$EX,,,2

80 TRANSFER ,INPUT

90 GENERATE 20, FN$EX,,,1

100 INPUT ASSIGN 1,LINE

110 QUEUE LINE

120 SEIZE LINE

130 DEPART LINE

140 ADVANCE 5,FN$EX

150 RELEASE LINE

160 TERMINATE 1

170 START 1000

60, 80 - безусловная передача транзактов;

50, 70, 90 - генерирование транзактов с приоритетами 3, 2, 1.

3. Задание к лабораторной работе

Данная работа рассчитана на 8 часов машинного времени и состоит из двух частей. Первая часть включает в себя следующие этапы:

* общее ознакомление с интерфейсом и возможностями программы GPSS по данному руководству;

* реализация на ЭВМ примера, описанного в разделе 2.7 методических указаний, и запись результатов моделирования;

* написание отчета в соответствии с указанными требованиями. Вторая часть работы включает в себя

* выполнение индивидуальных заданий из приложения в соответствии с указанным преподавателем вариантом;

* написание отчета с учетом требований, указанных в разделе 4.

4. Порядок выполнения работы

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

* ознакомиться на практике с интерфейсом и возможностями программы GPSS;

* ознакомиться с составом и функциями элементов, используемых при моделировании СМО;

* проанализировать пример модели СМО, приведенный в разделе 2.7;

* реализовать на ЭВМ схему модели СМО из раздела 2.7;

* записать результаты, полученные при моделировании СМО;

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

* ответить на контрольные вопросы.

Вторая часть работы выполняется по заданиям, приведенным в приложении. Для ее выполнения необходимо:

* построить модель СМО в соответствии с индивидуальным заданием;

* выполнить моделирование СМО на ЭВМ;

* записать результаты моделирования в отчет.

5. Требования к отчету

Отчет о выполнении работы должен содержать:

* титульный лист, на котором следует указать название и номер лабораторной работы, а также фамилию и группу студента;

* цель работы;

* задание на лабораторную работу;

* схему модели СМО в соответствии с заданием;

* таблицу параметров элементов модели;

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

* выводы по результатам моделирования.

6. Контрольные вопросы

1. Что понимают под системой массового обслуживания?

2. Какие потоки событий называют однородными и неоднородными?

3. Назовите основные элементы, используемые в программе GPSS для построения моделей СМО.

4. Назовите отличительные особенности функционирования генератора заявок.

5. Назовите отличительные особенности функционирования автогенератора.

6. В чем заключаются отличительные особенности простого и приоритетного накопителей?

7. В чем заключаются отличительные особенности простого и преобразующего исполнителей?

8. Какие виды селекторов используются в GPSS? Назовите особенности их функционирования.

9. Каким образом задается последовательность опроса элементов схемы СМО?

Варианты заданий

Задание 1. На комплектовочный участок партиями по 5 штук поступают детали трех видов через промежутки времени 10, 15 и 20 минут соответственно. Причем детали второго и третьего вида предварительно проверяются на отсутствие брака на двух различных установках в течении 6 минут каждая. При этом выбраковывается примерно 6% деталей. Процесс комплектации занимает 5±3 минуты и требует наличия 4 деталей первого вида, 3 деталей второго вида и 2 третьего вида,

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

Задание 2. Дисплейный класс оборудован 4 ЭВМ и 1 сетевым принтером. Работа на ЭВМ занимает в среднем 40±10 минут, а с принтером 15±10 минут. Пользователи приходят через каждые 15 минут, причем трети из них после окончания работы на ЭВМ необходим принтер.

Смоделировать работу класса в течении дня. Оценить загруженность принтера и предложить рекомендации для более эффективного использования оборудования класса.

Задание 3. На обрабатывающий участок цеха поступают заготовки с частотой 10 заготовок в час соответственно. На первом станке цеха заготовки проходят предварительную обработку за 15±3 минуты. Первый станок позволяет обрабатывать одновременно 4 заготовки. После этого производится проверка деталей в течении 2 минут. В результате проверки 3% деталей выбраковываются, а 35% поступают на повторную обработку. Остальные детали поступают на второй станок, где обрабатываются в течении 10±2 минуты.

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

Задание 4. В цех с некоторой частотой поступают два вида деталей. Оба вида деталей проходят предварительную обработку в течении 10±5 минут и 15±3 минуты соответственно. Одновременно может выполняться обработка 2 деталей первого и 3 деталей второго вида. После этого двух видов детали обрабатываются на двух различных станках в течении 25±5 и 12±3 минуты соответственно. Причем 5% деталей второго вида выбраковывается. Затем деталь первого и второго вида поступают на сборку, которая длится 6±2 минуты.

Смоделировать работу цеха в течении 10 часов. Определить оптимальные частоты поступления деталей первого и второго видов.

Список литературы

1.Советов Б.Я., Яковлев С.А. Моделирование систем. Практикум: Учеб. пособие для вузов по спец. "Автоматизир. системы обработки информ. И упр.".-М.:Высш.шк., 1999.-224 с.

2-Советов Б.Я., Яковлев С.А. Моделирование систем. -М.:Высш.шк., 1995.- 320с.

Размещено на Allbest.ru

...