Réinvention de la roue... des temporisations

Magazine
Marque
GNU/Linux Magazine
HS n°
Numéro
112
Mois de parution
janvier 2021
Spécialité(s)


Résumé

Les temporisations sont essentielles au sein des systèmes d'exploitation et dans certaines applications, pour déclencher des actions à l'échéance d'un délai. Il existe différents algorithmes pour les gérer de manière efficace. Cet article présente la fusion de deux d'entre eux, pour en tirer le meilleur.


Body

Les temporisations, essentielles dans les systèmes informatiques, doivent être gérées de manière efficace. Il existe des API standard dans Linux ou dans la GLIBC pour les mettre en œuvre. Cependant, pour des raisons d'optimisation ou de non-disponibilité de services adaptés à certains environnements logiciels ou matériels, des applications implémentent leur propre API. Cet article s'inscrit dans cette démarche en présentant deux algorithmes : la liste delta (delta list) et la roue des temporisations (timer wheel). Le premier est utilisé dans Minix [1], le célèbre système d'exploitation universitaire ancêtre de GNU/Linux. Le second est en service sous une certaine forme dans le noyau Linux [2]. Il sera ensuite proposé une fusion des deux solutions, afin de bénéficier d'une certaine complémentarité et obtenir de meilleures performances du point de vue de la latence et de la charge CPU induite.

1. Généralités sur les temporisations

1.1 Champs d'application

Les champs d'application des temporisations sont variés. En voici quelques exemples :

  • robustesse : dans le domaine des réseaux, un serveur peut se protéger contre les déconnexions subites des clients en armant une temporisation qui représente un délai maximum autorisé pour recevoir une réponse. En cas d'échéance du délai, les ressources dédiées au client sont désallouées pour être réaffectées à une nouvelle connexion ;
  • sécurité : lors de la connexion à un système, lorsque le mot de passe saisi est incorrect, le délai d'affichage des demandes suivantes est accru, de sorte à allonger le temps nécessaire à la connexion. Ainsi, on dissuade le pirate qui tente toutes les combinaisons possibles de caractères. C'est le principe des vitres dites à retard d'effraction. Elles ne sont pas indestructibles, mais le temps nécessaire à les briser est dissuasif. C'est aussi un des moyens utilisés pour parer les attaques par déni de service (Denial of Service ou DoS) [3]. Le serveur repère les adresses sources des systèmes qui le bombardent de requêtes et leur applique un délai de punition, pour étaler dans le temps l'acceptation des nouvelles demandes de connexion ;
  • planification : des utilitaires « calendrier » sont basés sur des temporisations à l'échéance desquelles des opérations de maintenance sont réalisées ;
  • fiabilité : certains garbage collectors, notamment dans les services de gestion mémoire (RAM ou disques), sont déclenchés cycliquement pour défragmenter les données, de sorte à garantir des temps de réponse moyens raisonnables. Les protocoles réseau tels que TCP garantissent le transfert des données de bout en bout en procédant à des retransmissions en interne lorsqu'à échéance de temporisations, certains acquittements sont perdus.

1.2 Types

Les champs d'application précédents permettent de distinguer deux types de temporisations :

  • temporisations dites de garde (timeout) qui ne sont pas censées échoir dans un mode de fonctionnement normal : elles sont en général arrêtées avant terme. À échéance, elles entraînent un mécanisme de rectification pour organiser un retour à l'état normal (par exemple, déconnexion d'un interlocuteur réseau qui ne répond plus ou retransmission d'un paquet perdu sur le réseau) ;
  • temporisations de planification qui vont à leur terme (run to completion) pour déclencher des activités dans le futur (par exemple, rappel d'un rendez-vous dans un utilitaire de calendrier ou délai avant affichage d'une nouvelle demande de saisie de mot de passe).

Ce dernier cas se décline en deux sous-catégories : les temporisations normales (one shot) qui une fois arrivées à leur terme ne sont pas forcément réarmées et les temporisations cycliques qui expirent périodiquement.

1.3 Opérations

Une API de gestion des temporisations propose les opérations suivantes :

  • allocation/démarrage d'une temporisation qui reçoit en entrée un type (normal ou cyclique), la durée avant expiration et l'action effectuée à échéance de la temporisation. Cela peut se faire en passant le pointeur sur une fonction à appeler (callback) ou un message à envoyer vers un destinataire. L'identifiant d'un descripteur de temporisation est en général retourné pour référence dans les opérations suivantes ;
  • arrêt d'une temporisation qui reçoit en entrée l'identifiant afin de désarmer la temporisation associée avant son terme. Cette fonction se charge aussi, quand c'est possible, de la résolution des cas de croisement. En effet, lorsque des tâches s'exécutent en parallèle, il peut arriver que l'application demande à arrêter une temporisation déjà échue. Si les structures de données le permettent, il faudra annuler l'appel de la fonction d'échéance ou supprimer le message d'échéance déjà posté dans la queue de réception du destinataire ;
  • désallocation d'une temporisation qui reçoit en entrée l'identifiant. Cette fonction est appelée quand il n'est plus envisagé d'utiliser la temporisation à plus ou moins long terme.

