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:

  1. Santa sleeps in his shop at the North Pole
  2. 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
  3. Reindeer have priority over elves
  4. Santa helps 3 elves at a time, then goes back to sleep
  5. 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:

  • Batch processing: Process when batch size reached or timeout
  • Database commits: Group transactions for efficiency
  • Network packet batching: Send when buffer full or timeout
  • Thread pool work stealing: Coordinate worker groups
  • Consensus protocols: Wait for quorum

Implementation in Go

package main

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

type SantaWorkshop struct {
	// Reindeer coordination
	reindeerWaiting int
	reindeerMu      sync.Mutex
	reindeerReady   *sync.Cond

	// Elf coordination
	elfWaiting      int
	elfGroup        []int // IDs of elves in current group
	elfMu           sync.Mutex
	elfReady        *sync.Cond
	elfGetHelp      *sync.Cond

	// Santa coordination
	santaSleeping bool
	santaMu       sync.Mutex
	santaWakeup   chan string // "reindeer" or "elves"
	santaDone     chan struct{}

	// Statistics
	deliveries   int
	elfSessions  int
	elvesSolved  map[int]int
	statsmu      sync.Mutex
}

func NewSantaWorkshop() *SantaWorkshop {
	sw := &SantaWorkshop{
		santaWakeup:  make(chan string, 1),
		santaDone:    make(chan struct{}),
		elvesSolved:  make(map[int]int),
		santaSleeping: true,
	}
	sw.reindeerReady = sync.NewCond(&sw.reindeerMu)
	sw.elfReady = sync.NewCond(&sw.elfMu)
	sw.elfGetHelp = sync.NewCond(&sw.elfMu)
	return sw
}

// Santa's main loop
func (sw *SantaWorkshop) Santa() {
	for {
		fmt.Println("\n[Santa] 😴 Sleeping...")

		// Wait to be woken up
		reason := <-sw.santaWakeup

		sw.santaMu.Lock()
		sw.santaSleeping = false
		sw.santaMu.Unlock()

		switch reason {
		case "reindeer":
			fmt.Println("[Santa] 🎅 Woken by reindeer! Preparing sleigh...")
			sw.deliverToys()

		case "elves":
			fmt.Println("[Santa] 🎅 Woken by elves! Helping with problems...")
			sw.helpElves()
		}

		sw.santaMu.Lock()
		sw.santaSleeping = true
		sw.santaMu.Unlock()

		// Check if simulation is done
		select {
		case <-sw.santaDone:
			fmt.Println("\n[Santa] 🎄 Merry Christmas! Going on vacation...")
			return
		default:
		}
	}
}

func (sw *SantaWorkshop) deliverToys() {
	fmt.Println("[Santa] 🦌 Hitching up all 9 reindeer...")
	time.Sleep(200 * time.Millisecond)

	fmt.Println("[Santa] 🎁 Delivering toys around the world!")
	time.Sleep(500 * time.Millisecond)

	fmt.Println("[Santa] ✓ Toys delivered! Unhitching reindeer...")

	sw.statsmu.Lock()
	sw.deliveries++
	sw.statsmu.Unlock()

	// Release reindeer
	sw.reindeerMu.Lock()
	sw.reindeerWaiting = 0
	sw.reindeerReady.Broadcast()
	sw.reindeerMu.Unlock()
}

func (sw *SantaWorkshop) helpElves() {
	sw.elfMu.Lock()
	elves := make([]int, len(sw.elfGroup))
	copy(elves, sw.elfGroup)
	sw.elfMu.Unlock()

	fmt.Printf("[Santa] 🧝 Helping elves %v with their problems...\n", elves)
	time.Sleep(300 * time.Millisecond)

	fmt.Printf("[Santa] ✓ Helped elves %v!\n", elves)

	sw.statsmu.Lock()
	sw.elfSessions++
	for _, elfID := range elves {
		sw.elvesSolved[elfID]++
	}
	sw.statsmu.Unlock()

	// Release elves
	sw.elfMu.Lock()
	sw.elfGroup = nil
	sw.elfWaiting = 0
	sw.elfGetHelp.Broadcast()
	sw.elfMu.Unlock()
}

