Real-time Systems Scheduling 2 E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: ISTE
• Sprache: Englisch

Seitenzahl: 320

Veröffentlichungsjahr: 2014

Beschreibung

Real-time systems are used in a wide range of applications, including control, sensing, multimedia, etc. Scheduling is a central problem for these computing/communication systems since it is responsible for software execution in a timely manner. This book, the second of two volumes on the subject, brings together knowledge on specific topics and discusses the recent advances for some of them. It addresses foundations as well as the latest advances and findings in real-time scheduling, giving comprehensive references to important papers, but the chapters are short and not overloaded with confusing details. Coverage includes scheduling approaches for networks and for energy autonomous systems. Other sophisticated issues, such as feedback control scheduling and probabilistic scheduling, are also addressed. This book can serve as a textbook for courses on the topic in bachelor's degrees and in more advanced master's degree programs. It also provides a reference for computer scientists and engineers involved in the design or the development of Cyber-Physical Systems which require up-to-date real-time scheduling solutions.

Leseprobe

Contents

Preface

List of Figures

List of Tables

1 Scheduling in Energy Autonomous Objects

1.1. Introduction

1.2. Modeling and terminology

1.3. Weaknesses of classical schedulers

1.4. Fundamental properties

1.5. Concepts related to energy

1.6. ED-H scheduling

1.7. Conclusion

1.8. Bibliography

2 Probabilistic Scheduling

2.1. Introduction

2.2. Notations and definitions

2.3. Modeling a probabilistic real-time system

2.4. Imposed properties

2.5. Worst-case probabilistic models

2.6. Probabilistic real-time scheduling

2.7. Probabilistic schedulability analysis

2.8. Classification of the main existing results

2.9. Bibliography

3 Control and Scheduling Joint Design

3.1. Control objectives and models

3.2. Scheduling of control loops

3.3. Continuous approach: regulated scheduling

3.4. Discrete approach: scheduling under the (m,k)-firm constraint

3.5. Case study: regulated scheduling of a video decoder

3.6. Conclusion

3.7. Bibliography

4 Synchronous Approach and Scheduling

4.1. Introduction

4.2. Classification

4.3. Synchronous languages

4.4. Scheduling with synchronous languages

4.5. Synchronous languages extended to perform scheduling

4.6. Conclusion

4.7. Bibliography

5 Inductive Approaches for Packet Scheduling in Communication Networks

5.1. Introduction

5.2. Scheduling problem

5.3. Approaches for real-time scheduling.

5.4. Basic concepts

5.5. Proposed model

5.6. Q-learning with approximation

5.7. Conclusion

5.8. Acknowledgment

5.9. Bibliography

6 Scheduling in Networks

6.1. Introduction

6.2. The CAN protocol

6.3. Example of an automotive embedded application distributed around a CAN network

6.4. Response time analysis of CAN messages

6.5. Conclusion and discussion

6.6. Bibliography

7 Focus on Avionics Networks

7.1. Introduction

7.2. Avionics network architectures

7.3. Temporal analysis of an AFDX network

7.4. Properties of a worst-case scenario

7.5. Calculating an upper bound of the delay

7.6. Results on an embedded avionic configuration

7.7. Conclusion

7.8. Bibliography

List of Authors

Index

Summary of Volume 1

First published 2014 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK

www.iste.co.uk

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA

www.wiley.com

© ISTE Ltd 2014The rights of Maryline Chetto to be identified as the author of this work have been asserted by her in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2014946162

British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-84821-789-8

Preface

We refer to a system as real-time when it has to meet deadlines when reacting to stimuli produced by an external environment. Punctuality therefore constitutes the most important quality of a real-time computer system, which, moreover, distinguishes it from conventional computer systems. We refer to a system as embedded when it is physically integrated into a physical device whose control and command it ensures, which have a particular impact on its sizing and the selection of its components.

