Le système de fichiers

Introduction et définition d'un fichier

Définition d'un fichier

Un fichier est une collection nommée d'information en relation. Pour l'utilisateur·ice c'est un moyen de conserver des informations.

Le contenu d'un fichier est défini par son type (et donc sa structure), le programme qui l'a créé et les informations placées par l'utilisateur·ice.

Il existe plusieurs médias qui peuvent être utilisés pour stocker des fichiers de manière "définitive". La qualité de ce dernier est importante, par exemple le stockage à long terme sur les disques optique est difficile à garantir.

Le système d'exploitations propose, grâce aux fichiers un moyen d'utiliser l'espace de stockage. Le fichier est une abstraction nécessaire qui permet la représentation informatique de concept existants, et cela, de manière uniforme et simple d'accès.

Un fichier a plusieurs attributs tel que, le nom, l'identifiant, le type, les permissions, la localisation, la taille, la date de création et le propriétaire.

Opérations sur les fichiers

Les opérations sur les fichiers sont,

Ouverture d'un fichier

L'ouverture d'un fichier est l'opération indiquant au système d'exploitation que le programme souhaite accéder à un fichier. Lors de cette ouverture le système mémorise les informations sur le fichier, vérifie si l'accès est autorisé et initialise les structures internes et place le pointeur de position au début.

Une fois que le traitement est fini, le fichier est fermé, ce qui va supprimer les structures internes.

Ce système d'ouverture et de fermeture soulage fortement le système d'exploitation, car sans ça il faudrait répéter toutes les procédures d'ouverture et fermeture à chaque opération sur le fichier, tandis qu'ici, on le fait qu'une fois.

Il est aussi bon de noter que plusieurs utilisateurs doivent pouvoir ouvrir les , il faut donc mettre une structure efficace en mémoire pour éviter les informations en double.

Informations à retenir sur les fichiers utilisés

Les informations à retenir sur le fichier sont, le mode d'ouverture (lecture seule, lecture-écriture, écriture seule, etc), l'emplacement vers le premier bloc du fichier, la position courante, et les permissions d'accès.

Type de fichier

Pour traiter le fichier correctement, il faut connaitre sa structure interne, et pour cela, il faut connaitre son type.

Le type est identifié par l'extension (sous Windows), par un Uniform Text Identifier (sous Mac OS X), par un "nombre magique" qui est la valeur des premiers octets (sous Unix) et avec des "attributs étendus" sous OS/2.

Méthode d'accès des fichiers

La méthode d'accès aux fichiers dépend du support physique, ainsi une bande magnétique aura un accès séquentiel alors qu'une clé USB ou un disque dur aura un accès aléatoire.

L'accès séquentiel correspond à un enregistrement en séquence, ainsi pour pouvoir lire le 10e élément, il faut d'abord passer sur les neuf premiers.

L'autre type d'accès est l'accès aléatoire ou direct qui correspond à des enregistrements de taille fixe, ainsi, on peut calculer directement l'adresse de l'élément auquel on veut aller sans avoir besoin de lire les précédents.

Il est aussi possible d'avoir un accès séquentiel indexé qui va créer un index permettant à la fois un accès séquentiel et un accès direct aux fichiers.

Structure du système de fichiers

Pour organiser le système de fichier, il y a deux structures principales,

La partition qui est une partie du disque dur. Ainsi, on peut découper le disque en plusieurs partitions (exemple, partition système, partition de données), ainsi cela peut permettre d'isoler des données du reste ou encore d'avoir plusieurs systèmes d'exploitations sur un même disque (dual-boot).

La deuxième structure est le répertoire (ou dossier), qui contient les informations sur les fichiers qu'il contient (nom, emplacement, taille, pointeur vers le premier bloc).

Ainsi, la structure interne d'un répertoire doit permettre de localiser, créer, supprimer, renommer, visualiser des fichiers ou encore aller dans un autre répertoire.

Organisation des répertoires

Les répertoires peuvent être à un niveau, deux niveaux ou sous forme d'arbre (c'est ce qui est utilisé aujourd'hui). Le répertoire de départ est appelé le répertoire racine (ou root directory), ainsi, on va représenter ce répertoire racine par un / ou un \.

Ainsi, un fichier peut être défini soit par un chemin d'accès absolu, c'est le chemin d'accès partant du répertoire racine (exemple /home/snowcode/image.png).

On peut aussi définir un fichier par un chemin d'accès relatif, c'est un chemin d'accès partant d'un autre répertoire. Voici par exemple un chemin d'accès relatif au dossier /home : snowcode/image.png ou encore ./snowcode/image.png.

La manière de supprimer un dossier qui contient des fichiers ou d'autres dossiers dépendent du système d'exploitation. Par exemple, sous Linux, pour supprimer un dossier, il faut faire rm -r mondossier le -r signifiant qu'il va supprimer de manière récursive.

