ARSE23 · Architecture d'un système d'exploitation¶

Une UE rare : un cours de systèmes d'exploitation écrit du point de vue du HPC, qui va jusqu'aux noyaux allégés de classe exascale.

Fiche signalétique¶


Code	ARSE23
Crédits	4 ECTS, 42 h
Semestre	3, option — lundi après-midi
Responsable	WIBER Gilles
Concurrentes sur le créneau	aucune sur ce créneau
Choix	Une seule option au S3, avec l'accord de l'entreprise
Prérequis	Aucun (OSSE11 de première année suffit)
Effectif max	30

Ce que dit la brochure¶

Objectifs cités :

« Cette UE présente les éléments d'un système d'exploitation en détaillant les composants critiques pour un système HPC. Le cours s'appuiera sur le noyau Linux et des exemples de systèmes allégés. Les étudiants seront en fin d'UE capables de décrire les différents composants d'un OS ainsi que plusieurs implémentations de ses composants. Ils sauront modifier un noyau Linux et comprendront l'influence des paramétrages et algorithmes sur les performances. »

Contenu cité, en sept parties :

Composants d'un système : historique des systèmes, besoins du HPC, composants d'un système, boot d'un système, génération et paramétrage du noyau Linux (TP).
Allocateur mémoire : mécanisme de pagination et optimisation matérielle (TLB, huge pages), impact de la pagination en contexte HPC, évaluation des mécanismes de pagination dans un simulateur (TD), problématique de l'allocation parallèle en contexte NUMA, présentation des différents allocateurs mémoire utilisateur, mise en œuvre dans un allocateur utilisateur (TD).
Ordonnanceur : algorithmes classiques d'ordonnancement, étude de l'ordonnanceur Linux, mise en œuvre dans une bibliothèque de threads utilisateur (TD).
Sécurité : rôle et fonctionnement de la sécurité au sein d'un système.
Systèmes de fichiers locaux : historique, architectures et mécanismes (principe de VFS, journaux, copy-on-write), exemples (FFS, extN, ZFS, log structured FS), mise en œuvre et manipulation des structures (TP : génération, debugfs).
Débogage système : traces systèmes, débogage (gdb), introduction à l'analyse de crash.
Optimisations systèmes : grands principes et outils d'optimisation du système, paramètres du noyau Linux, systèmes allégés et différences (McKernel, mOS).

Ce que ça vaut pour le HPC¶

Très élevé, et surtout difficile à acquérir ailleurs.

Trois raisons.

1. La pagination et les huge pages sont un levier de performance mesurable et souvent oublié. Sur un code qui balaie de grandes structures, le TLB — le cache des traductions d'adresses — sature. Chaque défaut de TLB coûte une traversée de la table des pages. Passer de pages de 4 Ko à des pages de 2 Mo divise par 512 le nombre d'entrées nécessaires, et fait gagner régulièrement 5 à 20 % sur un code mémoire. C'est un réglage d'une ligne, et presque personne ne le connaît.

2. NUMA est le piège du nœud moderne. Un nœud de calcul actuel a deux à huit sockets ou domaines NUMA, chacun avec sa mémoire locale. Accéder à la mémoire d'un autre domaine coûte deux à trois fois plus cher. La règle de la première touche (first touch) — une page est physiquement allouée dans le domaine du thread qui y écrit en premier — fait que le même code OpenMP va deux fois plus vite ou deux fois moins vite selon l'endroit où l'on initialise les tableaux. ARSE23 traite explicitement « la problématique de l'allocation parallèle en contexte NUMA ». Ce point vaut, à lui seul, l'UE.

3. « Ils sauront modifier un noyau Linux ». Recompiler un noyau, changer un paramètre d'ordonnanceur, mesurer l'effet : c'est le genre de geste qui distingue quelqu'un qui utilise une machine de quelqu'un qui la comprend. Dans une compétition où l'on a la main sur des nœuds, savoir désactiver les atténuations Spectre, activer les huge pages transparentes, fixer la politique de fréquence du processeur ou isoler des cœurs change les résultats.

La partie systèmes allégés (McKernel, mOS) est un luxe : ce sont des noyaux conçus pour les machines de très grande échelle, où l'on veut éliminer le bruit système (OS noise) — ces interruptions qui, sur un million de cœurs synchronisés, coûtent plus que le calcul. C'est un sujet de recherche, et vous serez très peu nombreux à l'avoir vu.