// Reindeer return from vacation
func (sw *SantaWorkshop) Reindeer(id int) {
	fmt.Printf("[Reindeer %d] 🦌 Returning from vacation...\n", id)

	sw.reindeerMu.Lock()
	sw.reindeerWaiting++

	if sw.reindeerWaiting == 9 {
		// All reindeer ready! Wake Santa
		fmt.Println("[Reindeer] 🔔 All 9 reindeer ready! Waking Santa...")

		// Priority: interrupt elves if needed
		select {
		case sw.santaWakeup <- "reindeer":
		default:
		}

		// Wait for Santa to finish
		for sw.reindeerWaiting > 0 {
			sw.reindeerReady.Wait()
		}

		sw.reindeerMu.Unlock()
		fmt.Printf("[Reindeer %d] ✓ Back on vacation!\n", id)
	} else {
		fmt.Printf("[Reindeer %d] Waiting (%d/9 here)\n", id, sw.reindeerWaiting)
		sw.reindeerMu.Unlock()
	}
}

// Elf needs help
func (sw *SantaWorkshop) Elf(id int, problems int) {
	for i := 0; i < problems; i++ {
		// Random delay before needing help
		time.Sleep(time.Duration(200+rand.Intn(300)) * time.Millisecond)

		fmt.Printf("[Elf %d] 🧝 Need help with problem %d!\n", id, i+1)

		sw.elfMu.Lock()

		// Wait if group is full or Santa is busy
		for len(sw.elfGroup) >= 3 {
			sw.elfReady.Wait()
		}

		// Join the group
		sw.elfGroup = append(sw.elfGroup, id)
		sw.elfWaiting++
		currentGroupSize := len(sw.elfGroup)

		fmt.Printf("[Elf %d] Joined group (%d/3)\n", id, currentGroupSize)

		if currentGroupSize == 3 {
			// Group full! Wake Santa
			fmt.Println("[Elves] 🔔 3 elves ready! Waking Santa...")

			sw.santaMu.Lock()
			sleeping := sw.santaSleeping
			sw.santaMu.Unlock()

			if sleeping {
				sw.santaWakeup <- "elves"
			}
		}

		// Wait for Santa to help
		for sw.elfWaiting > 0 {
			sw.elfGetHelp.Wait()
		}

		sw.elfMu.Unlock()
		fmt.Printf("[Elf %d] ✓ Got help from Santa!\n", id)
	}

	fmt.Printf("[Elf %d] 🎉 All problems solved!\n", id)
}

func main() {
	fmt.Println("=== Santa Claus Problem ===")
	fmt.Println("Coordinating elves and reindeer\n")

	workshop := NewSantaWorkshop()

	var wg sync.WaitGroup

	// Start Santa
	wg.Add(1)
	go func() {
		defer wg.Done()
		workshop.Santa()
	}()

	// Start elves (each has 2-3 problems)
	for i := 0; i < 10; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			problems := 2 + rand.Intn(2)
			workshop.Elf(id, problems)
		}(i)
	}

	// Start reindeer (return twice for 2 deliveries)
	for delivery := 0; delivery < 2; delivery++ {
		time.Sleep(time.Duration(2+delivery*3) * time.Second)

		for i := 0; i < 9; i++ {
			wg.Add(1)
			go func(id int) {
				defer wg.Done()
				workshop.Reindeer(id)
			}(i)
		}
	}

	// Wait for all elves to finish
	time.Sleep(8 * time.Second)
	close(workshop.santaDone)

	wg.Wait()

	// Print statistics
	workshop.statsmu.Lock()
	fmt.Println("\n📊 Workshop Statistics:")
	fmt.Printf("   Toy deliveries:   %d\n", workshop.deliveries)
	fmt.Printf("   Elf help sessions: %d\n", workshop.elfSessions)
	fmt.Println("   Problems solved per elf:")
	for id := 0; id < 10; id++ {
		fmt.Printf("      Elf %d: %d problems\n", id, workshop.elvesSolved[id])
	}
	workshop.statsmu.Unlock()

	fmt.Println("\n🎄 Merry Christmas! 🎄")
}

Key Synchronization Patterns

1. Group Formation

elfGroup = append(elfGroup, id)
if len(elfGroup) == 3 {
    // Wake Santa
}

Accumulate until threshold reached.

2. Priority Handling

// Reindeer always take priority
select {
case santaWakeup <- "reindeer":
default:
}

Reindeer can interrupt elf help.

3. Barrier Synchronization

// All wait for Santa to finish
for reindeerWaiting > 0 {
    reindeerReady.Wait()
}

Classic barrier pattern.

Alternative: Channel-Based Solution

Here’s a more Go-idiomatic approach using channels:

package main

import (
	"fmt"
	"time"
)

type ReindeerRequest struct {
	id   int
	done chan struct{}
}

type ElfRequest struct {
	id   int
	done chan struct{}
}

type ChannelWorkshop struct {
	reindeerQueue chan ReindeerRequest
	elfQueue      chan ElfRequest
	shutdown      chan struct{}
}

