Concurrency

The Banker’s Algorithm The Banker’s Algorithm is a deadlock avoidance algorithm developed by Edsger Dijkstra in 1965. It models a bank that has limited cash and customers with credit limits who request loans in chunks. The bank only grants loans if the system stays in a “safe state” - meaning it can fulfill all future maximum requests. The Scenario A bank has: Limited cash available Multiple customers with credit limits Customers request loans in chunks over time The rules: ...

Concurrency is one of Go’s most powerful features, built into the language from the ground up. This comprehensive guide covers all essential concurrency patterns with visual diagrams and practical code examples. Table of Contents Goroutines - Basic Concurrency Channels - Communication Select Statement - Multiplexing Worker Pool Pattern Fan-In Pattern Fan-Out Pattern Pipeline Pattern Semaphore Pattern Barrier Pattern Future/Promise Pattern Rate Limiting Pattern Circuit Breaker Pattern Context Pattern Mutex Pattern WaitGroup Pattern ErrGroup Pattern Goroutines - Basic Concurrency Goroutines are lightweight threads managed by the Go runtime. They enable concurrent execution with minimal overhead. ...

The Producer-Consumer Problem The Producer-Consumer pattern is one of the most fundamental concurrency patterns. It appears everywhere in modern software: Message queues (RabbitMQ, Kafka, SQS) Task processing (background jobs, worker pools) Data pipelines (ETL, streaming analytics) Event systems (event buses, pub/sub) Buffering (I/O buffers, network buffers) The Setup: Producers generate data, consumers process it. They run concurrently and need to coordinate through a shared buffer. The Unbounded Buffer Variant In this first variant, we use an unbounded buffer - the queue can grow infinitely (until we run out of memory). This is the simplest version and showcases Go’s beautiful channel abstraction. ...

The Token Ring Problem The Token Ring is a classic distributed mutual exclusion algorithm where nodes are arranged in a logical ring, and a single token circulates. Only the node holding the token can access the shared resource. It’s simple, fair, and starvation-free. The Scenario Nodes arranged in a ring: N nodes form a logical ring A single token passes around the ring Only token holder can enter critical section After using resource, pass token to next node Properties: Fair (FIFO order), no starvation, deadlock-free The challenge: ...

The River Crossing Problem The River Crossing Problem, inspired by Allen Downey’s “The Little Book of Semaphores,” demonstrates constrained group formation and safety-critical synchronization. It models scenarios where groups must form under specific rules before proceeding - common in distributed systems and resource allocation. The Scenario A river crossing with: Two types of people: Hackers (H) and Employees (E) A boat that holds exactly 4 people Random arrivals on the riverbank Safety rules for boarding: ...

The Elegant Solution In the previous articles, we explored the deadlock problem and the waiter solution. Now we’ll see the most elegant solution: the Asymmetric Solution, also known as Resource Ordering. The Key Insight: Deadlock requires circular wait. Break the circle, prevent the deadlock. The Asymmetric Solution Explained Instead of all philosophers picking up forks in the same order (left then right), we make ONE philosopher do the opposite: Philosophers 0-3: Pick up left fork first, then right fork Philosopher 4: Pick up right fork first, then left fork This simple change breaks the circular dependency and prevents deadlock! ...

Breaking the Deadlock In the previous article, we saw how the naive implementation of the Dining Philosophers problem inevitably leads to deadlock. Now we’ll implement the Waiter Solution - a centralized coordinator that prevents deadlock by controlling resource access. The Waiter Solution Concept The Idea: Add a waiter who controls access to the forks. No philosopher can pick up forks without the waiter’s permission. The waiter ensures that at most 4 philosophers can attempt to pick up forks simultaneously. ...

The Gossiping Problem The Gossiping Problem is a classic problem in distributed systems and graph theory. N people each know a unique secret, and they share information through phone calls. On each call, both parties share all secrets they know. The goal: find the minimum number of calls needed for everyone to know all secrets. The Scenario N people, N secrets: Person i knows secret Si initially When persons i and j call each other, they share ALL secrets they know Goal: Everyone knows all N secrets Question: What’s the minimum number of calls? The Mathematical Result For n ≥ 4 people: ...

The Santa Claus Problem The Santa Claus problem is a delightful synchronization challenge by J.A. Trono (1994). It demonstrates group coordination, prioritization, and conditional wake-up patterns. The Scenario Characters: Santa Claus (1) Reindeer (9) Elves (10) The rules: Santa sleeps in his shop at the North Pole Santa can be awakened by either: All 9 reindeer return from vacation → prepare sleigh, deliver toys Any 3 elves have problems → get help from Santa Reindeer have priority over elves Santa helps 3 elves at a time, then goes back to sleep After delivering toys, Santa unhitches reindeer and goes back to sleep The Challenge Coordination: Wake Santa only when conditions met Grouping: Exactly 9 reindeer OR 3 elves Priority: Reindeer interrupt elf help Fairness: All elves should eventually get help Real-World Applications This pattern models many production scenarios: ...

Scaling to Multiple Workers We’ve explored unbounded and bounded buffers with single or few workers. Now let’s scale to many producers and many consumers - the pattern behind most production systems! This pattern combines: Fan-out: Multiple producers generating work Fan-in: Multiple consumers processing work Load balancing: Work distributed across consumers Result aggregation: Collecting results from all consumers Real-World Applications This is THE pattern for scalable systems: Web servers: Multiple request handlers, multiple worker threads Message queues: Multiple publishers, multiple subscribers MapReduce: Multiple mappers, multiple reducers Microservices: Multiple API instances processing requests Data pipelines: Parallel ETL stages Video encoding: Multiple encoders processing jobs The Architecture Shared Channel Producers → Consumers [Buffer] P1 ─┐ ┌─→ C1 P2 ─┤→ [═════Queue═════] → ├─→ C2 P3 ─┤ ├─→ C3 P4 ─┘ └─→ C4 All producers send to same channel All consumers receive from same channel Go's scheduler load balances automatically! Basic Implementation package main import ( "fmt" "math/rand" "sync" "sync/atomic" "time" ) // Job represents work to be done type Job struct { ID int ProducerID int Data int CreatedAt time.Time } // Result represents processed work type Result struct { JobID int ConsumerID int Output int Duration time.Duration } // Stats tracks system metrics type Stats struct { jobsCreated atomic.Int64 jobsProcessed atomic.Int64 totalDuration atomic.Int64 // nanoseconds } func (s *Stats) Report() { created := s.jobsCreated.Load() processed := s.jobsProcessed.Load() avgDuration := time.Duration(0) if processed > 0 { avgDuration = time.Duration(s.totalDuration.Load() / processed) } fmt.Printf(` 📊 Final Statistics: Jobs created: %d Jobs processed: %d Avg duration: %v Jobs in flight: %d `, created, processed, avgDuration, created-processed) } // Producer generates jobs func Producer(id int, jobs chan<- Job, duration time.Duration, stats *Stats, wg *sync.WaitGroup) { defer wg.Done() jobNum := 0 deadline := time.Now().Add(duration) for time.Now().Before(deadline) { job := Job{ ID: id*1000 + jobNum, ProducerID: id, Data: rand.Intn(100), CreatedAt: time.Now(), } jobs <- job stats.jobsCreated.Add(1) jobNum++ // Variable production rate time.Sleep(time.Duration(50+rand.Intn(100)) * time.Millisecond) } fmt.Printf("[Producer %d] Finished, created %d jobs\n", id, jobNum) } // Consumer processes jobs and sends results func Consumer(id int, jobs <-chan Job, results chan<- Result, stats *Stats, wg *sync.WaitGroup) { defer wg.Done() processed := 0 for job := range jobs { start := time.Now() // Simulate work processingTime := time.Duration(80+rand.Intn(120)) * time.Millisecond time.Sleep(processingTime) // Compute result result := Result{ JobID: job.ID, ConsumerID: id, Output: job.Data * 2, Duration: time.Since(start), } results <- result stats.jobsProcessed.Add(1) stats.totalDuration.Add(int64(result.Duration)) processed++ queueTime := start.Sub(job.CreatedAt) if queueTime > 500*time.Millisecond { fmt.Printf("[Consumer %d] ⚠️ Job %d queued for %v\n", id, job.ID, queueTime) } } fmt.Printf("[Consumer %d] Finished, processed %d jobs\n", id, processed) } // ResultAggregator collects all results func ResultAggregator(results <-chan Result, done chan<- struct{}) { resultCount := 0 totalDuration := time.Duration(0) for result := range results { resultCount++ totalDuration += result.Duration if resultCount%10 == 0 { avgDuration := totalDuration / time.Duration(resultCount) fmt.Printf("📦 Aggregator: %d results (avg: %v)\n", resultCount, avgDuration) } } fmt.Printf("📦 Aggregator: Finished with %d total results\n", resultCount) close(done) } func main() { fmt.Println("=== Multiple Producers, Multiple Consumers ===\n") const ( numProducers = 4 numConsumers = 6 bufferSize = 20 duration = 3 * time.Second ) jobs := make(chan Job, bufferSize) results := make(chan Result, bufferSize) stats := &Stats{} fmt.Printf("Configuration:\n") fmt.Printf(" Producers: %d\n", numProducers) fmt.Printf(" Consumers: %d\n", numConsumers) fmt.Printf(" Buffer size: %d\n", bufferSize) fmt.Printf(" Duration: %v\n\n", duration) var producerWg, consumerWg sync.WaitGroup aggregatorDone := make(chan struct{}) // Start result aggregator go ResultAggregator(results, aggregatorDone) // Start consumers fmt.Println("Starting consumers...") for i := 0; i < numConsumers; i++ { consumerWg.Add(1) go Consumer(i, jobs, results, stats, &consumerWg) } // Start producers fmt.Println("Starting producers...\n") for i := 0; i < numProducers; i++ { producerWg.Add(1) go Producer(i, jobs, duration, stats, &producerWg) } // Wait for producers to finish producerWg.Wait() fmt.Println("\n✓ All producers finished") close(jobs) // Signal consumers no more jobs // Wait for consumers to finish consumerWg.Wait() fmt.Println("✓ All consumers finished") close(results) // Signal aggregator no more results // Wait for aggregator <-aggregatorDone fmt.Println("✓ Result aggregator finished") stats.Report() fmt.Println("\n✓ Pipeline complete!") } Load Balancing with Channels One of Go’s superpowers: channels provide automatic load balancing! ...