Les systŁmes de fichiers - mathinfo.univ-reims.frmathinfo.univ-reims.fr/IMG/pdf/SE-Cours5-Fichiers-Poly.pdf · A chaque fichier correspond une entrØe dans un rØpertoire Elle fournit

F. Nolot Licence d'informatique 2003-2004 1

Université de Reims – Champagne Ardenne

Les systèmes de fichiers




I. Généralités


Université de Reims Champagne-Ardenne

Les problèmes

Les données crées par un processus sont limités par son espace virtuel d'adressage

Une fois le processus terminé, perte des informations

Lors d'accès concurrents, les informations doivent pouvoir être consultées indépendamment des processus



Les objectifs

Enregistrer une très grande quantité d'informations

Conserver ces informations après la fin du processus qui les utilise

Plusieurs processus doivent pouvoir accéder simultanément à une information

La solution classique : les fichiers



Les types de fichiers existant

Fichiers ordinaires : contiennent les informations

Répertoires : ce sont des fichiers système qui conservent la structure du système de fichiers

Fichiers spéciaux caractères : permet de modéliser les périphériques d'E/S

Fichiers spéciaux bloc : permet de modéliser les disques




II. Les fichiers ordinaires



Les fichiers ordinaires

Soit des fichiers ASCII

lignes de textes

Possibilité de les lire et de les imprimer directement

Soit des fichiers binaires

Une suite d'octets incompréhensible si on ne connaît pas le format



Leur type ?

Déterminé soit par une extension

MS-DOS : les exécutables ont l'extension .exe ou .com

Soit par un attribut (MAC-OS)

Soit il n'est pas défini (UNIX), seul l'application utilise (et reconnaît) l'extension



Exemple de types de fichiers

Type de fichier Extension Fonction

Exécutable Exe, com, ou aucun

Objet obj, o Compilé, langage machine non linké

Code source c, cc, pas, java, asm Code source en divers langage

Traitement par lots bat, sh

Bibliothèque lib, a

Impression ou vue ps, dvi, pdf, jpg, bmp

Multimédia mpeg, mpg, mp3

Archive tgz, tar, zip, rar, bz2

Programme en langage machine prêt à etre exécuté

Ensemble de commandes de l'interpréteur de commandesBibliothèque de routine pour les programmeursFichiers dans un format d'impression ou de visualisationFichiers contenant de informations audio et/ou vidéoFichiers groupés dans un seul fichier pouvant etre compressé



Les accès aux fichiers

Accès séquentiel

lecture des octets du fichier dans l'ordre, à partir du début (ex : une bande magnétique)

Accès par rapport à leur position sur le support

Accès aléatoire

Possibilité d'accès direct à n'importe quel fichier

possibilité de se positionner à un endroit donné d'un fichier



Les attributs des fichiers

Informations complémentaires concernant un fichier

Le nombre d'attribut varie en fonction du système

Exemple :

indicateurs sur les possibilités de lecture, écriture et exécution

Le créateur, le propriétaire

Fichier ASCII ou binaire ...

L'heure et la date de création




III. Les répertoires



Pourquoi les répertoires ?

Pour hiérarchiser les fichiers

Gérer les fichiers de plusieurs utilisateurs

Pour pouvoir organiser ses données

Plusieurs utilisateurs peuvent avoir des fichiers ayant le même nom



Représentation d'une hiérarchie

usr

/

home bin

binlib A B lsC sh

cours doc

Chemin d'accès absolu : commence par le séparateur (/home/C/cours)Chemin relatif : Si /home est le répertoire courant, l'accès à cours

se fait par C/cours. représente le répertoire courant et .. le répertoire parent




IV. L'implantation




A. Le disque



Organisation du disque

Les fichiers sont stockés de manière contiguë ou pas

1ère solution : perte d'espace libre et temps pour compresser trop long

C'est donc la 2ème solution la plus souvent utilisée

Problème : utilisation de bloc de taille fixe donc quelle taille utiliser ?

Un secteur, une piste, un cylindre ou la taille d'une page pour les systèmes paginés ?

Si le bloc est trop grand, gaspillage

