3.4. Étude de la structuration d'un disque

On se propose d'étudier une structuration pour des disques dont la capacité est comprise entre 100 Mo. et 2 Go., les secteurs étant de 4096 octets.
Les machines pour lesquelles ils sont destinés manipulent des octets, des entiers sur 16 bits ou des entiers sur 32 bits.
Les concepteurs du système de gestion de fichiers ont décidé de diviser chaque unité de disque (amovible ou non) de la façon suivante:
Un fichier est constitué de deux parties:

A. Étude des descripteurs de fichiers.

Les descripteurs de fichiers doivent repérer l'ensemble des zones du fichier. Pour permettre à un fichier de contenir un nombre quelconque de zones, tout en ayant des descripteurs de taille fixe, les descripteurs sont décomposés en une partie principale (obligatoire) et des parties extensions (optionnelles). Les parties extensions éventuelles ont la même structure que les parties principales, les informations inutilisées étant simplement mises à 0 dans ce cas. Par la suite nous appellerons descripteur cette structure, qu'elle soit utilisée comme partie principale ou comme extension. Les descripteurs de fichiers sont regroupés dans des secteurs du disque. Ces secteurs sont chaînés entre eux, pour permettre la recherche des fichiers. Un descripteur de fichier a la structure suivante:
. le nom du fichier sur 16 octets,
. des informations diverses sur 12 octets,
. la longueur du fichier, c'est-à-dire le nombre total d'octets du fichier,
. le nombre total de zones du fichier,
. la taille des zones en nombre de secteurs,
. l'“adresse” de l'extension suivante (numéro de secteur et position dans le secteur),
. l'“adresse” de la dernière extension du fichier,
. la table des numéros de premiers secteurs des premières zones.
A.1- En considérant que tout entier sur disque a la même représentation qu'en mémoire centrale, c'est-à-dire 16 ou 32 bits, déterminer la taille en octets nécessaire à la représentation de chacune des informations suivantes:
. un numéro de secteur,
. la longueur du fichier, c'est-à-dire le nombre total d'octets du fichier,
. le nombre total de zones du fichier,
. la taille des zones en nombre de secteurs,
. l'“adresse” d'une extension (numéro de secteur et position dans le secteur).
A.2- Déterminer la taille d'un descripteur en fonction du nombre d'entrées q de la table des premiers secteurs de zones dans un descripteur. En déduire la valeur maximale du nombre r de descripteurs dans les secteurs du disque qui les contiennent, en fonction de q, et la perte qui résulte d'un choix donné de r et q compatibles.
A.3- Étudier en particulier les cas où ce nombre q prend les valeurs 31, 32 et 33. Calculer la perte d'espace dans chaque cas. Commenter le choix de 32.
A.4- Expliquer l'intérêt des différentes informations (autres que diverses) qui sont présentent dans la partie principale d'un descripteur. On distinguera celles qui sont nécessaires et celles qui sont redondantes, et on justifiera cette redondance. Montrer que l'on peut déduire de ces informations le nombre d'extensions du descripteur de fichier.

B. Étude des descripteurs de disque

Nous avons déjà dit que les descripteurs de fichiers étaient regroupés dans des secteurs du disque, chaînés entre eux. Pour minimiser le parcours de ces secteurs lors de la recherche d'un fichier, on partitionne les descripteurs en p ensembles disjoints par un calcul sur le nom du fichier, H(nom), qui délivre un entier entre 1 et p. Le descripteur du disque contient une table qui, pour chacune des valeurs entre 1 et p, indique le numéro du premier secteur contenant les descripteurs des fichiers dont le calcul H(nom) donne cette valeur (fonction de hachage). Le descripteur du disque, qui doit tenir dans un seul secteur du disque, est donc défini comme suit:
. le nom du disque sur 32 octets,
. le nombre total de secteurs du disque,
. le nombre de secteurs occupés,
. le nombre de fichiers existants sur le disque,
. le nombre de descripteurs de fichiers par secteurs,
. le nombre d'entrées de la table de hachage,
. la table de hachage, donnant pour chaque valeur de hachage le numéro du premier secteur des descripteurs de fichiers.
B.1- En considérant que tout entier sur disque a la même représentation qu'en mémoire centrale, c'est-à-dire 16 ou 32 bits, déterminer la taille en octets nécessaire à la représentation de chacune des informations suivantes:
. le nombre de fichiers existants sur le disque,
. le nombre de descripteurs de fichiers par secteurs,
. le nombre d'entrées de la table de hachage,
B.2- Le descripteur du disque devant tenir dans un seul secteur, combien peut-il y avoir au plus d'entrées dans la table de hachage? À quel endroit convient-il de mettre ce secteur sur le disque?
B.3- Expliquer l'intérêt des différentes informations qui sont présentent dans le descripteur du disque. On distinguera celles qui sont nécessaires et celles qui sont redondantes, et on justifiera cette redondance.
B.4- Comment jugez-vous ce système? Quels avantages ou inconvénients y voyez-vous?
B.5- Définir la procédure d'ouverture d'un fichier, ainsi que la procédure de lecture d'un octet quelconque de ce fichier défini par sa position relative au début du fichier.
Solution de l’exercice 3.4

