3.2. Représentation des fichiers séquentiels

On étudie dans cet exercice diverses représentations d'un fichier dont les enregistrements logiques sont de 50 octets.

A- On dispose d'un lecteur de bandes magnétiques à 1600 BPI (Bytes Per Inch). On suppose que l'espace interbloc est de 3/4 inch. Le temps de lecture ou d'écriture d'un bloc physique de T octets est 10 + 0.008 * T ms.

A.1- On place un enregistrement logique du fichier par bloc physique. Donner le coefficient d'utilisation de la bande ainsi que le temps de lecture/écriture d'un enregistrement logique.

A.2- Pour améliorer cette utilisation, proposer une structure d'un bloc physique permettant le regroupement de plusieurs enregistrements logiques dans un même bloc. Décrire brièvement l'algorithme de lecture, ainsi que l'algorithme d'écriture des enregistrements logiques du fichier.

A.3- Donner, dans les hypothèses de A.2, la taille d'un bloc en fonction du nombre n d'enregistrements logiques qu'il contient. Donner le coefficient d'utilisation de la bande et le temps moyen de lecture/écriture d'un enregistrement logique, lorsque n = 20 ou n = 50.

B- On dispose d'un disque dont les secteurs sont de 1024 octets. On suppose que le temps moyen de lecture/écriture de s secteurs consécutifs est 8 + s ms (On ne prend pas en compte le mouvement du bras, car on suppose le bras “ bien placé ” au moment de l'opération).

B.1- On place un enregistrement logique du fichier par secteur. Donner le coefficient d'utilisation du disque ainsi que le temps d'exécution de lecture/écriture par enregistrement logique, lors d'un accès séquentiel au fichier.

B.2- On applique la méthode de regroupement vue en A.2. Donner le coefficient d'utilisation de la bande et le temps moyen de lecture/écriture d'un enregistrement logique, lorsque n = 20 ou n = 50.

B.3- Donner la valeur de n qui utilise au mieux les blocs physiques sur 1 secteur; donner dans ce cas le coefficient d'utilisation du disque ainsi que le temps moyen de lecture/écriture d'un enregistrement logique dans ce cas. Même question lorsque les blocs occupent 2, puis 3 secteurs.

C- Le disque comporte 16 secteurs par piste, 20 faces, et 900 cylindres.

C.1- Proposer une numérotation linéaire de l'ensemble des secteurs, ainsi que l'algorithme associé permettant de retrouver à partir d'un numéro virtuel de secteur ses numéros de secteur, face, cylindre.

C.2- L'espace attribué au fichier est une collection d'au plus 24 groupes de secteurs virtuels contigus, le premier groupe étant de taille s, et les suivants étant de taille i. Proposer une représentation de l'espace alloué à un fichier. Définir les algorithmes de lecture et d'écriture séquentielle d'un enregistrement logique, en supposant les enregistrements regroupés par bloc de 1 secteur comme précisé en B.3.

C.3- Évaluer le nombre d'enregistrements logiques du fichier suivant les valeurs des paramètres s et i. Donner les critères de choix qui permettraient de déterminer ces paramètres.

C.4- Application numérique, d'une part au cas où l'on sait que le fichier contiendra exactement 500000 enregistrements logiques, d'autre part au cas où le fichier contiendra entre 300000 et 1000000 enregistrements.

Solution du problème 3.2

3.2.1. Question A

3.2.1.1. Question A.1

L'espace interbloc représente 3/4 * 1600 octets, soit 1200 octets. L'occupation est donc de 50 / 1250, soit 4 %. Le temps de lecture/écriture est de 10 + 0.008 * 50, soit 10.4 ms.

3.2.1.2. Question A.2

Lorsque les enregistrements sont de taille fixe, la structure la plus simple est de les mettre les uns derrière les autres, à charge pour les sous programmes de lecture et d’écriture de ces enregistrements de découper le bloc physique selon la taille connue des enregistrements logiques. Lorsqu’ils sont de taille variable, il faut connaître la taille de chacun. Le choix d’un caractère spécial comme séparateur n’est pas en général acceptable, car cela implique de l’interdire dans les enregistrements eux-mêmes, ce qui est une contrainte pour l’utilisateur. L’autre solution est de faire précéder chaque enregistrement de sa taille. Dans beaucoup de systèmes, la structure est définie de façon standard et complète, pour permettre de prendre en compte d'une part les enregistrements de taille variable, les blocs de taille variable, ainsi que les opérations de lecture arrière. Une certaine redondance est présente, pour permettre des contrôles. La structure d'un bloc physique pourrait être la suivante:

	numéro_bloc  2 octets
	long_bloc	  2 octets
		long_enrg		   2 octets
		enregistrement	   p octets	   n fois
		long_enrg		   2 octets
	long_bloc	  2 octets
	numéro_bloc  2 octets

