В чем суть EDF

EDF (Earliest Deadline - First) и LSTF (Least Slack Time - First) политика работают с динамическими приоритетами.
В политике EDF, чем меньше крайний срок задачи, тем выше приоритет назначается на эту задачу.

Условие:

Где Ci - время выполнения задачи и Di – относительный срок выполнения задачи, равный длине временного интервала, началу которого соответствует момент порождения задачи, концу – абсолютный срок выполнения задачи. То есть выполнимой является любое приложение с плотностью загрузки процессора не больше 1.

80. В чём отличие приоритета задачи от критичности задачи с точки зрения планировщика?

81. Какой дедлайн – абсолютный или относительный – использует EDF-алгоритм планирования? (не уверен)

Большинство ОСРВ оперируют относительным временем. Что-то происходит “до” и “после” некоторого другого события. В системе, полностью управляемой событиями, необходим часовой механизм (ticker), т.к. там нет квантования времени (time slicing). Однако, если нужны временные метки для некоторых событий или необходим системный вызов типа “ждать одну секунду”, то нужен тактовый генератор и/или таймер.

Синхронизация в ОСРВ осуществляется с помощью механизма блокирования (или ожидания) до наступления некоторого события. Абсолютное время не используется.

82. В каких случаях EDF-алгоритм планирования оптимален?

(EDF - Алгоритм планирования задач «наиболее срочная первой»)

Условие:

Где Ci - время выполнения задачи и Di – относительный срок выполнения задачи, равный длине временного интервала, началу которого соответствует момент порождения задачи, концу – абсолютный срок выполнения задачи. То есть выполнимой является любое приложение с плотностью загрузки процессора не больше 1.

При условии, что начало выполнения любой задачи способно «подождать» пока не будут выполнены наиболее срочные задачи.

83. Как влияет многороцессность на оптимальность EDF-планирования?

EDF – алгоритм с динамическим планированием задачи. Чем меньше срок выполнения, тем выше приоритет. Каждый раз задачи выстраиваются заново в зависимости от критического срока выполнения. Реализованный алгоритм зависит от количества задач в определенный момент времени.

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

84. Каким качеством характеризуются алгоритмы планирования на основе приоритетов с вытеснением с точки зрения оптимальности принимаемых решений в каждой точке планирования?

Под вытеснением имеется ввиду то, что если во время работы какой-то задачи возникает работа другой задачи с приоритетом выше, чем у работающей в данный момент, то управление передается вновь возникшей задаче. При невытесняющем EDF задача всегда доделывает свою очередную работу до конца, независимо от того, появились ли во время работы этой задачи другие задачи с более высоким приоритетом или не появились.

Для алгоритма EDF с вытеснением задач имеет место следующая

Теорема. Алгоритм EDF оптимален для любого набора задач (периодические с любым соотношением между периодами и крайними сроками, спорадические) если:

• все задачи независимы

• возможно вытеснение

• вытеснение не требует временных затрат (разумеется, это предположение не соответствует реальному положению вещей)

85. В чём суть алгоритма LST (Least Slack Time=LLF(Least Laxity First))?

Вместо этого, с LSTF политикой, чем меньше слабое время задачи, тем выше приоритет назначается на эту задачу.

Cлабое время задачи(slack time) определено как разница между оставшимся временем до крайнего срока задачи, и количеством времени, которое требует задача.