On réserve le plus souvent l'espace nécessaire à un fichier au fur et à mesure des besoins. Dans ce cas on alloue les blocs sur la surface suivant un algorithme qui dépend du système d'exploitation. Nous évoquerons ce problème dans la section 2 du chapitre V. Les adresses physiques des informations appartenant à un même fichier sont donc dispersées aléatoirement sur la ou les surfaces. Le système d'exploitation doit donc établir une correspondance entre ces adresses physiques rangées aléatoirement et les adresses logiques contiguës qui constituent le fichier, seules manipulables dans le programme. Les différents blocs de l'information constituent un ensemble dispersé sur le disque qu'il faut chaîner rapidement en minimisant le nombre d'opérations et d'accès. La sécurité, c'est à dire la possibilité de retrouver l'information en cas de dommage local, doit également être prise en compte.

Nous allons examiner deux méthodes de chaînage : par blocs chaînés ou au moyen de tables d'implantation. Elles résument les choix faits dans les différents systèmes d'exploitation.

Descripteurs par blocs chaînés

La topologie que nous allons décrire est simple à mettre en oeuvre mais limitée dans ses performances. Elle correspond sensiblement au système FAT de Windows, hérité du DOS, encore très employé dans les versions familiales. On en comprendra rapidement les limites et j'espère que cela vous convaincra de passer à NTFS qui correspond, comme les systèmes Linux, au deuxième modèle.

Lors de sa création le système alloue un ou plusieurs blocs à un fichier. Leur nombre dépend du système d'exploitation. Chacun est constitué de plusieurs secteurs contigus. Dans chaque bloc un emplacement est réservé pour inscrire la valeur d'un pointeur sur le bloc suivant (fig. 4.12). Comme le dernier bloc n'est pas forcément complètement rempli, il faut prévoir également un emplacement pour indiquer le nombre d'octets réellement inscrits.

Le descripteur du fichier contient deux pointeurs sur le premier et le dernier bloc. Augmenter l'espace réservé au fichier revient à modifier la valeur du pointeur de fin de fichier dans le descripteur . Celui du bloc final doit être modifié pour pointer sur l'adresse d'un nouveau bloc. Ceci permet, à priori, d'ajouter un espace n'importe où dans le fichier: il suffit de changer le pointeur du bloc précédent et d'inscrire dans le nouveau bloc celui du bloc suivant. En pratique aucun système d'exploitation n'utilise cette possibilité car elle est difficile à exploiter . Les blocs sont ajoutés à la fin uniquement .

Figure 4.12 - Structure en blocs chaînés

Cette structure est simple mais peu efficace. Pour retrouver une information placée à une adresse logique précise il est nécessaire de parcourir successivement tous les blocs. Cette recherche, déjà lente par elle-même est encore ralentie par de nombreux déplacements des têtes de lecture puisque les blocs sont dispersés sur toute la surface.

Imaginons par exemple le fichier contenant ce chapitre créé au moyen d'un traitement de texte. Lors de la première sauvegarde les premiers blocs ont été alloués le long d'un cylindre mais les suivants, au fur et à mesure du travail de rédaction, ont été placés là où un espace était disponible sur le disque. Pendant la même période, d''autres programmes ont eu besoin d'espace et ont réservés les blocs libres derrière le fichier de texte. Les différents fichiers se trouvent donc physiquement entrecroisés. Rapidement le fichier se trouve morcelé et son accès s'en trouve ralenti car la tête de lecture doit se déplacer partout sur la surface pour retrouver la suite des blocs qui le constitue. Il est alors conseillé de défragmenter le disque. Cette opération consiste à regrouper les différents blocs d'un même fichier à des adresses physiques contiguës le long de cylindres successifs. C'est ce que font les utilitaires de réorganisation de disque pour Windows. Tous ceux qui les ont utilisés savent combien les performances du système d'exploitation s'en trouvent améliorées. Unix emploie une autre structure et un algorithme de réservation des blocs qui évite cette difficulté. Il n'est pas nécessaire de défragmenter le disque.

Une organisation en blocs chaînés est donc une mauvaise organisation : les temps d'accès sont médiocres et les performances se dégradent avec le temps. Elle est simple à mettre en oeuvre et se justifiait dans les premiers temps de la micro informatique par le manque de puissance des processeurs et le peu de mémoire disponible. De plus tous les dispositifs de protection que nous avons précédemment évoqués sont inexistants pour la même raison. Pour Windows cette organisation est connue sous le nom de FAT16 et FAT32 (les deux versions ne se distinguent essentiellement que par la taille maximale des fichiers) et devrait être complètement abandonné au profit de NTFS qui emploie des tables d'indexation.

Table d'index

Pour accéder aux blocs constitutifs d'un fichier, il existe une méthode plus efficace. On construit une table de pointeurs contenant la liste des adresses de début des différents blocs (fig. 4.13).

Figure 4.13 - Principe d'un accès par table

