Preface ........................................................ xv
Editors ...................................................... xvii
Contributors .................................................. xix
1 Introduction and Overview
Insup Lee, Joseph Y-T. Leung and Sang Hyuk Son ............. 1-1
1.1 Introduction .......................................... 1-1
1.2 Overview .............................................. 1-2
I Real-Time Scheduling and Resource Management
2 Real-Time Scheduling and Resource Management
Giorgio C. Buttazzo ........................................ 2-1
2.1 Introduction .......................................... 2-1
2.2 Periodic Task Handling ................................ 2-3
2.3 Handling Aperiodic Tasks .............................. 2-7
2.4 Handling Shared Resources ............................. 2-9
2.5 Overload Management .................................. 2-12
2.6 Conclusions .......................................... 2-14
3 Schedulability Analysis of Multiprocessor Sporadic Task
Systems
Theodore P. Baker and Sanjoy K. Baruah ..................... 3-1
3.1 Introduction .......................................... 3-1
3.2 Definitions and Models ................................ 3-2
3.3 Dynamic Priority Scheduling ........................... 3-4
3.4 Fixed Job-Priority Scheduling ......................... 3-5
3.5 Fixed Task-Priority Scheduling ....................... 3-10
3.6 Relaxations of the Sporadic Model .................... 3-13
3.7 Conclusion ........................................... 3-15
4 Rate-Based Resource Allocation Methods
Kevin Jeffay ............................................... 4-1
4.1 Introduction .......................................... 4-1
4.2 Traditional Static Priority Scheduling ................ 4-3
4.3 A Taxonomy of Rate-Based Allocation Models ............ 4-4
4.4 Using Rate-Based Scheduling ........................... 4-9
4.5 Hybrid Rate-Based Scheduling ......................... 4-12
4.6 Summary and Conclusions .............................. 4-13
5 Compositional Real-Time Schedulability Analysis
Insik Shin and Insup Lee ................................... 5-1
5.1 Introduction .......................................... 5-1
5.2 Compositional Real-Time Scheduling Framework .......... 5-3
5.3 Workload Models ....................................... 5-6
5.4 Resource Models ....................................... 5-7
5.5 Schedulability Analysis ............................... 5-9
5.6 Schedulable Workload Utilization Bounds .............. 5-12
5.7 Extension ............................................ 5-16
5.8 Conclusions .......................................... 5-18
6 Power-Aware Resource Management Techniques for Low-Power
Embedded Systems
Jihong Kim and Tajana Simunic Rosing ....................... 6-1
6.1 Introduction .......................................... 6-1
6.2 Dynamic Voltage Scaling ............................... 6-2
6.3 Dynamic Power Management .............................. 6-8
6.4 Conclusions .......................................... 6-12
7 Imprecise Computation Model: Total Weighted Error and
Maximum Weighted Error
Joseph Y-T. Leung .......................................... 7-1
7.1 Introduction .......................................... 7-1
7.2 Total Weighted Error .................................. 7-3
7.3 Maximum Weighted Error ................................ 7-9
7.4 Concluding Remarks ................................... 7-13
8 Imprecise Computation Model: Bicriteria and Other
Related Problems
Joseph Y-T. Leung .......................................... 8-1
8.1 Introduction .......................................... 8-1
8.2 Total w-Weighted Error with Constraints ............... 8-2
8.3 Maximum w'-Weighted Error with Constraints ............ 8-3
8.4 0/1-Constraints ....................................... 8-6
8.5 Conclusions .......................................... 8-10
9 Stochastic Analysis of Priority-Driven Periodic Real-
Time Systems
José Luis Díaz, Kanghee Kim, José María López,
Lucia Lo Bello, Daniel E García, Chang-Gun Lee,
Sang Lyul Min and Orazio Mirabella ......................... 9-1
9.1 Introduction .......................................... 9-1
9.2 Related Work .......................................... 9-2
9.3 System Model .......................................... 9-3
9.4 Stochastic Analysis Framework ......................... 9-4
9.5 Steady-State Backlog Analysis ........................ 9-12
9.6 Computational Complexity ............................. 9-15
9.7 Experimental Results ................................. 9-17
9.8 Conclusions and Future Work .......................... 9-22
II Programming Languages, Paradigms, and Analysis for
Real-Time and Embedded Systems
10 Temporal Control in Real-Time Systems: Languages and
Systems
Sebastian Fischmeister and Insup Lee ...................... 10-1
10.1 Introduction ......................................... 10-1
10.2 The Model ............................................ 10-3
10.3 The Example: A Stopwatch ............................. 10-4
10.4 Implicit Temporal Control ............................ 10-6
10.5 Programming with Temporal Control .................... 10-7
10.6 Comparison and Conclusions .......................... 10-18
11 The Evolution of Real-Time Programming
Christoph M. Kirsch and Raja Sengupta ..................... 11-1
11.1 Introduction ......................................... 11-1
11.2 The Computing Abstractions of Control Engineering .... 11-3
11.3 Physical-Execution-Time Programming .................. 11-6
11.4 Bounded-Execution-Time Programming ................... 11-7
11.5 Zero-Execution-Time Programming ..................... 11-10
11.6 Logical-Execution-Time Programming .................. 11-12
11.7 Networked Real-Time Systems ......................... 11-14
12 Real-Time Java
Andy Wettings and Alan Burns .............................. 12-1
12.1 Introduction ......................................... 12-1
12.2 Background on the RTSJ ............................... 12-2
12.3 Scheduling Objects and Scheduling .................... 12-3
12.4 Resource Sharing and Synchronization ................. 12-9
12.5 Time Values and Clocks .............................. 12-11
12.6 Memory Management ................................... 12-13
12.7 Conclusions ......................................... 12-17
13 Programming Execution-Time Servers and Supporting EDF
Scheduling in Ada 2005
Alan Burns and Andy Wettings .............................. 13-1
13.1 Introduction ......................................... 13-1
13.2 The Ada 95 Version of the Language ................... 13-3
13.3 New Ada 2005 Features ................................ 13-3
13.4 Programming Execution-Time Servers ................... 13-8
13.5 Support for Deadlines ............................... 13-14
13.6 Baker's Preemption Level Protocol for Protected
Objects ............................................. 13-15
13.7 Supporting EDF Scheduling in Ada .................... 13-15
13.8 Mixed Dispatching Systems ........................... 13-19
13.9 Conclusion .......................................... 13-20
13.10 Postscript—Ada and Java ............................ 13-20
14 Synchronous Programming
Paul Caspi, Pascal Raymond and Stavros Tripakis ........... 14-1
14.1 Introduction ......................................... 14-1
14.2 From Practice ........................................ 14-2
14.3 To Theory ............................................ 14-3
14.4 Some Languages and Compilers ......................... 14-5
14.1 Back to Practice .................................... 14-14
14.6 Conclusions and Perspectives ........................ 14-19
III Operating Systems and Middleware for Real-Time and
Embedded Systems
15 QoS-Enabled Component Middleware for Distributed
Real-Time and Embedded Systems
Gan Deng, Douglas C. Schmidt, Christopher D. Gill and
Nanbor Wang ............................................... 15-1
15.1 Introduction ......................................... 15-1
15.2 R&D Challenges for DRE Systems ....................... 15-2
15.3 Comparison of Middleware Paradigms ................... 15-2
15.4 Achieving QoS-Enabled Component Middleware: CIAO,
DAnCE, and CoSMIC .................................... 15-5
15.5 Applications of CIAO, DAnCE, and CoSMIC .............. 15-9
15.6 Related Work ........................................ 15-13
15.7 Concluding Remarks .................................. 15-14
16 Safe and Structured Use of Interrupts in Real-Time and
Embedded Software
John Regehr ............................................... 16-1
16.1 Introduction ......................................... 16-1
16.2 Interrupt Definitions and Semantics .................. 16-2
16.3 Problems in Interrupt-Driven Software ................ 16-4
16.4 Guidelines for Interrupt-Driven Embedded Software .... 16-9
16.5 Conclusions ......................................... 16-12
17 QoS Support and an Analytic Study for USB l.x/2.0
Devices
Chih-Yuan Huang, Shi-Wu Lo, Tei-Wei Kuo and Ai-Chun Pang .. 17-1
17.1 Introduction ......................................... 17-1
17.2 QoS Guarantees for USB Subsystems .................... 17-6
17.3 Summary ............................................. 17-18
18 Reference Middleware Architecture for Real-Time and
Embedded\Systems: A Case for Networked Service Robots
Saehwa Kim and Seongsoo Hong .............................. 18-1
18.1 Introduction ......................................... 18-1
18.2 Robot Middleware Requirements ........................ 18-2
18.3 Reference Robot Middleware Architecture .............. 18-4
18.4 Future Challenges of Robot Middleware ............... 18-10
18.5 Conclusions ......................................... 18-12
IV Real-Time Communications/Sensor Networks
19 Online QoS Adaptation with the Flexible Time-Triggered
(FTT) Communication Paradigm
Luis Almeida, Paulo Pedreiras, Joaquim Ferreira,
Mário Calha, José Alberto Fonseca, Ricardo Marau,
Valter Silva and Ernesto Martins ......................... 19-12
19.1 Introduction ......................................... 19-1
19.2 Toward Operational Flexibility ....................... 19-2
19.1 The Flexible Time-Triggered Paradigm ................. 19-5
19.4 The Synchronous Messaging System ..................... 19-8
19.5 The Asynchronous Messaging System ................... 19-14
19.6 Case Study: A Mobile Robot Control System ........... 19-17
19.7 Conclusions ......................................... 19-19
20 Wireless Sensor Networks
John A. Stankovic ......................................... 20-1
20.1 Introduction ......................................... 20-1
20.2 MAC .................................................. 20-2
20.3 Routing .............................................. 20-2
20.4 Node Localization .................................... 20-4
20.5 Clock Synchronization ................................ 20-5
20.6 Power Management ..................................... 20-5
20.7 Applications and Systems ............................. 20-6
20.8 Conclusions .......................................... 20-9
21 Messaging in Sensor Networks: Addressing Wireless
Communications and Application Diversity
Hongwei Zhang, Anish Arora, Prasun Sinha and Loren
J. Kittle ................................................. 21-1
21.1 Introduction ......................................... 21-1
21.2 SMA: An Architecture for Sensornet Messaging ......... 21-2
21.3 Data-Driven Link Estimation and Routing .............. 21-6
21.4 Related Work ........................................ 21-17
21.5 Concluding Remarks .................................. 21-18
22 Real-Time Communication for Embedded Wireless Networks
Marco Caccamo and Tarek Abdelzaher ........................ 22-1
22.1 Introduction ......................................... 22-1
22.2 Basic Concepts for Predictable Wireless
Communication ........................................ 22-2
22.3 Robust and Implicit Earliest Deadline First .......... 22-3
22.4 Higher-Level Real-Time Protocols for Sensor
Networks ............................................. 22-9
22.5 Real-Time Capacity of Wireless Networks ............. 22-11
22.6 Concluding Remarks .................................. 22-13
23 Programming and Virtualization of Distributed
Multitasking Sensor Networks
Azer Bestavros and Michael J. Ocean ....................... 23-1
23.1 Introduction ......................................... 23-1
23.2 The SNAFU Programming Language ....................... 23-4
23.3 Sensorium Task Execution Plan ........................ 23-7
23.4 The Sensorium Service Dispatcher ..................... 23-9
23.5 Sensorium Execution Environments .................... 23-12
23.6 Putting It All Together ............................. 23-16
23.7 Related Work ........................................ 23-18
23.8 Conclusion .......................................... 23-19
V Real-Time Database/Data Services
24 Data-Intensive Services for Real-Time Systems
Krithi Ramamritham, Lisa Cingiser DiPippo and Sang Hyuk
Son ....................................................... 24-1
24.1 Introduction ......................................... 24-1
24.2 Data Freshness and Timing Properties ................. 24-4
24.3 Transaction Processing ............................... 24-6
24.4 Quality of Service in Real-Time Data Services ....... 24-12
24.5 Data Services in Sensor Networks .................... 24-17
24.6 Mobile Real-Time Databases .......................... 24-18
24.7 Dissemination of Dynamic Web Data ................... 24-20
24.8 Conclusion .......................................... 24-21
25 Real-Time Data Distribution
Angela Uvarov Frolov, Lisa Cingiser DiPippo and Victor
Fay-Wolfe ................................................. 25-1
25.1 Introduction to Real-Time Data Distribution .......... 25-1
25.2 Real-Time Data Distribution Problem Space ............ 25-1
25.3 Approaches to Real-Time Data Distribution ............ 25-5
25.4 Conclusion .......................................... 25-16
26 Temporal Consistency Maintenance for Real-Time Update
Transactions Ming Xiong and Krithi Ramamritham .......... 26-1
26.1 Introduction ......................................... 26-1
26.2 More-Less Using EDF .................................. 26-3
26.3 More-Less Using Deadline Monotonic ................... 26-7
26.4 Deferrable Scheduling ................................ 26-8
26.5 Conclusions ......................................... 26-17
27 Salvaging Resources by Discarding Irreconcilably
Conflicting Transactions in Firm Real-Time Database
Systems
Victor C.S. Lee, Joseph Kee-Yin Ng and Ka Man Ho .......... 27-1
27.1 Introduction ......................................... 27-1
27.2 Related Work ......................................... 27-3
27.3 A New Priority Cognizant CC Algorithm ................ 27-5
27.4 Experiments .......................................... 27-6
27.5 Results .............................................. 27-8
27.6 Conclusion .......................................... 27-13
28 Application-Tailored Databases for Real-Time Systems
Aleksandra Tešanović and Jörgen Hansson ................... 28-1
28.1 Introduction ......................................... 28-1
28.2 Dimensions of Tailorability .......................... 28-2
28.3 Tailorable Real-Time and Embedded Database Systems ... 28-3
28.4 The COMET Approach ................................... 28-6
28.5 Summary ............................................. 28-16
29 DeeDS NG: Architecture, Design, and Sample Application
Scenario
Sten F. Andler, Marcus Brohede, Sanny Gustavsson and
Gunnar Mathiason .......................................... 29-1
29.1 Introduction ......................................... 29-1
29.2 Active Research Problems ............................. 29-4
29.3 DeeDS NG ............................................. 29-5
29.4 Related Work ........................................ 29-16
29.5 Summary ............................................. 29-17
VI Formalisms, Methods, and Tools
30 State Space Abstractions for Time Petri Nets
Bernard Berthomieu and François Vernadat .................. 30-1
30.1 Introduction ......................................... 30-1
30.2 Time Petri Nets and Their State Space ................ 30-2
30.3 State Space Abstractions Preserving Markings and
Traces ............................................... 30-5
30.4 State Space Abstractions Preserving States and
Traces ............................................... 30-8
30.5 Abstractions Preserving States and Branching
Properties .......................................... 30-13
30.6 Computing Experiments ............................... 30-15
30.7 Conclusion and Further Issues ....................... 30-16
31 Process-Algebraic Analysis of Timing and Schedulability
Properties
Anna Philippou and Oleg Sokolsky .......................... 31-1
31.1 Introduction ......................................... 31-1
31.2 Modeling of Time-Sensitive Systems ................... 31-4
31.3 Modeling of Resource-Sensitive Systems ............... 31-9
31.4 Conclusions ......................................... 31-19
32 Modular Hierarchies of Models for Embedded Systems
Manfred Broy .............................................. 32-1
32.1 Motivation ........................................... 32-1
32.2 Comprehensive System Modeling Theory ................. 32-3
32.3 Structuring Interfaces .............................. 32-10
32.4 Refinement .......................................... 32-15
32.5 Composition and Combination ......................... 32-18
32.6 Modeling Time ....................................... 32-20
32.7 Perspective, Related Work, Summary, and Outlook ..... 32-23
33 Metamodeling Languages and Metaprogrammable Tools
Matthew Emerson, Sandeep Neema and Janos Sztipanovits ..... 33-1
33.1 Introduction ......................................... 33-1
33.2 Modeling Tool Architectures and
Metaprogrammability .................................. 33-3
33.3 A Comparison of Metamodeling Languages ............... 33-9
33.4 Relating Metamodeling Languages and
Metaprogrammable Tools .............................. 33-14
33.5 Conclusion .......................................... 33-16
34 Hardware/Software Codesign
Wayne Wolf ................................................ 34-1
34.1 Introduction ......................................... 34-1
34.2 Hardware/Software Partitioning Algorithms ............ 34-2
34.3 Cosynthesis Algorithms ............................... 34-4
34.4 CPU Customization .................................... 34-5
34.5 Codesign and System Design ........................... 34-6
34.6 Summary .............................................. 34-7
35 Execution Time Analysis for Embedded Real-Time Systems
Andreas Ermedahl and Jakob Engblom ........................ 35-1
35.1 Introduction ......................................... 35-1
35.2 Software Behavior .................................... 35-4
35.3 Hardware Timing ...................................... 35-5
35.4 Timing by Measurements ............................... 35-8
35.1 Timing by Static Analysis ........................... 35-10
35.6 Hybrid Analysis Techniques .......................... 35-15
35.7 Tools for WCET Analysis ............................. 35-15
35.8 Industrial Experience with WCET Analysis Tools ...... 35-15
35.9 Summary ............................................. 35-17
VII Experiences with Real-Time and Embedded Systems
36 Dynamic QoS Management in Distributed Real-Time
Embedded Systems
Joseph P. Loyall and Richard E. Schantz ................... 36-1
36.1 Introduction ......................................... 36-1
36.2 Issues in Providing QoS Management in DRE Systems .... 36-2
36.3 Solutions for Providing QoS Management in DRE
Systems .............................................. 36-5
36.4 Case Studies of Providing QoS Management ............ 36-12
36.5 Conclusions ......................................... 36-30
37 Embedding Mobility in Multimedia Systems and
Applications
Heonshik Shin ............................................. 37-1
37.1 Introduction ......................................... 37-1
37.2 Challenges for Mobile Computing with Multimedia ...... 37-2
37.3 System-Layer Approaches .............................. 37-4
37.4 Application-Layer Approaches ......................... 37-9
37.5 Conclusions ......................................... 37-14
38 Embedded Systems and Software Technology in the
Automotive Domain
Manfred Broy .............................................. 38-1
38.1 Introduction ......................................... 38-1
38.2 The History .......................................... 38-2
38.3 State of Practice Today .............................. 38-2
38.4 The Domain Profile ................................... 38-3
38.5 The Future ........................................... 38-4
38.6 Practical Challenges ................................. 38-6
38.7 Research Challenges ................................. 38-11
38.8 Comprehensive Research Agenda ....................... 38-16
38.9 Conclusion .......................................... 38-18
39 Real-Time Data Services for Automotive Applications
Gurulingesh Raravi, Krithi Ramamritham and Neera Sharma ... 39-1
39.1 Introduction ......................................... 39-1
39.2 Real-Time Data Issues in Automotive Applications ..... 39-2
39.3 Adaptive Cruise Control: An Overview ................. 39-5
39.4 Our Goals and Our Approach ........................... 39-7
39.5 Specifics of the Dual Mode System .................... 39-8
39.6 Specifics of the Real-Time Data Repository .......... 39-10
39.7 Robotic Vehicle Control: Experimental Setup ......... 39-12
39.8 Results and Observations ............................ 39-13
39.9 Related Work ........................................ 39-17
39.10 Conclusions and Further Work ....................... 39-18
Index ......................................................... 1-1
|
