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:

Agent puts 2 random ingredients on the table
The smoker who has the 3rd ingredient can smoke
Agent waits for smoker to finish
Repeat

The Challenge

The tricky part: Smokers must deduce which combination is available. If the agent puts tobacco + paper, only the matches-holder can smoke!

Real-World Applications

This pattern appears in systems needing resource coordination:

Database transactions: Need specific combination of locks
Build systems: Jobs need specific resources (CPU + disk + network)
Cloud resource allocation: VMs need CPU + memory + disk
Task scheduling: Tasks require specific resource combinations
Dependency resolution: Components need multiple dependencies ready

Implementation in Go

package main

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

// Ingredient types
type Ingredient int

const (
	Tobacco Ingredient = iota
	Paper
	Matches
)

func (i Ingredient) String() string {
	return []string{"Tobacco", "Paper", "Matches"}[i]
}

// Smoker represents a smoker with one ingredient
type Smoker struct {
	id         int
	has        Ingredient
	smokesLeft int
}

func (s *Smoker) String() string {
	return fmt.Sprintf("Smoker %d (has %s)", s.id, s.has)
}

// CigaretteSmokersGame coordinates the game
type CigaretteSmokersGame struct {
	table      chan [2]Ingredient // What's on the table
	smokerDone chan struct{}      // Signal when smoker finishes
	smokers    []*Smoker
	mu         sync.Mutex
	stats      map[int]int // Tracks smokes per smoker
}

func NewGame() *CigaretteSmokersGame {
	game := &CigaretteSmokersGame{
		table:      make(chan [2]Ingredient),
		smokerDone: make(chan struct{}),
		smokers: []*Smoker{
			{id: 0, has: Tobacco, smokesLeft: 3},
			{id: 1, has: Paper, smokesLeft: 3},
			{id: 2, has: Matches, smokesLeft: 3},
		},
		stats: make(map[int]int),
	}
	return game
}

// Agent puts two ingredients on table
func (g *CigaretteSmokersGame) Agent() {
	ingredients := []Ingredient{Tobacco, Paper, Matches}

	for {
		// Check if all smokers are done
		allDone := true
		for _, smoker := range g.smokers {
			if smoker.smokesLeft > 0 {
				allDone = false
				break
			}
		}
		if allDone {
			close(g.table)
			return
		}

		// Pick 2 random ingredients
		perm := rand.Perm(3)
		pair := [2]Ingredient{ingredients[perm[0]], ingredients[perm[1]]}

		missing := ingredients[perm[2]]

		fmt.Printf("\n[Agent] 🎲 Placing %s + %s on table (missing: %s)\n",
			pair[0], pair[1], missing)

		// Put on table
		g.table <- pair

		// Wait for smoker to finish
		<-g.smokerDone

		time.Sleep(200 * time.Millisecond)
	}
}

// Smoker waits for their combination
func (g *CigaretteSmokersGame) SmokerProcess(smoker *Smoker) {
	for pair := range g.table {
		// Check if this combination is for me
		canSmoke := false

		// I can smoke if the table has the two ingredients I DON'T have
		switch smoker.has {
		case Tobacco:
			canSmoke = (pair[0] == Paper && pair[1] == Matches) ||
			           (pair[0] == Matches && pair[1] == Paper)
		case Paper:
			canSmoke = (pair[0] == Tobacco && pair[1] == Matches) ||
			           (pair[0] == Matches && pair[1] == Tobacco)
		case Matches:
			canSmoke = (pair[0] == Tobacco && pair[1] == Paper) ||
			           (pair[0] == Paper && pair[1] == Tobacco)
		}

		if canSmoke && smoker.smokesLeft > 0 {
			smoker.smokesLeft--

			fmt.Printf("[%s] 🚬 Smoking! (%d left)\n", smoker, smoker.smokesLeft)
			time.Sleep(300 * time.Millisecond)

			fmt.Printf("[%s] ✓ Done smoking\n", smoker)

			g.mu.Lock()
			g.stats[smoker.id]++
			g.mu.Unlock()

			// Signal done
			g.smokerDone <- struct{}{}
			break
		}
	}
}

func main() {
	fmt.Println("=== Cigarette Smokers Problem ===")
	fmt.Println("Resource matching synchronization\n")

	game := NewGame()

	var wg sync.WaitGroup

	// Start agent
	wg.Add(1)
	go func() {
		defer wg.Done()
		game.Agent()
	}()

	// Start smokers
	for _, smoker := range game.smokers {
		wg.Add(1)
		s := smoker // Capture
		go func() {
			defer wg.Done()
			for s.smokesLeft > 0 {
				game.SmokerProcess(s)
			}
			fmt.Printf("[%s] 🎉 Finished all cigarettes!\n", s)
		}()
	}

	wg.Wait()

	fmt.Println("\n📊 Final Statistics:")
	for id, count := range game.stats {
		fmt.Printf("   Smoker %d: %d cigarettes\n", id, count)
	}
	fmt.Println("\n✓ Game complete!")
}