1.4 Granularité

Les temporisations sont cadencées par une pulsation périodique (tick) à l'échéance de laquelle on détermine quelles sont les temporisations expirées. La période du tick détermine la précision de la date d'échéance des temporisations. Quand on arme une temporisation pour une durée donnée, celle-ci est divisée par la période du tick et arrondie au tick supérieur, si nécessaire. Pour plus de précision, on a donc intérêt à avoir un tick de période la plus petite possible, mais la latence de traitement de l'échéance de la temporisation ainsi que les capacités matérielles sont des facteurs limitatifs. L'efficacité de l'algorithme utilisé pour gérer l'échéance est primordiale pour réduire la latence.

2. Algorithme de la liste delta

2.1 Principe et structures de données

Le code source de la librairie ainsi que l'API mettant en œuvre l'algorithme se trouvent respectivement dans les fichiers tdl.c et tdl.h.

La structure tdl_desc_t définit un descripteur de temporisation :

typedef struct tdl_link
{
  struct tdl_link *next;
  struct tdl_link *prev;
} tdl_link_t;
[...]
typedef struct tdl_desc
{
  unsigned int delta;
 
  tdl_link_t link;
 
  unsigned int timeout;
  int          type; // TDL_TIMER_NORMAL ou TDL_TIMER_CYCLIC
 
  void (* user_cbk)(void *user_ctx);
  void *user_ctx;
} tdl_desc_t;

Le champ timeout est la durée en pulsations de la temporisation. Elle est fournie par la fonction de démarrage. On parlera de période d'échéance si la temporisation est de type cyclique (champ type égal à TDL_TIMER_CYCLIC).

Le champ link regroupe, dans la structure tdl_link_t, les liens avant et arrières dans la liste doublement chaînée de tous les descripteurs de temporisations armées. La tête de cette liste est mémorisée dans la variable globale tdl_timers du fichier tdl.c.

static tdl_link_t tdl_timers;

Le choix d'un double chaînage permet l'ajout et la suppression efficaces des éléments dans la liste, car il n'y a pas besoin de la parcourir. Trois macros réalisent les opérations courantes dans la liste (ajout d'un élément avant un autre, suppression d'un élément et test de liste vide) :

#define TDL_LINK_BEFORE(l, lnext) do { (l)->next = (lnext);       \
                                           (l)->prev = (lnext)->prev; \
                                           (lnext)->prev->next = (l); \
                                           (lnext)->prev = (l); } while(0)
[...]
#define TDL_UNLINK(l) do { (l)->next->prev = (l)->prev; \
                              (l)->prev->next = (l)->next; } while(0)
[...]
#define TDL_IS_EMPTY(list) ((list)->next == (list))

La macro TDL_LINK2DESC() s'appuie sur la macro standard offsetof() pour retrouver l'adresse de début du descripteur de temporisation à partir de l'adresse des liens :

#define TDL_LINK2DESC(l) ((tdl_desc_t *)(((char *)(l)) - offsetof(tdl_desc_t, link)))

Les champs user_cbk et user_ctx sont respectivement le pointeur sur la fonction à appeler et le pointeur sur un contexte utilisateur à passer à cette dernière, lorsque la temporisation est échue.

Le champ delta est le délai d'échéance associé à ce descripteur après l'expiration de la temporisation dont le descripteur est situé juste avant dans la liste. C'est le principe de base de l'algorithme où le délai d'échéance d'un descripteur correspond à la somme de son champ delta avec les champs delta des descripteurs qui le précèdent dans la liste. La figure 1 illustre le fonctionnement en cinq étapes :

v-figure 01 delta list

Fig. 1 : Algorithme de la liste delta.

En étape 1, les pointeurs avant et arrières de la structure tdl_timers autoréférencent la structure pour signifier que la liste est vide.

En étape 2, une temporisation de 5 ticks est insérée (bloc vert).

En étape 3, une temporisation de 3 ticks est insérée (bloc jaune). Pour trouver sa place, la liste est parcourue du début vers la fin et le champ delta de son descripteur est décrémenté de la valeur de chaque champ delta rencontré, tant que ce dernier est inférieur ou égal à sa valeur courante. Comme la première valeur rencontrée est 5 (donc supérieure), le nouveau descripteur est inséré devant le premier descripteur (bloc vert), dans lequel on prend soin de soustraire à son champ delta la valeur du même champ du descripteur nouvellement inséré (c.-à-d. 3). D'où la nouvelle valeur égale à 2 du champ delta du bloc vert. La première temporisation (bloc vert) tombera bien à échéance dans 5 ticks, ou plutôt 2 ticks après la temporisation de 3 ticks (bloc jaune) nouvellement insérée devant elle.

