Systèmes d’exploitation
14 octobre 2020
L’ordinateur comporte des périphériques de stockage permanents (disques magnétiques, mémoire flash, etc.).
Pour le stockage et le manipulation des données enregistrées sur ces supports, le système d’exploitation implémente la notion de système de fichiers.
Abstraction selon laquelle (en général), pour le programmeur d’applications
open) : le système d’exploitation fournit au programme d’application un identifiant (file descriptor) qui correspond à un fichier.read, write) des données (un certain nombre d’octets, à partir de la position courantelseek),flock) pour s’assurer qu’aucun autre processus n’y accès en même temps,close) : mettre fin à cette correspondance.unlink) un fichierrename)symlink) ou matériel (link) sur un fichier existantopendir, etc.).stat, …),chmod)Programme en C (sous UNIX) qui montre ce qu’il y a dans le répertoire courant. Une barre de fraction est ajoutée après les noms de répertoires.
#include <dirent.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <assert.h>
int main()
{
DIR* dir = opendir(".");
assert(dir != NULL);
while (true) {
struct dirent* entry = readdir(dir);
if (entry == NULL) break;
printf("%s", entry->d_name);
// si c'est un répertoire, afficher un / à la fin
struct stat entry_stat;
int r = stat(entry->d_name, &entry_stat);
assert(r == 0);
if ((entry_stat.st_mode & S_IFMT) == S_IFDIR) {
printf("/");
}
printf("\t");
}
printf("\n");
return 0;
}Note : le traitement des erreurs est sommaire. La macro assert arrête le programme si la condition est fausse.
Exemple d’exécution
$ ./dir
dir .vscode/ dir.c Makefile ../ ./ Dit “disque dur” (Hard disk)
Quand le disque est en fonction, il tourne constamment (3600-15000 tours/minute). Pour une position donnée du bras, la tête de lecture parcourt donc (relativement) une piste circulaire découpée en secteurs (angulaires) sur lesquels sont enregistrés des blocs d’octets (typiquement 4K octets).
Un bloc est repéré par
Pour accéder à un bloc, il faut
En réalité, l’axe d’unité de disque modernes entraîne plusieurs plateaux, et le bras mobile porte une tête pour chaque face.
Les blocs décrits pour un position du bras s’appellent un cylindre.
Le temps d’accès est donc lié à des facteurs mécaniques. Il peut donc varier considérablement, selon qu’on doit ou non changer de piste/cylindre, et qu’on lit/écrit plusieurs blocs d’une piste consécutivement.
Quand un programme traite un fichier, il est assez probable qu’il le fasse séquentiellement. Pour ces raisons, un système d’exploitation essaiera (principe de localité) de “loger” les blocs d’un même fichier dans une même région du disque (avec des numéros de blocs voisins), pour éviter d’avoir à bouger le bras qui porte la tête de lecture.
Quand un programme demande à lire un bloc, on en profitera pour lire d’autres blocs du même cylindre, que l’on stockera dans des tampons mémoire , au cas où on en aura besoin ensuite (lectures anticipées).
Le temps d’accès moyen, de nos jours, est de l’ordre de 10 ms, soit environ 100 IOPS (Input-Output operations Per Second). Le débit est de l’ordre de 260 Mo/s.1
Prix grand public 2020 : environ 50 € pour 2 To. 500 € pour 12 To.
Technologie complètement différente, utilise des mémoires à semi-conducteurs.
L’élément de base est une cellule qui mémorise (comme un condensateur) un niveau de tension, et peut représenter quelques bits (1 à 4 ?).
Une page regroupe des cellules, avec une capacité typique de 512, 2048 ou 4096 octets. Les pages sont regroupées en blocs2 de 32-128 pages. Un circuit mémoire contient des blocs etc.
Les opérations de lecture/écriture se font par page. Mais l’écriture ne peut se faire que dans une page qui a été préalablement effacée, et l’effacement se fait par bloc complet.3
La vitesse de lecture/écriture est bien plus élevée (jusqu’à 3 Go/s) et le temps de latence beaucoup plus court, qui ne dépend pas de la localité des données. Il faut noter aussi que le nombre d’écritures par cellule est limité, ce qui réduit la durée de vie.
Les problématiques de gestion sont donc très différentes de celles des disques durs. On essaie de répartir l’usure sur les différents blocs de pages, en minimisant le nombre d’effacements. On tient donc une comptabilité des pages occupées, libres (effacées) et périmées (que l’on peut effacées) et défectueuses.
Avantages :
Inconvénients par rapport au disque magnétique :
Contexte : plusieurs processus demandent au système d’exploitation de faire des requêtes d’entrées-sorties sur un disque. L’unité de disque ne peut en traiter qu’une à la fois.
Le système d’exploitation a donc un stock de requête à faire traiter par le disque. Unestratégie d’ordonnancement indique comment choisir la prochaine requête à exécuter.
Dans le cas des disques magnétiques, la durée d’exécution d’une requête dépend fortement de la distance à parcourir par le bras qui porte les têtes de lectures. Plusieurs stratégies sont présentées ci-dessous.
Plusieurs critères pour juger d’une stratégie
Consiste à exécuter les requêtes dans l’ordre où elles sont arrivées.
Exemple : 4 processus A, B, C, D qui lisent des données sur disque. A demandera des blocs consécutifs à partir de la piste 0, B à partir de la piste 100, C à partir de 10, D à partir de 110.
En les traitant dans cet ordre on aura des déplacements de tête de la piste 0 à 100 puis 10 puis 110, puis 1, 101, 11, 111, etc.
C’est une stratégie équitable, mais peu performante, le temps de déplacement du bras étant proportionnel au nombre de pistes traversées.
Pour minimiser les mouvement du bras, une idée est de choisir la requête qui demandera le moins de déplacement. Après avoir lu la piste 0, on choisira la requête concernant la piste 10, qui est la plus proche.
Mais si, pendant cette lecture, le processus A a eu le temps d’émettre une autre requête, on reviendra à la piste 1. Puis 11, 2, 12, 3, etc. : les requêtes des processus C et D sont remises à plus tard, parce qu’elles sont “trop loin”.
Cette stratégie est donc plus performante en nombre d’entrées-sorties, mais moins équitable.
Dans cette stratégie, on traite les requêtes dans une direction (numéros de pistes montants, ou descendants), puis on change de direction, à la manière d’un ascenseur qui “ramasse” les passagers en montant, puis en descendant.
En partant de la piste 0, on passe à 10, puis 100, puis 110. On change alors de direction : 101, 21, 1. On change encore : 22, 102, 202, etc.
Ainsi on a un compromis qui réduit le nombre de mouvements du bras, tout en garantissant une certaine équitabilité.
Dans cette stratégie, on fixe un délai après lequel une requête est considérée comme devenue urgente4.
On choisit alors
Interopérabilité des matériels, Communication uniformisée avec l’ordinateur, standards SATA, SCSI, …
L’unité de stockage comporte (en plus du dispositif matériel) un contrôleur avec une interface hôte, de la mémoire RAM (pour les tampons) et l’électronique de commande.
L’électronique de commande peut assurer des fonctions qui étaient autrefois prises en charge par le système d’exploitation (gestion des blocs défectueux, lectures anticipées, tampons, …), et qui sont donc décentralisées dans l’unité de disque.
Nécessité d’avoir un standard pour interconnecter des matériels de constructeurs différents.
https://en.wikipedia.org/wiki/List_of_interface_bit_rates
| techno | année | type | débit |
|---|---|---|---|
| PATA | 1986 | parallèle (16 bits) | 8.3 MB/s |
| ATA 7 / UDMA 133 | 2002 | 133 MB/s | |
| SATA 1.0 | 2003 | série | 150 MB/s |
| SATA 2.0 | 2004 | 300 MB/s | |
| SATA 3.0 | 2008 | 600 MB/s | |
| SCSI-1 | 1986 | parallèle (8 bits) | 5 MB/s |
| Fast SCSI | 1994 | parallèle (16 bits) | 10 MB/s |
| Ultra 640 SCSI | 2003 | parallèle (16 bits) | 640 MB/s |
| SAS-1 | 2004 | série | 300 MB/s |
| SAS-4 | 2017 | 2.4 GB/s |
Le débit indiqué concerne la vitesse de communication entre le contrôleur et la machine hôte, qui peut être bien supérieure au débit de lecture/écriture sur disque.
Chacune de ces normes contient des commandes, pour
Définition : Une mémoire cache ou antémémoire est une mémoire qui enregistre temporairement des copies de données provenant d’une source, afin de diminuer la durée d’un accès ultérieur (en lecture) à ces données.
La mémoire vive du contrôleur a plusieurs usages : mémoire tampon pour les écritures, et mémoire cache pour les lectures.
La mémoire tampon améliore nettement les performances. Mais elle est en quantité limitée5, le contrôleur la gère avec des algorithmes d’éviction (similarité avec la mémoire virtuelle).
Les fabricants proposent divers compromis prix/performance/capacité. Depuis 2007, on trouve dans le commerce des unités de stockage hybrides, avec trois niveaux
Le contrôleur fait en sorte que la mémoire flash contienne une copie des blocs les plus fréquemment utilisés. Il assure la synchronisation avec ces trois supports, et l’interface avec le système hôte.
L’intérêt est de regrouper ces deux types de stockage (SSD rapide, HD avec grande capacité) dans une seule unité physique, ce qui a un intérêt pour les portables où il n’y a de place que pour une unité (et où les disques durs à 5400 t/mn sont relativement lents).
Exemple : grand public pour environ 60 € (2020), Disque dur hybride Seagate FireCuda SSHD 500 Go (ST500LX025) Disque dur 2.5" 500 Go (5400 t/mn), 8 Go NAND, 128 Mo Mémoire.
En réalité cette technologie a connu un succès relatif, à cause de l’évolution des prix des composants : on trouve des unités SSD de même capacité pour quasiment le même prix, et de performances bien supérieures.
Dans cette partie on regarde les techniques employées pour virtualiser le stockage, c’est-à-dire simuler un “disque virtuel” qui soit
(pas forcément les 3 à la fois !) , à partir de plusieurs disques physiques.
Depuis 1987, c’est ce qu’on appelle les technologies RAID (Redundant Array of Independant Disks).
À partir de plusieurs disques D1, D2, … (on parle de “grappe de disques”) on forme un disque virtuel DV plus gros en considérant
Par exemple, avec un disque de 2 To et un autre de 1 To, on aura un disque virtuel de 3 To.
Évaluation :
Objectif : mieux répartir la charge.
On utilise des disques de même taille. Chaque disque est considéré comme une succession de “bandes” (strips)6. Le disque virtuel est constitué des premières bandes des disques, puis des secondes etc.
| D1 | D2 | D3 |
|---|---|---|
| b1 | b2 | b3 |
| b4 | b5 | b6 |
| b7 | b8 | b9 |
| … | … | … |
Évaluation
Objectif : une redondance par duplication des données.
On utilise (au moins) deux disques de même taille. Chaque disque contient une copie des informations.
| D1 | D2 | D3 |
|---|---|---|
| b1 | b1 | b1 |
| b2 | b2 | b2 |
| b3 | b3 | b3 |
| … | … | … |
Fonctionnement
Évaluation
Exercice : soit des disques ayant 5% de chances de tomber en panne dans l’année qui vient. Quelle est la probabilité de perdre ses données avec un système RAID 0 à 2 disques ? À 3 disques ? (On suppose des pannes indépendants).
Panne : Lorsqu’un système RAID détecte des anomalies sur un disque, le disque est mis hors service, et une notification est envoyée à l’administrateur de le remplacer. Pendant ce temps, le travail peut continuer, avec un disque en moins, et des conditions dégradées.
Remplacement : Quand l’administrateur remplace le disque défaillant, le contrôleur RAID “reconstruit” automatiquement le contenu de ce disque à partir des données qui sont sur les autres, et le remet en fonction.
Spare disks: dans les matériels professionnels, une “baie de disques RAID” contient aussi des disques de rechange, qui sont immédiatement mis en service dès qu’un disque tombe en panne. Ceci minimise la durée de fonctionnement en mode dégradé. Le rôle de l’administrateur est alors de remplacer dès que possible les disques défectueux par des disques neufs.
Objectif : redondance sans duplication.
Parité et détection d’erreur : Si on transmet un octet (ex 01101101), 1 bit supplémentaire permet de contrôler que la transmission s’est faite correctement. Par exemple, on peut convenir qu’il y aura en tout un nombre pair de bits à 1. On adjoindra donc un 17, et on transmettra 011011011.
À la réception, on détectera un problème si, parmi les 9 bits reçus, ceux qui sont à 1 sont en nombre impair.
Parité et correction : ce bit de parité permet aussi de corriger un bit manquant. Si on reçoit 01101x011, il est facile de voir que le bit x doit être à 1. On reconstitue l’information manquante.
C’est parce qu’avec un système de parité paire, le “ou exclusif” de tous les bits (y compris bit de parité) vaut 0. Et donc, la valeur d’un bit est le ou-exclusif de tous les autres.
Application au RAID Dans un système RAID 4 à 4 disques par exemple, on constituera une agrégation par blocs de 3 disques, et le dernier disque contiendra le ou-exclusif des bandes de même niveau. En cas de panne d’un disque, on pourra reconstituer son contenu.
Fonctionnement
Évaluation
C’est une variation du RAID 4, pour éviter le goulet d’étranglement que constitue un disque dédié à la parité.
Les blocs de parité sont répartis sur les disques.
| D1 | D2 | D3 | D4 |
|---|---|---|---|
| b1 | b2 | b3 | p(b1,b2,b3) |
| b4 | b5 | p(b4,b5,b6) | b6 |
| b7 | p(b7,b8,b9) | b8 | b9 |
| p(b10,b11,b12) | b10 | b11 | b12 |
| b13 | b14 | b15 | p(b12,b14,b15) |
| … |
Pour améliorer à la fois les performances et la capacité, on réalise des combinaisons :
Par exemple, le RAID 5+1 (ou 51) consiste à utiliser plusieurs systèmes RAID 5, montés en “miroir” RAID 1.
Ceci utilise évidemment beaucoup de disques, mais la sécurité a un coût.
Exercice
Avant les ordinateurs, le terme système de fichiers désignait une méthode pour stocker et retrouver des documents en papier. Au début des années 60, il s’est étendu au stockage informatisé.
Définition : Un système de fichiers (File System) est une façon de stocker les informations et de les organiser dans des fichiers sur des mémoires secondaires (disque dur, CD-ROM, etc)
Il offre à l’utilisateur une vue abstraite sur ses données (fichiers, répertoires, …) et permet de les localiser à partir d’un chemin d’accès.
Un système de fichiers comporte au moins deux couches
open(), read(), write(), close() etc.La plupart des périphériques de stockage sont “orientés blocs”. C’est à dire que les informations contenues sur le périphérique sont accessibles par zones de même taille.
Physiquement, les informations sont enregistrées sur des secteurs, habituellement 512 octets (disques), 2Kio (CD et DVD), 4Ki (disques Advanced Format). Dans un secteur on trouve des “données utiles” et des codes correcteurs d’erreur.
Le terme “bloc” est utilisé de façon large. Dans le contexte des périphériques, il peut désigner la taille des informations échangées entre l’ordinateur et le contrôleur du disque, par exemple un bloc de 2Kio correspond à 4 enregistrements consécutifs sur disque. En principe consécutifs, parce que le contrôleur du disque, qui est intelligent, peut utiliser une table de “secteurs de remplacement” pour les zones défectueuses : le disque est alors vu comme une suite numérotée de blocs de 2kio.
Le bloc peut être aussi une unité de taille pour le système de fichiers : par exemple paramétré pour stocker les fichiers dans des zones d’une taille multiple de 4kio (qui correspondront à 2 blocs du disque, soit 8 secteurs).
Un extent (ou domaine) est une zone de stockage contiguë réservée pour un fichier sur le système de fichiers d’un ordinateur.
En allouant un extent à un fichier, les écritures qui suivent se font à proximité les unes des autres, ce qui limite la fragmentation qui est un problème pour les supports magnétiques dont le temps d’accès n’est pas uniforme.
http://www.informit.com/articles/article.aspx?p=25878&seqNum=3
CP/M est un système d’exploitation du début des 80’s. Équipement typique : processeur 8 bits Intel 8080, 4Kio de RAM et un lecteur de disquette 8 pouces de capacité 160 Kio.
Le système de fichiers contient un seul répertoire (mais qui aurait besoin de plusieurs répertoires, sur 160 Ko ?), une table avec des éléments de 32 octets. Les fichiers sont alloués par blocs de 1ko (8 secteurs physiques de 128 octets).
Quand la disquette est “montée” , le système d’exploitation lit le répertoire et calcule une table des blocs occupés (160 bits) qui tient sur 23 octets.
Pour chaque entrée de la table on a (dans le désordre)
Pour les fichiers de taille supérieure à 16Ko, il y a plusieurs entrées dans le répertoire, qui donnent donc les 16 premiers blocs, puis les 16 suivants, etc. Un champ supplémentaire indique l’ordre des entrées d’un même fichier.
Système de fichiers conçu pour les disquettes en 1977 par par Bill Gates et Marc McDonald, utilisé dans QDOS, MS-DOS, et Windows jusqu’à Windows 9x. Trois variantes : FAT12, FAT16 et FAT32. Windows repose maintenant sur NTFS mais reconnaît toujours FAT. De nombreux appareils électroniques (appareils photos, téléphones, etc) l’utilisent.
Voir https://fr.wikipedia.org/wiki/File_Allocation_Table
Un disque FAT contient essentiellement
Un répertoire est une table qui contient, pour chacun de ses éléments (fichier ou répertoire) :
Les blocs sont des “clusters” (groupes de secteurs) dont la taille est choisie au formattage.
Pour des raisons de sécurité, la FAT est dupliquée.
Les versions :
New Technology FileSystem, développé par Microsoft Corporation pour Windows NT.
Apporte de nombreuses améliorations techniques par rapport à la FAT
Voir par exemple https://fr.wikipedia.org/wiki/NTFS_(Microsoft)
Ne pas confondre avec la vitesse de transfert (SATA, SCSI, …) entre le contrôleur du disque et la carte mère.↩
Attention aux conflits de terminologie, bloc désigne ici un bloc de pages.↩
Par envoi d’une tension plus élevée qui efface toute une région du circuit.↩
Valeurs typiques sous Linux : 500 ms pour une lecture, 5000 ms pour une écriture.↩
La mémoire vive coûte beaucoup plus cher, au méga-octet, que l’espace sur disque.↩
Typiquement, 16KB à 256KB.↩
On le calcule en faisant le “ou-exclusif” des bits de l’octet.↩