FerrousPath

Nivel 4 · Experto· Lección 7 de 9 · 45 min

Async por dentro: construye un ejecutor

El contrato de Future, los wakers y RawWaker, un futuro hoja respaldado por un hilo temporizador, y un ejecutor completo de varias tareas en cien líneas.

async/await es sintaxis sobre un protocolo pequeño y preciso. Esta lección implementa sus dos lados —un futuro que espera a un temporizador y un ejecutor que ejecuta muchas tareas— usando solo la biblioteca estándar. Después de ella, Tokio deja de ser magia.

El contrato

pub trait Future {
    type Output;
    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>;
}

Reglas que toda implementación y todo código que llama deben respetar:

  1. poll debe retornar rápidamente. Hace el progreso que sea posible sin bloquear.
  2. Si devuelve Poll::Pending, debe haberse encargado de que cx.waker() —el waker de esta llamada— se despierte cuando sea posible progresar.
  3. Después de Poll::Ready, el futuro no debe volver a sondearse.
  4. Se permiten los sondeos espurios: un futuro debe tolerar que lo sondeen sin que lo hayan despertado.
  5. Los avisos para despertar pueden llegar desde cualquier hilo, en cualquier momento, incluso durante poll. Un waker es Send + Sync + Clone.

El lado del ejecutor: sondear una tarea cuando la despiertan, y no en otro caso.

A qué se compila async

async fn add_slowly(a: u32, b: u32) -> u32 {
    let x = step(a).await; // punto de suspensión 1
    let y = step(b).await; // punto de suspensión 2
    x + y
}

async fn step(n: u32) -> u32 { n }

El compilador lo convierte, más o menos, en un enum con una variante por cada punto de suspensión, cada una con las variables que están vivas a través de él:

enum AddSlowly {
    Start { a: u32, b: u32 },
    AwaitingFirst { b: u32, fut: Step },
    AwaitingSecond { x: u32, fut: Step },
    Done,
}

poll es un match sobre el estado que sondea el futuro interior y, o bien devuelve Pending (quedándose en el mismo estado), o bien guarda el resultado y pasa al estado siguiente. Consecuencias que ahora puedes explicar:

  • El tamaño del futuro es el mayor conjunto de variables locales vivas a través de algún await: un array grande mantenido a través de un await engorda toda la tarea.
  • Una async fn recursiva tendría tamaño infinito; debe meter en un box (Box::pin) la llamada recursiva.
  • Una referencia a una variable local mantenida a través de un await hace que el struct sea autorreferencial; de ahí Pin.
  • El futuro es Send solo si todo lo que se mantiene a través de un await es Send.

Un futuro hoja

Los combinadores y los bloques async solo delegan. En el fondo tiene que haber futuros hoja que se integren con una fuente de eventos y llamen al waker. Los runtimes reales usan un reactor sobre epoll, kqueue o IOCP. El nuestro usa un hilo:

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(); // le dice al ejecutor: vuelve a sondear esa tarea
            }
        });
        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(());
        }
        // Guarda siempre el waker del sondeo más reciente.
        match &s.waker {
            Some(w) if w.will_wake(cx.waker()) => {}
            _ => s.waker = Some(cx.waker().clone()),
        }
        Poll::Pending
    }
}

fn main() {
    // Lo hacemos avanzar a mano con un waker que no hace nada, para ver el protocolo.
    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));
}

El cerrojo cierra una carrera: el hilo temporizador activa done y toma el waker bajo el mismo mutex en el que poll comprueba done y guarda el waker. Sin él, el aviso podría caer entre la comprobación y el guardado y perderse para siempre: el clásico aviso perdido (lost wake-up).

block_on: el ejecutor más pequeño

Para ejecutar un futuro hasta que termine, sondéalo y aparca el hilo hasta que se dispare su waker:

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(), // duerme hasta que wake() nos desaparque
        }
    }
}

fn main() {
    let answer = block_on(async {
        let a = async { 40 }.await;
        a + 2
    });
    println!("{answer}");
}

std::task::Wake construye un Waker a partir de un Arc<impl Wake>. Por debajo, un Waker es un RawWaker: un puntero a los datos más una vtable escrita a mano con cuatro funciones (clone, wake, wake_by_ref, drop). Es un trait object manual, para que los ejecutores puedan prescindir de Arc cuando lo necesiten, como hacen los de sistemas embebidos. thread::park tolera un unpark que llegue antes, así que aquí tampoco hay aviso perdido.

Un ejecutor de varias tareas

Ahora lo de verdad: muchas tareas, una cola de ejecución y spawn. Una tarea es dueña de su futuro; su waker vuelve a meter la tarea en la cola.

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};