En étape 4, une nouvelle temporisation de 5 ticks (bloc noir) est insérée. Pour trouver sa place, on procède de même qu'à l'étape précédente, en parcourant la liste du début vers la fin. La position du nouveau descripteur sera donc juste avant le premier descripteur rencontré avec un champ delta supérieur ou lorsqu'on a atteint la fin de liste, comme dans cette étape. D'où la décrémentation de 3, puis 2 de son champ delta. Le champ est donc 0, car la temporisation associée doit tomber à échéance au même moment que la temporisation (bloc vert) située avant lui (c.-à-d. dans 3 + 2 + 0 = 5 ticks).

En étape 5, un arrêt avant terme est demandé pour la seconde temporisation (bloc jaune). Le descripteur est enlevé de la liste, mais on prend soin au préalable d'incrémenter le champ delta du descripteur situé juste après (bloc vert) avec la valeur du même champ du descripteur enlevé (c.-à-d. 2 + 3 = 5). Ainsi, le délai d'expiration de la temporisation associée sera bien dans 5 ticks.

À chaque pulsation de l'horloge, il suffit de décrémenter le champ delta du premier descripteur de la liste. Lorsque ce dernier atteint la valeur 0, toutes les temporisations associées aux descripteurs ayant leur champ delta à 0 en tête de liste sont échues. Leur descripteur est enlevé de la liste et la fonction utilisateur correspondante est appelée.

À l'image du système Minix, l'organisation des temporisations en liste delta est donc plutôt simple, car il est destiné avant tout à l'enseignement. Mais il n'en reste pas moins efficace et astucieux !

2.2 Allocation/désallocation

La fonction tdl_alloc() crée une temporisation. Elle reçoit en paramètre le type (cyclique ou non) de la temporisation. Le service alloue dynamiquement, via malloc(), une structure tdl_desc_t et retourne son adresse. Inutile de présenter le code source, car la fonction est triviale. De sorte à garder une opacité sur les structures de données internes au service, l'adresse retournée à l'utilisateur est un pointeur anonyme de type tdl_t défini dans le fichier d'en-tête tdl.h :

typedef void *tdl_t;

Ce pointeur servira de référence pour la temporisation dans les autres routines de l'API.

tdl_free() désalloue un descripteur de temporisation précédemment alloué par tdl_alloc(). Ce service, tout aussi trivial, reçoit en paramètre le descripteur et appelle la fonction free() pour libérer l'espace mémoire.

2.3 Armement/arrêt

La fonction tdl_start() démarre une temporisation. Elle reçoit en paramètres l'identifiant retourné par tdl_alloc(), la durée de la temporisation (en ticks), un pointeur sur une fonction à appeler au moment de l'échéance, ainsi qu'un pointeur sur un contexte à passer à cette dernière :

int tdl_start(tdl_t          timer,
              unsigned int   timeout,
              void         (* user_cbk)(void *),
              void          *user_ctx)
{
tdl_link_t *l, *lnext;
tdl_desc_t *tmr, *tmr_next;
[...]
  // Accès au descripteur à partir de l'identifiant
  tmr = (tdl_desc_t *)timer;
  l = &(tmr->link);
 
  // Début d'exclusion mutuelle
  TDL_LOCK();
 
  // Si le descripteur est chaîné, c'est un redémarrage
  // ==> On le déchaîne
  if (l->next != l) {
[...]
  }
 
  // Recherche de l'emplacement dans la liste delta
  tmr->delta = timeout;
  lnext = tdl_timers.next;
  while (lnext != &tdl_timers) {
 
    tmr_next = TDL_LINK2DESC(lnext);
 
    if (tmr_next->delta < tmr->delta) {
 
      tmr->delta -= tmr_next->delta;
      lnext = lnext->next;
 
    } else {
 
      tmr_next->delta -= tmr->delta;
      break;
 
    }
 
  } // End while
 
  // tmr_next est le descripteur avant lequel tmr est inséré
  TDL_LINK_BEFORE(l, lnext);
 
  // Renseignement du descripteur
  tmr->timeout = timeout;
  tmr->user_cbk = user_cbk;
  tmr->user_ctx = user_ctx;
 
  // Fin d'exclusion mutuelle
  TDL_UNLOCK();
 
  return 0;
} // tdl_start

La boucle while du service met en œuvre l'algorithme de la liste delta vu plus haut pour insérer le descripteur au bon endroit dans la liste. L'API étant destinée à un environnement multithread, une exclusion mutuelle (sous la forme des macros TDL_LOCK/UNLOCK()) est nécessaire pour protéger l'accès à la liste des temporisations. Ici, le service d'exclusion mutuelle est basé sur les futex [4] (dans les fichiers mtx.c et mtx.h), mais on aurait aussi pu utiliser les services POSIX standard de la GLIBC, basés eux aussi, sur les futex. Les sémaphores System V sont par contre déconseillés pour leur lenteur !