The rapid evolution of microelectronic techniques and communication infrastructures in recent years has led to the emergence of often-miniaturized interconnected embedded systems (wireless nodes processing data coming from sensors), leading to the birth of the concept of the “Internet of things”. The real-time qualifier therefore remains relevant for all these autonomous and intelligent objects as it was in the 1970s with the advent of microcomputers, when this qualifier was restricted to industrial process controlling systems.

The large variety of appliances in which real-time systems are now integrated requires increasingly strict constraints to be taken into account in terms of physical size, computational power, memory capacity, energy storage capacity and so on, in their design. It is therefore in this direction that research efforts have turned for several years.

Every piece of software with real-time application is composed of tasks, programs whose execution requires a concurrent access to shared resources limited in number (processor, memory, communication medium). This raises the central issue of scheduling whose solution leads to a planning of tasks that respects the time constraints.

Since the early 1970s, in particular following the publication of the crucial article by Liu and Layland, research activity in the field of real-time scheduling, both through its theoretical results and integration in operating systems, has allowed us to overcome numerous technological barriers.

Real-Time Systems Scheduling constitutes a learning support regarding real-time scheduling intended for instructors, master’s degree students and engineering students. It also aims to describe the latest major progress in research and development for scientists and engineers. The book groups together around 30 years of expertise from French and Belgian universities specialized in real-time scheduling. It was originally published in French and has now been translated into English.

This book is composed of two volumes with a total of 13 chapters.

Volume 1 entitled Fundamentals is composed of six chapters and should be of interest as a general course on scheduling in real-time systems. Reading the chapters in order, from 1 through to 6, is recommended but not necessary. Volume 1 is structured as follows: Chapter 1 constitutes a conceptual introduction to real-time scheduling. Chapters 2 and 3, respectively, deal with uniprocessor and multiprocessor real-time scheduling. Chapter 4 discusses results on scheduling tasks with resource requirements. Chapter 5 relates to the scheduling issue in energy-constrained systems. Chapter 6 presents the techniques of computing the worst-case execution time (WCET) for tasks.

Volume 2 entitled Focuses is composed of seven chapters. This volume aims at collecting knowledge on specific topics and discussing the recent advances for some of them. After reading Chapter 1 of Volume 1, a reader can move to any chapters of Volume 2 in any order. Volume 2 is structured as follows: Chapter 1 highlights the newer scheduling issues raised by the so-called energy-autonomous real-time systems. In Chapter 2, the authors consider a probabilistic modelization of the WCET in order to tackle the scheduling problem. In Chapter 3, the authors show how automatic control can benefit real-time scheduling. Chapter 4 deals with the synchronous approach for scheduling. In Chapter 5, the authors focus on the optimization of the Quality-of-Service in routed networks. Chapter 6 is devoted to the scheduling of messages in industrial networks. Finally, Chapter 7 pertains specifically to resolution techniques used in avionic networks such as AFDX.

Maryline CHETTOJuly 2014

List of Figures

Chapter 1

Figure 1.1. Diagram of an ambient energy harvesting system

Figure 1.2. The RTEH model

Figure 1.3. Schedule produced by EDF with ASAP

Figure 1.4. Schedule produced by EDF with ALAP

Figure 1.5. Schedule produced by ED-H

Chapter 2

Figure 2.1. Two vehicles reversing with radars emitting on the same frequency might not “see” each other

Figure 2.2. Hierarchy of models used to describe real-time systems. The arrows indicate the relations between the models

Figure 2.3. Possible relations between the CDFs of various random variables

Figure 2.4. The arrivals defined using the number of arrivals in an interval may correspond to different situations

Figure 2.5. Rate monotonic scheduling

Figure 2.6. A feasible assignment of priorities

Chapter 3

Figure 3.1. Principle of feedback control

Figure 3.2. Digital implementation of a control loop

Figure 3.3. Probability distribution of the execution time of a task

Figure 3.4. a) Relaxation of constraints b) Stability and sample Losses

Figure 3.5. Control architecture with regulated scheduling

