Одноканальная СМО

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

Пояснительная записка к курсовой работе

по дисциплине:

«Компьютерное моделирование» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Рязань 2011

Введение

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

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

     К основным этапам компьютерного моделирования  относятся:

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

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

     Целью курсовой работы является практическое усвоение основных разделов теоретической части курса «Компьютерное моделирование», закрепление и углубление знаний по математическим и программным средствам моделирования, получение навыков комплексного решения задач на базе современных ЭВМ.

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

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

     Одноканальная СМО – ЭВМ, на которую поступают заявки (требования на расчеты). Поток заявок – простейший со средним интервалом между заявками tср.=10 мин. Время обслуживания распределено по закону Эрланга 3-го порядка с математическим ожиданием tобсл.=8 мин.

     Определить  среднее число заявок в СМО и среднее число заявок в очереди, а также средние времена пребывания заявки в системе и в очереди. Решите задачу, используя аналитическую и имитационную модели СМО. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2. Разработка  концептуальной модели и ее формализация

  Переформулируем предложенную задачу в терминах теории массового обслуживания. В данном случае исследуемую систему можно представить в виде СМО разомкнутого типа, содержащей один канал обслуживания. Время обслуживания распределено по закону Эрланга 3-го порядка с математическим ожиданием tобсл.=8 мин. или с интенсивностью потока обслуживаний μ=1/ tобсл. При загруженном канале заявки могут ждать обслуживания в общей очереди числом мест m. Дисциплина ожидания – бесприоритетная, заявки ставятся в очередь в порядке поступления. Дисциплина обслуживания также бесприоритетная, при освобождении канала обслуживания заявка выбирается из начала очереди (дисциплина FIFO). Поток заявок – простейший, со средним интервалом между заявками tср.=10 мин. или с интенсивностью λ =1/ tср.

  Таким образом, исследуемая система представляет собой одноканальную СМО с неограниченной очередью при простейшем потоке заявок и одним обслуживающим аппаратом. Тогда модель исследуемой системы в виде СМО разомкнутого типа можно представить следующем образом (рисунок 1). 

                                                             tобсл.

                       λ 
 

     Рисунок 1. Модель исследуемой системы 
 
 
 
 
 
 
 

3. Аналитический расчет СМО

     Исследуемая система – одноканальная СМО  с неограниченной очередью при простейшем потоке заявок и произвольном времени обслуживания.

     На  одноканальную СМО поступает  простейший поток заявок с интенсивностью потока заявок λ, которую рассчитаем по формуле: 

     λ =1/ tср=1/10=0,1 (заявки/мин) 

     Время обслуживания распределяется по закону Эрланга 3-го порядка с математическим ожиданием tобсл.=1/ μ=8 (мин), где μ- интенсивность потока обслуживаний. Отсюда 

       μ=1/ tобсл. =1/8=0,125 (заявки/мин). 

     Коэффициент вариации времени обслуживания для  закона Эрланга 3-го порядка рассчитывается ν =1/ , так как k=3, то  

     ν =1/ . 

     Обозначим λ/μ=ρ. Эта величина носит название относительной интенсивности. Подставляем значения и получаем  

     ρ=0,1/0,125=0,8 

     Среднее число заявок в очереди rср. определяется по формуле Поллачека-Хинчина (1):

               

     rср.=                                                                                         (1)

     Подставляем значения и получаем:

     rср.= = = =2,128≈2,13 

     Среднее число заявок в СМО zср. рассчитываем по формуле

     Поллачека-Хинчина (2): 

     zср.=                                                                                 (2) 

