Improving adaptivity and fairness of processing real-time tasks with QoS requirements on clusters through dynamic scheduling

In this paper, we consider the problem of scheduling a set of independent real-time tasks with QoS requirements on a cluster, in which the adaptivity and fairness are the two important performance metrics. Thereby, we propose a novel scheduling strategy named AFSS that can guarantee: 1) excellent adaptivity, i.e., more real-time tasks can be accepted when the system is in heavy workload, and real-time tasks have high QoS levels when the system is lightly loaded; 2) fairness, i.e., real-time tasks have fair QoS levels to hold smooth processing quality. The GS and LA algorithms in AFSS are discussed and analyzed. Further, several theorems are given to prove the effectiveness of AFSS.     

Power-aware scheduling algorithms for sporadic tasks in real-time systems

In this paper, we consider the canonical sporadic task model with the system-wide energy management problem. Our solution uses a generalized power model, in which the static power and the dynamic power are considered. We present a static solution to schedule the sporadic task set, assuming worst-case execution time for each sporadic tasks release, and propose a dynamic solution to reclaim the slacks left by the earlier completion of tasks than their worst-case estimations. The experimental results show that the proposed static algorithm can reduce the energy consumption by 20.63%–89.70% over the EDF* algorithm and the dynamic algorithm consumes 2.06%–24.89% less energy than that of the existing DVS algorithm.     

Energy-efficient scheduling of real-time tasks with shared resources

This paper explores the energy-efficient scheduling of real-time tasks on a non-ideal DVS processor in the presence of resource sharing. We assume that tasks are periodic, preemptive and may access to shared resources. When dynamic-priority and fixed-priority scheduling are considered, we use the earliest deadline first (EDF) algorithm and the rate monotonic (RM) algorithm to schedule the given set of tasks. Based on the stack resource policy (SRP), we propose an approach, called blocking-aware two-speed (BATS) algorithm, to synchronize the tasks with shared resources and to calculate appropriate execution speeds so that the shared resources can be accessed in a mutual exclusive manner and the energy consumption can be reduced. Particularly, BATS uses a static low speed to execute tasks initially, and then it switches to a high speed dynamically whenever a task blocks a higher priority task. More specifically, the processor runs at the high speed from the beginning of the blocking until the deadline of the blocked task or the processor becomes idle. In order to guarantee that the deadlines of tasks are met, the static low speed and the dynamic high speeds are derived based on the theoretical analysis of the schedulability of tasks. Compared with existing work, BATS achieves more energy saving because its dynamic high speeds are lower than that of existing work and the processor has less chance to execute tasks at the high speeds. The schedulability analysis and the properties of our proposed BATS are provided in this paper. We also evaluated the capabilities of BATS by a series of experiments, for which we have some encouraging results.     

硬实时混合任务在线节能调度技术分析

对混合实时任务节能调度技术进行了分析,深入探讨了目前优秀的硬实时系统在线节能调度算法(OLDVS),指出其存在不足的原因 ,即松弛时间丢失和松弛时间转移。为了提高其节能效果,给出了多种改进思路,为进一步研究工作做出有益的探索。     

Energy efficient scheduling of real-time tasks on multi-core processors with voltage islands

This paper studies energy efficient scheduling of periodic real-time tasks on multi-core processors with voltage islands, in which cores are partitioned into multiple blocks (termed voltage islands) and each block has its own power source to supply voltage. Cores in the same block always operate at the same voltage level, but can be adjusted by using Dynamic Voltage and Frequency Scaling (DVFS). We propose a Voltage Island Largest Capacity First (VILCF) algorithm for energy efficient scheduling of periodic real-time tasks on multi-core processors. It achieves better energy efficiency by fully utilizing the remaining capacity of an island before turning on more islands or increasing the voltage level of the current active islands. We provide detailed theoretical analysis of the approximation ratio of the proposed VILCF algorithm in terms of energy efficiency. In addition, our experimental results show that VILCF significantly outperforms the existing algorithms when there are multiple cores in a voltage island.     

An energy-efficient real-time scheduling scheme on dual-channel networks

The recent evolution of wireless sensor networks have yielded a demand to improve energy-efficient scheduling algorithms and energy-efficient medium access protocols. This paper proposes an energy-efficient real-time scheduling scheme that reduces power consumption and network errors on dual channel networks. The proposed scheme is based on a dynamic modulation scaling scheme which can scale the number of bits per symbol and a switching scheme which can swap the polling schedule between channels. Built on top of EDF scheduling policy, the proposed scheme enhances the power performance without violating the constraints of real-time streams. The simulation results show that the proposed scheme enhances fault-tolerance and reduces power consumption.     

A two-phase scheduling strategy for real-time applications with security requirements on heterogeneous clusters

