Energy aware fixed priority scheduling in mixed-criticality systems

Most of studies about energy management for MC systems are based on dynamic priority scheme. The disadvantages of dynamic priority scheme are high system overhead and poor predictability. Unlike previous studies, we focus on the problem of scheduling mixed-criticality (MC) periodic tasks with minimizing energy consumption in MC systems based on fixed priority scheme. Firstly, we explain a criticality rate monotonic scheduling (CRMS) and propose the sufficient schedulability condition of CRMS. Secondly, we compute the energy minimization uniform scaled speed and present an optimal static solution algorithm based on CRMS. The extra workload of the high criticality level (HI) task executes with the maximum processor speed in the high criticality mode (HI-mode). But this algorithm does not exploit the slack time generated from the HI task in the low criticality mode (LO-mode). For energy efficiency, we propose a dynamic fixed priority energy minimization algorithm which exploits the slack time generated from the HI task in LO-mode to save energy. In addition, it combines a dynamic voltage and frequency scaling technique and a dynamic power management technique to reduce energy consumption. Finally, the experiments are applied to evaluate the performance of the proposed algorithm and the experimental results show that the proposed algorithm can save up 23.89% energy compared with other existing algorithms.     

实时协同的调度算法研究

研究了目前流行的实时调度技术,归纳总结了不同调度技术下的典型调度算法,介绍了实时调度算法的调度规则、调度特点、适用场合以及需要解决的问题,分析了典型商业实时操作系统中的调度技术,提出了增强操作系统实时性能需要解决的技术问题,为将优秀的实时调度算法应用在实时操作系统中奠定了理论基础。     

分布式嵌入式系统实时调度的建模

针对RBTPN模型在建模分布式嵌入式系统实时调度时的不足,提出了一种新的扩展时间Petri网模型。该模型通过在需要处理器资源的变迁上引入变迁速率因子,得到具有相同优先级变迁的运行速率函数,从而在分布式嵌入式系统的调度建模中,在单个处理器上结合了固定优先级可抢先调度和轮转调度。随后给出了该模型可达图的构造方法,以便可以得到调度序列的各种性质。     

关于RTOS抢占式调度及优先级反转的几点探讨

抢占式调度是RTOS的一个重要的调度策略,它保证了嵌入式系统的实时性.合理地分配任务的优先级和使用系统资源将会大大提高系统的性能.而解决优先级反转问题将保证系统共享资源的合理使用和多任务的正常运行.在对RTOS抢占式调度策略的研究的基础上,指出了什么是优先级反转,以及问题发生的原因,并给出了优先级继承和优先级封顶的解决方法.     

Fault-tolerant scheduling for real-time embedded control systems

With the increasing complexity of industrial application, an embedded control system (ECS) requires processing a number of hard real-time tasks and needs fault-tolerance to assure high reliability. Considering the characteristics of real-time tasks in ECS, an integrated algorithm is proposed to schedule real-time tasks and to guarantee that all real-time tasks are completed before their deadlines even in the presence of faults. Based on the nonpreemptive critical-section protocol (NCSP), this paper analyzes the blocking time introduced by resource conflicts of relevancy tasks in fault-tolerant multiprocessor systems. An extended schedulability condition is presented to check the assignment feasibility of a given task to a processor. A primary/backup approach and on-line replacement of failed processors are used to tolerate processor failures. The analysis reveals that the integrated algorithm bounds the blocking time, requires limited overhead on the number of processors, and still assures good processor utilization. This is also demonstrated by simulation results. Both analysis and simulation show the effectiveness of the proposed algorithm in ECS.     

实时操作系统任务调度策略的研究与设计

实时操作系统的调度策略是影响系统实时性和稳定性的一个重要因素,通过对抢占调度和分时调度的研究,设计了一个可分级抢占和分时调度的实时操作系统。用抢占调度方式来保证系统的实时性,用分时调度来减少进程饥饿现象的发生,提高系统的稳定性,更易于使用。     

Intra-task device scheduling for real-time embedded systems

