Nous nous intéressons à une gestion particulière de l'espace attribué aux fichiers. L'espace disponible pour les données des fichiers est découpé en blocs (au plus 32768 blocs) de taille fixe, multiple de 512 (taille d'un secteur). Les blocs de cet espace sont numérotés à partir de 0. L'espace libre est représenté par un tableau de bits. Le descripteur de volume contient les informations suivantes :

taille d'un bloc en octets (32 bits),

nombre total de blocs du volume (16 bits),

nombre de blocs libres de l'espace libre (16 bits),

numéro du premier bloc libre (16 bits),

L'espace alloué à un fichier est représenté par un certain nombre de zones, chaque zone étant définie par le numéro de son premier bloc et le nombre de blocs qu'elle contient. Les seize premières zones d'un fichier sont mémorisées dans le descripteur de fichier qui contiennent les informations suivantes :

la longueur physique du fichier en octets,

la longueur logique du fichier en octets,

16 descripteurs de zones (numéro de premier bloc, nombre de blocs).

Lorsque l'on tente d'écrire au delà de la fin physique d'un fichier, le système alloue un nouveau bloc. La recherche de ce bloc libre se fait de préférence au bout de la dernière zone déjà allouée au fichier. Si ce n'est pas possible, une nouvelle zone est ajoutée au fichier (le système peut gérer un nombre quelconque de zones, mais nous supposerons ici qu'il n'y en a jamais plus de 16).

A- Comment peut-on déterminer la taille en nombre d'octets du volume, ainsi que celle de l'espace libre? En supposant qu'un volume contient 1 Go, donner la taille minimale d'un bloc.

B- Quelle différence faites vous entre la longueur physique d'un fichier et sa longueur logique?

C- Expliquer les opérations effectuées pour trouver le secteur qui contient un octet quelconque, dont on connaît le numéro dans l'organisation non structurée.

D- Montrer que, s'il reste de l'espace libre, l'allocation est toujours possible. Evaluer le temps d'une allocation.

E- Cette implantation, faite sur un ordinateur individuel, permet en général d'avoir des zones de grandes tailles. Par contre, si elle est faite sur un ordinateur utilisé simultanément par beaucoup d'utilisateurs, elle conduira à des zones de petites tailles. Expliquer pourquoi.

F- Décrire ce qu'il faut faire lors de la destruction d'un fichier, quant à l'espace qu'il occupe.

G- Quels sont les avantages et les inconvénients de cette implantation.

La taille en nombre d'octets du volume est obtenue en faisant le produit entre les deux valeurs "taille d'un bloc en octets" et "nombre total de blocs du volume" qui sont situés dans le descripteur de volume. Pour connaître la taille de l'espace libre, il suffit de faire le produit entre les deux valeurs "taille d'un bloc en octets" et "nombre de blocs libres de l'espace libre" qui sont situés dans le descripteur de volume.

Si on suppose que le volume contient 1 Go, le nombre total de blocs étant limité à 32768, la taille d'un bloc est donc au moins de 1Go/32768, soit 32768. Notons que un bloc représente 64 secteurs.

La longueur physique d'un fichier représente la quantité d'espace disque qui lui est alloué. C'est donc le nombre d'octets qu'il occupe réellement sur le disque. La longueur logique d'un fichier représente le nombre d'octets qui contiennent des informations appartenant au fichier. C'est donc le nombre d'octets utiles du fichier. La longueur logique est toujours inférieure ou égale à la longueur physique, et la différence est un espace inutilisé du disque. Ces deux quantités ne sont pas égales, en général. La première est liée à la quantité d'informations à mettre dans le fichier. La seconde tient compte de la méthode de gestion de l'espace disque.

Notons Z_i la i-ème zone d'un fichier, T_i sa taille en nombre de blocs, et D_i le numéro de son premier bloc. Notons Tb la taille d'un bloc du volume. Rechercher le secteur qui contient l'octet de numéro N du fichier, en supposant que N est inférieur à la longueur logique du fichier, et donc à sa longueur physique, consiste d'abord à rechercher la zone Z_i qui contient cet octet, ainsi que la position relative Pr de l'octet dans la zone. Le secteur est alors celui de numéro (Pr + D_i * Tb)/512, la place de l'octet dans le secteur correspondant au reste de cette division.

Pour déterminer la zone, il faut déterminer i tel que :

, on a alors

On peut l'obtenir par le petit programme suivant:

Pr := N;				/* position dans le fichier */
I := 0;					/* première zone */
tantque Pr >= T[I] faire
	Pr := Pr - T[I];	/* position relative dans la suite */
	I := I + 1;
fait;
Ns := (Pr + D[I] * Tb)/512;

L'allocation d'espace se fait lorsque l'on tente d'écrire au delà de la fin physique du fichier, et dans ce cas on alloue un bloc unique. Donc s'il reste de l'espace libre, l'allocation sera possible, puisque n'importe quel bloc peut convenir. Si le système cherche de préférence à allouer un bloc au bout de la dernière zone, il alloue un autre bloc quelconque lorsque ce n'est pas possible. La seule contrainte pourrait être la limitation du nombre de zones d'un fichier. Or il est dit que le système gère un nombre quelconque de zones.

On peut penser que la table de bits représentant l'espace libre est toujours présente en mémoire, et n'est réécrite que de temps en temps lorsqu'elle a été modifiée. Ceci peut poser des problèmes de sécurité, mais nous n'en parlerons pas. Cette table contient au plus 32768 bits, donc 4096 octets, ou 8 secteurs. Ce n'est pas trop encombrant en mémoire centrale.

Lors de l'allocation, il faut d'abord tester si le bloc qui suit la dernière zone est libre. Notons qu'il s'agit du bloc de numéro D_i + T_i, si i est le numéro de cette zone. Si ce bloc est libre, il suffit de changer son état à occupé et d'allonger la zone Z_i en incrémentant T_i. Si ce bloc n'est pas libre, on crée une nouvelle zone, de taille 1, qui commence au numéro du premier bloc libre trouvé dans le descripteur du volume. Enfin, il faut mettre à jour la longueur physique du fichier et le nombre de blocs libres de l'espace libre. Toutes ces actions demandent un temps fixe que l'on peut estimer à quelques microsecondes sur les ordinateurs actuels.

Il faut également mettre à jour le numéro du premier bloc libre du descripteur de volume, si c'est ce bloc qui a été alloué. Cela implique de rechercher à partir de ce numéro de bloc (il est inutile de rechercher avant, car il n'y en a pas) le prochain bloc libre. Il est possible que ce soit le suivant. Il est possible que l'on ait besoin d'en parcourir beaucoup avant d'en trouver un de libre. Évidemment, il y en a au pire 32768, si le dernier bloc libre était le premier. Intuitivement, si l'on n'est pas trop près de la saturation, il y a des blocs libres un peu partout dans l'espace, et on ne mettra pas trop de temps pour le trouver. Supposons qu'il soit nécessaire de parcourir 1000 blocs occupés avant d'en trouver un de libre. S'il faut 1 microseconde par bit, cela donne 1 milliseconde. Cependant ceci peut être amélioré. En effet si on représente l'état occupé par un bit à 0, la recherche d'un bloc libre est la recherche d'un bit à 1. Mais un tel bit est alors situé dans un octet qui n'est pas nul, ou encore dans un mot machine qui n'est pas nul. Sur une machine à 32 bits, cela signifie rechercher un mot non nul parmi 32. Une fois ce mot trouvé, on recherche le bit à 1 parmi les 32 du mot. Tout ceci doit pouvoir être fait en au plus 64 microsecondes.

