Wiley Global Education UK

Concurrency: State Models and Java Programs

Jeff Magee; Jeff Kramer

In stock

No reviews

16.000 KD inc. VAT

License

90 180 perpetual 150

Table of contents

Front Mattervi
Prefacexiii
What Can Readers Expect from this Book?xiii
Intended Readershipxiv
Additional Resourcesxv
Second Editionxv
Acknowledgmentsxvii
1 Introduction1
1.1 Concurrent Programs2
Figure 1.1 Cruise control system.3
Figure 1.2 Simulation of the cruise control system.3
1.2 The Modeling Approach4
Figure 1.3 Speed input process.6
Figure 1.4 Animation of the cruise control system.6
1.3 Practice7
1.4 Content Overview8
Summary9
Notes and Further Reading9
2 Processes and Threads11
2.1 Modeling Processes11
Figure 2.1 Light switch state machine.12
2.1.1 Action Prefix12
Figure 2.2 ONESHOT state machine.13
Figure 2.3 LTSA Animator window for SWITCH.14
Figure 2.4 TRAFFICLIGHT.14
2.1.2 Choice15
Figure 2.5 DRINKS state machine.15
Figure 2.6 LTSA Animator window for DRINKS.16
Figure 2.7 FAULTY.17
Non-Deterministic Choice17
Figure 2.8 COIN.17
Figure 2.9 LTSA Animator window for COIN.18
2.1.3 Indexed Processes and Actions18
Figure 2.10 BUFF.19
Figure 2.11 SUM.20
2.1.4 Process Parameters20
2.1.5 Guarded Actions21
Figure 2.12 COUNT.21
Figure 2.13 COUNTDOWN.22
2.1.6 Process Alphabets22
2.2 Implementing Processes23
2.2.1 Operating System Processes23
Figure 2.14 Operating system threads.24
2.2.2 Threads in Java24
Figure 2.15 Implementing run() using inheritance.25
Figure 2.16 Implementing run() using the Runnable interface.25
2.2.3 Thread Life Cycle25
Figure 2.17 THREAD life cycle.27
2.2.4 Countdown Timer Example27
Figure 2.18 Countdown timer class diagram.28
Program 2.1 NumberCanvas class.28
Program 2.2 CountDown applet class.29
Summary31
Notes and Further Reading31
Exercises32
3 Concurrent Execution37
Figure 3.1 Process switching.37
3.1 Modeling Concurrency38
3.1.1 Parallel Composition39
Figure 3.2 Composition CONVERSE_ITCH.40
Figure 3.3 Composition CLOCK_RADIO.41
3.1.2 Shared Actions41
Figure 3.4 Composition BILL_BEN.42
Figure 3.5 Composition MAKER_USER.43
Figure 3.6 Composition MAKER_USERv2.43
Figure 3.7 Composition FACTORY.44
3.1.3 Process Labeling45
Figure 3.8 Process labeling in TWO_SWITCH.46
Figure 3.9 Process labeling in RESOURCE_SHARE.47
3.1.4 Relabeling48
Figure 3.10 Relabelingin CLIENT_SERVER.49
3.1.5 Hiding49
Figure 3.11 Hiding applied to USER.50
Figure 3.12 Minimized LTS for USER.50
3.1.6 Structure Diagrams50
Figure 3.13 Structure diagram conventions.51
Figure 3.14 Two-slot buffer TWOBUF.52
3.2 Multi-Threaded Programs52
Figure 3.15 Resource-sharing PRINTER_SHARE.53
3.2.1 ThreadDemo Example - Model53
Figure 3.16 ThreadDemo display.53
Figure 3.17 ROTATOR.54
Figure 3.18 ThreadDemo model.55
Figure 3.19 LTSA Animator window for THREAD_DEMO.55
3.2.2 ThreadDemo Example – Implementation56
Program 3.1 Rotator class.56
Program 3.2 ThreadPanel class.57
Figure 3.20 ThreadDemo class diagram.58
Program 3.3 ThreadDemo applet class.58
Summary59
Notes and Further Reading59
Exercises60
4 Shared Objects and Mutual Exclusion63
4.1 Interference63
4.1.1 Ornamental Garden Problem63
Figure 4.1 Ornamental Garden.64
Figure 4.2 Ornamental Garden class diagram.64
Program 4.1 Turnstile class.65
Program 4.2 Counter class.66
Figure 4.3 Garden display.67
4.1.2 Ornamental Garden Model67
Figure 4.4 Ornamental Garden model.68
Figure 4.5 LTS for TURNSTILE.69
Figure 4.6 An Animator trace for the Ornamental Garden.70
4.2 Mutual Exclusion in Java71
Program 4.3 Corrected Counter class.72
Figure 4.7 Corrected Garden display.73
4.3 Modeling Mutual Exclusion73
Figure 4.8 Minimized LTS for COUNTER.75
Figure 4.9 Minimized LTS for DISPLAY_COUNTER76
Summary77
Notes and Further Reading77
Exercises78
5 Monitors and Condition Synchronization79
5.1 Condition Synchronization79
Figure 5.1 Car park display.80
5.1.1 Car Park Model80
Figure 5.2 Car park model.81
Figure 5.3 Car park LTS.81
5.1.2 Car Park Program81
Figure 5.4 Car park class diagram.82
Program 5.1 Arrivals and Departures classes.83
5.1.3 Condition Synchronization in Java83
Figure 5.5 Monitor wait( ) and notify( ).84
Program 5.2 CarParkControl monitor.86
5.2 Semaphores86
5.2.1 Modeling Semaphores87
Figure 5.6 Semaphore LTS.88
Figure 5.7 Semaphore mutual exclusion model.89
5.2.2 Semaphores in Java89
Figure 5.8 SEMADEMO LTS.90
Program 5.3 Semaphore class.90
Figure 5.9 SEMADEMO display.91
Program 5.4 Extended version of ThreadPanel class.92
Program 5.5 MutexLoop class.93
5.3 Bounded Buffers93
Figure 5.10 Bounded buffer display.94
5.3.1 Bounded Buffer Model94
Figure 5.11 Bounded buffer model.95
Figure 5.12 Bounded buffer LTS.95
5.3.2 Bounded Buffer Program95
Program 5.6 Buffer interface and BufferImpl class.96
Program 5.7 Producer and Consumer classes.97
5.4 Nested Monitors97
Program 5.8 Buffer class using semaphores.98
Program 5.9 Fixed bounded buffer using semaphores.100
5.5 Monitor Invariants101
Summary102
Notes and Further Reading103
Exercises104
6 Deadlock107
6.1 Deadlock Analysis108
Figure 6.1 MOVE process.109
Figure 6.2 Printer-scanner system.110
Figure 6.3 LTS for process P.110
Figure 6.4 LTSLTS for the shared printer process.111
6.2 Dining Philosophers Problem112
Figure 6.5 The Dining Philosophers table.112
Figure 6.6 Dining Philosophers composite model.113
6.2.1 Dining Philosophers Implementation114
Figure 6.7 Dining Philosophers class diagram.114
Program 6.1 Outline of PhilCanvas class.115
Program 6.2 Fork monitor.115
Program 6.3 Philosopher thread class.116
Figure 6.8 Dining Philosophers applet –executing.117
Figure 6.9 Dining Philosophers applet - deadlocked.118
6.2.2 Deadlock-Free Philosophers118
Summary119
Notes and Further Reading120
Exercises120
7 Safety and Liveness Properties123
7.1 Safety124
Figure 7.1 ACTUATOR LTS.124
7.1.1 Safety Properties125
Figure 7.2 property POLITE.125
Figure 7.3 property CALM.126
7.1.2 Safety Property for Mutual Exclusion126
7.2 Single-Lane Bridge Problem127
Figure 7.4 Single-lane bridge.127
7.2.1 Single-Lane Bridge Model128
Figure 7.5 SingleLaneBridge model.130
7.2.2 Single-Lane Bridge Implementation130
Figure 7.6 Single-lane bridge class diagram.131
Program 7.1 BridgeCanvas class.131
Program 7.2 RedCar and BlueCar classes.132
Program 7.3 Bridge class.133
Figure 7.7 Single-lane bridge display using Bridge class.133
Program 7.4 SafeBridge class.134
7.3 Liveness135
7.3.1 Progress Properties135
Figure 7.8 COIN model.135
Figure 7.9 TWOCOIN model.137
7.3.2 Progress Analysis137
7.3.3 Action Priority139
High Priority Operator (“<<”)139
Low Priority Operator (“>>”)139
Figure 7.10 Action priority.140
7.4 Liveness of the Single-Lane Bridge140
Figure 7.11 CongestedBridge model with two cars.142
Figure 7.12 CongestedBridge model with one car.142
7.4.1 Revised Single-Lane Bridge Model142
7.4.2 Revised Single-Lane Bridge Implementation144
Program 7.5 FairBridge class.145
7.5 Readers–Writers Problem146
7.5.1 Readers–Writers Model146
Safety Property147
Figure 7.13 READWRITELOCK LTS.148
Figure 7.14 READERS_WRITERS model.149
Progress Property149
Figure 7.15 RW_PROGRESS LTS.150
7.5.2 Readers-Writers Implementation150
Program 7.6 ReadWrite interface.151
Program 7.7 ReadWriteSafe class.151
Figure 7.16 Readers–Writers applet display.152
7.5.3 Revised Readers–Writers Model and Implementation153
Program 7.8 ReadWritePriority class.155
Summary155
Notes and Further Reading156
Exercises157
8 Model-Based Design159
8.1 From Requirements to Models160
8.1.1 A Cruise Control System161
Figure 8.1 Cruise control system.162
Figure 8.2 Hardware constraints.162
8.1.2 Structure of the Model162
Figure 8.3 Structure diagram for the cruise control system.163
8.1.3 Model Elaboration164
Figure 8.4 Model for the cruise control system.164
Figure 8.5 LTS diagram for INPUTSPEED.165
Figure 8.6 LTS diagram for SPEEDCONTROL.165
Figure 8.7 CONTROL trace.166
8.1.4 Safety Properties167
Figure 8.8 LTS diagram for the property CRUISESAFETY.168
8.1.5 Revising the Model169
Figure 8.9 Minimized LTS diagram for CONTROLMINIMIZED.170
Figure 8.10 Minimized LTS diagram for the revised CONTROLMINIMIZED.171
8.1.6 Progress Properties172
8.2 From Models to Implementations174
Figure 8.11 Design architecture, behavior model and other models.175
Figure 8.12 Cruise control applet display.175
Figure 8.13 Cruise control class diagram.176
Program 8.1 CarSpeed interface.176
Program 8.2 Controller class.177
Summary178
Program 8.3 SpeedControl class.179
Notes and Further Reading180
Exercises181
9 Dynamic Systems183
9.1 Golf Club Program184
Figure 9.1 Golf Club applet display.184
Figure 9.2 Golf Club class diagram.185
Program 9.1 Allocator interface and SimpleAllocator class.186
Program 9.2 Player class.187
Program 9.3 SlotCanvas class.188
9.2 Golf Club Model188
Figure 9.3 ALLOCATOR LTS for N = 2.189
Figure 9.4 PLAYER LTS for N = 2.190
Figure 9.5 GOLFCLUB composition.191
9.3 Fair Allocation192
9.4 Revised Golf Ball Allocator193
Program 9.4 FairAllocator class.194
9.5 Bounded Overtaking194
Figure 9.6 Golf Club applet with fair allocation.195
9.6 Bounded Overtaking Golf Ball Allocator200
Figure 9.7 Golf Club with bounded overtaking allocator (bound = 3).200
Program 9.5 BoundedOvertakingAllocator class.201
9.7 Master–Slave Program202
Figure 9.8 join() demonstration applet.203
9.8 Master–Slave Model203
Program 9.6 Master and Slave classes.204
Figure 9.9 MASTER_SLAVE LTS.205
Summary205
Notes and Further Reading206
Exercises208
10 Message Passing209
10.1 Synchronous Message Passing209
Figure 10.1 Synchronous message-passing channel.210
10.1.1 Selective Receive211
10.1.2 Synchronous Message Passing in Java212
Program 10.1 Channel class.212
Figure 10.2 Synchronous message-passing applet display.213
Program 10.2 Sender and Receiver threads.213
10.1.3 Modeling Synchronous Message Passing214
Figure 10.3 Modeling synchronous message passing.215
Figure 10.4 SyncMsg labeled transition system.216
10.1.4 Modeling and Implementing Selective Receive216
Figure 10.5 Car park model.216
Program 10.3 MsgGate class.217
Program 10.4 MsgCarPark class.218
10.2 Asynchronous Message Passing219
Figure 10.6 Asynchronous message-passing port.219
10.2.1 Asynchronous Message Passing in Java220
Program 10.5 Port class.220
Figure 10.7 Asynchronous message-passing applet display.221
10.2.2 Modeling Asynchronous Message Passing221
Program 10.6 Asender and Areceiver classes.222
Figure 10.8 APORT labeled transition system.224
Figure 10.9 Asynchronous message applet model.224
10.3 Rendezvous225
Figure 10.10 Rendezvous message-passing protocol.225
10.3.1 Rendezvous in Java226
Program 10.7 Entry class.227
Figure 10.11 Rendezvous message-passing applet display.228
10.3.2 Modeling Rendezvous228
Program 10.8 Client and Server threads.229
Figure 10.12 Rendezvous applet model.230
10.3.3 Rendezvous and Monitor Method Invocation231
Summary232
Notes and Further Reading233
Figure 10.13 Message-passing classes.233
Exercises234
11 Concurrent Architectures237
11.1 Filter Pipeline237
11.1.1 Primes Sieve Model238
Figure 11.1 Primes Sieve process architecture.238
Figure 11.2 Minimized PRIMES LTS.240
Unbuffered Pipes241
Figure 11.3 Minimized PRIMESUNBUF LTS.241
Abstracting from Application Detail242
Figure 11.4 Minimized AFILTER LTS.243
Architectural Property Analysis243
11.1.2 Primes Sieve Implementation244
Figure 11.5 Primes Sieve applet display.245
Figure 11.6 Primes class diagram.245
Program 11.1 PrimesCanvas class.246
Program 11.2 Generator class.246
Program 11.3 Filter class.247
Program 11.4 Pipe, PipeImplUnBuf and PipeImplBuf classes.248
Why Use Buffering?249
11.2 Supervisor-Worker250
Figure 11.7 Supervisor-Worker process architecture.250
11.2.1 Linda Tuple Space251
Tuple Space Model252
Figure 11.8 TUPLE LTS.253
Tuple Space Implementation253
Program 11.5 TupleSpace interface.253
11.2.2 Supervisor–Worker Model254
Program 11.6 TupleSpaceImpl class.255
Figure 11.9 SUPERVISOR and WORKER LTS.256
Analysis257
Figure 11.10 Trace of Supervisor–Worker model.259
11.2.3 Supervisor-Worker Implementation260
Figure 11.11 Rectangle method.260
Figure 11.12 Supervisor-Worker applet.261
Figure 11.13 Supervisor-Worker class diagram.261
Program 11.7 SupervisorCanvas, WorkerCanvas and Function classes.262
Program 11.8 Result and Supervisor classes.263
Program 11.9 Worker class.264
Speedup and Efficiency265
11.3 Announcer–Listener265
Figure 11.14 Announcer-Listener process architecture.266
11.3.1 Announcer-Listener Model266
Figure 11.15 LTS for a:REGISTER.267
Analysis268
Figure 11.16 ANNOUNCER_LISTENER trace.269
11.3.2 Announcer – Listener Implementation269
Figure 11.17 EventDemo applet display.270
Program 11.10 BoxCanvas class.270
Figure 11.18 EventDemo class diagram.271
Program 11.11 BoxMover and MyListener classes.272
Summary273
Notes and Further Reading273
Exercises274
12 Timed Systems277
12.1 Modeling Timed Systems278
Figure 12.1 Discrete time and mouse clicks.278
Figure 12.2 DOUBLECLICK LTS and traces.280
12.1.1 Timing Consistency280
Figure 12.3 Timed Producer - Consumer deadlock.282
12.1.2 Maximal Progress282
12.1.3 Modeling Techniques284
Output in an Interval284
Figure 12.4 LTS for OUTPUT (1,3).284
Jitter285
Figure 12.5 LTS for JITTER(2).285
Timeout286
Figure 12.6 LTS for RECEIVER(2).287
12.2 Implementing Timed Systems287
12.2.1 Timed Objects288
Program 12.1 Timed interface.288
CountDown Timer288
Program 12.2 TimedCountDown class.289
Timed Producer-Consumer289
Program 12.3 ProducerConsumer class.289
Program 12.4 Producer class.290
Program 12.5 Consumer class.291
The Two-Phase Clock292
12.2.2 Time Manager293
Program 12.6 TimeManager class.293
Program 12.7 ImmutableList class.294
12.3 Parcel Router Problem295
Figure 12.7 Parcel router device.295
12.3.1 Parcel Router Model296
Figure 12.8 Parcel router model structure.296
GEN296
BIN297
STAGE297
Figure 12.9 STAGE structure.297
CHUTE298
SENSORCONTROLLER298
SWITCH299
Analysis299
Figure 12.10 Animation trace for STAGE(0).301
12.3.2 Parcel Router Implementation301
Figure 12.11 Parcel router applet display.302
Figure 12.12 Parcel router classes and interfaces.303
Program 12.8 ParcelMover and SwitchControl interfaces.303
Program 12.9 Chute class.304
Program 12.10 Switch class.305
Program 12.11 SensorController class.305
12.4 Space Invaders306
Figure 12.13 Space Invaders applet display.307
12.4.1 Space Invaders Model307
Figure 12.14 Game space.308
Sprite308
Alien309
Missile310
Spaceship310
Collision Detection310
Space Invaders311
Analysis311
12.4.2 Space Invaders Implementation313
Sprite and SpriteCanvas313
Figure 12.15 Sprite and SpriteCanvas classes.313
CollisionDetector314
Figure 12.16 CollisionDetector class diagram.314
SpaceInvaders314
Figure 12.17 SpaceInvaders class diagram.315
Summary315
Notes and Further Reading317
Exercises317
13 Program Verification319
13.1 Sequential Processes320
13.1.1 Local Process END320
Figure 13.1 Sequential process BOMB.320
13.1.2 Sequential Composition;320
Figure 13.2 Sequential composition LOOP.321
Figure 13.3 Sequential composition and recursion.321
13.1.3 Parallel Composition and Sequential Processes321
Figure 13.4 Parallel composition of sequential processes.322
13.1.4 Sequential Processes and Analysis322
13.2 Modeling Condition Synchronization322
13.2.1 Wait, Notify and NotifyAll323
Figure 13.5 WAITSET trace for notify.324
Figure 13.6 WAITSET trace for notifyAll.325
13.3 Modeling Variables and Synchronized Methods325
13.3.1 Variables325
13.3.2 Monitor Exit and Entry326
13.3.3 Synchronized Methods327
13.4 Bounded Buffer Example328
13.4.1 put( ) and get( ) Methods328
Program 13.1 Buffer interface and BufferImpl class.328
13.4.2 Producer and Consumer Threads330
13.4.3 Analysis331
Figure 13.7 LTS for property BUFFER.332
13.5 Readers—Writers Example334
Program 13.2 Class ReadWritePriority.334
13.5.1 ReadWritePriority Methods335
READER and WRITER Processes337
13.5.2 Analysis337
Progress Analysis339
Summary340
Notes and Further Reading341
Exercises342
14 Logical Properties345
14.1 Fluent Propositions346
14.1.1 Fluents346
Action Fluents347
14.1.2 Fluent Expressions347
14.2 Temporal Propositions348
14.2.1 Safety Properties348
Figure 14.1 MUTEX property process.349
Single-Lane Bridge Safety Property350
14.2.2 Liveness Properties351
Figure 14.2 Büchi automaton for FIRSTRED.352
Figure 14.3 CongestedBridge showing acceptance states.353
Figure 14.4 REDCROSS Büchi automaton.353
Response Properties354
Figure 14.5 REDEXIT Büchi automaton.354
14.3 Fluent Linear Temporal Logic (FLTL)355
14.3.1 Until355
Figure 14.6 POLITE Büchi automaton.355
14.3.2 Weak Until356
Figure 14.7 POLITE_W safety property process.356
Definitions357
14.3.3 Next Time358
Figure 14.8 SEQ property process.358
14.4 Database Ring Problem358
Figure 14.9 Database ring architecture.359
14.4.1 Database Ring Model359
14.4.2 Database Ring Properties361
Witness Executions362
Finite Executions363
Summary364
Notes and Further Reading365
Exercises366
Back Matter367
Appendix A FSP Quick Reference367
A.1 Processes367
Example367
Table A.1 Process operators367
A.2 Composite Processes368
Example368
Table A.2 Composite process operators368
A.3 Common Operators368
Table A.3 Common process operators369
A.4 Properties369
Table A.4 Safety and progress properties369
A.5 Fluent Linear Temporal Logic (FLTL)370
Table A.5 Fluent Linear Temporal Logic370
Appendix B FSP Language Specification371
B.1 FSP Description372
B.2 Identifiers372
B.3 Action Labels373
Examples373
Examples374
Examples374
B.4 const, range, set374
Examples375
B.5 Process Definition375
Examples376
Example377
Examples378
B.6 Composite Process378
Examples379
Example379
B.7 Parameters380
B.8 Re-Labeling and Hiding381
Examples381
Prefix Matching382
B.9 property, progress and menu382
Example383
B.10 Expression383
B.11 Basic FSP385
B.12 fluent and assert386
Example386
Appendix C FSP Semantics389
C.1 Labeled Transition System (LTS)389
C.2 Processes390
C.3 Composite Processes391
C.3.1 LTS Composition391
C.3.2 LTS Priority392
C.3.3 FSP Composition and Priority392
C.4 Common Operators393
C.4.1 Re-Labeling393
C.4.2 Hiding393
C.4.3 FSP Re-Labeling, Hiding and Interface393
C.5 Safety Properties394
C.6 Semantic Equivalences394
C.6.1 Strong Equivalence394
C.6.2 Weak Equivalence395
C.7 Fluent Linear Temporal Logic (FLTL)395
C.7.1 Linear Temporal Logic395
C.7.2 Fluents396
Appendix D UML Class Diagrams399
Bibliography401

