# Design a Multi-Producer Multi-Consumer Circular Buffer Design a fixed-capacity circular buffer shared by multiple producer and consumer threads. Producers append items, consumers remove the oldest item, producers block while the buffer is full, and consumers block while it is empty. Include a close operation that wakes waiters, rejects future writes, and lets consumers drain buffered items. Describe the in-memory layout, index arithmetic, synchronization, linearization points, timeout or cancellation behavior, and a testing strategy. A correct lock-based design is sufficient; if you propose a lock-free design, explain its memory-ordering and reclamation requirements. ### Constraints & Assumptions - Capacity is fixed and positive. - Multiple producers and consumers can call the API at exactly the same time. - Slots may hold arbitrary values and must not use a normal value as a close sentinel. - Operations must not lose, duplicate, or return an item before its producer publishes it. ### Clarifying Questions to Ask - Is strict FIFO across all producers required? - Should operations block, return immediately, or support both modes and deadlines? - Is strict fairness among waiting threads required? - What close and drain semantics do callers expect? ### What a Strong Answer Covers - Correct head, tail, and count invariants including wraparound - Publication and removal protected by a clear synchronization boundary - Condition waits that handle spurious wakeups and close - Trade-offs between a simple mutex design and lock-free MPMC algorithms - Deterministic wraparound and race-focused tests ### Follow-up Questions - Why is `head == tail` insufficient to distinguish full from empty by itself? - When may a producer safely make a slot visible to consumers? - How would false sharing affect a high-throughput implementation? - What additional mechanism is needed for at-least-once task processing?