Bien que le code source correspondant n'est pas exposé, la fonction gère aussi le redémarrage d'une temporisation avec une échéance éventuellement différente. Cela consiste à enlever le descripteur correspondant de la liste (comme le fait tdl_stop()), avant de le réinsérer à son nouvel emplacement.

La fonction tdl_stop() arrête une temporisation. Cette dernière reçoit en paramètre l'identifiant retourné par le service tdl_alloc() et déchaîne le descripteur de la liste des temporisations armées. Conformément à l'algorithme détaillé plus haut, s'il y a un successeur dans la liste, le champ delta de ce dernier est incrémenté avec la valeur du même champ dans le descripteur en cours de suppression :

int tdl_stop(tdl_t timer)
{
tdl_link_t *l;
tdl_desc_t *tmr, *tmr_next;
[...]
  tmr = (tdl_desc_t *)timer;
  l = &(tmr->link);
 
  TDL_LOCK();
[...]
  // Si le descripteur n'est pas le dernier de la liste,
   // incrémenter le champ delta du descripteur qui suit
  if (l->next != &tdl_timers) {
 
    tmr_next = TDL_LINK2DESC(l->next);
    tmr_next->delta += tmr->delta;
 
  }
 
  // Déchaînage du descripteur
  TDL_UNLINK(l);
  l->prev = l->next = l;
 
  TDL_UNLOCK();
 
  return 0;
} // tdl_stop

2.4 La pulsation

L'API est dans une librairie partagée libtdl.so dont le point d'entrée démarre implicitement un thread. Ce dernier est en charge de gérer la pulsation qui décrémente le champ delta du premier descripteur de la liste. La période TDL_TICK_PERIOD du tick est de 1 milliseconde :

#define TDL_TICK_PERIOD 1000 // microsecondes ==> 1 milliseconde

En espace utilisateur, différentes options s'offrent à nous pour générer le tick. Nous choisissons la fonction select() temporisée au sein d'une boucle infinie dans le point d'entrée tdl_engine() du thread. On gère aussi un pipe dont le côté en lecture tdl_fifo[0] est passé à select(). Cela permet à la fonction de sortie de la librairie (en cas de déchargement dynamique) d'envoyer un message pour signifier au thread de s'arrêter (sortie de la boucle infinie). Nous ne présentons ici que la section de code chargée de décrémenter le champ delta de la tête de la liste des temporisations. Quand ce champ atteint la valeur 0, la temporisation associée est échue. Il en est de même pour les descripteurs suivants.

static void *tdl_engine(void *ctx)
{
[...]
  // Période du tick
  tick.tv_sec = 0;
  tick.tv_usec = TDL_TICK_PERIOD;
 
  // Tant que la librairie n'est pas déchargée
  while(!end) {
 
    FD_ZERO(&set);
    FD_SET(tdl_fifo[0], &set);
    rc = select(tdl_fifo[0] + 1, &set, NULL, NULL, &tick);
 
    switch(rc) {
[...]
      case 0: {
 
        // Timeout
        TDL_LOCK();
 
        // S'il y a des temporisations actives (liste non vide)
        if (!TDL_IS_EMPTY(&tdl_timers)) {
 
          // Décrémentation du champ delta du premier de la liste
          tmr = TDL_LINK2DESC(tdl_timers.next);
          tmr->delta -= 1;
 
          // Déchaînage de tous les descripteurs expirés
          while (!(tmr->delta)) {
 
            // Déchaînage du premier de la liste
            TDL_UNLINK(&(tmr->link));
            tmr->link.prev = tmr->link.next = &(tmr->link);
 
            // Si c'est une temporisation cyclique, on la chaîne de
                  // nouveau pour la prochaine expiration
            if (tmr->type == TDL_TIMER_CYCLIC) {
[...]
            }
 
            // Appel de la fonction utilisateur en dehors de la section
                  // critique pour éviter un interblocage si la fonction fait appel
                  // au service de temporisation
            TDL_UNLOCK();
            tmr->user_cbk(tmr->user_ctx);
            TDL_LOCK();
 
            // Comme on est sorti de la section critique pendant l'appel
                  // à la fonction utilisateur, la liste peut avoir changé
                  // ==> On repointe systématiquement sur le début de la liste
            tmr = TDL_LINK2DESC(tdl_timers.next);
 
          } // End while timers expirés
 
        } // End if timers actifs
 
        TDL_UNLOCK();
 
        // Réarmement du tick
        tick.tv_sec = 0;
        tick.tv_usec = TDL_TICK_PERIOD;
 
      }
      break;
[...]
    } // End switch
 
  } // End while
 
  return NULL;
} // tdl_engine

