Energy-Efficient Scheduling in Distributed Real-Time Computing Systems

Journal of Computer and Systems Sciences International - Scheduling in multichannel distributed information processing systems is studied. The problem is solved for systems-on-a-chip and is...     

Fixed-Priority Allocation and Scheduling for Energy-Efficient Fault Tolerance in Hard Real-Time Multiprocessor Systems

Energy-efficient task allocation and scheduling schemes with deterministic fault-tolerance capabilities are proposed for symmetric multiprocessor systems executing tasks with hard real-time constraints. The proposed heuristic is proven to achieve energy savings by optimally balancing application workload among processors in a system. Based on the observation that fault-free operation is expected to remain dominant in the near future and the probability of the worst case faults is low, an optimistic fault-tolerant heuristic is then proposed to achieve maximum energy savings in the absence of faults while degrading gradually to meet application timing requirements in the worst case of faults. Simulation results show that compared to state-of-art allocation and scheduling schemes proposed heuristic achieves average energy savings of up to 70%. It is also shown that optimistic approach is more resilient to variations in application utilizations and fault occurrences beyond system specifications.     

基于（m，k）模型的任务可调度性分析

（m，k）模型是降低系统负载的一种有效方法。EDF算法由于其灵活性和自适应性而得到广泛应用。针对EDF算法，首先研究并给出了基于（m，k）模型的任务集可调度的必要条件和充分条件，然后给出了基于（m，k）模型的任务最大响应时间的一种新的计算方法。     

PLUFS: 一种开销敏感的周期任务在线多处理器节能实时调度算法

现有周期任务多处理器节能调度算法虽然在考虑处理器实际开销情况下可以实现较好的节能效果,但仍不能保证最优可调度性.针对嵌入式实时系统中不可忽视的状态切换开销,提出一种开销敏感的周期任务在线多处理器节能实时调度算法PLUFS.该算法通过TL面流调度模型与处理器实际切换开销模型相结合,在每个TL面的初始时刻、任务结束执行时刻实现节能调度,在不违反周期任务集最优可调度性的前提下,达到实时约束与能耗节余的合理折中.经过理论证明和模拟实验,结果表明：PLUFS算法不仅保证了周期任务集的最优可调度性,而且节能效果整体优于现有算法,能耗节余比现有算法提高约10%～20%.     

基于(m,k)-firm约束规范的混合任务调度算法研究

讨论了在准实时环境下,包括准实时周期任务和准实时非周期任务在内的混合任务调度算法HTSF.HTSF算法是在满足周期任务(m,k)-firm 约束规范的前提下提高非周期任务可调度性,同时合理利用可用空闲时间,提高整个系统的服务质量.HTSF算法给出了非周期任务的可调度性分析方法,同时采用静态调度与动态调度相结合的方法调度周期任务和非周期任务.模拟测试结果显示,系统对非周期任务的接收率比同类相关算法的接收率高.     

多核系统中基于动态电压频率调节的实时节能调度研究

在实时嵌入式领域,特别是无线移动和便携式计算领域,能耗是首要考虑的因素,这也是多核处理器尚未在嵌入式领域全面展开应用的首要因素。目前针对多核系统的实时应用,基于动态电压频率调节(DVFS)的实时节能调度技术研究得较少,还有许多问题亟待解决。本文介绍了多核系统中动态电压频率调节技术,分析讨论了当前多核系统中实时调度研究进展,主要针对同构多核、异构多核、并行任务模型和弱硬实时模型等方面,深入探讨了多核系统中基于DVFS的实时节能调度。本文结合多核系统、电压频率动态调节节能和实时调度,探索了多核系统中的实时节能调度,奠定了理论和技术基础,具有重大的理论意义和现实应用价值。     

基于滚动优化的虚拟云中实时任务节能调度方法

目前,节能已成为云数据中心的研究热点.建设节能的云数据中心不仅可以减少用电消耗,而且可以提高系统的可靠性.现有的云中心节能调度算法缺乏在任务调度级别的考虑,使得任务执行效果受到较大影响.为此,首先给出了一种基于滚动优化的实时任务调度器结构,然后详细分析和构建了任务能量消耗模型.在此基础上提出了一种实时非周期任务节能调度算法EARH(energy-aware scheduling algorithm).EARH采用的滚动优化策略能够被拓展并集成其他节能调度算法.此外,提出了资源动态增加与缩减策略,用于在系统可调度性与节能两方面进行权衡.最后,通过大量的模拟实验验证了EARH的性能.与其他3种基准算法相比,其实验结果表明,EARH的调度质量优于其他算法,可有效提高系统性能.     

