Министерство Высшего и Профессионального Образования РФ
НГТУ
Кафедра ВТ
СПО
Методические указания к выполнению лабораторной работы №2
Диспетчеризация задач
Новосибирск 2003
Содержание:
Содержание:................................................................................................................................... 2
Введение........................................................................................................................................ 3
1. Общие сведения о диспетчеризации................................................................................... 3
2. Общие сведения о программной модели "Диспетчеризация задач"................................ 3
2.1. Описание модели........................................................................................................... 4
2.2. Оценка качества обслуживания очереди задач........................................................... 5
Описание работы программы...................................................................................................... 8
1. Сводная таблица экспериментальных данных............................................................ 10
Выводы:........................................................................................................................................ 16
Список литературы:.................................................................................................................... 17
Введение
Планирование среднего уровня управления процессами
(диспетчеризация задач)
Цель работы.
Изучение и исследование некоторых алгоритмов и способов
планирования задач (диспетчеризация) в мультипрограммной ЭВМ.
1. Общие сведения о диспетчеризации.
Планирование распределения процессора производится на нескольких уровнях. Один из них - средний уровень планирования -диспетчеризация. На этом уровне диспетчер задач (планировщик процессов) выбирает одну задачу из числа готовых к выполнению и
предоставляет ей процессор. Каждая задача занимает процессор относительно малое время (как правило, недостаточное для выполнения задачи), затем диспетчирования повторяется, процессор выделяется другой задаче. Диспетчер принимает текущие решения в динамике сложившейся конкретной обстановки.
Таким образом, цели диспетчирования задач следующие:
- распределение центрального процессора в динамике в соответствии
с критериями;
- эффективная отработка алгоритмов управления задачами.
- сбалансированное использование ресурсов.
- баланс между временем ответа и коэффициентом использования ресурсов.
Итак: диспетчер - это программа, которая выбирает задачи (процессы)
из "очереди на выполнение", переводит их в активное состояние и
передает их на обработку центральному процессору.
2. Общие сведения о программной модели "Диспетчеризация задач".
Для изучения некоторых наиболее распространенных правил обслуживания
задач, стоящих в "очереди на выполнение", студентам предлагается модель
простейшей ЭВМ.
Структурная схема, поясняющая принцип работы этой ЭВМ, представлена на
рис.1.
 |
|
 | |
 | |
| |
 | |
Рис.1. Структурная схема модели
2.1. Описание модели.
Выделено три основных блока ЭВМ:
- генератор ( GEN );
- супервизор ( SV );
- центральный процессор ( CPU ).
Взаимодействие этих блоков и обеспечивает обработку задач (процессов).
Замечание: в модели ведется отсчет времени относительно модельного времени
главных часов ( TM ). Наряду с ТМ вводятся понятия:
TSV - время работы SV;
TGEN - время работы GEN;
TCPU - время работы CPU над проблемной задачей (квант времени);
TTGEN - квант времени, по истечении которого блок генератора
должен вступить в работу;
OST - остаток от кванта времени, отпущенного процессору
для работы над задачей. ( ВРемя ДОРаботки)
Блоком GEN формируются основные параметры задачи: номер задачи,
приоритет, трудоемкость, время поступления в систему следующей
задачи. Эти параметры формируются, исходя из максимально заданных
значений входных величин генератора случайных чисел. Блок
генератора вступает в работу по истечении TTGEN, при этом текущая
работа прерывается и возобновляется после постановки вновь
поступившей задачи в очередь на обработку.
Блок SV выполняет роль диспетчера задач.
Порядок работы модели.
1. Супервизор ожидает поступления в систему хотя бы одной задачи.
2. После поступления задачи в систему ей выделяется квант
процессорного времени. По истечении которого вновь будет запущен
супервизор.
3. При очередном запуске супервизора происходит вызов планировщика
заданий.
4. Пункты 2 и 3 повторяются до тех пор, пока задача не отработает
отведенное ей время целиком.
5. Через некоторые промежутки времени запускается генератор новой
задачи. При этом происходит запоминание текущего состояния
системы. Генерация новой задачи. Вызов планировщика заданий.
Возврат в запомненное состояние.
6. Весь процесс повторяется пока не будут выполнены все задачи.
2.2. Оценка качества обслуживания очереди задач.
Выбор заявок из очереди производится по правилу, которое называется
дисциплиной обслуживания. Обслуживание заявок в общем случае носит
стохастический характер, т. е. время обслуживания t обсл.(TR) различное.
На основе системы массового обслуживания время пребывания задачи
в системе определяется как составляющая времени ожидания и времени
обслуживания (трудоемкости).
Предъявляются следующие требования:
а) для всех задач время ожидания (tож - TO) должно быть равномерным;
б) трудоемкость (TR) дисциплины обслуживания должна быть минимальной.
Модель обеспечивает следующие дисциплины диспетчеризации задач.
1.FIFO - "первым пришел - первым выбран на обслуживание".
Время обслуживания заявки равно ее трудоемкости.
2.LIFO - "последним пришел - первым выбран на обслуживание".
Время обработки самой последней задачи аналогично FIFO.
3.RR - "круговорот". Отличается от FIFO лишь временем обслуживания:
каждая заявка получает определенный квант времени (одинаковый
для всех).
4.PRT - выбор заявок на обслуживание по приоритету. Более приоритетной
заявке соответствует меньшее число.
5.RAND - случайный выбор заявки из очереди.
6.SJF - выбор заявки на обслуживание с минимальной трудоемкостью.
О качестве дисциплины можно судить по среднему времени обслуживания
(STO).
Из теории очередей известна зависимость TO от TR (времени ожидания
от времени обслуживания задачи). Она представлена на рис.2.
 | |
