Clever Geek Handbook

Implementación de flujos cooperativos simples en C

¡Hola, Habr!



Gracias por su atención a nuestra publicación anterior traducida sobre REST . Hoy nos proponemos analizar el tema del diseño de sistemas desde un ángulo ligeramente diferente y publicar una traducción de un artículo de Stephen Brennan, un destacado de Linux, que habla sobre su propia implementación de la multitarea en el espacio de usuario y cómo puede ser beneficiosa.



La multitarea, como muchas otras capacidades que ofrece el sistema operativo, no solo la damos por sentada, sino que también la percibimos como algo común. Con nuestras potentes computadoras y teléfonos inteligentes, la idea de que una computadora no pueda manejar cientos de procesos parece extraña. Creo que esta es una de las posibilidades que hizo que las computadoras fueran tan útiles, pero es por eso que son tan complejas, a veces parece magia.



Es difícil incursionar en el código que implementa la multitarea, y no siempre está claro en qué casos es mejor implementarlo usted mismo, para no tener que escribir un sistema operativo completo. Estoy bastante seguro de que es imposible comprender completamente el fenómeno hasta que uno mismo se da cuenta. Por eso, decidí escribir un artículo en el que te diré cómo puedes jugar con una implementación de subprocesos simple. En este artículo, implementaremos flujos simples en un

programa C normal (no en un sistema operativo).



Una digresión lírica sobre setjmp y longjmp



El planificador dependerá en gran medida de las funciones setjmp()y longjmp(). Parecen un poco mágicos, así que primero describiré lo que hacen, y luego me tomaré un poco de tiempo y les diré exactamente cómo.



La función setjmp()te permite registrar información sobre en qué etapa de ejecución se encontraba el programa, para que luego puedas volver a saltar a este punto. Se le pasa una variable de tipo jmp_buf, en la que almacenaremos esta información. La primera vez que regresa, la función setjmp()devuelve 0.



Más tarde, puede usar la función longjmp(jmp_buf, value)para reanudar instantáneamente la ejecución desde el punto donde fue llamada setjmp(). En su programa, esta situación parecerá que setjmp()regresó por segunda vez. El argumento volverá esta vezvalueque pasó longjmp(), es más conveniente distinguir el segundo regreso del primero. Aquí hay un ejemplo para ilustrar este punto: 



#include <stdio.h>
#include <setjmp.h>

jmp_buf saved_location;
int main(int argc, char **argv)
{
    if (setjmp(saved_location) == 0) {
        printf("We have successfully set up our jump buffer!\n");
    } else {
        printf("We jumped!\n");
        return 0;
    }

    printf("Getting ready to jump!\n");
    longjmp(saved_location, 1);
    printf("This will never execute...\n");
    return 0;
}


Si compilamos y ejecutamos este programa, obtenemos el siguiente resultado: 



We have successfully set up our jump buffer!
Getting ready to jump!
We jumped!


¡Guauu! Es como una instrucción goto, pero en este caso incluso se puede usar para saltar fuera de una función. También es más difícil de leer de gotolo que es porque parece una llamada de función normal. Si su código usa setjmp()y en abundancia longjmp(), entonces será muy difícil leerlo para cualquiera (incluido usted).



Como es el caso goto, generalmente se recomienda evitar setjmp()y longjmp(). Pero al igual quegoto, las funciones anteriores pueden resultar útiles si se utilizan con moderación y de forma constante. El programador debe poder cambiar de contexto, por lo que usaremos estas funciones de manera responsable. Lo más importante es que utilizaremos estas funciones de nuestra API para que los usuarios de nuestro planificador no tengan que lidiar con este tipo de complejidad.



Setjmp y longjmp no guardarán su pila

True, funciones setjmp()ylongjmp()no están destinados a admitir ningún tipo de salto. Fueron diseñados para un caso práctico muy específico. Imagine que está realizando una operación compleja, como realizar una solicitud HTTP. En este caso, se involucrará un conjunto complejo de llamadas a funciones, y si alguna de ellas falla, deberá devolver un código de error especial de cada una de ellas. Dicho código se verá como en la siguiente lista, dondequiera que llame a la función (quizás docenas de veces): 



int rv = do_function_call();
if (rv != SUCCESS) {
    return rv;
}


