Планирование вычислительных процессов в системе

Размещено на http://www.allbest.ru/

В работе рассмотрены вопросы планирования вычислительных процессов в системе. Рассмотрен верхний и средний (диспетчеризация) уровни планирования.

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

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

Диспетчер - программа, которая выбирает задачи из “очереди на выполнение”, переводят их в активное состояние, и передаёт им контроль над центральным процессором.

Дисциплины обслуживания (ДО) - правила, в соответствии с которым из очереди выбирается соответствующее требование и предоставляется ресурс.

Требования к ДО:

- ДО должны обеспечивать высокий показатель эффективности, при этом время ожидания должно быть равномерно;

- Необходимо, чтобы ДО была минимальна по трудоёмкости.

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

Классификация ДО

§ бесприоритетные ДО

џ линейные

- в порядке поступления (FIFO)

- в инверсном порядке (LIFO)

- случайный выбор (RAND)

џ циклические ДО

- циклический алгоритм (RR)

- многоуровневый циклический алгоритм (FB)

- смешанный алгоритм

§ приоритетные ДО

џ с фиксированным приоритетом

- ДО с относительным приоритетом (ОП)

- с абсолютным приоритетом (АП)

- адаптивное обслуживание

џ с динамическим приоритетом

- в зависимости от t_ожид

- в зависимости от t_обслуж

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

- Линейные ДО характеризуются одинаковым средним временем ожидания;

- циклические ДО обслуживают короткие заявки с неявным приоритетом;

- бесприоритетые ДО не требуют предварительной информации о длительности заявок;

- уменьшение длительности ожидания коротких заявок происходит за счет увеличения t_ожид длинных заявок.

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

Для ДО с динамическим приоритетом приоритет заявок изменяется в период пребывания в вычислительной системе либо в процессе t_ожид, либо в процессе t_выполн.

Задание

Вычислительная система располагает оперативной памятью (ОП) V и внешним объемом памяти Н (НМД). ОП память выделяется перемещаемыми разделами, которые исключают влияние фрагментации. Реализуется режим мультипрограммирования: если одновременно выполняется несколько задач, то процессорное время распределяется между ними равномерно. В систему поступает поток из М заданий, очередное задание поступает через время t_i, для простоты каждое задание состоит из одной задачи и требует объем ОП - v_i, объем внешней памяти h_i, процессорное время. Каждое задание использует свою внешнюю память только для ввода данных в течение времени q*h_i , после чего начинается счет. Однако закрепленные за каждым заданием носители освобождаются только после завершения задания. Предположим, возможно параллельное использование внешней памяти заданиями без задержки друг друга. Если бы задания выполнялись по одному, то на каждое задание было бы затрачено время Т_i = q*h_i + ф_i. Вновь поступившие задания помещаются в очередь. Для выбора заданий из очереди на выполнение используются два алгоритма:

среди заданий в очереди, для которых достаточно свободных ресурсов, выбирается задание, поступившее первым (правило FIFO);

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

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

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

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

Поток заданий сформирован в соответствии с вариантом (расчёт номеров задач см. приложение 1). Исходные данные представлены в таблице 1.2.1.

Таблица 1.2.1. Последовательность заданий

№	1	2	3	4	5	6	7	8	9	10
ki	4	0	2	1	4	0	2	1	4	0
ti	4	0	2	1	4	0	2	1	4	0
tп	4	4	6	7	11	11	13	14	18	18
vi	3	6	2	3	3	6	2	3	3	6
hi	2	2	3	4	2	2	3	4	2	2
фi	60	70	40	90	60	70	40	90	60	70
q*hi	10	10	15	20	10	10	15	20	10	10

Здесь

k_i - номер задачи;

t_i - интервал поступления задания;

t_п - время поступления задания;

v_i - требуемый заданию объём ОП;

h_i - требуемый заданию объём НМД;

ф_i - трудоёмкость задания;

q*h_i - время ввода задания.

Таблица 1.3.1. Последовательность событий в системе

