Concerns about using slab to track Wakers

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 Mutex and 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?

1 Like

Interesting. Perhaps one should consider a VecDeque instead. I know it doesn't support easily removing wakers in the middle, but it might be okay to just let it stay until it is reached.