El significado setjmp()y longjmp()es lo que setjmp()ayuda a delimitar un lugar antes de embarcarse en la tarea realmente difícil. Luego, puede centralizar todo su manejo de errores en un solo lugar: 



int rv;
jmp_buf buf;
if ((rv = setjmp(buf)) != 0) {
    /*    */
    return;
}
do_complicated_task(buf, args...);


Si falla alguna función involucrada do_complicated_task(), simplemente sucede longjmp(buf, error_code). Esto significa que cada función en la composición do_complicated_task()puede asumir que cualquier llamada de función es exitosa, lo que significa que no puede poner este código para manejar errores en cada llamada de función (en la práctica esto casi nunca se hace, pero este es un tema para un artículo separado). ...



La idea básica aquí es que longjmp()solo le permite saltar de funciones profundamente anidadas. No puedes saltar a esa función profundamente anidada de la que saltaste antes. Así es como se ve la pila cuando saltas de la función. Asterisco (*) significa el puntero de la pila en el que se almacena setjmp(). 



  | Stack before longjmp    | Stack after longjmp
      +-------------------------+----------------------------
stack | main()              (*) | main()
grows | do_http_request()       |
down  | send_a_header()         |
 |    | write_bytes()           |
 v    | write()  - fails!       |


Como puede ver, solo puede retroceder en la pila, por lo que no hay peligro de corrupción de datos. Por otro lado, imagina cómo sería si quisieras saltar entre tareas. Si llama setjmp()y luego regresa, hace otras cosas e intenta reanudar el trabajo que ya ha estado haciendo antes, surgirá un problema: 



      | Stack at setjmp() | Stack later      | Stack after longjmp()
      +-------------------+------------------+----------------------
stack | main()            | main()           | main()
grows | do_task_one()     | do_task_two()    | do_stack_two()
down  | subtask()         | subtask()        | subtask()
 |    | foo()             |                  | ???
 v    | bar()         (*) |              (*) | ???               (*)


El puntero de pila guardado setjmp()apuntará a un marco de pila que ya no existe y que puede haber sido sobrescrito por otros datos en algún momento. Si intentamos longjmp()volver a la función de la que regresamos con ayuda , entonces comenzarán cosas muy extrañas que bien pueden llevar al colapso de todo el programa.



Moraleja: Si va a utilizar setjmp()y longjmp()saltar entre tareas complejas como estas, debe asegurarse de que cada tarea tenga su propia pila separada. En este caso, el problema se elimina por completo, ya que cuando longjmp()se restablece el puntero de la pila, el programa mismo reemplazará la pila por la deseada y no se borrará la pila.



Escribamos una API de planificador



La digresión es un poco larga, pero armados con lo que hemos aprendido, ahora podemos implementar flujos de espacio de usuario. Para empezar, observo que es muy útil diseñar la API usted mismo para inicializar, crear e iniciar subprocesos. Si hacemos esto con anticipación, ¡entenderemos mucho mejor qué es exactamente lo que estamos tratando de construir! 



void scheduler_init(void);
void scheduler_create_task(void (*func)(void*), void *arg);
void scheduler_run(void);


Estas funciones se utilizarán para inicializar el programador, agregar tareas y, finalmente, iniciar las tareas en el programador. Una vez iniciado, se scheduler_run()ejecutará hasta que se completen todas las tareas. Las tareas que se estén ejecutando actualmente tendrán las siguientes API: 



void scheduler_exit_current_task(void);
void scheduler_relinquish(void);


La primera función es responsable de salir de la tarea. La salida de la tarea también es posible al regresar de su función, por lo que esta construcción existe solo por conveniencia. La segunda función describe cómo nuestros hilos le dirán al programador que otra tarea debería estar ejecutándose por un tiempo. Cuando una tarea llama scheduler_relinquish(), se puede suspender temporalmente mientras se ejecutan otras tareas; pero eventualmente la función regresará y la primera tarea puede continuar.



Por el bien de un ejemplo concreto, consideremos un caso de uso hipotético para nuestra API, con el que probaremos el planificador: 



#include <stdlib.h>
#include <stdio.h>

#include "scheduler.h"

struct tester_args {
    char *name;
    int iters;
};

void tester(void *arg)
{
    int i;
    struct tester_args *ta = (struct tester_args *)arg;
    for (i = 0; i < ta->iters; i++) {
        printf("task %s: %d\n", ta->name, i);
        scheduler_relinquish();
    }
    free(ta);
}

