Моделирование процессов обработки информации

Аннотация.

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

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

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

Введение

Основная часть.

1.1 Описание моделируемой системы.

1.2 Структурная схема модели системы и ее описание.

1.3 Временная диаграмма и ее описание.

1.4 Q-схема системы и ее описание.

1.5 Укрупненная схема моделирующего алгоритма и описание ее блоков.

1.6 Блок-диаграмма.

1.7 Математическая модель и ее описание.

1.8 Описание машинной программы решения задачи.

1.9 Результаты моделирования и их анализ.

1.10 Сравнение результатов имитационного моделирования и аналитического расчета характеристик.

1.11 Описание возможных улучшений в работе системы Заключение Список литературы Приложение.

Данная курсовая работа по теме: «Моделирование процессов обработки информации» имеет следующее задание:

В узел коммутации пакетов данных, состоящий из входного буфера, процессора, двух выходных буферов и двух выходных линий, поступают пакеты данных с двух направлений. Пакеты данных с первого направления поступают во входной буфер, обрабатываются в процессоре, буферизуются в выходном буфере первой линии и передаются по выходной линии. Пакеты данных со второго направления обрабатываются аналогично, но передаются по элементам второй линии. Пакеты поступают через интервалы 15±7 мс на каждом направлении. Время обработки пакета в процессоре равно 7 мс, время передачи по выходной линии равно 15±5 мс. Если очередной пакет поступает при наличии трех пакетов в буфере, то оно получает отказ.

Необходимо смоделировать процесс обмена пакетами данных в течение 10с. Определить коэффициент загрузки процессора.

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

Целью моделирования является нахождение наиболее эффективного варианта решения какой-либо задачи.

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

Удобным вариантом реализации имитационного моделирования является среда General Purpose Simulation System (GPSS).

1. Основная часть.

1.1 Описание моделируемой системы.

Задача, решаемая в данной курсовой работе, относится к задачам теории систем массового обслуживания (СМО).

Пакеты данных на обработку поступают с двух направлений. Пакеты данных с первого направления поступают во входной буфер, обрабатываются в процессоре, буферируются в выходном буфере первой линий и передаются по выходной линии. Пакеты данных со второго направления обрабатываются аналогично, но передаются по элементам второй линии. Пакеты данных поступают через интервалы 15±7 мс на каждом направлении. Время обработки сообщения в процессоре равно 7 мс, время передачи по выходной линии равно 15±5 мс. Если очередной пакет поступает при наличии трех пакетов в буфере, то оно получает отказ.

1.2 Структурная схема модели системы и ее описание.

На основании задания, прежде всего, строим структурную схему данной СМО (Рис.1).

Рисунок 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-схем..

1.4 Укрупненная схема моделирующего алгоритма и ее описание.

После этапа формализации задачи необходимо приступить к построению моделирующего алгоритма. Обобщенная схема моделирующего алгоритма данной задачи, построенная с использованием «принципа t», представлена на Рис. 4.

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

Рисунок 4 - Обобщенная схема моделирующего алгоритма процесса функционирования узла коммутации пакетов..

Обозначения, принятые в блок-схеме: OZU — входной буфер, IC — процессор, Vbuf1 — буфер первой выходной лини Line1, Vbuf2 — буфер второй выходной линии Line2.

1.7 Математическая модель и ее описание.

Для решения одним из аналитических методов, базирующихся на теории массового обслуживания, ее следует предварительно упростить. Существуют следующие формулы, описывающие СМО с отказами:

K_{з1= (1.1)}.

K_{з2= (1.2)}.

K_з3=(1.3).

где t_c1 — время обработки сообщения в процессоре, t_c2 и t_c3 время передачи сообщения по выходным линиям, K_з1— коэффициент загрузки процессора_, K_з2 и K_з3 — коэффициенты загрузки выходных линий соответственно;

— суммарное время занятости процессора, и суммарное время занятости выходных линий соответственно;

Т — общее время моделироания.

1.8 Описание машинной программы решения задачи.

Программа, реализующая алгоритм создана в среде GPSS. Сообщения поступившие из двух источников направляются в общий буфер (OZU), затем обрабатываются в процессоре (IC). После обработки пакетов в процессоре они посредством блока TRANSFER, содержащего параметр безусловного перехода, направляются в буферы выходных линий Для проверки длины очереди буферов выходных линий используется оператор TEST. Из буферов сообщения передаются по выходным линиям.

Листинг программы приводится в приложении 1.

1.9 Результаты моделирования и их анализ.

Отчет GPSS имеет следующий вид:

START TIME END TIME BLOCKS FACILITIES STORAGES.

0.000 100.000 31 3 0.

NAME VALUE.