|
Рис.2.График качества обслуживания
w - среднее время ожидания (STO);
V - средняя длительность заявок.
Следующим параметром качества обслуживания (кроме STO, TR, TO) является
параметр загрузки процессора ZCP. Он зависит от дисциплин диспетчеризации
и выражается в процентном отношении:
ZCP=100*(STR/TM) , где
STR - суммарная трудоемкость всех задач, обслуженных мультипрограммной ЭВМ;
TM - модельное время. (имеется ввиду время выполнения всех
задач. Т начала 1ой задачи - Т окончания последней. )
Описание работы программы
Программа GFDispatch является полноценным 32х-разрядным многооконным(MDI) приложением, позволяющим произвести моделирование процесса диспетчеризации с помощью одного из следующих алгоритмов: FIFO (First In First Out), LIFO (Last In First Out), SJF (Short Job First), PRT (Priority), RR (Round Robin) и RND (Randomize).
Запуск программы осуществляется по команде GFDispatch. exe.
После запуска можно увидеть главное окно программы(Рис. 1)
Рис. 1. Главное окно программы
управление процессом моделирования ведется с помощью меню на рисунке 2,
Рис. 2. Диалог параметров моделирования
Здесь можно задать параметры моделирования, такие как:
Tasks – количество задач
TSV – время работы супервизора
KV – продолжительность кванта времени выделяемого задаче
MIP – максимальный интервал между поступлениями задач
MTR – максимальная трудоемкость задачи
MPRT – максимальный приоритет задачи
Данные параметры можно задать как, с помощью клавиатуры, в соответствующих окнах, так и с помощью “Бегунков”
Регенерировать? - пометив эту галочку, можно каждый раз проверять дисциплину обслуживания с помощью случайно сгенерированных параметров задач, если же флажок не помечен, то появляется возможность тестировать несколько дисциплин, пользуясь идентичным набором задач.
Запуск процесса моделирования можно осуществить с помощью нажатия кнопки “Моделирование”
По нажатию кнопки “Отчет” будет открыт текстовый файл с результатами работы программы.
При выборе пункта меню File->New создается новое окно программы GFDispatch, в котором можно промоделировать другую дисциплину обслуживания на тех же самых данных(при не установленной галочке “Регенерировать?”) и таким образом сравнить две или более дисциплин обслуживания.
Граничные значения параметров программы:
TSV - (1..100) Время работы супервизора.
MIP - (1..100) Максимальный интервал между поступлениями задач в систему.
(интервал между срабатываниями генератора.)
MTR - (1..100) Максимальная трудоемкость задач поступающих в систему.
MPRT - (1..100) Максимальный приоритет задач.
KV - (1..100) Квант времени, выделяемый задаче на обработку.
Tasks(1..10) Количество задач, обрабатываемых диспетчером.
Исследование зависимости загрузки процессора от различных параметров
1. Сводная таблица экспериментальных данных
TSV | MIP | MTR | Tasks | KV | MPRT | FIFO | SJF | LIFO | RR | RND | PRT |
10 | 10 | 20 | 5 | 10 | 20 | 38 | 40 | 32 | 29 | 30 | 31 |
20 | 23 | 23 | 18 | 18 | 17 | 18 | |||||
30 | 16 | 20 | 13 | 13 | 12 | 12 | |||||
40 | 14 | 13 | 9 | 8 | 9 | 10 | |||||
50 | 12 | 11 | 8 | 8 | 8 | 9 | |||||
10 | 20 | 20 | 5 | 10 | 20 | 36 | 33 | 32 | 29 | 30 | 31 |
30 | 30 | 33 | 32 | 30 | 31 | 30 | |||||
40 | 31 | 35 | 33 | 31 | 29 | 33 | |||||
50 | 27 | 31 | 31 | 31 | 32 | 31 | |||||
10 | 10 10 10 10 | 40 | 5 | 10 | 20 | 44 | 43 | 23 | 25 | 26 | 25 |
60 | 45 | 44 | 32 | 29 | 30 | 31 | |||||
80 | 43 | 44 | 32 | 31 | 31 | 32 | |||||
100 | 47 | 47 | 30 | 33 | 32 | 32 | |||||
10 | 10 10 10 10 | 20 | 6 | 10 | 20 | 41 | 38 | 32 | 32 | 33 | 33 |
7 | 39 | 38 | 32 | 32 | 33 | 33 | |||||
8 | 37 | 41 | 32 | 29 | 30 | 31 | |||||
9 | 38 | 37 | 31 | 31 | 30 | 32 | |||||
10 | 10 | 20 | 5 | 20 | 20 | 49 | 50 | 30 | 31 | 29 | 33 |
30 | 46 | 44 | 31 | 30 | 28 | 32 | |||||
40 | 46 | 48 | 31 | 31 | 28 | 31 | |||||
50 | 46 | 46 | 32 | 30 | 29 | 32 |
Таблица 1. Дисциплины FIFO, SRT, LIFO, RR, RND, PRT
2. Графики, построенные на основе данных из таблицы1.
Выводы:
Зависимость %CPU от TSV.Прослеживается очень сильная корреляция этих параметров – при изменении параметра TSV от 10 до 50 загрузка процессора падает примерно в 5 раз, т. е. от 40-38% до 8-12%. Это объясняется тем, что общее время выполнения задач увеличивается из-за более длительных прерываний супервизора.
Графики получаются довольно интересными – сначала идет линейная часть, где загрузка процессора довольно стабильна, а затем, после определенной точки, загрузка процессора резко падает для всех дисциплин. Это связано с тем, что при увеличении параметра MIP (максимальный интервал между поступлениями задач) начинают появляться «простои процессора», т. е. процессор обработал все текущие задачи и очередь задач пуста, загрузка падает, процессор ожидает поступления новых задач.
Зависимость %CPU от MTR.Увеличение параметра MTR в целом улучшает загрузку процессора, хотя и неравномерно (исключение составила дисциплина FIFO, где загрузка процессора незначительно упала). Корреляция %CPU от MTR довольно незначительна, разница граничных значений загрузки процессора в этом исследовании составляет примерно 3-4 %, что, в общем-то, немного.
Зависимость %CPU от MPRT.Прослеживать данную зависимость не совсем корректно, так как свой анализ на основе приоритета задачи строит только одна дисциплина обслуживания – PRT. Для остальных дисциплин обслуживания данная зависимость не прослеживается, колебания объясняются тем, что наборы задач генерируются с помощью датчика псевдослучайных чисел. Для дисциплины PRT сначала наблюдается скачок загруженности процессора, а затем график приобретает вид прямой.
Зависимость %CPU от Tasks.При изменении параметра Tasks (количество задач) загрузка процессора изменяется незначительно, более выигрышно выглядит дисциплина обслуживания FIFO, которая является самой простой и при увеличении количества задач время поиска для выборки новой задачи не увеличивается, тогда как для других дисциплин алгоритмы выборки следующей задачи из очереди задач требуют больше времени.
Зависимость %CPU от KV.Здесь прослеживается сильная зависимость, наглядно показанная на последних трех графиках. При увеличении кванта времени, выделяемого на обработку задачи, сначала идет резкий подъем загруженности процессора, это объясняется тем, что задача обрабатывается за меньшее число прерываний супервизора, затем наступает область насыщения, появление которой объясняется тем, что квант времени превышает максимальную трудоемкость и любая задача выполняется за один такт супервизора.
