Next: Une amélioration : les Up: Le système de fichiers Previous: Gestion des répertoires Index

Subsections

Gestion des blocs

Lors de la gestion du contenu d'un fichier, nous avons dit que le pilote de disque permet de voir celui-ci comme une suite de blocs numérotés.

Les tables d'allocation et les n $\oe$ uds d'informations permettent de gérer les blocs d'un fichier, sans se préoccuper des emplacements physiques des blocs. Cette abstraction est insuffisante dans le cas des SGBD pour lesquels il est nécessaire pour des raisons d'efficacité, de gérer les emplacements physiques, afin d'obtenir des allocations contiguës de blocs pour une même table.

Ordonnancement du disque

Un disque est formé de plateaux comportant chacun deux faces. Chacune des faces est découpée d'une part en pistes; d'autre part en secteurs. On définit ainsi cylindres qui correspondent intuitivement aux pistes alignées et $f \times p \times s$ blocs. Un bloc, qui est l'unité d'information pour le transfert avec la mémoire, correspond à l'intersection d'un secteur et d'une piste. Chaque bloc est identifié par un triplet .

Les blocs sont accédés au moyen de têtes de lecture/écriture montées sur un (ou plusieurs) bras. Quelque soit la technologie utilisée, il faut un certain temps pour lire et/ou écrire l'information contenu dans un bloc. Ce temps de recherche se décompose en :

temps de positionnement: qui correspond au déplacement du bras pour que les têtes de lecture soit sur le bon cylindre. Il peut donc être nul. On note le temps pour passer d'un cylindre au cylindre voisin.
temps de latence: qui correspond au positionnement de la tête sur le début du bon secteur. Ce temps dépend de la vitesse de rotation du disque. On note le temps pour passer d'un secteur au secteur voisin.
temps de transfert: qui correspond au temps de lecture/écriture du bloc. Ce temps dépend de la vitesse de rotation du disque et de la taille du secteur. On note le temps de transfert d'un secteur

