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.     

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 and transition-aware runtime task scheduling for multicore processors

Many embedded or portable devices have large demands on running real-time applications. The designers start to adopt the multicore processors in these devices. The multi-core processors, however, cause much higher power consumption than ever before. To resolve this problem, many researchers have focused their studies on designing the energy-aware task scheduling algorithms for multicore processors. Conventional scheduling algorithms assumed that each core can operate under different voltage levels. However, they have not considered the effects of voltage transition overheads, which may defeat the benefit of task scheduling. In this paper, we aim to resolve this scheduling problem with voltage transition overhead consideration. We formalize this problem by an integer linear programming model and propose a heuristic algorithm for a runtime environment. The experimental results show that the proposed online heuristic algorithm can obtain the comparable results with the optimal scheduling derived by the offline integer linear programming approach.     

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.     

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.     

Limited carry-in technique for real-time multi-core scheduling

Schedulability analysis has been widely studied to provide offline timing guarantees for a set of real-time tasks. The so-called limited carry-in technique, which can be orthogonally incorporated into many different multi-core schedulability analysis methods, was originally introduced for Earliest Deadline First (EDF) scheduling to derive a tighter bound on the amount of interference of carry-in jobs at the expense of investigating a pseudo-polynomial number of intervals. This technique has been later adapted for Fixed-Priority (FP) scheduling to obtain the carry-in bound efficiently by examining only one interval, leading to a significant improvement in multi-core schedulability analysis. However, such a successful result has not yet been transferred to any other non-FP scheduling algorithms. Motivated by this, this paper presents a generic limited carry-in technique that is applicable to any work-conserving algorithms. Specifically, this paper derives a carry-in bound in an algorithm-independent manner and demonstrates how to apply the bound to existing non-FP schedulability analysis methods for better schedulability.     

基于Linux的多核实时任务调度算法改进

嵌入式实时系统通常被实现为多任务系统,以满足多个外部输入的响应时间的最后期限约束。Linux内核中已经实现了基于EDF(Earliest Deadline First)调度算法的DL调度器,使得实时任务能在截止期限内运行完成。但对于多核处理器,由于实时任务在EDF算法下会出现Dhall效应,论文对 Linux内核中实时任务调度算法进行了改进。在EDF算法的基础上,实现LLF(Least Laxity First)调度算法并对其加以改进,通过降低任务上下文切换频率以及减少松弛度的计算来减小调度过程中的颠簸现象。实验证明该方法既避免了Dhall效应,又减少了任务上下文切换带来的系统开销,并使得任务能在截止期限内完成调度,取得了较好的调度性能。     

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.

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

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

Power efficient rate monotonic scheduling for multi-core systems

More computational power is offered by current real-time systems to cope with CPU intensive applications. However, this facility comes at the price of more energy consumption and eventually higher heat dissipation. As a remedy, these issues are being encountered by adjusting the system speed on the fly so that application deadlines are respected and also, the overall system energy consumption is reduced. In addition, the current state of the art of multi-core technology opens further research opportunities for energy reduction through power efficient scheduling. However, the multi-core front is relatively unexplored from the perspective of task scheduling. To the best of our knowledge, very little is known as of yet to integrate power efficiency component into real-time scheduling theory that is tailored for multi-core platforms. In this paper, we first propose a technique to find the lowest core speed to schedule individual tasks. The proposed technique is experimentally evaluated and the results show the supremacy of our test over the existing counterparts. Following that, the lightest task shifting policy is adapted for balancing core utilization, which is utilized to determine the uniform system speed for a given task set. The aforementioned guarantees that: (i) all the tasks fulfill their deadlines and (ii) the overall system energy consumption is reduced.     

Energy-aware scheduling and simulation methodologies for parallel security processors with multiple voltage domains

Dynamic voltage scaling (DVS) and power gating (PG) have become mainstream technologies for low-power optimization in recent years. One issue that remains to be solved is integrating these techniques in correlated domains operating with multiple voltages. This article addresses the problem of power-aware task scheduling on a scalable cryptographic processor that is designed as a heterogeneous and distributed system-on-a-chip, with the aim of effectively integrating DVS, PG, and the scheduling of resources in multiple voltage domains (MVD) to achieve low energy consumption. Our approach uses an analytic model as the basis for estimating the performance and energy requirements between different domains and addressing the scheduling issues for correlated resources in systems. We also present the results of performance and energy simulations from transaction-level models of our security processors in a variety of system configurations. The prototype experiments show that our proposed methods yield significant energy reductions. The proposed techniques will be useful for implementing DVS and PG in domains with multiple correlated resources.     

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.     

Applying pinwheel scheduling and compiler profiling for power-aware real-time scheduling