3.4.1. Question A

3.4.1.1. Question A.1

3.4.1.2. Question A.2

Pour déterminer le nombre de descripteurs de fichiers par secteur, il faut déterminer la taille d'un descripteur. Nous reprenons les données numériques de la question A.1, et les notons devant les informations du descripteur de fichier:
16
le nom du fichier sur 16 octets,
12
des informations diverses sur 12 octets,
4
le nombre total d'octets du fichier,
4
le nombre total de zones du fichier,
4
la taille des zones en nombre de secteurs,
4
l'“adresse” de l'extension suivante (numéro de secteur et position dans le secteur),
4
l'“adresse” de la dernière extension du fichier,
4*q
la table des numéros de premiers secteurs des premières zones.
Il s'ensuit que le descripteur occupe 48 + 4 * q octets, où q est le nombre d'entrées de la table des premiers secteurs de blocs d'un descripteur. Les secteurs contenant des descripteurs étant chaînés entre eux, le lien de chaînage occupe 4 octets, laissant libres 4092 octets pour r descripteurs, et il s'ensuit que r ≤ 4092 / (48 + 4 * q). Pour une valeur de r compatible avec q, la perte est 4092 - r * (48 + 4 * q).

3.4.1.3. Question A.3

Nous avons les valeurs suivantes:
q
r maximum
perte
31
23
136
32
23
44
33
22
132
Le choix de 32 est le plus optimal, puisqu'il correspond à la plus petite perte. Cependant, même s'il induisait une perte supérieure aux autres, il pourrait être conservé car il a l'avantage de permettre de représenter, dans chaque descripteur, qu'il soit partie principale ou extension, un nombre de zones qui est une puissance de 2.

3.4.1.4. Question A.4

Le nom du fichier est nécessaire pour distinguer les fichiers entre eux, et permet à l'utilisateur de désigner ce fichier par une chaîne de caractères. La longueur du fichier N est la seule information de taille qui permette de savoir exactement quels sont les octets de l'espace alloué au fichier qui en font partie. La taille des zones T est nécessaire pour déterminer la taille des zones à allouer au fur et à mesure des besoins au fichier; elle permet également de déterminer à quelle zone appartient le nième secteur du fichier. L'adresse de l'extension suivante est nécessaire pour parcourir les extensions du descripteur. La table des numéros de premiers secteurs permet de savoir où commence chaque zone sur disque, et donc détermine l'espace alloué au fichier.
Le nombre total de zones du fichier est une information redondante, en ce sens qu'elle peut être reconstruite à partir des autres. En effet, le nombre de secteurs S est égal à (N-1)%4096+1, où % désigne la division entière. À partir de la taille des zones T, on peut déduire le nombre de zones B = (S-1)%T+1. Elle évite de refaire ce calcul en particulier pour déterminer la taille de l'espace occupé par le fichier sur le disque. Enfin l'adresse de la dernière extension du fichier est également une information redondante, puisqu'elle peut être connue en parcourant les extensions successives. Elle est utile car l'allocation d'une nouvelle zone lors d'un allongement du fichier, entraîne la modification de cette extension.
Par ailleurs (B-1)%32 nous donne le nombre d'extensions du fichier.