Время	Событие	V	H	k
4	Поступили задания 1 и 2, свободных ресурсов хватает, они назначаются на выполнение. Начинается ввод заданий 1 и 2.	7	8	0
6	Поступило задание 3, свободных ресурсов хватает, начинается ввод задания 3. Продолжается ввод заданий 1 и 2.	5	5	0
7	Поступило задание 4, свободных ресурсов хватает, начинается ввод задания 4. Продолжается ввод заданий 1, 2 и 3.	2	1	0
11	Поступили задания 5 и 6. Ни одному из них не хватает свободных ресурсов, они ставятся в очередь. Продолжается ввод заданий 1, 2, 3 и 4.	2	1	0
13	Поступило задание 7, свободных ресурсов заданию не хватает, оно ставится в очередь. Продолжается ввод заданий 1, 2, 3 и 4.	2	1	0
14	Поступило задание 8, свободных ресурсов заданию не хватает, оно ставится в очередь. Окончен ввод заданий 1 и 2. Продолжается ввод заданий 3 и 4. Процессорное время делится между заданиями 1 и 2.	2	1	2
18	Поступили задания 9 и 10, свободных ресурсов ни одному из них не хватает, они ставятся в очередь. Продолжается ввод заданий 3 и 4. Процессорное время делится между заданиями 1 и 2.	2	1	2
21	Окончен ввод задания 3. Продолжается ввод задания 4. Процессорное время делится между заданиями 1, 2 и 3.	2	1	3
27	Окончен ввод задания 4. Процессорное время делится между заданиями 1, 2, 3 и 4.	2	1	4
179	Завершено выполнение задания 3, ресурсы, занятые им, освобождены. Свободных ресурсов достаточно для назначения на выполнение следующего задания. По алгоритму FIFO на выполнение назначается задание 5, поступившее в систему раньше других. Начинается ввод задания 5	1	2	3
Время	Событие	V	H	k
189	Окончен ввод задания 5. Процессорное время делится между заданиями 1,2, 4 и 5.	1	2	4
242	Завершено выполнение задания 1, ресурсы, занятые им освобождены. По дисциплине FIFO на выполнение назначается первое задание в очереди, которому хватает ресурсов - задание 7. Начинается ввод задания 7. Процессорное время делится между заданиями 2, 4 и 5.	2	1	3
257	Окончен ввод задания 7. Процессорное время делится между заданиями 2, 4, 5 и 7.	2	1	4
277	Завершено выполнение задания 2. По дисциплине FIFO на выполнение назначается первое задание в очереди, которому хватает ресурсов, - задание 6. Начинается ввод задания 6. Процессорное время делится между заданиями 4, 5 и 7.	2	1	3
287	Окончен ввод задания 6. Процессорное время делится между заданиями 4, 5, 6 и 7.	2	1	4
375	Завершено выполнение задания 4, ресурсы, занятые им, освобождены. По дисциплине FIFO на выполнение назначается первое задание в очереди, которому хватает ресурсов, - задание 8. Начинается ввод задания 8. Процессорное время делится между заданиями 5, 6 и 7.	2	1	3
395	Окончен ввод задания 8. Процессорное время делится между заданиями 5, 6, 7 и 8.	2	1	4
407	Завершено выполнение задания 7, ресурсы, занятые им, освобождены. По дисциплине FIFO на выполнение назначается первое задание в очереди, которому хватает ресурсов, - задание 9. Начинается ввод задания 9. Процессорное время делится между заданиями 5, 6 и 8.	1	2	3
Время	Событие	V	H	k
412	Завершено выполнение задания 5, ресурсы, занятые им освобождены. Свободных ресурсов недостаточно для назначения на выполнение следующего задания. Продолжается ввод задания 9. Процессорное время делится между заданиями 6 и 8.	4	4	2
417	Окончен ввод задания 9. Процессорное время делится между заданиями 6, 8 и 9.	4	4	3
519	Завершено выполнения задания 6, ресурсы, занятые им, освобождены. Свободных ресурсов достаточно, задание 10 назначается на выполнение. Начинается ввод задания 10. Процессорное время делится между заданиями 8 и 9.	4	4	2
529	Окончен ввод задания 10. Процессорное время делится между заданиями 8, 9 и 10.	4	4	3
592	Завершено выполнение задания 9, ресурсы, занятые им, освобождены. Процессорное время делится между заданиями 8 и 10.	7	6	2
637	Завершено выполнения задания 8, ресурсы, занятые им освобождены. Процессорное время отдаётся заданию 10.	10	10	1
663	Завершено выполнение задания 10, ресурсы, занятые им освобождены. Работа системы завершена.	16	12

Временная диаграмма мультипрограммной работы при использовании алгоритма FIFO представлена на рис. 1.3.1.

