Implémentation de flux coopératifs simples en C

Bonjour, Habr!



Merci pour votre attention sur notre précédent article traduit sur REST . Aujourd'hui, nous proposons de regarder le sujet de la conception de système sous un angle légèrement différent et de publier une traduction d'un article de Stephen Brennan, un luminaire Linux, qui parle de sa propre implémentation du multitâche dans l'espace utilisateur et de son utilité.



Le multitâche, comme de nombreuses autres fonctionnalités fournies par le système d'exploitation, non seulement nous le prenons pour acquis, mais nous le percevons également comme quelque chose d'ordinaire. Avec nos puissants ordinateurs et smartphones, l'idée même qu'un ordinateur ne peut pas jongler avec des centaines de processus semble étrange. Je pense que c'est l'une des possibilités qui ont rendu les ordinateurs si utiles, mais c'est à cause de cela qu'ils sont si complexes, parfois cela semble magique.



Il est difficile de se familiariser avec du code qui implémente le multitâche, et il n'est pas toujours clair dans quels cas il est préférable de l'implémenter vous-même, de sorte que vous n'ayez pas à écrire un système d'exploitation entier. Je suis convaincu qu'il est impossible de comprendre pleinement le phénomène tant que vous ne le réalisez pas vous-même. Par conséquent, j'ai décidé d'écrire un article dans lequel je vous dirai comment vous pouvez jouer avec une implémentation de threading simple. Dans cet article, nous allons implémenter des flux simples dans un

