Systèmes de stockage de données

Le dernier composant d’un ordinateur que nous analysons sont les dispositifs permettant de stocker des données et des programmes. De nombreuses technologies ont étés utilisées au fil des années pour stocker de l’information et des programmes de façon à ce que ces informations puissent être réutilisées après un redémarrage de l’ordinateur ou sur un autre ordinateur. Contrairement à la mémoire RAM, ces systèmes peuvent conserver l’information stockée même lorsque l’ordinateur est déconnecté du réseau électrique. Ces systèmes utilisent des technologies très variées pour stocker l’information. Une description détaillée de toutes ces technologies sort du cadre de ce syllabus.

Les plus anciennes technologies sont les cartes perforées. Ces cartes sont antérieures aux premiers ordinateurs puisqu’elles étaient initialement utilisées sur les métiers à tisser, les orgues de barbarie ou les pianos mécaniques. C’est en utilisant de telles cartes perforées que Charles Babbage a pu construire sa machine analytique qui est un ancêtre des ordinateurs.

Une carte perforée est une feuille de papier rigide sur laquelle on encode l’information en y faisant des trous. Ces cartes perforées sont lues par des dispositifs mécaniques ou optiques qui détectent les différents trous. Les cartes perforées courantes avaient 80 colonnes et douze lignes. Ces cartes ont servi jusque dans les années 1970s et 1980s pour soumettre des travaux et des données à des ordinateurs dans des centres de calcul. De nos jours, les cartes perforées ne sont plus utilisées.

De nombreux systèmes de stockage utilisent les propriétés magnétiques ou optiques de la matière pour stocker de l’information. Parmi les systèmes utilisant les propriétés magnétiques, on peut citer :

• les cassettes

• les lecteurs de bandes

• les disques souples (floppy disks)

• les disques durs (hard disks)

Parmi les systèmes utilisant les propriétés optiques de la matière, on peut noter :

• les CDs

• les DVDs

D’autres systèmes plus récents utilisent des dispositifs électroniques pour stocker de l’information. Parmi ces systèmes, on peut citer :

• les cartes mémoires

• les lecteurs SSD

• les mémoires non-volatiles (NVM)

Les informaticiens et informaticiennes interagissent rarement directement avec tous ces dispositifs de stockage. La plupart des programmes s’exécutent dans le cadre d’un système d’exploitation comme Linux, Windows, MacOS, … Ce système d’exploitation est un logiciel spécialisé qui gère l’ensemble de ressources matérielles d’un ordinateur et offre aux programmes applicatifs des abstractions qui leur permettent d’utiliser de la même façon un disque SSD et un CD, même si ces deux dispositifs utilisent des technologies très différentes. Pour cela, les informaticiens et informaticiennes qui ont conçu ces systèmes d’exploitation ont développé des abstractions qui facilitent les opérations de lecture et d’écriture sur des dispositifs de stockage. Vous avez l’habitude d’utiliser des fichiers pour stocker vos données et programmes. Ces fichiers et programmes sont généralement organisés dans des répertoires pour faciliter leur accès et regrouper logiquement les fichiers qui font partie d’un même projet ou d’un même cours. Ces fichiers et ces répertoires sont des abstractions qui ont été introduites par les informaticiens et informaticiennes qui ont construit ces systèmes d’exploitation.

Les répertoires et fichiers sont regroupés dans ce que l’on appelle en informatique un système de fichiers. Un système de fichiers est un ensemble de répertoires et de fichiers qui sont stockés sur un ou plusieurs dispositifs de stockage. Un répertoire est un ensemble contenant zéro, un ou plusieurs autres répertoires, zéro, un ou plusieurs autres fichiers. Dans un système de fichiers, les répertoires sont organisés sous la forme d’un arbre. Cet arbre commence par un répertoire spécial appelé la racine. Cette racine contient un ou plusieurs autres répertoires et parfois des fichiers. Chacun de ces répertoires, et tous les autres répertoires du système de fichiers, a un répertoire parent. Le seul répertoire qui n’a pas de parent est le répertoire qui se trouve à la racine du système de fichiers et s’appelle le répertoire racine.

Un fichier est simplement une séquence d’octets qui est identifié par un nom. Un fichier contient généralement un nombre positif d’octets, mais il est possible d’avoir des fichiers vides qui ne contiennent aucun octet. Un système d’exploitation associé généralement à un fichier des métadonnées comme sa date de création ou de dernière modification, des permissions, des informations sur le propriétaire, … Les métadonnées associées à un fichier peuvent varier d’un système d’exploitation à l’autre.

Les systèmes d’exploitation permettent aux logiciels d’accéder aux données qui sont stockées dans les fichiers à l’intérieur des répertoires. Chaque système d’exploitation contient des fonctions qui permettent aux applications d’accéder simplement au contenu des fichiers. A titre d’exemple, python fournit différentes fonctions qui permettent de manipuler les fichiers et répertoires. Avant de pouvoir utiliser un fichier, un programme doit l’ouvrir en utilisant la fonction open(). Lors de l’appel à cette fonction, le système d’exploitation vérifie notamment si le fichier existe et si le programme dispose des permissions nécessaires pour accéder au fichier. Les fonctions les plus connues pour accéder à un tel fichier sont read() et write(). Ces deux fonctions accèdent au fichier de façon linéaire. Lorsque un programme ouvre un fichier, le système d’exploitation associe à ce fichier ouvert une « tête de lecture ». Cette « tête de lecture » est un entier qui indique la position du fichier à laquelle la prochaine opération read() et write() sera réalisée. A l’ouverture du fichier, la « tête de lecture » indique le début du fichier (c’est-à-dire la position 0). Après avoir lu n octets, cette « tête de lecture » vaut n et référence donc le n+1 ième octet du fichier. Si le programme appelle la fonction write() à ce moment, les données seront écrites à partir du n+1 ième octet. Outre les fonctions read() et write(), python supporte des fonctions qui permettent de modifier directement la tête de lecture associée à un fichier ouvert. C’est notamment le cas de la fonction seek() qui permet de déplacer la « tête de lecture » de façon absolue ou relative. Pour la lecture de fichiers contenant du texte, la fonction seek() est peu utilisée. Par contre, seek() est très importante pour des logiciels qui doivent manipuler des fichiers contenant des images, des sons ou même des bases de données. Un système de fichier doit pouvoir fournir un support efficace aux applications qui accèdent à des fichiers de façon séquentielle en utilisant read()/write() mais aussi d’autres applications qui combinent ces deux fonctions avec seek() pour un accès direct aux fichiers. En python, le module os fournit différentes fonctions qui permettent d’accéder directement aux répertoires comme os.scandir() par exemple.