2.5 Complexité

L'armement d'une temporisation (fonction tdl_start()) peut amener, dans le pire des cas, à parcourir toute la liste des temporisations armées afin d'insérer le descripteur en dernière position. Sa complexité est par conséquent O(N). L'arrêt d'une temporisation (fonction tdl_stop()) est par contre O(1), car le double chaînage permet d'extraire le descripteur de la liste sans la parcourir. La gestion de la pulsation dans la boucle du thread est aussi O(1), car seul le champ delta du premier descripteur de temporisation de la liste est décrémenté. La gestion de l'échéance des temporisations dans la boucle du thread est O(N), car dans le pire des cas, toutes les temporisations expirent en même temps. On ne peut pas faire mieux pour ce cas précis. Mais cela tient plus du cas d'école que d'une situation courante.

3. Algorithme de la roue des temporisations

3.1 Principe et structures de données

Le code source de la librairie ainsi que l'API mettant en œuvre l'algorithme se trouvent respectivement dans les fichiers ttw.c et ttw.h. Il se schématise comme une roue de bicyclette dont les rayons sont représentés par les listes de temporisations armées. L'écart entre les rayons correspond à la période de la pulsation. À chaque tick, la roue tourne sur une distance correspondant à l'espace entre deux rayons. Traduit en langage informatique, il s'agit d'un tableau de listes chaînées indexé de manière circulaire avec une opération modulo. À chaque pulsation, l'index circulaire s'incrémente d'une unité pour référencer l'entrée suivante dans la table où se trouvent éventuellement des temporisations qui doivent échoir à ce moment, ou après un ou plusieurs tours supplémentaires de la roue. La figure 2 illustre le propos.

v-figure 02 timer wheel

Fig. 2 : Algorithme de la roue des temporisations.

Dans la figure, la roue présente 19 entrées (ticks). Dans certaines d'entre elles se trouvent des listes de temporisations armées. L'index circulaire courant dans la table est en position 2. À chaque pulsation, il est incrémenté par l'opération :

index_tick = (index_tick + 1) % taille_roue

Cette opération retourne l'indice suivant entre 0 et la taille de la roue moins 1 (c.-à-d. entre 0 et 18 pour l'exemple de la figure). Il est actuellement à la position 2.

L'index de l'entrée de la liste du descripteur d'une temporisation est calculé avec l'opération suivante :

index_tempo = (index_tick + (valeur_tempo % taille_roue)) % taille_roue

Mais son échéance n’arrivera qu'après un nombre de rotations correspondant à la division entière de la durée d'échéance par le nombre d'entrées dans la roue :

nombre_rotations = valeur_tempo / taille_roue

Ainsi sur la figure, la temporisation de 54 ticks est mise dans la liste à l'indice 18, mais elle ne sera échue qu'après 2 tours de roue. La temporisation de 6 ticks est, quant à elle, chaînée dans la liste à l'indice 8 et sera échue dès que l'index de la pulsation aura atteint cette valeur, car le nombre de rotations associé est à 0.

Le champ « nombre de rotations » des descripteurs est décrémenté à chaque fois que l'index courant de la pulsation référence leur entrée dans la roue. Cela signifie qu'à chaque tick, un parcours de bout en bout de la liste est effectué pour décrémenter les champs « nombre de rotations » différents de 0 (temporisations qui expireront dans les tours suivants) et enlever les descripteurs dont ce même champ est à 0 (temporisations échues dans le tour courant).

3.2 Allocation/désallocation

Les fonctions ttw_alloc() et ttw_free() sont triviales. Comme leurs homologues dans l'API de l'algorithme de la liste delta, elles consistent à allouer/désallouer un descripteur ttw_desc_t de temporisation :

typedef struct ttw_desc
{
  unsigned int rotations;
 
  ttw_link_t link;
 
  unsigned int timeout;
  int          type;
 
  void (* user_cbk)(void *user_ctx);
  void *user_ctx;
  ttw_link_t cbk_link;
} ttw_desc_t;

La structure est calquée sur le descripteur de l'algorithme de la liste delta, à ceci près que le champ delta est remplacé par le champ rotations. Même si nous ne le détaillerons pas, il y a aussi en plus le lien cbk_link qui sert à lier le descripteur dans une liste provisoire lors de l'appel de la fonction utilisateur, à échéance de la temporisation.

La roue des temporisations est la table globale ttw_wheel[] allouée dynamiquement au démarrage avec TTW_SIZE entrées. Ce sont les têtes des listes de descripteurs de temporisation qui tomberont à échéance lorsque l'indice courant global ttw_index référencera leur entrée. Cet indice est incrémenté d'une unité à chaque pulsation de période TTW_TICK_PERIOD microsecondes.

3.3 Démarrage/arrêt

