Plan du cours- Introduction

- Emergence et évolution des systèmes d’exploitation

- Système de fichiers : FAT - NTFS

- Ordonnancement

– Systèmes d’exploitation 1ère année – – p. 1

FATFAT = File Allocation TableSystème de fichiers de DOS (dérivé de CP/M unix),reconnu par d’autres OS :

Windows et linux . . .

documenté :

1. Hardware White Paper : "FAT : General Overview ofOn-Disk Format"

2. ISO/IEC 9293 :1994

– Systèmes d’exploitation 1ère année – – p. 2

FAT - allocationallocation de l’espace par blocs avec index

- CLUSTERS (blocs)

- FAT File Allocation Table (index)

. FAT12 (12 bits)

. FAT16/vfat (16 bits)

. FAT32 (28/32 bits)

– Systèmes d’exploitation 1ère année – – p. 3

FAT - Structurestructure d’une partition FAT

métadonnées et données du système de fichiers

- boot sector : métadonnées du système de fichiers

- FAT : index

- répertoire racine (FAT16)

- clusters : blocs des fichiers et répertoires

les clusters ne sont pas alignés sur le début de la partition

– Systèmes d’exploitation 1ère année – – p. 4

FAT - clusterstaille des clusters

taille d’un cluster : définie au formatage

1 cluster = n secteurs (512 bytes), n=puissance de 2 :

TAB. 1: Tailles des clusters

n 1 2 4 . . . 64 128

taille cluster 512b 1Kb 2Kb . . . 32Kb 64Kb

– Systèmes d’exploitation 1ère année – – p. 5

FAT - quelles limites ?certaines versions de windows limitent les clusters à 32Kb. . .

il est important de distinguer

- les limites dues au format

- les limites dues à l’utilisation

-> on parlera plutôt des limites dues au format (théoriques )

– Systèmes d’exploitation 1ère année – – p. 6

FAT - tabletaille des partitions

TAB. 2: Tailles maximum théoriques

Nom bits max clusters max taille

FAT16 16 2 exp 16 4GbFAT32 28(32) 2 exp 28 16Tb

– Systèmes d’exploitation 1ère année – – p. 7

FAT - tableFAT = index

- contient une entrée par cluster de la partition

- décrit le chaînage des clusters des fichiers

- chaque entrée contient le numéro du cluster suivantau sein du fichier

des valeurs particulières indiquent la fin de fichiers

– Systèmes d’exploitation 1ère année – – p. 8

FAT - tableFAT : valeurs réservées (FAT12,FAT16) :

- 0 - cluster disponible

- (F)FF0H à (F)FF6H (65520 - 65526) - cluster reservéMS-DOS

- (F)FF7H - cluster défectueux

- (F)FF8H à (F)FFFH - (-1) - dernier cluster du fichier

-> 2-65519 : clusters utilisables (non réservés)

-> 2-65526 : plage d’adresses des clusters pouvantêtre chaînés dans la FAT

– Systèmes d’exploitation 1ère année – – p. 9

FAT - tailles

16 ou 32 ?

- la taille maximum théorique d’un volume FAT32 est16Tb

- la taille maximim théorique d’un volume FAT16 est 4GB

-> taille des clusters ?

– Systèmes d’exploitation 1ère année – – p. 10

FAT - taillestaille de la table FAT

comment calculer la taille de la table FAT (index)

nombre entrées FAT = taille partition / taille clusters

taille FAT = nombre entrées FAT * taille entrée FAT

- la taille de la FAT pour un volume FAT32 de 500Gb etdes clusters de taille 4Kb est 500 Mb !

- avec des clusters de 16Kb on réduit à 125Mb

– Systèmes d’exploitation 1ère année – – p. 11

FAT - taillesla taille maximum d’une table FAT16 est 128Kb

la taille d’une table FAT32 peut devenir très grosse

chargée en RAM au démarrage du système ! !

-> un grand volume FAT ralentit le démarrage du système

– Systèmes d’exploitation 1ère année – – p. 12

FAT - valeurs défauttaille partition type de FAT< 2 Gb FAT162 Gb - 32 Gb FAT32> 32 Gb NTFS

– Systèmes d’exploitation 1ère année – – p. 13

FATil existe des restrictions supplémentaires :

- outils mal programmés ...