Book details

Vendor Wiley Global Education UK
SKU 0470064625R90
ISBN-13 9780470064627
Author Jeff Magee; Jeff Kramer
Edition 2nd
Category Computers
Subject Java

Do you have questions about this book?

Ask an expert!

Concurrency provides a thoroughly updated approach to the basic concepts and techniques behind concurrent programming. Concurrent programming is complex and demands a much more formal approach than sequential programming. In order to develop a thorough understanding of the topic Magee and Kramer present concepts, techniques and problems through a variety of forms: informal descriptions, illustrative examples, abstract models and concrete Java examples. These combine to provide problem patterns and associated solution techniques which enable students to recognise problems and arrive at solutions.

New features include:

New chapters covering program verification and logical properties.
More student exercises.
Supporting website contains an updated version of the LTSA tool for modelling concurrency, model animation, and model checking.
Website also includes the full set of state models, java examples, and demonstration programs and a comprehensive set of overhead slides for course presentation.

Instant delivery by email
Your access email arrives within minutes of checkout, with a sign-in link for each book — no shipping, no waiting.

Read on any device
Books open in VitalSource Bookshelf on your phone, tablet, or computer, online or offline. Your library is always available at aafaq.vitalsource.com — just log in with the email you used at checkout.

Lost the email?
Resend it to yourself in seconds from My eBook orders, or email cs@aafaqeducation.com and we'll help.