This page intentionally left blank CO N CU RRE N T A N D RE A L - T I M E P RO G RA M M I N G I N A DA Ada is the only ISO standard, object-oriented, concurrent, real-time programming language. It is intended for use in large, long-lived applications where reliability and efficiency are essen- tial, particularly real-time and embedded systems. In this book, Alan Burns and Andy Wellings give a thorough, self-contained account of how the Ada tasking model can be used to con- struct a wide range of concurrent and real-time systems. This is the only book that focuses on an in-depth discussion of the Ada tasking model.
Following on from the authors’ earlier title ‘Concurrency in Ada’, this book brings the discussion up to date to include the new Ada 2005 language and the recent advances in real-time programming techniques. It will be of value to software professionals and advanced students of programming alike; indeed, every Ada pro- grammer will find it essential reading and a primary reference work that will sit alongside the language reference manual. ALAN B URNS is a Professor in Computer Science at the University of York. His research ac- tivities have covered a number of aspects of real-time and safety critical systems, including the assessment of languages for use in the real-time safety critical domain, distributed operating systems, the formal specification of scheduling algorithms and implementation strategies, and the design of dependable user interfaces to safety critical applications.
His teaching activities include courses in Operating Systems, Scheduling and Real-time Systems. He has authored over 370 papers and reports and 8 books, including ‘Real-time Systems and Programming Lan- guages’ (3rd Edition), ‘Concurrency in Ada’ (2nd Edition) and ‘Concurrent and Real-Time Programming in Java’. ANDY WELLINGS is a Professor of Real-Time Systems in the Computer Science Department at the University of York. He is interested in most aspects of the design and implementa- tion of real-time dependable computer systems and, in particular, in real-time programming languages and operating systems.
He is European Editor-in-Chief for the Computer Science journal ‘Software-Practice and Experience’ and a member of the International Expert Groups currently developing extensions to the Java platform for real-time, safety critical and distributed programming. He has authored over 280 papers and several books, including ‘Real-time Sys- tems and Programming Languages’ (3rd edition) and ‘Concurrency in Ada’ (2nd edition). CONCURRENT AND REAL-TIME P RO G R A M M I N G I N A DA 2 0 0 5 ALAN BURNS AND ANDY WELLINGS University of York CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK Published in the United States of America by Cambridge University Press, New York www.org Information on this title: www. Wellings 2007 This publication is in copyright.
Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published in print format 2007 ISBN-13 978-0-511-29663-5 eBook (NetLibrary) ISBN-10 0-511-29663-0 eBook (NetLibrary) ISBN-13 978-0-521-86697-2 hardback ISBN-10 0-521-86697-9 hardback Cambridge University Press has no responsibility for the persistence or accuracy of urls for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. Contents Preface page xi 1 Introduction 1 1.2 Real-time systems 3 1.3 Ada’s time and clock facilities 6 1.5 Further reading 13 2 The nature and uses of concurrent programming 15 2.1 Uses of concurrent programming 17 2.4 A simple embedded system 21 2.6 Further reading 30 3 Inter-process communication 31 3.3 Deadlocks and indefinite postponements 34 3.4 System performance, correctness and reliability 36 3.5 Dining philosophers problem 38 3.6 Shared variables and protected variables 39 3.9 Message-based communication 48 3.11 Further reading 54 v vi Contents 4 Task types and objects 55 4.2 Task activation, execution, finalisation and termination 65 4.5 Task creation, communication and synchronisation within task finalisation 77 4.6 Summary 77 5 The rendezvous 79 5.1 The basic model 79 5.2 The entry statement 81 5.3 The accept statement 83 5.4 The Count attribute 88 5.6 Three-way synchronisation 90 5.8 Exceptions and the rendezvous 93 5.10 Summary 94 6 The select statement and the rendezvous 97 6.4 The else part 107 6.5 The correct use of guards 109 6.6 The terminate alternative 111 6.7 The exception Program Error 116 6.8 Summary of the selective accept statement 118 6.9 Conditional and timed entry calls 118 6.10 Mutual exclusion and deadlocks 121 6.11 The dining philosophers 124 6.13 Summary 127 7 Protected objects and data-oriented communication 129 7.4 Entry calls and barriers 135 7.5 Private entries and entry families 139 Contents vii 7.6 Restrictions on protected objects 142 7.7 Access variables and protected types 144 7.8 Elaboration, finalisation and exceptions 146 7.10 The readers and writers problem 148 7.11 The specification of synchronisation agents 151 7.13 Volatile and atomic data 156 7.15 Summary 161 8 Avoidance synchronisation and the requeue facility 163 8.1 The need for requeue 163 8.2 Semantics of requeue 175 8.3 Requeuing to other entities 179 8.4 Real-time solutions to the resource control problem 183 8.5 Entry families and server tasks 186 8.8 Summary 194 9 Exceptions, abort and asynchronous transfer of control 195 9.2 The abort statement 198 9.3 Asynchronous transfer of control 200 9.4 Understanding the asynchronous select statement 212 9.5 A robust readers and writers algorithm 217 9.7 Summary 221 10 Object-oriented programming and tasking 223 10.1 The Ada 2005 OOP model 224 10.2 Tasks and interfaces 231 10.3 Protected types and interfaces 239 10.6 Further reading 246 11 Concurrency utilities 247 11.1 Communication and synchronisation abstractions 248 11.4 Signals 263 viii Contents 11.10 Concurrent execution abstractions 277 11.11 Callables and futures 278 11.14 Image processing example revisited 288 11.15 Summary 291 12 Tasking and systems programming 293 12.1 Device driving and interrupt handling 296 12.2 Model of interrupts 300 12.6 Further reading 316 13 Scheduling real-time systems – fixed priority dispatching 317 13.2 Fixed priority dispatching 319 13.3 Priority ceiling locking 322 13.4 Entry queue policies 327 13.5 Active priorities and dispatching policies 327 13.7 Further reading 329 14 Scheduling real-time systems – other dispatching facilities 331 14.1 Non-preemptive dispatching 331 14.2 Round-robin dispatching 332 14.3 Earliest deadline first dispatching 335 14.6 Synchronous and asynchronous task control 354 14.8 Further reading 359 15 Timing events and execution-time control 361 15.1 Events and event handling 361 15.3 Dual priority scheduling 366 Contents ix 15.4 Execution-time clocks 369 15.5 Execution-time timers 371 15.7 Task termination events 387 15.9 Further reading 389 16 Real-time utilities 391 16.1 Real-time task state 393 16.2 Real-time task release mechanisms 395 16.3 Periodic release mechanisms 397 16.4 Sporadic release mechanisms 405 16.5 Aperiodic release mechanisms and execution-time servers 407 16.6 Real-time tasks 415 16.7 The cruise control system example 419 16.8 Summary 432 17 Restrictions, metrics and the Ravenscar profile 433 17.1 Restricted tasking and other language features 433 17.2 The Ravenscar profile 436 17.3 Partition elaboration control 439 17.4 Examples of the use of the Ravenscar profile 440 17.5 Metrics and optimisations 448 17.7 Further reading 450 18 Conclusion 451 18.1 Support for concurrency 452 18.2 Support for real-time 452 18.3 New to Ada 2005 453 18.4 Outstanding issues and the future 453 References 455 Index 457 Preface The development of the Ada programming language forms a unique and, at times, intriguing contribution to the history of computer languages. As all users of Ada must know, the original language design was a result of competition between a number of organisations, each of which attempted to give a complete language definition in response to a series of documented requirements.
This gave rise to Ada 83. Following 10 years of use, Ada was subject to a complete overhaul. The resulting language, Ada 95, had a number of significant changes from its predeces- sor. A further 10 years of use has produced another version of Ada, known as Ada 2005, this time the changes are less pronounced and yet there are some key extra facilities, especially in the areas of real-time programming.
Closely linked to the development of Ada has been this book on its concurrent features. Starting out as ‘Concurrent Programming in Ada’, it became ‘Concur- rency in Ada’ when the Ada 95 version of the language was defined. There were two editions of this title. With the new features of Ada 2005, it has been decided to broaden the focus of the book to include real-time issues – hence this first edition of the new title ‘Concurrent and Real-Time Programming in Ada 2005’.
No prior knowledge of concurrent programming (in general) or of Ada tasking (in particu- lar) is assumed in this book. However, readers should have a good understanding of at least one high-level sequential programming language and some knowledge of operating system principles. This book is aimed both at professional software engineers and at students of computer science (and other related disciplines). Many millions of lines of Ada 83 and 95 code have been produced world wide, and over the next decade a wide range of new applications will be designed with Ada 2005 as the target language.
It is important that Ada programmers do not restrict themselves to a sequential subset of the language on the dubious assumption that tasking is not appropriate to their work, or for fear that the tasking model is too complex and expensive. Tasking is an integral part of the language, and programmers must be familiar with, xi xii Preface if not experienced in, its use. Due to space considerations, books that describe the entire language may not deal adequately with the tasking model; this book therefore concentrates exclusively on this model. Students studying real-time programming, software engineering, concurrent pro- gramming or language design should find this book useful in that it gives a compre- hensive description of the features that one language provides.
Ada is not merely a product of academic research (as are many concurrent programming languages) but is a language intended for actual use in industry. Its model of tasking was therefore integrated into the entire language design, and the interactions between tasking and non-tasking features were carefully defined. Consequently, the study of Ada’s model of concurrency should be included in those advanced courses men- tioned above. However, this does not imply that the full tasking model is free from controversy, has a proven formal semantic basis or is amenable to efficient imple- mentation.
The nature of these areas of ‘discussion’ are dealt with, as they arise in this book. Unlike Ada 83, which defined a single language, the Ada 95 and 2005 definitions have a core language design plus a number of domain-specific annexes. A compiler need not support all the annexes but it must support the core language. Most of the tasking features are contained in the core definition.
But there are relevant annexes that address systems programming and real-time programming. The first chapter provides a basic introduction to concurrent and real-time sys- tems and gives an overview of the clock facilities within Ada. Chapters 2 and 3 look in detail at the uses of concurrent programming and the inherent difficulties of providing inter-process communication. There is, as yet, no agreement on which primitives a concurrent programming language should support and, as a consequence, many different styles and forms exist.
In order to understand the Ada tasking model fully, it is necessary to appreciate these different approaches and the problems faced by the user of any language that supports multi-processing. The Ada task is introduced in Chapter 4 and the rendezvous and the important select statement are considered in the following two chapters. The rendezvous pro- vides a synchronous communication mechanism. Data-orientated asynchronous communication is considered in Chapter 7, together with the important abstraction of a protected object.