A Distributed Scheduling Algorithm for Real-Time Communication on Slotted Shared Medium

Algorithms for arbitrating and scheduling transmissions from different transmitters sharing a common access medium arise often in the design of many shared and distributed systems. In this paper we present a distributed algorithm for arbitrating time-constrained transmissions on slotted shared access media. The two most important distinguishing features of our algorithm are: (1) unlike most of the other schemes that guarantee on-time transmission over shared media by centralized preallocation of slots, our algorithm is fully distributed and completely on-line; (2) it eliminates one of the common pitfalls of all slotted systems, that is, allocation in integral multiples of full slots. We derive sufficient conditions for schedulability and show that the proposed scheme achieves high levels of schedulable utilization. We also show that the schedulable utilization increases as the length of the allocation cycle increases and asymptotically approaches the maximum achievable utilization. We present a distributed slot access protocol to realize the proposed algorithm for ring architecture. The protocol can be easily modified for other topologies, such as bus and dual-bus networks. Using illustrative examples we demonstrate the effectiveness of the algorithm.     

实时系统调度算法的优化设计

文章介绍了Linux操作系统实时调度算法的简化模型,并提出了一种优化改进调度算法。该算法以进程的重要性为基础,兼顾截止期内完成进程的紧迫程度,建立了进程的优先级队列。算法可通过双链表来实现。对比实验结果表明,优化后的算法与优化前相比,特别是CPU正常负载时,可以实现更高的价值完成率和进程完成率,从而有效地提高了操作系统的实时性能。     

端到端(p,k)约束流的实时通讯

端到端系统的实时服务保证问题是当前广泛研究的问题。由于许多端到端应用可以容忍部分报文丢失,因此将窗口约束引入到端到端系统实时服务保证中,但是现有的端到端实时调度算法仅从固定窗口约束出发来保证实时服务,导致其在重度过载情况下性能下降显著。从基于可变窗口的（p,k）约束的角度出发保证实时数据流通过一系列服务器达到目的地的实时服务质量,提出了多跳K窗口约束调度（Multi—hop K—Window Constraint Scheduling,M—KWCS）算法,使其在重度过载下服务质量退化缓慢。实验表明M—KWCS算法在重度过载情况下的性能优于其它各类算法。     

Garbage Collector Scheduling in Dynamic, Multiprocessor Real-Time Systems

We consider garbage collection (GC) in dynamic, multiprocessor real-time systems. We consider the time-based, concurrent GC approach and focus on real-time scheduling to obtain mutator timing assurances, despite memory allocation and garbage collection. We present a scheduling algorithm called GCMUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, stochastic execution-time and memory demands, and overloads. We establish that GCMUA probabilistically lower bounds each mutator activity's accrued utility, lower bounds the system-wide total accrued utility, and upper bounds the timing assurances' sensitivity to variations in mutator execution-time and memory demand estimates. Our simulation experiments validate our analytical results and confirm GCMUA's effectiveness.     

Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems

The utilization bound for earliest deadline first (EDF) scheduling is extended from uniprocessors to homogeneous multiprocessor systems with partitioning strategies. First results are provided for a basic task model, which includes periodic and independent tasks with deadlines equal to periods. Since the multiprocessor utilization bounds depend on the allocation algorithm, different allocation algorithms have been considered, ranging from simple heuristics to optimal allocation algorithms. As multiprocessor utilization bounds for EDF scheduling depend strongly on task sizes, all these bounds have been obtained as a function of a parameter which takes task sizes into account. Theoretically, the utilization bounds for multiprocessor EDF scheduling can be considered a partial solution to the bin-packing problem, which is known to be NP-complete. The basic task model is extended to include resource sharing, release jitter, deadlines less than periods, aperiodic tasks, non-preemptive sections, context switches, and mode changes.     

一种新的异构实时分布式系统的容错调度算法

