无线传感器网络操作系统调度策略

提出了一种在无线传感器网络操作系统中可以同时针对周期性任务和非周期性任务进行抢占式调度操作的EF-RM调度策略。在无线传感器节点上执行的任务负载较重的情况下,该调度策略可以保证重要任务的优先执行,此外当无线传感器节点空闲时,通过将节点带入睡眠状态,实现无线传感器节点的节能。所提出的任务调度策略在TinyOS上进行实现,并通过实验测试得出,在总能耗代价增加较少的情况下可以有效地提高系统在较重负载情况下的响应性能。     

异构集群系统中安全关键实时应用调度研究

在集群系统中,为有安全需求的实时应用提供安全保障得到了广泛关注,但将实时应用的安全需求与调度算法相结合的研究并不多.文中提出了一种异构集群系统中安全关键实时应用的2阶段调度策略--TPSS.该策略综合考虑了任务的安全需求与时间限制.在TPSS的第1阶段,提出了一种自适应调度算法DSRF,当系统负载较重时,DSRF算法能在保证任务安全需求的基础上,通过降低新到任务和等待队列中任务的安全级别来提高任务的调度成功率.相反,当系统负载较轻时,DSRF算法能在保证系统具有较高调度成功率的基础上充分利用任务在截止期前的空闲时间提高新任务的安全级别.在TPSS的第2阶段,提出了一种新的算法FMSL,用来为所接收任务提供较为公平的安全服务,同时进一步提高了任务的整体安全级别.文中通过大量的模拟实验对TPSS策略与DSRF算法、SAEDF算法和RF算法进行了比较.实验结果表明,TPSS策略优于其它方法,使系统具有较强的安全性与灵活性.     

云环境下的基于Min-Max的节能资源调度算法的研究

针对云计算环境下的高能耗问题,从系统节能的角度提出一种节能资源调度算法(energy-saving scheduling algorithm based on min-max,ESSAMM)。在Min-Max算法的基础上综合考虑了用户对于任务期望的完成时间和能量消耗两个因素,以节省任务执行过程中产生的能量消耗,并提高用户的时间QoS满意度,实现负载均衡。将任务集合中各任务按照长度从小到大排序,并根据时间QoS为该集合中长度最大和最小的任务选出符合用户期望的物理资源;根据能量估算模型,计算出这两个任务在各物理机上的执行能耗;选择最小能耗对应的物理机来执行该任务;将这两个任务在任务集合中删除,并重复上述过程,直到任务集合为空。仿真结果表明,相比于Min-Max和Min-Min资源调度算法,该算法能够有效降低系统执行任务产生的总能耗,提高用户时间服务质量,并实现调度系统负载均衡。     

多处理器系统可靠性约束下的节能调度算法

针对多处理器系统中随机到达的任务,设计了可靠性约束下的节能调度算法(ESACR)。该算法在满足任务截止期限的前提下选择一个预计产生能耗最小的处理器以节能,在单个处理器上运用最早截止期限优先策略进行调度并尽量使各个任务的执行电压/频率均衡,当新到任务在处理器上不能满足截止期限要求时则逐个调高前面未执行任务的电压/频率。同时,为保证系统的可靠性,ESACR给正在执行的任务预留错误恢复时间以保证当发生瞬时错误时该任务能被恢复。实验结果表明,与最高电压节能调度(HVEA)、最小能耗最小完成时间调度(ME-MC)、最早完成时间优先调度(EFF)相比,ESACR在保证系统可靠性的前提下节能效果最好。     

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

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

EPTS:一种实时动态电压调整的抢占阈值调度器

低功耗目前已成为嵌入式实时系统设计中非常重要的性能需求。动态电压调度DVS机制通过动态调整处理器电压进而有效降低系统功耗,正在逐渐得到广泛应用。抢占阈值调度策略实现双优先级系统,每个任务具有两个优先级,任务优先级被用于任务之间竞争处理器,而抢占阈值作为任务开始运行后实际使用的优先级,从而减少现场切换次数,降低系统功耗,同时也提高整个任务集合的可调度性。本文提出一种在线节能调度算法EPTS,拓展抢占阈值调度模型,在任务执行过程中动态调节处理器电压,力求在保证任务集合可调度性的前提下尽可能减少系统功耗,提高系统性能。而后在AMDAthlon4处理器和RT-Linux平台上实现了EPTS调度器,实验证明对于实际任务集合能够有效节能,提高了处理器的利用率,改善了RT-Linux的实时性能。     

