Programmation des Systèmes
Système de gestion de fichiers
Travaux Dirigés assurés par Philippe Décogné
18/01/2003
Comment se décompose l'accès à un secteur du disque ?
Quelle phase de cet accès est la plus coûteuse ?
On considère un disque composé de 300 pistes numérotées de 0 à 299. Le bras est positionné sur la piste 50.
La liste des requêtes (n° de piste recherchée) à servir, donnée selon l'ordre d'arrivée, est la suivante:
- 62, 200, 150, 60, 12, 120, 250, 45, 10, 100
Donnez l'ordre de service des requêtes et le déplacement de bras total en résultant dans le cas :
- d'un service FCFS
- d'un service SSTF
- d'un service scan sens initial montant
Caractéristiques d'un disque dur
Le disque dur est composé d'un cylindre comportant plusieurs disques.
Chaque disque est organisé en pistes circulaires séparées par des espaces inter-pistes pour limiter les erreurs de positionnement à la frontière des pistes. Chaque piste est, à son tour, divisée en secteurs séparés par des espaces inter-secteurs pour limiter les erreurs de positionnement à la frontière des secteurs.
Un bras rétractable supporte les têtes de lecture, une par face, qui se déplacent toutes ensemble de la périphérie des disques vers le centre pour trouver la piste. Dans certains modèles, le bras de lecture ne se déplace pas, mais il y a autant de têtes de lecture que de pistes.
Ensuite les disques tournent pour venir mettre en face des têtes de lecture le secteur voulu. Les têtes de lecture ne reposent pas sur le disque dur pour éviter d'abîmer sa surface ; la technique utilisée s'apparente à celle des métros à coussin d'air.
Accès à un secteur d'un disque
Pour lire ou écrire un bloc de données sur le disque, il faut d'abord que le périphérique soit disponible, ensuite, s'il existe plusieurs canaux d'accès au périphérique, qu'un canal soit affecté au transfert.
Ce n'est qu'à partir de ce moment que la recherche d'un bloc sur le disque peut s'effectuer. Le système cherche d'abord la piste, puis le secteur, lit les données et les transfère.
Temps d'accès
Le temps de recherche de la piste se décompose en temps initial de démarrage (temps pour pousser le bras de lecture à sa vitesse de croisière) et temps de traversée des pistes.
Ce dernier temps se décompose, à son tour, en temps de démarrage (temps pour trouver la piste) et temps d'identification (temps requis pour confirmer l'identification de la piste).
Les temps d'attente varient suivant la politique de recherche utilisée, mais en moyenne, pour un accès séquentiel, on a les temps suivants :
- temps de recherche des pistes : 5 à 10 ms
- temps de recherche des secteurs : 3 ms
- temps de lecture d'un secteur : 6 ms
On voit que le temps le plus long est celui dédié à la recherche des pistes.
Politique de service de requêtes sur un disque
On distingue les politiques suivantes :
- FCFS (first come, first served)
Les requêtes sont servies dans l'ordre de leur arrivée. Technique très coûteuse en temps de déplacement du bras de lecture, si les requêtes successives concernent des pistes éloignées les unes des autres (cas de nombreux processus désirant accéder à des parties très différentes du disque).
Ordre de service des requêtes à partir de la piste 50 :
- 62, 200, 150, 60, 12, 120, 250, 45, 10, 100
Nombre de pistes parcourues :
| Piste initiale | Piste finale | Nb de pistes parcourues |
|---|---|---|
| 50 | 62 | 12 |
| 62 | 200 | 138 |
| 200 | 150 | 50 |
| 150 | 60 | 90 |
| 60 | 12 | 48 |
| 12 | 120 | 108 |
| 120 | 250 | 130 |
| 250 | 45 | 205 |
| 45 | 10 | 35 |
| 10 | 100 | 90 |
| Total | 906 | |
- SSTF (shortest seek time first)
Les requêtes sont servies de telle manière que le déplacement du bras soit minimum. Les temps d'accès sont alors moindres qu'avec la politique FCFS. Mais, il peut y avoir des risques de famine, si les nouvelles requêtes qui arrivent demandent un temps d'accès moindre que les requêtes déjà placées en file d'attente.
Ordre de service des requêtes à partir de la piste 50 :
- 45, 60, 62, 100, 120, 150, 200, 250, 12, 10
Nombre de pistes parcourues :
| Piste initiale | Piste finale | Nb de pistes parcourues |
|---|---|---|
| 50 | 45 | 5 |
| 45 | 60 | 15 |
| 60 | 62 | 2 |
| 62 | 100 | 38 |
| 100 | 120 | 20 |
| 120 | 150 | 30 |
| 150 | 200 | 50 |
| 200 | 250 | 50 |
| 250 | 12 | 238 |
| 12 | 10 | 2 |
| Total | 440 | |
- SCAN
Cette politique réduit les risques de famine encourus avec la politique SSTF. Le bras ne se déplace que dans une seule direction et sert les requêtes au fur et à mesure qu'il passe sur les pistes correspondantes jusqu'à atteindre la dernière piste dans cette direction. À ce moment, il repart dans la direction inverse.
Ordre de service des requêtes à partir de la piste 50 :
- 60, 62, 100, 120, 150, 200, 250, 45, 12, 10
Nombre de pistes parcourues :
| Piste initiale | Piste finale | Nb de pistes parcourues |
|---|---|---|
| 50 | 60 | 10 |
| 60 | 62 | 2 |
| 62 | 100 | 38 |
| 100 | 120 | 20 |
| 120 | 150 | 30 |
| 150 | 200 | 50 |
| 200 | 250 | 50 |
| 250 | 45 | 205 |
| 45 | 12 | 33 |
| 12 | 10 | 2 |
| Total | 440 | |
On peut aussi avoir une politique C-SCAN qui revient en début de disque une fois atteinte la fin du disque. On a alors le service suivant :
Ordre de service des requêtes à partir de la piste 50 :
- 60, 62, 100, 120, 150, 200, 250, 10, 12, 45
Nombre de pistes parcourues :
| Piste initiale | Piste finale | Nb de pistes parcourues |
|---|---|---|
| 50 | 60 | 10 |
| 60 | 62 | 2 |
| 62 | 100 | 38 |
| 100 | 120 | 20 |
| 120 | 150 | 30 |
| 150 | 200 | 50 |
| 200 | 250 | 50 |
| 250 | 10 | 240 |
| 10 | 12 | 2 |
| 12 | 45 | 33 |
| Total | 475 | |
Un processus lit séquentiellement un fichier de 8 Mo, à raison de 256 octets à la fois. On suppose que les blocs disque sont de 1 024 octets et qu'un numéro de bloc occupe 4 octets. Par ailleurs, le temps d'accès moyen au disque est de 40 ms.
Rappelez la structure d'un inode et d'un fichier UNIX.
Le système ne gère pas de mécanisme de buffer cache.
Donnez le nombre total d'accès disque nécessaire et le temps d'attente en entrées/sorties.
Le système gère un mécanisme de buffer cache.
Rappelez le fonctionnement de ce mécanisme.
Pourquoi la gestion de remplacement est-elle LRU plutôt que FIFO ?
Donnez le nombre total d'accès disque nécessaire et le temps d'attente en entrées/sorties.
L'écriture physique des blocs modifiés ne se fait que lorsqu'un bloc du buffer cache doit être libéré. Quel avantage et quel inconvénient cela présente-t-il ? Quel est alors le rôle de la primitive SYNC ?
Structure d'un inode et d'un fichier Unix
L'inode est un descripteur de fichier sur disque qui regroupent les informations suivantes :
- type du fichier et droits d'accès aux noeuds pour les différents utilisateurs,
- identité du propriétaire et du groupe,
- nombre de liens physiques,
- taille du fichier,
- date de dernière consultation, dernière modification des données, dernière modification du noeud,
- 13 adresses de blocs, dont 10 pointeurs sur des blocs de données et 3 pointeurs sur des blocs d'adresses, le premier en indirection simple, le second en indirection double, le troisième en indirection triple.
Les pointeurs d'adresses indirectes pointent sur un bloc de 256 pointeurs (par exemple), eux-mêmes pointant à leur tour sur un bloc de données de 1 Ko (par exemple). On peut adresser ainsi plus de 16 Go.
Système sans buffer cache
Comme il n'existe pas de buffer cache, il faut lire sur le disque 256 octets à chaque fois.
Les blocs sont de 1 024 octets. Il y a donc :
1 024 / 256 = 4 accès au disque
pour lire un bloc de données
Pour un fichier de 8 Mo, on a :
8 x 1 024 = 8 192 blocs
Il faudra donc lire tous les blocs de données en adressage direct, puis tous les blocs de données en adressage indirect simple. Enfin, il restera :
8 192 - 10 - 256 = 7 926 blocs de données à lire,
qui se trouvent forcément en adressage indirect double, puisque celui-ci permet de lire :
256 x 256 = 65 536 blocs de données
On supposera ici que l'inode est en mémoire, de telle sorte qu'on ne tiendra pas compte de l'accès au disque pour charger l'inode.
Pour chaque accès au disque, on lit d'abord le numéro de bloc (éventuellement indirect), puis le bloc de données.
On a ainsi :
- pour les 10 premiers blocs (adressage direct) :
- 4 accès disque pour chaque bloc de données (1 024 octets par bloc), soit : 4 x 10 = 40 accès disque
- pour les 256 suivants (indirection simple) :
- 4 accès disque pour lire le bloc d'adresses (4 octets par adresse, 256 adresses à lire),
- 4 accès pour lire chaque bloc de données
Soit : 8 x 256 = 2 048 accès disque
- pour les 7 926 suivants (indirection double) :
- 4 accès disque pour lire le premier niveau de bloc d'adresses (4 octets par adresse, 256 adresses à lire),
- 4 accès disque pour lire le deuxième niveau de bloc d'adresses (4 octets par adresse, 256 adresses à lire),
- 4 accès disque pour lire chaque bloc de données
Soit : 12 x 7 926 = 95 112 accès disque
Soit un total de :
40 + 2 048 + 95 112 = 97 200 accès disque
pour lire le fichier.
Si l'on tient compte d'un temps d'accès moyen au disque de 40 ms, le temps d'attente en entrées/sorties pour la lecture du fichier est de :
97 200 x 40 = 3 888 s, soit plus d'une heure.
Mécanisme de buffer cache
Le cache disque est un tampon en mémoire centrale qui contient une copie de certains secteurs du disque.
Quand un processus fait une requête d'entrée/sortie, le système vérifie d'abord dans le buffer cache si la requête peut être satisfaite, c'est-à-dire si les données demandées sont dans le buffer cache.
Si c'est le cas, la requête est satisfaite à partir du buffer cache, sinon le système va chercher l'information sur le disque et la copie dans le buffer cache, puis la sert à partir du buffer cache. Cela permet de diminuer le nombre d'accès au disque, donc le temps de service des requêtes.
En général, on rapatrie ou on envoie un bloc de données entier, ce qui permet de satisfaire le principe de localité spatiale.
Le cache est commun à tous les processus, ce qui permet d'utiliser un modèle lecteurs/rédacteurs pour le gérer et évite les transferts de mémoire à mémoire.
L'intérêt de ce mécanisme est qu'il minimise les accès au disque et gère au mieux les écritures différées. De plus, il permet de satisfaire le principe de localité spatiale.
Gestion FIFO - Gestion LRU
Gestion FIFO
Lors de la lecture du premier bloc indirect, on lit d'abord le bloc d'adresses qui se place en haut de la pile du disque cache. Puis on lit le bloc de données. À ce moment, le bloc d'adresses est placé en bas de la pile et le bloc de données en haut.
Lors de la lecture du bloc suivant, le bloc d'adresses étant déjà en cache, il suffit de charger le bloc de données. Le bloc d'adresses est alors sorti du cache, le bloc de données 1 est poussé en bas de la pile et le bloc de données 2 placé en haut de la pile.
Lors de la lecture du bloc suivant, on a perdu la référence au bloc d'adresses, il faut donc le recharger. Ainsi toutes les trois requêtes de blocs, il faut recharger le bloc d'adresses.
Gestion LRU
Dans ce mode, le bloc d'adresses, qui est celui qui doit être lu avant tout accès à un bloc de données, est toujours le plus récemment utilisé.
On se contente alors de remplacer le bloc de données précédemment chargé par le bloc de données à charger.
On a donc moins d'accès disque que dans le mode FIFO.
Système avec buffer cache en mode LRU
On supposera que la taille du buffer cache est au minimum de 3 blocs, de telle sorte qu'on n'ait jamais de relecture d'un bloc une fois lu.
Pour chaque accès au disque, on lit d'abord le numéro de bloc (éventuellement indirect), puis le bloc de données.
Il y a 8 192 blocs de données à lire, il y aura donc :
- 8 192 accès disque pour lire les blocs de données
En ce qui concerne les blocs d'adresses, on aura :
- pour les 10 premiers blocs (adressage direct) :
- 0 accès disque
- pour les 256 suivants (indirection simple) :
- 1 accès disque
- pour les suivants (indirection double) :
- 1 accès pour lire le premier niveau d'indirection
- 7 926 / 256 ≈ 31 accès disques pour le second niveau d'indirection
Soit un total de :
8 192 + 1 + 1 + 31 = 8 225 accès disque
pour lire le fichier.
Si l'on tient compte d'un temps d'accès moyen au disque de 40 ms, le temps d'attente en entrées/sorties pour la lecture du fichier est de :
8 225 x 40 = 329 s, soit environ 5 mn.
Écriture différée
L'avantage essentiel de ce mode est qu'il diminue sensiblement le nombre d'accès disque, donc le temps d'entrée/sortie.
Mais, par ailleurs, il y a un risque de perte de données en cas de panne de l'ordinateur. Les dernières modifications en cache ne sont pas écrites sur le disque.
Primitive sync : (void) sync(void);
Force l'écriture sur le disque des buffers modifiés dans le buffer cache.
La fonction peut retourner avant que tous les buffers soient vidés.
Librairie à utiliser : unistd.h.
Man page : sync(2)
On considère un système de gestion de fichiers qui fait de l'allocation par zone. L'ensemble du disque est constitué de 100 blocs, numérotés de 0 à 99. Trois fichiers existent sur le disque, définis comme suit, le reste de l'espace étant libre :
- F1 : début bloc 5, taille 20 blocs,
- F2 : début bloc 25, taille 5 blocs,
- F3 : début bloc 50, taille 10 blocs.
Les trois questions suivantes sont indépendantes, c'est-à-dire que, dans chaque cas, on part de la situation ci-dessus.
On veut rajouter 10 blocs au fichier F1. Quelles solutions proposez-vous suivant que l'implémentation séquentielle est simple ou avec extensions ? Justifiez votre raisonnement et évaluez le coût de ces solutions.
On veut créer un fichier F4 de 10 blocs. Où proposez-vous de le mettre ? Justifiez votre raisonnement.
On veut créer un fichier F4 de 40 blocs. Quelles solutions proposez-vous suivant que l'implémentation séquentielle est simple ou avec extensions ? Justifiez votre raisonnement.
L'allocation des zones sur le disque est la suivante :
Ajout de blocs
Implémentation séquentielle simple
Les blocs de fichier sont contigus. Il n'existe qu'une seule zone de blocs.
La seule solution pour rajouter 10 blocs au fichier F1 est de chercher une zone libre de :
20 + 10 = 30
blocs.
La première zone existante libre de 30 blocs se situe juste après F3. C'est celle qu'on choisira pour éviter une fragmentation inutile du disque.
Le coût en accès disque se composera :
- d'une lecture de F1
- de la réécriture après F3
Implémentation séquentielle avec extensions
Les blocs de fichier peuvent être chaînés de zone en zone.
On peut donc allouer une zone de 10 blocs :
- après F2, mais ceci empêchera F2 de s'étendre sans extension
- avant F3, mais ceci empêchera F1 de s'étendre sans extension
- après F3, mais ceci empêchera F3 de s'étendre sans extension
- juste avant la fin, il vaut mieux garder cette zone libre, car c'est la plus grande.
En fait, la meilleure solution est de minimiser les accès disque. Or il y a plus de chance que l'extension la plus proche de F1 soit dans le même bloc d'adresses, ou, en tout cas, dans le même groupe de blocs d'adresses lus en buffer cache, en particulier si l'on utilise une politique de pré-buffering (chargement en mémoire d'un bloc contigu au bloc demandé suivant le principe de localité spatiale). On choisira donc la zone juste après F2.
Création d'un fichier F4 de 10 blocs
La première zone existante libre de 10 blocs se situe juste après F2. C'est celle qu'on choisira pour éviter de fragmenter la zone la plus grande située après F3.
Création d'un fichier F4 de 40 blocs
Implémentation séquentielle simple
La seule zone libre de 40 blocs se situe juste après F3. C'est celle donc qu'on choisira.
Implémentation séquentielle avec extensions
Les blocs de fichier peuvent être chaînés de zone en zone.
On peut donc allouer une zone de 40 blocs :
- après F2, mais ceci empêchera F2 de s'étendre sans extension ; avec chaînage après F3
- avant F3, mais ceci empêchera F1 de s'étendre sans extension ; avec chaînage après F3
- après F3, mais ceci empêchera F3 de s'étendre sans extension
On choisira la dernière solution, car elle évite des chaînages successifs. Dans ce cas l'implémentation sera la même qu'en séquentiel simple.