programme C normal (pas un système d'exploitation).

Une digression lyrique sur setjmp et longjmp

L'ordonnanceur dépendra fortement des fonctions setjmp()et longjmp(). Ils semblent un peu magiques, alors je vais d'abord décrire ce qu'ils font, puis je prendrai un peu de temps pour vous dire exactement comment.



La fonction setjmp()vous permet d'enregistrer des informations sur le stade d'exécution du programme, afin que vous puissiez à nouveau sauter à ce stade plus tard. Une variable de type lui est transmise jmp_buf, dans laquelle nous stockerons ces informations. La première fois qu'elle revient, la fonction setjmp()renvoie 0.



Plus tard, vous pouvez utiliser la fonction longjmp(jmp_buf, value)pour reprendre instantanément l'exécution à partir du point où elle a été appelée setjmp(). Dans votre programme, cette situation semblera être setjmp()revenue une deuxième fois. L'argument reviendra cette foisvalueque vous avez réussi longjmp()- il est plus pratique de distinguer le deuxième retour du premier. Voici un exemple pour illustrer ce point:

#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 nous compilons et exécutons ce programme, nous obtenons la sortie suivante:

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

Hou la la! C'est comme une instruction goto, mais dans ce cas, elle peut même être utilisée pour sauter en dehors d'une fonction. Il est également plus difficile à lire qu'il gotone l'est car il ressemble à un appel de fonction normal. Si votre code est utilisé en abondance setjmp()et longjmp(), alors il sera très difficile de le lire pour quiconque (vous y compris).



Comme c'est le cas goto, il est généralement recommandé d'éviter setjmp()et longjmp(). Mais commegoto, les fonctions ci-dessus peuvent être utiles si elles sont utilisées avec parcimonie et de manière cohérente. Le planificateur doit pouvoir changer de contexte, nous allons donc utiliser ces fonctionnalités de manière responsable. Plus important encore, nous utiliserons ces fonctions de notre API afin que les utilisateurs de nos planificateurs n'aient pas à faire face à ce type de complexité.



Setjmp et longjmp ne sauveront pas votre pile

True, les fonctions setjmp()etlongjmp()ne sont pas destinés à prendre en charge tout type de saut. Ils ont été conçus pour un cas pratique très spécifique. Imaginez que vous effectuez une opération complexe, telle qu'une requête HTTP. Dans ce cas, un ensemble complexe d'appels de fonction sera impliqué, et si l'un d'entre eux échoue, vous devrez renvoyer un code d'erreur spécial pour chacun d'eux. Un tel code ressemblera à la liste suivante, partout où vous appelez la fonction (peut-être des dizaines de fois):

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

Le sens setjmp()et longjmp()c'est ce qui setjmp()permet de jalonner une place avant de se lancer dans la tâche vraiment difficile. Ensuite, vous pouvez centraliser toute votre gestion des erreurs en un seul endroit:

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

Si une fonction impliquée échoue do_complicated_task(), cela se produit simplement longjmp(buf, error_code). Cela signifie que chaque fonction de la composition do_complicated_task()peut supposer que tout appel de fonction est réussi, ce qui signifie que vous ne pouvez pas mettre ce code pour gérer les erreurs dans chaque appel de fonction (en pratique, cela n'est presque jamais fait, mais c'est un sujet pour un article séparé) ...



L'idée de base ici est longjmp()qu'elle vous permet uniquement de sauter hors des fonctions profondément imbriquées. Vous ne pouvez pas sauter dans cette fonction profondément imbriquée dont vous avez sauté plus tôt. Voici à quoi ressemble la pile lorsque vous sortez de la fonction. L'astérisque (*) désigne le pointeur de pile sur lequel il est stocké setjmp().

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

Comme vous pouvez le voir, vous ne pouvez que revenir en arrière sur la pile, il n'y a donc aucun risque de corruption des données. D'un autre côté, imaginez ce que ce serait si vous vouliez passer d'une tâche à l'autre. Si vous appelez setjmp()puis revenez, faites d'autres choses et essayez de reprendre le travail que vous avez déjà fait auparavant, un problème se posera:

      | 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()         (*) |              (*) | ???               (*)

Le pointeur de pile enregistré setjmp()pointera vers un cadre de pile qui n'existe plus et qui peut avoir été écrasé par d'autres données à un moment donné. Si nous essayons de longjmp()revenir à la fonction à partir de laquelle nous sommes revenus avec l'aide , des choses très étranges commenceront, ce qui pourrait bien conduire à l'effondrement de tout le programme.



Morale: Si vous comptez utiliser setjmp()et longjmp()sauter entre des tâches complexes comme celles-ci, vous devez vous assurer que chaque tâche a sa propre pile distincte. Dans ce cas, le problème est complètement éliminé, car lorsque longjmp()le pointeur de pile est réinitialisé, le programme lui-même remplacera la pile par celle souhaitée et aucun effacement de pile ne se produira.

Écrivons une API de planificateur

La digression est un peu longue, mais armé de ce que nous avons appris, nous pouvons maintenant implémenter des flux d'espace utilisateur. Pour commencer, je note qu'il est très utile de concevoir vous-même l'API pour l'initialisation, la création et le démarrage des threads. Si nous faisons cela à l'avance, nous aurons une bien meilleure compréhension de ce que nous essayons de construire exactement!

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

Ces fonctions seront utilisées pour initialiser le planificateur, ajouter des tâches, puis enfin démarrer les tâches dans le planificateur. Une fois lancé, il scheduler_run()fonctionnera jusqu'à ce que toutes les tâches soient terminées. Les tâches en cours d'exécution auront les API suivantes:

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

La première fonction est chargée de quitter la tâche. La sortie de la tâche est également possible lors du retour de sa fonction, donc cette construction n'existe que par commodité. La deuxième fonction décrit comment nos threads indiquent au planificateur qu'une autre tâche doit être en cours d'exécution pendant un certain temps. Lorsqu'une tâche appelle scheduler_relinquish(), elle peut être temporairement suspendue pendant que d'autres tâches sont en cours d'exécution; mais finalement la fonction reviendra et la première tâche pourra continuer.



Pour un exemple concret, considérons un cas d'utilisation hypothétique de notre API, avec lequel nous allons tester le planificateur:

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

Dans cet exemple, nous créons deux tâches qui exécutent la même fonction, mais prennent des arguments différents; ainsi, leur mise en œuvre peut être suivie séparément. Chaque tâche effectue un nombre défini d'itérations. À chaque itération, il imprime un message puis laisse une autre tâche s'exécuter. Nous nous attendons à voir quelque chose comme la sortie du programme:

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!

Implémentons l'API du planificateur

Pour implémenter l'API, nous avons besoin d'une sorte de représentation interne de la tâche. Alors, passons aux choses sérieuses; Collectons les champs dont nous avons besoin:

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

Discutons chacun de ces champs séparément. Toutes les tâches créées doivent être dans l'état «créé» avant l'exécution. Lorsqu'une tâche commence à s'exécuter, elle passe à l'état «en cours d'exécution», et si la tâche a besoin d'attendre une opération asynchrone, elle peut être mise dans l'état «en attente». Un champ idest simplement un identifiant unique pour une tâche. Il bufcontient des informations sur le moment où la longjmp()tâche sera exécutée pour reprendre. Les champs funcet argsont transmis à scheduler_create_task()et sont obligatoires pour démarrer la tâche. Le champ est task_listrequis pour implémenter une liste doublement liée de toutes les tâches. Les champs stack_bottom, stack_topet stack_sizeappartiennent tous à une pile séparée dédiée spécifiquement à cette tâche. En bas se trouve l'adresse renvoyée parmalloc()mais "top" est un pointeur vers une adresse directement au-dessus de la région donnée en mémoire. Étant donné que la pile x86 se développe vers le bas, vous devez définir le pointeur de pile sur une valeur stack_top, pas stack_bottom.



Dans de telles conditions, vous pouvez implémenter la fonction 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);
}

