Welcome to Golang Experiments!

This series explores classic concurrency problems through the lens of Go’s powerful concurrency primitives. Each problem is a timeless synchronization challenge that teaches fundamental concepts you’ll use in production systems every day.

What you’ll learn:

  • Go’s concurrency features (goroutines, channels, sync primitives)
  • How to recognize and solve common synchronization problems
  • Patterns that appear in real-world distributed systems
  • When to use different synchronization strategies

Why Study Classic Problems?

These aren’t just academic exercises! Each problem represents a pattern you’ll encounter in production:

  • Dining Philosophers → Database deadlocks, distributed locks
  • Producer-Consumer → Message queues, data pipelines
  • Readers-Writers → Cache updates, configuration management
  • Sleeping Barber → Thread pools, resource management
  • Cigarette Smokers → Dependency resolution, resource matching
  • Santa Claus → Batch processing, group coordination
  • Bathroom Problem → Fair resource access, gender-based coordination
  • Roller Coaster → Multi-phase batch processing, cyclic operations
  • Search-Insert-Delete → Three-way access control, database operations
  • River Crossing → Constrained group formation, safety rules

The Series

Part 1: Dining Philosophers

The classic deadlock problem and three different solutions:

🍴 Five Forks and a Deadlock

Learn how circular wait leads to deadlock. Understand the four Coffman conditions and how to detect deadlocks in production.

Key concepts:

  • Deadlock conditions
  • Circular wait
  • Timeout detection
  • Go’s sync.Mutex

🎩 The Waiter Solution

Use a centralized coordinator (semaphore) to prevent deadlock by limiting concurrency.

Key concepts:

  • Semaphores using buffered channels
  • Centralized coordination
  • Backpressure
  • Resource limiting

⚖️ The Asymmetric Solution

The elegant solution: break circular wait through resource ordering.

Key concepts:

  • Resource ordering
  • Lock hierarchies
  • Global ordering
  • Distributed deadlock prevention

Part 2: Producer-Consumer

The fundamental pattern behind all data pipelines:

📨 The Unbounded Buffer

Unlimited queue capacity - maximum throughput but potential memory issues.

Key concepts:

  • Channels as queues
  • Send-only and receive-only channels
  • Channel closing semantics
  • Atomic operations for metrics

📦 The Bounded Buffer

Limited queue capacity provides natural backpressure and prevents resource exhaustion.

Key concepts:

  • Buffered channels
  • Backpressure
  • Flow control
  • Drop strategies (oldest vs newest)

🔀 Multiple Producers, Multiple Consumers

Scale to many workers with automatic load balancing.

Key concepts:

  • Fan-out/fan-in patterns
  • Load balancing with channels
  • Result aggregation
  • Worker pools

Part 3: Readers-Writers

Managing concurrent read and exclusive write access:

📖 Readers Preference

Maximize read concurrency using Go’s sync.RWMutex. Writers can starve.

Key concepts:

  • sync.RWMutex
  • Read/write locks
  • Lock embedding
  • Performance characteristics

✍️ Writers Preference

Ensure writers don’t starve by giving them priority. Custom implementation required.

Key concepts:

  • Custom synchronization primitives
  • Condition variables
  • Writer starvation prevention
  • Priority mechanisms

⚖️ Fair Solution

FIFO ordering ensures neither readers nor writers starve.

Key concepts:

  • Fairness algorithms
  • Ticket systems
  • FIFO queues
  • Predictable latency

Part 4: Advanced Problems

💈 Sleeping Barber: The Waiting Room Problem

Model resource pools with waiting rooms - workers sleep when idle.

Key concepts:

  • Bounded queues
  • Worker lifecycle
  • Sleep/wake patterns
  • Graceful degradation

🚬 Cigarette Smokers: Resource Matching

Match complementary resources - demonstrates why semaphores alone aren’t enough.

Key concepts:

  • Resource matching
  • Combination detection
  • Pusher pattern
  • State machines

🎅 Santa Claus Problem: Elves and Reindeer

Coordinate groups with priority handling and batch processing.

Key concepts:

  • Group formation
  • Priority handling
  • Batch coordination
  • Barrier synchronization

Part 5: Coordination Puzzles

🚻 The Bathroom Problem: Unisex Bathroom Coordination

Fair access to shared resources with group-based exclusion and starvation prevention.

Key concepts:

  • Fairness algorithms
  • Group coordination
  • Starvation prevention
  • Condition variables
  • Gender-based mutual exclusion

🎢 The Roller Coaster: Multi-Phase Synchronization

Cyclic operations with three coordinated phases: boarding, riding, and unboarding.

Key concepts:

  • Multi-phase synchronization
  • Cyclic barriers
  • Batch processing
  • Last-actor pattern
  • Channel-based coordination

