Design a Thread-Safe Bounded MPMC Queue with Timeouts and Fairness

Context

You are building a reusable, in-memory, bounded queue that supports multiple producers and multiple consumers (MPMC). Operations must block with timeouts, avoid deadlocks and starvation, and be fair under contention.

Requirements

• Provide a bounded queue with capacity N.
• Support blocking operations with timeouts:
  1. enqueue(item, deadline) → true on success; false on timeout.
  2. dequeue(deadline) → item on success; timeout error/null on timeout.
• Ensure:
  • Thread safety with many producers and consumers.
  • No deadlocks.
  • No starvation; enforce fairness under contention.
  • Backpressure when the queue is full.
• Discuss:
  • Locking strategy (mutexes vs. lock-free).
  • Condition/signaling mechanisms.
  • Backpressure policy.
  • Testing strategy for correctness and performance.
  • Time and space complexity.

Assumptions

• Language/runtime provides mutexes, condition variables, and monotonic clocks for timeouts.
• Capacity N ≥ 1; item copy/move is safe and does not invoke user code while locks are held.
• If needed, define a close()/shutdown() method to wake waiters and terminate gracefully.