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.

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.