Précédent Remonter Suivant

3  Structure logique du système de fichiers

Le système de fichiers contient deux sortes d'entités : les répertoires et les fichiers ordinaires. Les répertoires permettent de structurer le système de fichiers et les fichiers ordinaires contiennent les informations utiles. En fait, ces deux entités sont implantées comme des fichiers avec un fonctionnement un peu particulier pour les répertoires, le terme fichier recouvre donc à la fois la notion de répertoire et de fichier ordinaire.

La structuration des répertoires est purement hiérarchique. En plus de ses sous-répertoires et de ses fichiers ordinaires, un répertoire désigne toujours lui-même (pourquoi ?1) et son répertoire père2. La racine de cette hiérarchie est un répertoire particulier appelé root qui est son propre père.

Tout fichier ordinaire est désigné au moins une fois par un ou plusieurs répertoires3 --- sinon il est inaccessible et ne devrait pas exister.

On appelle lien toute entrée de répertoire qui désigne un fichier (répertoire ou ordinaire). Un répertoire contient une suite de liens de la forme {i-nombre,nom}. Le i-nombre est un entier qui permet de retrouver le fichier correspondant (plus exactement, il sert d'indice dans la table des i-noeuds) : il est unique dans le système de fichiers. Le nom est une chaîne d'au plus 14 caractères qui identifie de façon unique une entrée du répertoire. Un répertoire possède toujours au moins deux entrées qui sont créées et détruites en même temps que le répertoire, ce sont {self,"."} qui désigne le répertoire lui-même (self est le i-nombre du répertoire) et {pere,".."} qui désigne le répertoire père. Dans le cas du répertoire racine, ces deux entrées sont fixées à {2,"."} et {2,".."} : le i-nombre du répertoire racine est toujours 2. Ainsi root est son propre père !

À l'inverse d'un fichier ordinaire, il ne peut y avoir d'autres liens sur un répertoire que ceux créés par la structure même du système de fichiers. En effet cela aurait pour effet de transformer l'arborescence des fichiers en un graphe pouvant contenir des cycles et provoquer des boucles sans fin lors de la résolution de noms de fichiers.

Un fichier est décrit dans le système de fichiers par un unique i-noeud qui contient les informations suivantes4 : Ces informations sont rangées dans une structure de type INOEUD_OCCUPE (figure 3). 
/* Taille d'un bloc */ 
#define BLOC_SIZE 64

enum CATEGORIE {ORDINAIRE, REPERTOIRE} ;

typedef u_short NUM_BLOC

typedef struct  INOEUD_OCCUPE {
   enum CATEGORIE type ;
   u_short    liens ; /* nombre d'entrees de repertoire referencant ce inoeud */
   u_long     taille ;  /* taille logique en octets du fichier */
#define NB_BLOCS_DIRECTS 7
   NUM_BLOC   direct [NB_BLOCS_DIRECTS] ;  /* les 7 premiers blocs du fichier */
   NUM_BLOC   indirect ;        /* bloc d'indirection pour les blocs suivants */
   NUM_BLOC   double_indirect ; /* bloc de double indirection ... */
} INOEUD_OCCUPE ;

typedef union { /* definition qui sera completee */
   INOEUD_OCCUPE occupe ;
   /* ... */
} INOEUD ;

/* Nombre de numeros de bloc par bloc (Pour les blocs d'indirection) */
#define NUMEROS_PAR_BLOC (BLOC_SIZE / sizeof (NUM_BLOC))

Figure 3 : Définitions de types pour les i-noeuds

Le système de fichiers contient une table des i-noeuds et c'est le i-nombre qui sert d'indice dans cette table.

La figure 4 montre un exemple de i-noeud de répertoire avec les blocs attachés.

Figure 4 : Un exemple de i-noeud répertoire. On remarque que le répertoire occupe tout l'espace des blocs utilisés (taille = 640) même si toutes les entrées ne sont pas utilisées. Dans le cas d'un fichier ordinaire, il se peut que le dernier bloc ne soit pas complètement utilisé.

La figure 5 montre un exemple de fichier ordinaire.

Figure 5 : Un exemple de i-noeud. On remarque que : (1) la taille n'est pas nécessairement multiple de celle d'un bloc (64 octets), en effet le dernier bloc n'est pas forcément complètement utilisé ; (2) le fichier utilise moins de blocs que ce qui semblerait nécessaire si on regarde sa taille (i.e. il y a des trous dans le fichier), ceci est dû au fait qu'il est possible de faire des écritures bien au-dela de la fin du fichier. Lors de la lecture, les trous d'un tel fichier sont considérés comme contenant des 0. Ceci peut paraître étrange, cependant, cela facilite l'implémentation (pas de vérification à faire lors de l'écriture) et permet de gagner de la place lorsqu'on a d'énormes fichiers creux.


Question 1   Sachant que les blocs font BLOC_SIZE =64 octets et qu'un numéro de bloc tient sur sizeof (NUM_BLOC) =2 octets, donnez la taille logique maximale en octets d'un fichier. Quels sont alors les nombres totaux minimaux et maximaux de blocs utilisés.

Question 2   Vérifiez que la taille du fichier donné dans l'exemple de i-noeud (figure 5) n'est pas débile.

Question 3   Les blocs qui constituent un fichier sont numérotés relativement à partir de 0. Étant donné un i-noeud et un numéro relatif de bloc, donnez l'algorithme qui donne le numéro logique de bloc correspondant. (En particulier, on retourne une valeur nulle pour un bloc non effectivement alloué6.)

Question 4   Donner l'algorithme de principe de la commande du qui, étant donné un i-noeud, retourne le nombre de blocs (ou d'octets, option -b) effectivement utilisés par le fichier.

Question 5   Dessinez les systèmes de fichiers en faisant figurer les répertoires, les i-noeuds avec leurs compteurs de liens et les fichiers dans les cas successifs suivant :
  1. le système de fichiers vient d'être créé, il ne contient que le répertoire racine ;
  2. on a ajouté un répertoire usr dans root ;
  3. on a ajouté un fichier fs.c dans le répertoire usr ;
  4. on a créé, dans root, un nouveau lien de nom xxx sur le fichier fs.c.

Question 6   Lorsqu'un fichier est ouvert (une ou plusieurs fois) il faut différer une demande de destruction jusqu'à la dernière fermeture de celui-ci, avez-vous une idée simple, mais pas forcément judicieuse pour assurer cela ? (indication : on peut utiliser le compteur de liens du fichier).

Précédent Remonter Suivant