Systèmes de gestion de fichiers - SGF PDF

# Systèmes de gestion de fichiers - SGF ## Sommaire - **IV ** Introduction - **V ** Stratégie d’allocation - **VI ** Gestion de SGF - **VII ** Algo de remplacement - **VIII ** Algorithmes - **IX ** Structure logique des disques : implantation du SGF sur le disque - **X ** Méthodes d’...

# Systèmes de gestion de fichiers - SGF ## Sommaire - **IV ** Introduction - **V ** Stratégie d’allocation - **VI ** Gestion de SGF - **VII ** Algo de remplacement - **VIII ** Algorithmes - **IX ** Structure logique des disques : implantation du SGF sur le disque - **X ** Méthodes d’allocation ## IV Introduction - Le système de gestion de fichiers (SGF) est la partie la plus visible d'un système d'exploitation, qui se charge de gérer le stockage et la manipulation de fichiers (sur une unité de stockage : Un SGF a pour principal rôle de gérer les fichiers et d'offrir les primitives pour manipuler ces fichiers partition, disque, CD, disquette. ## V Algorithmes ### Organisation physique des disques - Il est constitué d'un ou de plusieurs plateaux. - Chaque plateau est divisé en pistes (tracks). - Chaque piste est divisée en secteurs (sectors). - Le cylindre est formé par les pistes de même rayon sur chaque plateau. - Le formatage est effectué à deux niveaux. - En usine : le formatage bas niveau des pistes et secteurs. - Par l'utilisateur : Effacement ou réécriture des données. - La capacité d'un disque dépend: - De la taille des secteurs. - Du nombre de cylindres et donc du nombre de plateaux. - *Taille d'un disque* = (Nombre de cylindre) x (Nombre de piste par cylindre) x (Nombre moyen de secteur par piste) x (Taille du secteur) - *Exemple*: - Nombre de piste par cylindre 255 - Nombre de cylindre = 36481 - Nombre moyen de secteur par piste = 63 - Taille du secteur = 512 octets - *Taille du disque* ≈ 300 GB (255 * 36481 * 63 * 512 = 300066439680 octets) ### Algorithmes d'ordonnancement du bras du disque - **Application 1:** - On considère un disque caractérisé par : - Nombre de Cylindres : 1024 - Nombre de pistes par cylindre : 16 - Secteurs par piste : 64 - En supposant qu'un secteur contient 512 octets, quel est la taille maximale que peut utiliser ce système? - La taille maximale du disque est donnée par le nombre total de secteurs multiplié par la taille de chaque secteur : - Taille maximale = Total de secteurs × Taille du secteur - Taille maximale = 1048576 × 512 octets - Taille maximale = 536870912 octets - *En Ko (Kilooctets):* 536870912 / 1024 = 524288 Ko - *En Mo (Mégabytes):* 524288 / 1024 = 512 Mo - *En Go (Gigabytes):* 512 / 1024 = 0.5 Go ### L’organisation du disque - Organisation typique du poste de travail - MBR - Partition système - Partition données - Disque - *Master Boot Record (MBR)* Le MBR contient : - Table des partitions - Programme d'amorçage (charge le noyau du système) - **Partitionnement** - Permet de cloisonner le disque pour : - Cohabiter plusieurs systèmes (ex : DOS. UNIX) - Isoler des parties du système - Types de Partitions: - Primaire : Jusqu'à 4 partitions primaires par disque. - Étendue : Divise une partition primaire en partitions logiques (pas de secteur de démarrage). ### Algorithmes d’ordonnancement du bras du disque - Plusieurs algorithmes existent pour ordonnancer les requêtes d'I/O: - Politique *First Come Fist Served*. - Politique *Shortest Service Time First (SSTF)*. - Politique *SCAN (balayage)* - Imaginons qu'une file de requêtes contienne les blocs suivants : 98, 183, 37, 122, 14, 124, 65, 67 et que la tête soit positionnée sur le bloc 53 - **Politique *First Come Fist Served***. - **Shortest Service Time First (SSTF)** - Sélectionner la requête avec le minimum *seek time* à partir de la position courante de la tête *bras du disque*. - **Politique SCAN (balayage)** - Le bras de la tête va « au début » du disque puis « à la fin » ## VI Les tâches d’un SGF - Le stockage des fichiers sur le disque dur - La gestion de l'espace libre sur le disque dur - La gestion des fichiers dans un environnement multiutilisateurs - La fourniture d'une interface conviviale pour manipuler les fichiers (commandes et des attributs simples pour manipuler et décrire les fichiers) ## Application 2 - Sur un disque doté de 1 000 cylindres, les nombres 0 à 999 représentent les différentes pistes sur lesquelles le bras du disque doit se déplacer pour satisfaire les requêtes de la file du disque. Supposons que la dernière requête traitée se situait à la piste 345 et que la tête se déplaçait vers la piste 0. La file du disque contient les requêtes des pistes suivantes (ordre FIFO) : 123, 874, 692, 475, 105, 376 - Calculer le nombre de pistes traversées pour les algorithmes d'ordonnancement suivants *(*on représentera les déplacements sur un diagramme)*: - FIFO - SSTF - SCAN - *Correction: Application 2* - Calculons le nombre total pistes traversées pour chaque algorithme d'ordonnancement (FIFO, SSTF, SCAN) avec les données suivantes : - Nombre total de cylindres (pistes 0 à ­999): 1000 - Position actuelle de la tête: Piste 345 - Sens de déplacement: Vers la piste 0 - *File de requêtes*: 123, 692, 475, 105, 376 - *Correction: Application 2* - **FIFO** - Dans cet algorithme, les requêtes sont traitées dans l'ordre d'arrivée (FIFO). Le bras du disque se déplace de la position actuelle vers la première requête dans la file, puis vers la suivante, et ainsi de suite. - *Étapes de déplacement:* - Position initiale: 345, direction vers 0. - Requêtes: [123, 874, 692, 475, 105, 376] - *Calcul des déplacements*: - De 345 à 123: Déplacement = 345-123=222 pistes. - De 123 à 874 : Déplacement = 874-123=751 pistes. - De 874 à 692 : Déplacement = 874-692=182pistes. - De 692 à 475 : Déplacement = 692-475=217pistes. - De 475 à 105 : Déplacement = 475-105=370pistes. - De 105 à 376 : Déplacement = 376-105=271pistes. - *Total des déplacements FIFO*: 222+751+182+217+370+271=2013 pistes - *Correction: Application 2* - **SSTF** - Dans l'algorithme SSTF, le bras du disque se déplace toujours vers la requête la plus proche de sa position actuelle, afin de minimiser le temps de déplacement. - *Étapes de déplacement*: - Position initiale 345, Requêtes : [123, 874, 692, 475, 105, 376] - *Séquence des déplacements:* - Départ de la piste 345. - La piste la plus proche est 376. - Ensuite, la piste la plus proche de 376 est 475. - Ensuite, la piste la plus proche de 475 est 692. - Ensuite, la piste la plus proche de 692 est 874. - Ensuite, la piste la plus proche de 874 est 123. - Enfin, la piste la plus proche de 123 est 105. - *Calcul des pistes traversées:* - 345-376 = 31 - 376-475 = 99 - 1475-692 = 217 - 692-874 = 182 - 874-123 = 751 - 123-105 = 18 - *Total des pistes traversées:* 31+99+217+182+751+18 = ­1298 - *Nombre total de pistes traversées en SSTF:* 1298 - *Correction: Application 2* - **SCAN** - L'algorithme SCAN déplace la tête vers extrémité (ici vers 0 car elle se déplace vers cette direction), puis remonte pour satisfaire les requêtes. - *Étapes de déplacement*: - Position initiale: 345, Requêtes : [123, 874, 692, 475, 105, 376] - Départ de la piste 345.Se déplace d'abord vers 0 en traitant les requêtes rencontrées en chemin. Ensuite, remonte pour satisfaire les requêtes restantes dans l'ordre croissant. - *Calcul des pistes traversées:* - 345-123 = 222 - 123­-105= 18 - 105-0|= 105 - 0­376| = 376 - 376­-475= 99 - 475­-692 = 217 - 692­-874 = 182 - *Total des pistes traversées:* 222 + 18 + 105 +376 + 99 +217 + 182 = 1219 - *Diagramme des déplacements:* 345­123 → 105 → 0 → 376 → 475 → 692 → 874 - *Correction: Application 2* - **Résumé des résultats** | Algorithme | Nombre total de pistes traversées | | ----------- | -------------------------------- | | FIFO | 2013 | | SSTF | 1298 | | SCAN | 1219 | - SCAN est l'algorithme le plus efficace dans ce cas avec 1219 pistes traversées. - SSTF est également efficace avec 1298 pistes traversées. - FIFO est le moins efficace avec 2013 pistes traversées car il ne tient pas compte de l'ordre optimal des requêtes. ## VII Méthodes d’allocation - Méthodes d'allocation: Principe de l'allocation contiguë : - L'allocation contiguë est une méthode classique pour stocker des fichiers sur un disque. - **Blocs consécutifs**: - Les fichiers sont stockés dans des blocs de mémoire contigus (consécutifs) sur le disque. - **Temps de positionnement minimal:** - Comme les blocs d'un fichier sont disposés de manière contiguë, les têtes de lecture/écriture du disque n'ont pas besoin de se déplacer fréquemment, ce qui réduit le temps d'accès. - **Entrée de répertoire simplifiée:** - Chaque entrée du répertoire contient : - L'adresse du premier bloc du fichier. - La longueur du fichier ( exprimée en nombre de blocs ). - Méthodes d'allocation: Principe de l'allocation contiguë : - **Problèmes majeurs:** - Fragmentation externe: Au fil du temps, des fichiers sont supprimés et de nouveaux fichiers sont créés, laissant des espaces libres dispersés sur le disque. - Il devient difficile de trouver un espace contigu assez grand pour de nouveaux fichiers. - Fichiers de taille variable : Les fichiers peuvent grandir ou rétrécir, posant des problèmes d'espace : - Trop d'espace : Si l'espace alloué est plus grand que nécessaire, cela entraîne une *fragmentation interne* (perte d'espace inutilisé). - Pas assez d'espace: Si le fichier doit s'agrandir mais qu'il n'y a pas assez d'espace libre contigu a côté du fichier, il faut déplacer le fichier vers une autre zone avec suffisamment d'espace libre. - **Solutions:** - Pour résoudre la fragmentation externe, il peut être nécessaire de faire un compactage du disque, c'est-à-dire déplacer des fichiers pour regrouper les espaces libres - Méthodes d'allocation: Principe de l'allocation non contiguë : - Méthode d'allocation indexée (« i-nodes ») - Méthode d'allocation chaînée - *Exemple d'une chaîne blocs:* - [Bloc 5] -> [Bloc 9] -> [Bloc 2] -> NULL *(EOF ­- End of File)* - Bloc 5 contient des données et pointe vers le Bloc 9. - Bloc 9 contient des données et pointe vers le Bloc 2. - Bloc 2 contient des données et marque la fin de la chaîne. - *Avantages de l'allocation chaînée* - *Pas de fragmentation externe*: - Les blocs peuvent être stockés n'importe où sur le disque. - Il n'est pas nécessaire de trouver un espace contigu pour le fichier. - *Pas de limite de taille:* - Le fichier peut s'étendre en ajoutant simplement de nouveaux blocs à la chaîne - *Méthodes d'allocation: Principe de l'allocation non contiguë:* - *Méthode d'allocation indexée (« i-nodes ») | Type de pointeur | Description | | ---------------- | ----------- | | Pointeurs directs | Pointent directement vers les blocs de données | | Pointeur indirect simple | Pointe vers un bloc contenant des pointeurs vers les blocs de données | | Pointeur indirect double | Pointe vers un bloc de pointeurs indirects simples | | Pointeur indirect triple | Pointe vers un bloc de pointeurs indirects doubles |