任务调度器

Question

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

对于你的答案，请选择一个策略，并仔细研究它，而不是提供一些关于几个策略的信息。如果你有什么东西要添加到别人的描述中，并且它是简短的，那么添加一个评论而不是一个新的答案(如果它是长的或有用的，或者仅仅是一个更好的描述，那么请使用一个答案)

• 策略是什么?描述一般情况(假设人们知道任务队列、信号量、锁和调度程序本身之外的其他操作系统基本原理)
• 这种策略是针对什么(任务延迟、效率、实时、抖动、资源共享等)进行优化的。
• 它是实时的，还是实时的？

目前的战略：

• 基于优先级的抢占
• 最低功率最慢时钟

-Adam

Answer 1

正如在一篇题为基于能量感知的嵌入式系统实时任务调度的论文中所描述的，Swaminathan和Chakrabarty描述了在具有多处理器速度和可用功耗配置文件的低功耗(embedded)设备中实时任务调度的挑战。他们描述的调度算法(并且只比测试中的最优解差1%左右)有一种有趣的调度方法，他们称之为LEDF启发式。

从文件中：

低能量最早截止期first启发式算法(简称LEDF )是著名的最早截止期first算法的推广.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!
    }
}

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

Answer 2

一种常见的实时调度方案是采用基于优先级的抢占式多任务调度.

每个任务都分配了不同的优先级级别。

就绪队列上的最高优先级任务将是运行的任务。它将一直运行，直到放弃CPU (即延迟、等待信号量等)。或者更高优先级的任务可以运行。

此方案的优点是系统设计人员完全控制将以何种优先级运行的任务。调度算法简单，应该是确定性的。

另一方面，低优先级的任务可能需要CPU。这将表明存在设计问题。