抢占阈值调度的功耗优化

DVS(Dynamic Voltage Scaling)技术的应用使得任务执行时间延长进而使得处理器的静态功耗(由CMOS电路的泄露电流引起)迅速增加.延迟调度(Procrastination Scheduling)算法是近年提出用于减少静态功耗的有效方法,它通过推迟任务的正常执行来尽可能长时间地让处理器处于睡眠或关闭状态,从而避免过多的静态功耗泄露.文中针对可变电压处理器上运用抢占阈值调度策略的周期性任务集合,将节能调度和延迟调度结合起来,提出一种两阶段节能调度算法,先使用离线算法来计算每个任务的最优处理器执行速度,而后使用在线模拟调度算法来计算每个任务的延迟时间,从而动态判定处理器开启/关闭时刻.实例研究和仿真实验表明,作者的方法能够进一步降低抢占阈值任务调度算法的功耗.     

基于动态抢占阈值的实时调度

具有抢占阈值的调度算法集非抢占调度和纯抢占调度的特点,既减少了由于过多的随意抢占造成的CPU资源浪费,又保证了一定的任务截止期错失率及CPU资源利用率。已有的工作基本集中于讨论任务集完全给定,任务数、任务的优先级及任务的抢占阈值在调度前已完全确定,而且要求不同的任务具有不同的优先级,提出的具有抢占阈值的调度算法,完全放松了对这些条件的限制,即任务的个数不确定,任务的优先级及其抢占阈值在调度过程中可以动态地变化。最后以常用的LSF调度策略为例,结合动态的抢占阈值进行仿真,仿真结果表明,对于不确定的任务集、任务优先级和抢占阈值,利用具有抢占阈值的动态调度算法,降低了任务截止期错失率、提高了CPU的有效使用率。     

抢占阈值调度算法的分析与研究

本文详细论述了应用于静态优先级实时系统的抢占阈值调度算法。描述了算法实现和任务集合可调度性判定公式的推导,分析了算法的性能特点,阐述了抢占阈值调度是静态优先级嵌入式实时系统开发中调度算法的合适选择。     

基于动态抢占阈值的LSF调度算法

在最小空闲时间优先(LSF)调度算法中,当任务集中有多个任务的优先级相同或相近时,过多的上下文切换会产生“颠簸”现象,从而大幅增加系统开销。为此,结合LSF算法的特点,通过设计合理的动态抢占阈值,提出一种改进的调度算法DPTLSF。仿真结果表明,改进的算法能够大幅减少“颠簸”现象的发生,降低任务集的截止期错失率。     

一种采用动态电压调整的实时节能调度算法

较高的能量消耗会导致处理器热量的增加及系统可靠性的降低,合理运用动态电压调整技术有效降低实时任务运行所需的能耗成为一个研究热点.提出一种动态实时节能调度算法MSF,以最大空闲时间优先调度为基础,结合动态调整技术,使得实时任务在其截止期内完成的同时能够最大限度地降低整个系统的能量消耗.实验结果表明, 该方法能够充分利用任务的不同能量特性和动态空闲时间,更有效的实现节能,优于其它算法.     

在构件化嵌入式操作系统中应用抢占阈值调度

现有基于构件的嵌入式实时软件开发过程着重于从结构的角度分解系统成若干构件,以及重用构件。实践证明,该开发过程还应从运行角度将构件映射成任务,并选择适当的实时调度算法。为此,根据目前的工程实践提出一种实时构件模型,包含将构件映射成任务的方式。描述了当前构件化嵌入式操作系统可以使用的4种调度算法,并比较这些算法的性能特点。提出抢占阈值(preemptionthreshold)调度模型更适合构件化嵌入式实时系统,仿真实验的结果证明了该结论。比较结果和结论对构件化嵌入式实时系统的设计和开发有一定的参考价值。     

FPTS:一种任务间存在共享资源时的抢占阈值调度算法

受到广泛关注的抢占阈值调度算法能够有效减少现场切换次数,防止不必要的任务抢占,降低资源额外消耗,提高任务集合的可调度性.目前该调度算法的研究工作大多围绕独立任务集合展开,在实际实时系统中任务经常需要互斥访问共享资源,任务之间由于资源共享而导致的相关性对于任务集合的优先级分配和抢占阈值分配都有很大的影响.SRP协议是在实时系统中得到广泛应用的资源访问控制协议,具有死锁避免、提前阻塞、共享任务栈等一系列优良特性.将SRP和抢占阈值调度算法结合起来,提出FPTS调度模型,给出相应的可调度性判定公式,考虑在任务之间使用SRP协议时求解任务抢占阅值分配,最后给出计算抢占阈值分配的伪多项式时间算法.     