Les systèmes d’exploitation utilisent des abstractions qui représentent les caractéristiques des principaux dispositifs de stockage afin de pouvoir utiliser le même code pour manipuler de très nombreux dispositifs. Le logiciel est alors organisés en couches. La couche supérieure expose des structures de données et des fonctions qui correspondent à cette abstraction. L’implémentation de cette couche peut varier d’un dispositif à l’autre, mais l’avantage est que le code de gestion des fichiers et répertoire est le même quel que soit le dispositif de stockage. Nous utiliserons une telle abstraction dans le cadre de ce cours. Les dispositifs de stockage permettent d’écrire ou de lire des blocs d’octets de taille fixe. Un dispositif de stockage contient un nombre fixe de blocs et chaque bloc est identifié par un numéro unique. On pourrait représenter l’utilisation d’un dispositif de stockage par deux fonctions :

def read_block(pos):
  # Lit le contenu du bloc numéro pos et retourne le bloc complet

def write_block(bloc, pos):
  # Remplace le bloc numéro pos avec le bloc passé en argument

Les dispositifs de stockage utilisent différentes tailles de blocs. Plus la capacité de stockage est important, plus la taille des blocs est élevée. Sur un disque souple, les blocs de 512 octets étaient courants. Sur disque dur, les blocs de 4.096 octets sont très souvent utilisés. Dans le cadre de ce cours, nous représenteront un dispositif de stockage sous la forme d’une grille. Chaque cellule de la grille correspond à un bloc. Notre modèle de dispositif de stockage est illustré dans la figure ci-dessous. Chaque cellule correspond à un bloc et il contient le numéro du bloc.

Fig. 131 Modèle d’un dispositif de stockage

Dans un dispositif de stockage réel, seuls certains blocs sont utilisés pour stocker les fichiers et les répertoires. Les blocs du début du système de stockage sont généralement utilisés pour stocker des paramètres du système de fichier. Dans les exemples qui suivent, nous réserverons les dix premiers blocs à cette utilisation. En pratique, le nombre de ces blocs « spéciaux » varie d’un système de fichiers à l’autre. Généralement, le ou les premiers blocs d’un système de stockage sont utilisés pour placer le programme d’amorçage, c’est-à-dire le code qui est chargé automatiquement au lancement de l’ordinateur et qui charge généralement le système de stockage. Dans nos exemples, nous réservons les deux premiers blocs du système de stockage à cette utilisation. Ils seront représentés en rouge dans les figures.

Les systèmes de fichiers sont organisés sous la forme d’un arborescence comme illustré en Fig. 132. Les rectangles représentent des fichiers tandis que les rectangles arrondis sont les répertoires. Le premier répertoire est considéré comme la racine du système de fichiers. Il contient parfois quelques fichiers, mais souvent des répertoires. Chacun de ces répertoires peut lui-même contenir des fichiers et/ou des répertoires. Dans le cadre de ce chapitre, nous utiliserons une arborescence simple pour illustrer les différentes notions. Cette arborescence est reprise dans la figure ci-dessous avec pour chaque fichier l’indication de sa taille en octets.

Fig. 132 Arborescence des répertoires et fichiers

Ce système de fichiers contient un fichier (f1) et trois répertoires (bin, tmp et lib) dans le répertoire racine. Le sous-répertoire bin contient deux fichiers (sh et echo). Le sous-répertoire lib ne contient ni fichier si sous-répertoire. Le sous-répertoire tmp contient un fichier (file) et un répertoire (rep). Le sous-répertoire rep contient un sous-répertoire nommé sub qui contient lui-même un fichier nommé file. Dans un système de fichiers, il est possible (et même fréquent) d’avoir différents fichiers et/ou répertoires qui ont le même nom mais se trouvent à des endroits différents de l’arborescence. C’est possible car pour le système de fichiers, le nom d’un fichier ou d’un répertoire est toujours son nom complet depuis la racine.

Code source 15 Noms complets des fichiers du système de fichiers d’exemple

/  (répertoire racine)
/bin (répertoire)
/bin/sh (fichier, 2400 octets)
/bin/echo (fichier, 600 octets)
/tmp (répertoire)
/tmp/file (fichier, 0 octet)
/tmp/rep (répertoire)
/tmp/rep/sub (répertoire)
/tmp/rep/sub/file (fichier, 123 octets)
/lib (répertoire)
/f1 (fichier, 600 octets)

Dans l’exemple ci-dessus, nous avons utilisé le caractère / pour séparer les noms de sous-répertoire et de fichiers. C’est la convention qui est utilisée par les systèmes de fichiers dérivés du systèmes d’exploitation Unix. D’autres systèmes d’exploitation utilisent d’autres conventions. Par exemple, les systèmes d’exploitation produits par Microsoft utilisent plutôt le caractère \. La convention utilisée importe peu, par contre elle implique que le caractère qui est utilisé comme séparateur ne peut pas se trouver à l’intérieur d’un nom de répertoire ou de fichier.

Il existe un très grand nombre de systèmes de fichiers. Une page wikipedia dédiée aux systèmes de fichiers en liste plusieurs dizaines. Nous nous concentrerons sur deux exemples importants :

• le système de fichiers FAT utilisé par le système d’exploitation MSDOS

• le système de fichiers étendu utilisé par le système d’exploitation Linux

