operating-system - 任务调度器

Question

与一些同事就实时任务的最佳调度策略进行了有趣的讨论，但并不是每个人都对常见或有用的调度策略有很好的理解。

对于您的答案，请选择一种策略并详细讨论它，而不是提供有关几种策略的一些信息。如果您有什么要添加到其他人的描述中并且很短，请添加评论而不是新答案(如果它很长或有用，或者只是更好的描述，那么请使用答案)

什么是策略 - 描述一般情况(假设人们知道任务队列是什么、信号量、锁和调度程序本身之外的其他操作系统基础知识)

这个策略是针对什么优化的(任务延迟、效率、实时性、抖动、资源共享等)

是实时的，还是可以实时的

当前策略:

Priority Based Preemptive

Lowest power slowest clock

-亚当

Answer 1

如题为 Real-Time Task Scheduling for Energy-Aware Embedded Systems 的论文中所述、Swaminathan 和 Chakrabarty 描述了在具有多种处理器速度和功耗配置文件的低功耗(嵌入式)设备中实时任务调度的挑战。他们概述的调度算法(在测试中显示仅比最佳解决方案差约 1%)有一种有趣的调度任务方式，他们称之为 LEDF 启发式。

从论文:

The low-energy earliest deadline first heuristic, or simply LEDF, is an extension of the well-known earliest deadline first (EDF) algorithm. The operation of LEDF is as follows: LEDF maintains a list of all released tasks, called the “ready list”. When tasks are released, the task with the nearest deadline is chosen to be executed. A check is performed to see if the task deadline can be met by executing it at the lower voltage (speed). If the deadline can be met, LEDF assigns the lower voltage to the task and the task begins execution. During the task’s execution, other tasks may enter the system. These tasks are assumed to be placed automatically on the “ready list”. LEDF again selects the task with the nearest deadline to be executed. As long as there are tasks waiting to be executed, LEDF does not keep the pro- cessor idle. This process is repeated until all the tasks have been scheduled.

并在伪代码中:

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!
    }
}

随着小型、低功耗设备变得越来越普遍，实时调度似乎是一个有趣且不断发展的问题。我认为这是一个我们将看到大量进一步研究的领域，我期待与时俱进!