Cours Système d’exploitation

Niveau : GL2 & IIA2Enseignant : Mona LAROUSSIBureau : 4 A8-28E-mail: mona.laroussi@insat.rnu.tn

Chapitre 6

Systèmes de fichiers

Que c’est qu’un fichier

Collection nommée d’informations apparentées, enregistrée sur un stockage secondaire Nature permanente

Les données qui se trouvent sur un stockage secondaires doivent être dans un fichier

Différents types: Données (binaire, numérique, caractères….) Programmes

Structures de fichiers

Aucune – séquences d’octets… Texte: Lignes, pages, docs formatés Source: classes, méthodes,

procédures… Etc.

Attributs d’un fichierAttributs d’un fichier

Constituent les propriétés du fichiers et sont stockés dans un fichier spécial appelé répertoire (directory). Exemples d’attributs: Nom:

pour permet aux personnes d’accéder au fichier Identificateur:

Un nombre permettant au SE d’identifier le fichier Type:

Ex: binaire, ou texte; lorsque le SE supporte cela Position:

Indique le disque et l’adresse du fichier sur disque Taille:

En bytes ou en blocs Protection:

Détermine qui peut écrire, lire, exécuter… Date:

pour la dernière modification, ou dernière utilisation Autres…

Opérations sur les fichiers: de base

Création Écriture

Pointeur d’écriture qui donne la position d’écriture

Lecture Pointeur de lecture

Positionnement dans un fichier (temps de recherche) Suppression d’un fichier

Libération d’espace

Troncature: remise de la taille à zéro tout en conservant les attributs

Autres opérations Ajout d’infos Rénommage Copie

peut être faite par rénommage: deux noms pour un seul fichier

Ouverture d’un fichier: le fichier devient associé à un processus qui en garde les attributs, position, etc.

Fermeture Ouverture et fermeture peuvent être explicites (ops

open, close) ou implicites

Types de fichiers

9

Structure logique des fichiersStructure logique des fichiers

Le type d’un fichier spécifie sa structure Le SE peut alors supporter les différentes structures

correspondant aux types de fichiers Cela complexifie le SE mais simplifie les applications

Généralement, un fichier est un ensemble d’enregistrements (records) Chaque enregistrement est constitué d’un ensemble de

champs (fields) Un champ peut être numérique ou chaîne de chars.

Les enregistrements sont de longueur fixe ou variable (tout dépendant du type du fichier)

Mais pour Unix, MS-DOS et autres, un fichier est simplement une suite d’octets « byte stream » Donc ici, 1 enregistrement = 1 octet C’est l’application qui interprète le contenu et spécifie

une structure Plus versatile mais plus de travail pour le programmeur

Organisation de répertoires

Efficacité: arriver rapidement à un enregistrement

Structure de noms: convenable pour usager deux usagers peuvent avoir le même noms pour

fichiers différents Le même fichier peut avoir différents noms

Groupement de fichiers par type: tous les programmes Java tous les programmes objet

Listes et groupes d’accès - UNIX Modes d ’accès: R W E Trois classes d ’usager:

propriétaire groupe public

demander à l ’administrateur de créer un nouveau groupe avec un certain usager et un certain propriétaire

droit du propriétaire de régler les droits d ’accès et d ’ajouter des nouveaux usagers

Listes et groupes d’accèsListes et groupes d’accès

Mode d’accès: read, write, execute Trois catégories d’usagers:

RWXa) owner access 7 1 1 1

RWXb) group access 6 1 1 0

RWXc) others access 1 0 0 1

Demander au gestionnaire de créer un groupe, disons G, et ajouter des usagers au groupe

Pour un fichier particulier, disons jeux, définir un accès approprié owner group public

chmod 761 jeux

Changer le groupe d’un fichierchgrp G jeux

Chap 11 13

Méthodes d’accès

SéquentielleIndexée SéquentielleIndexéeDirecte

Chap 11 14

Méthodes d’accès: 4 de base

Séquentiel (rubans ou disques): lecture ou écriture des enregistrements dans un ordre fixe

Indexé séquentiel (disques): accès séquentiel ou accès direct (aléatoire) par l’utilisation d’index

Indexée: multiplicité d’index selon les besoins, accès direct par l’index

Direct ou hachée: accès direct à travers tableau d’hachage

Pas tous les SE supportent les méthodes d’accès Quand le SE ne les supporte pas, c’est à l’application de

les supporter

15

Méthodes d’accès aux fichiersMéthodes d’accès aux fichiers

La structure logique d’un fichier détermine sa méthode d’accès Les SE sur les « mainframe » fournissent généralement plusieurs

méthodes d’accès Car ils supportent plusieurs types de fichiers

Plusieurs SE modernes (Unix, Linux, MS-DOS…) fournissent une seule méthode d’accès (séquentielle) car les fichiers sont tous du même type (ex: séquence d’octets) Mais leur méthode d’allocation de fichiers (voir + loin) permet

habituellement aux applications d’accéder aux fichiers de différentes manières

Ex: les systèmes de gestions de bases de données (DBMS) requièrent des méthodes d’accès plus efficaces que juste séquentielle Un DBMS sur un « mainframe » peut utiliser une structure fournie

par le SE pour accès efficace aux enregistrements. Un DBMS sur un SE qui ne fournit qu’un accès séquentiel doit donc

