My current understanding of conditional variables is that all blocked (waiting) threads are inserted into a basic FIFO queue, the first item of which is awakened when signal() is called.
Is there any way to modify this queue (or create a new structure) to perform as a priority queue instead? I've been thinking about it for a while, but most solutions I have end up being hampered by the existing queue structure inherent to C.V.'s and mutexes.
Thanks!
Since condition variables are basically just a barrier and you have no control over the queue of waiting threads there's no real way to apply priorities. It's invalid to assume waiting threads will act in a FIFO manner.
With a combination of atomics, additional condition variables, and pre-knowledge of the threads/priorities involved you could construct a solution where a signaled thread will re-signal the master CV and then re-block on a priority CV but it certainly wouldn't be a generic solution. That's also off the top of my head so might also have some other flaw.
It's the scheduler that determines which thread will run. You can look at pthread_setschedparam and pthread_getschedparam and fiddle with the policies (SCHED_OTHER, SCHED_FIFO, or SCHED_RR) and the priorities. But it probably won't get you to where I suspect you want to go.
It sounds as if you want to make something predictable from the inherently non-deterministic. As Andrew notes you might hack something but my guess is that this will lead to heartache or a lot code you will hate yourself for writing in six months (or both).
I think you should rethink what you're trying to do. If you're trying to optimize your performance, you're probably barking up the wrong tree.
pthread_cond_signal() isn't even guaranteed to unblock exactly one thread -- it's guaranteed to unblock at least one thread, so your code better be able to handle the situation where multiple threads are unblocked simultaneously. The typical way to do this is for each thread to re-check the condition after becoming unblocked, and, if false, return to waiting again.
You could implement some sort of scheme where you kept your own priority queue of threads waiting, and each thread added itself to that queue immediately before it was to begin waiting, and then it would check the queue when unblocking, but this would add a lot of complexity and a lot of potential for serious problems (race conditions, deadlocks, etc.). It was also add a non-trivial amount of overhead.
Also, what happens if a higher-priority thread starts waiting on a condition variable at the same moment that condition variable is being signalled? Who gets unblocked, the newly arrived high-priority thread or the former highest priority thread?
The order that threads get unblocked in is entirely dependent on the kernel's thread scheduler, so you are at its mercy. I wouldn't even assume FIFO ordering, either.