Эксперименты над GPSS моделью

2.1.Пояснение к работе:

 

GPSS (англ. GeneralPurposeSimulationSystem — система моделирования общего назначения) — язык моделирования, используемый для имитационного моделирования различных систем, в основном систем массового обслуживания.

 

В настоящее время разработано несколько версий GPSS, которые различаются по годам (1961-1996 гг.).

 

Наиболее удобно в системе GPSS описываются модели систем массового обслуживания, для которых характерны относительно простые правила функционирования составляющих их элементов.

В системе GPSS моделируемая система представляется с помощью набора абстрактных элементов, называемых объектами, каждый из которых принадлежит к одному из типов объектов.

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

В теории массового обслуживания эти объекты называются приборами и заявками. Когда обработка поступившего объекта заканчивается, он покидает систему. Если в момент поступления заявки прибор обслуживания занят, то заявка становится в очередь, где и ждет до тех пор, пока прибор не освободится. Очередь также можно представлять себе, как объект, функционирование которого состоит в хранении других объектов.

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

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

Статистические данные, которые выводятся системой моделирования GPSS после завершения работы модели или после очередного прогона модели, являются итоговыми, статическими.

Стандартные числовые атрибуты (СЧА) и стандартные логические атрибуты (СЛА) обеспечивают доступ к динамической статистике – характеристикам объектов модели в процессе моделирования. Эти характеристики могут использоваться блоками модели в процессе моделирования.

Описание модели должно начинаться описательным блоком SIMULATE.

Завершает описание модели описательный блок END. Система моделирования GPSS читает блоки модели до описательного блока START и начинает работу модели. При одном обращении к системе моделирования модель можно перезапускать несколько раз с различными параметрами.

 

Объекты системы GPSSсоздаются в среде GPSSWorld и могут быть сохранены в файлах. Основными объектами являются:

 

Модель: Содержит описание в виде последовательности операторов, а также множество настроек, закладок в тексте программы, сообщений об ошибках и т.д.

 

Эксперимент: создается в результате трансляции модели, далее выполнение может осуществляться по этапам под действием команд (из описания модели, либо вводятся пользователем).

 

Отчет: создается при (успешном) завершении выполнения и эксперимента. Содержит статистику по модели в целом и отдельным блокам.

 