Si le bloc est trop petit, un grand de nombre de blocs est à gérer pour un fichier



Mémorisation des blocs libres

2 méthodes sont utilisées

Liste chaînée de blocs contenant chacun des numéros de blocs libres

Table de bits : pour un disque de n blocs, une table de n bits est utilisée. Un 1 indique que le bloc est libre et 0 qu'il est occupé (ou l'inverse)

La deuxième solution utilise généralement moins de place




B. Les fichiers



Organisation

Systèmes de fichiers enregistrés sur le disque

Chaque partition du disque possède un système de fichier qui peut être différent

Au secteur 0 du disque se trouve la MBR (Master Boot Record) puis la table des partitions

Premier bloc des partitions est le bloc de boot

Le suivant : le superbloc qui contient les informations sur le type de système de fichiers de la partition



Allocation contiguë

Chaque fichier est stocké dans une suite de blocs consécutifs

Exemple : bloc de 2Ko, 5 fichiers de taille respective 16Ko, 12Ko, 6Ko, 6Ko et 4Ko

��



Allocation contiguë (2)

Avantages :

Simple à mettre en place

Excellentes performances car un seul déplacement au début du fichier

Inconvénient : la fragmentation

Exemple : on supprime les fichiers B et D

� ��



Allocation par liste chaînée

Chaque fichier est considéré comme une liste chaînée de blocs du disque

Plus de fragmentation

Par contre, la lecture d'un fichier devient plus complexe et plus lente (multiples déplacements)

L'adresse du bloc de fichier suivant entraîne des tailles différentes des blocs de données du fichier

B

0 1 2 3

A0 1 2 3 4 5

4 6 7 9 2 0 8 1 3 5Blocphysique



Allocation par liste chaînée et FAT

Stockage du pointeur de chaque bloc dans une table en mémoire appelée FAT (File Allocation Table)

Avantage : un bloc physique est intégralement disponible pour des données

Inconvénient : la place occupée par la table peut être considérable

Exemple : un disque de 20Go avec des blocs de 2Ko, soit environ 10 millions d'entrées dans la table. Si chaque entrée n'est que de 2 octets, il faut donc au total près de 20 Mo



Exemple d'une FAT

-1

56

0

83

012345

1-1

976

789

B

0 1 2 3

A0 1 2 3 4 5

4 6 7 9 2 0 8 1 3 5Blocphysique

Début du fichier A

Début du fichier B



Les i-nodes

A chaque fichier, on associe une structure de données appelée i-node qui contient

les attributs

les adresses du disque des blocs du fichier

Avantage : on ne charge en mémoire que les i-nodes des fichiers ouverts.




C. Les répertoires



Les entrées des répertoires

A chaque fichier correspond une entrée dans un répertoire

Elle fournit les informations pour trouver le fichier sur le disque

Soit l'adresse disque du fichier entier

Soit le numéro du 1er bloc du fichier

Soit le numéro de l'i-node correspondant

Ainsi que les attributs sont stockés

Soit dans l'entrée du répertoire qui regroupe le nom du fichier, les attributs et l'adresses disques

Soit dans l'i-node du fichier. Dans ce cas, la taille de l'entrée est réduite au nom du fichier et au numéro de l'i-node



Gestion des noms de fichiers longs

Généralement, on fixe une taille maximale (255 caractères)

Problème : beaucoup d'espace perdu

2 solutions :

Chaque entrée d'un répertoire contient la longueur de l'entrée du fichier, ses attributs ( de longueur fixe), son nom de fichier (de longueur variable)

Problème : quand un fichier est supprimé, un trou se forme dans l'entrée du répertoire

Chaque entrée de répertoire est de longueur fixe, tous les noms de fichier se trouvant à la fin du répertoire




D. Les liens



Les liens physiques ou matériels (UNIX)

Ajout d'un nouveau nom dans le système de fichiers, qui pointe vers le même i-node que le nom original

Permet d'avoir plusieurs noms pour un même fichier

L'i-node contient un compteur de lien

Initialisé à 1 lors de la création du fichier original

Incrémenté à chaque création d'un lien vers ce fichier



Les liens physiques ou matériels (UNIX)