多核系统中基于Global EDF 的在线节能实时调度算法

随着多核系统能耗问题日益突出,在满足时间约束条件下降低系统能耗成为多核实时节能调度研究中亟待解决的问题之一.现有研究成果基于事先已知实时任务属性的假设,而实际应用中,只有当任务到达之后才能够获得其属性.为此,针对一般任务模型,不基于任何先验知识提出一种多核系统中基于Global EDF在线节能硬实时任务调度算法,通过引入速度调节因子,利用松弛时间,结合动态功耗管理和动态电压/频率调节技术,降低多核系统中任务的执行速度,达到实时约束与能耗节余之间的合理折衷.所提出的算法仅在上下文切换和任务完成时进行动态电压/频率调节,计算复杂度小,易于在实时操作系统中实现.实验结果表明,该算法适用于不同类型的片上动态电压/频率调节技术,节能效果始终优于Global EDF算法,最多可节能15％～20％,最少可节能5％～10％.     

异构云环境下的密码服务调度方法

针对云计算环境下存在密码服务请求算法种类多、资源需求差异化和节点性能异构等问题。为了提高系统的可靠性,保证服务质量,综合考虑用户请求任务和处理节点等多种因素,在作业包截止时间的基础上,通过任务映射策略完成密码服务的一级调度。设计一个基于用户优先级和任务等待时间的任务优先级调度算法实现二级调度,从而构造一种同时支持多种密码服务请求和任务动态可调整的调度系统框架,以保证云环境下任务的时效性。仿真结果表明,该系统有较好的执行效率和负载分布效果,达到设计目标。与随机法和遗传算法相比,其执行效率分别提高了17%和11%左右。     

抢占阈值调度的功耗优化

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

一种基于同构多核处理器的动态节能调度算法

在节能计算系统中节能调度是一个重要的研究方向。目前针对节能调度的研究中,多从动态电压频率调节（DVFS）的角度进行。但是随着芯片制造工艺的改进,处理器核心电压越来越低,所能调节的电压范围越来越小,通过DVFS技术实现节能遇到了理论上的瓶颈。提出了一种基于同构多核处理器的动态节能调度算法。在系统负载较轻的情况下,通过将系统任务分配到较少的处理核心上而使其他处理核心处于休眠状态来达到动态节能的效果。实验表明该算法具有较好的节能效果。     

Adaptive energy-efficient scheduling for real-time tasks on DVS-enabled heterogeneous clusters

Developing energy-efficient clusters not only can reduce power electricity cost but also can improve system reliability. Existing scheduling strategies developed for energy-efficient clusters conserve energy at the cost of performance. The performance problem becomes especially apparent when cluster computing systems are heavily loaded. To address this issue, we propose in this paper a novel scheduling strategy–adaptive energy-efficient scheduling or AEES–for aperiodic and independent real-time tasks on heterogeneous clusters with dynamic voltage scaling. The AEES scheme aims to adaptively adjust voltages according to the workload conditions of a cluster, thereby making the best trade-offs between energy conservation and schedulability. When the cluster is heavily loaded, AEES considers voltage levels of both new tasks and running tasks to meet tasks’ deadlines. Under light load, AEES aggressively reduces the voltage levels to conserve energy while maintaining higher guarantee ratios. We conducted extensive experiments to compare AEES with an existing algorithm–MEG, as well as two baseline algorithms–MELV, MEHV. Experimental results show that AEES significantly improves the scheduling quality of MELV, MEHV and MEG.     

Design optimization for security- and safety-critical distributed real-time applications