« ajouter » une structure aux fichiers de bases de données pour accès directs plus rapides.

16

Fichiers à accès séquentiel (archétype: rubans)

bloc bloc

enregistrements

. . . . . .

La seule façon de retourner en arrière est de retourner au début (rébobiner, rewind)

En avant seulement, 1 seul enreg. à la fois

espace interbloc

. . .

17

Lecture physique et lecture logique dans un fichier séquentiel

Un fichier séquentiel consiste en blocs d’octets enregistrés sur un support tel que ruban, disque…

La dimension de ces blocs est dictée par les caractéristiques du support Ces blocs sont lus (lecture physique) dans un tampon en mémoire Un bloc contient un certain nombre d’enregistrements (records) qui sont

des unités d’information logiques pour l’application (un étudiant, un client, un produit…) Souvent de longueur et contenu uniformes Triés par une clé, normalement un code (code d’étudiant, numéro

produit…) Une lecture dans un programme lit le prochain enregistrement Cette lecture peut être réalisée par

La simple mise à jour d’un pointeur si la lecture logique précédente ne s’était pas rendue à la fin du tampon

la lecture du proch. bloc (dans un tampon d’E/S en mémoire) si la lecture logique précédente s’était rendue à la fin du tampon Dans ce cas le pointeur est remis à 0

Chap 11 18

Autres propriétés des fichiers séquentiels Pour l’écriture, la même idée: une instruction d’écriture

dans un programme cause l’ajout d’un enregistrement à un tampon, quand le tampon est plein il y a une écriture de bloc

Un fichier séquentiel qui a été ouvert en lecture ne peut pas être écrit et vice-versa (impossible de mélanger lectures et écritures)

Les fichiers séquentiels ne peuvent être lus ou écrits qu’un enregistrement à la fois et seulement dans la direction ‘en avant’

Chap 11 19

Adressage Indexé séquentiel Adressage Indexé séquentiel (index sequential)(index sequential)

Un index permet d’arriver directement à l’enregistrement désiré, ou en sa proximité Chaque enregistrement contient un champ clé Un fichier index contient des repères (pointeurs) à

certain points importants dans le fichier principal (p.ex. début de la lettre S, début des Lalande, début des matricules qui commencent par 8)

Le fichier index pourra être organisé en niveaux (p.ex. dans l’index de S on trouve l’index de tous ceux qui commencent par S)

Le fichier index permet d’arriver au point de repère dans le fichier principal, puis la recherche est séquentielle

Chap 11 20

Exemples d’index et fichiers relatifs

Pointe au début des Smiths (il y en aura plusieurs)

Le fichier index est à accès direct, le fichier relatif est à accès séquentielAccès direct: voir ci-dessous

Chap 11 21

Index et fichier principal Index et fichier principal (Stallings)(Stallings)

(Relative file)

Dans cette figure, l’index est étendu à plusieurs niveaux, donc il y a un fichier index qui renvoie à un autre fichier index, n niveaux

Chap 11 22

Pourquoi plusieurs niveaux d’index Un premier niveau d’index pourrait

conduire au début de la lettre S Un deuxième niveau au début des

Smith, etc. Donc dans le cas de fichiers volumineux

plusieurs niveaux pourraient être justifiés.

Chap 11 23

Séquentiel et index séquentiel: comparaisonSéquentiel et index séquentiel: comparaison

P.ex. Un fichier contient 1 milliond’enregistrements

En moyenne, 500, 000 accès sont nécessaires pour trouver un enregistrement si l’accès est séquentiel!

Mais dans un séquentiel indexé, s’il y a un seul niveau d’indices avec 1000 entrées (et chaque entrée

pointe donc à 1000 autres),

En moyenne, ça prend 500 accès pour trouver le repère approprié dans le fichier index

Puis 500 accès pour trouver séquentiellement le bon enregistrement dans le fichier relatif

Chap 11 24

Mais… besoin de fichier débordementMais… besoin de fichier débordement

Les nouveaux enregistrements seront ajoutés à un fichier débordement

Les enregistrements du fichier principal qui le précèdent dans l’ordre de tri seront mis à jour pour contenir un pointeur au nouveau enregistrement Donc accès additionnels au

fichiers débordement Périodiquement, le fichier

principal sera fusionné avec le fichier débordement

Chap 11 25

Fichier indexéFichier indexé

Utilise des index multiples pour différentes clés, selon les différents besoins de consultation

Quelques uns pourraient être exhaustifs, quelques uns partiels, et organisés de façons différentes

Chap 11 26

Indexed File (Stallings)Indexed File (Stallings)

Chap 11 27

Accès directe (ou relatif)

Fichier est vu comme collection d’enregistrement logiques de grandeurs fixes Basé sur le modèle disque (composé de blocs) Spécifie numéro de bloc pour accédés données Numéro souvent relatif (du début du fichier)

Ce n’est pas tous les SEs qui offres les accès séquentiels et directes Facile de simuler l’accès séquentiel avec l’accès directe

Maintient un pointeur cp indiquant la position courante dans un fichier

L’inverse est très difficile

28

Utilisation des 4 méthodesUtilisation des 4 méthodes

Séquentiel (rubans ou disques): lecture ou écriture des enregistrements dans un ordre fixe Pour travaux ‘par lots’: salaires, comptabilité périodique…