动态抢占阈值调度中的快速任务选择算法

基于动态抢占阈值的实时调度算法集非抢占调度和纯抢占调度的特点,既减少了由于过多的随意抢占造成的CPU资源浪费,又保证了较高的CPU资源利用率。然而,现有的任务选择算法运行时的额外代价严重影响了系统的整体性能。针对这个问题,本文提出一种使用“选择树”作为任务队列结构的、时间复杂度为O（｜log2n｜）的快速任务选择算法。本文从理论上证明该算法正确性的同时,在使用ARM9芯片的Nokia智能手机上验证了该算法在嵌入式实时系统中的有效性。实验表明,该算法在充分利用处理器的同时能够有效降低动态阈值调度算法的额外代价。     

Linux中一种改进的实时调度算法及其应用

在实时操作系统中,调度算法起着关键性的作用,然而调度算法的开销与系统的调度性能之间经常是一对矛盾.就此问题,结合最新版Linux2.6内核任务调度的特点,提出了一种改进的最小裕度优先(LSF)算法.针对LSF算法中因任务间的频繁切换造成系统开销增大的缺点,通过采用适当的抢占阚值策略减少\"颠簸\"现象,提高了Linux2.6内核的实时性.     

容错优先级可提升的抢占阈值容错调度算法

基于软件容错模型,提出了允许容错优先级提升的抢占阈值容错调度算法(extended fault-tolerantfixed-priority with preemption threshold,简称FT-FPPT*).该算法能够在抢占式容错调度算法(fault-tolerantfixed-priority preemptive,简称FT-FPP)和抢占阈值容错调度算法(fault-tolerant fixed-priority with preemptionthreshold,简称FT-FPPT)无法提高系统容错能力的情况下,进一步提高系统的容错能力.为了获得系统中任务优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,提出了一种最优的优先级配置搜索算法(priorityassignment search algorithm,简称PASA).经过深入分析和实验证明,与FT-FPPT算法相比,FT-FPPT*算法能够有效地提高硬实时系统的容错能力.     

Feedback EDF Scheduling of Real-Time Tasks Exploiting Dynamic Voltage Scaling