En utilisant static int, nous garantissons qu'à chaque fois que la fonction est appelée, le champ id est incrémenté et qu'il y a un nouveau nombre. Tout le reste doit être clair sans explication, à l'exception de la fonction sc_list_insert_end()qui ajoute simplement struct taskà la liste globale. La liste globale est stockée dans une seconde structure qui contient toutes les données privées du planificateur. Voici la structure elle-même, ainsi que sa fonction d'initialisation:

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

Le champ est task_listutilisé pour faire référence à une liste de tâches (sans surprise). Le champ currentstocke la tâche en cours d'exécution (ou null, s'il n'y en a pas actuellement). Plus important encore, le champ bufsera utilisé pour sauter dans le code 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;
    }
}

Dès que la fonction est appelée scheduler_run(), nous définissons le tampon setjmp()afin de pouvoir toujours revenir à cette fonction. La première fois, 0 (INIT) est renvoyé et nous appelons immédiatement schedule(). Par la suite, nous pouvons passer des constantes SCHEDULE ou EXIT_TASK dans longjmp(), ce qui provoquera des comportements différents. Pour l'instant, ignorons le cas EXIT_TASK et passons directement à l'implémentation 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);
    }
    /*   */
}

Tout d'abord, nous appelons la fonction interne pour sélectionner la prochaine tâche à exécuter. Ce planificateur fonctionnera comme un carrousel normal, il sélectionnera donc simplement une nouvelle tâche dans la liste. Si cette fonction renvoie NULL, alors nous n'avons plus de tâches à effectuer et nous retournons. Sinon, il faut soit démarrer l'exécution de la tâche (si elle est à l'état ST_CREATED), soit reprendre son exécution.



Pour exécuter la tâche créée, nous utilisons l'instruction d'assemblage pour x86_64 pour affecter le champ à un stack_topregistre rsp(pointeur de pile). Ensuite, nous changeons l'état de la tâche, exécutons la fonction et quittons. Remarque: à la setjmp()fois longjmp()stocker et réorganiser les pointeurs de pile, nous n'avons donc ici qu'à utiliser l'assembleur pour changer le pointeur de pile.



Si la tâche a déjà été lancée, le champ bufdoit contenir le contexte dont nous avons besoin longjmp()pour reprendre la tâche, c'est ce que nous faisons.

