Operating SystemsSemaphores & Classic Problems

Other Classic Synchronization Problems

LevelIntermediate

Duration90 mins

TopicSemaphores & Classic Problems

2 / 5

The Cigarette Smokers Problem

Three Smokers, One Agent, and the Challenge of Resource Matching

Consider this scenario: three smokers sit at a table, each with an infinite supply of one of three ingredients needed to make and smoke a cigarette. One smoker has tobacco, another has paper, and the third has matches. An agent repeatedly places two random ingredients on the table. The smoker who possesses the third ingredient takes the two on the table, makes a cigarette, and smokes it. The process then repeats.

Introduced by Suhas Patil in 1971, the Cigarette Smokers Problem is deceptively simple to state but remarkably difficult to solve with semaphores alone. In fact, Patil designed it specifically to demonstrate limitations of the semaphore abstraction—showing that some synchronization patterns cannot be expressed cleanly with basic semaphores.

This problem models real-world scenarios where processes wait for specific combinations of resources rather than individual resources—matching problems in resource allocation, workflow coordination, and distributed systems.

Learning Objectives

By the end of this page, you will:

• Understand why the Cigarette Smokers Problem is fundamentally different from producer-consumer patterns • Recognize why naive semaphore solutions fail • Learn the "pusher" pattern that enables correct semaphore-based solutions • Analyze the theoretical significance: what this problem reveals about semaphore limitations • Connect the pattern to real-world resource matching and workflow systems

Formal Problem Statement

The Scenario:

Three ingredients are required to make and smoke a cigarette:

Tobacco (T)
Paper (P)
Matches (M)

Three smoker processes exist:

Smoker A: Has infinite tobacco, needs paper and matches
Smoker B: Has infinite paper, needs tobacco and matches
Smoker C: Has infinite matches, needs tobacco and paper

One agent process repeatedly:

Chooses two of the three ingredients randomly
Places them on the table
Waits until the smoker who needs those items finishes smoking
Repeats

Constraint: The agent process cannot be modified. It simply places two ingredients and signals. The solution must coordinate the smokers correctly.

Resource Matching Matrix
Agent Places	Smoker with Missing Resource	That Smoker Has	Creates Complete Set?
Tobacco + Paper	Smoker C (has matches)	Matches	✓ Yes: T + P + M
Tobacco + Matches	Smoker B (has paper)	Paper	✓ Yes: T + M + P
Paper + Matches	Smoker A (has tobacco)	Tobacco	✓ Yes: P + M + T

Correctness Requirements:

Safety:

Only one smoker smokes at a time
A smoker only smokes when they have all three ingredients
Items placed by the agent are consumed exactly once

Liveness:

When the agent places items, the correct smoker eventually smokes
No deadlock: the system makes progress indefinitely
No starvation: if a smoker's items appear, they eventually smoke

The Key Challenge:

Unlike simple producer-consumer, the smokers cannot simply wait for "any two items." Each smoker needs a specific pair. The matching logic—determining which smoker should wake up—is the crux of the problem.

The Fundamental Difficulty

The agent uses three different signals (e.g., three different semaphore posts) to indicate which pair of ingredients was placed. But a smoker needs to determine from two signals that their specific pair is present. This conditional wakeup based on a combination is what makes the problem hard with basic semaphores.

Why Naive Semaphore Solutions Fail

Let's examine why straightforward semaphore approaches don't work. This analysis reveals the core difficulty.

Naive Approach 1: One Semaphore Per Ingredient

The obvious first idea: have the agent signal a semaphore for each ingredient placed. Each smoker waits on the two semaphores for the ingredients they need.

naive_per_ingredient.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// BROKEN: Naive per-ingredient semaphore approach
 
sem_t tobacco;   // Signaled when tobacco is placed
sem_t paper;     // Signaled when paper is placed
sem_t matches;   // Signaled when matches is placed
 
// Smoker A has tobacco, needs paper + matches
void* smoker_a(void* arg) {
    while (1) {
        sem_wait(&paper);    // Wait for paper
        sem_wait(&matches);  // Wait for matches
        
        make_cigarette();
        smoke();
        
        signal_agent_done();
    }
}
 
// Smoker B has paper, needs tobacco + matches
void* smoker_b(void* arg) {
    while (1) {
        sem_wait(&tobacco);  // Wait for tobacco
        sem_wait(&matches);  // Wait for matches
        
        make_cigarette();
        smoke();
        
        signal_agent_done();
    }
}
 
// Agent places two ingredients
void* agent(void* arg) {
    while (1) {
        int choice = random() % 3;
        
        switch (choice) {
            case 0:  // Place tobacco + paper
                sem_post(&tobacco);
                sem_post(&paper);
                break;
            case 1:  // Place tobacco + matches
                sem_post(&tobacco);
                sem_post(&matches);
                break;
            case 2:  // Place paper + matches
                sem_post(&paper);
                sem_post(&matches);
                break;
        }
        
        wait_for_smoker();
    }
}

Deadlock Scenario

When agent places tobacco + paper (Smoker C should smoke):