Рис. 1.3.1. Временная диаграмма планирования при использовании алгоритма FIFO

Таблица 1.4.1. Последовательность событий в системе

Время	Событие	V	H	k
4	Поступили задания 1 и 2, свободных ресурсов хватает, они назначаются на выполнение. Начинается ввод заданий 1 и 2.	7	8	0
6	Поступило задание 3, свободных ресурсов хватает, начинается ввод задания 3. Продолжается ввод заданий 1 и 2.	5	5	0
7	Поступило задание 4, свободных ресурсов хватает, начинается ввод задания 4. Продолжается ввод заданий 1, 2 и 3.	2	1	0
11	Поступили задания 5 и 6. Ни одному из них не хватает свободных ресурсов, они ставятся в очередь. Продолжается ввод заданий 1, 2, 3 и 4.	2	1	0
13	Поступило задание 7, свободных ресурсов заданию не хватает, оно ставится в очередь. Продолжается ввод заданий 1, 2, 3 и 4.	2	1	0
14	Поступило задание 8, свободных ресурсов заданию не хватает, оно ставится в очередь. Окончен ввод заданий 1 и 2. Продолжается ввод заданий 3 и 4. Процессорное время делится между заданиями 1 и 2.	2	1	2
18	Поступили задания 9 и 10, свободных ресурсов ни одному из них не хватает, они ставятся в очередь. Продолжается ввод заданий 3 и 4. Процессорное время делится между заданиями 1 и 2.	2	1	2
21	Окончен ввод задания 3. Продолжается ввод задания 4. Процессорное время делится между заданиями 1, 2 и 3.	2	1	3
27	Окончен ввод задания 4. Процессорное время делится между заданиями 1, 2, 3 и 4.	2	1	4
179	Завершено выполнение задания 3, ресурсы, занятые им, освобождены. Свободных ресурсов достаточно для назначения на выполнение следующего задания. По алгоритму SJF на выполнение назначается задание 7, имеющее минимальную трудоёмкость. Начинается ввод задания 7. Процессорное время делится между заданиями 1, 2 и 4.	2	1	3
194	Окончен ввод задания 7. Процессорное время делится между заданиями 1,2, 4 и 7.	2	1	4
Время	Событие	V	H	k
240	Завершено выполнение задания 1, ресурсы, занятые им освобождены. По дисциплине SJF на выполнение назначается задание 5, имеющее минимальную трудоёмкость. Начинается ввод задания 5. Процессорное время делится между заданиями 2, 4 и 7.	2	1	3
250	Окончен ввод задания 5. Процессорное время делится между заданиями 2, 4, 5 и 7.	2	1	4
277	Завершено выполнение задания 2. По дисциплине SJF на выполнение назначается задание 9, имеющее минимальную трудоёмкость. Начинается ввод задания 9. Процессорное время делится между заданиями 4, 5 и 7.	5	1	3
287	Окончен ввод задания 9. Процессорное время делится между заданиями 4, 5, 7 и 9.	5	1	4
347	Завершено выполнение задания 7, ресурсы, занятые им, освобождены. По дисциплине SJF на выполнение назначается задание 6, имеющее минимальную трудоёмкость. Начинается ввод задания 6. Процессорное время делится между заданиями 4, 5 и 9.	1	2	3
357	Окончен ввод задания 6. Процессорное время делится между заданиями 4, 5, 6 и 9.	1	2	4
371	Завершено выполнение задания 4, ресурсы, занятые им, освобождены. По дисциплине SJF на выполнение назначается задание с минимальной трудоёмкостью, которому хватает ресурсов, - задание 8. Начинается ввод задания 8. Процессорное время делится между заданиями 5, 6 и 9.	1	2	3
391	Окончен ввод задания 8. Процессорное время делится между заданиями 5, 6, 8 и 9.	1	2	4
476	Завершено выполнение задания 5, ресурсы, занятые им освобождены. Свободных ресурсов недостаточно для назначения на выполнение следующего задания. Процессорное время делится между заданиями 6, 8 и 9.	4	4	3
Время	Событие	V	H	k
507	Завершено выполнение задания 9, ресурсы, занятые им, освобождены. Ресурсов достаточно, на выполнение назначается задание 10. Начинается ввод задания 10. Процессорное время делится между заданиями 6 и 8.	1	4	2
517	Окончен ввод задания 10. Процессорное время делится между заданиями 6, 8 и 10.	1	4	3
587	Завершено выполнения задания 6, ресурсы, занятые им освобождены. Процессорное время делится между заданиями 8 и 10.	7	6	2
647	Завершено выполнения задания 8, ресурсы, занятые им освобождены. Процессорное время отдаётся заданию 10.	10	10	1
663	Завершено выполнение задания 10, ресурсы, занятые им освобождены. Работа системы завершена.	16	12