Le bruit système, un phénomène contre-intuitif

Sur un nœud isolé, une interruption de 100 microsecondes toutes les secondes est invisible : 0,01 % de perte. Sur 10 000 nœuds qui se synchronisent par barrière à chaque itération, la probabilité qu'au moins un nœud soit interrompu pendant l'itération devient proche de 1, et tous les autres attendent. La perte passe de 0,01 % à plusieurs dizaines de pour cent. C'est pour cela que les centres de calcul retirent les démons inutiles des nœuds de calcul, et que des noyaux comme McKernel existent.

Référence : les articles de Petrini, Kerbyson, Pakin, « The Case of the Missing Supercomputer Performance » (SC 2003), qui est l'étude fondatrice sur le sujet, et Hoefler, Schneider, Lumsdaine, « Characterizing the Influence of System Noise on Large-Scale Applications by Simulation » (SC 2010).

Arriver prêt¶

⏱ 6 h :

Revoir OSSE11 : processus, fork, appels système, permissions. ARSE23 part de là.
Compiler un noyau Linux une fois, dans une machine virtuelle, avant le cours. Télécharger les sources sur kernel.org, make defconfig, make menuconfig, make -j, démarrer dessus. C'est long la première fois (deux à trois heures), trivial ensuite, et cela démystifie complètement le TP du cours.
Explorer /proc et /sys : lire /proc/meminfo, /proc/self/status, /proc/cpuinfo, /sys/kernel/mm/transparent_hugepage/. Comprendre que le noyau est interrogeable et réglable depuis l'espace utilisateur.

Ressources¶

Priorité 1¶