Exemple : un fichier toto et deux liens tata et titi vers toto



Les liens symboliques (UNIX)

Fichier texte qui contient le chemin d'accès et le nom du fichier vers lequel il pointe

Le lien est marqué par un type spécial



Liens physiques vs liens symboliques

Liens physiques : conservation du propriétaire

Si le propriétaire efface le fichier, celui-ci appartient toujours au propriétaire et donc s'il existe des quotas, cela peut poser des problèmes

Liens symboliques : pas ce problème car seul le propriétaire possède un pointeur sur l'i-node. Par contre, si le propriétaire supprime ce fichier, le lien devient invalide

Consommation de temps CPU supplémentaire car de nombreux accès disque afin de lire le chemin d'accès puis le fichier pointé

Problème commun : un fichier peut avoir plusieurs chemin d'accès possible. Lors d'une sauvegarde, un fichier peut donc être copié plusieurs fois.




E. Les commandes en langage C



Manipulation des flux

Ouverture d'un flux

FILE *fopen(char *nom, char *mode)

Mode est égale à r : lecture seule, le fichier doit existerw : écriture seule. Si le fichier existe, il est écrasé sinon il est crééa : écriture seule en fin de fichier. Si le fichier existe, il n'est pas

modifié sinon il est créér+ : lecture et écriture. Si le fichier existe, les lectures et écritures

commenceront au début et écraseront les données présentesw+ : lecture et écriture. Si le fichier existe, il est écrasé, sinon il est

crééa+ : ajout et lecture. Lecture commence au début et les ajouts à la

fin



Manipulation des flux (2)

Fermeture d'un flux

int fclose (FILE *flux)

Retourne 0 en cas de succès et EOF en cas d'échec

Ecriture dans un flux

int fwrite( const void *bloc, size_t taille_element, size_t nb_element,

FILE *flux)Retourne le nombre d'éléments correctement écrits

Lecture dans un fluxint fread( const void *bloc, size_t taille_element,

size_t nb_element, FILE *flux)

Retourne le nombre d'éléments correctement lusF. Nolot Licence d'informatique 2003-2004 38


Manipulation des flux (3)

Déplacement dans un flux

int fseek (FILE *flux, long position, int depart)

depart a pour valeur :

SEEK_SET : on mesure la position depuis le début du fichier

SEEK_CUR : on mesure la position depuis la position courante

SEEK_END : on mesure la position depuis la fin du fichier

Retourne 0 en cas de succès et -1 en cas d'erreur

Retour au début du flux

void rewind (FILE *fp)




V. La fiabilité



La sauvegarde

Les supports utilisés pour le stockage ne sont pas fiable à 100%

Plusieurs moyens de sauvegarde existent

La sauvegarde totale

On copie la totalité des données

La sauvegarde incrémentale

Au lieu de toujours faire une sauvegarde totale, sauvegarder régulièrement que les données modifiées



La cohérence

Si une panne arrive lorsque le système est en train de faire des modifications sur les blocs du disque

Que se passe-t-il si ces blocs sont des blocs d'i-nodes, de répertoires ou de blocs libres

La vérification de la cohérence est basée

Soit sur les blocs

Soit sur les fichiers



Cohérence basée sur les blocs

Fabrication de 2 tables

L'une contient le nombre de fois qu'un bloc est référencé dans un fichier

L'autre contient le nombre de fois qu'un bloc est référencé dans la liste des blocs libres

Une fois les tables remplies, 4 situations sont possibles



Cohérence basée sur les blocs (2)

Système cohérent

10 10 1 0

1 0 0 1 1 0 1 0 1 10 10010101

10 101 0 10 1 01 00

Bloc utilisé

Bloc libre

31 20 4 5 116 1087 9 1412 13 1615 1817

Indice des blocs




Système incohérent

Le bloc 5 est manquant. Il sera considéré comme libre

10 10 1 0

1 0 0 1 1 0 1 0 1 10 10010001

10 101 0 10 1 01 00

Bloc utilisé

Bloc libre

31 20 4 5 116 1087 9 1412 13 1615 1817

Indice des blocs





