Concurrent and Real-Time Programming in Ada

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Preface......Page 13
Real-time systems research at York......Page 15
Acknowledgements......Page 16
1 Introduction......Page 17
1.1 Concurrency......Page 18
1.2 Real-time systems......Page 19
1.3 Ada’s time and clock facilities......Page 22
Delay primitives......Page 27
1.5 Further reading......Page 29
2 The nature and uses of concurrent programming......Page 31
2.1 Uses of concurrent programming......Page 33
2.2 Program entities......Page 34
2.3 Process representation......Page 36
2.4 A simple embedded system......Page 37
2.4.1 Sequential solution......Page 39
2.4.2 Using operating system primitives......Page 41
2.4.3 Using a concurrent programming language......Page 43
2.4.4 Operating-systems-defined versus language-defined concurrency......Page 45
2.6 Further reading......Page 46
3 Inter-process communication......Page 47
3.1 Data communication......Page 48
3.2 Synchronisation......Page 49
3.3 Deadlocks and indefinite postponements......Page 50
3.4 System performance, correctness and reliability......Page 52
3.5 Dining philosophers problem......Page 54
3.6 Shared variables and protected variables......Page 55
3.7 Semaphores......Page 57
3.8 Monitors......Page 60
3.9 Message-based communication......Page 64
Selective waiting......Page 65
The rendezvous......Page 66
Remote invocation/extended rendezvous......Page 67
3.9.1 Asynchronous communication in Ada......Page 68
3.10 Summary......Page 69
3.11 Further reading......Page 70
4 Task types and objects......Page 71
4.1 Task creation......Page 73
4.1.1 Anonymous task types......Page 77
4.1.2 Task access types......Page 78
Primes by sieve example......Page 79
4.2.1 Task activation......Page 81
Program errors during task creation and activation......Page 84
Tasks states without task hierarchies......Page 85
4.3.1 Task creation with task hierarchies......Page 86
4.3.2 Task termination with task hierarchies......Page 88
Task termination and dynamic tasks......Page 90
4.4 Task identification......Page 91
4.6 Summary......Page 93
5.1 The basic model......Page 95
5.2 The entry statement......Page 97
5.3 The accept statement......Page 99
Primes by sieve example (revisited)......Page 102
Synchronisation without communication......Page 103
5.5 Entry families......Page 104
5.6 Three-way synchronisation......Page 106
5.7 Private entries......Page 108
5.8 Exceptions and the rendezvous......Page 109
5.10 Summary......Page 110
6.1 Selective accept......Page 113
Waiting for more than a single rendezvous at any one time......Page 114
6.2 Guarded alternatives......Page 117
6.3 Delay alternative......Page 119
Guards and the delay alternative......Page 121
Unnecessary use of the delay alternative......Page 122
6.4 The else part......Page 123
The delay alternative and the else part......Page 124
6.5 The correct use of guards......Page 125
6.6 The terminate alternative......Page 127
6.6.1 Last wishes......Page 130
6.7 The exception......Page 132
6.9 Conditional and timed entry calls......Page 134
6.9.1 Timed entry calls......Page 135
6.9.2 Conditional entry call......Page 136
6.10 Mutual exclusion and deadlocks......Page 137
6.11 The dining philosophers......Page 140
6.13 Summary......Page 143
7.1 Protected objects......Page 145
7.2 Mutual exclusion......Page 147
7.3 Condition synchronisation......Page 149
7.4 Entry calls and barriers......Page 151
The Count attribute......Page 153
7.5 Private entries and entry families......Page 155
7.6 Restrictions on protected objects......Page 158
7.7 Access variables and protected types......Page 160
7.8 Elaboration, finalisation and exceptions......Page 162
7.9 Shared data......Page 163
7.10 The readers and writers problem......Page 164
7.11 The specification of synchronisation agents......Page 167
7.12 Shared variables......Page 168
7.13 Volatile and atomic data......Page 172
Mutual exclusion and Simpson’s algorithm......Page 175
7.14 Task states......Page 176
7.15 Summary......Page 177
8.1 The need for requeue......Page 179
8.1.1 The resource allocation problem......Page 180
Using entry families......Page 181
The double interaction solution......Page 183
8.1.2 Solutions using language support......Page 187
Requeue example – concurrent solution to the resource control problem......Page 188
8.2 Semantics of requeue......Page 191
8.3 Requeuing to other entities......Page 195
8.4 Real-time solutions to the resource control problem......Page 199
8.5 Entry families and server tasks......Page 202
8.6 Extended example......Page 206
8.7 Task states......Page 209
8.8 Summary......Page 210
Unhandled exceptions during task execution......Page 211
Exceptions and the rendezvous......Page 212
Exceptions in interrupt handlers......Page 213
9.2 The abort statement......Page 214
9.2.1 Abort-deferred operations......Page 215
9.3 Asynchronous transfer of control......Page 216
9.3.1 The user need for ATC......Page 217
9.3.2 The asynchronous select statement......Page 218
Exceptions and ATC......Page 221
Error recovery......Page 223
Deadline overrun detection......Page 224
Mode changes......Page 225
Partial/imprecise computations......Page 226
9.4.2 Comparison with timed entry calls......Page 228
9.4.3 Multiple entry calls......Page 230
9.4.4 Interaction with requeue......Page 232
9.5 A robust readers and writers algorithm......Page 233
9.7 Summary......Page 237
10 Object-oriented programming and tasking......Page 239
10.1.1 The prefix notation......Page 240
10.1.2 Interfaces......Page 241
10.1.4 Synchronized, protected and task interfaces......Page 245
10.2 Tasks and interfaces......Page 247
10.2.1 Image processing example......Page 252
10.3 Protected types and interfaces......Page 255
Disk controller example......Page 258
10.4 Synchronized interfaces......Page 260
10.6 Further reading......Page 262
Warning: It is beyond the scope of this book to provide a definitive set of......Page 263
11.2 Semaphores......Page 264
11.2.1 Binary semaphores......Page 267
11.2.2 Quantity semaphores......Page 269
11.3 Locks......Page 273
11.4.1 Transient signals......Page 279
11.5 Event variables......Page 280
11.6 Buffers......Page 282
11.7 Blackboards......Page 284
11.8 Broadcasts......Page 285
11.8.1 Multicast to a group......Page 286
11.9 Barriers......Page 292
11.10 Concurrent execution abstractions......Page 293
11.11 Callables and futures......Page 294
11.12 Executors......Page 296
11.13 Completion services......Page 300
11.14 Image processing example revisited......Page 304
11.15 Summary......Page 307
12 Tasking and systems programming......Page 309
12.1.1 Representation aspects......Page 312
12.2.1 Handling interrupts using protected procedures......Page 316
12.2.2 A simple driver example......Page 319
12.2.3 Dynamic attachment of interrupt handlers......Page 322
12.2.4 User-implemented timers......Page 323
12.3 Task identifiers......Page 327
12.3.1 Secure resource control......Page 328
12.4 Task attributes......Page 329
12.4.1 Periodic scheduling – an example of task attributes......Page 330
12.6 Further reading......Page 332
13.1 Scheduling......Page 333
13.2 Fixed priority dispatching......Page 335
13.3 Priority ceiling locking......Page 338
13.5 Active priorities and dispatching policies......Page 343
13.7 Further reading......Page 345
14.1 Non-preemptive dispatching......Page 347
14.2 Round-robin dispatching......Page 348
14.3.1 Representing deadlines......Page 351
14.3.2 Dispatching......Page 354
14.3.3 EDF dispatching and the priority ceiling protocol......Page 355
14.3.4 An important constraint......Page 360
14.3.5 Example task set......Page 361
14.3.7 Other considerations......Page 362
14.4 Mixed scheduling......Page 363
14.5 Dynamic priorities......Page 364
14.5.1 Dynamic ceiling priorities for protected objects......Page 366
14.5.2 Mode change example......Page 367
14.6 Synchronous and asynchronous task control......Page 370
14.6.1 Synchronous task control......Page 371
14.6.2 Asynchronous task control......Page 373
14.8 Further reading......Page 375
15.1 Events and event handling......Page 377
15.2 Timing events......Page 378
15.3 Dual priority scheduling......Page 382
15.4 Execution-time clocks......Page 385
15.5 Execution-time timers......Page 387
15.6 Group budgets......Page 390
15.7 Task termination events......Page 403
15.9 Further reading......Page 405
16 Real-time utilities......Page 407
16.1 Real-time task state......Page 409
16.2 Real-time task release mechanisms......Page 411
16.3 Periodic release mechanisms......Page 413
16.4 Sporadic release mechanisms......Page 421
16.5 Aperiodic release mechanisms and execution-time servers......Page 423
Deferrable servers......Page 425
Banded sporadic servers......Page 427
16.6 Real-time tasks......Page 431
16.7.1 ACCS requirements......Page 435
16.7.3 Software design and implementation......Page 437
16.7.4 Putting it all together......Page 447
16.8 Summary......Page 448
17.1 Restricted tasking and other language features......Page 449
17.2 The Ravenscar profile......Page 452
17.3 Partition elaboration control......Page 455
17.4 Examples of the use of the Ravenscar profile......Page 456
17.5 Metrics and optimisations......Page 464
17.6 Summary......Page 465
17.7 Further reading......Page 466
18 Conclusion......Page 467
18.2 Support for real-time......Page 468
18.4 Outstanding issues and the future......Page 469
References......Page 471
Index......Page 473