一种新的实时多处理器系统的动态调度算法

实时多处理器系统的动态调度算法一直是实时系统研究中的重要课题,而评价实时调度算法性能的一个最重要的指标是调度成功率.在近视算法的基础上提出了一种新的实时多处理器系统的动态调度算法--节约算法.在该算法中,提出了一个新的处理器选择策略,从而提高了算法的调度成功率.同时,为了研究节约算法的有效性,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与近视算法的调度成功率进行了比较.模拟结果显示,节约算法的调度成功率要优于近视算法.     

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

基于分批优化的实时多处理器系统的集成动态调度算法

提出了一种基于分批优化的实时多处理器系统的集成动态调度算法，该算法采用在每次扩充当前局部调度时，通过对所选取的一批任务进行优化分配的策略以及软实时任务的服务质量QoS（quality of service）降级策略，以统一方式实现了对实时多处理器糸统中硬、软实时任务的集成动态调度．进行了大量的模拟研究，结果表明．在多种任务参数取值下，新算法的调度成功率均高于近视算法（Myopic Algorithm）．     

实时异构系统的动态分批优化调度算法

提出了一种实时异构系统的动态分批优化调度算法,该算法采用的是在每次扩充当前局部调度时,按一定规则在待调度的任务集中选取一批任务,对该批任务中的每项任务在每个处理器上的运行综合各种因素构造目标函数,将问题转化为非平衡分配问题,一次性为这些任务都分配一个处理器或为每个处理器分配一项任务,使得这种分配具有最好的“合适性”,以增大未被调度任务的可行性.这种方法有效地提高了算法调度成功率.同时,为了评估该算法的性能,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与老算法的调度成功率进行了比较.模拟结果显示,新算法优于老算法.     

基于多处理机的混合实时任务容错调度

提出了一种混合实时任务容错调度算法．该算法采用Rate Monotonic(RM)算法完成周期任务的静态调度；采用预订处理机时间方法和Earlier Deadline First(EDF)算法动态调度非周期任务；采用主／副版本备份技术确保系统的容错能力．通过充分利用周期任务的剩余处理机时间调度非周期任务和主动备份与被动备份相结合的方法有效地减少了处理机数．仿真结果证明了算法的有效性．     

Towards a Hybrid Dynamic Logic for Hybrid Dynamic Systems

We introduce a hybrid variant of a dynamic logic with continuous state transitions along differential equations, and we present a sequent calculus for this extended hybrid dynamic logic. With the addition of satisfaction operators, this hybrid logic provides improved system introspection by referring to properties of states during system evolution. In addition to this, our calculus introduces state-based reasoning as a paradigm for delaying expansion of transitions using nominals as symbolic state labels. With these extensions, our hybrid dynamic logic advances the capabilities for compositional reasoning about (semialgebraic) hybrid dynamic systems. Moreover, the constructive reasoning support for goal-oriented analytic verification of hybrid dynamic systems carries over from the base calculus to our extended calculus.     

实时多处理器系统中基于能量节约的动态调度算法

当前处理器由于较高的能量消耗。导致处理器热量散发的提高及系统可靠性的降低，已经成为目前计算机领域较为关心的问题．然而目前一些有效降低能量消耗的技术大多针对单处理器系统，较少考虑多处理器系统．本文提出的调度算法针对多处理器系统，以最短任务优先调度为基础，结合其它有效技术，如共享空闲时间回收等，使得实时任务在其截止期内完成的同时能够有效地减低整个系统的能量消耗．针对独立任务集及具有依赖关系的任务集，本文提出两种算法：STFBA1及STFBA2（Shortest Task First—Based Algorithm）．与目前所知的有效算法相比，我们的算法具有更好的性能（调度长度及能量消耗）．     

实时多处理器系统的动态分批优化调度算法