La fonction ttw_start() démarre une temporisation. Ses paramètres sont identiques à ceux de la même fonction pour l'algorithme précédent :

int ttw_start(ttw_t          timer,
               unsigned int   timeout,
               void         (* user_cbk)(void *),
               void          *user_ctx)
{
ttw_link_t   *l, *lend;
ttw_desc_t   *tmr;
unsigned int index;
[...]
  tmr = (ttw_desc_t *)timer;
  l = &(tmr->link);
 
  TTW_LOCK();
 
  // Si le descripteur est dans une liste, c'est un redémarrage
   // ==> On l'enlève de sa liste
  if (l->next != l) {
[...]
  } // End if
 
  // Recherche de l'index dans la roue
  index = (ttw_index + timeout % TTW_SIZE) % TTW_SIZE;
 
  // Calcul du nombre de rotations de la roue avant échéance
  tmr->rotations = timeout / TTW_SIZE;
 
  // Insertion du descripteur en fin de liste
  lend = &(ttw_wheel[index]);
  TTW_LINK_BEFORE(l, lend);
 
  // Renseignement du descripteur
  tmr->timeout = timeout;
  tmr->user_cbk = user_cbk;
  tmr->user_ctx = user_ctx;
 
  TTW_UNLOCK();
 
  return 0;
} // ttw_start

En fait, l'algorithme est une table de hachage qui ne dit pas son nom. La fonction de répartition étant l'opération modulo de la durée de la temporisation par TTW_SIZE afin de déterminer l'indice de la liste dans laquelle sera inséré le descripteur.

La fonction ttw_stop() arrête une temporisation. Elle reçoit en paramètre l'identifiant retourné par le service ttw_alloc(). Son code est trivial, car il s'agit tout simplement d'enlever le descripteur de la liste doublement chaînée des temporisations.

3.4 La pulsation

Comme pour l'algorithme précédent, le service démarre implicitement un thread dans le point d'entrée de la librairie partagée libttw.so. La pulsation est générée via l'appel système select() temporisé avec la période TTW_TICK_PERIOD. À chaque pulsation, le thread incrémente de manière circulaire (opération modulo avec TTW_SIZE) l'indice courant ttw_index dans la roue. Si la liste de l'entrée correspondante dans la table n'est pas vide, elle est parcourue d'un bout à l'autre pour déchaîner les descripteurs dont le champ rotations est à 0 (temporisations échues) et décrémenter ce même champ pour les autres (temporisations qui échoiront dans les tours suivants). Les fonctions utilisateur sont bien entendu appelées pour les temporisations expirées. Pour celles qui sont de type cyclique, le nouvel emplacement du descripteur dans la roue est calculé afin de le chaîner dans la liste correspondante.

static void *ttw_engine(void *ctx)
{
[...]
  // Période du tick
  tick.tv_sec = 0;
  tick.tv_usec = TTW_TICK_PERIOD;
 
  while(!end) {
[...]
    rc = select(ttw_fifo[0] + 1, &set, NULL, NULL, &tick);
 
    switch(rc) {
[...]
      // Timeout
      case 0: {
 
        TTW_LOCK();
 
        // Incrémentation de l'index courant dans la roue
        ttw_index = (ttw_index + 1) % TTW_SIZE;
 
        // Rayon courant (c.-à-d. liste de descripteurs)
        spoke = &(ttw_wheel[ttw_index]);
 
        // Initialisation de la liste où seront provisoirement stockées
            // les temporisations échues pour appeler leur callback
        cbk_list.prev = cbk_list.next = &cbk_list;
 
        // Si des temporisations sont actives (liste courante non vide)
        if (!TTW_IS_EMPTY(spoke)) {
 
          // First element in the list
          l = spoke->next;
 
          // Parcours de la liste du début à la fin
               // Déchaînage de tous les descripteurs échus (rotations = 0)
               // et décrémentation du champ rotation pour les autres
          while (l != spoke) {
 
            tmr = TTW_LINK2DESC(l);
 
            // Si la temporisation est échue
            if (tmr->rotations == 0) {
[...]
              // Déchaînage du descripteur
              TTW_UNLINK(l);
[...]
              // Chaînage du descripteur dans la liste des callbacks à appeler
              TTW_LINK_BEFORE(&(tmr->cbk_link), &(cbk_list));
 
              // Descripteur suivant
              l = lnext;
 
            } else {
 
              // Décrémentation des rotations
              tmr->rotations -= 1;
 
              // Descripteur suivant
              l = l->next;
            } // End if
 
          } // End while
 
          // Parcours de liste des callbacks pour appeler les
                // fonctions utilisateur des temporisations échues
                // Les temporisations cycliques sont remises à leur nouvel
                // emplacement dans la roue
          if (!TTW_IS_EMPTY(&cbk_list)) {
[...]
          } // End if temporisations échues
 
        } // End if temporisations actives
 
        TTW_UNLOCK();
 
        // Réarmement de la pulsation
        tick.tv_sec = 0;
        tick.tv_usec = TTW_TICK_PERIOD;
 
      }
      break;
[...]
    } // End switch
 
  } // End while
 
  return NULL;
 
} // ttw_engine

