€¦ · CSC4508–Systèmesd’exploitation Contents Licence vii Présentationdumodule 1 1Présentationdumodule 2 1.1Organisation

CSC4508 – Systèmes d’exploitation

François Trahay & Gaël thomas

2020


Contents

Licence vii

Présentation du module 1

1 Présentation du module 21.1 Organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Séances kernel: XV6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Évaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.4 Évaluation du module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Threads 5

1 Rôles d’un système d’exploitation 61.1 Pile logicielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2 Test du retour des appels système et des fonctions . . . . . . . . . . . . . . . . . . . . . . . 6

2 Utilisation de la pile 92.1 Contenu d’un stack frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Buffer overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.1 Stack overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2.2 Comment prévenir les buffer/stack overflow ? . . . . . . . . . . . . . . . . . . . . . . 13

3 Contexte d’exécution d’un processus 133.1 Fil d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2 Processus multithread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.3 Création d’un Pthread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.4 Autres fonctions Pthread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4 Partage de données 164.1 Thread-safe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164.2 Réentrant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.3 TLS – Thread-Local Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

5 Synchronisation 205.1 Mutex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.2 Opérations atomiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Bibliographie du chapitre 24

Programmation concurrente 25

1 Introduction 26

2 Mécanismes de synchronisation inter processus 262.1 Tubes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.2 Mémoire partagée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.3 Sémaphore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 Mécanismes de synchronisation intra-processus 283.1 Mutex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.2 Moniteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.3 Barrière . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.3.1 Read-Write lock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Télécom SudParis — François Trahay & Gaël thomas — 2020 — i


4 Patterns de synchronisation classiques 314.1 Exclusion mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2 Cohorte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.3 Producteur/Consommateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.3.1 Implémentation d’un Producteur/Consommateur . . . . . . . . . . . . . . . . . . . . 334.4 Lecteur/Rédacteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.4.1 Implémentation d’un Lecteur/Rédacteur . . . . . . . . . . . . . . . . . . . . . . . . . 34

Mécanismes de synchronisation 37

Plan du document 38

1 Introduction 38

