 |
Пример использования стратегии HPF.
|
|
|
|
Выбор самого короткого задания (shortest job first - SJF).
Время выполнения – характеристика, на которой основан приоритет. Приоритет обратно пропорционален ожидаемому времени обработки.
Этот вариант
удобен для “коротких” процессов.
1) Класс подходов, использующих линейно возрастающий приоритет.
Процесс при входе в систему получает некий приоритет, который возрастает с коэффициентом A во время ожидания в очереди готовых процессов, и с коэффициентом B во время выполнения.
Из выбора A и В - разные правила планирования:
- Если 0<A<=B обслуживание очереди по дисциплине FIFO
- Если 0>B>=A обслуживание очереди по дисциплине LIFO
Нелинейные функции изменения приоритета
Например, приоритет убывает по линейному закону с течением времени. Когда достигается некое максимальное время, приоритет скачком возрастает до некоторой большой величины. Это благоприятствует коротким процессам, и при этом соблюдается условие, что ни одному процессу не придется ждать обслуживания слишком долго.
Разновидности круговорота.
Простой круговорот (RR – round robin) не использует никакой статистической или динамической информации о приоритетах. (см. рисунок выше)
При круговороте со смещением каждому процессу соответствует своя длина кванта, пропорциональная его приоритету.
«Эгоистический» круговорот. Если параметры A и B: 0<=B<A.
Процесс, войдя в систему ждет пока его приоритет не достигнет приоритета работающих процессов, а далее выполняется в круговороте.
Приоритет выполняемых процессов увеличивается с коэффициентом B<A, следовательно, ожидающие процессы их догонят.
При B=0 «эгоистический» круговорот практически сводится к простому.
|
|
|
Очереди с обратной связью (feedback – FB).
Используется N очередей. Новый процесс ставится в первую очередь, после получения кванта он переносится во вторую и так далее. Процессор обслуживает непустую очередь с наименьшим номером.
В FB поступивший процесс неявно получает наивысший приоритет и выполняется подряд в течении нескольких квантов до прихода следующего, но не более чем успел проработать предыдущий.
«-» Работа с несколькими очередями – издержки.
«+» Удобны для коротких заданий: не требуется предварительная информация о времени выполнения процессов.
Смешанные алгоритмы планирования
На практике концепции квантования и приоритетов часто используются совместно.
К примеру, в основе – концепция квантования, а определение кванта и/или дисциплина обслуживания очередей базируется на приоритетах.
Планирование в системах реального времени
Системы реального времени являются специализированными системами в которых все функции планирования ориентированы на обработку некоторых событий за время, не превосходящее некоторого предельного значение.
Системы реального времени бывают “Жесткие” и ”мягкие ”.
В первом случае время завершения выполнения каждого из процессов должно быть гарантировано для всех сценариев функционирования системы.
Это может быть обеспечено за счет:
- полного тестирования всевозможных сценариев
- построения статического расписания
- выбора математически просчитанного алгоритма динамического планирования
Периодические запросы – все моменты запроса периодического процесса можно определить заранее.
Пусть {Ti} набор периодических процессов с периодами – pi, предельными сроками выполнения diи требованиями ко времени выполнения ci.
Для проверки возможного составления расписания анализируется расписание на отрезке времени равному наименьшему общему множителю периодов этих процессов.
|
|
|
Необходимое условие наличия расписания:
Сумма коэффициентов использования m=S ci/ pi<= k, где k - количество доступных процессоров.
2)Алгоритмы с динамическим изменением приоритетов.
Параметр deadline – конечный срок выполнения.
Выбор процесса на выполнение по правилу:
выбирается процесс, у которого текущее значение разницы между конечным сроком выполнения и временем, необходимым для его непрерывного выполнения, является наименьшим.
Таким образом, можно сфтрмулировать общие критерии для сравнения алгоритмов планирования
использование времени ЦП
пропускная способность (кол-во процессов в единицу времени)
время ожидания (в очереди готовых)
время оборота (полное время от момента поступления до завершения)
время отклика (для интерактивных программ – время от поступления в систему до момента первого обращения к терминалу
предельный срок выполнения процесса
и т.д.
Планирование в ОС UNIX
Используется принцип кругового планирования в рамках очередей каждого приоритета.
Если процесс не завершается или не блокируется в рамках 1 секунды – он вытесняется.
В общем случае значение приоритета есть функция
P=F (CPU, nice), т.е. в вычислении приоритета используются две изменяемые составляющие – CPU (системная) и nice (пользовательская). Учитывается история выполнения, величины CPU и nice ограничены.
Пересчет приоритета процесса происходит в момент выбора процесса для выполнения на ЦП 1 раз в секунду.
Процессам назначается базовый приоритет, чтобы их можно было разделять на фиксированные группы уровней приоритетов.
Эти группы используются для оптимизации доступа к блочным устройствам (например, к диску) и обеспечения быстрого отклика операционной системы на системные вызовы.
Группы приоритетов
(в порядке убывания)
- программа свопинга
- управление байт-ориентированными устройствами ввода/вывода
- пользовательские процессы
Иерархия обеспечивает эффективное использование устройств ввода/вывода
СPUj (i) - время использования ЦП процессом j за время i;
Pj (i) - приоритет процесса j в начале кванта i (приоритет выше, если значение меньше);
|
|
|
Basej- базовый приоритет j-го процесса (необходим для разделения процессов на фиксированные группы уровней приоритетов);
nicej - пользовательская составляющая приоритета (значение может только увеличиваться до некоторого уровня).
Пример традиционного планирования процессов в ОС Unix
В примере не учитывается составляющая nice.
Планирование в Windows NT.
Квантование сочетается с использованием динамических абсолютных приоритетов.
В системе определено 32 уровня приоритетов.
Два класса нитей:
Нити с переменными приоритетами (0-15]
Нити “реального” времени (16-31] – высокоприоритетные нити.
Критичны по времени выполнения.
|
|
|