Many embedded systems are constrained by limits on power consumption, which are reflected in the design and implementation for conserving their energy utilization. Dynamic voltage scaling (DVS) has become a promising method for embedded systems to exploit multiple voltage and frequency levels and to prolong their battery life. However, pure DVS techniques do not perform well for systems with dynamic workloads where the job execution times vary significantly. In this paper, we present a novel approach combining feedback control with DVS schemes targeting hard real-time systems with dynamic workloads. Our method relies strictly on operating system support by integrating a DVS scheduler and a feedback controller within the earliest-deadline-first (EDF) scheduling algorithm. Each task is divided into two portions. The objective within the first portion is to exploit frequency scaling for the average execution time. Static and dynamic slack is accumulated for each task with slack-passing and preemption handling schemes. The objective within the second portion is to meet the hard real-time deadline requirements up to the worst-case execution time following a last-chance approach. Feedback control techniques make the system capable of selecting the right frequency and voltage settings for the first portion, as well as guaranteeing hard real-time requirements for the overall task. A feedback control model is given to describe our feedback DVS scheduler, which is used to analyze the system's stability. Simulation experiments demonstrate the ability of our algorithm to save up to 29% more energy than previous work for task sets with different dynamic workload characteristics. This work was supported in part by NSF grants CCR-0208581, CCR-0310860 and CCR-0312695. Preliminary versions of parts of this work appeared in the ACM SIGPLAN Joint Conference Languages, Compilers, and Tools for Embedded Systems (LCTES'02) and Software and Compilers for Embedded Systems (SCOPES'02) (Dudani et al., 2002), in the Workshop on Compilers and Operating Systems for Low Power 2002 (Zhu and Mueller, 2002) and in the IEEE Real-Time Embedded Technology and Applications Symposium 2004 (Zhu and Mueller, 2004a).     

一个基于资源操作的强实时动态调压算法

动态调压算法能够降低系统功耗，可用来降低CPU发热量、延长电池供电系统的工作时间．然而，现有动态调压算法均不允许进程进行资源操作（申请或释放资源），这在实际应用中是难以满足的．因此，现有算法不便于实际应用,本文提出了一种新的强实时动态调压算法．该算法允许进程进行资源操作，并且功耗低于现有算法；该算法还能避免死锁．该算法易于应用到实际系统中．     

一种基于程序段的动态电压缩放算法

动态电压缩放技术是一种能有效优化处理器能耗的方法,它允许处理器在运行时动态地改变其时钟频率和供电电压.针对处理器提出了一种基于程序段的动态电压缩放算法PBVSA,该算法使用建立在指令工作集签名基础上的程序段监测状态机来判断程序段是否发生变化,并作出CPU电压和频率调整决定,在程序段内,通过计算该段的频率缩放因子β(片外工作时间与片上工作时间的比例关系)来设定CPU的电压和频率,在sim-panalyzer模拟器上完成了算法的实现,通过对Mibench测试程序集的测试表明:该算法平均降低了处理器29%的能耗,而性能损失平均为5.3%.     

基于动态电压调节的低功耗视频解码技术研究

讨论在嵌入式系统中使用动态电压调节技术降低视频解码功耗。提出一种基于动态电压调节的低功耗解码技术。该方法采用移动平均法预测帧的解码时间,依据预测的结果动态地调节解码过程中微处理器的工作电压,降低能量消耗。实验结果表明,基于动态电压调节的视频解码器比常规解码器减少10%￣30%的能量消耗。     

Dynamic Voltage Scaling for Digital Control System Implementation

For real-time computer-controlled systems, control performances of tasks as well as energy consumption of overall system must be optimized. A control task does not have a fixed period but a range of periods in which the control performance varies. Hence, when more than one control tasks are scheduled on a single processor, an optimization problem appears. Furthermore, when an energy saving technique such as dynamic voltage scaling is used, its properties affect the control performance.Using a performance index that involves control performance and energy consumption, a static solution is proposed to obtain the optimal processor speed and a set of periods for given control tasks in O(k). Also a dynamic solution is proposed to utilize system services of real-time operating systems to overcome unavoidable deficiencies of the static solution and to further reduce the energy consumption of the overall system. The performances of proposed solutions are revealed via simulation studies.Hyung Sun Lee received his B.S. and M.S. degrees in electronics engineering from Korea Advanced Institute of Science and Technology (KAIST) in 2000 and 2002, respectively. He is currently a Ph.D. student in the Department of Electrical Engineering and Computer Science (EECS) at KAIST. His research interests include real-time control and power-aware real-time embedded systems.Byung Kook Kim received his B.S. degree in Electronics Engineering from Seoul National University in 1975, and his M.S. and Ph.D. degrees from KAIST in 1977 and 1981, respectively. Dr. Kim was a manager and founder of the Calibration Laboratory, Woojin Instrument Co. Ltd, in 1981. He performed his postdoctoral research at the University of Michigan, Ann Arbor, Michigan, from 1982 to 1983. He returned to Woojin Instruments as a chief researcher of the R&D Department from 1984 to 1986. He joined the faculty of the Department of Electrical Engineering at KAIST in 1986, where he is currently a professor. His research interests include real-time systems, parallel and distributed systems, fault-tolerant computing, mobile robot sensing and navigation, and manipulator control.     

改进的基于抢占阈值调度的任务响应时间分析方法

基于抢占阈值调度的任务响应时间分析方法是一种新型实时系统任务可调度性判定技术。然而已有的研究工作,有时对以前的任务请求检查过少,可能导致对响应时间估计过低。同时对任务响应时间的分析忽略了任务释放抖动和时钟嘀嗒调度对任务响应时间的影响,造成任务错过期限的现象,系统任务可调度性判定存在潜在的不精确因素。针对上述缺点不足,本文提出改进的基于抢占阈值调度的任务响应时间分析方法,在修正已有方法缺陷的同时,考虑任务释放抖动和时钟嘀嗒调度的影响,引入额外的时间需求,使用改进的任务参数计算系统任务时间需求函数。仿真对比结果表明,改进后的方法较单纯固定优先级抢占阈值调度下的任务响应时间分析方法得到更加精确可调度性分析结果。     

CPU频率对电池的影响以及对动态调压算法的改进

对电池供电的嵌入式系统来说，电池工作时间是重要的指标．利用动态调压算法对CPU频率进行调度．可以延长电池工作时间．然而，目前尚没有通用的方法对CPU频率和电池之间的关系进行深入研究，这导致动态调压算法不能最大限度地延长电池工作时间，本文提出一种新方法来研究CPU频率对电池的影响，其结论具有通用性，并得到实验的验证，利用这个结论，本文对动态调压算法进行了优化，使之更适于电池供电系统。