Indexé séquentiel (disques): accès séquentiel ou accès direct par l’utilisation d’index Pour fichiers qui doivent être consultés parfois de façon séquentielle,

parfois de façon directe (p.ex. par nom d’étudiant) Indexée: multiplicité d’index selon les besoins, accès direct par

l’index Pour fichiers qui doivent être consultés de façon directe selon des

critères différents (p.ex. pouvoir accéder aux infos concernant les étudiants par la côte du cours auquel ils sont inscrits)

Direct ou hachée: accès direct à travers tableau d’hachage Pour fichiers qui doivent être consultés de façon directe par une clé

uniforme (p.ex. accès aux information des étudiants par No. de matricule)

29

Répertoires

Chap 11 30

Structures de répertoires (directories) Une collection de structures de données contenant infos

sur les fichiers.

F 1 F 2F 3

F 4

F n

Répertoires

Fichiers

Tant les répertoires, que les fichiers, sont sur disques À l’exception d’un rép. racine en mém. centrale

Chap 11 31

Organisation typique de système de fichiers

Chap 11 32

Information dans un répertoire

Nom du fichier Type Adresse sur disque,... Longueur courante Longueur maximale Date de dernier accès Date de dernière mise à jour Propriétaire Protection

Chap 11 33

Opérations sur répertoires

Recherche de fichier Création de fichier Suppression de fichier Lister un répertoire Rénommer un fichier Traverser un système de fichier

Chap 11 34

Organisation de répertoires

Efficacité: arriver rapidement à un enregistrement

Structure de noms: convenable pour usager deux usagers peuvent avoir le même noms

pour fichiers différents Le même fichier peut avoir différents noms

Groupement de fichiers par type: tous les programmes Java tous les programmes objet

Chap 11 35

Structure à un niveau

Un seul rép. pour tous les usagers Ambiguïté de noms Problèmes de groupement Primitif, pas pratique

Chap 11 36

Répertoires à deux niveaux

Rép. séparé pour chaque usager `path name`, nom de chemin même nom de fichier pour usagers différents est

permis recherche efficace Pas de groupements

Chap 11 37

Répertoires à arbres (normal aujourd’hui)

Chap 11 38

Caractéristiques des répertoires à arbres Recherche efficace Possibilité de grouper Repertoire courant (working directory)

cd /spell/mail/prog

Chap 11 39

Graphes sans cycles: permettent de partager fichiers

Unix: un symbolic link donne un chemin à un fichier ou sous-répertoire

Chap 11 40

Références multiples dans graphes acycliques

Un nœud peut avoir deux noms différents

Si dict supprime list donc pointeur vers fichier inexistant (danglingpointer). Solutions: Pointeurs en arrière, effacent

tous les pointeurs Compteurs de références (s’il y

a encore des refs au fichier, ilne sera pas effacé)

Ni Unix ni Microsoft n’implémentent ces politiques, donc messages d’erreur

Solutions impossibles à gérer dans un système fortement reparti (ex: www)

Chap 11 41

Graphes avec cycles (structure générale)

• Presque inévitables quand il est permis de pointer à un noeud arbitraire de la structure• Pourraient être détectés avec des contrôles appropriés au moment de la création d ’un nouveau pointeur•Contrôles qui ne sont pas faits dans les SE courants

Chap 11 42

Considérations dans le cas de cycles

En traversant le graphe, il est nécessaire de savoir si on retombe sur un noeud déjà visité

Un noeud peut avoir compteur de ref != 0 en se trouvant dans une boucle de noeuds qui n ’est pas accessible!

Des algorithmes existent pour permettre de traiter ces cas, cependant ils sont compliqués et ont des temps d ’exécution non-négligeables, ce qui fait qu’ ils ne sont pas toujours employés Ramasse-miettes = garbage collection

root Un sous-arbre qui n’est pas accessible à partir de la racine mais il ne peut pas être effacé en utilisant le critère ref=0 car il fait ref à lui-meme!

Chap 11 43

Combiner plusieurs systèmes de fichier

Le système de fichier

Répertoire qui réside dans une partition/appareil spécifique

Pourquoi combiner?

Plusieurs partitions de disques rigides, disquettes, CDROM, disques réseau.

Vision et accès uniforme

Comment?

Attacher un système de fichier à un nœud particuler dans la hiérarchie du répertoire.

Windows: système à 2 niveaux – attaché à des lettres d’appareils

Unix: opération d’attachement explicit (mount), peut attacher un système de fichier n’importe où dans le répertoire.

Chap 11 44

Attachement du système de fichier

Un système de fichier doit être attaché (mounted) avant d’être accédé

Un système de fichier est attacher à un point d’attachement (mount point)

Chap 11 45

(a) Existant. (b) Partition non-attachée

Chap 11 46

Point d’attachement (mount point)

Chap 11 47

Partage de fichiers

Désirable sur les réseaux

Nécessite de protection

Chap 11 48

Protection

Types d ’accès permis lecture écriture exécution append (annexation) effacement listage: lister les noms et les attributs d ’un

fichier

Par qui

Chap 11 49

Listes et groupes d’accès - UNIX

Modes d ’accès: R W E Trois classes d ’usager:

propriétaire groupe public

demander à l ’administrateur de créer un nouveau groupe avec un certain usager et un certain propriétaire

