Дедлайн-монотонное планирование - Deadline-monotonic scheduling

Дедлайн-монотонное присвоение приоритетов это политика назначения приоритетов, используемая с упреждающее планирование с фиксированным приоритетом.

С дедлайном-монотонный приоритет назначение, задачи назначаются приоритеты в соответствии с их сроки. Задаче с кратчайшим сроком выполнения присваивается наивысший приоритет.[1] Эта политика назначения приоритетов оптимальна для набора периодических или спорадических задач, которые соответствуют следующей модели системы:

  1. Все задачи имеют крайние сроки, меньшие или равные минимальному времени (или периодам) между прибытиями.
  2. Все задачи есть время исполнения в наихудшем случае (WCET), которые меньше или равны их крайним срокам.
  3. Все задачи независимы, поэтому не блокируют друг друга. исполнение (например, путем доступа к взаимоисключающим общие ресурсы ).
  4. Ни одна задача не приостанавливается добровольно.
  5. Есть некоторый момент времени, называемый критическим моментом, когда все задачи готовы к выполнению одновременно.
  6. Накладные расходы на планирование (переключение с одной задачи на другую) равны нулю.
  7. У всех задач нулевой релиз дрожь (время от поступления задачи до ее готовности к выполнению).

Если ограничение 7 снимается, то оптимальным является монотонное назначение приоритета «крайний срок минус дрожание».

Если ограничение 1 снято, разрешая крайние сроки, превышающие периоды, то оптимальное назначение приоритета Одсли алгоритм может использоваться, чтобы найти оптимальное назначение приоритета.

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

Политика назначения фиксированного приоритета P называется оптимальной, если не существует набора задач, который можно планировать с использованием другой политики назначения приоритетов, которая также не может быть запланирована с использованием политики назначения приоритетов P. Или, другими словами: политика назначения монотонного приоритета по срокам (DMPA) является оптимальным, если любой набор процессов Q, который может быть запланирован схемой приоритетов W, также может быть запланирован DMPA[2]

Смотрите также

Рекомендации

  1. ^ «Монотонное планирование сроков». CiteSeerX  10.1.1.53.8928. Цитировать журнал требует | журнал = (помощь)
  2. ^ Алан Бернс и Энди Веллингс (2001). Системы реального времени и языки программирования (3-е изд.). Эддисон Уэсли. п. 485. ISBN  0-201-72988-1.