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

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

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

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

抢占阈值调度的功耗优化

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

基于改进型统一调度算法改善任务集的可调度性

实时系统要求任务在最差情况下能在其截止时间前获得结果,若超过了其截止时间,也会认为是错误的行为,所以改进任务可调度性分析、提高任务集可调度性尤其重要。统一调度能结合固定优先级调度的优点,防止不必要的抢占,降低资源额外销耗,能够提高任务集合的可调度性;但其任务的可调度性分析方法过于粗糙,影响任务最差响应时间分析的结果,降低了任务集的可调度性。针对存在的问题,基于统一调度,增加任务运行阶段数,重新建立任务模型,并提出通过分配任务抢占阈值、调整运行阶段的抢占阈值与长度,优化任务可容忍阻塞,改善任务集可调度性的算法。最后,实验表明,与统一调度算法及其他算法相比,所提出的调度算法能够有效改善任务集的可调度性。     

多处理器硬实时系统的抢占阈值调度研究

在实时系统中,抢占在提高系统灵活性的同时带来额外的系统开销,特别在多处理器平台上抢占导致的作业迁移会造成相当大的性能下降,减少不必要的抢占是硬实时系统研究的重要方向.抢占阈值调度是处于抢占调度和不可抢占调度之间的一种混合调度方法,在保持调度能力的基础上限制抢占.基于截止期分析建立了多处理器硬实时系统抢占阈值调度的可调度性判定条件,针对抢占阈值调度提出一种改进的优先级分配算法OPA-MLL,并建立了抢占阈值分配(preemption threshold assignment,PTA)算法.仿真结果表明,采用OPA-MLL算法和PTA算法分别给任务集分配优先级和抢占阈值时,可调度任务集比率明显提高,同时能最大程度限制抢占次数.     

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

现有的基于抢占阈值调度的任务响应时间分析方法对实时任务系统进行可调度性判定时，对任务响应时间估计过低，造成任务错过期限的现象。针对上述缺点不足，该文提出改进的基于抢占阈值调度的任务响应时间分析方法，考虑了任务释放抖动和时钟嘀嗒调度的影响，使用改进的任务参数计算系统任务时间需求函数。仿真对比结果表明，改进后的方法较单纯固定优先级抢占阈值调度下的任务响应时间分析方法得到更加精确可调度性分析结果。     

一种不影响任务集合可调度性的优先级映射算法

采用静态优先级调度的实时系统中,当任务个数多于优先级个数时,只能给多个任务分配相同的优先级·现有分配算法增大了高优先级任务的最坏情况响应时间,可能造成任务集合不可调度·利用抢占阈值的调度算法,能在提高任务集合可调度性的同时,使用较少的线程·但所用优先级个数没有减少·提出了一种优先级映射算法———阈值段间映射法(threshold segment mapping,TSM),以及与之配合的事件驱动线程框架·证明了TSM是严格排序的·仿真结果表明,在保证任务集合可调度的前提下,TSM使用了比现有映射算法更少的优先级·     

引入虚拟特征参数的混合实时任务调度及应用

提出了在实时环境下周期任务与非周期任务混合调度的一种新方法。引入非周期实时任务虚拟截止期、虚拟周期的特征参数,综合考虑各实时任务的多特征参数进行优先级设计,克服了单独考虑任务的个别参数以及忽略非周期任务自身特征的调度策略的局限性及调度风险,且能够尽可能地加快非周期任务的响应速度,提高系统整体的调度性能。将该方法在RT-Linux实时环境中实现,并针对无人飞艇的自动驾驶仪进行了任务实例的可调度性测试,证明了该调度策略的可行性。     

信息物理融合系统的动态多优先级调度

信息物理融合系统(Cyber-physical Systems,CPS)的复杂和异构性给设计者带来了不少挑战,其中任务的多样性使得传统的调度策略不能满足CPS的性能需求.提出了专门针对基于大规模传感器网络的CPS的动态多优先级调度策略.根据任务类型分配4级缓存队列:第1级是来自控制器待处理的实时任务,拥有最高的可抢占式优先级;第2级是来自控制器待转发的实时任务,拥有次高的可抢占式优先级;第3级是来自其他节点待转发的非实时任务,拥有第三高的非抢占式优先级;第4级是来自本地待发送的非实时任务,拥有最低的非抢占式优先级.设计了抢占与非抢占混合的动态调度策略来减少任务的平均等待时间,加入了等待时间阈值机制来保证第4级任务的公平性.通过理论分析和仿真实验对调度策略的性能做了评价.仿真结果显示,动态多优先级调度策略在提高系统性能和稳定性上要优于传统优先级调度.     

引入虚拟特征参数的混合实时任务调度及应用

提出了在实时环境下周期任务与非周期任务混合调度的一种新方法。引入非周期实时任务虚拟截止期、虚拟周期的特征参数,综合考虑各实时任务的多特征参数进行优先级设计,克服了单独考虑任务的个别参数以及忽略非周期任务自身特征的调度策略的局限性及调度风险,且能够尽可能地加快非周期任务的响应速度,提高系统整体的调度性能。将该方法在RT-Linux实时环境中实现,并针对无人飞艇的自动驾驶仪进行了任务实例的可调度性测试,证明了该调度策略的可行性。     

System level fixed priority energy management algorithm for embedded real time application