Le bloc 5 est dupliqué dans l'espace des blocs libres

10 10 1 0

1 0 0 1 1 0 1 0 1 10 10010201

10 101 0 10 1 01 00

Bloc utilisé

Bloc libre

31 20 4 5 116 1087 9 1412 13 1615 1817

Indice des blocs





Le bloc 5 appartient à 2 fichiers. La solution : allouer un bloc libre, y copier le bloc dupliquer et le copier dans un des fichiers

10 10 1 2

1 0 0 1 1 0 1 0 1 10 10010001

10 101 0 10 1 01 00

Bloc utilisé

Bloc libre

31 20 4 5 116 1087 9 1412 13 1615 1817

Indice des blocs



Cohérence basée sur les fichiers

Utilisé pour vérifier les entrées dans les répertoires

Pour chaque fichier, un compteur est incrémenté à chaque fois qu'il se trouve dans un répertoire

Comparaison avec le compteur de lien enregistré dans les i-nodes




VI. Exemples




A. ISO-9660



ISO 9660

Standard international pour les CD-ROM depuis 1988

Compatible avec la majorité des systèmes d'exploitation

Données organisées sur une simple spirale continue

La spirale est divisé en bloc de 2352 octets

La partie utile est de 2048 octets par bloc



ISO 9660 (2)

Début de 16 blocs d'une utilisation non définie

Ensuite, le bloc descripteur primaire de volume composé des identificateurs

du système : 32 octets

du volume : 32 octets

de l'éditeur : 128 octets

du préparateur de données : 128 octets

Le nom de 3 fichiers qui contiennent le résumé, la note sur les droits réservés et des informations bibliographiques

Le nombre de blocs du CD, la date de création, la position du répertoire racine F. Nolot Licence d'informatique 2003-2004 52


ISO 9660 – les répertoires

Le répertoire racine et les autres sont composés d'un nombre variable d'entrées dont la dernière est marquée par un bit spécial

Chaque entrée est de taille variable, constituée de 10 à 12 champs codés en ASCII ou binaire

Ceux codés en binaires utilisent le format

Little endian (octet représenté avec le poids faible en premier)

Big endian (octet représenté avec le poids fort en premier)



ISO 9660 – les entrées de répertoire

Longueur de l'entrée du répertoire (1 octet)

Longueur de l'enregistrement des attributs étendus (1 octet)

Localisation du 1er bloc du fichier (8 octets). Stockage contigu des fichiers dont le 1er détermine la position des suivants

Taille du fichier (8 octets)

Date et heure (7 octets)

Flags pour cacher une entrée, pour distinguer une entrée de répertoire de celle d'un fichier, ... (1 octet)

Intervalle (2 octets)

Identification du CD qui contient le fichier : possibilité de stocké un « super » répertoire sur un CD et tous ses fichiers sur un autre (4 octets)



ISO 9660 – les entrées de répertoire (2)

La taille du nom du fichier (1 octet)

Le nom du fichier composé : d'un nom (max. 8 caractères), d'une extension (max. 3 caractères), un point, un point virgule, un numéro de version en binaire (entre 4 octets et 15 octets)

Le nom : caractères (majuscules ou pas), chiffres et _

Les entrées d'un répertoire sont listées dans l'ordre alphabétique

Pas de limite au nombre d'entrée d'un répertoire mais Profondeur maximale d'un répertoire : 8 niveaux

Padding pour ajuster la taille de l'entrée pour obtenir une longueur constante pour toutes les entrées

Champ System use : non défini mais de taille paire



ISO 9660 – Les 3 niveaux

Il existe 3 niveaux concernant cette norme

Niveaux 1 : la plus restrictive

Nom de fichier : 8+3 caractères

Tous les fichiers doivent être contigus

Nom de répertoire : 8 caractères sans extension

Niveaux 2 : nom de fichier et répertoire allant jusque 31 caractères

Niveaux 3 : Niveau 2 + allègement de la contiguïté

un fichier peut être constitué de plusieurs sections, chacune d'elles étant constitué de blocs contigus. Plusieurs blocs peuvent apparaître plusieurs fois dans un même fichier ou dans plusieurs fichiers. On obtient une optimisation de l'espace




B. L'extension Rock Ridge



Reproduire un système Unix

ISO-9660 ne permet pas de reproduire un système de fichiers Unix (les liens, les attributs, ...)

Avec ISO-9660 + extension Rock Ridge, c'est possible

Utilisation du champ System use pour stocker

Les attributs POSIX (rwxrwxrwx)

Numéro majeur et mineur d'un device

Lien symbolique

Autre nom du fichier : permet de lever la restriction sur les noms de fichier de la norme ISO-9660

Relocalisation d'un répertoire pour lever la limite sur la profondeur

Heure de création, de modification et d'accès du fichierF. Nolot Licence d'informatique 2003-2004 58



C. L'extension Joliet



Reproduire un système Windows

Plusieurs extensions possibles:

Les noms longs : maximum de 64 caractères

Utilisation de caractères Unicode, codés sur 2 octets

Profondeur de répertoire supérieure à 8 niveaux

Des répertoires pouvant avoir des extensions !




D. MS-DOS



Format d'une entrée répertoire

Nom du fichier (8 octets) + extension (3 octets)

Attributs : 1 octet

Lecture seule, archive, caché, système

Inutilisé : 10 octets

Heure (2 octets) et Date (2 octets)

Heure subdivisée en secondes (5 bits), minutes (6 bits) et heures (5 bits)

Date subdivisée en jour (5 bits), mois (4 bits), année (7 bits) : la base 1980

Indice du premier bloc du fichier : 2 octets

Taille du fichier : 4 octets



FAT pour MS-DOS

Numéro du premier bloc du fichier, dans la table FAT

Il existe 3 FAT pour MS-DOS

FAT-12 : 12 bits pour une adresse disque



Pour toutes les FAT : chaque bloc est un multiple de 512 octets et la taille d'unité d'allocation (cluster) varie



Limites de la FAT-12

Taille maximale d'une partition : 212 x512=2 Mo

En mémoire 4096 entrées de 2 octets chacune

Ensuite, apparition de bloc de 1, 2 et 4 Ko. Cela permet des partitions de 16 Mo maximum

MS-DOS supporte au maximum 4 partitions par disque donc des disques de 64 Mo maximum




Tailles des blocs : 8, 16 et 32 Ko

Taille maximale d'une partition : 2 Go (64 Ko d'entrées de 32 Ko chacune)

Taille maximale des disques : 8 Go

Apparition avec Windows 95 SE de la FAT-32




Adresses disques de 28 bits

Partition de taille maximale théorique : 228x215=8 To

Or le système mémorise les tailles des partitions dans des secteurs de 512 octets, en utilisant un nombre de 32 bits, donc 29x232=2 To

Avantage de la FAT-32

Pour un disque de 2 Go, possibilité d'utiliser des blocs plus petit qu'en FAT-16 (obligatoirement 32 Ko en FAT-16) F. Nolot Licence d'informatique 2003-2004 66


Le système de fichiers de Windows 98

Windows 95 : limité au format de MS-DOS : 8+3 et FAT-12 ou FAT-16

Win95 Second Edition : utilisation des noms longs et FAT-32

Windows 98 et ME : idem que Win95SE

Utilisation des 10 octets inutilisés



Utilisation des 10 octets libres

1 octet pour la compatibilité avec Windows NT

1 octet pour gestion de l'heure avec une meilleur précision

4 octets pour la date et heure de création

2 octets pour la date du dernier accés

2 octets pour stocker les 16 bits de poids fort du bloc de début

Donc à l'emplacement de l'indice du premier bloc, on trouve maintenant les 16 bits de poids faible du bloc de début



Gestion des noms longs

2 noms sont possibles pour un fichier (ou répertoire)

Soit format 8+3

Soit un autre format

Dans ce cas, fabrication d'un nom au format 8+3

Algorithme utilisé : 6 premiers caractères, suivis de ~1. Si le nom existe, ~2, ...

Les espaces, point en trop sont effacésCertains caractères spéciaux remplacés par _



Gestion des noms longs (2)

