Systèmes d'Exploitation - Implémentation des systèmes de fichiers

Didier Verna

Description

Systèmes
d’Exploitation
Didier Verna
EPITA
Généralités Systèmes d’Exploitation
Allocation
Implémentation des systèmes de fichiers
Répertoires
Swap
Espace libre
Didier Verna
Corruption
Performance
[e-mail]
http://www.lrde.epita.fr/˜didier
Version EPITA du 28 septembre 2009
1/25Table des matières
Systèmes
d’Exploitation
1 Généralités
Didier Verna
EPITA
Généralités 2 Méthodes d’allocation
Allocation
Répertoires 3 Implémentation des répertoires
Swap
Espace libre
4 du swap
Corruption
Performance
5 Représentations de l’espace libre
6 Corruption des systèmes de fichiers
7 Performances des systèmes de fichiers
2/25Fonctionnalités requises
Systèmes
d’Exploitation Définir l’interface utilisateur : caractéristiques et
Didier Verna attributs des fichiers, opérations sur les fichiers,
EPITA
structures des répertoires etc.
Généralités
Définir l’interface matérielle : structure de données,
Allocation
algorithmes, liaison entre système logique et dispositif
Répertoires
de stockage en mémoire auxiliaireSwap
Espace libre
Système de fichiers logique Module d’organisation des fichiers Système de fichiers de base Contrôle des Entrées / Sorties
Corruption
Connaissance de la Traduction entre adresses
structure de répertoires de bloc logiques et Drivers de périphériquesPerformance Commandes génériques de
physiques
lecture / écriture de
blocs physiques
Mécanismes de Gestion de l’espace Handlers d’interruptions
protection / sécurité libre
4/25
Programmes
PrériphériquesAllocation et ...

Sujets

• Algèbre de Clifford
• Entrée des Croisés à Constantinople
• Grippe aviaire chez l'animal
• Roi
• Système de fichiers
• Rémunération et avantages sociaux

Informations

• Publié par: Thewyung
• Nombre de lectures: 240
• Langue: Français

Extrait

Systèmes d’Explotitaoi D n dieiVrre E P na A G IT érénital lA sé acolnoit epéRres S rtoi spac wap Eer oC lebi itnorrpu maorrfPeenc 15/2

Version E PITA du 28 septembre 2009

[e-mail] http://www.lrde.epita.fr/˜didier

Didier Verna

Systèmes d’Exploitation Implémentation des systèmes de fichiers

Implémentation du swap

3

Représentations de l’espace libre

4

Méthodes d’allocation

1

Implémentation des répertoires

2

Généralités

22/5

Performances des systèmes de fichiers

Table des matières

6

7

5

Corruption des systèmes de fichiers

d s E’pxoltitaoi D n Système tilaréné acollA sé errVieid A G IT E P na psca aw E p er oC lebi Répe tion res S rtoi encfrePamro purrnoit

/452

Définir l’interface utilisateur : caractéristiques et attributs des fichiers, opérations sur les fichiers, structures des répertoires etc. Définir l’interface matérielle : structure de données, algorithmes, liaison entre système logique et dispositif de stockage en mémoire auxiliaire

Fonctionnalités requises

’d semètsyS diDi ontitaoiplEx seri pawS péR n otre e C br ruor paEslice IPAT éGén reeVnr E a llocatio ralités A er n P iopt ceanrmfo

tèmeSys oi D ntitapxold s E’ A G IT E P naerrVieid acollA sétilaréné itno éReptrioer S s wap Espacelibre Copurrnoit frePamroenc

Allocation et efficacité Utiliser la mémoire auxiliaire le plus efficacement possible

256/

Efficacité des entrées / sorties : transferts de données par « blocs » (Cf. aussi le DMA). = ⇒ Allocation d’espace disque également par bloc plutôt que par octet. Compromis espace / performance : blocs de 1K. Accès direct : par opposition aux périphériques à accès séquentiel (ex. bandes magnétiques). = ⇒ Implémentation des méthodes d’accès aux fichiers facile.

Allocation contiguë Exemple : IBM VM/CMS

Principe I Fichiers stockés par blocs contigus sur le disque I Temps de positionnement des têtes minimal I Entrée de répertoire : adresse du premier bloc et longueur (en nombre de blocs) I Accès direct et séquentiel faciles à implémenter : il suffit de mémoriser l’adresse du premier bloc I Gestion de l’espace libre : Cf. ∗ -fit, fragmentation externe, compactage etc. Problème majeur : fichiers de taille variable I Trop d’espace : fragmentation interne I Pas assez d’espace : déplacement (coûteux) du fichier. Pas toujours possible. Utilisation actuelle : CD / DVD-ROM

