解决方案
正如一篇题为 能源感知嵌入式系统的实时任务调度, 、Swaminathan 和 Chakrabarty 描述了在具有多种处理器速度和功耗配置文件的低功耗(嵌入式)设备中进行实时任务调度的挑战。他们概述的调度算法(在测试中显示仅比最佳解决方案差 1% 左右)有一种有趣的任务调度方式,他们称之为 LEDF 启发式。
来自论文:
最早的截止日期最早的启发式术,即简单的LEDF,是最早的最早截止日期(EDF)算法的延伸。LEDF的操作如下:LEDF保留了所有已发布任务的列表,称为“就绪列表”。什么时候 任务被释放,任务与 选择最近的截止日期为 执行。执行检查以查看 如果任务截止日期可以通过 在较低的电压下执行它 (速度)。如果可以按时完成, LEDF 将较低的电压分配给 任务,任务开始执行。在任务执行期间,其他 任务可能会进入系统。这些 假定已放置任务 自动在“就绪列表”上。LEDF 再次选择任务,并使用 要执行的最近截止日期。如 只要有任务等着做 执行时,LEDF 不会保留 pro- cessor 闲置。重复此过程 直到所有任务都完成 计划。
并用伪代码表示:
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。这表明存在设计问题。