# Les systèmes d'exploitation/Les systèmes de fichiers

Le système de fichiers est la portion du système d'exploitation qui s'occupe de la gestion des mémoires de masse. Il prend en charge le stockage des fichiers sur le disque dur, le rangement de ceux-ci dans des répertoires, l'ouverture ou la fermeture de fichiers/répertoires, et bien d'autres choses encore.
    La gestion des partitions du disque dur n'implique pas du tout le système de fichier. Le partitionnement est en réalité réalisé avant même toute implication du système d'exploitation, par le BIOS ou l'UEFI.

## Les fichiers

Les données sont organisées sur le disque dur sous la forme de fichiers. Ce sont généralement de simples morceaux d'une mémoire de masse, sur lesquels un programme peut écrire ce qu'il veut. Le système de fichiers attribuent plusieurs caractéristiques à chaque fichier.
* Chaque fichier reçoit un nom de fichier, qui permet de l'identifier et de ne pas confondre les fichiers entre eux. L'utilisateur peut évidemment renommer les fichiers, choisir le nom des fichiers, et d'autres choses dans le genre.
* En plus du nom, le système d'exploitation peut mémoriser des informations supplémentaires sur le fichier : la date de création, la quantité de mémoire occupée par le fichier, et d'autres choses encore. Ces informations en plus sont appelées des attributs de fichier.
* Il existe des normes qui décrivent comment les données doivent être rangées dans un fichier, suivant le type de données à stocker : ce sont les formats de fichiers. Le format d'un fichier est indiqué à la fin du nom du fichier par une extension de fichier. Généralement, cette extension de nom commence par un ".", suivi d'une abréviation. Par exemple, le .JPEG, le .WAV, le .MP3 ou le .TXT sont des formats de fichiers. Ces formats de fichiers ne sont pas gérés par le système d'exploitation. Tout ce que peut faire l'OS, c'est d'attribuer un format de fichier à une application : il sait qu'un .PDF doit s'ouvrir avec un lecteur de fichiers .PDF, par exemple.

### Les clusters

Pour rappel, toutes les mémoires de masse sont découpées en secteurs de taille fixe, qui possèdent tous une adresse (pour plus d'information le livre portant sur le fonctionnement d'un ordinateur peut être utile: Les mémoires de masse : généralités). Les systèmes de fichiers actuels ne travaillent pas toujours sur la base des secteurs, mais utilisent des clusters, des groupes de plusieurs secteurs consécutifs. L'adresse d'un cluster est celle de son premier secteur. La taille d'un cluster dépend du système de fichiers utilisé, et peut parfois être configuré. Par exemple, Windows permet d'utiliser des tailles de clusters comprises entre 512 octets et 64 kibioctets.
La taille idéale des clusters dépend du nombre de fichiers à stocker et de leur taille. Pour de petits fichiers, il est préférable d'utiliser une taille de cluster faible, alors que les gros fichiers ne voient pas d'inconvénients à utiliser des clusters de grande taille. En effet, un fichier doit utiliser un nombre entier de clusters. Illustrons la raison par un exemple. Si un fichier fait 500 octets, il utilisera un cluster complet : seuls les 500 premiers octets seront utilisés, les autres étant tout simplement inutilisés tant que le fichier ne grossit pas. Si le cluster a une taille de 512 octets, seuls 12 octets seront gâchés. Mais avec une taille de cluster de 4 kibioctets, la grosse majorité du cluster sera inoccupé. La même chose a lieu quand les fichiers prennent un faible nombre de clusters. Par exemple, un fichier de 9 kilooctets n'utilisera pas d'espace inutile avec des clusters de 512 octets : le fichier utilisera 18 clusters au complet. Mais avec une taille de clusters de 4 Kio (kibioctets), trois clusters seront utilisés, dont le dernier ne contiendra qu'1 Kio de données utiles, 3 Kio étant gâchés.
En comparaison, le débit en lecture et écriture sera nettement amélioré avec des clusters suffisamment gros. Pour comprendre pourquoi, il faut savoir que le débit d'un disque dur est le produit de deux facteurs : la taille d'une unité d'allocation (ici, un cluster) multiplié par le nombre d'opérations disque par secondes. Ces opérations disque correspondent à une lecture ou écriture de cluster. Chaque opération d'entrée-sortie utilise un peu de processeur, vu qu'il s'agit d'un appel système. Cela peut se résumer par la formule suivante, avec D le débit du HDD (Hard Data Disk ou disque dur en français), IOPS le nombre d'opérations disque par secondes, et $T_{cluster}$ la taille d'un cluster : $D=IOPS\times T_{cluster}$. Pour un débit constant, augmenter la taille d'un cluster diminue le nombre d’opérations disque nécessaires. Le débit maximal est donc plus stable, beaucoup de disques durs ayant une limite au nombre d’opérations disque qu'ils peuvent gérer en une seconde. Expérimentalement, on constate que le débit en lecture ou écriture est meilleur avec une grande taille de cluster, du moins pour des accès à de gros fichiers, dont la lecture/écriture demande d’accéder à des secteurs/cluster consécutifs.

