Each queue has its own mutex (or better, use N lock free queues), but they would all share a single signaling object. As signaling is the slow path and it is rare, it is fine to contend in that case. You can't use a condition variable directly, but can build an event signaling object on top of a condvar and (another) mutex.