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

对于答案，请选择一种策略并对其进行详细介绍，而不要提供有关几种策略的一些信息。如果我们要在别人的说明中添加一些内容，但内容简短，请添加评论而不是新答案(如果内容冗长或者有用，或者只是一个更好的说明，请使用答案)

• 策略是什么-描述一般情况(假设人们知道什么是任务队列，信号量，锁以及调度程序本身之外的其他OS基础知识)
• 此策略针对(任务等待时间，效率，实时性，抖动，资源共享等)进行了优化的策略是什么？
• 是实时的还是实时的

当前策略：

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

-亚当

解决方案

回答

Swaminathan和Chakrabarty在题为《能源感知嵌入式系统的实时任务调度》的论文中描述了Swaminathan和Chakrabarty描述了具有多个处理器速度和可用功耗配置文件的低功率(嵌入式)设备中实时任务调度的挑战。他们概述的调度算法(并且被证明仅比测试中的最佳解决方案低约1％)具有一种有趣的调度任务的方式，它们称为LEDF启发式。

从本文：

The low-energy earliest deadline ?rst
  heuristic, or simply LEDF, is an
  extension of the well-known earliest
  deadline ?rst (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!
    }
}

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

回答

一种常见的实时调度方案是使用基于优先级的抢占式多任务处理。
每个任务都分配有不同的优先级。
准备就绪队列中优先级最高的任务将是正在运行的任务。它会一直运行直到它放弃CPU(即延迟，等待信号灯等)或者更高优先级的任务准备运行为止。

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

另一方面，低优先级的任务可能会饿死CPU。这将指示设计问题。