- table des partitions d’un disque MBR

- adressage des secteurs du disque

- . . .

– Systèmes d’exploitation 1ère année – – p. 14

FAT - exercicescalculer :

- taille maximum d’une table FAT 16 ?

- taille maximum d’une partition FAT 16 ?

- que peut-on dire de la fragmentation interne ?

- taille minimum de clusters pour 2 Tb en FAT 32(28) ?

- taille de la table FAT dans ce cas ?

- taille de la table FAT avec clusters de 4Kb pour 32 Gben FAT 32(28) ?

– Systèmes d’exploitation 1ère année – – p. 15

FAT - Structurestructure d’une partition FAT

métadonnées et données du système de fichiers

- boot sector et zone réservée (1 secteur pour FAT 12-16, 32 secteurs pour FAT32)

- zone FAT

- zone du répertoire racine (FAT 12-16)

- zone pour les fichiers et répertoires

– Systèmes d’exploitation 1ère année – – p. 16

FAT - secteur de Bootle Boot sector et Bios Parameter Blockmétadonnées du système de fichiers :

- (3b) instruction de saut au chargeur du système (plus loin)

- . . .

- (2b) taille d’un secteur (512)

- (1b) nombre de secteurs par cluster

- (2b) taille zone réservée (1-32)

- (1b) nombre de FAT (2)

- (2b) nombre d’entrées de 32 bytes dans le répertoire racine en FAT16 (512, 0 pourFAT32 et 4 bytes ailleurs)

- (2b) nombre de secteurs dans le volume FAT (4b pour FAT32)

- . . .

- code du chargeur du système

avec restrictions d’usage car les outils n’en ont pas toujours tenu compte :-(

– Systèmes d’exploitation 1ère année – – p. 17

FAT - secteur de Bootnombre d’entrées répertoire racine

pour une FAT 16 le nombre d’entrés du répertoire racineest limité :

512 - 1 (utilisé pour pour le Volume-id)

inférieur dans le cas d’utilisation de noms longs !

– Systèmes d’exploitation 1ère année – – p. 18

FAT - exemple

- reconstituons entièrement A et B à partir du numéro deleur premier cluster

– Systèmes d’exploitation 1ère année – – p. 19

FAT - répertoires

répertoire

- fichier particulier

- contient les métadonnées des fichiers

- descripteurs de 32 bytes (un parfichier/sous-répertoire)

- fichier d’enregistrements

- a au moins deux sous-répertoires : dot, dotdot(sauf laracine)

– Systèmes d’exploitation 1ère année – – p. 20

FAT - localiser

– Systèmes d’exploitation 1ère année – – p. 21

FAT - répertoires

entrée de répertoire

tout fichier/répertoire est décrit dans son répertoire parent(mais est-ce bien vrai ?)

les 32 bytes d’une entrée de répertoire en FAT16

– Systèmes d’exploitation 1ère année – – p. 22

FAT- répertoiresattributs :

- ARCHIVE

- READ_ONLY

- HIDDEN

- SYSTEM

- DIRECTORY

- VOLUME_ID

- 2 bits à 0

– Systèmes d’exploitation 1ère année – – p. 23

FAT- répertoiresnom et extension : 11 bytes (8+3)

- nom DOS

premier byte du nom : valeurs particulières

- 0x00 : première entrée libre

- 0xF5 : fichier supprimé

- 0x05 : vaut 0xF5 :-)

- . . .

noms longs depuis vfat

– Systèmes d’exploitation 1ère année – – p. 24

FAT- répertoires

- en cas de nom long on occupe plusieurs entréesrépertoire

- chaque nouvelle entrée permet d’étendre le nom de 13caractères

- l’entrée est marquée grâce à l’attribut ATTR_LONG_NAME

- ATTR_LONG_NAME = READ_ONLY + HIDDEN + SYSTEM + VOLUME_ID

la combinaison d’atributs est ignorée par DOS

ce choix assurait la compatibilité ascendantepour DOS

– Systèmes d’exploitation 1ère année – – p. 25

FAT- répertoiresheure-date en FAT16 :

dernier accès en écritureune heure et une date (2 bytes chacun)

- heure : (heure : 5 bits, minutes : 6 bits, secondes : 5 bits) -> max secondes 32 (30)précision 2 secondes ! !