Рис. 1.4.1. Временная диаграмма планирования при использовании алгоритма SJF

Анализ диаграмм

Сравнение выполняется по средневзвешенному времени обращения. Средневзвешенное время обращения рассчитывается следующим образом:

где

- время завершения задания;

- время поступления задания в систему;

- действительное время выполнения задания.

Для определения средневзвешенного времени обращения построены таблицы, характеризующие выполнение заданий по FIFO и SJF (табл. 1.5.1 и 1.5.2).

Таблица 1.5.1. Характеристика выполнения заданий по FIFO

№	1	2	3	4	5	6	7	8	9	10
tп	4	4	6	7	11	11	13	14	18	18
Начало ввода	4	4	6	7	179	277	242	375	407	519
Начало счёта	14	14	21	27	189	287	257	395	417	529
tз	242	277	179	375	412	519	407	637	592	663
Время выполнения	238	273	173	368	233	242	165	262	185	144
Wi	1,00	1,00	1,00	1,00	1,72	2,10	2,39	2,38	3,10	4,48
									W =	2,02

Таблица 1.5.2. Характеристика выполнения заданий по SJF

№	1	2	3	4	5	6	7	8	9	10
tп	4	4	6	7	11	11	13	14	18	18
Начало ввода	4	4	6	7	240	347	179	371	277	507
Начало счёта	14	14	21	27	250	357	194	391	287	507
tз	240	277	179	371	476	587	347	647	507	663
Время выполнения	236	273	173	364	236	240	168	276	230	156
Wi	1,00	1,00	1,00	1,00	1,97	2,40	1,99	2,29	2,13	4,13
									W =	1,89

Для алгоритма FIFO максимальный коэффициент мультипрограммирования равен 4. Средневзвешенное время обращения W = 2,02. Для алгоритма SJF максимальный коэффициент мультипрограммирования равен 4. Средневзвешенное время обращения W = 1,89. Для обоих алгоритмов максимальный коэффициент мультипрограммирования одинаков и равен 4.

В данном случае алгоритм SJF обладает меньшим средневзвешенным временем обращения (W = 1,89) по сравнению с алгоритмом FIFO (W = 2,02). Следовательно, при данной последовательности заданий более рационально использовать дисциплину SJF.

Задание

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

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

В соответствии с вариантом рассматриваются следующие дисциплины обслуживания (ДО):

- бесприоритетная ДО - LIFO;

- приоритетная ДО - адаптивное обслуживание.

Максимальный коэффициент мультипрограммирования (k = 4) достигается на интервале [27; 179], длительность интервала 152 единицы.

Таблица 2.2.1. Параметры задач

№	1	2	3	4
ki	4	0	2	1
vi	3	6	2	3
hi	2	2	3	4
фi	60	70	40	90
Приоритет	1	2	3	4

Число циклов диспетчеризации на данном участке равно коэффициенту мультипрограммирования и равно 4. Квант цикла получается делением длительности интервала на коэффициент мультипрограммирования, квант цикла KVC = 38.

Диспетчер задач для бесприоритетной ДО LIFO

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

Для ДО LIFO выбор заявки осуществляется по принципу последним пришёл - первым вышел (по принципу стека), т. е. последняя пришедшая заявка будет обслужена первой. Построение оптимизированной таблицы задач основывается на данном принципе. Квант цикла распределяется поровну между задачами, т. е. делится на число задач. Т. о. квант времени, выделяемый каждой задаче, KVZ = 9,5.

Рис. 2.3.1. Схема диспетчера для ДО LIFO

на входе 4 задачи (I, II, III, IV) в порядке поступления (1, 2, 3, 4);

1) в соответствии с ДО LIFO формируется оптимизированная таблица задач;

2) задаче выделяется процессорное время;

3) в соответствии с ДО LIFO в выходной цепочке задачи в обратном порядке относительно поступления.

Блок-схема подпрограммы, реализующей ДО LIFO представлена на рис. 2.3.2.

