强实时系统静态优先级调度的可调度性分析

文章在系统阐述和借鉴经典的强实时系统静态优先级调度理论的基础上,通过引入忙周期的概念,分析了任务时限超过任务周期的实时系统任务集的可调度特性,拓宽了该理论的应用范围,更有利于实时系统的设计者对任务的运行时间行为进行事前分析与预测。     

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.     

基于RMS调度周期、非周期混合任务集的一种新方法*

提出了一种利用速率单调（RMS）算法确定计算机实时系统中整个任务集优先级的新方法。该方法利用数理统计的规律克服了普通RMS算法只能对系统中周期任务进行有效调度而不能对系统中的非周期任务进行有效调度的局限,扩大了RMS算法的适用范围,简化了非周期任务的处理过程,减小了系统开销。利用该方法在先进飞机电气综合控制与管理系统中进行了整个任务集的可调度性测试、验证,并给出了任务集的实际调度的验证实例。     

实时Petri网及其在任务可调度性分析中的应用

本文描述了一种实时任务可调度性分析工具－实时Petri网,给出了由数据流图向实时Petri网转化的方法,介绍了应用实时Petri网进行可调度性分析折步骤,最后讨论了不可调度的情形和处理方法。     

异构分布式系统混合型实时容错调度算法

基/副版本技术是实现实时分布式系统容错的一个重要手段。提出了一种异构分布式混合型容错模型,该模型与传统的异构分布式实时调度模型相比同时考虑了周期和非周期调度任务。在此基础上给出3种容错调度算法:以可调度性为目的SSA算法、以可靠性为目的RSA算法、以负载均衡性为目的BSA算法。算法能够在异构系统中同时调度具有周期和非周期容错需求的实时任务,且能够保证在异构系统中某节点机失效情况下,实时任务仍然能在截止时间内完成。最后从可调度性、可靠性代价、负载均衡性、周期与非周期任务数及任务周期与粒度J个方面对算法进行了分析。模拟实验结果显示算法各有优缺点,所以在选择调度算法时应该根据异构系统的特点来选择。     

SET-MRTS: An empirical experiment tool for real-time scheduling and synchronization

In the real-time scheduling theory, schedulability and synchronization analyses are used to evaluate scheduling algorithms and real-time locking protocols, respectively, and the empirical synthesis experiment is one of the major methods to compare the performance of such analyses. However, since many sophisticated techniques have been adopted to improve the analytical accuracy, the implementation of such analyses and experiments is often time-consuming. This paper proposes a schedulability experiment toolkit for multiprocessor real-time systems (SET-MRTS), which provides a framework with infrastructures to implement the schedulability and synchronization analyses and the deployment of empirical synthesis experiments. Besides, with well-designed peripheral components for the input and output, experiments can be conducted easily and flexibly on SET-MRTS. This demonstration further proves the effectiveness of SET-MRTS in both functionality and availability.     

A Process Algebraic Approach to the Schedulability Analysis of Real-Time Systems

To engineer reliable real-time systems, it is desirable to detect timing anomalies early in the development process. However, there is little work addressing the problem of accurately predicting timing properties of real-time systems before implementations are developed. This paper describes an approach to the specification and schedulability analysis of real-time systems based on the timed process algebra ACSR-VP, which is an extension of ACSR with value-passing communication and dynamic priorities. Combined with the existing features of ACSR for representing time, synchronization and resource requirements, ACSR-VP is capable of specifying a variety of real-time systems with different scheduling disciplines in a modular fashion. Moreover, we can use VERSA, a toolkit we have developed for ACSR, to perform schedulability analysis on real-time systems specified in ACSR-VP automatically by checking for a certain bisimulation relation.     

An analysis of global edf schedulability for arbitrary-deadline sporadic task systems

Recent results on the global multiprocessor edf scheduling of sporadic task systems are, for the most part, applicable only to task systems in which each task’s relative deadline parameter is constrained to be no larger than its minimum inter-arrival separation. This paper introduces new analysis techniques that allow for similar results to be derived for task systems in which individual tasks are not constrained in this manner. For tasks with deadlines greater than their minimum inter-arrival separation, two models are considered, with and without an implicit intra-task job precedence constraint. The new analyses yield schedulability conditions that strictly dominate some previously proposed tests that are generally accepted to represent the current state of the art in multiprocessor edf schedulability analysis, and permits the derivation of an improved speed-up bound.

Rate monotonic schedulability tests using period-dependent conditions

Feasibility and schedulability problems have received considerable attention from the real-time systems research community in recent decades. Since the publication of the Liu and Layland bound, many researchers have tried to improve the schedulability bound of the RM scheduling. The LL bound does not make any assumption on the relationship between any of the task periods. In this paper we consider the relative period ratios in a system. By reducing the difference between the smallest and the second largest virtual period values in a system, we can show that the RM schedulability bound can be improved significantly. This research has also proposed a system design methodology to improve the schedulability of real time system with a fixed system load.

Implementation and analysis of real-time communication protocol compositions

A flexible way of building modular communication stacks relies on the use of protocol composition. This paper describes a protocol composition framework that simplifies the task of deriving the worst-case response time of a protocol composition from the protocol implementation. In order to derive the worst-case response time of a protocol composition, one needs to capture its event-graph: the event-graph consists of the set of all events processed by each component and the relation between those events. The framework, called RT-Appia, takes a pragmatic approach: instead of requiring the use of domain specific code analysis tools, or dedicated compilers, it simply requires protocol programmers to make explicit which events are processed and produced by each layer, and how these events are related. An interesting aspect of the approach is that the same data structures that are used to simplify the task of computing the worst-case response time of the protocol composition are also used to optimize the performance and to debug the resulting implementation.