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

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

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.     

A real-time scheduling framework for embedded systems with environmental energy harvesting

Real-time scheduling refers to the problem in which there is a deadline associated with the execution of a task. In this paper, we address the scheduling problem for a uniprocessor platform that is powered by a renewable energy storage unit and uses a recharging system such as photovoltaic cells. First, we describe our model where two constraints need to be studied: energy and deadlines. Since executing tasks require a certain amount of energy, classical task scheduling like earliest deadline is no longer convenient. We present an on-line scheduling scheme, called earliest deadline with energy guarantee (EDeg), that jointly accounts for characteristics of the energy source, capacity of the energy storage as well as energy consumption of the tasks, and time. In order to demonstrate the benefits of our algorithm, we evaluate it by means of simulation. We show that EDeg outperforms energy non-clairvoyant algorithms in terms of both deadline miss rate and size of the energy storage unit.     

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.     

Fault-tolerant adaptive scheduling for embedded real-time systems

Describes a fault-tolerant algorithm which uses a time-value scheduling approach to detect faults, sustain high processor utilization, and ensure timely execution of critical tasks     

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.     

Performance estimation for real-time distributed embedded systems

Many embedded computing systems are distributed systems: communicating processes executing on several CPUs/ASICs. This paper describes a performance analysis algorithm for a set of tasks executing on a heterogeneous distributed system. Tight bounds are essential to the synthesis and verification of application-specific distributed systems, such as embedded computing systems. Our bounding algorithms are valid for a general problem model: The system can contain several tasks with hard real-time deadlines and different periods; each task is partitioned into a set of processes related by data dependencies. The periods of tasks and the computation times of processes are not necessarily constant and can be specified by a lower bound and an upper bound. Such a model requires a more sophisticated algorithm, but leads to more accurate results than previous work. Our algorithm both provides tighter bounds and is faster than previous methods     

实时性分布嵌入式系统设计

分布嵌入式系统的应用通常具有实时性要求,其实时性需要从任务调度、通信协议、调用接口和嵌入式操作系统四个方面得到支持。采用两阶段调度策略既可以保证调用的透明性,又可以简化任务调度算法;基于优先级的线路竞争算法可以改进以太网使其符合实时性要求;采用微型Java虚拟机作为分布式中间件可以为系统调用接口提供一个统一的支持平台。     

Task scheduling in distributed real-time systems

An approach to the flow shop scheduling of the computation process in distributed realtime systems is considered. This approach is based on the concept of a solvable class of systems for which simple optimal scheduling algorithms exist.     

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.     

High performance real-time scheduling of multiple mixed-criticality functions in heterogeneous distributed embedded systems

The architectures of high-end embedded system have evolved into heterogeneous distributed integrated architectures. The scheduling of multiple distributed mixed-criticality functions in heterogeneous distributed embedded systems is a considerable challenge because of the different requirements of systems and functions. Overall scheduling length (i.e., makespan) is the main concern in system performance, whereas deadlines represent the major timing constraints of functions. Most algorithms use the fairness policies to reduce the makespan in heterogeneous distributed systems. However, these fairness policies cannot meet the deadlines of most functions. Each function has different criticality levels (e.g., severity), and missing the deadlines of certain high-criticality functions may cause fatal injuries to people under this situation. This study first constructs related models for heterogeneous distributed embedded systems. Thereafter, the criticality certification, scheduling framework, and fairness of multiple heterogeneous earliest finish time (F_MHEFT) algorithm for heterogeneous distributed embedded systems are presented. Finally, this study proposes a novel algorithm called the deadline-span of multiple heterogeneous earliest finish time (D_MHEFT), which is a scheduling algorithm for multiple mixed-criticality functions. The F_MHEFT algorithm aims at improving the performance of systems, while the D_MHEFT algorithm tries to meet the deadlines of more high-criticality functions by sacrificing a certain performance. The experimental results demonstrate that the D_MHEFT algorithm can significantly reduce the deadline miss ratio (DMR) and keep satisfactory performance over existing methods.     

A pre-run-time scheduling algorithm for object-based distributed real-time systems

The most important goal in hard real-time systems is to guarantee that all timing constraints are satisfied. Even though object-based techniques (which contain reusable software components) are used to manage the complexity in the software development process of such systems, execution efficiency may have to be sacrificed, due to the large number of procedure calls and contention for accessing software components. These issues are addressed by the following parallelizing techniques: (a) converting potentially inefficient procedure calls to a source of concurrency via asynchronous remote procedure calls (ARPC) (b) replicating (or cloning) software components to reduce the contention. The existing object-based scheduling algorithms construct an initial schedule and apply incremental parallelization techniques to modify the initial schedule till a feasible schedule is generated. But these algorithms are applicable for scheduling only multiple independent tasks. This paper describes a pre-run-time scheduling algorithm for a set of periodic object-based tasks having precedence constraints among them. The algorithm allocates the components of object-based periodic real-time tasks to the sites of a distributed system based on a clustering heuristic which takes into account the ARPC parallelism and load balancing, and schedules them on respective sites. The algorithm also finds a schedule for communication channel(s). Further, it clones the components of object-based periodic tasks, if contention occurs in accessing them. In addition to the above (periodicity and precedence) constraints, the tasks handled by our algorithm can have resource constraints among them. The experimental evaluation of the algorithm shows that the combination of the proposed clustering heuristic and cloning enhances schedulability.     

A static scheduling algorithm for distributed hard real-time systems