Ces deux systèmes de fichiers ont une structure assez différente et ils ont tous les deux étés largement déployés. L’objectif principal de ces deux systèmes de fichiers est de stocker les fichiers, les répertoires mais aussi l’arborescence qui représente le système de fichiers sur un dispositif de stockage composé de blocs.

La partie la plus simple dans le design d’un système de fichiers est le stockage des fichiers. Dans notre exemple, nous avons cinq fichiers à stocker :

• /bin/sh (fichier, 2400 octets)

• /bin/echo (fichier, 600 octets)

• /tmp/file (fichier, 0 octet)

• /tmp/rep/sub/file (fichier, 123 octets)

• /f1 (fichier, 600 octets)

Si l’on suppose que le système de fichiers utilise des blocs de 512 octets, le premier fichier, /bin/sh occupera 5 blocs, /bin/echo en occupera 2, /tmp/file n’en occupera aucun, /tmp/rep/sub/file utiliser 1 bloc et enfin les données de /f1 nécessiteront deux blocs sur le système de fichiers. Pour simplifier la comparaison des deux systèmes de fichiers, nous supposerons que les dix blocs qui contiennent les données de ces fichiers seront stockés dans les blocs numérotés de 30 à 39. La Fig. 133 décrit une organisation possible des blocs contenant les données de ces fichiers. Chaque fichier est composé de blocs qui sont contigus, mais cette contrainte n’est imposée que sur les dispositifs de stockage tels que les CD-ROMs et DVDs où les données sont écrites une seule fois. Dans un système de stockage où des fichiers sont créés, modifiés et supprimés de façon dynamique, les blocs qui composent un fichier ne sont pas nécessairement contigus.

Fig. 133 Blocs contenant les données des fichiers

Fig. 134 Autre organisation possible des blocs contenant les données des fichiers

Sur base de ces exemples, on remarque aisément qu’un fichier correspondant à une séquence d’octets est en fait stocké sur le dispositif de stockage comme une liste de blocs. Ainsi, dans l’exemple de la Fig. 134, le fichier /bin/sh est composé du bloc 39 suivi du bloc 35 puis du bloc 36 puis du bloc 33 et enfin du bloc 38. Le fichier /bin/echo correspond lui au bloc 31 suivi du bloc 32. Le fichier /f1 débute lui par le bloc 34 et se termine par le bloc 30. La liste correspondant à chaque fichier évolue à chaque fois que l’on modifie les fichiers, notamment lors des créations, suppressions et des ajouts de données dans des fichiers. La figure Fig. 135 représente graphiquement les listes chaînées qui correspondent à ces différents fichiers.

Fig. 135 Liste chaînée et autre organisation des blocs contenant les données des fichiers

Le système de fichiers doit stocker les listes ordonnées correspondant à chacun de ces fichiers. Ces listes doivent se trouver sur le dispositif de stockage car elles doivent pouvoir être lues par l’ordinateur. Une première possibilité serait d’ajouter à l’intérieur de chaque bloc le numéro de son successeur dans la liste et -1 en fin de fichier. Pour cela, il faudrait réserver une partie du bloc pour stocker le numéro du bloc suivant. Si les blocs ont une capacité de 512 octets, on pourrait par exemple réserver 4 octets pour encoder le numéro du bloc suivant. Une telle organisation est représentée dans Fig. 136.

Fig. 136 Ajout d’une référence vers le bloc suivant dans chaque bloc

Malheureusement, cette approche souffre de plusieurs problèmes. Tout d’abord, elle réduit la taille des blocs. Un bloc contient \(k\) octets de moins où \(k\) est le nombre d’octets nécessaire pour encoder un numéro de blocs (typiquement 4 pour un disque dur). De plus, en stockant la liste chaînée directement dans les blocs, on force le système de fichiers à lire tous les blocs qui composent un fichier pour pouvoir y faire des accès directs. Considérons un fichier qui est édité par l’utilisateur ou créé par un programme. Lorsque la taille de ce fichier grandit, le système de fichiers doit allouer un nouveau bloc au fichier et l’ajouter à la liste chaînée. Si le fichier rétrécit suite à une opération d’édition, le système de fichiers va devoir « remonter » la liste chaînée pour retrouver les blocs à retirer. Cela peut nécessiter de reparcourir tout le fichier depuis son premier bloc ce qui sera coûteux en nombre d’accès au dispositif de stockage. Sur des dispositifs lents comme des disques souples ou durs, cela peut avoir un impact très important au niveau des performances. Pour ces raisons, les systèmes de fichiers ont choisi d’autres astuces pour stocker les listes chaînées qui représentent les différents fichiers et répertoires.

La table d’allocation des fichiers

La table d’allocation des fichiers (File Allocation Table - FAT en anglais) est une table qui permet de stocker de façon compacte toutes les listes chaînées qui représentent tous les fichiers (et répertoires) du système de fichiers.

Fig. 137 Les listes chaînées correspondant à des fichiers peuvent être stockées dans une table d’allocation

Cette table d’allocation représente de façon compacte l’ensemble des listes chaînées qui correspondent à nos quatre fichiers. La Fig. 137 représente à la fois l’index des lignes de la table et le numéro du bloc stocké à chaque ligne. Cette table indique pour le bloc d’index i le numéro du bloc qui le suit dans le fichier auquel il appartient. La valeur de -1 est réservée pour indiquer qu’un bloc est le dernier bloc d’un fichier. On pourrait aussi réserver d’autres valeurs comme par exemple -2 pour indiquer que le bloc n’est actuellement pas utilisé pour stocker des données ou un répertoire ou -3 pour indiquer que le bloc a été marqué comme invalide par le dispositif de stockage et qu’il ne doit donc jamais être utilisé.

Dans la Fig. 137, le fichier /f1 commence par le bloc 34 et se termine au bloc 30. Le fichier /bin/echo commence lui au bloc 31 et se termine au bloc 32. Le fichier /tmp/rep/sub/file n’utilise que le bloc 37. Enfin, le fichier /bin/sh commence au bloc 39 et utilise ensuite les blocs 35, 36 et 33 pour se terminer au bloc 38.