- date : (jour : 5 bits, mois : 4 bits, année : 7 bits) -> max année = 127 ans (1980+127 =2107)

et si on représentait date par un nombre de

secondes sur 32 bits ?(2exp32 sec)/(1 jour =86400 sec) / 365 = 136 ans (1980+136 = 2116)-> 9 ans de plus avec 1 seconde comme précision !

– Systèmes d’exploitation 1ère année – – p. 26

FAT- répertoiresheure-date en FAT32

un byte dans la partie réservée permet d’obtenir uneprécision plus fine :0-199 centièmes de secondes (= 2 secondes)

gère également la date du dernier accès (lecture ouécriture)

– Systèmes d’exploitation 1ère année – – p. 27

FAT- répertoiresnuméro du premier bloc : 2 bytes

le premier cluster du fichier

pour un fichier vide ce premier cluster vaut 0

FAT32 utilise 4 bytes pour ce champ (deux bytes supplémentaires dans la partie réservée)

– Systèmes d’exploitation 1ère année – – p. 28

FAT- répertoirestaille du fichier : 4 bytes (taille logique)

-> le plus grand fichier sur une partition FAT : 4Gb

– Systèmes d’exploitation 1ère année – – p. 29

FAT - racine

répertoire racine

particularités du répertoire racine : aucun autre répertoirene le décrit

nom ? premier cluster ? longueur ?

sa position est calculable

son contenu, comme celui des autres répertoires, est unesuite de descripteurs de fichiers/répertoires de 32 bytes :un par entrée

sa longueur : une métadonnée du système de fichiers

– Systèmes d’exploitation 1ère année – – p. 30

FAT - racineen FAT12-16

- le répertoire racine a un emplacement fixe calculable

- sa taille est limitée !

- son allocation contiguë

en FAT32

- racine = chaîne de clusters, le premier est connu(souvent le 2)

la zone réservée en début de partition contient :

- le n°du premier cluster, les suivants sont chaînés

- le nombre d’entrées du répertoire racine (4bytes)

– Systèmes d’exploitation 1ère année – – p. 31

FAT - localiserlocalisation

- quel numéro de cluster F du fichier contient le byte N dufichier ?

- quel numéro de cluster disque correspond au cluster Fdu fichier ?

- quel est le numéro de secteur contenant le byte N dufichier ?

- quelle est la position du byte N dans ce secteur ?

– Systèmes d’exploitation 1ère année – – p. 32

FAT - localiser

numérotation des clusters

les clusters sont numérotés depuis le n°2

- pour une FAT16 le cluster 2 suit le répertoire racine

- pour une FAT32 le cluster 2 suit les tables FAT

la position d’un cluster est calculée sur base desmétadonnées du système de fichiers

– Systèmes d’exploitation 1ère année – – p. 33

FAT - localiserexemple :

Soit une partition FAT16 avec le fichier et le répertoire :\rep\fichLe fichier contient 1030 caractères ’a’La taille des clusters est 1Kb (1024 bytes)Le répertoire rep est décrit dans le cluster 268Le fichier fich occupe les clusters 1000 et 1024

essayons de dessiner la structure du système de fichiersFAT correspondant

comment fait le système pour accéder aux données dufichier \rep\fich ?

– Systèmes d’exploitation 1ère année – – p. 34

FAT - localiser- localiser \

- lire les enregistrements successifs du fichier \ jusqueau descripteur de "rep" et obtenir sa position

- lire les enregistrements successifs du fichier rep jusqueau descripteur de "fich" (en parcourant les clusterschaînés)

- obtenir la position de fich

- lire les données du fichier fich (en parcourant lesclusters chaînés)

comment le Système d’exploitation sait-il que le cluster1024 ne contient que 6 ’a’ ?

– Systèmes d’exploitation 1ère année – – p. 35

FAT - localiser

– Systèmes d’exploitation 1ère année – – p. 36

FAT - questions

- que doit faire le système quand la taille d’un fichieraugmente et que le dernier cluster du fichier est plein ?

- que doit faire le système pour créer un nouveau fichiervide ?

- que doit faire le système pour lire un fichierentièrement ?

- que doit faire le système pour créer un nouveaurépertoire ?

- pourquoi le premier cluster d’un nouveau répertoire nevaut pas 0 ?