Pour réaliser les opérations de lecture et d'écriture, on doit disposer d'un tampon de au moins T octets, et de trois variables numéro donnant le numéro du bloc en cours, long repérant la longueur du bloc courant et position repérant la position dans le bloc du prochain enregistrement à lire (ou écrire). Nous ne nous préoccupons ici que de la lecture avant, laissant au lecteur le soin de réaliser l'opération de lecture arrière. Les procédures pourraient être comme suit:

procédure lire_enrg(var enregistrement: tableau_octets; var l_enrg: entier);
début si position >= long - 4 alors
		numéro:=numéro+1; lire_bloc; {lecture physique dans le tampon[0..T-1]}
		si tampon[0..1] ≠ numéro alors erreur("numéro de bloc erroné") finsi;
		long := tampon[2..3]; position := 4;
	  finsi;
	  l_enrg := tampon[position .. position + 1];
	  enregistrement := tampon[position + 2 .. position + 1 + l_enrg];
	  position := position + 4 + l_enrg;
fin;
procédure écrire_enrg( enregistrement : tableau_octets; l_enrg : entier);
début si position + l_enrg + 8 > taille_max alors
		numéro := numéro + 1;			   { fin de préparation du bloc }
		tampon[0 .. 1] := numéro;
		tampon[2 .. 3] := position + 4;
		tampon[position .. position + 1] := position + 4;
		tampon[position + 2 .. position + 3] := numéro;
		écrire_bloc;					 { écriture physique du tampon }
		position := 4;
	  finsi;
	  tampon[position .. position + 1] := l_enrg;
	  tampon[position + 2 .. position + 1 + l_enrg] := enregistrement;
	  tampon[position + 2 + l_enrg .. position + 3 + l_enrg] := l_enrg;
	  position := position + 4 + l_enrg;
fin;

3.2.1.3. Question A.3

La taille d'un bloc est T = 8 + n * ( p + 4 ), soit dans notre cas, T = 8 + n * 54. On peut mesurer l'utilisation de deux façons, soit en prenant l'ensemble des informations écrites, soit en ne considérant que les enregistrements seuls. On a donc:

n	T	utilisation	util. stricte	temps
	8+n(4+p)	T/(T+1200)	np/(T+1200)	(10+810^-3 T)/n
20	1088	48 %	44 %	0.94 ms
50	2708	69 %	64 %	0.63 ms

3.2.2. Question B

3.2.2.1. Question B.1

En prenant 1 secteur par enregistrement logique, le coefficient d'utilisation du disque est de 50 / 1024, soit environ 4.9 %. Le temps d'une opération est de 9 ms par enregistrement logique.

3.2.2.2. Question B.2

Avec la méthode de regroupement définie en A.2, comme il faut un nombre entier de secteurs par bloc, on a donc:

n	T	s	utilisation	util. stricte	temps
	8+n(4+p)	⌈T/1024⌉	T/1024s	np/1024s	(8+s)/n
20	1088	2	53 %	49 %	0.5 ms
50	2708	3	88 %	81 %	0.22 ms

3.2.2.3. Question B.3

En conservant la méthode de A.2, la valeur optimale de n pour un bloc de s secteurs est la partie entière de (1024 * s - 8) / (p + 4). On a donc:

s	n	T	utilisation	util. stricte	temps
	⌊(1024s-8)/(p+4)⌋	8+n(4+p)	T/1024s	np/1024s	(8+s)/n
1	18	980	96 %	88 %	0.5 ms
2	37	2006	98 %	90 %	0.27 ms
3	56	3032	98.7 %	91 %	0.2 ms

3.2.3. Question C

3.2.3.1. Question C.1

Une numérotation linéaire possible est nv = ns + 16 * (nf + 20 * nc). Cette numérotation permet de donner des numéros consécutifs à tous les secteurs d'un même cylindre, et donc d'éviter les mouvements de bras entre secteurs virtuels voisins. L'algorithme permettant de retrouver les numéros de secteur, face, cylindre d'un secteur virtuel est le suivant:

ns := nv mod 16;

nf := (nv % 16) mod 20;

nc := (nv % 16) % 20;

3.2.3.2. Question C.2

L'espace alloué au fichier peut être représenté par la structure suivante:

espace = article s, i: entier;				{ taille 1er groupe et suivants }
			    nbg : entier;		{ nombre de groupes effectifs du fichier }
			    tab : tableau [0 .. 23] de entier;
			     {tab[i] est le numéro virtuel du premier secteur du groupe i}
	    finarticle;

Cette structure est contenue dans le descripteur du fichier. Elle est retrouvée depuis le disque lors de l'ouverture du fichier, et sera éventuellement réécrite sur disque en cas de modification (nouvelle allocation). Pour permettre de parcourir le contenu du fichier, on dispose d'une variable supplémentaire nsf qui repère le numéro logique du secteur correspondant au bloc actuellement dans le tampon. Ce numéro varie depuis 0 jusqu'à N-1, si N est le nombre total de secteurs du fichier. L'algorithme de lecture d'un enregistrement logique est le même que précédemment. Nous n'avons qu'à préciser l'opération de lecture des blocs physiques.