Текст: содержит часть описания модели (подключаются в тексте программы, использоваться при вводе/выводе и т.д.

 

 

Все операторы языка GPSSделятся на блоки и команды(рис.2.1.)

Блок: элемент модели, выполняющий определенные функции.

Рис.2.1. Классификация операторов GPSS

 

Динамическим элементом модели является транзакт — абстрактный объект, который перемещается между статическими элементами, воспроизводя различные события реального моделируемого объекта. В процессе работы модели накапливается статистика, автоматически выводимая по завершении процесса моделирования. Статические элементы модели: источники транзактов, устройства, очереди и другие. Их расположение в модели определяется блоками.

Рис.2.2. Пример кода программы.

 

Понятие «вычислительный процесс» (или просто – процесс) является одним из основных при рассмотрении операционных систем.

 

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

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

Програм­ма– это план действий, а

 процесс – это само действие,

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

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

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

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

Рис.2.3. Состояния процесса

Система массового обслуживания (СМО) – математический

(абстрактный) объект, содержащий один или несколько приборов П

(каналов), обслуживающих заявки З, поступающие в систему, и

накопитель Н, в котором находятся заявки, образующие очередь О и

ожидающие обслуживания

Для описания потока заявок, в общем случае, необходимо задать

интервалы времени t _  i _ - i _{k -1} между соседними моментами t _{k - 1} и t _k

поступления заявок с порядковыми номерами (k - 1) и k соответственно

(k 1, 2,...; t ₀ 0 – начальный момент времени).

P0

P1

Pn

λ₀ λ₁λ _{n -1}

 P₀ P ₁                                                                

µ₁µ₂µ _n

Граф состояний процесса с конечным числом состояний.

Граф перехода имеет вид цепочки состояний в которой каждое состояние (кроме крайних) связаны с двумя соседними состояниями, а крайние состояния P ₀ и P_n только с одним соседним состоянием.

Граф переходов процесса с конечным числом состояний соответствует матрицы интенсивностей переходов.

P _į 0                1       2                   n – 1        n

  0  - λ₀λ₀      0 0           0

1 µ₁ – (λ₁ + µ₁)  λ₁                                 0            0

2   0                µ₂– (λ₂+ µ₂)           0            0

.   .                 .        .......    .             .

.     .                .        .....         .            .

.   .                .         .....     .            .

.   .               .          .....     .           .

n – 1 0                 0       0             – (λ _{n -1} + µ _{n -1}) λ _{n -1}

n   0                 0       0                  µ _n            - µ _n

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

Рассмотрим систему с конечным числом состояний P ₁ ,... P_n.

Обозначим через вероятность того, что в момент времени i стоянии система в состоянии P_į.

В любой момент времени i система может находится в одном из n

Возможных состояний, то есть для любого момента времени выполняется условие ∑ⁿ₁P_į (i) = 1, которое называют нормированным

Совокупность вероятностей Pį () может быть представлено вектором с числом координат, равных числу возможных состояний.

P(i) = { P_į1(i); P₂(i); … P_įn(i)}

0≤P_į (i)≤ 1;     ∑ⁿ₁P_į (i) = 1

Сформулируем правила составления уравнений для стационарных вероятностей состояний Марковского процесса по графу переходов и матрице интенсивностей переходов.

Правило 1. (по графу переходов).

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

 

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

λ₀ P _{0 =} µ₁ P ₁

(λ₁ + µ₁) P ₁ = λ₀ P ₀ + µ₂ P ₂

.

.

         .

(λ _k + µ_k) P_k = λ _k-1 P_k-1 + µ_k+1 P_k+1

µ_n P_n = λ _n-1 P_n-1

P ₀ + P ₁ + … + Р. = 1

Правило 2. (по матрице интенсивностей переходов).

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

- λ₀ P ₀  + µ₁ P ₁ = 0

-(λ₁ + µ₁) P ₁ + λ₀ P ₀  + µ₂ P ₂  = 0

.

          .

.

- (λ _k + µ_k) P_k + λ _k-1 P_k-1 + µ_k+1 P_k+1 = 0

_-- µ_n P_n + λ _n-1 P_n-1 = 0

P₀ +P₁ + … + Pn = 1

Решая полученную систему уравнений аналитически или с применением численных методов можно определить значения P ₀, P₁, … P_n стационарных вероятностей процесса.

Кроме того, могут быть рассчитаны другие характеристики исследуемой системы, в частности.

- коэффициент загрузки магистрали η = (1 - P ₀)

- среднее время ожидания программ

Средние значения длительности фаз счета

 Средние значения длительности фаз обмена

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

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

- ₍t_ож^н)_ср среднего начального времени ожидания, равного промежутку времени между моментами появления заявки на входе СМО и моментом первого назначения заявки на обслуживание или ухода из очереди.

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

t_ож^ср = ₍t_ож^н)_ср + (t_ож ⁿ)_ср

 

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

n _ср  = (t_ож^ср) * λ

Для определения n_ср   необходимо знание совокупности вероятностей нахождения в очереди заявок.

 

2.2. Формулировка задачи

 

Для мультипроцессорной вычислительной системы с числом процессоров n с двумя независимыми модулями памяти, связанными между собой общей шиной. Предложить эффективный алгоритм разрешения конфликтов на магистрали. Известно, что каждый из процессоров работает по независимой от другой программы. Каждая программа представляет чередующуюся последовательность фаз счета и обмена с памятью. Средние значения длительности фаз счета и обмена   и  соответственно. Структура системы представлена на рис.4.6.

….

1

3

2

n

….

ОП

ОП

 

Рис.2.2.

 

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

 

1) выбрать бесприоритетную дисциплину разрешения конфликтов и провести анализ при различных характеристиках программ и усредненных характеристиках;

