Наименьший резерв времени

с наименьшим резервом времени ( LST ) Планирование — это алгоритм динамического планирования приоритетов . Он назначает приоритеты процессам на основе их простоя . Резервное время — это количество времени, оставшееся после выполнения задания, если задание было начато сейчас. Этот алгоритм также известен как « сначала наименьшая небрежность» . Чаще всего он используется во встроенных системах , особенно с несколькими процессорами. Он накладывает простое ограничение, согласно которому каждый процесс на каждом доступном процессоре имеет одинаковое время выполнения и что отдельные процессы не имеют привязки к определенному процессору. Именно это делает его пригодным для встроенных систем.

Слабое время

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

Более формально, свободное время $s$ для процесса определяется как:

$s=(d-t)-c'$

где $d$ крайний срок процесса, $t$ - это реальное время с момента начала цикла, и $c'$ — оставшееся время вычислений.

Приложения

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

Пригодность

Планирование LST наиболее полезно в системах, содержащих в основном апериодические задачи, поскольку не делается никаких предварительных предположений о частоте возникновения событий. Основная слабость LST в том, что он не заглядывает вперед и работает только с текущим состоянием системы. Таким образом, при кратковременной перегрузке системных ресурсов LST может оказаться неоптимальным. Это также будет неоптимально при использовании с бесперебойными процессами. Однако, как и в случае с первым крайним сроком , и в отличие от планирования с монотонной скоростью , этот алгоритм можно использовать для загрузки процессора до 100%.

См. также

• Первое планирование по самому раннему сроку — другой алгоритм динамического планирования приоритетов, который гарантирует оптимальную пропускную способность.