Планировщики заданий - PullRequest
Новая
       19

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

4 голосов
/ 08 сентября 2008

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

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

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

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

-Adam

Ответы [ 2 ]

8 голосов
/ 08 сентября 2008

Как описано в статье под названием Планирование задач в реальном времени для энергосберегающих встраиваемых систем , Swaminathan и Chakrabarty описывают проблемы планирования задач в режиме реального времени на маломощных (встроенных) устройствах с несколькими процессорами Доступны профили скорости и энергопотребления. Алгоритм планирования, который они описывают (и показано, что он на 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!
    }
}

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

2 голосов
/ 16 сентября 2008

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

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

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

...