Le temps de transfert est une donnée du disque, qui ne peut être modifié par logiciel, et généralement, le temps de latence maximal (une rotation - 1 secteur) est très inférieur au plus petit temps de positionnement non nul (d'une piste à une voisine).

Une approximation du temps de recherche entre les blocs et est donc $t_r = \vert p_i - p_j\vert \times t_p + \vert s_i - s_j\vert \times t_l$

Allocation contiguë et blocs consécutifs

Soit le bloc , tous les blocs $(p_i,f_j,s_{i+1})$ sont à un temps de recherche . En réalité, pour des raisons autres (alignement plus ou moins parfait des têtes de lecture, temps entre deux transferts qui ne peut être nul), ce n'est pas tout à fait vrai. En pratique, les blocs qui minimisent le temps de recherche à partir de sont :

le bloc qui correspond à la rotation pendant le temps nécessaire entre deux transferts. C'est la notion de blocs entrelacés.
ainsi de suite pour tous les blocs même face, même piste.
les blocs qui ne nécessitent qu'un réalignement (un temps ) des têtes.
les blocs des cylindres voisins $(p_{i-1},f_j,s_j)$ et $(p_{i+1},f_j,s_j)$
ainsi de suite pour les autres cylindres.

Une meilleure approximation du temps de recherche est donc $t_r(b_i,b_j) = \vert p_i - p_j\vert \times t_p + (f_i \neq f_j) \times t_a + \vert s_i - s_j\vert \times t_l$

Étant donné un disque et ses caractéristiques, il est donc possible de définir une fonction de coût pour le temps de recherche d'un bloc, de définir la notion de blocs successifs, et donc d'avoir une politique d'allocation contigüe. Le système VMS/CMS d'IBM le permet. Les administrateurs de bases de données peuvent être également amenés à ce type de travail. Les problèmes vu au cours du chapitre sur la mémoire sont présents : estimation taille d'un fichier, fichier qui dépasse son allocation, fragmentations interne et externe. Les algorithmes First Fit, Best Fit et Worst Fit peuvent être utilisés, ainsi que le compactage de disque.

Algorithmes d'accès aux blocs

Lors d'un défaut de page, la mémoire demande au pilote du disque de lui retourner le contenu d'un bloc identifié par un triplet .

Plus généralement, à un instant donné, le pilote a en attente une liste de requêtes constituée d'identificateurs de blocs.

FIFO : la requête la plus ancienne

Cet algorithme très simple ne tient pas compte de la structure d'un disque. Il est équitable, mais assez inefficace.

PCTR : Plus Court Temps de Recherche

Considérons la fonction $t_r(b_i,b_j) = \vert p_i - p_j\vert \times t_p + (f_i \neq f_j) \times t_a + \vert s_i - s_j\vert \times t_l$ . Cette propriété fournit directement l'algorithme suivant, connu sous le nom de PCTR.


debut
tant que vrai faire debut
   min = MaxInt;
   pour bj dans la liste des blocs en attente faire
      si tr(bi,bj) < min alors debut
         min = tr(bi,bj);
         prochainBloc = bj;
         fin
   lire/ecrire prochainBloc
   bi = prochainBloc;
   fin
fin

PCTR est optimal pour le temps de recherche mais malheureusement non équitable. Il n'est donc pas utilisé en pratique, mais sert de référence.

Remarque : $t_p >> t_a >> t_l \Rightarrow t_r(b_i,b_j) \sim (\vert p_i - p_j\vert, (f_i \neq f_j), \vert s_i - s_j\vert)$ .

On obtient la variante (plus efficace)


debut
tant que vrai faire debut
   min = (MaxInt,MaxInt,MaxInt);
   pour bj dans la liste des blocs en attente faire
      si (|p_i - p_j|, (f_i \neq f_j), |s_i - s_j|) < min alors
         debut
         min = (|p_i - p_j|, (f_i \neq f_j), |s_i - s_j|);
         prochainBloc = bj;
         fin
   lire/ecrire prochainBloc
   bi = prochainBloc;
   fin
fin

Remarque : si l'on maintient un tableau trié des blocs en attente, une recherche dichotomique accélère encore la recherche.

Les algorithmes de balayage

Un bloc peut être également identifié par $b_i = (p_i \times f \times s) + (f_i \times s) + s_i$ . Un bloc est alors un numéro entre et $(p \times f \times s)-1$ .

Deux algorithmes sont basés sur cette propriété. Le premier est dit de balayage circulaire, et le second de balayage.


debut
tant que vrai faire
   pour i de 0 a (p*f*s)-1 faire
      si i est dans la liste des blocs en attente alors
         lire/ecrire bloc bi
fin


debut
tant que vrai faire debut
   pour i de 0 a (p*f*s)-1 faire
      si i est dans la liste des numéros de blocs en attente alors
         lire/ecrire bloc bi
   pour i de (p*f*s)-1 a 0 faire
      si i est dans la liste des numéros de blocs en attente alors
         lire/ecrire bloc bi
   fin
fin

Si l'on maintient la liste des requêtes triée par numéro, ces deux algorithmes peuvent être améliorés.


debut
tant que vrai faire debut
   i = premier(liste);
   tant que i <= dernier(liste) faire debut
      lire/ecrire bloc i;
      i = suivant(liste);
      fin
   fin
fin


debut
tant que vrai faire debut
   i = premier(liste);
   tant que i <= dernier(liste) faire debut
      lire/ecrire bloc i;
      i = suivant(liste);
      fin
   i = dernier(liste);
   tant que i >= premier(liste) faire debut
      lire/ecrire bloc i;
      i = précédent(liste);
      fin
   fin
fin

Les algorithmes de balayage sont les plus utilisés aujourd'hui. Ils sont équitables. Ils sont également utilisés pour la gestion des ascenseurs.

Gestion des blocs libres

Le système doit gérer (affecter, libérer) les blocs libres. L'ensemble des blocs libre peut être vu comme une liste soit de triplet , soit de numéro $b_i = (p_i \times f \times s) + (f_i \times s) + s_i$ .

Plusieurs gestions sont possibles :

un vecteur binaire

0101110000111001110...

Avantages: simple, efficace pour l'allocation de blocs contigüe.
Défauts: doit résider en mémoire pour être efficace, sa taille est alors pénalisante.

C'est la solution retenue par le système Macintosh, avec une optimisation de lecture du vecteur par mot.

un vecteur de comptage

qui liste des couples (adresse de blocs, nombres de blocs libres successifs). C'est une variante du vecteur binaire.

une liste chaînée

des blocs.

Avantages: simple,
Défauts: inefficace pour l'allocation d'un grand nombre de blocs.

C'est la solution retenue par MS-DOS, car elle est gratuite avec la FAT. L'espace libre est un fichier particulier.

une liste de groupement

de blocs, consiste à utiliser le contenu des blocs libres comme adresses des blocs libres suivants.

Avantages: le codage est compact, la recherche d'un grand nombre de blocs libres est rapide.
Défauts: la gestion est plus complexe.

La gestion des fichiers Unix est très complexe. Elle a évoluée avec le temps (sans que les utilisateurs s'en aperçoivent). Elle a permis de passer d'un taux d'utilisation de la largeur de bande (débit maximal du transfert) de 3% à 30%

Gestion des blocs défectueux

Les disques neufs possèdent des blocs défectueux, et en cours d'utilisation des blocs le deviennent également. Cette liste peut être gérée de différente manière, mais c'est du ressort du contrôleur et non du système.

statiquement: Le formatage reconnaît les blocs défectueux, et ils ne sont pas mis dans la première description des blocs libres. Le système n'a donc jamais accès à ces blocs. C'est la solution retenue par les disques IDE.
dynamiquement: Au formatage, le contrôleur livre une description incomplète des blocs libres. Le contrôleur en conserve certains pour rediriger un bloc qui deviendrait défectueux, sans que le système s'en aperçoive. Cela peut diminuer les performances en cas d'allocation contiguë, mais peu si les blocs réservés sont répartis équitablement dans le disque. C'est la solution retenue par les disques SCSI.

Cohérence des blocs

Les fichiers ouverts et les répertoires possèdent généralement deux images : une sur disque et une en mémoire plus actuelle.

Une panne de l'ordinateur (matérielle ou logicielle) peut donc avoir des conséquences graves. Un bloc peut être libre et pris, où n'apparaître nul part.

Généralement un programme spécifique vérifie au démarrage le statut de chacun des blocs. En fonction des algorithmes d'allocation de blocs, certaines erreurs peuvent où ne peuvent pas être réparés. Pour ces dernières, le système d'exploitation va faire en sorte de les minimiser : écriture systématique des blocs fichiers modifiés et des blocs i-nodes concernés.

Next: Une amélioration : les Up: Le système de fichiers Previous: Gestion des répertoires Index

Alain GRIFFAULT
2000-12-22