提出了一种实时多处理器系统的新的高效动态调度算法--动态分批优化调度算法,该算法突破了以往算法中一次只安排一项任务的做法,采用在每次扩充当前局部调度时,按一定规则在待调度的任务集中选取一批任务,对该批任务中的每项任务在每个处理器上运行构造目标函数,将问题转化为非平衡分配问题,一次性为这些任务都安排一个处理器或为每个处理器安排一项任务,使得这种安排具有最好的"合适性",以增大未安排任务的可行性.这种方法极大地提高了算法的调度成功率.同时,为了研究该算法的有效性,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与节约算法的调度成功率进行了比较.模拟结果显示,在节约算法的调度成功率小于10%的约束条件下,该算法的调度成功率大于90%,说明新算法的优势是非常明显的.     

Scheduling of Time-Triggered Real-Time Systems

Thispaper introduces a new class of applications for constraint programming.This new type of application originates out of a special classof real-time systems, enjoying increasing popularity in areassuch as automotive electronics and aerospace industry. Real-timesystems of this kind are time triggered in the sense that theiroverall behavior is globally controlled by a recurring clocktick. Being able to compute an appropriate pre-runtime scheduleautomatically is the major challenge for such an architecture.What makes this specific off-line scheduling problem somewhatuntypical is that a potentially indefinite, periodic processinghas to be mapped onto a single time window. In this article wewill show how this problem can be solved by constraint programmingand we will describe which techniques from traditional schedulingand real-time computing led to success and which failed whenconfronted with a large-scale application of this type. The techniquesthat proved to be the most successful were special global constraintsand an elaborate search heuristics from Operations Research.Also for finding a valid schedule mere serialization is shownto be sufficient. The actual implementation was done in the concurrentconstraint programming language Oz.     

异构实时多处理器系统的动态调度算法研究

实时多处理器系统的动态调度算法一直是实时系统中的重要研究课题.根据异构实时多处理器的特点,提出了一种新的异构实时动态调度算法P_IEFT.该算法采用了一个新的处理器分配策略——将任务分配到能最早完成任务的处理器上.该策略能够缩短调度长度,提高后继任务被接受的可能性,从而能够提高成功调度率.模拟结果表明,该调度算法的成功调度率高于近视算法和节约算法的成功调度率.     

基于简单反馈的混合静态/动态节能弱硬实时调度算法

随着能耗问题目益显著,节能实时调度成为实时调度领域研究的热点.由于混合静态/动态节能弱硬实时调度算法基于最坏情况执行时间计算任务的执行速度,因此限制了节能效果,文中针对这一问题,提出一种新算法,通过引入简单反馈机制,估计任务的实际执行时间,通过任务划分,降低任务的整体执行速度,延长执行时间,进而达到高效节能的目的.实验表明,当平均情况执行时间低于最坏情况执行时间较多时,新算法优于原始算法,最多可节能60%～70%,最少可节能约10%.算法的不足之处在于当平均情况执行时间接近最坏情况执行时间时,新算法比原算法更耗能.     

一种基于分组与适当选取策略的实时多处理器系统的动态调度算法

在分析了近视算法和节约算法缺点的基础上，提出了一种新的实时多处理器系统的动态调度算法——分组适度算法．分组适度算法包括两个策略：分组策略和适当选取策略．分组策略是为了提高资源的利用率，在保证具有较小目标函数值的任务截止期限的情况下，优先选择可以共享访问资源的任务进行扩展．适当选取策略是为了提高处理器的利用率，当任务不访问资源以及任务所需资源的最早可用时间小于系统中处理器的最小最早可用时间时，选择最早可用时间最小的处理器；否则，选择最早可用时间最接近资源的最早可用时间的处理器．模拟结果表明，分组适度算法的任务接受率高于近视算法和节约算法的任务接受率．     

一种实时异构系统的集成动态调度算法

提出了一种实时异构系统的集成动态调度算法.该算法通过一个新的任务分配策略以及软实时任务的服务质量QoS(quality of service)降级策略,不仅以统一方式完成了对实时异构系统中硬、软实时任务的集成动态调度,而且提高了算法的调度成功率.同时,还进行了大量的模拟研究.这些模拟以传统的近视算法为基准,将其应用在实时异构系统集成动态调度时的调度成功率与新算法进行比较,模拟结果表明,在多种任务参数取值下,新算法的调度成功率均高于传统的近视算法.     