Ajouter un bloc revient à modifier et à réorganiser la table. La correspondance entre adresses physiques et logiques est aisée.

Soit S la taille d'un bloc et a l'adresse logique recherchée dans le fichier. La position r du pointeur sur le bloc, dans la table, est obtenue en calculant la partie entière b de la division de a par S.

Le reste de la division indique l'adresse relative de l'information dans le bloc. Il suffit donc de lire la valeur du pointeur contenu dans la ligne b de la table pour retrouver l'adresse de ce bloc. L'accès est bien plus rapide que par blocs chaînés. Regrouper les blocs constitutifs d'un fichier à des adresses contiguës peut optimiser les mouvements des têtes de lecture. Néanmoins cela est moins nécessaire que dans l'organisation précédente car on calcule directement les adresses. L'interface du disque peut alors réorganiser les requêtes pour minimiser les 4.15déplacements.

Figure 4.14 - Tables chaînées	Figure 4.15 - Table à deux niveaux d'indirection

Cette structure présente néanmoins une difficulté. Pour que le système d'accès soit efficace il est indispensable de ranger les tables à des adresses prédéterminées et donc de leur donner une taille fixe. Pour créer des fichiers contenant plus de blocs que le nombre maximum de lignes prévu dans une table on peut envisager deux mécanismes : allouer un espace supplémentaire c'est à dire chaîner des tables entre elles (fig. 4.14) ou établir plusieurs niveaux d'indirection (fig. ).

Chaîner les tables (fig. 4.14) présente le même inconvénient que chaîner des blocs. Il faut les parcourir successivement pour accéder à un bloc de rang donné. C'est pourquoi on préfère le deuxième mécanisme (fig. 4.15) à condition de limiter le nombre d'indirections. Dans la pratique on ne dépasse pas deux niveaux. Ceci limite donc la longueur d'un fichier. Unix utilise des tables avec niveaux d'indirection et la longueur maximum d'un fichier dépend de l'implantation réalisée par le constructeur. C'est ainsi qu'il est nécessaire de modifier la structure des systèmes de fichiers pour suivre l'évolution de la capacité des disques. C'est l'une des raisons essentielles pour lesquelles toutes les nouvelles versions des systèmes d'exploitation utilisent maintenant des mots de huit octets (64 bits). On ne vise absolument pas à améliorer la précision des calculs en nombres flottants mais à représenter les entiers sur 64 bits, ce qui permet de manipuler de plus grandes tailles et d'adresser des tailles de fichiers en rapport avec les capacités des supports qui dépassent maintenant courramment la centaine de Goctets.

Partitions

Un système de fichiers est créé dans une partition qui est une sorte de disque virtuel. Les partitions sont elles-mêmes crées à la mise en service des disques. Un disque peut contenir plusieurs partitions et une partition, dans les systèmes modernes, peut s'étendre sur plusieurs disques. Une partition est une sorte de container dans lequel on place des fichiers et qui, du point de vue de l'utilisateur, s'apparente à un disque. La mise en service d'un disque comporte donc deux phases :

1. La création des partitions sur un ou plusieurs disques. Définir la taille d'une partition est primordial car il n'est pas simple de l'étendre. Ceci est possible, sous certaines conditions, avec les dernières versions de systèmes mais reste délicat. Si une partition est trop petite pour contenir toute l'information que l'on veut y placer il faudra, le plus souvent, la recréer, en ayant au prélable sauvegardé ailleurs tout son contenu puis l'y replacer !
   
   L'intérêt du partitionnement est d'introduire une barrière étanche qui évite bien des problèmes :
   • impossibilité de remplir tout le disque, ce qui pourrait générer les autres utilisateurs ou introduire des perturbations dans le fonctionnement de la machine car le système d'exploitation ne trouverait plus la place de créer les fichiers nécessaires à son fonctionnement
   • Possibilité de reconstruire le système d'exploitation sans risque de détruire les données des utilisateurs. Par exemple, sous Windows, il est conseillé de créer une partition D: en plus de la partition C:. Celle-ci contiendra obligatoirement le système, D les données de "Mes documents".
2. La construction d'un système de fichiers dans chaque partition. Cete opération crée les tables nécessaires à la gestion des fichiers, comme nous les avons décrites précédemment. Nous y reviendrons plus en détails, à propos d'Unix, dans la section suivante.

En résumé :

• l'ensemble des disques doit être partionné avant otu usage et les utilisateurs les voient comme autant de disques indépendants. Il faut employer des commandes spéciales qui interrogent les dispositifs physiques pour distinguer les partitions des disques.
• Chaque partition contient un système de fichiers unique qui doit être construit dans un deuxième temps. Des partitions différentes peuvent contenir des systèmes de fichiers de structure différente, par exemple FAT32 pour une première, NTFS pour une seconde sous Windows ou ext2 et ext3 sous Linux.

---

Copyright Yves Epelboin, université P.M. Curie, 2000, MAJ 15 mars, 2006