7a:T1526,/* * The Sleeping Barber Problem - Correct Semaphore Solution * * This solution uses Dijkstra's original approach with three semaphores: * - customers: signals presence of waiting customers (count) * - barber: signals barber readiness (binary-like behavior) * - mutex: protects the waiting count variable */ #include #include #include #include #define CHAIRS 5 // Number of waiting room chairs sem_t customers; // Counts waiting customers (semaphore value = waiting count) sem_t barber; // Signals barber is ready for next customer pthread_mutex_t mutex; // Protects 'waiting' variable int waiting = 0; // Customers currently in waiting room /* ============================================ * BARBER THREAD * ============================================ */ void* barber_thread(void* arg) { while (1) { /* * Step 1: Wait for a customer to arrive * * sem_wait decrements 'customers' semaphore. * If customers == 0, barber blocks (sleeps) here. * When a customer arrives and posts to 'customers', * the barber wakes up. */ sem_wait(&customers); /* * Step 2: Acquire mutex to safely decrement waiting count * * We must hold the mutex while modifying 'waiting' to prevent * race conditions with arriving customers. */ pthread_mutex_lock(&mutex); waiting--; // Customer moved from waiting room to barber chair /* * Step 3: Signal that barber is ready * * This wakes up the customer who is waiting for service. * The customer was blocked on sem_wait(&barber). */ sem_post(&barber); pthread_mutex_unlock(&mutex); /* * Step 4: Cut hair (critical section - service delivery) * * The actual work happens here. In a real system, * this could be processing a request, handling a connection, etc. */ cut_hair(); } return NULL; } /* ============================================ * CUSTOMER THREAD * ============================================ */ void* customer_thread(void* arg) { int customer_id = *(int*)arg; /* * Step 1: Acquire mutex to check and modify waiting count * * We need mutual exclusion because we're doing a compound operation: * checking if space is available AND reserving a spot. */ pthread_mutex_lock(&mutex); /* * Step 2: Check if waiting room has space (bounded buffer check) */ if (waiting < CHAIRS) { /* * Step 3a: Space available - join the queue */ waiting++; // Reserve a spot in waiting room /* * Step 4: Signal barber that a customer is waiting * * sem_post increments 'customers' semaphore. * If barber was sleeping (blocked on sem_wait), this wakes him. * If barber was busy, this just increments the count. */ sem_post(&customers); pthread_mutex_unlock(&mutex); // Release mutex before blocking /* * Step 5: Wait for barber to be ready * * Block until barber signals readiness with sem_post(&barber). * This ensures proper handoff between barber and customer. */ sem_wait(&barber); /* * Step 6: Get haircut * * Customer is now in barber chair receiving service. */ get_haircut(); printf("Customer %d: haircut complete, leaving satisfied ", customer_id); } else { /* * Step 3b: No space - leave immediately (balk) * * Customer cannot wait, must leave without service. * This is the "balk" behavior in queueing theory. */ pthread_mutex_unlock(&mutex); printf("Customer %d: no space, leaving without haircut ", customer_id); } return NULL; } /* ============================================ * SERVICE FUNCTIONS * ============================================ */ void cut_hair() { printf("Barber: cutting hair... "); sleep(3); // Simulate haircut duration printf("Barber: done with this customer "); } void get_haircut() { printf("Customer: getting haircut... "); // Duration controlled by cut_hair() - customer just waits } /* ============================================ * INITIALIZATION AND MAIN * ============================================ */ int main() { // Initialize semaphores sem_init(&customers, 0, 0); // Initially no customers waiting sem_init(&barber, 0, 0); // Barber not ready initially pthread_mutex_init(&mutex, NULL); // Create barber thread pthread_t barber_tid; pthread_create(&barber_tid, NULL, barber_thread, NULL); // Simulate customer arrivals for (int i = 0; i < 20; i++) { pthread_t customer_tid; int* id = malloc(sizeof(int)); *id = i; pthread_create(&customer_tid, NULL, customer_thread, id); // Random arrival interval usleep((rand() % 1000) * 1000); // 0-1000ms } // In practice, would join threads and cleanup pthread_join(barber_tid, NULL); return 0; }7b:T843,/* * Multiple Barbers Extension * * The key insight is that multiple barber threads can share * the same semaphores. The 'customers' semaphore naturally * handles waking one barber per customer. */ #define NUM_BARBERS 3 #define CHAIRS 10 sem_t customers; sem_t barber_ready[NUM_BARBERS]; // One per barber for debugging pthread_mutex_t mutex; int waiting = 0; void* barber_thread(void* arg) { int barber_id = *(int*)arg; while (1) { printf("Barber %d: checking for customers... ", barber_id); // Wait for any customer - multiple barbers compete here sem_wait(&customers); pthread_mutex_lock(&mutex); waiting--; printf("Barber %d: serving customer, %d still waiting ", barber_id, waiting); pthread_mutex_unlock(&mutex); // Signal ready (for this barber's customer) sem_post(&barber_ready[barber_id]); // Perform haircut cut_hair(barber_id); } return NULL; } void* customer_thread(void* arg) { int customer_id = *(int*)arg; pthread_mutex_lock(&mutex); if (waiting < CHAIRS) { waiting++; int my_position = waiting; printf("Customer %d: waiting in position %d ", customer_id, my_position); sem_post(&customers); // Wake up any sleeping barber pthread_mutex_unlock(&mutex); // In a fair variant, would need assignment to specific barber // Simplified: assume any barber_ready signal works for us // Real implementation needs more sophisticated matching get_haircut(); printf("Customer %d: haircut complete ", customer_id); } else { pthread_mutex_unlock(&mutex); printf("Customer %d: shop full, leaving ", customer_id); } return NULL; } /* * Note: This simplified version has a subtle fairness issue. * The sem_post(&barber_ready[barber_id]) may not go to the * customer that originally woke this barber. In practice, * you'd use a single barber semaphore or explicit queuing. */72:{"json":{"id":"seed_6c1edf3003b5b907a695455ad44be2e5","slug":"other-classic-problems","category":"Operating Systems","topic":"Semaphores & Classic Problems","title":"Other Classic Synchronization Problems","description":"Master additional classic synchronization problems beyond producer-consumer, readers-writers, and dining philosophers. Explore the Sleeping Barber, Cigarette Smokers, bounded buffer variations, common patterns, and solution strategies that form the foundation of concurrent programming expertise.","difficulty":"INTERMEDIATE","estimatedMinutes":90,"pages":[{"id":"seed_388d6e7a14203ed67c387d0d3b821539","title":"The Sleeping Barber Problem","order":0,"content":[{"id":"opening-context","title":"A Shop, A Barber, and the Art of Waiting","content":[{"data":{"content":"Imagine a small barbershop with a single barber, one barber chair, and a waiting room containing a fixed number of chairs. When no customers are present, the barber sits in his chair and falls asleep. When a customer arrives, they must wake the barber if he is sleeping, or sit in one of the waiting chairs if the barber is busy. If all waiting chairs are occupied, the customer must leave without getting a haircut.\n\nThis seemingly simple scenario encapsulates one of the most elegant and instructive synchronization problems in computer science: **The Sleeping Barber Problem**, introduced by Edsger W. Dijkstra in 1965. What makes this problem profound is not its complexity, but how naturally it maps to real-world concurrent programming challenges—server connection pools, thread pools, request queues with bounded capacity, and any system where consumers must coordinate access to limited service capacity with finite waiting space."},"type":"text"},{"data":{"icon":"Target","title":"Learning Objectives","content":"By the end of this page, you will:\n\n• Deeply understand the Sleeping Barber problem and its variants\n• Recognize the synchronization challenges: mutual exclusion, conditional waiting, and signaling\n• Implement correct solutions using semaphores\n• Identify how this problem maps to real-world systems (connection pools, thread pools, service queues)\n• Analyze why naive solutions fail and how to avoid common pitfalls","variant":"info"},"type":"callout"}]},{"id":"problem-statement","title":"Formal Problem Statement","content":[{"data":{"content":"Before diving into solutions, we must precisely define the problem. Imprecise problem statements lead to incomplete solutions.\n\n**The Scenario:**\n\nA barbershop operates under the following constraints:\n\n1. **Single Barber**: There is exactly one barber who can serve one customer at a time\n2. **Barber Chair**: There is exactly one barber chair where haircuts occur\n3. **Waiting Room**: There are exactly N waiting chairs (finite capacity)\n4. **Barber Behavior**: When no customers are waiting, the barber sleeps in the barber chair\n5. **Customer Arrival**: Customers arrive at random intervals, independent of each other\n\n**Customer Actions Upon Arrival:**\n- If the barber is sleeping, the customer wakes them up and sits in the barber chair for a haircut\n- If the barber is busy but waiting chairs are available, the customer sits and waits\n- If the barber is busy and all waiting chairs are full, the customer leaves immediately"},"type":"text"},{"data":{"icon":"AlertCircle","title":"Critical Constraints","content":"The problem involves **three distinct resources** that must be coordinated:\n\n1. **The barber's attention** — only one customer can have it at a time\n2. **The barber chair** — exclusive access during haircut\n3. **Waiting chairs** — bounded capacity, first-come-first-served\n\nAdditionally, we must coordinate **two asymmetric roles**: the barber (service provider) and customers (service consumers).","variant":"warning"},"type":"callout"},{"data":{"content":"**Correctness Requirements:**\n\nA correct solution must satisfy these properties:\n\n**Safety Properties (nothing bad happens):**\n1. **Mutual Exclusion**: Only one customer receives a haircut at a time\n2. **Capacity Enforcement**: No more than N customers wait at any time\n3. **No Race Conditions**: Customer count and state transitions are atomic\n\n**Liveness Properties (something good eventually happens):**\n1. **No Deadlock**: The system never reaches a state where both the barber and customers are waiting forever\n2. **No Unnecessary Blocking**: Customers are served if the barber is available\n3. **Progress**: If customers are waiting, the barber eventually serves them\n\n**Fairness Properties (optional but desirable):**\n1. **Bounded Waiting**: A waiting customer is eventually served\n2. **FIFO Service**: Customers are served in arrival order (not strictly required, but often desired)"},"type":"text"},{"data":{"rows":[["Sleeping","0","Barber idle, waiting room empty","Wake barber, get haircut immediately"],["Cutting hair","0","Serving one, none waiting","Sit in waiting room (if space)"],["Cutting hair","1 to N-1","Serving one, some waiting","Sit in waiting room (if space)"],["Cutting hair","N","Serving one, waiting room full","Leave immediately (balk)"],["Done cutting",">0","Transitioning to next customer","System invokes next waiter"]],"caption":"State Space of the Sleeping Barber Problem","headers":["Barber State","Waiting Customers","System Behavior","Next Customer Action"]},"type":"table"}],"titleType":"number","titleNumber":1},{"id":"synchronization-challenges","title":"Synchronization Challenges","content":[{"data":{"content":"The Sleeping Barber problem elegantly combines multiple synchronization challenges that must be solved simultaneously. Understanding these challenges individually clarifies why naive solutions fail.\n\n**Challenge 1: The Wakeup Coordination Problem**\n\nWhen the barber sleeps, a customer must wake them. This involves a classic producer-consumer coordination where:\n- The barber waits for customers (consumes service requests)\n- Customers signal availability (produce service requests)\n\nThe danger is a **lost wakeup**: if the barber checks for customers and finds none, then a customer arrives and signals *before* the barber goes to sleep, the signal is lost. The barber sleeps forever while a customer waits forever—deadlock."},"type":"text"},{"data":{"code":"// BROKEN: Demonstrates the lost wakeup race condition\n\n// Shared state (unprotected)\nint waiting_customers = 0;\n\nvoid barber() {\n while (true) {\n // RACE CONDITION WINDOW OPENS HERE\n if (waiting_customers == 0) {\n // Suppose a customer arrives RIGHT HERE\n // Customer increments waiting_customers to 1\n // Customer signals wakeup (but barber not sleeping yet!)\n sleep(); // Barber goes to sleep AFTER signal was sent\n // DEADLOCK: Signal was lost, barber sleeps forever\n }\n // Cut hair...\n }\n}\n\nvoid customer() {\n waiting_customers++; // Might happen during barber's check\n wakeup_barber(); // Signal lost if barber not sleeping yet\n // Wait for haircut...\n}","fileName":"lost_wakeup_race_condition.c"},"type":"code"},{"data":{"content":"**Challenge 2: The Bounded Buffer Constraint**\n\nThe waiting room has finite capacity. When full, arriving customers must be turned away. This is a **bounded buffer** scenario, but with a twist: customers who can't wait must *balk* (leave immediately) rather than block.\n\nThis introduces the need to:\n1. Atomically check if space is available\n2. Only allow the customer to wait if space exists\n3. Ensure the count of waiting customers is always accurate\n\n**Challenge 3: Mutual Exclusion for State Transitions**\n\nMultiple state variables must be updated atomically:\n- Number of waiting customers\n- Barber's state (sleeping vs. cutting)\n- Which customer is currently being served\n\nWithout proper mutual exclusion, concurrent updates create inconsistent states."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Recognizing the Pattern","content":"The Sleeping Barber combines three fundamental patterns:\n\n1. **Producer-Consumer**: Customers produce work; barber consumes it\n2. **Bounded Buffer**: Limited waiting capacity with rejection policy\n3. **Rendezvous**: Barber and customer must synchronize for service delivery\n\nRecognizing these patterns helps decompose the problem into manageable parts.","variant":"tip"},"type":"callout"},{"data":{"content":"**Challenge 4: The Rendezvous Problem**\n\nWhen a customer wakes the barber, they must coordinate to actually perform the haircut. The customer can't leave before the haircut completes, and the barber can't serve the next customer until the current one vacates the chair.\n\nThis requires a **barrier-like synchronization** where:\n1. Customer signals \"I'm ready for my haircut\"\n2. Barber acknowledges and begins cutting\n3. Barber signals \"haircut complete\"\n4. Customer receives signal and leaves\n\nWithout this coordination, customers might leave before their haircut, or the barber might try to serve the same customer twice."},"type":"text"},{"data":{"rows":[["Lost Wakeup","Signal before sleep","Deadlock: barber and customer wait forever"],["Race on Count","Non-atomic check-then-act","Too many customers admitted; capacity violated"],["Multiple Barber Chairs","No exclusion on chair access","Multiple customers served simultaneously"],["Premature Customer Departure","No completion handshake","Customer leaves mid-haircut"],["Barber Double-Serves","No rendezvous protocol","Same customer served twice, other starves"]],"caption":"Synchronization Challenges and Their Consequences","headers":["Challenge","Incorrect Handling","Consequence"]},"type":"table"}],"titleType":"number","titleNumber":2},{"id":"semaphore-solution","title":"Semaphore-Based Solution","content":[{"data":{"content":"Now we develop a correct solution using semaphores. We use three semaphores and a mutex to coordinate the barber and customers:\n\n**Semaphores:**\n1. `customers`: Counts customers waiting (including one in barber chair). The barber waits on this.\n2. `barber`: Signals that the barber is ready for the next customer. Customers wait on this.\n3. `mutex`: Provides mutual exclusion for accessing shared state.\n\n**Shared Variables:**\n- `waiting`: Number of customers in waiting room (not including the one being served)\n- `CHAIRS`: Constant defining waiting room capacity\n\nThe key insight is using semaphores both for signaling (wakeup coordination) and counting (bounded buffer)."},"type":"text"},{"data":{"code":"$7a","fileName":"sleeping_barber_solution.c","languages":[{"label":"C (Semaphore)","value":"c"},{"label":"Pseudocode","value":"pseudocode"}]},"type":"code"},{"data":{"icon":"CheckCircle","title":"Why This Solution is Correct","content":"**Lost Wakeup Prevention**: The customer posts to 'customers' semaphore BEFORE blocking on 'barber'. The barber waits on 'customers', so the signal is never lost.\n\n**Atomic Capacity Check**: The mutex protects the check-then-increment of 'waiting', preventing over-admission.\n\n**Bounded Waiting**: Customers block on 'barber' with FIFO ordering (if semaphore is FIFO), ensuring bounded waiting.\n\n**No Deadlock**: Mutex is always released before any blocking wait on semaphores.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"correctness-analysis","title":"Detailed Correctness Analysis","content":[{"data":{"content":"Let's rigorously verify that our solution satisfies all correctness properties. This type of analysis is essential for concurrent programs where intuition often fails.\n\n**Property 1: Mutual Exclusion on Barber Chair**\n\n*Claim*: At most one customer is being served at any time.\n\n*Proof*: \n- Only one barber thread exists, and it executes `cut_hair()` sequentially\n- A customer only proceeds to `get_haircut()` after receiving `sem_post(&barber)` from the barber\n- The barber only issues `sem_post(&barber)` once per iteration of its loop\n- Therefore, at most one customer can be past the `sem_wait(&barber)` at any time ∎\n\n**Property 2: Bounded Waiting Room Capacity**\n\n*Claim*: At most CHAIRS customers are in the waiting state.\n\n*Proof*:\n- `waiting` is only incremented inside the mutex-protected critical section\n- The increment only occurs if `waiting < CHAIRS`\n- `waiting` is decremented by the barber when a customer moves to service\n- The invariant `0 ≤ waiting ≤ CHAIRS` is maintained ∎"},"type":"text"},{"data":{"content":"**Property 3: No Deadlock**\n\n*Claim*: The system is deadlock-free.\n\n*Proof by contradiction*:\n\nAssume deadlock occurs. In deadlock:\n- The barber is blocked on `sem_wait(&customers)` (waiting for customers)\n- At least one customer is blocked on `sem_wait(&barber)` (waiting for barber)\n\nBut if a customer is blocked on `sem_wait(&barber)`, they already executed `sem_post(&customers)` (line order in code). This means the `customers` semaphore was incremented, so the barber cannot be blocked—contradiction.\n\nAlternatively, if customers are blocked on `mutex`, no thread holds it indefinitely (mutex is always released before blocking waits). ∎\n\n**Property 4: No Lost Wakeups**\n\n*Claim*: If a customer arrives while the barber sleeps, the barber wakes up.\n\n*Proof*:\n- \"Barber sleeps\" means barber is blocked on `sem_wait(&customers)` with `customers == 0`\n- Customer arriving executes `sem_post(&customers)` which increments to 1\n- `sem_post` wakes any thread blocked on that semaphore\n- Therefore, barber wakes up ∎"},"type":"text"},{"data":{"rows":[["Barber sleeping, none waiting","0","0","0"],["Customer arrives, wakes barber","1 → 0","0 → 1","1 → 0"],["Barber cutting, 2 waiting","2","0","2"],["Barber finishes, signals next","2 → 1","0 → 1","2 → 1"],["Customer gets signal, enters chair","1","1 → 0","1"]],"caption":"Semaphore Invariants Throughout Execution","headers":["State","customers value","barber value","waiting value"]},"type":"table"},{"data":{"icon":"Info","title":"Invariant Reasoning","content":"At all times: **customers.value == waiting** (number of customers who have signaled arrival but not yet been served). This invariant is key to understanding why the solution works. The mutex ensures atomic updates to 'waiting' that correspond to semaphore operations.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"real-world-mappings","title":"Real-World System Mappings","content":[{"data":{"content":"The Sleeping Barber problem is not merely academic—it directly models many real-world systems. Understanding these mappings helps recognize when to apply this pattern.\n\n**Connection Pool Management**\n\nDatabase connection pools exactly mirror the Sleeping Barber:\n- **Barber** = Database connection handler thread\n- **Waiting room chairs** = Pending request queue capacity\n- **Customers** = Application threads requesting connections\n- **Haircut** = Executing a database query\n- **Balking** = Returning error when pool and queue are full\n\nConnection pool libraries like HikariCP use these exact synchronization patterns to manage bounded pools with bounded queues."},"type":"text"},{"data":{"left":[{"data":{"items":["**Worker threads** = Barbers","**Task queue** = Waiting room","**Submitted tasks** = Customers","**Queue capacity** = Number of chairs","**Rejection policy** = Balking behavior"],"title":{"icon":"Code2","text":"Thread Pool Executor","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["**Request handler** = Barber","**Listen queue backlog** = Waiting room","**Incoming requests** = Customers","**TCP backlog limit** = Number of chairs","**Connection refused** = Balking"],"title":{"icon":"Code2","text":"Web Server Model","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"content":"**Printer Spooler Systems**\n\nPrint spoolers implement the Sleeping Barber pattern:\n- The printer device driver (barber) sleeps when no jobs are queued\n- Print jobs (customers) arrive from applications\n- The spooler queue (waiting room) has finite capacity\n- When queue is full, new print requests are rejected\n\n**Message Broker Consumers**\n\nMessage queue consumers follow this pattern:\n- Consumer threads sleep waiting for messages\n- Messages arrive from producers\n- Queue has configurable capacity limits\n- Backpressure mechanisms reject or slow producers when full\n\nApache Kafka consumers, RabbitMQ channel consumers, and AWS SQS pollers all implement variations of this synchronization pattern."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Pattern Recognition","content":"Anytime you encounter a system with these characteristics, think Sleeping Barber:\n\n• **Single or few servers** handling work\n• **Bounded queue** for pending work\n• **Bursty arrival** of work items\n• **Server sleeps** when queue empty\n• **Rejection policy** when queue full\n\nThe semaphore solution translates directly to condition variables, channels, or async/await constructs depending on your platform.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"multiple-barbers","title":"Extension: Multiple Barbers","content":[{"data":{"content":"A natural extension is the **Multiple Barbers** variant, which models systems with multiple equivalent service providers (thread pools with multiple workers, multi-core request handlers, etc.).\n\n**Extended Problem Statement:**\n- There are B barbers, each with their own barber chair\n- There are N waiting chairs shared among all customers\n- Each barber works independently but draws from the same waiting queue\n- When all barbers are sleeping and a customer arrives, any one barber wakes up\n\n**Key Insight:** The solution generalizes naturally because the `customers` semaphore already acts as a counting mechanism. Multiple barber threads can all wait on it, and customers signal it. The semaphore's internal queue handles waking exactly one barber per customer."},"type":"text"},{"data":{"code":"$7b","fileName":"multiple_barbers.c"},"type":"code"},{"data":{"icon":"AlertCircle","title":"Fairness Consideration","content":"With multiple barbers, preserving FIFO ordering becomes more complex. The simple solution above doesn't guarantee the first waiting customer gets served first. For strict FIFO, you need an explicit queue data structure protected by the mutex, where each barber dequeues the next customer.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"pitfalls-debugging","title":"Common Pitfalls and Debugging","content":[{"data":{"content":"Implementing the Sleeping Barber correctly requires avoiding several subtle bugs. Here are the most common pitfalls:\n\n**Pitfall 1: Mutex Held During Blocking Wait**\n\nIf the customer holds the mutex while waiting on `barber` semaphore, deadlock occurs:"},"type":"text"},{"data":{"code":"// WRONG: Holding mutex during semaphore wait\nvoid* customer_wrong(void* arg) {\n pthread_mutex_lock(&mutex);\n \n if (waiting < CHAIRS) {\n waiting++;\n sem_post(&customers);\n \n // BUG: Still holding mutex!\n sem_wait(&barber); // Blocks while holding mutex\n // Barber can't acquire mutex to signal\n // DEADLOCK!\n \n pthread_mutex_unlock(&mutex);\n get_haircut();\n } else {\n pthread_mutex_unlock(&mutex);\n }\n return NULL;\n}\n\n// CORRECT: Release mutex before blocking\nvoid* customer_correct(void* arg) {\n pthread_mutex_lock(&mutex);\n \n if (waiting < CHAIRS) {\n waiting++;\n sem_post(&customers);\n pthread_mutex_unlock(&mutex); // Release BEFORE waiting\n \n sem_wait(&barber); // Safe to block now\n get_haircut();\n } else {\n pthread_mutex_unlock(&mutex);\n }\n return NULL;\n}","fileName":"pitfall_mutex_held.c"},"type":"code"},{"data":{"content":"**Pitfall 2: Incorrect Semaphore Order**\n\nIf the barber signals `barber` before waiting on `customers`, customers can proceed without actual service:"},"type":"text"},{"data":{"code":"// WRONG: Signaling before waiting\nvoid* barber_wrong(void* arg) {\n while (1) {\n pthread_mutex_lock(&mutex);\n \n // BUG: Post barber signal before actually ready\n sem_post(&barber); // Customer can proceed immediately\n \n sem_wait(&customers); // Now waiting, but customer already gone!\n // Customer thinks they got a haircut but barber hasn't done anything\n \n pthread_mutex_unlock(&mutex);\n cut_hair(); // Cutting hair for nobody\n }\n return NULL;\n}\n\n// CORRECT: Wait for customer first, then signal ready\nvoid* barber_correct(void* arg) {\n while (1) {\n sem_wait(&customers); // Wait for customer first\n \n pthread_mutex_lock(&mutex);\n waiting--;\n sem_post(&barber); // Then signal barber is ready\n pthread_mutex_unlock(&mutex);\n \n cut_hair(); // Actually cut the waiting customer's hair\n }\n return NULL;\n}","fileName":"pitfall_wrong_order.c"},"type":"code"},{"data":{"items":["**Not initializing semaphores correctly**: `customers` must start at 0, not at `waiting` value","**Race between checking and decrementing `waiting`**: Barber must hold mutex when decrementing","**Customers incrementing `waiting` outside mutex**: Creates race with capacity check","**Barber not decrementing `waiting`**: Leads to artificial capacity limits","**Using binary semaphore for `customers`**: Must be counting semaphore to handle multiple waiters"],"title":{"icon":"AlertCircle","text":"Other Common Pitfalls","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"icon":"Info","title":"Debugging Technique: Trace Analysis","content":"When debugging, add logging that shows:\n1. Thread ID and action (customer arriving, barber waking, etc.)\n2. Semaphore values before/after each operation\n3. Mutex state and waiting count\n\nTraces help identify the exact interleaving that causes failures. Tools like ThreadSanitizer can detect races automatically.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary-takeaways","title":"Summary and Key Takeaways","content":[{"data":{"content":"The Sleeping Barber problem teaches essential synchronization concepts that recur throughout systems programming. Let's consolidate what we've learned:"},"type":"text"},{"data":{"type":"ordered","items":["**The problem combines multiple patterns**: Producer-consumer, bounded buffer, and rendezvous synchronization all appear in one scenario","**Lost wakeups are the critical bug**: Semaphores prevent lost wakeups by providing durable signaling that persists until consumed","**Bounded capacity requires atomic check-then-act**: The mutex protects the capacity check and reservation as an atomic operation","**Order of operations matters critically**: Releasing mutex before blocking, waiting before signaling—these orderings prevent deadlock","**The solution maps to real systems**: Connection pools, thread pools, request queues, and message consumers all use this pattern","**Multiple servers generalize naturally**: The counting semaphore approach scales to multiple barbers without fundamental changes"],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now deeply understand the Sleeping Barber problem—its challenges, correct solution, and real-world applications. This foundation prepares you for the next classic problem: the Cigarette Smokers Problem, which introduces the challenge of matching producers with specific resource combinations.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_4e35997d801469e6b83acda1e0db9658","title":"The Cigarette Smokers Problem","order":1,"content":null,"isLocked":true},{"id":"seed_82b30c9653c9b5ce5c4b32db8b14454a","title":"Bounded Buffer Variations","order":2,"content":null,"isLocked":true},{"id":"seed_24710acd93aafdf6bb4d9d9aab08f1f8","title":"Common Patterns in Synchronization Problems","order":3,"content":null,"isLocked":true},{"id":"seed_f9803e1759315ad25a65959db1e9d9a2","title":"Solution Strategies for Synchronization Problems","order":4,"content":null,"isLocked":true}]}}