An ever increasing need for extra functionality in a single embedded system demands for extra Input/Output (I/O) devices, which are usually connected externally and are expensive in terms of energy consumption. To reduce their energy consumption, these devices are equipped with power saving mechanisms. While I/O device scheduling for real-time (RT) systems with such power saving features has been studied in the past, the use of energy resources by these scheduling algorithms may be improved.Technology enhancements in the semiconductor industry have allowed the hardware vendors to reduce the device transition and energy overheads. The decrease in overhead of sleep transitions has opened new opportunities to further reduce the device energy consumption. In this research effort, we propose an intra-task device scheduling algorithm for real-time systems that wakes up a device on demand and reduces its active time while ensuring system schedulability. This intra-task device scheduling algorithm is extended for devices with multiple sleep states to further minimise the overall device energy consumption of the system. The proposed algorithms have less complexity when compared to the conservative inter-task device scheduling algorithms. The system model used relaxes some of the assumptions commonly made in the state-of-the-art that restrict their practical relevance. Apart from the aforementioned advantages, the proposed algorithms are shown to demonstrate the substantial energy savings.     

Lowest priority first based feasibility analysis of real-time systems

The feasibility problem of periodic tasks under fixed priority systems has always been a critical research issue in real-time systems and a number of feasibility tests have been proposed to guarantee the timing requirements of real-time systems. These tests can be broadly classified into: (a) inexact and (b) exact tests. The inexact tests are applied to the task sets that present lower utilization, while the exact tests become inevitable when system utilization is high. The exact tests can be further classified into: (a) Scheduling Points Tests (SPT) and (b) Response Time Tests (RTT). The SPT analyze task set feasibility at the arrival times while the RTT utilize fixed-point techniques to determine task feasibility. All of the available exact feasibility tests, whichever class it belongs to, share pseudo-polynomial complexity. Therefore, the aforementioned tests become impractical for online systems. Currently, both SPT and RTT employ the Highest Priority First (HPF) approach, which determines the system feasibility by testing the schedulability of individual tasks in the decreasing order of priority. In contrast, this work exploits the Lowest Priority First (LPF) alternative which is an aggressive solution based on the observation that the system infeasibility is primarily due to the lower priority tasks and not because of the higher priority tasks. For the average case analysis, our technique demonstrates promising results. Moreover, in the worst case scenario our solution is no inferior to the existing state of the art alternatives. We compare our proposed technique with the existing tests: (a) by counting the number of scheduling points used by a test that belongs to the SPT, (b) by counting the number of inner-most loops executed by an algorithm for the RTT, and (c) by measuring the actual running time of the existing alternatives.     

Utility accrual real-time scheduling for multiprocessor embedded systems

We present the first Utility Accrual (or UA) real-time scheduling algorithm for multiprocessors, called the global Multiprocessor Utility Accrual scheduling algorithm (or gMUA). The algorithm considers an application model where real-time activities are subject to time/utility function time constraints, variable execution time demands, and resource overloads where the total activity utilization demand exceeds the total capacity of all processors. We consider the scheduling objective of (1) probabilistically satisfying lower bounds on each activity’s maximum utility, and (2) maximizing the system-wide, total accrued utility. We establish several properties of gMUA including optimal total utility (for a special case), conditions under which individual activity utility lower bounds are satisfied, a lower bound on system-wide total accrued utility, and bounded sensitivity for assurances to variations in execution time demand estimates. Finally, our simulation experiments validate our analytical results and confirm the algorithm’s effectiveness.     

Modeling and analysis of scheduling for distributed real-time embedded systems

Aimed at the deficiencies of resources based time Petri nets (RBTPN) in doing scheduling analysis for distributed real-time embedded systems, the assemblage condition of complex scheduling sequences is presented to easily compute scheduling length and simplify scheduling analysis. Based on this, a new hierarchical RBTPN model is proposed. The model introduces the definition of transition border set, and represents it as an abstract transition. The abstract transition possesses all resources of the set, and has the highest priority of each resource; the execution time of abstract transition is the longest time of all possible scheduling sequences. According to the characteristics and assemblage condition of RBTPN, the refinement conditions of transition border set are given, and the conditions ensure the correction of scheduling analysis. As a result, it is easy for us to understand the scheduling model and perform scheduling analysis.