– Systèmes d’exploitation 1ère année – – p. 37

FAT - exercicesservez-vous des informations du secteur de boot pour :

- calculer le nombre de secteurs occupés par lerépertoire racine en FAT16

- calculer la position du cluster N

peut-on saturer un système de fichiers FAT16 de 2Gb ,

- avec +/- 2 exp 30 fichiers de 1 byte ?

- avec +/- 2 exp 16 fichiers de 1 byte ?

- avec +/- 30 fichiers de 1 byte ?

- pourquoi ?

– Systèmes d’exploitation 1ère année – – p. 38

FAT - Questions- les clusters d’une FAT ont tous la même taille [V-F]

- en FAT, il y a perte d’espace disque par fragmentationinterne [V-F]

- un répertoire quelconque en FAT tient sur maximum uncluster [V-F]

- la File Allocation Table sert à trouver le premier clusterd’un fichier[V-F]

– Systèmes d’exploitation 1ère année – – p. 39

FAT - appels systèmeA ce stade, le SE dispose d’une description d’un Systèmede fichiers appelé FAT

Le programmeur système peut écrire les différents servicesqui permettront de manipuler ce FS

Ces différents services seront écrits sous forme d’appelssystème.

Quelques cas . . .

– Systèmes d’exploitation 1ère année – – p. 40

FAT - appels système

les appels système ...

les fichiers sont lus en plusieurs opérations successives

-> stocker localisation et position courante dans une Tabledes descripteurs de fichiers ouverts en RAM

- open s’occupe de localiser le fichier

- read

- write

- seek

- close libère l’entrée de la table

- . . .

– Systèmes d’exploitation 1ère année – – p. 41

FAT - appels système

Appel de l’appel système openA l’aide de l’instruction INT.

en précisant que c’est l’appel système open que l’onsouhaite

Informations échangées avec l’appel système Open

1. le nom de fichier doit être fourni

2. après l’appel Système, il faut pouvoir récupérer le n°d’entrée dans la table des processus

Pourquoi faut-il un n°d’entrée ?

– Systèmes d’exploitation 1ère année – – p. 42

FAT - appels systèmePour ouvrir le fichier \windows\desktop\image.jpg, leprogramme doit :

- Compléter le registre 1 avec le nom de fichier

- Compléter le registre 2 avec le n°de l’appel systèmecorrespondant à open

- INT

- . . .

- Lorsque le processus est débloqué et nouvellementélu : lire le n°de l’entrée du fichier dans un registre 3récupéré de la table des processus.

– Systèmes d’exploitation 1ère année – – p. 43

FAT - appels système

Appel système open

1. sauvegarder le contexte du processus appelant.

2. parcourir le F.S. pour trouver le n°du premier cluster dufichier.

3. ouvrir une entrée dans la table en mémoire quimémorise n°de premier cluster et position courantedans ce fichier (0 au départ)

4. mémoriser ce n°d’entrée dans la table des processus(registres) pourque le processus puisse en disposer

5. effectuer un branchement à l’ordonnanceur.

Que pensez-vous du point 2 ?

– Systèmes d’exploitation 1ère année – – p. 44

FAT - appels système

Appel de l’appel système readà l’aide de l’instruction INTcet appel utilise les informations suivantes :

- n°de fichier

- adresse où placer le résultat de la lecture

- nombre de bytes à lire

l’appel système fournit également une information :

- Le nombre de bytes réellement lus

A quoi peut servir ce nombre ?

– Systèmes d’exploitation 1ère année – – p. 45

FAT - appels systèmePour lire 271 bytes du fichier n°7, le programme doit :

- Compléter le registre 1 avec le numéro du fichier, soit 7.

- Compléter le registre 2 avec l’adresse de la mémoire oùles 271 bytes seront écrits, soit un nom de variable.

- Compléter le registre 3 avec le nombre de bytes à lire,soit 271.

- INT

- . . .

- Une fois réélu : lire le nombre de bytes réellement lusdans un registre 4.

– Systèmes d’exploitation 1ère année – – p. 46

FAT - appels système

Appel système read

read va donc :

- sauvegarder le contexte du processus appelant.

- commander le périphériue

- demander au D.M.A. de transférer du disque vers lamémoire (d’où ? où ?, combien ?).

- mémoriser qui est le processus qui demande letransfert D.M.A.