Рис. 2.3.2. Блок-схема алгоритма LIFO формирования временной диаграммы диспетчеризации

1) вычисление кванта задачи;

2) формирование оптимизированной таблицы задач;

3) запись значения выделенного кванта для каждой задачи.

Программная реализация диспетчера см. приложение 2 (функция LIFO стр. 18).

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

Рис. 2.3.3. Временная диаграмма диспетчеризации для ДО LIFO

Диспетчер задач для приоритетной ДО - адаптивного обслуживания

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

В этом случае решения об абсолютном или относительном приоритетах принимаются в зависимости от обстановки. Для решения этого вопроса взвешивается - "что стоит" прерывание.

Пусть Сi - "стоимость" ожидания заявки для i-ой работы (т.е. высокоприоритетная), Сj - "стоимость" ожидания заявки для j-ой работы (низкоприоритетной), т.е. j>i (отсчет от меньшего к большему).

С - коэффициент, штраф за задержку заявки на единицу времени (целое число);

Тj - время обслуживания j-ой заявки;

Тi - время обслуживания i-ой заявки,

тогда, если ТjСi <Тi Сj , то работа (заявка) не прерывается. Если будет прервана, то будет "стоить" Тi Сj, если не будет прервана, то будет "стоить" ТjСi.

Схема адаптивного обслуживания представлена на рис. 2.4.1.



Рис.

Таблица задач с учётом стоимостей ожидания заявки:

Таблица 2.4.1. Параметры задач
№	1	2	3	4
ki	4	0	2	1
vi	3	6	2	3
hi	2	2	3	4
фi	60	70	40	90
Приоритет	1	2	3	4
C	4	3	2	1

Программная реализация диспетчера см. приложение 2 (функция Adaptive стр. 18 и далее).

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

Рис. 2.4.1. Временная диаграмма диспетчеризации для ДО адаптивного обслуживания

Приложение 1

Расчёт параметров заданий в соответствии с вариантом (выполнено в пакете Mathcad)

Рис.

Приложение 2

планирование вычислительный обслуживание

Программная реализация ДО LIFO и адаптивного обслуживания.

Программа является MFC-приложением, приведён только код, отвечающий за формирование и отрисовку диаграмм.

Формирование диаграмм

BOOL CDispatcherDoc::OnOpenDocument(LPCTSTR lpszPathName) // Открытие файла

{

if (!CDocument::OnOpenDocument(lpszPathName))

return FALSE;

if (m_pTasks) delete [] m_pTasks;

if (m_pnTaskNumsLIFO) delete [] m_pnTaskNumsLIFO;

if (m_pnTaskNumsAdapt) delete [] m_pnTaskNumsAdapt;

if (m_pdKvantsLIFO) delete [] m_pdKvantsLIFO;

if (m_pdKvantsAdapt) delete [] m_pdKvantsAdapt;

fstream file(lpszPathName, ios::in); // открытие файла с параметрами задач

file >> m_nTaskCount; // чтение числа задач

file >> m_dInterval; // чтение интервала

m_pTasks = new Task[m_nTaskCount];

for (int i=0; i<m_nTaskCount; i++) { // ввод параметров задач из файла

file >> m_pTasks[i].v; // ОП

file >> m_pTasks[i].h; // НМД

file >> m_pTasks[i].tr; // трудоёмкость

file >> m_pTasks[i].priority; // приоритет

}

FormDiagrams(); // формирование диаграмм

return TRUE;

}

void CDispatcherDoc::FormDiagrams() // Функция формирования диаграмм

{

m_dKVC = m_dInterval/m_nTaskCount;

m_pnTaskNumsLIFO = new int[m_nTaskCount];

m_pdKvantsLIFO = new double[m_nTaskCount];

LIFO(); // формирование диаграммы LIFO

Adaptive(); // формирование диаграммы адаптивного обслуживания

}

void CDispatcherDoc::LIFO() // Формирует диаграмму LIFO

{

int i;

double KVZ;

KVZ = m_dKVC/m_nTaskCount; // вычисление кванта задачи

for (i=0; i<m_nTaskCount; i++) {

m_pnTaskNumsLIFO[i] = m_nTaskCount-i; // перестановка входного потока задач в обратном порядке

m_pdKvantsLIFO[i] = KVZ; // запись квантов, выделяемых задачам

}

}

