Katkat
Back

Implement a Thread-Safe Bounded Blocking Queue for Producers and Consumers

AppleSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Implement a thread-safe bounded blocking queue shared by multiple producer and consumer threads, built from a mutex and condition variables instead of a library concurrent queue. Tests wait and wakeup logic, spurious wakeups, FIFO ordering, shutdown handling and the OS mechanisms beneath blocking synchronization.

You are asked to implement a queue that producer threads and consumer threads share. Producers add items, consumers remove them in first-in, first-out order, and any number of producers and consumers may call the queue at the same time. A thread that cannot make progress must wait without burning CPU. The point of the exercise is the synchronization, so build the queue yourself from basic primitives.

Whether the queue is bounded was not stated. Assume a fixed capacity given at construction unless the interviewer says otherwise, and this interface:

BlockingQueue(capacity)
put(item) -> None # waits while the queue is full, then appends item at the tail
take() -> item # waits while the queue is empty, then removes and returns the head

Use a mutex and condition variables, or your language's equivalent monitor primitives. Wrapping a ready-made concurrent or blocking queue from a library would skip the exercise.

Constraints and Clarifications

  • capacity is a positive integer fixed at construction.
  • Items leave in the order they arrived.
  • No busy-waiting: a blocked thread sleeps until it can make progress.
  • Apart from waiting, put and take should take constant time.

Clarifying Questions

  • Is the queue bounded? If so, should put on a full queue block, fail immediately, or drop an item?
  • Do callers need timed variants, such as offer(item, timeout) and poll(timeout)?
  • Is there a shutdown path, so that consumers blocked on an empty queue can exit?
  • Which language and threading library should the implementation use?

Hints

Hint 1

What each side waits for: Producers and consumers wait for different events. Work out what each side is waiting for, and which operation should wake it.

Hint 2

Waking up is not a guarantee: A thread that returns from a wait may find that the condition it waited for no longer holds. Decide what it must do before it touches the buffer.

Follow-up questions

  • Add `offer(item, timeout)` and `poll(timeout)`. How do you keep the total wait bounded when a thread wakes up early?
  • Add `close()`: consumers should drain what remains and then stop, and producers should fail fast. What changes in the wait loops?
  • With a single condition variable shared by producers and consumers and a signal-one call, construct an interleaving in which every thread ends up asleep.
  • One well-known design uses a single lock for both ends of the queue; another uses separate locks for `put` and `take`. What does the two-lock design gain, and what keeps it correct?