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

 

Оглавление


Цели работы

Раздел 1. Планирование верхнего уровня управления заданиями

1.1 Общие сведения о планировании заданий

1.2 Задание и исходные данные

1.3 Выполнение работы

1.3.1 Алгоритм FIFO

1.3.2 Алгоритм SJF

1.4 Графики

Выводы

Раздел 2. Диспетчеризация

2.1 Общие сведения о диспетчеризации

2.2 Задание

2.3 Исходные условия

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

2.5 Диспетчеризация задач для ДО с динамическим приоритетом (зависимость от времени обслуживания)

2.6 Алгоритм функционирования диспетчера

2.7 Описание программы

2.8 Результаты моделирования. Временные диаграммы

Список литературы

Приложение 1. Программная реализация диспетчера

Цели работы


1.Изучение основных понятий планирования и диспетчеризации заданий.

.Изучение и исследование различных дисциплин обслуживания.

Задачи работы:

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

.Провести сравнительный анализ двух ДО.

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

Инструментарий:

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

Раздел 1.Планирование верхнего уровня управления заданиями


1.1 Общие сведения о планировании заданий


В наше время компьютеры представляют собой крайне сложные машины, и для стабильной работы им просто необходимы системы управления, а именно - операционные системы. В свою очередь, операционные системы (ОС) представляют собой целый комплекс управляющих <#"justify">Современные ОС имеют целое множество функций:

Основные функции:

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

·Загрузка программ в оперативную память и их выполнение.

