Исследование системы методом имитационного моделирования

Министерство образования и  науки Российской Федерации

 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ»

 

Факультет информационных технологий

 

Кафедра программного обеспечения  вычислительной техники 

и автоматизированных систем

 

 

 

Курсовая работа

 

по дисциплине "Компьютерное моделирование"

 

«Исследование системы методом имитационного  моделирования»

 

 

 

 

 

 

 

Руководитель  работы

__________________ Паничев В.В.

"____" _____________________2013г.

Исполнитель

студент гр. З-11ПИнж(б)РПиС(у)

___________________ Нургалиев А.И

"____" _____________________2013г.

 

 

 

 

 

Оренбург 2013

 

Содержание

Введение 3

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

1. Разработка математической модели 5

1.1 Построение концептуальной модели 5

1.2 Формализация концептуальной модели системы 7

2. Разработка структурной схемы имитационной модели 8

2.1 Разработка моделирующего алгоритма 8

2.2 Описание программной реализации имитационной модели 14

3. Эксперимент с имитационной моделью 16

Заключение 20

Список  использованной литературы 21

 

 

 

Введение

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

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

 

 

 

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

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

 

Задание по моделированию:

- Смоделировать прохождение через  систему требований в течение  5ч.

- Определить вероятность немедленного  обслуживания

- Определить среднюю длину очереди

- Определить среднее число занятых  каналов обслуживания (из 5)

 

1 Разработка математической  модели системы 

 

1.1 Построение  концептуальной модели

 

На первом этапе компьютерного  моделирования осуществляется построение концептуальной модели системы и  её формализация. Формулируется модель и строится её формальная схема. На этапе построения концептуальной модели системы:

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

- дается описание модели с  использованием типовых математических  схем;

- принимаются окончательно гипотезы  и предположения;

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

Таким образом, на этом этапе проводится подробный анализ задачи, рассматриваются  возможные методы её решения, и дается детальное описание концептуальной модели, которая затем используется на втором этапе моделирования.

Требования из источника поступают  в накопитель с интервалом, распределенным по экспоненциальному закону с параметром  λ=1 1/мин. Во время первой фазы проходят подготовку к специальной обработке. Во время второй фазы требование пытается пойти на обработку на канал К21, в случае его занятости – на канал К22, в случае занятости канала К22– на канал К23, в случае его занятости – на канал К24, в случае занятости канала К24 – на канал К25, в случае его занятости – на канал К26, в случае занятости канала К26 – на канал К27.

В случае занятости всех семи каналов  требование встает в очередь на обработку.

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

 

Обозначения на Q-схеме:

 

И - источник требований;

Н₁ -накопитель;

K₁₁-канал подготовки данных;

K₂₁, K₂₂, K₂₃, K₂₄, K₂₅, K₂₆, K₂₇ – каналы обслуживания требований, время обслуживания каждого прибора подчиняется экспоненциальному закону с параметром =0,1 1/мин;

K₃₁-канал сбора полученных результатов;

N - поток поступающих на обработку требований с источника;

N₁ - поток необработанных требований;

N₃ - поток обслуженных требований.

 

 

Система состоит из источника требований, накопителя (с неограниченной емкостью), канала подготовки данных, семи каналов  обслуживания и канала cбора полученных результатов. На Q-схеме (рисунок 1) система представлена так: выход источника требований И соединен с вводом накопителя Н1, выход накопителя Н1 соединен с каналом подготовки данных К11, который соединен с каналами обслуживания К21..К27; выводы каналов К21..К27 соединены с входом канала сбора полученных данных, выход которого завершает схему.

 

1.2 Формализация концептуальной  модели системы

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

Опишем возможные состояния  системы для второй фазы.

Все возможные состояния системы  будут представлять собой:

S₀ – все каналы свободны;

S₁ – занят 1 канал;

S₂ – заняты 2 канала;

S₃ – заняты 3 канала;

S₄ – заняты 4 канала;

S₅ – заняты 5 каналов;

S₆ – заняты 6 каналов;

S₇ – заняты все каналы;

P_i – вероятность нахождения системы в состоянии S_i;

λ – интенсивность потока требований;

μ – интенсивность потока обслуживания;

Граф состояний представлен  на рисунке 2.

Финальные вероятности состояний  находим по формулам Эрланга:

  ;    

    где =1/10=0,1

Характеристики  эффективности:

_{Пропускная способность  системы:}

А= (1-р_n)=0,99999999998

Вероятность обслуживания требований:

Вероятность не обслуживания требований:

Оценка среднего числа занятых  приборов: _* =0,1*0,9=0,09

Оценка времени нахождения требования в системе:

Коэффициент использования каналов:

 

2 Разработка структурной схемы имитационной модели 

 

2.1 Разработка моделирующего алгоритма

 

    Для моделирования процессов функционирования системы используем детерминированный моделирующий алгоритм. Укрупненная схема моделирующего алгоритма с постоянным шагом соответствующего системе (Рисунок 1 – Q-схема) приведена на рисунке 3. Особенностью ее является наличие блока системного времени, вычисляющего значения текущих моментов времени , и блока, определяющего момент окончания моделирования по условию  , где T- время моделирования.

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

Рассмотрим детальные схемы  алгоритмов этих блоков с учетом принятых обозначений в них: Процедура обслуживания заявки каналом   оформлена в виде подпрограммы WORK[K(K,J)], позволяющей обратиться к генератору случайных чисел с соответствующим данному каналу законом распределения, генерирующей длительности интервалов обслуживания очередных заявок . Процедура генерации заявок источником также оформлена в виде подпрограммы, но D(TM), которая определяет момент поступления очередной заявки в систему.

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

 

 

После проверки условия окончания  моделирования переходят к имитации обслуживания заявки каналом 3-й фазы. Если закончено обслуживание в канале 3-й фазы, то фиксируется выход из системы очередной заявки (подсчет их) и производится освобождение этого канала  (рисунок 4).

 

Далее имитируется переход заявки из 2-й в 3-ю фазу (рисунок 5). При этом осуществляется просмотр каналов 2-й фазы и определение заявок, ожидающих обслуживания в канале К₃₁ и, если он свободен, то согласно дисциплине обслуживания выбирается одна из заявок и имитируется ее обслуживание в канале К₃₁, занятость его и освобождение канала 2-й фазы. Если канал К₃₁  занят, то осуществляется блокировка заявки в канале 2-й фазы.

 

 

 

 

Далее имитируется обслуживание заявок каналом 1-й фазы (рисунок 6). Для этого проверяется наличие заявок в накопителе Н₁   и отсутствие их в канале 1-й фазы, а также организуется обслуживание заявок каналом 1-й фазы и изменение состояний канала и накопителя.

 

 

Алгоритм имитации поступления заявок из источника в накопитель 1-й  

фазы (рисунок 7) с учетом занятости канала заключается в последовательном    выполнении следующих операций:

- проверка поступления заявки из источника в текущий момент  времени;   

- проверка отсутствия заявки  в канале 1-й фазы;

- организация обслуживания поступившей  заявки в канал первой фазы   

    (вызов процедуры  WORK и изменения состояния канала);

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

Если канал первой фазы занят, то поступившая заявка помещается в   накопитель первой фазы. После чего  опять осуществляется генерация момента поступления очередной заявки и управления передается блоку 9, который определяет момент очередного шага моделирования (рисунок 3).

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

 

2.2 Описание программной реализации  имитационной модели

Рассмотрим принципиальные особенности  реализации имитационной вероятностной  модели СМО в среде GPSS World.

Для организации реализации обработки  заявок в течение 5 часов через СМО в программной реализации использован блок генерации количества моделирования, в котором остановка моделирования происходит по факту выхода из цикла переданного через оператор TERMINATE

 

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

 

GENERATE 300

TERMINATE 1

GENERATE (EXPONENTIAL(1,0,1))

QUEUE MEN

SEIZE 11

DEPART MEN

ADVANCE (EXPONENTIAL(1,0,1))

RELEASE 11

TRANSFER ALL,CHAN1,CHAN7,4

CHAN1 SEIZE 21

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 21

TRANSFER ,OUT

CHAN2 SEIZE 22

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 22

TRANSFER ,OUT

CHAN3 SEIZE 23

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 23

TRANSFER ,OUT

CHAN4 SEIZE 24

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 24

TRANSFER ,OUT

CHAN5 SEIZE 25

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 25

TRANSFER ,OUT

CHAN6 SEIZE 26

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 26

TRANSFER ,OUT

CHAN7 SEIZE 27

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 27

OUT SEIZE 31

ADVANCE (EXPONENTIAL(3,0,1))

RELEASE 31

TERMINATE 0

 

Оператор GENERATE.

Оператор  GENERATE осуществляет первоначальный ввод транзактов в модель:

В – может быть отличен от const и рассматривается как модификатор;

С – задержка начала генерации;

D – число генерируемых транзактов (емкость источника);

Е – приоритет транзактов. Целое без знака: 0, 1,2, ...;