Nonsequential and Distributed Programming with Go

Höfundur: Christian Maurer (Útgáfa: 2)
Nonsequential and Distributed Programming with Go

Kaup valmöguleikar

After a short chapter on basic aspects of software engineering and its realization in Go, this book introduces to nonsequential and distributed programming with Go. It systematically presents basic concepts for the synchronization and communication of concurrent processes. These include locks, semaphores, fairness and deadlocks, monitors, local and network-wide message passing, networks as graphs, network exploration, distributed depth and breadth first search, and the selection of a leader in networks.

In order to make readers familiar with the concepts, the author always takes up the same classic examples. This makes learning easier, because the concepts presented can be compared more easily with the language resources. The algorithms are formulated in the Go programming language, which can be used to express numerous synchronization concepts. Due to its simple syntax, Go also offers the advantage that readers without prior knowledge can follow the basic concepts.

The chapters on locks, semaphores, monitors and network-wide message passing also present some basic approaches to programming in C and Java. All source texts are available online. Besides a number of error corrections and smaller updates, in this second edition the nanouniverse nU is replaced with the microuniverse μU. This allows for beautiful animations in many places, which are not possible with the nanouniverse due to a lack of the necessary support for inputs and outputs; e.

Nánar um bókina

Útgefandi
Springer Nature
ISBN
9783662709290
Print ISBN
9783662709283
Format
Page Fidelity (PDF)
Útgáfa
2
Höfundar
Christian Maurer
Tungumál
English
Útgefið
2025-07-01
Prent takmörkun á líftíma
100
Prent takmörkun
2
Afritunar takmörkun
2

