logo资料库

Deadline Scheduling for Real-Time Systems EDF and Related Algori....pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：21.51M 资料格式：pdf 举报 版权申诉
第1页 / 共290页
第2页 / 共290页
第3页 / 共290页
第4页 / 共290页
第5页 / 共290页
第6页 / 共290页
第7页 / 共290页
第8页 / 共290页
资料共290页，剩余部分请下载后查看
    DEADL~DULING DEADL~DULING FOR REAL-TIME SYSTEMS FOR REAL-TIME SYSTEMS EDF and Related Algoritluns EDF and Related Algoritluns
    THE KLUWER INTERNATIONAL SERIES THE KLUWER INTERNATIONAL SERIES IN ENGINEERING AND COMPUTER SCIENCE IN ENGINEERING AND COMPUTER SCIENCE REAL-TIME SYSTEMS REAL-TIME SYSTEMS Consulting Editor Consulting Editor John A. Stankovic John A. Stankovic HARD REAL-TIME COMPUTING SYSTEMS: Predictable Scheduling Algorithms and HARD REAL-TIME COMPUTING SYSTEMS: Predictable Scheduling Algorithms and Applications, by Giorgio C. Buttazzo, ISBN: 0-7923-9994-3 Applications, by Giorgio C. Buttazzo, ISBN: 0-7923-9994-3 REAL-TIME DATABASE AND INFORJ\iATION RESEARCH ADVANCES, by Azer REAL-TIME DATABASE AND INFORJ\iATION RESEARCH ADVANCES, by Azer Bestavros, Victor Wolfe, ISBN: 0-7923-8011-8 Bestavros, Victor Wolfe, ISBN: 0-7923-8011-8 REAL-TIME SYSTEMS: Design Principles for Distributed Embedded Applications, by REAL-TIME SYSTEMS: Design Principles for Distributed Embedded Applications, by Hennann Kopetz, ISBN: 0-7923-9894-7 Hennann Kopetz, ISBN: 0-7923-9894-7 REAL-TIME DATABASE SYSTEMS: Issues alld Applications, edited by Azer REAL-TIME DATABASE SYSTEMS: Issues alld Applications, edited by Azer Bestavros, Kwei-Jay Lin and Sang Hyuk Son, ISBN: 0-7923-9897-1 Bestavros, Kwei-Jay Lin and Sang Hyuk Son, ISBN: 0-7923-9897-1 FAULT-TOLERANT REAL-TIME SYSTEMS: The Problem ofReplica Determinism, FAULT-TOLERANT REAL-TIME SYSTEMS: The Problem ofReplica Determinism, by Stefan Poledna, ISBN: 0-7923-9657-X by Stefan Poledna, ISBN: 0-7923-9657-X RESPONSIVE COMPUTER SYSTEMS: Steps Toward Fault-Tolerant Real-Time RESPONSIVE COMPUTER SYSTEMS: Steps Toward Fault-Tolerant Real-Time Systems, by Donald Fussell and Miroslaw Malek, ISBN: 0-7923-9563-8 Systems, by Donald Fussell and Miroslaw Malek, ISBN: 0-7923-9563-8 IMPRECISE AND APPROXIMATE COMPUTATION, by Swaminathan Natarajan, IMPRECISE AND APPROXIMATE COMPUTATION, by Swaminathan Natarajan, ISDN: 0-7923-9579-4 ISDN: 0-7923-9579-4 FOUNDATIONS OF DEPENDABLE COMPUTING: System Implementation, edited FOUNDATIONS OF DEPENDABLE COMPUTING: System Implementation, edited by Gary M. Koob and Clifford G. Lau, ISBN: 0-7923-9486-0 by Gary M. Koob and Clifford G. Lau, ISBN: 0-7923-9486-0 FOUNDATIONS OF DEPENDABLE COMPUTING: Paradigms for Dependable FOUNDATIONS OF DEPENDABLE COMPUTING: Paradigms for Dependable Applications, edited by Gary M. Koob and Clifford G. Lau, ISBN: 0-7923-9485-2 Applications, edited by Gary M. Koob and Clifford G. Lau, ISBN: 0-7923-9485-2 FOUNDATIONS OF DEPENDABLE COMPUTING: Models and Frameworks for FOUNDATIONS OF DEPENDABLE COMPUTING: Models and Frameworks for Depelldable Systems, edited by Gary M. Koob and Clifford G. Lau, ISBN: 0-7923-9484-4 Depelldable Systems, edited by Gary M. Koob and Clifford G. Lau, ISBN: 0-7923-9484-4 THE TESTABILITY OF DISTRIBUTED REAL-TIME SYSTEMS, THE TESTABILITY OF DISTRIBUTED REAL-TIME SYSTEMS, Werner Schlitz; ISBN: 0-7923-9386-4 Werner Schlitz; ISBN: 0-7923-9386-4 A PRACTITIONER'S HANDBOOK FOR REAL-TIME ANALYSIS: Guide to Rate A PRACTITIONER'S HANDBOOK FOR REAL-TIME ANALYSIS: Guide to Rate llfollotollic Analysis for Real-Time Systems, Carnegie Mellon University (Mark Klein, llfollotollic Analysis for Real-Time Systems, Carnegie Mellon University (Mark Klein, Thomas Ralya, Bill Pollak, Ray Obenza, Michale Gonzalez Harbour); Thomas Ralya, Bill Pollak, Ray Obenza, Michale Gonzalez Harbour); ISBN: 0-7923-9361-9 ISBN: 0-7923-9361-9 FORMAL TECHNIQUES IN REAL-TIME FAULT-TOLERANT SYSTEMS, J. FORMAL TECHNIQUES IN REAL-TIME FAULT-TOLERANT SYSTEMS, J. Vytopil; ISBN: 0-7923-9332-5 Vytopil; ISBN: 0-7923-9332-5 SYNCHRONOUS PROGRAMMING OF REACTIVE SYSTEMS, N. Halbwachs; SYNCHRONOUS PROGRAMMING OF REACTIVE SYSTEMS, N. Halbwachs; ISBN: 0-7923-9311-2 ISBN: 0-7923-9311-2 REAL-TIME SYSTEMS ENGINEERING AND APPLICATIONS, M. Schiebe, S. REAL-TIME SYSTEMS ENGINEERING AND APPLICATIONS, M. Schiebe, S. Pferrer; ISBN: 0-7923-9196-9 Pferrer; ISBN: 0-7923-9196-9 SYNCHRONIZATION IN REAL-TIME SYSTEMS: A Priority Inheritance Approach, SYNCHRONIZATION IN REAL-TIME SYSTEMS: A Priority Inheritance Approach, R. Rajkumar; ISBN: 0-7923-9211-6 R. Rajkumar; ISBN: 0-7923-9211-6 CONSTRUCTING PREDICTABLE REAL TIME SYSTEMS, W. A. Halang, A. D. CONSTRUCTING PREDICTABLE REAL TIME SYSTEMS, W. A. Halang, A. D. Stoyenko; ISBN: 0-7923-9202-7 Stoyenko; ISBN: 0-7923-9202-7 FOUNDATIONS OF REAL-TIME COMPUTING: Formal Specificatiolls and Met/lOds, FOUNDATIONS OF REAL-TIME COMPUTING: Formal Specificatiolls and Met/lOds, A. M. van Tilborg, G. M. Koob; ISBN: 0-7923-9167-5 A. M. van Tilborg, G. M. Koob; ISBN: 0-7923-9167-5 FOUNDATIONS OF REAL-TIME COMPUTING: Scheduling alld Resource FOUNDATIONS OF REAL-TIME COMPUTING: Scheduling alld Resource Managemellt, A. M. van Tilborg, G. M. Koob; ISBN: 0-7923-9166-7 Managemellt, A. M. van Tilborg, G. M. Koob; ISBN: 0-7923-9166-7 REAL-TIME UNIX SYSTEMS: Design alldApplication Guide, B. Furht, D. Grostick, REAL-TIME UNIX SYSTEMS: Design alldApplication Guide, B. Furht, D. Grostick, D. Gluch, G. Rabbat, J. Parker, M. McRoberts, ISBN: 0-7923-9099-7 D. Gluch, G. Rabbat, J. Parker, M. McRoberts, ISBN: 0-7923-9099-7
    ~~! . ~~! . ,.'"" ,.'"" G(H G(H 70 =D~E~A~D~L=I~N~E~S=C=H~E~D~U~LI=N~G= 70 =D~E~A~D~L=I~N~E~S=C=H~E~D~U~LI=N~G= I::J Y FOR REAL-TIME SYSTEMS I::J Y FOR REAL-TIME SYSTEMS Otl3 Otl3 jCfc)g jCfc)g /I/;-///\} ////-)//\} EDF and Related Algorithms EDF and Related Algorithms by by (i..i 3}'!; 912- (i..i 3}'!; 912- / / ! ! I I Jobn A. Stankovic Jobn A. Stankovic University of Virginia University of Virginia Charlottesville, Virginia, USA Charlottesville, Virginia, USA ;- ;- Marco Spuri Marco Spuri Merloni Elettrodomestici Spa Merloni Elettrodomestici Spa Fabriano, Italy Fabriano, Italy Kritbi Ramamritbam Kritbi Ramamritbam University ofMassachusetts University ofMassachusetts Amherst, Massachusetts, USA Amherst, Massachusetts, USA Giorgio C. Buttazzo Giorgio C. Buttazzo Scuola Superiore S. Anna Scuola Superiore S. Anna Pisa, Italy Pisa, Italy KLUWER ACADEMIC PUBLISHERS KLUWER ACADEMIC PUBLISHERS Boston / Dordrecht / London Boston / Dordrecht / London
    Distributors for North, Central and South America: Distributors for North, Central and South America: Kluwer Academic Publishers Kluwer Academic Publishers 101 Philip Drive 101 Philip Drive Assinippi Park Assinippi Park Norwell, Massachusetts 02061 USA Norwell, Massachusetts 02061 USA Telephone (781) 871-6600 Telephone (781) 871-6600 Fax (781) 871-6528 Fax (781) 871-6528 E-Mail E-Mail Distributors for all other countries: Distributors for all other countries: Kluwer Academic Publishers Group Kluwer Academic Publishers Group Distribution Centre Distribution Centre Post Office Box 322 Post Office Box 322 3300 AH Dordrecht, THE NETHERLANDS 3300 AH Dordrecht, THE NETHERLANDS Telephone 31 78 6392 392 Telephone 31 78 6392 392 Fax 31 786546474 Fax 31 786546474 E-Mail E-Mail .... .... , . ElectrOniC Services , . Electromc Services . . . . Library of Congress Cataloging-in-Publication Data Library of Congress Cataloging-in-Publication Data Deadline scheduling for real-time systems: EDF and related algorithms Deadline scheduling for real-time systems: EDF and related algorithms / by John A. Stankovic ... [et al.]. / by John A. Stankovic ... [et al.]. p. p. cm. -- (The Kluwer international series in engineering and cm. -- (The Kluwer international series in engineering and computer science; SECS 460. Real-time systems) computer science; SECS 460. Real-time systems) Includes bibliographical references and index. Includes bibliographical references and index. ISBN 0-7923-8269-2 (alk. paper) ISBN 0-7923-8269-2 (alk. paper) I. Real-time data processing. 2. Computer algorithms. I. Real-time data processing. 2. Computer algorithms. I. Stankovic, John. A. II. Series: Kluwer I. Stankovic, John. A. II. Series: Kluwer III. Series; Kluwer international series in engineering and III. Series; Kluwer international series in engineering and 3. Scheduling. 3. Scheduling. international series in engineering and computer science ; SECS international series in engineering and computer science ; SECS 460. 460. computer science. Real-time systems. computer science. Real-time systems. QA76.54.043 1998 QA76.54.043 1998 004' .33 -- dc21 004' .33 -- dc21 98-39004 98-39004 crp crp Copyright © 1998 by Kluwer Academic Publishers Copyright © 1998 by Kluwer Academic Publishers All rights reserved. No part of this publication may be reproduced, stored in a All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any fonn or by any means, mechanical, photo retrieval system or transmitted in any fonn or by any means, mechanical, photo copying, recording, or otherwise, without the prior written pennission of the copying, recording, or otherwise, without the prior written pennission of the publisher, Kluwer Academic Publishers, 101 Philip Drive, Assinlppi Park, Norwell, publisher, Kluwer Academic Publishers, 101 Philip Drive, Assimppi Park, Norwell, Massachusetts 02061 Massachusetts 02061 Printed on acid~free paper. Printed on acid~free paper. Printed in the United States of America Printed in the United States of America The cover of this book was designed by Curtis Buyrn. The cover of this book was designed by Curtis Buyrn.
    CONTENTS CONTENTS LIST OF FIGURES LIST OF FIGURES LIST OF TABLES LIST OF TABLES PREFACE PREFACE 1 1 INTRODUCTION INTRODUCTION 1.1 Real-Time Systems 1.1 Real-Time Systems 1.2 Common Misconceptions 1.2 Common Misconceptions 1.3 A Typical Example of a Real-Time Application 1.3 A Typical Example of a Real-Time Application 1.4 1.4 1.5 1.5 Purpose of this Book Purpose of this Book FormaL of the Book FormaL of the Book REFERENCES REFERENCES 2 2 TERMINOLOGY AND ASSUMPTIONS TERMINOLOGY AND ASSUMPTIONS 2.1 2.1 2.2 2.2 2.3 Metrics 2.3 Metrics Task Models, Assumptions and Notation Task Models, Assumptions and Notation Static versus Dynamic Scheduling Static versus Dynamic Scheduling REFERENCES REFERENCES 3 3 FUNDAMENTALS OF EDF SCHEDULING FUNDAMENTALS OF EDF SCHEDULING 3.1 Optimality on Uni-Processor Systems 3.1 Optimality on Uni-Processor Systems 3.2 3.2 3.3 3.3 Feasibility Analysis Feasibility Analysis Summary Summary ix ix xiii xiii xv xv 1 1 1 1 4 4 4 4 7 7 8 8 11 11 13 13 14 14 19 19 22 22 25 25 27 27 28 28 31 31 61 61
    Vl Vl DEADLINE SCHEDULING FOR REAL-TIME SYSTEMS DEADLINE SCHEDULING FOR REAL-TIME SYSTEMS REFERENCES REFERENCES 4 RESPONSE TIMES UNDER EDF 4 RESPONSE TIMES UNDER EDF SCHEDULING SCHEDULING Finding Local Maxima 4.1 4.1 Finding Local Maxima 4.2 Deadline Busy Periods 4.2 Deadline Busy Periods 4.3 Algorithm Description 4.3 Algorithm Description 4.4 Extended Task Modeling 4.4 Extended Task Modeling 4.5 Case Study 4.5 Case Study 4.6 4.6 Summary Summary REFERENCES REFERENCES 5 5 PLANNING-BASED SCHEDULING PLANNING-BASED SCHEDULING Preliminaries: Load, Metrics, Value Functions 5.1 5.1 Preliminaries: Load, Metrics, Value Functions 5.2 5.2 Steps in a Dynamic Planning-Based Scheduling Approach Steps in a Dynamic Planning-Based Scheduling Approach 5.3 Algorithms for Dynamic Planning 5.3 Algorithms for Dynamic Planning 5.4 Timing of the Planning 5.4 Timing of the Planning 5.5 5.5 5.6 Dispatching Jobs in a Planning-based Schedule 5.6 Dispatching Jobs in a Planning-based Schedule 5.7 5.7 Implementing Planning-Based Scheduling Implementing Planning-Based Scheduling Summary Summary REFERENCES REFERENCES 6 6 EDF SCHEDULING FOR SHARED EDF SCHEDULING FOR SHARED RESOURCES RESOURCES 6.1 The Nature of Resources and the Resulting Scheduling Prob- 6.1 The Nature of Resources and the Resulting Scheduling Prob- lems lems 6.2 The Priority Inversion Problem 6.2 The Priority Inversion Problem 6.3 The Priority Inheritance Protocol 6.3 The Priority Inheritance Protocol 6.4 The Dynamic Priority Ceiling Protocol 6.4 The Dynamic Priority Ceiling Protocol 6.5 The Stack Resource Policy 6.5 The Stack Resource Policy 6.6 Resource Scheduling in Planning-based Schedulers 6.6 Resource Scheduling in Planning-based Schedulers 6.7 6.7 Summary Summary REFERENCES REFERENCES 63 63 67 67 68 68 71 71 73 73 74 74 82 82 83 83 85 85 87 87 91 91 98 98 101 101 111 111 113 113 114 114 116 116 117 117 121 121 122 122 125 125 127 127 HO HO 142 142 144 144 147 147 149 149
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料