3.5 Complexité

L'armement d'une temporisation (fonction ttw_start()) est O(1), car il s'agit d'insérer le descripteur en fin de liste à l'indice dans la roue correspondant à la durée de la temporisation. L'arrêt d'une temporisation (fonction ttw_stop()) est aussi O(1), car le double chaînage permet d'extraire le descripteur de sa liste sans la parcourir. La gestion de la pulsation dans la boucle du thread est O(N), car il faut parcourir tous les éléments de la liste située à l'indice courant dans la roue pour repérer les temporisations échues (champ rotations à 0) et décrémenter le champ rotations des temporisations qui échoiront dans les tours suivants. Dans le pire des cas, toutes les temporisations armées peuvent s'y trouver (cas d'école). De même, la gestion de l'échéance des temporisations dans la boucle du thread est O(N), car dans le pire des cas, toutes les temporisations expirent en même temps (cas d'école).

4. Fusion des algorithmes

Les rayons de la roue souffrent d'un parcours complet des listes de temporisations afin de repérer celles qui sont échues et de décrémenter le champ rotations pour les autres. C'est un parcours systématique sur toute la liste à l'échéance de la pulsation (complexité O(N) !). Pour éviter ou accélérer ce parcours complet, [6] propose un ordonnancement de la liste. C'est justement l'idée de notre amélioration. Elle consiste à appliquer le principe de la liste delta sur chaque rayon de la roue. En clair, les deux algorithmes sont fusionnés. Le champ rotations, renommé delta_rotations, est géré comme le champ delta du premier algorithme présenté. Ainsi, à chaque pulsation de l'horloge, si le champ delta_rotations du premier descripteur de la liste courante est à 0, la temporisation correspondante ainsi que celles qui suivent avec le même champ à 0 sont échues. Sinon, on ne décrémente que le champ delta_rotations du premier descripteur de la liste. Il n'y a plus de parcours systématique de toute la liste ! L'algorithme résultant est donc une synthèse du meilleur des deux solutions précédentes. On l'appelle temporisations sur roue delta (ou TDW pour Timers on Delta Wheel).

Le code source de l'API est dans les fichiers tdw.c et tdw.h. La librairie partagée correspondante se nomme libtdw.so. Pour rester concis, nous ne détaillons pas les sources, car la description des deux premières API permet de comprendre la troisième. Nous sommes simplement partis du code source de la seconde dans laquelle la manipulation des listes chaînées de la roue utilise l'algorithme de la liste delta.

La figure 3 énumère la complexité des opérations dans chaque algorithme.

figure 03 complexity

Fig. 3 : Complexité des algorithmes.

Nous avons amélioré le traitement de l'échéance de la pulsation qui passe de O(N) à O(1). C'est de bon augure pour la charge CPU moyenne induite par le service à chaque tick. Du côté de l'échéance des temporisations, même si la complexité théorique O(N) ne change pas, d'un point de vue purement pratique, nous nous trouvons très rarement dans le pire cas (c.-à-d. le cas où toutes les temporisations expirent en même temps). Ce sont donc les deux points essentiels d'amélioration apportés par la fusion.

Le démarrage de la temporisation passe de O(1) à O(N), car c'est le principe de la liste delta qui s'applique. C'est le prix, plus souvent théorique que pratique, à payer pour être O(1) au moment du traitement de la pulsation. Cependant, on peut noter qu'en positionnant la taille de la roue TDW_SIZE à 1, on n'a plus qu'un rayon. En d'autres termes, on a une seule liste correspondant tout simplement à l'algorithme de base de la liste delta. Augmenter le nombre d'entrées dans la roue revient à découper la liste delta en plusieurs listes plus courtes, de sorte à diminuer le temps moyen de parcours de la liste lors de l'insertion d'un nouveau descripteur de temporisation. Le temps de démarrage d'une temporisation est donc en pratique meilleur quand le nombre d'entrées dans la roue augmente.

Conclusion

Améliorer un algorithme s'apparente souvent à réinventer la roue, tant l'effort peut être vain. L'algorithme universel qui répond à tous les besoins n'existe pas en général. Le choix est guidé par les capacités matérielles (CPU, mémoire), le profil d'exécution (quantité de ressources simultanées) ou encore la latence du service (temps de réponse moyen stable ou tolérance de certains pics de charge). La gestion des temporisations présentée dans cet écrit synthétise le meilleur de deux algorithmes. Sans vouloir s'imposer comme une nouvelle référence, il a le mérite d'élargir le choix en la matière [7].

Les exemples d'implémentation de cet article doivent être plus robustes et configurables pour un usage dans des applications. Une version améliorée de la librairie TDW est disponible sous licence LGPL [8].

Références

[1] Le système Minix : https://fr.wikipedia.org/wiki/Minix

[2] Reinventing the timer wheel : https://lwn.net/Articles/646950/

[3] Attaque par déni de service : https://fr.wikipedia.org/wiki/Attaque_par_d%C3%A9ni_de_service

[4] R. KOUCHA, « Approche détaillée des futex », GNU/Linux Magazine nos 173, 175, 176 et 178 : https://connect.ed-diamond.com/GNU-Linux-Magazine/GLMF-173/Approche-detaillee-des-futex-partie-1-4 pour le premier.

[5] An embedded Single Timer Wheel : https://www.drdobbs.com/embedded-systems/an-embedded-single-timer-wheel/217800350

[6] G. VARGHESE et T. LAUCK, « Data Structures for the Efficient Implementation of a Timer Facility » : http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf

[7] A. COLYER, « Data structures for the efficient implementation of a timer facility » : https://blog.acolyer.org/2015/11/23/hashed-and-hierarchical-timing-wheels/

[8] La librairie TDW : https://sourceforge.net/projects/tdwheel/



Article rédigé par

Par le(s) même(s) auteur(s)

À la découverte des namespaces mount et uts

Magazine
Marque
GNU/Linux Magazine
Numéro
247
Mois de parution
avril 2021
Spécialité(s)
Résumé

Le namespace mount, premier d'une longue série de namespaces a été ajouté à Linux quelques années après chroot() pour offrir plus de possibilités et de sécurité dans l'isolation des systèmes de fichiers. Introduit peu après et indéniablement plus simple, le namespace uts permet d'instancier les noms de machine. Les conteneurs sont bien entendu les premiers clients de ces fonctionnalités.

Les derniers articles Premiums

Les derniers articles Premium

Cryptographie : débuter par la pratique grâce à picoCTF

Magazine
Marque
Contenu Premium
Spécialité(s)
Résumé

L’apprentissage de la cryptographie n’est pas toujours évident lorsqu’on souhaite le faire par la pratique. Lorsque l’on débute, il existe cependant des challenges accessibles qui permettent de découvrir ce monde passionnant sans avoir de connaissances mathématiques approfondies en la matière. C’est le cas de picoCTF, qui propose une série d’épreuves en cryptographie avec une difficulté progressive et à destination des débutants !

Game & Watch : utilisons judicieusement la mémoire

Magazine
Marque
Contenu Premium
Spécialité(s)
Résumé

Au terme de l'article précédent [1] concernant la transformation de la console Nintendo Game & Watch en plateforme de développement, nous nous sommes heurtés à un problème : les 128 Ko de flash intégrés au microcontrôleur STM32 sont une ressource précieuse, car en quantité réduite. Mais heureusement pour nous, le STM32H7B0 dispose d'une mémoire vive de taille conséquente (~ 1,2 Mo) et se trouve être connecté à une flash externe QSPI offrant autant d'espace. Pour pouvoir développer des codes plus étoffés, nous devons apprendre à utiliser ces deux ressources.

Raspberry Pi Pico : PIO, DMA et mémoire flash

Magazine
Marque
Contenu Premium
Spécialité(s)
Résumé

Le microcontrôleur RP2040 équipant la Pico est une petite merveille et malgré l'absence de connectivité wifi ou Bluetooth, l'étendue des fonctionnalités intégrées reste très impressionnante. Nous avons abordé le sujet du sous-système PIO dans un précédent article [1], mais celui-ci n'était qu'une découverte de la fonctionnalité. Il est temps à présent de pousser plus loin nos expérimentations en mêlant plusieurs ressources à notre disposition : PIO, DMA et accès à la flash QSPI.

Les listes de lecture

9 article(s) - ajoutée le 01/07/2020
Vous désirez apprendre le langage Python, mais ne savez pas trop par où commencer ? Cette liste de lecture vous permettra de faire vos premiers pas en découvrant l'écosystème de Python et en écrivant de petits scripts.
11 article(s) - ajoutée le 01/07/2020
La base de tout programme effectuant une tâche un tant soit peu complexe est un algorithme, une méthode permettant de manipuler des données pour obtenir un résultat attendu. Dans cette liste, vous pourrez découvrir quelques spécimens d'algorithmes.
10 article(s) - ajoutée le 01/07/2020
À quoi bon se targuer de posséder des pétaoctets de données si l'on est incapable d'analyser ces dernières ? Cette liste vous aidera à "faire parler" vos données.
Voir les 53 listes de lecture

Abonnez-vous maintenant

et profitez de tous les contenus en illimité

Je découvre les offres

Déjà abonné ? Connectez-vous