:tocdepth: 2 ===================== Système de fichiers ===================== .. include:: common.rst.inc Problématique ============= Exemple +++++++ .. code-block:: c fd = open("mon_fichier.txt", O_WRONLY); write(fd, "hello world\n", 12); close(fd); Niveaux d'abstraction +++++++++++++++++++++ * matériel (*e.g.* cylindre/tête/secteur) * stockage de masse (tableau d'octets) * système de fichiers (hiérarchie de fichiers) Chaque fichier possède : * sa propre structure interne (tableau d'octets) * un *nom* (adressage indirect) * des permissions (drois d'accès différents) Fonctionalités ++++++++++++++ * Création / destruction * Ouverture / fermeture * mode d'ouverture / verrouillage (concurrence) * Lecture / écriture * Atteindre une position donnée (seek) * selon le type de fichier (accès direct / séquentiel) Généralités =========== .. index:: méta-données Terminologie ++++++++++++ * Données : les données « contenues dans » le fichier. * Méta-données = données **à propos** des données, nécessaire à leur *structuration* et à leur gestion par le système d'exploitation. * Le périphérique de stockage contient à la fois les données et les méta-données (surcoût) .. figure:: _static/stockage_metadonnees_donnees.* :width: 70% Méta-données d'un fichier +++++++++++++++++++++++++ * Nom* * Type (simple, répertoire, tube, etc...) * Taille * Adresse du contenu sur le périphérique * Informations de sécurité * Dates de création / accès / modification Types de fichiers +++++++++++++++++ * stockage (fichier « classique ») * répertoires, * liens symboliques, * périphérique (pas de contenu effectif : redirigé vers le matériel) * tube, socket, mémoire partagée... (pas de contenu effectif : redirigé vers une ressource du SE) Hiérarchie ++++++++++ * Chaque fichier doit avoir un nom univoque * éventuellement plusieurs... * L'espace de nom est structuré en hiérarchie : * notions de *répertoire* et de *chemin* * notion de répertoire *racine* (point d'entrée de la hiérarchie) * notions de chemin *relatif* et de répertoire *courant* Hiérarchie sous MS DOS / Windows -------------------------------- Chaque périphérique possède sa propre racine, identifiée par une lettre. .. figure:: _static/hierarchie_dos.* :width: 90% Hierarchie sous UNIX -------------------- On a une hiérarchie *unique* ; chaque périphérique ancre sa racine dans un répertoire (**montage**). .. figure:: _static/hierarchie_unix.* :width: 90% Hierarchie sous Plan9 --------------------- * Chaque processus dispose de sa propre hiérarchie (racine et points de montage), héritée du processus père, mais personnalisable. * NB: sous UNIX, l'appel système *chroot* permet de changer la racine pour un processus donné, mais pas les points de montage. Stockage des méta-données ========================= Différentes méthodes ++++++++++++++++++++ * stockages dans les répertoire * ISO8859 (CD/DVD) * FAT32 (MS-DOS, Windows anciens, clés USB) * stockage dans des *i-nodes* * NTFS (Windows modernes) * ext4 (Linux) Répertoires +++++++++++ Les méta-données (y compris le nom) de chaque fichier sont stockées directement dans le contenu du répertoire le contenant. .. figure:: _static/metadonnees_repertoire.* :width: 80% .. index:: i-node I-nodes +++++++ * Les méta-données (sauf le nom) de chaque fichier sont stockées dans un bloc indépendant appelé **i-node**. * Chaque i-node est identifié par un numéro unique sur le périphérique (tableau des i-nodes). * Le contenu d'un répertoire ne contiennent qu'une correspondance entre nom local du fichier et numéro d'i-node. Illustration ------------ .. figure:: _static/metadonnees_inodes.* :width: 100% .. index:: single: lien; physique Remarques ````````` * NB : dans un système utilisant des i-nodes, on peut envisager d'avoir plusieurs fichiers possédant le même i-node (**lien physique**, ou *hard link*). * Cela nécessite un compteurs de références pour savoir quand libérer les données. * La commande ``rm`` / l'appel système ``unlink`` ne supprime pas directement le fichier, ils suppriment simplement le lien entre un répertoire et un i-node, et diminuent le compteur de références de cet i-node. * Les données sont libérées lorsque l'i-node devient inaccessible (0 références). .. index:: single: compteur de références; fichier Compteur de références ---------------------- .. figure:: _static/metadonnees_hard_link.* :width: 100% Hiérarchie cyclique ------------------- * Problème en cas de création de cycles dans la hiérarchie .. figure:: _static/hierarchie_cyclique.* :width: 36% Exemple de hiérarchie cyclique Restrictions nécessaires ```````````````````````` * UNIX : liens physiques sur les répertoires tant qu'ils forment un graphe acyclique. * LINUX, Windows (NTFS) : pas de liens physiques sur les répertoire (à part '.' et '..'). Autres types de fichiers ======================== Généralités +++++++++++ * En plus des fichiers de stockage et des répertoires, il existe d'autres types de fichiers, qui donnent accès à des données situées « ailleurs » * périphérique, tube, socket (cf. chapitre `es`:doc:) * lien symbolique (cf. ci après). * Leur « contenu » (sur le périphérique) n'est en général pas accédé directement, * il sert au SE à savoir ou se trouvent réellement les données; * (mais il existe aussi des appels systèmes pour modifier ce contenu). .. index:: single: lien; symbolique Lien symbolique +++++++++++++++ * le contenu de ce fichier est un chemin vers un autre fichier ; * le système d'exploitation interprète le contenu du lien symbolique lorsqu'on cherche à y accéder, et redirige vers le fichier pointé ; * nécessite une API plus riche permettant de travailler sur le lien lui même. Comparaison avec les liens physiques ------------------------------------ * Le lien sybolique fonctionne avec *tout* type de structuration (répertoires ou i-node). Il peut même pointer vers un autre périphérique (car utilise le chemin). * Le lien symbolique est asymétrique : si l'original est déplacé ou détruit, le lien est « brisé » → pas de problème de cycles. Exemple de hiérarchie pseudo-cyclique ------------------------------------- .. figure:: _static/hierarchie_soft_link.* :width: 36% Exemple de lien symbolique (répertoire) --------------------------------------- .. figure:: _static/metadonnees_soft_link_dir.* :width: 100% Exemple de lien symbolique (i-node) ----------------------------------- .. figure:: _static/metadonnees_soft_link_inode.* :width: 100% Structration du contenu ======================= Problème ++++++++ Les méta-données décrivent comment sont *logiquement* structurées les données dans le système de fichier La **structuration physique** de ces données doit rendre compte de la structure logique en optimisant : * le temps d'accès séquentiel * le temps d'accès direct * le surcoût en espace (stockage) * l'évolution de la taille des fichiers (fragmentation) Remarques --------- Ces critères dépendent des caractéristiques du périphérique de stockage sous-jacent. * Par exemple, les périphériques mécaniques ont des temps d'accès direct supérieur au temps d'accès séquentiel (bande > CD > disques dûrs). * On discutera en fin de chapitre des évolutions rendues nécessaires par d'autres technologies (notamment mémoires flash). Remarques (2) ````````````` De même qu'il existe plusieurs manière de gérer les méta-données, il existe plusieurs manière de gérer les données. Ces deux problématiques sont orthogonales, toutes les combinaisons sont en théorie possibles. Allocation contiguë +++++++++++++++++++ Principe : les fichiers sont stockés de manière contigüe, les uns à la suite des autres. .. figure:: _static/sf_continue.* :width: 100% Évaluation ---------- Avantages: * accès séquentiel et direct optimal (selon périphérique) * pas de surcoût en espace (autre que les méta-données) Inconvénients: * impraticable si les fichiers sont appelés à croître en taille Évaluation (2) `````````````` → Adapté sur les périphériques en lecture seule, ou non appelés à évoluer. * CD-ROM, DVD-ROM * bande magnétique (sauvegarde, cf. commande ``tar``) Listes chaînées +++++++++++++++ Principe : les fichiers sont séparés en bloc ; chaque bloc pointe vers le bloc suivant. .. figure:: _static/sf_listes_chainees.* :width: 100% Évaluation ---------- Avantages: * évolution de la taille des fichiers Inconvénients: * fragmentation interne (gaspillage) * performance * le parcours séquentiel du fichier requiert des accès direct au périphérique (changement de bloc) * l'accès direct au fichier requier un parcours séquentiel de la *liste* → nombreux accès au périphérique Évaluation (2) `````````````` À propos des inconvénients : * la fragmentation interne et les accès directs pour changer de bloc sont le pendant inévitable du découpage en bloc, donc de l'évolutivité des fichiers ; * la pénalisation de l'accès direct, en revanche, semblent prohibitive. → En pratique, on n'utilisera jamais cette structuration telle quelle. .. index:: FAT (File Allocation Table) File Allocation Table (FAT) +++++++++++++++++++++++++++ (a donné son nom au format FAT32) Principe : on « externalise » la structure de la liste chaînée dans une table qui, pour chaque bloc, donne le numéro du bloc suivant. .. figure:: _static/sf_fat.* :width: 100% Évaluation ---------- Avantages : * avantages de la liste chaînée... * ... sans pénaliser l'accès direct car la FAT est maintenue en mémoire (le parcours séquentiel de la liste de blocs est donc négligeable devant le temps d'accès au périphérique) Inconvénients : * ceux liées au découpage en blocs (fragmentation interne, accès séquentiel) Évaluation (2) `````````````` Inconvénients (suite) : * La FAT est une ressource critique (elle est généralement dupliquée par sécurité). * La FAT peut devenir volumineuse lorsque la capacité des disques augmente (occupation sur le disque et en mémoire). Solutions partielles: * ne charger qu'une partie de la FAT en mémoire (réduit les performances) * augmenter la taille des blocs (gaspillage) .. index:: table d'index Tables d'index ++++++++++++++ Principe : une table contient la liste ordonnée des blocs contenant les données du fichier. .. figure:: _static/sf_tables_index.* :width: 100% Évaluation ---------- Avantages: * les mêmes que la FAT... * mais plus modulaire : on ne charge que les tables des fichiers ouverts Inconvénients: * ceux liées au découpage en blocs (fragmentation interne, accès séquentiel) * la taille du fichier est limité par la taille de la table d'index Variante 1 ---------- Afin d'autoriser des tables plus grandes, il est préférable de les stocker dans un bloc plutôt que dans la description du fichier .. figure:: _static/sf_tables_index_2.* :width: 100% Variante 2 ---------- * Comme pour la pagination, on peut utiliser plusieurs niveaux de table * avantage : augmentation de la taille maximale des fichiers, tout en limitant le surcoût en espace * inconvénient : augmente le surcoût en temps (un accès par niveau dans la hiérarchie) * Afin d'optimiser l'accès, on peut mixer différents niveaux d'indexation * avantage : surcoûts en temps et en mémoire proportionnels de la taille du fichier Exemple ------- .. figure:: _static/inode_bsd.* :width: 60% .. Exemple : BSD Unix blocs de 4Ko, adresses sur 4o, soit 1024 entrées dans un bloc d'index un inode référence : 12 blocs 3 tables de niveau 1 une table de niveau 2 une table de niveau 3 4,4 tera-octets adressables Pour aller plus loin ==================== .. index:: extent Extents, allocation différée ++++++++++++++++++++++++++++ On a vu que le découpage en blocs permet l'évolution des noms de fichiers, mais pénalise en revanche l'accès séquentiel. Les systèmes de fichiers modernes offrent les fonctionalités suivantes : * allocation par *extent* : au lieu d'indexer des blocs individuels, ils indexent des plages de blocs (numéro de bloc + *nombre* de blocs) * allocation différée : au lieu d'allouer les blocs immédiatement, ils gardent les données en mémoire tampon le plus longtemps possible, afin de savoir combien de blocs seront disponibles. .. index:: journalisation Journalisation ++++++++++++++ * principe : ne pas laisser le système de fichiers dans un état incohérent → transaction * chaque transaction est écrite dans un journal avant d'être effectuée * si une transaction ne peut être terminée, le journal permet de l'annuler ou de la terminer * NTFS (mais pas FAT32), ext3/4 (mais pas ext2)... Mémoires flash ++++++++++++++ * Les mémoires flash sont de plus en plus utilisées dans les périphériques de stockage : clés USB, cartes mémoire, Solid State Drives. * Elles ont des caractéristiques très différentes des autres périphériques : * temps d'accès équivalent en séquentiel et en direct * écriture asymétrique (0→1 nécessite d'effacer un bloc complet) * nombre d'écriture limité (~ 100.000 - 1.000.000) Impacts sur les systèmes de fichiers ------------------------------------ * Les implémentations conçues pour les autres périphériques fonctionnent, mais sont sub-optimale * Certains efforts visent à tirer le meilleur parti des mémoires flash * privilégier l'utilisation équitable de tous les blocs, plutôt que de privilégier l'utilisation de blocs contigus * tenir compte de l'asymétrie des écriture dans les structures de données utilisées