A static scheduling algorithm is presented for off-line scheduling of tasks in distributed hard real-time systems. The tasks considered are instances of periodic jobs and have deadlines, resource requirements and precedence constraints. Tasks are divided into nonpreemptable blocks and all task characteristics are known a priori. The algorithm orders the tasks and iteratively schedules the tasks according to the order. Each task is scheduled globally by selecting a node to which it is assigned. Then, the task is scheduled locally by adding the task to the schedule of the selected node. Heuristics are used for both task ordering and node selection in order to guide the algorithm to a feasible schedule. Whenever local scheduling leads to an infeasible schedule, backtracking is used.Results of simulation studies of randomly generated task sets are presented. Although the scheduling problem is NP-hard, the results show that time performance is acceptable for off-line scheduling, except for extremely difficult task sets which make extensive use of the available resources.     

Static priority scheduling of event-triggered real-time embedded systems

Real-time embedded systems are often specified as a collection of independent tasks, each generating a sequence of event-triggered code blocks. The goal of scheduling tasks in this domain is to find an execution order which satisfies all real-time constraints. Within the context of recurring real-time tasks, all previous work either allowed preemptions, or only considered dynamic scheduling, and generally had exponential complexity. However, for many embedded systems running on limited resources, preemptive scheduling may be very costly due to high context switching and memory overheads, and dynamic scheduling can be less desirable due to high CPU overhead. In this paper, we study static priority scheduling of recurring real-time tasks. We focus on and obtain schedule-theoretic results for the non-preemptive uniprocessor case. To achieve this, we derive a sufficient (albeit not necessary) condition for schedulability under static priority scheduling and show that this condition can be efficiently tested in practice. The latter technique is demonstrated with examples, where in each case, an optimal solution for a given problem specification is obtained within reasonable time, by first detecting good candidates using meta-heuristics, and then by testing them for schedulability.

Runtime and energy constrained work scheduling for heterogeneous systems

The Journal of Supercomputing - Heterogeneous hardware systems consisting of CPUs and different types of accelerators are wide-spread nowadays for large supercomputers as well as smaller cluster...     

Energy efficient scheduling for real-time embedded systems with QoS guarantee

While the dynamic voltage scaling (DVS) techniques are efficient in reducing the dynamic energy consumption for the processor, varying voltage alone becomes less effective for the overall energy reduction as the static power is growing rapidly. On the other hand, Quality of Service (QoS) is also a primary concern in the development of today’s pervasive computing systems. In this paper, we propose a dynamic approach to minimize the overall energy consumption for soft real-time systems while ensuring the QoS-guarantee. The QoS requirements are deterministically quantified with the window-constraints, which require that at least m out of each non-overlapped window of k consecutive jobs of a task meet their deadlines. Necessary and sufficient conditions for checking the feasibility of task sets with arbitrary service times and periods are developed to ensure that the window-constraints can be guaranteed in the worst case. And efficient scheduling techniques based on pattern variation and dynamic slack reclaiming extensions are proposed to combine the task procrastination and dynamic slowdown to minimize the energy consumption. In contrast to the previous leakage-aware dynamic reclaiming work which never scales the job speed below the critical speed, we will show that it can be more energy efficient to reclaim the slack with speed lower than the critical speed when necessary. Through extensive simulations, our experiment results demonstrate that the proposed techniques significantly outperformed the previous research in both overall and idle energy reduction.     

模型驱动工程在分布式实时嵌入式系统QoS评价中的应用

在分析传统的分布式实时嵌入式系统开发过程中,针对服务质量(QoS)评价方法存在弊端的问题,总结了运用模型驱动工程(MDE)对分布式实时嵌入式系统的服务质量进行管理,将服务质量评价引入系统开发周期的各种探索,指出该方法应解决的几个关键问题,并分析了几种具有代表性解决方案的优缺点,提出了解决方法和建议.     

A model for scheduling of object-based,distributed real-time systems

This paper describes a general model for pre-run-time scheduling of distributed real-time systems that are composed of abstract data types (definable in languages such as Ada, Clu and Modula-2) and abstract data objects (which can be defined in C++, Eiffel and RT Euclid). An architecture model, a programming paradigm, and execution and communication paradigms form the basis for this general model. The model includesabsolute timing constraints to represent periodicity and deadlines,relative timing constraints to model several kinds of timed precedence relations and synchronization requirements,independency constraints to capture non-determinism of conditionals and repetitions, andconsistency constraints to enforce consistent use of resources. In this paper, the model is formalized to obtain a mathematical foundation on which assignment (Verhoosel et al. 1993a, Welch 1992, Welch et al. 1993) and pre-run-time scheduling problems (Verhoosel et al. 1991, Verhoosel 1992, 1993a, 1993c) are defined. Additionally, the model is extended to allow exploitation of parallelism from programs, a technique that can be used during assignment and scheduling for meeting timing constraints.     

Communications-oriented development of component-based vehicular distributed real-time embedded systems

We propose a novel model- and component-based technique to support communications-oriented development of software for vehicular distributed real-time embedded systems. The proposed technique supports modeling of legacy nodes and communication protocols by encapsulating and abstracting the internal implementation details and protocols. It also allows modeling and performing timing analysis of the applications that contain network traffic originating from outside of the system such as vehicle-to-vehicle, vehicle-to-infrastructure, and cloud-based applications. Furthermore, we present a method to extract end-to-end timing models to support end-to-end timing analysis. We also discuss and solve the issues involved during the extraction of these models. As a proof of concept, we implement our technique in the Rubus Component Model which is used for the development of software for vehicular embedded systems by several international companies. We also conduct an application-case study to validate our approach.