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:

5 men in bathroom
3 women waiting
Men keep arriving every few seconds
Bathroom never empties completely
Women wait forever!

Simple solutions fail:

“First come, first served” - Men can keep entering while women wait
“Empty bathroom required” - Inefficient, underutilizes capacity
“No rules” - Complete chaos, gender mixing

Real-World Applications

This pattern appears everywhere:

Database readers/writers: Multiple readers or single writer
Meeting rooms: Different teams can’t overlap
Shared workspaces: Different groups need exclusive access
Network bandwidth: Fair queuing between traffic classes
CPU scheduling: Fair resource allocation between processes

State Diagram

stateDiagram-v2 [*] --> Empty Empty --> MenInside: Man arrives Empty --> WomenInside: Woman arrives MenInside --> MenInside: Man arrives\n(if capacity available) MenInside --> Empty: Last man leaves WomenInside --> WomenInside: Woman arrives\n(if capacity available) WomenInside --> Empty: Last woman leaves note right of MenInside Men can enter if: - Bathroom has men - Capacity available - No women waiting (fairness) end note note right of WomenInside Women can enter if: - Bathroom has women - Capacity available - No men waiting (fairness) end note

Implementation in Go

package main

import (
	"fmt"
	"math/rand"
	"sync"
	"time"
)

type Gender int

const (
	Male Gender = iota
	Female
)

func (g Gender) String() string {
	if g == Male {
		return "Man"
	}
	return "Woman"
}

func (g Gender) Emoji() string {
	if g == Male {
		return "👨"
	}
	return "👩"
}

type Bathroom struct {
	capacity      int
	currentGender *Gender // nil when empty
	occupancy     int
	menWaiting    int
	womenWaiting  int
	mu            sync.Mutex
	condition     *sync.Cond

	// Statistics
	totalEntries  map[Gender]int
	maxWaitTime   map[Gender]time.Duration
}

func NewBathroom(capacity int) *Bathroom {
	b := &Bathroom{
		capacity:     capacity,
		totalEntries: make(map[Gender]int),
		maxWaitTime:  make(map[Gender]time.Duration),
	}
	b.condition = sync.NewCond(&b.mu)
	return b
}

// Enter attempts to enter the bathroom with fairness guarantee
func (b *Bathroom) Enter(gender Gender, id int) {
	b.mu.Lock()

	startWait := time.Now()

	// Update waiting count
	if gender == Male {
		b.menWaiting++
	} else {
		b.womenWaiting++
	}

	// Wait until we can enter
	for !b.canEnter(gender) {
		b.condition.Wait()
	}

	waitTime := time.Since(startWait)
	if waitTime > b.maxWaitTime[gender] {
		b.maxWaitTime[gender] = waitTime
	}

	// Update waiting count
	if gender == Male {
		b.menWaiting--
	} else {
		b.womenWaiting--
	}

	// Enter bathroom
	if b.currentGender == nil {
		g := gender
		b.currentGender = &g
		fmt.Printf("[Bathroom] 🚪 Now serving: %s\n", gender)
	}

	b.occupancy++
	b.totalEntries[gender]++

	fmt.Printf("[%s %d] %s Entered (occupancy: %d/%d, waiting: 👨 %d, 👩 %d)\n",
		gender, id, gender.Emoji(), b.occupancy, b.capacity, b.menWaiting, b.womenWaiting)

	b.mu.Unlock()
}

// canEnter determines if a person can enter with fairness rules
func (b *Bathroom) canEnter(gender Gender) bool {
	// Empty bathroom - anyone can enter
	if b.currentGender == nil {
		return true
	}

	// Wrong gender currently inside
	if *b.currentGender != gender {
		return false
	}

	// At capacity
	if b.occupancy >= b.capacity {
		return false
	}

	// Fairness check: prevent starvation
	// If opposite gender is waiting, don't let more of current gender enter
	// unless bathroom is being emptied
	if gender == Male && b.womenWaiting > 0 && b.occupancy > 0 {
		return false
	}
	if gender == Female && b.menWaiting > 0 && b.occupancy > 0 {
		return false
	}

	return true
}