Подставляя  необходимые значения величин, получаем:

     zср.= = = =2,928≈2,93 

     Среднее время пребывания заявки в системе tср.сист. рассчитываем по формуле Литтла (3). 

     tср.сист.= zср / λ                                                                                           (3) 

     Аналогично  рассчитываем среднее время пребывания заявок в очереди по формуле Литтла (4): 

     tср.оч.= rср/ λ                                                                                                (4) 

     Подставляя  в формулы (3) и (4) рассчитанные выше значения zср. и rср, а также значение интенсивности потока заявок , получаем:

     tср.сист.=2,93/0,1=29,3 (мин)

     tср.оч.=2,13/0,1=21,3 (мин)

     Расчет  величин rср. и  zср. производился по формулам Поллачека-Хинчина, так как эти формулы используется в случае, если рассматривается одноканальная СМО с неограниченной очередью, на которую поступает произвольный рекуррентный поток заявок с интенсивностью λ и коэффициентом вариации ν, заключенным между нулем и единицей: 0< ν <1. Время обслуживания tобсл. также имеет произвольное распределение со средним значением tобсл. == 1/m . Для этого случая точных аналитических формул получить не удается, можно только приближенно оценить среднюю длину очереди, ограничить ее сверху и снизу. Но, если входящий поток – простейший (как в исследуемой системе), то обе оценки - верхняя и нижняя - совпадают, и получается формула Поллачека–Хинчина (формулы (1) и (2)) [1].

     Также при расчетах использовались формулы  Литтла. Формула Литтла применяется для любой СМО, при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания .Среднее время пребывания заявки в системе равно среднему числу заявок в системе, деленному на интенсивность потока заявок.

     Точно таким же образом определяется вторая формула Литтла, связывающая среднее время пребывания заявки в очереди и среднее число заявок в очереди (формулы (3) и (4)). 

Рассмотрим  состояние системы, когда в ней  m заявок.

     Возможные переходы:

     S0 - в системе нет ни одной заявки;

     S1 - в системе одна заявка, она находится на обслуживании в обслуживающем аппарате, очереди нет;

     S2 – в системе две заявки, причем одна из них на обслуживании, другая в очереди;

     Sm – в системе m заявок , причем одна на обслуживании, а m-1 заявок в очереди.

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

                     λ                      λ                 λ     .........   λ               λ

                     μ                     μ                   μ    .........   μ               μ 

Рисунок 2. Граф переходов

     Этой  системе соответствует матрица  интенсивности переходов  Λ . Сумма интенсивностей переходов, выходящих данного состояния записывается со знаком «-» в главной диагонали. Интенсивности переходов, входящие в данное состояние записываются со знаком «+».

                   S0            S1           S2                                   Sm        

         S0        -λ         λ            0 …………...  …0

Λ=     S1         μ     (-λ +μ)       λ ………0  …….0                                                      

            S2         0          μ        (-λ +μ)      λ……...0

          Sm         0            0              0  ……. μ     (-λ +μ)     λ

     По полученной матрице составим систему уравнений. Запись ведется по столбцам.

В установившемся режиме имеем систему алгебраических уравнений:

- λP0 + μP1=0

λP0-( λ +μ)P1+ μP2=0                                                                                             (*)

λP1-( λ +μ)P2+ μP3=0

………………………

λPm-1-( λ +μ)Pm+ μPm-1=0

Дополним  систему условием нормировки:

                                                              ∞

                                                             ∑Pi=1                                                      (**) 

                                                             i=0 

Введем  обозначение ρ =λ/ μ= υср* λ.

Решая систему с приведенными обозначениями , получаем:

Из первого  уравнения: P1= ρP0

Из второго  уравнения: P2= ρP1= ρ²Po

Из третьего уравнения: P3= ρP2= ρ³Po

………………….

Из m-го уравнения: Pm= ρPm-1= ρ^mPo

Чтобы найти Pi, найдем прежде P0,подставив их в уравнение (**), получим:

n        n

∑ Pi=∑ ρⁱ Po=1

i=0      i=0 

Если  ρ<1, то существует предел суммы как суммы бесконечно убывающей геометрической прогрессии. Таким образом:

P0=(1/(1-ρ))^-1         

P0=1- ρ

1- ρ=η,      следовательно η – коэффициент загрузки.

ρ =1- η

Тогда P0=1-ρ=η – вероятность того, что система простаивает или это коэффициент простоя СМО. Таким образом, физический смысл коэффициента ρ состоит в том, что он определяет загрузку СМО или вероятность того, что система не простаивает.

Рассчитаем  вероятность для исследуемой системы:

P0=1- 0,8=0,2 

4. Алгоритмизация  модели

  Работу СМО можно представить в виде непрерывной цепи блоков, добавив к ней компоненты, предназначенные для управления моделированием. Блоки GPSS используются для описания функций моделируемой системы и управляют движением транзактов. После выполнения соответствующей программы транзакт либо продолжает движение к следующему блоку, либо задерживается на некоторое время в том же блоке, где он находился. В зависимости от назначения блоки подразделяются на несколько групп [2]. В данной моделируемой системе будут использоваться следующие группы блоков:

1. Блоки, осуществляющие модификацию атрибутов транзактов (ADVANCE, GENERATE, TERMINATE).
2. Блоки, организующие использование объектов аппаратной категории (SEIZE, RELEASE).
3. Блоки, обеспечивающие получение статистических результатов (QUEUE, DEPART).

     Порядок блоков в блок-диаграмме соответствует  порядку обслуживания заявок в моделируемой системе массового обслуживания. Блок-диаграмма модели работы моделируемой системы представлена в Приложении 1.

     Заполним  таблицу определений (см. таблицу 1). Таблица определений является списком различных элементов языка GPSS, использованных в модели, с краткой характеристикой тех частей системы, которые описываются этими элементами [3]. 
 
 
 
 

     Таблица 1 - Таблица определений

 
 
 
 
 
 
 
 
 
 
 

5. Кодирование программы

    Программа была разработана на основе алгоритмического описания модели и составлена на языке  имитационного моделирования GPSS.

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

транзакта  из очереди,  занятие  устройства,  задержку  на  время обработки

(выполнения  транзакта),    освобождение  устройства,  уход  транзакта из

моделируемой  системы [3]. Модель включает   в   себя    семь   общих    блоков,    которые    выполняют следующие функции:

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

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

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

     именем  Device,  имитирующим ecnhjqcndj  с одним входом  и одним

выходом;

4 - выход  транзакта из очереди;

5 - моделирование  обслуживания транзакта устройства  Device;

6 - освобождение  транзактом устройства Device;

7 - удаление  одного транзакта из модели.

    Также модель  содержит  помимо  основного  сегмента (блоки

1-9) дополнительный,  который задает время моделирования (блоки

10-11). Блоки GENERATE  работают   независимо   друг   от   друга.      Через      100      единиц модельного  времени  блок  GENERATE  с  номером  10 сгенерирует один   транзакт,      что   вызовет   вычитание   единицы   из   счетчика завершений и моделирование прекратится.

     Также, необходимо учесть, что время обслуживания в модели распределено по закону Эрланга 3-го порядка  В этой модели выборка случайных чисел,  распределенных по закону Эрланга, формируется с помощью  с  датчика равномерно распределенных чисел RN1 и вычисляемого объекта функции с именем ERLAN, функция непрерывная (C) и задана таблично 23 узловыми точками.

     Строки   1-6      модели      определяют   функцию   распределения

Эрланга  третьего  порядка.    Моделирование наступления событий

производится  блоком    GENERATE,    операнд A  которого  является

величиной обратной параметру λ.

Все описанные  выше события были реализованны с  помощью возможностей языка GPSS.

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

Generate [интервал],[разброс],[задержка],[ограничение],[приоритет].

Интервал —     среднее время между созданием транзакций;

Разброс —     разброс времени между созданием транзакций (число или функция);

Задержка —     начальная задержка создания первой транзакции;

Ограничение      —     максимальное количество создаваемых транзакций;

Приоритет          —     приоритет создаваемых транзакций.

• TERMINATE [<вычитаемое>] - данный блок уничтожает транзакции, входящие в него. Попытка захвата транзакцией блока всегда успешна.

 Вычитаемое      —     значение, вычитаемое из счётчика завершения при удалении очередной транзакции (0 по умолчанию).

• SEIZE [<имя устройства>] - данный блок устанавливает заданное одноканальное устройство в состояние занятости входящей в него транзакцией.

Имя устройства      —     имя или номер устройства.

Действие  блока:

Если  данное устройство свободно, то входящая транзакция занимает

его и  пытается войти в следующий блок.

 Если  устройство занято, транзакция помещается  последней в очередь

ожидающих это устройство (с тем же приоритетом).

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

мгновенно с точки зрения моделирования. Внесение задержек в прохождение

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

• ADVANCE [<интервал>],[<разброс>]

Интервал, разброс      —     имеют тот же смысл, что и аналогичные пара-

метры блока GENERATE.

• RELEASE [<имя устройства>]

Действие  блока:

Транзакция, владеющая устройством, покидает его  и переходит

к следующему блоку.

Транзакция, вытесненная из владения устройством, удаляется

из его  списка прерывания.

• QUEUE имя очереди [<количество>]

Количество      —     количество  единиц,  на  которые  увеличивается длина

очереди при вхождении заявки в блок.

• DEPART [<имя очереди>],[<количество>]