Module 10 – Structure de mémoire de

masse (disque)

Chapitre 10 (Silberschatz)

Chap. 10 1
 Concepts importants du Module 10
 Fonctionnement et structure des unités
disque
 Calcul du temps d’exécution d’une
séquence d’opérations
 Différents algorithmes d’ordonnancement
 Fonctionnement, rendement
 Gestion de l’espace de permutation
 Unix

 RAID – disques résistants aux erreurs

Chap. 10 2
 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

Chap. 10 3
 Nomenclature -
cylindre: l’ensemble de pistes qui se trouvent dans la
même position du bras de lecture/écriture

Chap. 10 4
 Disques électroniques
 Aujourd’hui nous trouvons de plus en plus
des types de mémoires qui sont adressées
comme si elle étaient des disques, mais
sont complètement électroniques
 P. ex. flash memory – clefs USBs
 Il n’y aura pas les temps de positionnement,
latence, etc. discutés plus tard

Chap. 10 5
 Ordonnancement disques
 Problème: utilisation optimale du matériel
 Réduction du temps total de lecture disque
 étantdonné une file de requêtes de lecture
disque, dans quel ordre les exécuter?

Chap. 10 6
 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

Chap. 10 7
 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

Chap. 10 8
 Premier entré, premier sorti: FIFO

axe de
rotation
45
85

146
85
108
110
59
2

Mouvement total: 640 cylindres = (98-53) + (183-98)+...

En moyenne: 640/8 = 80
Chap. 10 9
 SSTF: Shortest Seek Time First
Plus 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édent
 Mais pas nécessairement optimal! (v.
manuel)
 Peut causer famine

Chap. 10 10
 SSTF: Plus court servi

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

En moyenne: 236/8 = 29.5 (80 pour le précédent)
Chap. 10 11
 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

Chap. 10 12
 SCAN: l ’ascenseur
direction

Mouvement total: 208 cylindres

En moyenne: 208/8 = 26 (29.5 pour SSTF)
Chap. 10 13
 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

Chap. 10 14
 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

C-LOOK
 La même idée, mais au lieu de retourner au
cylindre 0, retourner au premier cylindre
qui a une requête

Chap. 10 15
 C-LOOK
direction 

retour: 169 (??)

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
Chap. 10 16
 C-LOOK avec direction initiale opposée

direction

Retour 169

Résultats très semblables:

157 sans considérer le retour, 326 avec le retour
Chap. 10 17
 Exemple pratique…
 Si on doit ramasser des gens de Gatineau
Est à Aylmer, il pourrait être plus rapide de
faire le tour à Gatineau, puis prendre
l’autoroute jusqu’à Aylmer et ramasser le
reste, au lieu d’arriver à Aylmer par rues
régulières tout en ramassant des gens…

Chap. 10 18
 Comparaison
 Si la file souvent ne contient que très peu