🔍 The Search-Insert-Delete Problem: Three-Way Synchronization

Coordinate three operation types with asymmetric compatibility rules.

Key concepts:

  • Three-way access control
  • Asymmetric compatibility
  • Multiple condition variables
  • Priority-based scheduling
  • Advanced locking patterns

⛴️ The River Crossing: Group Formation with Constraints

Form groups under safety constraints - demonstrates deadlock prevention in group coordination.

Key concepts:

  • Constrained group formation
  • Safety-critical synchronization
  • Deadlock prevention
  • Fairness vs efficiency
  • Multi-type coordination

Part 6: Distributed Algorithm Stories

Real distributed systems problems that appear in blockchain, databases, and networked applications:

🏰 The Byzantine Generals: Achieving Consensus with Traitors

Achieve consensus when some participants may be faulty or malicious. Fundamental to blockchain and fault-tolerant systems.

Key concepts:

  • Byzantine fault tolerance
  • n ≥ 3f+1 requirement
  • Practical Byzantine Fault Tolerance (PBFT)
  • Consensus impossibility results
  • Blockchain applications

👑 The Bully Election: Leader Election in Distributed Systems

Elect a leader when the current leader fails - highest ID always wins.

Key concepts:

  • Leader election
  • Distributed coordination
  • Failure detection
  • O(n²) message complexity
  • Heartbeat-based monitoring

🔄 The Token Ring: Fair Resource Access Through Token Passing

Pass a token around a ring - only token holder can access resources. Simple and fair but sensitive to failures.

Key concepts:

  • Token-based mutual exclusion
  • FIFO fairness
  • Token loss detection
  • Ring topology
  • Fault recovery

⚔️ Two Generals’ Problem: The Impossibility of Perfect Consensus

The fundamental impossibility result - perfect consensus over unreliable channels is impossible.

Key concepts:

  • Impossibility results
  • Unreliable communication
  • Practical solutions (timeouts, retries)
  • TCP 3-way handshake
  • Eventual consistency

📢 The Gossiping Problem: Efficient Information Spreading

Spread information efficiently through a network - achieves optimal 2n-4 calls for n participants.

Key concepts:

  • Epidemic algorithms
  • Information dissemination
  • 2n-4 optimal solution
  • Parallel gossiping
  • Anti-entropy protocols

Part 7: Resource Allocation Dilemmas

Advanced resource management problems that model real-world systems:

🏦 The Banker’s Algorithm: Deadlock Avoidance Through Safe States

Allocate resources only if system remains in a safe state - guarantees deadlock avoidance.

Key concepts:

  • Safe state detection
  • Deadlock avoidance (not just detection)
  • Resource allocation graphs
  • Maximum need declaration
  • O(m × n²) complexity

🍷 The Drinking Philosophers: Arbitrary Resource Dependencies

Generalization of dining philosophers with arbitrary conflict graphs - models real resource allocation better.

Key concepts:

  • Arbitrary resource graphs
  • Clean/dirty protocol
  • Decentralized coordination
  • Multiple resources per process
  • Graph-based synchronization

🛗 The Elevator Problem: Multi-Objective Scheduling

Schedule multiple elevators to optimize wait time, travel time, and throughput - classic scheduling problem.

Key concepts:

  • Multiple scheduling strategies (SCAN, LOOK, Nearest-First)
  • Multi-objective optimization
  • Load balancing
  • Real-time decision making
  • Cost-based dispatch

Go Concurrency Primitives Used

Throughout the series, we use Go’s excellent concurrency tools:

Goroutines

go func() {
    // Concurrent execution
}()

Lightweight threads managed by the Go runtime.

Channels

ch := make(chan T)        // Unbuffered
ch := make(chan T, 100)   // Buffered
ch <- value               // Send
value := <-ch             // Receive
close(ch)                 // Close

Type-safe communication between goroutines.

Sync Package

var mu sync.Mutex         // Mutual exclusion
var rw sync.RWMutex       // Read/write lock
var wg sync.WaitGroup     // Wait for group
var once sync.Once        // Run exactly once
cond := sync.NewCond(&mu) // Condition variable

Select Statement

select {
case val := <-ch1:
    // Received from ch1
case ch2 <- val:
    // Sent to ch2
case <-time.After(timeout):
    // Timeout
default:
    // Non-blocking
}

Context Package

ctx, cancel := context.WithTimeout(parent, timeout)
ctx, cancel := context.WithCancel(parent)

Atomic Operations

var counter atomic.Int64
counter.Add(1)
counter.Load()
counter.Store(42)

Pattern Summary