·Стандартизованный доступ к периферийным устройствам (устройства ввода-вывода <#"justify">Дополнительные функции:

·Параллельное или псевдопараллельное выполнение задач (многозадачность <#"justify">Дисциплины обслуживания.

Известно большое количество правил в соответствии с которыми формируется список готовых к выполнению задач. Различают два больших класса дисциплин обслуживания - бес приоритетные и приоритетные. При бес приоритетном обслуживании выбор задачи производится в некотором заранее установленном порядке без учета их относительной важности и времени обслуживания. При реализации приоритетных дисциплин обслуживания отдельным задачам предоставляется преимущественное право попасть в состояние исполнения. Более развёрнутая классификация имеет следующий вид:

Бес приоритетные ДО:

.FIFO - "первым пришел - первым выбран на обслуживание".

Время обслуживания заявки равно ее трудоемкости.

.LIFO - "последним пришел - первым выбран на обслуживание".

Время обработки самой последней задачи аналогично FIFO.

. RAND - случайный выбор заявки из очереди.

. RR - "круговорот". Отличается от FIFO лишь временем обслуживания: каждая заявка получает определенный квант времени (одинаковый для всех).

Приоритетные ДО:

. PRT - выбор заявок на обслуживание по приоритету. Более приоритетной заявке соответствует меньшее число.

. SJF - выбор заявки на обслуживание с минимальной трудоемкостью.

. Дисциплины обслуживания со сложными динамическими приоритетами.

Оценки эффективности планирования

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

= tЗ - tП, где

- время обращения задания,З - время завершения задания,П - время поступления задания.

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

Более универсальной оценкой, позволяющей сравнивать между собой задания любой длины, является взвешенное время обращения

= (tЗ - tП) / T, где

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

Для случая M заданий можно провести оценку по среднему взвешенному времени обращения



WСР - средневзвешенное время обращения,i - взвешенное время обращения i -го задания,- количество заданий.


1.2 Задание и исходные данные


Задание.

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

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

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

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


,


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

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

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


Таблица 1. Последовательность заданий и их параметры

nXKvhTt поступления03905503051147134906244634110935397913016419079130235747674202966462234031793943260358990134903693479135045Значение используемых параметров: V=16, H=12, q=5, M=10, последовательность периодов времени (интервал поступления заданий) ti=ki .


1.3 Выполнение работы


Ниже приводятся трассировки планирования по алгоритмам FIFO и SJF и статистика по каждой задаче. Принципы работы и формулы, по которым производится вычисления взвешенных времен обращения см. выше.


1.3.1 Алгоритм FIFO


Таблица 2. Трассировка планирования по алгоритму FIFO

ВремяСобытиеV,H,KВремя: 5 Поступило задание 0: ввод задания не нужен. Задания на процессоре: 0 .V=11, H=12, K=1.Время: 6 Поступило задание 1: начинается ввод задания. Задания на процессоре: 0 .V=8, H=8, K=1.Время: 9 Поступило задание 2: начинается ввод задания. Задания на процессоре: 0 .V=4, H=7, K=1.Время: 13 Завершён ввод задания 2. Задания на процессоре: 0 2 .V=4, H=7, K=2.Время: 16 Поступило задание 3: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 2 .V=4, H=7, K=2.Время: 23 Поступило задание 4: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 2 .V=4, H=7, K=2.Время: 25 Завершён ввод задания 1. Задания на процессоре: 0 1 2 .V=4, H=7, K=3.Время: 29 Поступило задание 5: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 1 2 .V=4, H=7, K=3.Время: 31 Поступило задание 6: начинается ввод задания. Задания на процессоре: 0 1 2 .V=2, H=4, K=3.Время: 35 Поступило задание 7: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 1 2 .V=2, H=4, K=3.Время: 36 Поступило задание 8: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 1 2 .V=2, H=4, K=3.Время: 39 Завершено задание 2 и его ресурсы освобождены. Задания на процессоре: 0 1 2 .V=6, H=5, K=3.Время: 45 Завершён ввод задания 6. Поступило задание 9: начинается ввод задания. Задания на процессоре: 0 1 6 .V=5, H=2, K=3.Время: 59 Завершён ввод задания 9. Задания на процессоре: 0 1 6 9 .V=5, H=2, K=4.Время: 75 Завершено задание 0 и его ресурсы освобождены. Из очереди выбирается задание 3: начинается ввод задания. Задания на процессоре: 0 1 6 9 .V=1, H=1, K=4.Время: 80 Завершён ввод задания 3. Задания на процессоре: 1 3 6 9 .V=1, H=1, K=4.Время: 200 Завершено задание 3 и его ресурсы освобождены. Из очереди выбирается задание 4: начинается ввод задания. Задания на процессоре: 1 3 6 9 .V=1, H=1, K=4.Время: 201 Завершено задание 6 и его ресурсы освобождены. Задания на процессоре: 1 6 9 .V=3, H=4, K=3.Время: 205 Завершён ввод задания 4. Задания на процессоре: 1 4 9 .V=3, H=4, K=3.Время: 246 Завершено задание 9 и его ресурсы освобождены. Задания на процессоре: 1 4 9 .V=4, H=7, K=3.Время: 280 Завершено задание 4 и его ресурсы освобождены. Из очереди выбирается задание 5: начинается ввод задания. Задания на процессоре: 1 4 .V=6, H=4, K=2.Время: 281 Из очереди выбирается задание 7: начинается ввод задания. Задания на процессоре: 1 .V=3, H=2, K=1.Время: 291 Завершено задание 1 и его ресурсы освобождены. Завершён ввод задания 7. Из очереди выбирается задание 8: начинается ввод задания. Задания на процессоре: 1 7 .V=3, H=2, K=2.Время: 300 Завершён ввод задания 5. Задания на процессоре: 5 7 .V=3, H=2, K=2.Время: 311 Завершён ввод задания 8. Задания на процессоре: 5 7 8 .V=3, H=2, K=3.Время: 355 Завершено задание 5 и его ресурсы освобождены. Задания на процессоре: 5 7 8 .V=10, H=6, K=3.Время: 420 Завершено задание 7 и его ресурсы освобождены. Задания на процессоре: 7 8 .V=13, H=8, K=2.Время: 464 Завершено задание 8 и его ресурсы освобождены. Задания на процессоре: 8 .V=16, H=12, K=1.

Таблица 3. Сводная таблица для алгоритма FIFO

Заданиеt поступленияt назначения на выполнениеt начала счетаt завершенияW0555752.366667166252912.60000029913392.06666731676802005.2857144232012052807.3714295292813003558.17500063131452013.1090917352822914205.5142868362923114643.90000094545592463.107692

Средневзвешенное время обращения W = 4.349655

Максимальный коэффициент мультипрограммирования = 4


1.3.2 Алгоритм SJF


Таблица 4. Трассировка планирования по алгоритму SJF

ВремяСобытиеV,H,KВремя: 5 Поступило задание 0: ввод задания не нужен. Задания на процессоре: 0 .V=11, H=12, K=1.Время: 6 Поступило задание 1: начинается ввод задания. Задания на процессоре: 0 .V=8, H=8, K=1.Время: 9 Поступило задание 2: начинается ввод задания. Задания на процессоре: 0 .V=4, H=7, K=1.Время: 13 Завершён ввод задания 2. Задания на процессоре: 0 2 .V=4, H=7, K=2.Время: 16 Поступило задание 3: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 2 .V=4, H=7, K=2.Время: 23 Поступило задание 4: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 2 .V=4, H=7, K=2.Время: 25 Завершён ввод задания 1. Задания на процессоре: 0 1 2 .V=4, H=7, K=3.Время: 29 Поступило задание 5: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 1 2 .V=4, H=7, K=3.Время: 31 Поступило задание 6: начинается ввод задания. Задания на процессоре: 0 1 2 .V=2, H=4, K=3.Время: 35 Поступило задание 7: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 1 2 .V=2, H=4, K=3.Время: 36 Поступило задание 8: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 1 2 .V=2, H=4, K=3.Время: 39 Завершено задание 2 и его ресурсы освобождены. Задания на процессоре: 0 1 2 .V=6, H=5, K=3.Время: 45 Завершён ввод задания 6. Поступило задание 9: начинается ввод задания. Задания на процессоре: 0 1 6 .V=5, H=2, K=3.Время: 59 Завершён ввод задания 9. Задания на процессоре: 0 1 6 9 .V=5, H=2, K=4.Время: 75 Завершено задание 0 и его ресурсы освобождены. Задания на процессоре: 0 1 6 9 .V=10, H=2, K=4.Время: 170 Завершено задание 6 и его ресурсы освобождены. Из очереди выбирается задание 5: начинается ввод задания. Задания на процессоре: 1 6 9 .V=5, H=1, K=3.Время: 190 Завершён ввод задания 5. Задания на процессоре: 1 5 9 .V=5, H=1, K=3.Время: 207 Завершено задание 9 и его ресурсы освобождены. Задания на процессоре: 1 5 9 .V=6, H=4, K=3.Время: 237 Завершено задание 5 и его ресурсы освобождены. Из очереди выбирается задание 3: начинается ввод задания. Задания на процессоре: 1 5 .V=4, H=7, K=2.Время: 242 Завершён ввод задания 3. Задания на процессоре: 1 3 .V=4, H=7, K=2.Время: 258 Завершено задание 1 и его ресурсы освобождены. Задания на процессоре: 1 3 .V=7, H=11, K=2.Время: 281 Завершено задание 3 и его ресурсы освобождены. Из очереди выбирается задание 4: начинается ввод задания. Задания на процессоре: 3 .V=7, H=11, K=1.Время: 282 Из очереди выбирается задание 7: начинается ввод задания. Процессор простаивает.V=4, H=9, K=0.Время: 283 Из очереди выбирается задание 8: начинается ввод задания. Процессор простаивает.V=1, H=5, K=0.Время: 286 Завершён ввод задания 4. Задания на процессоре: 4 .V=1, H=5, K=1.Время: 292 Завершён ввод задания 7. Задания на процессоре: 4 7 .V=1, H=5, K=2.Время: 303 Завершён ввод задания 8. Задания на процессоре: 4 7 8 .V=1, H=5, K=3.Время: 359 Завершено задание 4 и его ресурсы освобождены. Задания на процессоре: 4 7 8 .V=10, H=6, K=3.Время: 432 Завершено задание 7 и его ресурсы освобождены. Задания на процессоре: 7 8 .V=13, H=8, K=2.Время: 468 Завершено задание 8 и его ресурсы освобождены. Задания на процессоре: 8 .V=16, H=12, K=1.

Таблица 5. Сводная таблица для алгоритма SJF

Заданиеt поступленияt назначения на выполнениеt начала счетаt завершенияW0555752.366667166252582.30000029913392.0666673162382422817.6000004232822863599.6285715291711902375.22500063131451702.5454557352832924325.6857148362843034683.93636494545592072.507692

Средневзвешенное время обращения W= 4.386213

Максимальный коэффициент мультипрограммирования равен 4


1.4 Графики


Графики выполнения заданий на процессоре:


Рис. 2. График исполнения задач на процессоре для ДО FIFO


Рис. 3. График исполнения задач на процессоре для ДО SJF

Выводы


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

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

Раздел 2. Диспетчеризация


2.1 Общие сведения о диспетчеризации


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

Таким образом, цели диспетчирования задач следующие:

распределение центрального процессора в динамике в соответствии

с критериями;

эффективная отработка алгоритмов управления задачами.

сбалансированное использование ресурсов.

баланс между временем ответа и коэффициентом использования ресурсов.

Итак: диспетчер - это программа, которая выбирает задачи (процессы) из "очереди на выполнение", переводит их в активное состояние и передает их на обработку центральному процессору.


2.2 Задание


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

Диспетчер использует метод разделения времени в сочетании с приоритетами. ДО - следующие:

бес приоритетные ДО (БП) - FB- обратная связь;

приоритетные ДО (П) - обслуживание с динамическим приоритетом (зависимость от времени обслуживания - tобсл).

Матрица работ из раздела 1 (правило FIFO):


Таблица №4 Исходные данные

NTtpPr030531203082402711340295470107755011356701749750183108903271993037913

2.3 Исходные условия


Вариант выбирается согласно последним двум цифрам зачетной книжки (09).

Соответственно варианту выбираются дисциплины обслуживания, то есть:

  • бес приоритетная: FB - Feed Back (обратная связь) - многоуровневый циклический алгоритм
  • приоритетная: ДО динамическим приоритетом (зависимость от времени обслуживания - tобсл..);

планирование алгоритм диспетчеризация моделирование

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


На рисунке 4 представлена схема циклической ДО (FB)


Рис. 4. Схема циклической ДО (FB)


n=1 - это первая очередь, в нее поступает входной поток заявок. Из нее заявка поступает на ресурс и/или полностью обслуживается или снова поступает в очередь, но с номером на 1 больше. Поток заявок поступает в самую приоритетную очередь n=1. Заявка получает квант и переходит в очередь n+1. Заявка в i-ой очереди обслуживается, если пусты все остальные очереди. В очереди N заявки обслуживаются до завершения (в очереди N принцип FIFO + RR).

Рис.5. Алгоритм ДО FB.

2.5 Диспетчеризация задач для ДО с динамическим приоритетом (зависимость от времени обслуживания)


Приоритет изменяется в период выполнения задания (tобсл.). На рисунке представлена временная диаграмма изменения приоритета от времени.


Рис.6. Временная диаграмма изменения приоритета от времени.


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


Pi(t) = ai*tожид. + bi*tвыполн., где Pi(t) - приоритет i- ой работы.


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

1.процесс завершен или произошла ошибка;

2.процесс перешел в состояние ожидания;

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

.в очереди появился процесс с большим приоритетом

Достоинства системы с динамическим приоритетом:

·возможность настраиваться при изменении характеристик входного потока на эффективное обслуживание;

·дисциплина основана на реальных динамических характеристиках заявок.

·Учитывает приоритетность задач

·Уменьшает возможность недобросовестного использования механизмов приоритетов

Недостатки:

·Возможность бесконечного откладывания низкоприоритетных процессов

·Сложная организация, так как необходим пересчет приоритетов

Рис.7. Блок-схема алгоритма ДО с динамическим приоритетом.


.6 Алгоритм функционирования диспетчера


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

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


Рис. 8. Блок-схема алгоритма диспетчера.


2.7 Описание программы


Программа Disp позволяет произвести моделирование c помощью одного из двух алгоритмов: FB или обслуживание с динамическим приоритетом (зависимость от времени обслуживания tобсл).

Запуск программы осуществляется по команде Disp.exe Внешний вид программы представлен на рисунке 9.

В меню программы можно задать параметры моделирования.

SV - время работы супервизора;

PROC - продолжительность кванта времени в течении которого обрабатывается задание;

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

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


Рис.9. Внешний вид программы


.8 Результаты моделирования. Временные диаграммы


Рис.10. Временная диаграмма результатов моделирования алгоритма FB

Рис.11. Временная диаграмма результатов моделирования алгоритма с динамическим приоритетом


Заключение


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

Были построены временные диаграммы мультипрограммной работы каждого, из указанных в задании алгоритмов. И проведено сравнение двух случаев по средневзвешенному времени обращения. По результатам построения временных диаграмм ДО SJF (средневзвешенное время 4.04единиц) оказалась немного более эффективной, чем ДО FIFO (4.70единиц).

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

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

Список литературы


1.Л.А. Коршикова. Операционные системы как системы управления вычислительными ресурсами: Учеб. пособие. - Новосибирск.: НГТУ, 2007. - 52с.: ил.

2.Э. Таненбаум. Современные операционные системы. 2-е изд. - СПб.: Питер, 2007. - 1038 с.: ил.

Приложение 1. Программная реализация диспетчера


void CKR_OSDlg::FB()

{

//собственно сам алгоритм

int countT=0;//счетчик в списке aMCPU

int cTr=0;tT=0;tPT=0;c=0;nIndex=0;s1[10];s2[10]=": ";st;

//oDop.SV=atoi(m_SV);

//oDop.PROC=atoi(m_PROC);OutFile2("trace1.txt",CFile::modeCreate | CFile::modeWrite);s[80];len=0;x=true;(true)

{.SortTaskTime(oDop.cTask);=1;

tT=oDop.T-cTr;//от чего

oDop.T+=oDop.SV;//до чего

if (oDop.T==115)

{++;-;

}.Format("%d: Супервизор старт ",tT+cTr);//oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st); (int n=1;n<oDop.cTask;n++) // проверяем на конец моделирования

if (oDop.aTask[n].b) c++;(c==oDop.cTask)

{.Format("%d: Супервизор финиш ",oDop.T);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);.Format("Конец моделирования");.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);++;

return;

}

countT=1;

for (int i=1;i<oDop.cTask;i++)//формируем список только что поступивших задач

if (oDop.aTask[i].Time<oDop.T)

{.tTask[i]=oDop.aTask[i];(oDop.aTask[i].Time>=tT+cTr && !oDop.aTask[i].b)

{.aTask[i].Queue=1; //очередь.tTask[i].Queue=1;.Format("%d: %d задача поступила ",oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);

}++;

};.Format("%d: Супервизор финиш ",oDop.T);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);.SortQueue(countT-1);//? сортитуем список по приоритетам

while (true) // выбираем из списка ту, которая получит свой квант

{(countT==1) break;(!oDop.tTask[countT-1].b)

{

if (oDop.tTask[countT-1].Trud<=oDop.PROC) //если осталось у задачи трудоемкость меньше,//чем 5 квантов

{

cTr=oDop.tTask[countT-1].Trud; //то продвигаем время на труд этой задачи

nIndex=oDop.Index(countT-1);.aTask[nIndex].Trud=0;.aTask[nIndex].b=true;(int j=1,in=0;j<countT-1;j++)

{=oDop.Index(j);(!oDop.aTask[in].b)

{

//oDop.aTask[in].Function(cTr);

}

}.Format("%d: %d задача начала выполнение ",oDop.T,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st); (int i=1;i<oDop.cTask;i++)//формируем список только что поступивших задач

if (oDop.aTask[i].Time<oDop.T+cTr)

{(oDop.aTask[i].Time>=oDop.T && !oDop.aTask[i].b)

{.aTask[i].Queue=1; //очередь

//oDop.tTask[i].Queue=1;.Format("%d: %d задача поступила ",oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);

}

}.Format("%d: у задачи %d закончился квант времени ",oDop.T+cTr,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);.Format("задача %d выполнена ",oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);(oDop.cTask);;

}

{=oDop.PROC;//иначеипродвигаем время на 5 квантов

nIndex=oDop.Index(countT-1);

oDop.aTask[nIndex].Trud-=oDop.PROC;// обнуляем трудоемкость

oDop.aTask[nIndex].Prior--;.aTask[nIndex].Queue++; //очередь(int j=1,in=0;j<countT-1;j++)

{=oDop.Index(j);(!oDop.aTask[in].b)

{

//oDop.aTask[in].Function(cTr);

}

}.Format("%d: %d задача начала выполнение ",oDop.T,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st); (int i=1;i<oDop.cTask;i++)//формируем список только что поступивших задач

if (oDop.aTask[i].Time<oDop.T+cTr)

{(oDop.aTask[i].Time>=oDop.T && !oDop.aTask[i].b)

{.aTask[i].Queue=1; //очередь.Format("%d: %d задача поступила ",oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);

}

}.Format("%d: у задачи %d закончился квант времени ",oDop.T+cTr,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceF.InsertString(-1,st);(oDop.cTask);;

}

}countT--; //следущая в списке

}

oDop.T+=cTr; //продвигаем модельное время

}

}CKR_OSDlg::Dinam()