DEL 29.000.

IC 10 001.000.

LINE1 10 005.000.

LINE2 10 003.000.

OZU 10 000.000.

VBUF1 10 004.000.

VBUF2 10 002.000.

VLINE1 15.000.

VLINE2 22.000.

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY.

1 GENERATE 6 0 0.

2 QUEUE 6 0 0.

3 SEIZE 6 0 0.

4 ADVANCE 6 1 0.

5 DEPART 5 0 0.

6 RELEASE 5 0 0.

7 TRANSFER 5 0 0.

8 GENERATE 5 0 0.

9 QUEUE 5 0 0.

10 SEIZE 5 0 0.

11 ADVANCE 5 0 0.

12 DEPART 5 0 0.

13 RELEASE 5 0 0.

14 TRANSFER 5 0 0.

VLINE1 15 TEST 5 0 0.

16 QUEUE 5 0 0.

17 SEIZE 5 0 0.

18 ADVANCE 5 1 0.

19 DEPART 4 0 0.

20 RELEASE 4 0 0.

21 TERMINATE 4 0 0.

VLINE2 22 TEST 5 0 0.

23 QUEUE 5 1 0.

24 SEIZE 4 0 0.

25 ADVANCE 4 1 0.

26 DEPART 3 0 0.

27 RELEASE 3 0 0.

28 TERMINATE 3 0 0.

DEL 29 TERMINATE 0 0 0.

30 GENERATE 1 0 0.

31 TERMINATE 1 0 0.

FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY.

IC 11 0.719 6.537 1 11 0 0 0 0.

LINE2 4 0.618 15.442 1 10 0 0 0 1.

LINE1 5 0.671 13.422 1 9 0 0 0 0.

QUEUE MAX CONT. ENTRY ENTRY (0) AVE.CONT. AVE. TIME AVE.(-0) RETRY.

OZU 2 1 11 0 0.941 8.558 8.558 0.

VBUF2 2 2 5 0 0.637 12.736 12.736 0.

VBUF1 3 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 Описание возможных улучшений в работе системы.

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

Для оптимизации работы системы сделаем её двухпроцессорной. Ниже приведен листинг программы с двумя процессорами.

Листинг программы.

10 SIMULATE.

20 GENERATE 15,7.

30 QUEUE OZU.

40 SEIZE IC1.

50 ADVANCE 7.

60 DEPART OZU.

75 RELEASE IC1.

76 TRANSFER, VLine1.

80 GENERATE 15,7.

90 QUEUE OZU.

100 SEIZE IC2.

110 ADVANCE 7.

120 DEPART OZU.

130 RELEASE IC2.

140 TRANSFER, VLine2.

150 VLine1 TEST L Q$Vbuf1,3,DEL.

160 QUEUE Vbuf1.

170 SEIZE Line1.

175 ADVANCE 15,5.

180 DEPART Vbuf1.

190 RELEASE Line1.

200 TERMINATE.

210 VLine2 TEST L Q$Vbuf2,3,DEL.

215 QUEUE Vbuf2.

220 SEIZE Line2.

230 ADVANCE 15,5.

240 DEPART Vbuf2.

250 RELEASE Line2.

260 TERMINATE.

270 GENERATE 100.

280 TERMINATE 1.

290 START 1.

Выходная статистика системы с двумя процессорами.

START TIME END TIME BLOCKS FACILITIES STORAGES.

0.000 100.000 30 4 0.

NAME VALUE.

DEL UNSPECIFIED.

IC1 10 002.000.

IC2 10 001.000.

LINE1 10 006.000.

LINE2 10 004.000.

OZU 10 000.000.

VBUF1 10 005.000.

VBUF2 10 003.000.

VLINE1 15.000.

VLINE2 22.000.

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY.

1 GENERATE 6 0 0.

2 QUEUE 6 0 0.

3 SEIZE 6 0 0.

4 ADVANCE 6 0 0.

5 DEPART 6 0 0.

6 RELEASE 6 0 0.

7 TRANSFER 6 0 0.

8 GENERATE 5 0 0.

9 QUEUE 5 0 0.

10 SEIZE 5 0 0.

11 ADVANCE 5 0 0.

12 DEPART 5 0 0.

13 RELEASE 5 0 0.

14 TRANSFER 5 0 0.

VLINE1 15 TEST 6 0 0.

16 QUEUE 6 1 0.

17 SEIZE 5 0 0.

18 ADVANCE 5 1 0.

19 DEPART 4 0 0.

20 RELEASE 4 0 0.

21 TERMINATE 4 0 0.

VLINE2 22 TEST 5 0 0.

23 QUEUE 5 0 0.

24 SEIZE 5 0 0.