La table d’allocation contient toutes les informations concernant les fichiers. Elle est critique pour pouvoir accéder aux données stockées sur le disque. Elle est stockée directement sur le dispositif de stockage dans une suite de blocs qui sont contigus. Le nombre de blocs nécessaire pour stocker la table d’allocation des fichiers dépend de deux paramètres : la taille du dispositif de stockage (en blocs) et le nombre d’octets utilisés pour encoder les numéros de blocs. La première version du système d’exploitation MS-DOS de Microsoft utilisait 1.5 octets (12 bits) pour identifier chaque bloc. Les dernières versions du système de fichier FAT utilisaient 4 octets (32 bits) pour encoder les numéros de blocs. Dans un bloc de 512 octets, on pouvait donc stocker une table d’allocation des fichiers pour un dispositif comprenant 128 blocs. Dans nos exemples, nous supposerons que l’on utilise cette version du système de fichiers FAT et que la table d’allocation contient 1024 entrées. Si chaque bloc a une capacité de 512 octets, cette table d’allocation peut donc gérer des dispositifs de stockage d’une capacité de 512 Ko. La table d’allocation nécessite 8 blocs consécutifs. Elle est généralement placée dans des blocs dont le numéro est bien connu. Dans notre système de fichier d’exemple, nous avons choisi de la placer dans les blocs 2 à 9.

La table d’allocation est consultée par le système d’exploitation lors de chaque accès à un fichier. Si chaque accès à un fichier devait nécessiter aussi des accès aux blocs qui contiennent la table d’allocation, les performances seraient fortement réduites. En pratique, les systèmes d’exploitation qui utilisent une table d’allocation des fichiers chargent en mémoire une copie de la table d’allocation des fichiers au démarrage. Tous les accès en lecture à la table d’allocation se font directement en mémoire qui est nettement plus rapide que le dispositif de stockage. Par contre, lors des opérations qui modifient la table d’allocation des fichiers, comme la création ou l’édition d’un fichier, cette modification est d’abord effectuée en mémoire et ensuite copiée sur le dispositif de stockage. Cette écriture sur le dispositif de stockage est nécessaire pour pouvoir récupérer le dernier état du système de fichiers si l’ordinateur s’arrêtait à cet instant en raison par exemple d’une panne d’électricité.

Note

La table d’allocation ne peut pas être perdue

La table d’allocation contient toutes les informations concernant les fichiers. Une erreur de lecture dans un des blocs contenant la table d’allocation rendrait inaccessible tous les fichiers affectés par cette erreur. Pour cette raison, les systèmes de fichiers qui utilisent une table d’allocation maintiennent généralement deux copies de cette table de façon à pouvoir parer à toute erreur de lecture. Cela complexifie le système de fichiers puisqu’il faut s’assurer de toujours stocker les mêmes informations dans les deux copies de la table, mais c’est une assurance très utile pour éviter de perdre des données.

Grâce à la table d’allocation des fichiers, nous pouvons stocker sur un dispositif de stockage des fichiers de taille quelconque, mais nous n’avons pas pas encore défini comment stocker les répertoires. Dans un système de fichiers, un répertoire est simplement un fichier ayant un format particulier. Un répertoire peut être vu comme un tableau qui contient plusieurs entrées. Chaque entrée a une structure particulière. A titre d’exemple, considérons le format des répertoires utilisés par MS-DOS version 2.0. Ce système de fichiers utilisait des entrées de répertoires qui sont encodées sur 32 octets. 16 de ces entrées pouvaient donc se trouver dans un bloc de 512 octets. La Fig. 138 présente le format de cette entrée de répertoire.

Fig. 138 Une entrée d’un répertoire MS-DOS

Chaque entrée de répertoire comprend plusieurs informations. Les 8 premiers caractères contiennent le nom du fichier. Ils sont suivis de trois caractères qui contiennent l’extension du nom de fichier. Sous MS-DOS, les trois caractères de l’extension sont utilisés pour indiquer le type de fichier. Ainsi, l’extension .EXE correspond à un programme exécutable, .BAT un script batch, .DOC un document pour le traitement de textes Word. Il faut noter que le caractère . qui sépare le nom de l’extension ne se trouve pas explicitement dans l’entrée d’un répertoire. L’octet Attr (Attribut) contient des bits qui indiquent si l’entrée correspond à un répertoire ou un fichier, si il est accessible en lecture ou en écriture, … Les champs Time et Date indiquent de quand date le fichier. Les deux derniers champs d’un répertoire sont très importants. Le premier, FAT indique le numéro du premier bloc contenant le fichier. Sur base de ce numéro de bloc, le système d’exploitation peut utiliser la table d’allocation des fichiers pour accéder aux autres blocs qui le composent. Le dernier champ est la longueur totale du fichier en octets. Ce champ est nécessaire pour indiquer où le fichier se termine dans le dernier bloc stocké sur le disque comme les fichiers ont rarement une longueur qui est un multiple de la taille des blocs.

Nous pouvons maintenant construire le répertoire racine de notre système de fichiers et voir comment il aurait été stocké en MS-DOS. Celui-ci contient les fichiers et répertoires suivants:

/bin (répertoire)
/tmp (répertoire)
/lib (répertoire)
/f1 (fichier, 600 octets)

Nous devons donc stocker 4 entrées dans ce répertoire. Les trois premières correspondent aux répertoires /bin, /tmp et /lib. La dernière correspond au fichier /f1. L’entrée du répertoire correspondant au fichier f1 aura comme champ FAT le numéro de bloc 34. Nous devons aussi stocker sur le dispositif de stockage le répertoire racine et les trois sous-répertoires /bin, /tmp et /lib. Chaque répertoire est un fichier contenant des entrées de répertoire. Le répertoire racine est un peu particulier car il doit pouvoir être lu au démarrage du système de fichiers. Il est placé par convention dans un bloc dont le numéro est bien connu. Dans notre système de fichiers d’exemple, nous supposons que le répertoire racine commence toujours au bloc 10. Certains systèmes de fichiers de type FAT utilisent un répertoire racine de taille fixe, ce qui limite le nombre de fichiers dans le répertoire racine. D’autres systèmes de fichiers supportent un répertoire racine de taille variable.