Figure 3.6. State-transition diagram of a task with (2,3)-firm

Figure 3.7. Drone – axes and coordinate system

Figure 3.8. Stabilization of the axes a) without loss b) with controlled losses

Figure 3.9. Frame controls and computing speed

Figure 3.10. Frame control

Figure 3.11. Experimental results

Chapter 4

Figure 4.1. Interaction between processes and the control system

Figure 4.2. Scope of application of synchronous languages for the specification of a real-time implementation problem

Figure 4.3. Precedence relation between events of a signal

Figure 4.4. Synchrony relations between events of two signals

Figure 4.5. Signal synchrony relation

Figure 4.6. Immediate function S3:= F(S1,S2)

Figure 4.7. The instruction X:= A when B

Figure 4.8. The instruction Y:= X0 default X1

Figure 4.9. The instruction ZX:= X $ 1 init 0

Figure 4.13. Two operations – one with a fast period, the other with a slow period

Chapter 5

Figure 5.1. Abstract view of an agent in its environment in RL

Figure 5.2. Approximation of the Q-function. The input layer is made up of states and actions. The output layer has a single neuron which contains the Q-value for current entry values

Figure 5.3. Mean delay for two classes of traffic

Figure 5.4. Mean flow rate for two classes of traffic

Figure 5.5. Mean delay through the network (scenario 1)

Figure 5.6. Mean delay through the network (scenario 2)

Chapter 6

Figure 6.1. Example of application of an FIP fieldbus

Figure 6.2. FIP polling table of the example with the periodic variables A, B and C

Figure 6.3. Arbitration of CAN medium access

Figure 6.4. The bit stuffing method

Figure 6.5. Example of a PSA application

Chapter 7

Figure 7.1. A small AFDX network

Figure 7.2. Example of an AFDX configuration

Figure 7.3. Frame transmission scenario

Figure 7.4. Scenario maximizing the delay of v1 over mi1

Figure 7.5. Candidate worst-case scenario

Figure 7.6. Another candidate worst-case scenario

Figure 7.7. Scenario without hole in the sequence c1 – c2

Figure 7.8. Scenario with a hole in the sequence c1 – c2

Figure 7.9. Traffic envelope of a VL

Figure 7.10. Maximum delay h(F,B)

Figure 7.11. Curve of v1 output from mi1

Figure 7.12. Envelope of the link m1 – c1

Figure 7.13. The trajectories for AFDX

Figure 7.14. A worst-case scenario

Figure 7.15. An AFDX configuration

Figure 7.16. Worst-case scenario for v1

Figure 7.17. A worst-case scenario with v8 added

Figure 7.18. A typical AFDX configuration

Figure 7.19. Network link load

List of Tables

Chapter 4

Table 4.2. Primitive instructions of the signal language

Chapter 5

Table 5.1. Simulation parameters (scenario 1)

Table 5.2. Simulation parameters (scenario 2)

Chapter 6

Table 6.1. Format of a CAN frame

Table 6.2. Specification of the messaging system

Table 6.3. Numerical example of the CAN messaging system

Table 6.4. Specification of the messaging system

Chapter 7

Table 7.1. Characteristics of VLs

Table 7.2. BAGs and frame lengths of an industrial application

Table 7.3. VL path lengths

1

Scheduling in Energy Autonomous Objects

Maryline CHETTO

In an autonomous system, in other words a system supplied during its entire lifetime by ambient energy, the issue of scheduling must be addressed in jointly taking into account the two physical constraints: time and energy. The fundamental scheduling questions can be raised as follows: is a scheduler as efficient, simple and high-performance as earliest deadline first (EDF) is appropriate? Is there, in this new context of perpetual energy autonomy, a scheduler which is optimal with acceptable implementation costs? How do we dimension the energy storage unit in such a way that no energy starvation, and therefore no deadline violation can occur at any time?

This chapter proposes to answer these questions according to the following plan: