APznzaZqtDeUBpNKtZfm_k0IxcP5dO-fClKcTAb06weyoI_BWz8hFOUw47wyf7loa_jFQ_0PfA8XTLqdTaWazKPrXocGjiE0MWkkCr2URZpgdIHKmY3SmXWKTMyBqNZtjCkFLbalryQY4qYcEozZAGLoDnMc94CutxzqBHg69E-pEVXJH3C9SGgMqtDy.pdf

République Algérienne Démocratique et Populaire Ministère de l’enseignement supérieur et de la recherche scientifique Université Mouloud Mammeri de Tizi-Ouzou Faculté de Génie Electrique et Informatique - Départeme...

République Algérienne Démocratique et Populaire Ministère de l’enseignement supérieur et de la recherche scientifique Université Mouloud Mammeri de Tizi-Ouzou Faculté de Génie Electrique et Informatique - Département Informatique Intitulé du Cours STRUCTURES DE FICHIERS ET DE DONNEES SFSD Equipe pédagogique: Chargée de cours et de TP : Mme LAZIB Samia 1  1 Chapitre 1: Généralités sur les fichiers 2 Chapitre 2: Les structures séquentielles 3 Chapitre 3: Les méthodes d’index 4 Chapitre 4: Les méthodes à base d’arbres de recherche 5 Chapitre 5: Les méthodes de hachage 6 Chapitre 6: Les opérations de haut niveau ------ Introduction aux Bases de Données ------ Structures de Fichiers et Structures de Données (SFSD) 2  Chapitre 1 Généralités sur les fichiers Structures de Fichiers et Structures de Données (SFSD) 3 Plan du chapitre Chapitre 1: Généralités sur les fichiers 1. Introduction 2. Les différents types de mémoires 3. Les notions de fichiers 4. La machine abstraite pour les structures de fichiers 5. Les fichiers en langage C 6. Conclusion Structures de Fichiers et Structures de Données (SFSD) 4 Introduction Structures de Fichiers et Structures de Données (SFSD) 5 Introduction Le système de gestion de fichiers Le SGF joue le rôle central dans un système d’exploitation car il doit gérer la plupart des informations des usagers et du système lui-même. Il a des liens étroits avec le système d’E/S Son rôle est d’assurer La conservation des informations (fichiers) et la réalisation des fonctions d’accès Ce qui impliquent la prise en charge par le SGF de : La gestion du support physique en masquant à l’utilisateur les détails de l’organisation physique de ses fichiers La sécurité et la protection des fichiers, c’est à dire la garantie de leur intégrité en cas d’incident ou de malveillance et le respect des règles d’utilisation fixées (droits d’accès, conditions de partage...) Structures de Fichiers et Structures de Données (SFSD) 6 Introduction Un fichier est le concept à travers lequel, un programme ou une application stocke des données en mémoire externe. Donnée VS Information: Une donnée est un élément brut. Exp: une suite de 0 et 1 Une information est une donnée transformée ayant une sémantique (signification, un sens,…) Exp: 05/07/1962 date de l’indépendance de l’Algèrie Les ensembles de données sont représentés par des structures de données externes et internes. Leurs manipulations induit des transferts de données entre mémoire centrale (MC) et mémoire externe (secondaire) (MS). Structures de Fichiers et Structures de Données (SFSD) 7 Les différents types de mémoire Dans l’architecture des ordinateurs actuels, il existe différents niveaux de mémoires : + Côut Structures de Fichiers et Structures de Données (SFSD) 8 Les différents types de mémoire Dans l’architecture des ordinateurs actuels, il existe différents niveaux de mémoires : 1 Les registres du processeur : très rapide (qlq ns), volatile, taille de quelques mots mémoires 2 La mémoire cache : entre processeur et mémoire centrale (MC), plus rapide que la MC (qlq dizaines de ns), volatile, très petite taille 3 La mémoire centrale (MC) : rapide (qlq centaines de ns), volatile, relativement de petite taille 4 Une zone tampon : (jouant le rôle de cache) entre MC et MS, c’est une petite partie de la mémoire centrale réservée par le système ⇒ ‘buffer cache’ 5 Les différents types de mémoires secondaires (MS) : principalement les disques magnétiques (ou disque durs HDD) et flash-disk (SSD...) plus lents que MC, non volatiles, grande taille et moins coûteux que MC 6 Les mémoires d’archivage (tertiaire): Généralement des bandes magnétiques (ou plus rarement des disques optiques) Très lentes, non volatile, grande taille et généralement à très faible coût Structures de Fichiers et Structures de Données (SFSD) 9 Les différents types de mémoire Caractéristiques Il existe plusieurs types de mémoires dans un ordinateur. Chaque type de mémoire est caractérisé par: la vitesse d’accès, la taille, la nature de l’accès permis (lecture, écriture, effacement,...), le coût et la volatilité (pertes d’information en cas de crash système ou redémarrage). Structures de Fichiers et Structures de Données (SFSD) 10 Les différents types de mémoire Pourquoi doit-on utiliser un espace secondaire? La MC est de taille toujours limitée La MC est plus coûteuse que la MS La MC est volatile (perte de données, …) Problème avec le stockage sur les MS? Le temps d’accès est très lent en MS (10-3 secondes), Par contre en MC très rapide (10-9 secondes). Structures de Fichiers et Structures de Données (SFSD) 11 Les différents types de mémoire Disque Magnétique: HDD (Hard Disk Drive) C’est un dispositif de stockage externe (MS) relativement pas cher, robuste et offrant d’assez bonnes performances Structures de Fichiers et Structures de Données (SFSD) 12 Les différents types de mémoire Disque Magnétique: HDD (Hard Disk Drive) C’est un dispositif de stockage externe (MS) relativement pas cher, robuste et offrant d’assez bonnes performances Structures de Fichiers et Structures de Données (SFSD) 13 Les différents types de mémoire Disque Magnétique: HDD (Hard Disk Drive) C’est un dispositif de stockage externe (MS) relativement pas cher, robuste et offrant d’assez bonnes performances Disque = ensemble de plateaux tournant avec une vitesse de rotation déterminée Plateau = ensemble de pistes concentriques numérotées 0, 1, 2,... sur chaque face (surface) Cylindre = ensemble de pistes ayant un même diamètre sur les différents plateaux Piste = ensemble de secteurs de même taille Le bras du disque contient les têtes de lecture/écriture (une pour chaque face d'un plateau) Structures de Fichiers et Structures de Données (SFSD) 14 Les différents types de mémoire Disque Magnétique: HDD (Hard Disk Drive) Plateaux Bras Secteurs Surfaces Têtes Pistes Structures de Fichiers et Structures de Données (SFSD) 15 Les différents types de mémoire Disque Magnétique: HDD (Hard Disk Drive) Temps d'accès = Temps du déplacement du bras vers la bonne piste (Temps de translation) + Temps d'attente de passage du secteur sous la tête de lecture/écriture (Latence rotationnelle) + Transfert de données NB: Le temps de déplacement du bras (temps de translation) est plus grand que le temps de rotation. Structures de Fichiers et Structures de Données (SFSD) 16 Les différents types de mémoire Disque Magnétique: HDD (Hard Disk Drive) La capacité du disque est le produit : Exemple d’un disque de 1 TO 16 surfaces 8 plateaux (donc 16 surfaces) * 65,536 pistes 2 , ou alors 65 536, pistes par surface 16 * (en moyenne) 2 = 256 secteurs par piste. 8 256 secteurs 212 = 4096 octets par secteur. * 4096 octets ⇒240 octets ( 1 TO ) Structures de Fichiers et Structures de Données (SFSD) 17 Les différents types de mémoire Les Disques Solid State Drive (SSD) C’est un dispositif de stockage externe (MS) à base de mémoire flash NAND, robuste et offrant de meilleurs performances que le disque magnétique. Structures de Fichiers et Structures de Données (SFSD) 18 Les différents types de mémoire Les Disques Solid State Drive (SSD) Les données sont stockées dans des micro-puces. Structures de Fichiers et Structures de Données (SFSD) 19 Les différents types de mémoire Les Disques Solid State Drive (SSD) Structures de Fichiers et Structures de Données (SFSD) 20 Les différents types de mémoire Les Disques Solid State Drive (SSD) La mémoire est divisée en blocs (ex: 256 Ko) et chaque bloc est composé d’un certain nombre de pages (ex: 4 Ko). Il y a 3 opérations possibles : Lire une page ⇒très rapide (20 microsecondes) Ecrire une page, à condition qu’elle soit dans un état effacé ⇒rapide (100 à 200 microsecondes) Effacer toute les pages d’un bloc ⇒ lente (quelques millisecondes) Structures de Fichiers et Structures de Données (SFSD) 21 Les différents types de mémoire Les Disques Solid State Drive (SSD) Inconvénients: Le nombre de fois qu’une page flash peut être effacée est limité (environ 100 000 à 1 000 000 fois) Une fois cette limite atteinte, des erreurs dans le stockage des bits sont susceptibles de se produire. Puisque les blocs supportent un nombre fixe d’effacements, au delà duquel ils deviennent inutilisables. Il faut donc répartir de manière uniforme les effacements sur l’ensemble des blocs du disque ⇒C’est la technique du WearLeveling (nivellement de l’usure) Structures de Fichiers et Structures de Données (SFSD) 22 Interface d’accès pour la mémoire externe Quelque soit le type du disque (HDD ou SSD) l’interface reste la même : L’unité de transfert = un bloc physique ( 1secteur ou + : HDD ou 1 page du SSD) Structures de Fichiers et Structures de Données (SFSD) 23 Notion de fichier Les fichiers sont apparus pour satisfaire trois besoins et ils doivent donc répondre à trois conditions essentielles correspondantes. Structures de Fichiers et Structures de Données (SFSD) 24 Notion de fichier On considère la mémoire secondaire MS comme une grande zone de stockage formée de blocs physiques de même taille fixe. Selon le type de la MS, le bloc physique, au niveau du système d’exploitation, peut être composé: d’un ou de plusieurs secteurs d’un HDD ou alors d’une ou de plusieurs pages d’un SSD. Chaque bloc physique représente donc un tableau d'octets pouvant être lu ou écrit en une seule opération d'accès (ou d’E/S physique) : LireBloc(num, Buf) EcrireBloc(num, Buf) Structures de Fichiers et Structures de Données (SFSD) 25 Notion de fichier Définition Un fichier est le concept à travers lequel, un programme ou une application stocke des données en mémoire externe. Un fichier est une structure de données persistante hébergée dans un ‘système de fichiers’ gérant la MS. Les fichiers sont utilisés à différents niveaux d'abstraction avec des sémantiques différentes: Au niveau applicatif (haut niveau) Au niveau interne ( système ou niveau physique) Structures de Fichiers et Structures de Données (SFSD) 26 Notion de fichier Niveau Applicatif Fichier Typé Fichier Non Typé (suite Enregistrements) (flux d’octets) Un fichier est une suite d’enregistrements Un fichier est une suite d’octets (articles) en MS (caractères) en MS Ex : F = < e1, e2, e3, … en > Ex : Chaque enregistrement est formé d’un F = < a,b,c,d,e,f,g,h,i,j,k,l,m, … > certain nombre de champs (attributs) Ex : e = { nom :’aaa’ , age : 19 , adr : ‘cccccc’ } Structures de Fichiers et Structures de Données (SFSD) 27 Notion de fichier Niveau Interne Un fichier est un ensemble de blocs physiques en MS, renfermant une suite d'octets non interprétés. Les données (par exemple les enregistrements) dufichier sont stockés à l'intérieur des blocs selon une certaine organisation. L'accès aux contenus des blocs se fait via les opérations d'E/S bufférisées (LireBloc et EcrireBloc). Structures de Fichiers et Structures de Données (SFSD) 28 Notion de fichier Fichiers BINAIRES Un fichier binaire est simplement une suite d'octets sans aucune interprétation particulière faite par le système. Ces suites d'octets représentent les données telle qu'elles étaient représentées en MC avant leur transfert sur le fichier. De ce fait les données d'un fichier binaire sont très dépendantes du système où elles ont été produites (donc généralement peu portables). Structures de Fichiers et Structures de Données (SFSD) 29 Notion de fichier Fichiers TEXTES Un fichier texte est formé d'un ensemble de lignes terminées chacune par une marque de fin de ligne. Dans les systèmes de type Unix (comme Linux par exemple), cette marque de fin de ligne est le caractère '\n‘ (code ascii 10). Dans d'autres systèmes, la marque de fin peut être composée de deux caractères (comme '\r' et '\n’). Les fonctions de lecture et d'écriture sur les fichiers textes, permettent de s'abstraire de ces différences entre systèmes. Structures de Fichiers et Structures de Données (SFSD) 30 Notion de fichier Caractéristiques Un ensemble d'informations sont nécessaires pour l'exploitation d’un fichier Ces informations sont sauvegardés : Soit dans des fichiers spéciaux (les répertoires) gérés par le systèmes d’exploitation Soit au début de chaque fichier (bloc d’entête) des fois gérés par l’application elle-même. Il existe deux types d'information : informations statiques, telles que le nom du fichier, la date de création, etc. informations dynamiques telles que le nombre courant d'articles, l'adresse du dernier bloc, etc. Structures de Fichiers et Structures de Données (SFSD) 31 Notion de fichier Fonctionnement du Cache buffer Toutes les opérations du niveau 'application' passent par le système qui les traduit en opérations de bas niveau pour accéder physiquement aux blocs de la MS Structures de Fichiers et Structures de Données (SFSD) 32 Notion de fichier Fonctionnement du Cache buffer Comme les opérations d'E/S sont coûteuses (en temps) le système maintient en MC une zone spéciale de taille limitée (la zone tampon ou "buffer cache") Permettant de garder en MC les copies de quelques blocs physiques choisis selon certaines stratégies (par exemple les plus utilisés) Cette zone tampon est totalement transparentes aux programmes d'application qui utilisent les fichiers. Structures de Fichiers et Structures de Données (SFSD) 33 Notion de fichier Fonctionnement du Cache buffer Lors de la lecture Si une application demande la lecture d'un enregistrement donné le système vérifie d'abord si le bloc contenant cet enregistrement ne se trouve pas déjà en MC (dans la zone tampon). S'il y est, l'enregistrement cherché, sera directement transmis à l'application, sans qu'il y ait de lecture physique en mémoire externe. Sinon, l'application est mise en attente Une opération de lecture physique de bloc est engagée afin de récupérer d'abord le bloc en MC Ensuite l'enregistrement est cherché. Structures de Fichiers et Structures de Données (SFSD) 34 Notion de fichier Fonctionnement du Cache buffer Lors de la lecture Lors de la lecture physique d'un bloc, le système cherche un emplacement libre dans la zone tampon pour y copier le contenu du bloc lu. S'il n'y a pas d'emplacement libre, le système choisit un des blocs déjà présents en zone tampon le recopie, éventuellement, sur disque (EcrireBloc) avant de l'écraser par le contenu du nouveau bloc. Le choix du bloc à écraser dépend de la stratégie de remplacement adoptée par le système. Structures de Fichiers et Structures de Données (SFSD) 35 Notion de fichier Fonctionnement du Cache buffer Lors de l’écriture Lors de la mise à jour d'un enregistrement par une application le système réalise l'opération directement dans sa zone tampon (en MC) L'écriture physique sur disque ne se fera que plus tard lors d'un remplacement de bloc par exemple Structures de Fichiers et Structures de Données (SFSD) 36 Notion de fichier Fonctionnement du Cache buffer Lors de l’écriture Périodiquement, le système synchronise son cache avec la MS Tous les blocs qui ont été modifiés dans la zone tampon seront alors physiquement écrits en MS lors de l'opération de synchronisation En cas de panne provoquant la perte de la MC donc de la zone tampon aussi les dernières modifications effectués sur les fichiers ouverts, risquent donc d'être perdues Structures de Fichiers et Structures de Données (SFSD) 37 Notion de fichier Fonctionnement du Cache buffer Lors de l’écriture Pour les applications critiques il existe des moyens pour forcer l'écriture physique Sans attendre la synchronisation périodique du cache Dans les systèmes de type Unix l'appel système 'fsync( f )' permet d'écrire physiquement sur la MS tous les blocs modifiés de la zone tampon et non encore synchronisés, relatifs au fichier f Structures de Fichiers et Structures de Données (SFSD) 38 Notion de fichier Méthode d’accès Une structure de fichier consiste : à définir et concevoir des structures de données et algorithmes associés, pour organiser les blocs d'un fichier sur MS et implémenter certaines opérations d'accès pour la manipulation des données du fichier. Structures de Fichiers et Structures de Données (SFSD) 39 Notion de fichier Méthode d’accès Cela inclus par exemple de définir : une manière d'organiser les blocs du fichier sur MS le placement des enregistrements à l'intérieur des blocs les caractéristiques et informations nécessaires pour manipuler le fichier le nombre de buffers à réserver en MC pour optimiser les accès l'implémentation des opérations d'accès (recherche, insertion, suppression, …) Le but des structures de fichiers est d'optimiser les performances d'accès (temps d'exécution et occupation mémoire) Structures de Fichiers et Structures de Données (SFSD) 40 Notion de fichier Performances des structures de fichiers Le principal critère de performance se résume au : Nombre d’Entrée/Sortie physiques effectuées. La complexité algorithmique est alors directement liée au nombres d’Entrée/Sortie. Un autre critère de performance concerne l’occupation de l’espace mémoire L’encombrement mémoire : Taille des structures de données utilisées / Taille des données stockées ≥ 100 % (plus le rapport est petit, plus c’est intéressant) Le facteur de chargement : Nombre de données insérées / Nombre de place disponibles dans le fichier ] 0 % , 100% ] (plus le rapport est grand, plus c’est intéressant) Structures de Fichiers et Structures de Données (SFSD) 41 La machine abstraite pour les structures de fichier Lors de la déclaration d’un fichier, on définira : le type des blocs, les Buffers, et les caractéristiques à utiliser (Entête) Ex : TypeBloc = struct tab : tableau[b] de TypeEnreg NB : entier Fin F : FICHIER de TypeBloc BUFFER buf1, buf2 ENTETE ( entier ) Structures de Fichiers et Structures de Données (SFSD) 42 La machine abstraite pour les structures de fichier Ex : TypeBloc = struct tab : tableau[b] de TypeEnreg NB : entier Fin F : FICHIER de TypeBloc BUFFER buf1, buf2 ENTETE ( entier ) Dans cette déclaration on dit que : F est un fichier formé par des blocs ayant la structure TypeBloc buf1 et buf2 sont 2 variables buffer (en MC) de type TypeBloc (on les utilisera comme buffers pour accéder aux blocs de F) Les caractéristiques de F se résume à un seul entier (on l’utilisera par exemple pour sauvegarder le nombre de blocs dans F) On peut aussi déclarer les variables buffers indépendamment de F (dans des déclarations à part) buf3 : TypeBloc ; Structures de Fichiers et Structures de Données (SFSD) 43 La machine abstraite pour les structures de fichier Pour écrire des algorithmes sur les structures de fichiers, on utilisera la machine abstraite définie par le modèle suivant: {Ouvrir, Fermer, LireDir, EcrireDir, Aff_Entete, Entete, Allocbloc } Dans ce modèle, on manipule des numéros de blocs relatifs au début de chaque fichier (c’est donc des numéros logiques). L'utilisation des adresses physiques n'est pas d'une utilitéparticulière à ce niveau de la présentation. Dans ce modèle, un fichier est donc un ensemble de blocs numérotés logiquement (1, 2, 3,... n). Structures de Fichiers et Structures de Données (SFSD) 44 La machine abstraite pour les structures de fichier Les opérations du modèle Opération Rôle OUVRIR( F , nomfichier , mode) Ouvre ou crée un fichier Mode = ‘A’ veut dire ouvrir en lecture/écriture un fichier qui existe déjà. Les caractéristiques seront lues en MC lors de l’ouverture. Mode = ‘N’ veut dire créer un nouveau fichier en lecture/écriture. Les caractéristiques seront allouées en MC lors de le création FERMER( F ) Ferme le fichier F et les caractéristiques seront sauvegardées en MS LIREDIR( F , i , buf ) Lecture du bloc numéro i de F dans la variable buf ECRIREDIR( F , i , buf ) Ecriture de buf dans le bloc numéro i de F ENTETE( F , i ) Retourne la valeur de la caractéristique numéro i AFF_ENTETE( F , i , v ) Affecte v à la caractéristique numéro i ALLOC_BLOC( F ) Retourne le numéro d’un nouveau bloc alloué à F Structures de Fichiers et Structures de Données (SFSD) 45 La machine abstraite pour les structures de fichier Exemple Const b= 3 Type Tetudiant = Structure // le contenu des enregistrements matricule: entier; nom: chaine; fin Type TBloc = Structure // le contenu des blocs tab : Tableau [ b ] de Tetudiant; nb : entier; fin f : FICHIER de TBloc BUFFER buf ENTETE (entier, entier); // caractéristiques: -1- nombre de blocs -2- nombre d’enregistrements I,j: entier; Val: Tetudiant; Structures de Fichiers et Structures de Données (SFSD) 46 La machine abstraite pour les structures de fichier Exemple Type TBloc = Structure // le contenu des blocs tab : Tableau [ b ] de Tetudiant; nb : entier; fin F : FICHIER de TBloc BUFFER buf ENTETE (entier, entier); // caractéristiques: -1- nombre de blocs -2- nombre d’enregistrements Structures de Fichiers et Structures de Données (SFSD) 47 La machine abstraite pour les structures de fichier Exemple //Affichage du contenu d’un fichier Début OUVRIR ( F , « fichier.dat », ’A’ ); // ouverture en mode ancien Nbre_Bloc ← ENTETE (F , 1); i ← 1; TANTQUE i