3.4.2. Question B

3.4.2.1. Question B.1

3.4.2.2. Question B.2

Nous reprenons les données numériques des questions A.1 et B.1, et les notons devant les informations du descripteur du disque:
32
le nom du disque sur 32 octets,
4
le nombre total de secteurs du disque,
4
le nombre de secteurs occupés,
4
le nombre de fichiers existants sur le disque,
2
le nombre de descripteurs de fichiers par secteurs,
2
le nombre d'entrées de la table de hachage,
4*p
la table des premiers secteurs de descripteurs de fichiers.
Il s'ensuit que le descripteur occupe 48 + 4 * p octets. Comme il doit tenir dans un secteur, il s'ensuit que p ≤ (4096 - 48) / 4 = 1012.
Le système doit être capable de trouver le descripteur d'un disque quelconque, avant d'avoir aucune information sur sa structure. Ce descripteur doit donc être dans un secteur fixe pour tous les disques. Il est alors logique de le mettre dans le secteur 0, c'est-à-dire, secteur 0 de la face 0 du cylindre 0.

3.4.2.3. Question B.3

Le nom du disque permet d'attacher un “label” au volume ainsi structuré. Les utilisateurs pourront utiliser cette chaîne de caractères pour demander au système de contrôler qu'il s'agit du bon volume. Le nombre total de secteurs permet de connaître la taille du disque lui-même. Cette information est parfois redondante, si le matériel impose le nombre de secteurs par piste, le nombre de faces et le nombre de cylindres, mais ce n'est pas toujours le cas. Le nombre de descripteurs de fichiers par secteurs est nécessaire si le SGF admet que ce nombre varie d'un volume à l'autre. Cette paramétrisation a l'avantage de faciliter l'adaptation de la structure aux besoins des utilisateurs plutôt que de l'imposer en tant que constante interne au système. Le nombre d'entrées de la table de hachage permet d'adapter cette valeur à la capacité du disque et au nombre de fichiers que l'on prévoit d'y mettre.
Le nombre de secteurs occupés est une information redondante, puisqu'il suffit de parcourir l'ensemble de tous les descripteurs de fichiers pour la retrouver. Le nombre de fichiers existants est également une information redondante, puisque ce nombre peut être obtenu par parcours des descripteurs de fichiers. La conservation de ces valeurs évite ce parcours lorsqu'on désire savoir quel est le taux d'occupation du disque, le nombre de fichiers, la taille moyenne des fichiers, etc...

3.4.2.4. Question B.4

La désignation des fichiers dans ce système est assez pauvre, puisque tous les fichiers sont désignés par un nom sur 16 octets, et qu'il y a un répertoire unique pour l'ensemble des fichiers du disque: il n'y a pas de structure arborescente. Cet inconvénient peut être particulièrement important si les fichiers sont de petite taille, et le disque de grosse capacité (500000 fichiers de 4Ko. par exemple). La présence de la table de hachage peut améliorer nettement l'efficacité de la recherche d'un fichier, puisqu'elle implique un partitionnement de l'ensemble des noms de fichiers en 1000 groupes environ. Cependant, il n'en reste pas moins qu'un tel répertoire plat est désagréable pour les utilisateurs dans leur construction et manipulation des noms de fichiers.
Ce système permet de prendre en compte des fichiers de taille quelconque. Si l'utilisateur fixe correctement la taille des zones de son fichier, et que les allocations contiguës de cette taille sont possibles, le comportement peut se rapprocher de celui des systèmes à nombre fixe maximum de zones, puisque alors son descripteur de fichier peut n'avoir qu'une partie principale, sans extension. Si par contre, l'utilisateur fixe une taille de zones égale à 1 secteur, il a la garantie de pouvoir créer un fichier de taille quelconque, dans la limite de l'espace réellement disponible, au prix d'une certaine perte d'efficacité due au nombre de ses extensions si son fichier est de taille importante. Notons cependant que les fichiers dont la taille est inférieure ou égale à 128 Ko n'ont jamais besoin d'une extension, s'il y a 32 entrées dans la table des numéros de premiers secteurs d'un descripteur.
Notons qu'un disque de 100 Mo offre ici 25000 secteurs, alors qu'un disque de 2 Go en offre 500000. Dans ce dernier cas, l'allocation au niveau du secteur peut être jugée lourde et inefficace. Une méthode courante pour diminuer cette difficulté est de considérer que l'unité minimum d'allocation est de plusieurs secteurs. Le seul changement à apporter à la structure est de mémoriser dans le descripteur du disque cette unité d'allocation en nombre de secteurs. Lors de la création d'un fichier, la taille effective des zones est alors forcée au multiple de cette unité d'allocation immédiatement supérieure ou égale à celle demandée par l'utilisateur, sans qu'il ait à se préoccuper de la valeur de cette unité d'allocation.

