4

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

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

  • 策略是什么 - 描述一般情况（假设人们知道任务队列是什么、信号量、锁和调度程序本身之外的其他操作系统基础）
  • 该策略针对什么进行了优化（任务延迟、效率、实时、抖动、资源共享等）
  • 是实时的，还是可以实时的

当前策略：

-亚当

4

2 回答 2

8

正如题为“能源感知嵌入式系统的实时任务调度”的论文中所述，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!
    }
}

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

于 2008-09-08T16:09:55.887 回答
2

一种常见的实时调度方案是使用基于优先级的抢占式多任务。
每个任务都分配了不同的优先级。
就绪队列中优先级最高的任务将是运行的任务。它将一直运行，直到它放弃 CPU（即延迟、等待信号量等）或更高优先级的任务准备好运行。

这种方案的优点是系统设计人员可以完全控制哪些任务将以什么优先级运行。调度算法也很简单，应该是确定性的。

On the other hand, low priority tasks might be starved for CPU. This would indicate a design problem.

于 2008-09-16T17:37:45.157 回答