Concurrency : State Models and Java Programs

by Jeff Magee; Jeff Kramer

• ISBN13: 9780471987109
• ISBN10: 0471987107
• Edition: CD
• Format: Hardcover
• Copyright: 1999-04-01
• Publisher: WILEY

Summary

Concurrency is an area of software design that is vital in a wide range of applications where responsiveness are issues. They are especially important in the development of control systems. By their nature, concurrent programs are more complex, and therefore more difficult to reason than sequential programs. In order to ensure a thorough understanding of concurrency, concepts, techniques and problems are presented in many forms, through informal descriptions and illustrative examples, abstractly in models, and concretely in Java.

Table of Contents

Preface	xi
Acknowledgments	xv
Introduction	1	(10)
Concurrent Programs	2	(2)
The Modeling Approach	4	(3)
Practice	7	(1)
Content Overview	8	(3)
Summary	9	(1)
Notes and Further Reading	9	(2)
Processes and Threads	11	(26)
Modeling Processes	11	(12)
Implementing Processes	23	(14)
Summary	31	(1)
Notes and Further Reading	31	(1)
Exercises	32	(5)
Concurrent Execution	37	(26)
Modeling concurrency	38	(15)
Multi-Threaded Programs	53	(10)
Summary	60	(1)
Notes and Further Reading	60	(1)
Exercises	61	(2)
Shared Objects and Mutual Exclusion	63	(16)
Interference	63	(8)
Mutual Exclusion in Java	71	(2)
Modeling Mutual Exclusion	73	(6)
Summary	76	(1)
Notes and Further Reading	77	(1)
Exercises	77	(2)
Monitors and Condition Synchronization	79	(28)
Condition Synchronization	79	(8)
Semaphores	87	(7)
Bounded Buffers	94	(4)
Nested Monitors	98	(4)
Monitor Invariants	102	(5)
Summary	103	(1)
Notes and Further Reading	103	(1)
Exercises	104	(3)
Deadlock	107	(14)
Deadlock Analysis	108	(3)
Dining Philosophers Problem	111	(10)
Summary	118	(1)
Notes and Further Reading	119	(1)
Exercises	119	(2)
Safety and Liveness Properties	121	(38)
Safety	122	(3)
Single-Lane Bridge Problem	125	(8)
Liveness	133	(5)
Liveness of the Single-Lane Bridge	138	(6)
Readers-Writers Problem	144	(15)
Summary	154	(1)
Notes and Further Reading	155	(1)
Exercises	155	(4)
Model-Based Design	159	(24)
From Requirements to Models	160	(13)
From Models to Implementations	173	(10)
Summary	179	(1)
Notes and Further Reading	179	(1)
Exercises	180	(3)
Dynamic Systems	183	(22)
Golf Club Program	184	(4)
Golf Club Model	188	(4)
Fair Allocation	192	(2)
Revised Golf Ball Allocator	194	(1)
Bounded Overtaking	195	(2)
Master-Slave Program	197	(3)
Master-Slave Model	200	(5)
Summary	201	(1)
Notes and Further Reading	201	(2)
Exercises	203	(2)
Message Passing	205	(28)
Synchronous Message Passing	205	(10)
Asynchronous Message Passing	215	(6)
Rendezvous	221	(12)
Summary	229	(1)
Notes and Further Reading	230	(1)
Exercises	230	(3)
Concurrent Architectures	233	(42)
Filter Pipeline	233	(13)
Supervisor-Worker	246	(17)
Announcer-Listener	263	(12)
Summary	270	(1)
Notes and Further Reading	271	(1)
Exercises	272	(3)
Time Systems	275	(42)
Modeling Timed Systems	276	(9)
Implementing Timed Systems	285	(8)
Parcel Router Problem	293	(11)
Space Invaders	304	(13)
Summary	314	(1)
Notes and Further Reading	315	(1)
Exercises	315	(2)
Appendix A FSP Quick Reference	317	(4)
A.1 Processes	317	(1)
A.2 Composite Processes	318	(1)
A.3 Common Operators	319	(1)
A.4 Properties	319	(2)
Appendix B FSP Language Specification	321	(14)
B.1 FSP Description	322	(1)
B.2 Identifiers	322	(1)
B.3 Action Labels	323	(1)
B.4 const, range, set	324	(1)
B.5 Process Definition	325	(2)
B.6 Composite Process	327	(2)
B.7 Parameters	329	(1)
B.8 Relabeling and Hiding	330	(1)
B.9 property, progress and menu	331	(1)
B.10 Expression	332	(2)
B.11 Basic FSP	334	(1)
Appendix C FSP Semantics	335	(8)
C.1 Labeled Transition System (LTS)	335	(1)
C.2 Processes	336	(1)
C.3 Composite Processes	337	(1)
C.4 Common Operators	338	(2)
C.5 Safety Properties	340	(1)
C.6 Semantic Equivalences	340	(3)
Appendix D UML Class Diagrams	343	(2)
Bibliography	345	(4)
Index	349