Hard Real-Time Computing Systems Predictable Scheduling Algorithms a
This updated edition offers an indispensable exposition on real-time computing, with particular emphasis on predictable scheduling algorithms. It introduces the fundamental concepts of real-time computing, demonstrates the most significant results in the
- PDF / 3,897,239 Bytes
- 527 Pages / 439.37 x 666.142 pts Page_size
- 250 Downloads / 1,096 Views
Real-Time Systems Series Series Editor John A. Stankovic University of Virginia, Virginia, USA
For further volumes: http://www.springer.com/series/6941
Giorgio C. Buttazzo
Hard Real-Time Computing Systems Predictable Scheduling Algorithms and Applications Third Edition
Giorgio C. Buttazzo RETIS Lab Scuola Superiore Sant’Anna Pisa Italy [email protected]
ISSN 1867-321X e-ISSN 1867-3228 e-ISBN 978-1-4614-0676-1 ISBN 978-1-4614-0675-4 DOI 10.1007/978-1-4614-0676-1 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2011937234
© Springer Science+Business Media, LLC 2011 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid- free paper Springer is part of Springer Science+Business Media (www.springer.com)
CONTENTS
Preface 1
A GENERAL VIEW 1.1 1.2 1.3
2
Introduction Types of task constraints Definition of scheduling problems Scheduling anomalies
APERIODIC TASK SCHEDULING 3.1 3.2 3.3 3.4 3.5 3.6
4
Introduction What does real time mean? Achieving predictability
BASIC CONCEPTS 2.1 2.2 2.3 2.4
3
ix
Introduction Jackson’s algorithm Horn’s algorithm Non-preemptive scheduling Scheduling with precedence constraints Summary
PERIODIC TASK SCHEDULING 4.1 4.2 4.3 4.4 4.5 4.6 4.7
Introduction Timeline scheduling Rate Monotonic scheduling Earliest Deadline First Deadline Monotonic EDF with constrained deadlines Comparison between RM and EDF
1 1 4 13 23 23 25 34 42 53 53 54 58 63 70 76 79 79 84 86 100 103 110 116 v
vi
5
Contents
FIXED-PRIORITY SERVERS 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10
6
DYNAMIC PRIORITY SERVERS 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 6.10
7
Introduction Background scheduling Polling Server Deferrable Server Priority Exchange Sporadic Server Slack stealing Non-existence of optimal servers Performance evaluation Summary
Introduction Dynamic Priority Exchange Server Dynamic Sporadic Server Total Bandwidth Server Earliest Deadline Late Server Improved Priority Exchange Server Improving TBS Performance evaluation The Constant Bandwidth Server Summary
RESOURCE ACCESS PROTOCOLS 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9 7.10
Introduction The priority inversion phenomenon Terminology and assumptions Non-Preemptive Protocol Highest Locker Priority Protocol Priority Inheritance Protocol Priority Ceiling Protocol Stack Resource Policy Schedulability analysis Summary
119 119 120 121 130 1
Data Loading...