Problem Pattern Go Primitives Use Case
Dining Philosophers Resource ordering Mutex, Resource IDs Distributed locks
Producer-Consumer Pipeline Channels, WaitGroup Data processing
Readers-Writers Shared access RWMutex, Atomic Caching
Sleeping Barber Resource pool Channels, Goroutines Thread pools
Cigarette Smokers Resource matching Channels, Cond Dependencies
Santa Claus Batch coordination Channels, Cond Batch processing
Bathroom Problem Fair group access Cond, Mutex, Counters Resource fairness
Roller Coaster Multi-phase sync Channels, Barriers Batch operations
Search-Insert-Delete Three-way access Cond, Atomic, Mutex Database indexes
River Crossing Constrained groups Channels, Cond Group formation
Byzantine Generals Consensus with faults Channels, Crypto Blockchain, fault tolerance
Bully Election Leader election Heartbeats, Timeouts Distributed coordination
Token Ring Fair mutual exclusion Channels, Ring topology FIFO resource access
Two Generals Impossibility Timeouts, Retries Network protocols
Gossiping Information spread Epidemic algorithms Distributed databases
Banker’s Algorithm Deadlock avoidance State analysis Resource allocation
Drinking Philosophers Arbitrary dependencies Graph-based locks Complex resource sharing
Elevator Problem Multi-objective scheduling Cost functions Load balancing

When to Use Each Pattern

Use Dining Philosophers patterns when:

  • Managing multiple locks
  • Preventing deadlock is critical
  • Resources have natural ordering

Use Producer-Consumer when:

  • Building data pipelines
  • Processing streams of work
  • Need backpressure control

Use Readers-Writers when:

  • Data is read frequently, written rarely
  • Need to maximize read concurrency
  • Cache invalidation scenarios

Use Sleeping Barber when:

  • Managing worker pools
  • Resources should idle when unused
  • Queue has capacity limits

Use Cigarette Smokers when:

  • Need specific resource combinations
  • Complex dependency resolution
  • Resources come from different sources

Use Santa Claus when:

  • Batch processing is more efficient
  • Need group coordination
  • Have priority levels

Use Bathroom Problem when:

  • Resources need fair group access
  • Groups are mutually exclusive
  • Preventing starvation is critical
  • Multiple users can share simultaneously

Use Roller Coaster when:

  • Operations have distinct phases
  • Cyclic batch processing needed
  • Must wait for full capacity
  • Coordinated state transitions required

Use Search-Insert-Delete when:

  • Three or more operation types
  • Operations have different compatibility rules
  • Need asymmetric access control
  • Database or data structure implementation

Use River Crossing when:

  • Groups must form under constraints
  • Safety rules must be enforced
  • Multiple valid group combinations
  • Deadlock prevention in group coordination

Use Byzantine Generals when:

  • System must tolerate arbitrary failures
  • Nodes may behave maliciously
  • No trusted party exists
  • Consensus is safety-critical

Use Bully Election when:

  • Need leader election in distributed system
  • Clear priority ordering exists
  • Can tolerate O(n²) messages
  • Deterministic leader selection required

Use Token Ring when:

  • Fairness is critical (FIFO ordering)
  • Predictable access pattern needed
  • Small number of nodes
  • Simple coordination sufficient

Use Two Generals Problem understanding when:

  • Designing over unreliable networks
  • Need to understand consensus limits
  • Implementing retry/timeout logic
  • Choosing between consistency models

Use Gossiping when:

  • Need high availability
  • Can tolerate eventual consistency
  • Large number of nodes
  • Network may be unreliable
  • No central coordinator

Use Banker’s Algorithm when:

  • Resources limited and shared
  • Deadlock avoidance critical
  • Can declare maximum needs upfront
  • System state can be analyzed before allocation

Use Drinking Philosophers when:

  • Arbitrary resource dependencies
  • Conflict graph is not a simple ring
  • Multiple resources per process
  • Decentralized coordination needed

Use Elevator Problem patterns when:

  • Multiple servers handle requests
  • Need to optimize wait time and throughput
  • Load balancing is critical
  • Real-time scheduling decisions required

Best Practices from the Series

1. Always Use Timeouts

select {
case <-done:
    // Success
case <-time.After(timeout):
    // Detect deadlock/starvation
}

2. Use Directional Channels

func producer(out chan<- T)  // Send-only
func consumer(in <-chan T)   // Receive-only

Compile-time safety!

3. Close Channels from Sender

// Producer
for _, item := range items {
    ch <- item
}
close(ch)  // Signal done

// Consumer
for item := range ch {
    // Process until closed
}

4. Use sync.WaitGroup for Coordination

var wg sync.WaitGroup
wg.Add(n)
for i := 0; i < n; i++ {
    go func() {
        defer wg.Done()
        // Work
    }()
}
wg.Wait()

5. Defer Unlocks

mu.Lock()
defer mu.Unlock()
// Can't forget to unlock!

