EDZL scheduling analysis

A schedulability test is derived for the global Earliest Deadline Zero Laxity (EDZL) scheduling algorithm on a platform with multiple identical processors. The test is sufficient, but not necessary, to guarantee that a system of independent sporadic tasks with arbitrary deadlines will be successfully scheduled, with no missed deadlines, by the multiprocessor EDZL algorithm. Global EDZL is known to be at least as effective as global Earliest-Deadline-First (EDF) in scheduling task sets to meet deadlines. It is shown, by testing on large numbers of pseudo-randomly generated task sets, that the combination of EDZL and the new schedulability test is able to guarantee that far more task sets meet deadlines than the combination of EDF and known EDF schedulability tests. In the second part of the paper, an improved version of the EDZL-schedulability test is presented. This new algorithm is able to efficiently exploit information on the slack values of interfering tasks, to iteratively refine the estimation of the interference a task can be subjected to. This iterative algorithm is shown to have better performance than the initial test, in terms of schedulable task sets detected.

An optimal GTS scheduling algorithm for time-sensitive transactions in IEEE 802.15.4 networks

IEEE 802.15.4 is a new enabling standard for low-rate wireless personal area networks and has been widely accepted as a de facto standard for wireless sensor networking. While primary motivations behind 802.15.4 are low power and low cost wireless communications, the standard also supports time and rate sensitive applications because of its ability to operate in TDMA access modes. The TDMA mode of operation is supported via the Guaranteed Time Slot (GTS) feature of the standard. In a beacon-enabled network topology, the Personal Area Network (PAN) coordinator reserves and assigns the GTS to applications on a first-come-first-served (FCFS) basis in response to requests from wireless sensor nodes. This fixed FCFS scheduling service offered by the standard may not satisfy the time constraints of time-sensitive transactions with delay deadlines. Such operating scenarios often arise in wireless video surveillance and target detection applications running on sensor networks. In this paper, we design an optimal work-conserving scheduling algorithm for meeting the delay constraints of time-sensitive transactions and show that the proposed algorithm outperforms the existing scheduling model specified in IEEE 802.15.4.     

Supporting end-to-end quality of service properties in OMG data distribution service publish/subscribe middleware over wide area networks

Assuring end-to-end quality-of-service (QoS) in distributed real-time and embedded (DRE) systems is hard due to the heterogeneity and scale of communication networks, transient behavior, and the lack of mechanisms that holistically schedule different resources end-to-end. This paper makes two contributions to research focusing on overcoming these problems in the context of wide area network (WAN)-based DRE applications that use the OMG Data Distribution Service (DDS) QoS-enabled publish/subscribe middleware. First, it provides an analytical approach to bound the delays incurred along the critical path in a typical DDS-based publish/subscribe stream, which helps ensure predictable end-to-end delays. Second, it presents the design and evaluation of a policy-driven framework called Velox. Velox combines multi-layer, standards-based technologies—including the OMG DDS and IP DiffServ—to support end-to-end QoS in heterogeneous networks and shield applications from the details of network QoS mechanisms by specifying per-flow QoS requirements. The results of empirical tests conducted using Velox show how combining DDS with DiffServ enhances the schedulability and predictability of DRE applications, improves data delivery over heterogeneous IP networks, and provides network-level differentiated performance.     

Dual ceiling protocol for real-time synchronization under preemption threshold scheduling

The application of object-oriented design methods to real-time embedded systems is seriously hindered by the lack of existing real-time scheduling techniques that can be seamlessly integrated into these methods. Preemption threshold scheduling (PTS) enables a scalable real-time system design and thus has been suggested as a solution to this problem. However, direct adoption of PTS may lead to long priority inversion since object-oriented real-time systems require synchronization considerations in order to maintain consistent object states. In this paper, we propose the dual ceiling protocol (DCP) in order to solve this problem. While DCP exploits both priority ceilings and preemption threshold ceilings, this is not a straightforward integration of existing real-time synchronization protocols for PTS. We present the rationale for the locking conditions of DCP and show that it leads to the least blocking and response times by comparison with other real-time synchronization protocols. We also present its blocking properties and schedulability analyses. We implemented PTS and DCP in a real-time object-oriented CASE tool and present the associated experimental results, which show that the proposed protocol is a viable solution that is superior to other real-time synchronization protocols for PTS.     

MPS-CAN analyzer: Integrated implementation of response-time analyses for Controller Area Network