Sur un ordinateur individuel, il n'y a qu'un seul utilisateur à la fois. Il s'en suit qu'il n'y a en général qu'un seul fichier en cours de création. Bien que l'allocation se fasse bloc par bloc, l'espace alloué au fichier viendra des premières portions d'espace contigu, qui sont libres avant cette création.

Si l'ordinateur est utilisé simultanément par beaucoup d'utilisateurs, cela implique qu'il peut y avoir plusieurs fichiers en cours de création. Le système sera alors amené à allouer de l'espace, à raison de un bloc à la fois, tantôt pour l'un tantôt pour l'autre de ces fichiers. Les blocs ainsi alloués ne seront alors jamais au bout de la dernière zone déjà allouée au fichier, et conduiront à l'ajout d'une nouvelle zone. Notons que ceci pourrait également se faire sur un ordinateur individuel si un même programme créait deux fichiers simultanément, en écrivant tantôt dans l'un tantôt dans l'autre. Un tel programme est cependant assez rare.

Lors de la destruction d'un fichier, en dehors des actions à faire sur les répertoires, il faut restituer à l'espace libre l'espace qu'il occupait. Ceci se traduit simplement par la remise à l'état libre de chacun des blocs contenus dans chacune des zones du fichier. En même temps, il faut éventuellement remettre à jour le numéro de premier bloc libre du descripteur de volume. Le morceau de programme suivant donne les grandes lignes de ce qu'il faut faire.

J := Longueur_Physique / Tb;  /* nombre de blocs du fichier */
I := 0;							/* première zone du fichier */
tantque J > 0 faire
	pour K dans D[I] .. D[I] + T[I] - 1 faire
		Etat[K] := Libre;	/* libérer les blocs de la zone */
	fait;
	si D[I] < Premier_Bloc_Libre alors Premier_Bloc_Libre := D[I]; finsi;
	J := J - T[I];
	I := I + 1;
fait;

Les avantages comme les inconvénients ont déjà été évoqués, en grande partie du moins, dans les questions précédentes. On note ainsi que, contrairement aux différentes techniques d'allocation par zone, l'allocation est toujours possible, pourvu qu'il reste de la place, évidemment. En ce sens, le système se rapproche de la technique utilisée dans VMS, lorsque l'utilisateur demande une allocation au mieux. De plus, si le disque comporte de grandes zones libres, le système allouera un nombre réduit de zones au fichier, améliorant les performances par rapport à une allocation par blocs de taille fixe. On a donc un bon compromis entre les deux techniques d'allocation.

L'inconvénient majeur est lié au fait que les zones d'un fichier sont de tailles variables. Si on ne fait que des accès séquentiels sur de tels fichiers, ce n'est pas gênant, puisqu'on va parcourir les zones les unes après les autres en tenant compte de leurs tailles successives. Si on fait de l'accès aléatoire, nous avons vu dans la question C qu'il faudra parcourir la table des descripteurs de zones du fichier, pour déterminer celle qui contient l'information recherchée. Si le fichier contient peu de zones, ce parcours sera très rapide. S'il contient beaucoup de zones, cela peut prendre un peu de temps. Encore faut-il relativiser: s'il y a 50 zones, il faut en parcourir 25 en moyenne, ce qui peut demander 100 microsecondes à raison de 4 microsecondes par zone. Or la question E induit l'idée que même un gros fichier ne comportera qu'un nombre réduit de zones.

Remarque (hors sujet): cet exercice, comme le précédent d’ailleurs, est tiré de la gestion du MacIntosh. Dans le système réel, le descripteur de fichier ne contient que 3 descripteurs de zones, les autres descripteurs de zones éventuels sont rangés dans un B-arbre, tous fichiers confondus. L'expérience montre que très peu de fichiers ont plus de 3 zones, cependant la méthode n'impose pas de véritable limite sur le nombre de zones d'un fichier.