droit du propriétaire de régler les droits d ’accès et d ’ajouter des nouveaux

Listes et groupes d’accèsListes et groupes d’accès Mode d’accès: read, write, execute Trois catégories d’usagers:

RWXa) owner access 7 1 1 1

RWXb) group access 6 1 1 0

RWXc) others access 1 0 0 1

Demander au gestionnaire de créer un groupe, disons G, et ajouter des usagers au groupe

Pour un fichier particulier, disons jeux, définir un accèsapproprié

owner group public

chmod 761 jeux

Changer le groupe d’un fichierchgrp G jeux

Méthodes d’allocation

Structures de systèmes de fichiers

Structure de fichiers: deux façons de voir un fichier: unité d’allocation espace collection d ’informations reliées

Le système de fichiers réside dans la mémoire secondaire: disques, rubans...

File control block: structure de données contenant de l ’info sur un fichier

Trois méthodes d’allocation de fichiers

Allocation contiguëAllocation enchaînéeAllocation indexée

Allocation contiguë sur disquerépertoire

Allocation contiguë

Chaque fichier occupe un ensemble de blocs contigu sur disque

Simple: nous n’avons besoin que d’adresses de début et longueur

Supporte tant l’accès séquentiel, que l’accès direct

Moins pratique pour les autres méthodes

Allocation contiguë

Application des problèmes et méthodes vus dans le chapitre de l’alloc de mémoire contiguë

Les fichiers ne peuvent pas grandir Impossible d’ajouter au milieu Exécution périodique d’une compression

(compaction) pour récupérer l’espace libre

Allocation enchaînée

Le répertoire contient l ’adresse du premier et dernier bloc, possibl. le nombre de blocs

Chaque bloc contient un pointeur à l’adresse du prochain bloc:

pointeurbloc =

Allocation enchaînéerépertoire

Tableau d’allocation de fichiers

Avantages - inconvénients

Pas de fragmentation externe - allocation de mémoire simple, pas besoin de compression

L ’accès à l ’intérieur d ’un fichier ne peut être que séquentiel Pas façon de trouver directement le 4ème

enregistrement... N’utilise pas la localité car les enregistrements

seront éparpillés L ’intégrité des pointeurs est essentielle Les pointeurs gaspillent un peu d ’espace

Allocation indexée: semblable à la pagination

Tous les pointeurs sont regroupés dans un tableau (index block)

index table

Allocation indexée

-1: pointeur nul

Allocation indexée

À la création d ’un fichier, tous les pointeurs dans le tableau sont nil (-1)

Chaque fois qu’un nouveau bloc doit être alloué, on trouve de l ’espace disponible et on ajoute un pointeur avec son adresse

Allocation indexée

Pas de fragmentation externe, mais les index prennent de l’espace

Permet accès direct (aléatoire) Taille de fichiers limitée par la taille de

l’index block Mais nous pouvons avoir plusieurs niveaux

d’index: Unix Index block peut utiliser beaucoup de

mémoire

UNIX BSD: indexé à niveaux (config. possible)

12 blocs disque de 4K chaque

1024 blocs de 4K chaque

1024x1024 blocs de 4K

Bloc de 4K contient 1024 pointeurs

Ce répertoire est en mémoire, tous les autres sont sur disque

Gestion de l’espace libre

Gestion d’espace libre Solution 1: vecteur de bits (solution Macintosh, Windows 2000)

…0 1 2 n-1

bit[i] =

0 block[i] libre

1 block[i] occupé

Exemple d’un vecteur de bits où les blocs 3, 4, 5, 9, 10, 15, 16 sont occupés: 00011100011000011…

L’adresse du premier bloc libre peut être trouvée par un simple calcul

Gestion d’espace libreSolution 2: Liste liée de mémoire libre (MS-DOS, Windows 9x)

Tous les blocs de mémoire libre sont liés ensemble par des pointeurs

Table d'allocation des fichiers

Une variation de l'allocation liée est d'utiliser une table d'allocation des fichiers (FAT).

- Utilisé par MS-DOS et OS/2.- Une partie du disque est réservée pour stocker la table qui

contient les pointeurs vers tous les fichiers de la partition.- Chaque entrée dans la FAT correspond à un bloc sur le

disque. Chaque entrée contient le pointeur vers le bloc suivant du fichier.

- Une valeur spéciale indique la fin du fichier.- Une entrée nulle signifie un bloc inutilisé.

Table d'allocation (2)

Les FATs sont stockées en mémoire tant que le SE est actif

Utilisé pour gérer les problèmes liés aux deux autres méthodes.

Similaire à l'allocation liée mais tous les pointeurs sont stockés ensembles dans un bloc spécial (index block)

Allocation indexée

Exemple

Inodes Une structure qui contient la description

du fichier : Type Droits d'accès Possesseurs Dates de modifications Taille Pointeurs vers les blocs de données

Les inodes sont stockés en mémoire tant que le fichier est ouvert

Inodes (2)

inode

infos

Blocs directs Indirection simple

Indirection double

Répertoires Structurés dans/par l'arborescence Chaque répertoire peut contenir des fichiers et

des répertoires Un répertoire est juste un fichier de type

spécial Fonctions spéciales pour accéder à un

répertoire Chaque entrée de répertoire contient le nom du

fichier et son inode Le noyau recherche l'arborescence pour convertir

