Nonsequential and Distributed Programming with Go: Synchronization of Concurrent Processes: Communication - Cooperation - Competition

Description

Der Band bietet eine kompakte Einführung in die Nichtsequentielle Programmierung als gemeinsamen Kern von Vorlesungen über Betriebssysteme, Verteilte Systeme, Parallele Algorithmen, Echtzeitprogrammierung und Datenbanktransaktionen. Basiskonzepte zur Synchronisation und Kommunikation nebenläufiger Prozesse werden systematisch dargestellt: Schlösser, Semaphore, Monitore, lokaler und netzweiter Botschaftenaustausch. Die Algorithmen sind in der Programmiersprache Google Go formuliert, mit der viele Synchronisationskonzepte ausgedrückt werden können. Preface Contents List of Figures List of Tables 1 Introduction 1.1 Definition of Terms 1.2 Motivation and Applications 1.3 The (Non-)Sense of Testing 1.4 Examples of Concurrent Algorithms 1.5 Concurrency and the Informal Notion of a Process 1.6 Conflicts When Addressing Shared Data 1.7 Atomic Statements 1.8 Critical Sections and Lock Synchronization 1.9 Process States 1.9.1 Process Transitions in C, Java, and Go 1.9.2 Example in C, Java, and Go 2 Packages, Interfaces, and Abstract Data Types 2.1 The Role of Packages 2.1.1 Packages Only as Interfaces 2.2 All Source Codes from This Book in the nUniverse Package 2.3 The Package Object 2.3.1 Any 2.3.2 Interfaces for Describing Objects 2.3.3 The Interface of the Package 2.3.4 Queues as Abstract Data Type 2.3.5 A Queue as an Abstract Data Object 2.3.6 Bounded Buffers 2.4 On the Problem of References 3 Locks 3.1 Specification of Locks 3.2 Locks in C, Java, and Go 3.2.1 Locks in C 3.2.2 Locks in Java 3.2.3 Locks in Go 3.3 Locks Based on Indivisible Machine Instructions 3.3.1 Test and Set 3.3.2 Compare and Swap 3.3.3 Exchange 3.3.4 Decrement 3.3.5 Fetch and Increment 3.3.6 The Counter Problem 3.3.7 Evaluation of the Use of Machine Instructions 3.4 Lock Algorithms for 2 Processes at High-Level Language Level 3.4.1 On the Indivisibility of Value Assignments 3.4.2 Approaches to the Development of a Correct Algorithm 3.4.3 Algorithm of Peterson 3.4.4 Algorithm of Kessels 3.4.5 Algorithm of Dekker 3.4.6 Algorithm of Doran and Thomas 3.4.7 Algorithm of Hyman 3.5 Lock Algorithms for Several Processes 3.5.1 Tiebreaker Algorithm of Peterson 3.5.2 Algorithm of Dijkstra 3.5.3 Algorithm of Knuth 3.5.4 Algorithm of Eisenberg and McGuire 3.5.5 Algorithm of Habermann 3.5.6 Ticket Algorithm 3.5.7 Bakery Algorithm of Lamport 3.5.8 Algorithm of Kessels for N Processes 3.5.9 Algorithm of Morris 3.5.10 Algorithm of Szymanski 3.6 Locks as Abstract Data Types 4 Semaphores 4.1 Disadvantages of the Implementation of Locks 4.2 Dijkstra's Approach 4.3 Binary Semaphores 4.3.1 Equivalence of Locks and Binary Semaphores 4.3.2 Algorithm of Udding 4.4 Buffers in the Nonsequential Case 4.5 General Semaphores 4.5.1 Specification of General Semaphores 4.5.2 Development of a Correct Implementation 4.6 Unbounded Buffers and the Sleeping Barber 4.7 Construction of General Semaphores from Binary Semaphores 4.7.1 Representation 4.7.2 Naive (Wrong) Approach 4.7.3 Correction and Consequence 4.7.4 The Algorithm of Barz 4.8 Semaphores in C, Java, and Go 4.8.1 Semaphores in C 4.8.2 Semaphores in Java 4.8.3 Semaphores in Go 4.9 Additive Semaphores 4.9.1 Multiple Semaphores 4.10 Barrier Synchronization 4.11 Shortest Job Next 4.12 The Readers–Writers Problem 4.12.1 The First Readers–Writers Problem 4.12.2 The Second Readers–Writers Problem 4.12.3 Priority Adjustment 4.12.4 Implementation with Additive Semaphores 4.12.5 Efficient Implementation in Go 4.12.6 The Readers–Writers Problem as an Abstract Data Type 4.13 The left–right Problem 4.14 The Dining Philosophers 4.15 The Problem of the Cigarette Smokers 4.16 Implementation of Semaphores 4.16.1 The Convoy Phenomenon 5 The Baton Algorithm 5.1 Development of the Problem 5.1.1 The Baton of Andrews 5.2 The Readers–Writers Problem 5.3 The Second Left–Right Problem 6 Universal Critical Sections 6.1 Basic Idea and Construction 6.1.1 Specification 6.1.2 Implementation 6.2 Semaphores 6.3 The Sleeping Barber 6.4 The Readers–Writers Problem 6.5 The Left–Right Problem 6.6 Universal Critical Resources 6.7 The Dining Philosophers 6.8 The Problem of the Cigarette Smokers 7 Fairness 7.1 Weak Versus Strong Fairness 8 Deadlocks 8.1 Characterization 8.1.1 A Simple Examples 8.2 Countermeasures 8.2.1 Prevention 8.2.2 Detection and Recovery 8.2.3 Avoidance 8.2.4 The Bankers' Algorithm 8.3 Probability of Deadlocks 8.4 Evaluation of the Countermeasures 9 Monitors 9.1 Characterization of Monitors 9.1.1 Hoare's Approach 9.1.2 Virtual Monitors in Go 9.2 Condition Variables 9.3 Monitors in C, Java, and Go 9.3.1 Monitors in C 9.3.2 Monitors in Java 9.3.3 Monitors in Go 9.4 The Bounded Buffer 9.5 The Readers–Writers Problem 9.6 Signal Semantics 9.6.1 Signal and Continue 9.6.2 Signal and Wait 9.6.3 Signal and Urgent Wait 9.6.4 Preemptive Versus Nonpreemptive Semantics 9.6.5 Comparing Evaluation of the Signal Semantics 9.6.6 A Semaphore as Monitor 9.6.7 Barrier Synchronization 9.7 Broadcast in C, Java, and Go 9.7.1 Broadcast in C 9.7.2 Broadcast in Java 9.7.3 Broadcast in Go 9.8 The Sleeping Barber: Haircut as a Rendezvous 9.9 Priority Rules 9.9.1 Hoare's Alarm Clock 9.9.2 Shortest Job next 9.10 Equivalence of the Semaphore and the Monitor Concepts 9.11 Implementation of the Monitor Concept 9.12 The Problem of Nested Monitor Calls 10 Universal Monitors 10.1 The Basic Idea 10.1.1 Specification 10.1.2 Implementation 10.2 Conditioned Universal Monitors 10.2.1 Specification 10.2.2 Implementation 10.3 Semaphores 10.4 Account 10.5 Bounded Buffers 10.6 The Sleeping Barber 10.7 Barrier Synchronization 10.8 The Readers–Writers Problem 10.9 The Left–Right Problem 10.10 The Dining Philosophers 10.11 The Cigarette Smokers 11 Message Passing 11.1 Channels and Messages 11.1.1 Syntax of Message Passing in Go 11.1.2 Synchronous Message Passing with Asynchronous 11.2 Asynchronous Communication 11.2.1 Semaphores 11.2.2 Bounded Buffers 11.2.3 The Cigarette Smokers 11.3 Networks of Filters 11.3.1 Caesar's Secret Messages 11.3.2 The Sieve of Eratosthenes 11.3.3 Mergesort 11.3.4 The Dining Philosophers 11.4 Selective Waiting 11.5 The Client–Server Paradigm 11.6 Synchronous Communication 11.6.1 Semaphores 11.6.2 Bounded Buffers 11.6.3 Equivalence of Synchronous and Asynchronous Message Passing 11.6.4 The Readers–Writers Problem 11.6.5 The Left–Right Problem 11.7 Guarded Selective Waiting 11.7.1 Semaphores 11.7.2 Bounded Buffers 11.7.3 The Readers–Writers Problem 11.7.4 The Left–Right Problem 11.8 Equivalence of Message Passing and the Semaphore Concept 11.9 Duality Between Monitors and Servers 12 Comparison of the Previous Language Constructs 12.1 Locks 12.2 Semaphores 12.3 Monitors 12.4 Message Passing 13 Netwide Message Passing 13.1 Channels in the Network 13.1.1 Technical Aspects (in C) 13.1.2 Remarks on the Realization in Java 13.2 Realization in Go 13.3 1:1-Network Channels Between Processes on Arbitrary Computers 13.3.1 A Simple Example 13.4 Distributed Locks Due to Ricart/Agrawala 14 Universal Far Monitors 14.1 Extension of Net Channels to the Case 1:n 14.2 Construction of the Far Monitors 14.2.1 Specification 14.2.2 Implementation 14.3 Correctness 14.4 Distributed Semaphores 14.5 Distributed Queues and Bounded Buffers 14.6 Distributed Readers–Writers and Left–Right Problems 14.7 Account 14.8 Remote Procedure Calls 14.8.1 Example of a Remote Procedure Call 15 Networks as Graphs 15.1 Graphs 15.1.1 Definition of the Graph Concept 15.2 Realization in Go 15.2.1 Specification 15.2.2 Implementation 15.3 Adjacency Matrices 15.3.1 Specification 15.3.2 Implementation 15.4 Distributed Graphs 15.4.1 Specification 15.4.2 Implementation 15.5 Examples 15.5.1 Output to the Screen 16 Heartbeat Algorithms 16.1 The Basic Idea 16.2 Getting to Know the Network 16.3 Preconditions for the Realization in Go 16.4 Matrix-Based Solution 16.5 Graph-Based Solutions 16.5.1 With Knowledge of the Diameter of the Network Graph 16.5.2 Without Global Knowledge 17 Traversing Algorithms 17.1 Preconditions for the Realization in Go 17.2 Distributed Depth-First Search 17.2.1 Transfer of the Spanning Tree to All Processes 17.2.2 Realization with Far Monitors and Transfer of the Spanning Tree 17.3 Algorithm of Awerbuch 17.3.1 Realization with Far Monitors 17.3.2 Transfer of the Spanning Tree to All Processes 17.3.3 Algorithm of Hélary/Raynal 17.4 Construction of a Ring 17.4.1 Transfer of the Ring to All Processes 17.5 Distributed Breadth-First Search 17.5.1 Realization with Far Monitors 17.5.2 Realization with Far Monitors and Transfer of the Spanning Tree 18 Leader Election Algorithms 18.1 Basics 18.2 Preconditions for the Realization in Go 18.3 Algorithm of Chang/Roberts 18.4 Algorithm of Hirschberg/Sinclair 18.5 Algorithm of Peterson 18.6 Election with Depth-First Search Index