Chacun des sous-répertoires du répertoire racine est stocké sous la forme d’un fichier spécial contenant des entrées de répertoire. Le répertoire racine contient donc les champs suivants :

• Name: bin, Attr: répertoire, FAT: 11, Length: 64

• Name: tmp, Attr: répertoire, FAT: 12, Length: 64

• Name: lib, Attr: répertoire, FAT: 13, Length: 0

• Name: f1, Attr: fichier, FAT: 34, Length: 600

Le répertoire /bin ne contient que deux fichiers. Il contient les champs suivants :

• Name: sh, Attr: fichier, FAT: 39, Length: 2400

• Name: echo, Attr: fichier, FAT: 31, Length: 600

Le répertoire lib est vide. Le répertoire tmp contient un fichier et un sous-répertoire, c’est-à-dire :

• Name: file, Attr: fichier, FAT: 0, Length: 0

• Name: rep, Attr: répertoire, FAT: 14, Length: 0

Le sous-répertoire rep contient le sous-répertoire sub :

• Name: sub, Attr: répertoire, FAT: 15, Length: 32

Le dernier répertoire est le répertoire sub qui contient le fichier file de 123 octets :

• Name: file, Attr: fichier, FAT: 37, Length: 123

Nos répertoires sont donc stockés dans les blocs 10 à 15. En pratique, il est fréquent qu’une zone du système de stockage soit réservée aux blocs qui contiennent les répertoires. Cela permet notamment de précharger certains répertoires en mémoire afin d’accélérer les accès aux fichiers ultérieurement. Cela facilite aussi la récupération d’erreurs lorsque l’ordinateur est arrêté avant que le système d’exploitation n’aie pu écrire les dernières modifications au système de fichiers sur le dispositif de stockage.

Grâce aux champs FAT qui se trouvent dans les répertoires, nous avons construit une arborescence de fichiers et de répertoire. Il y a quatre branches qui partent de la racine. Les trois premières correspondent aux répertoires bin, tmp et lib. La quatrième branche est celle du fichier f1. Cette arborescence est illustrée dans la Fig. 138 avec le numéro du premier bloc de chaque fichier ou répertoire.

Fig. 139 Arborescence des répertoires et fichiers

Fig. 140 Le système de fichiers complet et sa table d’allocation des fichiers. La FAT occupe les blocs 2 à 9. Les répertoires sont dans les blocs 10 à 15. Les fichiers occupent les blocs 30 à 39.

Note

Vérification d’un système de fichiers corrompu

Durant son utilisation, un système de fichiers doit pouvoir gérer les lectures et écritures classiques de fichiers et de répertoires et toutes les modifications de blocs qui y sont associées. Il doit aussi pouvoir faire face à des événements inattendus tout en préservant le plus possible les données se trouvant sur le dispositif de stockage. Pour un système de fichiers utilisant une table d’allocation des fichiers, les problèmes les plus pénalisants sont les erreurs de lecture qui rendent un bloc inutilisable et les pannes de courant.

Les inodes

La table d’allocation est une des techniques qui permet de construire un système de fichiers, mais c’est loin d’être la seule. Depuis les années 1970s les systèmes d’exploitation dérivés de Unix (dont Linux, MacOS et Android notamment) utilisent une technique basée sur les inodes. L’origine du nom inode n’est pas clairement établie. Il semble que ce sera la contraction des mots index et node (noeud en français). L’idée intuitive de l’inode est d’y stocker la liste des numéros des blocs qui composent un fichier. On pourrait intuitivement voir l’inode comme une sorte de table des matières des blocs qui composent un fichier.

Un inode est une zone du dispositif de stockage qui contient la liste des blocs qui composent un fichier. A titre d’exemple, considérons le même système de fichiers que celui de la section précédente et supposons que les fichiers sont stockés dans les mêmes blocs. Le fichier /bin/sh est composé des blocs 39, 35, 36, 38 et 33. Ces cinq blocs sont listés dans cet ordre dans l’inode correspondant à ce fichier. Grâce à cet inode, on connaît la position exacte de tous les blocs qui composent le fichier. Il en va de même pour les fichiers f1, /bin/echo et /tmp/rep/sub/file comme illustré dans la Fig. 141.

Fig. 141 Les inodes stockent les listes chaînées correspondant à chaque fichier

A titre d’illustration sur l’utilisation des inodes, considérons le système de fichiers ext2 utilisé dans les premières versions du système d’exploitation Linux. Ce système de fichiers est inspiré des systèmes de fichiers Unix.

Un système de fichiers ext2 est composé d’une suite de blocs. Les premiers blocs sont des blocs de contrôle qui contiennent de l’information sur le système de fichiers et sa structure. La plupart des blocs sont les blocs qui contiennent les données relatives aux fichiers et aux répertoires. Les premiers blocs d’un système de fichiers ext2 contiennent les paramètres principaux du système de fichiers comme la taille des blocs, le nombre d’inodes, … Une description détaillée du contenu du Super Block et des FS descriptors sort du cadre de ce cours. Après ces blocs de contrôle, un système de fichiers ext2 contient deux bitmaps: le bitmap des block et le bitmap des inodes. Ensuite on retrouve la table des inodes. Cette table contient tous les inodes du système de fichiers. Tous les blocs de contrôle sont initialisés lors de la réaction (le formatage) du système de fichiers. La taille des bitmaps, des blocs et de la table des inodes sont fixées à ce moment. Ces tailles ne changeront jamais durant la vie du système de fichiers.

Fig. 142 Un système de fichiers `ext2` contient un superblock, un FS descriptor, un bitmap des blocks, un bitmap des inodes, une table des inodes et des blocs de données

