Résumé

  • La livelock de réception apparaît lorsque les interruptions d’arrivée accaparent le processeur et empêchent protocole, émission ou application d’achever le traitement ; le débit utile peut alors tomber à zéro.
  • Mogul et Ramakrishnan ont associé interruption de réveil, scrutation en tourniquet, quota par rappel, rejet précoce, retour d’état des files et plafond de cycles. La scrutation sans quota échouait encore.
  • Les mesures provenaient d’un DECstation monoprocesseur lent sur Ethernet à 10 Mbit/s. Les quotas de cinq à dix paquets et les seuils de file n’étaient pas des réglages universels.

Beaucoup d’activité, aucun travail achevé

Une interruption donne à un événement matériel le droit de passer devant le travail ordinaire. Quand les arrivées sont rares, ce droit réduit la latence. Quand elles dépassent la capacité de traitement, il peut abolir toute progression.

Dans le modèle issu de 4.2BSD étudié par Mogul et Ramakrishnan, le pilote retirait les paquets de l’interface à un niveau de priorité élevé, puis les déposait dans une file IP. Le traitement protocolaire intervenait plus tard, à une priorité moindre. Chaque nouvelle arrivée pouvait donc interrompre l’étape chargée de vider la file. Une fois celle-ci pleine, le noyau continuait à investir des cycles dans des paquets qui seraient abandonnés avant la livraison.

Ce n’était pas un blocage définitif : la baisse du trafic rendait le système à nouveau productif. Pendant la surcharge, en revanche, le processeur fonctionnait à plein régime sans transmettre de paquet ni alimenter l’application. Le bon dénominateur n’était donc pas le nombre d’interruptions servies, mais le nombre de paquets arrivés au consommateur final.

La priorité des interruptions faisait office d’ordonnanceur caché

L’ordonnanceur général n’avait presque aucune prise sur ce travail. Une hiérarchie fixe de priorités décidait avant lui. Elle favorisait l’admission et affamait les étapes qui complétaient le service : protocoles, émission, maintenance des routes, gestion locale et processus utilisateur.

Le regroupement d’interruptions réduisait le coût unitaire et repoussait le point de rupture, sans corriger la structure. Une entrée plus efficace restait une entrée ; elle ne garantissait ni la sortie ni l’équité.

L’interruption réveille, la scrutation partage

Le noyau modifié conservait les interruptions à faible charge. À forte charge, le gestionnaire se contentait de signaler qu’un périphérique avait besoin d’attention, lançait un fil de scrutation et laissait les interruptions de cette interface masquées.

Le fil visitait ensuite en tourniquet les sources d’événements de réception et d’émission. Chaque rappel recevait un quota de paquets. Lorsque le travail en attente avait disparu, les interruptions étaient réarmées. Un paquet accepté depuis l’interface était poussé aussi loin que possible vers sa destination plutôt que remis dans une nouvelle file de priorité.

Cette combinaison comptait davantage que l’opposition entre interruption et scrutation. La première détectait vite un événement imprévisible. La seconde distribuait un flux devenu prévisible parce qu’il saturait déjà la machine.

L’échec sans quota

Le résultat le plus instructif fut négatif. Sans quota, le rappel d’entrée trouvait toujours un paquet supplémentaire et ne rendait jamais la main. La boucle de scrutation n’atteignait plus l’achèvement des émissions. Les descripteurs de sortie restaient occupés, la file d’émission se remplissait et le débit utile retombait presque à zéro.

La scrutation avait déplacé le monopole au lieu de le supprimer. Sur cette machine, cinq à dix paquets par tour donnaient un comportement stable et proche de l’optimum. Un lot plus grand réduisait le coût de passage mais augmentait la latence et le risque d’affamer les autres tâches. Les auteurs précisaient qu’un autre processeur ou une autre interface réclamerait un autre réglage.

Rejeter tôt et écouter l’aval

En surcharge, certains paquets ne peuvent pas être menés à terme. Les abandonner à l’interface évite de gaspiller pilote, protocole et mise en file sur une unité condamnée. Mais le rejet précoce n’est utile que si l’entrée sait que l’aval ne progresse plus.

Dans l’essai avec screend, le noyau suspendait l’entrée lorsque la file atteignait 75 %, la reprenait à 25 % et utilisait un délai d’environ une milliseconde comme soupape. Ces valeurs étaient choisies arbitrairement. Le résultat durable était la boucle de preuve : une file aval pleine devait arrêter l’admission, pas simplement enregistrer davantage de pertes tardives.

Un autre mécanisme comptait les cycles consommés par le réseau sur des fenêtres de dix millisecondes. Une fois la part autorisée épuisée, l’entrée s’arrêtait afin que les processus utilisateur et l’entretien du système puissent avancer. La console locale redevenait réactive ; les échanges distants restaient pénalisés par les pertes. Une réserve de CPU ne transformait pas la surcharge en capacité.

Des mesures avec leur dénominateur

Le routeur était un DECstation 3000/300 sous Digital UNIX V3.2, volontairement le plus lent des Alpha disponibles. Il reliait deux Ethernet à 10 Mbit/s. Chaque essai envoyait 10 000 datagrammes UDP de quatre octets de charge utile ; la cadence, imparfaitement régulière, était calculée sur plusieurs secondes.

Avec le noyau d’origine et screend, la dégradation commençait au-dessus d’environ 2 000 paquets par seconde et la livelock complète apparaissait vers 6 000. Sans screend, le débit culminait autour de 4 700 paquets par seconde. Le rapport interdit d’extrapoler ces chiffres aux réseaux et processeurs plus rapides. Le vrai SMP n’avait pas été testé, et la politique indiquait quand abandonner, non quel paquet méritait d’être sauvé.

La documentation actuelle de NAPI sous Linux décrit encore une forme familière : une interruption planifie une scrutation, les IRQ restent masquées pendant le traitement et un budget borne le tour. C’est une comparaison opérationnelle, pas la preuve que toute surcharge moderne serait la même pathologie.

Le profil Google Research de Mogul retrace son passage par DEC/Compaq WRL, HP Labs et l’infrastructure réseau de Google. L’article historique reste un travail commun avec Ramakrishnan. Sa leçon la plus solide tient dans le compteur refusé : une machine très occupée ne peut pas appeler « débit » ce qui n’atteint jamais la sortie.

Sources