Producer - multiple consumer implementation using futures
I notice several things.

You have a data race on the shared queue. The consumer has an unsynchronized access to the nonEmpty property.

The notifyAll after you removed an element from the queue is unnecessary. Consumers shouldn't care about other consumers removing items.

But the main problem, which is suspect is the source of your deadlocks, is the race condition between the producer and the consumers. Here's what I think happens:


The producer produces the last item. It notifies all threads, releases the lock, but is preempted before setting the promise.
Consumer C1 wakes up, sees the queue is non-empty and grabs the element. It notifies all threads, releases the lock, and goes out to add the element to its list.
The other consumers wake up, see that the queue is empty but the promise is not set, and go back to sleep.
The producer sets the promise.
Consumer C1 sees that the promise is set and terminates.
The other consumers continue sleeping for all eternity.


To solve this, you need to notifyAll after you've set the promise. You can also probably optimize the whole thing by only calling notifyOne after adding an element.