Dual-Priority versus Background Scheduling: A Path-Wise Comparison

In this paper, two well-known scheduling policies for real-time systems, namely background scheduling (BS) and dual-priority (DP) are compared in terms of response times for soft real-time traffic (SRT). It is proved in the preemptive as well as in the non-preemptive case that, when the SRT traffic is FIFO, the DP policy always outperforms BS for all instances of SRT tasks. When the SRT traffic is not FIFO but if all tasks are of equal size then, in the non-preemptive case, the average response times is shown to be always better under DP than under BS. As a complementary result, some non-FIFO examples where BS behaves better than DP for some SRT tasks but also on the average of the SRT response times, are given. The proofs are based on a trajectorial method that may be used for comparing other scheduling policies.     

Dynamic voltage scaling under EDF revisited

Basic algorithms have been proposed in the field of low-power (Yao, F., et al. in Proceedings of lEEE annual foundations of computer science, pp. 374–382, 1995) which compute the minimum energy-schedule for a set of non-recurrent tasks (or jobs) scheduled under EDF on a dynamically variable voltage processor. In this study, we propose improvements upon existing algorithms with lower average and worst-case complexities. They are based on a new EDF feasibility test that helps to identify the “critical intervals”. The complexity of this feasibility test depends on structural characteristics of the set of jobs. More precisely, it depends on how tasks are included one in the other. The first step of the algorithm is to construct the Hasse diagram of the set of tasks where the partial order is defined by the inclusion relation on the tasks. Then, the algorithm constructs the shortest path in a geometrical representation at each level of the Hasse diagram. The optimal processor speed is chosen according to the maximal slope of each path.

Controller area network [automotive applications]

The controller area network (CAN) is becoming a de facto standard for data transmission in automotive applications. Such applications are characterized by their obligation to respect stringent time and dependability constraints. This is why it is vital, at the design step, to validate their behavior. The verification is based on the performance evaluation of the operational architecture. The authors' approach involves: (1) building models (both analytic and simulation) and solving them (model-based evaluation); and (2) performing network monitoring on a prototype of the system (prototype-based evaluation). Automotive communications systems face an extremely hostile electrical environment (strong electromagnetic disturbances). To assume it is a 100% reliable medium is irresponsible in the face of such reality. So, the authors focus on transmission errors that may cause missed deadlines because of retransmitting corrupted frames. They propose using a flexible error-model for assessing the transmission's reliability and for designing well-suited message scheduling policies     

Maximizing the Robustness of TDMA Networks with Applications to TTP/C

In this study we show how one can use Fault-Tolerant Units (FTU) in an optimal way to make a TDMA network robust to bursty random perturbations. We consider two possible objectives. If one wants to minimize the probability of losing all replicas of a given message, then the optimal policy is to spread the replicas over time. This is proved using convexity properties of the loss probability. On the contrary if one wants to minimize the probability of losing at least one replica, then the optimal solution is to group all replicas together. This is proved by using majorization techniques. Finally we show how these ideas can be adapted for the TTP/C protocol. Bruno Gaujal is a research director at INRIA Rhone-Alpes since 2003 where he is the leader of the group on large scale networks. He has held several positions in INRIA Sophia-Antipolis, Loria and ENS-Lyon before. His main interest are performance evaluation and control of discrete event dynamic systems. Nicolas Navet received the M.S. in Computer Science from the University of Berlin (Germany) in 1994 and the PhD in Computer Science from the University of Nancy in 1999. Before joining the INRIA (LORIA Lab.) in November 2000, he was research scientist at Gemplus Software. His research interests include scheduling theory, the design of communication protocols for real-time and fault-tolerant data transmission and probabilistic risk evaluation when transient faults may occur (for instance, due to electromagnetic interferences). More information on his work can be found at url http://www.loria.fr/~nnavet.     

Trends in Automotive Communication Systems

The use of networks for communications between the electronic control units (ECU) of a vehicle in production cars dates from the beginning of the 1990s. The specific requirements of the different car domains have led to the development of a large number of automotive networks such as Local Interconnect Network, J1850, CAN, TTP/C, FlexRay, media-oriented system transport, IDB1394, etc. This paper first introduces the context of in-vehicle embedded systems and, in particular, the requirements imposed on the communication systems. Then, a comprehensive review of the most widely used automotive networks, as well as the emerging ones, is given. Next, the current efforts of the automotive industry on middleware technologies, which may be of great help in mastering the heterogeneity, are reviewed. Finally, we highlight future trends in the development of automotive communication systems.     

Timing Analysis of Compound Scheduling Policies: Application to Posix1003.1B

The analysis of fixed priority preemptive scheduling has been extended in various ways to improve its usefulness for the design of real-time systems. In this paper, we define the layered preemptive priority scheduling policy which generalizes fixed preemptive priorities by combination with other policies in a layered structure. In particular, the combination with the Round Robin scheduling policy is studied. Its compliance with Posix 1003.1b requirements is shown and its timing analysis is provided. For this purpose and as a basis for the analysis of other policies, the concept of majorizing work arrival function, is introduced to synthesize essential ideas used in existing analysis of the fixed preemptive priority policy.If critical resources are protected by semaphores, the Priority Ceiling Protocol (PCP) can be used under fixed preemptive priorities to control resulting priority inversions. An extension of the PCP is proposed for Round Robin, to allow a global control of priority inversions under the layered priority policy and to prevent deadlocks. The initial timing analysis is extended to account for the effects of the protocol. The results are illustrated by a small test case.     

Fine-Tuning MAC-Level Protocols for Optimized Real-Time QoS

In distributed real-time systems, meeting the real-time constraints is mandatory, but the satisfaction of other application-dependent criteria is most generally required as well. In particular, networked control systems (NCS) are known to be sensitive to communication delays such as frame response time jitters. Well-known medium access control (MAC) algorithms such as non-preemptive deadline monotonic (NP-DM) or non-preemptive earliest deadline first (NP-EDF) are efficient in terms of bandwidth usage, but they may perform poorly regarding other application-dependent performance criteria. This paper highlights a class of online scheduling policies targeted at scheduling frames at the MAC level, and it provides a schedulability analysis that is valid for all policies within the considered class. As it will be shown, these algorithms are implementable on COTS components (e.g., Controller Area Network controllers) and offer good trade-offs between feasibility and the satisfaction of other application-dependent criteria such as the response time jitter.