void CDispatcherDoc::Adaptive() // Формирует диаграмму для адаптивного обслуживания

{

int i;

int *C;

C = new int[m_nTaskCount]; // массив стоимостей ожидания

for (i=0; i<m_nTaskCount; i++) { // формирования массива стоимостей ожидания

C[i] = m_pTasks[m_nTaskCount-i-1].priority;

}

m_pdKvantsAdapt = new double[100];

int kv = KVDZ; // квант, выделяемый задаче

Queue InQ; // очередь поступивших задач

Queue OutQ; // здесь будет формироваться очередь квантов на процессоре

int *ar;

double *ost;

ost = new double[m_nTaskCount];

int max=0,j;

int J, I;

J=I=0;

ar= new int [m_nTaskCount]; // массив счетчиков времени

for (int k=0; k<m_nTaskCount; k++)

ar[k]=0;

for (k=0; k<m_nTaskCount; k++) // массив остатков времени для каждой задачи

ost[k]=m_dInterval/m_nTaskCount;

for (i=j=0; i<m_nTaskCount; i++,j++) { // запись в очередь эл-тов в порядке поступления

InQ.Enqueue(i);

}

int CPU=0;

CPU=InQ.Dequeue()->num; // начинаем с первой поступившей задачи

OutQ.Enqueue(CPU);

ar[CPU]+=kv;

ost[CPU] -= kv;

if (ost[CPU] >= 0) { // вычисление длины выделенного кванта

m_pdKvantsAdapt[0] = kv;

}

else {

m_pdKvantsAdapt[0] = kv + ost[CPU];

}

i=0;

while (!InQ.Empty()) // цикл пока очередь не будет пуста, т. е. все задачи не отработают

{

//Извлекаем из очереди очередную задачу

int tmp=InQ.Dequeue()->num; // в tmp находится номер поступившей задачи

//Проверка прерывания, его целесообразности

//J,I - это индексы обрабатываемых задач

//CPU - номер текущей задачи, tmp - это номер поступившей

if (tmp>CPU) {

J=tmp;

I=CPU;

}

else {

J=CPU;

I=tmp;

}

if (m_pTasks[J].tr*C[I]>=m_pTasks[I].tr*C[J]) { // TjCi >= TiCj ?

// да - прервать выполнение текущего задания

InQ.Enqueue(CPU); // текущая задача прервана и помещается в очередь

OutQ.Enqueue(tmp); // поступившая задача получает квант

CPU=tmp; // в CPU находится номер новой задачи

}

else {

//Не прерывается задача текущая - поместить обратно поступившую

InQ.Enqueue(tmp); // новая задача помещается в очередь

OutQ.Enqueue(CPU); // текущая задача получает квант

}

i++;

ar[CPU]+=kv; //наращиваем время пребывания текущей задачи на ресурсе

ost[CPU] -= kv;

if (ost[CPU] >= 0) { // вычисление длины выделенного кванта

m_pdKvantsAdapt[i] = kv;

}

else {

m_pdKvantsAdapt[i] = kv + ost[CPU];

}

if (ar[CPU]>=m_dInterval/m_nTaskCount) { // задача получила нужное кол-во времени?

// да - снять с обслуживания

CPU=InQ.Dequeue()->num; // новая задача на ресурсе

OutQ.Enqueue(CPU); // задача получает квант

i++;

ar[CPU]+=kv;

ost[CPU] -= kv;

if (ost[CPU] >= 0) { // вычисление длины выделенного кванта

m_pdKvantsAdapt[i] = kv;

}

else {

m_pdKvantsAdapt[i] = kv + ost[CPU];

}

}

}

//обработка заданий завершена

m_pnTaskNumsAdapt = new int[OutQ.cnt];

m_nNumKvantsAdapt = OutQ.cnt;

for (i=0; i<m_nNumKvantsAdapt; i++) {

m_pnTaskNumsAdapt[i] = OutQ.Dequeue()->num + 1;

}

}

void CDispatcherDoc::OnCloseDocument()

{

// TODO: Add your specialized code here and/or call the base class

if (m_pTasks) delete [] m_pTasks;

if (m_pnTaskNumsLIFO) delete [] m_pnTaskNumsLIFO;

if (m_pnTaskNumsAdapt) delete [] m_pnTaskNumsAdapt;

if (m_pdKvantsLIFO) delete [] m_pdKvantsLIFO;

if (m_pdKvantsAdapt) delete [] m_pdKvantsAdapt;

CDocument::OnCloseDocument();

}