void create_test_task(char *name, int iters)
{
    struct tester_args *ta = malloc(sizeof(*ta));
    ta->name = name;
    ta->iters = iters;
    scheduler_create_task(tester, ta);
}

int main(int argc, char **argv)
{
    scheduler_init();
    create_test_task("first", 5);
    create_test_task("second", 2);
    scheduler_run();
    printf("Finished running all tasks!\n");
    return EXIT_SUCCESS;
}


En este ejemplo, creamos dos tareas que realizan la misma función, pero toman diferentes argumentos; por lo tanto, su implementación se puede rastrear por separado. Cada tarea realiza un número determinado de iteraciones. En cada iteración, imprime un mensaje y luego deja que se ejecute otra tarea. Esperamos ver algo como la salida del programa: 



task first: 0
task second: 0
task first: 1
task second: 1
task first: 2
task first: 3
task first: 4
Finished running all tasks!


Implementemos la API del planificador



Para implementar la API, necesitamos algún tipo de representación interna de la tarea. Entonces, vayamos al grano; Recopilemos los campos que necesitamos: 



struct task {
    enum {
        ST_CREATED,
        ST_RUNNING,
        ST_WAITING,
    } status;

    int id;

    jmp_buf buf;

    void (*func)(void*);
    void *arg;

    struct sc_list_head task_list;

    void *stack_bottom;
    void *stack_top;
    int stack_size;
};


Analicemos cada uno de estos campos por separado. Todas las tareas creadas deben estar en el estado "creado" antes de su ejecución. Cuando una tarea comienza a ejecutarse, entra en el estado de "ejecución", y si la tarea alguna vez necesita esperar alguna operación asincrónica, se puede poner en el estado de "espera". Un campo ides simplemente un identificador único para una tarea. Este bufcontiene información acerca de cuándo la longjmp()tarea se ejecutará a reanudar. Los campos funcy argse pasan scheduler_create_task()y son necesarios para ejecutar la tarea. Se task_listrequiere que el campo implemente una lista doblemente vinculada de todas las tareas. Los campos stack_bottom, stack_topy stack_sizetodos pertenecen a una pila separada dedicada específicamente a esta tarea. Abajo es la dirección devuelta pormalloc()pero "top" es un puntero a una dirección directamente encima de la región dada en la memoria. Dado que la pila x86 crece hacia abajo, debe establecer el puntero de la pila en un valor stack_top, no stack_bottom.



En tales condiciones, puede implementar la función scheduler_create_task(): 



void scheduler_create_task(void (*func)(void *), void *arg)
{
    static int id = 1;
    struct task *task = malloc(sizeof(*task));
    task->status = ST_CREATED;
    task->func = func;
    task->arg = arg;
    task->id = id++;
    task->stack_size = 16 * 1024;
    task->stack_bottom = malloc(task->stack_size);
    task->stack_top = task->stack_bottom + task->stack_size;
    sc_list_insert_end(&priv.task_list, &task->task_list);
}


Al usar static int, garantizamos que cada vez que se llama a la función, el campo id se incrementa y hay un nuevo número. Todo lo demás debe quedar claro sin explicación, excepto la función sc_list_insert_end()que simplemente se agrega struct taska la lista global. La lista global se almacena dentro de una segunda estructura que contiene todos los datos privados del planificador. A continuación se muestra la estructura en sí, así como su función de inicialización: 



struct scheduler_private {
    jmp_buf buf;
    struct task *current;
    struct sc_list_head task_list;
} priv;

void scheduler_init(void)
{
    priv.current = NULL;
    sc_list_init(&priv.task_list);
}


El campo se task_listutiliza para hacer referencia a una lista de tareas (como era de esperar). El campo currentalmacena la tarea que se está realizando actualmente (o null, si no existen tales tareas en este momento). Lo más importante es que el campo bufse utilizará para saltar al código scheduler_run(): 



enum {
    INIT=0,
    SCHEDULE,
    EXIT_TASK,
};

void scheduler_run(void)
{
    /*     ! */
    switch (setjmp(priv.buf)) {
    case EXIT_TASK:
        scheduler_free_current_task();
    case INIT:
    case SCHEDULE:
        schedule();
        /*       ,    */
        return;
    default:
        fprintf(stderr, "Uh oh, scheduler error\n");
        return;
    }
}