Ensuite, examinons une fonction d'assistance qui sélectionne la prochaine tâche à exécuter. C'est le cœur du planificateur, et comme je l'ai dit plus tôt, ce planificateur fonctionne comme un carrousel:

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 vous n'êtes pas familier avec mon implémentation de liste chaînée (tirée du noyau Linux), ce n'est pas grave. Une fonction sc_list_for_each_entry()est une macro qui vous permet de parcourir toutes les tâches de la liste des tâches. La première tâche sélectionnable (pas dans un état en attente) que nous trouvons est supprimée de sa position actuelle et déplacée à la fin de la liste des tâches. Cela garantit que la prochaine fois que nous exécuterons le planificateur, nous aurons une tâche différente (s'il y en a une). Nous retournons la première tâche disponible pour la sélection, ou NULL s'il n'y a aucune tâche.



Enfin, passons à l'implémentation scheduler_relinquish()pour voir comment la tâche peut s'auto-éliminer:

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

C'est un autre cas d'utilisation de la fonction setjmp()dans notre planificateur. Fondamentalement, cette option peut sembler un peu déroutante. Lorsqu'une tâche appelle cette fonction, nous l'utilisons setjmp()pour enregistrer le contexte actuel (y compris le pointeur de pile réel). Ensuite, nous l'utilisons longjmp()pour entrer dans le planificateur (à nouveau scheduler_run()) et passer la fonction SCHEDULE; ainsi nous vous demandons d'assigner une nouvelle tâche.



Lorsque la tâche est reprise, la fonction setjmp()retourne avec une valeur différente de zéro, et nous quittons toute tâche que nous aurions pu faire auparavant!

Enfin, voici ce qui se passe lorsqu'une tâche se termine (cela se fait soit explicitement, en appelant la fonction de sortie, soit en revenant de la fonction de tâche correspondante):

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

Il s’agit d’un processus en deux parties. La première fonction est renvoyée directement par la tâche elle-même. Nous supprimons l'entrée correspondant à celle-ci de la liste des tâches, car elle ne sera plus affectée. Puis, en utilisant, longjmp()nous retournons à la fonction scheduler_run(). Cette fois, nous utilisons EXIT_TASK. C'est ainsi que nous disons au planificateur ce qu'il doit appeler avant d'attribuer une nouvelle tâche scheduler_free_current_task(). Si vous revenez à la description scheduler_run(), vous verrez que c'est exactement ce qu'il fait scheduler_run().



Nous l'avons fait en deux étapes, depuis quandscheduler_exit_current_task(), il utilise activement la pile contenue dans la structure de la tâche. Si vous libérez la pile et continuez à l'utiliser, il y a une chance que la fonction puisse accéder à la même mémoire de pile que nous venons de libérer! Pour nous assurer que cela ne se produit pas, nous devrons longjmp()revenir au planificateur en utilisant une pile séparée avec de l'aide . Ensuite, nous pouvons publier en toute sécurité les données liées à la tâche.



Nous avons donc analysé entièrement l'implémentation de l'ordonnanceur. Si nous essayions de le compiler en ajoutant mon implémentation de liste chaînée et le programme principal ci-dessus, nous obtiendrions un planificateur pleinement fonctionnel! Afin de ne pas vous déranger avec le copier-coller, je vous dirige vers le référentiel sur github , qui contient tout le code de cet article.

À quoi sert l'approche décrite?

Si vous avez lu jusqu'à présent, je pense qu'il n'est pas nécessaire de vous convaincre que l'exemple est intéressant. Mais à première vue, cela peut ne pas sembler très utile. Après tout, en C, vous pouvez utiliser de «vrais» threads qui peuvent fonctionner en parallèle et qui n'ont pas à attendre les uns les autres jusqu'à ce que l'un d'eux appelle scheduler_relinquish().



Cependant, je vois cela comme un point de départ pour toute une série d'implémentations passionnantes de fonctionnalités utiles. Nous pouvons parler de tâches d'E / S lourdes, de l'implémentation d'une application asynchrone à un seul thread, de la même manière que les nouveaux utilitaires asynchrones fonctionnent en Python. Des générateurs et des coroutines peuvent également être implémentés à l'aide d'un tel système. Enfin, avec un travail acharné, ce système peut également être lié d'amitié avec les «vrais» threads du système d'exploitation pour fournir une concurrence supplémentaire si nécessaire. Un projet intéressant se cache derrière chacune de ces idées, et je vous recommande d'essayer d'en réaliser vous-même, cher lecteur.

C'est sur?

Je pense que c'est plus probable que oui! Le code d'assembly en ligne qui affecte le pointeur de pile ne peut pas être considéré comme sûr. Ne prenez pas le risque d'utiliser ces choses en production, mais assurez-vous de les bricoler et de faire des recherches!



Une implémentation plus sûre d'un tel système peut être construite en utilisant une API "non contextuelle" (voir man getcontext), qui vous permet de basculer entre ces types de "flux" d'espace utilisateur sans incorporer de code d'assemblage. Malheureusement, une telle API n'est pas couverte par les standards (elle a été supprimée de la spécification POSIX). Mais il peut toujours être utilisé dans le cadre de la glibc.

Comment faire déplacer un tel mécanisme?

Ce planificateur, tel que présenté ici, ne fonctionne que si les threads transfèrent explicitement le contrôle vers le planificateur. Ce n'est pas bon pour un programme général, par exemple pour un système d'exploitation, car un thread mal fait peut bloquer l'exécution de tout le monde (bien que cela n'ait pas empêché l'utilisation du multitâche coopératif sous MS-DOS!) Je ne pense pas que cela rende le multitâche coopératif clairement mauvais; tout dépend de l'application.



Lors de l'utilisation d'une API «hors contexte» non standard, les signaux POSIX stockent le contexte du code qui a été précédemment exécuté. En réglant la minuterie sur des bips périodiques, le planificateur de l'espace utilisateur peut en effet fournir une version fonctionnelle du multitâche préventif! Ceci est un autre projet cool qui mérite un article séparé.