double * CDispatcherDoc::GetKvantsLIFO()

{

return m_pdKvantsLIFO;

}

int * CDispatcherDoc::GetTaskNumsLIFO()

{

return m_pnTaskNumsLIFO;

}

int CDispatcherDoc::GetCycles()

{

return m_nTaskCount;

}

double CDispatcherDoc::GetInterval()

{

return m_dInterval;

}

double * CDispatcherDoc::GetKvantsAdapt()

{

return m_pdKvantsAdapt;

}

int * CDispatcherDoc::GetTaskNumsAdapt()

{

return m_pnTaskNumsAdapt;

}

int CDispatcherDoc::GetNumKvantsAdapt()

{

return m_nNumKvantsAdapt;

}

Отрисовка диаграмм

void CDispatcherView::OnDraw(CDC* pDC)

{

int i,j;

int widthscale=2;

int heightscale=20;

int svlen = 10;

CString str;

CString strdt("dt");

CDispatcherDoc* pDoc = GetDocument();

ASSERT_VALID(pDoc);

int n = pDoc->GetCycles();

double *kvants;

int *nums;

kvants = pDoc->GetKvantsLIFO();

nums = pDoc->GetTaskNumsLIFO();

CPoint stp(50,150);

CPoint place;

CBrush brush(m_color);

CBrush* p_oldBrush=(CBrush*)pDC->SelectObject(brush);

int endlinex;

endlinex = stp.x + (int)((double)n*n*svlen + pDoc->GetInterval())*widthscale + 20;

pDC->MoveTo(stp);

pDC->LineTo(stp.x, stp.y - (n+1)*heightscale);

// ---LIFO---

for (i=0; i<=n; i++) { // отрисовка сетки

if (i == 0) {

str.Format("sv");

pDC->TextOut(stp.x - 20, stp.y - i*heightscale - 10, str);

}

else {

str.Format("%d", i);

pDC->TextOut(stp.x - 10, stp.y - i*heightscale - 8, str);

}

pDC->MoveTo(stp.x, stp.y - i*heightscale);

pDC->LineTo(endlinex, stp.y - i*heightscale);

}

for (i=0; i<n; i++) { // отрисовка квантов

for (j=0; j<n; j++) {

pDC->TextOut(stp.x + 4, stp.y - 16, strdt);

stp.x += svlen*widthscale;

str.Format("%.2f", kvants[j]);

pDC->TextOut(stp.x - 5, stp.y + 5, str);

CSize sz((int)(kvants[j]*widthscale), (int)(nums[j]*heightscale)+1);

place = stp;

place.y-=sz.cy - 1;

CRect rt(place, sz);

pDC->Rectangle(rt);

stp.x += (int)(kvants[j]*widthscale);

}

}

kvants = pDoc->GetKvantsAdapt();

nums = pDoc->GetTaskNumsAdapt();

int m = pDoc->GetNumKvantsAdapt();

stp = CPoint(50,400);

pDC->MoveTo(stp);

pDC->LineTo(stp.x, stp.y - (n+1)*heightscale);

// ---Адаптивное обслуживание---

for (i=0; i<=n; i++) { // отрисовка сетки

if (i == 0) {

str.Format("sv");

pDC->TextOut(stp.x - 20, stp.y - i*heightscale - 10, str);

}

else {

str.Format("%d", i);

pDC->TextOut(stp.x - 10, stp.y - i*heightscale - 8, str);

}

pDC->MoveTo(stp.x, stp.y - i*heightscale);

pDC->LineTo(endlinex, stp.y - i*heightscale);

}

for (j=0; j<m; j++) { // отрисовка квантов

pDC->TextOut(stp.x + 4, stp.y - 16, strdt);

stp.x += svlen*widthscale;

str.Format("%.2f", kvants[j]);

pDC->TextOut(stp.x - 5, stp.y + 5, str);

CSize sz((int)(kvants[j]*widthscale), (int)(nums[j]*heightscale)+1);

place = stp;

place.y-=sz.cy - 1;

CRect rt(place, sz);

pDC->Rectangle(rt);

stp.x += (int)(kvants[j]*widthscale);

}

pDC->SelectStockObject(BLACK_BRUSH);

}

Размещено на Allbest.ru

...