le nom de fichier en un numéro d'inode.

Directory diagram

Table des inodes

i1 Fichier1i2 Fichier2i3 Fichier3i4 fichier4

Répertoire

La cohérence

Un système de fichiers est cohérent s’il est capable de restituer à l’utilisateur ses fichiers et ses répertoires dans l’état où il les a laissés.

Parmi les utilitaires d’un système d’exploitation, on trouve un utilitaire de vérification et de correction des erreurs au niveau du système de fichiers tel que scandisk pour Windows.

Du point de vue pratique, ces utilitaires examinent les SDD du système d’exploitation et corrigent les erreurs qu’il peuvent y trouver.

La vérification concerne les blocs appartenant aux fichiers ou libres, et l’état des répertoires.

Les tableaux qui suivent illustrent un cas d’incohérence obtenu avec un utilitaire d’Unix qui compte le nombre de fois où un bloc est trouvé libre ou occupé :

Numéros des blocs0123456789101112131415Tableau des blocs libres1101021110011100Tableau des blocs utilisés0000200001100011Quand le SGF est cohérent, chaque bloc apparaît une fois au maximum soit dans le premier tableau soit dans le second.

Le second utilitaire vérifie les I-Nodes. Son rôle consiste à parcourir tous les répertoires en partant de la racine et à construire un tableau où le contenu d’une case est le nombre de fois où un I-Node est référencé.

Lorsqu’un fichier est partagé par un lien physique son numéro d’I-Node apparaît dans un autre répertoire.

Pour vérifier la cohérence, on compare la valeur obtenue avec le compteur de liens dans chaque I-Node.

79

Enregistrements logiques et physiquesUn enregistrement logique est un ensemble de données ayant unsens pour l’utilisateur. Un fichier est une suite d’enregistrementslogiques.Un enregistrement physique, aussi appelé bloc, est l’unité destockage manipulée par le système. Avec les disques, cette unité destockage est un secteur ou un multiple de cette taille. On l’appelleunité d’allocation, parfois Cluster.Les blocs peuvent être plus grands ou plus petits que les enre-gistrements logiques décidés par le programmeur. Le système peutenregistrer plusieurs enregistrements logiques de petite taille dans unseul bloc, ou peut avoir besoin de plusieurs blocs pour enregistrer degrands enregistrements logiques.

Gestion de fichiers

80

Les blocs physiques sont numérotés par le système et formentla base de toute structure de fichier.Le caractère (octet, byte) est la plus petite quantité d’informationmanipulée par le système. Un fichier, vu par le système, est doncun ensemble de blocs de taille fixe, chacun étant constitué d’unesuite de caractères.

Gestion de fichiers

81

Le système doit connaître l’emplacement sur disque (numéro decylindre, piste et secteur) de chaque bloc.La première idée qui vient à l’esprit est de placer le fichier dansdes blocs consécutifs. Cette approche n’est pas réaliste comptetenu de l’accroissement et des modifications des fichiers.On peut gagner en flexibilité en adoptant une structure de blocsdans laquelle chaque bloc contient un pointeur indiquant l’empla-cement du bloc suivant. Cette approche facilite les modificationset l’accroissement, mais alourdit la recherche d’un enregistre-ment, qui devient séquentielle.

Gestion des ressources disques

82

Une possibilité est d’utiliser une table de pointeurs contenantles indications nécessaires pour déterminer l’emplacement d’unbloc cherché.Il y a deux stratégies possibles : une table par unité de disque,ou une table par fichier. Dans le premier cas, il faut charger enmémoire la table contenant les pointeurs de tous les fichiers dudisque. Dans le second, on ne garde en mémoire que la tabledes fichiers ouverts.Un autre problème est celui de l’allocation de l’espace disque.Le système tient à jour des tables facilitant la recherche desecteurs disponibles. Deux possibilités sont courammentutilisées : une table d’allocation, ou un bitmap.

Gestion des ressources disques

83

Table d’allocation

Piste Secteur Nombre de secteursallouables consécutivement

0 0 50 10 31 3 52 0 32 7 6… … ...

Gestion des ressources disques

84

Bitmap

Gestion des ressources disques

0 1 2 3 4 5 6 7 8 9 10 11 120 0 0 0 0 0 1 1 1 1 1 0 0 01 1 1 1 0 0 0 0 0 1 1 1 1 12 0 0 0 1 1 1 1 0 0 0 0 0 03 0 0 0 0 1 1 1 1 0 0 1 1 14 1 1 0 0 1 1 0 0 0 0 1 0 05 1 1 1 1 0 0 0 0 0 0 0 1 1

PistesSecteurs

0 = libre, 1 = occupé

85

Le lien entre le nom d’un fichier et sa localisation sur disque estréalisé à l’aide d’une table de correspondance appelée répertoire(directory).On peut concevoir des répertoires à un seul niveau, i.e.contenant le nom de tous les fichiers du disque, ou à plusieursniveaux, permettant à chaque utilisateur d’organiser ses fichiersde façon hiérarchique au moyen de sous-répertoires.

Répertoires

86

Structure d ’un disque souple

Piste0

Secteur 123456789

10 11 12 13 14 15 16 17 18

