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

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

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

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

 

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

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

 

 

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

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

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

 

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

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

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

 

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

 

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

 

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

Пусть {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. системный вызов, связанный с освобождением ресурса. Если какой-то процесс ждет этот ресурс, то освобождение подождет.