2 Opérations atomiques 382.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392.2 Opérations atomiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392.3 Test and set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402.4 À quoi sert volatile ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412.5 Compare And Swap (CAS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432.6 Fetch and Add . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.7 Barrière mémoire / Memory Fence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462.8 Modèle mémoire C11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

2.8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472.8.2 Relaxed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482.8.3 Release Acquire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482.8.4 Release-Consume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492.8.5 Sequentially Consistent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3 Primitives de synchronisation 513.1 Synchronisation par attente active . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513.2 Futex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.3 Construction d’un mutex à l’aide d’un futex . . . . . . . . . . . . . . . . . . . . . . . . . . . 533.4 Construction d’un moniteur à l’aide d’un futex . . . . . . . . . . . . . . . . . . . . . . . . . 54

4 De l’utilisation de la synchronisation 574.1 Interblocage / Deadlock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.2 Granularité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584.3 Scalabilité d’un système parallèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58


Appels système 61

1 Le Système d’exploitation 621.1 Le système d’exploitation (2/2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

2 L’interface user/system 622.1 L’interface user/system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632.2 L’interface user/system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

Interruptions et communication 65

Plan du document 66

Télécom SudParis — François Trahay & Gaël thomas — 2020 — ii


1 Les bus de communication 661.1 Les bus de communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661.2 Le bus mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

1.2.1 DMA: Direct Memory Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671.2.2 MMIO: Memory-Mapped IO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

1.3 Le bus d’entrées/sorties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681.4 Le bus d’interruptions – principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

2 Interruptions 692.1 Réception d’une interruption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702.2 Réception d’une interruption : exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702.3 Réception d’une interruption (suite) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712.4 Interruptions et multicœurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712.5 MSI: Message Signaling Interrupt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 722.6 Communication inter cœur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 722.7 La table IDT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 732.8 Gestion du temps : deux sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

Mémoire virtuelle 75

1 Introduction 76

2 Pagination 762.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772.2 État des pages mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772.3 Adresse logique (ou virtuelle) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 782.4 Table des pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 792.5 Mise en œuvre sur un pentium 64 bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 792.6 Translation Lookaside Buffer (TLB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

3 Le point de vue utilisateur 803.1 Espace mémoire d’un processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803.2 Mapping mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 813.3 Allocation mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 813.4 Le point de vue libc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4 Politiques d’allocation mémoire 834.1 Non-Uniform Memory Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 844.2 Politique d’allocation First touch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 844.3 Politique d’allocation Interleaved . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 854.4 mbind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

Architecture 87

Plan du document 88

1 Introduction 881.1 Loi de Moore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

2 Processeur séquentiel 89

3 Pipeline 893.1 Micro architecture d’un pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903.2 Processeurs superscalaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

3.2.1 Processeurs superscalaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 913.2.2 Dépendance entre instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

3.3 Gestion des branchements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 923.4 Prédiction de branchement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

Télécom SudParis — François Trahay & Gaël thomas — 2020 — iii


3.5 Instructions vectorielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

4 Parallel Processing 944.1 Hyperthreading / SMT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 954.2 Processeurs multi-cœurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 954.3 Architectures SMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 964.4 Architectures NUMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

5 Hiérarchie mémoire 975.1 Enjeux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 975.2 Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 985.3 Memory Management Unit (MMU) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

5.3.1 Fully-associative caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1005.3.2 Direct-mapped caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1005.3.3 Set-associative caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1015.3.4 Cohérence de cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101


Entrées/sorties 103

Plan du document 104

1 IO bufferisée / non bufferisée 105

2 Primitives Unix d’entrée-sortie 1052.1 Ouverture/fermeture de fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1052.2 Lecture sur descripteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1062.3 Écriture sur descripteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1072.4 Duplication de descripteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

3 Entrées-sorties et concurrence 1093.1 Verrouillage de fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1103.2 Manipulation de l’offset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4 Améliorer les performances des entrées-sorties 1124.1 Conseil au noyau pour les lectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1124.2 IO asynchrones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1134.3 mmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

Systèmes de fichier 115

Plan du document 116

1 Périphérique et pilote de périphérique 1161.1 Périphérique et pilote de périphérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1161.2 Les périphériques dans les UNIX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1171.3 2 types de périphériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1171.4 Périphériques de type bloc dans xv6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1181.5 Principe de l’algorithme de iderw . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

2 Le cache d’entrées/sorties 1192.1 Le cache d’entrée/sortie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1192.2 Principe d’un cache d’entrée/sortie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1202.3 Le buffer cache de xv6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1202.4 Fonctionnement du buffer cache (1/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1212.5 Fonctionnement du buffer cache (2/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1212.6 Fonctionnement du buffer cache (3/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

Télécom SudParis — François Trahay & Gaël thomas — 2020 — iv


3 Le journal 1223.1 Opération versus écriture sur disque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1233.2 Problèmes de cohérence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1233.3 Mauvaises solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1243.4 Première idée : les transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1243.5 Deuxième idée : le journal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1253.6 Troisième idée : le journal parallèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1253.7 Structure du journal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1263.8 Principe d’algorithme du journal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1263.9 Utilisation du journal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1273.10 Mise en œuvre dans xv6 (1/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1273.11 Mise en œuvre dans xv6 (2/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1283.12 Mise en œuvre dans xv6 (3/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

4 Partitions et systèmes de fichiers 1294.1 Système de fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1294.2 Principe d’un système de fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1304.3 Les partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1304.4 L’image disque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

5 Le système de fichiers UFS/xv6 1315.1 Structure globale du système de fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1325.2 Le dinode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1325.3 Les blocs de données d’un fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1335.4 Ajout d’un bloc à un fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1335.5 Les répertoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1345.6 Du chemin à l’inode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1345.7 Création et suppression de fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

6 La pile d’entrée/sortie de xv6 1356.1 L’inode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1366.2 Principales fonctions des inodes (1/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1366.3 Principales fonctions des inodes (2/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1376.4 Principales fonctions des inodes (3/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1376.5 Le fichier ouvert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1386.6 Le descripteur de fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

7 Ce qu’il faut retenir 139

Références 141

Index 143

Télécom SudParis — François Trahay & Gaël thomas — 2020 — v


Télécom SudParis — François Trahay & Gaël thomas — 2020 — vi


# 1

'

&

$

%

Licence

Ce document est une documentation libre, placée sous la Licence de Documentation Libre GNU (GNUFree Documentation License).

Copyright (c) 2020 François Trahay & Gaël ThomasPermission est accordée de copier, distribuer et/ou modifier ce document selon lestermes de la Licence de Documentation Libre GNU (GNU Free Documentation License),version 1.2 ou toute version ultérieure publiée par la Free Software Foundation; avecles Sections Invariables qui sont ‘Licence’ ; avec les Textes de Première de Couverturequi sont ‘CSC4508 – Systèmes d’exploitation’et avec les Textes de Quatrième de Couverture qui sont ‘Help’.Une copie de la présente Licence peut être trouvée à l’adresse suivante :http://www.gnu.org/copyleft/fdl.html.

Remarque : La licence comporte notamment les sections suivantes : 2. COPIES VERBATIM, 3.

COPIES EN QUANTITÉ, 4. MODIFICATIONS, 5. MÉLANGE DE DOCUMENTS, 6. RECUEILS DE

DOCUMENTS, 7. AGRÉGATION AVEC DES TRAVAUX INDÉPENDANTS et 8. TRADUCTION.

Ce document est préparé avec des logiciels libres :

• LATEX : les textes sources sont écrits en LATEX (http://www.latex-project.org/, le sitedu Groupe francophone des Utilisateurs de TEX/LATEX est http://www.gutenberg.eu.org).Une nouvelle classe et une nouvelle feuille de style basées sur la classe seminar ontété tout spécialement dévéloppées: newslide et slideint (projet fusionforge slideint,https://fusionforge.int-evry.fr/www/slideint/);

• emacs: tous les textes sont édités avec l’éditeur GNU emacs (http://www.gnu.org/software/emacs);

• dvips: les versions PostScript (PostScript est une marque déposée de la société Adobe Systems In-corporated) des transparents et des polycopiés à destination des étudiants ou des enseignants sontobtenues à partir des fichiers DVI (« DeVice Independent ») générés à partir de LaTeX par l’utilitairedvips (http://www.ctan.org/tex-archive/dviware/dvips);

• ps2pdf et dvipdfmx: les versions PDF (PDF est une marque déposée de la société Adobe Sys-tems Incorporated) sont obtenues à partir des fichiers Postscript par l’utilitaire ps2pdf (ps2pdfétant un shell-script lançant Ghostscript, voyez le site de GNU Ghostscript http://www.gnu.org/-software/ghostscript/) ou à partir des fichiers DVI par l’utilitaire dvipfmx;

• makeindex: les index et glossaire sont générés à l’aide de l’utilitaire Unix makeindex(http://www.ctan.org/tex-archive/indexing/makeindex);

• TeX4ht: les pages HTML sont générées à partir de LaTeX par TeX4ht (http://www.cis.ohio--state.edu/~gurari/TeX4ht/mn.html);

• Xfig: les figures sont dessinées dans l’utilitaire X11 de Fig xfig (http://www.xfig.org);

• fig2dev: les figures sont exportées dans les formats EPS (« Encapsulated PostScript ») et PNG(« Portable Network Graphics ») grâce à l’utilitaire fig2dev (http://www.xfig.org/userman/-installation.html);

• convert: certaines figures sont converties d’un format vers un autre par l’utilitaire convert(http://www.imagemagick.org/www/utilities.html) de ImageMagick Studio;

• HTML TIDY: les sources HTML générés par TeX4ht sont « beautifiés » à l’aide de HTML TIDY(http://tidy.sourceforge.net) ; vous pouvez donc les lire dans le source.

Nous espérons que vous regardez cette page avec un navigateur libre: Firefox par exemple. Comme l’indiquele choix de la licence GNU/FDL, tous les éléments permettant d’obtenir ces supports sont libres.

Télécom SudParis — François Trahay & Gaël thomas — 2020 — vii


Télécom SudParis — François Trahay & Gaël thomas — 2020 — viii

Présentation du module

François Trahay


2019–2020

1

Présentation du module 1 Présentation du module

# 2

'

&

$

%

1 Présentation du module

Objectifs du module :

� Comprendre le fonctionnement interne d’un système d’exploitation

� Savoir interagir avec l’OS depuis un programme

Structure du module :

[U] des séances orientées “userland”

[K] des séances orientées “kernel”

[G] des séances “plus générales”

# 3

'

&

$

%

1.1 Organisation

1. ProcessusCI1 [U] ThreadsCI2 [U] Programmation concurrenteCI3 [G] Mécanismes de synchronisationCI4 [K] Appels systèmesCI5 [K] Interruption et ordonnancementCI6 [K] Sprint : finalisation de l’ordonnanceur

2. MémoireCI7 [U] Mémoire virtuelleCI8 [K] Memory Management UnitCI9 [G] ArchitectureCI10 [K] Sprint

3. Entrées/SortiesCI11 [U] Entrées/sortiesCI12 [U] Synthèse : mini-projetCI13 [K] Systèmes de fichierCI14 [K] Sprint

CI15 TP noté

Télécom SudParis — François Trahay — 2019–2020 — CSC4508 – Systèmes d’exploitation 2


# 4

'

&

$

%

1.2 Séances kernel : XV6

Lors des séances [K], vous allez développer un OS

� basé sur l’OS xv6

� développement de certains mécanismes de l’OS

� séances sprint :� finalisation du développement� évaluation par les enseignants

# 5

'

&

$

%

1.3 Évaluation

Évaluation :

� 20% - Contrôle continu lors des sprints :� “comment vous avez implémenté ce mécanisme de l’OS ?”� “que se passe-t-il si X ?”

� 80% - TP noté avec plusieurs parties :� question(s) de cours� expliquer comment vous avez implémenté un mécanisme de l’OS� développer une application



# 6

'

&

$

%

1.4 Évaluation du module

� À la fin du module, les étudiants évaluent le module.

� Objectif : améliorer le module


Threads

François Trahay


2019–2020

5

Threads 1 Rôles d’un système d’exploitation

# 2

'

&

$

%

1 Rôles d’un système d’exploitation

� Abstraction : fournir une interface unique pour des matériels divers� exemple : accès à un disque dur, disque SSD, disque NVMe, etc.

� Gestion des ressources : assurer l’utilisation efficiente des ressources� ordonnancement des processus sur les CPUs, allocation mémoire, etc.

� Protection : contrôler l’utilisation des ressources et gérer les erreurs� séparation de l’espace mémoire des processus, droits d’accès aux ressources, etc.

# 3

'

&

$

%

1.1 Pile logicielle

hardware

operating system

libraries

application

CPU Mem Disk ...

filesystem

device driverblock char netw

buffer cache

networkipc scheduler

memorymanagement

libc

fprintf

write syscall wrappers

high level API

write

sd_setup_read_write_cmnd

main

store_result

kern

el sp

ace

use

r s

pace

Le système d’exploitation est chargé d’exploiter des matériels divers. Il intègre donc des pilotes (drivers)capables de dialoguer avec un matériel particulier. Les différents pilotes pour un même type de périphériqueoffrent une même interface, ce qui permet aux couches supérieures de l’OS d’utiliser indifféremment lematériel.

Le passage de l’espace utilisateur à l’espace noyau se fait via un appel système (syscall). Le noyau traitela demande de l’application et retourne un entier positif ou nul en cas de succès, et -1 en cas d’échec.

Du point de vue d’une application, les appels système sont exposés sous la forme de fonctions (définiesdans la libc) chargées d’exécuter l’appel système.



# 4

'

&

$

%

1.2 Test du retour des appels système et des fonctions

� Il faut toujours tester la valeur de retour d’un appel système et traiter les erreurs� Évite la propagation d’erreurs (la découverte de l’erreur peut avoir lieux

beaucoup plus tard)I voir l’approche fail-fast présentée en CSC4102

� errno : variable externe indiquant la cause de la dernière erreur� La section ERRORS du manuel d’une fonction décrit les causes d’erreur possibles

Témoignage d’un ancien ASR : « Sans insistance de [l’équipe pédagogique de CSC4508], cela ne nousaurait pas sauté si vite aux yeaux que les problèmes (en début de la coupe de robotique) venait d’un manquede gestion des erreurs sur un code qui n’avait pas été relu par suffisamment de monde ».

Comment vérifier le code de retour d’une fonction et traiter les problèmes ? La macrovoid assert(scalar expression) teste l’expression passée en paramètre et, si celle-ci est fausse, afficheun message d’erreur et termine le programme (avec la fonction abort()) :

struct stat buf;int rc = stat(file, &buf);assert(rc>=0);// -> en cas d’erreur, affiche:// appli: appli.c:12: main: Assertion ‘rc>=0’ failed.// Abandon

Toutefois, la macro est à utiliser avec précaution car elle est désactivée lorsque le programme est compiléen mode optimisé (avec gcc -O3 par exemple).

Il est donc préférable de tester le code de retour, afficher un message décrivant l’erreur, et éventuellementterminer le processus.

struct stat buf;int rc = stat(file, &buf);if(rc < 0) {fprintf(stderr, "Error\n");exit(EXIT_FAILURE); // ou abort();

}

Afficher la cause d’une erreur. Le fichier errno.h listes les erreurs standard. Le manuel de chaqueappel système (voir man 2 fonction, ou man 3 fonction) et de chaque fonction indique, dans la sectionERRORS, les différents codes d’erreurs qui peuvent être renvoyés.

Le message d’erreur associé à une valeur de errno peut être obtenu avec strerror() ou perror() :

struct stat buf;int rc = stat(file, &buf);if(rc < 0) {



fprintf(stderr, "Error while accessing file ’%s’: %s\n", file, strerror());// -> message "Error while accessing file ’plop’: No such file or directory"exit(EXIT_FAILURE);

}

ou

struct stat buf;int rc = stat(file, &buf);if(rc < 0) {perror("Error while accessing file");// -> message affiché: "Error while accessing file: No such file or directory"exit(EXIT_FAILURE);

}

Traitement d’erreur générique. Il est possible de définir une macro affichant un message d’erreur etindiquant où a eu lieu l’erreur. Par exemple :

#define FATAL(errnum, ...) do { \fprintf(stderr, "Error in %s:%d:\n", __FILE__, __LINE__); \fprintf(stderr, __VA_ARGS__); \fprintf(stderr, ": %s\n", strerror(errnum)); \abort(); \

} while(0)

int main(int argc, char**argv) {char *file = argv[1];struct stat buf;int rc = stat(file, &buf);if(rc < 0) {FATAL(errno, "Cannot access file ’%s’", file);

}return EXIT_SUCCESS;

}// affiche:// Error in fatal.c:21:// Cannot access file ’plop’: No such file or directory// Abandon

Debugger. Lorsqu’un programme appelle la fonction abort() afin de terminer le processus. Un fichiercore dump décrivant le processus lors de l’erreur peut alors être généré afin de débugger le programme avecgdb.

Pour activer la génération d’un core dump, lancer la commande ulimit -c unlimited. Dès lors, lafonction abort() génère un core dump qui peut être fourni à gdb :

$ ./fatal plopError in fatal.c:21:Cannot access file ’plop’: No such file or directoryAbandon (core dumped)

$ gdb ./fatal coreGNU gdb (Debian 8.1-4+b1) 8.1[...]Reading symbols from ./fatal...(no debugging symbols found)...done.[New LWP 11589]Core was generated by ‘./fatal plop’.


Threads 2 Utilisation de la pile

Program terminated with signal SIGABRT, Aborted.#0 __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:5050 ../sysdeps/unix/sysv/linux/raise.c: Aucun fichier ou dossier de ce type.(gdb) bt#0 __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50#1 0x00007ffff7dfb535 in __GI_abort () at abort.c:79#2 0x0000555555555232 in main (argc=2, argv=0x7fffffffdcd8) at fatal.c:21

# 5

'

&

$

%

2 Utilisation de la pile

� Chaque appel de fonction crée un stack frame sur la pile

� Un stack frame contient� les variables locales� une sauvegarde des registres modifiés� les arguments de la fonction (spécifique aux architectures x86 32 bits)� l’adresse de retour de la fonction (spécifique aux architectures x86)

# 6

'

&

$

%

2.1 Contenu d’un stack frame

� Un stack frame est défini par� une adresse de base qui indique où le frame commence (le registre rbp sur x86)� l’adresse du sommet de la pile (le registre rsp sur x86)

� Entrée de fonction :� sauvegarder rbp (avec push rbp)� réinitialiser rbp (avec mov rbp, rsp)

� Sortie de fonction :� restoration de l’ancien rbp (pop rbp)� saut à l’adresse de retour (ret)

Convention d’appel de fonction. En fonction de l’architecture CPU (et parfois du compilateur), lafaçon de faire un appel de fonction peut varier.



x86 32 bits. Sur les architectures x86 32 bits, les arguments sont placés sur la pile de façon à ce que lepremier argument soit à l’adresse ebp+8, le deuxième à l’adresse ebp+12 (si le premier argument est stockésur 4 octets), etc.

L’adresse de retour (c’est-à-dire l’adresse de l’instruction à exécuter après la fonction) est stockée sur lapile à l’adresse ebp+4.

ebpfoo

ebp - 4 first local variable

second local variableebp - 8

ebp (base pointer)

esp (stack pointer)

old ebp value

return adress

1st argument

foo+17

2nd argument

3rd argument

ebp + 4

ebp + 8

ebp + 12

ebp + 16

arg1

arg2

arg3

var1

var2

Figure 1 : Stack frame sur architecture x86 32 bits

x86 64 bits. Sur les architectures x86 64 bits, les arguments sont passés via les registres rdi, rsi, rdx,rcx, r8 et r9. S’il y a plus de 6 arguments, les arguments suivants sont placés sur la pile.

rbpfoo

rbp - 4 first local variable

second local variablerbp - 8

rbp

rsp

old rbp value

return adressfoo+17rbp + 8rsi

rdi

rdx

var1

var2

r8

r9

arg1

arg2

arg3

arg4

arg5

Figure 2 : Stack frame sur architecture x86 64 bits

Arm. Sur les architectures Arm, les arguments sont passés via les registres (x0 à x7 sur Arm 64 bits).L’adresse de retour est également stockée dans un registre.



rbpfoo

rbp - 4 first local variable

second local variablerbp - 8

x29

sp

old rbp value

return adress

x1

x0

x2

var1

var2

x3

x4

arg1

arg2

arg3

arg4

arg5

x30 foo+17

Figure 3 : Stack frame sur architecture Arm 64 bits

# 7

'

&

$

%

2.2 Buffer overflow

� Buffer overflow / dépassement de tampon

� Écriture en dehors de l’espace alloué pour un buffer

� Risque d’écraser d’autres données

� Faille de sécurité : l’écrasement de données risque de changer le comportement del’application

Voici un exemple de buffer overflow :

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

int main(int argc , char **argv) {

int N = 4;char tab[N];int a = 17;

for(int i=0; i<=N ; i++) {tab[i] = ’a’+i;

}

printf("tab = {%c, %c, %c, %c}\n", tab[0], tab[1], tab[2], tab [3]);printf("a = %d\n", a);return 0;

}


2 Utilisation de la pile 2.2 Buffer overflow

Exemple. Ici, le bug vient de la boucle sensée remplir le tableau qui effectue une itération de trop (àcause du “<=”. Après les 4 premières itérations, voici l’état de la mémoire :

0x1000Adresse

valeur 0x410x1001

0x420x1002

0x430x1003

0x440x1004

0x110x1005

0x000x1006

0x000x1007

0x000x1008

0x000x1009

0x500x100A

0x21

tab[0]variable a

tab[1] tab[2] tab[3]

Lors de la cinquième itération, la modification de tab[4] modifie un octet de la variable a :

0x1000Adresse

valeur 0x410x1001

0x420x1002

0x430x1003

0x440x1004

0x450x1005

0x000x1006

0x000x1007

0x000x1008

0x000x1009

0x500x100A

0x21

tab[0]variable a

tab[1] tab[2] tab[3]

La variable a ne vaut donc plus 17, mais 69 (ou 0x45).

Faille de sécurité. Les bugs de type buffer overflow sont potentiellement graves pour la sécurité d’unsystème, car en fonction d’une entrée (par exemple, une chaîne de caractères saisie par l’utilisateur), le bugpeut modifier le comportement de l’application (sans nécessairement crasher). Dans notre exemple, si lavariable a correspondait à l’identifiant de l’utilisateur, le bug permettrait de se faire passer pour quelqu’und’autre (par exemple, un administrateur) !

Les buffer overflows sont parmi les failles de sécurité les plus répandues. Pour s’en convaincre, il suf-fit de rechercher les annonces de vulnérabilités mentionnant « buffer overflow »(https://cve.mitre.org/cgi-bin/cvekey.cgi?keyword=buffer%20overflow) (environ 780 failles en 2017)

# 8

'

&

$

%

2.2.1 Stack overflow

� Utilisation d’un buffer overflow pour changer le flot d’exécution du programme

� L’adresse de retour d’une fonction se situe sur la pile

=⇒ possibilité de choisir le code à exécuter par la suite

Exemple. Voici un exemple de stack overflow :

stack_overflow.c# include <stdio.h># include <stdlib.h># include <string.h>

void foo(char* str) {char new_str [16];strcpy(new_str , str);printf("new_str = %s\n", new_str );

}

int main(int argc , char **argv) {

foo(argv [1]);printf("De retour dans main\n");


Threads

return 0;}

Ici, la fonction foo ne vérifie pas que new_str est suffisament grand pour contenir str. Donc, si str esttrop long, strcpy déborde et peut écraser l’adresse de retour de foo.

Voici un exemple d’exécution menant à un stack overflow :

$ gdb ./stack_overflow(gdb) r coucouAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

The program being debugged has been started already.Start it from the beginning? (y or n) yStarting program: stack_overflow coucouAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAnew_str = coucouAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

Program received signal SIGSEGV, Segmentation fault.0x000055555555518e in foo (str=0x7fffffffe03e "coucou", ’A’ <repeats 83 times>) at stack_overflow.c:99 }(gdb) bt#0 0x000055555555518e in foo (str=0x7fffffffe03e "coucou", ’A’ <repeats 83 times>) at stack_overflow.c:9#1 0x4141414141414141 in ?? ()#2 0x4141414141414141 in ?? ()#3 0x4141414141414141 in ?? ()#4 0x4141414141414141 in ?? ()#5 0x4141414141414141 in ?? ()#6 0x4141414141414141 in ?? ()#7 0x4141414141414141 in ?? ()#8 0x4141414141414141 in ?? ()#9 0x0000555555550041 in ?? ()#10 0x0000000000000000 in ?? ()(gdb)

Ici, on observe qu’en sortant de la fonction foo, le programme tente d’exécuter l’instruction située àl’adresse 0x4141414141414141 (0x41 est la valeur hexadécimale de ’A’), ce qui génère une erreur.

On pourrait exploiter le bug en insérant dans argv[1] l’adresse de la fonction void bar(int a, int b)ainsi que ses paramètres [?].

# 9

'

&

$

%

2.2.2 Comment prévenir les buffer/stack overflow ?� Vérifier les bornes lors de l’accès à un tableau� fait de manière automatique en Java� n’est pas fait en C/C++ car trop coûteux

� Ne pas utiliser les fonctions “dangereuses” (strcpy, gets ...)� Utiliser à la place les fonctions sûres (strncpy, fgets ...)

� Pile non-exécutable (activé par défaut par Linux)� évite l’exécution de code arbitraire

� Stack canaries� Un canari (une valeur spécifique) est positionné sur la pile à l’entrée de la

fonction� Si en sortant de la fonction, le canari a été modifié, il y a eu stack overflow� option -fstack-protector-all de gcc

� Address space layout randomization (ASLR) (activé par défaut par Linux)� charge le code de l’application à une adresse aléatoire


Threads 3 Contexte d’exécution d’un processus

# 10

'

&

$

%

3 Contexte d’exécution d’un processus

� Contexte : contexte d’exécution + contexte du noyau

� Espace d’adressage : code, données et pile

Execution contextData registersStatus registerStack pointer SP)Program counter (PC)

Kernel context

Virt. Mem. structuresDescriptor table

brk pointer

Process context

0x0000008000000000

0x0000000000000000.text

.data

.bss

Heap

Stack

Libs

Functions context

Shared libraries

Dynamic allocation(malloc, ...)

Unitialized variables

Initialized variables

Instructionsusers

pace

PC (program counter)

brk

SP (stack pointer)

# 11

'

&

$

%

3.1 Fil d’exécution

� Fil d’exécution != Ressources� Fil d’exécution (ou thread) : contexte d’exécution + pile� Ressources : code, données, contexte du noyau

Execution contextData registersStatus registerStack pointer SP)Program counter (PC)

Kernel context


brk pointer

Thread

0x0000008000000000

0x0000000000000000.text

.data

.bss

Heap

LibsShared libraries




Instructions

users

pace


brk

StackFunctions context

SP (stack pointer)


Threads 3 Contexte d’exécution d’un processus

# 12

'

&

$

%

3.2 Processus multithread

� Plusieurs fils d’exécution

� Ressources partagées

Execution context 1Data registersStatus registerStack pointer SP)Program counter (PC)

Kernel context


brk pointer

Thread 1

0x0000000000000000.text

.data

.bss

Heap





Instructions

users

pace


brk

Stack 1Functions context

SP (stack pointer)

Execution context 2Data registersStatus registerStack pointer SP)Program counter (PC)

Thread 2

Stack 2Functions context

SP (stack pointer)

Stack 1

Stack 2

Dans un processus multi-thread, chaque thread possède un contexte (registres + pile). Le reste de lamémoire (code, données, etc.) et les ressources (fichiers ouverts, etc.) sont partagés entre les threads.

Les piles des différents threads sont espacées en mémoire de manière à ce qu’elles puissent grossir. Tou-tefois, si la pile d’un thread grossit trop, elle risque de déborder sur la pile d’un autre thread. Pour éviter ceproblème, la taille des piles est limitée (la commande ulimit -s donne la taille de pile maximum). Cette taillelimite peut être modifiée en ligne de commande (par exemple ulimit -s 32768), ou depuis un programme(en utilisant la fonction setrlimit).

# 13

'

&

$

%

3.3 Création d’un Pthread

Création d’un pthread

� int pthread_create(pthread_t *thread, const pthread_attr_t *attr,void *(*start_routine) (void *), void *arg);

� attr (in) : attributs du thread à créer� start_routine (in) : fonction à exécuter une fois le thread créé� arg (in) : paramètre à passer à la fonction� thread (out) : identifiant du thread créé

Nous présentons ici l’API Pthread (POSIX thread) qui est la plus utilisée en C. La norme C11 définit uneautre interface pour la manipulation de threads. Toutefois, rares sont les implémentations de cette interface.Le standard de facto reste donc Pthread.

Contrairement à la création de processus qui génère une hiérarchie (ie. un processus parent d’un autre


Threads 4 Partage de données

processus), il n’y a pas de hiérarchie entre les threads.

# 14

'

&

$

%

3.4 Autres fonctions Pthread

� int pthread_exit(void* retval);

� Termine le thread courant avec la valeur de retour retval

� int pthread_join(pthread_t tid, void **retval);

� Attend la terminaison du thread tid et récupère sa valeur de retour

# 15

'

&

$

%

4 Partage de données

L’espace mémoire est partagé entre les threads, notamment

� les variables globales

� les variables locales statiques

� le contexte du noyau (flux, signaux, etc.)

Ne sont pas partagées :

� les variables locales

Techniquement, tout l’espace mémoire est partagé entre les threads. Il est donc possible de partagertoutes les variables, y compris les variables locales.



# 16

'

&

$

%

4.1 Thread-safe

Code thread-safe : donne un résultat correct lorsqu’exécuté simultanément par plusieursthreads :

� Pas d’appel à du code non thread-safe

� Protéger l’accès aux données partagées

# 17

'

&

$

%

4.2 Réentrant

Code réentrant : code dont le résultat ne dépend pas d’un état précédent

� Ne pas maintenir d’état persistant entre les appels

� exemple de fonction non réentrante : fread dépend de la position du curseur du flux

Exemple : strtok. Un autre exemple de fonction non-réentrante est la fonction char* strtok(char*str, char *delim). Cette fonction extrait des sous-chaînes d’une chaîne.

Par exemple, le code suivant affiche les différents répertoires de la variable PATH :

strtok_example.c# include <stdlib.h># include <stdio.h># include <string.h>

void extract_path () {char* string = getenv("PATH");printf("Parsing ’%s’\n", string );



for(char* token = strtok(string , ":") ;token ;token = strtok(NULL , ":") ){

printf("\t %s\n", token);}

}

int main(int argc , char **argv) {extract_path ();return 0;

}

Voici un exemple de résultat obtenu :

Parsing ’/usr/local/bin:/usr/bin:/bin:/usr/local/games:/usr/games’/usr/local/bin/usr/bin/bin/usr/local/games/usr/games

La fonction strtok n’est pas réentrante car elle se base sur un état précédent (un pointeur sur le derniercaractère testé dans la chaîne). Ainsi, dans cet exemple, le traitement appliqué à chaque token ne peut pasutiliser strtok. Par exemple :

strtok_example_bug.c# include <stdlib.h># include <stdio.h># include <string.h>

void extract_path () {char* string = getenv("PATH");printf("Parsing ’%s’\n", string );// string should contain a list of directories separated with :// eg. /usr / local / bin :/ usr/ bin :/ bin :/ usr / local / games :/ usr/ games

// Extract the directories// eg. /usr / local /bin , / usr /bin , /bin , / usr / local /games , / usr/ gamesfor(char* token = strtok(string , ":") ;

token ;token = strtok(NULL , ":") ){

// token contains a directory (eg. / usr / local / bin )printf("\t %s contains: ", token );

// Extract the subdirectories// eg. usr , local , binfor(char* word = strtok(token , "/ ") ;

word ;word = strtok(NULL , "/") ){

printf("%s ", word);}printf("\n");

}}


}

Aura pour résultat :

Parsing ’/usr/local/bin:/usr/bin:/bin:/usr/local/games:/usr/games’/usr/local/bin contains: usr local bin

Ici, le premier token (/usr/local/bin) est découpé en mots (usr, local, bin) par des appels suc-cessif à strtok qui modifient l’état précédent de strtok, ce qui empêche les appels suivants à token =strtok(NULL, ":") de parcourir la chaîne string.

Rendre une fonction réentrante. Il est possible de rendre réentrante une fonction non-réentrante enajoutant un paramètre correspondant à l’état de la fonction. Par exemple, la version réentrante de char*strtok(char *str, const char *delim); est char* strtok_r(char *str, const char *delim, char**saveptr );

Ainsi, le programme précédent peut être corrigé en :



strtok_example_fixed.c# include <stdlib.h># include <stdio.h># include <string.h>

void extract_path () {char* string = getenv("PATH");char* saveptr = NULL;printf("Parsing ’%s’\n", string );

for(char* token = strtok_r(string , ":", &saveptr) ;token ;token = strtok_r(NULL , ":", &saveptr) ){

printf("\t %s contains: ", token );

char* saveptr_word = NULL;for(char* word = strtok_r(token , "/ ", &saveptr_word) ;

word ;word = strtok_r(NULL , "/", &saveptr_word) ){

printf("%s ", word);}printf("\n");

}}


}

Qui aura pour résultat :Parsing ’/usr/local/bin:/usr/bin:/bin:/usr/local/games:/usr/games’

/usr/local/bin contains: usr local bin/usr/bin contains: usr bin/bin contains: bin/usr/local/games contains: usr local games/usr/games contains: usr games

# 18

'

&

$

%

4.3 TLS – Thread-Local Storage

� Variable globale (ou locale statique) propre à chaque thread

� Exemple : errno

� Déclaration :� en C11 : _Thread_local int variable = 0;

� en C99 avec gcc : __thread int variable = 0;

� en C99 avec Visual studio : __declspec(thread) int variable = 0;

pthread_key. Une autre manière (plus portable, mais beaucoup plus pénible à écrire) de déclarer unevariable TLS est d’utiliser un pthread_key :

• création :

– int pthread_key_create(pthread_key_t *key, void (*destructor)(void*));


Threads

• destruction :

– int pthread_key_delete(pthread_key_t *key););

• utilisation :

– void *pthread_getspecific(pthread_key_t key);

– int pthread_setspecific(pthread_key_t key, const void *value);

• initialisation :

– int pthread_once(pthread_once_t *once_control, void (*init_routine) (void));

# 19

'

&

$

%

5 Synchronisation

� Garantir la cohérence des données� Accès simultanés à une variable partagée en lecture/écritureI x++ n’est pas atomique (constitué de load, update, store)� Accès simultanés à un ensemble de variables partagéesI exemple : une fonction swap(a, b){ tmp=a; a=b; b=tmp; }

� Plusieurs mécanismes de synchronisation� Mutex� Instructions atomiques� Conditions, sémaphores, etc. (cf CI3)

Le programme suivant illustre le problème des accès simultanés à des variables partagées. Ici, deux threadsincrémentent chacun 1 000 000 000 fois la même variable :


Threads 5 Synchronisation

compteurBOOM.c/*

* compteurBOOM .c** Probleme de synchronisation***/

# include <error.h># include <unistd.h># include <stdlib.h># include <stdio.h># include <pthread.h>

/* INT_MAX / 2 */# define NBITER 1000000000

int compteur = 0;

void *start_routine(void *arg) {int i;

for (i = 0; i < NBITER; i++) {/* OOPS : FAUX acces a variable partagee non protegee */compteur ++;

}pthread_exit(NULL);

}

int main (int argc , char *argv []) {int rc;pthread_t thread1 , thread2;

rc = pthread_create (&thread1 , NULL , start_routine , NULL);if (rc)

error(EXIT_FAILURE , rc , "pthread_create");



rc = pthread_join(thread1 , NULL);if (rc)

error(EXIT_FAILURE , rc , "pthread_join");rc = pthread_join(thread2 , NULL);if (rc)

error(EXIT_FAILURE , rc , "pthread_join");

if (compteur != 2 * NBITER)printf("BOOM! compteur = %d\n", compteur );

elseprintf("OK compteur = %d\n", compteur );

exit(EXIT_SUCCESS );}

Alors que le compteur devrait valoir 2*1 000 000 000 = 2 000 000 000, l’exécution de ce programme donneun autre résultat, par exemple :$ ./compteurBOOMBOOM! compteur = 1076588402



# 20

'

&

$

%

5.1 Mutex

� Type : pthread_mutex_t

� Initialisation :� pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

� int pthread_mutex_init(ptread_mutex_t *m, constpthread_mutexattr_t *attr);

� Utilisation :� int pthread_mutex_lock(pthread_mutex_t *mutex));

� int pthread_mutex_trylock(pthread_mutex_t *mutex);

� int pthread_mutex_unlock(pthread_mutex_t *mutex);

� Destruction :� int pthread_mutex_destroy(pthread_mutex_t *mutex);

En utilisant un mutex, on peut corriger le programme compteurBOOM en assurant que les incrémenta-tions du compteur se font en exclusion mutuelle :

compteur_mutex.c/*




int compteur = 0;pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;


for (i = 0; i < NBITER; i++) {pthread_mutex_lock (&mutex );compteur ++;pthread_mutex_unlock (&mutex);


}















Si le résultat obtenu est correct, l’utilisation d’un mutex ralentit considérablement le programme (144savec mutex, contre 4.1s sans mutex)

# 21

'

&

$

%

5.2 Opérations atomiques

� Opération s’exécutant de manière atomique

� C11 définit un ensemble de fonctions effectuant des opérations atomiques� C atomic_fetch_add(volatile A *object, M operand);

� _Bool atomic_flag_test_and_set(volatile atomic_flag *object);

� C11 définit des types atomiques� les opérations sur ces types sont atomiques� déclaration : _Atomic int var; ou _Atomic(int) var;

On peut corriger le programme compteurBOOM en utilisant des opérations atomiques. Pour cela, il suffit dedéclarer le compteur comme _Atomic int. L’incrémentation du compteur utilise alors l’opération atomiqueatomic_fetch_add.


Threads

compteur_atomic.c/*




_Atomic int compteur = 0;


for (i = 0; i < NBITER; i++) {compteur ++;


}







error(EXIT_FAILURE , rc , "pthread_join");rc = pthread_join(thread2 , NULL);if (rc)





Ici, le résultat est correct et le programme nettement plus rapide qu’en utilisant un mutex :

• sans synchronisation : 4.1s

• avec mutex : 144s

• avec opération atomique : 35s

Bibliographie du chapitre


Programmation concurrente

François Trahay


2019–2020

25

Programmation concurrente 2 Mécanismes de synchronisation inter processus

# 2

'

&

$

%

1 Introduction

Contenu de cette séance :

� découverte des mécanismes de synchronisation existants� mécanismes inter processus� mécanismes intra processus

� étude des patterns de synchronisation les plus classiques

# 3

'

&

$

%

2 Mécanismes de synchronisation inter processus

� IPC : Inter Process Communication� basés sur des objets IPC dans l’OS� utilisation : souvent via une entrée dans le système de fichierI fournit une persistance des données


Programmation concurrente 2 Mécanismes de synchronisation inter processus

# 4

'

&

$

%

2.1 Tubes

� Fichiers spéciaux gérés en FIFO

� Tubes anonymes� int pipe(int pipefd[2]);

I crée un tube accessible par le processus courantI accessible également aux futurs processus enfantsI pipefd[0] pour lecture, pipefd[1] pour écriture

� Tubes nommés� int mkfifo(const char *pathname, mode_t mode);

� crée une entrée dans le système de fichier accessible par n’importe quel processus

� Utilisation (presque) comme un fichier “normal”� lecture bloquante� pas de lseek

Vous avez déja manipulé des tubes sans forcément vous en apercevoir : en bash, l’enchaînement decommandes reliées par des pipes se fait via des tubes anonymes créés par le processus bash.

Ainsi, lorsqu’on exécute cmd1 | cmd2 | cmd3, bash crée 2 tubes anonymes et 3 processus, puis redirige(grâce à l’appel système dup2, cf le Cours Intégré 11) les entrées et sorties standards des processus vers lesdifférents tubes.

# 5

'

&

$

%

2.2 Mémoire partagée

� Permet de partager certaines pages mémoire entre plusieurs processus

� Création d’un segment de mémoire partagée de taille nulle :� int shm_open(const char *name, int oflag, mode_t mode);

I name est une clé de la forme “/cle”

� Changement de la taille du segment :� int ftruncate(int fd, off_t length);

� Projeter en mémoire le segment :� void *mmap(void *addr, size_t length, int prot, int flags, int

fd, off_t offset);

� flags doit contenir MAP_SHARED

Nous reverrons plus tard (lors du CI 11 sur les entrées/sorties) une autre utilisation de mmap.


Programmation concurrente 3 Mécanismes de synchronisation intra-processus

# 6

'

&

$

%

2.3 Sémaphore� Objet constitué d’une valeur et d’une file d’attente� Création :� sémaphore nommé : sem_t *sem_open(const char *name, int oflag,

mode_t mode, unsigned int value);I name est une clé de la forme “/cle”� sémaphore anonyme : int sem_init(sem_t *sem, int pshared, unsigned

int value);I si pshared != 0, utilisable depuis plusieurs processus (via une mémoire

partagée)� Utilisation :� int sem_wait(sem_t *sem);

� int sem_trywait(sem_t *sem);

� int sem_timedwait(sem_t *sem, const struct timespec*abs_timeout);

� int sem_post(sem_t *sem);

# 7

'

&

$

%

3 Mécanismes de synchronisation intra-processus

� Basés sur des objets partagés en mémoire

� Utilisation possible d’IPC


Programmation concurrente 3 Mécanismes de synchronisation intra-processus

# 8

'

&

$

%

3.1 Mutex

� Assure une exclusion mutuelle

� Type : pthread_mutex_t

� Initialisation :� pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

� int pthread_mutex_init(ptread_mutex_t *m, constpthread_mutexattr_t *attr);

� Utilisation :� int pthread_mutex_lock(pthread_mutex_t *mutex));

� int pthread_mutex_trylock(pthread_mutex_t *mutex);

� int pthread_mutex_unlock(pthread_mutex_t *mutex);

� Destruction :� int pthread_mutex_destroy(pthread_mutex_t *mutex);

Mutex inter-processus Il est possible de synchroniser des threads de plusieurs processusavec un pthread_mutex_t si celui-ci se trouve dans une zone de mémoire partagée. Pour cela,il est nécessaire de positionner l’attribut PTHREAD_PROCESS_SHARED du mutex avec la fonction intpthread_mutexattr_setpshared(pthread_mutexattr_t *attr, int pshared);

# 9

'

&

$

%

3.2 Moniteur

� Permet d’attendre qu’une condition se réalise

� Constitué d’un mutex et d’une condition

� Exemple d’utilisation :

pthread_mutex_lock (&l);while (! condition) {

pthread_cond_wait (&c, &l);}process_data ();pthread_mutex_unlock (&l);

pthread_mutex_lock (&l);produce_data ();pthread_cond_signal (&c);pthread_mutex_unlock (&l);

Voici les prototypes des fonctions associées aux conditions :

• int pthread_cond_init(pthread_cond_t *cond, const pthread_condattr_t *attr);

• int pthread_cond_destroy(pthread_cond_t *cond);

• pthread_cond_t cond = PTHREAD_COND_INITIALIZER;


3 Mécanismes de synchronisation intra-processus 3.3 Barrière

• int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);

– attend qu’une condition se réalise.

• int pthread_cond_timedwait(pthread_cond_t *cond, pthread_mutex_t *mutex, conststruct timespec *abstime);

• int pthread_cond_signal(pthread_cond_t *cond);

– débloque un thread en attente de la condition

• int pthread_cond_broadcast(pthread_cond_t *cond);

– débloque tous les threads en attente de la condition

Le mutex permet d’assurer qu’entre le test de la condition (while(!condition)) et l’attente(pthread_cond_wait()), aucun thread ne réalise la condition.

Moniteur inter-processus Pour synchroniser plusieurs processus avec un moniteur, il est nécessairede positionner les attributs suivants :

• l’attribut PTHREAD_MUTEX_SHARED du mutex (à l’aide de la fonction intpthread_mutexattr_setpshared(pthread_mutexattr_t *attr, int pshared)).

• l’attribut PTHREAD_PROCESS_SHARED de la condition (à l’aide de la fonction intpthread_condattr_setpshared(pthread_condattr_t *attr, int pshared)).

# 10

'

&

$

%

3.3 Barrière

� Permet d’attendre qu’un ensemble de threads atteignent un point de rendez-vous

� Initialisation :� int pthread_barrier_init(pthread_barrier_t *barrier, const

pthread_barrierattr_t *restrict attr, unsigned count);

� Attente :� int pthread_barrier_wait(pthread_barrier_t *barrier);

I bloque jusqu’à ce que count threads appellent pthread_barrier_waitI débloque tous les count threads

Une fois que tous les threads ont atteint la barrière, ils sont tous débloqués et pthread_barrier_waitretourne 0 sauf pour un thread qui retourne PTHREAD_BARRIER_SERIAL_THREAD.

Barrière inter-processus Pour synchroniser des threads issus de plusieurs processusavec une barrière, il est nécessaire de positionner l’attribut PTHREAD_PROCESS_SHARED avec intpthread_barrierattr_setpshared(pthread_barrierattr_t *attr, int pshared);


Programmation concurrente 4 Patterns de synchronisation classiques

# 11

'

&

$

%

3.3.1 Read-Write lock

� Type : pthread_rwlock_t

� int pthread_rwlock_rdlock(pthread_rwlock_t* lock)

� Verrouillage en lecture� Possibilité de plusieurs lecteurs concurrents

� int pthread_rwlock_wrlock(pthread_rwlock_t* lock)

� Verrouillage en écriture� Exclusion mutuelle avec les autes écrivains et les lecteurs

� int pthread_rwlock_unlock(pthread_rwlock_t* lock)

� Relâche le verrou

# 12

'

&

$

%

4 Patterns de synchronisation classiques

Buts :

� Savoir identifier les patterns classiques

� Implémenter ces patterns avec des méthodes éprouvées

Dans la littérature, ces problèmes sont généralement résolus à l’aide de sémaphores. Cela vient du faitque ces problèmes ont été théorisés dans les années 1960-1970 par Dijkstra en se basant sur des sémaphores.De plus, les sémaphores ont l’avantage de pouvoir être utilisés pour les synchronisations inter-processus ouintra-processus.

Toutefois, les systèmes d’exploitation modernes implémentent de nombreuses primitives de synchroni-sation qui sont bien plus efficacientes que les sémaphores. Dans la suite, nous nous baserons donc sur cesmécanismes plutôt que sur des sémaphores.



# 13

'

&

$

%

4.1 Exclusion mutuelle

� Permet la gestion d’accès concurrents à une ressource partagée

� Principe :� Mutex m initialisé� Primitive mutex_lock(m) en début de section critique� Primitive mutex_unlock(m) en fin de section critique

� Exemple :� mutex m initialisé� Prog1 Prog2

mutex_lock(m) mutex_lock(m)x=lire (cpte) x=lire (cpte)x = x + 10 x = x - 100écrire (cpte=x) écrire (cpte=x)mutex_unlock(m) mutex_unlock(m)

Implémentation intra-processus Dans un processus multi-thread, il suffit d’utiliser un mutex de typepthread_mutex_t.

Implémentation inter-processus Pour implémenter une exclusion mutuelle entre plusieurs processus,plusieurs solutions sont possibles :

• utiliser un pthread_mutex_t dans une zone de mémoire partagée entre les processus. Pour cela, ilest nécessaire de positionner l’attribut PTHREAD_MUTEX_SHARED du mutex (à l’aide de la fonctionpthread_mutexattr_setpshared) ;

• utiliser un sémaphore initialisé à 1. L’entrée en section critique est protégée par sem_wait, et on appellesem_post lors de la sortie de la section critique.

# 14

'

&

$

%

4.2 Cohorte� Permet la coopération d’un groupe de taille maximum donnée� Principe :� Un compteur initialisé à N , et un moniteur m pour le protéger� Décrémenter le compteur en début de besoin� Incrémenter le compteur en fin de besoin

Prog Vehicule...mutex_lock(m);while(cpt == 0){ cond_wait(m); }cpt--;

mutex_unlock(m);|...mutex_lock(m);cpt++;cond_signal(m);

mutex_unlock(m);



# 15

'

&

$

%

4.3 Producteur/Consommateur

� Un/des threads produisent des données

� Un/des threads consomment les données produites

� Communication via un buffer de N cases1. Exécution Produc : il produit info0

info02. Exécution Produc : il produit info1

info0 info13. Exécution Conso : il consomme info0

info14. Exécution Produc : il produit info2

info1 info2

# 16

'

&

$

%

4.3.1 Implémentation d’un Producteur/Consommateur

� Un moniteur places_dispo initialisé à N

� Un moniteur info_prete initialisé à 0Producteur: Consommateur:

répéter répéter... ...

mutex_lock(places_dispo); mutex_lock(info_prete);while(places_dispo<=0) while(info_prete<=0)

cond_wait(places_dispo); cond_wait(info_prete);reserver_slot(); extraire(info)

mutex_unlock(places_dispo); mutex_unlock(info_prete);

calcul(info) mutex_lock(place_dispo);liberer_slot();

mutex_lock(info_prete); cond_signal(place_dispo)déposer(info); mutex_unlock(place_dispo);cond_signal(info_prete);

mutex_unlock(info_prete); ...... finRépéterfinRépéter

Producteur/Consommateur inter-processus Il est bien sûr possible d’implémenter un produc-teur/consommateur entre processus en utilisant des conditions et des mutex. Une autre solution plus simpleconsiste à utiliser un tube : l’écriture dans un tube étant atomique, le dépôt d’une donnée se limite à écriredans le tube, et lire depuis le tube permet l’extraction de la donnée.


4 Patterns de synchronisation classiques 4.4 Lecteur/Rédacteur

# 17

'

&

$

%

4.4 Lecteur/Rédacteur

� Permettre une compétition cohérente entre deux types de processus :� les « lecteurs » peuvent accéder simultanément à la ressource� les « rédacteurs » accèdent à la ressource en exclusion mutuelle avec les autres

lecteurs et rédacteurs

# 18

'

&

$

%

4.4.1 Implémentation d’un Lecteur/Rédacteur

� Utilisation de pthread_rwlock_t� int pthread_rwlock_rdlock(pthread_rwlock_t* lock) pour protéger les

lectures� int pthread_rwlock_wrlock(pthread_rwlock_t* lock) pour protéger les

écritures� int pthread_rwlock_unlock(pthread_rwlock_t* lock) pour relacher le

lock

Implémentation avec un mutex Il est possible d’implémenter le lecteur/rédacteur en utilisant unmutex à la place du rwlock : les lectures et les écritures sont protégées par un mutex. Toutefois, cetteimplémentation ne permet pas à plusieurs lecteurs de travailler en parallèle.

Implémentation avec un moniteur L’implémentation du lecteur/rédacteur à base de moniteur estplus complexe. Elle nécessite principalement :

• un entier readers qui compte le nombre de threads en train de lire

• un booléen writing qui indique qu’un thread est en train d’écrire



• une condition cond pour notifier les changements de ces variables

• un mutex mutex pour protéger les accès concurrents

Voici une implémentation du lecteur/rédacteur utilisant un moniteur :

rw_thread_condition.c# include <stdlib.h># include <unistd.h># include <stdio.h># include <pthread.h>

// This program simulates operations on a set of bank accounts// Two kinds of operations are available :// - read operation : compute the global balance (ie. the sum of all accounts )// - write operation : transfer money from one account to another//// Here ’s an example of the program output ://// $ ./ rw_threads_condition// Balance : 0 ( expected : 0)// 3982358 operation , including :// 3581969 read operations (89.945932 % )// 400389 write operations (10.054068 % )

# define N 200int n_loops = 1000000;int accounts[N];

int nb_read = 0;int nb_write = 0;

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

int readers =0;int writing =0;

/* read all the accounts */int read_accounts () {

pthread_mutex_lock (&mutex);while(writing)

pthread_cond_wait (&cond , &mutex);readers ++;pthread_mutex_unlock (&mutex);

nb_read ++;int sum = 0;for(int i=0; i<N; i++) {

sum += accounts[i];}

pthread_mutex_lock (&mutex);readers --;if(! readers) {

pthread_cond_signal (&cond);}pthread_mutex_unlock (&mutex);return sum;

}

/* transfer amount units from account src to account dest */void transfer(int src , int dest , int amount) {

pthread_mutex_lock (&mutex);while(writing || readers)

pthread_cond_wait (&cond , &mutex);writing = 1;pthread_mutex_unlock (&mutex);

nb_write ++;accounts[dest] += amount;accounts[src] -= amount;

pthread_mutex_lock (&mutex);writing =0;pthread_cond_signal (&cond);pthread_mutex_unlock (&mutex);

}

void* thread_function(void*arg) {for(int i=0; i<n_loops; i++) {



/* randomly perform an operation* threshold sets the proportion of read operation .* here , 90% of all the operations are read operation* and 10% are write operations*/

int threshold = 90;int x = rand ()%100;if(x < threshold) {

/* read */int balance = read_accounts ();if(balance != 0) {

fprintf(stderr , "Error : balance = %d !\n", balance );abort ();

}} else {

/* write */int src = rand ()%N;int dest = rand ()%N;int amount = rand ()%100;transfer(src , dest , amount );

}}return NULL;

}

int main(int argc , char **argv) {for(int i = 0; i<N; i++) {

accounts[i] = 0;}

int nthreads =4;pthread_t tid[nthreads ];

for(int i=0; i<nthreads; i++) {pthread_create (&tid[i], NULL , thread_function , NULL);

}

for(int i=0; i<nthreads; i++) {pthread_join(tid[i], NULL);

}

int balance = read_accounts ();printf("Balance: %d (expected: 0)\n", balance );

int nb_op = nb_read+nb_write;printf("%d operation , including :\n",nb_op);printf("\t%d read operations (%f %% )\n", nb_read , 100.* nb_read/nb_op);printf("\t%d write operations (%f %% )\n", nb_write , 100.* nb_write/nb_op);

return EXIT_SUCCESS;}


Mécanismes de synchronisation

François Trahay


2019–2020

37


# 2

'

&

$

%

Plan du document

2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Opérations atomiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Primitives de synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 De l’utilisation de la synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

# 3

'

&

$

%

1 Introduction

Objectifs de cette séance :

� Comment sont implémentées les primitives de synchronisation ?

� Comment se passer de verrous ?


Mécanismes de synchronisation 2 Opérations atomiques

# 4

'

&

$

%

2 Opérations atomiques

2.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Opérations atomiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3 Test and set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4 À quoi sert volatile ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.5 Compare And Swap (CAS). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .92.6 Fetch and Add . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.8 Barrière mémoire / Memory Fence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.8 Modèle mémoire C11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

# 5

'

&

$

%

2.1 Motivation

� Par défaut, une instruction modifiant une variable est non-atomique

� exemple : x++ donne :� registre = load(x)

� registre ++

� x = store (registre)

→ Problème si la variable est modifiée par un autre thread simultanément



# 6

'

&

$

%

2.2 Opérations atomiques

C11 fournit un ensemble d’opérations atomiques, notamment

� atomic_flag_test_and_set

� atomic_compare_exchange_strong

� atomic_fetch_add

� atomic_thread_fence

# 7

'

&

$

%

2.3 Test and set

� _Bool atomic_flag_test_and_set(volatile atomic_flag* obj)

� positionne un flag et retourne sa valeur précédente

Effectue de manière atomique :

int atomic_flag_test_and_set(int* flag) {int old = *flag;*flag = 1;return old;

}

Implémentation d’un verrou :

void lock(int* lock) {while(atomic_flag_test_and_set(lock) == 1) ;

}

Voici un exemple de programme utilisant un lock à base de test_and_set :

test_and_set.c# include <assert.h># include <stdio.h># include <stdlib.h># include <pthread.h># include <stdatomic.h>

# define NITER 1000000# define NTHREADS 4

volatile int lock =0;

int x = 0;



# ifdef NOT_THREAD_SAFE

/* thread - unsafe version */void do_lock () {

while(lock) ;lock = 1;

}

void do_unlock () {lock = 0;

}

# else

/* thread - safe version */void do_lock () {

while(atomic_flag_test_and_set (&lock)) ;}

void do_unlock () {lock = 0;

}

# endif /* NOT_THREAD_SAFE */

void* thread_function(void* arg) {for(int i=0; i<NITER; i++) {

do_lock ();x++;do_unlock ();

}return NULL;

}

int main(int argc , char **argv) {pthread_t tids[NTHREADS ];int ret;for(int i = 0; i<NTHREADS; i++) {

ret = pthread_create (&tids[i], NULL , thread_function , NULL);assert(ret == 0);

}for(int i = 0; i<NTHREADS; i++) {

ret = pthread_join(tids[i], NULL);assert(ret == 0);

}

printf("x = %d\n", x);return EXIT_SUCCESS;

}

# 8

'

&

$

%

2.4 À quoi sert volatile ?

� Indique au compilateur que la variable peut changer d’un accès à l’autre :� modification par un autre thread� modification par un traitement de signal



Voici un exemple de programme pouvant souffrir d’une optimisation trop agressive par le compilateur :

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

#if USE_VOLATILEvolatile int a = 0;# elseint a = 0;# endif

void* thread1(void*arg) {while(a == 0) ;printf("Coucou\n");return NULL;

}

void* thread2(void*arg) {a = 1;return NULL;

}

int main(int argc , char **argv) {pthread_t t1, t2;pthread_create (&t1 , NULL , thread1 , NULL);pthread_create (&t2 , NULL , thread2 , NULL);

pthread_join(t1, NULL);pthread_join(t2, NULL);return EXIT_SUCCESS;

}

Lorsqu’il est compilé avec le niveau d’optimisation -O0 (c’est-à-dire en désactivant les optimisations),thread1 effectue une attente active, et lorsque thread2 modifie la variable a, il débloque thread1 qui affiche“Coucou” :

$ gcc -o volatile volatile.c -Wall -pthread -O0$ ./volatileCoucou$

Lorsqu’il est compilé avec le niveau d’optimisation -O1, le code généré ne fonctionne plus :

$ gcc -o volatile volatile.c -Wall -pthread -O1$ ./volatile[bloque indéfiniment]^C$

Un examen du code généré par le compilateur permet de comprendre le problème :

$ gcc -o volatile volatile.c -Wall -pthread -O2$ gdb ./volatile[...](gdb) disassemble thread1Dump of assembler code for function thread1:

0x00000000000011c0 <+0>: mov 0x2e7e(%rip),%eax # 0x4044 <a>0x00000000000011c6 <+6>: test %eax,%eax0x00000000000011c8 <+8>: jne 0x11d0 <thread1+16>0x00000000000011ca <+10>: jmp 0x11ca <thread1+10>0x00000000000011cc <+12>: nopl 0x0(%rax)0x00000000000011d0 <+16>: sub $0x8,%rsp0x00000000000011d4 <+20>: lea 0xe29(%rip),%rdi # 0x20040x00000000000011db <+27>: callq 0x1040 <puts@plt>0x00000000000011e0 <+32>: xor %eax,%eax0x00000000000011e2 <+34>: add $0x8,%rsp



0x00000000000011e6 <+38>: retqEnd of assembler dump.$

On voit ici qu’à l’adresse 0x11ca, on saute à l’adresse 0x11ca. On saute donc sur place indéfiniment.Cela s’explique par le fait que la variable a n’est pas volatile. Le compilateur pense donc pouvoir

optimiser l’accès à cette variable : la fonction thread1 ne faisant que des accès en lecture à la variable, ilsuffit de la charger une fois dans un registre (ici, le registre eax, cf. l’instruction 0x11c0), puis de consulterle registre. Lorsque thread2 modifie la variable a, la modification n’est donc pas perçue par thread1 !

Le fait de déclarer la variable volatile force le compilateur à relire la variable à chaque fois :

$ gcc -o volatile volatile.c -Wall -pthread -O2 -DUSE_VOLATILE=1$ gdb volatile(gdb) disassemble thread1Dump of assembler code for function thread1:

0x00000000000011c0 <+0>: sub $0x8,%rsp0x00000000000011c4 <+4>: nopl 0x0(%rax)0x00000000000011c8 <+8>: mov 0x2e76(%rip),%eax # 0x4044 <a>0x00000000000011ce <+14>: test %eax,%eax0x00000000000011d0 <+16>: je 0x11c8 <thread1+8>0x00000000000011d2 <+18>: lea 0xe2b(%rip),%rdi # 0x20040x00000000000011d9 <+25>: callq 0x1040 <puts@plt>0x00000000000011de <+30>: xor %eax,%eax0x00000000000011e0 <+32>: add $0x8,%rsp0x00000000000011e4 <+36>: retq

End of assembler dump.

Ici, la boucle while(a == 0) est traduite par les lignes 0x11c8 à 0x11d0. À chaque tour de boucle, lavaleur de a est chargée, puis testée.

# 9

'

&

$

%

2.5 Compare And Swap (CAS)

� _Bool atomic_compare_exchange_strong(volatile A* obj, C* expected,C desired);

� compare *obj et *expected� s’ils sont égaux, copie desired dans *obj et renvoie true� sinon, renvoie la valeur de *obj dans *expected et renvoie false

Effectue de manière atomique :bool CAS(int* obj , int* expected , int desired) {

if(*obj != *expected) {*expected = desired;return false;

} else {*obj = desired;return true;

}}

Voici un exemple de programme manipulant une liste lock-free grâce à compare_and_swap :

cas.c

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



# include <pthread.h># include <stdatomic.h>


struct node {int value;struct node* next;

};

struct node *stack = NULL;


/* thread - unsafe version */void push(int value) {

struct node* n = malloc(sizeof(struct node ));n->value = value;n->next = stack;stack = n;

}

int pop() {struct node* n = stack;int value = 0;if(n) {

value = n->value;stack = n->next;free(n);

}return value;

}

# else

/* thread - safe version */void push(int value) {

struct node* n = malloc(sizeof(struct node ));n->value = value;

int done = 0;do {

n->next = stack;done = atomic_compare_exchange_strong (&stack , &n->next , n);

} while (!done);}

int pop() {int value = 0;struct node* old_head = NULL;struct node* new_head = NULL;int done = 0;

do {/* Warning : this function still suffers a race condition ( search for

* " ABA problem " for more information ).* Fixing this would be too complicated for this simple example .*/

old_head = stack;if(old_head)

new_head = old_head ->next;done = atomic_compare_exchange_strong (&stack , &old_head , new_head );

} while (!done);

if(old_head) {value = old_head ->value;free(old_head );

}return value;

}


_Atomic int sum = 0;void* thread_function(void* arg) {

for(int i=0; i<NITER; i++) {push (1);

}

int value;while ((value=pop()) != 0) {

sum+=value;}



return NULL;}

int main(int argc , char **argv) {pthread_t tids[NTHREADS ];for(int i = 0; i<NTHREADS; i++) {

pthread_create (&tids[i], NULL , thread_function , NULL);}for(int i = 0; i<NTHREADS; i++) {

pthread_join(tids[i], NULL);}printf("sum = %d\n", sum);return EXIT_SUCCESS;

}

# 10

'

&

$

%

2.6 Fetch and Add

� C atomic_fetch_add( volatile A* obj, M arg );

� remplace obj par arg+obj� retourne l’ancienne valeur de obj

Effectue de manière atomique :

int fetch_and_add(int* obj , int value) {int old = *obj;*obj = old+value;return old;

}

Voici un exemple de programme utilisant fetch_and_add pour incrémenter de manière atomique unevariable :

fetch_and_add.c

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


volatile int x = 0;


/* thread - unsafe version */void inc(volatile int * obj) {

*obj = (*obj )+1;}

# else

/* thread - safe version */void inc(volatile int * obj) {

atomic_fetch_add(obj , 1);}


void* thread_function(void* arg) {



for(int i=0; i<NITER; i++) {inc(&x);

}return NULL;

}

int main(int argc , char **argv) {pthread_t tids[NTHREADS ];for(int i = 0; i<NTHREADS; i++) {

pthread_create (&tids[i], NULL , thread_function , NULL);}for(int i = 0; i<NTHREADS; i++) {

pthread_join(tids[i], NULL);}

printf("x = %d\n", x);return EXIT_SUCCESS;

}

# 11

'

&

$

%

2.7 Barrière mémoire / Memory Fence

� C atomic_thread_fence( memory_order order );

� effectue une synchronisation mémoire� assure que toutes les opérations mémoires passées sont « visibles »par tous les

threads selon le modèle mémoire choisi (voir suite du cours)


2 Opérations atomiques 2.8 Modèle mémoire C11

# 12

'

&

$

%

2.8 Modèle mémoire C11

2.8.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .132.8.3 Relaxed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.8.3 Release Acquire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.8.5 Release-Consume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.8.5 Sequentially Consistent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

# 13

'

&

$

%

2.8.1 Introduction

� Le compilateur/le processeur peuvent réordonnancer les instructions

� C11 défini plusieurs modèles mémoires spécifiant les réordonnancements autorisés

� Spécifie comment les accès mémoires non atomiques sont ordonnancés autour d’uneopération atomique� memory_order_relaxed

� memory_order_consume

� memory_order_acquire

� memory_order_release

� memory_order_acq_rel

� memory_order_seq_cst (par défaut)

La plupart des fonctions atomiques disposent de 2 versions. Par exemple pour pour atomic_fetch_add :

• C atomic_fetch_add( volatile A* obj, M arg ) : opération utilisant le modèle mémoire par dé-faut (sequentially consistent)

• C atomic_fetch_add_explicit( volatile A* obj, M arg, memory_order order ) : même opé-ration, mais utilisant le modèle mémoire spécifié

D’autres opérations atomiques sont également disponibles :

• atomic_store : écriture atomique (écrit tous les octets atomiquement)

• atomic_load : lecture atomique (lit tous les octets atomiquement)



• atomic_exchange : échange atomique de deux valeurs (c’est-à-dire atomic_flag_test_and_set avecn’importe quelle valeur)

Une description plus complète des différents modèles mémoires disponibles en C11 est disponible en ligne :https://en.cppreference.com/w/c/atomic/memory_order

Le modèle mémoire utilisé en JAVA est décrit dans cette publication [Manson et al., 2005].

# 14

'

&

$

%

2.8.2 Relaxed

� Possibilité de réordonnancer les instructions

� Comportement par défaut en JAVA (des variables non volatiles)

� Comportement par défaut en C (pour les instructions non atomiques)x = 0;y = 0;

Thread 1:atomic_store_explicit(&x, 42, memory_order_relaxed); // Aatomic_store_explicit(&y, 42, memory_order_relaxed); // B

Thread 2:r2 = atomic_load_explicit(&y, memory_order_relaxed); // Cr1 = atomic_load_explicit(&x, memory_order_relaxed); // D

� Valeur possible : r1 = 0 et r2 = 42

� B peut être exécuté avant A, ce qui peut conduire à l’ordonnancement B C D A

� D peut être exécuté avant C, ce qui peut conduire à l’ordonnancement D A B C

Avec le modèle mémoire par défaut (relaxed), on peut se demander quel est l’intérêtdes instructions atomic_load_explicit(&x, memory_order_relaxed) et atomic_store_explicit(&x,memory_order_relaxed). Le atomic_load permet d’assurer que, bien que l’instruction puisse être réor-donnancée, la lecture de x est effectuée de façon atomique (c’est-à-dire que tous les octets sont lus de façonatomique). Le atomic_store permet d’assurer de la même façon que tous les octets de x sont modifiés defaçon atomique.

# 15

'

&

$

%

2.8.3 Release Acquire

� Tout ce qui est avant un store est visible à partir du load correspondant

� Tout ce qui suit le load correspondant n’est pas visible avant le store correspondantx = 0;y = 0;z = 0;

Thread1:z = 1; // Ay = 17; // Batomic_store_explicit(x, 42, memory_order_release); // C

Thread2:r1 = atomic_load_explicit(x, memory_order_acquire); // Dr2 = y; // Er3 = z; // F

� si r1==42, alors y==17, et z==1



Pour simplifier, toutes les opérations (non atomiques ou relaxed) placées avant le store release peuventêtre déplacées (par le compilateur par exemple), mais doivent s’exécuter avant le store. Par exemple, l’ordredes instructions A et B peut être échangés, mais on est assuré que A et B ont lieu avant C.

De la même manière, toutes les opérations (non atomiques ou relaxed) placées après le load acquirepeuvent être déplacées, mais doivent s’exécuter après le load. Ainsi, les instructions E et F peuvent s’excéuterdans un ordre quelconque, mais on est assuré que E et F s’exécutent après D.

Il faut savoir que les fonctions pthread_mutex_lock et pthread_mutex_unlock sont des fonctions qui fontchacune une lecture/écriture, et que, fort heureusement, ces lectures/écritures fournissent une sémantiqueacquire-release (plus précisemment en cohérence séquentiel, voir la suite du cours). C’est ce qui permetd’assurer que les instructions placées à l’intérieur d’une section critique sont bien exécutées après la prise deverrou et avant qu’il soit relaché à la fin.

# 16

'

&

$

%

2.8.4 Release-Consume� The specification of release-consume ordering is being revised, and the use of

memory_order_consume is temporarily discouraged.� La spécification est tellement confuse que les développeurs de compilateur ne

l’implémentent souvent pas correctement !� Principe : comme release-acquire, mais ne concerne que les variables qui “portent”

une dépendance.x = 0;y = 0;z = 0;

Thread1:x = 42; // Ay = 42; // Batomic_store_explicit(&z, x, memory_order_release); // C

Thread2:r1 = atomic_load_explicit(&z, memory_order_consume); // Dr2 = y; // Er3 = x; // F

� Si r1==42, alors r3==42 car C porte une dépendance vers A. En revanche, r2peut valoir 0 ou 42 car C ne porte pas de dépendance vers B.

D’après [https://en.cppreference.com/w/c/atomic/memory_order], aucun compilateur n’est capablede suivre les chaînes de dépendance du modèle Release-Consume. Ces opérations sont donc transformées enopérations Release-Acquire (qui est plus restrictif).



# 17

'

&

$

%

2.8.5 Sequentially Consistent

� Comme release-acquire, et assure de plus que tous les threads voient les écritureatomiques en cohérence séquentielle dans le même ordre

� Comportement par défaut des opérations atomiques en Cx = 0; y = 0;Thread 1: atomic_store(&x, 1); // AThread 2: atomic_store(&y, 1); // BThread 3: r1 = atomic_load(&x); r2 = atomic_load(&y);Thread 4: r3 = atomic_load(&x); r4 = atomic_load(&y);

� Si r1 = 1 et r2 = 0, alors A est exécuté avant B pour Thread 3

� Comme on est cohérence séquentiel, c’est aussi le cas pour Thread 4

� Donc on ne peut pas avoir r3 = 0 et r4 = 1 (B exécuté avant A pour Thread 4, cequi serait possible en aquire-release)

Bien souvent, la sémantique acquire-release suffit car, en général, on a uniquement besoin de chaînes dedépendances acquire-release.

Il faut aussi savoir que sur un pentium, à part pour les instructions atomic_load et atomic_store, toutesles autres instructions atomiques sont en cohérence séquentielle car seules ces instructions existent.

Enfin, il faut savoir que les fonctions pthread_mutex_lock et pthread_mutex_unlock utilisent une sé-mantique de cohérence séquentielle. Par exemple, dans le code suivant, on a la garantie que si r1=1 et r2=0,alors on ne peut pas avoir r3=0 et r4=1 :

pthread_mutex_t lock;x = 0;y = 0;

Thread 1: pthread_mutex_lock(&lock); // 1.ax = 1; // 1.bpthread_mutex_unlock(&lock); // 1.c

Thread 2: pthread_mutex_lock(&lock); // 2.ay = 1; // 2.bpthread_mutex_unlock(&lock); // 2.c

Thread 3: pthread_mutex_lock(&lock); // 3.ar1 = x; // 3.br2 = y; // 3.cpthread_mutex_unlock(&lock); // 3.d

Thread 4: pthread_mutex_lock(&lock); // 4.ar3 = x; // 4.br4 = y; // 4.cpthread_mutex_unlock(&lock); // 4.d

On suppose r1 = 1 et r0 = 0. On commence par regarder l’ordre d’exécution vu par le thread 3. Commer1 = 1, on a forcément 1.b -> 3.b (où -> signifie précède). Comme on a une sémantique acquire-releaseentre 1.c et 3.a et que le thread 3 ne peut que entrer en section critique lorsque le verrou est libre, on nepeut que avoir 1.b -> 1.c -> 3.a -> 3.b. De la même façon comme r2 = 0, on a forcément 3.d -> 2.a.Donc, vu par thread 3, 1.c -> 2.a.


Mécanismes de synchronisation 3 Primitives de synchronisation

Comme les fonctions pthread_mutex_lock et pthread_mutex_unlock ont une sémantique sequentialconsistency, 1.c -> 2.a dans Thread 4 aussi. Si r3 = 0, alors, en prenant en compte le fait que les verrousdoivent être libres pour entrer en section critique et en prenant en compte la sémantique acquire-release lorsde la prise de verrou, on ne peut que avoir cette exécution vu par thread 4 : 4.a -> 4.b -> 4.c -> 4.d-> 1.a -> 1.b -> 1.c. Ensuite 1.c -> 2.a dans thread 4 puisque c’est le cas dans thread 3, et 2.a ->2.b vu par thread 4 à cause de la sémantique acquire-release des prises de verrou. On a donc 4.c -> 2.b,et donc r4 = 0. On ne peut donc pas avoir r3 = 0 et r4 = 1.

# 18

'

&

$

%

3 Primitives de synchronisation

Propriétés à prendre en compte lors du choix d’une primitive de synchronisation

� Réactivité : temps passé entre le relâchement d’un verrou et le débloquage d’unthread attendant ce verrou

� Contention : traffic mémoire engendré par l’attente d’un verrou

� Équité et risque de famine : si plusieurs threads attendent un verrou, ont-ils tous lamême probabilité de l’obtenir ? Certains risquent-ils d’attendre indéfiniment ?

# 19

'

&

$

%

3.1 Synchronisation par attente active

� int pthread_spin_lock(pthread_spinlock_t *lock);

� teste la valeur du verrou jusqu’à ce qu’il soit libre, puis prend le verrou

� int pthread_spin_unlock(pthread_spinlock_t *lock);

� Avantages� Simple à implémenter (avec test_and_set)� Réactivité

� Inconvénients� Consomme du CPU à attendre� Consomme de la bande passante mémoire à attendre

Il est également possible d’implémenter soi-même un spinlock à l’aide d’une opération atomique :

spin_lock.c



# include <stdio.h># include <stdlib.h># include <unistd.h># include <pthread.h># include <stdatomic.h># include <assert.h>


struct lock {/* if flag =0, the lock is available

* if flag =1, the lock is taken*/

volatile int flag;};typedef struct lock lock_t;

void lock(lock_t *l) {/* try to set flag to 1.

* if the flag is already 1, loop and try again*/

while(atomic_flag_test_and_set (&l->flag)) ;}

void unlock(lock_t *l) {l->flag = 0;

}

void lock_init(lock_t *l) {l->flag = 0;

}

lock_t l;int x;

void* thread_function(void*arg){for(int i=0; i<NITER; i++) {

lock(&l);x++;unlock (&l);

}return NULL;

}

int main(int argc , char **argv) {lock_init (&l);

pthread_t tids[NTHREADS ];int ret;for(int i = 0; i<NTHREADS; i++) {




}

printf("x = %d\n", x);printf("expected: %d\n", NTHREADS*NITER );return EXIT_SUCCESS;

}



# 20

'

&

$

%

3.2 Futex

Fast Userspace Mutex

� Appel système permettant de construire des mécanismes de synchronisation enuserland

� Permet d’attendre sans monopoliser le CPU

� Un futex est constitué de :� une valeur� une liste d’attente

� Opérations disponibles (entre autres)� WAIT(int *addr, int value)

I while(*addr == value) sleep(); : met le thread courant en attente� WAKE(int *addr, int value, int num)

I *addr = value : réveille num threads en attente sur addr

# 21

'

&

$

%

3.3 Construction d’un mutex à l’aide d’un futex

� mutex : un entier à 1 (déverrouillé), ou 0 (verrouillé)

� mutex_lock(m) :� Test and unset du mutex� Si mutex vaut 0, on fait FUTEX_WAIT

� mutex_unlock(m) :� Test and set du mutex� on fait FUTEX_WAKE pour réveiller un thread en attente

Voici un exemple de programme implémentant un mutex à l’aide de futex :

mutex.c# include <stdio.h># include <stdlib.h># include <unistd.h># include <pthread.h># include <stdatomic.h># include <linux/futex.h># include <sys/time.h># include <sys/syscall.h># include <errno.h># include <assert.h>

# define NITER 1000000



# define NTHREADS 4

struct lock {int flag;

};typedef struct lock lock_t;

static int futex(int *uaddr , int futex_op , int val ,const struct timespec *timeout , int *uaddr2 , int val3) {

return syscall(SYS_futex , uaddr , futex_op , val ,timeout , uaddr , val3);

}

void lock(lock_t *l) {while (1) {

/* Is the futex available ? */int expected = 1;if (atomic_compare_exchange_strong (&l->flag , &expected , 0))

return; /* Yes */

/* Futex is not available ; wait */int s = futex(&l->flag , FUTEX_WAIT , 0, NULL , NULL , 0);if (s == -1 && errno != EAGAIN) {

perror("futex_wait failed");abort ();

}}

}

void unlock(lock_t *l) {int expected = 0;atomic_compare_exchange_strong (&l->flag , &expected , 1);int s = futex(&l->flag , FUTEX_WAKE , 1, NULL , NULL , 0);if (s == -1) {

perror("futex_wake failed");abort ();

}}

void lock_init(lock_t *l) {l->flag = 1;

}

lock_t l;int x;

void* thread_function(void*arg){for(int i=0; i<NITER; i++) {

// printf ("% d\n", i);lock(&l);x++;unlock (&l);

}return NULL;

}

int main(int argc , char **argv) {lock_init (&l);

pthread_t tids[NTHREADS ];int ret;for(int i = 0; i<NTHREADS; i++) {




}

printf("x = %d\n", x);printf("expected: %d\n", NTHREADS*NITER );return EXIT_SUCCESS;

}



# 22

'

&

$

%

3.4 Construction d’un moniteur à l’aide d’un futex

� condition : un compteurstruct cond {

int cpt;};

void cond_wait(cond_t *c, pthread_mutex_t *m) {int value = atomic_load (&c->value);pthread_mutex_unlock(m);futex(&c->value , FUTEX_WAIT , value);pthread_mutex_lock(m);

}

void cond_signal(cond_t *c) {atomic_fetch_add (&c->value , 1);futex(&c->value , FUTEX_WAKE , 0);

}

Voici un exemple de programme implémentant une condition à l’aide de futex :

cond.c# include <stdlib.h># include <unistd.h># include <stdio.h># include <pthread.h># include <sys/syscall.h># include <linux/futex.h># include <stdatomic.h># include <assert.h>

# define N 10

int n_loops = 20;

struct cond {int cpt;

};typedef struct cond cond_t;

static int futex(int *uaddr , int futex_op , int val) {return syscall(SYS_futex , uaddr , futex_op , val , NULL , uaddr , 0);

}

void cond_init(cond_t *c) {c->cpt = 0;

}

void cond_wait(cond_t *c, pthread_mutex_t *m) {int cpt = atomic_load (&c->cpt);pthread_mutex_unlock(m);futex(&c->cpt , FUTEX_WAIT , cpt);pthread_mutex_lock(m);

}

void cond_signal(cond_t *c) {atomic_fetch_add (&c->cpt , 1);futex(&c->cpt , FUTEX_WAKE , 0);

}

struct monitor{int value;pthread_mutex_t mutex;cond_t cond;

};

int infos[N];



int i_depot , i_extrait;int nb_produits = 0;struct monitor places_dispo;struct monitor info_prete;

void* function_prod(void*arg) {static _Atomic int nb_threads =0;int my_rank = nb_threads ++;

for(int i=0; i<n_loops; i++) {int cur_indice;int product_id;usleep (100);pthread_mutex_lock (& places_dispo.mutex);while(places_dispo.value == 0) {

cond_wait (& places_dispo.cond , &places_dispo.mutex );}places_dispo.value --;cur_indice = i_depot ++;i_depot = i_depot % N;

product_id = nb_produits ++;pthread_mutex_unlock (& places_dispo.mutex);

usleep (500000);printf("P%d produit %d dans %d\n", my_rank , product_id , cur_indice );

pthread_mutex_lock (& info_prete.mutex );infos[cur_indice] = product_id;info_prete.value ++;cond_signal (& info_prete.cond);pthread_mutex_unlock (& info_prete.mutex );

}return NULL;

}

void* function_cons(void*arg) {static _Atomic int nb_threads =0;int my_rank = nb_threads ++;

for(int i=0; i<n_loops; i++) {int cur_indice;int product_id;usleep (100);pthread_mutex_lock (& info_prete.mutex );while(info_prete.value == 0) {

cond_wait (& info_prete.cond , &info_prete.mutex);}info_prete.value --;product_id = infos[i_extrait ];cur_indice = i_extrait;i_extrait = (i_extrait +1) % N;pthread_mutex_unlock (& info_prete.mutex );

usleep (100000);printf("C%d consomme %d depuis %d\n", my_rank , product_id , cur_indice );

pthread_mutex_lock (& places_dispo.mutex);places_dispo.value ++;cond_signal (& places_dispo.cond);pthread_mutex_unlock (& places_dispo.mutex);

}return NULL;

}

void init_monitor(struct monitor *m, int value) {m->value = value;pthread_mutex_init (&m->mutex , NULL);cond_init (&m->cond);

}

int main(int argc , char **argv) {init_monitor (& places_dispo , N);init_monitor (&info_prete , 0);i_depot = 0;i_extrait = 0;

int nthreads_prod =2;int nthreads_cons =2;pthread_t tid_prod[nthreads_prod ];pthread_t tid_cons[nthreads_cons ];int ret;


Mécanismes de synchronisation 4 De l’utilisation de la synchronisation

for(int i=0; i<nthreads_prod; i++) {ret = pthread_create (& tid_prod[i], NULL , function_prod , NULL);assert(ret == 0);

}for(int i=0; i<nthreads_cons; i++) {

ret = pthread_create (& tid_cons[i], NULL , function_cons , NULL);assert(ret == 0);

}

for(int i=0; i<nthreads_prod; i++) {ret = pthread_join(tid_prod[i], NULL);assert(ret == 0);

}for(int i=0; i<nthreads_cons; i++) {

ret = pthread_join(tid_cons[i], NULL);assert(ret == 0);

}


# 23

'

&

$

%

4 De l’utilisation de la synchronisation

Problèmes classiques :

� interblocage (ou deadlock)

� granularité du verrouillage

� passage à l’échelle


Mécanismes de synchronisation 4 De l’utilisation de la synchronisation

# 24

'

&

$

%

4.1 Interblocage / Deadlock

� Situation telle que deux processus au moins sont chacun en attente d’une ressourcenon partageable déja allouée à l’autre

� Conditions nécessaires et suffisantes (Coffman, 1971[Coffman et al., 1971])1. Ressources en exclusion mutuelle (ressources concernées non partageables)2. Processus en attente (les processus conservent les ressources allouées)3. Non-préemption des ressoruces (ressources concernées non préemptibles)4. Chaîne circulaire de processus bloqués

� Stratégies :� Prévention : acquisition des mutex dans le même ordre, évitement� Détection puis résolution de deadlock (eg. avec pthread_mutex_timedlock)

# 25

'

&

$

%

4.2 Granularité

� Verrouillage à gros grain (Coarse grain locking)� Un verrou protège une grande portion de programme� Avantage : simple à implémenter� Inconvénient : réduit le parallélisme

� Verrouillage à grain fin (Fine grain locking)� Chaque verrou protège une portion réduite du programme� Avantage : possibilité d’utiliser des ressources diverses en parallèle� Inconvénients :I Complexe à implémenter sans bugI La prise de verrou a un coût



# 26

'

&

$

%

4.3 Scalabilité d’un système parallèle

� Scalabilité = capacité à réduire le temps d’exécution quand on ajoute des unités decalcul

� Les parties séquentielles d’un programme réduisent la scalabilité d’un programme(loi d’Amdhal [Amdahl, 1967])

� Dans un programme parallèle, l’attente d’un verrou introduit de la séquentialité

→ Les verrous peuvent nuire à la scalabilité

Le sujet de la scalabilité est discuté plus en détails dans le module CSC5001 Systèmes Hautes Perfor-mances.

Bibliographie du chapitre[Amdahl, 1967] Amdahl, G. M. (1967). Validity of the single processor approach to achieving large scale

computing capabilities. In Proceedings of the April 18-20, 1967, spring joint computer conference, pages483–485. ACM.

[Coffman et al., 1971] Coffman, E. G., Elphick, M., and Shoshani, A. (1971). System deadlocks. ACMComputing Surveys (CSUR), 3(2) :67–78.

[Manson et al., 2005] Manson, J., Pugh, W., and Adve, S. V. (2005). The Java Memory Model. In Procee-dings of the 32Nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL’05, pages 378–391. ACM.




Appels système

Gaël Thomas


2019–2020

61

Appels système

# 2

'

&

$

%

1 Le Système d’exploitation

� Fonctionnalités� Offre une interface de programmation unifiée au développeur� Cache les détails de mise en œuvre du matériel� Permet d’exécuter plusieurs processus sur un processeur

� Composition� Une bibliothèque appelée noyau (kernel en anglais)I Interface de programmation unifiée (open, fork. . . )I Définie par des spécifications (System V, POSIX, Win32. . . )� + Un ensemble de programmes permettant d’interagir avec le noyauI ls, cp, X, gnome, etc.

# 3

'

&

$

%

1.1 Le système d’exploitation (2/2)

Processus 1 Processus 2

Noyau

Matériel

read()

signal()

iderw() INTRswtch()

Télécom SudParis — Gaël Thomas — 2019–2020 — CSC4508 – Systèmes d’exploitation 62

Appels système 2 L’interface user/system

# 4

'

&

$

%

2 L’interface user/system

� Le noyau doit se protéger des processus� Pour éviter les bugs� Pour déjouer les attaques

� Pour cela, le processeur offre deux modes de fonctionnement� Le mode system : accès à toute la mémoire et à l’ensemble des instructions du

processeur� Le mode user : accès uniquement à la mémoire du processus et à un jeu

d’instructions restreintI En particulier, pas d’accès direct aux périphériques et aux instructions qui

gèrent les droits associés à la mémoire

# 5

'

&

$

%

2.1 L’interface user/system

� Problème : comment appeler une fonction du noyau alors qu’on ne peut pas accéderà sa mémoire ?

Codeprocessus

Donnéesprocessus

Codenoyau

Donnéesnoyau

g() du processusappelle la fonction

read du noyau

code f()et g()

f() du processusappelle g() du processus

OK

accessiblemémoire

inaccessiblemémoire code de read()

Impossible !!!Accès mémoire

interdit


Appels système 2 L’interface user/system

# 6

'

&

$

%

2.2 L’interface user/system

� Solution : instruction spéciale du processeur appelée trap� Noyau associe l’adresse d’une fonction appelée syscall à trap

� Pour appeler une fonction du noyauI Le processus donne le n° de fonction à appeler via un paramètreI Le processus exécute l’instruction trapI Le processeur change de mode et exécute syscallI syscall utilise le paramètre pour sélectionner la fonction à exécuter

Codeprocessus

Donnéesprocessus

Codenoyau

Donnéesnoyau

paramètre = 4 (read)trap

accessiblemémoire

inaccessiblemémoire

syscall

read

En fonction du type de processeur, la manière d’effectuer un appel système peut varier. La façon depasser les paramètres est une convention pouvant varier d’un OS à l’autre. Par exemple, pour Linux :

x86_32 :

• Les paramètres de l’appel système sont stockés dans les registres ebx, ecx, edx, esi, edi, et ebp ;

• Le numéro d’appel système est chargé dans le registre eax ;

• Le passage en mode noyau se fait en générant l’interruption 128 : INT 0x80 ;

• À la fin de l’appel système, la valeur de retour est stockée dans le registre eax.

x86_64

• Les paramètres de l’appel système sont stockés dans les registres rdi, rsi, rdx, rcx, r8, et r9 ;

• Le numéro d’appel système est chargé dans le registre rax ;

• Le passage en mode noyau se fait avec l’instruction syscall ;

• La valeur de retour de l’appel système est stockée dans le registre rax.

ARM 64 bits

• Les paramètres de l’appel système sont stockés dans les registres x0 à x5 ;

• Le numéro d’appel système est chargé dans le registre x8 ;

• Le passage en mode noyau se fait avec l’instruction svc 0 ;

• La valeur de retour de l’appel système est stockée dans le registre x0.


Interruptions et communication

Gaël Thomas


2019–2020

65

Interruptions et communication 1 Les bus de communication

# 2

'

&

$

%

Plan du document

1 Les bus de communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Interruptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

# 3

'

&

$

%

1 Les bus de communication

1.1 Les bus de communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Le bus mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3 Le bus d’entrées/sorties. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .82.1 Le bus d’interruptions – principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10


1 Les bus de communication 1.2 Le bus mémoire

# 4

'

&

$

%

1.1 Les bus de communication

� Les composants matériels communiquent via des busbus de communication

� Du point de vue logiciel, 3 principaux bus� Bus mémoire : principalement pour accéder à la mémoire� Bus d’entrée/sortie : message processeur vers périphérique� Bus d’interruption : message périphérique vers processeur

� Du point de vue matériel : un ensemble de bus matériels avec différents protocolespouvant multiplexer les bus logiciels

# 5

'

&

$

%

1.2 Le bus mémoire

� Processeur utilise le bus mémoire pour les lectures/écritures� Émetteur : le processeur ou un périphérique� Récepteur : le plus souvent la mémoire, mais peut aussi être un périphérique

(memory-mapped IO)bus mémoire<write, 1024, 42>

x = 42avec @x = 1024 4217 23... ...

1024eme case mémoire = variable x


Interruptions et communication 1 Les bus de communication

# 6

'

&

$

%

1.2.1 DMA : Direct Memory Access� Périphérique utilise le bus mémoire pour les lectures/écritures� Émetteur : le processeur ou un périphérique� Récepteur : le plus souvent la mémoire, mais peut aussi être un périphérique

(memory-mapped IO)

� Le controleur DMA gère le transfert entres les périphérique ou la mémoire� Le processeur configure le controleur DMA� Le controleur DMA effectue le transfert� Lorsqu’il a fini, le controleur DMA émet une interruption

=⇒ Le processeur peut exécuter autre chose pendant une entrée/sortiebus mémoire<write, 1025, 66>

Envoi d'une donnée4217 66... ...

1025eme case mémoire

stockée sur disquedans la mémoire

# 7

'

&

$

%

1.2.2 MMIO : Memory-Mapped IO

� Processeur utilise le bus mémoire pour accéder au périphérique� Émetteur : le processeur ou un périphérique� Récepteur : le plus souvent la mémoire, mais peut aussi être un périphérique

(memory-mapped IO)

� La mémoire du périphérique est mappée en mémoire� Lorsque le processeur accède à cette zone mémoire, les données sont transférées

depuis/vers le périphériquebus mémoire <write, 0xb8000, 'a'>

4217 66... ...


Interruptions et communication 2 Interruptions

# 8

'

&

$

%

1.3 Le bus d’entrées/sorties

� Protocole requête/réponse, instructions spéciales in/out� Émetteur : le processeur� Récepteur : un périphérique� Exemples : activer la diode caps-lock, lancer un DMA, lire la touche pressée sur

un clavier...bus I/O<out, 0x1F1, 0xc8>

A la réception,4217 66... ...démarre un transfert

DMA

# 9

'

&

$

%

1.4 Le bus d’interruptions – principe

� Utilisé pour signaler un événement à un processeur� Émetteur : un périphérique ou un processeur� Récepteur : un processeur� Exemples : touche clavier pressée, DMA terminé, milliseconde écoulée...� IRQ (Interrupt ReQuest) : numéro d’interruption. Identifie le périphérique

émetteurbus d'interruptions<IRQ, 0x14>

Fin de DMA4217 66... ...=> interruption pour

prévenir le processeur



# 10

'

&

$

%

2 Interruptions

2.2 Réception d’une interruption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2 Réception d’une interruption : exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.4 Réception d’une interruption (suite) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.4 Interruptions et multicœurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.6 MSI : Message Signaling Interrupt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .162.6 Communication inter cœur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .162.8 La table IDT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.8 Gestion du temps : deux sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

# 11

'

&

$

%

2.1 Réception d’une interruption

� Deux tables configurées par le noyau pour gérer la réception� Table de routage : associe une IRQ à un numéro d’IDT� Table IDT (interrupt descriptor table) : associe un numéro d’IDT à une

fonction appelée gestionnaire d’interruption

� Deux tables permettent plus de souplesse qu’une unique table qui associe unnuméro d’IRQ directement à un gestionnaire

� Utile en particulier en multicœurs (voir la suite du cours)



# 12

'

&

$

%

2.2 Réception d’une interruption : exemple

� Un périphérique envoie une IRQ (par exemple 0x14)

� La table de routage associe IRQ14 à IDT47

� La table IDT indique que IDT47 est géré par la fonction handle_disk_interrupt

bus d'interruptions<IRQ, 0x14>

Table de routage: IRQ14 => IDT 47

Table IDT: IDT 47 => gestionnairehandle_disk_interrupt

# 13

'

&

$

%

2.3 Réception d’une interruption (suite)

� Dans le processeur, après l’exécution de chaque instruction� Regarde si une interruption a été reçue� Si c’est le cas, trouve l’adresse du gestionnaire associé� Passe en mode noyau et exécute le gestionnaire� Puis repasse dans le mode précédent et continue l’exécution là où elle s’était

interrompue

� Remarque : un gestionnaire peut être exécuté n’importe quand� Problème d’accès concurrent entre les gestionnaires et le reste du code du noyau� Solution : masquer les interruptions (cli/sti)



# 14

'

&

$

%

2.4 Interruptions et multicœurs

� Protocole xAPIC sur pentium (x2APIC depuis les processeurs Intel Core)� Chaque cœur possède un numéro appelé n° d’APIC (Advanced Programmable

Interrupt Controller)� Chaque cœur gère les interruptions via son LAPIC (local APIC)� Un IOAPIC route une interruption vers un LAPIC donnéI Table de routage configurée par le noyau du système

<IRQ, 0x14>

Table de routage

IOAPIC

Coeur 1

LAPIC

Coeur 0

LAPIC

Coeur 3

LAPIC

Coeur 2

LAPIC

<APIC1, IDT 47>

IRQ14 =>APIC1 - IDT 47...

Table IDT: IDT47 => gestionnairehandle_disk_interrupt

# 15

'

&

$

%

2.5 MSI : Message Signaling Interrupt

� MSI : interruption directe d’un périphérique à un LAPIC sans passer par le IOAPIC� Le noyau doit configurer le périphérique pour que le périphérique sache quel

couple LAPIC/IDT doit être généré� Utilisé lorsque le besoin de performances est important

Coeur 1

LAPIC

Coeur 0

LAPIC

Coeur 3

LAPIC

Coeur 2

LAPIC<APIC1, IDT 47>

Table IDT: IDT47 => gestionnairehandle_disk_interrupt



# 16

'

&

$

%

2.6 Communication inter cœur

� Un cœur peut envoyer une interruption à un autre coeur� Appelé Inter-Processor Interrupt (IPI)� LAPIC x envoie un IPI à LAPIC y� Dans LAPIC y, la réception d’un IPI est associé à un n° d’IDT

<IPI, APIC1>

Coeur 1

LAPIC

Coeur 0

LAPIC

Coeur 3

LAPIC

Coeur 2

LAPIC

IPI => IDT34Table IDT: IDT34 => gestionnaire handle_ipi

# 17

'

&

$

%

2.7 La table IDT

� Table qui associe un gestionnaire à chaque n° d’IDT� Utilisé par les interruptions comme vu précédemment� Mais aussi pour un appel système : int 0x64 génère simplement l’interruption

IDT 0x64

� Mais aussi pour attraper les fautes lors d’exécution d’instructionsI une division par zéro génère l’interruption IDT 0x00, un accès mémoire illicite

(SIGSEGV) l’interruption IDT 0x0e etc.

� La table IDT est donc la table qui contient l’ensemble des points d’entrées vers lenoyau� Provenant du logiciel via l’appel système� Provenant du matériel pour les autres IDTs



# 18

'

&

$

%

2.8 Gestion du temps : deux sources

� Jiffies : source de temps globale pour mettre à jour l’heure� Périphérique (par ex., HPET) envoie régulièrement une IRQ� Réceptionné par un unique cœur qui met à jour l’heure

� Tick : source de temps locale à un cœur pour l’ordonnancement� LAPIC génère régulièrement une interruption à son cœur� Le système associe un n° d’IDT et un gestionnaire à cette interruption� Moins précis que le jiffies


Mémoire virtuelle

François Trahay


2019–2020

75

Mémoire virtuelle

# 2

'

&

$

%

1 Introduction

� Un processus a besoin d’être présent en mémoire centrale pour s’exécuter

� Mémoire centrale divisée en deux parties :� L’espace réservé au système d’exploitation� L’espace alloué aux processus

� La gestion mémoire concerne l’espace processus

� Capacités mémoire augmentent, mais les besoins aussi=⇒ Nécessité de plusieurs niveaux� Mémoire(s) rapide(s) (cache[s])� Mémoire centrale� Mémoire auxiliaire (disque)

Principe d’inclusion pour limiter les mises à jour entre les différents niveaux

À propos du principe d’inclusion, dans une architecture Intel, le cache L1 (Level 1) est inclus dans lecache L2 (Level 2), lui-même inclus dans la RAM, elle-même incluse dans le swap (disque).

Voici les temps d’accès typiques à des données situées dans les différents types de mémoire sur unemachine « classique »(processeur Intel Core i5 Skylake) en 2017 1 :

• donnée dans le cache L1 : 4 cycles soit 1 ns

• donnée dans le cache L2 : 12 cycles soit 3 ns (3 fois plus lent que L1)

• donnée dans le cache L3 : 44 cycles soit 10 ns (10 fois plus lent que L1)

• donnée dans la RAM : 60 - 100 ns (100 fois plus lent que L1)

• donnée sur un disque NVMe : 20 µ (20 000 fois plus lent que L1)

• donnée sur un disque SSD : 150 µs (150 000 fois plus lent que L1)

• donnée sur un disque dur : 10 ms (10 millions de fois plus lent que L1)

Le tableau suivant montre les différences de coût entre les types de mémoire (et l’évolution avec lesannées) :

Année 2008 2009 2010 2014 2019Disque dur, 7200 tr/mn (en €/Go) 0,50 0,32 0,10 0,04 0.027Disque SSD (en €/Go) – – – 0,50 0.17Clé USB (en €/Go) – – 1,64 0.62 0.27RAM (en €/Go) – 37,00 21,85 8.75 7.23NVMe (en €/Go) – – – – 0.21

1. Données disponibles dans le manuel “Intel 64 and IA-32 Architectures Optimization Reference Manual”


Mémoire virtuelle 2 Pagination

# 3

'

&

$

%

2 Pagination

2.2 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 État des pages mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.4 Adresse logique (ou virtuelle) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.6 Table des pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.6 Mise en œuvre sur un pentium 64 bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.6 Translation Lookaside Buffer (TLB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

# 4

'

&

$

%

2.1 Généralités

virtual memoryP1

virtual memoryP2 physical memory

� Espace adressable de chaque programme découpé en pages

� Mémoire physique divisée en cadres de pages

� Correspondance de certaines pages avec des cadres de pages



# 5

'

&

$

%

2.2 État des pages mémoire

� Les pages d’un processus peuvent être� En mémoire centrale / en RAM (pages actives)� Inexistantes en mémoire (pages inactives jamais écrites)� En mémoire secondaire / dans le Swap (pages inactives qui ont déjà été écrites)

=⇒ chaque processus possède un espace mémoire contigu où stocker ses données

� Le dispositif de pagination� Effectue la correspondance d’adresse� Charge les pages nécessaires (déroutement par défaut de page)� (Éventuellement) décharge des pages actives en mémoire secondaire

Sous Linux, les cadres de page ont une taille de 4 Ko (taille définie par les constantes PAGE_SIZE etPAGE_SHIFT dans le fichier page.h).

# 6

'

&

$

%

2.3 Adresse logique (ou virtuelle)

� Espace adressable divisé à partir des bits de poids forts de l’adresse

Adresse logique sur k bitsNuméro de Page Déplacement dans la page

p bits ( d = (k − p) bits )

=⇒ 2p pages et une page contient 2k−p octets

� Taille d’une page� À l’origine : 512 octets ou 1 Ko� Aujourd’hui : 4 Ko (k-p = 12 bits, donc p = 52 bits) et plus

� Choix = compromis entre divers critères opposés� Dernière page à moitié gaspillée� Temps de transfert d’une page faible par rapport au temps d’accès total� Mémoire de petite capacité : petites pages

Sur les architectures Intel 64 bits (x86_64) ou ARM 64 bits (ARMv8), les adresses sont stockées sur 64bits (c’est-à-dire size(void*) vaut 8 octets), mais seuls 48 bits sont utilisables pour les adresses virtuelles.



Huge pages Certaines applications manipulent de grandes quantités de données (parfois plusieurs Go)qui doivent être placées dans de très nombreuses pages mémoires de 4 Ko. Afin de limiter le nombre depages à manipuler, certaines architectures (notamment arm64 et x86_64) permettent l’utilisation de pagesmémoire plus grandes (typiquement 2 Mo et 1 Go) appelées huge pages.

# 7

'

&

$

%

2.4 Table des pages� La correspondance entre adresse logique et adresse physique se fait avec une table

des pages contenant� Numéro de cadre de page� Bits d’information (présence, permissions, date de chargement. . .)

offsetl. page

logical address

information physical page

01...

p. page

offsetp. page

page table

physical address

RAM

off

set

addressed word

swap

page fault

page hit

# 8

'

&

$

%

2.5 Mise en œuvre sur un pentium 64 bits� Table des pages = arbre à 4 niveaux :� L’adresse physique d’une table racine de 512 entrées est stockée dans le registre CR3� Chaque entrée d’une table donne l’adresse de la table suivante

� @virt décomposée en 4 index (n[0..3]) + 1 offset, puis traduit avec :uint64_t cur = %cr3; // cur = adresse physique de la table racinefor(int i=0; i<3; i++)

cur = ((uint64_t*)cur)[n[i]]; // accès mémoire physique, entrée suivantereturn cur + offset; // ajoute l’offset

@virt = 0x1

47 39

0x3

38 30

0x2

29 21

0x8

20 12

0x016

11 0 bits

Processor

%cr3 =

0x1000

0x00

0x01

0x02

0x03

...

0xfe

0xff

...

0x5000

0x00

0x01

0x02

0x03

...

0xfe

0xff

...

0x8000

0x00

0x01

0x02

0x03

...

0xfe

0xff

...

0xa000

...

...

0x00

0x01

...

0x08

...

0xfe

0xff

...

0xc000

0xc016@phy =

0x1000

physical addresses0x5000 0x8000 0xa000

@virt = 0x01030208016


Mémoire virtuelle 3 Le point de vue utilisateur

# 9

'

&

$

%

2.6 Translation Lookaside Buffer (TLB)

� Problème : tout accès à une information nécessite plusieurs accès mémoire

� Solution : utiliser des mémoires associatives (registres d’accès rapide)

� Principe� On a un certain nombre de registres à disposition� Numéro de page logique Np comparé au contenu de chaque registre� Égalité trouvée → en sortie numéro Nc du cadre correspondant� Sinon utilisation de la table des pages

offsetl. page

logical address

logical page physical page

01...

p. page

offsetp. page

Translation Lookaside Buffer

physical address

RAM

off

set

addressed word

l. page

tlb hit

tlb miss

page table

Dans une architecture Intel, on dispose d’un Translation Look-aside Buffer (TLB) muni de 32, 64, voire256 entrées. NB : on parle également de cache de traduction d’adresse.

# 10

'

&

$

%

3 Le point de vue utilisateur

3.1 Espace mémoire d’un processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.3 Mapping mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .133.3 Allocation mémoire. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .134.0 Le point de vue libc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15



# 11

'

&

$

%

3.1 Espace mémoire d’un processus

Composé de :� l’espace réservé au noyau� les différentes section du fichier ELF

exécuté (.text, .data, etc.)� le tas� la pile (une par thread)� les bibliothèques dynamiques

0x0000000000000000.text

.data

.bss

Heap





Instructions

users

pace


brk

Stack 1

Stack 2

0x0000008000000000

kernel

N/A

0xFFFFFF8000000000

0xFFFFFFFFFFFFFFFF

# 12

'

&

$

%

3.2 Mapping mémoireComment peupler l’espace mémoire d’un processus ?

� Pour chaque fichier ELF à charger :� ouverture du fichier avec open� chaque section ELF est mappée en mémoire (avec mmap) avec des permissions

adaptées

� Résultat visible dans /proc/<pid>/maps$ cat /proc/self/maps5572f3023000-5572f3025000 r--p 00000000 08:01 21495815 /bin/cat5572f3025000-5572f302a000 r-xp 00002000 08:01 21495815 /bin/cat5572f302e000-5572f302f000 rw-p 0000a000 08:01 21495815 /bin/cat5572f4266000-5572f4287000 rw-p 00000000 00:00 0 [heap]7f33305b4000-7f3330899000 r--p 00000000 08:01 22283564 /usr/lib/locale/locale-archive7f3330899000-7f33308bb000 r--p 00000000 08:01 29885233 /lib/x86_64-linux-gnu/libc-2.28.so7f33308bb000-7f3330a03000 r-xp 00022000 08:01 29885233 /lib/x86_64-linux-gnu/libc-2.28.so[...]7f3330ab9000-7f3330aba000 rw-p 00000000 00:00 07ffe4190f000-7ffe41930000 rw-p 00000000 00:00 0 [stack]7ffe419ca000-7ffe419cd000 r--p 00000000 00:00 0 [vvar]7ffe419cd000-7ffe419cf000 r-xp 00000000 00:00 0 [vdso]



# 13

'

&

$

%

3.3 Allocation mémoire

� void* malloc(size_t size)

Renvoie un pointeur vers une zone de size octets

� void* realloc(void* ptr, size_t size)

� Change la taille d’une zone mémoire réservée précédemment par malloc

� void* calloc(size_t nmemb, size_t size)

� Même rôle que malloc, mais avec initialisation de la mémoire à 0

� void *aligned_alloc( size_t alignment, size_t size )

� Même rôle que malloc. L’adresse retournée est un multiple de alignment

� void free(void* ptr)

� Libération une zone mémoire allouée

• Toutes ces fonctions sont des fonctions de la bibliothèque C (qui font dans certains cas des appelssystème).

• L’algorithme de malloc(3) est très performant. Il n’est donc pas nécessaire en général de chercher àl’optimiser.

• Toutefois :

– Lors d’une allocation d’une zone mémoire qui doit être initialisée à 0, on privilégiera calloc(3)(il est plus efficace qu’un malloc(3) suivi d’un memset(3)).

– Si besoin, on peut affiner les paramètres de fonctionnement de malloc(3) avec mallopt(3).– De plus, en affectant __malloc_hook, __realloc_hook et __free_hook, on peut personnaliser le

comportement des routines d’allocation/libération standard. Attention, ces mécanismes peuventposer des problèmes de réentrance.

• Quand on libère une zone avec free, il est vivement conseillé d’affecter NULL au pointeur qu’on avaitsur cette zone. Cela permet un plantage net si, par erreur, dans la suite du programme, on cherche ànouveau à accéder à cette zone (désormais libérée) à l’aide de ce pointeur.

Le programme suivant illustre comment comment cette affectation à NULL permet d’avoir un plantagenet et comment le passage sous debugger permet de retrouver rapidement l’origine de l’erreur.

ilFautMettreNULL.c/* ******************** *//* ilFautMettreNULL .c *//* ******************** */

/* Ce programme illustre l’interet d’affecter a NULL une variable qui *//* contient un pointeur vers une zone non allouee . *//* En effet , il fait une segmentation fault , ce qui permet de reperer *//* qu ’on a commis une operation illicite . Utiliser un debugger permet *//* de comprendre le probleme . *//* *//* 1) Compiler le programme avec l’option -g *//* cc -g -o ilFautMettreNULL ilFautMettreNULL .c *//* 2) ./ ilFautMettreNULL *//* ==> Segmentation fault *//* 3) ulimit -c unlimited *//* 4) ./ ilFautMettreNULL *//* ==> Segmentation fault ( core dumped ) */


Mémoire virtuelle

/* 5) ddd ./ ilFautMettreNULL core */

# include <stdlib.h># include <assert.h>

void h(char *p){*p = ’a’;

}

void g(char *p){h(p);

}

void f(char *p){g(p);

}

int main (){char *p = NULL;

f(p);

p = malloc (1);assert(p != NULL);

f(p);

free(p);p = NULL;

f(p);


# 14

'

&

$

%

3.4 Le point de vue libc

Pour demander de la mémoire à l’OS

� void *sbrk(intptr_t increment)

� augmente la taille du tas de increment octets

� void *mmap(void *addr, size_t length, int prot, int flags, int fd,off_t offset)

� permet de mapper un fichier en mémoire� si flags contient MAP_ANON, ne mappe pas de fichier, mais alloue une zone

remplie avec des 0


Mémoire virtuelle 4 Politiques d’allocation mémoire

# 15

'

&

$

%

4 Politiques d’allocation mémoire

4.2 Non-Uniform Memory Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.2 Politique d’allocation First touch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.4 Politique d’allocation Interleaved . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.4 mbind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

# 16

'

&

$

%

4.1 Non-Uniform Memory Access

� Plusieurs controleurs mémoire interconnectés� Cohérence mémoire entre les processeurs� Accès privilégié au banc mémoire local� Accès possible (avec surcoût) aux bancs mé-

moires distants=⇒ Non-Uniform Memory Access

=⇒ Sur quel banc mémoire allouer les données ?

CPUMem

I/O

CPUMem

I/O

CPU

Mem

CPUMem



# 17

'

&

$

%

4.2 Politique d’allocation First touch

� Politique d’allocation paresseuse par défaut sous Linux

� Allocation d’une page mémoire sur le nœud local lors du premier accès

� Hypothèse : le premier thread à utiliser une page est sans doute celui qui va l’utiliserdans le futur

first_touch.cdouble *array = malloc(sizeof(double )*N);

for(int i=0; i<N; i++) {array[i] = something(i);

}

#pragma omp parallel forfor(int i=0; i<N; i++) {

double value = array[i];/* ... */

}

cpumem

cpu

mem

cpu

cpu

mem

mem

# 18

'

&

$

%

4.3 Politique d’allocation Interleaved

� Les pages sont allouées sur les différents nœuds en round-robin

� Permet d’équilibrer la charge entre les nœuds NUMA

� void *numa_alloc_interleaved(size_t size)

interleaved.cdouble *array =

numa_alloc_interleaved(sizeof(double )*N);

for(int i=0; i<N; i++) {array[i] = something(i);

}



}

cpumem

cpu

mem

cpu

cpu

mem

mem

Il est également possible d’utiliser la fonction set_mempolicy afin d’appliquer une politique d’allocationpour les futures allocations mémoire.



# 19

'

&

$

%

4.4 mbind

� long mbind(void *addr, unsigned long len, int mode,

const unsigned long *nodemask, unsigned long maxnode,

unsigned flags)

� Place un ensemble de pages mémoire sur un/des nœuds NUMA

=⇒ permet le placement manuel des pages mémoire

manual.cdouble *array = malloc(sizeof(double )*N);mbind(&array [0], N/4* sizeof(double),

MPOL_BIND , &nodemask , maxnode ,MPOL_MF_MOVE );



}

cpumem

cpu

mem

cpu

cpu

mem

mem


Architecture

François Trahay


2019–2020

87

Architecture 1 Introduction

# 2

'

&

$

%

Plan du document

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Processeur séquentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .63 Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Parallel Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Hiérarchie mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

# 3

'

&

$

%

1 Introduction

Pourquoi ce cours ?

� Comprendre ce qui se passe dans la partie “hardware” de la pile d’exécution

� Pour écrire des programmes adaptés aux machines modernes

Dans les faits, le compilateur se débrouille généralement pour générer un binaire qui permette d’exploitertoutes les capacités du processeur. Mais le compilateur échoue parfois et génère un code non optimisé. Ilfaut donc être capable de détecter le problème, et être capable d’écrire un code que le compilateur sauraoptimiser.


Architecture

# 4

'

&

$

%

1.1 Loi de Moore

1965 - 2005

� Loi de Moore (1965) : le nombre de transistors des micro processeurs double tousles deux ans

� La finesse de gravure du processeur diminue

� La fréquence d’horloge augmente

=⇒ Augmentation des performances du processeur

Depuis 2005

� La finesse de gravure continue de diminuer (mais moins vite)

� La fréquence d’horloge n’augmente plus� Dissipation thermique dépend de la fréquence, du nombre de transistors, de la

taille des transistors� Si on diminue la taille des transistors, il faut réduire la fréquence

# 5

'

&

$

%

2 Processeur séquentiel

� Une instruction nécessite N étapes� Fetch : chargement de l’instruction depuis la mémoire� Decode : identification de l’instruction� Execute : exécution de l’instruction� Writeback : stockage du résultat

� Chaque étape est traitée par un circuit du processeur

� La plupart des circuits ne sont pas utilisés à chaque étape

→ Une instruction est exécutée tous les N cycles

instructions

cycles d'horloge

Fetch

Decode

Execute

Writeback

Le nombre d’étapes nécessaires à l’exécution d’une instruction dépend du type de processeur (Pentium4 : 31 étapes, Intel Haswell : 14-19 étapes, ARM9 : 5 étapes, etc.)


Architecture 3 Pipeline

# 6

'

&

$

%

3 Pipeline

� Pipeline d’instructions

� À chaque étape, plusieurs circuits sont utilisés

→ Une instruction est exécutée à chaque cycle

instructions

Fetch

Decode

Execute

Writeback

cycles d'horloge

Figure 1 : Exécution d’instructions sur un processeur avec pipeline

# 7

'

&

$

%

3.1 Micro architecture d’un pipeline

� Chaque étape du pipeline est implémenté par un ensemble de portes logiques

� Étage Execute : un sous-circuit par type d’opération (unité fonctionnelle)

fetch decode

int

float

branch

mem

writeback

Figure 2 : Micro-architecture d’un pipeline


3 Pipeline 3.2 Processeurs superscalaires

# 8

'

&

$

%

3.2 Processeurs superscalaires

� Utilisation des différentes unités fonc-tionnelles simultanément

=⇒ plusieurs instructions exécutées simulta-nément !

� Nécessité de charger et décoder plusieursinstructions simultanément fetch

int

float

writeback

writeback

test branch

mem writeback

decode &dispatch

Figure 3 : Micro-architecture d’un pro-cesseur superscalaire

# 9

'

&

$

%

3.2.1 Processeurs superscalaires

instructions

Fetch

Decode

Execute

Writeback

cycles d'horloge



# 10

'

&

$

%

3.2.2 Dépendance entre instructions

Limitations du superscalaire :

� Il ne doit pas y avoir de dépendance entre les instructions exécutées simultanément.� Exemple d’instructions non parallélisables

a = b * c;d = a + 1;

� Degré de parallélisme des instructions : Instruction Level Parallelism (ILP)

� Les instructions exécutées en parallèles doivent utiliser des unités fonctionnellesdifférentes

# 11

'

&

$

%

3.3 Gestion des branchements� Comment remplir le pipeline quand les instructions contiennent des branchements

conditionnels ?cmp a, 7 ; a > 7 ?ble L1mov c, b ; b = cbr L2

L1: mov d, b ; b = dL2: ...

� En cas de mauvais choix : il faut “vider” le pipeline=⇒ perte de temps

instructions

cycles d'horloge

cmp a,7ble L1

mov d,b

mov c,b

?

Fetch

Decode

Execute

Writeback

Le coût d’un mauvais choix lors du chargement d’une branche dépend de la profondeur du pipeline : plusle pipeline est long, plus il faut vider d’étapes (et donc attendre avant d’exécuter une instruction). Pour cetteraison (entre autres), la profondeur du pipeline dans un processeur est limitée.



# 12

'

&

$

%

3.4 Prédiction de branchement

� Le processeur met en œuvre un algorithme de prédiction

� Idée générale :� Pour chaque branchement, on se rappelle des résultats précédents

0x12 loop:...

0x50 inc eax0x54 cmpl eax, 100000x5A jl loop0x5C end_loop:

...

addr branch history

0x23 0011

0x42 1000

0x5A 1111

0x7E 0000

Les algorithmes de prédiction de branchement implémentés dans les processeurs modernes sont aujour-d’hui très évolués et atteignent une efficacité supérieure à 98 % (sur la suite de benchmarks SPEC89).

Pour connaître le nombre de bonnes/mauvaises prédictions, on peut consulter les compteurs matérielsdu processeur. Avec la bibliothèque PAPI 1, les compteurs PAPI_BR_PRC et PAPI_BR_MSP donnent le nombrede branchements correctement et incorrectement prédits.

# 13

'

&

$

%

3.5 Instructions vectorielles

� De nombreuses applications fonctionnent en mode Data Parallelism

� Single Instruction, Multiple Data (SIMD) : une même opération appliquée à unensemble de donnéesfor(i=0; i<size; i++) {

C[i] = A[i] * B[i];}

� Exemple : traitement d’image, scientific computing

� Utilisation d’instructions vectorielles (MMX, SSE, AVX, ...)� Instructions spécifiques à un type de processeurfor(i=0; i<size; i+= 8) {

*pC = _mm_mul_ps(*pA, *pB);pA++; pB++; pC++;

}

Les instructions vectorielles ont été démocratisées à la fin des années 1990 avec les jeux d’instructionsMMX (Intel) et 3DNow ! (AMD) permettant de travailler sur 64 bits (par exemple pour faire 2 opérations 32bits en simultané). Depuis, chaque génération de processeurs x86 apporte son extension au jeu d’instructions :SSE2, SSSE3 (128 bits), SSE4, AVX, AVX2 (256 bits), AVX512 (512 bits). Les autres types de processeursfournissent également des jeux d’instructions vectorielles (par exemple NEON [128 bits] sur ARM).

Les jeux d’instructions vectorielles sont spécifiques à certains processeurs. Le fichier /proc/cpuinfo

1. http ://icl.cs.utk.edu/projects/papi/


Architecture

contient (entre autres) les jeux d’instructions disponibles sur le processeur d’une machine. Par exemple, surun Intel Core i7 :

$ cat /proc/cpuinfoprocessor : 0vendor_id : GenuineIntelcpu family : 6model : 69model name : Intel(R) Core(TM) i7-4600U CPU @ 2.10GHzstepping : 1microcode : 0x1dcpu MHz : 1484.683cache size : 4096 KBphysical id : 0siblings : 4core id : 0cpu cores : 2apicid : 0initial apicid : 0fpu : yesfpu_exception : yescpuid level : 13wp : yesflags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmovpat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nxpdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good noplxtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcidsse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avxf16c rdrand lahf_lm abm ida arat epb pln pts dtherm tpr_shadow vnmiflexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 ermsinvpcid xsaveoptbugs :bogomips : 5387.82clflush size : 64cache_alignment : 64address sizes : 39 bits physical, 48 bits virtualpower management:[...]

Le champs flags contient la liste de toutes les capabilities du processeur, notamment les jeux d’instruc-tions disponibles : mmx, sse, sse2, ssse3, sse4_1, sse4_2, avx2.

L’utilisation de ces jeux d’instructions vectorielles peut se faire en programmant directement en assem-bleur ou en exploitant les intrinsics que fournissent les compilateurs. Toutefois, devant le nombre de jeuxd’instructions disponibles et l’évolutilité des architectures des processeurs, il est recommandé de laisser lecompilateur optimiser lui-même le code, par exemple en utilisant l’option -O3.


Architecture 4 Parallel Processing

# 14

'

&

$

%

4 Parallel Processing

4.2 Hyperthreading / SMT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164.2 Processeurs multi-cœurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164.4 Architectures SMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184.4 Architectures NUMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

# 15

'

&

$

%

4.1 Hyperthreading / SMT

� Problème du superscalaire/vectoriel :� Il faut que l’application ait suffisamment de parallélisme à exploiter� Il y a d’autres applications qui attendent d’avoir le CPU

� Simultaneous Multi-Threading (SMT, ou Hyperthreading) :� Modifier un processeur superscalaire pour l’exécution de plusieurs threads� Duplication de certains circuits� Mise en commun de certains circuits

ALU (int)

FPU (float)

ALU (int)

fetchdecode & dispatch

Mem/Branch

Mem/Branch

writeback

Thread B

Thread A

Shared

Le SMT est un moyen peu cher d’augmenter les performances d’un processeur : en dupliquant les “petits”circuits (ALU, registres, etc.) et en mettant en commun les “gros” circuits (FPU, prédiction de branchements,caches), on peut exécuter plusieurs threads simultanément. Le surcoût en terme de fabrication est léger etle gain en performances peut être grand.

Comme le dispatcher ordonnance les instructions de plusieurs threads, une erreur du prédicteur de bran-chement devient moins grave puisque pendant que le pipeline du thread fautif se renouvelle, un autre threadpeut s’exécuter.

Le gain de performance lorsque plusieurs threads s’exécutent n’est pas systématique puisque certainscircuits restent partagés (par exemple, le FPU).


Architecture 4 Parallel Processing

# 16

'

&

$

%

4.2 Processeurs multi-cœurs

� Scalabilité du SMT limitée� dispatcher partagé� FPU partagé

→ Duplication de tous les circuits

ALU (int)

FPU (float)

ALU (int)

fetchdecode &dispatch

Mem/Branch

Mem/Branch

writeback

Core B

Core A

fetchdecode & dispatch

writeback

FPU (float)

Il est bien sûr possible de combiner multi-cœur avec SMT. La plupart des fondeurs produisent desprocesseurs multi-cœur SMT : Intel Core i7 (4 cœurs x 2 threads), SPARC T3 Niagara-3 (16 cœurs x 8threads), IBM POWER 7 (8 cœurs x 4 threads).

# 17

'

&

$

%

4.3 Architectures SMP

� Symmetric Multi-Processing

� Assemblage de processeurs sur une carte mère

� Les processeurs se partagent le bus système

� Les processeurs se partagent la mémoire

� Problème de scalabilité : contention pour l’accès au bus

CPU CPU

Mem

System bus I/O


Architecture 5 Hiérarchie mémoire

# 18

'

&

$

%

4.4 Architectures NUMA

� Nœuds NUMA connectés par un réseau rapide

� Cohérence mémoire entre les processeurs

� Accès privilégié au banc mémoire local

� Accès possible (avec un surcoût) aux bancs mémoire situés sur les autres nœuds

→ Non-Uniform Memory Architecture

CPUMem

I/O

CPUMem

I/O

CPU

Mem

CPUMem

Les premières machines NUMA (dans les années 1990) étaient simplement des ensembles de machinesreliées par un réseau propriétaire chargé de gérer les transferts mémoire. Depuis 2003, certaines cartes mèrespermettent de relier plusieurs processeurs Opteron (AMD) reliés par un lien HyperTransport. Intel a par lasuite développé une technologie similaire (Quick Path Interconnect, QPI) pour relier ses processeurs Nehalem(sortis en 2007).

# 19

'

&

$

%

5 Hiérarchie mémoire



# 20

'

&

$

%

5.1 Enjeux

� Jusqu’en 2005 : augmentation des perfs des CPUs : 55%/an

� Depuis 2005 : augmentation du nombre de cœur par processeur

� Augmentation des perfs de la mémoire : 10%/an

� Ce sont les accès mémoire qui sont coûteux : Memory Wall

� Il faut des mécanismes pour améliorer les performances de la mémoire

Jusqu’aux années 1990, le goulet d’étranglement était le processeur. Du point de vue logiciel, on cherchaitalors à minimiser le nombre d’instructions à exécuter.

Avec l’augmentation des performances des processeurs, la pression est maintenant sur la mémoire. Côtélogiciel, on cherche donc à minimiser le nombre d’accès à la mémoire. Cette pression sur la mémoire estexacerbée par le développement des processeurs multi-cœurs.

Par exemple, un processeur Intel Core i7 peut engendrer jusqu’à 2 accès mémoire par cycle d’horloge. Unprocesseur à 8 cœurs hyper-threadés (donc 16 threads) tournant à 3.0 Ghz 1 peut donc générer 2×16.0×109 =96 milliards de références mémoire par seconde. Si l’on considère des accès à des données de 64 bits, celareprésente 3072 Go/s (3.072 To/s). À ces accès aux données, il faut ajouter les accès aux instructions (jusqu’à128 bits par instruction). On arrive donc à 6144 Go/s (donc 6.144 To/s !) de débit maximum.

À titre de comparaison, en 2016, une barette de mémoire RAM (DDR4) a un débit maximum de l’ordrede 20 Go/s. Il est donc nécessaire de mettre en place des mécanismes pour éviter que le processeur ne passeson temps à attendre la mémoire.

1. Exemple : un Intel Core i7-5960X sorti en 2014



# 21

'

&

$

%

5.2 Caches� Accès à la mémoire (RAM) très coûteux (env. 60 ns – env. 180 cycles)

� Pour accélérer les accès mémoire, utilisation de mémoire cache rapide :� Cache L1 : très petite capacité (typiquement : 64 Ko), très rapide (env. 4 cycles)� Cache L2 : petite capacité (typiquement : 256 Ko), rapide (env. 10 cycles)� Cache L3 : grande capacité (typiquement : entre 4Mo et 20Mo), lent (env. 40

cycles)

� Accès au disque dur (SWAP) très coûteux : env. 40 ms (150 µs sur un disque SSD)

Pour visualiser la hiérarchie mémoire d’une machine, vous pouvez utiliser l’outil lstopo fourni par labibliothèque hwloc.


5 Hiérarchie mémoire 5.3 Memory Management Unit (MMU)

# 22

'

&

$

%

5.3 Memory Management Unit (MMU)

� Traduit les adresses mémoire virtuellesen adresses physiques

� Cherche dans le TLB (Translation Loo-kaside Buffer), puis dans la table despages

� Une fois l’adresse physique trouvée, de-mande les données au cache/mémoire

Data / Instructionregisters

CPU MMU

TLB

cache RAMdisk

Pagetable

v addr.

p addr.

# 23

'

&

$

%

5.3.1 Fully-associative caches

� Cache = tableau à N entrées� À chaque référence, recherche de Tag dans le

tableau� Si trouvé (cache hit) et Valid=1 : accès à la

ligne de cache Data� Sinon (cache miss) : accès RAM

� Problème : nécessite de parcourir tout le tableau→ Principalement utilisé pour les petits caches

(ex : TLB)

Adresse

Tag Offset

Tag DataValid

La taille d’une ligne de cache dépend du processeur (généralement entre 32 et 128 octets). On peutretrouver cette information dans /proc/cpuinfo :

$ cat /proc/cpuinfo |grep cache_alignmentcache_alignment : 64


5 Hiérarchie mémoire 5.3 Memory Management Unit (MMU)

# 24

'

&

$

%

5.3.2 Direct-mapped caches

� Utilisation des bits de poids faible de l’adressepour trouver l’index de l’entrée dans le cache

� Comparaison du Tag (bits de poids fort) del’adresse et de l’entrée.

→ Accès direct à la ligne de cache� Attention : risque de collision� exemple : 0x12345678 et 0xbff72678

Adresse

Tag Offset

Tag DataValid

31 30 ... 13 12 11 2 1 0...

10

Index012 ...

102110221023

=20 32

20Index

# 25

'

&

$

%

5.3.3 Set-associative caches

� Index pour accéder à un set de K lignes decache

� Recherche du Tag parmi les adresses du set→ Cache associatif K-voies (K-way associative

cache)

Adresse

Tag Offset

Tag DataValid

31 30 ... 13 12 11 2 1 0...

10

Index

0

20Index

1

...

n-1

n

0011 ... 1010

0011 ... 1010

1001 ... 0110

32

De nos jours, les caches (L1, L2 et L3) sont généralement associatifs à 4 (ARM Cortex A9 par exemple),8 (Intel Sandy Bridge), voire 16 (AMD Opteron Magny-Cours) voies.


Architecture

# 26

'

&

$

%

5.3.4 Cohérence de cache

� Que faire si 2 threads accèdent à une même zone mémoire ?� En lecture : réplication dans les caches locaux� En écriture : nécessité d’invalider les données dans les autres cachesI Cache snooping : le cache envoie un message qui invalide les autres caches

Pour détailler un peu plus ce cours, nous vous conseillons cette page web : Modern microprocessors – A90 minutes guide ! (http://www.lighterra.com/papers/modernmicroprocessors/).

Pour avoir (beaucoup) plus de détails, tournez-vous vers les livres [?] et [?] qui décrivent en détaill’architecture d’un ordinateur. Si vous cherchez à connaître le fonctionnement très en détail d’un pointprécis, lisez [?].

Bibliographie du chapitre


Entrées/sorties

François Trahay


2019–2020

103

Entrées/sorties

# 2

'

&

$

%

Plan du document

2 IO bufferisée / non bufferisée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Primitives Unix d’entrée-sortie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Entrées-sorties et concurrence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .94 Améliorer les performances des entrées-sorties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Lors de ce cours, nous parlerons surtout de fichiers, car c’est l’exemple d’entrées-sorties le plus facilementmanipulable. Toutefois, notez bien que le contenu des 3 premières sections s’applique aux entrées-sortiesautres que les fichiers.

Rappel sur les fichiers (notions vues en première année) :

• Un fichier est une suite d’octets contigus stockés dans un support (par exemple, un disque) sous unnom (le « nom du fichier »).

• On distingue les fichiers :

– texte : contenant des octets affichables à l’écran. Ce type de fichiers est constitué de lignes iden-tifiées par le caractère de fin de ligne (sous Unix, caractère de code ASCII 10 alors que sousWindows, caractère de code ASCII 10 suivi d’un caractère de code ASCII 13) ;

– binaire : contenant des octets non affichables à l’écran.

Sous Unix, les commandes hexdump -C nomFichier, bless nomFichier ou xxd nomFichier per-mettent de visualiser le contenu d’un fichier de manière précise. Utilisez-les pour 1) com-parer le contenu de helloWorldUnix.c et helloWorldWindows.c, 2) voir que le fichierdefault_names_fichierIssuDuTP10DuModuleCSC4103.txt n’est pas tout à fait un fichier texte (et,annexement, voir aussi concrètement comment sont stockés les caractères accentués dans un fichier).

• Quand on « ouvre » un fichier, le système d’exploitation fournit une notion de position courante(appelée parfois offset dans la suite de ce cours) de lecture/écriture.

– Cette position courante détermine le rang de l’octet dans le fichier à partir duquel les primitivessystème lisent ou bien écrivent des octets dans le fichier.

– Cet offset avance à chaque fois qu’on effectue une lecture ou une écriture.– Le système d’exploitation met à disposition de l’utilisateur des primitives pour changer explicite-

ment cette position courante (sans lire ou écrire des octets).

• La « fin d’un fichier » correspond à l’endroit situé derrière le dernier octet du fichier. Quand on està la fin du fichier, on ne peut pas lire d’octets. En revanche, on peut écrire des octets (selon le modedans lequel on a ouvert le fichier).

• Il existe 3 modes d’accès à un fichier :

– Séquentiel : les octets sont lus les uns à la suite des autres à partir du début du fichier.


Entrées/sorties 2 Primitives Unix d’entrée-sortie

– Direct : on peut positionne l’offset sans avoir besoin de lire les octets situés avant l’offset.– Séquentiel indexé : le fichier contient des enregistrements, chaque enregistrement étant identifié

par une clé (unique ou non). À l’aide de la clé, on peut se positionner au début d’un enregistrement.On peut également lire les enregistrements dans l’ordre définis par leur clé.

Le système Linux et la librairie C offrent les modes d’accès séquentiels et directs. Pour un mode d’accèsséquentiel indexé, il faut s’appuyer sur une librairie (Unix NDBM, GDBM, Oracle Berkeley DB. . .).

# 3

'

&

$

%

1 IO bufferisée / non bufferisée

� Entrées/sorties bufferisées� Les écritures sont groupées dans un buffer qui est écrit sur disque de temps en

temps� Lors d’une lecture, un bloc de données est chargé depuis le disque vers un buffer→ une I/O bufferisée 6= une opération sur le disque� eg. fopen, fread, fscanf, fwrite, fprintf, etc.� Flux de données identifié par un pointeur opaque FILE*

� Entrées/sorties non bufferisées� une I/O non bufferisée = une opération sur le disque†� eg. open, read, write, etc.� Fichier ouvert identifié par un file descriptor de type int

† Pour être exact, une I/O “non bufferisée” génère un appel système. L’OS peut alors décider de mettreen cache les données ou non.

# 4

'

&

$

%

2 Primitives Unix d’entrée-sortie

2.1 Ouverture/fermeture de fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Lecture sur descripteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3 Écriture sur descripteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.1 Duplication de descripteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9



# 5

'

&

$

%

2.1 Ouverture/fermeture de fichier� int open(const char *path, int flags, mode_t mode) : retour = f_id

flags peut prendre l’une des valeurs suivantes :� O_RDONLY : lecture seulement� O_WRONLY : écriture seulement� O_RDWR : écriture et lecture

Associée à :� O_APPEND : écritures en fin de fichier� O_TRUNC : remise à vide du fichier� O_CREAT : création si le fichier n’existe pas. Les droits sont (mode & ∼ umask)� O_SYNC : ouverture du fichier en écriture synchronisée� O_NONBLOCK (ou O_NDELAY) : open et les opérations ultérieures faites sur le

descripteur ne pourront pas se bloquer.

� int close(int desc)

À propos de l’option O_SYNC dans open :

• Pour gagner en performance, par défaut, lors d’une opération d’écriture, le système d’exploitationn’écrit pas physiquement les octets sur le disque (ils sont gardés dans des caches du noyau en attented’un moment considéré comme favorable par le système pour réaliser l’écriture sur disque)

• De ce fait, en cas d’arrêt brutal de la machine (exemple : coupure de courant) :

– des données qu’on croyait avoir écrites sur disque peuvent être perdues car elles étaient en fait enmémoire ;

– il y aussi risque d’incohérence sur les données qu’on trouve dans le fichier.

• Solutions pour synchroniser des données de fichier en mémoire avec le disque :

– synchronisation implicite (i.e. à chaque écriture) : ajout de l’option O_SYNC au moment du open ;– synchronisation explicite (i.e. sur décision de l’application) via la primitive

int fsync(int fd)

Notez qu’on peut aussi créer un fichier à l’aide de la primitive creat :

int creat(const char *path, mode_t mode) : retour = f_id

qui est équivalent à l’appel suivant de open :

open(path, O_WRONLY|O_CREAT|O_TRUNC, mode).



# 6

'

&

$

%

2.2 Lecture sur descripteur

� ssize_t read(int fd, void *buf, size_t count) : retour = nombre d’octetslus� Au retour de read, la zone buf est modifiée avec le résultat de la lecture� Dans le cas d’un fichier, le nombre d’octets lus peut ne pas être égal à count :I On se trouve à la fin du fichierI On a fait une lecture non bloquante et les données étaient verrouillées de

manière exclusive

Dans le cas où la fonction read est utilisée sur un descripteur autre qu’un fichier (tube, socket), le faitque le nombre d’octets lus peut ne pas être égal à count peut avoir d’autres significations :

• pour un tube de communication (cf. chapitre Communications Inter-processus), le correspondant afermé son extrémité du tube.

• pour une socket (cf. cours NET4103), le protocole réseau utilise des paquets de données de tailleinférieure à celle qui est réclamée.

# 7

'

&

$

%

2.3 Écriture sur descripteur

� ssize_t write(int fd, const void *buf, size_t count) : retour = nombred’octets écrits� Dans le cas d’un fichier, le retour (sans erreur) de l’écriture signifie que :I Les octets ont été écrits dans les caches du noyau si pas de O_SYNC au

moment du openI Les octets ont été écrits sur disque si O_SYNC au moment du open.� Dans le cas d’un fichier, si le nombre d’octets écrits est différent de count, cela

signifie une erreur (disque plein, par exemple)

L’écriture sur disque est atomique : si deux processus P1 et P2 écrivent simultanément dans le mêmefichier au même endroit, lorsque les deux processus auront fini leur écriture, on trouvera à cet endroit :

• soit l’écriture faite par P1,



• soit l’écriture faite par P2,

• mais jamais un mélange des écritures faites par P1 et P2.

Notez que quand le fichier est ouvert avec l’option O_APPEND, si P1 et P2 écrivent simultanément (à la findu fichier, puisqu’on a l’option O_APPEND), lorsque les deux processus auront fini leur écriture, on trouveraen fin de fichier :

• soit l’écriture faite par P1 suivie de celle faite par P2,

• soit l’écriture faite par P2 suivie de celle faite par P1.

Aucune écriture n’est donc perdue ! Attention, cette écriture simultanée en fin de fichier n’est pas équivalenteà deux processus exécutant simultanément les opérations suivantes :

lseek(fd,0,SEEK_END); /* Fixe la position courante à la fin du fichier */write(fd,data,taille);

En effet, dans ce dernier cas, l’une des écritures risque d’être écrasée par l’autre.

Le fichier copier.c de la page suivante illustre l’utilisation de open, read, write et close.

copier.c/* ********** *//* copier .c *//* ********** */# include <stdlib.h># include <unistd.h># include <sys/stat.h># include <fcntl.h># include <string.h># include <stdio.h>

# define USAGE "USAGE = copier nomSource nomDest\n"# define ERRECRIT "Erreur d’ecriture (disque plein ?)\n"

int source , dest;int buf;int nbCarLu , nbCarEcrit;

int main(int argc , char *argv []) {if (argc != 3) {

write(STDERR_FILENO , USAGE , strlen(USAGE ));return EXIT_FAILURE;

}source = open(argv[1], O_RDONLY );if (source < 0) {

perror(argv [1]);return EXIT_FAILURE;

}dest = open(argv[2],

O_WRONLY|O_CREAT|O_TRUNC ,S_IRWXU|S_IRWXG|S_IRWXO );

if (dest < 0) {perror(argv [2]);return EXIT_FAILURE;

}while (( nbCarLu = read(source , (void *)&buf , sizeof(buf))) > 0) {

nbCarEcrit = write(dest , (void *)&buf , nbCarLu );if (nbCarEcrit <= 0) {

if (nbCarEcrit == 0) {write(STDERR_FILENO , ERRECRIT , strlen(ERRECRIT ));

}else {

perror("write");}return EXIT_FAILURE;

}}if (nbCarLu < 0) {

perror("read");return EXIT_FAILURE;

}if (close(source) < 0) {


}if (close(dest) < 0) {


Entrées/sorties 3 Entrées-sorties et concurrence


}return EXIT_SUCCESS;

}

Cette opération de recopie du contenu d’un fichier vers un autre descripteur est une opération fré-quemment réalisée dans les serveurs Web. En effet, ces serveurs doivent notamment envoyer le contenude fichiers aux clients qui leur en ont fait la demande. C’est pourquoi le système Linux offre la primitivesendfile (ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count)). Elle permetde lire count octets de in_fd pour les écrire sur out_fd (qui doit correspondre à une socket). sendfile estplus performant que la combinaison read/write.

La fonction fallocate est la version spécifique Linux de la fonction (portable) posix_fallocate.

# 8

'

&

$

%

2.4 Duplication de descripteur

� Mécanisme principalement utilisé pour réaliser des redirections des trois fichiersd’entrée-sorties standard.

� int dup(int fdACloner) : retour = nouveauFd

associe le plus petit descripteur disponible du processus appelant à la même entréedans la table des fichiers ouverts que le descripteur fdACloner

� int dup2(int fdACloner, int fdClone)

force le descripteur fdClone à devenir un synonyme du descripteur fdACloner. Sile descripteur fdClone n’est pas disponible, le système réalise au préalable uneopération de fermeture close(fdClone)

# 9

'

&

$

%

3 Entrées-sorties et concurrence

3.1 Verrouillage de fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104.1 Manipulation de l’offset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13



# 10

'

&

$

%

3.1 Verrouillage de fichier

� struct flock { short l_type; short l_whence;off_t l_start; off_t l_len; };

� int fcntl(int fd, F_SETLK, struct flock*lock);

� Les verrous sont attachés à un inode. Donc, l’effet d’un verrou sur un fichier estvisible au travers de tous les descripteurs (et donc tous les fichiers ouverts)correspondant à cet inode

� Un verrou est la propriété d’un processus : ce processus est le seul habilité à lemodifier ou à l’enlever

� Les verrous ont une portée de [entier1 : entier2] ou [entier :∞]

� Les verrous ont un type :� F_RDLCK : autorise les accès concurrents en lecture� F_WRLCK : accès exclusif

Le fichier vExcl.c illustre la pose d’un verrou exclusif :

vExcl.c/* ********* *//* vExcl .c *//* ********* */# include <stdlib.h># include <unistd.h># include <sys/stat.h># include <fcntl.h># include <stdio.h>int main (){

int fd;struct flock verrou;

fd = open("/tmp/ficTest",O_RDWR|O_CREAT , S_IRWXU|S_IRWXG|S_IRWXO );if (fd < 0) {

perror("open");exit(EXIT_FAILURE );

}

/* Verrou exclusif sur le 15 eme caractere */verrou.l_type = F_WRLCK;verrou.l_whence = SEEK_SET;verrou.l_start = 15;verrou.l_len = 1;/* A cause du parametre F_SETLKW , on se bloque sur le fcntl si jamais *//* le verrou ne peut pas etre pris */printf("tentative de pose de verrou (exclusif) par processus %d...\n",

getpid ());if (fcntl(fd, F_SETLKW , &verrou) < 0){

perror("Pose verrou");exit(EXIT_FAILURE );

}printf("... Verrou (exclusif) pose par processus %d\n", getpid ());

/* Ici on pourrait faire le traitement qui necessitait d’etre protege *//* par le verrou */sleep (10);

/* Liberation du verrou */printf("Relachement verrou par processus %d...\n", getpid ());verrou.l_type = F_UNLCK;verrou.l_whence = SEEK_SET;verrou.l_start = 15;verrou.l_len = 1;if (fcntl(fd, F_SETLK , &verrou) < 0){

perror("Relachement verrou");exit(EXIT_FAILURE );

}



printf("...OK\n");


Le fichier vPart.c illustre la pose d’un verrou partagé :

vPart.c/* ********* *//* vPart .c *//* ********* */# include <stdlib.h># include <unistd.h># include <sys/stat.h># include <fcntl.h># include <stdio.h>int main (){

int fd;struct flock verrou;

fd = open("/tmp/ficTest",O_RDWR|O_CREAT , S_IRWXU|S_IRWXG|S_IRWXO );if (fd < 0) {

perror("open");exit(EXIT_FAILURE );

}

/* Verrou partage sur le 15e caractere */verrou.l_type = F_RDLCK;verrou.l_whence = SEEK_SET;verrou.l_start = 15;verrou.l_len = 1;/* A cause du parametre F_SETLKW , on se bloque sur le fcntl si jamais *//* le verrour ne peut pas etre pris */printf("tentative de pose de verrou (partage) par processus %d...\n",

getpid ());if (fcntl(fd, F_SETLKW , &verrou) < 0){

perror("Pose verrou");exit(EXIT_FAILURE );

}printf("... Verrou (partage) pose par %d\n", getpid ());

/* Ici on pourrait faire le traitement qui necessitait d’etre protege *//* par le verrou */sleep (10);

/* Liberation du verrou */printf("Relachement verrou par processus %d...\n", getpid ());verrou.l_type = F_UNLCK;verrou.l_whence = SEEK_SET;verrou.l_start = 15;verrou.l_len = 1;if (fcntl(fd, F_SETLK , &verrou) < 0){

perror("Relachement verrou");exit(EXIT_FAILURE );

}printf("...OK\n");


• Si on exécute vExcl en premier, un autre vExcl ou un vPart doivent attendre avant de pouvoir poserleur verrou.

• Si on exécute vPart en premier, un autre vPart peut poser le verrou (partagé). En revanche, un vExcldoit attendre avant de pouvoir poser son verrou.

• Notez qu’on peut avoir une famine de vExcl :

– on démarre un 1er vPart.– on démarre vExcl : il se met en attente.– on démarre un 2e vPart. Le 1er vPart se termine. Mais comme le 2è vPart est en train de s’exécuter,

vExcl attend encore.– on démarre un 3e vPart. Le 2e vPart se termine. Mais comme le 3e vPart est en train de s’exécuter,

vExcl attend encore.


Entrées/sorties 4 Améliorer les performances des entrées-sorties

– on constate que tant que des vPart démarrent alors que le vPart précédent n’a pas fini de s’exé-cuter, vExcl doit attendre : il peut donc y avoir une famine de vExcl.

Pour empêcher cette famine, il faut ajouter une exclusion mutuelle.

# 11

'

&

$

%

3.2 Manipulation de l’offset

� off_t lseek(int fd, off_t unOffset, int origine) : retour = nouvelemplacement

permet de manipuler l’offset du fichier

� Attention ! Race condition si plusieurs threads manipulent le fichier

� Solutions :� Manipulation du fichier en exclusion mutuelle� Utilisation de pread ou pwrite au lieu de lseek+read ou lseek+write

# 12

'

&

$

%

4 Améliorer les performances des entrées-sorties

4.1 Conseil au noyau pour les lectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.3 IO asynchrones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .154.3 mmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15



# 13

'

&

$

%

4.1 Conseil au noyau pour les lectures

� int posix_fadvise(int fd, off_t offset, off_t len, int advice)

� exemples de conseils : POSIX_FADV_SEQUENTIAL, POSIX_FADV_RANDOM,POSIX_FADV_WILLNEED

� retour = 0 si OK, numéro d’erreur sinon� permet d’annoncer au noyau la manière dont on va accéder à un fichier, ce qui

permet au noyau de faire des optimisations appropriées

Depuis janvier 2011, on sait que cette fonction est utilisée dans les prochaines versions de Fi-refox pour gagner 40% à 50% de temps au moment du démarrage en chargeant plus efficace-ment les deux librairies de l’interface graphique xul.dll et mozjs.dll (plus d’informations icihttps://bugzilla.mozilla.org/show_bug.cgi?id=627591).

# 14

'

&

$

%

4.2 IO asynchrones

� int aio_read(struct aiocb *aiocbp)

� int aio_write(struct aiocb *aiocbp)

� Démarre une opération de lecture/écriture asynchrone

� Retourne immédiatement

� int aio_suspend(const struct aiocb * const aiocb_list[],

int nitems, const struct timespec *timeout)

� Attend la fin d’une opération asynchrone

� int aio_error(const struct aiocb *aiocbp)

� Teste la fin d’une opération asynchrone

Pour plus d’informations concernant les IO asynchrones, référez-vous à la documentation (man 7 aio).L’implémentation actuelle d’AIO Posix est fournie en user-land par la libc et peut poser des problèmes

de scalabilité. Une autre solution consiste à utiliser l’interface d’I/O Asynchrone fournie par le noyau Linux(voir les appels systèmes io_submit, io_setup, etc.), ou la bibliothèque libaio qui fournit une surcoucheaux appels systèmes de Linux.



# 15

'

&

$

%

4.3 mmap

� void *mmap(void *addr, size_t length, int prot, int flags, int fd,off_t offset)

� “mappe” un fichier en mémoire� les accès mémoires à la zone mémoire sont transformés en opérations sur le

disque

� int munmap(void *addr, size_t length)

� “détache” la zone mémoire

Pour s’assurer que les accés mémoires ont bien été répercutés sur le disque, on peut utiliser la fonctionmsync.


Systèmes de fichier

Gaël Thomas


2019–2020

115

Systèmes de fichier 1 Périphérique et pilote de périphérique

# 2

'

&

$

%

Plan du document

1 Périphérique et pilote de périphérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Le cache d’entrées/sorties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Le journal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 Partitions et systèmes de fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 Le système de fichiers UFS/xv6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 La pile d’entrée/sortie de xv6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 Ce qu’il faut retenir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

# 3

'

&

$

%

1 Périphérique et pilote de périphérique

1.1 Périphérique et pilote de périphérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Les périphériques dans les UNIX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3 2 types de périphériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.5 Périphériques de type bloc dans xv6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.5 Principe de l’algorithme de iderw . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8



# 4

'

&

$

%

1.1 Périphérique et pilote de périphérique

� Périphérique = composant matériel autre que CPU et mémoire

� Pilote de périphérique = logiciel permettant d’accéder à un périphérique� 1 structure de données donnant l’état du périphérique� 1 fonction d’entrée/sortie permettant d’accéder au périphérique� Le pilote se trouve en général dans le noyau

# 5

'

&

$

%

1.2 Les périphériques dans les UNIX

� Un périphérique est identifié par un nombre appelé dev� Bits de poids forts (major) : numéro de piloteI Par exemple : 8 = pilote disque dur ssd

� Bits de poids faibles (minor) : numéro de périphérique� Par exemple : 0 = disque 1, 1 = disque 1/part 1, 2 = disque 1/part 2

� Le noyau possède une table qui associe un numéro de pilote avec le pilote (fonctiond’accès + état)



# 6

'

&

$

%

1.3 2 types de périphériques

� Périphériques de type « caractère »� Lecture/écriture octet par octet� En général accès via MMIO ou bus d’entrées/sorties→ bloque le CPU pendant l’entrée/sortie� Clavier, imprimante, carte son. . .

� Périphériques de type « bloc »� Lecture/écriture par blocs de données (typiquement 512 octets)� Le périphérique est donc vu comme un tableau de blocs� En général, accès via DMA→ ne bloque pas le CPU pendant l’entrée/sortie� Disque dur, lecteur DVD. . .

# 7

'

&

$

%

1.4 Périphériques de type bloc dans xv6

� Un unique pilote de périphérique de type bloc dans xv6� Gère les disques durs de type IDE� Fonction iderw() dans ide.c

� iderw() prend en paramètre une structure buf (buf.h)� buf.flags :I B_VALID : si faux, demande de lectureI B_DIRTY : si vrai, demande d’écriture� buf.dev/blockno : accès au bloc blockno du disque dev� buf.data : données lues ou écritesI Si lecture, en sortie de iderw, data = données luesI Si écriture, en entrée de iderw, data = données à écrire


Systèmes de fichier 2 Le cache d’entrées/sorties

# 8

'

&

$

%

1.5 Principe de l’algorithme de iderw

� iderw effectue principalement les actions suivantes :� Lancement du DMA (voir séance 5)I De la mémoire vers le disque si demande d’écritureI Du disque vers la mémoire si demande de lecture� Endort le processus avec la fonction sleep (voir séance 4)→ commutation vers un autre processus prêt

� Une fois le transfert terminé� Le disque génère une interruption� L’interruption est traitée par la fonction ideintr

� ideintr appelle wakeup pour réveiller le processus endormi

# 9

'

&

$

%

2 Le cache d’entrées/sorties

2.1 Le cache d’entrée/sortie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3 Principe d’un cache d’entrée/sortie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3 Le buffer cache de xv6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .122.5 Fonctionnement du buffer cache (1/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.5 Fonctionnement du buffer cache (2/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.0 Fonctionnement du buffer cache (3/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16



# 10

'

&

$

%

2.1 Le cache d’entrée/sortie

� Un accès disque est très lent comparé à un accès mémoire� Disque plateau : de l’ordre de la milliseconde� Disque SSD : x10, de l’ordre de la centaine de microsecondes� Disque NVMe : x100, de l’ordre de la microseconde� Mémoire : x100, de l’ordre de la dizaine de nanosecondes

� Cache d’entrées/sorties permet d’améliorer les performances des périphériques detype bloc� Conserve en mémoire les blocs fréquements ou récemments utilisés� Géré par le noyau du système d’exploitation

# 11

'

&

$

%

2.2 Principe d’un cache d’entrée/sortie

� Le système gère un ensemble de buffers en mémoire

� Pour lire un bloc (opération de lecture)� Si le bloc n’est pas encore dans le cache1. Sort un buffer inutilisé du cache2. Copie le contenu du bloc disque vers ce buffer� Sinon, renvoi simplement le buffer associé au bloc

� Pour modifier un bloc (opération d’écriture)1. Lit le bloc (appel de l’opération de lecture)2. Modifie le contenu du buffer en mémoire3. Marque le buffer comme modifié (écrit sur disque plus tard)



# 12

'

&

$

%

2.3 Le buffer cache de xv6

� buffer cache = cache d’entrée/sortie de xv6� Constitué d’un ensemble fini de structures buf� Chaque structure buf est associée à un bloc d’un disque

� Trois états possibles� ! B_VALID : lecture du bloc non terminée → nécessite lecture� B_VALID et ! B_DIRTY : lecture ok et buffer non modifié� B_VALID et B_DIRTY : lecture ok et buffer modifié en mémoire→ nécessite écriture avant de le sortir du cache

→ dans iderw(), ! B_VALID ⇔ lecture et B_DIRTY ⇔ écriture

# 13

'

&

$

%

2.4 Fonctionnement du buffer cache (1/3)

� Les structures buf forment une liste doublement chaînée circulaire, la tête étant lebloc le plus récemment utilisé

� struct buf* bget(uint dev, uint blkno) : renvoie un buffer verrouilléassocié à (dev, blkno)� S’il existe déjà un buffer associé à (dev, blkno)I Incrémente un compteur de référence associé au bufferI Prend un verrou sur le bufferI Renvoie le buffer� SinonI Cherche un buffer avec compteur == 0 et à l’état ! B_DIRTYI Associe ce buffer à (dev, blkno) (+ cpt = 1 et prise de verrou)



# 14

'

&

$

%


� struct buf* bread(uint dev, uint blkno)

� Renvoie un buffer verrouillé à l’état B_VALID� Appel bget()� Si le buffer est à l’état ! B_VALID, appelle iderw()

� void bwrite(struct buf* b)

� Écrit le contenu de b sur disque� Marque le buffer B_DIRTY� Appelle iderw() pour écrire le buffer

# 15

'

&

$

%


� void brelse(struct buf* b)

� Lâche le verrou associé à b

� Diminue le compteur de références� Place le buffer en tête de liste (plus récemment utilisé)


Systèmes de fichier 3 Le journal

# 16

'

&

$

%

3 Le journal

3.2 Opération versus écriture sur disque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2 Problèmes de cohérence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.4 Mauvaises solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.4 Première idée : les transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.6 Deuxième idée : le journal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.6 Troisième idée : le journal parallèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.8 Structure du journal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.8 Principe d’algorithme du journal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.10 Utilisation du journal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.10 Mise en œuvre dans xv6 (1/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.12 Mise en œuvre dans xv6 (2/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.12 Mise en œuvre dans xv6 (3/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

# 17

'

&

$

%

3.1 Opération versus écriture sur disque

� Une opération en écriture d’un processus nécessite souvent plusieurs écrituresde blocs� Création de fichier nécessiteI Allocation d’un nouveau fichierI Ajout du nom dans un répertoire� Ajout de données dans un fichier nécessiteI Écriture de nouveaux blocs sur disqueI Mise à jour de la taille du fichier� Suppression d’un fichier nécessiteI Libération des blocs de données du fichierI Suppression du nom dans le répertoire� ...



# 18

'

&

$

%

3.2 Problèmes de cohérence

� Le système peut crasher n’importe quand→ Incohérence si arrêt au milieu d’une opérationI Un nom dans un répertoire référence un fichier inexistantI Données ajoutées à un fichier mais taille non mise à jourI ...

� Les opérations doivent être propagées dans l’ordre dans lequel elles ont étéexécutées→ Incohérence si propagation dans un ordre aléatoireI Ajout d’un fichier puis suppression =⇒ le fichier n’existe pas à la finI Suppression d’un fichier puis ajout =⇒ le fichier existe à la finI De façon similaire, ajout de données puis troncation (taille à 0)I ...

# 19

'

&

$

%

3.3 Mauvaises solutions

� Pas de cache en écriture (écritures directement propagées)� Très inefficace car chaque écriture devient très (très !) lente

� Réparation en cas de crash� Réparation du système de fichiers lente pour l’utilisateurI exemples : FAT32 sous Windows ou ext2 sous Linux� Réparation n’est pas toujours possible→ crash rend le système de fichiers inutilisable !



# 20

'

&

$

%

3.4 Première idée : les transactions

� Une transaction est un ensemble d’écritures qui est� Soit entièrement exécuté� Soit pas du tout exécuté

� Principe de mise en oeuvre� Une opération (ensemble cohérent d’écritures) == une transaction� Les écritures d’une transaction sont d’abord écrite sur disque dans une zone “en

attente”� Une fois l’opération terminée, la zone “en attente” est marquée comme valide

(on dit que la transaction est validée)� Régulièrement (ou en cas de crash), les écritures validées de la zone en attente

sont propagées dans le système de fichiers

# 21

'

&

$

%

3.5 Deuxième idée : le journal

� Pour assurer que les écritures sont propagées dans l’ordre dans lequel elles ont étéexécutées, la zone en attente est structurée comme un journal� Chaque écriture est ajoutée à la fin du journal� Les transactions validées de la zone en attente sont propagées dans le système

de fichiers dans l’ordre du journal (du début du journal à la fin du journal)



# 22

'

&

$

%

3.6 Troisième idée : le journal parallèle

� Problèmes : plusieurs processus peuvent effectuer des transactions en parallèle� Les écritures des transactions // sont entrelacées dans le journal→ comment savoir lesquelles sont validées ?

� Solution classique� Si plusieurs transactions en //, l’ensemble des opérations est validée lorsque la

dernière est terminée� Avantage : simple à mettre en oeuvre (compteur du nombre d’opérations en //)� Désavantage : risque de ne jamais valider si arrivée continue de nouvelles

opérations

# 23

'

&

$

%

3.7 Structure du journal

� Le système gère techniquement deux journaux� L’un en mémoire appelé journal mémoireI Contient uniquement la liste des n° de blocs modifiésI Le contenu des blocs modifiés, lui, se trouve dans le buffer cache� L’un sur disque appelé journal disqueI Contient la liste des n° de blocs modifiés et une copie des blocsI Note : le bloc est propagé du journal vers le syst. de fic. plus tard

→ le système peut donc gérer jusqu’à 3 copies d’un bloc� L’un sur disque dans le système de fichiers appelé bloc disque� L’un sur disque dans le journal appelé bloc du journal disque� L’un en mémoire dans le buffer cache appelé bloc en cache



# 24

'

&

$

%

3.8 Principe d’algorithme du journal

� Étapes pour modifier le bloc numéro n1. chargement du bloc disque dans le buffer cache2. modification du buffer (c’est-à-dire du bloc en cache)3. ajout de n à la liste des blocs modifiés du journal mémoire

� À la fin d’une opération, étapes pour valider la transaction1. copie des blocs en cache modifiés dans le journal disque2. copie de la liste des blocs modifiés dans le journal disque3. marquage de la transaction comme validée

� Plus tard, pour propager la transaction1. copie les blocs du journal disque dans le système de fichiers2. réinitialise le journal disque et le journal mémoire

# 25

'

&

$

%

3.9 Utilisation du journal

� Trois fonctions dans l’interface de gestion du journal (log.c)� begin_op() : démarre une transaction� end_op() : valide une transaction� log_write(struct buf* b) : ajoute b à la transaction

� Pour effectuer une opération journalisée, au lieu d’appeler directement bwrite(),on doit donc exécuter :

begin_op()

log_write(b1)

log_write(b2)

...

end_op()



# 26

'

&

$

%

3.10 Mise en œuvre dans xv6 (1/3)

� void begin_op() : démarre une transaction� Si écriture du journal sur disque en cours, attend� Si journal plein, attend� Incrémente le nombre d’opérations en cours (log.outstanding)

� void end_op() : termine une transaction� Décrémente le nombre d’opérations en cours, et si égal à 0 :I Écrit journal mémoire + blocs en cache dans journal disque

(write_log())I Marque la transaction du journal disque validée (write_head())I Propage les écritures du journal disque vers le système de fichiers

(install_trans())I Supprime les journaux en mémoire et sur disque (write_head())

# 27

'

&

$

%


� void log_write(struct buf* b)

� Ajoute le bloc associé à b au journal� Ajoute le numéro de bloc au journal mémoire� Marque buffer B_DIRTY =⇒ ne sort pas du cache (voir bget())


Systèmes de fichier 4 Partitions et systèmes de fichiers

# 28

'

&

$

%


� Après un crash, appelle install_trans() qui propage les écritures du journaldisque vers le système de fichiers� Dans le pire des cas, des écritures qui avaient déjà été effectuées sont rejouées� Mais à la fin du rejeu, le système de fichiers est dans un état cohérent

# 29

'

&

$

%

4 Partitions et systèmes de fichiers

4.1 Système de fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.3 Principe d’un système de fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.3 Les partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325.0 L’image disque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34


Systèmes de fichier 4 Partitions et systèmes de fichiers

# 30

'

&

$

%

4.1 Système de fichiers

� Système de fichiers : définit la structure permettant de stocker des fichiers (souventpour un périphérique de type bloc)� UFS : Unix Files System (xv6, BSD)� ext : extended file system (Linux - ext4 aujourd’hui)� NTFS : New Technology File System (Windows)� APFS : APple File System (MacOS)� FAT : File Allocation Table (Windows)� BTRFS : B-TRee File System (Linux)� et beaucoup d’autres !

# 31

'

&

$

%

4.2 Principe d’un système de fichiers

� Fichier = ensemble cohérent de données pouvant être lues ou écrites

� Système de fichiers = associe des noms et des fichiers� Exemple : /etc/passwd → root :* :0 :0 :System Administrator...

� En général, un symbole spécial sert de séparateur pour des répertoires� / dans les systèmes UNIX, \ dans les systèmes Windows



# 32

'

&

$

%

4.3 Les partitions

� Un disque est souvent composé de plusieurs partitions� Partition = zone continue qui contient un système de fichiers

� Structure typique d’un disque dur� Premier bloc : table des partitionsI Par exemple : Master Boot Record� Bloc 2 à x : chargeur de noyauI S’occupe de charger le noyau d’une des partitionsI Par exemple : LILO, GRUB� Bloc x à y : partition 1� Bloc y à z : partition 2� etc...

# 33

'

&

$

%

4.4 L’image disque

� Un fichier peut lui-même contenir les données d’un disque complet� On parle alors d’une image disque ou d’un disque virtuel� Typiquement utilisé en virtualisation� Par exemple : xv6.img est l’image disque utilisée avec l’émulateur qemu pour

démarrer xv6


Systèmes de fichier 5 Le système de fichiers UFS/xv6

# 34

'

&

$

%

5 Le système de fichiers UFS/xv6

5.2 Structure globale du système de fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.2 Le dinode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.4 Les blocs de données d’un fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.4 Ajout d’un bloc à un fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.6 Les répertoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.6 Du chemin à l’inode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406.0 Création et suppression de fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

# 35

'

&

$

%

5.1 Structure globale du système de fichiers

� Cinq grandes zones contiguës (fichier fs.h)� Le super bloc décrit les autres zones� Le journal contient les journaux disque� La table des dinodes contient les méta-données des fichiers (taille, type comme

ordinaire ou répertoire...)� La table des blocs libres indique les blocs de données libres� La zone des blocs de données contient les données des fichiers



# 36

'

&

$

%

5.2 Le dinode

� Un fichier sur disque est constitué :� de méta-données appelées un dinode (taille fixe, voir fs.h)I type du fichier (ordinaire, répertoire, device)I taille du fichierI liste de blocs de données du fichierI un bloc d’indirection (voir diapositives suivantes)I numéro de device si fichier deviceI nombre de liens durs vers le fichier (rappel : un lien dur est un nom dans un

répertoire)� de blocs de donnéesI ce sont les blocs qui contiennent le contenu du fichier

# 37

'

&

$

%

5.3 Les blocs de données d’un fichier

� Un dinode liste directement les n° des 12 premiers blocs� le bloc dinode.addrs[0] contient les octets de 0 à 511 du fichier� ...� le bloc dinode.addrs[i] contient les octets i*512 à i*512 + 511

� Le bloc d’indirection contient les n° de blocs suivants� le n° du bloc d’indirection ind est donné en dinode.addrs[12]� le bloc ind[0] contient les octets 12*512 à 12*512 + 511

Note : comme un bloc fait 512 octets et qu’un n° de bloc est codé sur 4 caractères, unfichier a une taille maximale de 12 + 512/4 blocs



# 38

'

&

$

%

5.4 Ajout d’un bloc à un fichier

� Pour ajouter un nouveau bloc à un dinode dino (fonction bmap() dans fs.h)1. Trouve un n° de bloc libre dans la table des blocs libres

(fonction balloc() dans fs.h)2. Marque le bloc occupé (mettre son bit 1 dans la table)3. Ajoute le n° de bloc à la liste des blocs de données de dino� cet ajout peut nécessiter l’allocation du bloc d’indirection

# 39

'

&

$

%

5.5 Les répertoires

� Un répertoire est un fichier qui a pour type T_DIR

� Contient un tableau associant des noms et des n° de dinodes� inum : numéro d’inode� name : nom du fichier

� L’inode 1 est forcément un répertoire : c’est le répertoire racine du système defichiers

Remarque : dinode.nlink donne le nombre de fois où un dinode est référencé à partird’un répertoire =⇒ fichier supprimé quand nlink égal à 0



# 40

'

&

$

%

5.6 Du chemin à l’inode

� Pour trouver un n° de dinode à partir du chemin /e0/../en (voir namex() dansfs.c)1. cur = 1

2. Pour i de 0 à n inclus(a) Chercher l’association [inum, name] dans les blocs de données du dinode

cur tel que name soit égal à ei(b) cur = inum

# 41

'

&

$

%

5.7 Création et suppression de fichier

� Pour créer le fichier f dans le répertoire d (fonction create() dans sysfile.c)1. Trouver un dinode inum libre en trouvant un inode ayant pour type 0 dans le

tableau des dinodes (ialloc() dans fs.h)2. Ajouter l’association [inum, f] à d

� Pour supprimer le fichier f du répertoire d (fonction sys_unlink() danssysfile.c)1. Supprimer l’entrée correspondant à f dans d2. Décrémenter le nlink de f et si nlink égale 03. Supprimer les blocs de données du fichier f4. Supprimer l’inode f (en mettant son type à 0)


Systèmes de fichier 6 La pile d’entrée/sortie de xv6

# 42

'

&

$

%

6 La pile d’entrée/sortie de xv6

6.2 L’inode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446.2 Principales fonctions des inodes (1/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446.4 Principales fonctions des inodes (2/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466.4 Principales fonctions des inodes (3/3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466.6 Le fichier ouvert. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .486.6 Le descripteur de fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

# 43

'

&

$

%

6.1 L’inode

� inode = cache mémoire d’une dinode� Entre dans le cache au open()

� Peut être évincé du cache à partir du close()

� Contient les champs du dinode� + des champs pour savoir à quel dinode l’inode correspondI Numéro de device et numéro de dinode� + des champs nécessaires lorsque le dinode est utiliséI Un verrou pour gérer les accès concurrentsI Un compteur donnant le nombre de processus utilisant l’inode pour savoir

quand l’inode peut être évincé du cache

� Table des inodes = table qui contient les inodes



# 44

'

&

$

%

6.2 Principales fonctions des inodes (1/3)

� struct inode* iget(int dev, int inum)

� Correspond à open() : renvoie un inode associé à [dev, inum]

� Incrémente le compteur d’utilisation de l’inode (non évinçable)� Ne verrouille pas l’inode et ne lit pas l’inode à partir du disque (optimisation

pour éviter une lecture disque lorsqu’on crée un fichier)I inode.valid indique si l’inode a été lu à partir du disque

� void ilock(struct inode* ip)

� Prend un verrou sur l’inode� Lit l’inode à partir du disque si pas déjà fait

� void iunlock(struct inode* ip)

� Lâche le verrou sur l’inode

# 45

'

&

$

%


� void itrunc(struct inode* ip)

� Libère tous les blocs du fichier (taille à 0)

� void iupdate(struct inode* ip)

� Copie l’inode vers la dinode disque (techniquement, via le cache d’entrée/sortie)



# 46

'

&

$

%


� void iput(struct inode* ip)

� Correspond à close()

� Diminue le compteur d’utilisation de l’inode� Si cpt tombe à 0, l’inode est évinçable du cache et dans ce casI Si nlink est égal à 0 (l’inode n’est plus référencé par un répertoire)F Supprimer les blocs de données de l’inode (itrunc)F Marque l’inode comme libre (type = 0)

Remarque : si on supprime un fichier d’un répertoire (unlink()) alors que le fichier estencore utilisé (ouvert) par un processus, l’inode n’est pas supprimé : il le sera lors dudernier close() quand le compteur d’utilisation tombe à 0

# 47

'

&

$

%

6.5 Le fichier ouvert

� Plusieurs processus peuvent ouvrir le même fichier� Chaque processus possède des droits en lecture/écriture indépendants� Chaque processus possède une tête de lecture, et indépendante de celle des

autres processus

� Une structure de fichier ouvert par open() :� Un pointeur vers un inode� Des droits d’accès� Une tête de lecture



# 48

'

&

$

%

6.6 Le descripteur de fichier

� Chaque processus possède une table ofile des fichiers ouverts� Un descripteur d est un index dans cette table� proc[i].ofile[d] pointe vers un fichier ouvert� proc[i].ofile[d].ip pointe vers l’inode

� Bon à savoir� Lors d’un fork(), le père et le fils partagent les fichiers ouverts� Donc proc[pere].ofile[d] == proc[fils].ofile[d]

� Et donc, si le père lit, il avance la tête de lecture pour le fils� Utile pour mettre en œuvre les tubes

# 49

'

&

$

%

7 Ce qu’il faut retenir

� Un pilote de périphérique est simplement une fonction (iderw() par exemple)

� Les lectures et écritures sont journalisées� Assure la cohérence du système de fichiers en cas de crash

� Le noyau dispose d’un cache d’entrée/sortie� Se trouve en mémoire, géré par le noyau� Permet d’accélérer les entrées/sorties

� Un système de fichiers sépare� Le nommage (répertoire) des fichiers (dinodes + blocs données)� Les méta-données (dinode) des blocs des données

� Un descripteur est un index dans la table ofile� proc->ofile[i] est un fichier ouvert qui référence un inode




Références

[Aleph, 1996] Aleph, O. (1996). Smashing the stack for fun and profit. Phrack #49.

[Amdahl, 1967] Amdahl, G. M. (1967). Validity of the single processor approach to achieving large scalecomputing capabilities. In Proceedings of the April 18-20, 1967, spring joint computer conference, pages483–485. ACM.

[Bryant and O’Hallaron, 2003] Bryant, R. E. and O’Hallaron, D. R. (2003). Computer Systems: A Program-mer’s Perspective. Prentice Hall.

[Coffman et al., 1971] Coffman, E. G., Elphick, M., and Shoshani, A. (1971). System deadlocks. ACMComputing Surveys (CSUR), 3(2):67–78.

[Manson et al., 2005] Manson, J., Pugh, W., and Adve, S. V. (2005). The Java Memory Model. In Proceed-ings of the 32Nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL’05, pages 378–391. ACM.

[Patterson, 2011] Patterson, D. A. (2011). Computer architecture: a quantitative approach. Elsevier.

[Patterson and Hennessy, 2013] Patterson, D. A. and Hennessy, J. L. (2013). Computer organization anddesign: the hardware/software interface. Newnes.

141

142

IndexA

Adresse logique, 78aio_error, 113aio_read, 113aio_suspend, 113aio_write, 113

BBarrière, 30

pthread_barrier_init, 30pthread_barrier_wait, 30

Berkeley DB, see Oracle Berkeley DBbless, 104

Ccache, 23

Mémoire, 76Cache

d’adresses, 80cache fully-associatif, 23cache hit, 23cache miss, 23cache snooping, 102calloc, 82close, 106cohérence de cache, 102Cohorte, see Synchronisation, Cohortecreat, 106Création de fichier, see Fichier, Création de

DDescripteur, 109

Écriture, 107Lecture, 107

dup, 109dup2, 109Duplication de descripteur, 109

EÉcriture fichier, see Fichier, ÉcritureÉcriture sur descripteur, see Descripteur, ÉcritureExclusion mutuelle, see Synchronisation, Exclusion

mutuelle

Ffcntl, 110Fermeture fichier, see Fichier, FermetureFichier

Conseil, 113Création de, 106Écriture, 107Fermeture de, 106Lecture, 107Ouverture de, 106Verrouillage de, 110

fopen, 105

fread, 105free, 82fsync, 106fwrite, 105

GGDBM, 105

Hhexdump, 104Huge page, 79Hyperthreading, 95Hypertransport, 97

IInclusion, see Principe d’inclusionInstruction Level Parallelism (ILP), 92Instructions vectorielles, 93Intel, 76, 80io_setup, 113io_submit, 113IPC, 28

LLecteurs/Rédacteurs, see Synchronisation,

Lecteurs/RédacteursLecture de fichier, see Fichier, LectureLecture sur descripteur, see Descripteur, Lecturelibaio, 113ligne de cache, 23

Mmalloc, 82mallopt, 82Mémoire partagée, 28

ftruncate, 27mmap, 27shm_init, 28shm_open, 27, 28shm_post, 28shm_timedwait, 28shm_trywait, 28shm_wait, 28

memory wall, 20memset, 82mkfifo, 27mmap, 81mmap, 114Moniteur, 29, 34

pthread_cond_broadcast, 29pthread_cond_destroy, 29pthread_cond_init, 29pthread_cond_signal, 29pthread_cond_timedwait, 29pthread_cond_wait, 29

msync, 114

143

munmap, 114Mutex, 29, 34

pthread_mutex_destroy, 29pthread_mutex_init, 29pthread_mutex_lock, 29pthread_mutex_t, 29pthread_mutex_trylock, 29pthread_mutex_unlock, 29

NNDBM, 105Non Uniform Memory Architecture, 97NUMA, 97

OO_APPEND, 106O_CREAT, 106O_NDELAY, 106O_NONBLOCK, 106open, 105, 106Oracle Berkeley DB, 105O_RDONLY, 106O_RDWR, 106O_SYNC, 106O_TRUNC, 106Ouverture fichier, see Fichier, OuvertureO_WRONLY, 106

PPagination, 78PAPI, 12pipe, 27Pipeline, 90posix_fadvise, 113Principe d’inclusion, 76Processeur, 88pthread_rwlock_rdlock, 34pthread_rwlock_t, 34pthread_rwlock_unlock, 34pthread_rwlock_wrlock, 34

QQPI, 97Quick Path Interconnect, 97

Rread, 105, 107Read-Write lock, 31

pthread_rwlock_rdlock, 31pthread_rwlock_t, 31pthread_rwlock_unlock, 31pthread_rwlock_wrlock, 31

realloc, 82Rédacteurs, see Synchronisation, Lecteurs/Rédac-

teurs

Ssendfile, 109

SMP, 96SMT, 95superscalaire, 91Symmetric Multi-Processing, 96Synchronisation

Cohorte, 33disque, 106Exclusion mutuelle, 32Lecteurs/Rédacteurs, 34Producteur-Consommateur, 33

TTable des pages, 79TLB, 80Translation Look-aside Buffer, 80

UUnix NDBM, see NDBM

VVerrouillage de fichier, see Fichier, Verrouillage de

Wwrite, 105, 107

Xxxd, 104

144

Documents

€¦ · CSC4508–Systèmesd’exploitation Contents Licence vii Présentationdumodule 1 1Présentationdumodule 2 1.1Organisation