I've noticed a common pattern for implementing Futures that need to notify potentially multiple tasks, use a
Slab to keep track of the wakers. For example
Shared in futures-preview and
Mutex in async-std.
My first concern was that this uses iteration over the slab to find a
Waker to wake, and the slab documentation specifically says this should be avoided, since it has to iterate the whole slab of memory. But on further contemplation I realized that it is probably ok, since the number of slots in the slab will usually be very small.
My bigger concern came to me while I was working an implementing condition variable semantics for a future. Since iterating over a slab always begins at the beginning of the slab of memory the order tasks are awoken won't always be fair.
For example, suppose Task A currently holds the mutex, slot 0 is empty, Task B has a waker in slot 1 and Task C has a waker in slot 2, and the current size of the slab is three slots.
When Task A releases the lock, Task B is woken and slot 1 becomes available. If Task A tries to take the lock again it will put its waker in slot 1 and be the task woken after Task B releases the lock. If A and B are both continually contending over the lock, then Task C will never get woken (or at least may not be woken for a long time).
Am I missing something? Or does the current implementation suffer from task starvation?