Kaflar

  • 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.1.1 Non-existent → Ready
  • 1.9.1.2 Ready ⇄ Active
  • 1.9.1.3 Active → Blocked
  • 1.9.1.4 Blocked → Ready
  • 1.9.1.5 Active → Terminated
  • 1.9.1.6 Terminated → Non-existent
  • 1.9.2 Example in C, Java, and Go
  • References
  • 2 Packages, Interfaces, and Abstract Data Types
  • 2.1 The Role of Packages
  • 2.1.1 Packages Only as Interfaces
  • 2.1.1.1 On the Naming of Identifiers
  • 2.2 All Source Code from This Book in the Universe-Package
  • 2.3 The Package Object
  • 2.3.1 Interfaces for Describing Objects
  • 2.3.1.1 Equaler
  • 2.3.1.2 Comparer
  • 2.3.1.3 Clearer
  • 2.3.1.4 Coder
  • 2.3.2 The Interface of the Package
  • 2.3.3 Queues as Abstract Data Type
  • 2.3.4 A Queue as an Abstract Data Object
  • 2.3.5 Bounded Buffers
  • 2.4 On the Problem of References
  • 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 as Abstract Data Types
  • 3.3.1 lock2
  • 3.3.2 lock
  • 3.3.3 lockn
  • 3.4 Locks Based on Indivisible Machine Instructions
  • 3.4.1 Test and Set
  • 3.4.2 Compare and Swap
  • 3.4.3 Exchange
  • 3.4.4 Decrement
  • 3.4.5 Fetch and Increment
  • 3.4.6 The Counter Problem
  • 3.4.7 Evaluation of the Use of Machine Instructions
  • 3.5 Lock Algorithms for Two Processes at High-Level Language Level
  • 3.5.1 On the Indivisibility of Value Assignments
  • 3.5.2 Approaches to the Development of a Correct Algorithm
  • 3.5.3 Algorithm of Peterson
  • 3.5.3.1 Mutual Exclusion
  • 3.5.3.2 Absence of Unnecessary Delay
  • 3.5.3.3 Absence of Deadlocks
  • 3.5.3.4 Fairness
  • 3.5.4 Algorithm of Kessels
  • 3.5.5 Algorithm of Dekker
  • 3.5.6 Algorithm of Doran and Thomas
  • 3.5.7 Algorithm of Hyman
  • 3.6 Lock Algorithms for Several Processes
  • 3.6.1 Tiebreaker Algorithm of Peterson
  • 3.6.2 Algorithm of Dijkstra
  • 3.6.3 Algorithm of Knuth
  • 3.6.4 Algorithm of Eisenberg/McGuire
  • 3.6.5 Algorithm of Habermann
  • 3.6.6 Ticket Algorithm
  • 3.6.7 Bakery Algorithm of Lamport
  • 3.6.8 Algorithm of Kessels for n Processes
  • 3.6.9 Algorithm of Morris
  • 3.6.9.1 Mutual Exclusion
  • 3.6.9.2 Absence of Unnecessary Delay
  • 3.6.9.3 Absence of Deadlocks
  • 3.6.9.4 Fairness
  • 3.6.10 Algorithm of Szymanski
  • References
  • 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.6 Construction of General Semaphores from Binary Semaphores
  • 4.6.1 Representation
  • 4.6.2 Naive (Wrong) Approach
  • 4.6.3 Correction and Consequence
  • 4.6.4 Algorithm of Barz
  • 4.6.5 The Convoy Phenomenon
  • 4.6.6 Algorithm of the Go Authors
  • 4.7 Semaphores in C, Java, and Go
  • 4.7.1 Semaphores in C
  • 4.7.2 Semaphores in Java
  • 4.7.3 Semaphores in Go
  • 4.8 Additive Semaphores
  • 4.8.1 Multiple Semaphores
  • 4.9 The Sleeping Barber
  • 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 Abstract Data Type
  • 4.13 The Left-Right Problem
  • 4.14 The Dining Philosophers
  • 4.15 The Problem of the Cigarette Smokers
  • References
  • 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
  • References
  • 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
  • Reference
  • 7 Fairness
  • 7.1 Weak vs. Strong Fairness
  • 8 Deadlocks
  • 8.1 Characterization
  • 8.1.1 Simple Examples
  • 8.2 Countermeasures
  • 8.2.1 Exclusion
  • 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
  • References
  • 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.1.1 Signal and Exit
  • 9.6.2 Signal and Wait
  • 9.6.3 Signal and Urgent Wait
  • 9.6.4 Preemptive Versus Non-preemptive 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 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 Concept
  • 9.11 Implementation of the Monitor Concept
  • 9.12 The Problem of Nested Monitor Calls
  • References
  • 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 Bounded Buffers
  • 10.5 The Sleeping Barber
  • 10.6 Barrier Synchronization
  • 10.7 The Readers-Writers Problem
  • 10.8 The Left-Right Problem
  • 10.9 The Dining Philosophers
  • 10.10 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 The Readers-Writers Problem
  • 11.6.4 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
  • References
  • 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-Networkchannels Between Processes on Arbitrary Computers
  • 13.3.1 A Simple Example
  • 13.4 Distributed Locks Due to Ricart/Agrawala
  • References
  • 14 Universal Far Monitors
  • 14.1 Extension of the 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 Problem
  • 14.7 Account
  • 14.8 Remote Procedure Calls
  • 14.8.1 Example of a Remote Procedure Call
  • References
  • 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.2.2.1 Writing Graphs to the Screen
  • 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
  • Reference
  • 16 Heartbeat Algorithms
  • 16.1 The Basic Idea
  • 16.2 Getting to Know the Network
  • 16.3 Matrix-Based Solution
  • 16.4 Graph-Based Solutions
  • 16.4.1 With Knowledge of the Diameter of the Network Graph
  • 16.4.2 Without Global Knowledge
  • References
  • 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
  • References
  • 18 Leader Election Algorithms
  • 18.1 Basics
  • 18.2 Algorithm of Chang/Roberts
  • 18.3 Algorithm of Hirschberg/Sinclair
  • 18.4 Algorithm from Peterson
  • 18.5 Election with Depth-First Search
  • References
  • Further Literature
  • References
  • Index