一般来说,异构分布式实时系统中任务的周期并不完全相同且任务的时限不等于它们的周期,同时系统中还有一些无容错需求的任务.因此现有的任务调度算法一般不能满足这些要求.针对这类系统,在结合基版本/副版本技术和EDF算法的基础上,给出了一种新的容错调度算法.该算法由两部分组成：任务分配调度算法和单处理器调度算法.对于单处理器调度算法,本文采用了EDF算法;在此基础上,给出一种启发式静态任务分配算法.分析了系统的可调度性,给出了任务可调度条件和基版本/副版本时限的设置方法.仿真结果表明,这种算法是有效的.     

一种同构多处理机动态实时调度算法

本文提出一种新型线性复杂度多处理机实时任务启发式调度算法,利用并行技术为动态实时系统提供较优解．使用大量存在可行调度的任务集合测试多处理机实时任务调度算法的性能,分析了几种主要参数对调度成功率的影响．实验表明新调度算法调度成功率较高,适用于不完全知晓任务参数的动态多处理机实时系统．     

一种动态可重构系统的实时任务调度算法

硬件任务的软实时调度是影响动态可重构系统性能的关键因素之一。本文提出了一种基于顶点链表的硬件任务间最小空间调度算法MSSA,该算法将硬件任务按照长、宽及调度时间构成一个三维资源模型,以到达任务与已放置任务在三维空间的邻接度来构建代价函数,获取具有最大代价函数值的放置位置和启动时间,可使任务安排得更紧凑,减小对系统资源的浪费,提高并行度。仿真实验表明,与MSG-4V和Stuffing算法相比,本文算法具有更高的芯片利用率和任务接受率。     

一种实时异构嵌入式系统的任务调度算法

异构分布式系统已被广泛应用在实时嵌入式系统中,而调度算法是在进行嵌入式系统综合时,确保系统实现性能目标的一个关键问题,这是一个NP-完全问题.现有的算法主要是启发式算法,性能还有待提高.提出了一个异构分布式系统的动态BLevel优先(dynamic BLevel first,简称DBLF)算法,算法选择就绪任务中动态BLevel值最大的任务进行调度,用插入法为任务分配处理器,遵循以下3个插入原则:满足任务先后顺序关系;任务的最早完成时间(earliest-finish-time,简称EFT)最小;在EFT相等时,优先分配到利用率较低的处理器上.与现有算法比较可以看出,DBLF算法可以有效降低调度长度.     

基于 Linux的实时控制系统的调度算法研究

在实时系统中,实时调度算法是影响实时性能的关键因素。本文首先分析了当前基于Linux的内核实时支持的相关主流技术,说明了Linux在实时性支持上的现状和弱点,综合比较了各种解决方案的优缺点。以往对实时调度算法的研究着重于硬实时性的满足,本文基于具体应用的特殊性以及当前对实时调度研究的发展趋势,对共存于同一系统中的
的周期性实时任务和非周期性任务的混合调度问题做进一步的探讨,提出一种实时任务的层次调度算法,保证了带宽的利用,克服了传统混合调度算法处理器利用率受限制、系统开销较大和非周期部分响应时间长的问题。基于这些研究成果,提出了改造方案,并在Linux操作系统中予以了实现。     

强实时系统静态优先级调度的可调度性分析

文章在系统阐述和借鉴经典的强实时系统静态优先级调度理论的基础上,通过引入忙周期的概念,分析了任务时限超过任务周期的实时系统任务集的可调度特性,拓宽了该理论的应用范围,更有利于实时系统的设计者对任务的运行时间行为进行事前分析与预测。     

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

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

一种开放混合实时系统的开放自适应调度算法

开放计算环境下的实时与非实时任务不确定并发,以及多种实时约束混合的复杂约束系统,即开放混合实时系统的需求越来越广泛.通过引入接收控制、调度服务器、自适应调节机制,提出一种开放环境下的自适应实时系统调度架构--OARtS(open adaptive real-time scheduling).它能适应开放计算环境的不确定性,有控制地接受实时任务运行;可根据系统空闲计算带宽变化,自适应地调节任务的实时等级,使得系统运行在最优的实时性能上;对于软实时任务,可根据其计算带宽需求变化,自适应地调节其计算带宽分配,以适应任务执行时间时变引起的实时不确定性.