We present a new response-time analyzer for Controller Area Network (CAN) that integrates and implements a number of response-time analyses which address various transmission modes and practical limitations in the CAN controllers. The existing tools for the response-time analysis of CAN support only periodic and sporadic messages. They do not analyze mixed messages which are partly periodic and partly sporadic. These messages are implemented by several higher-level protocols based on CAN that are used in the automotive industry. The new analyzer supports periodic, sporadic as well as mixed messages. It can analyze the systems where periodic and mixed messages are scheduled with offsets. It also supports the analysis of all types of messages while taking into account several queueing policies and buffer limitations in the CAN controllers such as abortable or non-abortable transmit buffers. Moreover, the tool supports the analysis of mixed, periodic and sporadic messages in the heterogeneous systems where Electronic Control Units (ECUs) implement different types of queueing policies and have different types of buffer limitations in the CAN controllers. We conduct a case study of a heterogeneous application from the automotive domain to show the usability of the tool. Moreover, we perform a detailed evaluation of the implemented analyses.     

UM-RTCOM: An analyzable component model for real-time distributed systems

Component-based development is a key technology in the development of software for modern real-time systems. However, standard component models and tools are not suitable for this type of system, since they do not explicitly address real time, memory or cost constraints. This paper presents a new predictable component model for real-time systems (UM-RTCOM) together with a set of tools to support it. The environment allows new components to be developed which can then be assembled to build complete applications, including hardware interaction. The model includes support for real-time analysis at the component and application level. The analysis is achieved by combining component meta-information in the form of an abstract behaviour model and a method to measure worst-case execution times in the final platform. Additionally, we propose an implementation model based on RT-CORBA where the developer uses the UM-RTCOM components and a set of tools to map these elements to elements of the desired platform. In order to apply our proposals, we have used the model and tools in real applications specifically in the context of nuclear power plant simulators.     

控制系统中周期性任务的静态优化调度算法

分析了控制系统中的周期任务特性，给出了控制系统中周期性任务模型。分析了RMS调度算法任务下的可调度性，给出了求任务响应时间的算法。提出任务调度中系统优化应满足的条件。最后，给出了求优化采样频率的算法和控制系统的静态优化调度算法。     

On the gap between schedulability tests and an automotive task model

In this paper, we study the adequacy of available schedulability tests for monoprocessor fixed-priority systems to enable performing scheduling analysis for automotive applications. We show that, in spite of the work carried out during the last decade to enhance these tests in order to support more realistic task model, a gap still exists between the task model considered in these tests and the usual automotive task model. However, we claim that an extension of these tests is possible to support some of the uncovered automotive features. The aim of this study is to raise discussion and make researchers involved in the development of such schedulability tests be aware of the effort needed to bridge the gap between current schedulability tests and automotive task model mostly used. The study is illustrated by showing the concrete challenges faced when applying scheduling analysis to a case study derived from a real engine control application.     

On the convergence of the holistic analysis for EDF distributed systems

Dynamic scheduling techniques, and EDF (Earliest Deadline First) in particular, have demonstrated their ability to increase the schedulability of real time systems compared to fixed-priority scheduling. In distributed systems, the scheduling policies of the processing nodes tend to be the same as in stand-alone systems and, although few EDF networks exist, it is foreseen that dynamic scheduling will gradually develop into real-time networks. There are some response time analysis techniques for EDF scheduled distributed systems, mostly derived from the holistic analysis developed by Spuri. A major factor influencing the response time is the release jitter of each task, which is the maximum variation suffered by the release time of the task jobs. The convergence of the holistic analysis in the context of EDF distributed systems with shared resources had not been studied until now. There is a circular dependency between the task release jitter values, response times and the preemption level ceilings of shared resources. In this paper we present an extension of Spuri’s algorithm and we demonstrate that its iterative formulas are non-decreasing, even in the presence of shared resources. This result enables us to assert that the new algorithm converges towards a solution for the response times of the tasks and messages in a distributed system.¹     

A new algorithm for scheduling periodic, real-time tasks

We consider the problem of preemptively scheduling a set of periodic, real-time tasks on a multiprocessor computer system. We give a new scheduling algorithm, the so-called Slack-Time Algorithm, and show that it is more effective than the known Deadline Algorithm. We also give an (exponential-time) algorithm to decide if a task system is schedulable by the Slack-Time or the Deadline Algorithm. The same algorithm can also be used to decide if a task system is schedulable by any given fixed-priority scheduling algorithm. This resolves an open question posed by Leung and Whitehead. Finally, it is shown that the problem of deciding if a task system is schedulable by the Slack-Time, the Deadline, or any given fixed-priority scheduling algorithm is co-NP-hard for each fixedm.