diff options
author | Carl Lerche <me@carllerche.com> | 2020-03-28 13:55:12 -0700 |
---|---|---|
committer | GitHub <noreply@github.com> | 2020-03-28 13:55:12 -0700 |
commit | caa7e180e43fdf914774de86f01f88e6b41f4a32 (patch) | |
tree | acd63c2a01e11f2c728f2d7527efafbc99c66132 /tokio/src/runtime/queue.rs | |
parent | 7b2438e7441e98b2a3f72eb239b1c51489b7d9b8 (diff) |
rt: cap fifo scheduler slot to avoid starvation (#2349)
The work-stealing scheduler includes an optimization where each worker
includes a single slot to store the **last** scheduled task. Tasks in
scheduler's LIFO slot are executed next. This speeds up and reduces
latency with message passing patterns.
Previously, this optimization was susceptible to starving other tasks in
certain cases. If two tasks ping-ping between each other without ever
yielding, the worker would never execute other tasks.
An early PR (#2160) introduced a form of pre-emption. Each task is
allocated a per-poll operation budget. Tokio resources will return ready
until the budget is depleted, at which point, Tokio resources will
always return `Pending`.
This patch leverages the operation budget to limit the LIFO scheduler
optimization. When executing tasks from the LIFO slot, the budget is
**not** reset. Once the budget goes to zero, the task in the LIFO slot
is pushed to the back of the queue.
Diffstat (limited to 'tokio/src/runtime/queue.rs')
-rw-r--r-- | tokio/src/runtime/queue.rs | 29 |
1 files changed, 0 insertions, 29 deletions
diff --git a/tokio/src/runtime/queue.rs b/tokio/src/runtime/queue.rs index 233fe454..81408135 100644 --- a/tokio/src/runtime/queue.rs +++ b/tokio/src/runtime/queue.rs @@ -13,9 +13,6 @@ use std::sync::atomic::Ordering::{AcqRel, Acquire, Release}; /// Producer handle. May only be used from a single thread. pub(super) struct Local<T: 'static> { inner: Arc<Inner<T>>, - - /// LIFO slot. Cannot be stolen. - next: Option<task::Notified<T>>, } /// Consumer handle. May be used from many threads. @@ -96,7 +93,6 @@ pub(super) fn local<T: 'static>() -> (Steal<T>, Local<T>) { let local = Local { inner: inner.clone(), - next: None, }; let remote = Steal(inner); @@ -110,26 +106,6 @@ impl<T> Local<T> { !self.inner.is_empty() } - /// Returns true if the queue has an unstealable entry. - pub(super) fn has_unstealable(&self) -> bool { - self.next.is_some() - } - - /// Push a task to the local queue. Returns `true` if a stealer should be - /// notified. - pub(super) fn push(&mut self, task: task::Notified<T>, inject: &Inject<T>) -> bool { - let prev = self.next.take(); - let ret = prev.is_some(); - - if let Some(prev) = prev { - self.push_back(prev, inject); - } - - self.next = Some(task); - - ret - } - /// Pushes a task to the back of the local queue, skipping the LIFO slot. pub(super) fn push_back(&mut self, mut task: task::Notified<T>, inject: &Inject<T>) { let tail = loop { @@ -270,11 +246,6 @@ impl<T> Local<T> { /// Pops a task from the local queue. pub(super) fn pop(&mut self) -> Option<task::Notified<T>> { - // If a task is available in the FIFO slot, return that. - if let Some(task) = self.next.take() { - return Some(task); - } - let mut head = self.inner.head.load(Acquire); let idx = loop { |