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

StackOverflow https://stackoverflow.com/questions/49962

Вопрос

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

Для вашего ответа, пожалуйста, выберите одну стратегию и рассмотрите ее более подробно, вместо того чтобы давать немного информации о нескольких стратегиях.Если вам есть что добавить к чьему-либо описанию, и оно короткое, добавьте комментарий, а не новый ответ (если оно длинное или полезное, или просто намного лучшее описание, тогда, пожалуйста, используйте ответ)

  • Какова стратегия - опишите общий случай (предположим, люди знают, что такое очередь задач, семафоры, блокировки и другие основы операционной системы за пределами самого планировщика)
  • Для чего оптимизирована эта стратегия (задержка выполнения задачи, эффективность, реальное время, дрожание, совместное использование ресурсов и т.д.)
  • Это в реальном времени, или это можно сделать в реальном времени

Текущие стратегии:

-Адам

Это было полезно?

Решение

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

Из газеты:

Низкоэнергетический алгоритм earlest deadline first эвристический, или просто LEDF, является расширением хорошо известного алгоритма earlest deadline first (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!
    }
}

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

Другие советы

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top