| |
| |
| |
| The Concurrent Computing Landscape | |
| |
| |
| The Essence of Concurrent Programming | |
| |
| |
| Hardware Architectures | |
| |
| |
| Single Processor Machines | |
| |
| |
| Shared-Memory Multiprocessors | |
| |
| |
| Multicomputers Networks | |
| |
| |
| Applications and Programming Styles | |
| |
| |
| Iterative Parallelism: Matrix Multiplication | |
| |
| |
| Recursive Parallelism: Adaptive Quadrature | |
| |
| |
| Producers and Consumers: Unix Pipes | |
| |
| |
| Clients and Servers: Remote Files | |
| |
| |
| Peers: Distributed Matrix Multiplication | |
| |
| |
| Summary of Programming Notation | |
| |
| |
| Declarations Sequential Statements | |
| |
| |
| Concurrent Statements and Process Declarations | |
| |
| |
| Comments | |
| |
| |
| |
| Shared Variable Programming | |
| |
| |
| |
| Processes and Synchronization | |
| |
| |
| States, Actions, Histories, and Properties | |
| |
| |
| Parallelization: Finding Patterns in Files | |
| |
| |
| Synchronization: The Maximum of an Array | |
| |
| |
| Atomic Actions and Await Statements | |
| |
| |
| Fine-Grained Atomicity | |
| |
| |
| Specifying Synchronization: The Await Statement | |
| |
| |
| Finding Patterns in a File Revisited | |
| |
| |
| A Synopsis of Axiomatic Semantics | |
| |
| |
| Formal Logical Systems | |
| |
| |
| A Programming Logic | |
| |
| |
| Semantics of Concurrent Execution | |
| |
| |
| Techniques for Avoiding Interference | |
| |
| |
| Disjoint Variables Weakened Assertions | |
| |
| |
| Global Invariants | |
| |
| |
| Synchronization | |
| |
| |
| An Example: The Array Copy Problem Revisited | |
| |
| |
| Safety and Liveness Properties | |
| |
| |
| Proving Safety Properties | |
| |
| |
| Scheduling Policies and Fairness | |
| |
| |
| |
| Locks and Barriers | |
| |
| |
| The Critical Section Problem | |
| |
| |
| Critical Sections: Spin Locks | |
| |
| |
| Test and Set | |
| |
| |
| Test and Test and Set | |
| |
| |
| Implementing Await Statements | |
| |
| |
| Critical Sections: Fair Solutions | |
| |
| |
| The Tie-Breaker Algorithm | |
| |
| |
| The Ticket al.gorithm | |
| |
| |
| The Bakery Algorithm | |
| |
| |
| Barrier Synchronization | |
| |
| |
| Shared Counter | |
| |
| |
| Flags and Coordinators | |
| |
| |
| Symmetric Barriers | |
| |
| |
| Data Parallel Algorithms | |
| |
| |
| Parallel Prefix Computations | |
| |
| |
| Operations on Linked Lists | |
| |
| |
| Grid Computations: Laplace's Equation | |
| |
| |
| Synchronous Multiprocessors | |
| |
| |
| Parallel Computing with a Bag of Tasks | |
| |
| |
| Matrix Multiplication | |
| |
| |
| Adaptive Quadrature | |
| |
| |
| |
| Semaphores | |
| |
| |
| Syntax and Semantics | |
| |
| |
| Basic Problems and Techniques | |
| |
| |
| Critical Sections: Mutual Exclusion | |
| |
| |
| Barriers: Signaling Events | |
| |
| |
| Producers and Consumers: Split Binary Semaphores | |
| |
| |
| Bounded Buffers: Resource Counting | |
| |
| |
| The Dining Philosophers | |
| |
| |
| Readers and Writers | |
| |
| |
| Readers/Writers as an Exclusion Problem | |
| |
| |
| Readers/Writers Using Condition Synchronization | |
| |
| |
| The Technique of Passing the Baton | |
| |
| |
| Alternative Scheduling Policies | |
| |
| |
| Resource Allocation and Scheduling | |
| |
| |
| Problem Definition and General Solution Pattern | |
| |
| |
| Shortest-Job-Next Allocation | |
| |
| |
| Case Study: Pthreads | |
| |
| |
| Thread Creation | |
| |
| |
| Semaphores | |
| |
| |
| Example: A Simple Producer and Consumer | |
| |
| |
| |
| Monitors | |
| |
| |
| Syntax and Semantics | |
| |
| |
| Mutual Exclusion | |
| |
| |
| Condition Variables | |
| |
| |
| Signaling Disciplines | |
| |
| |
| Additional Operations on Condition Variables | |
| |
| |
| Synchronization Techniques | |
| |
| |
| Bounded Buffers: Basic Condition Synchronization | |
| |
| |
| Readers and Writers: Broadcast Signal | |
| |
| |
| Shortest-Job-Next Allocation: Priority Wait | |
| |
| |
| Interval Timer: Covering Conditions | |
| |
| |
| The Sleeping Barber: Rendezvous | |
| |
| |
| Disk Scheduling: Program Structures | |
| |
| |
| Scheduler as a Separate Monitor | |
| |
| |
| Scheduler as an Intermediary | |
| |
| |
| Scheduler as a Nested Monitor | |
| |
| |
| Case Study: Java | |
| |
| |
| The Threads Class | |
| |
| |
| Synchronized Methods | |
| |
| |
| Parallel Readers/Writers | |
| |
| |
| Exclusive Readers/Writers | |
| |
| |
| True Readers/Writers | |
| |
| |
| Case Study: Pthreads | |
| |
| |
| Locks and Condition Variables | |
| |
| |
| Example: Summing the Elements of a Matrix | |
| |
| |
| |
| Implementations | |
| |
| |
| A Single-Processor Kernel | |
| |
| |
| A Multiprocessor Kernel | |
| |
| |
| Implementing Semaphores in a Kernel | |
| |
| |
| Implementing Monitors in a Kernel | |
| |
| |
| Implementing Monitors Using Semaphores | |
| |
| |
| |
| Distributed Programming | |
| |
| |
| |
| Message Passing | |
| |
| |
| Asynchronous Message Passing | |
| |
| |
| Filters: A Sorting Network | |
| |
| |
| Clients and Servers | |
| |
| |
| Active Monitors | |
| |
| |
| A Self-Scheduling Disk Driver | |
| |
| |
| File Servers: Conversational Continuity | |
| |
| |
| Interacting Peers: Exchanging Values | |
| |
| |
| Synchronous Message Passing | |
| |
| |
| Case Study: CSP | |
| |
| |
| Communication Statements | |
| |
| |
| Guarded Communication | |
| |
| |
| Example: The Sieve of Eratosthenes | |
| |
| |
| Case Study: Linda | |
| |
| |
| Tuple Space and Process Interaction | |
| |
| |
| Example: Prime Numbers with a Bag of Tasks | |
| |
| |
| Case Study: MPI | |
| |
| |
| Basic Functions | |
| |
| |
| Global Communication and Synchronization | |
| |
| |
| Case Study: Java | |
| |
| |
| Networks and Sockets | |
| |
| |
| Example: A Remote File Reader | |
| |
| |
| |
| RPC and Rendezvous | |
| |
| |
| Remote Proc | |