// Leave exits the bathroom
func (b *Bathroom) Leave(gender Gender, id int) {
	b.mu.Lock()
	defer b.mu.Unlock()

	b.occupancy--

	fmt.Printf("[%s %d] %s Left (occupancy: %d/%d)\n",
		gender, id, gender.Emoji(), b.occupancy, b.capacity)

	// Last person out? Reset gender
	if b.occupancy == 0 {
		b.currentGender = nil
		fmt.Println("[Bathroom] 🚪 Now empty, available to all")
	}

	// Wake up all waiting goroutines
	b.condition.Broadcast()
}

// Person simulates a person using the bathroom
func (b *Bathroom) Person(gender Gender, id int) {
	// Random arrival time
	time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond)

	fmt.Printf("[%s %d] %s Approaching bathroom...\n", gender, id, gender.Emoji())

	b.Enter(gender, id)

	// Use bathroom
	time.Sleep(time.Duration(100+rand.Intn(200)) * time.Millisecond)

	b.Leave(gender, id)
}

// Stats prints bathroom statistics
func (b *Bathroom) Stats() {
	b.mu.Lock()
	defer b.mu.Unlock()

	fmt.Println("\n📊 Bathroom Statistics:")
	fmt.Printf("   Capacity: %d\n", b.capacity)
	fmt.Printf("   Total entries:\n")
	fmt.Printf("     👨 Men:   %d\n", b.totalEntries[Male])
	fmt.Printf("     👩 Women: %d\n", b.totalEntries[Female])
	fmt.Printf("   Max wait time:\n")
	fmt.Printf("     👨 Men:   %v\n", b.maxWaitTime[Male].Round(time.Millisecond))
	fmt.Printf("     👩 Women: %v\n", b.maxWaitTime[Female].Round(time.Millisecond))
}

func main() {
	fmt.Println("=== The Bathroom Problem ===")
	fmt.Println("Unisex bathroom with fairness guarantee\n")

	const (
		capacity   = 3
		numMen     = 8
		numWomen   = 8
	)

	bathroom := NewBathroom(capacity)

	var wg sync.WaitGroup

	// Men
	for i := 0; i < numMen; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			bathroom.Person(Male, id)
		}(i)
	}

	// Women
	for i := 0; i < numWomen; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			bathroom.Person(Female, id)
		}(i)
	}

	wg.Wait()

	bathroom.Stats()
	fmt.Println("\n✓ Simulation complete!")
}

How It Works

1. State Management with Mutex

type Bathroom struct {
    currentGender *Gender  // nil = empty, non-nil = current gender
    occupancy     int      // How many inside
    menWaiting    int      // Waiting men count
    womenWaiting  int      // Waiting women count
    mu            sync.Mutex
    condition     *sync.Cond
}

All state protected by a single mutex for consistency.

2. Condition Variable for Waiting

b.condition = sync.NewCond(&b.mu)

// Wait
for !b.canEnter(gender) {
    b.condition.Wait()  // Releases lock, sleeps, reacquires on wake
}

// Wake all
b.condition.Broadcast()  // On leave, wake everyone to recheck

sync.Cond provides efficient waiting without busy polling.

3. Fairness Algorithm

func (b *Bathroom) canEnter(gender Gender) bool {
    // Empty? Anyone can enter
    if b.currentGender == nil {
        return true
    }

    // Wrong gender or at capacity?
    if *b.currentGender != gender || b.occupancy >= b.capacity {
        return false
    }

    // Fairness: if opposite gender waiting, don't let more in
    if gender == Male && b.womenWaiting > 0 && b.occupancy > 0 {
        return false  // Women are waiting, let bathroom empty
    }

    return true
}

Key insight: Once opposite gender is waiting, no more entries - forces bathroom to empty and switch.

Advanced: Priority-Based Fairness

Let’s add a priority system where longer waits get higher priority:

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
	"time"
)

type WaitingPerson struct {
	gender  Gender
	id      int
	arrival time.Time
}

type PriorityBathroom struct {
	capacity      int
	currentGender *Gender
	occupancy     int
	waiting       []WaitingPerson
	mu            sync.Mutex
	condition     *sync.Cond
	switchCount   atomic.Int64
}

