Today in class we studied wait queues in Linux and something interesting came up when talking about exclusive/non-exclusive waits.
A question was asked: What happens if a wait-queue has some processes waiting in the exclusive state and others in the non-exclusive state.
The lecturer replied that the wake_up() will traverse the queue, waking up all non-exclusive processes, until it encounters an exclusive one, and then it will just wake that last process up and stop.
For example: Let N, E, represent a non-exclusive and exclusive process in the wait queue, respectively:
N - N - N - E - N - E - N - N
The lecturer claimed that the first 4 waits will be woken up (N-N-N-E) and the kernel will stop traversing after the first E.
This sounded weird, since E is exclusive, meaning it doesn't want to be woken up with anyone else, and in this case it is woken up with others.
Googling the question yielded the following:
When a wait queue is “woken up” all tasks on the wait queue are enabled for the scheduler. If a task is added to a wait queue using an exclusive function then the wake up call will only wake up one exclusive task leaving the others still waiting. If a mixture of exclusive tasks and non exclusive tasks are added to the queue then the wake up function will wake up any non exclusive tasks until it wakes up the exclusive task. The wakeup order is normally the reverse of the order in which tasks are added to the queue. https://blackfin.uclinux.org/doku.php?id=linux-kernel:wait_queues
Which one is correct? Is the real answer something entirely different?
NOTE: In class we are talking about Linux2.4.18-14, i386 (please comment if additional info is needed on the system)
N - N - N - E - N - E - N - N
The first thing to note is that entries that are WQ_FLAG_EXCLUSIVE are added to the end of the queue instead of at the beginning. So, the cited example never occurs; wait queues are always sorted: all Ns, then all Es.
since E is exclusive, meaning it doesn't want to be woken up with anyone else, and in this case it is woken up with others
The second thing to note is that exclusive waiters don't want to be woken up with other exclusive waiters. Presumptively, non-exclusive waiters are performing entirely non-overlapping jobs, while exclusive waiters are doing related jobs--perhaps they all require the same shared resource, so waking them all would cause a "thundering herd" as they all try for the same lock.
Thus, what you found via Google is correct. Most of what you were told is also correct, namely that Linux stops after waking the first exclusive waiter it finds. The suggestion that the wait queue is unsorted by exclusivity was not correct, however.