一种批优化调度策略的实时异构系统的集成动态调度算法

针对实时异构多任务调度的特点,提出了软、硬实时任务形式化描述非精确计算的统一任务模型,在此基础上,提出了一种基于批优化调度策略的实时异构系统的集成动态调度算法.该算法以启发式搜索为基础,引入软实时任务服务质量降级策略,在每次扩充当前局部调度时,按制定的规则选取一批任务,计算其在各处理器上运行的目标函数,采用指派问题解法对任务优化分配.模拟实验表明,该算法与同类算法相比,提高了调度成功率.     

基于多传感器的控制系统实时调度算法

将简单反馈控制与任务准入/回归、可达/夭折等策略相结合,设计新的动态调度框架。在此基础上,综合截止期、关键度和最坏执行时间3种特征参数,提出基于反馈控制的混合策略调度算法,该算法也适用于对任务的其他多种特征参数的综合。从截止期错失率、错失任务平均关键度和CPU有效利用率3个方面,分析算法的性能。实验结果表明,该算法在混合任务和动态负载下与最早截止期优先和最高价值优先算法相比具有更好的性能。     

混合动态系统的稳定性

讨论混合动态系统（HDS）的稳定性问题。首先给出关于HDS的稳定性、可吸收性和渐近稳定性的几个结论,然后给出关于HDS的Lyapunov稳定性定量。     

基于软件容错的动态实时调度算法

在硬实时系统中，由于任务超时完成将会导致灾难性后果，因而硬实时系统具有严格的时间及可靠性限制条件．目前实时容错调度算法大多针对硬件的容错，很少考虑软件运行的故障．提出了一种类似EDF的软件容错的动态实时调度算法PKSA(Probng-step Algorithm)，本算法在任务执行过程中，通过若干试探性检测步骤，提高了任务可执行性的预测，尽可能地避免了任务早期的失败对后续任务的影响，因此提高了任务的完成率，并同时有效地减少了浪费的CPU时间片．通过实验测试．同目前所知的同类算法相比，具有更佳的调度性能-调度成本比.     

基于软件容错的动态实时调度算法

在硬实时系统中,由于任务超时完成将会导致灾难性后果,因而硬实时系统具有严格的时间及可靠性限制条件.目前实时容错调度算法大部分针对硬件的容错,很少考虑软件运行的故障.提出了一种类似EDF基于软件容错的动态实时调度算法EBPA(expectation-based probing algorithm),该算法在任务执行过程中通过基于期望值的若干试探性检测步骤,提高了任务可执行性的预测,尽可能避免了任务早期的错误对后续任务的影响,因此提高了任务的完成率并同时有效地减少了浪费的CPU时间片.通过实验测试,同目前所知的同类算法相比,具有更佳的调度性能-调度成本比.     

硬实时系统中基于软件容错的动态调度算法

在硬实时系统中,由于任务超时完成将会导致灾难性后果,因而硬实时系统具有严格的时间及可靠性限制条件.目前实时容错调度算法大部分针对硬件的容错,很少考虑软件运行的故障.提出了两种类似EDF(earliest deadline first)的软件容错的动态实时调度算法:PKSA(probing K-step algorithm)和CUBA(changing utilization-based algorithm).两种算法在任务执行过程中,通过若干试探性检测步骤,提高了任务可执行性的预测,尽可能地避免了任务早期的失败对后续任务的影响,因此提高了任务的完成率,同时也有效地减少了浪费的CPU时间片数量.通过实验测试,与目前所知的同类算法相比,具有更佳的调度性能--调度成本平衡性.     

混杂系统的存在与研究

混杂系统（HDS）是由连续变量动态系统（CVDS）与离散事件动态系统（DEDS）共同组成的大型动态系统。随着CIMS的兴起与发展，人们应该关注HDS的建模、分析与优化运行。本文通过分析实例介绍了HDS的存在、特征与研究前景。