Планировщики заданий

Как описано в документе под названием Планирование задач в реальном времени для встраиваемых систем с учетом энергопотребления Сваминатан и Чакрабарти описывают проблемы планирования задач в режиме реального времени на маломощных (встроенных) устройствах с несколькими скоростями процессора и профилями энергопотребления. Алгоритм планирования, который они обрисовывают в общих чертах (и показано, что он лишь примерно на 1% хуже, чем оптимальное решение в тестах), имеет интересный способ планирования задач, который они называют эвристикой LEDF.

Из бумаги:

Низкоэнергетическая эвристика «самый ранний крайний срок — первая», или просто LEDF, является расширением хорошо известного алгоритма «самый ранний крайний срок — первый» (EDF). Работа LEDF выглядит следующим образом: LEDF поддерживает список всех выпущенных задач, называемый «списком готовности». Когда задачи освобождаются, для выполнения выбирается задача с ближайшим сроком. Выполняется проверка, чтобы увидеть, можно ли уложиться в срок задачи, выполнив ее при более низком напряжении (скорости). Если срок может быть соблюден, LEDF назначает более низкое напряжение для задачи, и задача начинает выполняться. Во время выполнения задачи в систему могут поступать другие задачи. Предполагается, что эти задачи автоматически помещаются в «готовый список». LEDF снова выбирает задачу с ближайшим сроком выполнения. Пока есть задачи, ожидающие выполнения, LEDF не оставляет процессор бездействующим. Этот процесс повторяется до тех пор, пока все задачи не будут запланированы.

И в псевдокоде:

Repeat forever {
    if tasks are waiting to be scheduled {
        Sort deadlines in ascending order
        Schedule task with earliest deadline
        Check if deadline can be met at lower speed (voltage)
        If deadline can be met,
            schedule task to execute at lower voltage (speed)
        If deadline cannot be met,
            check if deadline can be met at higher speed (voltage)
        If deadline can be met,
            schedule task to execute at higher voltage (speed)
        If deadline cannot be met,
            task cannot be scheduled: run the exception handler!
    }
}

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

Одной из распространенных схем планирования в реальном времени является использование вытесняющей многозадачности на основе приоритета.
Каждой задаче назначается свой уровень приоритета.
Запускаемая задача имеет наивысший приоритет в очереди готовности. Он будет работать до тех пор, пока либо не откажется от ЦП (т. е. задержится, будет ждать на семафоре и т. д.), либо задача с более высоким приоритетом не станет готовой к запуску.

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

С другой стороны, задачи с низким приоритетом могут испытывать нехватку ресурсов ЦП. Это указывало бы на проблему с дизайном.