procédure lire_bloc;
début nsf := nsf + 1;
	  si nsf < espace.s alors nv := espace.tab[0] + nsf; {premier groupe}
	  sinon ng := (nsf - espace.s) % espace.i + 1;      {groupes suivants}
		    si ng ≥ espace.nbg alors erreur ("non alloué"); finsi;
		    nv := espace.tab[ng] + (nsf - espace.s) mod espace.i;
	  finsi;
	  ns := nv mod 16; nf := (nv % 16) mod 20; nc := (nv % 16) % 20;
	  lire_secteur (tampon, ns, nf, nc);
fin;

De même, l'algorithme d'écriture d'un enregistrement logique est le même que précédemment, et c'est même ce qui justifie de prendre la même structure de bloc. Nous n'avons qu'à définir la procédure d'écriture des blocs physiques.

procédure écrire_bloc;
début si nsf < espace.s alors nv := espace.tab[0] + nsf;  {premier groupe}
	  sinon ng := (nsf - espace.s) % espace.i + 1;       {groupes suivants}
		tantque ng ≥ espace.nbg faire
			si espace.nbg = 24 alors erreur ("trop de groupes"); finsi;
			demande_allocation( espace.tab[espace.nbg], espace.i);
			espace.nbg := espace.nbg + 1;
		fait;
		nv := espace.tab[ng] + (nsf - espace.s) mod espace.i;
	  finsi;
	  ns := nv mod 16; nf := (nv % 16) mod 20; nc := (nv % 16) % 20;
	  écrire_secteur (tampon, ns, nf, nc);
	  nsf := nsf + 1;
fin;

3.2.3.3. Question C.3

La réponse à B.3 précise qu'il y a 18 enregistrements logiques par secteur. Le nombre de secteurs alloués au fichier est s + (nbg - 1) * i. Donc le nombre d'enregistrements logiques du fichier est 18 * (s + (nbg - 1) * i) au plus, pour un nombre fixé de groupes. Si tous les groupes sont alloués, le nombre d'enregistrements peut atteindre 18 * (s + 23 * i). Par ailleurs, toujours pour un nombre de groupes fixé, il en contient:

nbg	nombre minimal d'enregistrements	nombre maximal d'enregistrements
0	0	0
1	1	18 * s
> 1	18 * (s + (nbg - 2) * i)) + 1	18 * (s + (nbg - 1) * i))

Cependant, le dernier groupe alloué ne sera occupé en moyenne qu'à 50 %. La perte sera donc de 9 * s ou de 9 * i suivant les cas. Ceci permet d'énoncer quelques critères de choix:

a) Si le nombre d'enregistrements logiques du fichier, disons N, est connu lors de la création, et ne doit pas varier, un seul groupe permet de diminuer les mouvements de bras, puisque l'espace alloué est contigu, donc occupe des cylindres consécutifs. Mais encore faut-il trouver un espace de s = N / 18 secteurs consécutifs libres.

b) Si le nombre N n'est connu que par sa limite inférieure N₁ et sa limite supérieure N₂, on doit avoir s + 23 * i ≥ N₂ / 18. Pour minimiser la perte d'espace pour non utilisation, on peut prendre i = (N₂ - N₁ ) / (18 * 24) et s = N₁ / 18 + i. La perte d'espace sera alors en moyenne équivalente à 9 * i enregistrements logiques du fichier. Mais encore faut-il trouver un espace libre contigu d'au moins s secteurs.

c) Il est toujours possible de diminuer s, pour faciliter l'allocation du premier groupe, mais il faut alors augmenter i en conséquence. Cependant, si l'allocation du premier groupe est impossible dans ce cas, il est inutile de prendre s < i, car l'allocation des groupes suivants sera de toute façon impossible. On peut donc en déduire que s ≥ N₂ / (18 * 24). Par ailleurs, on doit avoir i ≥ ((N₂ / 18) - s) / 23, pour pouvoir ranger les N₂ enregistrements.

3.2.3.4. Question C.4

Dans le cas où N = 500000, de a) ci-dessus, on en déduit que l'on peut prendre s = 500000 / 18 = 27778 secteurs. Ceci représente 10 % de l'espace total du disque, qu'il faut trouver de façon contiguë. Si ceci n'est pas possible, de c) ci-dessus, on en déduit que s ≥ 500000 / (18 * 24) = 1158 secteurs, et i ≥ (27778 - s) / 23.

Dans le cas où N₁ = 300000 et N₂ = 1000000, de b) ci-dessus, on en déduit que l'on peut prendre i = 700000 / (18 * 24) = 1621, et s = 16667 + 1621 = 18288. Notons que en vertu de c) ci-dessus, on doit avoir s ≥ 2315, et i ≥ (55560 - s) / 23.