- mettre l’état du processu appelant à bloqué.

- effectuer un branchement à l’ordonnanceur.

– Systèmes d’exploitation 1ère année – – p. 47

FAT - INT externe D.M.A.- sauvegarder le contexte du processus en cours(->prêt).

- Debloquer le processus qui avait demandé le transfertD.M.A.

- inscrire dans la table des fichiers ouverts en mémoire lanouvelle position courante dans ce fichier.

- effectuer un branchement à l’ordonnanceur.

– Systèmes d’exploitation 1ère année – – p. 48

Exercices- Détailler le fonctionnement de l’appel système write.

- Détailler le fonctionnement de l’appel système seek.

– Systèmes d’exploitation 1ère année – – p. 49

FAT - fiabilitéincohérences

des incohérences peuvent survenir suite à une panne decourant lors d’ajout ou suppression d’un cluster d’un fichier

ajout d’un cluster :

- le cluster libre pointe vers le clusters suivant du fichierou la fin du fichier

- le cluster qui précède le nouveau pointe vers lenouveau cluster

– Systèmes d’exploitation 1ère année – – p. 50

FAT - fiabilitésuppression d’un cluster :

- le cluster qui précède celui à supprimer pointe vers leclusters suivant

- le cluster à supprimer est marqué libre

Dans les deux cas, si une panne de courant survient entreles deux mises à jour, la FAT sur disque reste dans un étatincohérent

– Systèmes d’exploitation 1ère année – – p. 51

FAT - fiabilitéexemple dans le cas d’ajout :

– Systèmes d’exploitation 1ère année – – p. 52

FAT - fiabilitéUne incohérence peut survenir dans une informationredondante

- un cluster libre chaîné ?

- un cluster non chaîné, non libre ?

la redondance permet de "réparer" l’incohérence

où est la redondance dans ce cas ?

– Systèmes d’exploitation 1ère année – – p. 53

FAT - fiabilitéla commande chkdsk utilise cette redondance :

1. parcourt la FAT à la recherche des clusters chainés :ceux qui apartiennent à un fichier

2. cherche les clusters libres : ceux qui ont un 0 en FAT

en théorie un cluster "normal" doit soit être libre soit êtrechaîné

La comparaison entre ces deux résultats permet d’isolerdes "chaines de clusters perdues"Ces dernières sont récupérées sous forme de fichiersnommés FILE0000.CHK, FILE0001.CHK dans le répertoireracine

– Systèmes d’exploitation 1ère année – – p. 54

FAT - fiabilitéCluster défectueux ?cluster défectueux dans un fichier -> perte d’une partie dedonnées

cluster défectueux dans la FAT -> le système de fichiersrisque d’être fortement compromis

-> la copie de la FAT peut être maintenue pour garantirune plus grande fiabilité

si le cluster défectueux est au niveau d’un fichier utilisateurc’est moins grave

– Systèmes d’exploitation 1ère année – – p. 55

FAT - conclusions- (++)FAT système de fichiers simple et connu par

plusieurs systèmes d’exploitation

- (-)taille des fichiers limitée à 4Gb

- (-)pas de gestion d’attributs pour la protection d’accès

- (-)non adapté aux grandes partitions, ni à unenvironnement multiutilisateur

- (-)souffre de la fragmentation des fichiers

NB. la fragmentation de fichiers est due notamment à la manière d’allouer les nouveauxblocs aux fichiers (en début de volume)

– Systèmes d’exploitation 1ère année – – p. 56

FAT - conclusionsTable FAT chargée en RAM et mise à jour en même tempsen RAM et sur le disque

- (-)taille FAT imposante pour grandes partitions etclusters petits

- (-)chargement de la FAT en RAM : ralentit ledémarrage du système

– Systèmes d’exploitation 1ère année – – p. 57

FAT16/32 - conclusions- (+)FAT32 utilise l’espace plus efficacement que FAT16

- (-)FAT32 +lent au chargement car grosse table FAT

Les clés usb ou disques externes actuels sont souventformatés en FAT

– Systèmes d’exploitation 1ère année – – p. 58

FAT - VRAI-FAUX- L’appel système open fait des lectures sur le disque

- Détaillez ce que fait l’appel système open

– Systèmes d’exploitation 1ère année – – p. 59