### L'allocation des clusters

Le système d'exploitation doit mémoriser pour chaque fichier, quels sont les clusters du HDD qui correspondent au fichier (leur adresse). Cette liste de clusters est stockée dans une table de correspondance, située au tout début d'une partition du disque dur : la Master File Table. Le partitionnement d'un disque dur permet de découper une unique mémoire de masse en plusieurs portion de mémoire. Chaque portion/partition étant une mémoire proprement dit, du point de vue du système d'exploitation. La Master File Table (MFT) contient, pour chaque fichier, son nom, ses attributs, ainsi que la liste de ses clusters. Avec un système de fichiers de ce type, chaque partition est décomposée en trois morceaux :
* le secteur de boot proprement dit, qui contient le chargeur de système d'exploitation (voir le chapitre suivant) ;
* la Master File Table, qui contient entre autre la liste des clusters de chaque fichier ;
* et enfin, les fichiers et répertoires contenus dans le répertoire racine.
Reste que lors de la création ou de l'agrandissement d'un fichier, l'O.S doit lui allouer un certain nombre de clusters. Pour cela, il existe diverses méthodes d'allocation.
La première méthode est celle de l'allocation contiguë. Elle consiste à trouver un bloc de clusters consécutifs ayant une capacité suffisante pour y stocké l'ensemble du fichier. Repérer un fichier sur le disque dur demande simplement de mémoriser l'adresse du premier cluster, et le nombre de clusters utilisés. Cette méthode a de nombreux avantages, notamment pour les performances des lectures et des écritures à l'intérieur d'un fichier (préchargement, écriture en rafale, etc). C'est d'ailleurs la voie royale pour le stockage de fichiers sur les CD/DVD, où les fichiers sont impossible à supprimer. Mais sur les disques durs, les choses changent. À force de supprimer ou d'ajouter des fichiers de taille différentes, on se retrouve avec des blocs de clusters vides, coincés entre deux fichiers proches. Ces clusters sont inutilisables, vu que la plupart des fichiers à stocker sont trop gros pour rentrer dedans. Une telle situation est ce qu'on appelle de la fragmentation interne. Le seul moyen pour récupérer ces blocs est de compacter les fichiers, pour récupérer l’espace libre : c'est l'opération de défragmentation (similaire à celle du chapitre précédant).
Sur d'autres systèmes de fichiers, les clusters d'un fichier ne sont donc pas forcément consécutifs sur le disque dur. Le système d'exploitation doit garder, pour chaque fichier, la liste des clusters qui correspondent à ce fichier. Cette liste est ce qu'on appelle une liste chaînée : chaque cluster indique quel est l'adresse du cluster suivant (un pointeur, autrement dit). L'accès à un fichier se fait cluster par cluster. L'accès à un cluster bien précis demande de parcourir le fichier depuis le début, jusqu'à tomber sur le cluster demandé. Avec cette méthode, la défragmentation reste utile sur les HDD, vu que l'accès à des secteurs consécutifs est plus rapide. On parle d'allocation par liste chaînée.
On peut améliorer la méthode précédente, en regroupant toutes les correspondances (adresse du cluster courant -> adresse du cluster suivant) dans une table en mémoire RAM. Cette table est appelée la FAT, pour File Allocation Table. Avec cette méthode, l'accès aléatoire est plus rapide : parcourir cette table en mémoire RAM, est plus rapide que de parcourir le disque dur. Malheureusement, cette table a une taille assez imposante pour des disques durs de grande capacité : pour un disque dur de 200 gibioctets, la taille de la FAT est de plus de 600 mébioctets. On parle d'allocation indexée, ou allocation par FAT.
Une autre méthode consiste à ne pas stocker les correspondances (adresse du cluster courant -> adresse du cluster suivant), mais simplement les adresses des clusters les unes à la suite des autres dans une table : on obtient ainsi un i-nœud. C'est cette méthode qui est utilisée dans les systèmes d'exploitation UNIX et leurs dérivés (Linux, notamment). Sous Linux, chaque i-noeud a une table des adresses de cluster d'une taille limitée. Pour gérer des fichiers de taille arbitraire, il est possible d'utiliser plusieurs tables d'i-nœuds par fichier. Ces tables sont reliées sous la forme d'une liste chaînée, chaque table d'i-nœud indiquant l'adresse de la suivante dans la partition. Dans certains cas extrêmes, cette organisation en liste chaînée disparaît au profit d'une organisation partiellement arborescente, certaines tables contenant plusieurs pointeurs vers les tables suivantes (tables doublement indirectes).

## Les répertoires

Sur les premiers systèmes d'exploitation, on ne pouvait pas ranger les fichiers : tous les fichiers étaient placés sur le disque dur sans organisation. De nos jours, tous les systèmes d'exploitation gèrent des répertoires. Ceux-ci sont représentés sur le disque dur par des fichiers, qui contiennent des liens vers les fichiers contenus dans le répertoire. Le fichier répertoire mémorise aussi toutes les informations concernant les fichiers : leur nom, leur extension, leur taille, leurs attributs, etc. Ces informations sont rarement stockées dans le fichier lui-même. Ainsi, quand vous ouvrez un répertoire ou que vous consultez les propriétés d'un fichier, ce fichier n'est jamais ouvert : ces informations sont récupérées dans le répertoire.

