Самодел 2 (1114717), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

К
ванты постоянной длины.

Простой круговорот (round robin):

• Время ожидания кванта процессом ~ q(n-1)

• Параметры: длина очереди и величина кванта.

• Дисциплина обслуживания очереди, например, FIFO.

• Переключение процессов – операция, требующая времени.

Кванты переменной длины

• Величина кванта может меняться со временем

  • Вначале «большой» квант q=A, на следующем шаге q=A-t, q=A-2t,…, до q=B (B<A). Преимущество для коротких задач.

  • Вначале q=B, далее q=B+t,…, до q=A. Уменьшение накладных расходов на переключение задач, когда несколько задач выполняют длительные вычисления.

• Если процесс интенсивно пользуется операциями ввода/вывода, то он может использовать выделенный квант не до конца. В качестве компенсации ему могут предоставляться привилегии при дальнейшем обслуживании.

Квантование с предпочтением процессам, интенсивно обращающимся к вводу/выводу.

Выполнение

Квант исчерпан Процесс завершён

или ошибка

Очередь готовых процессов 1

назначен

квант требуется

ввод/вывод

Очередь готовых процессов 2

ожидание

назначен

квант

ввод/вывод завершён

Алгоритмы, основанные на приоритетах

Вычисление приоритета основывается на статических и динамических характеристиках.

Изменение приоритета может происходить по инициативе:

- процесса

- пользователя

- ОС

Правила назначения приоритета процессов определяют эффективность работы системы.

Планирование по наивысшему приоритету (highest priority first - HPF).

• При появлении в очереди готовых процессов процесса с более высоким приоритетом, чем у текущего наступает момент смены процесса. Возможно два варианта:

- относительный приоритет (ожидание исчерпания кванта у текущего процесса)

- абсолютный приоритет (немедленная смена текущего процесса)

• Задача выбора/постановки процесса с наивысшим приоритетом зависит от организации очереди (упорядочена/неупорядочена).

• Возможно наличие очередей с одинаковым приоритетом.

Пример использования стратегии HPF.

• Выбор самого короткого задания (shortest job first - SJF).

Время выполнения – характеристика, на которой основан приоритет. Приоритет обратно пропорционален ожидаемому времени обработки.

Удобно для “коротких” процессов

SRT(shortest remaining time)

Класс правил, использующих линейно возрастающий приоритет.

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

Процесс при входе в систему получает некий приоритет, который возрастает с коэффициентом A во время ожидания в очереди готовых процессов, и с коэффициентом B во время выполнения.

• Выбор A и В - разные правила планирования:

- Если 0<A<=B обслуживание очереди по дисциплине FIFO

- Если 0>B>=A обслуживание очереди по дисциплине LIFO

• Возможен выбор нелинейных функций.

Нелинейные функции изменения приоритета

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

В частности, метод SJF можно модифицировать, добавляя приоритет длинным процессам после некоторого времени ожидания.

Разновидности круговорота.

Простой круговорот (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 - количество доступных процессоров.

Классический алгоритм для жестких систем реального времени с одним процессором

Используются периодические запросы на выполнение процессов.

Срок выполнения каждого процесса равен его периоду p.

Все процессы независимы

Максимальное время выполнения каждого процесса с известно и постоянно игнорируется время переключения контекста.

Вводится ограничение на суммарный коэффициент загрузки процессора S ci / pi, при существовании n задач не превосходит n(21/n-1). Эта величина при n¥® равна ln 2, то есть 0.7

Лью, Лейланд 1973. Используются вытеснения и статические приоритеты.

Суть алгоритма:

Процессы получают статические приоритеты в соответствии с величиной их периодов выполнения, при этом самый высший приоритет получает самая короткая задача.

Соблюдение приведенных ограничений гарантирует выполнение временных ограничений для всех процессов во всевозможных ситуациях

Алгоритмы с динамическим изменением приоритетов.

Параметр deadline – конечный срок выполнения.

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

Общие критерии для сравнения алгоритмов планирования:

использование времени ЦП

• пропускная способность (кол-во процессов в единицу времени)

• время ожидания (в очереди готовых)

• время оборота (полное время от момента поступления до завершения)

• время отклика (для интерактивных программ – время от поступления в систему до момента первого обращения к терминалу

• предельный срок выполнения процесса

• и т.д.

Планирование в ОС UNIX

Используется принцип кругового планирования в рамках очередей каждого приоритета.

Если процесс не завершается или не блокируется в рамках 1 секунды – он вытесняется.

В общем случае значение приоритета есть функция:

P=F (CPU, nice),

т.е. в вычислении приоритета используются две изменяемые составляющие – CPU (системная) и nice (пользовательская)

Пересчёт приоритета процесса происходит в момент выбора процесса для выполнения на ЦП 1 раз в секунду. Процессам назначается базовый приоритет, чтобы их можно было разделить на фиксированные группы уровней приоритетов. Эти группы используются для оптимизации доступа к блочным устройствам (например, к диску).

Группы приоритетов

(в порядке убывания)

• программа свопинга

• управление блочными устройствами ввода/вывода

• управление файлами

• управление байт-ориентированными устройствами ввода/вывода

• пользовательские процессы

Иерархия обеспечивает эффективное использование устройств ввода/вывода

Используются формулы:

СPUj (i) - время использования ЦП процессом j за время i Pj (i) - приоритет процесса j в начале кванта i (приоритет выше, если значение меньше);

Basej - базовый приоритет j-го процесса (необходим для разделения процессов на фиксированные группы уровней приоритетов);

nicej - пользовательская составляющая приоритета (значение может только увеличиваться до некоторого уровня).

Пример традиционного планирования процессов в ОС Unix

Планирование в Windows NT.

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

В системе определено 32 уровня приоритетов.

Два класса нитей:

Нити с переменными приоритетами (0-15]

Характеристики

Список файлов лекций