Tout comme pour le système de fichiers utilisant une table d’allocation, commençons par analyser comment les répertoires sont encodés. Nous verrons ensuite plus en détails le contenu des inodes et terminerons par le rôle des deux bitmaps.

Dans le système de fichiers ext2, les entrées d’un répertoire ont une longueur variable. Chaque entrée d’un répertoire comprend quatre informations:

• le numéro de l’inode correspondant au fichier/répertoire sur 32 bits

• un entier sur 16 bits indiquant la longueur en octets de cette entrée du répertoire

• un entier sur 16 bits indiquant la longueur du nom de fichier/répertoire

• une chaîne de caractère contenant le nom du fichier/répertoire

Cette organisation des répertoires permet de supporter les fichiers et répertoires dont le nom contient un nombre quelconque de caractères. Contrairement au système de fichiers MS-DOS le répertoire ne contient pas d’attributs ni d’information sur la longueur des fichiers/répertoires. Dans le système de fichiers ext2, toutes ces informations sont stockées dans les inodes. La Fig. 143 représente cette arborescence avec en gras les inodes associés à chaque fichier/répertoire.

Fig. 143 Arborescence des répertoires et fichiers de notre système `ext2`

Pour comprendre comment cette arborescence est stockée en utilisant le système de fichiers ext2, nous devons décrire plus en profondeur le contenu d’un inode. Dans un système de fichiers ext2, un inode contient différentes informations. Les plus importantes sont les suivantes :

• le mode du fichier/répertoire

• l’identifiant du propriétaire du fichier

• l’identifiant du groupe propriétaire du fichier

• la longueur du fichier (en octets)

• les dates de création, de dernier accès et de dernière modification du fichier

• le nombre de blocs du fichier

• le nombre de liens vers le fichier

• la liste des blocs qui composent le fichier

L’inode ne contient donc pas le nom du fichier. Celui-ci est uniquement spécifié dans le répertoire qui le contient. Le mode indique si il s’agit d’un fichier ou d’un répertoire. Ce champ contient également les attributs telles que les permissions de lecture, d’écriture et d’exécution sur le fichier. Comme Unix et Linux sont des systèmes d’exploitation multi-utilisateurs, l’inode comprend également les identifiants de l’utilisateur et du groupe qui sont propriétaires du fichier. Le système d’exploitation vérifie ces informations pour autoriser ou non une opération de lecture ou d’écriture sur le fichier en fonction des permissions de l’utilisateur qui exécute le programme. La longueur du fichier est spécifiée en nombre de blocs et en octets. La longueur en blocs est utile pour accéder facilement à la liste des blocs tandis que la longueur en octets est nécessaire lorsque le dernier bloc d’un fichier/répertoire est lu. Les dates sont encodées sous la forme d’un entiers de 32 bits qui contient le nombre de secondes depuis le premier janvier 1970. Le champ le plus important de l’inode est la liste des blocs.

Note

Le deuxième bug de l’an 2000

Les premières versions du système d’exploitation Unix datent du début des années 1970s. Quand les concepteurs de Unix ont réfléchi à une technique efficace pour encoder les dates de création des fichiers, ils ont opté pour un entier de 32 bits qui représente le nombre de secondes entre la date courante et une date de référence qu’ils ont arbitrairement fixé au premier janvier 1970. Sur un entier 32 bits, on peut stocker au maximum 4294967296 valeur différentes. En utilisant le premier janvier 1970 comme référence, la date la plus ancienne que l’on peut encoder est le 13 décembre 1901. Malheureusement la date la plus avancé que l’on pourra encoder est le mardi 19 janvier 2038. Les 32 bits du timestamp Unix ne permettent pas d’encoder de date postérieure à cette date. Ce problème est connu par les informaticiens comme étant le problème de l’année 2038. Il fait suite au problème de l’an 2000 où de nombreuses applications informatiques qui encodaient les années sur deux chiffres ont du être adaptées suite au passage du millénaire. Pour résoudre le problème de l’année 2038, il faut éviter d’encoder les timestamps sur 32 bits et préférer un encodage sur 64 bits. Plusieurs systèmes d’exploitation ont déjà fait le pas et mis à jour leurs systèmes de fichiers et autres structures de données.

Les concepteurs des systèmes de fichiers qui utilisent des inodes sont confrontés à une difficulté. D’un côté, il est important que chaque inode soit encodé en utilisant un nombre fixe d’octets pour faciliter l’accès direct à chaque inode sur le système de stockage. D’un autre côté, l’inode doit contenir la liste des blocs qui composent le fichier/répertoire. Une première approche serait de dire qu’un inode doit pouvoir contenir la liste des tous les blocs du fichier de taille maximale. Sur un système de stockage de 1 TBytes utilisant des blocs de 1024 octets, le plus grand fichier peut contenir un milliard de blocs. Si chaque bloc est identifié par un entier de 32 bits, cela signifierait qu’il faudrait réserver 4 milliards d’octets dans chaque inode au cas où cet inode correspondrait à un fichier gigantesque, alors que la quasi totalité des fichiers sont assez petits. Les systèmes de fichiers utilisant les inodes résolvent ce problème en utilisant un inode de petite taille, par exemple 128 octets. Cette taille permet de stocker 4 inodes directement dans un bloc de 512 octets. Elle permet aussi de stocker directement dans l’inode les numéros des premiers blocs du fichier. Pour des petits fichiers, qui ne contiennent quelque milliers d’octets, le système de fichiers peut récupérer les identifiants de blocs directement de l’inode. Pour les plus gros fichiers, il faut cependant utiliser un mécanisme plus complexe. En pratique, l’inode contient n entrées qui pointent directement vers des numéros de blocs. Ces entrées sont généralement appelées les pointeurs directs. L’entrée suivante (n+1) pointe elle vers un bloc qui contient des numéros de blocs. Cette entrée est généralement appelée pointeur avec une indirection simple. Si les numéros de blocs sont encodés sur 32 bits et qu’un bloc contient 512 octets, alors en utilisant l’inode plus ce premier bloc on peut encoder \(n+128\) numéros de blocs. La Fig. 144 illustre l’utilisation de ce type de pointeur. L’entrée suivante de l’inode est le pointeur avec une indirection double. Ce pointeur contient le numéro d’un bloc qui contient des numéros de blocs indirects. Via cette entrée, on peut donc référencer \(128^2\) blocs du fichier. Pour les très longs fichiers, il reste le pointeur d’indirection triple. Ce pointeur contient le numéro d’un bloc qui contient des pointeurs d’indirection double. Via ce dernier pointeur, il est possible d’encoder \(128^3\) blocs. La figure ci-dessous illustre comment, grâce à un pointeur indirect, un inode peut référencer un fichier composé de 16 blocs, même si il ne contient que douze pointeurs directs.