Dynamic power management (DPM) and dynamic voltage scaling (DVS) are crucial techniques to reduce the energy consumption in embedded real-time systems. Many previous studies have focused on the energy consumption of the processor or I/O devices. In this paper, we focus on the problem of energy management integrating DVS and DPM techniques for periodic embedded real-time applications with rate monotonic (RM) policy and present a system level fixed priority energy-efficient scheduling (SLFPEES) algorithm. The SLFPEES algorithm consists of I/O device scheduling and job scheduling. I/O device scheduling is based on the dynamic power management with rate monotonic (DPM-RM) policy which puts devices into the sleep state when the idle interval is larger than devices break even time. Job scheduling is based on the RM policy and uses stack resource protocol (SRP) to guarantee exclusive access to the shared resources. For energy efficiency, the SLFPEES algorithm schedules the task with a lower speed and a higher speed. The experimental result shows that the SLFPEES algorithm can yield significantly energy savings with respect to the existing techniques.     

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

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

面向对象实时多任务系统的优化实现模型

论文提出了一种基于抢占门限的实时多任务系统的优化实现模型,它同时具有低开销与高可调度性。该模型扩展了固定优先级调度模型,同时通过实现模型中线程数的减少实现了运行时的低开销。文中同时也讨论了互不抢占分组的实现算法及每个任务最大抢占门限的分配算法。     

无线传感器网络异步任务集双效节能延迟调度算法研究

深亚微米技术的发展,使得漏电功耗在CMOS电路总功耗中所占比重日益增大,传统的传感器节点CPU节能研究主要针对动态功耗,其能耗估计和优化方法已凸显局限.针对此问题,提出动态电压调节(DVS)和动态功耗管理(DPM)相结合的双效节能延迟调度算法.从相对截止期小于等于周期的异步实时任务调度出发,结合DVS技术,综合考虑动态功耗和漏电功耗的影响,在满足任务实时性的前提下,选取每个任务的CPU执行速度,以降低总能耗,并通过任务的延迟调度对CPU空闲时段加以合并,采用DPM方法使CPU在空闲时段有选择性的进入低功耗状态,从而进一步降低漏电能耗.仿真实验验证了该算法的有效性.     

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).     

Cache-Conscious Limited Preemptive Scheduling

In multi-tasking real-time systems, inter-task cache interference due to preemptions degrades schedulability as well as performance. To address this problem, we propose a novel scheduling scheme, called limited preemptive scheduling (LPS), that limits preemptions to execution points with small cache-related preemption costs. Limiting preemptions decreases the cache-related preemption costs of tasks but increases blocking delay of higher priority tasks. The proposed scheme makes an optimal trade-off between these two factors to maximize the schedulability of a given task set while minimizing cache-related preemption delay of tasks. Experimental results show that the LPS scheme improves the maximum schedulable utilization by up to 40\% compared with the traditional fully preemptive scheduling (FPS) scheme. The results also show that up to 20\% of processor time is saved by the LPS scheme due to reduction in the cache-related preemption costs. Finally, the results show that both the improvement of schedulability and the saving of processor time by the LPS scheme increase as the speed gap between the processor and main memory widens.     

Energy-aware mixed partitioning scheduling in standby-sparing systems

Previous standby-sparing techniques assume that all tasks don't access to shared resources. In addition, primary tasks and backup tasks are allocated to the primary processor and spare processor respectively. Spare processor schedules tasks with maximum processor speed. Unlike previous techniques, we have studied the problem of minimizing energy consumption and preserving the original reliability for dynamic-priority real-time task set with shared resources in a standby-sparing system. We propose a novel energy-aware mixed partitioning scheduling algorithm (EAMPSA). Earliest deadline first/dynamic deadline modification (EDF/DDM) scheduling scheme is used to ensure that the shared resources can be accessed in a mutual exclusive manner. Uniformly speed is used to the primary processor and the spare processor. In addition, we use the mixed mapping partitioning of primary and backup tasks method to map tasks. A novel method of mapping task is proposed i.e. the tasks which need to access to shared resources are mapped into the primary processor and the tasks which have no resource requirements are mapped into the spare processor. Furthermore, DVS and DPM techniques are used for both primary and backup tasks to save energy. The experimental results show that the EAMPSA algorithm consumes average 55.43% less energy than that of the SSPT algorithm.     

Power-aware fixed priority scheduling for sporadic tasks in hard real-time systems

In this paper, we consider the generalized power model in which the focus is the dynamic power and the static power, and we study the problem of the canonical sporadic task scheduling based on the rate-monotonic (RM) scheme. Moreover, we combine with the dynamic voltage scaling (DVS) and dynamic power management (DPM). We present a static low power sporadic tasks scheduling algorithm (SSTLPSA), assuming that each task presents its worst-case work-load to the processor at every instance. In addition, a more energy efficient approach called a dynamic low power sporadic tasks scheduling algorithm (DSTLPSA) is proposed, based on reclaiming the dynamic slack and adjusting the speed of other tasks on-the-fly in order to reduce energy consumption while still meeting the deadlines. The experimental results show that the SSTLPSA algorithm consumes 26.55–38.67% less energy than that of the RM algorithm and the DSTLPSA algorithm reduces the energy consumption up to 18.38–30.51% over the existing DVS algorithm.