Solution TD 3

Université Mohammed V de Rabat Systèmes d’ExploitationII
Faculté des Sciences

Département d’informatique
TD3 : Gestion de la mémoire secondaire

Solution
I.
1. Chaque bloc de données peut contenir 256 pointeurs. Si on ne se préoccupe pas de
l'espace adressable avec des pointeurs de 4 octets, on obtient :
Taille = (12 * 1K) + (256 * 1K) + (256 * 256 * 1K) + (256 * 256 *256 * 1K)
direct ind. simple ind. double ind. triple
= (12 + 256 + 256*256 + 256*256*256) K
= 16,843,020 K octets. (bien plus grand que ce que les disques permettent)
2. Si on considère un fichier contenant 100,000 octets, on voit que

100,000 = 97 * 1024 + 672. Il faudra donc 98 blocs pour conserver les données de ce
fichier. Le inode ne dispose que de 12 pointeurs directs, il va donc falloir utiliser des blocs
supplémentaires (98-12=86) pour conserver le reste des données. Comme ces blocs de
données seront accessibles à partir du pointeur indirect simple du inode. Une partie d'un
bloc sera nécessaire pour conserver les 86 pointeurs sur des blocs de données. Le nombre
total de blocs utilisés est donc 98+1 = 99.
II. Sur le système qui nous intéresse ici :

• Le inode contient
• 12 pointeurs directs ;
• 1 pointeur indirect simple ;
• 1 pointeur indirect double ;
• 1 pointeur indirect triple.
• Un bloc fait 4K, soit 4096 octets.
• Un pointeur (adresse) occupe 4 octets.
• Un bloc peut donc contenir 4096/4 = 1024 pointeurs.
Blocs occupés par le fichier
Notre fichier compte 20,000,000 = 4882 * 4096 + 3328 octets. Il faudra donc 4883 blocs pour
conserver les données de ce fichier. Il faudra aussi leur ajouter des blocs qui vont être utilisés
pour stocker des pointeurs vers ces blocs de données.
On effectue donc le calcul suivant (sur les blocs) :
• Le fichier compte 4883 blocs de données.
• Les pointeurs directs du inode permettent d'accéder à 12 de ces blocs. Il donc 4871
blocs de données pour lesquels l'accès se fera à travers l'un des liens indirects.
• Le pointeur de lien indirect simple pointe sur un bloc qui contient 1024 pointeurs vers
des blocs de données. Nous avons donc ajouté 1 bloc de pointeurs, et il reste 4871 -
1024 = 3847 blocs à traiter.
• Le pointeur de lien indirect double permet d'accéder à 1024*1024 blocs, ce qui est
plus que suffisant. Il suffit d'utiliser 4 blocs de données pour stocker les 3847
pointeurs de blocs permettant d'accéder aux données restantes.
Nous aboutissons donc à la structure données par la figure suivante :
1
Fragmentation interne
Sur la figure, nous voyons l'espace alloué mais non utilisé :
• 4 octets sur le inode
• 4080 octets dans le bloc sur lequel pointe le pointeur indirect double.
• 996 octets dans le dernier bloc de pointeurs alloué.
• Finalement, 768 octets dans le dernier bloc de données.
La fragmentation interne totale sur le disque est donc de 5848 octets.
III. Un bloc contient 2048 octets. Il peut donc contenir jusqu'à 512 liens vers d'autres blocs.
On parle d'un fichier pour lequel 500 blocs sont utilisés pour stocker des liens.
• On sait que le lien indirect simple pointe vers un bloc contenant des liens directs vers
des blocs de données.
• De même, le lien indirect double pointe vers un bloc contenant des liens vers des blocs
contenant eux-mêmes des liens directs.
• Par conséquent, il y a 498 blocs de liens supplémentaires.
On a donc la structure suivante :
2
1. Si on fait le compte pour la taille max de fichier, on a :