Fig. 144 Un inode référençant un fichier de 16 blocs via un bloc indirect

Nous pouvons maintenant revenir à notre système de fichiers d’exemple. Celui-ci utilise dix inodes qui sont stockés dans la table des inodes. Il est représenté dans la Fig. 145.

Fig. 145 Notre système de fichiers d’exemple en format `ext2`

Il nous reste maintenant à expliquer le rôle des deux blocs qui contiennent les bitmaps. Dans un système de fichiers de type ext2, il est nécessaire de savoir si un bloc de données est utilisé par un fichier/répertoire ou libre. Il en va de même pour les inodes. Une première solution pour conserver cette information serait de maintenir une liste chaînée avec les numéros des blocs de données libres ou occupés. Malheureusement, une telle liste prendrait de la place sur le dispositif de stockage et pourrait être difficile à manipuler. Une solution plus efficace pour conserver cette information est d’utiliser un bitmap. Le bitmap des inodes est une structure de données simple qui utilise un bit pour indiquer si un inode est libre ou occupé. La structure contient autant de bits qu’il n’y a d’inodes dans le système de fichiers. Dans notre système de fichiers d’exemple, nous avons une dizaine d’inodes et 32 blocs. Si l’on s’en réfère à la Fig. 145, le bitmap des inodes contiendrait la chaîne de bits suivante, en supposant que 1 corresponde à un inode occupé et que le bit de poids fort corresponde à l’inode 0 :

Code source 16 Bitmap des inodes

11111111 11000000

Pour le bitmap des blocs on procède de la même façon. Le bit correspondant à un bloc est mis à 1 lorsqu’il est occupé par un fichier/répertoire et 0 sinon. Dans notre système de fichiers d’exemple, le bitmap des blocs serait :

Code source 17 Bitmap des blocs

11111100 00000000 00000011 11111111

Maintenant que nous avons décrit les principaux éléments du système de fichiers ext2, il est intéressant de voir plus en détails toutes les opérations qui doivent être réalisées sur le système de fichiers pour lire des données, écrire des données et créer un fichier.

Commençons par la lecture des données dans un fichier. Pour accéder aux données d’un fichier, le système de fichier doit d’abord accéder à l’inode qui le décrit. Cet inode est référencé dans l’entrée du répertoire qui correspond au fichier. Avant de lire le fichier, il faut vérifier qu’il s’agit bien d’un fichier et que l’utilisateur dispose des permissions de lecture sur ce fichier. Cette information est présente dans le champ mode de l’inode. Ensuite, le système de fichiers va parcourir la liste des pointeurs directs et indirects pour pouvoir accéder aux différents blocs de données qui composent le fichier. Grâce au champ length de l’inode, le système de fichiers pourra arrêter la lecture des données au dernier octet utile du fichier. Il faut aussi mettre à jour la date de dernier accès au fichier dans l’inode.

Les opérations d’écriture dans un fichier sont assez similaires sauf lorsqu’il faut ajouter un nouveau bloc à un fichier existant. Dans ce cas, le système de fichier va d’abord consulter le bitmap des blocs pour trouver un bloc libre. Pour améliorer les performances du système de fichiers, il est généralement utile de placer les blocs d’un fichier dans des zones contiguës, mais si les blocs qui suivent ceux utilisés par le fichier sont déjà occupés, rien n’empêche le système de fichiers de choisir un bloc dans une autre partie du dispositif de stockage. Une fois ce bloc choisi, il faut le référencer dans l’inode du fichier et mettre à jour la longueur du fichier (en blocs et en octets). Si il reste un pointeur direct de libre dans l’inode, il suffit de le modifier pour référencer le nouveau bloc. Sinon, il peut être nécessaire d’obtenir un nouveau bloc pour stocker un pointeur indirect, doublement indirect ou triplement indirect. Dans les trois cas, cela nécessite de trouver un nouveau bloc via le bitmap des blocs, mettre à jour ce bitmap et référencer ce bloc correctement. Il faut aussi mettre à jour les dates de dernière modification et d’accès au fichier dans l’inode.

Les opérations de création de fichier sont les plus complexes. Pour créer un nouveau fichier et y stocker des données, il faut d’abord trouver un inode de libre. Cela se fait en consultant le bitmap des inodes. On peut ensuite commencer à remplir l’inode avec les informations relatives au propriétaire du fichier, … Ce fichier peut maintenant être référencé dans un répertoire. Si le bloc qui contient le répertoire est incomplet, il suffit d’ajouter l’entrée au répertoire. Si le bloc est complet, il faut consulter le bitmap des blocs pour trouver un nouveau bloc de libre, le marquer comme occupé, et l’ajouter dans l’inode du répertoire. Ensuite, il faut trouver dans le bitmap des blocs les blocs libres nécessaires au nouveau fichier et les référencer dans l’inode de ce nouveau fichier.

Note

Un même fichier peut se retrouver dans plusieurs répertoires

