Synchronization

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

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

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

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