class WaitQueueCollection

A WaitQueueCollection is the data structure which holds a collection of

threads which are currently blocked in a wait queue. The data structure

imposes a total ordering on the threads meant to represent the order in which

the threads should be woken, from "most important" to "least important".

One unusual property of the ordering implemented by a WaitQueueCollection is

that, unlike an ordering determined completely by properties such as thread

priority or weight, it is dynamic with respect to time. This is to say that

while at any instant in time there is always a specific order to the threads,

as time advances, this order can change. The ordering itself is determined

by the nature of the various dynamic scheduling disciplines implemented by

the Zircon scheduler.

At any specific time |now|, the order of the collection is considered to

be:

1) The deadline threads in the collection whose absolute deadlines are in the

future, sorted by ascending absolute deadline. These are the threads who

still have a chance of meeting their absolute deadline, with the nearest

absolute deadline considered to be the most important.

2) The deadline threads in the collection whose absolute deadlines are in the

past, sorted by ascending relative deadline. These are the threads who

have been blocked until after their last cycle's absolute deadline. If

all threads were to be woken |now|, the thread with the minimum relative

deadline would be the thread which has the new absolute deadline across

the set.

3) The fair threads in the collection, sorted by their "virtual finish time".

This is equal to the start time of the thread plus the scheduler's maximum

target latency divided by the thread's weight (normalized to the range

(0.0, 1.0]. This is the same ordering imposed by the Scheduler's RunQueue

for fair threads, and is intended to prioritize higher weight threads,

while still ensuring some level of fairness over time. The start time

represents the last time that a thread entered a run queue, and while high

weight threads will be chosen before low weight threads who arrived at

similar times, threads who arrived earlier (and have been waiting for

longer) will eventually end up being chosen, no matter how much weight

other threads in the collection have compared to it.

TODO(johngro): Instead of using the start time for the last time a

thread entered a RunQueue, should we use the time at which the thread

joined the wait queue instead?

In an attempt to make the selection of the "best" thread in a wait queue as

efficient as we can, in light of the dynamic nature of the total ordering, we

use an "augmented" WAVL tree as our data structure, much like the scheduler's

RunQueue. The tree keeps all of its threads sorted according to a primary

key representing the minimum absolute deadline or a modified version its

virtual finish time, depending on the thread's scheduling discipline).

The virtual finish time of threads is modified so that the MSB of the time is

always set. This guarantees that fair threads _always_ come after in the

sorting of threads. Note that we could have also achieved this partitioning

by tracking fair threads separately from deadline thread in a separate tree

instance. We keep things in a single tree (for now) in order to help to

minimize the size of WaitQueueCollections to help control the size of objects

in the kernel (such as the Mutex object).

There should be no serious issue with using the MSB of the sort key in this

fashion. Absolute timestamps in zircon use signed 64 bit integers, and the

monotonic clock is set at startup to start from zero, meaning that there is

no real world case where we would be searching for a deadline thread to

wake using a timestamp with the MSB set.

Finally, we also maintain an addition augmented invariant such that: For

every node (X) in the tree, the pointer to the thread with the minimum

relative deadline in the subtree headed by X is maintained as nodes are

inserted and removed.

With these invariants in place, finding the best thread to run can be

computed as follows.

1) If the left-most member of the tree has the MSB of its sorting key set,

then the thread is a fair thread, and there are _no_ deadline threads in

the tree. Additionally, this thread has the minimum virtual finish time

across all of the fair threads in the tree, and therefore is the "best"

thread to unblock. When the tree is in this state, selection is O(1).

2) Otherwise, there are deadline threads in the tree. The tree is searched

to find the first thread whose absolute deadline is in the future,

relative to |now|. If such a thread exists, then it is the "best" thread

to run right now and it is selected. When the tree is in this state,

selection is O(log).

3) If there are no threads whose deadlines are in the future, the pointer to

the thread with the minimum relative deadline in the tree is chosen,

simply by fetching the best-in-subtree pointer maintained in |root()|.

While this operation is O(1), when the tree is this state, the over all

achieved order was O(log) because of the search which needed to happen

during step 2.

Insert and remove order for the tree should be:

1) Insertions into the tree are always O(log).

2) Unlike a typical WAVL tree, removals of a specific thread from the tree

are O(log) instead of being amortized constant. This is because of the

cost of restoring the augmented invariant after removal, which involves

walking from the point of removal up to the root of the tree.