• 10 blocs de données correspondant aux liens directs,
• 512 blocs de données correspondant au lien indirect simple (1 bloc de liens),
• 498 *512 blocs de données correspondant au lien indirect double (1 + 498 bloc de
liens).
Au total, 255 498 * 2K = 510 996 K = 523 259 904 octets.
Si on fait le compte pour la taille min, on a :
• 10 blocs de données correspondant aux liens directs,
• 512 blocs de données correspondant au lien indirect simple (1 bloc de liens),
• 497 *512 blocs de données correspondant au lien indirect double (1 + 497 bloc de
liens),
• Le dernier bloc de liens contient un seul lien (au lieu de 512), vers un bloc de données
ne contenant qu'un seul caractère (mais les blocs entiers sont allouées).
Au total : (10 + 512 + 497*512) * 2K + 1 = 522 211 329 octets.
2. On perd tous les blocs de données auxquels on accédait à travers les liens indirects double
et triple. Il ne nous reste donc plus que les blocs obtenus par accès direct ou accès indirect
simple, à savoir :
10 * 2048 + 512 * 2048 = 1 069 056 caractères.
On a donc perdu P = (2 500 000 - 1 069 056) / 2 500 000 = 57% du contenu du fichier.
3
IV. On est au secteur 2, on se déplace selon les numéros croissants des secteurs et les
requêtes en attentes sont les secteurs : 11, 5, 8 et 7
L’ordre de traitement serait 5, 7, 8 et 11.
V. La tête de lecture sert une requête piste 143, et vient de terminer une requête piste 125.
Ceci nous indique le sens du déplacement du bras. Elle était à 125 et se trouve à 143.
Donc c’est le sens croissant des pistes. (On en aura besoin pour certain algorithme où le
sens est important).
• PCTR : le plus court temps de recherche : 86, 147, 91, 177, 94, 150, 102, 175 et 130
De 143 on va a 147, 150, 130, 102, 94, 91, 86, 175 et 177 donc la distance parcourue
est :
150-143+150-86+177-86
• Scan : se déplace en servant d’un bout à l’autre donc :

De 143 on va a 147, 150, 175 et 177 continue jusqu’à 199 et rebrousse chemin en
servant 130, 102, 94, 91, 86 donc la distance parcourue est :
199-143+199-86
• C-Scan : se déplace en servant d’un bout à l’autre mais dans un sens donc il revient à
vide comme si la piste 0 était collée à la piste 199 :
De 143 on va a 147, 150, 175 et 177 continue jusqu’à 199 et rebrousse chemin en
allant directement à la piste 0 en servant 86, 91, 94, 102, 130 donc la distance
parcourue est :
199-143+130-0 plus le saut
• Look : se déplace en servant d’un bout à l’autre dans les deux sens en allant seulement
de la plus petite requête à la plus grande donc :
De 143 on va a 147, 150, 175 et 177 mais au lieu de continuer jusqu’à 199 il rebrousse
chemin en servant 130, 102, 94, 91, 86 donc la distance parcourue est :
177-143+177-86
• C-Look : se déplace en servant d’un bout à l’autre dans un seul sens en allant
seulement de la plus petite requête à la plus grande donc :
De 143 on va a 147, 150, 175 et 177 mais au lieu de continuer jusqu’à 199 il rebrousse
chemin et saute à la plus petite requête donc sert : 86, 91, 94, 102, 130 donc la distance
parcourue est :
177-143+177-86+ le saut

Solution TD 3

Transféré par

Droits d'auteur :

Formats disponibles

Solution TD 3

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Solution TD 3

Transféré par

Droits d'auteur :

Formats disponibles

Université Mohammed V de Rabat Systèmes d’ExploitationII

Faculté des Sciences

TD3 : Gestion de la mémoire secondaire

2. Si on considère un fichier contenant 100,000 octets, on voit que

II. Sur le système qui nous intéresse ici :

On a donc la structure suivante :

1. Si on fait le compte pour la taille max de fichier, on a :

• Scan : se déplace en servant d’un bout à l’autre donc :

Vous aimerez peut-être aussi