Système de fichiers

Problématique

Exemple

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

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)
_images/stockage_metadonnees_donnees.svg

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.

_images/hierarchie_dos.png

Hierarchie sous UNIX

On a une hiérarchie unique ; chaque périphérique ancre sa racine dans un répertoire (montage).

_images/hierarchie_unix.png

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.

_images/metadonnees_repertoire.png

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

_images/metadonnees_inodes.png
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).

Compteur de références

_images/metadonnees_hard_link.png

Hiérarchie cyclique

  • Problème en cas de création de cycles dans la hiérarchie
_images/hierarchie_cyclique.png

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 Entrées-sorties)
    • 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).

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

_images/hierarchie_soft_link.png

Exemple de lien symbolique (répertoire)

_images/metadonnees_soft_link_dir.png

Exemple de lien symbolique (i-node)

_images/metadonnees_soft_link_inode.png

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.

_images/sf_continue.png

É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.

_images/sf_listes_chainees.png

É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.

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.

_images/sf_fat.png

É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)

Tables d’index

Principe : une table contient la liste ordonnée des blocs contenant les données du fichier.

_images/sf_tables_index.png

É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

_images/sf_tables_index_2.png

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

_images/inode_bsd.png

Pour aller plus loin

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.

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