Reducing atomic reference counting The final optimization we will discuss in this article is how the new scheduler reduces the amount of atomic reference counts needed. There are many outstanding references to the task structure: the scheduler and each waker hold a handle. A common way to manage this memory is to use atomic reference counting. This strategy requires an atomic operation each time a reference is cloned and an atomic operation each time a reference is dropped. When the final reference goes out of scope, the memory is freed. In the old Tokio scheduler, each waker held a counted reference to the task handle, roughly: struct Waker { task: Arc<Task>, } impl Waker { fn wake(&self) { let task = self.task.clone(); task.scheduler.schedule(task); } } When the task is woken, the reference is cloned (atomic increment). The reference is then pushed into the run queue. When the processor receives the task and is done executing it, it drops the reference resulting in an atomic decrement. These atomic operations add up. This problem has previously been identified by the designers of the std::future task system. It was observed that when Waker::wake is called, often times the original waker reference is no longer needed. This allows for reusing the atomic reference count when pushing the task into the run queue. The std::future task system now includes two "wake" APIs: wake which takes self wake_by_ref which takes &self. This API design pushes the caller to use wake which avoids the atomic increment. The implementation now becomes: impl Waker { fn wake(self) { task.scheduler.schedule(self.task); } fn wake_by_ref(&self) { let task = self.task.clone(); task.scheduler.schedule(task); } } This avoids the overhead of additional reference counting only if it is possible to take ownership of the waker in order to wake. In my experience, it is almost always desirable to wake with &self instead. Waking with self prevents reusing the waker (useful in cases where the resource sends many values, i.e. channels, sockets, ...) it also is more difficult to implement thread-safe waking when self is required (the details of this will be left to another article). The new scheduler side steps the entire "wake by self" issue by avoiding the atomic increment in wake_by_ref, making it as efficient as wake(self). This is done by having the scheduler maintain a list of all tasks currently active (have not yet completed). This list represents the reference count needed to push a task into the run queue. The difficulty with this optimization is to ensure that the scheduler will not drop any tasks from its list until it can be guaranteed that the task will not be pushed into the run queue again. The specifics of how this is managed are beyond the scope of this article, but I urge you to further investigate this in the source.

fn wake_by_ref(&self) {
    let task = self.task.clone();
    task.scheduler.schedule(task);
}

Reducing allocations The new Tokio scheduler requires only a single allocation per spawned task while the old one required two. Previously, the Task struct looked something like: struct Task { /// All state needed to manage the task state: TaskState, /// The logic to run is represented as a future trait object. future: Box<dyn Future<Output = ()>>, } The Task struct would then be allocated in a Box as well. This has always been a wart that I have wanted to fix for a long time (I first attempted to fix this in 2014). Since the old Tokio scheduler, two things have changed. First, std::alloc stabilized. Second, the Future task system switched to an explicit vtable strategy. These were the two missing pieces needed to finally get rid of the double allocation per task inefficiency. Now, the Task structure is represented as: struct Task<T> { header: Header, future: T, trailer: Trailer, } Both Header and Trailer are state needed to power the task, however they are split between "hot" data (header) and "cold" data (trailer), i.e. roughly data that is accessed often and data that is rarely used. The hot data is placed at the head of the struct and is kept as small as possible. When the CPU dereferences the task pointer, it will load a cache line sized amount of data at once (between 64 and 128 bytes). We want that data to be as relevant as possible.

/// 以未来特性对象表示的运行逻辑
future: Box<dyn Future<Output = ()>>,

Reducing cross thread synchronization The other critical piece of a work-stealing scheduler is sibling notification. This is where a processor notifies a sibling when it observes new tasks. If the sibling is sleeping, it wakes up and steals tasks. The notification action has another critical responsibility. Recall the queue algorithm used weak atomic orderings (Acquire / Release). Because of how atomic memory ordering work, without additional synchronization, there is no guarantee that a sibling processor will ever see tasks in the queue to steal. The notification action also is responsible for establishing the necessary synchronization for the sibling processor to see the tasks in order to steal them. These requirements make the notification action expensive. The goal is to perform the notification action as little as possible without resulting in CPU under utilization, i.e. a processor has tasks and a sibling is unable to steal them. Overeager notification results in a thundering herd problem. The original Tokio scheduler took a naive approach to notification. Whenever a new task was pushed on to the run queue, a processor was notified. Whenever a processor was notified and found a task upon waking, it would then notify yet another processor. This logic very quickly resulted in all processor getting woken up and searching for work (causing contention). Very often, most of these processors failed to find work and went back to sleep. The new scheduler significantly improves on this by borrowing the same technique used in the Go scheduler. Notification is attempted at the same points as the previous scheduler, however, notification only happens if there are no workers in the searching state (see previous section). When a worker is notified, it is immediately transitioned to the searching state. When a processor in the searching state finds new tasks, it will first transition out of the searching state, then notify another processor. This logic has the effect of throttling the rate at which processors wake up. If a batch of tasks is scheduled at once (for example, when epoll is polled for socket readiness), the first one will result in notifying a processor. That processor is now in the searching state. The rest of the scheduled tasks in the batch will not notify a processor as there is at least one in the searching state. That notified processor will steal half the tasks in the batch, and in turn notify another processor. This third processor will wake up, find tasks from one of the first two processors and steal half of those. This results in a smooth ramp up of processors as well as rapid load balancing of tasks.

To address this, the new Tokio scheduler implements an optimization (also found in Go's and Kotlin's schedulers). When a task transitions to the runnable state, instead of pushing it to the back of the run queue, it is stored in a special "next task" slot. The processor will always check this slot before checking the run queue. When inserting a task into this slot, if a task is already stored in it, the old task is removed from the slot and pushed to the back of the run queue. In the message passing case, this will result in the receiver of the message to be scheduled to run next.

The last missing piece is consuming the global queue. This queue is used to handle overflow from processor local queues as well as to submit tasks to the scheduler from non-processor threads. If a processor is under load, i.e. the local run queue has tasks. The processor will attempt to pop from the global after executing ~60 tasks from the local queue. It also checks the global queue when in the "searching" state, described below.

The steal function is similar to the pop function but the load from self.tail must be atomic. Also, similar to push_overflow, the steal operation will attempt to claim half of the queue instead of a single task. This has some nice characteristics which we will cover later.

The queue implementation is a circular buffer, using an array to store values. Atomic integers are used to track the head and tail positions.

If you are familiar with the details of atomic memory orderings, you might notice a potential "issue" with the push function as shown above. An atomic load with Acquire ordering is pretty weak. It may return stale values, i.e. a concurrent steal operation may have already incremented the value of self.head but the thread performing the push had an old value in the cache so it didn't notice the steal operation. This is not a problem for the correctness of the algorithm. In the fast-path of push, we only care if the local run queue is full or not. Given that the current thread is the only thread that can push into the run queue, a stale load will result in seeing the run queue as more full than it actually is. It may incorrectly determine that the queue is full and enter the push_overflow function, but this function includes a stronger atomic operation. If push_overflow determines the queue is not actually full, it returns w/ Err and the push operation tries again. This is another reason why push_overflow will move half of the run queue to the global queue. By moving half of the queue, the "run queue is empty" false positive is hit a lot less often.