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 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.
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
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 :
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
Soit le bloc , tous les blocs
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 :
Une meilleure approximation du temps de recherche est donc
É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.
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.
Cet algorithme très simple ne tient pas compte de la structure d'un disque. Il est équitable, mais assez inefficace.
Considérons la fonction
.
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 :
.
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.
Un bloc
peut être également identifié par
. Un bloc est alors un numéro entre
et
.
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.
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
.
Plusieurs gestions sont possibles :
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%
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.
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.