BOOTFAT1 FAT1 FAT1 FAT1 FAT1 FAT1 FAT1 FAT1 FAT1 FAT2 FAT2 FAT2 FAT2 FAT2 FAT2 FAT2 FAT2

1FAT2DIR DIR DIR DIR DIR DIR DIR DIR DIR DIR DIR DIR DIR DIR

u.a. 2 u.a. 3 u.a. 4

2u.a. 5

678....

Débu t des données del'utilisateur

87

ExtensionAttribut

RéservéNom(en ASCII)Statut

Réservé Heure DateNo. dela1eu.a.

Tailledu fichier

0 7 9 15

16 21 23 25 27 31

AttributsŹ:1 = Lecture seulement2 = Fichier cachˇ4 = Fichier syst¸ me8 = Nom du volume16 = Sous-rˇ pertoire32 = Archive

88

Table d’allocation de fichiers (FAT)

FF FF

Type dedisque

No.de l'u.a.suivante dufichier ou:000=libreFF8-FFF=dernière u.a. d'un fichierFF7=non lisible

0 1 2 3 4 5 6 7 8 9U.a. No.

Dans la FAT originale de DOS, on n’avait que 12 bits par entrée. Ceci limitait la taille du disque à 4095 u.a.Par exemple, 4096 u.a. de 512 octets = 2 Mo.

89

On peut grossir la taille des unités d’allocation, mais la perted’espace par fichier augmente en conséquence. En moyenne,cette perte est de 1/2 u.a. par fichier.

Depuis ce temps, on a eu la FAT16, avec 16 bits par entrée, etsur les disques durs on utilise aujourd’hui la FAT32 avec 32 bitspar entrée.Windows NT et Windows 2000 utilisent un nouveau système defichiers beaucoup plus performant appelé NTFS.

90

Unix a été développé par Bell Laboratories à partir de 1970 parKen Thompson et Dennis Ritchie. Ce système a été missuccessivement sur PDP-7, 9 et 11, puis sur VAX, et enfin surdes machines à base de microprocesseur MC68000. Aujourd’hui,il fonctionne sur les stations de travail avec des micro-processeurs RISC.

En l979, on en est rendu à la version 7, la mieux connue. En1982 apparaît le SYSTEM III, puis en 1983 le SYSTEM V suivantla politique de distribution commerciale de AT&T.

Exemple : UNIX

91

Depuis 1991, le phénomène Linux a fait son apparition. Il s'agitd'un UNIX de domaine public pour micro-ordinateur initialementécrit par un étudiant en informatique finlandais, Linus Torvalds.

Il a été porté sur plusieurs plates-formes, notamment : Intel80x86, PowerPC, Alpha, Amiga, etc. Sa conception est moderneet c'est elle que nous examinerons ici.

Exemple : UNIX

92

Sous Unix, un fichier est une séquence linéaire de mots de 8bits, de 1 octet à 1000 Mo. L'usager visualise le fichier commeune séquence linéaire et peut atteindre n'importe quel octet dufichier soit de façon absolue, soit en spécifiant une positionrelative par rapport à la position courante, ou encore par rapportà la fin du fichier.

À partir d'une position quelconque, on peut lire un nombrequelconque d'octets.

Exemple : UNIX

93

Exemple : UNIXUnité d'allocation : bloc de 512 octets 1024 octets pour le SYSTEM V et le système 4.1 de Berkeley. 4096 octets pour la version 4.2,

1 Ko à 4 Ko pour Linux.

94

À chaque fichier (y compris les répertoires qui sont égalementdes fichiers et les périphériques, que Unix considère comme desfichiers spéciaux) on associe un inode (i-node ou index-node)dans lequel on peut trouver les informations suivantes :- le propriétaire (user ID, group ID)- les protections (code de 16 bits)- les dates (création, dernièremodification)- les liens vers d'autres nœuds-i(nombre de répertoires qui contiennent ce fichier)- le type de fichier (données,répertoire, périphérique)- les adresses disques des blocs dedonnées (13)- la longueur du fichier en octets.

Exemple : UNIX

95

Exemple : UNIX

0 Type et permissions Utilisateur (UID) Taille du fi chier8 Heure et da te d 'accès Heure et da te de création

16 Heure et da te de modification Heure et da te d 'effacement24 Groupe (GID) Compteur de liens Nb. de blocs32 Attributs du fichier Réservé40 1e bloc 2e bloc48 3e bloc 4e bloc56 5e bloc 6e bloc64 7e bloc 8e bloc72 9e bloc 10e bloc80 11e bloc 12e bloc88 Bloc de 1e indirection Bloc de 2e indirection96 Bloc de 3e indirection Version du fichier

104 ACL du fichier ACL du répertoire112 Adresse de fragment Réservé120 Réservé

AC L = Ac cess Control List, pas enco re implémenté

96

Exemple : UNIX

Dans Linux, la taille d’un inode est de 128 octets.

Dans le système de fichiers Ext2 adopté par la plupart dessystèmes Linux, le disque est divisé en groupes de blocs.Chaque groupe de blocs contient un superbloc, des descripteursde groupe, un bitmap de blocs, un bitmap d'inodes, une tabled'inodes et des blocs de données. Les bitmaps occupent chacun1 bloc ou u.a. Ceci limite donc la taille des groupes à 8 192blocs pour des blocs de 1 Ko. ou 32 768 blocs pour des blocs de4 Ko. Les inodes sont répartis également parmi les groupes deblocs. Le nombre d'inodes par groupe ne peut non plus dépasserles nombres ci-dessus.