Tan pronto como se llama a la función scheduler_run(), configuramos el búfer setjmp()para que siempre podamos volver a esa función. La primera vez, se devuelve 0 (INIT) y llamamos inmediatamente schedule(). Posteriormente, podemos pasar las constantes SCHEDULE o EXIT_TASK longjmp(), lo que provocará diferentes comportamientos. Por ahora, ignoremos el caso EXIT_TASK y saltemos directamente a la implementación schedule(): 



static void schedule(void)
{
    struct task *next = scheduler_choose_task();

    if (!next) {
        return;
    }

    priv.current = next;
    if (next->status == ST_CREATED) {
        /*
         *     .   
         * ,        .
         */
        register void *top = next->stack_top;
        asm volatile(
            "mov %[rs], %%rsp \n"
            : [ rs ] "+r" (top) ::
        );

        /*
         *   
         */
        next->status = ST_RUNNING;
        next->func(next->arg);

        /*
         *     ,    .   – ,   
         *   
         */
        scheduler_exit_current_task();
    } else {
        longjmp(next->buf, 1);
    }
    /*   */
}


Primero, llamamos a la función interna para seleccionar la siguiente tarea a ejecutar. Este programador funcionará como un carrusel normal, por lo que simplemente seleccionará una nueva tarea de la lista. Si esta función devuelve NULL, no nos quedan más tareas por realizar y volvemos. De lo contrario, debemos iniciar la ejecución de la tarea (si está en el estado ST_CREATED) o reanudar su ejecución.



Para ejecutar la tarea creada, usamos la instrucción de ensamblaje para x86_64 para asignar el campo a un stack_topregistro rsp(puntero de pila). Luego cambiamos el estado de la tarea, ejecutamos la función y salimos. Nota: setjmp()las dos longjmp()tiendas y la pila rearrange punteros, por lo que aquí sólo tiene que utilizar ensamblador para cambiar el puntero de pila.



Si la tarea ya se ha iniciado, entonces el campo bufdebe contener el contexto que necesitamos longjmp()para reanudar la tarea, así que eso es lo que hacemos.

A continuación, veamos una función auxiliar que selecciona la siguiente tarea a ejecutar. Este es el corazón del planificador y, como dije antes, este planificador funciona como un carrusel: 



static struct task *scheduler_choose_task(void)
{
    struct task *task;

    sc_list_for_each_entry(task, &priv.task_list, task_list, struct task)
    {
        if (task->status == ST_RUNNING || task->status == ST_CREATED) {
            sc_list_remove(&task->task_list);
            sc_list_insert_end(&priv.task_list, &task->task_list);
            return task;
        }
    }

    return NULL;
}


Si no está familiarizado con la implementación de mi lista enlazada (tomada del kernel de Linux), no es gran cosa. Una función sc_list_for_each_entry()es una macro que le permite iterar sobre todas las tareas de la lista de tareas. La primera tarea seleccionable (no en un estado pendiente) que encontramos se elimina de su posición actual y se mueve al final de la lista de tareas. Esto asegura que la próxima vez que ejecutemos el programador, obtendremos una tarea diferente (si hay una). Devolvemos la primera tarea disponible para la selección, o NULL si no hay ninguna tarea.



Finalmente, pasemos a la implementación scheduler_relinquish()para ver cómo la tarea puede auto-eliminarse: 



void scheduler_relinquish(void)
{
    if (setjmp(priv.current->buf)) {
        return;
    } else {
        longjmp(priv.buf, SCHEDULE);
    }
}


Este es otro caso de uso de la función setjmp()en nuestro planificador. Básicamente, esta opción puede parecer un poco confusa. Cuando la tarea llama a esta función, la usamos setjmp()para guardar el contexto actual (incluido el puntero de pila real). Luego lo usamos longjmp()para ingresar al programador (nuevamente en scheduler_run()) y pasar la función PROGRAMAR; por eso le pedimos que asigne una nueva tarea.



Cuando se reanuda la tarea, la función setjmp()regresa con un valor distinto de cero y salimos de cualquier tarea que pudiéramos haber estado haciendo antes.