Agent posts tobacco, then posts paper
Smoker A wakes on paper (was waiting for paper+matches)
Smoker A blocks on matches (which wasn't placed!)
Smoker B wakes on tobacco (was waiting for tobacco+matches)
Smoker B blocks on matches (same issue!)
Smoker C (who needs tobacco+paper) never got a signal
DEADLOCK: A and B are blocked waiting for matches that don't exist

The fundamental problem is that semaphores don't support conditional waits on combinations. Each smoker needs to wait for a specific pair, but sem_wait only waits for a single semaphore. When multiple smokers compete for the same ingredient signal, the wrong smoker can grab it.

Naive Approach 2: Per-Smoker Semaphores

The agent could directly signal the appropriate smoker:

naive_per_smoker.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// This works, but violates the problem constraints
 
sem_t smoker_a_can_go;  // Signal smoker A (has tobacco)
sem_t smoker_b_can_go;  // Signal smoker B (has paper)
sem_t smoker_c_can_go;  // Signal smoker C (has matches)
 
void* agent(void* arg) {
    while (1) {
        int choice = random() % 3;
        
        switch (choice) {
            case 0:  // Place tobacco + paper → smoker C needs matches
                sem_post(&smoker_c_can_go);
                break;
            case 1:  // Place tobacco + matches → smoker B needs paper
                sem_post(&smoker_b_can_go);
                break;
            case 2:  // Place paper + matches → smoker A needs tobacco
                sem_post(&smoker_a_can_go);
                break;
        }
        
        wait_for_smoker();
    }
}
 
void* smoker_a(void* arg) {
    while (1) {
        sem_wait(&smoker_a_can_go);
        make_cigarette();
        smoke();
        signal_agent_done();
    }
}
 
// This WORKS but is considered "cheating" - the agent knows
// which smoker to signal. The problem requires the matching
// logic to be in the smoker/pusher code, not the agent.

This solution works but violates the problem constraints: the agent must be unaware of which smoker needs which ingredients. The agent only knows which ingredients it placed, not which smoker should respond.

Why This Matters:

In real systems, the "agent" is often hardware or a fixed protocol that cannot embed application-specific logic. For example:

A network interface that receives packets with certain header combinations
A hardware interrupt controller signaling device events
A database trigger that fires on certain column updates

The matching logic must be in the consumer (smoker) side, not the producer (agent) side.

The Pusher Pattern Solution

The correct solution introduces pusher threads that act as intermediaries. Pushers observe which ingredients are placed and, when they detect a complete pair, signal the appropriate smoker.

Key Insight:

We separate the problem into two stages:

Stage 1: Track which ingredients are currently on the table
Stage 2: When a combination is complete, signal the right smoker

Pushers provide the "conditional logic" that basic semaphores lack. Each ingredient has a pusher that:

Wakes when that ingredient is placed
Checks if the complementary ingredient is already present
If yes: signals the appropriate smoker
If no: records that this ingredient is now waiting

pusher_solution.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
/*
 * The Cigarette Smokers Problem - Pusher Pattern Solution
 * 
 * The key insight: introduce "pusher" threads that observe
 * individual ingredient signals and track state to determine
 * when a complete pair exists for a specific smoker.
 */
 
#include <semaphore.h>
#include <pthread.h>
#include <stdio.h>
#include <stdbool.h>
 
/*
 * Agent's semaphores - one per ingredient
 * These are signaled by the agent when it places ingredients.
 */
sem_t tobacco_on_table;
sem_t paper_on_table;
sem_t matches_on_table;
 
/*
 * Smoker semaphores - signaled when their pair is complete
 */
sem_t smoker_with_tobacco;   // Needs paper + matches
sem_t smoker_with_paper;     // Needs tobacco + matches
sem_t smoker_with_matches;   // Needs tobacco + paper
 
/*
 * Agent synchronization
 */
sem_t agent_ready;
 
/*
 * Shared state: tracks what's currently on the table
 * Protected by mutex
 */
pthread_mutex_t table_mutex = PTHREAD_MUTEX_INITIALIZER;
bool has_tobacco = false;
bool has_paper = false;
bool has_matches = false;
 
/* ============================================
 * PUSHER THREADS
 * ============================================
 * Each pusher wakes when its ingredient arrives,
 * checks if a complement is present, and signals
 * the appropriate smoker if so.
 */
 
void* tobacco_pusher(void* arg) {
    while (1) {
        // Wait for tobacco to be placed
        sem_wait(&tobacco_on_table);
        
        pthread_mutex_lock(&table_mutex);
        
        if (has_paper) {
            // Tobacco + Paper on table → Smoker with matches can smoke
            has_paper = false;  // Consume the paper
            sem_post(&smoker_with_matches);
        } else if (has_matches) {
            // Tobacco + Matches on table → Smoker with paper can smoke
            has_matches = false;  // Consume the matches
            sem_post(&smoker_with_paper);
        } else {
            // Neither complement present yet - record tobacco and wait
            has_tobacco = true;
        }
        
        pthread_mutex_unlock(&table_mutex);
    }
    return NULL;
}
 
void* paper_pusher(void* arg) {
    while (1) {
        sem_wait(&paper_on_table);
        
        pthread_mutex_lock(&table_mutex);
        
        if (has_tobacco) {
            // Paper + Tobacco on table → Smoker with matches can smoke
            has_tobacco = false;
            sem_post(&smoker_with_matches);
        } else if (has_matches) {
            // Paper + Matches on table → Smoker with tobacco can smoke
            has_matches = false;
            sem_post(&smoker_with_tobacco);
        } else {
            // Record paper and wait
            has_paper = true;
        }
        
        pthread_mutex_unlock(&table_mutex);
    }
    return NULL;
}
 
void* matches_pusher(void* arg) {
    while (1) {
        sem_wait(&matches_on_table);
        
        pthread_mutex_lock(&table_mutex);
        
        if (has_tobacco) {
            // Matches + Tobacco on table → Smoker with paper can smoke
            has_tobacco = false;
            sem_post(&smoker_with_paper);
        } else if (has_paper) {
            // Matches + Paper on table → Smoker with tobacco can smoke
            has_paper = false;
            sem_post(&smoker_with_tobacco);
        } else {
            // Record matches and wait
            has_matches = true;
        }
        
        pthread_mutex_unlock(&table_mutex);
    }
    return NULL;
}
 
/* ============================================
 * SMOKER THREADS
 * ============================================
 * Each smoker waits on their personal semaphore,
 * which is signaled by a pusher when their pair
 * is complete.
 */
 
void* smoker_with_tobacco_thread(void* arg) {
    while (1) {
        sem_wait(&smoker_with_tobacco);
        
        printf("Smoker with tobacco: making cigarette...\n");
        make_cigarette();
        
        sem_post(&agent_ready);  // Signal agent can place more
        
        printf("Smoker with tobacco: smoking...\n");
        smoke();
    }
    return NULL;
}
 
void* smoker_with_paper_thread(void* arg) {
    while (1) {
        sem_wait(&smoker_with_paper);
        
        printf("Smoker with paper: making cigarette...\n");
        make_cigarette();
        
        sem_post(&agent_ready);
        
        printf("Smoker with paper: smoking...\n");
        smoke();
    }
    return NULL;
}
 
void* smoker_with_matches_thread(void* arg) {
    while (1) {
        sem_wait(&smoker_with_matches);
        
        printf("Smoker with matches: making cigarette...\n");
        make_cigarette();
        
        sem_post(&agent_ready);
        
        printf("Smoker with matches: smoking...\n");
        smoke();
    }
    return NULL;
}
 
/* ============================================
 * AGENT THREAD
 * ============================================
 * Randomly places two ingredients, then waits.
 * This code is "fixed" - cannot be modified
 * per problem constraints.
 */
 
void* agent_thread(void* arg) {
    while (1) {
        sem_wait(&agent_ready);
        
        int choice = random() % 3;
        
        switch (choice) {
            case 0:  // Place tobacco + paper
                printf("Agent: placing tobacco and paper\n");
                sem_post(&tobacco_on_table);
                sem_post(&paper_on_table);
                break;
            case 1:  // Place tobacco + matches
                printf("Agent: placing tobacco and matches\n");
                sem_post(&tobacco_on_table);
                sem_post(&matches_on_table);
                break;
            case 2:  // Place paper + matches
                printf("Agent: placing paper and matches\n");
                sem_post(&paper_on_table);
                sem_post(&matches_on_table);
                break;
        }
    }
    return NULL;
}
 
/* ============================================
 * MAIN - INITIALIZATION
 * ============================================ */
int main() {
    // Initialize ingredient semaphores (start at 0)
    sem_init(&tobacco_on_table, 0, 0);
    sem_init(&paper_on_table, 0, 0);
    sem_init(&matches_on_table, 0, 0);
    
    // Initialize smoker semaphores (start at 0)
    sem_init(&smoker_with_tobacco, 0, 0);
    sem_init(&smoker_with_paper, 0, 0);
    sem_init(&smoker_with_matches, 0, 0);
    
    // Agent can start immediately
    sem_init(&agent_ready, 0, 1);
    
    // Create threads
    pthread_t pushers[3], smokers[3], agent;
    
    pthread_create(&pushers[0], NULL, tobacco_pusher, NULL);
    pthread_create(&pushers[1], NULL, paper_pusher, NULL);
    pthread_create(&pushers[2], NULL, matches_pusher, NULL);
    
    pthread_create(&smokers[0], NULL, smoker_with_tobacco_thread, NULL);
    pthread_create(&smokers[1], NULL, smoker_with_paper_thread, NULL);
    pthread_create(&smokers[2], NULL, smoker_with_matches_thread, NULL);
    
    pthread_create(&agent, NULL, agent_thread, NULL);
    
    // Run forever
    pthread_join(agent, NULL);
    
    return 0;
}

Why Pushers Solve the Problem

The pushers provide conditional logic that semaphores lack:

• Each pusher tracks whether its ingredient arrived first or second • When an ingredient finds its complement already present, the pusher knows which pair is complete • The pusher then signals the specific smoker who needs that pair • This moves the matching logic from the agent to the middleware layer

Key invariant: At any time, at most one boolean (has_tobacco, has_paper, has_matches) is true, because the agent places exactly two ingredients.

Correctness Analysis

Let's rigorously verify the pusher solution's correctness.

Property 1: Mutual Exclusion

Claim: Only one smoker smokes at a time.

Proof:

The agent waits on agent_ready before placing ingredients
agent_ready starts at 1, allowing one placement
After a smoker finishes making a cigarette, they post agent_ready
Therefore, at most one ingredient pair is on the table at any time
Only one smoker can be signaled per pair
Thus, only one smoker smokes at a time ∎

Property 2: Correct Smoker Selection

Claim: When the agent places ingredients X and Y, the smoker with ingredient Z (where Z is the missing one) is signaled.

Proof by case analysis:

Case: Agent places tobacco + paper

tobacco_on_table and paper_on_table are posted
Suppose tobacco pusher runs first:
- Checks has_paper (false) and has_matches (false)
- Sets has_tobacco = true
Then paper pusher runs:
- Checks has_tobacco (true!)
- Sets has_tobacco = false
- Posts smoker_with_matches

Alternatively, if paper pusher runs first:

Sets has_paper = true
Tobacco pusher runs:
- Checks has_paper (true!)
- Sets has_paper = false
- Posts smoker_with_matches

Either way, smoker_with_matches is signaled ✓

Symmetric analysis applies to other cases. ∎

Complete Case Analysis
Agent Places	First Pusher	Sets	Second Pusher	Signals
T + P	tobacco_pusher	has_tobacco = true	paper_pusher	smoker_with_matches
T + P	paper_pusher	has_paper = true	tobacco_pusher	smoker_with_matches
T + M	tobacco_pusher	has_tobacco = true	matches_pusher	smoker_with_paper
T + M	matches_pusher	has_matches = true	tobacco_pusher	smoker_with_paper
P + M	paper_pusher	has_paper = true	matches_pusher	smoker_with_tobacco
P + M	matches_pusher	has_matches = true	paper_pusher	smoker_with_tobacco

Property 3: No Deadlock

Claim: The system never reaches a state where all threads are blocked forever.

Proof:

Initially, agent_ready = 1, so agent can run
Agent posts to two ingredient semaphores, waking two pushers
One pusher (the second to check) finds the complement and signals a smoker
The smoker runs, posts agent_ready, and the cycle continues
No circular wait is possible because information flows unidirectionally: Agent → Ingredient semaphores → Pushers → Smoker semaphores → Smokers → agent_ready ∎

Key Invariant

At any point between complete agent placements: exactly zero or one of (has_tobacco, has_paper, has_matches) is true. This holds because:

Initially all are false
Agent places exactly two ingredients
First pusher sets one to true
Second pusher finds it true, sets it false, and signals smoker
Smoker signals agent, resetting for next round

Theoretical Significance: Limitations of Semaphores

Patil designed the Cigarette Smokers Problem specifically to expose a limitation of the semaphore abstraction. Understanding this deepens appreciation for why monitors and other synchronization primitives exist.

The Core Limitation:

Semaphores excel at:

Signaling between processes
Counting resources
Enforcing mutual exclusion

But semaphores struggle with conditional synchronization based on multiple conditions—waiting until a combination of states is true.

Why Can't Smokers Just Wait on Two Semaphores?

The naive approach has smokers wait on two semaphores (for their two missing ingredients). The problem is that sem_wait is atomic but doesn't support atomic wait on multiple semaphores simultaneously.

atomic_wait_problem.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// What we WANT (but semaphores don't support):
wait_for_all(paper, matches);  // Atomic wait for BOTH
 
// What semaphores give us:
sem_wait(&paper);   // Might succeed
sem_wait(&matches); // Might block forever if matches not there
 
// The problem: after getting paper, if matches isn't there,
// we're stuck holding paper. Meanwhile, another smoker
// might need paper but we've taken it.
 
// This is analogous to the "two-army problem" in atomicity:
// We can't atomically acquire two resources when we don't
// control both resource's timing.

What the Pusher Pattern Actually Demonstrates:

The pusher pattern shows that we can work around the limitation by:

Introducing an intermediate coordination layer
Using shared state (the boolean flags) to track partial progress
Having the coordinator (pusher) make decisions and signal the right consumer

But this feels like we're compensating for a missing primitive—and we are. Monitors with condition variables handle this more naturally:

monitor_solution_sketch.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// With monitors, the solution is more direct:
 
monitor CigaretteSmokers {
    condition can_smoke[3];  // One per smoker
    int placed[3] = {0, 0, 0};  // Count of each ingredient on table
    
    procedure agent_places(ingredients) {
        for each i in ingredients:
            placed[i]++;
        
        // Wake appropriate smoker based on what's there
        if (placed[PAPER] > 0 && placed[MATCHES] > 0)
            signal(can_smoke[TOBACCO_SMOKER]);
        else if (placed[TOBACCO] > 0 && placed[MATCHES] > 0)
            signal(can_smoke[PAPER_SMOKER]);
        else if (placed[TOBACCO] > 0 && placed[PAPER] > 0)
            signal(can_smoke[MATCHES_SMOKER]);
    }
    
    procedure smoker_takes(smoker_id, ingredient1, ingredient2) {
        while (placed[ingredient1] == 0 || placed[ingredient2] == 0)
            wait(can_smoke[smoker_id]);
        
        placed[ingredient1]--;
        placed[ingredient2]--;
    }
}
 
// Note: This still has conditional logic, but the monitor's
// encapsulation and condition variables make it cleaner.
// We still need to know which smoker to signal - that's
// fundamental to the problem, not an artifact of the solution.

Broader Lesson

The Cigarette Smokers Problem teaches a meta-lesson:

Different synchronization primitives have different expressive power. Semaphores are powerful but not universal. When you find yourself building elaborate workarounds (like pushers), consider whether a different primitive (monitors, channels, actor model) might express the solution more directly.

In practice, choose the abstraction that matches your problem's natural structure.

Real-World Applications and Patterns

Despite its abstract formulation, the Cigarette Smokers pattern appears in real systems:

1. Workflow Engines with Parallel Dependencies

In workflow systems, a task might require multiple asynchronous inputs before executing:

A report generation task needs data from both Database A and API B
A build task needs both compilation to succeed and tests to pass
An approval process needs sign-off from both Legal and Finance

The "pusher" pattern translates to a join node in workflow engines that collects required inputs and triggers the downstream task only when all are ready.

Event-Driven Architecture

•Events = Ingredients
•Event handlers = Pushers
•Aggregate state = Table state (booleans)
•Complex event = Complete pair
•Action trigger = Signaling smoker

Hardware Interrupt Handling

•Interrupt signals = Ingredients
•Interrupt handlers = Pushers
•Device state = Table state
•Ready condition = Both signals received
•Device driver = Smoker

2. Complex Event Processing (CEP)

CEP systems detect patterns across event streams. The Cigarette Smokers pattern represents conjunction patterns:

Detect when Event A AND Event B occur within a time window
Only trigger the downstream action when both are present
Track partial matches (one event but not the other)

Pushers are analogous to event correlators in CEP engines that track partial matches and trigger downstream logic when complete.

3. Resource Matching in Scheduling

In some scheduling problems, a job requires multiple resources of specific types:

A video rendering job needs both a GPU and fast storage
A database query needs both a read replica and a cache hit
A network request needs both outgoing bandwidth and a connection slot

The coordinator must match available resources and dispatch jobs when complete resource sets are available.

workflow_engine_example.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
"""
Workflow Engine Join Node - Cigarette Smokers Pattern
 
This models a workflow task that requires multiple async inputs.
The JoinNode acts as a "pusher" - collecting inputs and triggering
the downstream task when all required inputs are present.
"""
 
from typing import Dict, Set, Callable
import threading
 
class JoinNode:
    """
    Collects multiple asynchronous inputs and triggers action
    when all required inputs are present.
    """
    
    def __init__(self, required_inputs: Set[str], action: Callable):
        self.required = required_inputs
        self.action = action
        self.received: Dict[str, any] = {}
        self.lock = threading.Lock()
        self.completed = threading.Event()
    
    def receive(self, input_name: str, value: any):
        """Called when an upstream task completes."""
        with self.lock:
            if input_name not in self.required:
                return  # Ignore unexpected inputs
            
            self.received[input_name] = value
            
            # Check if all inputs present (pusher logic)
            if set(self.received.keys()) == self.required:
                # All inputs present - trigger action (signal smoker)
                self._trigger()
    
    def _trigger(self):
        """Execute the downstream task with collected inputs."""
        self.action(self.received)
        self.received.clear()  # Reset for next execution
        self.completed.set()
 
# Usage example:
def generate_report(inputs):
    db_data = inputs["database_query"]
    api_data = inputs["api_response"]
    print(f"Generating report with DB:{db_data}, API:{api_data}")
 
join = JoinNode({"database_query", "api_response"}, generate_report)
 
# Async inputs arrive...
join.receive("database_query", {"users": 1000})  # First input
join.receive("api_response", {"weather": "sunny"})  # Second input triggers action

Pattern Recognition

When you see these characteristics, think Cigarette Smokers:

• Multiple independent event sources • Consumer needs a specific combination of events • Events arrive asynchronously in any order • Action should trigger only when complete combination exists

The solution is always some form of coordinator/aggregator that tracks partial state.

Variations and Extensions

Several variations of the Cigarette Smokers Problem explore additional complexities:

1. Multiple Agents

What if multiple agents can place ingredients simultaneously? This introduces additional race conditions:

Two agents might each place tobacco + one other, creating two tobaccos on the table
The matching logic must handle arbitrary counts, not just presence/absence
Fairness becomes an issue: which smoker gets precedence if multiple can smoke?

2. Non-Exclusive Smoking

In the original problem, only one smoker smokes at a time. A relaxed variant allows concurrent smoking:

Multiple ingredient pairs might be on the table
Multiple smokers can smoke simultaneously if resources permit
Maximizing throughput becomes an optimization goal

3. Generalized to N Ingredients and M Smokers

With more ingredients and smokers, the combinatorics explode:

Each smoker might need a unique subset of K ingredients (from N total)
Matching becomes more complex as subsets can overlap
This models real resource allocation with multiple resource types

generalized_matching.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
"""
Generalized Cigarette Smokers: N ingredients, M consumers
 
Each consumer has a set of "owned" ingredients and needs
all other ingredients to proceed.
"""
 
from typing import Set, List, Dict
import threading
 
class GeneralizedMatcher:
    def __init__(self, ingredient_sets: Dict[str, Set[str]], 
                 all_ingredients: Set[str]):
        """
        ingredient_sets: maps consumer ID to ingredients they OWN
        all_ingredients: complete set of all ingredients
        
        Each consumer NEEDS: all_ingredients - their_owned_set
        """
        self.consumers = {
            consumer_id: all_ingredients - owned
            for consumer_id, owned in ingredient_sets.items()
        }
        
        self.on_table: Set[str] = set()
        self.lock = threading.Lock()
        self.consumer_signals = {
            cid: threading.Semaphore(0) 
            for cid in self.consumers
        }
    
    def place_ingredients(self, ingredients: Set[str]):
        """Agent places a set of ingredients."""
        with self.lock:
            self.on_table.update(ingredients)
            
            # Check each consumer
            for consumer_id, needed in self.consumers.items():
                if needed.issubset(self.on_table):
                    # This consumer can proceed
                    self.on_table -= needed  # Consume ingredients
                    self.consumer_signals[consumer_id].release()
                    return  # Only one consumer per placement
    
    def wait_and_consume(self, consumer_id: str):
        """Consumer waits until their ingredients are ready."""
        self.consumer_signals[consumer_id].acquire()
        # Consumer has now obtained their ingredients

4. Timed Ingredients (Expiration)

In real systems, resources might expire or become stale:

Ingredients placed on the table might "spoil" after a timeout
Smokers must act within a window or the opportunity is lost
This models cache expiration, session timeouts, and resource leases

5. Priority-Based Matching

Some smokers might have higher priority:

When multiple smokers could potentially use available ingredients
High-priority smoker should be signaled first
This models priority-based resource allocation and scheduling

Design Insight

Each variation teaches something about real systems:

• Multiple agents → Concurrent producers, need stronger serialization • Non-exclusive → Throughput optimization under resource constraints • Generalized matching → Complex resource allocation problems • Timed resources → Dealing with real-time constraints and expiration • Priority matching → Fairness vs. efficiency tradeoffs

Summary and Key Takeaways

The Cigarette Smokers Problem reveals deep truths about synchronization primitives and their limitations. Let's consolidate the key lessons:

Key Takeaways

•Semaphores can't atomically wait on combinations: A thread can wait on one semaphore or acquire multiple sequentially, but not atomically wait for a condition involving multiple resources
•The pusher pattern fills the gap: Intermediate coordinators that track partial state and signal consumers when complete combinations exist
•Matching logic must exist somewhere: Whether in the producer, consumer, or middleware—someone must determine which consumer gets which resources
•Different primitives have different strengths: Monitors with condition variables express this pattern more naturally, though the matching logic remains necessary
•Real systems face this constantly: Workflow engines, CEP systems, resource schedulers all implement variations of this pattern
•The problem is designed to teach: Patil created it specifically to show semaphore limitations—understanding why it's hard is as important as solving it

Page Complete

You now understand the Cigarette Smokers Problem—one of the most instructive synchronization problems ever designed. Its value lies not just in the solution, but in revealing why the problem is hard in the first place. Next, we explore Bounded Buffer Variations, where we'll see how the basic producer-consumer pattern extends to handle more complex requirements.

2 / 5

Loading learning content...

Operating SystemsSemaphores & Classic Problems

Other Classic Synchronization Problems

LevelIntermediate

Duration90 mins

TopicSemaphores & Classic Problems

2 / 5

The Cigarette Smokers Problem

Three Smokers, One Agent, and the Challenge of Resource Matching

Learning Objectives

By the end of this page, you will:

Formal Problem Statement

The Scenario:

Three ingredients are required to make and smoke a cigarette:

Tobacco (T)
Paper (P)
Matches (M)

Three smoker processes exist:

Smoker A: Has infinite tobacco, needs paper and matches
Smoker B: Has infinite paper, needs tobacco and matches
Smoker C: Has infinite matches, needs tobacco and paper

One agent process repeatedly:

Chooses two of the three ingredients randomly
Places them on the table
Waits until the smoker who needs those items finishes smoking
Repeats

Constraint: The agent process cannot be modified. It simply places two ingredients and signals. The solution must coordinate the smokers correctly.

Resource Matching Matrix
Agent Places	Smoker with Missing Resource	That Smoker Has	Creates Complete Set?
Tobacco + Paper	Smoker C (has matches)	Matches	✓ Yes: T + P + M
Tobacco + Matches	Smoker B (has paper)	Paper	✓ Yes: T + M + P
Paper + Matches	Smoker A (has tobacco)	Tobacco	✓ Yes: P + M + T

Correctness Requirements:

Safety:

Only one smoker smokes at a time
A smoker only smokes when they have all three ingredients
Items placed by the agent are consumed exactly once

Liveness:

When the agent places items, the correct smoker eventually smokes
No deadlock: the system makes progress indefinitely
No starvation: if a smoker's items appear, they eventually smoke

The Key Challenge:

The Fundamental Difficulty

Why Naive Semaphore Solutions Fail

Let's examine why straightforward semaphore approaches don't work. This analysis reveals the core difficulty.

Naive Approach 1: One Semaphore Per Ingredient

The obvious first idea: have the agent signal a semaphore for each ingredient placed. Each smoker waits on the two semaphores for the ingredients they need.

naive_per_ingredient.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// BROKEN: Naive per-ingredient semaphore approach
 
sem_t tobacco;   // Signaled when tobacco is placed
sem_t paper;     // Signaled when paper is placed
sem_t matches;   // Signaled when matches is placed
 
// Smoker A has tobacco, needs paper + matches
void* smoker_a(void* arg) {
    while (1) {
        sem_wait(&paper);    // Wait for paper
        sem_wait(&matches);  // Wait for matches
        
        make_cigarette();
        smoke();
        
        signal_agent_done();
    }
}
 
// Smoker B has paper, needs tobacco + matches
void* smoker_b(void* arg) {
    while (1) {
        sem_wait(&tobacco);  // Wait for tobacco
        sem_wait(&matches);  // Wait for matches
        
        make_cigarette();
        smoke();
        
        signal_agent_done();
    }
}
 
// Agent places two ingredients
void* agent(void* arg) {
    while (1) {
        int choice = random() % 3;
        
        switch (choice) {
            case 0:  // Place tobacco + paper
                sem_post(&tobacco);
                sem_post(&paper);
                break;
            case 1:  // Place tobacco + matches
                sem_post(&tobacco);
                sem_post(&matches);
                break;
            case 2:  // Place paper + matches
                sem_post(&paper);
                sem_post(&matches);
                break;
        }
        
        wait_for_smoker();
    }
}

Deadlock Scenario

When agent places tobacco + paper (Smoker C should smoke):

Agent posts tobacco, then posts paper
Smoker A wakes on paper (was waiting for paper+matches)
Smoker A blocks on matches (which wasn't placed!)
Smoker B wakes on tobacco (was waiting for tobacco+matches)
Smoker B blocks on matches (same issue!)
Smoker C (who needs tobacco+paper) never got a signal
DEADLOCK: A and B are blocked waiting for matches that don't exist

Naive Approach 2: Per-Smoker Semaphores

The agent could directly signal the appropriate smoker:

naive_per_smoker.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// This works, but violates the problem constraints
 
sem_t smoker_a_can_go;  // Signal smoker A (has tobacco)
sem_t smoker_b_can_go;  // Signal smoker B (has paper)
sem_t smoker_c_can_go;  // Signal smoker C (has matches)
 
void* agent(void* arg) {
    while (1) {
        int choice = random() % 3;
        
        switch (choice) {
            case 0:  // Place tobacco + paper → smoker C needs matches
                sem_post(&smoker_c_can_go);
                break;
            case 1:  // Place tobacco + matches → smoker B needs paper
                sem_post(&smoker_b_can_go);
                break;
            case 2:  // Place paper + matches → smoker A needs tobacco
                sem_post(&smoker_a_can_go);
                break;
        }
        
        wait_for_smoker();
    }
}
 
void* smoker_a(void* arg) {
    while (1) {
        sem_wait(&smoker_a_can_go);
        make_cigarette();
        smoke();
        signal_agent_done();
    }
}
 
// This WORKS but is considered "cheating" - the agent knows
// which smoker to signal. The problem requires the matching
// logic to be in the smoker/pusher code, not the agent.

Why This Matters:

In real systems, the "agent" is often hardware or a fixed protocol that cannot embed application-specific logic. For example:

A network interface that receives packets with certain header combinations
A hardware interrupt controller signaling device events
A database trigger that fires on certain column updates

The matching logic must be in the consumer (smoker) side, not the producer (agent) side.

The Pusher Pattern Solution

The correct solution introduces pusher threads that act as intermediaries. Pushers observe which ingredients are placed and, when they detect a complete pair, signal the appropriate smoker.

Key Insight:

We separate the problem into two stages:

Stage 1: Track which ingredients are currently on the table
Stage 2: When a combination is complete, signal the right smoker

Pushers provide the "conditional logic" that basic semaphores lack. Each ingredient has a pusher that:

Wakes when that ingredient is placed
Checks if the complementary ingredient is already present
If yes: signals the appropriate smoker
If no: records that this ingredient is now waiting

pusher_solution.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
/*
 * The Cigarette Smokers Problem - Pusher Pattern Solution
 * 
 * The key insight: introduce "pusher" threads that observe
 * individual ingredient signals and track state to determine
 * when a complete pair exists for a specific smoker.
 */
 
#include <semaphore.h>
#include <pthread.h>
#include <stdio.h>
#include <stdbool.h>
 
/*
 * Agent's semaphores - one per ingredient
 * These are signaled by the agent when it places ingredients.
 */
sem_t tobacco_on_table;
sem_t paper_on_table;
sem_t matches_on_table;
 
/*
 * Smoker semaphores - signaled when their pair is complete
 */
sem_t smoker_with_tobacco;   // Needs paper + matches
sem_t smoker_with_paper;     // Needs tobacco + matches
sem_t smoker_with_matches;   // Needs tobacco + paper
 
/*
 * Agent synchronization
 */
sem_t agent_ready;
 
/*
 * Shared state: tracks what's currently on the table
 * Protected by mutex
 */
pthread_mutex_t table_mutex = PTHREAD_MUTEX_INITIALIZER;
bool has_tobacco = false;
bool has_paper = false;
bool has_matches = false;
 
/* ============================================
 * PUSHER THREADS
 * ============================================
 * Each pusher wakes when its ingredient arrives,
 * checks if a complement is present, and signals
 * the appropriate smoker if so.
 */
 
void* tobacco_pusher(void* arg) {
    while (1) {
        // Wait for tobacco to be placed
        sem_wait(&tobacco_on_table);
        
        pthread_mutex_lock(&table_mutex);
        
        if (has_paper) {
            // Tobacco + Paper on table → Smoker with matches can smoke
            has_paper = false;  // Consume the paper
            sem_post(&smoker_with_matches);
        } else if (has_matches) {
            // Tobacco + Matches on table → Smoker with paper can smoke
            has_matches = false;  // Consume the matches
            sem_post(&smoker_with_paper);
        } else {
            // Neither complement present yet - record tobacco and wait
            has_tobacco = true;
        }
        
        pthread_mutex_unlock(&table_mutex);
    }
    return NULL;
}
 
void* paper_pusher(void* arg) {
    while (1) {
        sem_wait(&paper_on_table);
        
        pthread_mutex_lock(&table_mutex);
        
        if (has_tobacco) {
            // Paper + Tobacco on table → Smoker with matches can smoke
            has_tobacco = false;
            sem_post(&smoker_with_matches);
        } else if (has_matches) {
            // Paper + Matches on table → Smoker with tobacco can smoke
            has_matches = false;
            sem_post(&smoker_with_tobacco);
        } else {
            // Record paper and wait
            has_paper = true;
        }
        
        pthread_mutex_unlock(&table_mutex);
    }
    return NULL;
}
 
void* matches_pusher(void* arg) {
    while (1) {
        sem_wait(&matches_on_table);
        
        pthread_mutex_lock(&table_mutex);
        
        if (has_tobacco) {
            // Matches + Tobacco on table → Smoker with paper can smoke
            has_tobacco = false;
            sem_post(&smoker_with_paper);
        } else if (has_paper) {
            // Matches + Paper on table → Smoker with tobacco can smoke
            has_paper = false;
            sem_post(&smoker_with_tobacco);
        } else {
            // Record matches and wait
            has_matches = true;
        }
        
        pthread_mutex_unlock(&table_mutex);
    }
    return NULL;
}
 
/* ============================================
 * SMOKER THREADS
 * ============================================
 * Each smoker waits on their personal semaphore,
 * which is signaled by a pusher when their pair
 * is complete.
 */
 
void* smoker_with_tobacco_thread(void* arg) {
    while (1) {
        sem_wait(&smoker_with_tobacco);
        
        printf("Smoker with tobacco: making cigarette...\n");
        make_cigarette();
        
        sem_post(&agent_ready);  // Signal agent can place more
        
        printf("Smoker with tobacco: smoking...\n");
        smoke();
    }
    return NULL;
}
 
void* smoker_with_paper_thread(void* arg) {
    while (1) {
        sem_wait(&smoker_with_paper);
        
        printf("Smoker with paper: making cigarette...\n");
        make_cigarette();
        
        sem_post(&agent_ready);
        
        printf("Smoker with paper: smoking...\n");
        smoke();
    }
    return NULL;
}
 
void* smoker_with_matches_thread(void* arg) {
    while (1) {
        sem_wait(&smoker_with_matches);
        
        printf("Smoker with matches: making cigarette...\n");
        make_cigarette();
        
        sem_post(&agent_ready);
        
        printf("Smoker with matches: smoking...\n");
        smoke();
    }
    return NULL;
}
 
/* ============================================
 * AGENT THREAD
 * ============================================
 * Randomly places two ingredients, then waits.
 * This code is "fixed" - cannot be modified
 * per problem constraints.
 */
 
void* agent_thread(void* arg) {
    while (1) {
        sem_wait(&agent_ready);
        
        int choice = random() % 3;
        
        switch (choice) {
            case 0:  // Place tobacco + paper
                printf("Agent: placing tobacco and paper\n");
                sem_post(&tobacco_on_table);
                sem_post(&paper_on_table);
                break;
            case 1:  // Place tobacco + matches
                printf("Agent: placing tobacco and matches\n");
                sem_post(&tobacco_on_table);
                sem_post(&matches_on_table);
                break;
            case 2:  // Place paper + matches
                printf("Agent: placing paper and matches\n");
                sem_post(&paper_on_table);
                sem_post(&matches_on_table);
                break;
        }
    }
    return NULL;
}
 
/* ============================================
 * MAIN - INITIALIZATION
 * ============================================ */
int main() {
    // Initialize ingredient semaphores (start at 0)
    sem_init(&tobacco_on_table, 0, 0);
    sem_init(&paper_on_table, 0, 0);
    sem_init(&matches_on_table, 0, 0);
    
    // Initialize smoker semaphores (start at 0)
    sem_init(&smoker_with_tobacco, 0, 0);
    sem_init(&smoker_with_paper, 0, 0);
    sem_init(&smoker_with_matches, 0, 0);
    
    // Agent can start immediately
    sem_init(&agent_ready, 0, 1);
    
    // Create threads
    pthread_t pushers[3], smokers[3], agent;
    
    pthread_create(&pushers[0], NULL, tobacco_pusher, NULL);
    pthread_create(&pushers[1], NULL, paper_pusher, NULL);
    pthread_create(&pushers[2], NULL, matches_pusher, NULL);
    
    pthread_create(&smokers[0], NULL, smoker_with_tobacco_thread, NULL);
    pthread_create(&smokers[1], NULL, smoker_with_paper_thread, NULL);
    pthread_create(&smokers[2], NULL, smoker_with_matches_thread, NULL);
    
    pthread_create(&agent, NULL, agent_thread, NULL);
    
    // Run forever
    pthread_join(agent, NULL);
    
    return 0;
}

Why Pushers Solve the Problem

The pushers provide conditional logic that semaphores lack:

Key invariant: At any time, at most one boolean (has_tobacco, has_paper, has_matches) is true, because the agent places exactly two ingredients.

Correctness Analysis

Let's rigorously verify the pusher solution's correctness.

Property 1: Mutual Exclusion

Claim: Only one smoker smokes at a time.

Proof:

The agent waits on agent_ready before placing ingredients
agent_ready starts at 1, allowing one placement
After a smoker finishes making a cigarette, they post agent_ready
Therefore, at most one ingredient pair is on the table at any time
Only one smoker can be signaled per pair
Thus, only one smoker smokes at a time ∎

Property 2: Correct Smoker Selection

Claim: When the agent places ingredients X and Y, the smoker with ingredient Z (where Z is the missing one) is signaled.

Proof by case analysis:

Case: Agent places tobacco + paper

tobacco_on_table and paper_on_table are posted
Suppose tobacco pusher runs first:
- Checks has_paper (false) and has_matches (false)
- Sets has_tobacco = true
Then paper pusher runs:
- Checks has_tobacco (true!)
- Sets has_tobacco = false
- Posts smoker_with_matches

Alternatively, if paper pusher runs first:

Sets has_paper = true
Tobacco pusher runs:
- Checks has_paper (true!)
- Sets has_paper = false
- Posts smoker_with_matches

Either way, smoker_with_matches is signaled ✓

Symmetric analysis applies to other cases. ∎

Complete Case Analysis
Agent Places	First Pusher	Sets	Second Pusher	Signals
T + P	tobacco_pusher	has_tobacco = true	paper_pusher	smoker_with_matches
T + P	paper_pusher	has_paper = true	tobacco_pusher	smoker_with_matches
T + M	tobacco_pusher	has_tobacco = true	matches_pusher	smoker_with_paper
T + M	matches_pusher	has_matches = true	tobacco_pusher	smoker_with_paper
P + M	paper_pusher	has_paper = true	matches_pusher	smoker_with_tobacco
P + M	matches_pusher	has_matches = true	paper_pusher	smoker_with_tobacco

Property 3: No Deadlock

Claim: The system never reaches a state where all threads are blocked forever.

Proof:

Initially, agent_ready = 1, so agent can run
Agent posts to two ingredient semaphores, waking two pushers
One pusher (the second to check) finds the complement and signals a smoker
The smoker runs, posts agent_ready, and the cycle continues
No circular wait is possible because information flows unidirectionally: Agent → Ingredient semaphores → Pushers → Smoker semaphores → Smokers → agent_ready ∎

Key Invariant

At any point between complete agent placements: exactly zero or one of (has_tobacco, has_paper, has_matches) is true. This holds because:

Initially all are false
Agent places exactly two ingredients
First pusher sets one to true
Second pusher finds it true, sets it false, and signals smoker
Smoker signals agent, resetting for next round

Theoretical Significance: Limitations of Semaphores

The Core Limitation:

Semaphores excel at:

Signaling between processes
Counting resources
Enforcing mutual exclusion

But semaphores struggle with conditional synchronization based on multiple conditions—waiting until a combination of states is true.

Why Can't Smokers Just Wait on Two Semaphores?

atomic_wait_problem.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// What we WANT (but semaphores don't support):
wait_for_all(paper, matches);  // Atomic wait for BOTH
 
// What semaphores give us:
sem_wait(&paper);   // Might succeed
sem_wait(&matches); // Might block forever if matches not there
 
// The problem: after getting paper, if matches isn't there,
// we're stuck holding paper. Meanwhile, another smoker
// might need paper but we've taken it.
 
// This is analogous to the "two-army problem" in atomicity:
// We can't atomically acquire two resources when we don't
// control both resource's timing.

What the Pusher Pattern Actually Demonstrates:

The pusher pattern shows that we can work around the limitation by:

Introducing an intermediate coordination layer
Using shared state (the boolean flags) to track partial progress
Having the coordinator (pusher) make decisions and signal the right consumer

But this feels like we're compensating for a missing primitive—and we are. Monitors with condition variables handle this more naturally:

monitor_solution_sketch.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// With monitors, the solution is more direct:
 
monitor CigaretteSmokers {
    condition can_smoke[3];  // One per smoker
    int placed[3] = {0, 0, 0};  // Count of each ingredient on table
    
    procedure agent_places(ingredients) {
        for each i in ingredients:
            placed[i]++;
        
        // Wake appropriate smoker based on what's there
        if (placed[PAPER] > 0 && placed[MATCHES] > 0)
            signal(can_smoke[TOBACCO_SMOKER]);
        else if (placed[TOBACCO] > 0 && placed[MATCHES] > 0)
            signal(can_smoke[PAPER_SMOKER]);
        else if (placed[TOBACCO] > 0 && placed[PAPER] > 0)
            signal(can_smoke[MATCHES_SMOKER]);
    }
    
    procedure smoker_takes(smoker_id, ingredient1, ingredient2) {
        while (placed[ingredient1] == 0 || placed[ingredient2] == 0)
            wait(can_smoke[smoker_id]);
        
        placed[ingredient1]--;
        placed[ingredient2]--;
    }
}
 
// Note: This still has conditional logic, but the monitor's
// encapsulation and condition variables make it cleaner.
// We still need to know which smoker to signal - that's
// fundamental to the problem, not an artifact of the solution.

Broader Lesson

The Cigarette Smokers Problem teaches a meta-lesson:

In practice, choose the abstraction that matches your problem's natural structure.

Real-World Applications and Patterns

Despite its abstract formulation, the Cigarette Smokers pattern appears in real systems:

1. Workflow Engines with Parallel Dependencies

In workflow systems, a task might require multiple asynchronous inputs before executing:

A report generation task needs data from both Database A and API B
A build task needs both compilation to succeed and tests to pass
An approval process needs sign-off from both Legal and Finance

The "pusher" pattern translates to a join node in workflow engines that collects required inputs and triggers the downstream task only when all are ready.

Event-Driven Architecture

•Events = Ingredients
•Event handlers = Pushers
•Aggregate state = Table state (booleans)
•Complex event = Complete pair
•Action trigger = Signaling smoker

Hardware Interrupt Handling

•Interrupt signals = Ingredients
•Interrupt handlers = Pushers
•Device state = Table state
•Ready condition = Both signals received
•Device driver = Smoker

2. Complex Event Processing (CEP)

CEP systems detect patterns across event streams. The Cigarette Smokers pattern represents conjunction patterns:

Detect when Event A AND Event B occur within a time window
Only trigger the downstream action when both are present
Track partial matches (one event but not the other)

Pushers are analogous to event correlators in CEP engines that track partial matches and trigger downstream logic when complete.

3. Resource Matching in Scheduling

In some scheduling problems, a job requires multiple resources of specific types:

A video rendering job needs both a GPU and fast storage
A database query needs both a read replica and a cache hit
A network request needs both outgoing bandwidth and a connection slot

The coordinator must match available resources and dispatch jobs when complete resource sets are available.

workflow_engine_example.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
"""
Workflow Engine Join Node - Cigarette Smokers Pattern
 
This models a workflow task that requires multiple async inputs.
The JoinNode acts as a "pusher" - collecting inputs and triggering
the downstream task when all required inputs are present.
"""
 
from typing import Dict, Set, Callable
import threading
 
class JoinNode:
    """
    Collects multiple asynchronous inputs and triggers action
    when all required inputs are present.
    """
    
    def __init__(self, required_inputs: Set[str], action: Callable):
        self.required = required_inputs
        self.action = action
        self.received: Dict[str, any] = {}
        self.lock = threading.Lock()
        self.completed = threading.Event()
    
    def receive(self, input_name: str, value: any):
        """Called when an upstream task completes."""
        with self.lock:
            if input_name not in self.required:
                return  # Ignore unexpected inputs
            
            self.received[input_name] = value
            
            # Check if all inputs present (pusher logic)
            if set(self.received.keys()) == self.required:
                # All inputs present - trigger action (signal smoker)
                self._trigger()
    
    def _trigger(self):
        """Execute the downstream task with collected inputs."""
        self.action(self.received)
        self.received.clear()  # Reset for next execution
        self.completed.set()
 
# Usage example:
def generate_report(inputs):
    db_data = inputs["database_query"]
    api_data = inputs["api_response"]
    print(f"Generating report with DB:{db_data}, API:{api_data}")
 
join = JoinNode({"database_query", "api_response"}, generate_report)
 
# Async inputs arrive...
join.receive("database_query", {"users": 1000})  # First input
join.receive("api_response", {"weather": "sunny"})  # Second input triggers action

Pattern Recognition

When you see these characteristics, think Cigarette Smokers:

The solution is always some form of coordinator/aggregator that tracks partial state.

Variations and Extensions

Several variations of the Cigarette Smokers Problem explore additional complexities:

1. Multiple Agents

What if multiple agents can place ingredients simultaneously? This introduces additional race conditions:

Two agents might each place tobacco + one other, creating two tobaccos on the table
The matching logic must handle arbitrary counts, not just presence/absence
Fairness becomes an issue: which smoker gets precedence if multiple can smoke?

2. Non-Exclusive Smoking

In the original problem, only one smoker smokes at a time. A relaxed variant allows concurrent smoking:

Multiple ingredient pairs might be on the table
Multiple smokers can smoke simultaneously if resources permit
Maximizing throughput becomes an optimization goal

3. Generalized to N Ingredients and M Smokers

With more ingredients and smokers, the combinatorics explode:

Each smoker might need a unique subset of K ingredients (from N total)
Matching becomes more complex as subsets can overlap
This models real resource allocation with multiple resource types

generalized_matching.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
"""
Generalized Cigarette Smokers: N ingredients, M consumers
 
Each consumer has a set of "owned" ingredients and needs
all other ingredients to proceed.
"""
 
from typing import Set, List, Dict
import threading
 
class GeneralizedMatcher:
    def __init__(self, ingredient_sets: Dict[str, Set[str]], 
                 all_ingredients: Set[str]):
        """
        ingredient_sets: maps consumer ID to ingredients they OWN
        all_ingredients: complete set of all ingredients
        
        Each consumer NEEDS: all_ingredients - their_owned_set
        """
        self.consumers = {
            consumer_id: all_ingredients - owned
            for consumer_id, owned in ingredient_sets.items()
        }
        
        self.on_table: Set[str] = set()
        self.lock = threading.Lock()
        self.consumer_signals = {
            cid: threading.Semaphore(0) 
            for cid in self.consumers
        }
    
    def place_ingredients(self, ingredients: Set[str]):
        """Agent places a set of ingredients."""
        with self.lock:
            self.on_table.update(ingredients)
            
            # Check each consumer
            for consumer_id, needed in self.consumers.items():
                if needed.issubset(self.on_table):
                    # This consumer can proceed
                    self.on_table -= needed  # Consume ingredients
                    self.consumer_signals[consumer_id].release()
                    return  # Only one consumer per placement
    
    def wait_and_consume(self, consumer_id: str):
        """Consumer waits until their ingredients are ready."""
        self.consumer_signals[consumer_id].acquire()
        # Consumer has now obtained their ingredients

4. Timed Ingredients (Expiration)

In real systems, resources might expire or become stale:

Ingredients placed on the table might "spoil" after a timeout
Smokers must act within a window or the opportunity is lost
This models cache expiration, session timeouts, and resource leases

5. Priority-Based Matching

Some smokers might have higher priority:

When multiple smokers could potentially use available ingredients
High-priority smoker should be signaled first
This models priority-based resource allocation and scheduling

Design Insight

Each variation teaches something about real systems:

Summary and Key Takeaways

The Cigarette Smokers Problem reveals deep truths about synchronization primitives and their limitations. Let's consolidate the key lessons:

Key Takeaways

•Semaphores can't atomically wait on combinations: A thread can wait on one semaphore or acquire multiple sequentially, but not atomically wait for a condition involving multiple resources
•The pusher pattern fills the gap: Intermediate coordinators that track partial state and signal consumers when complete combinations exist
•Matching logic must exist somewhere: Whether in the producer, consumer, or middleware—someone must determine which consumer gets which resources
•Different primitives have different strengths: Monitors with condition variables express this pattern more naturally, though the matching logic remains necessary
•Real systems face this constantly: Workflow engines, CEP systems, resource schedulers all implement variations of this pattern
•The problem is designed to teach: Patil created it specifically to show semaphore limitations—understanding why it's hard is as important as solving it

Page Complete

2 / 5