Better Solution: Pusher Pattern

The naive solution above has a problem: all smokers read from the same channel, creating a race. The classic solution uses “pushers” - intermediaries that detect combinations.

package main

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

// PusherGame uses intermediaries to detect combinations
type PusherGame struct {
	tobaccoAvail chan struct{}
	paperAvail   chan struct{}
	matchesAvail chan struct{}

	tobaccoSmoker chan struct{}
	paperSmoker   chan struct{}
	matchesSmoker chan struct{}

	agentDone chan struct{}
}

func NewPusherGame() *PusherGame {
	return &PusherGame{
		tobaccoAvail:  make(chan struct{}, 1),
		paperAvail:    make(chan struct{}, 1),
		matchesAvail:  make(chan struct{}, 1),
		tobaccoSmoker: make(chan struct{}),
		paperSmoker:   make(chan struct{}),
		matchesSmoker: make(chan struct{}),
		agentDone:     make(chan struct{}),
	}
}

// Pushers detect combinations
func (g *PusherGame) TobaccoPusher() {
	for {
		<-g.tobaccoAvail
		select {
		case <-g.paperAvail:
			// Tobacco + Paper → signal matches smoker
			g.matchesSmoker <- struct{}{}
		case <-g.matchesAvail:
			// Tobacco + Matches → signal paper smoker
			g.paperSmoker <- struct{}{}
		}
	}
}

func (g *PusherGame) PaperPusher() {
	for {
		<-g.paperAvail
		select {
		case <-g.tobaccoAvail:
			// Paper + Tobacco → signal matches smoker
			g.matchesSmoker <- struct{}{}
		case <-g.matchesAvail:
			// Paper + Matches → signal tobacco smoker
			g.tobaccoSmoker <- struct{}{}
		}
	}
}

func (g *PusherGame) MatchesPusher() {
	for {
		<-g.matchesAvail
		select {
		case <-g.tobaccoAvail:
			// Matches + Tobacco → signal paper smoker
			g.paperSmoker <- struct{}{}
		case <-g.paperAvail:
			// Matches + Paper → signal tobacco smoker
			g.tobaccoSmoker <- struct{}{}
		}
	}
}

// Agent places ingredients
func (g *PusherGame) Agent(rounds int) {
	defer close(g.agentDone)

	ingredients := [][2]string{
		{"Tobacco", "Paper"},
		{"Tobacco", "Matches"},
		{"Paper", "Matches"},
	}

	for i := 0; i < rounds; i++ {
		choice := ingredients[i%3]
		fmt.Printf("\n[Agent] Placing %s + %s\n", choice[0], choice[1])

		// Signal available ingredients
		switch choice[0] + "+" + choice[1] {
		case "Tobacco+Paper":
			g.tobaccoAvail <- struct{}{}
			g.paperAvail <- struct{}{}
		case "Tobacco+Matches":
			g.tobaccoAvail <- struct{}{}
			g.matchesAvail <- struct{}{}
		case "Paper+Matches":
			g.paperAvail <- struct{}{}
			g.matchesAvail <- struct{}{}
		}

		time.Sleep(500 * time.Millisecond)
	}
}

// Smokers wait for their signal
func (g *PusherGame) Smoker(id int, has string, signal <-chan struct{}) {
	count := 0
	for range signal {
		count++
		fmt.Printf("[Smoker %d - has %s] 🚬 Smoking! (total: %d)\n", id, has, count)
		time.Sleep(200 * time.Millisecond)
	}
}

func RunPusherGame() {
	fmt.Println("\n=== Pusher Pattern Solution ===\n")

	game := NewPusherGame()

	// Start pushers
	go game.TobaccoPusher()
	go game.PaperPusher()
	go game.MatchesPusher()

	// Start smokers
	go game.Smoker(0, "Tobacco", game.tobaccoSmoker)
	go game.Smoker(1, "Paper", game.paperSmoker)
	go game.Smoker(2, "Matches", game.matchesSmoker)

	// Start agent
	go game.Agent(9)

	// Wait for completion
	<-game.agentDone
	time.Sleep(1 * time.Second)

	fmt.Println("\n✓ Pusher game complete!")
}

func main() {
	RunPusherGame()
}

State Machine Approach

Another elegant solution uses a state machine:

package main