3.4.2.5. Question B.5

Donnons tout d'abord les structures manipulées dans un langage “à la Pascal”.
type t_descripteur: article	   { représentation d'un descripteur }
		nom: chaîne [16];
		info: chaîne [12];
		longueur: entier;
		nb_zone: entier;
		taille_zone: entier;
		ext_suivante, dernière_ext: entier;
		def_zone: tableau [0 .. 31] de entier;
	fin article;
type t_sect_descr: article	   { représentation d'un secteur de descripteurs }
		descr: tableau [0 .. 22] de t_descripteur;
		suivant: entier;
	fin article;
Nous supposons que la table de hachage du disque est déjà présente en mémoire centrale. La procédure suivante d'ouverture de fichier initialise le descripteur de fichier qui lui est passé en paramètre avec la partie principale si elle a été trouvée, ou avec un descripteur invalide sinon.
var tab_hachage: tableau [1 .. p] de entier;		{ supposé déja en mémoire }
procédure ouvrir (nom: chaîne [16]; var descr: t_descripteur);
var sect_descr: t_sect_descr;
   s, i: entier;
   non_trouvé: booléen;
début non_trouvé := vrai;
	  s := tab_hachage [H (nom)];
	  tantque s ≠ 0 et non_trouvé faire
		lire_disque (sect_descr, s);
		i := 0;
		tantque i < 23 et non_trouvé faire
			si sect_descr.descr [i].nom = nom alors non_trouvé := faux
			sinon i := i + 1 finsi;
		fait;
		s := sect_descr.suivant;
	  fait;
	  si non_trouvé alors descr := descripteur_invalide
	  sinon descr := sect_descr.descr [i]; finsi;
fin;
Cette procédure pourrait être complétée par la lecture des extensions du fichier. Comme le nombre de zones du fichier est mémorisé dans la partie principale, il serait alors possible de constituer un tableau unique avec tous les numéros de premier secteur de toutes les zones du fichier. Cependant si le fichier fait l'objet d'allongement (écriture au bout), ceci peut conduire à augmenter la taille de cette table au cours de l'exécution du programme, à moins de la surdimensionner initialement pour réduire l'éventualité de cet allongement.
La procédure de lecture d'un octet situé à une position donnée, peut se définir comme suit:
procédure lire (descr: t_descripteur; position: entier; var c: octet);
var sect_descr: t_sect_descr;
   sect_donnée: tableau [0 .. 4095] de octets;
   num_ext, num_zone, num_sect, num_oct: entier;
   s, i: entier;
début num_oct := position mod 4096;	 { position dans le secteur de données }
  position := position % 4096;		 { numéro relatif de secteur du fichier }
  num_sect := position mod descr.taille_zone;{numéro du secteur dans la zone}
  position := position % descr.taille_zone;{numéro relatif de zone du fichier}
  num_zone := position mod 32;	   { numéro de zone dans l'extension }
  num_ext := position % 32;
  si num_ext = 0 alors s := descr.def_zone [num_zone]
  sinon { lecture de l'extension si ce n'est pas fait lors de l'ouverture }
	s := descr.ext_suivante;
	tantque num_ext ≠ 0 faire
	  i := s mod nb_descr_par_secteur;
	  s := s % nb_descr_par_secteur;
	  lire_disque (sect_descr, s);
	  s := sect_descr.descr [i].ext_suivante;
	  num_ext := num_ext - 1;
	fait;
	s := sect_descr.descr [i].def_zone [num_zone];
  finsi;
  lire_disque (sect_donnée, s);
  c := sect_donnée [num_oct];
fin;