97

Exemple : UNIXBloc 0

Blocd’amorce

Groupe de blocs 0 Groupe de blocs 1 … Groupe de blocs n

Chaque groupe de blocs contient une copie du superbloc, des inodes et des blocs de données :

Super-bloc

Descripteursde groupe

Bitmapde blocs

Bitmapd'inodes

Tabled'inodes

Blocs de données

98

Exemple : UNIX

Le superbloc contient le nombre d'inodes et le nombre de blocsdans le système de fichiers. Il contient aussi de l'information surle nombre d'inodes et de blocs par groupe de blocs.

Le descripteur de groupe est une structure de 32 octets donnantle nombre de blocs dans le bitmap d'inodes, dans le bitmap deblocs et dans la table d'inodes, le nombre d'inodes libres, lenombre de blocs libres et le nombre de répertoires. Cettedernière information est utile au système qui tente répartir lesrépertoires parmi les différents groupes de blocs. Il allouera doncun nouveau répertoire dans le groupe qui en a le moins.

Cette organisation permet aux inodes d'être voisines des blocsauxquels elles font référence, et aux inodes d'être voisines deleur inode de répertoire, ce qui permet un accès plus rapide.

99

Exemple : UNIX

Dans chaque inode, on trouve 15 adresses disque en termes deno de blocs. Les 12 premières adresses d'une inode permettentd'atteindre un espace données de :

12 1024 octets = 12 288 octets.

La 13e adresse disque pointe vers un autre bloc de 1024 octetsqui contient 256 adresses disque (4 octets par adresse), soit :

256 1024 octets = 262144 octets.

La 14e adresse disque pointe vers 256 blocs indirects(indirection d'ordre 2) qui pointent à leur tour chacun vers 256adresses disques :

256 256 1024 octets = 67108 864 octets.

100

Exemple : UNIX

La 15e adresse disque est une indirection d'ordre 3, ce quipermet aux fichiers Linux d'atteindre des tailles avoisinant

256 256 256 1024 octets = 17 179 869 184 octets.

La taille maximale d'un tel fichier sera donc :

17 179 869 184 + 67 108 864 + 262 144 + 12 288 Go.

Cette implantation privilégie, du point de vue accès, les fichiersde petite taille (12 Ko). À l'ouverture, le premier descripteur dufichier (inode) est copié en mémoire. Lorsqu'on franchit le cap de12 288 octets, le système d'exploitation copie le premier blocindirect, et ainsi de suite.

101

Exemple : UNIXPour savoir où se trouve l'octet n d'un fichier,:° si n < 12 288, il se trouve dans le bloc direct n / 1024 à l'offset

n mod 1024.° si n >12 288 et n ≤ 262 144, il se trouve dans le bloc donné par

la table de première indirection (n - 12 288) / 1024 à l'offset : (n - 12 288) mod 1024,

° etc.

102

Exemple : UNIX

Ext2 tente de minimiser la fragmentation des fichiers lors del'allocation des blocs. Il cherche des blocs libres autour d'un bloccible. Si ce dernier est libre, il est alloué. Sinon, on cherche unbloc libre dans les 32 entourant le bloc cible. Si on en trouve un,il est alloué. Sinon, on cherche un bloc libre qui soit au moinsdans le même groupe de blocs que le bloc cible. Il y a plusieursheuristiques pour la définition du bloc cible. L'un d'entre eux estde prendre le premier bloc libre dans le groupe de blocs où setrouve l'inode du fichier.

Lorsqu'un bloc libre est trouvé, on réserve les 8 blocs suivants,s'ils sont libres. Quand le fichier sera fermé, les blocs réservésrestants seront libérés.

103

Exemple : UNIXRépertoires

Les entrées d'un répertoire Linux sont de longueur variable parce queles noms de fichier peuvent aller de 1 caractère à 255 caractères. Ils'agit en fait d'une liste chaînée, puisque le champ longueur de l'entrée(rec_len), toujours arrondi vers le haut à un multiple de 4, donne en faitla position de l'entrée suivante.

Octets 4 2 2 1 à 255rec_len name_len Nom du fichier

No. d'inode longueur longueur

de l'entrée du nom

104

Exemple : UNIX

inode rec_len name_len Entrée

3 12 1 . Pointeur vers lui-même2 12 2 .. Pointeur vers son parent11 20 9 Fichier 1

2017 12 4 Toto

… … … …… … … …

123 1 . 2120

12 2 ..24

2011 9 Fichier 144

122017 4 Toto56

105

Exemple : UNIXRépertoires

Chaque répertoire ne peut avoir qu'un parent. Le répertoireracine n'a pas de parent et son pointeur “parent” contient lui-même, c.-à-d. le #2.

Lorsqu'un fichier est effacé, le numéro d'inode de l'entrée derépertoire est mis à 0 et l'entrée est éliminée de la liste chaînéeen augmentant le champ rec_len de l'entrée précédente pourqu'elle pointe à l'entrée suivante.

2) le SGF d’UNIX (1/3)

* Structure hiérarchique

* 4 types de fichiers:ordinaires: suite octetscatalogues: nœuds de l’arbre de cette structureliens: pointent vers fichierspéciaux: accès aux périphériques