Nowadays, increasing attention has been directed towards the issue of security service for real-time applications with security requirements on clusters. However, the study of integrating security demands of real-time applications into scheduling is rare. In this paper, we propose a novel two-phase scheduling strategy TPSS which takes timing constraints and security needs into consideration for security-critical real-time applications on heterogeneous clusters. In the first-phase, a novel algorithm DSRF is proposed to schedule real-time tasks. When the system is in heavy burden, DSRF is able to degrade the security levels of new tasks and tasks waiting in local queues so as to enhance guarantee ratio. On the contrary, when the system is in light burden, DSRF is capable of employing slack time to improve the security quality of new tasks and adequately utilize the system resource. The minimal security level can guarantee the system security, and higher security level is able to make the system more secure. In the second-phase, a new algorithm FMSL is proposed to minimize the difference of security levels of accepted tasks and further improve the security levels of accepted tasks on the whole, which degrades the probability of the applications being attacked. We compare TPSS, DSRF, SAEDF and RF by extensive simulations. The experimental results indicate that TPSS significantly improves the flexibility of scheduling and outperforms other algorithms.     

A green energy-efficient scheduling algorithm using the DVFS technique for cloud datacenters

Information and communication technology (ICT) has a profound impact on environment because of its large amount of CO₂ emissions. In the past years, the research field of “green” and low power consumption networking infrastructures is of great importance for both service/network providers and equipment manufacturers. An emerging technology called Cloud computing can increase the utilization and efficiency of hardware equipment. The job scheduler is needed by a cloud datacenter to arrange resources for executing jobs. In this paper, we propose a scheduling algorithm for the cloud datacenter with a dynamic voltage frequency scaling technique. Our scheduling algorithm can efficiently increase resource utilization; hence, it can decrease the energy consumption for executing jobs. Experimental results show that our scheme can reduce more energy consumption than other schemes do. The performance of executing jobs is not sacrificed in our scheme. We provide a green energy-efficient scheduling algorithm using the DVFS technique for Cloud computing datacenters.     

Feedback fuzzy-DVS scheduling of control tasks

To consider the energy-aware scheduling problem in computer-controlled systems is necessary to improve the control performance, to use the limited computing resource sufficiently, and to reduce the energy consumption to extend the lifetime of the whole system. In this paper, the scheduling problem of multiple control tasks is discussed based on an adjustable voltage processor. A feedback fuzzy-DVS (dynamic voltage scaling) scheduling architecture is presented by applying technologies of the feedback control and the fuzzy DVS. The simulation results show that, by using the actual utilization as the feedback information to adjust the supply voltage of processor dynamically, the high CPU utilization can be implemented under the precondition of guaranteeing the control performance, whilst the low energy consumption can be achieved as well. The proposed method can be applied to the design in computer-controlled systems based on an adjustable voltage processor.     

A DVS-assisted hard real-time I/O device scheduling algorithm

The I/O subsystem has become a major source of energy consumption in a hard real-time monitoring and control system. To reduce its energy consumption without missing deadlines, a dynamic power management (DPM) policy must carefully consider the power parameters of a device, such as its break-even time and wake-up latency, when switching off idle devices. This problem becomes extremely complicated when dynamic voltage scaling (DVS) is applied to change the execution time of a task. In this paper, we present COLORS, a composite low-power scheduling framework that includes DVS in a DPM policy to maximize the energy reduction on the I/O subsystem. COLORS dynamically predicts the earliest-access time of a device and switches off idle devices. It makes use of both static and dynamic slack time to extend the execution time of a task by DVS, in order to create additional switch-off opportunities. Task workloads, processor profiles, and device characteristics all impact the performance of a low-power real-time algorithm. We also identify a key metric that primarily determines its performance. The experimental results show that, compared with previous work, COLORS achieves additional energy reduction up to 20%, due to the efficient utilization of slack time.

一种基于混合任务集的高能效调度算法

动态电源与频率调整技术能够帮助实时系统显著减少能耗,之前的研究大多聚焦于基于周期性任务的线程调度算法,却很少考虑周期性与非周期性任务混合的模型。同时,尽管基于CPU利用率的DVS算法可以从系统级上减少能耗,但不能保证实时性。本文提出一种新的算法,它结合减慢因子的DVFS调度算法与系统级的DVS技术,融合PID控制器与自适应的权衡策略为软实时系统提供更好的能耗减少方法。该算法的能耗在服务器利用率低于25%的情况下比加州大学提出的算法下降了14.2%²5.9%,周期性任务超过时限率低于3%。     

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.     

实时任务在异构集群中的自适应容错调度研究

异构集群由于良好的扩展性和可用性,逐渐成为当前并行计算的热点。在具有实时性要求的异构集群中,调度是提高系统性能的关键所在。在此提出了两种自适应调度算法SANOL和SAOL,在保证异构集群中任务的实时性和容错性的前提下,自适应地根据系统的负载情况动态地调整任务的服务级别,从而提高整个系统的灵活性、可调度性和资源利用率。通过实验将这两种算法与另外一种有效率的调度算法DYFARS算法进行比较,结果表明所提出的SAOL算法具有更好的性能。     

