Level 4 · Expert· Lesson 7 of 9 · 45 min
Async internals: build an executor
The Future contract, wakers and RawWaker, a leaf future backed by a timer thread, and a complete multi-task executor in a hundred lines.
async/await is syntax over a small, precise protocol. This lesson implements both sides of it — a future that waits for a timer, and an executor that runs many tasks — using only the standard library. After it, Tokio is no longer magic.
The contract
pub trait Future {
type Output;
fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>;
}
Rules every implementation and every caller must respect:
pollmust return quickly. It makes whatever progress is possible without blocking.- If it returns
Poll::Pending, it must have arranged forcx.waker()— the waker from this call — to be woken when progress becomes possible. - After
Poll::Ready, the future must not be polled again. - Spurious polls are allowed: a future must tolerate being polled without having been woken.
- Wake-ups may arrive from any thread, at any time, including during
poll. A waker isSend + Sync + Clone.
The executor’s side: poll a task when it is woken, and not otherwise.
What async compiles to
async fn add_slowly(a: u32, b: u32) -> u32 {
let x = step(a).await; // suspension point 1
let y = step(b).await; // suspension point 2
x + y
}
async fn step(n: u32) -> u32 { n }
The compiler turns this into, roughly, an enum with one variant per suspension point, each holding the variables that are live across it:
enum AddSlowly {
Start { a: u32, b: u32 },
AwaitingFirst { b: u32, fut: Step },
AwaitingSecond { x: u32, fut: Step },
Done,
}
poll is a match on the state that polls the inner future, and either returns Pending (staying in the same state) or stores the result and falls through to the next state. Consequences you can now explain:
- The future’s size is the largest set of locals live across any await — a big array held across an await bloats the whole task.
- A recursive
async fnwould have infinite size; it must box (Box::pin) the recursive call. - A reference to a local held across an await makes the struct self-referential, hence
Pin. - The future is
Sendonly if everything held across an await isSend.
A leaf future
Combinators and async blocks only delegate. At the bottom there must be leaf futures that integrate with an event source and call the waker. Real runtimes use a reactor over epoll, kqueue or IOCP. Ours uses a thread:
use std::future::Future;
use std::pin::Pin;
use std::sync::{Arc, Mutex};
use std::task::{Context, Poll, Waker};
use std::thread;
use std::time::Duration;
struct Shared {
done: bool,
waker: Option<Waker>,
}
pub struct Sleep {
shared: Arc<Mutex<Shared>>,
}
impl Sleep {
pub fn new(duration: Duration) -> Self {
let shared = Arc::new(Mutex::new(Shared { done: false, waker: None }));
let for_thread = Arc::clone(&shared);
thread::spawn(move || {
thread::sleep(duration);
let mut s = for_thread.lock().unwrap();
s.done = true;
if let Some(waker) = s.waker.take() {
waker.wake(); // tell the executor: poll that task again
}
});
Sleep { shared }
}
}
impl Future for Sleep {
type Output = ();
fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
let mut s = self.shared.lock().unwrap();
if s.done {
return Poll::Ready(());
}
// Always store the waker from the most recent poll.
match &s.waker {
Some(w) if w.will_wake(cx.waker()) => {}
_ => s.waker = Some(cx.waker().clone()),
}
Poll::Pending
}
}
fn main() {
// Drive it by hand with a waker that does nothing, to see the protocol.
let mut sleep = std::pin::pin!(Sleep::new(Duration::from_millis(50)));
let mut cx = Context::from_waker(Waker::noop());
println!("first poll: {:?}", sleep.as_mut().poll(&mut cx));
thread::sleep(Duration::from_millis(100));
println!("second poll: {:?}", sleep.as_mut().poll(&mut cx));
}
The lock closes a race: the timer thread sets done and takes the waker under the same mutex in which poll checks done and stores the waker. Without it, the wake-up could fall between the check and the store and be lost forever — the classic lost wake-up.
block_on: the smallest executor
To run one future to completion, poll it, and park the thread until its waker fires:
use std::future::Future;
use std::pin::pin;
use std::sync::Arc;
use std::task::{Context, Poll, Wake, Waker};
use std::thread::{self, Thread};
struct ThreadWaker(Thread);
impl Wake for ThreadWaker {
fn wake(self: Arc<Self>) {
self.0.unpark();
}
}
pub fn block_on<F: Future>(future: F) -> F::Output {
let mut future = pin!(future);
let waker = Waker::from(Arc::new(ThreadWaker(thread::current())));
let mut cx = Context::from_waker(&waker);
loop {
match future.as_mut().poll(&mut cx) {
Poll::Ready(value) => return value,
Poll::Pending => thread::park(), // sleep until wake() unparks us
}
}
}
fn main() {
let answer = block_on(async {
let a = async { 40 }.await;
a + 2
});
println!("{answer}");
}
std::task::Wake builds a Waker from an Arc<impl Wake>. Underneath, a Waker is a RawWaker: a data pointer plus a hand-written vtable of four functions (clone, wake, wake_by_ref, drop) — a manual trait object, so that executors can avoid Arc when they need to, as embedded ones do. thread::park tolerates an unpark that arrives first, so there is no lost wake-up here either.
A multi-task executor
Now the real thing: many tasks, a run queue, and spawn. A task owns its future; its waker pushes the task back onto the queue.
use std::future::Future;
use std::pin::Pin;
use std::sync::mpsc::{channel, Receiver, Sender};
use std::sync::{Arc, Mutex};
use std::task::{Context, Poll, Wake, Waker};
use std::thread;
use std::time::{Duration, Instant};
// ---------- the leaf future from above ----------
struct Shared { done: bool, waker: Option<Waker> }
struct Sleep { shared: Arc<Mutex<Shared>> }
impl Sleep {
fn new(d: Duration) -> Self {
let shared = Arc::new(Mutex::new(Shared { done: false, waker: None }));
let t = Arc::clone(&shared);
thread::spawn(move || {
thread::sleep(d);
let mut s = t.lock().unwrap();
s.done = true;
if let Some(w) = s.waker.take() { w.wake(); }
});
Sleep { shared }
}
}
impl Future for Sleep {
type Output = ();
fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
let mut s = self.shared.lock().unwrap();
if s.done { return Poll::Ready(()); }
s.waker = Some(cx.waker().clone());
Poll::Pending
}
}
// ---------- the executor ----------
type BoxFuture = Pin<Box<dyn Future<Output = ()> + Send>>;
struct Task {
/// `None` once the future has completed.
future: Mutex<Option<BoxFuture>>,
/// Where to send this task when it is woken.
queue: Sender<Arc<Task>>,
}
impl Wake for Task {
fn wake(self: Arc<Self>) {
// Waking = scheduling. If the executor is gone, there is nothing to do.
let _ = self.queue.send(Arc::clone(&self));
}
}
#[derive(Clone)]
struct Spawner {
queue: Sender<Arc<Task>>,
}
impl Spawner {
fn spawn(&self, future: impl Future<Output = ()> + Send + 'static) {
let task = Arc::new(Task {
future: Mutex::new(Some(Box::pin(future))),
queue: self.queue.clone(),
});
self.queue.send(task).expect("executor is running");
}
}
struct Executor {
ready: Receiver<Arc<Task>>,
}
fn new_executor() -> (Executor, Spawner) {
let (queue, ready) = channel();
(Executor { ready }, Spawner { queue })
}
impl Executor {
/// Runs until every task has finished and every Spawner and Waker has been dropped.
fn run(&self) {
while let Ok(task) = self.ready.recv() {
let mut slot = task.future.lock().unwrap();
if let Some(mut future) = slot.take() {
let waker = Waker::from(Arc::clone(&task));
let mut cx = Context::from_waker(&waker);
if future.as_mut().poll(&mut cx).is_pending() {
*slot = Some(future); // not done: keep it for the next wake-up
}
// If Ready, the future is dropped here and the task is finished.
}
}
}
}
fn main() {
let (executor, spawner) = new_executor();
let start = Instant::now();
for id in 1..=3u64 {
let inner = spawner.clone();
spawner.spawn(async move {
println!("[{:>3} ms] task {id} started", start.elapsed().as_millis());
Sleep::new(Duration::from_millis(100 * id)).await;
println!("[{:>3} ms] task {id} woke up", start.elapsed().as_millis());
if id == 3 {
// Tasks can spawn tasks.
inner.spawn(async move {
Sleep::new(Duration::from_millis(50)).await;
println!("[{:>3} ms] child of task 3 done", start.elapsed().as_millis());
});
}
});
}
drop(spawner); // so `run` can end once all tasks are done
executor.run();
println!("all tasks finished in {} ms on one thread", start.elapsed().as_millis());
}
Run it: three tasks sleep concurrently on a single executor thread, and the total is about 350 ms rather than the 650 ms a sequential run would need.
How termination works: the channel closes when every Sender is gone. Senders live in the Spawners and inside each Task — and a task stays alive only while it sits in the queue or some Waker (held by a timer thread) refers to it. When the last task completes, the last sender drops, recv returns Err, and run exits. Ownership does the bookkeeping.
From this to Tokio
Everything a production runtime adds is refinement of the pieces above:
| Our executor | A production runtime |
|---|---|
One thread draining an mpsc channel |
A pool of worker threads, each with a local queue, stealing work from each other |
Mutex<Option<BoxFuture>> per task |
One allocation holding header, future and output, with an atomic state word (idle / scheduled / running / complete) so that a wake during poll re-schedules exactly once |
| A thread per timer | A reactor: one epoll/kqueue/IOCP call waiting on all sockets, plus a hierarchical timer wheel; it stores wakers keyed by event source |
No JoinHandle |
The task’s output slot plus a second waker for whoever awaits the handle |
| Tasks run until they yield | Cooperative budgeting: a task that has done too much work is forced to yield so others are not starved |
Send futures only |
LocalSet / current-thread runtimes for !Send futures |
Design questions you can now reason about: Why must spawned futures be 'static? (The task outlives the spawning stack frame.) Why is wake() required to be cheap and non-reentrant? (It may be called from an interrupt handler or from inside poll.) Why do select! and join! on many futures re-poll all of them on any wake-up, and why does FuturesUnordered give each child its own waker instead?
Exercises
- Add a
JoinHandle<T>to the executor:spawnreturns a future that resolves to the task’s output. You need a shared slot withOption<T>andOption<Waker>. - Write
async fn yield_now()— a future that returnsPendingonce after callingcx.waker().wake_by_ref(). Use it to show two tasks interleaving. - Replace the thread-per-
Sleepwith one timer thread holding aBinaryHeap<(Instant, Waker)>— a miniature reactor. - Make the executor multi-threaded: share the receiver behind a
Mutexamong four worker threads. What must change so a task woken while it is being polled is not polled concurrently or lost? - Implement a
RawWakervtable by hand for theblock_onthread waker, withoutArc.
Check your understanding
Pick an answer to see the explanation.
1.What must a future do before returning
Poll::Pending?2.Why should a leaf future store the *latest* waker on every poll rather than only the first?
3.In the executor from this lesson, what does
wake()do?