Fonctionnement des liens

Sous Windows, on utilise des raccourcis, les raccourcis sont simplement des fichiers .lnk désignant un autre emplacement.

En revanche, sous Unix, on utilise des liens symboliques, c'est une entrée particulière (comme un fichier ou un dossier) qui désignent un emplacement différent.

À la différence de Windows, si un programme ouvre un lien symbolique, il va automatiquement ouvrir le fichier (ou le dossier) qui est pointé par ce dernier. C'est donc très intéressant pour faire apparaître un même fichier à plusieurs endroits.

Sous Linux, un lien symbolique peut être créé avec la commande ln -s <chemin de fichier vers lequel pointer> <position du lien>

Opération de montage

L'opération de montage permet de rendre accessible un système de fichier. Il peut s'agir d'une autre partition, d'un autre média (DVD, USB, etc), et le format peut être différent de la partition actuelle (NTFS, FAT, ext4, etc).

Le format de systèmes de fichiers FAT, bien qu'ancien et un peu limité, a l'avantage d'être supporté par tous les systèmes d'exploitations. En revanche, NTFS est un système Windows, ext4 est un système Linux et APFS est un format de système macOS.

Durant cette opération de montage, le système vérifie la cohérence et donne accès aux informations.

Cette opération de montage peut être implicite (le système le fait automatiquement) ou explicite (l'utilisateur·ice doit lui demander spécifiquement de monter le système).

Ainsi dans Linux, si je connecte une clé USB et que je la monte dans un dossier, je pourrais aller dans le dossier et interagir avec les fichiers comme si de rien était alors qu'en vérité ces fichiers sont sur la clé USB.

Implémentation

Maintenant on va voir comment la structure vue précédemment est implémentée dans le système d'exploitation.

Informations stockées

Sur le disque on va stocker :

En mémoire, on va retenir :

Ainsi, lorsqu'un fichier est créé, on va stocker un FCB (file control block ou i-node) pour y inclure les permissions, la date, le propriétaire, le groupe, la taille, le premier bloc, etc.

Ensuite le fichier va être enregistré dans la TFO (qui comprend les informations du FCB ainsi que le nombre de processus lié à ce fichier).

Le fichier va aussi être enregistré dans la TDF du processus pour inclure le mode d'accès et le pointeur de position courante.

Lorsque le fichier est fermé, on supprime l'entrée de la TDF du processus et on met à jour la TFO. On ne supprimera ce fichier de la TFO que si plus aucun processus n'utilise le fichier.

Implémentation des répertoires

Maintenant, il faut trouver une manière d'implémenter les répertoires de manière que leur gestion puisse être rapide et qu'il soit facile de retrouver l'information.

Plusieurs méthodes sont possibles, mais le choix dépendra de si on souhaite favoriser la rapidité ou l'espace disque.

Il faut donc pouvoir gérer le fait qu'un dossier peut contenir un autre dossier aussi bien que des fichiers.

Pour en savoir plus sur les deux solutions vu ci-dessous, vous pouvez consulter cet article.

Répertoires sous forme de liste

La première solution est simplement de considérer chaque répertoire comme une liste contenant les noms des fichiers avec un pointeur vers le début de ces fichiers.

Cela implique donc qu'il faudra faire une recherche séquentielle pour trouver un fichier dans un répertoire, de même cela implique qu'il faudra faire cette même recherche séquentielle pour créer le fichier (pour vérifier si le nom existe) ainsi que pour le marqué comme libéré.

Les inconvénients de cette méthode sont que le parcours séquentiel ralenti considérablement l'utilisation. Si on décide de faire une liste triée, le problème sera toujours là, car il faudra toujours maintenir la liste triée.

Note sur la libération de l'espace

Marquer l'espace comme libéré consiste à marquer l'entrée du répertoire comme inutilisée.

Il est important de se rappeler que lorsqu'on supprime un fichier ou un dossier, ce dernier n'est pas réellement supprimé, l'espace est simplement marqué comme étant libre. Il est donc tout à fait faisable de récupérer ces informations si on lit séquentiellement les espaces libres. Pour supprimer définitivement un fichier, on peut utiliser la commande shred

Répertoires sous forme de table hashée

L'idée de cette deuxième solution est d'avoir une liste d'éléments, mais avec en plus une table de hash donnant directement le pointeur du fichier.

Ainsi, lorsque l'on cherche un fichier avec un certain nom, on va hasher le nom du fichier, ce qui va nous donner la clé dans la table. Ensuite, on va pouvoir trouver le pointeur vers le fichier directement en la récupérant depuis la table avec la clé.

Cette méthode a l'avantage d'être très rapide, car il n'y a pas besoin de parcourir quoi que ce soit pour trouver les fichiers. Il est toute fois important de noter qu'il faut trouver des solutions pour traiter les cas où plusieurs noms arriveraient au même hash (collision).

Un désavantage de cette méthode est que les tables hashées ont généralement une table fixe et que la performance de la fonction de hash est aussi dépendante de la taille de la table. C'est pourquoi il faut soit limiter la taille du dossier, ou bien étendre la table lorsqu'elle est pleine.

Allocation des fichiers

Maintenant, il va falloir trouver un moyen d'allouer efficacement les fichiers le plus rapidement possible.

On va parler ici de trois méthodes couramment utilisées, la méthode utilisée dépend du système d'exploitation.

Allocation contiguë

L'allocation contiguë signifie que chaque fichier occupe des blocs qui se suivent sur le disque. Ainsi, si quand un bloc est en cours de lecture, la lecture du bloc suivant ne requiert pas de mouvement de la tête de lecture, ce qui offre donc une performance intéressante.

Également, si on sait combien de blocs occupe le fichier et que l'on sait la position de son premier bloc, on peut calculer la position du dernier bloc du fichier, ainsi cela fait un accès séquentiel et direct, facile et rapide.

Problèmes

Le souci avec l'allocation contiguë est que l'on va se retrouver avec des problèmes de fragmentation externe à cause des allocations et libérations successibles. Pour résoudre ce problème, il faut donc utiliser le compactage (la défragmentation). C'est une opération qui peut être dangereuse si elle est interrompue ainsi que chronophage.

Un deuxième problème est de déterminer la taille initiale du fichier, car les fichiers ont tendance à croitre avec le temps. Si un fichier est suivi directement par un autre fichier, que faire si on veut faire croitre le fichier A ?

Si on veut copier le fichier à un autre endroit, cela va rendre le système beaucoup plus lent.

Si on prévoit un "buffer" pour permettre au fichier de croire, alors ça nous mène à de la fragmentation interne et externe.

Résolution du problème de la fragmentation sous Linux

Pour régler ces problèmes, cependant Linux (avec ext4) utilise une variante. À la place de placer chaque fichier à la suite des autres. Les fichiers sont éparpillés sur le disque de manière à maximiser les espace entre eux.

De cette manière, on s'assure que les fichiers ont toujours suffisamment de place pour grandir et quand les fichiers sont trop rapprochés, le système d'exploitation va les réarranger pour les espacer à nouveau.

Grâce à cette technique, la défragmentation est presque entièrement inutile sous Linux, car le taux de fragmentation reste toujours très bas.

Si vous voulez en savoir plus, vous pouvez consulter cet article Wikipedia sur ext4 ou cet article comparant la fragmentation sous Linux et Windows.

Allocation chainée

L'allocation chainée consiste à ce que chaque fichier soit une liste de blocs chainés entre eux. Ainsi, le répertoire contient un pointeur vers le premier bloc de la liste et chaque bloc contient un lien vers le bloc suivant.

Cela a l'avantage de ne pas avoir de fragmentation externe et le fichier peut croitre sans problème puis ce que le bloc peut être écrit n'importe où.

Problème

Le problème de cette méthode est que le contenu des fichiers va être éparpillé partout, la tête de lecture va donc devoir beaucoup voyager et donc ralentir la lecture et l'écriture.

Pour résoudre ce problème, le système FAT alloue des groupes de blocs (cluster) plus tôt que des blocs. Le problème toute fois avec cette méthode, c'est que cela crée de fragmentation interne si les clusters ne sont pas utilisés complètement.

Allocation indexée

Le principe de l'allocation indexée est de garder un bloc "index" pour chaque fichier. Le bloc va contenir les informations des positions de tous les autres blocs du fichier.

L'avantage principal de l'allocation indexée est qu'elle permet un accès direct aux différents blocs utilisés dans le fichier. Cela permet donc un accès au fichier beaucoup plus rapide si on veut accéder à un point précis.

Problème

Un problème avec cette méthode est que l'on ne sait pas d'avance la taille nécessaire de l'index. Ainsi, on peut soit lier les index entre eux (via une liste chainée) ou alors utiliser des index d'index (index à plusieurs niveaux).

Un autre problème est que cela empire le problème de tête de lecture de l'allocation chainée, car il faudra, en plus de devoir passer sur tous les blocs éparpillés, passer sur tous les blocs d'index.

Également, pour les très petits fichiers (2 ou 3 blocs), l'allocation indexée garde un bloc complet pour l'index, ce qui est donc beaucoup moins efficace au niveau de l'utilisation du disque.

Quelle méthode d'allocation choisir ?

La méthode d'allocation à choisir dépends donc de la façon dont le système sera utilisé, car chaque méthode montre des différences (niveau temps, gaspillage, etc) comme nous l'avons vu juste avant.

Une idée est donc de permettre différents types d'allocations différentes ou de mêler plusieurs méthodes.

Par exemple, certains systèmes utilisent l'allocation contiguë pour les petits fichiers et l'allocation indexée pour les fichiers plus gros ou grandissent.

Gestion de l'espace libre

Nous avons vu précédemment le fonctionnement de la gestion de l'allocation, cependant pour faire cela, il faut prendre un bloc libre et l'utiliser. Il faut donc avant tout trouver un moyen de trouver un bloc libre.

On peut donc utiliser les mêmes méthodes que celles utilisées pour la gestion de mémoire. C'est-à-dire l'utilisation de table de bits ou de liste chaînées.

En utilisant une table de bits (ou bitmap en anglais), on va garder une table qui mentionne pour chaque bloc s'il est libre ou occupé. L'avantage est que cette méthode est assez simple et efficace. En revanche, le désavantage est que pour des gros volumes cette table va prendre beaucoup de place. Par conséquent, cette méthode est intéressante pour des volumes faibles, mais devient embêtante pour des volumes plus grands.

L'autre solution est d'utiliser une liste chainée, ainsi chaque bloc libre connait le bloc libre suivant. On peut également faire en sorte de grouper les blocs libre de manière à pouvoir les allouer plus rapidement sans devoir tous les parcourir un à un.

ext2 (précurseur de ext3 et ext4) utilisait une liste chainée pour stocker les blocs libres. Cependant, cela menait à plus de fragmentation, car les fichiers étaient collés les un aux autres (voir Résolution du problème de la fragmentation sous Linux pour comprendre pourquoi).

Ensuite ext3 a commencé à utiliser une table de bit. Cependant, ce système faisait les choses bloc par bloc, alors ext4 a remplacé ce système par un nouveau qui fait plusieurs blocs d'un coup ce qui améliore drastiquement les performances. De plus, ext4 est optimisé de manière à séparer les allocations pour éviter la fragmentation.

Restauration des données

Vérification et correction

Le système de fichier peut devenir incohérent et des erreurs peuvent apparaitre à cause d'arrêt inattendu du système ou encore de problèmes matériels. C'est pour ces raisons que le système d'exploitation doit mettre en place des mécanismes pour vérifier la cohérence du système et corriger les erreurs.

La vérification consiste à parcourir les différents blocs des différents fichiers et à résoudre les problèmes qui pourraient survenir, par exemple :

Sauvegarde et restauration

La sauvegarde consiste souvent en la copie de donnée, ailleurs. Elle est prévue pour une restauration rapide.

L'archivage consiste à sauvegarder des données plus longtemps, dans quel cas il faut également faire attention au média utilisé pour qu'il soit fiable, éprouvé, robuste et durable.

Il y a deux types de sauvegardes, les sauvegardes incrémentales et différentielle.

La sauvegarde incrémentale consiste à seulement sauvegarder les changements. Par exemple, la première fois, on fait une sauvegarde complète, la deuxième fois, on fait une sauvegarde de ce qui a changé depuis la première fois, et la troisième fois, on fait une sauvegarde de ce qui a changé depuis la deuxième fois.

La sauvegarde différentielle consiste à ne copier que les modifications ayant changé depuis la dernière sauvegarde complète. Par exemple, la première fois, on fait une sauvegarde complète, la deuxième fois, on fait une sauvegarde de ce qui a changé depuis la première fois, la troisième fois, on fait une sauvegarde de ce qui a changé depuis la première fois (ce qui inclut donc une redondance de ce qui était dans la deuxième sauvegarde), etc.

La taille de la sauvegarde différentielle va donc beaucoup plus augmenter que celle de la sauvegarde incrémentale, jusqu'à la prochaine sauvegarde complète.

La sauvegarde incrémentale est donc plus légère et plus rapide, mais sera plus complexe à restaurer (car s'il y a eu 17 sauvegarde, il faudra restaurer les 17 éléments) tandis qu'avec la sauvegarde différentielle, il suffira de restaurer la dernière sauvegarde complète et la dernière sauvegarde différentielle.

Système de fichiers journalisé

Le système de fichier est quelque chose de complexe et sa manipulation nécessite beaucoup d'opérations. Un problème peut arriver n'importe quand et si l'opération en cours ne peut pas se terminer, alors cela peut mener à un état incohérent dont la correction pourrait engendrer une perte de donnée.

Le système de fichier journalisé permet de limiter les dégâts en gardant un historique des opérations en cours, de cette manière le système peut défaire les opérations non terminées en cas de panne.

C'est un système qui est assez similaire à celui des transactions en base de données, il faut donc garantir l'atomicité (le fait qu'une action ne puisse pas être décomposée), la cohérence, l'isolation et la durabilité (ACID) pour chaque action du journal.