25 ADVANCE 5 1 0.

26 DEPART 4 0 0.

27 RELEASE 4 0 0.

28 TERMINATE 4 0 0.

DEL 29 TERMINATE 0 0 0.

30 GENERATE 1 0 0.

31 TERMINATE 1 0 0.

FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY.

IC2 5 0.350 7.000 1 0 0 0 0 0.

IC1 6 0.420 7.000 1 0 0 0 0 0.

LINE2 5 0.684 13.683 1 11 0 0 0 0.

LINE1 5 0.724 14.480 1 10 0 0 0 1.

QUEUE MAX CONT. ENTRY ENTRY (0) AVE.CONT. AVE. TIME AVE.(-0) RETRY.

OZU 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.

20 GENERATE 15,7.

30 QUEUE OZU.

40 SEIZE IC.

50 ADVANCE 7.

60 DEPART OZU.

75 RELEASE IC.

76 TRANSFER, VLine1.

80 GENERATE 15,7.

90 QUEUE OZU.

100 SEIZE IC.

110 ADVANCE 7.

120 DEPART OZU.

130 RELEASE IC.

140 TRANSFER, VLine1.

150 VLine1 TEST L Q$Vbuf, 3, DEL.

160 QUEUE Vbuf.

170 SEIZE Line.

175 ADVANCE 15,5.

180 DEPART Vbuf.

190 RELEASE Line.

200 TERMINATE.

260 TERMINATE.

265 DEL TERMINATE.

270 GENERATE 100.

280 TERMINATE 1.

290 START 1.

Выходная статистика системы с двумя процессорами.

START TIME END TIME BLOCKS FACILITIES STORAGES.

0.000 100.000 25 2 0.

NAME VALUE.

DEL 23.000.

IC 10 001.000.

LINE 10 003.000.

OZU 10 000.000.

VBUF 10 002.000.

VLINE1 15.000.

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY.

1 GENERATE 6 0 0.

2 QUEUE 6 0 0.

3 SEIZE 6 0 0.

4 ADVANCE 6 0 0.

5 DEPART 6 0 0.

6 RELEASE 6 0 0.

7 TRANSFER 6 0 0.

8 GENERATE 5 0 0.

9 QUEUE 5 0 0.

10 SEIZE 5 0 0.

11 ADVANCE 5 0 0.

12 DEPART 5 0 0.

13 RELEASE 5 0 0.

14 TRANSFER 5 0 0.

VLINE1 15 TEST 11 0 0.

16 QUEUE 7 2 0.

17 SEIZE 5 0 0.

18 ADVANCE 5 1 0.

19 DEPART 4 0 0.

20 RELEASE 4 0 0.

21 TERMINATE 4 0 0.

22 TERMINATE 0 0 0.

DEL 23 TERMINATE 4 0 0.

24 GENERATE 1 0 0.

25 TERMINATE 1 0 0.

FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY.

IC 11 0.770 7.000 1 0 0 0 0 0.

LINE 5 0.741 14.822 1 7 0 0 0 2.

QUEUE MAX CONT. ENTRY ENTRY (0) AVE.CONT. AVE. TIME AVE.(-0) RETRY.

OZU 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 заявки получили отказ.

Советов Б.Я., Яковлев С. А. Моделирование систем. — М.:Высш. шк., 1995.

Советов Б.Я., Яковлев С. А. Моделирование систем. Практикум. — М.:Высш. шк., 1999.

Вентцель Е. С. Теория вероятностей. — М.:Наука, 1969.

Вентцель Е. С. Исследование операций. — М.:Радио и связь, 1972.

Приложение.

10 SIMULATE.

20 GENERATE 15,7.

30 QUEUE OZU.

40 SEIZE IC.

50 ADVANCE 7.

60 DEPART OZU.

75 RELEASE IC.

76 TRANSFER, VLine1.

80 GENERATE 15,7.

90 QUEUE OZU.

100 SEIZE IC.

110 ADVANCE 7.

120 DEPART OZU.

130 RELEASE IC.

140 TRANSFER, VLine2.

150 VLine1 TEST L Q$Vbuf1,3,DEL.

160 QUEUE Vbuf1.

170 SEIZE Line1.

175 ADVANCE 15,5.

180 DEPART Vbuf1.

190 RELEASE Line1.

200 TERMINATE.

210 VLine2 TEST L Q$Vbuf2,3,DEL.

215 QUEUE Vbuf2.

220 SEIZE Line2.

230 ADVANCE 15,5.

240 DEPART Vbuf2.

250 RELEASE Line2.

260 TERMINATE.

265 DEL TERMINATE.

270 GENERATE 100.

280 TERMINATE 1.

290 START 1.