{

//собственно сам алгоритм с динамическим приоритетомcountT=0;//счетчик в списке aMCPU

int cTr=0;tT=0;tPT=0;c=0;nIndex=0;s1[10];s2[10]=": ";st;

//oDop.SV=atoi(m_SV);

//oDop.PROC=atoi(m_PROC);OutFile2("trace1.txt",CFile::modeCreate | CFile::modeWrite);s[80];len=0;x=true;(true)

{.SortTaskTime(oDop.cTask);

c=1;=oDop.T-cTr;//от чего.T+=oDop.SV;//до чего

if (oDop.T==145)

{++;-;

}.Format("%d: Супервизор старт ",tT+cTr);//oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);

for (int n=1;n<oDop.cTask;n++) // проверяем на конец моделирования

if (oDop.aTask[n].b) c++;(c==oDop.cTask)

{.Format("%d: Супервизор финиш ",oDop.T);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);.Format("Конец моделирования");.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);

cc++;;

}=1;(int i=1;i<oDop.cTask;i++)//формируем список только что поступивших задач

if (oDop.aTask[i].Time<oDop.T)

{.tTask[i]=oDop.aTask[i];(oDop.aTask[i].Time>=tT+cTr && !oDop.aTask[i].b)

{.Format("%d: %d задача поступила ",oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);

}++;

};.Format("%d: Супервизор финиш ",oDop.T);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);