// ---------- el futuro hoja de arriba ----------
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
    }
}

// ---------- el ejecutor ----------
type BoxFuture = Pin<Box<dyn Future<Output = ()> + Send>>;

struct Task {
    /// `None` cuando el futuro ya ha terminado.
    future: Mutex<Option<BoxFuture>>,
    /// Adónde enviar esta tarea cuando la despiertan.
    queue: Sender<Arc<Task>>,
}

impl Wake for Task {
    fn wake(self: Arc<Self>) {
        // Despertar = planificar. Si el ejecutor ya no existe, no hay nada que hacer.
        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 {
    /// Se ejecuta hasta que todas las tareas han terminado y se han liberado todos los Spawner y Waker.
    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); // no ha terminado: guárdalo para el próximo aviso
                }
                // Si es Ready, el futuro se libera aquí y la tarea ha terminado.
            }
        }
    }
}

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 {
                // Las tareas pueden lanzar tareas.
                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); // para que `run` pueda terminar cuando todas las tareas hayan acabado
    executor.run();
    println!("all tasks finished in {} ms on one thread", start.elapsed().as_millis());
}

Ejecútalo: tres tareas duermen de forma concurrente en un único hilo ejecutor, y el total es de unos 350 ms en lugar de los 650 ms que necesitaría una ejecución secuencial.

Cómo funciona la terminación: el canal se cierra cuando desaparecen todos los Sender. Los emisores viven en los Spawner y dentro de cada Task, y una tarea solo sigue viva mientras está en la cola o mientras algún Waker (que tiene un hilo temporizador) se refiere a ella. Cuando termina la última tarea, se libera el último emisor, recv devuelve Err y run sale. La propiedad lleva la contabilidad.

De esto a Tokio

Todo lo que añade un runtime de producción es un refinamiento de las piezas anteriores:

Nuestro ejecutor Un runtime de producción
Un hilo que vacía un canal mpsc Un grupo de hilos de trabajo, cada uno con una cola local, que se roban trabajo entre sí
Un Mutex<Option<BoxFuture>> por tarea Una sola reserva que contiene la cabecera, el futuro y la salida, con una palabra de estado atómica (inactiva / planificada / en ejecución / completa) para que un aviso durante poll replanifique exactamente una vez
Un hilo por temporizador Un reactor: una sola llamada a epoll/kqueue/IOCP que espera por todos los sockets, más una rueda de temporizadores jerárquica; guarda los wakers indexados por fuente de eventos
Sin JoinHandle El hueco de salida de la tarea más un segundo waker para quien espere el handle
Las tareas se ejecutan hasta que ceden Presupuesto cooperativo: a una tarea que ha hecho demasiado trabajo se la obliga a ceder para que las demás no sufran inanición
Solo futuros Send LocalSet / runtimes de un solo hilo para futuros !Send

Preguntas de diseño sobre las que ahora puedes razonar: ¿por qué los futuros lanzados deben ser 'static? (La tarea sobrevive al marco de pila que la lanzó.) ¿Por qué se exige que wake() sea barato y no reentrante? (Puede llamarse desde un manejador de interrupción o desde dentro de poll.) ¿Por qué select! y join! sobre muchos futuros vuelven a sondearlos todos ante cualquier aviso, y por qué FuturesUnordered da en cambio a cada hijo su propio waker?

Ejercicios

  1. Añade un JoinHandle<T> al ejecutor: spawn devuelve un futuro que se resuelve con la salida de la tarea. Necesitas un hueco compartido con un Option<T> y un Option<Waker>.
  2. Escribe async fn yield_now(): un futuro que devuelve Pending una vez después de llamar a cx.waker().wake_by_ref(). Úsalo para mostrar dos tareas que se intercalan.
  3. Sustituye el hilo por cada Sleep por un único hilo temporizador que tenga un BinaryHeap<(Instant, Waker)>: un reactor en miniatura.
  4. Haz que el ejecutor sea multihilo: comparte el receptor detrás de un Mutex entre cuatro hilos de trabajo. ¿Qué debe cambiar para que una tarea despertada mientras se la está sondeando no se sondee de forma concurrente ni se pierda?
  5. Implementa a mano una vtable de RawWaker para el waker de hilo de block_on, sin Arc.

Comprueba lo que has entendido

Elige una respuesta para ver la explicación.

  1. 1.¿Qué debe hacer un futuro antes de devolver Poll::Pending?

  2. 2.¿Por qué un futuro hoja debe guardar el waker *más reciente* en cada sondeo, y no solo el primero?

  3. 3.En el ejecutor de esta lección, ¿qué hace wake()?

Términos clave de esta lección

¿Has terminado la lección y los ejercicios?