Build a Tiny Async Executor in Rust to See How Wakers Work
An executor is a loop that polls tasks when their wakers fire. Build one with the standard library alone and Tokio stops looking like magic.
This executor runs on the standard library only. It handles spawn on a single thread, a block_on sits beside it, and you can read all of it in one sitting, which is the point. Everything below was compiled and run on Rust 1.99, edition 2024, on an Apple M1 Max. Tokio 1.47.1 appears once, as the thing the executor is measured against. The post builds on the hand written futures in writing a future by hand, and it assumes you have met async and .await in async and await explained.
An async fn does nothing when you call it. It returns a value that implements Future, and that value sits there until somebody calls poll on it. The somebody is an executor. Everything that feels like magic about Tokio, the tasks that run "in the background", the sleeps that do not block a thread, comes from two small ideas: a loop that polls futures, and a handle called a waker that tells the loop when to poll a particular future again. Build those two and the rest is engineering.
What poll and wake actually promise
The Future trait has one method. poll takes a pinned mutable reference to the future and a Context, and returns either Poll::Ready(value) or Poll::Pending. The contract that matters sits in the second case. If a future returns Pending, it promises that it has arranged for the context's waker to be called when it might make progress. Break that promise and the future is never polled again. The executor will not guess, because guessing means polling in a loop, which is the busy wait that async exists to avoid (futures as state machines shows what the compiler generates behind each await).
So an executor needs three things. A place to keep futures that are not finished. A way to learn which of them to poll next. And a way to build a Waker for each future that feeds that second answer. In this design all three live in one small struct.
The design
- A Task owns its future in a
Mutex<Option<Pin<Box<dyn Future>>>>and holds a sender to the ready queue. - Waking a task sends a clone of its
Arcback to the queue. That is allwakedoes. - The run loop receives tasks from the queue and polls each one once, with a waker built from the task itself.
The queue is the scheduler. There is no list of "pending tasks" anywhere; a task that is waiting is simply one that nobody has put in the queue yet. That inversion is what makes the design small. The executor does not track what is blocked on what. The thing that unblocks a task is responsible for saying so.
The code
use std::future::Future;
use std::pin::Pin;
use std::sync::mpsc::{Receiver, SyncSender, sync_channel};
use std::sync::{Arc, Mutex};
use std::task::{Context, Poll, Wake, Waker};
type BoxFuture = Pin<Box<dyn Future<Output = ()> + Send + 'static>>;
struct Task {
future: Mutex<Option<BoxFuture>>,
queue: SyncSender<Arc<Task>>,
}
impl Wake for Task {
fn wake(self: Arc<Self>) {
let again = Arc::clone(&self);
let _ = self.queue.send(again);
}
}
pub struct Executor {
ready: Receiver<Arc<Task>>,
}
#[derive(Clone)]
pub struct Spawner {
queue: SyncSender<Arc<Task>>,
}
pub fn new_executor() -> (Executor, Spawner) {
let (tx, rx) = sync_channel(1024);
(Executor { ready: rx }, Spawner { queue: tx })
}
impl Spawner {
pub fn spawn(&self, fut: impl Future<Output = ()> + Send + 'static) {
let task = Arc::new(Task {
future: Mutex::new(Some(Box::pin(fut))),
queue: self.queue.clone(),
});
self.queue.send(task).expect("queue full");
}
}
impl Executor {
pub fn run(self) {
while let Ok(task) = self.ready.recv() {
let mut slot = task.future.lock().unwrap();
if let Some(mut fut) = slot.take() {
let waker = Waker::from(Arc::clone(&task));
let mut cx = Context::from_waker(&waker);
if fut.as_mut().poll(&mut cx).is_pending() {
*slot = Some(fut);
}
}
}
}
}Walk through it from the top. BoxFuture is a heap allocated, pinned, type erased future. It is boxed because tasks of different types have to live in one queue, and pinned because an async block can hold references into its own state and must not be moved once polled. Putting it in a Box and never moving the box satisfies that, and Box::pin is how you say so (pin, Box and dyn Future). The Send + 'static bound is not decoration; the next section shows what it protects.
The future sits in an Option so that a finished task can be emptied, and in a Mutex because wake can run on any thread while run is polling. In this single threaded loop the mutex is never contended, but without it the compiler cannot prove that a Task is safe to share through an Arc, and the Wake trait requires it.
impl Wake for Task is the whole waker machinery. The standard library turns any Arc<impl Wake> into a Waker with no unsafe code and no hand written vtable, which is how it was done before Wake stabilised. wake takes the Arc by value, clones it so a second owner exists, and sends that clone into the queue. The send result is ignored on purpose: if the executor has already stopped, the receiver is gone and there is nobody left to wake.
run is the loop. It takes a task out of the queue, locks the future slot, and takes the future out of the Option. If the slot was already empty, the task finished earlier and this is a stale wake, which is harmless and skipped. Otherwise it builds a waker with Waker::from(Arc::clone(&task)), wraps it in a Context and polls. A Pending result puts the future back in the slot. A Ready result drops it, and the task disappears once the last Arc is gone.
Running it
To see the scheduling, a future that is pending exactly once is enough. Yield returns Pending on its first poll after calling wake_by_ref on its own waker, and Ready on the second. It asks to be polled again immediately, which puts its task at the back of the queue. That is what tokio::task::yield_now does.
struct Yield(bool);
impl Future for Yield {
type Output = ();
fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
if self.0 {
Poll::Ready(())
} else {
self.0 = true;
cx.waker().wake_by_ref();
Poll::Pending
}
}
}
fn main() {
let (executor, spawner) = new_executor();
for id in 0..3 {
spawner.spawn(async move {
println!("task {id} start");
Yield(false).await;
println!("task {id} end");
});
}
drop(spawner);
executor.run();
println!("run() returned");
}task 0 start
task 1 start
task 2 start
task 0 end
task 1 end
task 2 end
run() returnedEach task runs to its first Yield, goes to the back of the queue, and the three tasks interleave. Nothing was written to make that happen. The tasks were queued 0, 1, 2; each yields and is queued again behind the others; so each runs its second half in the same order. run returns when the queue is empty and every sender has been dropped. Tasks hold a sender each, so the channel closes only after the last task is finished and the spawner handle was dropped, which is why drop(spawner) sits before executor.run(). Leave it out and run waits forever for work that cannot arrive.
A failing example: why spawn wants 'static
The 'static bound on spawn is the first thing that stops people writing their own. This program borrows a local string from a spawned block:
use std::future::Future;
fn spawn(_fut: impl Future<Output = ()> + Send + 'static) {}
fn main() {
let name = String::from("worker");
spawn(async {
println!("hello from {name}");
});
}I replaced the executor with a bare function with the same signature so the error is the only thing on screen. The compiler says:
error[E0373]: async block may outlive the current function, but it borrows `name`, which is owned by the current function
--> src/bin/e2_fail.rs:7:11
|
7 | spawn(async {
| ^^^^^ may outlive borrowed value `name`
8 | println!("hello from {name}");
| ---- `name` is borrowed here
|
= note: async blocks are not executed immediately and must either take a reference or ownership of outside variables they use
help: to force the async block to take ownership of `name` (and any other referenced variables), use the `move` keyword
|
7 | spawn(async move {
| ++++The reason is in the design above, not in the compiler's taste. A spawned future is stored in a queue that outlives the call to spawn, and nothing says when it will be polled. If it borrowed name, the function could return and free the string while the task still sat in the queue. The compiler can only prove soundness if the task owns everything it needs. The fix the message suggests, async move, is right here, since the block then owns name. When two tasks need the same value, put it in an Arc and clone it into each (why spawn needs a 'static future covers the same rule in Tokio, with more ways out).
Following one task through the loop
It helps to trace the demo by hand, because the executor has no state beyond the queue and the tasks. Call the tasks A, B and C. After the three spawn calls the queue holds [A, B, C] and no task has been polled. run receives A, locks its slot, takes the future out and polls it. The future prints "task 0 start", awaits Yield, and Yield calls wake_by_ref on the waker it was given. That waker is the Arc<Task> for A, so wake sends a clone of A into the queue, which is now [B, C, A]. Then Yield returns Pending, the poll returns Pending, and run puts the future back in A's slot.
B and C do the same, leaving [A, B, C] again with each future one step further along. The second round polls A, whose Yield now returns Ready, the async block prints "task 0 end" and finishes, and run leaves the slot empty. When the last task is done, the only Arc handles left are the ones that went through the loop, they are dropped, the senders go with them, and recv returns an error that ends the while let.
Two details are easy to miss. First, wake happens while the future is being polled, so the queue entry can arrive before the poll has returned. That is fine here: the entry waits in the queue, and by the time run receives it, the previous poll has finished and put the future back. A multi thread executor has to do real work to keep this safe, because another worker could receive the entry while the first is still inside poll. The mutex around the slot is what makes that case correct. The second worker blocks on the lock until the first is done, then finds the future back in place.
Second, the same task can be in the queue twice. Two wake calls between polls put two entries in; the second poll finds either a future that is ready or one that is still waiting and returns Pending again. A spurious poll is allowed by the contract and costs one call. This is why a future must tolerate being polled when it has nothing new to do, and why the code in Sleep below checks done on every poll instead of assuming it was woken for a reason.
Why Wake::wake takes Arc<Self> by value deserves a line as well. A waker is a handle that is cloned freely and may outlive the poll it was created in; some leaf future stores it for later. Taking the Arc by value lets a waker that is used once be consumed without an extra clone, while wake_by_ref, which has a default implementation that clones and calls wake, serves the case where the caller keeps its handle. Implementing wake_by_ref yourself is a small optimisation that avoids one atomic increment per wake.
Parking the thread: block_on
The queue based loop above has no way to wait for the outside world. A channel receive is a blocking call, and nothing yet turns a timer firing into a wake. The next step is the small cousin of the executor, block_on, which runs one future to completion on the current thread. It also gives us a real source of wake ups: a helper thread that calls the waker when a delay is up.
use std::future::Future;
use std::pin::pin;
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
use std::sync::{Arc, Mutex};
use std::task::{Context, Poll, Wake, Waker};
use std::thread::{self, Thread};
use std::time::{Duration, Instant};
struct ThreadWaker(Thread);
impl Wake for ThreadWaker {
fn wake(self: Arc<Self>) {
self.0.unpark();
}
}
fn block_on<F: Future>(fut: F) -> F::Output {
let mut fut = pin!(fut);
let waker = Waker::from(Arc::new(ThreadWaker(thread::current())));
let mut cx = Context::from_waker(&waker);
loop {
match fut.as_mut().poll(&mut cx) {
Poll::Ready(v) => return v,
Poll::Pending => thread::park(),
}
}
}
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 s = Arc::clone(&shared);
thread::spawn(move || {
thread::sleep(d);
let mut s = s.lock().unwrap();
s.done = true;
if let Some(w) = s.waker.take() {
w.wake();
}
});
Sleep { shared }
}
}
static POLLS: AtomicUsize = AtomicUsize::new(0);
impl Future for Sleep {
type Output = ();
fn poll(self: std::pin::Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
POLLS.fetch_add(1, Ordering::Relaxed);
let mut s = self.shared.lock().unwrap();
if s.done {
Poll::Ready(())
} else {
s.waker = Some(cx.waker().clone());
Poll::Pending
}
}
}
struct Spin(Arc<AtomicBool>);
impl Future for Spin {
type Output = ();
fn poll(self: std::pin::Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
POLLS.fetch_add(1, Ordering::Relaxed);
if self.0.load(Ordering::Relaxed) {
Poll::Ready(())
} else {
cx.waker().wake_by_ref();
Poll::Pending
}
}
}
fn main() {
let t = Instant::now();
block_on(Sleep::new(Duration::from_millis(200)));
println!("slept {:?} ms in {} polls", t.elapsed().as_millis(), POLLS.swap(0, Ordering::Relaxed));
let flag = Arc::new(AtomicBool::new(false));
let f = Arc::clone(&flag);
thread::spawn(move || {
thread::sleep(Duration::from_millis(200));
f.store(true, Ordering::Relaxed);
});
let t = Instant::now();
block_on(Spin(flag));
println!("spun {:?} ms in {} polls", t.elapsed().as_millis(), POLLS.load(Ordering::Relaxed));
}Three pieces to read. ThreadWaker is a Wake whose wake calls unpark on a saved thread handle. block_on pins the future on the stack with pin!, polls it, and on Pending calls thread::park(), which sleeps with no CPU use until someone unparks the thread. Sleep is a timer made from the simplest ingredients: a helper thread sleeps for the duration, sets done, and calls the stored waker. The future stores a clone of the waker from its context on every pending poll, since the waker handed in may differ from poll to poll and the freshest one is the one to call.
The second future, Spin, is the lazy alternative. It never stores a waker for later; it calls wake_by_ref before returning Pending, so the executor re-polls it at once. The program runs both for 200 milliseconds and counts how many times poll was called:
slept 203 ms in 2 polls
spun 204 ms in 6281024 pollsBoth waited the same time, within a few milliseconds of the 200 requested. The properly woken future was polled twice: once to start the timer and return Pending, once after the timer thread woke it. The spinning one was polled 6,281,024 times in the same interval, and it kept a core at 100 percent the whole time. The difference is the entire reason wakers exist, and it is a number you can reproduce on your own machine. A future that spins and a future that registers a waker produce the same output; only one of them costs anything while it waits.
The parked thread also makes an invariant visible. unpark has a token: if it is called before park, the next park returns immediately. That is what makes the loop free of a race. If the timer thread fires between the poll returning Pending and the call to park, the wake is not lost. This is the same property a real executor needs from its own wake path, and it is why waking is allowed to happen from any thread at any moment.
The opposite failure: a future that forgets the waker
The contract fails in the other direction too. A future that returns Pending and does not arrange a wake leaves the executor parked for ever:
use std::future::Future;
use std::pin::{Pin, pin};
use std::sync::Arc;
use std::task::{Context, Poll, Wake, Waker};
use std::thread::{self, Thread};
use std::time::Duration;
struct ThreadWaker(Thread);
impl Wake for ThreadWaker {
fn wake(self: Arc<Self>) {
self.0.unpark();
}
}
struct Forgetful;
impl Future for Forgetful {
type Output = ();
fn poll(self: Pin<&mut Self>, _cx: &mut Context<'_>) -> Poll<()> {
Poll::Pending
}
}
fn main() {
thread::spawn(|| {
thread::sleep(Duration::from_secs(2));
println!("still parked after 2s, nothing will wake it");
std::process::exit(2);
});
let mut fut = pin!(Forgetful);
let waker = Waker::from(Arc::new(ThreadWaker(thread::current())));
let mut cx = Context::from_waker(&waker);
loop {
match fut.as_mut().poll(&mut cx) {
Poll::Ready(()) => return,
Poll::Pending => thread::park(),
}
}
}still parked after 2s, nothing will wake itThe program parks on the first poll, nothing calls unpark, and the watchdog thread has to kill the process after two seconds. This is the textbook cause of a hang that has no CPU use and no error, and it is the bug in the middle of debugging a hung async program when the culprit is a hand written future. Hand written futures are the only place it can occur in everyday code, because .await on a well behaved leaf future forwards the context for you.
What is missing compared with Tokio
- Threads: one here; a work stealing pool in Tokio.
- Timers: a helper thread per sleep here; a shared timer wheel in Tokio.
- I/O: none here; an epoll, kqueue or IOCP reactor in Tokio.
- Task results: none here; a
JoinHandlein Tokio. - Fairness: queue order only here; a cooperative budget that forces yields in Tokio.
- Cancellation: none here;
abortand drop semantics on theJoinHandlein Tokio.
Without a reactor, a future waiting on a socket has nothing to wake it. The helper thread in Sleep stands in for the reactor, badly: one OS thread per timer does not scale past a few hundred. Tokio parks a worker in epoll_wait or kevent with a timeout taken from its timer wheel, so one syscall waits on every socket and every timer at once, and the reactor calls wake on the right task when the kernel reports readiness (the Tokio runtime explained lays out the pieces).
How fast is the simple version?
A fair question after reading 60 lines: how much slower is it than the real thing? I measured spawn plus two yields per task, 500 tasks per round and 200 rounds, so 100,000 tasks and 300,000 polls, in a release build. The Tokio side used a current_thread runtime so both ran on one thread.
#[path = "e1_lib.rs"]
mod e1;
use std::time::Instant;
fn main() {
const TASKS: usize = 500;
const ROUNDS: usize = 200;
let t = Instant::now();
for _ in 0..ROUNDS {
let (ex, sp) = e1::new_executor();
for _ in 0..TASKS {
sp.spawn(async {
e1::Yield(false).await;
e1::Yield(false).await;
});
}
drop(sp);
ex.run();
}
let mine = t.elapsed();
let rt = tokio::runtime::Builder::new_current_thread().build().unwrap();
let t = Instant::now();
rt.block_on(async {
for _ in 0..ROUNDS {
let mut hs = Vec::with_capacity(TASKS);
for _ in 0..TASKS {
hs.push(tokio::spawn(async {
tokio::task::yield_now().await;
tokio::task::yield_now().await;
}));
}
for h in hs { h.await.unwrap(); }
}
});
let theirs = t.elapsed();
println!("tiny executor: {:?} tokio current_thread: {:?}", mine, theirs);
}tiny executor: 18.350042ms tokio current_thread: 23.963958ms
tiny executor: 18.097667ms tokio current_thread: 24.65975ms
tiny executor: 19.966167ms tokio current_thread: 24.888917msThe toy was a little faster, about 18 ms against 24 ms across three runs. That is not a sign the toy is better. It is a sign of how little it does: no JoinHandle result slot, no cooperative budget accounting, no task ids, no hooks for tracing, and a plain mpsc queue. The measurement is also narrow, because it exercises nothing the toy cannot do. Add timers, I/O and multiple threads and the comparison stops being meaningful; add work stealing and Tokio wins on any real workload.
The experiment also found a limit. My first version spawned all 100,000 tasks before calling run, and the program hung. The ready queue is a sync_channel(1024), so after 1,024 spawns the next send blocks, waiting for a receiver that has not started yet. The benchmark above spawns 500 at a time to stay under the cap. This is a direct, unfashionable example of backpressure: a bounded queue turns "too much queued work" into a blocked caller instead of unbounded memory (mpsc channels in Rust). In an executor it is also a hazard, because wake uses the same queue and can block on a full one. A real runtime uses an unbounded or intrusive queue for exactly that reason.
When this does not apply
This executor is a model, not a tool.
- It cannot do I/O. A socket needs a reactor. If you want a small runtime you can read, read
smolor its pieces; if you want production, use Tokio. - It runs one thread. A task that blocks, as
std::thread::sleepdoes, stops every other task. Tokio has the same property per worker (blocking the runtime). - Its wake path can deadlock if a task wakes itself while the queue is full and the executor is the only consumer. Fine for a demo, wrong for a library.
- Futures that need a Tokio context (
tokio::time::sleep,TcpStream) panic with "there is no reactor running" when polled here, since they look for Tokio's runtime handle on the thread.
Where to take it
Four additions, each one a small step, make one more piece of tokio::spawn obvious. First, a JoinHandle: a shared slot protected by a mutex and a waker, written by the task on completion and read by the handle, which is the same structure as Sleep above. Second, a real timer: one thread holding a heap of deadlines ordered by time, which is what the hashed wheel optimises. Third, a worker pool by running several copies of run that share one receiver behind a mutex. Fourth, a reactor, using the mio crate to turn socket readiness into wake calls. After those, you will have rebuilt the shape of the thing, and the stack traces in a real program stop looking like someone else's code. When one of your programs hangs, the model explains why: some future returned Pending and nobody was assigned to wake it.