6. Use Context for Cancellation

func worker(ctx context.Context) {
    for {
        select {
        case <-ctx.Done():
            return
        case work := <-workCh:
            // Process
        }
    }
}

Common Pitfalls to Avoid

1. Closing Channels Multiple Times

// ✗ Wrong
close(ch)
close(ch)  // Panic!

// ✓ Correct
var closeOnce sync.Once
closeOnce.Do(func() { close(ch) })

2. Lock Upgrade Deadlock

// ✗ Wrong
mu.RLock()
// ...
mu.Lock()  // Deadlock!

// ✓ Correct
mu.RLock()
needWrite := checkCondition()
mu.RUnlock()
if needWrite {
    mu.Lock()
    // ...
}

3. Forgotten defer

// ✗ Risky
mu.Lock()
if err != nil {
    return  // Leak!
}
mu.Unlock()

// ✓ Safe
mu.Lock()
defer mu.Unlock()

4. Goroutine Leaks

// ✗ Wrong: Goroutine never exits
go func() {
    <-ch  // If ch never closed, leaks
}()

// ✓ Correct: Use context
go func() {
    select {
    case <-ch:
    case <-ctx.Done():
        return
    }
}()

Tools for Debugging

Race Detector

go test -race
go run -race main.go

Deadlock Detection

# GODEBUG=schedtrace=1000 shows scheduler trace
GODEBUG=schedtrace=1000 go run main.go

Profiling

go test -cpuprofile=cpu.prof
go tool pprof cpu.prof

Stack Traces

import "runtime/debug"

debug.PrintStack()

Further Reading

Books

  • “Concurrency in Go” by Katherine Cox-Buday
  • “The Go Programming Language” by Donovan & Kernighan
  • “The Little Book of Semaphores” by Allen Downey

Go Documentation

Papers

  • “The Little Book of Semaphores” - Allen B. Downey
  • “Communicating Sequential Processes” - C.A.R. Hoare
  • Original problem papers - Dijkstra, Courtois, Trono, et al.

What’s Next?

This series covers classic problems, but there’s more to explore:

  • Advanced patterns: Circuit breakers, rate limiters, bulkheads
  • Distributed systems: Consensus, replication, distributed locks
  • Performance: Lock-free algorithms, work stealing
  • Testing: Race detection, chaos testing

Running the Examples

All examples in this series are complete, runnable programs. To try them:

# Clone examples
git clone https://github.com/yourrepo/go-concurrency-experiments

# Run any example
cd dining-philosophers-deadlock
go run main.go

# Run with race detector
go run -race main.go

# Run tests
go test -v -race

Contributing

Found a better solution? Have a question? Want to add another classic problem?

Conclusion

Classic concurrency problems aren’t just theoretical exercises - they’re patterns you’ll see daily in production code. By mastering these problems in Go, you’ll:

✓ Write safer concurrent code ✓ Recognize deadlock and starvation ✓ Choose appropriate synchronization primitives ✓ Debug concurrency issues faster ✓ Design scalable systems

Start with Dining Philosophers: Five Forks and a Deadlock and work through the series. Each problem builds on concepts from previous ones.

Happy coding, and may your goroutines never deadlock! 🚀

Series Index

Dining Philosophers

  1. Five Forks and a Deadlock
  2. The Waiter Solution
  3. The Asymmetric Solution

Producer-Consumer

  1. The Unbounded Buffer
  2. The Bounded Buffer
  3. Multiple Producers, Multiple Consumers

Readers-Writers

  1. Readers Preference
  2. Writers Preference
  3. Fair Solution

Advanced Problems

  1. Sleeping Barber: The Waiting Room Problem
  2. Cigarette Smokers: Resource Matching
  3. Santa Claus Problem: Elves and Reindeer

Coordination Puzzles

  1. The Bathroom Problem: Unisex Bathroom Coordination
  2. The Roller Coaster: Multi-Phase Synchronization
  3. The Search-Insert-Delete Problem: Three-Way Synchronization
  4. The River Crossing: Group Formation with Constraints

Distributed Algorithm Stories

  1. The Byzantine Generals: Achieving Consensus with Traitors
  2. The Bully Election: Leader Election in Distributed Systems
  3. The Token Ring: Fair Resource Access Through Token Passing
  4. Two Generals’ Problem: The Impossibility of Perfect Consensus
  5. The Gossiping Problem: Efficient Information Spreading

Resource Allocation Dilemmas

  1. The Banker’s Algorithm: Deadlock Avoidance Through Safe States
  2. The Drinking Philosophers: Arbitrary Resource Dependencies
  3. The Elevator Problem: Multi-Objective Scheduling

A comprehensive series on classic concurrency problems solved with Go’s powerful primitives