func NewChannelWorkshop() *ChannelWorkshop {
	return &ChannelWorkshop{
		reindeerQueue: make(chan ReindeerRequest, 9),
		elfQueue:      make(chan ElfRequest, 10),
		shutdown:      make(chan struct{}),
	}
}

func (cw *ChannelWorkshop) Santa() {
	var reindeerBatch []ReindeerRequest
	var elfBatch []ElfRequest

	for {
		select {
		case <-cw.shutdown:
			return

		case req := <-cw.reindeerQueue:
			reindeerBatch = append(reindeerBatch, req)

			if len(reindeerBatch) == 9 {
				fmt.Println("[Santa] 🎅 All reindeer ready! Delivering toys...")
				time.Sleep(500 * time.Millisecond)

				for _, r := range reindeerBatch {
					close(r.done)
				}
				reindeerBatch = nil
			}

		case req := <-cw.elfQueue:
			elfBatch = append(elfBatch, req)

			if len(elfBatch) == 3 {
				fmt.Printf("[Santa] 🎅 Helping elves %d, %d, %d\n",
					elfBatch[0].id, elfBatch[1].id, elfBatch[2].id)
				time.Sleep(300 * time.Millisecond)

				for _, e := range elfBatch {
					close(e.done)
				}
				elfBatch = nil
			}
		}
	}
}

func (cw *ChannelWorkshop) Reindeer(id int) {
	done := make(chan struct{})
	cw.reindeerQueue <- ReindeerRequest{id: id, done: done}
	<-done
}

func (cw *ChannelWorkshop) Elf(id int) {
	done := make(chan struct{})
	cw.elfQueue <- ElfRequest{id: id, done: done}
	<-done
}

Real-World Example: Batch Processing System

package main

import (
	"fmt"
	"sync"
	"time"
)

type Transaction struct {
	ID     int
	Amount float64
	Done   chan struct{}
}

type BatchProcessor struct {
	transactions []Transaction
	batchSize    int
	timeout      time.Duration
	mu           sync.Mutex
	cond         *sync.Cond
	processed    int
}

func NewBatchProcessor(batchSize int, timeout time.Duration) *BatchProcessor {
	bp := &BatchProcessor{
		batchSize: batchSize,
		timeout:   timeout,
	}
	bp.cond = sync.NewCond(&bp.mu)
	return bp
}

// Processor waits for batch or timeout
func (bp *BatchProcessor) Processor() {
	for {
		bp.mu.Lock()

		// Wait for batch size or timeout
		timer := time.AfterFunc(bp.timeout, func() {
			bp.mu.Lock()
			if len(bp.transactions) > 0 {
				bp.cond.Signal()
			}
			bp.mu.Unlock()
		})

		for len(bp.transactions) < bp.batchSize {
			bp.cond.Wait()
			// If woken up, check if we should process
			if len(bp.transactions) >= bp.batchSize {
				timer.Stop()
				break
			}
		}

		// Process batch
		batch := bp.transactions
		bp.transactions = nil
		bp.mu.Unlock()

		if len(batch) > 0 {
			bp.processBatch(batch)
		}
	}
}

func (bp *BatchProcessor) processBatch(batch []Transaction) {
	fmt.Printf("[Processor] Processing batch of %d transactions\n", len(batch))
	time.Sleep(200 * time.Millisecond)

	total := 0.0
	for _, txn := range batch {
		total += txn.Amount
		close(txn.Done)
	}

	bp.mu.Lock()
	bp.processed += len(batch)
	bp.mu.Unlock()

	fmt.Printf("[Processor] ✓ Batch complete: $%.2f total\n", total)
}

// Submit adds transaction to batch
func (bp *BatchProcessor) Submit(txn Transaction) {
	bp.mu.Lock()
	defer bp.mu.Unlock()

	bp.transactions = append(bp.transactions, txn)

	if len(bp.transactions) >= bp.batchSize {
		bp.cond.Signal()
	}
}

Advantages of This Pattern

✓ Efficient batching - Process groups together ✓ Priority handling - Critical tasks can interrupt ✓ Resource optimization - Santa helps multiple elves at once ✓ Clear coordination - Explicit group formation

When to Use

✓ Use when:

  • Operations are more efficient in batches
  • Need to coordinate groups
  • Have priority levels
  • Can wait for threshold or timeout

✗ Simpler solutions when:

  • Single-item processing is fine
  • No batching benefits
  • No priority needed
  • Immediate processing required

Try It Yourself

  1. Add timeouts - Elves give up if waiting too long
  2. Variable thresholds - 2-4 elves instead of exactly 3
  3. Add priorities - Urgent elf problems
  4. Track fairness - Ensure all elves get equal help
  5. Add cancellation - Elves can leave the queue

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