oDop.SortPrior(countT-1);//? сортитуем список по приоритетам(true) // выбираем из списка ту, которая получит свой квант

{(countT==1) break;(!oDop.tTask[countT-1].b)

{(oDop.tTask[countT-1].Trud<=oDop.PROC) //если осталось у задачи трудоемкость меньше,//чем 5 квантов

{=oDop.tTask[countT-1].Trud; //то продвигаем время на труд этой задачи

nIndex=oDop.Index(countT-1);.aTask[nIndex].Trud=0;.aTask[nIndex].b=true;(int j=1,in=0;j<countT-1;j++)

{=oDop.Index(j);(!oDop.aTask[in].b)

{

//oDop.aTask[in].Function(cTr);

}

}.Format("%d: %d задача начала выполнение ",oDop.T,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);

for (int i=1;i<oDop.cTask;i++)//формируем список только что поступивших задач

if (oDop.aTask[i].Time<oDop.T+cTr)

{(oDop.aTask[i].Time>=oDop.T && !oDop.aTask[i].b)

{.Format("%d: %d задача поступила ",oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);

}

}.Format("%d: у задачи %d закончился квант времени ",oDop.T+cTr,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);.Format("задача %d выполнена ",oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);(oDop.cTask);;

}

{

cTr=oDop.PROC;//иначеипродвигаем время на 5 квантов=oDop.Index(countT-1);.aTask[nIndex].Trud-=oDop.PROC;// обнуляем трудоемкость

oDop.aTask[nIndex].Prior--;(int j=1,in=0;j<countT-1;j++)

{=oDop.Index(j);(!oDop.aTask[in].b)

{

//oDop.aTask[in].Function(cTr);

}

}.Format("%d: %d задача начала выполнение ",oDop.T,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);

for (int i=1;i<oDop.cTask;i++)//формируем список только что поступивших задач

if (oDop.aTask[i].Time<oDop.T+cTr)

{(oDop.aTask[i].Time>=oDop.T && !oDop.aTask[i].b)

{.Format("%d: %d задача поступила ",oDop.aTask[i].Time,oDop.aTask[i].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);

}

}.Format("%d: у задачи %d закончился квант времени ",oDop.T+cTr,oDop.aTask[nIndex].Name);.Write(st,st.GetLength());.Write("\n",1);_TraceD.InsertString(-1,st);(oDop.cTask);;

}

}countT--; //следущая в списке

}.T+=cTr; //продвигаем модельное время

}

}


Оглавление Цели работы Раздел 1. Планирование верхнего уровня управления заданиями 1.1 Общие сведения о планировании заданий 1.2 Задание и исход

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