2) le SGF d’UNIX (2/3)

Fichier et structure inode:

1) Type (parmi les 4)2) Taille3) Date4) Permission5) Propriétaire6) Localisation des données

Micro$oft en 1988…

* Mieux que la FAT du Dos/Windows

* Mieux que HPFS de OS/2

New Technology File System (NTFS)

le SGF de Windows NT

* Logical Cluster Numbers (LCN)* Virtual Cluster Number (VCN)

Master File Table...

le SGF de Windows NT

File Record ...

le SGF de Windows NT

* Resident* Non Resident

* Attribute header* Attribute value

File Record Sample...

3) le SGF de Windows NT (4/5)

MFT in action !

Mais elle ressemble à quoi cette

MST ? MFT ?

La comparaison...

Feature XFS UFS VxFS NTFS

Max FS Size 18 million TB 1 TB 1 TB 2 TB

Max File Size 9 million TB 1 TB 1 TB 2 TB

File SpaceAllocation

Extents Blocks Extents Extents

Max. Extent Size 4 GB NA 64 MB Undoc’d

Free SpaceMgmt

Free extentsorganized by

B+ trees

Bitmap percylinder grp

Bitmap perallocation unit

Single bitmap

Variable BlockSize?

512 bytes to 64KB

4KB or 8KB 512 bytes to64KB (4KB w/compression)

Sparse FileSupport?

Yes Yes No NT 5.0

DirectoryOrganization

B+ Tree Linear Hashed B+ tree

Inode allocation Dynamic Static Dynamic Dynamic

Crash Recovery Asynch.Journal

Fsck* Synch. Journal Synch. Journal

MaximumPerformance

7GB/sec

4GB/sec (singlefile)

Not Available 1GB/sec Not Available

chapitre dernier (résumé)

Structure de mémoire de masse (disques)

Disques magnétiques

Plats rigides couverts de matériaux d ’enregistrement magnétique surface du disque divisée en pistes (tracks)

qui sont divisées en secteurs le contrôleur disque détermine l`interaction

logique entre l ’unité et l ’ordinateur

Ordonnancement disques

Problème: utilisation optimale du matériel

Réduction du temps total de lecture disque étant donné une file de requêtes de lecture

disque, dans quel ordre les exécuter?

Paramètres à prendre en considération

Temps de positionnement (seek time): le temps pris par l`unité disque pour

se positionner sur le cylindre désiré Temps de latence de rotation

le temps pris par l ’unité de disque qui est sur le bon cylindre pour se positionner sur le secteur désirée

Temps de lecture temps nécessaire pour lire la piste

Le temps de positionnement est normalement le plus important, donc il est celui que nous chercherons à minimiser

File d’attente disque

Dans un système multiprogrammé avec mémoire virtuelle, il y aura normalement une file d’attente pour l ’unité disque

Dans quel ordre choisir les requêtes d ’opérations disques de façon à minimiser les temps de recherche totaux

Nous étudierons différents méthodes par rapport à une file d ’attente arbitraire:

98, 183, 37, 122, 14, 124, 65, 67 Chaque chiffre est un numéro séquentiel de cylindre Il faut aussi prendre en considération le cylindre de départ: 53 Dans quel ordre exécuter les requêtes de lecture de façon à

minimiser les temps totaux de positionnement cylindre Hypothèse simpliste: un déplacement d`1 cylindre coûte 1 unité

de temps

Premier entré, premier sorti: FIFO

Mouvement total: 640 cylindres = (98-53) + (183-98)+...En moyenne: 640/8 = 80

axe de rotation45

85

14685

108

11059

2

SSTF: Shortest Seek Time FirstPlus court d’abord

À chaque moment, choisir la requête avec le temps de recherche le plus court à partir du cylindre courant

Clairement meilleur que le précédentMais pas nécessairement optimal! (v.

manuel) Peut causer famine

SSTF: Plus court servi

Mouvement total: 236 cylindres (680 pour le précédent)

En moyenne: 236/8 = 29.5 (80 pour le précédent)

SCAN: l’algorithme de l’ascenseur La tête balaye le disque dans une

direction, puis dans la direction opposée, etc., en desservant les requêtes quand il passe sur le cylindre désiré Pas de famine

SCAN: l ’ascenseur

Mouvement total: 208 cylindresEn moyenne: 208/8 = 26 (29.5 pour SSTF)

direction

Problèmes du SCAN

Peu de travail à faire après le renversement de direction

Les requêtes seront plus denses à l’autre extrémité

Arrive inutilement jusqu’à 0

C-SCAN

Retour rapide au début (cylindre 0) du disque au lieu de renverser la direction

Hypothèse: le mécanisme de retour est beaucoup plus rapide que le temps de visiter les cylindres Comme si les disques étaient en forme de cercle!

CC--LOOKLOOK La même idée, mais au lieu de retourner au

cylindre 0, retourner au premier cylindre qui a une requête

C-LOOK

153 sans considérer le retour (19.1 en moyenne) (26 pour SCAN)MAIS 322 avec retour (40.25 en moyenne)Normalement le retour sera rapide donc le coût réel sera entre les deux

retour: 169 (??)

direction

C-LOOK avec direction initiale opposée

direction

Résultats très semblables:157 sans considérer le retour, 326 avec le retour

Retour 169