In this paper, we are interested in the design of real-time applications with security, safety, timing, and energy requirements. The applications are scheduled with cyclic scheduling, and are mapped on distributed heterogeneous architectures. Cryptographic services are deployed to satisfy security requirements on confidentiality of messages, task replication is used to enhance system reliability, and dynamic voltage and frequency scaling is used for energy efficiency of tasks. It is challenging to address these factors simultaneously, e.g., better security protections need more computing resources and consume more energy, while lower voltages and frequencies may impair schedulability and security, and also lead to reliability degradation. We introduce a vulnerability based method to quantify the security performance of communications on distributed systems. We then focus on determining the appropriate security measures for messages, the voltage and frequency levels for tasks, and the schedule tables such that the security and reliability requirements are satisfied, the application is schedulable, and the energy consumption is minimized. We propose a Tabu Search based metaheuristic to solve this problem. Extensive experiments and a real-life application are conducted to evaluate the proposed techniques.     

A multi-objective co-evolutionary algorithm for energy-efficient scheduling on a green data center

Nowadays, the environment protection and the energy crisis prompt more computing centers and data centers to use the green renewable energy in their power supply. To improve the efficiency of the renewable energy utilization and the task implementation, the computational tasks of data center should match the renewable energy supply. This paper considers a multi-objective energy-efficient task scheduling problem on a green data center partially powered by the renewable energy, where the computing nodes of the data center are DVFS-enabled. An enhanced multi-objective co-evolutionary algorithm, called OL-PICEA-g, is proposed for solving the problem, where the PICEA-g algorithm with the generalized opposition based learning is applied to search the suitable computing node, supply voltage and clock frequency for the task computation, and the smart time scheduling strategy is employed to determine the start and finish time of the task on the chosen node. In the experiments, the proposed OL-PICEA-g algorithm is compared with the PICEA-g algorithm, the smart time scheduling strategy is compared with two other scheduling strategies, i.e., Green-Oriented Scheduling Strategy and Time-Oriented Scheduling Strategy, different parameters are also tested on the randomly generated instances. Experimental results confirm the superiority and effectiveness of the proposed algorithm.     

基于模型预测控制的数据中心节能调度算法

如今日益增长的数据中心能耗,特别是冷却系统能耗已日益受到重视,降低系统能耗能够减少数据中心碳排放.提出了一种基于模型预测控制（model prediction control,简称MPC）的节能调度策略,该策略可以有效地减小数据中心冷却能耗.该方法采用动态电压频率调节技术来调整计算节点频率,从而减少节点间的热循环;所有节点的峰值温度可被保持在温度阈值下,在任务的执行中稳态误差较小.该方法可以通过动态频率调节来抑制由于负载类型变化造成的模型不确定性带来的内部扰动,分析结果表明,基于模型预测的温控算法系统开销较小,具有良好的可扩展性.基于该算法设计的控制器能够有效地降低输入温度,提高数据中心能耗效率.通过在实际数据中心内运行的模拟网上书店,该方法与安全最小热传递算法和传统反馈温控算法这两种经典方法相比,无论是在正常条件下还是在扰动存在的情况下都能取得较好的温度抑制效果,系统性能如吞吐率也达到最大.在相同的负载条件下,该方法能够获得最小的输入峰值温度和最小的冷却能耗.     

Energy-efficient deadline scheduling for heterogeneous systems

Energy efficiency is a major concern in modern high performance computing (HPC) systems and a power-aware scheduling approach is a promising way to achieve that. While there are a number of studies in power-aware scheduling by means of dynamic power management (DPM) and/or dynamic voltage and frequency scaling (DVFS) techniques, most of them only consider scheduling at a steady state. However, HPC applications like scientific visualization often need deadline constraints to guarantee timely completion. In this paper we present power-aware scheduling algorithms with deadline constraints for heterogeneous systems. We formulate the problem by extending the traditional multiprocessor scheduling and design approximation algorithms with analysis on the worst-case performance. We also present a pricing scheme for tasks in the way that the price of a task varies as its energy usage as well as largely depending on the tightness of its deadline. Last we extend the proposed algorithm to the control dependence graph and the online case which is more realistic. Through the extensive experiments, we demonstrate that the proposed algorithm achieves near-optimal energy efficiency, on average 16.4% better for synthetic workload and 12.9% better for realistic workload than the EDD (Earliest Due Date)-based algorithm; The extended online algorithm also outperforms the EDF (Earliest Deadline First)-based algorithm with an average up to 26% of energy saving and 22% of deadline satisfaction. It is experimentally shown as well that the pricing scheme provides a flexible trade-off between deadline tightness and price.     