func NewPriorityBathroom(capacity int) *PriorityBathroom {
	pb := &PriorityBathroom{
		capacity: capacity,
		waiting:  make([]WaitingPerson, 0),
	}
	pb.condition = sync.NewCond(&pb.mu)
	return pb
}

func (pb *PriorityBathroom) Enter(gender Gender, id int) {
	pb.mu.Lock()

	// Add to waiting queue
	wp := WaitingPerson{gender, id, time.Now()}
	pb.waiting = append(pb.waiting, wp)

	// Wait until we can enter
	for !pb.canEnter(gender, id) {
		pb.condition.Wait()
	}

	// Remove from waiting queue
	for i, w := range pb.waiting {
		if w.id == id && w.gender == gender {
			pb.waiting = append(pb.waiting[:i], pb.waiting[i+1:]...)
			break
		}
	}

	// Enter
	if pb.currentGender == nil {
		g := gender
		pb.currentGender = &g
		pb.switchCount.Add(1)
		fmt.Printf("[Priority Bathroom] 🔄 Switched to: %s (switch #%d)\n",
			gender, pb.switchCount.Load())
	}

	pb.occupancy++
	waitTime := time.Since(wp.arrival)

	fmt.Printf("[%s %d] %s Entered after %v wait (occupancy: %d/%d)\n",
		gender, id, gender.Emoji(), waitTime.Round(time.Millisecond),
		pb.occupancy, pb.capacity)

	pb.mu.Unlock()
}

func (pb *PriorityBathroom) canEnter(gender Gender, id int) bool {
	// Empty - check if we're highest priority
	if pb.currentGender == nil {
		return pb.isHighestPriority(gender, id)
	}

	// Wrong gender
	if *pb.currentGender != gender {
		return false
	}

	// At capacity
	if pb.occupancy >= pb.capacity {
		return false
	}

	// Check if opposite gender has been waiting longer
	longestWait := pb.getLongestWaitTimeForOppositeGender(gender)
	if longestWait > 500*time.Millisecond && pb.occupancy > 0 {
		return false // Let bathroom empty for waiting people
	}

	return true
}

func (pb *PriorityBathroom) isHighestPriority(gender Gender, id int) bool {
	if len(pb.waiting) == 0 {
		return true
	}

	// Find longest waiting person
	oldest := pb.waiting[0]
	for _, w := range pb.waiting[1:] {
		if w.arrival.Before(oldest.arrival) {
			oldest = w
		}
	}

	// Are we the oldest?
	return oldest.gender == gender && oldest.id == id
}

func (pb *PriorityBathroom) getLongestWaitTimeForOppositeGender(gender Gender) time.Duration {
	var maxWait time.Duration
	oppositeGender := Female
	if gender == Female {
		oppositeGender = Male
	}

	for _, w := range pb.waiting {
		if w.gender == oppositeGender {
			waitTime := time.Since(w.arrival)
			if waitTime > maxWait {
				maxWait = waitTime
			}
		}
	}

	return maxWait
}

func (pb *PriorityBathroom) Leave(gender Gender, id int) {
	pb.mu.Lock()
	defer pb.mu.Unlock()

	pb.occupancy--
	fmt.Printf("[%s %d] %s Left (occupancy: %d/%d)\n",
		gender, id, gender.Emoji(), pb.occupancy, pb.capacity)

	if pb.occupancy == 0 {
		pb.currentGender = nil
		fmt.Println("[Priority Bathroom] 🚪 Empty")
	}

	pb.condition.Broadcast()
}

func (pb *PriorityBathroom) Person(gender Gender, id int) {
	time.Sleep(time.Duration(id*50) * time.Millisecond)

	pb.Enter(gender, id)
	time.Sleep(200 * time.Millisecond) // Use bathroom
	pb.Leave(gender, id)
}

func RunPriorityBathroom() {
	fmt.Println("\n=== Priority-Based Fairness ===\n")

	bathroom := NewPriorityBathroom(3)

	var wg sync.WaitGroup

	// Create a scenario that could cause starvation without priority
	// 10 men arrive first
	for i := 0; i < 10; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			bathroom.Person(Male, id)
		}(i)
	}

	// Then 5 women arrive (should get priority eventually)
	time.Sleep(100 * time.Millisecond)
	for i := 0; i < 5; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			bathroom.Person(Female, id+100)
		}(i)
	}

	wg.Wait()

	fmt.Printf("\n📊 Total gender switches: %d\n", bathroom.switchCount.Load())
	fmt.Println("✓ Priority simulation complete!")
}

