This page intentionally left blank BURNSWELL:“BURNS” — 2007/4/27 — 20:22 — PAGE ii — #2 CONCURRENT AND REAL-TIME PROGRAMMING IN ADA AdaistheonlyISOstandard,object-oriented,concurrent,real-timeprogramminglanguage. It isintended foruseinlarge, long-lived applications wherereliabilityandefficiencyareessen- tial,particularlyreal-timeandembeddedsystems.Inthisbook,AlanBurnsandAndyWellings give a thorough, self-contained account of how the Ada tasking model can be used to con- structawiderangeofconcurrentandreal-timesystems. Thisistheonlybookthatfocuseson anin-depth discussionoftheAdataskingmodel. Followingonfrom theauthors’ earliertitle ‘ConcurrencyinAda’,thisbookbringsthediscussionuptodatetoincludethenewAda2005 languageandtherecentadvancesinreal-timeprogramming techniques. Itwillbeofvalueto software professionals and advanced students of programming alike; indeed, every Ada pro- grammerwillfinditessentialreadingandaprimaryreferenceworkthatwillsitalongsidethe languagereferencemanual. ALANBURNSisaProfessorinComputerScienceattheUniversityofYork. Hisresearchac- tivitieshavecoveredanumberofaspectsofreal-timeandsafetycriticalsystems,includingthe assessment of languages for use in the real-time safety critical domain, distributed operating systems,theformalspecificationofschedulingalgorithms andimplementationstrategies,and thedesignofdependable userinterfacestosafetycriticalapplications. Histeachingactivities include courses in Operating Systems, Scheduling and Real-time Systems. He has authored over370papersandreportsand8books,including‘Real-timeSystemsandProgrammingLan- guages’ (3rd Edition), ‘Concurrency in Ada’ (2nd Edition) and ‘Concurrent and Real-Time ProgramminginJava’. ANDYWELLINGSisaProfessorofReal-TimeSystemsintheComputerScienceDepartment 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 andExperience’ andamemberoftheInternational Expert Groups currentlydevelopingextensionstotheJavaplatformforreal-time,safetycriticalanddistributed programming. Hehasauthoredover280papersandseveralbooks, including‘Real-timeSys- temsandProgrammingLanguages’(3rdedition)and‘ConcurrencyinAda’(2ndedition). BURNSWELL:“BURNS” — 2007/4/27 — 20:22 — PAGE i — #1 BURNSWELL:“BURNS” — 2007/4/27 — 20:22 — PAGE ii — #2 CONCURRENT AND REAL-TIME PROGRAMMING IN ADA 2005 ALAN BURNS AND ANDY WELLINGS UniversityofYork BURNSWELL:“BURNS” — 2007/4/27 — 20:22 — PAGE iii — #3 CAMBRIDGEUNIVERSITYPRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo Cambridge University Press The Edinburgh Building, Cambridge CB28RU, UK Published in the United States of America by Cambridge University Press, New York www.cambridge.org Information on this title: www.cambridge.org/9780521866972 © A. Burns and A. 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 pagexi 1 Introduction 1 1.1 Concurrency 2 1.2 Real-timesystems 3 1.3 Ada’stimeandclockfacilities 6 1.4 Summary 13 1.5 Further reading 13 2 Thenatureandusesofconcurrentprogramming 15 2.1 Usesofconcurrent programming 17 2.2 Program entities 18 2.3 Process representation 20 2.4 A simple embedded system 21 2.5 Summary 30 2.6 Further reading 30 3 Inter-process communication 31 3.1 Data communication 32 3.2 Synchronisation 33 3.3 Deadlocks and indefinite postponements 34 3.4 Systemperformance, correctness andreliability 36 3.5 Diningphilosophers problem 38 3.6 Sharedvariablesandprotected variables 39 3.7 Semaphores 41 3.8 Monitors 44 3.9 Message-based communication 48 3.10 Summary 53 3.11 Further reading 54 v BURNSWELL:“BURNS” — 2007/4/27 — 20:22 — PAGE v — #5 vi Contents 4 Tasktypesandobjects 55 4.1 Taskcreation 57 4.2 Taskactivation, execution, finalisation andtermination 65 4.3 Taskhierarchies 70 4.4 Taskidentification 75 4.5 Taskcreation, communication andsynchronisation withintask finalisation 77 4.6 Summary 77 5 Therendezvous 79 5.1 Thebasicmodel 79 5.2 Theentrystatement 81 5.3 Theacceptstatement 83 5.4 TheCountattribute 88 5.5 Entryfamilies 88 5.6 Three-waysynchronisation 90 5.7 Privateentries 92 5.8 Exceptions andtherendezvous 93 5.9 Taskstates 94 5.10 Summary 94 6 Theselectstatementandtherendezvous 97 6.1 Selectiveaccept 97 6.2 Guardedalternatives 101 6.3 Delayalternative 103 6.4 Theelsepart 107 6.5 Thecorrectuseofguards 109 6.6 Theterminatealternative 111 6.7 Theexception Program Error 116 6.8 Summaryoftheselectiveacceptstatement 118 6.9 Conditional andtimedentrycalls 118 6.10 Mutualexclusionanddeadlocks 121 6.11 Thediningphilosophers 124 6.12 Taskstates 127 6.13 Summary 127 7 Protectedobjectsanddata-oriented communication 129 7.1 Protectedobjects 129 7.2 Mutualexclusion 131 7.3 Condition synchronisation 133 7.4 Entrycallsandbarriers 135 7.5 Privateentriesandentryfamilies 139 BURNSWELL:“BURNS” — 2007/4/27 — 20:22 — PAGE vi — #6 Contents vii 7.6 Restrictions onprotected objects 142 7.7 Accessvariablesandprotected types 144 7.8 Elaboration, finalisation andexceptions 146 7.9 Shareddata 147 7.10 Thereadersandwritersproblem 148 7.11 Thespecification ofsynchronisation agents 151 7.12 Sharedvariables 152 7.13 Volatileandatomicdata 156 7.14 Taskstates 160 7.15 Summary 161 8 Avoidancesynchronisation andtherequeuefacility 163 8.1 Theneedforrequeue 163 8.2 Semanticsofrequeue 175 8.3 Requeuing tootherentities 179 8.4 Real-timesolutions totheresource controlproblem 183 8.5 Entryfamiliesandservertasks 186 8.6 Extended example 190 8.7 Taskstates 193 8.8 Summary 194 9 Exceptions,abortandasynchronoustransferofcontrol 195 9.1 Exceptions 195 9.2 Theabortstatement 198 9.3 Asynchronous transfer ofcontrol 200 9.4 Understanding theasynchronous selectstatement 212 9.5 Arobustreadersandwritersalgorithm 217 9.6 Taskstates 221 9.7 Summary 221 10 Object-oriented programmingandtasking 223 10.1 TheAda2005OOPmodel 224 10.2 Tasksandinterfaces 231 10.3 Protected typesandinterfaces 239 10.4 Synchronized interfaces 244 10.5 Summary 246 10.6 Furtherreading 246 11 Concurrencyutilities 247 11.1 Communication andsynchronisation abstractions 248 11.2 Semaphores 248 11.3 Locks 257 11.4 Signals 263 BURNSWELL:“BURNS” — 2007/4/27 — 20:22 — PAGE vii — #7 viii Contents 11.5 Eventvariables 264 11.6 Buffers 266 11.7 Blackboards 268 11.8 Broadcasts 269 11.9 Barriers 276 11.10 Concurrent executionabstractions 277 11.11 Callablesandfutures 278 11.12 Executors 280 11.13 Completionservices 284 11.14 Imageprocessing examplerevisited 288 11.15 Summary 291 12 Taskingandsystemsprogramming 293 12.1 Devicedrivingandinterrupt handling 296 12.2 Modelofinterrupts 300 12.3 Taskidentifiers 311 12.4 Taskattributes 313 12.5 Summary 316 12.6 Furtherreading 316 13 Schedulingreal-timesystems–fixedprioritydispatching 317 13.1 Scheduling 317 13.2 Fixedprioritydispatching 319 13.3 Priorityceilinglocking 322 13.4 Entryqueuepolicies 327 13.5 Activepriorities anddispatching policies 327 13.6 Summary 329 13.7 Furtherreading 329 14 Schedulingreal-timesystems–otherdispatchingfacilities 331 14.1 Non-preemptive dispatching 331 14.2 Round-robin dispatching 332 14.3 Earliestdeadlinefirstdispatching 335 14.4 Mixedscheduling 347 14.5 Dynamicpriorities 348 14.6 Synchronous andasynchronous taskcontrol 354 14.7 Summary 359 14.8 Furtherreading 359 15 Timingeventsandexecution-timecontrol 361 15.1 Eventsandeventhandling 361 15.2 Timingevents 362 15.3 Dualpriorityscheduling 366 BURNSWELL:“BURNS” — 2007/4/27 — 20:22 — PAGE viii — #8