Si le nom est une partie d'un nom long : attribut prend la valeur 0x0F : valeur inexistante dans le format MS-DOS

Le nom long est stocké dans une ou plusieurs entrées de répertoire, précédant le nom de fichier MS-DOS

Chaque entrée de nom long peut comprendre jusqu'à 13 caractères



Entrée avec un nom long

Séquence : 1 octet

5 caractères : 10 octets

Attributs : 1 octet

0 : 1 octet

Checksum : 1 octets


0 : 2 octets




Organisation des séquences

Stockage dans l'ordre inverse avec le début du nom de fichier juste à coté du nom MS-DOS

Les dernières parties du nom long : ajout de la valeur 64 à son numéro de séquence

Limite à 260 caractères



Exemple de noms longs

Fichier qui a pour nom : Sujet de l'examen de Système en Licence

67 em e An Ck0 iL ec cn e0

2 ma ne A Ck0 ed s sy t0 è

1 uS ej At Ck0 d e 'l e0 x

A SNTSujetd~1 Heure Bas Taille




E. Ext 2



L'implémentation d'ext2

Bloc 0 : boot

Ensuite on a des groupes de blocs

Chaque groupe de blocs est constitué

D'un superbloc : nombre de blocs et i-nodes, taille des blocs, ...

Descripteur de groupe

Bitmap des blocs libres puis des i-nodes libres

i-nodes

Blocs de données

Chaque i-node fait 128 octets

12 blocs et 3 indirections

Les adresses sur 4 octets



Les indirections

Structure d'un i-node dans ext2:

Les Attributs

12 premières adresses disques du fichier

Si c'est insuffisant, existence de blocs d'indirections simple, double et triple

Simple : pointe sur une structure qui contient des adresses disques supplémentaires

Double : pointe sur une structure qui contient des adresses de redirection simple

Triple : ...F. Nolot Licence d'informatique 2003-2004 76


Les répertoires

Ensenble non trié d'entrée de 16 octets

Chaque entrée contient un nom de fichier et le numéro de l'i-node correspondant

Quand un fichier recherché est utilisé, chargement du numéro d'i-node et chargement de l'i-node dans la table des i-nodes (le numéro est utilisé comme indice) qui contient tous les i-nodes des fichiers ouverts




F. NTFS (version Windows 2000)



Caractéristiques de NT FileSystem

Système de fichiers récent, mis au point pour Windows NT, réutilisé dans Windows 2000, amélioré dans Windows XP

Utilisation d'adresses disque sur 64 bits

Les noms de fichiers limités à 255 caractères

Chemin complet limité à 32767 caractères

Codage des noms au format Unicode

Respect de la casse (mais pas par l'API Win32)



Structure du système de fichiers

Chaque volume (partition)

contient des fichiers, répertoires, bitmaps et structures de données

est organisé en une séquence de blocs (cluster) de taille comprise entre 512 octets et 64 Ko (généralement cluster de 4Ko)

Chaque bloc est repérée par son offset par rapport au début du volume, utilisation d'adresses sur 64 bits



Structure du système de fichiers (2)

Chaque fichier possède une entrée dans la MFT et est vu comme une suite d'attribut.

Si l'attribut peut être stoké dans la MFT, il est dit résident (date, nom du fichier, ...)

Les non-résidents sont alloués sur le disque

Si un fichier est de petite taille, il est intégralement stoké dans la MFT, sinon pointe vers des clusters externes

La MFT est un fichier qui peut croître jusque 248

enregistrements



Les fontionnalités de NTFS

Support de la compression de fichiers, de répertoires et de volume

Lecture/écriture par n'importe quelles applications, sans décompression par un autre programme

L'algo de compression supporte des clusters au max. de 4Ko

EFS (Encrypting File System) : NTFS5

Utilisation de clé de cryptage symétrique en combinaison avec la technologies des clés publiques pour protéger l'accés aux fichiers.

Documents

Les systŁmes de fichiers - mathinfo.univ-reims.frmathinfo.univ-reims.fr/IMG/pdf/SE-Cours5-Fichiers-Poly.pdf · A chaque fichier correspond une entrØe dans un rØpertoire Elle fournit