### Le codage des répertoires

Un répertoire contient une liste de fichier. Pour chaque fichier, il mémorise son nom, ses attributs, ainsi que la liste des clusters qui lui sont attribués. Les attributs sont stockés dans une structure de taille fixe, le nombre des attributs par fichier étant connu à l'avance. Mais la liste des clusters et les noms des fichiers n'ont pas de taille fixée à l'avance. Cela ne pose pas de problème pour la liste des clusters, contrairement à ce qu'on a pour les noms. Généralement, les répertoires mémorisent les noms des fichiers qu'ils contiennent, avec leurs attributs. Ceux-ci sont donc placées dans un bloc de taille fixe, un en-tête.
La gestion des noms de fichiers peut se faire de plusieurs manières. Avec la première méthode, on limite la taille des noms de fichiers. On peut alors réserver une taille suffisante dans le fichier répertoire pour stocker ce nom. Par exemple, sur les premiers systèmes de fichiers FAT, les noms de fichiers étaient limités à 8 caractères (plus 3 pour l'extension de fichier). Le répertoire allouait 8 octets pour chaque nom de fichier, plus 3 octets pour l'extension. La taille utilisée était alors limitée. Cette méthode, bien que simple d'utilisation, a tendance à gâcher de la mémoire si de petits noms de fichiers sont utilisés. De plus, les utilisateurs pourront se sentir limités par la taille maximale des noms de fichier.
On peut aussi utiliser des noms de fichiers de taille variable. La solution la plus simple consiste à placer ceux-ci à la suite de l'en-tête (qui contient les attributs). Cette méthode a cependant un désavantage lors de la suppression du fichier : elle génère de la fragmentation assez facilement. Si les en-têtes sont consécutifs dans le fichier de répertoire. La suppression de l'en-tête entraînera la suppression du nom de fichier qui va avec, et cette mémoire libre se retrouve alors potentiellement entre deux en-têtes. Plus le nom de fichier sera grand, plus il y aura de fragmentation donc. Pour éviter cela, on peut placer les noms de fichier de taille variable à la fin du fichier répertoire (en dehors des en-têtes), chaque en-tête pointant vers le nom de fichier adéquat (comme le fait Linux).

### La hiérarchie de répertoires

Sur les premiers systèmes d'exploitation, tous les fichiers étaient placés dans un seul et unique répertoire. Quand le nombre de fichier était relativement faible, cela ne posait pas trop de problèmes. L'avantage de cette méthode était que le système d'exploitation était plus simple et qu'il n'avait pas à gérer une arborescence de répertoire sur le disque dur. Mais l'inconvénient se faisait sentir quand les fichiers devenaient de plus en plus nombreux. Cette organisation est encore utilisée sur les baladeurs et appareils photo numériques.
De nos jours, les répertoires sont organisés en une hiérarchie de répertoire : un répertoire peut contenir d'autres répertoires, et ainsi de suite. Évidemment, cette hiérarchie commence par un répertoire maître, tout en haut de cette hiérarchie : ce répertoire est appelé la racine. Sous Windows, on trouve une seule et unique racine par partition ou disque dur : on en a une sur C : , une autre sur D : , etc. Sous Linux, il n'existe qu'une seule racine, chaque partition étant un répertoire accessible depuis la racine : ces répertoires sont appelés des points de montage. Sur Windows, ce répertoire est noté : soit \, soit nom_lecteur : \ (C:\, D:\). Sous Linux, il est noté : / .
Reste que savoir où se trouve un fichier demande de préciser quel est le chemin qu'il faut suivre en partant du répertoire maître : on doit préciser qu'il faut ouvrir tel répertoire, puis tel autre, et ainsi de suite jusqu’au fichier. Ce chemin, qui reprend le chemin de la racine jusqu’au fichier, est appelé le chemin d'accès absolu. Sous Windows, les noms de répertoires sont séparés par un \ : C:\Program Files\Internet Explorer. Sous Linux, les noms de répertoires sont séparés par un / : /usr/ast/courrier. Les chemins d'accès relatifs sont similaires, sauf qu'ils ne partent pas de la racine : ils partent d'un répertoire choisit par l'utilisateur, nommé répertoire courant. Dans les grandes lignes, l'utilisateur ou un programme choisissent un répertoire et lui attribuent le titre de répertoire courant. Généralement, chaque processus a son propre répertoire de travail, qu'il peut changer à loisir. Pour cela, le programme doit utiliser un appel système, chdir sous Linux.
Linux a une particularité : il normalise la place de certains répertoires bien précis du système d'exploitation. L'arborescence des répertoires est en effet standardisé par le Filesystem Hierarchy Standard, la dernière version datant de juin 2015.