Michael Kerrisk, The Linux Programming Interface, No Starch Press, 2010. 1 500 pages, la bible des appels système Linux. Ne se lit pas d'un bout à l'autre : c'est une référence, mais la meilleure qui existe. Les chapitres sur la mémoire, les processus et les threads couvrent une bonne part d'ARSE23.
Ulrich Drepper, What Every Programmer Should Know About Memory, 2007, PDF gratuit (publié à l'origine sur LWN.net). Le texte de référence sur les caches, la TLB, la pagination et NUMA du point de vue du programmeur. Techniquement daté sur certains chiffres, conceptuellement inégalé.
Robert Love, Linux Kernel Development, 3ᵉ éd., 2010. L'introduction la plus abordable au noyau : ordonnanceur, gestion mémoire, VFS. Daté mais les structures fondamentales n'ont pas changé.

Priorité 2¶

Daniel Bovet, Marco Cesati, Understanding the Linux Kernel, 3ᵉ éd., O'Reilly, 2005. Plus détaillé que Love, plus daté aussi. Excellent sur la pagination.
Remzi et Andrea Arpaci-Dusseau, Operating Systems: Three Easy Pieces, gratuit sur pages.cs.wisc.edu/~remzi/OSTEP/. Le meilleur manuel de systèmes d'exploitation gratuit, très pédagogique, avec de vrais exercices. À lire en parallèle du cours.
La documentation du noyau elle-même, dans Documentation/ des sources, et sur docs.kernel.org. Les pages sur les huge pages, numa_balancing, les classes d'ordonnancement et cgroups sont directement utiles.
Le wiki d'Arch Linux sur sysctl, cpupower, les gouverneurs de fréquence. Pragmatique et à jour.

Priorité 3 — pour la partie recherche¶

Sur les noyaux allégés : les publications du projet McKernel (RIKEN et Université de Tokyo) et de mOS (Intel). Chercher « lightweight kernel multi-kernel HPC » ; l'article de synthèse « A Survey of Operating Systems for Exascale » et les travaux de Gerofi, Ishikawa et al. sont les points d'entrée.
Sur les allocateurs : les articles de jemalloc (Evans), tcmalloc (Google) et mimalloc (Microsoft Research, Leijen et al., 2019). Le dernier est le plus lisible et explique bien les enjeux de contention.

Outils à maîtriser¶

Outil	Usage
`lstopo` (hwloc)	Cartographier la topologie NUMA et les caches du nœud
`numactl`	Contrôler le placement mémoire : `--cpunodebind`, `--membind`, `--interleave`
`numastat`	Compter les accès mémoire locaux et distants
`perf stat -e dTLB-load-misses,…`	Mesurer les défauts de TLB
`perf c2c`	Détecter le false sharing entre cœurs
`/sys/kernel/mm/transparent_hugepage/enabled`	Activer ou non les THP
`madvise(MADV_HUGEPAGE)`, `mmap(MAP_HUGETLB)`	Demander des huge pages explicitement
`cpupower frequency-set -g performance`	Fixer le gouverneur de fréquence
`debugfs`, `dumpe2fs`	Inspecter les structures d'un système de fichiers ext4
`ftrace`, `trace-cmd`, `bpftrace`	Tracer le noyau
`crash`, `kdump`	Analyse post-mortem d'un plantage noyau

Le réglage en cinq lignes qui fait gagner 10 %

Sur un nœud de calcul dont on a la main, avant une mesure sérieuse :

# Fréquence fixée au maximum, pas de gouverneur dynamique
sudo cpupower frequency-set -g performance
# Huge pages transparentes toujours actives
echo always | sudo tee /sys/kernel/mm/transparent_hugepage/enabled
# Pas de migration NUMA automatique pendant la mesure
echo 0 | sudo tee /proc/sys/kernel/numa_balancing
# Vider les caches pour une mesure d'E/S reproductible
sync && echo 3 | sudo tee /proc/sys/vm/drop_caches
# Placement explicite : un rang par domaine NUMA, mémoire locale
numactl --cpunodebind=0 --membind=0 ./mon_binaire

Mesurez avant et après. Consignez l'écart. C'est ce genre de chiffre qui fait la différence en compétition, et c'est exactement le type de « paramètres du noyau Linux » qu'ARSE23 aborde en partie 7.

Exercices¶

E1 · ★ ⏱ 2 h — Cartographier la machine. Sur la machine la plus grosse à laquelle vous avez accès : produire la sortie de lstopo, numactl --hardware, lscpu, et rédiger une demi-page décrivant la machine — nombre de sockets, cœurs par socket, fils par cœur, tailles de L1/L2/L3, nombre de domaines NUMA, distances NUMA. Cet exercice paraît trivial ; c'est le premier geste de toute campagne de mesure et la moitié des étudiants ne le fait jamais.

E2 · ★★ ⏱ 3 h — Le coût de NUMA. Écrire un programme qui alloue un grand tableau, l'initialise, puis le balaie en lecture. Mesurer la bande passante obtenue dans quatre configurations :

allocation et calcul sur le même domaine NUMA ;
allocation sur le domaine 0, calcul sur le domaine 1 ;
allocation entrelacée (numactl --interleave=all) ;
sans contrainte, en laissant le système décider.

Le rapport entre le meilleur et le pire cas doit être de 1,5 à 3 selon la machine.

E3 · ★★ ⏱ 3 h — La règle de la première touche. Reprendre E2 en version multithread. Initialiser le tableau dans un seul thread, mesurer. Puis l'initialiser dans la même boucle parallèle que celle du calcul, mesurer à nouveau. L'écart illustre la règle de la première touche : c'est l'erreur la plus commune en OpenMP, et vous la retrouverez en ICPA24.

E4 · ★★★ ⏱ 4 h — Huge pages. Mesurer les défauts de TLB avec perf stat -e dTLB-load-misses,dTLB-loads sur un parcours aléatoire d'un tableau de 8 Go, en pages de 4 Ko puis en huge pages de 2 Mo (via madvise(MADV_HUGEPAGE) ou les THP). Rapporter le taux de défauts et le temps. Expliquer le lien quantitatif entre les deux.

E5 · ★★★ ⏱ 6 h — Recompiler et mesurer. Compiler deux noyaux qui ne diffèrent que par une option — par exemple la fréquence du timer (CONFIG_HZ), le modèle de préemption, ou CONFIG_NO_HZ_FULL. Démarrer sur chacun et mesurer le même programme de calcul intensif. Quantifier l'écart, et le bruit système (variance entre répétitions). C'est le TP central de l'UE, autant l'avoir préparé.

E6 · ★★★★ ⏱ 10 h — Un allocateur. Écrire un allocateur mémoire utilisateur minimal : mmap d'une grande zone, listes libres par classe de taille, cache par thread pour éviter la contention. Le tester avec un banc d'essai multithread (par exemple larson ou un banc maison qui alloue et libère en boucle depuis N threads). Comparer à malloc de la glibc et, si vous les installez, à jemalloc et mimalloc. Vous comprendrez pourquoi la contention de l'allocateur est un goulot réel dans les codes multithread.

Projet¶

Projet ARSE23 · Le rapport de caractérisation d'un nœud

⏱ 20 h · ★★★

Sujet. Produire le document que tout ingénieur HPC devrait avoir sur chaque machine qu'il utilise : une caractérisation complète et mesurée d'un nœud de calcul.

Contenu attendu :

Topologie : sortie de lstopo commentée, tableau des caches, matrice des distances NUMA.
Pic de calcul théorique, calculé à partir de la fréquence, du nombre de cœurs, de la largeur des unités vectorielles et du nombre d'opérations par cycle. Comparé au pic mesuré par un micro-noyau de FMA saturant.
Bande passante mémoire mesurée par STREAM, pour 1 thread puis pour tous les cœurs, dans les quatre configurations NUMA de l'exercice E2.
Latences et tailles de cache mesurées, avec la courbe de l'exercice E2 du socle de première année.
Taux de défauts de TLB avec et sans huge pages.
Bruit système : la distribution des temps d'une boucle de calcul fixe répétée mille fois. Tracer l'histogramme, relever la médiane, le 99ᵉ centile et le maximum. Commenter.
L'intensité arithmétique de bascule de la machine, c'est-à-dire le point de coude du modèle roofline. Voir Modèles de performance.

Pourquoi ce projet. Parce qu'en compétition, c'est la première chose à faire quand on reçoit l'accès à une machine, et que les équipes qui ne le font pas optimisent à l'aveugle. Ce document est réutilisable : gardez-le, refaites-le sur chaque machine nouvelle, et vous aurez en trois ans une collection qui vaut de l'or.

Erreurs fréquentes¶

Cinq pièges du réglage système

Mesurer sans fixer la fréquence. Un processeur moderne varie sa fréquence de 1,2 à 4,5 GHz selon la charge, la température et le nombre de cœurs actifs. Une mesure faite sans gouverneur performance n'est pas reproductible. Pire, l'AVX offset fait baisser la fréquence quand on utilise les unités vectorielles larges : une version SIMD peut tourner à une fréquence plus basse que la version scalaire.
Croire que les huge pages sont toujours bonnes. Elles augmentent la fragmentation et peuvent provoquer des pauses de compaction. Sur un code avec beaucoup de petites allocations, les THP en mode always peuvent coûter plus qu'elles ne rapportent. Mesurez.
Confondre transparent huge pages et huge pages explicites. Les premières sont gérées par le noyau et opportunistes ; les secondes sont réservées à l'avance (vm.nr_hugepages) et garanties. Les grands centres utilisent souvent les secondes.
Oublier l'hyper-threading. Deux fils logiques sur un cœur physique partagent les unités de calcul. Sur un code intensif en calcul, activer l'hyper-threading peut ralentir. Sur un code en attente de mémoire, il peut accélérer. Il faut mesurer, et il faut savoir compter les cœurs physiques (lscpu : Core(s) per socket et Thread(s) per core).
Ne pas isoler les cœurs. Le démon du système, le garbage collector de votre éditeur ou votre navigateur consomment des cœurs pendant la mesure. Sur une machine partagée, utilisez taskset ou les cpusets, et acceptez la variance.

Comment l'UE s'articule avec le reste¶

UE ou chapitre	Lien
OSSE11 (S1)	Le prérequis direct : processus, appels système, threads POSIX
ICPA24 (S4)	L'optimisation NUMA d'OpenMP repose entièrement sur ARSE23 ; la bibliothèque de threads utilisateur est le même TD
SYFP24 (S4)	Les systèmes de fichiers locaux d'ARSE23 (VFS, journaux, COW) sont la base des systèmes parallèles
LOCL24 (S4)	Le boot, le paramétrage et le déploiement se retrouvent à l'échelle du cluster
Architecture et mémoire	Le complément côté matériel : caches, pipeline, SIMD

À retenir¶

ARSE23 en trois phrases

C'est le cours de systèmes d'exploitation vu par le HPC : pagination et TLB, huge pages, NUMA, ordonnanceur, et jusqu'aux noyaux allégés de classe exascale. Son apport le plus rentable est la maîtrise de NUMA et des huge pages, deux leviers qui font gagner 10 à 30 % sur des codes mémoire et que presque personne ne connaît. Le geste à acquérir est de caractériser une machine avant de l'optimiser.

Fiche suivante : ASCO23 · Assembleur et compilation.