|
 ,
|
(11)
|
|
|
(12)
|
|
|
|
Очевидно, что если вероятность пребывания в системе любого
определенного числа заявок равна нулю, то количество заявок в системе не
ограничено. Следовательно, в буферах вычислительного центра может оказаться
сколь угодно много заявок.
модель уравнение алгоритм результат
4. Построение моделирующего алгоритма
Построение моделирующего можно разбить на два этапа:
построение обобщенного моделирующего алгоритма и построение детального
моделирующего алгоритма. Детальный моделирующий алгоритм разрабатывается для
его реализации на языках программирования, не предназначенных для
моделирования. В таких языках, как GPSS, предоставляются специальные средства
для описания и расчета большинства исследуемых и промежуточных величин. Как
правило, при написании программы для языка моделирования, достаточно разработки
обобщенной схемы моделирующего алгоритма и построения блок-диаграммы программы.
Обобщенный моделирующий алгоритм представлен на рис. 4. При его построении
использован «принцип Δt»: состояние системы
производится каждые Δt единиц времени. При
моделировании на языке GPSS квант времени - 1 единица модельного времени. В
модели исследуемой системы Δt = 1 секунда.
Окончание процесса моделирования происходит тогда, когда
заканчивается системное время моделирования (30 часов). Эта проверка показана
на схеме алгоритма в блоке 2. В блоках 3 - 8 происходит перемещение заданий
между элементами системы. На каждом этапе производится множество сравнений
времени наступления очередного события и текущего системного времени, а также
реализуется логика работы базовых элементов систем массового обслуживания и
осуществляется сбор статистических данных.
Опишем программу моделирования в символах блок-диаграмм
программ GPSS. Блок-диаграмма моделирующего алгоритма представлена на рис. 5.
Следует отметить, что задержка после занятия блоков ввода, обработки и вывода
для каждого задания одна и та же. Она определяется длиной запроса и скоростью
обработки. Скорость во всех трех устройствах одинаковая. Формулы для получения
заданной длины задания и соответствующей задержки в устройствах показаны в виде
комментариев. При получении случайного значения длины задания (выражение «Length») используется
встроенная функция RN1, которая возвращает случайную величину, распределенную
равномерно в интервале 0 - 999. Для расчета времени обслуживания задания на
каждом из устройств используется выражение «Delay».
5. Описание программы решения задачи
Программу решения задачи (см. приложение I) можно разделить на две
части, описывающие два параллельных процесса: отсчет заданного времени
моделирования и собственно прохождение заявок через вычислительный центр.
Отсчет в GPSS заданного времени моделирования реализуется элементарно.
Рассмотрим подробнее часть программы, моделирующую процесс прохождения заданий
вычислительного центра.
Непосредственно после генерации транзактов, их первому
параметру присваивается случайное значение (блок ASSIGN), равномерно
распределенное в диапазоне целых чисел [300; 700]. Таким образом моделируется
длина задания. Теперь один транзакт будет задерживаться при вводе, обработке и
выводе одно и то же время DELAY, записываемое первым параметром транзакта.
Дальнейший процесс разбивается на три фазы: ввод (INPUT),
обработку (PROCESSING) и вывод (OUTPUT). Каждая фаза состоит из следующих
блоков: постановка в очередь (QUEUE), занятие устройства (SEIZE), освобождение
очереди (DEPART), задержка (ADVANCE) и освобождение устройства (RELEASE).
6. Результаты моделирования и их анализ
Из всех данных, сгенерированных GPSS (см. приложение II), нас интересуют
статистические данные об устройствах и очередях. Согласно поставленной задаче,
необходимо определить, будет ли вычислительный центр справляться с заданным
потоком заданий и, если да, какой объем входных буферов для этого необходим.
Для того, чтобы определить, способна ли система с ограниченными буферами
обслуживать заданный поток заявок, достаточно выяснить, будет ли постоянно
расти максимальное количество заявок в любом из буферов при увеличении времени
моделирования. Определить это можно несколькими способами.
Первый, статистический, подразумевает проведение N количества
испытаний с фиксацией на каждом из них максимального количества заявок в
буферах. Если это значение стремится к постоянному значению, значит система
устойчивая при объеме буфера, немного большего полученного значения.
Второй способ позволяет качественно определить, проведя один
эксперимент, будет ли количество заявок в очереди расти до бесконечности, либо
оно ограничено определенной константой вне зависимости от времени
моделирования. Достаточно сравнить среднее время, через которое генерируются
заявки со средним временем нахождения их в буферах. Очевидно, что если заявки
генерируются чаще, чем покидают буфер, то система не устойчивая при
ограниченном объеме буферов. И наоборот, если заявки могут покидать очередь
заметно чаще, чем генерироваться, перед нами устойчивая система с ограниченными
буферами. В последнем случае объем буферов определяется как заведомо больший
максимального количества заявок в них.
Обращаясь к отчету, сгенерированному GPSS, и зная среднюю
частоту генерации заявок, имеем следующие данные:
- среднее время, через которое генерируются заявки - 300
секунд;
- среднее время пребывания заявок в буфере ввода -
617.676 секунд;
среднее время пребывания заявок в буфере обработки -
111.930 секунд;
среднее время пребывания заявок в буфере вывода -
114.143 секунд;
максимально количество заявок в буфере ввода - 6;
максимально количество заявок в буфере обработки -
2;
максимально количество заявок в буфере вывода - 2.
На основании приведенных данных можно сделать вывод, что при
данном потоке заявок и данной пропускной способности вычислительного центра
нельзя ограничивать буфер ввода никаким конечным значением. В противном случае
неизбежны отказы при непрерывной генерации заявок.
7. Описание возможных улучшений системы
Для того, чтобы вычислительный центр справлялся с заданным
потоком заявок, необходимо либо увеличить скорость ввода, обработки и вывода
заданий, либо увеличить число этих устройств, получив многоканальную систему.
Увеличить пропускную способность системы достаточно до момента, когда среднее
время пребывания заявок во всех очередях будет меньше среднего времени, через
которое генерируются заявки. В этом случае можно задать такие конечные значения
объемов буферов, при которых исключаются отказы.
Проведем ряд экспериментов с моделью системы, изменяя
скорость обработки заданий и наблюдая за средним временем пребывания задания в
очереди перед каждым из устройств. Результаты экспериментов представлены в
таблице 2.
Таблица 2 Зависимость среднего времени пребывания заданий в
буферах от скорости их обработки
|
№
|
Скорость
обработки заданий, байт/мин
|
Среднее время
пребывания заданий в буфере ввода, с
|
Среднее время
пребывания заданий в буфере обработки, с
|
Среднее время
пребывания заданий в буфере вывода, с
|
|
1
|
99
|
533352.261
|
121.025
|
120.999
|
|
2
|
100
|
6478.145
|
118.954
|
119.235
|
|
3
|
101
|
709.100
|
108.458
|
|
4
|
102
|
340.947
|
99.556
|
104.690
|
|
5
|
103
|
221.317
|
92.385
|
99.401
|
|
6
|
104
|
154.159
|
86.025
|
94.708
|
|
7
|
105
|
117.009
|
80.390
|
90.446
|
Среднее время пребывания заданий в буфере ввода лишь тогда
меньше 300 секунд, когда скорость обработки заданий больше или равно 103
байт/мин.
8. Окончательный вариант модели с результатами
Произведем описанные в предыдущем подразделе улучшения
вычислительного центра. В ходе последовательного увеличения скорости обработки
заданий и анализа получаемых результатов приходим к выводу, что для устойчивой
работы вычислительного центра достаточно увеличить пропускную способность
каждого из устройств на 3 байта в минуту (до 103 байт/мин). Промоделировав полученную
систему 1000 раз, получаем следующие средние значения (см. также приложение IV):
- среднее время, через которое генерируются заявки - 300
секунд;
- среднее время пребывания заявок в буфере ввода -
221.317 секунд;
среднее время пребывания заявок в буфере обработки -
92.385 секунд;
среднее время пребывания заявок в буфере вывода -
99.401 секунд;
максимально количество заявок в буфере ввода - 9;
максимально количество заявок в буфере обработки -
2;
максимально количество заявок в буфере вывода - 2.
Из результатов видно, что в данной системе можно использовать
буферы конечного объема. Причем буфер ввода можно ограничить значением, не
меньшим 9, а буферы обработки и вывода - не меньшим 2. Для более устойчивой
работы вычислительного центра желателен запас в емкости буферов в 1 - 2 заявки.
Зная максимальную длину заявок (700 байт), требуемые емкости
буферов можно выразить в байтах - соответственно 7000, 1400 и 1400 байт для
буферов ввода, обработки и вывода.
Заключение
При исследовании первоначальной модели системы для данной
постановки задачи достаточно качественного определения устойчивости системы:
низкая пропускная способность очевидна - среднее время пребывания заданий в
буфере ввода в два раза больше времени, через которое они генерируются. После внесенных
в систему изменений, направленных на улучшение ее эффективности, потребовалось
точное определение емкостей буферов, достаточных для безотказной работы
вычислительного центра. В целях получения достоверных результатов,
моделирование улучшенной системы было проведено 1000 раз. В процессе проведения
экспериментов емкости буферов были определены: буфер ввода - 7000, буфер
обработки и вывода - по 1400 байт.
Моделирование первоначальной системы GPSS производит за доли
секунды, а выполнение программы, моделирующей улучшенную систему 1000 раз,
производится за 13 секунд. При этом объем кода, моделирующего систему, составил
всего 24 строки. Все это раскрывает большие возможности GPSS как системы построения
имитационных моделей. Единственным и несущественным упрощением является
искусственная дискретизация модельного времени.
Список литературы
1.
Советов Б.Я., Яковлев С.А. Моделирование систем. - М.: Высш. шк.,1995.
.
Вентцель Е.С. Исследование операций. - М.: Радио и связь, 1972.
Приложения
I Текст программы, моделирующей исходную систему
LENGTH FVARIABLE 300+(RN1/1000)#400) ; длина в байтах
DELAY FVARIABLE P1#60/100 ;
задержка
SIMULATE 300, 10 ; задания
поступают через 300±10 секунд 1,V$LENGTH ;
параметр 1 - длина задания BEFORE_INPUT ; очередь перед вводом
задания в ВЦ INPUT ; начало ввода задания BEFORE_INPUT ;
выход из очереди перед вводом V$DELAY ; время ввода зависит от
длины задания INPUT ; ввод завершен BEFORE_PROCESSING ;
очередь перед обработкой задания в ВЦ PROCESSING ;
начало обработки задания BEFORE_PROCESSING ; выход из очереди перед
обработкой V$DELAY ; время обраб. зависит от длины задания PROCESSING ;
обработка завершена BEFORE_OUTPUT ; очередь перед выводом
результатов OUTPUT ; начало вывода BEFORE_OUTPUT ;
выход из очереди перед выводом V$DELAY ; время вывода
зависит от длины задания OUTPUT ; вывод завершен 108000 ;
моделирование 30 часов процесса
TERMINATE 1
START 1
II Текст программы, моделирующей улучшенную систему
LEN FVARIABLE (300+(RN1/1000)#400) ;
длина в байтах
DELAY FVARIABLE P1#60/103 ;
задержка
SIMULATE
GENERATE 300, 10 ;
задания поступают через 300±10 с
ASSIGN 1,V$LEN ; параметр 1 - длина
задания
QUEUE BEFORE_INPUT ; очередь перед вводом задания в ВЦ
SEIZE INPUT ; начало ввода задания
DEPART BEFORE_INPUT ; выход из очереди перед вводом
ADVANCE V$DELAY ; время ввода
зависит от длины задания
RELEASE INPUT ; ввод завершен
QUEUE BEFORE_PROCESSING ; очередь перед обработкой
задания в ВЦ
SEIZE PROCESSING ; начало обработки задания
DEPART BEFORE_PROCESSING ; выход из очереди перед
обработкой
ADVANCE V$DELAY ; время обраб.
зависит от длины задания
RELEASE PROCESSING ; обработка завершена
QUEUE BEFORE_OUTPUT ; очередь перед выводом рез.
обработки
SEIZE OUTPUT ; начало вывода
DEPART BEFORE_OUTPUT ; выход из очереди перед
выводом
ADVANCE V$DELAY ; время вывода
зависит от длины задания
RELEASE OUTPUT ; вывод завершен
TERMINATE
GENERATE 108000 ;
моделирование 30 часов процесса
TERMINATE 1
START 1000
III Отчет GPSS № 1
START TIME END TIME BLOCKS FACILITIES STORAGES
0.000 108000.000 20 3 0
NAME VALUE
BEFORE_INPUT 10002.000
BEFORE_OUTPUT 10006.000
BEFORE_PROCESSING 10004.000
INPUT 10003.000
LEN 10000.000
OUTPUT 10007.000
PROCESSING 10005.000
LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT
RETRY
1 GENERATE 360 0 0
2 ASSIGN 360 0 0
3 QUEUE 360 4 0
4 SEIZE 356 0 0
5 DEPART 356 0 0
6 ADVANCE 356 1 0
7 RELEASE 355 0 0
8 QUEUE 355 1 0
9 SEIZE 354 0 0
10 DEPART 354 0 0
11 ADVANCE 354 1 0
12 RELEASE 353 0 0
13 QUEUE 353 0 0
14 SEIZE 353 0 0
15 DEPART 353 0 0
16 ADVANCE 353 1 0
17 RELEASE 352 0 0
18 TERMINATE 352 0 0
19 GENERATE 1 0 0
20 TERMINATE 1 0 0ENTRIES UTIL. AVE. TIME AVAIL.
OWNER PEND INTER RETRY DELAY
INPUT 356 0.996 302.149 1 357 0 0 0 4
PROCESSING 354 0.992 302.671 1 355 0 0 0 1
OUTPUT 353 0.988 302.341 1 354 0 0 0 0MAX CONT.
ENTRY ENTRY(0) AVE.CONT. AVE.TIME AVE.(-0) RETRY
BEFORE_INPUT 6 4 360 10 2.059 617.676 635.323 0
BEFORE_PROCESSING 2 1 355 13 0.368 111.930
116.185 0
BEFORE_OUTPUT 2 0 353 11 0.373 114.143 117.814
0XN PRI BDT ASSEM CURRENT NEXT PARAMETER VALUE
362 0 108010.000 362 0 1
355 0 108017.920 355 11 12 1 674.000
354 0 108032.800 354 16 17 1 418.400
357 0 108114.160 357 6 7 1 354.000
363 0 216000.000 363 0 19
IV Отчет GPSS № 2
START TIME END TIME BLOCKS FACILITIES STORAGES
0.000 108000000.000 20 3 0
NAME VALUE
BEFORE_INPUT 10002.000
BEFORE_OUTPUT 10006.000
BEFORE_PROCESSING 10004.000
DELAY 10001.000
INPUT 10003.000
LEN 10000.000
OUTPUT 10007.000
PROCESSING 10005.000
LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT
RETRY
1 GENERATE 360000 0 0
2 ASSIGN 360000 0 0
3 QUEUE 360000 0 0
4 SEIZE 360000 0 0
5 DEPART 360000 0 0
6 ADVANCE 360000 1 0
7 RELEASE 359999 0 0
8 QUEUE 359999 0 0
9 SEIZE 359999 0 0
10 DEPART 359999 0 0
11 ADVANCE 359999 1 0
12 RELEASE 359998 0 0
13 QUEUE 359998 0 0
14 SEIZE 359998 0 0
15 DEPART 359998 0 0
16 ADVANCE 359998 1 0
17 RELEASE 359997 0 0
18 TERMINATE 359997 0 0
19 GENERATE 1000 0 0
20 TERMINATE 1000 0 0ENTRIES UTIL. AVE. TIME
AVAIL. OWNER PEND INTER RETRY DELAY
INPUT 360000 0.971 291.193 1 361000 0 0 0 0
PROCESSING 359999 0.971 291.193 1 360999 0 0 0 0
BEFORE_INPUT 9 0 360000 60476 0.738 221.317
266.003 0
BEFORE_PROCESSING 2 0 359999 49604 0.308 92.385
107.149 0
BEFORE_OUTPUT 2 0 359998 38641 0.331 99.401
111.353 0XN PRI BDT ASSEM CURRENT NEXT PARAMETER VALUE
361001 0 108000010.000 361001 0 1
0 108000027.825 361000 6 7 1 531.600
0 108000125.223 360999 11 12 1 440.400
0 108000275.748 360998 16 17 1 523.200
0 108108000.000 361002 0 19