Fonctionnement d’un

Système de Gestion de
Fichiers (SGF) - les
disques

[Link]@[Link]
27 décembre 2012

1
Systèmes de fichiers
 Propriétés attendues :  Vue abstraite: tableau
 Stocker de très dont les cases (blocs)
grandes quantités
d'information sont de taille fixe :
 L'information doit  Comment trouver ?
survivre à la fin du  Comment s'assurer
processus qui l'a qu'un utilisateur
créée accède uniquement
 Plusieurs processus aux données d'un
doivent pouvoir y fichier donné ?
accéder  Comment savoir quels
concurremment sont les blocs libres ?

2
I- Organisation d’un PC (ancien)

3
Le chemin des données
 Remarques technologiques : S-ATA, PCI Express et
PCI-X (sont des normes récentes concernant les
I/O)
 L’envoi d’octets depuis un disque vers la carte
réseaux passe par la RAM et le bus mémoire (2
fois)
 Ceci est dû à la méthode d’accès (les choix pour
sauvegarder et gérer les données entre
composants différents)

4
Structures logiques de fichiers

Figure 1. Three kinds of files. (a) Byte sequence.

(b) Record sequence. (c) Tree.
5
Organisation d’un fichier
 Le fichier séquentiel :
1. Un format fixé est utilisé pour les
enregistrements
2. Les enregistrements sont de même longueur
3. Tous les champs sont les mêmes
4. Un champs est appelé la clé… pour identifier
l’enregistrement
5. Nouveaux enregistrements sont traités par lots
pour être fusionnés

6
Organisation d’un fichier
 Le fichier (séquentiel) indexé :
1. Une table (un indexe) est utilisé pour retrouver
rapidement un enregistrement
2. Le reste est inchangé
3. Exemple d’indexe : (clé, ensemble des numéros des blocs
ou apparaissent la clé). Si l’ensemble est trié, on peut
faire une recherche dichotomique de coût O(log n).
Discussion : coût associé pour un ajout/suppression ? On
peut avoir plusieurs indexes pour une même clé :
compliqué !!!

7
Fichier indexé
Ici on a plusieurs
indexes et des
records de taille
variable
RQ : les indexes
sont aussi rangés
sur les disques

8
Fichier à accès direct (hash)
 Objectif : accéder avec un coût constant
(en une seule opération d’I/O : idéal) et pas
fonction de la taille du fichier ;
 H(key_field) => adresse du bloc
 Problème des collisions

9
Organisation physique d'un
système de gestion de données

10
 Allocation contiguë

Figure 2. (a) Contiguous allocation of disk space for 7 files.

(b) The state of the disk after files D and F have been removed.
11
Méthodes d’allocation des blocs
sur le disque
 Allocation contiguë permet de ne garder
comme information pour l’acces qu’une seule
adresse et le nombre de blocs.
 C’est bon pour les performances… mais
quand on supprime, on crée des « trous »
d’où la nécessité de faire autrement.

12
Allocation contiguë

13
Allocation contiguë et compactage

14
Allocation chainée

15
Allocation chainée

Il suffit de connaître le bloc

de début et la longueur
(nobre de blocs)

Le principe de localité n’est

pas respecté

16
Allocation chainée et consolidation

17
Allocation par liste chainée
utilisant une table en mémoire

18
Allocation des indexes

Que se passe t’il si

le nombre de blocs
est grand ?

19
Allocation des indexes

20
I-nodes
(terme du
monde
Unix)

21
Le cas d’Unix

22
II- Structure d’un disque
 Un disque peut être vu comme un tableau à 1
dimension de blocs logiques ;
 Le bloc est la plus petite unité de transfert (512
octets ?) ;
 Le tableau à 1 dimension est « mappé » dans les
secteurs physiques
 Le secteur 0 est mappé avec le premier secteur de
la première piste du cyclindre extérieur

23
Organisation physique
Cylindres
Pistes
QuickTime™ et un
décompresseur TIFF (non compressé)
Secteurs
sont requis pour visionner cette image.
Plateaux
Têtes de lecture

Exemple : pour un disque de 1024 cylindres, 16 têtes

et 63 secteurs (de 512 k), on aura donc une capacité
totale de disque dur de 1024 * 16 *63 * 512 =
528 482 304 octets soit environ 504 Mo
((528 482 304 / 1024) / 1024). 24
 Organisation physique
CFDISK(8) Linux Programmer's Manual

NAME
cfdisk - Curses based disk partition table manipulator
for Linux

SYNOPSIS
cfdisk [ -agvz ] [ -c cylinders ] [ -h heads ]
[ -s sectors-per-track ] [ -P opt ] [ device ]

Les commandes de gestion dépendent de la version utilisée

d’Unix !!!
25
Organisation physique
cfdisk 0.8i Disk Drive: /dev/hda
Heads: 64 Sectors per Track: 63 Cylinders: 528Name
Flags Part Type FS Type Size (MB)
---------------------------------------------------------------------------
/dev/hda1 Boot Primary DOS FAT16 [NO NAME ] 127.97
/dev/hda2 Primary Linux Swap 33.47
/dev/hda3 Primary Linux 878.07

[Bootable] [ Delete ] [ Help ] [Maximize] [ Print ] [ Quit ]