Efficient real-time divisible load scheduling

Providing QoS and performance guarantees to arbitrarily divisible loads has become a significant problem for many cluster-based research computing facilities. While progress is being made in scheduling arbitrarily divisible loads, current approaches are not efficient and do not scale well. In this paper, we propose a linear algorithm for real-time divisible load scheduling. Unlike existing approaches, the new algorithm relaxes the tight coupling between the task admission controller and the task dispatcher. By eliminating the need to generate exact schedules in the admission controller, the algorithm avoids high overheads. We also proposed a hybrid algorithm that combines the best of our efficient algorithm and a previously best-known approach. We experimentally evaluate the new algorithm. Simulation results demonstrate that the algorithm scales well, can schedule large numbers of tasks efficiently, and performs similarly to existing approaches in terms of providing real-time guarantees.     

Requirement-aware strategies for scheduling real-time divisible loads on clusters

This paper investigates the real-time scheduling problem for handling heterogeneous divisible loads on cluster systems. Divisible load applications occur in many fields of science and engineering. Such applications can be easily parallelized in a master–worker fashion, but pose several scheduling challenges. We consider divisible loads associated with deadlines to enhance quality-of-service (QoS) and provide performance guarantees in distributed computing environments. In addition, since the divisible loads to be performed may widely vary in terms of their required hardware and software, we capture the loads’ various processing requirements in our load distribution strategies, a unique feature that is applicable for running proprietary applications only on certain eligible processing nodes. Thus in our problem formulation each load can only be processed by certain processors as both the loads and processors are heterogeneous. We propose scheduling algorithms referred to as Requirements-Aware Real-Time Scheduling (RARTS) algorithms, which consist of a novel scheduling policy, referred to as Minimum Slack Capacity First (MSCF), and two multi-round load distribution strategies, referred to as All Eligible Processors (AEP) and Least Capability First (LCF). We perform rigorous performance evaluation studies to quantify the performance of our strategies on a variety of scenarios.     

On the complexity of fixed-priority scheduling of periodic, real-time tasks

We consider the complexity of determining whether a set of periodic, real-time tasks can be scheduled on m 1 identical processors with respect to fixed-priority scheduling. It is shown that the problem is NP-hard in all but one special case. The complexity of optimal fixed-priority scheduling algorithm is also discussed.     

面向同构多核处理器的节能任务调度方法

对于运行在同构多核处理器上的周期性硬实时任务,设计了一个基于动态电压调节的节能调度方法。该方法首先将计算任务按照周期数降序排序并基于计算任务调度长度最短的原则安排任务映射。然后将各个处理核上具有最小通讯时间的计算任务设置为最后执行的计算任务而其它计算任务顺序保持不变。在初始映射中所有计算任务都被分配最高频率的情况下,每个处理核上的计算任务在执行时间扩展过程中确定最佳的计算任务顺序。基于 Intel PXA270的功耗模型,以几个随机任务集作实验。结果表明提出的方法能够有效地降低多核处理器的能量。     

Power optimization for dynamic configuration in heterogeneous web server clusters

To reduce the environmental impact, it is essential to make data centers green, by turning off servers and tuning their speeds for the instantaneous load offered, that is, determining the dynamic configuration in web server clusters. We model the problem of selecting the servers that will be on and finding their speeds through mixed integer programming; we also show how to combine such solutions with control theory. For proof of concept, we implemented this dynamic configuration scheme in a web server cluster running Linux, with soft real-time requirements and QoS control, in order to guarantee both energy-efficiency and good user experience. In this paper, we show the performance of our scheme compared to other schemes, a comparison of a centralized and a distributed approach for QoS control, and a comparison of schemes for choosing speeds of servers.     

DFTS: A dynamic fault-tolerant scheduling for real-time tasks in multicore processors

This paper presents a dynamic scheduling for real-time tasks in multicore processors to tolerate single and multiple transient faults. The scheduling is performed based on three important issues: (1) current released tasks, (2) current available processor cores, and (3) consideration of the number of faults and their occurrences. Using tasks utilization along with a defined criticality threshold in the proposed scheduling method, current ready tasks are divided into critical- and noncritical ones. Based on whether a task is critical or noncritical, an appropriate fault-tolerance policy is exploited. Moreover, scheduling decisions are made to fulfill two key goals: (1) increasing scheduling feasibility and (2) decreasing the total tasks execution time. Several simulation experiments are carried out to compare the proposed method with two well-known methods, called checkpointing with rollback recovery and hardware replication. Experimental results reveal that in the presence of multiple transient faults, the feasibility rate of the proposed method is considerably higher than the other well-known fault-tolerance methods. Moreover, the average timing overhead of this method is lower than the traditional methods.