Rolling-horizon scheduling for energy constrained distributed real-time embedded systems

Energy-efficient scheduling approaches are critical to battery driven real-time embedded systems. Traditional energy-aware scheduling schemes are mainly based on the individual task scheduling. Consequently, the scheduling space for each task is small, and the schedulability and energy saving are very limited, especially when the system is heavily loaded. To remedy this problem, we propose a novel rolling-horizon (RH) strategy that can be applied to any scheduling algorithm to improve schedulability. In addition, we develop a new energy-efficient adaptive scheduling algorithm (EASA) that can adaptively adjust supply voltages according to the system workload for energy efficiency. Both the RH strategy and EASA algorithm are combined to form our scheduling approach, RH-EASA. Experimental results show that in comparison with some typical traditional scheduling schemes, RH-EASA can achieve significant energy savings while meeting most task deadlines (namely, high schedulability) for distributed real-time embedded systems with dynamic workloads.     

处理顺序约束的信息物理融合系统静态任务表调度算法

针对异构环境并行计算的静态任务调度问题,以最小化有向无环图 (Directed acyclic graph, DAG)的执行跨度为目标,改变HEFT (Heterogeneous earliest finish time)算法中任务上行权重的计算方法, 获得更加合理的任务顺序排列,提出了一种最早完成时间优先的表调度算法IHEFT (Improvement heterogeneous earliest finish time).该算法在计算任务的上行权重时, 分别计算该任务分配给不同资源的上行权重,取其最小值,比使用所有资源对该任务的平均处理时间进行计算的HEFT算法更为准确. 确定任务的处理顺序后采用最早完成时间越小越优先的策略将任务分配给最优资源,并使得任务的开始执行时间和结束时间满足DAG中有向边的通讯时间约束.通过使用部分文献中的算例数据以及随机生成满足一定结构要求的DAG进行算法测试,将IHEFT与HEFT, CPOP (Critical-path-on-a-processor)和LDCP (Longest dynamic critical path)进行了比较,结果显示IHEFT算法更有效,而且时间复杂度较低.     

Task scheduling for heterogeneous systems using an incremental approach

Effective scheduling of the tasks of a distributed application is one of the key factors in achieving improved performance. It results in an adequate utilization of the underlying resources and also reduces the total execution time of the application. Generating an optimal schedule for a distributed application is not a trivial task as it exists in the class of NP-complete problems. In this paper, a novel strategy called incremental subgraph earliest finish time (INCSEFT) is proposed. It is aimed at scheduling tasks on heterogeneous systems. It incorporates the use of a subgraph that grows incrementally by adding critical paths. At each step, the scheduling strategy attempts to minimize the schedule length. Considering a large set of nodes at an instance makes this approach perform better than other scheduling strategies used for heterogeneous systems. The experiments performed with several graphs show that the INCSEFT strategy produces significant improvement over the well-known HEFT, LOOKAHEAD and CEFT strategies used for scheduling heterogeneous systems.     

Energy-efficient real-time heterogeneous cluster scheduling with node replacement due to failures

Energy preservation in computing systems is an important research topic nowadays. Clusters are usually composed of different hardware with different performance and energy consumption. Performance and efficiency are two metrics introduced in this paper that describe servers’ computational power and energy efficiency, respectively. Based on these metrics, we propose three scheduling policies for hard real-time tasks that are executed on a heterogeneous cluster with power-aware dynamic voltage/frequency scaling processors. Simulation experiments show promising results as compared to those of other existing scheduling policies. In order to study the effects of processor failures, the impact of replacing high-performance processors with high-efficiency processors is studied. Furthermore, the load balancing mechanism used in the system is viewed from an energy perspective.