Concurrency

The Bathroom Problem The Bathroom Problem is a classic coordination puzzle that illustrates fairness, starvation prevention, and group coordination in concurrent systems. First proposed by Jon Kleinberg, it demonstrates how to manage resource access with group-based constraints. The Scenario A unisex bathroom has: Capacity for N people Only people of one gender at a time Random arrivals from multiple genders The rules: Multiple people of the same gender can enter simultaneously (up to capacity) People of different genders cannot be in the bathroom at the same time When empty, either gender can enter Must prevent starvation - no gender should wait forever The Challenge: Fairness vs Throughput The trap is starvation. Consider: ...

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: ...

The Cigarette Smokers Problem The Cigarette Smokers problem is a unique synchronization challenge that demonstrates resource matching and conditional waiting. Proposed by Suhas Patil in 1971, it’s known for not being solvable with only semaphores! The Scenario There are: 3 smokers 1 agent Each smoker needs 3 ingredients to smoke: Tobacco Paper Matches The setup: Smoker 1 has infinite tobacco Smoker 2 has infinite paper Smoker 3 has infinite matches The agent has infinite of ALL three The rules: ...

The Two Generals’ Problem The Two Generals’ Problem, also known as the Two Armies Problem, is a classic thought experiment that demonstrates the impossibility of achieving perfect consensus over an unreliable communication channel. It was first formulated by E. A. Akkoyunlu, K. Ekanadham, and R. V. Huber in 1975. The Scenario Two armies need to coordinate an attack: General A and General B surround an enemy They must attack simultaneously to win If only one attacks → defeat They communicate via messengers through enemy territory Messages can be lost or intercepted Question: Can they guarantee coordinated attack? The Impossible Dilemma %%{init: {'theme':'dark', 'themeVariables': {'primaryTextColor':'#fff','secondaryTextColor':'#fff','tertiaryTextColor':'#fff','textColor':'#fff','nodeTextColor':'#fff','edgeLabelText':'#fff','clusterTextColor':'#fff','actorTextColor':'#fff'}}}%% sequenceDiagram participant GA as General A participant Enemy as Enemy Territory participant GB as General B Note over GA: Wants to attackat dawn GA->>Enemy: "Attack at dawn" Enemy->>GB: Message delivered Note over GB: Received message,but A doesn't know! GB->>Enemy: "Acknowledged" Enemy->>GA: ACK delivered? Note over GA: Received ACK,but B doesn't know! GA->>Enemy: "ACK of ACK" Enemy->>GB: Delivered? Note over GA,GB: This never ends! The Core Problem The infinite regress: ...

The Roller Coaster Problem The Roller Coaster Problem, introduced by Allen Downey in “The Little Book of Semaphores,” demonstrates multi-phase synchronization and cyclic barriers. It’s a perfect model for batch processing systems where work happens in coordinated phases. The Scenario A roller coaster ride has: A car with capacity C passengers Passengers continuously arriving and queuing The car cycles through: board → ride → unboard → repeat The rules: Car waits until exactly C passengers are ready Passengers can’t board until car is empty Car can’t run until full Passengers must unboard before new passengers board Process repeats indefinitely The Challenge: Three-Phase Coordination Each ride has three synchronized phases: ...

The Search-Insert-Delete Problem The Search-Insert-Delete Problem extends the classic Readers-Writers problem with three different access patterns instead of two. It demonstrates how to coordinate multiple operation types with different compatibility requirements - a common challenge in database systems and data structures. The Scenario Three types of goroutines access a shared list: Searchers - Read the list without modifying it Inserters - Add new elements to the list Deleters - Remove elements from the list Compatibility rules: ...

File monitoring is a common requirement in many applications: watching for configuration changes, processing uploads, syncing directories, or building development tools. In this post, we’ll build a production-ready file monitoring service that tracks word counts across all files in a directory using Go’s powerful concurrency primitives. The Challenge Build a service that: Monitors a directory and all its subdirectories Counts words in all files in real-time Updates counts when files are modified, created, or deleted Processes multiple files concurrently Provides current statistics on demand Handles errors gracefully Why This Matters Real-time file monitoring powers many production systems: ...

The Writer Starvation Problem In the readers preference solution, we saw how continuous readers can starve writers. The writers preference solution fixes this by giving writers priority. Key idea: When a writer is waiting, no new readers are allowed to start, even if other readers are currently reading. Real-World Need for Writer Priority Some systems need writer priority: Databases with critical updates (billing, inventory) Real-time systems (sensor updates must not be delayed) Logging systems (log writes can’t be delayed) Configuration systems (updates must propagate quickly) Leader election (state changes need priority) The Solution Go’s sync.RWMutex uses readers preference, so we need to implement writer preference manually using additional synchronization: ...

From Unbounded to Bounded In the previous article, we explored the unbounded buffer pattern where the queue could grow infinitely. This works until you run out of memory! The bounded buffer adds a crucial constraint: maximum queue size. This introduces backpressure - when the buffer is full, producers must wait for consumers to catch up. Why Bounded Buffers Matter Bounded buffers appear everywhere in production systems: TCP sliding windows (flow control) HTTP/2 stream flow control (prevents overwhelm) Message queue limits (RabbitMQ, Kafka partition limits) Thread pool queues (bounded task queues) Rate limiters (token buckets with finite capacity) Circuit breakers (limit concurrent requests) The key benefit: Bounded buffers provide natural backpressure and prevent resource exhaustion. ...

The Sleeping Barber Problem The Sleeping Barber is a classic synchronization problem proposed by Edsger Dijkstra in 1965. It elegantly demonstrates resource management, waiting, and signaling in concurrent systems. The Scenario A barbershop has: 1 barber 1 barber chair N waiting room chairs The rules: If no customers, the barber sleeps When a customer arrives: If barber is sleeping → wake him up If barber is busy → sit in waiting room (if space available) If waiting room is full → leave When barber finishes a customer → check waiting room Real-World Applications This pattern appears in many systems: ...