What is the best way to wait on multiple condition variables in C++11?

You ask,

What is the best way to wait on multiple condition variables in C++11?

You can't, and must redesign. One thread may wait on only one condition variable (and its associated mutex) at a time. In this regard the Windows facilities for synchronization are rather richer than those of the "POSIX-style" family of synchronization primitives.

The typical approach with thread-safe queues is to enqueue a special "all done!" message, or to design a "breakable" (or "shutdown-able") queue. In the latter case, the queue's internal condition variable then protects a complex predicate: either an item is available or the queue has been broken.

In a comment you observe that

a notify_all() will have no effect if there is no one waiting

That's true but probably not relevant. wait()ing on a condition variable also implies checking a predicate, and checking it before actually blocking for a notification. So, a worker thread busy processing a queue item that "misses" a notify_all() will see, the next time it inspects the queue condition, that the predicate (a new item is available, or, the queue is all done) has changed.

Recently I resolved this issue with the help of single condition variable and separate Boolean variable for each producer/worker. The predicate within the wait function in consumer thread can check for these flags and take the decision which producer/worker has satisfied the condition.

Maybe this can works:

get rid of interrupt.

 message wait_and_pop(std::condition_variable& interrupt) {    std::unique_lock<std::mutex> lock(mutex);    {        new_msg_notification.wait(lock,[&]{            return !queue.empty() || stop;        });        if( !stop )        {            auto msg(std::move(queue.front()));            queue.pop();            return msg;        }        else        {            return NULL; //or some 'terminate' message        }}

In destructor, replace interrupt.notify_all() with new_msg_notification.notify_all()