Оптимизация программы "диспетчер-кодировщик"

 

Оглавление:

 

Введение

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

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

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

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

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

 

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

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

В некоторой автоматизированной информационной системе (АИС) поток запросов представляет собой последовательность "пачек" информации, каждая объемом Н байт. Эта информация направляется вначале в блок предварительной обработки, попадая в пять независимых модулей А1, А2, А3, А4, А5, и распределяется между ними в количествах а1, а2, а3, а4 и а5 байт соответственно (а1 + а2 + ... + а5 = Н). После использования в блоках А1 - А5 каждая пачка информации специальной программой "диспетчер-кодировщик" (ДК) направляется в другую группу модулей В1, В2, В3, В4, В5 так, чтобы в каждый из этих модулей попало ровно b1, b2, b3, b4 и b5 байт информации соответственно (b1 + b2 + ... + b5 = H).

На рисунке 1 показан один из возможных  вариантов распределения информации между модулями типа А и модулями типа В.

Блок предварительной  обработки запросов:

Рис.1

Прежде чем направить какую-то часть информации из модуля Аi в модуль Вj, программа ДК перекодирует ее, затрачивая время с_ij на перекодировку одного байта информации. Передача (с предварительной кодировкой) информации от модулей группы А к модулям группы В происходит последовательно: сначала от модуля А1 к какому-то модулю группы В, затем к другому модулю той же группы и так до тех пор, пока А1 не очистится; далее точно так же освобождается от своего запаса информации модуль А2 и так до тех пор, пока все пять модулей группы А не очистятся.

Необходимо установить, как следует распределить информационные потоки между отдельными модулями группы А и группы В, чтобы общее время "перекачки" всей информации между этими группами было минимальным (именно такое – оптимальное – распределение и должно быть предусмотрено проектировщиком программы ДК).

 

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

После использования в модулях  В1 – В5 (определение характера запросов, их сортировка по трудоемкости выполнения, регистрация и т.д.) вся информация направляется единым потоком (пуассоновский стационарный поток интенсивностью l) в блок выполнения запросов БВЗ (рис.2).

Рис.2

Каждая пачка формируется из k последовательных сигналов, появляющихся в пределах отрезка времени Y в случайные моменты, равномерно распределенные на интервале времени (0,Y). Между этими сигналами установлена определенная "дисциплина ожидания", а именно: сигнал, пришедший первым, ожидает последнего в течение времени u (u<Y) и если k-тый сигнал приходит вовремя, пачка формируется. Если же после прихода первого сигнала и до прихода последнего проходит время, большее, чем u, первый сигнал "уходит" и вся пачка теряется, не доходя до БВЗ.

Необходимо определить характер и интенсивность потока информационных пачек, достигающих БВЗ.

 

Оптимизация работы БВЗ.

Блок выполнения запросов состоит  из N независимых друг от друга, равнодоступных для потока запросов модулей. Каждый модуль при получении запроса  выполняет его в течение случайного времени, имеющего показательное распределение со средним значением Т.

Запрос, заставший все  модули занятыми, встает в очередь  при условии, что в ней находится  не более m ожидающих обслуживания запросов; в противном случае запрос теряется ("отказывается от обслуживания"). Для фирмы, эксплуатирующей АИС, такие ситуации (потеря запроса) при многократном их повторении чреваты в будущем потерей заказчика, вероятность которой пропорциональна вероятности отказа от обслуживания запроса .

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

С другой стороны, если какой-то модуль БВЗ в данный момент не занят выполнением запроса, то он участвует в обслуживании других, вспомогательных операциях. Неучастие в выполнении этих операций приносит фирме определенные убытки.

С учетом всех указанных  обстоятельств, совокупный средний  доход в единицу времени D от эксплуатации АИС может быть записан в количественном виде следующей формулой:

,

где:  
– доход, который приносит фирме один выполненный запрос;  
– штраф за единицу времени обслуживания одного запроса;  
– среднее время пребывания запроса в АИС;  
– абсолютная пропускная способность блока выполнения запросов (среднее число выполняемых запросов в единицу времени);  
– убытки от неучастия в течение единицы времени одного модуля БВЗ в выполнении вспомогательных операций;  
– количество модулей БВЗ, непосредственно занятых выполнением запросов.

Необходимо:

Выбрать оптимальное количество модулей БВЗ, предназначенных для непосредственного выполнения запросов, приняв во внимание одновременно два критерия оптимальности (направление оптимизации по обоим критериям – максимизация):

1) – средний доход в единицу времени от эксплуатации АИС  
2) – относительную пропускную способность АИС (среднюю долю выполняемых запросов) с весами (коэффициентами относительной важности) и соответственно ( ).

 

Исходные данные

Для первой части:

Данные определяются из “магического” квадрата:

11	24	7	20	3
4	12	25	8	16
17	5	13	21	9
10	18	1	14	22
23	6	19	2	15

Правило выбора индивидуальных данных следующее.

Столбец запасов информации а_i байт (i = 1, 2, ... , 5) и строка потребностей в ней b_j байт (j = 1, 2, ... , 5) соответствуют столбцу и строке квадрата, на пересечении которых находится число, совпадающее с номером варианта.

Затраты времени с_ij на перекодировку и передачу единицы информации от блока Аi к блоку Bj получаются из соответствующих элементов квадрата g_ij по формуле:

c_ij = (g_ij + f₁(No)) x 10^-3 сек

где f₁(No) = No = 3 согласно номеру варианта (№=3)

Составляем исходную матрицу стоимостей:

14	27	10	23	6	3
7	15	28	11	19	16
20	8	16	24	12	9
36	44	27	40	48	22
13	21	4	17	25	15
11	24	7	20	3	65

 

Для второй части :

k=10;

;

u/Y= ;

lисх=100 сек^-1;

Для третьей  части:

;.

;.

(руб);

(руб/сек);

 (руб/сек);

 сек;

N=10;

m=3;

;

;

 

Решение

Оптимизация программы «Диспетчер-Кодировщик»  в блоке предварительной обработки  запросов.

Задача распределения  информационных потоков между модулями группы А и В может быть решена как транспортная задача по доставке грузов, т. е. мы формализуем работу блока предварительной обработки запросов как детерминированную  модель транспортной задачи  линейного программирования, где роль "поставщиков" играют  модули А1 - А5 с запасами информации а₁ - а₅, а роль "потребителей" - модули В1 -  В5 с потребностями b₁ -  b₅ соответственно, так как все С_ij умножаются на 10 ^-3 , то расчеты можно вести с нормальными (не дробными) числами, а расчеты  вести в единицах миллисекундах.

Получим таблицу транспортной задачи:

	b1	b2	b3	b4	b5
a1	14	27	10	23	6	3
a2	7	15	28	11	19	16
a3	20	8	16	24	12	9
a4	13	21	4	17	25	22
a5	26	9	22	5	18	15
	11	24	7	20	3	65

11+24+7+20+3 = 3+16+9+22+15 = 65 , тогда

Задача является сбалансированной.

1) Составим  начальный опорный план метода северо-западного угла.

1. Выбираем клетку левого верхнего  угла таблицы.

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

3. Переходим в соседнюю невычеркнутую ячейку

4. Повторяем шаги №1, №2, №3 до тех пор, пока все запасы ресурсов не закончатся.

 

	14		27		10		23		6	3
	3
	7		15		28		11		19	16
	8		8
	20		8		16		24		12	9
			9		5
	13		21		4		17		25	22
			7		7		8
	26		9		22		5		18	15
							12		3
11		24		7		20		3		65