/257 S pxE’tiol ètsy d sem bier oCrrpuitno ePrformance itacollA trepéR no wa s S reoi elacsp p E D n di taoi reaneiVr A Gén E PIT itéséral

treperio itac éR no elacreib wa s S sp p E no ePfrro oCrrpuit mance tèysS pxE’d sem oitatiol ierV n Did E PIT erna rélaG A né lAol tisé 258/

Principe I Fichier = chaîne non contiguë de blocs disque I Chaque bloc se termine par un pointeur sur le bloc suivant I Une entrée de répertoire contient un pointeur sur le premier bloc Avantages I Pas de fragmentation externe I Pas de limite de taille Inconvénients I Accès direct inefficace I Fiabilité : perte de pointeur critique. Solutions : listes doublement chaînées, reproduction du nom de fichier et numéro de bloc dans chaque bloc etc. Coûteux dans tous les cas.

Allocation chaînée

ecreofmrna ruption P libre Cor

File Allocation Table (FAT) Variante de l’allocation chaînée (MS-DOS, OS/2)

259/

Principe I Une FAT au début de chaque partition I Table indexée par numéros de bloc I Chaque entrée pointe sur le numéro de bloc suivant I Une entrée de répertoire contient un pointeur sur le premier bloc Avantages (à condition de mettre la FAT en mémoire) I Moins de risque de corruption I Accès séquentiel aussi rapide I Accès direct (presque) aussi rapide que l’accès séquentiel Inconvénients I Taille de la FAT Disque de 20G, blocs de 1Kb = ⇒ FAT de 80M

ploid’Ex èmesSyst oi R n pére A s llcota ap Espace toires Sw reidnreV itat iD no ranétéli PI a E Gé TA

10/

Principe I Chaque fichier possède un bloc d’index (1 er bloc) I Une entrée de répertoire pointe sur le bloc d’index I La i e entrée du bloc d’index pointe sur le i e bloc de données du fichier Avantages I Implémentation efficace de l’accès direct I Table des i-nodes de taille proportionnelle au nombre de fichiers (Cf. FAT : taille du disque) Inconvénients I Fragmentation interne plus grande qu’avec l’allocation chaînée I Problème de la taille des index

25

Allocation indexée (« i-nodes ») Schéma analogue à la pagination

ecnamrof orru bre Cn Per ptio wSpa rise ecilsEap péR n otre colloita liras A té TAPI néGé reeVnr E a itno iDid Exploita stèmes d’ yS

P n reofmrnaec licee C br ruoriopt otreseri pawS apsE liranéGé TAPI a E rn péR noitacollA sét Expl es d’ stèmSy reeViDid itnoioat

Schéma chaîné : réserver le dernier mot du bloc d’index pour un pointeur sur le bloc d’index suivant. Index à multiniveaux : analogue à la pagination à plusieurs niveaux. Index pointant sur des index pointant . . . sur des blocs de données. Indexation à 2 niveaux = ⇒ Fichiers de l’ordre de 10 Go. Schéma combiné : les premières entrées pointent sur des blocs de données. Les suivantes pointent sur des blocs d’index de différents niveaux.

Schémas d’indexation Comment stocker des index sur plusieurs blocs ?

112/5

Systèmes d’Exploitation

Didier Verna E PITA

Généralités

Allocation

Répertoires

Swap

Espace libre

Corruption

Performance

212/5

Structure des i-node Schéma combiné d’Unix (BSD, System

V)

ecnamrofreP noit aw E p er S strioéRep rrup re Co elibspac G ATI réné reVr P E an caloonti ital Al és ètem d s E’ Ssy ion Didie xploitat 52/4

Liste linéaire : noms de fichiers / attributs / pointeurs sur des blocs de données, ou noms de fichiers / pointeurs sur des i-nodes. I Avantage : implémentation simple I Inconvénient : recherche linéaire dans la liste • Caching des répertoires fréquemment utilisés. Triage de la liste (arbre binaire chaîné, recherche dichotomique etc. ) Table de hachage : transformation des noms de fichiers en index de tableau (fonction de hachage). I Avantage : temps de recherche plus court I Inconvénient : tables de taille fixe, fonction de hachage dépendante de la taille de la table

Implémentation des répertoires

1