Energy consumption is a critical design issue in embedded systems, especially in battery-operated systems. Maintaining high performance while extending the battery life is an interesting challenge for system designers. Dynamic voltage scaling and dynamic frequency scaling allow us to adjust supply voltage and processor frequency to adapt to the workload demand for better energy management. Because of the high complexity involved, most solutions depend on heuristics for online power-aware real-time scheduling or offline time-consuming scheduling. In this paper, we discuss how we can apply pinwheel model to power-aware real-time scheduling so that task information, including start times, finish times, preemption times, etc, can be efficiently derived using pinwheel model. System predictability is thus increased and under better control on power-awareness. However, job execution time may be only a small portion of its worst case execution time and can only be determined at runtime. We implement a profiling tool to insert codes for collecting runtime information of real-time tasks. Worst case execution time is updated online for scheduler to perform better rescheduling according to actual execution. Simulations have shown that at most 50% energy can be saved by the proposed scheduling algorithm. Moreover, at most additional 33% energy can be saved when the profiling technique is applied. This paper is an extended version of the paper Power-Aware Real-Time Scheduling using Pinwheel Model and Profiling Technique that appeared in the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications.     

Energy-aware task migration for multiprocessor real-time systems

A task migration method is proposed for energy savings in multiprocessor real-time systems. The method is based on the portioned scheduling technique which classifies each task as a fixed task or a migratable task. The basic task migration problem with specific parameters is formulated as a linear programming problem to minimize average power. Then, the method is extended to more general case with a complete migration algorithm. Moreover, a scheduling algorithm is proposed for migratable tasks. Simulation results on two processor models demonstrated significant energy savings over existing methods.     

On-line scheduling of scalable real-time tasks on multiprocessor systems

The computation time of scalable tasks depends on the number of processors allocated to them in multiprocessor systems. As more processors are allocated to a scalable task, the overall computation time of the task decreases but the total amount of processors’ time devoted to the execution of the task, called workload, increases due to parallel execution overhead. In this paper, we propose a task scheduling algorithm that utilizes the property of scalable tasks for on-line and real-time scheduling. In the proposed algorithm, the total workload of all scheduled tasks is reduced by managing processors allocated to the tasks as few as possible without missing their deadlines. As a result, the processors in the system have less load to execute the scheduled tasks and can execute more newly arriving tasks before their deadlines. Simulation results show that the proposed algorithm performs significantly better than the conventional algorithm based on a fixed number of processors to execute each task.     

RT-ROS: A real-time ROS architecture on multi-core processors

ROS, an open-source robot operating system, is widely used and rapidly developed in the robotics community. However, running on Linux, ROS does not provide real-time guarantees, while real-time tasks are required in many robot applications such as robot motion control. This paper for the first time presents a real-time ROS architecture called RT-RTOS on multi-core processors. RT-ROS provides an integrated real-time/non-real-time task execution environment so real-time and non-real-time ROS nodes can be separately run on a real-time OS and Linux, respectively, with different processor cores. In such a way, real-time tasks can be supported by real-time ROS nodes on a real-time OS, while non-real-time ROS nodes on Linux can provide other functions of ROS. Furthermore, high performance is achieved by executing real-time ROS nodes and non-real-time ROS nodes on different processor cores. We have implemented RT-ROS on a dual-core processor and conducted various experiments with real robot applications. The experimental results show that RT-ROS can effectively provide real-time support for the ROS platform with high performance by exploring the multi-core architecture.     

Slack computation for DVS algorithms in fixed-priority real-time systems using fluid slack analysis

This work presents a scheduling algorithm to reduce the energy of hard real-time tasks with fixed priorities assigned in a rate-monotonic policy. Sets of independent tasks running periodically on a processor with dynamic voltage scaling (DVS) are considered as well. The proposed online approach can cooperate with many slack-time analysis methods based on low-power work demand analysis (lpWDA) without increasing the computational complexity of DVS algorithms. The proposed approach introduces a novel technique called low-power fluid slack analysis (lpFSA) that extends the analysis interval produced by its cooperative methods and computes the available slack in the extended interval. The lpFSA regards the additional slack as fluid and computes its length, such that it can be moved to the current job. Therefore, the proposed approach provides the cooperative methods with additional slack. Experimental results show that the proposed approach combined with lpWDA-based algorithms achieves more energy reductions than do the initial algorithms alone.     

适用于不确定环境中的DVS软实时调度算法

为了解决嵌入式软实时系统的节能问题,提出了一种DVS调度算法。它的特点是克服了任务执行时间不确定所带来的干扰,在运行时动态地寻找最优电压调节方案。实验表明：该调度算法可以很好地保证软实时系统的效率和稳定性,即使在处理器超载的情况下,也能自动调节,超过99%的作业可以在时间期限之前完成。对多种随机任务集的评测显示,该调度算法使得系统能耗平均减少15%以上。     

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.     

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.