Моделирование процессов обработки информации
Аннотация
Курсовая работа предназначена для практического
усвоения студентами основных разделов дисциплины «Моделирование систем»,
закрепления знаний по математическим методам и программным средствам системного
моделирования, развития практических навыков комплексного решения задач
исследования и проектирования систем на современных ЭВМ.
Система представляет в общем случае
двухканальное двухфазное устройство. Одним из лучших вариантов решения подобных
задач является имитационное моделирование, позволяющее, в отличие от
математического, более верно оценить систему и получить более точный результат.
В качестве среды имитационного моделирования
используется GPSS, как удобная и наглядная система.
Содержание
Введение
Основная
часть
.1
Описание моделируемой системы
.2
Структурная схема модели системы и ее описание
.3
Временная диаграмма и ее описание
.4
Q-схема системы и ее
описание
.5
Укрупненная схема моделирующего алгоритма и описание ее блоков
.6
Блок-диаграмма
.7
Математическая модель и ее описание
.8
Описание машинной программы решения задачи
.9
Результаты моделирования и их анализ
.10
Сравнение результатов имитационного моделирования и аналитического расчета
характеристик
.11
Описание возможных улучшений в работе системы
Заключение
Список
литературы
Приложение
Введение
Данная курсовая работа по теме: «Моделирование
процессов обработки информации» имеет следующее задание:
В узел коммутации пакетов данных, состоящий из
входного буфера, процессора, двух выходных буферов и двух выходных линий,
поступают пакеты данных с двух направлений. Пакеты данных с первого направления
поступают во входной буфер, обрабатываются в процессоре, буферизуются в
выходном буфере первой линии и передаются по выходной линии. Пакеты данных со
второго направления обрабатываются аналогично, но передаются по элементам
второй линии. Пакеты поступают через интервалы 15±7 мс на каждом направлении.
Время обработки пакета в процессоре равно 7 мс, время передачи по выходной
линии равно 15±5 мс. Если очередной пакет поступает при наличии трех пакетов в
буфере, то оно получает отказ.
Необходимо смоделировать процесс обмена пакетами
данных в течение 10с. Определить коэффициент загрузки процессора.
Актуальность подобных задач в нашем мире не
вызывает сомнения, поскольку благодаря предварительно смоделированной системе
удается гораздо быстрее и дешевле выяснить наиболее сложные и случайные моменты
работы реальной системы, вычислить ее временные и иные характеристики.
Целью моделирования является нахождение наиболее
эффективного варианта решения какой-либо задачи.
Оптимальным вариантом решения приведенной задачи
будет использование имитационного моделирования. Для решения одним из
аналитических методов, базирующихся на теории массового обслуживания, ее
следует предварительно упростить, что, естественно, скажется на точности и
достоверности полученных результатов. Использование языков программирования при
решении задачи так же не является оптимальным методом, так как разработчик
столкнется с трудностями машинной реализации программы моделирования.
Удобным вариантом реализации имитационного
моделирования является среда General Purpose Simulation System (GPSS).
1. Основная часть
.1 Описание моделируемой
системы
Задача, решаемая в данной курсовой работе,
относится к задачам теории систем массового обслуживания (СМО).
Пакеты данных на обработку поступают с двух
направлений. Пакеты данных с первого направления поступают во входной буфер,
обрабатываются в процессоре, буферируются в выходном буфере первой линий и
передаются по выходной линии. Пакеты данных со второго направления
обрабатываются аналогично, но передаются по элементам второй линии. Пакеты
данных поступают через интервалы 15±7 мс на каждом направлении. Время обработки
сообщения в процессоре равно 7 мс, время передачи по выходной линии равно 15±5
мс. Если очередной пакет поступает при наличии трех пакетов в буфере, то оно
получает отказ.
1.2 Структурная схема модели системы
и ее описание
На основании задания, прежде всего, строим
структурную схему данной СМО (Рис.1).
Рисунок 1 - Структурная схема
процесса функционирования узла коммутации пакетов.
.2 Временная диаграмма и ее
описание
Более детально процесс функционирования узла
коммутации пакетов можно представить на временной диаграмме (Рис. 2).
На диаграмме:
·
ось
1 - моменты поступления пакетов в процессор;
·
ось
2 - пребывание пакетов в приемном накопителе;
·
оси
3 - обработка пакетов в процессоре;
·
ось
4 - пребывание пакетов из первого источника в накопителе перед вторичной
обработкой;
·
ось
5 - пребывание пакетов из второго источника в накопителе перед вторичной
обработкой;
·
ось
6 - передача пакетов из первого источника по первой выходной линии;
·
ось
7 - передача пакетов из второго источника по второй выходной линии;
С помощью временной диаграммы можно выявить все
особые состояния системы, которые необходимо будет учесть при построении
блок-диаграммы.
Все описанное выше есть, по сути, этап
построения концептуальной модели системы. Следующим должен стать этап
формализации модели.
Рисунок 2 - Временная диаграмма
процесса функционирования узла коммутации пакетов.
1.3 Q-схема
системы и ее описание
Так как описанные процессы являются процессами
массового обслуживания, то для формализации задачи используем символику Q-схем.
В соответствии с построенной концептуальной моделью и символикой Q-схем
структурную схему данной СМО можно представить в виде, показанном на Рис. 3.,
где И - источник, К - канал, Н - накопитель.
Источник И имитирует процесс поступления пакетов
во входной буфер, накопитель Н1 ставит сообщения в очередь.
Заявки, обслуженные каналом К1, поступают в
накопитель Н1 или в Н2 в зависимости из какого направления они поступили , а
затем обслуживаются каналом К2 или К3, имитирующими первую и вторую выходные линии
соответственно.
.
Рисунок 3 - Структурная схема
системы в символике Q-схем.
.4 Укрупненная схема
моделирующего алгоритма и ее описание
После этапа формализации задачи необходимо
приступить к построению моделирующего алгоритма. Обобщенная схема моделирующего
алгоритма данной задачи, построенная с использованием «принципа 
t»,
представлена на Рис. 4.
После пуска модели и ввода исходных данных
происходит проверка, если обслужено заданное число заявок, то идет обработка
результатов и вывод их на печать. В обратном случае переход к следующему
интервалу 
.
Рисунок 4 - Обобщенная схема
моделирующего алгоритма процесса функционирования узла коммутации пакетов.
Обозначения, принятые в блок-схеме: OZU
- входной буфер, IC
- процессор, Vbuf1 - буфер
первой выходной лини Line1,
Vbuf2 - буфер второй
выходной линии Line2.
.7 Математическая
модель и ее описание
Для решения одним из аналитических методов,
базирующихся на теории массового обслуживания, ее следует предварительно
упростить. Существуют следующие формулы, описывающие СМО с отказами:
Kз1=
(1.1)
Kз2=
(1.2)
Kз3=
(1.3)
где tc1 - время
обработки сообщения в процессоре, tc2 и tc3 время
передачи сообщения по выходным линиям, Kз1- коэффициент
загрузки процессора, Kз2 и Kз3 -
коэффициенты загрузки выходных линий соответственно;
- суммарное
время занятости процессора, и суммарное
время занятости выходных линий соответственно;
Т - общее время моделироания.
Программа, реализующая алгоритм создана в среде
GPSS. Сообщения поступившие из двух источников направляются в общий буфер (OZU),
затем обрабатываются в процессоре (IC).
После обработки пакетов в процессоре они посредством блока TRANSFER,
содержащего параметр безусловного перехода, направляются в буферы выходных
линий Для проверки длины очереди буферов выходных линий используется оператор TEST.
Из буферов сообщения передаются по выходным линиям.
Листинг программы приводится в приложении 1.
.9 Результаты
моделирования и их анализ
Отчет GPSS
имеет следующий вид:
START TIME END TIME BLOCKS
FACILITIES STORAGES
.000 100.000 31 3
0VALUE29.00010001.00010005.00010003.00010000.00010004.00010002.00015.00022.000LOC
BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY
GENERATE 6 0 0
QUEUE 6 0 0
SEIZE 6 0 0
ADVANCE 6 1 0
DEPART 5 0 0
RELEASE 5 0 0
TRANSFER 5 0 0
GENERATE 5 0 0
QUEUE 5 0 0
SEIZE 5 0 0
ADVANCE 5 0 0
DEPART 5 0 0
RELEASE 5 0 0
TRANSFER 5 0 015 TEST 5 0 0
QUEUE 5 0 0
SEIZE 5 0 0
ADVANCE 5 1 0
DEPART 4 0 0
RELEASE 4 0 0
TERMINATE 4 0 022 TEST 5 0 0
QUEUE 5 1 0
SEIZE 4 0 0
ADVANCE 4 1 0
DEPART 3 0 0
RELEASE 3 0 0
TERMINATE 3 0 029 TERMINATE 0 0 0
GENERATE 1 0 0
TERMINATE 1 0 0ENTRIES UTIL. AVE.
TIME AVAIL. OWNER PEND INTER RETRY DELAY11 0.719 6.537 1 11 0 0 0 04 0.618
15.442 1 10 0 0 0 15 0.671 13.422 1 9 0 0 0 0MAX CONT. ENTRY ENTRY(0) AVE.CONT.
AVE.TIME AVE.(-0) RETRY
OZU 2 1 11 0 0.941 8.558 8.558 02 2 5 0 0.637
12.736 12.736 03 1 5 0 1.074 21.490 21.490 0
Из отчета можно сделать выводы: количество
заявок, прошедших через устройство IC
(процессор) равно 11, количество заявок переданных по первой линии равно 5, по
второй 4, две заявки не были обработаны - одна заявка находится в блоке ADVANCE
IC (обработка
сообщения в процессоре), другая в блоке QUEUE
Vbuf2 (буфер второй
выходной линии). Заявки получившие отказ отсутствуют. Занятость процессора -
0.719.
1.10 Сравнение
результатов имитационного моделирования и аналитического расчета характеристик
Вычислим коэффициенты занятости процессора и
выходных линий по формулам (1.1), (1.2), (1.3) и сравним полученные результаты
с результатами имитационного моделирования.
Сравним полученные результаты с
результатами имитационного моделирования.
Из сравнения видно, что результаты
моделирования незначительно отличаются от математических расчетов.
1.11 Описание возможных улучшений в
работе системы
имитационный моделирование процессор буферизация
Работа данной системы моделируется за конкретный
промежуток времени, следовательно основной задачей оптимизации является
нахождение условий, при которых обрабатывается максимальное количество заявок,
но в то же время должны отсутствовать отказы в обслуживании заявок.
Для оптимизации работы системы сделаем её
двухпроцессорной. Ниже приведен листинг программы с двумя процессорами.
Листинг программы
SIMULATE
GENERATE 15,7
QUEUE OZU
SEIZE IC1
ADVANCE 7
DEPART OZU
RELEASE IC1
TRANSFER ,VLine1
GENERATE 15,7
QUEUE OZU
SEIZE IC2
ADVANCE 7
DEPART OZU
RELEASE IC2
TRANSFER ,VLine2
VLine1 TEST L Q$Vbuf1,3,DEL
QUEUE Vbuf1
SEIZE Line1
ADVANCE 15,5
RELEASE Line1
TERMINATE
VLine2 TEST L Q$Vbuf2,3,DEL
QUEUE Vbuf2
SEIZE Line2
ADVANCE 15,5
DEPART Vbuf2
RELEASE Line2
TERMINATE
GENERATE 100
280 TERMINATE
1
START 1
Выходная статистика системы с двумя процессорами
START TIME END TIME BLOCKS
FACILITIES STORAGES
.000 100.000 30 4 0VALUEUNSPECIFIED10002.00010001.00010006.00010004.00010000.00010005.00010003.00015.00022.000LOC
BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY
GENERATE 6 0 0
QUEUE 6 0 0
SEIZE 6 0 0
ADVANCE 6 0 0
DEPART 6 0 0
RELEASE 6 0 0
TRANSFER 6 0 0
GENERATE 5 0 0
QUEUE 5 0 0
SEIZE 5 0 0
ADVANCE 5 0 0
DEPART 5 0 0
RELEASE 5 0 0
TRANSFER 5 0 015 TEST 6 0 0
QUEUE 6 1 0
SEIZE 5 0 0
ADVANCE 5 1 0
DEPART 4 0 0
RELEASE 4 0 0
TERMINATE 4 0 022 TEST 5 0 0
QUEUE 5 0 0
SEIZE 5 0 0
ADVANCE 5 1 0
DEPART 4 0 0
RELEASE 4 0 0
TERMINATE 4 0 029 TERMINATE 0 0 0
GENERATE 1 0 0
TERMINATE 1 0 0ENTRIES UTIL. AVE.
TIME AVAIL. OWNER PEND INTER RETRY DELAY5 0.350 7.000 1 0 0 0 0 06 0.420 7.000
1 0 0 0 0 05 0.684 13.683 1 11 0 0 0 05 0.724 14.480 1 10 0 0 0 1MAX CONT.
ENTRY ENTRY(0) AVE.CONT. AVE.TIME AVE.(-0) RETRY 2 0 11 0
0.770 7.000 7.000 0
VBUF2 2 1 5 0
0.775 15.491 15.491 0
VBUF1 2 2 6 0
1.028 17.140 17.140 0
Анализируя статистику, имеем: количество
обработанных заявок в процессоре 1 - 6, в процессоре 2 - 5; занятость
процессора 1 - 0,420, процессора 2 - 0,350, выходной линии 1 - 0,684, выходной
линии 2 - 1,724. И лишь незначительно умельчился коэффициент занятости выходных
линий. Из этого можно сделать вывод что добавление второго процессора не
является лучшим вариантом оптимизации системы.
Объединим две выходные линии в одну и просмотрим
выходную статистику с данными устройствами.
Листинг программы
10 SIMULATE
GENERATE 15,7
QUEUE OZU
SEIZE IC
ADVANCE 7
DEPART OZU
RELEASE IC
TRANSFER ,VLine1
GENERATE 15,7
QUEUE OZU
SEIZE IC
ADVANCE 7
DEPART OZU
RELEASE IC
TRANSFER ,VLine1
VLine1 TEST L Q$Vbuf,3,DEL
QUEUE Vbuf
SEIZE Line
ADVANCE 15,5
DEPART Vbuf
RELEASE Line
TERMINATE
DEL TERMINATE
GENERATE 100
TERMINATE 1
START 1
Выходная статистика системы с двумя процессорами
START TIME END TIME BLOCKS
FACILITIES STORAGES
.000 100.000 25 2
0VALUE23.00010001.00010003.00010000.00010002.00015.000LOC BLOCK TYPE ENTRY
COUNT CURRENT COUNT RETRY
GENERATE 6 0 0
QUEUE 6 0 0
SEIZE 6 0 0
ADVANCE 6 0 0
DEPART 6 0 0
RELEASE 6 0 0
TRANSFER 6 0 0
GENERATE 5 0 0
QUEUE 5 0 0
SEIZE 5 0 0
ADVANCE 5 0 0
DEPART 5 0 0
RELEASE 5 0 0
TRANSFER 5 0 015 TEST 11 0 0
QUEUE 7 2 0
SEIZE 5 0 0
ADVANCE 5 1 0
DEPART 4 0 0
RELEASE 4 0 0
TERMINATE 4 0 0
TERMINATE 0 0 023 TERMINATE 4 0 0
GENERATE 1 0 0
TERMINATE 1 0 0ENTRIES UTIL. AVE.
TIME AVAIL. OWNER PEND INTER RETRY DELAY11 0.770 7.000 1 0 0 0 0 05 0.741
14.822 1 7 0 0 0 2MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME AVE.(-0) RETRY
3 0 11 0 1.142 10.385 10.385 0
VBUF 3 3 7 0
1.864 26.623 26.623 0
Анализируя статистику, имеем:
Количество обработанных заявок в процессоре -
11; занятость процессора - 0,770, занятость выходной линии 0,741. Мы получили
большую загрузку процессора и выходных линий, чем при других значениях, но в
системе 4 заявки получили отказ. Следовательно, объединять выходные линии не
является лучшим вариантом оптимизации системы.
Заключение
Модель решения поставленной задачи с одним
процессором и двумя выходными линиями является оптимальным. Это объясняется
следующим: исследования системы показывают что при добавлении второго
процессора загрузка выходных линий увеличивается на 0.660 и 0.510
соответственно, но загрузка процессоров не превышает 0.420 для первого и 0.350
для второго. При замене двух выходных линий одной загрузка процессора
увеличивается на 0.510, загрузка выходной линии равна 0.741, но в системе 4
заявки получили отказ.
Список литературы
1. Советов
Б.Я., Яковлев С. А. Моделирование систем. - М.:Высш. шк.,1995.
2. Советов
Б.Я., Яковлев С.А. Моделирование систем. Практикум. - М.:Высш. шк.,1999.
3. Вентцель
Е.С. Теория вероятностей. - М.:Наука, 1969.
4. Вентцель
Е.С. Исследование операций. - М.:Радио и связь, 1972.
Приложение
SIMULATE
GENERATE 15,7
QUEUE OZU
SEIZE IC
ADVANCE 7
DEPART OZU
RELEASE IC
TRANSFER , VLine1
GENERATE 15,7
QUEUE OZU
SEIZE IC
ADVANCE 7
DEPART OZU
RELEASE IC
TRANSFER , VLine2
VLine1 TEST L Q$Vbuf1,3,DEL
QUEUE Vbuf1
SEIZE Line1
ADVANCE 15,5
DEPART Vbuf1
RELEASE Line1
TERMINATE
VLine2 TEST L Q$Vbuf2,3,DEL
QUEUE Vbuf2
SEIZE Line2
ADVANCE 15,5
DEPART Vbuf2
RELEASE Line2
TERMINATE
GENERATE 100
TERMINATE 1
START 1