func main() {
	RunPriorityBathroom()
}

Key Go Patterns

1. Condition Variables with sync.Cond

condition := sync.NewCond(&mutex)

// Wait pattern
mutex.Lock()
for !condition_met {
    condition.Wait()  // Atomically unlocks mutex and waits
}
// condition is true, mutex is locked
doWork()
mutex.Unlock()

// Signal pattern
mutex.Lock()
updateState()
condition.Broadcast()  // Wake all waiters
mutex.Unlock()

2. Pointer to Indicate Optional State

currentGender *Gender  // nil = empty, non-nil = occupied

if b.currentGender == nil {
    // Empty bathroom
} else {
    // *b.currentGender gives current gender
}

3. Fair Scheduling with Wait Counters

// Track waiting counts
menWaiting++
womenWaiting++

// Use in fairness logic
if oppositeGenderWaiting > 0 && occupancy > 0 {
    return false  // Let bathroom empty first
}

Performance Considerations

Throughput vs Fairness Trade-off

Maximum throughput (no fairness):

Let same gender keep entering forever
High capacity utilization
Other gender starves

Perfect fairness (strict alternation):

Empty bathroom between switches
Low capacity utilization
No starvation

Balanced approach (implemented above):

Allow filling with same gender
Switch when opposite gender waiting
Good utilization + fairness

Optimal Capacity

Capacity = Expected_Group_Size * 1.5

Too small: Frequent switches, low throughput
Too large: Groups block each other, unfair
Sweet spot: 2-4 for typical scenarios

Variations

1. Timeout-Based Entry

func (b *Bathroom) EnterWithTimeout(gender Gender, id int, timeout time.Duration) bool {
    deadline := time.Now().Add(timeout)

    b.mu.Lock()
    defer b.mu.Unlock()

    for !b.canEnter(gender) {
        if time.Now().After(deadline) {
            return false  // Timed out
        }
        b.condition.Wait()
    }

    // Entered successfully
    return true
}

2. Three or More Groups

type Group int

const (
    GroupA Group = iota
    GroupB
    GroupC
)

// Same logic, just track current group
// Use round-robin or priority queue for fairness

3. Capacity Per Group

// Men capacity: 5, Women capacity: 3
func (b *Bathroom) canEnter(gender Gender) bool {
    capacity := b.capacityFor(gender)
    return b.occupancy < capacity && *b.currentGender == gender
}

Advantages of This Pattern

✓ Prevents starvation - Fairness guaranteed ✓ High throughput - Multiple concurrent users ✓ Simple semantics - Clear rules ✓ Graceful under load - No busy waiting

When to Use

✓ Use when:

Resources need exclusive group access
Multiple users can share simultaneously
Fairness is required
Groups arrive randomly

✗ Avoid when:

Single-user resources (use mutex)
No fairness needed (use simple locks)
Groups have priorities (use priority queue)
Unlimited capacity (use semaphore)

Try It Yourself

Vary arrival patterns - Burst arrivals vs steady
Test starvation - What if men arrive 10x more frequently?
Add priorities - VIP vs regular users
Measure fairness - Track max wait times
Three genders - Extend to 3+ groups

This is part 13 of “Golang Experiments: Classic Concurrency Problems”

The Bathroom Problem#

The Scenario#

The Challenge: Fairness vs Throughput#

Real-World Applications#

State Diagram#

Implementation in Go#

How It Works#

1. State Management with Mutex#

2. Condition Variable for Waiting#

3. Fairness Algorithm#

Advanced: Priority-Based Fairness#

Key Go Patterns#

1. Condition Variables with sync.Cond#

2. Pointer to Indicate Optional State#

3. Fair Scheduling with Wait Counters#

Performance Considerations#

Throughput vs Fairness Trade-off#

Optimal Capacity#

Variations#

1. Timeout-Based Entry#

2. Three or More Groups#

3. Capacity Per Group#

Advantages of This Pattern#

When to Use#

Try It Yourself#