import (
	"fmt"
	"sync"
)

type State struct {
	tobacco bool
	paper   bool
	matches bool
}

type StateMachineGame struct {
	state State
	mu    sync.Mutex
	cond  *sync.Cond

	tobaccoSmoker chan struct{}
	paperSmoker   chan struct{}
	matchesSmoker chan struct{}
}

func NewStateMachineGame() *StateMachineGame {
	g := &StateMachineGame{
		tobaccoSmoker: make(chan struct{}, 1),
		paperSmoker:   make(chan struct{}, 1),
		matchesSmoker: make(chan struct{}, 1),
	}
	g.cond = sync.NewCond(&g.mu)
	return g
}

func (g *StateMachineGame) AddIngredient(ing Ingredient) {
	g.mu.Lock()
	defer g.mu.Unlock()

	switch ing {
	case Tobacco:
		g.state.tobacco = true
	case Paper:
		g.state.paper = true
	case Matches:
		g.state.matches = true
	}

	// Check for complete combinations
	if g.state.paper && g.state.matches {
		g.state = State{} // Reset
		g.tobaccoSmoker <- struct{}{}
	} else if g.state.tobacco && g.state.matches {
		g.state = State{}
		g.paperSmoker <- struct{}{}
	} else if g.state.tobacco && g.state.paper {
		g.state = State{}
		g.matchesSmoker <- struct{}{}
	}
}

Real-World Example: Build System Resource Allocation

package main

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

type Resource int

const (
	CPU Resource = iota
	Memory
	Disk
)

func (r Resource) String() string {
	return []string{"CPU", "Memory", "Disk"}[r]
}

type BuildTask struct {
	id       int
	has      Resource // Resource task brings
	requires [2]Resource
}

type BuildSystem struct {
	available map[Resource]bool
	mu        sync.Mutex
	cond      *sync.Cond
	tasks     []*BuildTask
}

func NewBuildSystem() *BuildSystem {
	bs := &BuildSystem{
		available: make(map[Resource]bool),
		tasks: []*BuildTask{
			{id: 0, has: CPU, requires: [2]Resource{Memory, Disk}},
			{id: 1, has: Memory, requires: [2]Resource{CPU, Disk}},
			{id: 2, has: Disk, requires: [2]Resource{CPU, Memory}},
		},
	}
	bs.cond = sync.NewCond(&bs.mu)
	return bs
}

func (bs *BuildSystem) AllocateResources(r1, r2 Resource) {
	bs.mu.Lock()
	defer bs.mu.Unlock()

	bs.available[r1] = true
	bs.available[r2] = true

	fmt.Printf("[Allocator] Allocated %s + %s\n", r1, r2)

	bs.cond.Broadcast()
}

func (bs *BuildSystem) RunTask(task *BuildTask) {
	bs.mu.Lock()
	defer bs.mu.Unlock()

	// Wait for required resources
	for !(bs.available[task.requires[0]] && bs.available[task.requires[1]]) {
		bs.cond.Wait()
	}

	// Got resources
	fmt.Printf("[Task %d] 🔨 Building with %s + %s + %s\n",
		task.id, task.has, task.requires[0], task.requires[1])

	// Clear resources
	bs.available = make(map[Resource]bool)

	bs.mu.Unlock()
	time.Sleep(300 * time.Millisecond)
	bs.mu.Lock()

	fmt.Printf("[Task %d] ✓ Build complete\n", task.id)
}

Key Insights

Why Semaphores Alone Don’t Work

The problem requires detection of combinations, not just counting. You need to know:

What combination is present
Who can proceed

Semaphores can’t express “wait for A AND B simultaneously.”

The Pusher Solution

Pushers act as combination detectors:

Monitor ingredient channels
Detect valid combinations
Signal appropriate smoker

This is a classic example of active agents vs passive synchronization.

When to Use This Pattern

✓ Use when:

Tasks require specific resource combinations
Resources come from different sources
Need to match complementary items
Coordination is complex

✗ Simpler solutions when:

Resources are independent
No combination matching needed
Simple counting suffices

Try It Yourself

Add more smokers - 4+ smokers with different ingredient sets
Add priorities - Some smokers get preference
Add timeouts - Smokers give up if waiting too long
Track fairness - Ensure even distribution
Add resource types - More than 3 ingredients

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

The Cigarette Smokers Problem#

The Scenario#

The Challenge#

Real-World Applications#

Implementation in Go#

Better Solution: Pusher Pattern#

State Machine Approach#

Real-World Example: Build System Resource Allocation#

Key Insights#

Why Semaphores Alone Don’t Work#

The Pusher Solution#

When to Use This Pattern#

Try It Yourself#