Les systèmes de fichiers utilisant les inodes ont une caractéristique que nous n’avons pas encore analysé. Comme une entrée de répertoire contient un nom de fichier/répertoire et le numéro de l’inode correspondant, il est possible qu’un même fichier soit accessible depuis plusieurs répertoires différents. Ce n’est pas une erreur, mais une optimisation introduite par les concepteurs de Unix. Sous Unix/Linux, c’est la commande ln qui permet de créer des liens vers des fichiers. Si l’on reprend l’exemple de la Fig. 145 et que l’on crée un lien vers le fichier echo dans les répertoires /tmp et lib, on obtiendra l’arborescence reprise en Fig. 146 et le système de fichiers sera modifié comme décrit dans la Fig. 147. Dans ce système de fichier, les noms /bin/echo, /tmp/echo et /lib/echo correspondent tous les trois au fichier qui est référencé par l’inode 6.

Fig. 146 Arborescence des répertoires et fichiers de notre système `ext2`

Pour pouvoir gérer ces liens, le système de fichiers utilise le champ nombre de liens vers le fichier qui se trouve dans l’inode. Quand un fichier est créé, ce champ est initialisé à la valeur 1. Cette valeur indique qu’il existe un seul lien vers le fichier qui est représenté par cet inode. Si un deuxième répertoire fait référence à cet inode, alors ce champ passera à la valeur 2. Ce champ est important lors des opérations de suppression des fichiers. Quand un fichier est effacé d’un répertoire, le système de fichiers décrémente d’abord le champ contenant le nombre de liens vers le fichier. Si celui-ci passe à zéro, alors l’inode et les blocs utilisés par le fichier sont marqués comme libres et les bitmaps sont mis à jour. Sinon, cela signifie que le fichier est encore référencé dans au moins un autre répertoire. Il est important de noter que lorsque plusieurs liens existent vers le même fichier, tout accès en écriture à ce fichier est directement visible depuis tous les répertoires qui y font référence.

Fig. 147 Notre système de fichiers d’exemple en format `ext2` avec deux liens pour le fichier ``echo``

Tout comme pour le système de fichiers utilisant une table d’allocation, un système utilisant des inodes doit pouvoir survivre à plusieurs types de perturbations. Les premiers problèmes à considérer sont la perte d’un bloc. Si un bloc du système de fichiers devient illisible, quel impact cela peut-il avoir sur le système de fichiers. La seconde classe de problèmes est un système de fichiers qui se trouve dans un état incohérent car l’ordinateur qui le gérait a été arrêté brusquement alors qu’il était en train d’écrire sur le dispositif de stockage les modifications de blocs relatives à une opération. Tous ces problèmes ajoutent une couche importante de complexité aux systèmes de fichiers et à leur implémentation dans les systèmes d’exploitation. Chaque système d’exploitation contient des utilitaires spécialisés pour récupérer partiellement ou totalement un système de fichiers incohérent. C’est le cas notamment de fsck sous Linux ou de chkdsk sous Windows.

Commençons par analyser l’impact de la perte d’un bloc. Les deux premiers blocs, le Super Block et le FS descriptor, sont critiques car ils contiennent les paramètres du système de fichiers. Ils définissent notamment le nombre de blocs sur le dispositif de stockage, le nombre d’inodes et la taille de chaque bloc. Si ces blocs deviennent inutilisables, le système de fichiers l’est aussi. Pour faire face à ce risque, la solution la plus fréquente est de stocker une copie de ces deux blocs dans une autre partie du disque. Cette copie doit évidemment être mise à jour à chaque modification des blocs primaires.

Les bitmaps jouent un rôle important dans le fonctionnement du système de fichiers. Si une partie du bitmap des blocs devenait inaccessible, alors le système de fichiers ne saurait plus quels blocs sont libres. Un utilitaire spécialisé pourrait récupérer cette panne en parcourant les blocs contenant les inodes pour voir quels inodes sont utilisés. Cela suppose que lorsqu’un fichier est effacé son inode est marqué comme étant libre sur le disque et dans le bitmap des inodes. Cela peut se faire par exemple en mettant certains champs de l’inode à une valeur de référence comme 0.

Si le bitmap des blocs est affecté par une erreur, la situation est un peu différente. Il faudra dans ce cas parcourir tous les inodes pour voir quels sont les blocs du dispositif de stockage qui sont référencés et reconstruire le bitmap des blocs. Ce bitmap peut ensuite être recopié dans une autre partie du dispositif de stockage. Si un bloc contenant un répertoire est devenu illisible, les fichiers et les sous-répertoires de ce répertoire ne seront plus accessibles. Il faudra faire appel à un utilitaire spécialisé pour les récupérer. Si un bloc contenant des données est illisible, le fichier correspondant devient malheureusement aussi illisible.

Les incohérences du système de fichier sont plus complexes. Elles dépendent de l’ordre dans lequel les opérations de modification au système de fichiers sont réalisées et également du moment auquel l’ordinateur est arrêté. Pour récupérer ces incohérences, les logiciels spécialisés procèdent généralement en deux phases. Tout d’abord, ils doivent lire tous les blocs de contrôle (Super Block, FS descriptor, Inode Bitmap, Block Bitmap et Inode Table) du système de fichiers. Ensuite, il faut vérifier la cohérence entre d’abord le bitmap des inodes et l’information lue dans la table des inodes. En cas d’incohérence, ce sont les inodes qui seront considérés comme valides. L’étape suivante est de comparer le bitmap des blocs avec les blocs référencés dans les inodes. La troisième étape sera d’analyser l’arborescence des répertoires et fichiers. Cette structure doit être un arbre et non un graphe contenant des cycles. Si un cycle est détecté, il devra être supprimé généralement avec l’aide de l’utilisateur. En comparant la liste des inodes et les inodes référencés dans les répertoires, il est possible que l’on trouve un ou des inodes qui ne sont pas repris dans l’arborescence. Ces fichiers et répertoires seront recréés avec un nom générique et placé dans le répertoire /lost+found. L’administrateur du système de fichiers pourra consulter le contenu de ces fichiers pour déterminer si ils doivent être conservés ou peuvent être effacés du système de fichiers.