Preface |
|
xi | |
|
Introduction to Concurrent Programming |
|
|
1 | (45) |
|
Processes and Threads: An Operating System's View |
|
|
1 | (2) |
|
Advantages of Multithreading |
|
|
3 | (1) |
|
|
4 | (2) |
|
|
6 | (3) |
|
|
9 | (5) |
|
|
14 | (5) |
|
C++ Class Thread for Win32 |
|
|
14 | (5) |
|
C++ Class Thread for Pthreads |
|
|
19 | (1) |
|
|
19 | (10) |
|
Nondeterministic Execution Behavior |
|
|
23 | (2) |
|
|
25 | (4) |
|
Testing and Debugging Multithreaded Programs |
|
|
29 | (9) |
|
|
30 | (4) |
|
Class TDThread for Testing and Debugging |
|
|
34 | (3) |
|
Tracing and Replaying Executions with Class Template shared Variable |
|
|
37 | (1) |
|
|
38 | (8) |
|
|
38 | (1) |
|
|
39 | (2) |
|
|
41 | (5) |
|
The Critical Section Problem |
|
|
46 | (38) |
|
Software Solutions to the Two-Thread Critical Section Problem |
|
|
47 | (7) |
|
|
48 | (1) |
|
|
49 | (1) |
|
|
50 | (2) |
|
|
52 | (1) |
|
Using the volatile Modifier |
|
|
53 | (1) |
|
Ticket-Based Solutions to the n-Thread Critical Section Problem |
|
|
54 | (4) |
|
|
54 | (2) |
|
|
56 | (2) |
|
Hardware Solutions to the n-Thread Critical Section Problem |
|
|
58 | (4) |
|
|
59 | (1) |
|
|
59 | (1) |
|
|
60 | (2) |
|
Deadlock, Livelock, and Starvation |
|
|
62 | (2) |
|
|
62 | (1) |
|
|
62 | (1) |
|
|
63 | (1) |
|
Tracing and Replay for Shared Variables |
|
|
64 | (20) |
|
|
65 | (2) |
|
Alternative Definition of ReadWrite-Sequences |
|
|
67 | (1) |
|
Tracing and Replaying ReadWrite-Sequences |
|
|
68 | (2) |
|
Class Template sharedVariable |
|
|
70 | (1) |
|
|
71 | (3) |
|
Note on Shared Memory Consistency |
|
|
74 | (3) |
|
|
77 | (1) |
|
|
78 | (1) |
|
|
79 | (5) |
|
|
84 | (93) |
|
|
84 | (2) |
|
|
86 | (4) |
|
|
86 | (1) |
|
|
87 | (3) |
|
Binary Semaphores and Locks |
|
|
90 | (2) |
|
|
92 | (4) |
|
Implementing P( ) and V( ) |
|
|
92 | (2) |
|
|
94 | (2) |
|
Semaphore-Based Solutions to Concurrent Programming Problems |
|
|
96 | (15) |
|
|
96 | (1) |
|
|
96 | (2) |
|
|
98 | (3) |
|
|
101 | (7) |
|
Simulating Counting Semaphores |
|
|
108 | (3) |
|
Semaphores and Locks in Java |
|
|
111 | (8) |
|
|
111 | (2) |
|
|
113 | (2) |
|
|
115 | (1) |
|
|
116 | (1) |
|
Example: Java Bounded Buffer |
|
|
116 | (3) |
|
Semaphores and Locks in Win32 |
|
|
119 | (15) |
|
|
119 | (3) |
|
|
122 | (2) |
|
|
124 | (8) |
|
|
132 | (2) |
|
Other Synchronization Functions |
|
|
134 | (1) |
|
Example: C++/Win32 Bounded Buffer |
|
|
134 | (1) |
|
Semaphores and Locks in Pthreads |
|
|
134 | (7) |
|
|
136 | (1) |
|
|
137 | (4) |
|
Another Note on Shared Memory Consistency |
|
|
141 | (2) |
|
Tracing, Testing, and Replay for Semaphores and Locks |
|
|
143 | (34) |
|
Nondeterministic Testing with the Lockset Algorithm |
|
|
143 | (3) |
|
Simple SYN-Sequences for Semaphores and Locks |
|
|
146 | (4) |
|
Tracing and Replaying Simple PV-Sequences and LockUnlock-Sequences |
|
|
150 | (4) |
|
|
154 | (3) |
|
Reachability Testing for Semaphores and Locks |
|
|
157 | (3) |
|
|
160 | (3) |
|
|
163 | (1) |
|
|
164 | (2) |
|
|
166 | (11) |
|
|
177 | (81) |
|
|
178 | (4) |
|
|
178 | (1) |
|
Condition Variables and SC Signaling |
|
|
178 | (4) |
|
Monitor-Based Solutions to Concurrent Programming Problems |
|
|
182 | (5) |
|
Simulating Counting Semaphores |
|
|
182 | (1) |
|
Simulating Binary Semaphores |
|
|
183 | (1) |
|
|
183 | (4) |
|
|
187 | (1) |
|
|
187 | (7) |
|
|
190 | (1) |
|
|
191 | (3) |
|
Simulating Multiple Condition Variables |
|
|
194 | (1) |
|
|
194 | (5) |
|
Pthreads Condition Variables |
|
|
196 | (1) |
|
Condition Variables in J2SE 5.0 |
|
|
196 | (3) |
|
|
199 | (7) |
|
|
199 | (3) |
|
|
202 | (2) |
|
Urgent-Signal-and-Continue |
|
|
204 | (1) |
|
Comparing SU and SC Signals |
|
|
204 | (2) |
|
Using Semaphores to Implement Monitors |
|
|
206 | (3) |
|
|
206 | (1) |
|
|
207 | (2) |
|
|
209 | (2) |
|
Toolbox for SC Signaling in Java |
|
|
210 | (1) |
|
Toolbox for SU Signaling in Java |
|
|
210 | (1) |
|
Monitor Toolbox for Win32/C++/Pthreads |
|
|
211 | (2) |
|
Toolbox for SC Signaling in C++/Win32/Pthreads |
|
|
213 | (1) |
|
Toolbox for SU Signaling in C++/Win32/Pthreads |
|
|
213 | (1) |
|
|
213 | (4) |
|
Tracing and Replay for Monitors |
|
|
217 | (5) |
|
|
217 | (2) |
|
Tracing and Replaying Simple M-Sequences |
|
|
219 | (1) |
|
Other Approaches to Program Replay |
|
|
220 | (2) |
|
Testing Monitor-Based Programs |
|
|
222 | (36) |
|
|
222 | (5) |
|
Determining the Feasibility of an M-Sequence |
|
|
227 | (6) |
|
Determining the Feasibility of a Communication-Sequence |
|
|
233 | (1) |
|
Reachability Testing for Monitors |
|
|
233 | (2) |
|
|
235 | (8) |
|
|
243 | (1) |
|
|
243 | (2) |
|
|
245 | (13) |
|
|
258 | (54) |
|
|
258 | (8) |
|
|
259 | (4) |
|
Channel Objects in C++/Win32 |
|
|
263 | (3) |
|
|
266 | (6) |
|
|
272 | (3) |
|
Message-Based Solutions to Concurrent Programming Problems |
|
|
275 | (6) |
|
|
275 | (3) |
|
|
278 | (3) |
|
Simulating Counting Semaphores |
|
|
281 | (1) |
|
Tracing, Testing, and Replay for Message-Passing Programs |
|
|
281 | (31) |
|
|
282 | (6) |
|
|
288 | (2) |
|
Determining the Feasibility of an SR-Sequence |
|
|
290 | (6) |
|
|
296 | (1) |
|
Reachability Testing for Message-Passing Programs |
|
|
297 | (2) |
|
|
299 | (5) |
|
|
304 | (1) |
|
|
304 | (1) |
|
|
304 | (8) |
|
Message Passing in Distributed Programs |
|
|
312 | (69) |
|
|
312 | (5) |
|
|
313 | (1) |
|
|
314 | (3) |
|
|
317 | (12) |
|
Classes TCPSender and TCPMailbox |
|
|
318 | (8) |
|
Classes TCPSynchronousSender and TCPSynchronous Mailbox |
|
|
326 | (2) |
|
Class TCPSelectableSynchronousMailbox |
|
|
328 | (1) |
|
Timestamps and Event Ordering |
|
|
329 | (12) |
|
|
330 | (1) |
|
|
331 | (1) |
|
|
332 | (1) |
|
|
332 | (2) |
|
|
334 | (1) |
|
|
335 | (4) |
|
Timestamps for Programs Using Messages and Shared Variables |
|
|
339 | (2) |
|
Message-Based Solutions to Distributed Programming Problems |
|
|
341 | (12) |
|
Distributed Mutual Exclusion |
|
|
341 | (5) |
|
Distributed Readers and Writers |
|
|
346 | (2) |
|
|
348 | (5) |
|
Testing and Debugging Distributed Programs |
|
|
353 | (28) |
|
|
353 | (9) |
|
|
362 | (1) |
|
Tracing, Testing, and Replaying CARC-Sequences and CSC-Sequences |
|
|
362 | (7) |
|
|
369 | (2) |
|
Other Approaches to Replaying Distributed Programs |
|
|
371 | (3) |
|
|
374 | (1) |
|
|
375 | (1) |
|
|
376 | (5) |
|
Testing and Debugging Concurrent Programs |
|
|
381 | (76) |
|
Synchronization Sequences of Concurrent Programs |
|
|
383 | (5) |
|
Complete Events vs. Simple Events |
|
|
383 | (3) |
|
Total Ordering vs. Partial Ordering |
|
|
386 | (2) |
|
Paths of Concurrent Programs |
|
|
388 | (7) |
|
|
388 | (3) |
|
Path-Based Testing and Coverage Criteria |
|
|
391 | (4) |
|
Definitions of Correctness and Faults for Concurrent Programs |
|
|
395 | (13) |
|
Defining Correctness for Concurrent Programs |
|
|
395 | (2) |
|
Failures and Faults in Concurrent Programs |
|
|
397 | (3) |
|
Deadlock, Livelock, and Starvation |
|
|
400 | (8) |
|
Approaches to Testing Concurrent Programs |
|
|
408 | (11) |
|
|
409 | (1) |
|
|
410 | (4) |
|
Combinations of Deterministic and Nondeterministic Testing |
|
|
414 | (5) |
|
|
419 | (38) |
|
Reachability Testing Process |
|
|
420 | (4) |
|
SYN-Sequences for Reachability Testing |
|
|
424 | (5) |
|
Race Analysis of SYN-Sequences |
|
|
429 | (4) |
|
|
433 | (6) |
|
|
439 | (2) |
|
Reachability Testing Algorithm |
|
|
441 | (6) |
|
|
447 | (2) |
|
|
449 | (1) |
|
|
449 | (3) |
|
|
452 | (5) |
Index |
|
457 | |