2) проанализировать указанные приоритетные правила разрешения конфликтов (приоритет убывает с номером задачи), приоритет относительный и абсолютный.

Исходные данные представлены в табл.1 (время измеряется в относительных единицах).

Таблица 1

 

Вариант	Программы						Приоритеты
	1		2		3
	τ	T	τ	t	τ	t	1	2	3
3	35	6	45	6	55	6	1	2	3

Бесприоритетная дисциплина решения конфликтов

 

 ,  , ;

 ,  ,  ;

 

 

2.3. Решение аналитическим методом.

Бесприоритетная дисциплина решения конфликтов.

 

 

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

p000=	0,5085
p100=	0,1059
p200=	0,0936
p300=	0,0785
p120=	0,0168
p130=	0,0160
p230=	0,0121
p210=	0,0178
p310=	0,0140
p320=	0,0121
p123=	0,0023
p132=	0,0023
p231=	0,0023
p213=	0,0023
p312=	0,0023
p321=	0,0023

 

Коэффициент загрузки магистрали = 0.39

Среднее время ожидания программ:

 

 

 

2.4 Моделирование в пакете GPSS:

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

 

Бесприоритетная дисциплина:

proc1      equ         42

exch1      equ         8

proc2      equ         52

exch2      equ         8

proc3      equ         62

exch3      equ         8

initial      x$cnt      100

 

               GENERATE,,, 1;,1                  ;Приоритет. Тип приоритета?

fproc       queue      fpq

               advance  (exponential(1,0, proc1))

               depart     fpq

               seize       exch

               advance  (exponential(1,0,exch1))

               release    exch

               savevalue cnt-,1

               test le      x$cnt,0,fproc

               savevalue fres,((ac1/qc$fpq)-qt$fpq)

               terminate 1

 

               GENERATE,,,1;,2

sproc       queue      spq

               advance  (exponential(1,0,proc2))

               depart     spq

               seize       exch

               advance  (exponential(1,0,exch2))

               release    exch

               savevalue cnt-,1

               test le      x$cnt,0,sproc

               savevalue sres,((ac1/qc$spq)-qt$spq)

               terminate 1

 

               GENERATE,,,1;,3

tproc       queue      tpq

               advance  (exponential(1,0,proc3))

               depart     tpq

               seize       exch

               advance  (exponential(1,0,exch3))

               release    exch

               savevalue cnt-,1

               test le      x$cnt,0,tproc

               savevalue tres,((ac1/qc$tpq)-qt$tpq)

               terminate 1

 

Start 3

 

Отчет

 

         GPSS World Simulation Report - Untitled Model 3.3.1

 

 

              Saturday, April 15, 2017 21:33:39 

 

      START TIME      END TIME BLOCKS FACILITIES STORAGES

           0.000      2202.558 33   1     0

 

 

         NAME                  VALUE 

     CNT                    10006.000

     EXCH                   10010.000

     EXCH1                      8.000

     EXCH2                      8.000

     EXCH3                      8.000

     FPQ                    10007.000

     FPROC                      2.000

     FRES                       10012.000

     PROC1                     42.000

     PROC2                     52.000

     PROC3                     62.000

     SPQ                    10008.000

     SPROC                     13.000

     SRES                   10013.000

     TPQ                    10009.000

     TPROC                     24.000

     TRES                   10011.000

 

 

 LABEL         LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY

               1 GENERATE        1        0  0

FPROC          2 QUEUE          43        0  0

               3 ADVANCE        43        0  0

               4 DEPART         43        0  0

               5 SEIZE          43        0  0

               6 ADVANCE        43        0  0

               7 RELEASE        43        0  0

               8 SAVEVALUE      43        0  0

               9 TEST           43        0  0

              10 SAVEVALUE       1        0  0

              11 TERMINATE       1        0  0

 

Раздел 3.

 Моделирование динамической управляющей системы заданной структуры с коррекцией по критерию устойчивости

3.1.Определение, понятия динамической системы.

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

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

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

Абстрактная динамическая система представляет собой математическую модель некоторого объекта, процесса или явления.

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