Banker's Algorithm: Deadlock Avoidance Through Safe State Detection

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

    November 18, 2025 · 14 min · Rafiul Alam

    Cigarette Smokers: Resource Matching Problem

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

    November 18, 2025 · 8 min · Rafiul Alam

    Dining Philosophers: Five Forks and a Deadlock

    The Classic Dining Philosophers Problem The Dining Philosophers problem is one of the most famous concurrency problems, introduced by Edsger Dijkstra in 1965. It beautifully illustrates the challenges of resource sharing and deadlock in concurrent systems. The Setup: Five philosophers sit around a circular table. Between each pair of philosophers is a single fork (5 forks total). Each philosopher needs two forks to eat - one from their left and one from their right. ...

    November 18, 2025 · 6 min · Rafiul Alam

    Dining Philosophers: The Asymmetric Solution

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

    November 18, 2025 · 8 min · Rafiul Alam

    Dining Philosophers: The Waiter Solution

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

    November 18, 2025 · 7 min · Rafiul Alam

    Drinking Philosophers: Generalized Resource Contention

    The Drinking Philosophers Problem The Drinking Philosophers Problem is a generalization of the classic Dining Philosophers Problem, proposed by K. M. Chandy and J. Misra in 1984. Unlike the dining version where philosophers share forks with immediate neighbors in a circle, drinking philosophers share bottles with arbitrary neighbors based on a conflict graph. This makes it much more realistic for modeling real-world resource allocation. The Scenario The drinking party has: ...

    November 18, 2025 · 12 min · Rafiul Alam

    Golang Experiments: Classic Concurrency Problems

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

    November 18, 2025 · 11 min · Rafiul Alam

    Producer-Consumer: Multiple Producers, Multiple Consumers

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

    November 18, 2025 · 9 min · Rafiul Alam

    Producer-Consumer: The Bounded Buffer

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

    November 18, 2025 · 8 min · Rafiul Alam

    Producer-Consumer: The Unbounded Buffer

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

    November 18, 2025 · 7 min · Rafiul Alam