Systèmes d’Exploitation I

Systèmes d’Exploitation I Chapitre IV : Système de Gestion des Fichiers Amine DHRAIEF 1 [ère] année ESEN, Université de la Manouba À quoi ressemble un disque dur ? 18/04/18 OS I 2 Structure physique d'un disque dur 18/04/18 OS I 3 Structure physique d'un disque dur A : plateau ; B : bras ; C : tête ; D : cylindre ; E : piste ; F : secteur géométrique Source : Wikimedia Commons Structure physique d'un disque dur Source : Wikimedia Commons (A) piste, (B) secteur géométrique, (C) secteur d'une piste, (D) bloc Le secteur (ou bloc) est la plus petite unité physique de stockage sur un support de donnée Sa taille varie de 512 octets à 4096 octets 18/04/18 OS I 5 Géométrie d'un disque dur Adressage CHS : Cylinder/Head/Sector Cylindre: superposition de plusieurs pistes Les pistes au dessus les unes des autres sont têtes de lecture 18/04/18 OS I 6 Géométrie d'un disque dur Adressage CHS : Cylinder/Head/Sector Head: Les têtes de lecture/enregistrement sont solidaires des bras mobiles Le plus souvent il y a une tête par surface soit deux par plateau Le chemin parcouru par une tête particulière sur un cylindre particulier s'appelle une piste Secteur : La piste est divisée en secteurs (aussi appelés blocs) contenant les données. La taille d'une piste diminue en allant vers le centre du disque → le nombre de secteur par piste diminue aussi en allant vers le centre Taille d'un secteur plus commune= 512 octets 18/04/18 OS I 7 Géométrie d'un disque dur Adressage CHS : Cylinder/Head/Sector L'adresse CHS est simplement constituée par l'assemblage des trois composants décrits ci- dessus. Le tout premier secteur d'un disque est à l'adresse 0 / 0 / 1 : c'est le premier secteur accédé par la première tête positionnée sur le premier cylindre. Le suivant sera 0 / 0 / 2 (ce secteur est naturellement atteint juste après par la même tête) 18/04/18 OS I 8 Taille d'un disque 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) 18/04/18 OS I 9 Pourquoi a-t-on besoin de fichiers ? 18/04/18 OS I 10 Définition d'un fichier Toutes les applications informatiques doivent enregistrer et retrouver des informations. L’espace d’adressage étant insuffisant, on utilise des fichiers pour cela. Fichier (nom masculin) Meuble, boîte servant à recevoir des fiches. Ensemble de données regroupées en une unité indépendante de traitement informatique. 18/04/18 OS I 11 Définition #1 : Dictionnaire Larousse ##### Fichier (nom masculin) : Ensemble organisé d'informations, désigné par un nom précis, que le système d'exploitation d'un ordinateur manipule comme une simple entité, dans sa mémoire ou sur un support de stockage . 18/04/18 OS I 12 Définition #2 : Wikipedia ##### Un fichier informatique est au sens commun, une collection, un ensemble de données numériques réunies sous un même nom, enregistrées sur un support de stockage permanent, appelé mémoire de masse, tel qu'un disque dur, un CD-ROM, une mémoire flash ou une bande magnétique, et manipulées comme une unité. 18/04/18 OS I 13 Information indépendante du processus Un processus en cours d’exécution peut enregistrer une quantité d’informations dans son espace d’adressage mais cette façon de faire présente trois inconvénients : 1)La capacité de stockage est limitée à la mémoire vive. Cette taille peut convenir pour certaines applications, mais elle est beaucoup trop faible pour d’autres (applications des banques, réservations, téléchargement p2p,...) 2)Les informations stockées en mémoire vive sont perdues, lorsque le processus se termine ou lors du plantage de l'ordinateur. Pour un grand nombre d'applications, les informations doivent être conservées pendant des durées importantes. 3)Il ne peut pas y avoir d’accès simultané à ces informations. Un répertoire téléphonique stocké dans l’espace d’adressage d’un processus ne peut être examiné que par ce seul processus (pour les raisons de protection des données expliquées lors de l’étude des processus), de telle sorte qu’on ne peut rechercher qu’un seul numéro à la fois. → Pour résoudre ce problème, il faut rendre l’information indépendante d’un processus donné. 18/04/18 OS I 14 Stockage à long terme des informations Trois caractéristiques sont donc requises pour le stockage des informations à long terme : 1) Il faut pouvoir stocker des informations de très grande taille ; 2) Les informations ne doivent pas disparaître lorsque le processus qui les utilise se termine ; 3) Plusieurs processus doivent pouvoir accéder simultanément aux informations. 18/04/18 OS I 15 Fichiers = solution au problème La solution à tous ces problèmes consiste à stocker les informations dans des fichiers sur des disques ou d’autres supports. Les processus peuvent alors les lire ou en écrire de nouvelles. Les informations stockées dans des fichiers doivent être permanentes, c’est-à- dire non affectées par la création ou la fin d’un processus. Un fichier ne doit disparaître que lorsque son propriétaire le supprime explicitement. 18/04/18 OS I 16 Disque= suite de blocs Nous considérons un disque comme une suite séquentielle de blocs de taille fixe qui supportent deux opérations Lire le bloc k Écrire le bloc k → Ces deux opérations permettent en principe de résoudre le stockage à long terme des informations. 18/04/18 OS I 17 Des questions évidentes ##### Voici quelques questions que l'on se pose rapidement : 1)Comment trouve-t-on l'information ? 2)Comment empêche-t-on un utilisateur de lire les données d'un autre utilisateur ? 3)Comment sait-on qu'un bloc est libre ? 18/04/18 OS I 18 Vie et mort d'un fichier Le fichier (file) est l'unité d'information qui est créée par un processus. L'information enregistrée dans des fichier doit être persistante → c'est-à-dire qu'elle ne doit pas être affectée par la création ou la fin d'un processus Un fichier doit disparaître quand son propriétaire le demande expressément 18/04/18 OS I 19 Qui les gère alors ? Les fichiers sont gérés par le système d’exploitation. La façon dont ils sont structurés, nommés, utilisés, protégés et implémentés sont des points majeurs de la conception du système d’exploitation. La partie du système d’exploitation qui gère les fichiers est appelée le gestionnaire du système de fichiers (en anglais file system) 18/04/18 OS I 20 Les fichiers 18/04/18 OS I 21 Les fichiers du point de vue utilisateur ##### Le système de fichiers est la partie la plus visible d’un système d’exploitation. La plupart des programmes lisent ou écrivent au moins un fichier, et les utilisateurs manipulent beaucoup de fichiers. De nombreuses personnes jugent un système d’exploitation sur la qualité de son système de fichiers : son interface, sa structure et sa fiabilité. 18/04/18 OS I 22 Les fichiers du point de vue utilisateur L’utilisateur attache la plus grande importance à l’interface d’un système de fichiers, c’est-à-dire à la manière de nommer les fichiers, de les protéger, aux opérations permises sur eux, etc. Il est moins important pour lui de connaître les détails de son implémentation, c’est-à-dire de connaître le nombre de secteurs d’un bloc logique ou de savoir si l’on utilise des listes chaînées ou des tables de bits pour mémoriser les emplacements libres. Ces points sont, en revanche, fondamentaux pour le concepteur du système de fichiers. 18/04/18 OS I 23 Nom d’un fichier : Pourquoi ? Les fichiers sont un mécanisme d'abstraction. Ils permettent d’écrire des informations sur le disque et de les lire ultérieurement. Ceci doit être fait de manière à masquer le fonctionnement et l’emplacement de stockage des informations à l’utilisateur. Il ne doit pas avoir à choisir tel ou tel secteur, par exemple. La gestion et l’affectation des noms des objets sont les parties les plus importantes d’un mécanisme abstrait. Un processus qui crée un fichier lui attribue un nom. Lorsque le processus se termine, le fichier existe toujours et un autre processus peut y accéder au moyen de ce nom. 18/04/18 OS I 24 Nom d’un fichier : Règles de formation ? Les règles d’affectation des noms de fichiers varient d’un système à un autre, mais tous les systèmes d’exploitation autorisent les noms de fichiers constitués de chaînes de un à huit caractères non accentués. Ainsi « tunis » et «ariana » sont des noms de fichiers valides. Les chiffres et des caractères spéciaux sont quelquefois autorisés. Ainsi « 2 », « urgent! » et « Fig.2-14 » peuvent être des noms valides. Certains systèmes de fichiers différencient les lettres majuscules et minuscules alors que d’autres ne le font pas. Unix fait partie de la première catégorie et MS-DOS de la deuxième. Les noms suivants désignent donc des fichiers distincts sur un système Unix : « tunis », «Tunis» et « TUNIS». Sur MS-DOS, ils désignent le même fichier. 18/04/18 OS I 25 Nom de fichier: extension De nombreux systèmes d’exploitation gèrent des noms en deux parties, les deux parties étant séparées par un point, comme dans « prog.c ». La partie qui suit le point est alors appelée extension ; elle donne en général une indication sur la nature du fichier. Sous MS-DOS, par exemple, les noms de fichiers comportent 1 à 8 caractères éventuellement suivis d’une extension de 1 à 3 caractères. Sous Unix, la taille de l’extension éventuelle est libre, le fichier pouvant même avoir plus d’une extension comme dans « prog.c.Z ». Dans certains cas, les extensions sont simplement des conventions et ne sont pas contrôlées. Un fichier « fichier.txt » est vraisemblablement un fichier texte, mais ce nom est destiné davantage au propriétaire du fichier qu’au système d’exploitation. En revanche, certains compilateurs C imposent l’extension « .c » à tous les fichiers à compiler 18/04/18 OS I 26 La structure des fichiers ##### Les fichiers peuvent être structurés de différentes manières Suite d'octets Suite enregistrement Arbre 18/04/18 OS I 27 Fichier= suite d'octets Le fichier est une suite d'octets sans structure Le système d'exploitation ne connaît pas et ne s'occupe pas du contenu de ce fichier Il ne voit que des octets Toute signification doit être apporté par le programme des utilisateurs UNIX et Windows suivent tout deux cette approche 1 octet 18/04/18 OS I 28 Fichier= suite d'enregistrements Le fichier est une suite d'enregistrements de longueur fixe Concept principal : une opération de lecture renvoie un enregistrement/une opération d’écriture réécrit ou ajoute un enregistrement 80 caractère → carte perforées de 80 colonnes 132 caractères → imprimantes de 132 colonnes Les programmes lisaient les données par bloc de 80 caractère est écrivaient par bloc de 132 caractères Obsolète 18/04/18 OS I 29 Fichier= arbre ##### Le fichier est un arbre d'enregistrement Les enregistrements n'ont pas la même longueur Chaque enregistrement contient une clé dont la position est fixe dans l'enregistrement L'arbre est trié en fonction des clés → permet de rechercher rapidement une clé donnée L'opération fondamentale ne consiste pas à obtenir le prochain enregistrement, mais obtenir un enregistrement avec une clé donnée 18/04/18 OS I 30 Les types de fichiers La plupart des systèmes d'exploitation supportent plusieurs types de fichiers UNIX est Windows ont des fichiers ordinaires et des répertoires UNIX traite aussi des fichiers spéciaux caractère et bloc Les fichiers ordinaires ( regular files ) sont ceux qui contiennent les informations des utilisateurs. Ils sont soit des fichiers en code ASCII, soit des fichiers binaires. Les répertoires ( directories ) sont des fichiers systèmes qui conservent la structure du système de fichiers Les fichiers spéciaux caractère ( character special files ) sont liés aux périphériques entrées/sorties Les fichiers spéciaux bloc ( block special files ) servent à modéliser les disques. 18/04/18 OS I 31 Les fichiers ASCII ##### Les fichiers ASCII se composent de lignes de texte Chaque ligne se termine par le caractère retour chariot (CR : Carriage Return) ou le caractère saut de ligne (LF : Line Feed) On peut les afficher et les éditer avec n'importe quel éditeur de texte 18/04/18 OS I 32 Les fichiers binaires Ce ne sont pas des fichiers ASCII ! Si on les affiche cela donne un résultat incompréhensible Ils possèdent une structure interne connue des programme qui les exploitent Bien que techniquement le fichier soit juste une structure d'octets, le système d'exploitation exécutera ce fichier seulement s'il possède un certain format 18/04/18 OS I 33 Les fichiers binaires ###### Un fichier binaire comporte généralement cinq parties : L'en-tête ( header ) Le code Les données Les bits de translation ( relocation ) La table des symboles 18/04/18 OS I 34 Les fichiers binaires Le début de l'en-tête est un nombre magique (Magic number) C'est une valeur qui identifie le fichier comme étant un fichier exécutable Pour éviter l’exécution accidentelle d'un fichier qui ne possède pas ce format 18/04/18 OS I 35 Les fichiers binaires ##### Le code et les données du programme lui même suivent l'en- tête Ils sont chargés en mémoire et déplacés à l'aide des bits de translation 18/04/18 OS I 36 L'accès au fichiers : accès séquentiel ##### Les premiers systèmes d'exploitation proposaient un seul type d'accès au fichiers : l'accès séquentiel ( sequential access ). Dans ce système, un processus pouvait lire tous les octets ou tous les enregistrements d'un fichier dans l'ordre en commençant au début Les fichiers séquentiels étaient pratiques quand le support de stockage était une bande magnétique . 18/04/18 OS I 37 L'accès au fichiers : accès aléatoire Lorsque les disques ont servi à l'enregistrement des fichiers, il est devenu possible de lire des octets ou des enregistrement d'un fichier dans n'importe quel ordre Les fichiers dont les octets ou les enregistrements peuvent être lus dans n'importe quel ordre sont appelés fichier à accès directe ou accès aléatoire (random access) 18/04/18 OS I 38 Les attributs des fichiers Chaque fichier possède un nom et des données. Les systèmes d'exploitation associent des informations complémentaire : l'heure et la date de sa création et sa taille → Ces informations sont appelés les attributs du fichier ( file's attributes ) ou metadonnées ( metadata ) 18/04/18 OS I 39 Les attributs des fichiers 18/04/18 OS I 40 Les opérations sur les fichiers Create Delete Open Close Read Write Append Seek Get atributes Set attributes Rename 18/04/18 OS I 41 Les répertoires 18/04/18 OS I 43 Les répertoires : des fichiers comme d'autres ? Pour conserver une trace des fichiers, les systèmes de fichiers possèdent généralement des répertoires (directory) ou des dossiers (folders) Les répertoires sont eux mêmes des fichiers dans nombre de systèmes 18/04/18 OS I 44 Les répertoires sous UNIX Sur un système Unix les fichiers sont organisés, du point de vue de l’utilisateur, selon un domaine de nommage structuré en arbre, et dont les éléments principaux sont les répertoires et les chemins. 18/04/18 OS I 45 Les répertoires Chaque nœud de l’arbre, hormis les feuilles, est un répertoire Le répertoire correspondant à la racine de l’arbre est appelé le répertoire racine ( root directory en anglais). Par convention, son nom est une oblique « / » (slash en anglais). Les noms de fichiers d’un même répertoire doivent être différents, mais le même nom peut être utilisé dans des répertoires différents 18/04/18 OS I 46 Les chemins d'accès : absolue ou relatif Pour identifier un fichier particulier, on utilise un chemin ( path en anglais), c’est-à-dire la suite des noms des répertoires qui conduisent au fichier, séparés par des obliques. Si le premier élément de départ est une barre oblique, le chemin est dit absolu ( absolute path name ). Son point de départ est alors le répertoire racine. Exemple : /home/amine/Dropbox/Cours/Cours-ESEN/L1-OS-I/ Sinon (le premier élément est un nom de répertoire ou le nom du fichier lui- même), le chemin est dit relatif : son point de départ est alors le répertoire de travail courant du processus en cours, répertoire qui lui est associé lors de sa création. Exemple : Dropbox/Cours/Cours-ESEN/L1-OS-I/ 18/04/18 OS I 47 Les répertoires spéciaux ##### Chaque répertoire contient au moins deux répertoires, notés « . » et « .. » : ils représentent respectivement le répertoire courant et son répertoire parent. ##### Dans le cas du répertoire racine, ils coïncident. 18/04/18 OS I 48 Dessine moi un système de fichiers ? 18/04/18 OS I 49 La conception des systèmes de fichiers utilisateur vs. concepteur Nous examinons maintenant le système de fichiers du point de vue du concepteur. Les utilisateurs se préoccupent des noms des fichiers, des opérations qui permettent de les manipuler, de l’arborescence des fichiers, ... Les concepteurs portent d'avantage leur attention sur l’organisation de l’espace du disque et sur la manière dont les fichiers et les répertoires sont sauvegardés. → Ils recherchent un fonctionnement efficace et fiable 18/04/18 OS I 50 L'organisation du système de fichier rôle de l'MBR Les systèmes de fichiers sont enregistrés sur des disques. Les disques peuvent être divisés en une ou plusieurs partitions, avec des systèmes de fichiers indépendants sur chaque partition. Le secteur 0 du disque appelé enregistrement d'amorçage maître (MBR – Master Boot Record) sert à amorcer la machine La fin du MBR comprend la table de partitions, laquelle indique l'adresse de début et de fin de chaque partition Une de ces partitions est marquée comme étant la partition active 18/04/18 OS I 51 L'organisation du système de fichier le bloc d'amorçage Quand l’ordinateur est amorcé, le BIOS lit et exécute le MBR Le programme MBR détermine la partition active, y lit le premier bloc appelé bloc d'amorçage ( boot block ) et l'exécute Le programme du bloc d'amorçage charge le système d'exploitation contenu dans cette partition 18/04/18 OS I 52 L'organisation du système de fichier Pour une question d'uniformité, chaque partition commence un bloc d'amorçage, même si elle ne contient pas de système d'exploitation Elle pourrait en contenir un ultérieurement Une organisation possible d'un système de fichiers 18/04/18 OS I 53 L'organisation du système de fichier le superbloc Après le bloc de boot, vient généralement le superbloc ( superblock ) Contient tout les paramètres clé concernant le système de fichier Contient un numéro magique qui identifie le type de système de fichier 18/04/18 OS I 54 Organisation logicielle de l’espace du disque Les fichiers étant habituellement sauvegardés sur des disques, l’organisation logicielle de l’espace du disque est primordiale pour les concepteurs de systèmes de fichiers. Celle-ci porte sur la stratégie de stockage, sur la taille des blocs et sur la façon de repérer les blocs libres. 18/04/18 OS I 55 Organisation logicielle de l’espace du disque Stratégie de stockage Il existe deux stratégies pour stocker un fichier de n octets : on alloue n octets consécutifs sur le disque ou on divise le fichier en plusieurs blocs (pas nécessairement contigus/adjacents). Si l’on sauvegarde un fichier sur un nombre contigu d’octets, on doit le déplacer chaque fois que sa taille augmente (ce qui arrive fréquemment). La plupart des concepteur systèmes de fichiers préfèrent donc stocker les fichiers dans plusieurs blocs de taille fixe, pas nécessairement adjacents. 18/04/18 OS I 56 Organisation de l’espace du disque Taille des blocs Il faut alors déterminer la taille optimale d’un bloc. Le compromis habituellement adopté consiste à prendre des blocs de 512 octets, 1 Ko ou 2 Ko. Si l’on prend des blocs de 1 Ko sur un disque dont les secteurs font 512 octets, le système de fichiers lit et écrit deux secteurs consécutifs en les considérant comme un ensemble unique et indivisible, appelé unité d’allocation ( cluster ). 18/04/18 OS I 57 Organisation de l’espace du disque Repérage des blocs libres Dès qu’on a choisi la taille des blocs, on doit trouver un moyen de mémoriser les blocs libres Les deux méthodes les plus répandues sont Liste chaînée Table de bits 18/04/18 OS I 58 Organisation de l’espace du disque Repérage des blocs libres 18/04/18 OS I 59 Organisation de l’espace du disque Repérage des blocs libres La première méthode consiste à utiliser une liste chaînée des blocs du disque, chaque bloc contenant des numéros de blocs libres. La deuxième technique de gestion des espaces libres a recours à une table de bits, chaque bit représentant un bloc et valant 1 si le bloc est occupé (ou libre suivant le système d’exploitation). Un disque de n blocs requiert une table de n bits. 18/04/18 OS I 60 Organisation de l’espace du disque Repérage des blocs libres - liste chaînée Considérons un disque dur de 500GB. Une taille d'un bloc de 1KB. → Le disque contient 524 millions de bloc (500 1024 1024= 524 288 000) Le numéro de bloc codée sur 32 bits. Taille d'un élément de la liste chaînée = un bloc contiendra 256 numéros de bloc libres Nombre de numéro de bloc libre que peut contenir un bloc de 1Ko = Taille d'un bloc en bit / taille du numéro du bloc (1024 octet*8 bit /32 bits) Pour adresser tous les blocs du disque dur (524 millions de numéro de blocs) on a besoin de (524 288 000 / 256 = 2 048 000 blocs) → 2 millions de blocs !!!! 18/04/18 OS I 61 Organisation de l’espace du disque Repérage des blocs libres – table de bit Considérons un disque dur de 500GB. Une taille d'un bloc de 1KB. → Le disque contient 524 millions de bloc (500 1024 1024) 1 bloc est représenté par un bit → taille max de la table de bit = 524 millions de bits = (524/8) / 1024 = 64000 Ko = 64000 blocs Pour adresser tous les blocs du disque dur → 64000 bloc 18/04/18 OS I 62 Les méthodes de stockage des fichiers Les fichiers étant constitués d’un certain nombre de blocs, le système de fichiers doit mémoriser les blocs des différents fichiers. Le principe fondamental pour stocker un fichier est de mémoriser l’adresse des blocs le constituant. Différentes méthodes sont utilisées pour cela : allocation contiguë, allocation par liste chaînée, allocation par liste chaînée indexée et nœud d’information (i-node) 18/04/18 OS I 63 Stockage des fichiers Allocation contiguë La méthode d’allocation la plus simple consiste à stocker chaque fichier dans une suite de blocs consécutifs. Un fichier de 50 Ko, par exemple, occupera 50 blocs consécutifs sur un disque dont la taille des blocs est 1 Ko. Cette méthode a deux avantages importants : 1)Elle est simple à mettre en œuvre puisqu’il suffit de mémoriser un nombre, l’adresse du premier bloc, pour localiser le fichier. 2)Les performances sont excellentes puisque tout le fichier peut être lu en une seule opération. → Aucune autre méthode d’allocation ne peut l’égaler. 18/04/18 OS I 64 Stockage des fichiers Allocation contiguë Malheureusement, l’allocation contiguë présente également deux inconvénients importants : Premièrement, elle ne peut être mise en œuvre que si la taille maximum du fichier est connue au moment de sa création. **Sans cette information, le système d’exploitation ne peut pas déterminer** l’espace à réserver sur le disque. **Dans les systèmes où les fichiers doivent être écrits en une seule opération,** elle peut néanmoins être avantageusement utilisée. Le deuxième inconvénient est la fragmentation du disque qui découle de cette politique d’allocation. **Elle gaspille de l’espace sur le disque.** **Le compactage du disque peut y remédier mais il est en général coûteux. Il** peut cependant être réalisé la nuit lorsque le système n’est pas chargé. 18/04/18 OS I 65 Stockage des fichiers Allocation contiguë (a) Allocation contiguë de l'espace disque pour 7 fichier (b) L'état du disque après suppression des fichiers D et F 18/04/18 OS I 66 Stockage des fichiers Allocation par liste chaînée La deuxième méthode consiste à sauvegarder les blocs des fichiers dans une liste chaînée. Le premier mot de chaque bloc, par exemple, est un pointeur sur le bloc suivant. Le reste du bloc contient les données. Cette méthode possède les avantages suivants : Contrairement à l’allocation contiguë, tous les blocs peuvent être utilisés → Il n’y a pas d’espace perdu en raison d’une fragmentation du disque. L’entrée du répertoire stocke simplement l’adresse du premier bloc. Les autres blocs sont trouvés à partir de celui-là. Elle possède également des inconvénients : Si la lecture séquentielle d’un fichier est simple, l’accès direct est extrêmement lent. Le pointeur sur le bloc suivant occupant quelques octets → l’espace réservé aux données dans chaque bloc n’est plus une puissance de deux. Ceci est moins efficace car de nombreux programmes lisent et écrivent des blocs dont la taille est une puissance de deux. 18/04/18 OS I 67 Stockage des fichiers Allocation par liste chaînée 18/04/18 OS I 68 Stockage des fichiers Allocation par liste chaînée indexée Les inconvénients de l’allocation au moyen d’une liste chaînée peuvent être éliminés en retirant le pointeur de chaque bloc pour le placer dans une table ou en index en mémoire. MS- DOS utilise cette méthode avec la FAT (File Allocation Table). Cette méthode possède les avantages suivants : Elle libère intégralement l’espace du bloc pour les données → Elle facilite les accès directs. La liste doit toujours être parcourue pour trouver un déplacement donné dans le fichier, mais elle réside entièrement en mémoire et peut être parcourue sans accéder au disque. Comme pour la méthode précédente, l’entrée du répertoire contient un seul entier (le numéro du premier bloc) qui permet de retrouver tous les autres blocs quelle que soit la taille du fichier. 18/04/18 OS I 69 Stockage des fichiers Allocation par liste chaînée indexée Le fichier A utilise les blocs 4,7 2 10 et 12 Le fichier B utilise les blocs 6,3 11 et 14 18/04/18 OS I 70 Stockage des fichiers Allocation par liste chaînée indexée ##### Le principal inconvénient de cette méthode vient du fait que la table doit résider entièrement en mémoire en permanence. ##### Un grand disque de 500 000 blocs requiert 500 000 entrées dans la table qui occupent chacune 4 octets dans le cas de FAT32. La table occupera 2 Mo en mémoire 18/04/18 OS I 71 Stockage des fichiers Nœuds d’information i-node Pour mémoriser quel bloc appartient à quel fichier, une dernière méthode consiste à associer à chaque fichier un structure de donnée appelée nœud d'index ou i-node. Un i-node inclut 1)les attributs 2)et les adresses disque des blocs du fichier En fonction de l'i-node il est possible de trouver tous les blocs d'un fichier 18/04/18 OS I 72 Stockage des fichiers: Avantage des i-node Le grand avantage de cette conception est que le i- node a besoin d'être en mémoire seulement quand le fichier correspondant est ouvert. Si chaque i-node occupe n octets Et un maximum de k fichiers peuvent être ouvert en même temps La mémoire totale occupée par le tableau contenant les i nodes des fichiers ouverts est k*n octets → seul cet espace pourra être réservé à l'avance. 18/04/18 OS I 73 Stockage des fichiers: Avantage des i-node Le tableau des i-node des fichiers ouverts est plus petit que l'espace occupé par la table du cas de l'allocation par liste chaînée indexée. La taille de la table de maintient de la liste chaînée croît proportionnellement avec la taille du disque : si le disque contient n blocs la table contient n entrée → elle croît linéairement à mesure que la taille du disque augmente Le concept de i-node requiert un tableau en mémoire dont la taille est proportionnelle au nombre maximum de fichier qui peuvent être ouvert simultanément → quelque soit la taille du disque 18/04/18 OS I 74 Stockage des fichiers : Problème des i-node Les i-nodes posent cependant un problème : Si chacun d'eux a la place pour un nombre donné d'adresse disque, que se passe-t-il lorsqu'un fichier croît au-delà de cette limite ? La solution est de réserver la dernière adresse disque, non pour un bloc de données du fichier mais pour l'adresse d'un bloc comprenant plusieurs adresse supplémentaire 18/04/18 OS I 75 Les répertoires dans tout ça ? Pour lire un fichier, il faut qu'il soit ouvert Quand un fichier est ouvert, le système d'exploitation se sert du chemin d'accès précisé par l'utilisateur afin de rechercher l'entrée du répertoire. L'entrée du répertoire fournit les informations nécessaires pour trouver les blocs de disque. Ces informations peuvent être L'adresse disque du fichier entier (allocation contiguë) Le numéro du premier bloc (liste chaînée) Le numéro de l'i-node La fonction principale du répertoire est de faire correspondre le nom ASCII du fichier à une information nécessaire pour trouver les données. 18/04/18 OS I 76 Les répertoires dans tout ça ? ##### Pour UNIX, les répertoires sont des fichiers et leurs i-nodes mappent les noms de fichiers aux i-node correspondant 18/04/18 OS I 77 Mise en œuvre des répertoires : ou stocker les attributs des fichiers ? Chaque système de fichier gère des attributs, tels que le propriétaire de chaque fichier ou sa date de création, et cela doit être stocké quelque part Une solution évidente consiste à les stocker directement dans l'entrée du répertoire Dans cette conception simple, un répertoire consiste en une liste d'entrées dont la taille est fixe, qui correspond chacune à un fichier Chaque entrée contient le nom du fichier, une structure d’attribut et une ou plusieurs adresses disque précisant les blocs du disque Approche de Windows 18/04/18 OS I 78 Mise en œuvre des répertoires : ou stocker les attributs des fichiers ? Pour les systèmes qui fonctionnent avec les i- nodes, une autre possibilité de stocker les attributs est de le faire dans les i-node plutôt que dans les entrées de répertoires Dans ce cas l'entrée du répertoire peut être plus petite et être juste constituée d'un nom de fichier et d'un numéro d'i-node Approche d 'UNIX 18/04/18 OS I 79 Les fichiers partagés : un beso...