d’éléments, l’algorithme du ‘premier servi ’ devrait
être préféré (simplicité)
 Sinon, SSTF ou SCAN ou C-SCAN?
 En pratique, il faut prendre en considération:
 Les temps réels de déplacement et retour au début
 L`organisation des fichiers et des répertoires
 Les répertoires sont sur disque aussi…
 La longueur moyenne de la file
 Le débit d ’arrivée des requêtes

Chap. 10 19
 Gestion des disques
 Formatage de bas niveau, i.e. formatage physique.
 Division du disque en secteurs manipuler par le
contrôleur
 Initialiser le secteur (fanion de début et de fin)
 Se fait chez le fournisseur.

 Les partitions
 Division du disque en partition en groups d’un ou
plusieurs cylindres (pour stocker un système de fichier).
 Définir la partition boot.

 Le format logique ou « création du système de

fichier »
 Écrire le SF sur le disque
 i.e. tableau FAT, SB, tableau d’inodes, répertoire
racine.
Chap. 10 20
 Démarrer d’un disque en Windows 2000

Chap. 10 21
 Gestions de mauvais blocs
Il y a des dizaine et centaines de millions de blocs
dans un disque
Des mauvais blocs y sont présents
Que faire d’eux
 Avons des blocs en surplus pour les remplacer
 i.e. Disque contiens 100 blocs, mais a été fabriqué
avec 110, donc 0..99 utilisé, 100..109 sont en surplus
 Si bloc 50 devient endommagé, le contrôleur (après
avoir été informé par le noyau) le remplace avec le
bloc 100 (il devient le bloc 50 logiquement)
 Ceci affect l’efficacité des algorithmes
d’ordonnancement des disques
 Pas de panique! Les blocs en surplus se
retrouvent dans chaque cylindre: sector
Chap. 10 sparing or sector slipping 22
 Gestion de l’espace de permutation en mémoire
virtuelle (swap space) (12.6)
 Nous avons vu comment les systèmes de
mém virtuelle utilisent la mém secondaire
 Grande variété d’implémentations de
systèmes d’espace de permutation dans
différents SE
 L’espace de permutation
 peut être des fichiers normaux dans l’espace
disque utilisé par les autres fichiers,
 ou peut avoir sa propre partition disque
 Peut être mis dans des disques plus
efficaces

Chap. 10 23
 Gestion d’espace de permutation (disque) en
Unix 4.3BSD

 Pour chaque processus, il y a

 Un segment texte = le programme
 Ne change pas pendant exécution

 Et il y a aussi un segment données

 Sa taille peut changer pendant exéc

Chap. 10 24
 Gestion d’espace de permutation
 Swap-space — mémoire virtuel qui utilise
l’espace disque pour étendre la mémoire
principale
 Où se trouve-t-il sur le disque?
 Dans un fichier normal du système
 bon: Simple, flexible
 mauvais: Leeeent

 Dans une partition séparée

 Structures et algorithmes optimaux et spécifiques
pour le swap.
 Ex: fragmentation pas un vrai problème

 Bon: plus rapide

 Mauvais: peut gaspiller de l’espace.

Chap. 10 25
 Gestion d’espace de permutation
 Quand alloué l’espace dans le swap?
 Quand le processus démarre – la page
virtuelle est créée.
 Quand la page est remplacée.

 Que doit-être géré?

 L’utilisation
des « swap maps » pour faire la
gestion des pages dans le swap.

Chap. 10 26
 Autres mécanismes en Unix
 Les mécanismes sont différents dans
différentes versions de Unix
 Les différentes versions fonctionnent avec
autres mécanismes, comme pagination,
systèmes compagnons (buddy) etc.

Chap. 10 27
 Niveaux RAID
 Striping: lecture de
plusieurs disques en
parallèle
 Entrelacement de bits
 Entrelacement de
blocs
 Redondance: données
redondantes pour
recouvrir données,
 données dupliquées
(disques miroirs)
 Parité ou codes de
correction
 Exemples: Les six
niveaux RAID stockent
4 disques de données

Chap. 10 28
 RAID: Redundant Array of Independent Disks

Stallings

En distribuant les données sur différents disques, il est probable

qu’une grosse lecture puisse être faite en parallèle (au lieu de lire
strip0 et strip1 en séquence, cette organisation permet de les lire
en même temps)
Chap. 10 29
 Redondance dans RAID

Stallings
Dupliquer les données pour incrémenter le parallélisme
et remédier aux pertes de données (coûteux mais
utilisé en pratique)
Chap. 10 30
 RAID: Correction d’erreurs par codes de
correction

Stallings

Les codes de correction d’erreur pour des données

enregistrées sur un disque sont sauvegardés sur un autre
disque (plus de résistance aux erreurs)

Chap. 10 31
 RAID: Correction d’erreurs par parité

Stallings

Les bits de parité pour des données enregistrées sur un disque

sont sauvegardés sur un autre disque

Chap. 10 32
 RAID: Correction d’erreurs par bits de parité
avec entrelacement de blocs

Stallings

Les codes de correction d’erreur pour des données

enregistrées sur un disque sont sauvegardés sur un autre
disque (plus de résistance aux erreurs)

Chap. 10 33
 RAID (0 + 1) et (1 + 0)

Chap. 10 34
 Concepts importants du Module 10
 Fonctionnement et structure des unités
disque
 Calcul du temps d’exécution d’une
séquence d’opérations
 Différents algorithmes d’ordonnancement
 Fonctionnement, rendement
 Gestion de l’espace de permutation
 RAID: réorganisation des fichiers pour
performance et résistance aux erreurs

Chap. 10 35