[ Type ] [ Units ] [ Write ]
Toggle bootable flag of the current partition

26
Système de fichier consistant
Imaginons une panne avant que

toutes les modifications (écritures)
 Trois cas :
sur un bloc aient eu lieu  (b) bloc manquant.
 Unix fsck (réponse pratique pour Free block passe à 1
Linuxien)  (c) 4 apparaît deux
 Définitions : fois. 2 → 1
 Table « Blocks in use » :  (d) le bloc 5 est
combien de fois un block présent dans 2
est présent dans un fichier ; fichiers : allouer un
 Table « Free blocks » : nouveau bloc et
combien de fois chaque copier le contenu de
bloc est présent dans la 5 dedans
liste des blocs disponibles

27
 Système de fichier consistant

Figure 3. File system states. (a) Consistent. (b) Missing block. (c)
Duplicate block in free list. (d) Duplicate data block.

28
Débit, performance d’un disque
 Le temps d’accès à un disque est modélisé par la
somme du seek time et rotational latency :
 Seek time: temps pour positionner les têtes sur le
bon cylindre ;
 Rotational latency: temps pour que la tête se
positionne sur le bon secteur ;
 Disk bandwidth: nombre total d’octets transférés /
(Tfin - Tdébut)

29
 Transfert

Tdébut Tfin

data transfert << wait+seek+rotational => poor bandwidth

On a donc besoin d’un… cache
30
Calcul plus précis
 Estimated seek time Ts = n*m+s (n=nombre de
pistes traversées, m=cte propre au disque,
s=startup time)
 Rotational delay : s’exprime en RPM (7200, 5400,
4200)
 Transfer Time T=b/(r*N) avec b=nombre d’octets à
transférer, N=nombre d’octets par piste, r=vitesse
de rotation en rpm)
 Total average seek time Ta = Ts+1/2r+b/(r*N)

31
Ordonnancement des accès au
disque
 Si les données d’un même fichier sont un « peu
partout » sur le disque alors la somme des Taccès est
grande !
 Plusieurs algorithmes existent pour ordonnancer
les requêtes d’I/O
 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.

32
Politique First Come Fist Serve
Illustration shows total head movement of 640 cylinders.

FCFS

33
Shortest Service Time First
(SSTF)
 Select requête avec le • Il peut y avoir famine (si
minimum seek time à partir on réalimente la file)
de la position courrante de
la tête
• Ici : 236 movements

34
Politique SCAN (balayage)
 Le bras de la tête va « au  Principe de l’ascensseur
début » du disque puis « à  Ici : 208 mouvements
la fin »

35
 Politique C-SCAN (circular)
 Fournit un temps d’attente  Quand on « atteint » la fin
plus uniforme que SCAN du disque on revient au début
sans rien faire
 Gestion par liste circulaire de
cylindres  Balayage dans un sens unique

36
Politique C-LOOK
 Version de C-SCAN  Quand on « atteint » la dernière
position la tête revient à la
première position sans rien faire
 Balayage dans un sens unique

37
Politique N-step-SCAN & FSCAN

 L’ordonnanceur gère  Deux files

des files de taille N  Une file vide pour
 Au moment d’un ajout, recevoir les nouvelles
on dépose dans une file requêtes
qui n’est pas en cours
de traitement
 Chaque file a une
politique SCAN

38
Quel choix pour des
performance ?
 Le meilleur algorithme est à choisir en
fonction du motif d’accès… mais il est
inconnu à priori
 Le système de fichier devrait tous les
implémenter et être capable de commuter
de l’un à l’autre pendant l’exécution
 SSTF ou LOOK sont choisis par défaut

39
 Exemple de système de
fichiers : ext3
ext3 alloue les blocs libres juste à côté des autres blocs
utilisés par le fichier, ce qui a pour effet de minimiser
l'espace physique entre les blocs.
ext3 est néanmoins par définition fragmenté, c'est
pourquoi son successeur ext4 inclut un utilitaire de
défragmentation natif travaillant au niveau des bits
et gérant la défragmentation à chaud.

Un système de fichiers ext3 est créé dans une partition

or le format de table de partition géré par fdisk6 ne
permet pas de créer des partitions de plus de 2,2
Tio (2^32*512)7. Utilisez la commande parted et le
format de table de partitions GPT8 pour s'affranchir
de cette limite de 2,2 Tio.

40
Technique du RAID pour augmenter
les performances… et la sureté
(pérénité des données)

 Principe : un contrôleur qui supervise

plusieurs disques en autorisant des requêtes
simultanées + sureté via la redondance
 Il y a différents niveaux de RAID

RAID=Redundant Array of Inexpensive Disks

41
RAID-0 (non redondant)

C’est bon pour les perfs, pas pour la pérénité !

42
RAID-0

43
RAID-1 (mirroir)

44
RAID-2 (redondance via code de
Hamming)

45
RAID-5 (calcul parité+distribution
de la comme de contrôle)

Et si un seul disque tombe en panne ?

46
Conclusion

[Link]

… et les systèmes de fichiers pour lecteurs de CD, disques

SSD, lecteurs de bandes... le noyau du système
d'exploitation doit aussi pouvoir les gérer !

47