Finalmente, esto es lo que sucede cuando una tarea sale (esto se hace explícitamente, llamando a la función de salida o regresando de la función de tarea correspondiente): 



void scheduler_exit_current_task(void)
{
    struct task *task = priv.current;
    sc_list_remove(&task->task_list);
    longjmp(priv.buf, EXIT_TASK);
    /*   */
}

static void scheduler_free_current_task(void)
{
    struct task *task = priv.current;
    priv.current = NULL;
    free(task->stack_bottom);
    free(task);
}


Este es un proceso de dos partes. La primera función es devuelta directamente por la propia tarea. Estamos eliminando la entrada correspondiente a esta de la lista de tareas, ya que ya no estará asignada. Luego, usando, longjmp()volvemos a la función scheduler_run(). Esta vez usamos EXIT_TASK. Así es como le decimos al programador qué debe llamar antes de asignar una nueva tarea scheduler_free_current_task(). Si vuelve a la descripción scheduler_run(), verá que esto es exactamente lo que hace scheduler_run().



Hicimos esto en dos pasos, desde cuandoscheduler_exit_current_task(), utiliza activamente la pila contenida en la estructura de tareas. Si libera la pila y continúa usándola, entonces existe la posibilidad de que la función aún pueda acceder a la misma memoria de pila que acabamos de liberar. Para asegurarnos de que esto no suceda, tendremos que longjmp()volver al planificador usando una pila separada con ayuda . Entonces podemos liberar de forma segura los datos relacionados con la tarea.



Así que hemos analizado toda la implementación del planificador por completo. Si intentáramos compilarlo agregando mi implementación de lista vinculada y el programa principal anterior, obtendríamos un programador completamente funcional. Para no molestarlo con copiar y pegar, lo dirijo al repositorio en github , que contiene todo el código de este artículo.



¿Cuál es el uso del enfoque descrito?



Si has leído hasta ahora, creo que no es necesario que te convenza de que el ejemplo es interesante. Pero a primera vista, puede que no parezca muy útil. Después de todo, puede usar subprocesos "reales" en C, que pueden ejecutarse en paralelo y no tienen que esperar el uno al otro hasta que uno de ellos llame scheduler_relinquish().



Sin embargo, veo esto como un punto de partida para toda una serie de interesantes implementaciones de funciones útiles. Podemos hablar de tareas pesadas de E / S, de implementar una aplicación asíncrona de un solo subproceso, de la misma manera que funcionan las nuevas utilidades asíncronas en Python. También se pueden implementar generadores y corrutinas usando dicho sistema. Por último, con un poco de trabajo duro, este sistema también puede hacerse amigo de los hilos "reales" del sistema operativo para proporcionar simultaneidad adicional cuando sea necesario. Detrás de cada una de estas ideas se esconde un proyecto interesante, y te recomiendo que intentes completar una de ellas tú mismo, querido lector.



¿Es seguro?



¡Creo que es más probable que no que sí! El código ensamblador en línea que afecta al puntero de la pila no se puede considerar seguro. No se arriesgue a usar estas cosas en producción, ¡pero asegúrese de jugar con ellas e investigar!



Se puede construir una implementación más segura de dicho sistema usando una API "no contextual" (ver man getcontext), que le permite cambiar entre estos tipos de "flujos" de espacio de usuario sin incrustar código ensamblador. Desafortunadamente, dicha API no está cubierta por los estándares (se ha eliminado de la especificación POSIX). Pero todavía se puede utilizar como parte de glibc.



¿Cómo se puede hacer desplazar un mecanismo así?



Este planificador, como se presenta aquí, solo funciona si los subprocesos transfieren explícitamente el control al planificador. Esto no es bueno para un programa general, por ejemplo, para un sistema operativo, ya que un hilo mal hecho puede bloquear la ejecución de todos los demás (¡aunque esto no impidió el uso de multitarea cooperativa en MS-DOS!) No creo que esto haga que la multitarea cooperativa sea claramente mala; todo depende de la aplicación.



Cuando se utiliza una API "fuera de contexto" no estándar, las señales POSIX almacenarán el contexto del código que se ejecutó previamente. Al configurar el temporizador para que emita un pitido, el programador del espacio de usuario puede proporcionar una versión funcional de la multitarea preventiva. Este es otro proyecto genial que merece un artículo aparte.


More articles:


All Articles