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

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

Планирование в системах реального времени

Смешанные алгоритмы планирования

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

К примеру, в основе – концепция квантования, а определение кванта и/или дисциплина обслуживания очередей базируется на приоритетах.

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

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

Системы реального времени бывают “Жесткие” и ” мягкие ”.

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

Это может быть обеспечено за счет:

- полного тестирования всевозможных сценариев

- построения статического расписания

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

Периодические запросы – все моменты запроса периодического процесса можно определить заранее.

Пусть {Ti} набор периодических процессов с периодами – pi, предельными сроками выполнения di и требованиями ко времени выполнения ci.

Расписание удается построить не всегда.

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

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

Необходимое условие наличия расписания:

Сумма коэффициентов использования m=S ci / pi <= k, где k - количество доступных процессоров.

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

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

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

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

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

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

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

Выбор процесса на выполнение по правилу:

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

Перепланировка – функция ОС. Планировщик – программа, которая реализует некоторый алгоритм.

Перепланировка происходит после одного из следующих событий:

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

2.выполнение системного вызова, а ресурс занят

3. системный вызов, связанный с освобождением ресурса. Если какой-то процесс ждет этот ресурс, то освобождение подождет.