1.

Introduction
INTRODUCTION aux SYSTEMES et
RESEAUX (FLIN302) Définition d’un SE
Couche logicielle offrant une interface entre la machine
Michel MEYNARD matérielle et les utilisateurs.

Objectifs
- convivialité de l'interface (GUI/CUI);
- clarté et généricité des concepts (arborescence de répertoires
PLAN et fichiers, droits des utilisateurs, ...);
- efficacité de l'allocation des ressources en temps et en espace;
1. Introduction..................................................................... 1
2. Représentation de l’information.................................... 10 Services
3. Structure des ordinateurs............................................... 31 - multiprogrammé (ou multi-tâches) préemptif ;
4. La Couche Machine ...................................................... 57 - multi-utilisateurs ;
5. Librairies et édition de liens en C ................................. 74 - fonctionnalités réseaux (partage de ressources distantes) ;
6. Les Systèmes de Gestion de Fichiers ............................ 76 - communications réseaux (protocoles Internet) ;
7. Conclusion .................................................................. 107 - personnalisable selon l’utilisation (développeur, multimédia,
SGBD, applications de bureau, …)

Bibliographie
Utilisateur 1 u2 prog1
[Tanenbaum 1988] Architecture de l’ordinateur, InterEditions Shell éditeur (appli) compilateur
noyau du SE
[Delacroix 2003] Linux progr. Syst. et réseau, Dunod
matériel (hardware)
[Peterson, Silberschatz 1985]Operating System Concepts,
Addison-Wesley

Systèmes Informatiques Chapitre 1 Introduction 2 Systèmes Informatiques Chapitre 1 Introduction 3

1.1 Historique
solution 1
− regroupement (batch) des opérations de même type;
− A l'origine : machine énorme programmée depuis une − seuls les opérateurs manipulent la console et les périph. ;
console, beaucoup d'opérations manuelles ; − en cas d'erreur, dump mémoire et registres fourni au
− développement de périphériques d'E/S (cartes 80 col., programmeur;
imprimantes, bandes magnétiques), développement logiciel :
assembleur, chargeur, éditeur de liens, librairies, pilotes de
périphérique.
solution 2
− langages évolués (compilés); exemple de job : exécution
d'un prg Fortran; − moniteur résidant en mémoire séquençant les jobs;
− montage manuel de la bande magnétique contenant le − cartes de ctrl ajoutées spécifiant la tâche à accomplir;
compilateur F; − définition d'un langage de commande des jobs (JCL) ancêtre
− lecture du prg depuis le lecteur de cartes 80 col. des shell.
− production du code assembleur sur une bande ;
− montage de la bande contenant l'assembleur;
− assemblage puis édition de lien produisant le binaire sur solution 3
une bande; − améliorer le moniteur pour en faire un SE multiprogrammé !
− chargement et exécution du prog. − stocker le SE sur disque dur et l’amorcer (bootstrap) depuis
un moniteur résidant en ROM (le BIOS) ;

Remarques :
− beaucoup d'interventions manuelles !
− sous-utilisation de l'UC ;
− machine à 2 millions de dollars réservée par créneaux d’1h !
Systèmes Informatiques Chapitre 1 Introduction 4 Systèmes Informatiques Chapitre 1 Introduction 5

1.2.1 Décomposition des SI

1.2 Principe de décomposition
Architecture multi-niveaux (ou couches) niveau 5 Couche des langages d'application
Afin d’améliorer les performances, et en raison des impératifs Traduction (Compilation)
technologiques, le jeu d’instructions des machines réelles est
limité et primitif. On construit donc au-dessus, une série de niveau 4 Couche du langage d'assemblage
couches logicielles permettant à l'homme un dialogue plus Traduction (Assemblage)
aisé. Soft
niveau 3 Couche du Système d'Exploitation
Machine virtuelle Mn Interprètation partielle appels syst.
niveau n
Langage Ln
niveau 2 Couche machine traditionnelle
Interprètation (microprogramme)

Machine virtuelle M3 Couche microprogrammée Hard

niveau 3 niveau 1
Langage L3 Execution par le matériel
Machine virtuelle M2 Couche physique
niveau 2 niveau 0
Langage L2
niveaux composant (électronique) puis atomique (physique solide)
Machine virtuelle M1
niveau 1
Langage L1 Vocabulaire : niveau ou langage ou machine

Les programmes en Li sont : • 0 : portes logiques, circuits combinatoires, à mémoire ;

• soit traduits (compilés) en Li-1 ou Li-2 ou … L1, • 1 : une instruction machine (code binaire) interprétée par son
microprogramme ;
• soit interprétés par un interpréteur tournant sur Li-1 ou Li-2 • 2 : suite d'instructions machines du jeu d'instructions
ou … L1 • 3 : niveau 2 + ensemble des services offerts par le S.E. (appels systèmes) ;
• 4 : langage d’assemblage symbolique traduit en 3 par le programme
assembleur ;
• 5 : langages évolués (de haut niveau) traduits en 3 par compilateurs ou alors
interprétés par des programmes de niveau 3.

Systèmes Informatiques Chapitre 1 Introduction 6 Systèmes Informatiques Chapitre 1 Introduction 7

1.3 Matériel et Logiciel Exemples de répartition matériel/logiciel

Matériel (Hardware) • premiers ordinateurs : multiplication, division, manip. de

Ensemble des composants mécaniques et électroniques de la chaînes, commutation de processus … par logiciel :
machine : processeur(s), mémoires, périphériques, bus de actuellement descendus au niveau matériel ;
liaison, alimentation… • à l'inverse, l'apparition des processeurs micro-programmés à
fait remonter d'un niveau les instructions machines ;
• les processeurs RISC à jeu d'instructions réduit ont
Logiciel (Software) également favorisé la migration vers le haut ;
Ensemble des programmes, de quelque niveau que ce soit, • machines spécialisées (Lisp, bases de données) ;
exécutables par un ou plusieurs niveaux de l'ordinateur. Un • Conception Assistée par Ordinateur : prototypage de circuits
programme = mot d'un langage. électroniques par logiciel ;
Le logiciel est immatériel même s'il peut être stocké • développement de logiciels destinés à une machine
physiquement sur des supports mémoires. matérielle inexistante par simulation (contrainte économique
fondamentale).
Matériel et Logiciel sont conceptuellement équivalents La frontière entre logiciel et matériel est très mouvante et
dépend fortement de l'évolution technologique (de même pour
les frontières entre niveaux).
Toute opération effectuée par logiciel peut l'être directement
par matériel et toute instruction exécutée par matériel peut être A chaque niveau, le programmeur communique avec une
simulée par logiciel. machine virtuelle sans se soucier des niveaux inférieurs.

Le choix est facteur du coût de réalisation, de la vitesse

d'exécution, de la fiabilité requise, de l'évolution prévue
(maintenance), du délai de réalisation du matériel…
Systèmes Informatiques Chapitre 1 Introduction 8 Systèmes Informatiques Chapitre 1 Introduction 9

1.4 Objectifs du cours 1.5 Processus de compilation des

programmes (C sous Unix) ;
- Comprendre le processus de compilation des programmes
(C sous Unix) ; - Unix développé en C donc interface naturelle avec le SE ;
- Compilation vs interprétation : maîtriser les phases
o Analyse lexicale et syntaxique (parse error ou
- posséder les bases indispensables de la représentation des syntax error) ;
o Analyse sémantique (correspondance de type,
données en machines afin de comprendre l’utilité de déclaration préalable des objets, …) ;
structure de données efficaces ; o Prétraitement des directives de compilation
(#include, #define, #ifdef, …) de chaque fichier ;
o Compilation proprement dite du source C en
- développer des algorithmes simples puis les traduire en un source écrit en langage d’assemblage;
o Assemblage en fichier objet .o ;
langage de programmation (C) ; o Edition des liens des objets entre eux et avec la ou
les bibliothèques pour réaliser le fichier binaire
exécutable ;
- distinguer les appels systèmes Unix des fonctions de la
- Cette succession est souvent réalisée à l’aide d’une unique
bibliothèque C ; commande :
gcc monprog.c –o monprog
- la commande gcc supporte ces principales options :
- appréhender les Entrées/Sorties généralisées et leur lien
-c Compiler et assembler seulement (compile)
avec un Système de Gestion de Fichier ;
-o xxx Renommage du fichier de sortie (output)
-lm Utilisation de la librairie mathématique libm.a
- maîtriser la gestion des fichiers sous Unix ; -Wall Voir tous les avertissements (Warning all)
-g Ajoute les informations de débogage
-E Que le prétraitement
-S Compiler sans assembler
-std=c99 Permet les déf de var dans les for, les //, …

Systèmes Informatiques Chapitre 3 : Représentation de l’information 11

2. Représentation de l’information Poids fort et faible

La longueur des mots étant la plupart du temps paire (n=2p),
2.1 Introduction on parle de demi-mot de poids fort (ou le plus significatif)
pour les p bits de gauche et de demi-mot de poids faible (ou le
moins significatif) pour les p bits de droite.
La technologie passée et actuelle a consacrée les circuits
mémoires (électroniques et magnétiques) permettant de Exemple : mot de 16 bits
stocker des données sous forme binaire. b15 b14 … b8 b7 b6 … b0
octet le plus significatif octet le moins significatif
Remarque : Most Signifant Byte Least Significant Byte
des chercheurs ont étudié et continuent d'étudier des circuits
ternaires et même décimaux…

le bit : Unités multiples

abréviation de binary digit, le bit constitue la plus petite unité Ces mots sont eux-mêmes groupés et on utilise fréquemment
d'information et vaut soit 0, soit 1. les unités multiples de l'octet suivantes :
les bits sont généralement stockés séquentiellement et sont
1 Kilo-octet = 210 octets = 1024 octets noté 1 Ko
conventionnellement numérotés de la façon suivante :
bn-1 bn-2 … b2 b1 b0
1 Méga-octet = 220 octets = 1 048 576 octets noté 1 Mo
1 0 … 0 1 1
1 Giga-octet = 230 octets ≅ 109 octets noté 1 Go
On regroupe ces bits par paquets de n qu'on appelle des
quartets (n=4), des octets (n=8) « byte », ou plus
généralement des mots de n bits « word ». 1 Téra-octet = 240 octets ≅ 1012 octets noté 1 To
Systèmes Informatiques Chapitre 3 : Représentation de l’information 12 Systèmes Informatiques Chapitre 3 : Représentation de l’information 13

2.2 Représentation des entiers positifs 2.2.2 Représentation en base 2p

2.2.1 Représentation en base 2 La représentation d'un entier x en base 2,

bn-1bn-2…b0, est lourde en écriture. Aussi lui préfère-t-on une
représentation plus compacte en base 2p. On obtient cette
Un mot de n bits permet de représenter 2n configurations
représentation en découpant le mot bn-1bn-2…b0 en tranches
différentes. En base 2, ces 2n configurations sont associées
aux entiers positifs x compris dans l'intervalle [0, 2n-1] de la de p bits à partir de la droite (la dernière tranche est complétée
façon suivante : par des 0 à gauche si n n'est pas multiple de p). Chacune des
tranches obtenues est la représentation en base 2 d'un chiffre
x = bn-1 * 2n-1 + bn-2 * 2n-2 + … + b1 * 2 + b0 de x représenté en base 2p.

Ainsi, un quartet permet de représenter l'intervalle [0, 15], un Avec p=3 (représentation octale), on préfixe par un 0
octet [0, 255], un mot de 16 bits [0, 65535]. l’écriture des chiffres octaux : 0377=255.

Exemples : Avec p=4 (représentation hexadécimale), les valeurs 10 à 15

00…0 représente 0 sont représentées par les symboles A à F. On préfixe par un 0x
000…001 représente 1 l’écriture des chiffres hexadécimaux : 0xFF=255.
0000 0111 représente 7 (4+2+1)
0110 0000 représente 96 (64+32) Exemples :
1111 1110 représente 254 (128+64+32+16+8+4+2) x=200 et n=8
0000 0001 0000 0001 représente 257 (256+1) en binaire : 11 001 000 (128+64+8)
100…00 représente 2n-1 en octal : 3 1 0 (3*64+8) : 0310
111…11 représente 2n-1 en hexadécimal : C 8 (12*16+8) : 0xC8

Par la suite, cette convention sera notée Représentation

Binaire Non Signée (RBNS).

Systèmes Informatiques Chapitre 3 : Représentation de l’information 14 Systèmes Informatiques Chapitre 3 : Représentation de l’information 15

2.3.2 Le complément à 1 (C1)

2.3 Représentation des entiers relatifs
(ou complément restreint)
Quatre façons d'utiliser les nombres négatifs en machine ont
été employées. Actuellement et en pratique, la méthode du Dans cette représentation, les entiers positifs sont en RBNS
« complément à 2 » est la plus utilisée. tandis qu'un négatif -|x| est obtenu par inversion de tous les
bits de la RBNS de |x|. Ici encore, le bit de poids n-1 indique
2.3.1 La valeur absolue signée le signe (0 → positif, 1 → négatif).

Intervalle de définition : [-2n-1+1, 2n-1-1]

Dans cette représentation, le bit de poids n-1 indique le signe
(0 → positif, 1 → négatif) tandis que les bits n-2 ... 0 Exemples sur un octet :
représentent la valeur absolue de l'entier négatif dans la 3 0000 0011 -3 1111 1100
Représentation Binaire Non Signée (RBNS). 127 0111 1111 -127 1000 0000
0 0000 0000 0 1111 1111
Intervalle de définition : [-2n-1+1, 2n-1-1]
Inconvénients :
Exemples sur un octet : • 2 représentations distinctes de 0
3 0000 0011 -3 1000 0011 • opérations arithmétiques peu aisées : 3 + -3 = 0 (1111 1111)
127 0111 1111 -127 1111 1111 mais 4 + -3 = 0 (00…0) !
0 0000 0000 -0 1000 0000
Le second problème est résolu si l'on ajoute 1 lorsqu'on
Inconvénients : additionne un positif et un négatif :
2 représentations distinctes de 0 3+1+ -3=0 (00…0) et 4 +1+ -3=1 (00…01)
opérations arithmétiques peu aisées :
3 + -3 = -6 ! D'où l'idée de la représentation en Complément à 2.
Systèmes Informatiques Chapitre 3 : Représentation de l’information 16 Systèmes Informatiques Chapitre 3 : Représentation de l’information 17

2.3.3 Le complément à 2 (C2) Dépassement de capacité en C2

127+127=-2 : 0111 1111+0111 1111=(0) 1111 1110

En C2 les entiers positifs sont en RBNS tandis que les négatifs
-128+-128=0 : 1000 0000+1000 0000=(1) 0000 0000
sont obtenus par inversion de leur valeur absolue (C1) puis
-127+-128=1 : 1000 0001+1000 0000=(1) 0000 0001
addition binaire de 1. Ici encore, le bit de poids n-1 indique le
signe (0 → positif, 1 → négatif). Lors de la 1° addition, la somme de deux grands positifs
Une autre façon d'obtenir le C2 d'un entier relatif x consiste à aboutit à un résultat négatif (retenue entrante sur le bit 7) et le
écrire la RBNS de la somme de x et de 2n. Carry n'est pas positionné (pas de retenue sortante du bit 7).
Dans les deux autres exemples, la somme de deux grands
Intervalle de définition : [-2n-1, 2n-1-1] négatifs donne un positif (retenue sortante du bit 7, Carry=1,
mais pas de retenue entrante).
Exemples sur un octet [-128, +127] :
3 0000 0011 -3 1111 1101 La condition pour qu'une addition de deux entiers relatifs
127 0111 1111 -127 1000 0001 en C2 sur n bits soit correcte est que les retenues entrante
0 0000 0000 -128 1000 0000 et sortantes du bit n-1 soient identiques.
Inconvénient : La plupart des processeurs possèdent un indicateur
• Intervalle des négatifs non symétrique des positifs ; d'Overflow (dépassement de capacité) dans leur registre d'état
• Le C2 de -128 est -128 ! qui permet au programmeur de tester l'incorrection d'une
opération en C2.
Avantage fondamental :
• l'addition binaire fonctionne correctement ! Overflow = Carry XOR Retenuen-2 → n-1
-3+3=0 : 1111 1101+0000 0011=(1) 0000 0000
-3 + -3 = -6 : 1111 1101+1111 1101=(1) 1111 1010 Remarquons que l'addition d'un positif et d'un négatif ne peut
jamais donner lieu à overflow.
Remarquons ici que le positionnement du Carry à 1 n'indique
pas un dépassement de capacité !

Systèmes Informatiques Chapitre 3 : Représentation de l’information 18 Systèmes Informatiques Chapitre 3 : Représentation de l’information 19

2.3.4 L'excédent à 2n-1 2.3.5 Opérations en RBNS et C2

Dans cette représentation, l'ensemble des nombres Le C2 étant la représentation la plus utilisée, nous allons
représentables est le même qu'en C2. Tout nombre x de cet étudier les opérations arithmétiques en non signé et en C2.
ensemble est représenté par x+2n-1 en RBNS. Attention, le bit
de poids n-1 indique le signe (0 → négatif, 1 → positif). [Link] Addition

L'excédent à 2n-1 se déduit du C2 en inversant le bit de signe ! Rappelons qu'en RBNS et en C2, l'addition binaire (ADD
réalisée par toutes les UAL de processeur) donne un résultat
Intervalle de définition : [-2n-1, 2n-1-1] cohérent tant que celui-ci reste dans l'intervalle représenté ([0,
2n-1] et [-2n-1, 2n-1-1])
Exemples sur un octet : En RBNS, le dépassement de capacité est signalé par le
3 1000 0011 -3 0111 1101 positionnement à 1 du Carry tandis qu'en C2, c'est l'indicateur
127 1111 1111 -127 0000 0001 d'Overflow qui est mis à 1.
0 1000 0000 -128 0000 0000
[Link] Soustraction
Avantage :
représentation uniforme des entiers relatifs La soustraction x-y pourrait être réalisée par inversion du
signe de y puis addition avec x (sauf pour -128). L'inversion
Inconvénients : de signe (en C2) est généralement fournie par le matériel
représentation des positifs différente de la RBNS (NEG).
opérations arithmétiques peu aisées 3+-3 =-128 !
Exemple : R1 := 5 - 8
R1 := 5; R2 := 8; NEG R2; ADD R1,R2
L'instruction de soustraction SUB est généralement câblée par
le matériel.
Systèmes Informatiques Chapitre 3 : Représentation de l’information 20 Systèmes Informatiques Chapitre 3 : Représentation de l’information 21

[Link] Multiplication et Division

La multiplication x*y peut être réalisée par y additions 2.4 Représentation des décimaux
successives de x tandis que la division peut être obtenue par
soustractions successives et incrémentation d'un compteur tant On s'intéresse ici à la catégorie des nombres décimaux, D, et
que le dividende est supérieur à 0 (pas efficace). non pas des réels, R. Les types de données real sont
trompeurs : la précision est toujours limitée !
Cependant, la plupart des processeurs fournissent des
instructions MUL et DIV directement câblées et efficaces. 2.4.1 Décimal Codé Binaire BCD
Cas particulier Utilisé principalement en comptabilité pour sa précision, ce
Lorsqu'une multiplication ou une division a comme opérande codage utilise un quartet pour chaque chiffre décimal :
2n, on peut la simuler par décalage (Shift) à gauche ou à droite 0 → 0000; 1 → 0001; 2 → 0010; …; 9 → 1001
de n positions de l'autre opérande.
Les quartets de code hexa 0xA à 0xF sont inutilisés. Chaque
Exemples : octet permet donc de stocker 100 combinaisons différentes
13*8 : 0000 1101 décalé 3 fois à gauche : représentant les entiers de 0 à 99.
0110 1000 c’est-à-dire 104 ;
126/16 : 0111 1110 décalé 4 fois à droite : Les opérations de l'arithmétique binaire sur ces entiers
0000 0111 c’est-à-dire 7. provoque des incohérences de représentation dans certaines
situations :
En C2, il faut également réintroduire le bit de signe lors du 33+58 : 0011 0011 + 0101 1000 = 1000 1011 =0x8B
décalage. Des instructions de décalage arithmétique sont
généralement fournies par le processeur. Aussi, les processeurs possèdent des instructions spécialisées
d'ajustement des résultats à exécuter à la suite d'opérations
binaires sur des opérandes DCB. Ici, il faut rajouter 0x6 au
résultat !

Systèmes Informatiques Chapitre 3 : Représentation de l’information 22 Systèmes Informatiques Chapitre 3 : Représentation de l’information 23

2.4.2 Virgule flottante Remarques :

• 20 = 1 ≤ m < 21 = 2
On exprime généralement les nombres décimaux à l'aide de la • Les puissances négatives de 2 sont : 0,5; 0,25; 0,125;
notation scientifique en virgule flottante : 0,0625; 0,03125; 0,015625; 0,0078125; …
• La plupart des nombres à partie décimale finie n'ont pas de
représentation binaire finie : (0,1; 0,2; …).
• Par contre, tous les nombres finis en virgule flottante en
x=m*be base 2 s'expriment de façon finie en décimal car 10 est
multiple de 2.
où m est la mantisse, b la base et e l'exposant. • Réfléchir à la représentation en base 3.

Il faut bien comprendre que cette représentation binaire en virgule

Exemple : flottante, quel que soit le nombre de bits de mantisse et d'exposant, ne fait
pi = 0,0314159*102 = 31,4159*10-1=3,14159 qu'approcher la plupart des nombres décimaux. Et cela, avant
quelqu'opération que ce soit !
Il existe une représentation normalisée de la mantisse
consistant à positionner un seul chiffre différent de 0 à gauche Algorithme de conversion de la partie décimale
de la virgule et tous les autres à droite de la virgule. On On applique à la partie décimale des multiplications
obtient ainsi : successives par 2, et on range, à chaque itération, la partie
b0 ≤ m < b1. entière du produit dans le résultat.

Exemple : Exemples :
pi = 3,14159*100 0,375 à coder en binaire virgule flottante
0,375*2=0,75*2=1,5; 0,5*2=1,0 → 0,011
On a la même forme de représentation en virgule flottante à
mantisse normalisée pour le binaire (b=2) 0,23*2=0,46*2=0,92*2=1,84*2=1,68*2=1,36*2=0,72*2=1,44
*2=0,88……
Exemple : 7,2510 → 111,012 → 1,1101*22 0,2310 sur 8 bits de mantisse : 0,00111010
4+2+1+0,25=(1+0,5+0,25+0,0625)*4
Systèmes Informatiques Chapitre 3 : Représentation de l’information 24 Systèmes Informatiques Chapitre 3 : Représentation de l’information 25

2.4.3 Virgule Flottante en machine Exemple :

-5,25 = -101,01 = -1,0101 22
représenté par : 1 1000 0001 0101 000...
Standardisation :
c’est-à-dire : 0x C0 A8 00 00
− portabilité entre machines, langages
− reproductibilité des calculs et « exactitude » Attention, certains codes spéciaux servent à représenter des
− communication de données via les réseaux nombres exceptionnels !
− représentation de nombres spéciaux − 0 : e=0x0 et m=0x0 (s donne le signe)
− procédures d’arrondi − infini : e=0xFF et m=0x0 (s donne le signe)
− NaN (Not a Number) : e=0xFF et m qcq
− dénormalisés : e=0x0 et m≠0x0 ; dans ce cas, il n’y a plus
La norme IEEE-754 (1985) de bit caché et la mantisse doit être décalée d’un cran à
− simple précision sur 32 bits (float) gauche : très petits nombres (de 2-149=1.4 10-45 à 2-126-2-
− double précision sur 64 bits (double) 149
=1.18 10-38)

En normalisé :
Norme IEEE-754 flottants en simple précision Plus grande valeur absolue représentable
− signe : 1 bit (0 : +, 1 : -) MAX = 2127 * (2-2-23) ≈ 3.4 1038
− exposant : 8 bits en excédent 127 [-127, 128] PAS = 2127 * 2-23 ≈ 2.03 1031
− mantisse : 23 bits en RBNS ; normalisé sans représentation soit 7 chiffres significatifs
du 1 de gauche ! La mantisse est arrondie !

soit 4 octets ordonnés : signe, exposant, mantisse. Plus petite valeur absolue représentable (sauf 0)
MIN = 2-126 * (1) ≈ 1.18 10-38
Valeur d’un float : (-1)s * 2(e-127) * 1,m PAS = 2-126 * 2-23 ≈ 1.4 10-45
soit 7 chiffres significatifs
Exemple : Quelques règles de calcul
33,0 = +100001,0 = +1,00001 25
représenté par : 0 1000 0100 0000 100... -0=+0 ; 1/+0=+∞ ; 1/-0=-∞ ; x/∞=0 ;
c’est-à-dire : 0x 42 04 00 00 NaN=∞/∞= 0/0=(-|x|)1/n ; x+∞=∞
règles d’arrondi extrêmement complexes ...

Systèmes Informatiques Chapitre 3 : Représentation de l’information 26 Systèmes Informatiques Chapitre 3 : Représentation de l’information 27

Remarques : 2.5 Représentation des caractères

Il existe, entre deux nombres représentables, un intervalle de
Symboles
réels non exprimables. La taille de ces intervalles (pas) croît
avec la valeur absolue : − alphabétiques,
− numériques,
proche et ≠ 0 : 2-149=1.4 10-45 − de ponctuation et autres (semi-graphiques, ctrl)
proche de ∞ : 2124=2.03 1031
Utilisation
− entrées/sorties
Cependant, si l'on exprime la distance entre un nombre et son
− représentation externe (humaine) des programmes (sources)
"successeur" en pourcentage de ce nombre, ce pourcentage
et données y compris les données numériques
reste constant :

2-149/2-126 = 2-23 ≈ 1,19 10-7 ≈ 2104/2127 = 2-23 Code ou jeu de car.

Ensemble de caractères associés aux mots binaires les
Ainsi l'erreur relative due à l'arrondi de représentation est représentant. La quasi-totalité des codes ont une taille fixe (7
approximativement la même pour les petits nombres et les ou 8 ou 16 bits) afin de faciliter les recherches dans les
grands ! mémoires machines.

− ASCII (7) ;
Le nombre de chiffres décimaux significatifs varie en fonction
du nombre de bits de mantisse, tandis que l’étendue de − EBCDIC (8) ;
l’intervalle représenté varie avec le nombre de bits − ISO 8859-1 ou ISO Latin-1 (8)
d’exposant : − UniCode (16).
− UTF-8 (8-32)

double
− 1 bit de signe
− 11 bits d’exposant
− 52 bits de mantisse (16 chiffres significatifs)
Systèmes Informatiques Chapitre 3 : Représentation de l’information 28 Systèmes Informatiques Chapitre 3 : Représentation de l’information 29

2.5.1 Jeux de caractères ASCII

Hexa MSD 0 1 2 3 4 5 6 7
Code ASCII LSD Bin. 000 001 010 011 100 101 110 111
American Standard Code for Information Interchange
0 0000 NUL DLE espace 0 @ P ‘ p
Ce très universel code à 7 bits fournit 128 caractères (0..127) 1 0001 SOH DC1 ! 1 A Q a q
2 0010 STX DC2 " 2 B R b r
divisé en 2 parties : 32 caractères de fonction (de contrôle) 3 0011 ETX DC3 # 3 C S c s
permettant de commander les périphériques (0..31) et 96 4 0100 EOT DC4 $ 4 D T d t
caractères imprimables (32..127). 5 0101 ENQ NAK % 5 E U e u
6 0110 ACK SYN & 6 F V f v
Codes de contrôle importants : 7 0111 BEL ETB ' 7 G W g w
0 Null <CTRL> <@>; 3 End Of Text <CTRL> <c>; 8 1000 BS CAN ( 8 H X h x
4 End Of Transmission <CTRL> <d>; 7 Bell 9 1001 HT EM ) 9 I Y i y
8 Backspace 10 Line Feed 12 Form Feed A 1010 LF SUB * : J Z j z
13 Carriage Return 27 Escape <CTRL> <z> B 1011 VT ESC + ; K [ k {
C 1100 FF FS , < L \ l |
Codes imprimables importants : D 1101 CR GS - = M ] m }
20H Espace; 30H..39H "0".."9"; 41H..5AH "A".."Z" E 1110 SO RS . > N ^ n ~
61H..7AH "a".."z" F 1111 SI US / ? O _ o DEL

Le code ASCII est normalisé par le CCITT (Comité

Consultatif International Télégraphique et Téléphonique) qui a
prévu certaines variantes nationales : {} aux USA donnent éè ISO-8859-1
en France …
Hexa LSD
La plupart du temps, l'unité mémoire étant l'octet, le 8° bit est MSD 0 1 2 3 4 5 6 7 8 9 A B C D E F
utilisé : C À Á Â Ã Ä Å Æ Ç È É Ê Ë Ì Í Î Ï
• soit pour détecter les erreurs de transmission (bit de parité) D Ð Ñ Ò Ó Ô Õ Ö × Ø Ù Ú Û Ü Ý Þ ß
• soit pour définir des caractères spéciaux (semi-graphiques, E à á â ã ä å æ ç è é ê ë ì í î ï
accents) dans un code ASCII "étendu". F ð ñ ò ó ô õ ö ÷ ø ù ú û ü ý þ ÿ

Systèmes Informatiques Chapitre 4 : La Couche Machine 31

Codage UTF-8 3. Structure des ordinateurs

UTF-8 (UCS transformation format 8 bits) est un format de Le modèle d'architecture de la plupart des ordinateurs actuels
codage de caractères défini pour les caractères Unicode provient d'un travail effectué par John Von Neumann en
(UCS). Chaque caractère est codé sur une suite d'un à quatre 1946.
octets. Il a été conçu pour être compatible avec certains
logiciels originellement prévus pour traiter des caractères d'un Le modèle de Von Neumann
seul octet.
L’IETF requiert qu’UTF-8 soit pris en charge par les Unité Centrale Mémoire Centrale Périphériques
protocoles de communication d’Internet échangeant du texte. Unité de Commande

Les caractères de numéro 0 à 127 (ASCII) sont codés sur un Unité Arith. et Log.
octet dont le bit de poids fort est toujours nul. Registres
Les caractères de numéro supérieur à 127 sont codés sur
plusieurs octets. Dans ce cas, les bits de poids fort du premier
octet forment une suite de 1 de longueur égale au nombre
d'octets utilisés pour coder le caractère, les octets suivants
Bus (données, adresses, contrôle)
ayant 10 comme bits de poids fort.
Définition du nombre d'octets utilisés Principes du modèle de programmation :
Représentation binaire Signification - code = séquence d'instructions en MC ;
- données stockées en MC ;
0xxxxxxx 1 octet codant 1 à 7 bits
110xxxxx 10xxxxxx 2 octets codant 8 à 11 bits Actuellement, d'autres types d'architecture (5° génération,
1110xxxx 10xxxxxx 10xxxxxx 3 octets codant 12 à 16 bits machines systoliques, …) utilisant massivement le
11110xxx 10xxxxxx 10xxxxxx parallélisme permettent d'améliorer notablement la vitesse
10xxxxxx 4 octets codant 17 à 21 bits
des calculs.
Exemples de codage UTF-8
Numéro du Codage binaire On peut conjecturer que dans l'avenir, d'autres paradigmes de
Caractère programmation spécifiques à certaines applications induiront
caractère UTF-8
de nouvelles architectures.
A 65 01000001

é 233 11000011 10101001

11100010 10000010
€ 8364 10101100
Systèmes Informatiques Chapitre 4 : La Couche Machine 32 Systèmes Informatiques Chapitre 4 : La Couche Machine 33

3.1 L' Unité Centrale (UC) L'Unité de Commande

ou processeur (Central Processing Unit CPU) Celle-ci exécute l'algorithme suivant :

Cerveau de l'ordinateur, l'UC exécute séquentiellement les répéter

instructions stockées en Mémoire Centrale. Le traitement 1. charger dans RI l'instruction stockée en MC à l'adresse
d'une instruction se décompose en 3 temps : chargement, pointée par le CO;
décodage, exécution. C'est l'unité de commande qui 2. CO:=CO+taille(instruction en RI);
ordonnance l'ensemble, tandis que l'UAL exécute des 3. décoder (RI) en micro-instructions;
opérations telles que l'addition, la rotation, la conjonction…, 4. (localiser en mémoire les données de l'instruction;)
dont les paramètres et résultats sont stockés dans les registres 5. (charger les données;)
(mémoires rapides). 6. exécuter l'instruction (suite de micro-instructions);
7. (stocker les résultats mémoires;)
Les registres jusqu'à l'infini
Certains registres spécialisés jouent un rôle particulièrement
important. Le Compteur Ordinal (CO) Instruction Pointer IP,
Program Counter PC pointe sur la prochaine instruction à exécuter; Lors du démarrage de la machine, CO est initialisé soit à
le Registre Instruction (RI) contient l'instruction en cours d'exécution; l'adresse mémoire 0 soit à l'adresse correspondant à la fin de la
le registre d'état Status Register, Flags, Program Status Word PSW mémoire (2m-1). A cette adresse, se trouve le moniteur en
contient un certain nombre d'indicateurs (ou drapeaux ou bits) mémoire morte qui tente de charger l'amorce "boot-strap" du
permettant de connaître et de contrôler certains états du processeur; Le système d'exploitation.
pointeur de pile Stack Pointer permet de mémoriser l'adresse en MC
du sommet de pile (structure de données Last In First Out LIFO Remarquons que cet algorithme peut parfaitement être simulé
indispensable pour les appels procéduraux); Des registres d'adresse
par un logiciel (interprèteur). Ceci permet de tester des
(index ou bases) permettent de stocker les adresses des données en
mémoire centrale tandis que des registres de travail permettent de processeurs matériels avant même qu'il en soit sorti un
stocker les paramètres et résultats de calculs. prototype, ou bien de simuler une machine X sur une machine
Y (émulation).

Systèmes Informatiques Chapitre 4 : La Couche Machine 34 Systèmes Informatiques Chapitre 4 : La Couche Machine 35

L'Unité Arith. et Log.

Celle-ci exécute des opérations : 3.2 La Mémoire Centrale (MC)
arithmétiques : addition, soustraction, C2, incrémentation,
décrémentation, multiplication, division, décalages La mémoire centrale de l'ordinateur est habituellement
arithmétiques (multiplication ou division par 2n). constituée d'un ensemble ordonné de 2m cellules (cases),
logiques : et, ou, xor, non, rotations et décalages. chaque cellule contenant un mot de n bits. Ces mots
permettent de conserver programmes et données ainsi que la
Selon le processeur, certaines de ces opérations sont présentes pile d'exécution.
ou non. De plus, les opérations arithmétiques existent parfois
pour plusieurs types de nombres (C2, DCB, virgule flottante)
ou bien des opérations d'ajustement permettent de les réaliser. 3.2.1 Accès à la MC
Enfin, les processeurs récents contiennent une Unité La MC est une mémoire électronique et l'on accède à
Arithmétique spécialisée pour les opérations en virgule n'importe laquelle de ses cellules au moyen de son adresse
flottante. Sur d’autres, des co-processeurs arithmétiques comprise dans l'intervalle [0, 2m-1]. Les deux types d'accès à
flottants peuvent être adjoint pour les réaliser. la mémoire sont :
la lecture qui transfère sur le bus de données, le mot contenu
Les opérations arithmétiques et logiques positionnent certains dans la cellule dont l'adresse est située sur le bus d'adresse.
indicateurs d'état du registre PSW. C'est en testant ces l'écriture qui transfère dans la cellule dont l'adresse est sur le
indicateurs que des branchements conditionnels peuvent être bus d'adresse, le mot contenu sur le bus de données.
exécutés vers certaines parties de programme.
La taille n des cellules mémoires ainsi que la taille m de
Pour accélérer les calculs, on a intérêt à utiliser les registres de
l'espace d'adressage sont des caractéristiques fondamentales
travail comme paramètres des procédures, notamment
de la machine. Le mot de n bits est la plus petite unité
l'accumulateur quand il existe.
d'information transférable entre la MC et les autres
composants. Généralement, les cellules contiennent des mots
de 8, 16 ou 32 bits.
Systèmes Informatiques Chapitre 4 : La Couche Machine 36 Systèmes Informatiques Chapitre 4 : La Couche Machine 37

3.2.3 RAM et ROM

3.2.2 Contenu/adresse (valeur/nom) Random Access Memory/ Read Only Memory

Attention à ne jamais confondre le contenu d'une cellule, mot La RAM est un type de mémoire électronique volatile et
de n bits, et l'adresse de celle-ci, mot de m bits même lorsque réinscriptible. Elle est aussi nommée mémoire vive et
n=m. plusieurs technologies permettent d'en construire différents
sous-types : statique, dynamique (rafraîchissement). La
Parfois, le bus de données a une taille multiple de n ce qui RAM constitue la majeure partie de l'espace mémoire
permet la lecture ou l'écriture de plusieurs mots consécutifs en puisqu'elle est destinée à recevoir programme, données et pile
mémoire. Par exemple, le microprocesseur 8086 permet des d'exécution.
échanges d'octets ou de mots de 16 bits (appelés "mots").
La ROM est un type de mémoire électronique non volatile et
Exemple (cellules d'un octet) non réinscriptible. Elle est aussi nommée mémoire morte et
plusieurs technologies permettent d'en construire différents
Adresse Contenu bin hexa. sous-types (ROM, PROM, EPROM, EEPROM (Flash), …).
0 0 1 0 1 0 0 1 1 53H La ROM constitue une faible partie de l'espace mémoire
1 1 1 1 1 1 0 1 0 0FAH puisqu'elle ne contient que le moniteur réalisant le chargement
2 1 0 0 0 0 0 0 0 80H du système d'exploitation et les Entrées/Sorties de plus bas
… niveau. Sur les PCs ce moniteur s'appelle le Basic Input
32 0 0 1 0 0 0 0 0 20H (3210) Output System. Sur les Macintosh, le moniteur contient
… également les routines graphiques de base. C'est toujours sur
2m-1 0 0 0 1 1 1 1 1 1FH une adresse ROM que le Compteur Ordinal pointe lors du
démarrage machine.
Parfois, une autre représentation graphique de l'espace mémoire est utilisé, en
inversant l'ordre des adresses : adresses de poids faible en bas, adresses fortes DDR SDRAM : Double Data Rate Synchronous Dynamic
en haut. Cependant, pour le 8086, lorsqu'on range un mot (16 bits) à l'adresse RAM est une RAM dynamique (condensateur) qui a un
mémoire i, l'octet de poids fort se retrouve en i+1. Il est aisé de s'en souvenir pipeline interne permettant de synchroniser les opérations
mnémotechniquement via la gravité dans les liquides de densités différentes. R/W.

Systèmes Informatiques Chapitre 4 : La Couche Machine 38 Systèmes Informatiques Chapitre 4 : La Couche Machine 39

3.3 Les périphériques 3.3.2 Mémorisation de masse

ou mémorisation secondaire
Les périphériques, ou organes d'Entrée/Sortie (E/S)
Input/Output (I/O), permettent à l'ordinateur de communiquer Les mémoires électroniques étant chères et soit volatiles (non
avec l'homme ou d'autres machines, et de mémoriser fiables) soit non réinscriptibles, le stockage de masse est
massivement les données ou programmes dans des fichiers. réalisé sur d'autres supports. Ces autres supports sont
La caractéristique essentielle des périphériques est leur caractérisés par :
lenteur : • non volatilité et réinscriptibilité
Processeur cadencé en Giga-Hertz : instructions éxécutées • faible prix de l'octet stocké
chaque nano-seconde (10-9 s) ; • lenteur d'accès et modes d'accès (séquentiel, séquentiel
Disque dur de temps d’accès entre 10 et 20 ms (10-3 s) : indexé, aléatoire, …)
rapport de 107 ! • forte densité
Clavier avec frappe à 10 octets par seconde : rapport de 108 ! • parfois amovibilité
• Mean Time Between Failures plus important car organes
3.3.1 Communication mécaniques → stratégie de sauvegarde

L'ordinateur échange des informations avec l'homme à travers Supports Optiques

des terminaux de communication homme/machine : clavier Historiquement, les cartes 80 colonnes ont été parmi les
←, écran →, souris ←, imprimante →, synthétiseur (vocal) premiers supports mais sont complètement abandonnées
→, table à digitaliser ←, scanner ←, crayon optique ←, aujourd'hui. Les rubans perforés, utilisés dans les milieux à
risque de champ magnétique (Machines Outils à Commande
lecteur de codes-barres ←, lecteur de cartes magnétiques ←,
Numérique), sont leurs descendants directs dans le cadre des
terminaux consoles stations ↔ …
supports optiques.
Il communique avec d'autres machines par l'intermédiaire de
réseaux ↔ locaux ou longue distance (via un modem). Supports Magnétique
Aujourd'hui (années 90), les supports magnétiques constituent
la quasi-totalité des mémoires de masse des ordinateurs à
usage général.
 Systèmes Informatiques Chapitre 4 : La Couche Machine 40 Systèmes Informatiques Chapitre 4 : La Couche Machine 41

Bandes magnétiques cylindre est constitué d'un ensemble de pistes de même

Ce sont des supports à accès séquentiel particulièrement utilisés dans la diamètre.
sauvegarde. On les utilise de plus en plus sous forme de cassettes. Les Un contrôleur de disque (carte) est chargé de transférer les
dérouleurs de cassettes sont appelés streamers. Les densités et vitesses sont informations entre un ou plusieurs secteurs et la MC. Pour
variables : quelques milliers de bytes per inch (bpi) et autour d'un Mo/s. Le
cela, il faut lui fournir : le sens du transfert (R/W), l'adresse de
temps d'accès dépendant de la longueur de la bande …
début en MC (Tampon), la taille du transfert, la liste des
schéma d'une bande magnétique adresses secteurs (n° face, n° cylindre, n° secteur). La plus
bloc i bloc i+1
petite unité de transfert physique est 1 secteur.
1
2
3
4 Pour accéder à un secteur donné, le contrôleur doit
Pistes 5
6
••• commencer par translater les bras mobiles portes-têtes sur le
7
8
9
bon cylindre, puis attendre que le bon secteur passe sous la
tête sélectionnée pour démarrer le transfert. Le temps d'accès
bit de parité gap inter-bloc
moyen caractérise la somme de ces deux délais moyens.

Disques magnétiques Exemple : TAmoyen et transfert d'1 secteur ?

Ils constituent la majorité des mémoires secondaires. Durs ou souples, fixes ou disque dur 8 faces, 50 cylindres, 10 secteurs/piste d'1 Ko,
amovibles, solidaires (Winchester) ou non (dispack) de leurs têtes de
tournant à 3600 tours/mn, ayant une vitesse de translation de 1
lecture/écriture, il en existe une très grande diversité. Les disques durs ont des
capacités variant entre quelques dizaines à quelques centaines de Mo, des
m/s et une distance entre la 1° et la dernière piste de 5 cm.
vitesses de transfert autour du Mo/s et des temps d'accès approchant les 10 ms.
schéma d'un disque magnétique TAmoyen = (5 cm/2)/1 m/s + (1/60 t/s)/2= 25ms+8,3 ms
face tête de lecture/écriture trou d'index Transfert d'1 secteur = (1/60)/10 = 1,66 ms
secteurs 0, 1, …, 7
0 •
1
2 translation
3
pistes
4

5
6
gap
7

rotation rotation
Composé de faces, de pistes concentriques, de secteurs "soft
sectored", la densité des disques est souvent caractérisée par
le nombre de "tracks per inch" (tpi) . Sur les disques durs, un

Systèmes Informatiques Chapitre 4 : La Couche Machine 42 Systèmes Informatiques Chapitre 4 : La Couche Machine 43

Supports optiques
Supports optiques
3.4 Pilote, contrôleur d'E/S et IT
unités de lecture fonctionnant au moyen d'un faisceau laser ;
densités de stockage supérieures au magnétique : de 102 à 104 A l’origine, l’UC gérait les périphériques en leur envoyant une
fois plus ; requête puis en attendant leur réponse. Cette attente active
temps d'accès plus longs : archivage de masse. était supportable en environnement monoprogrammé.

CDROM : disques compacts (même format que les CDs Actuellement, l’UC délègue la gestion des E/S aux
audio) pré-enregistrés par pressage en usine et non processeurs situés sur les cartes contrôleur (disque, graphique,
réinscriptibles : (logiciels, annuaires, encyclopédies, …). …). La communication avec un périphérique donné est
réalisée par le pilote (driver) qui est un module logiciel du
CDR : inscriptibles une seule fois ; SE :
- la requête d’un processus est transmise au moniteur
CDRW : réinscriptibles (1000 fois) concerné qui la traduit en programme contrôleur
puis qu’il envoie à la carte contrôleur ;
DVDR, DVDRW : idem CD mais avec des capacités plus - le processus courant « s’endort » et l’UC exécute un
importantes : 4,7 Go contre 700 Mo, double couches ... processus « prêt » ;
- le contrôleur exécute l’E/S ;
Magnéto-optiques : combinant la technologie optique (laser) - le contrôleur prévient l’UC de la fin de l’E/S grâce au
et magnétique (particules orientées), ils sont réinscriptibles. mécanisme matériel d’interruption ;
Amovibles, plus denses que les disques magnétiques mais - l’UC désactive le processus en cours d’exécution puis
moins rapides, ils constituent un compromis pour les « réveille » le processus endormi qui peut continuer
archivages et les fichiers rarement accédés. à s’exécuter.

Grâce à ce fonctionnement, l’UC ne perd pas son temps à des

tâches subalternes !

Généralement, plusieurs niveaux d'interruption plus ou

moins prioritaires sont admis par l'UC
Systèmes Informatiques Chapitre 4 : La Couche Machine 44 Systèmes Informatiques Chapitre 4 : La Couche Machine 45

3.5 Le(s) Bus 3.6 Améliorer les performances

Le bus de données est constitué d'un ensemble de lignes 3.6.1 Hiérarchie mémoire et Cache
bidirectionnelles sur lesquelles transitent les bits des données
lues ou écrites par le processeur. (Data 0-31)
Classiquement, il existe 3 niveaux de mémoire ordonnés par
vitesse d'accès et prix décroissant et par taille croissante :
Le bus d'adresses est constitué d'un ensemble de lignes
Registres ;
unidirectionnelles sur lesquelles le processeur inscrit les bits
Mémoire Centrale ;
formant l'adresse désirée.
Mémoire Secondaire.
Le bus de contrôle est constitué d'un ensemble de lignes
Afin d’accélérer les échanges, on peut augmenter le nombre
permettant au processeur de signaler certains événements et
des niveaux de mémoire en introduisant des CACHE ou
d'en recevoir d'autres. On trouve fréquemment des lignes
antémémoire de Mémoire Centrale et/ou Secondaire :
représentant les signaux suivants :
Mémoire plus rapide mais plus petite, contenant une copie de
certaines données :
Vcc et GROUND : tensions de référence ←
RESET : réinitialisation de l'UC ← Fonctionnement :
R/ W : indique le sens du transfert → Le demandeur demande à lire ou écrire une information ;
si le cache possède l’information, l’opération est réalisée,
MEM/ IO : adresse mémoire ou E/S → sinon, il récupère l’info. depuis le fournisseur puis réalise l’op.

Technologiquement, les bus de PC évoluent rapidement (Vesa Le principe de séquentialité des instructions et des structures
Local Bus, ISA, PCI, PCI Express, ATA, SATA, SCSI, …) de données permet d’optimiser le chargement du cache avec
des segments de la mémoire fournisseur. Stratégie de
remplacement est généralement LRU (Moins Récemment Utilisée).
[Link] Niveaux et localisation des caches

Cache Processeur réalisé en SRAM

- Niveau 1 (L1) : séparé en 2 caches (instructions, données),

situé dans le processeur, communique avec L2 ;

Systèmes Informatiques Chapitre 4 : La Couche Machine 46 Systèmes Informatiques Chapitre 4 : La Couche Machine 47

- Niveau 2 (L2) : unique (instructions et données) situé dans 3.6.2 Pipeline

le processeur ;
- Niveau 3 (L3) : existe parfois sur certaines cartes mères.
Technique de conception de processeur avec plusieurs petites
unités de commande placées en série et dédiées à la réalisation
Par exemple, Pentium 4 ayant un cache L2 de 256 Ko.
d’une tâche spécifique. Plusieurs instructions se chevauchent à
l'intérieur même du processeur.
Cache Disque
Par exemple, décomposition simple d'une instruction en 4
étapes :
De quelques Méga-octets, ce cache réalisé en DRAM est géré
par le processeur du contrôleur disque. Il ne doit pas être
confondu avec les tampons systèmes stockés en mémoire Fetch : chargement de l'instruction depuis la MC ;
centrale (100 Mo). Intérêts de ce cache : Decode : décodage en micro-instructions ;
Exec : exécution de l'instruction (UAL) ;
Lecture en avant (arrière) du cylindre ; Write Back : écriture du résultat en MC ou dans un
Synchronisation avec l’interface E/S (IDE, SATA, …) registre
Mise en attente des commandes (SCSI, SATA) Soit la séquence d'instruction : i1, i2, i3, ...
sans pipeline :
i1F, i1D, i1E, i1W, i2F, i2D, i2E, i2W, i3F, ...

avec pipeline à 4 étages

i1F i1D i1E i1W
i2F i2D i2E I2W
i3F i3D I3E
i4F i4D

Chaque étage du pipeline travaille « à la chaîne » en répétant

la même tâche sur la série d’instructions qui arrive.
Systèmes Informatiques Chapitre 4 : La Couche Machine 48 Systèmes Informatiques Chapitre 4 : La Couche Machine 49

Si la séquence est respectée, et s’il n’y a pas de conflit, le

débit d’instructions (throughput) est multiplié par le nombre 3.6.4 DMA et BUS Mastering
d’étages !
L'accès direct mémoire ou DMA (Direct Memory Access) est
Problèmes et solutions :
un procédé informatique où des données circulant de ou vers
Rupture de séquence : vidage des étages !
un périphérique (port de communication, disque dur) sont
Dépendance d’instructions : mise en attente forcée
transférées directement par un contrôleur adapté vers la
mémoire centrale de la machine, sans intervention du
Architecture superscalaire :
microprocesseur si ce n'est pour initier et conclure le transfert.
Plusieurs pipeline (2) dans le même processeur travaillent en
La conclusion du transfert ou la disponibilité du périphérique
parallèle (→instons indépendantes). peuvent être signalés par interruption.
Exemple : La technique de Bus Mastering permet à n’importe quel
Pentium 4 : selon ses versions, de 20 à 31 étages ! contrôleur de demander et prendre le contrôle du bus : le
maître peut alors communiquer avec n’importe lequel des
3.6.3 SIMD autres contrôleurs sans passer par l’UC.
Cette technique implémentée dans le bus PCI permet à
Single Instruction Multiple Data désigne un ensemble n’importe quel contrôleur de réaliser un DMA. Si l’UC a
d’instructions vectorielles permettant des opérations besoin d’accéder à la mémoire, elle devra attendre de
scientifiques ou multimédia. Par exemple, l’AMD 64 possède récupérer la maîtrise du bus. Le contrôleur maître lui vole
8 registres 128 bits et des instructions spécifiques utilisables alors des cycles mémoires.
pour le streaming, l’encodage audio ou vidéo, le calcul
scientifique.

Systèmes Informatiques Chapitre 4 : La Couche Machine 50 Systèmes Informatiques Chapitre 4 : La Couche Machine 51

3.7 Les périphériques 3.7.2 Mémorisation de masse

ou mémorisation secondaire
Les périphériques, ou organes d'Entrée/Sortie (E/S)
Input/Output (I/O) , permettent à l'ordinateur de Les mémoires électroniques étant chères et soit volatiles (non
communiquer avec l'homme ou d'autres machines, et de fiables) soit non réinscriptibles, le stockage de masse est
mémoriser massivement les données ou programmes dans réalisé sur d'autres supports. Ces autres supports sont
des fichiers. La caractéristique essentielle des périphériques caractérisés par :
est leur lenteur. • non volatilité et réinscriptibilité
• faible prix de l'octet stocké
En effet, sur les micro-ordinateurs travaillant à quelques dizaines de Méga-Hertz, le cycle d'un
accès mémoire est de quelques dizaines de nano-secondes (10-9 s). En revanche, une
• lenteur d'accès et modes d'accès (séquentiel, séquentiel
communication à 104 bits/s permet d'échanger 1 octet/milliseconde, et un disque dur a un indexé, aléatoire, …)
temps d'accès de quelques dizaines de ms pour un Ko. Le rapport d'échelle se situe donc entre • forte densité
103 et 105 (voire beaucoup plus pour les imprimantes) pour l'accès à un octet. • parfois amovibilité
• Mean Time Between Failures plus important car organes
3.7.1 Communication mécaniques → stratégie de sauvegarde

L'ordinateur échange des informations avec l'homme à travers Supports Optiques

des terminaux de communication homme/machine : clavier Historiquement, les cartes 80 colonnes ont été parmi les
←, écran →, souris ←, imprimante →, synthétiseur (vocal) premiers supports mais sont complètement abandonnées
→, table à digitaliser ←, scanner ←, crayon optique ←, aujourd'hui. Les rubans perforés, utilisés dans les milieux à
lecteur de codes-barres ←, lecteur de cartes magnétiques ←, risque de champ magnétique (Machines Outils à Commande
terminaux consoles stations ↔ … Numérique), sont leurs descendants directs dans le cadre des
Il communique avec d'autres machines par l'intermédiaire de supports optiques.
réseaux ↔ locaux ou longue distance (via un modem).
Supports Magnétique
Aujourd'hui (années 90), les supports magnétiques constituent
la quasi-totalité des mémoires de masse des ordinateurs à
usage général.
 Systèmes Informatiques Chapitre 4 : La Couche Machine 52 Systèmes Informatiques Chapitre 4 : La Couche Machine 53

Bandes magnétiques cylindre est constitué d'un ensemble de pistes de même

Ce sont des supports à accès séquentiel particulièrement utilisés dans la diamètre.
sauvegarde. On les utilise de plus en plus sous forme de cassettes. Les Un contrôleur de disque (carte) est chargé de transférer les
dérouleurs de cassettes sont appelés streamers. Les densités et vitesses sont informations entre un ou plusieurs secteurs et la MC. Pour
variables : quelques milliers de bytes per inch (bpi) et autour d'un Mo/s. Le
cela, il faut lui fournir : le sens du transfert (R/W), l'adresse de
temps d'accès dépendant de la longueur de la bande …
début en MC (Tampon), la taille du transfert, la liste des
schéma d'une bande magnétique adresses secteurs (n° face, n° cylindre, n° secteur). La plus
bloc i bloc i+1
petite unité de transfert physique est 1 secteur.
1
2
3
4 Pour accéder à un secteur donné, le contrôleur doit
Pistes 5
6
••• commencer par translater les bras mobiles portes-têtes sur le
7
8
9
bon cylindre, puis attendre que le bon secteur passe sous la
tête sélectionnée pour démarrer le transfert. Le temps d'accès
bit de parité gap inter-bloc
moyen caractérise la somme de ces deux délais moyens.

Disques magnétiques Exemple : TAmoyen et transfert d'1 secteur ?

Ils constituent la majorité des mémoires secondaires. Durs ou souples, fixes ou disque dur 8 faces, 50 cylindres, 10 secteurs/piste d'1 Ko,
amovibles, solidaires (Winchester) ou non (dispack) de leurs têtes de
tournant à 3600 tours/mn, ayant une vitesse de translation de 1
lecture/écriture, il en existe une très grande diversité. Les disques durs ont des
capacités variant entre quelques dizaines à quelques centaines de Mo, des
m/s et une distance entre la 1° et la dernière piste de 5 cm.
vitesses de transfert autour du Mo/s et des temps d'accès approchant les 10 ms.
schéma d'un disque magnétique TAmoyen = (5 cm/2)/1 m/s + (1/60 t/s)/2= 25ms+8,3 ms
face tête de lecture/écriture trou d'index Transfert d'1 secteur = (1/60)/10 = 1,66 ms
secteurs 0, 1, …, 7
0 •
1
2 translation
3
pistes
4

5
6
gap
7

rotation rotation
Composé de faces, de pistes concentriques, de secteurs "soft
sectored", la densité des disques est souvent caractérisée par
le nombre de "tracks per inch" (tpi) . Sur les disques durs, un

Systèmes Informatiques Chapitre 4 : La Couche Machine 54 Systèmes Informatiques Chapitre 4 : La Couche Machine 55

Nouveaux supports optiques et magnéto-optiques 3.7.3 Hiérarchie de mémoire

De nouveaux produits tels que les vidéodisques (images), les
disques optiques numériques et les disques magnéto-optiques
Usuellement, il existe 3 niveaux de mémoire ordonnés par
sont "récemment" apparus sur le marché. Ils sont caractérisés
vitesse d'accès et prix décroissant et par taille croissante :
par des densités de stockage supérieures au magnétique : de
registres, mémoire centrale, mémoire secondaire. Les
102 à 104 fois plus; mais aussi par des temps d'accès plus
machines et systèmes d'exploitation sont conçus afin de
longs ! Par conséquent, ils servent essentiellement à
réguler et de minimiser les temps d'exécution de l'UC sur les
l'archivage de masse.
données. Les données les moins utilisées sont donc stockées
sur les mémoires les plus lentes et les plus grosses tandis que
CDROM : disques compacts (même format que les CDs
les plus utilisées restent le plus près possible de l'UC. La
audio) pré-enregistrés par pressage en usine et non
vitesse/prix et la taille étant deux paramètres conflictuels,
réinscriptibles : (annuaires, encyclopédies, …). Les unités de
différents types de solutions sont possibles :
lecture fonctionnent au moyen d'un faisceau laser.
1. Elargissement du bus de données : 8080 (8 bits), 8086 (16
CDWORM (Write Once Read Many) : les CDs peuvent être
bits), 80386 (32 bits).
écrit une seule fois sur le site de l'utilisateur avec une unité de
lecture/écriture à faisceau laser.
2. introduction d'un niveau intermédiaire dans la hiérarchie de
mémoire : les mémoires cache sont des RAM très rapides
Magnéto-optiques : combinant la technologie optique (laser)
interposées entre l'UC et la MC. Utilisant divers algorithmes
et magnétique (particules orientées), ils sont réinscriptibles.
prédicatifs, ces caches ont comme fonction de contenir les
Amovibles, plus denses que les disques magnétiques mais
instructions et données dont l'UC aura besoin.
moins rapides, ils constituent un excellent compromis pour les
archivages et les fichiers rarement accédés.
3. Prefetching (pré-chargement) : Dans l'algorithme déroulé
par l'Unité de Commande de l'UC, on parallèlise le traitement
de l'exécution courante avec le chargement de l'instruction
suivante.
 Systèmes Informatiques Chapitre 4 : La Couche Machine 56 Systèmes Informatiques Chapitre 4 : La Couche Machine 57

3.7.4 Canaux ou Processeurs d'E/S et IT

4. La Couche Machine
Différents boîtiers électroniques sont conçus afin de piloter
certains périphériques selon certaines normes (ou interfaces) Elle constitue le niveau le plus bas auquel l’utilisateur a
V24, Centronics, SCSI…. Ces processeurs d'E/S sont accès.
commandés par l'UC qui leur confie l'exécution de tâches
spécialisées. Les commandes peuvent être fort simple mais Types d’ordinateurs (évolution constante !)
aussi donner lieu à un programme canal plus complexe.
les ordinateurs personnels (PC ou Macintosh) ;
Ces tâches peuvent engendrer une attente active de la part de - les ordinateurs de bureau ;
l'UC mais on préfère généralement désynchroniser les E/S et - les ordinateurs portables ;
l'UC. Pour ce faire, on utilise majoritairement le mécanisme - les assistants personnels (ou PDA) ;
d'Interruption (IT) de l'UC qui permet de suspendre le
traitement courant pour entreprendre l'exécution d'un les moyens systèmes (midrange) (ex IBM AS/400-ISeries,
programme prioritaire. Par exemple, après avoir lancé une E/S RISC 6000...)
disque via un processeur d'E/S, l'UC peut exécuter un autre
programme qui sera interrompu par le processeur d'E/S les mainframes (serveurs centraux) (ex. : IBM zSeries 64 bits,
lorsque le transfert aura été effectué! Siemens SR2000 et S110 ...) ;

les superordinateurs (Blue Gene machine IBM utilisant 65536

Généralement, plusieurs niveaux d'interruption plus ou
Power PC réalisant 136,8 TFlops);
moins prioritaires sont admis par l'UC. Par exemple, sur le
8086, 2 niveaux de priorités existent: les IT normales qui
peuvent ne pas être prises en compte, et les IT non
les stations de travail (PC puissants pour CAO, …) ;
masquables qui déroutent tout programme en cours.

Systèmes Informatiques Chapitre 4 : La Couche Machine 58 Systèmes Informatiques Chapitre 4 : La Couche Machine 59

4.2 Format des instructions

4.1 Exemples
Programme = suite d'instructions machines
Pentium 4 (x86 CPU) Une instruction est composée de plusieurs champs :
8 registres 32 bits (AL, AH, AX, EAX); • 1 champ obligatoire : le code opération désigne le type
Espace adrs : 4 Go ; d'instruction. Sa longueur est souvent variable afin
Mémoire virtuelle segmentée (CS code, DS data, SS stack) d'optimiser la place et la vitesse utilisée par les instructions les
avec un sélecteur de segment 16 bits + adrs virtuelle 32 plus fréquentes (Huffman).
bits ; • 0 à n champs optionnels : les opérandes désignent des
(x87) coprocesseur arithmétique flottante (FPU) 32, 64 ou 80 données immédiates ou stockées dans des registres ou en MC.
bits Le type de désignation de ces données est nommé mode
d'adressage.
AMD 64
16 registres 64 bits (AL, AH, AX, EAX, RAX) Exemple :
Espace adrs : 256 To Code Opération Opérande1 Opérande2
Mémoire virtuelle non segmentée sur 64 bits De plus, la taille des cases et mots mémoires doivent être des
SIMD avec registres 128 bits multiples de la taille d'un caractère afin d'éviter le gaspillage de
place ou des temps de recherche prohibitifs. Les codes
Big endian (petit boutiste) Little endian alphanumériques usuels étant sur 8 bits (EBCDIC) ou 7+1 bits
(ASCII), c'est la raison du découpage des MC en octets.
0 0000 1111 MSB 0 0000 1111 LSB
mot 0 MS LS Enfin, des adresses devant également être stockées en MC, c'est
1 mot 0 MSW 1
2 2 la raison pour laquelle la taille de l'espace d'adressage est
3 LSB 3 double mot 0 MSW
Adr
généralement un multiple de 28 octets (64 Ko, 16 Mo, 4 Go).
4 double mot 0 4 mot 4
5 LS 5 Sauf lorsque la technique d'adressage utilise des segments
6 6 double mot 4 recouvrants : 8086 : 1Mo = 220 o; 1 adrs = 2 mots.
7 7
8 mot 8 8
… … … …
double mot 8
IBM 370, Motorola 68000 x86, AMD 64,
En Little endian, mnémotechniquement, la "gravité" est orientée vers le bas de la
mémoire (adresses supérieures). Les Power PC d’IBM sont bi-endian.
Systèmes Informatiques Chapitre 4 : La Couche Machine 60 Systèmes Informatiques Chapitre 4 : La Couche Machine 61

4.3 Modes d'adressage 4.3.1 Adressage immédiat

Remarque : pour simplifier, nous utiliserons dorénavant la La valeur de la donnée est stockée dans l'instruction. Cette
notation mnémonique des instructions machines, notation valeur est donc copiée de la MC vers l'UC lors de la phase de
alphanumérique qui correspond à la couche 4 du langage chargement (fetch) de l'instruction.
d'assemblage.
Avantage : pas d'accès supplémentaire à la MC
Types de donnée représentés par les opérandes : Inconvénient : taille limitée de l'opérande
• donnée immédiate stockée dans l'instruction machine
• donnée dans un registre de l'UC Exemples : Z80
• donnée à une adresse en MC (1) ADD A, <n> ; Code Op. 8 bits, n sur 8 bits en C2
(2) LD <Reg>, <n> ; Code Op 5 b., Reg 3 b., n 8 b.
Nombres d'opérandes :
Nous supposerons un nombre maximal de 2 opérandes, ce qui 4.3.2 Adressage registre
représente le cas général. Souvent, un opérande implicite n'est
pas désigné dans l'instruction : c'est l'accumulateur qui est un La valeur de la donnée est stockée dans un registre de l'UC.
registre de travail privilégié; le Z80 a au maximum un La désignation du registre peut être explicite (2) ou implicite
opérande explicite (et A comme opérande implicite). (1) (A sur Z80).
Source et Destination :
Lorsque 2 opérandes interviennent dans un transfert ou une Avantage : accès rapide % MC
opération arithmétique, l'un est source et l'autre destination de Inconvénient : taille limitée de l'opérande
l'instruction. L'ordre d'apparition varie suivant le type d'UC :
IBM 370, 8086 : ADD DST, SRC DST := DST+SRC Selon le nombre de registres de travail de l'UC, la taille du
PDP-11, 68000 : ADD SRC, DST DST := DST+SRC code des instructions varie :
8 registres nécessitent 3 bits (Z80)
16 registres nécessitent 4 bits (68000)

Systèmes Informatiques Chapitre 4 : La Couche Machine 62 Systèmes Informatiques Chapitre 4 : La Couche Machine 63

4.3.3 Adressage direct 4.3.4 Adressage indirect

La valeur de la donnée est stockée à une adresse en MC. C'est La valeur de la donnée est stockée à une adresse m en MC.
cette adresse qui est représentée dans l'instruction. Cette adresse m est stockée dans un registre r ou à une adresse
m'. C'est r ou m' qui est codé dans l'instruction (m' est appelé
Avantage : taille quelconque de l'opérande un pointeur). L'adressage indirect par registre est présent dans
Inconvénient : accès mémoire supplémentaire, taille la totalité des UC, par contre, l'adressage indirect par mémoire
importante de l'instruction est moins fréquent. Il peut cependant être simulé par un
adressage direct dans un registre suivi d'un adressage indirect
Selon le type d'implantation mémoire requis par l'UC, par registre.
plusieurs adressages directs peuvent coexister. Peu de machines disposent de mode d'adressage indirect à
plusieurs niveaux d'indirection !
Exemples : 8086
MOV AL, <dis> ; déplacement intra-segment (court) Avantage : taille quelconque de l'opérande
transfère dans le registre AL, l'octet situé à l'adresse dis dans Inconvénient : accès mémoire supplémentaire(s), taille
le segment de données : dis est codé sur 16 bits, Data Segment importante de l'instruction (pas par registre)
est implicite.
Exemples : Z80 indirection seulement par HL
ADD BX, <aa> ; adresse absolue aa= S,D (long) ADD A, (HL) ; adressage indirect par registre
ajoute à BX, le mot de 16 bits situé à l'adresse D dans le codage de l'instruction sur 8 bits (code op.) : A et HL sont
segment S : D et S sont codés sur 16 bits. désignés implicitement

LD (HL), <reg> ; adressage indirect par registre

L'IBM 370 n'a pas de mode d'adressage direct, tandis que le code op. sur 5 bits et reg sur 3 bits; HL implicite
68000 permet l'adressage direct court (16 bits) et long (32
bits).
Systèmes Informatiques Chapitre 4 : La Couche Machine 64 Systèmes Informatiques Chapitre 4 : La Couche Machine 65

4.3.5 Adressage indexé (ou basé) 4.3.6 Remarques

Il est parfois nécessaire d'accéder à des données situées à des Dans une instruction, lorsque deux opérandes sont utilisés,
adresses consécutives en MC. En adressage indexé, on charge deux modes d'adressages interviennent. Souvent certains
un registre d'index avec l'adresse de début de cette zone de modes sont incompatibles avec d'autres pour des raisons de
données, puis on spécifie dans l'instruction, le déplacement à taille du code instruction ou de temps d'accès : par exemple en
réaliser à partir de cet index. L'adresse réelle de la donnée 8086, jamais deux adressages directs. Par contre, un opérande
accédée est donc égale à l'adresse de l'index ajoutée au fait parfois appel à la conjonction de deux modes d'adressage :
déplacement. mode indexé et basé + déplacement du 8086 !
Certaines UC exécutent automatiquement l'incrémentation ou
la décrémentation de leurs registres d'index ce qui permet, en
bouclant, de réaliser des transferts ou d'autres opérations sur Schéma des différents modes d'adressage
des zones (chaînes de caractères).
MC
LDIMM R, 100 LDIMM R, 100
Avantage : taille importante de la zone (256 octets si LDIND R, (R)
100 102 R := 100
déplacement sur 8 bits) LDIND R, (R)
Inconvénient : taille importante de l'instruction (si codage du LDDIR R, (100) R := 104
102 104
déplacement) R := 102
LDIMM RX, 100
104 35 LDIX R, (RX+4)
LDIND R, ((100))
Exemple : Z80 indexation par IX et IY R := 104 rare R := 35
LD (IX+<dépl>), <reg> ; adressage indexé par IX
codage de l'instruction : code op. sur 12 bits, IX sur 1 bit, reg
sur 3 bits, dépl sur 8 bits. Toute indirection à n niveaux peut être simulée dès lors qu'on
possède une instruction à indirection simple.
Sur le 8086, MOVSB (MOVe String Byte) permet de
transférer l'octet en (SI) vers (DI) puis d'incrémenter ou
décrémenter SI et DI. Remarquons que l'indexation sans
déplacement équivaut à l'indirection.

Systèmes Informatiques Chapitre 4 : La Couche Machine 66 Systèmes Informatiques Chapitre 4 : La Couche Machine 67

4.3.7 Adressage par pile 4.3.8 Utilisations de la pile

La pile d'exécution de l'UC est constituée d'une zone de la Avantages :
MC dans laquelle sont transférés des mots selon une stratégie • structure de données LIFO et opérations de manipulation
Dernier Entré Premier Sorti (Last In First Out LIFO). Le physiquement implantées : vitesse
premier élément entré dans la pile est placé à la base de la pile • instructions courtes car opérandes implicites
et le dernier élément entré se situe au sommet de la pile.
Inconvénients :
• pas toujours dans une zone MC protégée
70
71 …
• sa cohérence nécessite égalité du nombre d'empilages et de
Sommet 72 0000 0011 PUSH 0 dépilages (programmeur).
73 0000 0001 PUSH 0FFH • capacité souvent limitée (par exemple 1 segment)
74 1111 1111 PUSH 1
Base 75 0000 0000 PUSH 3
76 … L'appel procédural
77
78 L'intérêt de l'utilisation de sous-programmes nommés
procédures lors de l'écriture de gros programmes a été
démontré : concision, modularité, cohérence, … Le
Les instructions d'entrée et de sortie de pile sont PUSH <n> et programme principal (PP) fait donc appel (CALL) à une
POP <reg>. Selon le type d'UC, la pile remonte vers les procédure P1 qui exécute sa séquence d'instructions puis rend la
adresses faibles (voir schéma) ou bien descend vers les main, retourne (RET) à l'instruction du PP qui suit l'appel. Cette
adresses fortes. rupture de séquence avec retour doit également pouvoir être
L'adresse du sommet de pile est toujours conservée dans un réalisée dans le code de la procédure appelée P1, soit
registre nommé pointeur de pile (Stack Pointer SP). Sur récursivement, soit vers une autre procédure P2. Ces appels
certaines machines, un registre général peut servir de SP. imbriqués, en nombre quelconque, rendent impossible
Certaines UC utilisent également un pointeur de base de pile l'utilisation d'une batterie de registres qui sauveraient les valeurs
(Base Pointer BP). de retour du CO !
Systèmes Informatiques Chapitre 4 : La Couche Machine 68 Systèmes Informatiques Chapitre 4 : La Couche Machine 69

Exemple d'appels procéduraux imbriqués Paramètres et Variables locales

P1 P2
La plupart des langages de programmation évolués (Pascal, c,
ADD AX,BX MUL AX, BX
DIV AX, CX …) permettent le passage de paramètres et l'utilisation de
PP CALL P2
… b1 : MOV AX, CX RET variables locales aux procédures. Les paramètres sont passés
ADD AX, 2 RET soit par valeur, soit par adresse. Les variables locales sont
MOV BX, 6
CALL P1 P3 créées à l'activation de la procédure et détruites lors de son
a1 : ADD CX, 12 DEC CX retour (durée). D'autre part, leur visibilité est réduite aux
CALL P3 CMP CX, 0
a2 : ROTL AX CALLNZ P3
instructions de la procédure.
… c1 : RET
Passage de paramètre
Les appels procéduraux imbriqués nécessitent l'utilisation de
la pile de la manière suivante : Dans les programmes écrits en langage machine, la gestion
des paramètres d'appel et de retour est à la charge du
CALL <adrs> génère automatiquement (couche 1) : programmeur (registres, MC, pile). Par contre, un
1. PUSH CO ; le compteur ordinal pointe toujours sur compilateur doit fournir une gestion générique des
l'instruction suivante paramètres quel que soit leur nombre et leur mode de passage.
2. JMP <adrs> ; jump = goto La plupart du temps, la pile est utilisée de la façon suivante :
Dans l’appelant, juste avant l'appel (CALL), le compilateur
RET génère automatiquement : génère des instructions d'empilage (PUSHs) des paramètres
1. POP CO ; branchement à l'adresse de retour d'appel et de retour. Juste après le CALL, il génère le même
nombre de dépilage afin de nettoyer la pile. Dans le corps de
Exemple d'évolution de la pile la procédure appelée, la première opération consiste à affecter
à un registre d'index ou de base (BP) la valeur du sommet de
c1 pile ± taille adresse de retour. Par la suite, les références aux
c1 …
b1 c1 c1 c1 c1 paramètres sont effectuées via ce registre (BP±0..n) !
a1 a1 a1 a2 a2 a2 a2 a2 a2

Attention aux appels récursifs mal programmés qui provoquent

des débordements de pile (Stack Overflow) ! P3 : 2n appels
maximum (mots de n bits).

Systèmes Informatiques Chapitre 4 : La Couche Machine 70 Systèmes Informatiques Chapitre 4 : La Couche Machine 71

Exemple de passage de paramètres : Paramètres et variables locales

Finalement, chaque instance d’appel de procédure possède un
Appelant Appelée espace d’adressage local composé :
…
PUSH <param1> ; param de retour
PUSH BP; de l'appelant • d’une part, des paramètres d’appel et de retour localisés
MOV BP, SP dans la pile à (BP+2..n);
PUSH <param2> ; param d'appel MOV AX, (BP+2) ; param n
… MOV BX, (BP+3) ; param n-1 • d’autre part, des variables locales localisées dans la pile à
PUSH <param n> ; param d'appel MOV CX, (BP+4) ; param n-2
CALL <appelée> (BP+1..m).
…
a0 : POP <reg> MOV (BP+n+1), AX ; résultat
n … POP BP Exemple simple
POP <reg> ; résultat (retour) RET
… Nous considérerons une procédure récursive simple n’utilisant
que des paramètres et variables locales codés sur un mot
BP appelant machine. La fonction mult est une procédure à un paramètre
a0 a0 a0
param n param n param n param n param n de retour réalisant la multiplication de 2 entiers positifs par
param n-1 param n-1 param n-1 param n-1 param n-1 additions successives. Nous ne traiterons pas des problèmes de
… … … … … dépassement de capacité ni de l’optimisation de l’algorithme
param1 param1 param1 param1 param1
(y=0).

entierpositif mult(entierpositif x, entierpositif y)

Variables locales
entierpositif i ; // inutile dans l’algo. !
L'implémentation de l'espace dédié aux variables locales est
si x=0 alors retourne 0
réalisé dans la pile d'exécution. Les premières instructions
sinon début
machines correspondant à la compilation d'une procédure
i=y
consistent toujours à positionner les variables locales dans la
retourne mult(x-1,i) + y
pile, juste au dessus de l’adresse de retour. Dans l’exemple
fin
précédent, il suffit de rajouter autant de PUSH, après le MOV
BP,SP, que nécessaires. Ces variables locales seront ensuite
Etudions le code compilé de cette procédure et d’un appel
accédées via des adressages (BP-i) générés par le compilateur.
initial avec des données en entrée : x=2, y=5.
Ce type d’implémentation permet l’appel procédural ainsi que
la récursivité.
 Systèmes Informatiques Chapitre 4 : La Couche Machine 72 Systèmes Informatiques Chapitre 4 : La Couche Machine 73

Image du code compilé et de la pile Autres utilisations de la pile

Mult Cette structure de données LIFO est massivement employée

PUSH BP ; de l'appelant dans le cadre d’algorithmes divers et variés.
MOV BP, SP
PUSH DX ; i qcq en (BP-1)
CMP (BP+3), 0 ; x=0 ? Exemples
JE ZERO
MOV (BP-1),(BP+2) ; i:=y
Appelant
MOV AX, (BP+3) ;x • dérécursivation automatique : dans l’exemple précédent, les
… DEC AX ; x-1 CALL récursifs peuvent être évités en empilant
PUSH <multret> ; param de retour PUSH DX ; retour qcq
PUSH x ; param d'appel 2
successivement les valeurs des paramètres d’appels puis en
PUSH AX ; appel x-1
PUSH y ; param d'appel 5 PUSH (BP-1) ; appel i réalisant des additions successives lors des dépilages.
CALL mult CALL mult ; récursif
A0: POP DX A1: POP DX ; dépile
POP DX POP DX ; dépile appel
• évaluation d’expressions arithmétiques infixées et
POP AX ; résultat (retour) POP AX ; résultat (retour) parenthésées : 3*(5+4*2)
CALL AFFICHEAX ADD AX, (BP+2) ; résult + y
… MOV (BP+4), AX ; range résultat 3*(5+4*2)
JMP FIN
ZERO : MOV (BP+4),0 ; range rés.=0
* 2 *
FIN : POP DX ; var locale i 8 +
4 + 4 +
POP BP ; BP appelant + 5 ( 13
( 5 ( 5 ( 5 (
RET 3 *
0 3 * 3 * 3 * 3 * 3 * 39
BP2 ? BP3 ? 5
BP2
BP1 BP2 BP1 )
A1 A1 A1 5 8=2*4 39=13*3
? 13=8+5
BP1 5 5 5 5
BP0 1 0 1 BP0
A0 ? ? 5 A0 • parcours d’arbre (préfixe, infixe, postfixe)
5 5 5 5 5 5
2 BP0 BP1 BP0 2 2
? … … … 10 10 • etc …
1° appel 2° appel 3° appel 1° retour 2° retour 3° retour

Cet exemple illustre bien le danger de croissance de la pile

lors d’appels récursifs mal programmés ! Remarquons que la
dérécursivation évidente de mult peut être réalisée par le
programmeur mais parfois aussi par le compilateur.

Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 75

5.2 Edition de liens dynamique

5. Librairies et édition de liens en C
Les librairies dynamiques possèdent l’extension .so et sont
L’édition de lien peut-être : généralement situées dans /usr/lib/. Le programme
- statique :
[Link] charge les librairies partagées nécessaires à un
• + le binaire exécutable contient tout ce dont il a besoin programme, le prépare et lance son exécution.
pour s’exécuter ;
Les librairies dynamiques chargées par [Link] sont cherchées
• + il est portable et rapide une fois chargé ;
dans les répertoires indiqués dans la variable d'environnement
• - il est gros car il contient les fichiers objets et les
LD_LIBRARY_PATH.
bibliothèques qui sont dupliquées ;
- dynamique :
• + le binaire est léger
5.2.1 En pratique
• + les bibliothèques dynamiques n’existent qu’en un seul
exemplaire en mémoire ;
Pour créer une librairie dynamique personnelle :
• - le temps d’exécution est plus grand du fait de la liaison ; $ gcc -fPIC -c *.c
$ gcc -shared -Wl,-soname,[Link].1 -o [Link].1.0 *.o
$ ln -s [Link].1.0 [Link].1
5.1 Edition de liens statique $
$
ln -s [Link].1 [Link]
LD_LIBRARY_PATH=`pwd`:$LD_LIBRARY_PATH ; export LD_LIBRARY_PATH

En pratique, sur les systèmes modernes l’édition de liens est dynamique par -fPIC : position independant code
défaut : il faut préciser si l’on veut une édition statique :
gcc -static –o monprog monprog.o –lmabib –L. -shared : librairie partagée
-Wl : fait passer l'option –soname [Link].1 à l’éditeur de lien.
-static : édition statique -o : output
-lx : librairie statique libx.a -L. : chercher dans . -soname : nom interne de la librairie inscrit par ld (Link eDit)
ln : pour les références avec des versions différentes
Pour construire une librairie statique :
ar rs libmabib.a a.o b.o
r: replace les .o s : maj la table des Symboles
Pour compiler mon programme :
gcc -o monprog monprog.c -ltruc
ar t libmabib.a
t : affiche les fichiers objets contenus Pour lister les dépendances dynamiques de monprog :
ldd monprog
Pour afficher les symboles d’une librairie statique : Pour exécuter mon programme :
nm –g libmabib.a ou nm -g monprog.o
monprog
-g : affiche les symboles externes
Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 76 Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 77

Remarque :
6. Les Systèmes de Gestion de Fichiers Selon les SE, la longueur, le nombre, la structure des champs
est fixe ou variable. Lorsque l'article est réduit à un octet, le
fichier est qualifié de non structuré. Au niveau logique,
6.1 Les Fichiers plusieurs modèles de base de données ont été définis : modèle
relationnel [Codd 76], réseau, hiérarchique.

6.1.1 Introduction Définition physique :

Un fichier est constitué d'un ensemble de blocs
Définition conceptuelle : (enregistrement physique, granule, unité d'allocation, "block",
Un fichier est une collection organisée d'informations de "cluster") situés en mémoire secondaire. Les articles d'un
même nature regroupées en vue de leur conservation et de leur même fichier peuvent être groupés sur un même bloc (Facteur
utilisation dans un Système d'Information. de groupage ou de Blocage (FB) = nb d'articles/bloc) mais on
peut aussi avoir la situation inverse : une taille d'article
Remarque : nécessitant plusieurs blocs. En aucun cas, un article de taille ≤
inclut les SI non automatisés (agenda, catalogue de produits, taille d'un bloc n'est partitionné sur plusieurs blocs → lecture
répertoire téléphonique,…) 1 article = 1 E/S utile.

Remarque :
les blocs de MS sont alloués à un fichier selon différentes
méthodes liées au type de support qu'il soit adressable
Définition logique : (disques, …) ou séquentiel (bandes, cassettes, "streamers").
C'est une collection ordonnée d'articles (enregistrement Ces méthodes d'allocation sont couplées à des méthodes de
logique, item, "record"), chaque article étant composés de chaînage des différents blocs d'un même fichier et seront
champs (attributs, rubriques, zones, "fields"). Chaque champ étudiées dans le chapitre SGF.
est défini par un nom unique et un domaine de valeurs.

Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 78 Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 79

6.1.2 Opérations et modes d'accès 6.1.3 Caractéristiques fonctionnelles

Un certain nombre d'opérations génériques doivent pouvoir Volume : taille d'un fichier en octets ou multiples. Si articles
être réalisées sur tout fichier : de longueur fixe alors taille article*nb articles.

- création création et initialisation du noeud Taux de consultation/mise à jour pour un traitement donné :
descripteur (i-node, File Control Block, rapport entre le nombre d'articles intervenant dans le
Data Control Block) contenant taille, date traitement et nb total d'articles.
modif., créateur, adrs bloc(s), …
- destruction désallocation des blocs occupés et Exemple : fichier "personnel", traitement "paye"
suppression du noeud descripteur ==> taux de consultation = 100%
- ouverture réservation de tampons d'E/S en MC pour
le transfert des blocs Remarque : un taux de consultation important implique
- fermeture recopie des tampons MC vers MS souvent un traitement par lot avec une méthode d'accès
(sauvegarde) séquentielle.

- lecture consultation d'un article Fréquence d'utilisation : nb de fois où le fichier est utilisé
- écriture insertion ou suppression d'un article pendant une période donnée.

La lecture et l'écriture constituent les modes d'accès et Taux d'accroissement : pourcentage d'articles ajoutés
peuvent être combinés (mise à jour) lors de l'ouverture d'un pendant une période donnée.
fichier (existant). A la création, un fichier est toujours ouvert
en écriture. Un SE multi-utilisateurs doit toujours vérifier les Taux de renouvellement/suppression : pourcentage d'articles
droits de l'utilisateur lors de l'ouverture d'un fichier. nouveaux/supprimés pendant une période donnée. (TR=TS ==>
volume stable)
Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 80 Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 81

Ces différentes caractéristiques ainsi que le type prépondérant 6.1.4 Structure et Longueur des articles
d'utilisation (traitement par lot ou interactif) d'un fichier
doivent permettre de décider de la structuration des articles,
Articles de longueur fixe et de structure unique
du type de support de stockage et des méthodes d'accès.
Dans la plupart des cas, chaque article d'un fichier contient le
même nombre de champs chaque champ étant de taille fixe. Il
On classe souvent les fichiers en différentes catégories :
existe un type unique d'articles.
fichiers permanents : informations vitales de l'entreprise :
Exemple : fichier STOCK
Client, Stock, Fournisseurs...
nom champ type taille exemple
durée de vie illimitée, Fréquence d'Utilisation élevée, màj
périodique par mouvements ou interactive. REF N 4 0018
DESIGN A 15 VIS 8*20
fichiers historiques : archives du SI : Tarifs, Prêts- QTE N 7 550 000
Bibliothèque, journal des opérations… DATE D 6 23/09/92
pas de màj, taux d'accroissement élevé, taux de suppression
nul. Articles de longueur fixe et de structure multiple
Les articles peuvent varier de structure parmi plusieurs sous-
fichiers mouvements : permettent la màj en batch des types d'articles (record variant de Pascal, union de C, C++).
permanents afin d'éviter incohérences ponctuelles : La longueur fixe des articles d'un tel fichier correspond à la
Entrée/Sortie hebdomadaire stock, heures supplémentaires longueur maximale des différents sous-types.
Janvier, …
durée de vie limité, fréquence d'utilisation très faible. Exemple : fichier PERSONNE, articles de 42 octets

fichiers de manoeuvre : durée de vie très courte (exécution NOM(20), PRENOM(15), SITUATION(1),
d'un programme) : spool, fichier intermédiaire. cas SITUATION=M alors DATE_MAR(6)
cas SITUATION=D alors DATE_DIV(6)
cas SITUATION=C alors rien

Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 82 Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 83

Remarque : les deux types d'articles précédents constituent la 6.1.5 Méthodes d'accès
quasi-totalité des fichiers. La longueur fixe des articles permet
de réaliser efficacement les calculs d'adresses de ceux-ci.
Accès Séquentiel
Les articles sont totalement et strictement ordonnés. L'accès
Articles de longueur var. et de structure multiple
(lecture/écriture) à un article ne peut être réalisé qu'après
L'intérêt principal de ce type d'articles consiste dans le gain de
l'accès à l'article précédent. Un pointeur d'article courant
place (suppression des blancs) constitué par le compactage des
permet de repérer la position dans le fichier à un instant
fichiers concernés. L'inconvénient majeur réside dans la
donné. L'ouverture en lecture positionne le pointeur sur le
difficulté à calculer l'adresse d'un article. Ce type d'articles est
1er article puis les lectures successives font progresser le
particulièrement utilisé à des fins d'archivage sur support
séquentiel et pour la téléinformatique. pointeur jusqu'à la position End Of File (EOF). Selon les cas,
l'ouverture en écriture positionne le pointeur en début de
La séparation des articles et des champs est souvent effectuée fichier (rewrite) ou en fin de fichier (append). Il existe une
par insertion de préfixes indiquant la longueur de l'article ou opération spécifique de remise à zéro du pointeur (retour en
du champ. début de fichier, rembobinage, "reset", "rewind").

Exemple : fichier PERSONNE Historiquement lié au support bande magnétique et cartes

perforées, cette méthode d'accès est la plus simple et de surcroît
TailleArt(1), NOM(1+20), PRENOM(1+15), SIT(1), est universelle. Elle reste très utilisée notamment pour les
cas SIT=M alors DATE_MAR(6) fichiers non structurés (textes, exécutables,…) ou les fichiers
cas SIT=D alors DATE_DIV(6) historiques. Pour les fichiers permanents, si le taux de
cas SIT=C alors rien consultation ou de màj est important, la solution séquentielle
doit être envisagée. Cependant, l'accès séquentiel est impensable
18,5,UHAND,4,PAUL,M,23/08/91, pour un bon nombre d'op. interactives (réservations, op.
12,5,PETIT,4,JEAN,C, bancaires, …)
19,6,HOCHON,4,PAUL,D,10/10/89,
…
Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 84 Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 85

Accès direct Adressage relatif

(ou sélectif, aléatoire, "random")
La clé est un nombre entier correspondant au numéro logique
Ce type d'accès nécessite un support adressable! Un ou
(0..n-1) d'article dans le fichier. On obtient aisément l'adresse
plusieurs champs des articles servent d'expression d'accès
physique (bloc ; dépl.) de celui-ci :
(clé) pour "identifier" et accéder à un ou plusieurs articles. On taille fixe : AdPhy:=(Orga(nl div FactBloq); taille*(nl mod FactBloq))
peut directement lire ou écrire l'article grâce à une opération taille var. : il existe une table de correspondance [nl --> AdPhy]
du type suivant :
Si la numérotation logique n'est plus continue (suppressions),
lire/écrire(fichier, valclé, adrsMCtransfert) de l'espace inutile continue à être occupé par le fichier ! En
effet, la compression après chaque suppression serait trop
On peut également vouloir accéder aux articles par coûteuse. L'insertion suivante sera donc réalisée dans un trou.
l'intermédiaire de plusieurs clés : L'ordre des nl ne correspond donc pas forcément à l'ordre
d'insertion !
Exemple : fichier Personne; clé1 = N°SS; clé2 = Nom
Par la suite, nous traiterons de la manière de réaliser l'accès Adressage dispersé, calculé ("hash-coding")
direct sur un fichier à clé unique. Selon les cas, la
L'adressage dispersé consiste à calculer un numéro logique
transposition aux clés multiples est plus ou moins simple !
d'article à partir d'une valeur de clé et d'une fonction de
hachage : nl:=f(c).
Adressage direct
Ce type d'adressage est un cas d'école puisqu'il associe à chaque valeur de clé f permet de réduire le domaine des nl par rapport au domaine
l'adresse physique du bloc contenant l'article. Il y a ainsi identité des valeurs de des clés afin de donner un volume de fichier supérieur au
clé d'article et des adresses physiques de bloc. Un inconvénient évident est que volume utile mais inférieur à card(domaineClé)*tailleArt.
le domaine des valeurs de clé doit correspondre exactement aux domaine des
adresses physiques. De plus, l'espace adressable est très fortement sous-occupé
(FB=1) et ne peut être partagé par plusieurs fichiers ayant des valeurs de clés Avantages :
conflictuelles ! Par contre, le temps d'accès à un article est minimal. La clé doit calcul en MC ==> accès très rapide
être identifiante ! clés quelconques : non identifiantes ==> collisions

Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 86 Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 87

exemple : La détermination d'une bonne fonction de hachage donnant un

faible taux de collision est un gage de rapidité d'accès.
Domaine Clé Clés utilisées numéros logiques Exemple : somme des entiers (16 bits) composant la clef
0 modulo taille fichier. Avec une clé non identif., le taux de
1 0
2
1 1 collision augmente.
3 2
4 f 3
4 Lorsque le volume utile du fichier croît, il est nécessaire de
4
5
… 5 réorganiser celui-ci, par exemple, en allouant un espace
99998 99998 6 logique double du précédent, en modifiant f et en réorganisant
7
99999
8
les articles existants.

Dans cet exemple, un domaine de 106 clés potentielles est réduit à un espace inconvénients :
logique de 9 numéros logiques permettant de stocker les 3 articles réels. collisions coûteuses
pas d'accès séquentiel (accès calculés répétés)
hachage parfait taux d'occupation mémoire <= 1
Une fonction de dispersion idéale est celle qui réalise une taille du fichier connue à priori
bijection de l'ensemble des clés existantes vers l'ensemble des réorganisations coûteuses
numéros logiques. Il n'y a ainsi aucun espace perdu. La
recherche d'une fonction idéale est calculable sur un ensemble Adressage indexé
statique de clés identifiantes mais impossible sur un ensemble
dynamique Un index est une table de couples (valeur clé, nl) triée sur les
valeurs de la clé. L'index est dense si toutes les clés du fichier
Collisions ou conflits y sont recensées. Sinon l'index est dit creux et une clé c
Il y a collision lorsque la fonction de hachage associe un
présente dans le fichier et absente de l'index est dite couverte
numéro logique déjà utilisé à un nouvel article. Il faut alors
par la clé tout juste inférieure présente dans l'index. Un index
traiter la collision pour insérer le nouvel article dans le fichier
creux implique une clé primaire, c'est à dire que le fichier
:
soit trié sur cette clé. D'autres index secondaires doivent alors
- soit dans une zone de collision générale accédée soit séquentiellement, soit par
une autre fonction f2 être dense !
- soit dans une zone de collision spécifique à chaque numéro logique.
Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 88 Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 89

Exemple d'Index creux primaire : Exemple d'index par b-arbre :

numéros logiques
0 1 2 3
Index 14 22
6,Paul/13,Durand/14,Pierre/
( ,4) 4 blocs
(6,0) d'index
1,Dupont/5,Hochon/ / /
(15,16) 10 18 20 30
(46,12) 135,Michel/ / / / Blocs (FB=4)
(135,8)
46,Potuit/49,Dru/ / / 2 10 14 18 20 22 30
Paul Ilot Duri Py Rat Ture Pou
9 19 29
15,Riton/ / / /
Piera Tota Roit
La recherche d'une clé d'un article est réalisée par dichotomie
sur le fichier d'index. Lorsque le fichier atteint un volume
1 bloc de fichier = 1 à 2 articles
important, son fichier d'index ne tient plus sur un seul bloc et
on est alors forcé de parcourir séquentiellement les blocs Afin de maintenir les contraintes lors des suppressions ou des
d'index. insertions d'articles, on est parfois obligé de réorganiser
l'arborescence !
Aussi, on préfère une organisation arborescente (b-arbre) de Moins rapide que le hachage pour l'accès direct, l'adressage
l'index dans laquelle existe une hiérarchie de sous-tables indexé permet cependant de traiter également l'accès
d'index creux permettant une bonne rapidité d'accès. En fait, séquentiel à moindre coût (index creux ou b-arbre).
on indexe chaque bloc d'index !
Remarques
• Il existe toujours un compromis (place utilisée/temps d'accès).
Contraintes sur un b-arbre d'ordre p (#ptrs/bloc index) • Les insertions et suppressions d'articles provoquent des trous dans les blocs
• tout chemin (racine --> feuille) est de longueur identique = de données. L'index b-arbre gère ceux-ci mais les index linéaires (creux ou
hauteur (exemple h=2) denses) ne le font pas… (voir SGF)
• chaque bloc d'index est toujours au moins à moitié plein • Pratiquement, les b-arbres et les index creux (ISAM) prédominent dans les
(sauf la racine) : chaque bloc d'index contient k clés avec SGBD (vitesse + accès séquentiel).
• index multiples : on peut ajouter des index secondaires denses peu efficaces
EntInf(p/2)≤k≤p-1 (ex. p=3). pour l'accès séquentiel.

Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 90 Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 91

6.2 Gestion des fichiers en C sous Unix 6.2.2 Appels systèmes E/S et Fichiers

6.2.1 Généralités - appels systèmes : on travaille directement sur les tampons

systèmes des fichiers ;
• différence entre appel système (manuel section 2) et fonction de
- fon bibli : on travaille sur une image du fichier en zone
bibliothèque ("library") (section 3). utilisateur et cette image est transférée de temps à autre en
- appel système : primitive du noyau interrompant le pus (passe en mode zone système (E/S tamponnées) : nb d'it mini mais pbs de
noyau), pas d'édition de liens, vu comme une fonction C externe retournant un concurrence !
résultat==-1 si erreur : lire alors la variable 'extern int errno' pour connaitre le
type d'erreur (1 : permission, 2 : fichier non existant, …)
- fon bibli : édition de liens avec librairies (E/S formatées, maths, etc …). 2 types : - manip. des liens de répertoires
- manip. fichier et i-node par descripteur
• passage des paramètres de la ligne de cde :
descripteur : entier positif désignant le fichier ou le périph :
main(int nbpar, char *argv[], char *env[]) {…}
nbpar : nombre de paramètres ($#argv)
0,1,2 réservés pour Entrée, Sortie et Err standard
argv : tableau de chaines == liste des paramètres (0 .. nbpar-1) [Link] Création
env : tableau de chaines == liste des var d'env. (nomvar=valeur) int creat(char *path, int droits); A EVITER
int open(char *path, int flags, int droits)
• sortie de pus : void exit(int status); params: flags==O_WRONLY |O_CREAT|O_TRUNC
path : nom ou chemin d'accès au fichier « ../Monrep/[Link] »
• lancement d'une cde externe : void system(char *commande); droits : droits d'accès qui seront masqués par umask.
Return : un descripteur entier
exemple :
/* essai source c */ Par exemple :
#include <stdio.h> fic=open("../toto/ficessai", O_WRONLY|O_CREAT|O_TRUNC, 0666);
main(int n, char*argv[], char*env[]) {
printf("essai affichage de .cshrc\n"); ouvre un fichier vide en écriture, pointeur à 0. Attention, si le fichier existait
system("cat .cshrc"); déjà, il conserve ses anciens droits d'accès !!! Il est donc utile de faire précéder
exit(9); la création par : chmod(path,droits).
}
toto> cc essai.c; [Link] [Link] Ouverture
int open(char *path, int flags[, int mode])
params: flags : O_RDONLY (0) xor O_WRONLY (1) xor O_RDWR
(2) , O_APPEND, O_TRUNC…
ouvre un fichier selon un mode (R|W|RW) et positionne le pointeur en début
(fin si O_APPEND) de fichier; retourne un descripteur
Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 92 Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 93

[Link] Lecture 6.2.3 Bibliothèque d'E/S standard du C

int read(int desc, char *buf, int nboctets)
retourne le nb d'octets (≤ nboctets) effectivement transférés dans buf et avance le
pointeur; 0 si EOF, -1 si problème (desc inexistant…). Le type FILE permettant de manipuler les fichiers par des
FILE * souvent nommés flots « stream » :
[Link] Ecriture - 3 macros : stdin, stdout, stderr pour descripteurs 0, 1, 2
int write(int desc, char *buf, int nboctets) - constante EOF (-1) == entier retourné lorsque fin de fichier
retourne le nb de car écrits dans le fichier et avance le pointeur, -1 si pb. Si
O_APPEND positionné, toute écriture est précédée de l'avancée du pointeur en FILE *fopen(char *path, char *mode)
EOF sinon écriture (surcharge) à partir de la position courante et avance le path:nom du fichier; mode:{"r","w","a"append,"r+"rw,"w+"raz et
pointeur. rw}

[Link] Fermeture int fclose(FILE* f) vidage du tampon sur le fichier.

int close(int desc)
int [f]getc(FILE *g); int [f]putc(char c,FILE
le nb de fichiers ouverts d'un processus étant limité (16), il peut être utile de
fermer ses fichiers même si le exit les ferme tous automatiquement.
*g); getchar(); putchar(c)
lit/écrit un caractère du fichier g ; sans f : stdin, stdout
[Link] Déplacement de pointeur (accès Direct)
long lseek(int desc, long depl, int flags) int [f]gets(char *ch, int n, FILE *f) : lit une
déplacement absolu ou relatif du pointeur en fonction de la valeur de flags :
chaîne ; min(nb car jusqu'à '\n', n-1) char +'\0' sont copiés dans ch
SEEK_SET ou 0 : début ; SEEK_CUR ou 1 : courant ; SEEK_END ou 2 : fin.
Retourne la position relative du pointeur par rapport au début de fichier (0..n-1)
Attention, gets remplace le'\n' par '\0' mais pas fgets !
ou -1 si erreur.
int [f]puts(char *ch, FILE *f) : écrit une chaîne ;
[Link] Redirection d'E/S par duplication de desc. copie ch dans f, sauf le '\0' final
int dup(int desc)
retourne un nouveau descripteur de valeur minimale désignant le même fichier int fseek(FILE *f, long depl, int base) : déplace
ou E/S que desc.
ex : … d=creat("ficredir", 0666); close(1); dup(d); …
le pointeur de fichier ; base==0 (1,2) : déplacement % au début
redirige la sortie standard vers ficredir (courant, fin) de f

[Link] Autres appels systèmes (voir man 2) int feof(FILE* f) : retourne vrai (!=0) si le pointeur
access : teste les droits d'accès link, unlink : multi-références est en EOF
stat : retourne le contenu du i-noeud d'un fichier (lstat, fstat)
chdir : change répertoire courant int fflush(FILE *f) ; vidage du tampon en écriture
chown, chmod : change propriétaire, droits d'accès vers le fichier
mkdir, mkfifo : crèe un répertoire, un tube …
int fpurge(FILE *f) ; RAZ des tampons en écriture et
en lecture sans utilisation du contenu !

Systèmes Informatiques Chapitre 5 : Les Systèmes de Gestion de Fichiers 94

[Link] E/S Formattées 6.3 Organisation hiérarchique des Fichiers

int [f]printf(FILE *f, format, liste_vals) ;
printf pour stdout : écriture formatée : %s chaîne, %c car, %d 6.3.1 Organisation arborescente
entier décimal, %x hexa
%10.2d pour convertir un entier en chaîne de 10 car dont 2
La quasi-totalité des SGF sont organisés en arborescence de
décimales
répertoires (catalogue, "directory") contenant des sous-
répertoires et fichiers. Suivant le cas, les répertoires sont
int [f]scanf(FILE *f, format, liste_ptrs) ;
considérés comme des fichiers (unix) ou bien demeurent dans
scanf pour stdin : lecture selon un certain format dans un fichier des zones de MS spécifiques (MS-DOS zone DIR). Le
répertoire permet d'accéder au noeud descripteur d'un fichier
[Link] Formatages sur chaines de car qu'il contient. Ce noeud permettra de connaître la localisation
int sprintf(char *ch, format, liste_vals) et l'ordonnancement des blocs contenant les données de ce
écriture formatée dans une chaîne. fichier. Par la suite, on supposera des répertoires de même
nature que les fichiers.
int sscanf(char *ch, format, liste_ptrs)
lecture selon un certain format dans une chaîne 6.3.2 Allocation de mémoire secondaire
[Link] Manipulation de chaînes [Link] Support séquentiel (bande)
- pistes longitudinales (1 car/ 8|16 pistes //)
int strlen(char *s) : longueur de s - densité d'enregistrement en bpi (1600..6000)
char *strcat(char *dst, *src) - blocs séparés par des gap inter-bloc (2 cm)
char *strncat(char *dst, *src, int n) - fichiers séparés par des gaps inter-fichier
concaténation (bornée par n) - entêtes de blocs et de fichiers permettant le positionnement.
- on ne modifie jamais directement une bande.
strcmp(char *s1,*s2) strncmp(char *s1, *s2, int n)
- les maj sont effectuées lors de la recopie sur une autre bande.
comparaison (bornée par n) - faible coût, accès lent ==> archives, copies, sauvegardes

char *strcpy(char*dst,*src) char *strncpy(dst,src,n)

copie (bornée par n)

char*strchr(char *s,char c) : recherche du 1er c dans s

char *strpbrk(char *s1, char *s2)
recherche d’un char de s2 dans s1
Systèmes d’exploitation Les processus Unix 96 Systèmes d’exploitation Les processus Unix 97

[Link] Support adressable (disque) Allocation contigüe

Espace adressable numéroté (0..b-1) de b blocs. L'accès à
deux blocs consécutifs est peu coûteux (translation et rotation Ex : fic1 (b0..b3); fic2(b9..b12); …; fick(b5..b6)
minimale de la tête de lecture/écriture). Remarquons que la
• temps d'accès séquentiel et direct optimal
numérotation logique des blocs ne correspond pas à la
• noeud descripteur contenant blocDebut, nbBlocs
topologie (facteur d'entrelacement).
• peu utilisé car les fichiers ont des tailles dynamiques ==>
surévaluation a priori des volumes fichiers, réorganisations
2 problèmes :
fréquentes et coûteuses lors des augmentations de volume.
• disponibilité ou occupation d'un bloc • utilisation pour les tables systèmes de taille fixe :
• localisation et ordonnancement des blocs d'un fichier MS-DOS : boot, FAT1, FAT2, DIR
Unix : boot, SF type, i-node table
Gestion des blocs disponibles Problème de l'allocation dynamique (=new, malloc)
lors d'une demande de n blocs libres, le système doit chercher
Une liste des blocs libres doit être maintenue afin de gérer les un trou (suite de blocs libres) suffisament grand parmi les
créations et destructions de fichiers. trous de l'espace disque.
Stratégies
implémentations : • Premier trouvé ("First-Fit") : on parcours la liste des trous
• tableau de bits : 0100011111101…110 (mot de b bits) jusqu'à en avoir trouvé un assez grand.
demande bloc : chercher le 1° 0 dans la liste puis 0 -> 1 • Plus Petit ("Best-Fit") : on cherche dans toute la liste la
rejet bloc : 1 -> 0 borne supérieure des trous => parcours intégral ou liste des
trous triée et recherche dicho.
• considérer cette liste des blocs libres comme un fichier, donc • Plus Grand ("Worst-Fit") : inverse de Best-Fit.
utiliser une des méthodes d'allocation suivantes.
Des simulations ont prouvées la meilleure performance de BF et FF en temps et
en espace utilisé. Lorsque l'espace libre est suffisant mais qu'il n'existe pas de
trou assez grand, cette fragmentation externe implique un compactage des
fichiers.

Systèmes d’exploitation Les processus Unix 98 Systèmes d’exploitation Les processus Unix 99

Allocation chaînée Allocation chaînée déportée

On déporte le chaînage dans une table système (FAT pour
Les blocs de données d'un fichier contiennent un pointeur sur
MS-DOS) dont chaque entrée pointe sur le bloc de données
le bloc suivant. Le noeud descripteur contient, lui, la tête de
suivant du fichier. La tête de liste est positionnée dans le
liste. Lors de la création, la tête est mise à nil, puis, au fur et à
noeud descripteur. Cette table de chaînage est chargée en MC
mesure des demandes, une allocation contigüe (optimale en
(volume courant) afin de permettre des accès directs rapides.
temps d'accès) est tentée. Si celle-ci ne peut avoir lieu, on
choisit le(s) premier bloc disponible.
Avantage
• Accès direct et séquentiel peu coûteux
Avantage
Inconvénients
• plus de fragmentation externe donc seule limitation = taille
• fragmentation interne (compactages périodiques)
espace disque libre.
• accès direct après parcours de la liste en MC
Inconvénients
Allocation indirecte (indexée)
• Accès séquentiel seulement !
Un bloc d'index contient la liste des pointeurs sur les blocs de
• fragmentation interne des fichiers nécessitant de nombreux
données du fichier. Ce bloc d'index est lui-même pointé par un
mouvements de tête. Des utilitaires de compactage permettent
champ du noeud descripteur de fichier. A la création le bloc
la réorganisation périodique des fichiers en allocation
d'index est initialisé à nil, nil, …, nil et lors des écritures
contigüe.
successives, les premiers pointeurs sont affectés des adresses
des blocs alloués par le gestionnaire de mémoire disponible. Ici
• fiabilité : si un pointeur est détruit logiciellement ou
encore la contiguïté est tentée ! A l'ouverture, le bloc index est
matériellement (bloc illisible) on perd tout le reste du fichier.
chargé en MC afin de permettre les accès.
• encombrement disque dû aux pointeurs si blocs de petite
taille
Systèmes d’exploitation Les processus Unix 100 Systèmes d’exploitation Les processus Unix 101

Avantage 6.4 Exemples

• accès direct et séquentiel rapide

Inconvénients 6.4.1 Le SGF MS-DOS

• fragmentation interne => compactages périodiques
• taille gaspillée dans les blocs d'index >> taille des pointeurs Nous décrivons ci-après l'organisation physique d'un volume
en alloc chaînée. MS-DOS sous la forme d'une disquette 5,25 pouces. Les
• petits fichiers : pour 2 ou 3 adresses de blocs, on monopolise principes d'allocation de MS-DOS restent les-mêmes quel que
un bloc index ! soit le support adressable, seuls le nombre et la taille des
• très grands fichiers : un bloc index étant insuffisant, champs varient.
plusieurs blocs index peuvent être chaînés et un mécanisme de
multiple indirection peut être utilisé. Une disquette, ou disque souple ou "floppy disk", est constituée d'un support
plastique mince de forme discale d'un rayon de 5,25 pouces (1 pouce = 2,54 cm)
sur lequel a été déposé un substrat magnétique. Dans le cas de disquettes double
face double densité, cette surface homogène de particules magnétisables est
Allocation directe
structurée en 2 faces de 40 pistes possédant chacune 9 secteurs. Les pistes
concentriques sont numérotées de 0 à 39 depuis l'extérieur vers l'intérieur.
Le noeud descripteur contient tous les pointeurs sur les blocs Chaque secteur contient 512 octets utiles. La capacité d'une disquette est donc
de données. De taille fixe et petite, cette structure de données de 2 * 40 * 9 * 512 = 360 Koctets.
ne pourra être utilisée que pour des fichiers de faible volume.

Avantage L'unité d'allocation ("cluster"), ou bloc, est la plus petite partie d'espace
mémoire allouable sur une disquette. Pour une disquette 5,25 pouces à 360 Ko,
• accès direct et séquentiel très rapide
un bloc est constitué de deux secteurs consécutifs et a donc une capacité d'1
• peut être mixtée avec indirection ou chaînage Ko. La numérotation des secteurs est effectuée de la façon suivante :

Inconvénients Face 0 Piste 0 Secteurs 0 à 8

• taille limitée des fichiers Face 1 Piste 0 Secteurs 9 à 17
• fragmentation interne Face 0 Piste 1 Secteurs 18 à 26
Face 1 Piste 1 Secteurs 27 à 35 etc…

Systèmes d’exploitation Les processus Unix 102 Systèmes d’exploitation Les processus Unix 103

Fichier et catalogue FCB

Un fichier MS-DOS est une suite d'octets désigné par un identifiant composé 0..7 nom du fichier sur 8 octets
d'un nom de 8 caractères et d'une extension de 3 caractères. Par exemple, 8..15 extension sur 3 octets attribut réservé par MS-DOS
[Link], [Link], [Link], [Link]… 16..23 réservé par MS-DOS heure modificat
24..31 date modificat. 1° entrée FAT Taille fichier (LSB, MSB)
Un catalogue ("directory") MS-DOS est un type de fichier particulier
permettant de regrouper différents fichiers de données et/ou d'autres catalogues L'octet d'attribut permet de spécifier certaines protections : fichier caché,
dans une même entité. L'architecture du Système de Fichiers est donc une lecture seulement, archive, système, normal ou encore de préciser que le fichier
arborescence dont toutes les feuilles sont des fichiers et tous les nœuds est un catalogue. L'heure et la date de dernière modification permettent de
intermédiaires des catalogues. Le catalogue racine est désigné par un retrouver la dernière version d'un fichier de travail. La taille du fichier est codé
"backslash" \ et est stocké en début de disquette. sur 32 bits ce qui permet une taille maximale de 4 Giga-octets ! Ce qui est bien
entendu impossible sur une disquette de 360 Ko. Enfin, la 1ère entrée dans la
FAT permet d'indiquer le premier maillon du chaînage dans la FAT qui
Allocation pointera lui-même sur le second qui pointera sur le troisième etc…

Les fichiers sont fragmentés en allocation chaînée déportée et MS-DOS

conserve dans une table l'adresse des différents fragments. Cette table s'appelle la FAT
Table d'Allocation des Fichiers ("File Allocation Table") et sera désignée par la
suite par FAT. Deux copies de la FAT sont stockées sur la disquette (secteurs C'est une table d'entrées d'une longueur de 12 bits (1,5 octets) qui spécifie le
1,2 et 3,4) afin de garantir la sécurité des données en cas de destruction chaînage permettant de reconstituer un fichier fragmenté sur plusieurs blocs.
accidentelle d'une des deux copies. Le catalogue général (racine) de la Les deux premières entrées (0 et 1) de cette table sont réservées par le système
disquette est lui situé sur les secteurs 5 à 11. Le secteur 0, quant à lui, contient pour préciser le type de la disquette sur laquelle elle se trouve (simple/double
le programme d'amorçage sur les disquettes systèmes ("boot-strap"). Enfin les face, simple/double densité). L'entrée numéro 2 correspond au premier bloc de
secteurs 12 à 719 contiennent les données des différents fichiers. la disquette non réservé au système, c'est-à-dire le bloc n° 6 (secteurs 12 et 13).
Ainsi le fichier dont le "1° entrée FAT" de son entrée de répertoire est 2 verra
son premier bloc de données situé sur les secteurs 12 et 13. Dans cette première
catalogue racine entrée FAT on trouve la valeur de l'entrée suivante, par exemple 005, qui
correspond au bloc de données suivant.
C'est une table dont les entrées ("File Control Block") ont une longueur de 32
octets qui décrivent les fichiers et les sous-catalogues. Une entrée de répertoire
peut être schématisée de la façon suivante :
Systèmes d’exploitation Les processus Unix 104 Systèmes d’exploitation Les processus Unix 105

exemple de FAT La VFAT 32

type disquette 005 000 i … FFF …
0 1 2 3 4 5 6 … i Nouveau standard de FAT permettant de gérer des disques
1° bloc du fichier 2° bloc du fichier indique la fin durs de grande capacité (>2Go) :
= bloc n° 6 = bloc n° 9 du chaînage • Entrées de FAT sur 12, 16 ou 32 bits permettant des petits
clusters ;
Dans cet exemple, le fichier est contenu sur trois blocs (6, 9 et i+4). La fin du
chaînage est indiqué par la valeur 0FFFH (nil) tandis qu'une valeur 000 indique
• FCB sur 32, 37 ou 44 octets (FCB étendu).
un bloc libre. La gestion des blocs libres (table de "12 bits") est en effet couplé
au mécanisme de FAT.
Exemple : disquette 1.4 Mo
Deux remarques
- Les entrées du répertoire racine ne sont pas compactées et la valeur 0E5H Volume :
située sur le premier octet d'un FCB signifie que cette entrée est libre. Soit • 80 pistes/face : 160 pistes
cette entrée n'a jamais été utilisée pour décrire un fichier ou un catalogue, soit
ce fichier ou ce catalogue a été détruit (delete ou rmdir) et le système a
• 18 secteurs/piste : 2880 secteurs
simplement surchargé le premier octet du nom du fichier par un code 0E5H. • 512 octets/secteurs : 1440 Ko soit 1.40 Mo
Par conséquent, la recherche d'un nom dans le catalogue général est effectuée • 1 secteur/cluster
séquentiellement sur toutes les entrées. On aurait pu tout aussi bien choisir de
compacter les entrées du catalogue à chaque destruction de fichier, ce qui aurait FAT
diminué le temps de recherche d'un fichier n'existant pas ! Mais cela aurait
interdit les utilitaires de récupération de fichiers détruits (undelete).
• 1 FAT : 9 secteurs * 2 copies ;
- La seconde remarque concerne la fragmentation des fichiers sur la disquette. • Entrée de FAT : 12 bits ;
Au bout d'un certain nombre de créations et de destructions de fichiers et de • 3072 entrées (2880 clusters)
répertoires, les différents blocs supportant les données d'un fichier se trouvent
être disséminés sur la disquette. Or le transfert en mémoire centrale de tous les Répertoire racine :
blocs de ce fichier va nécessiter un grand nombre de mouvements de
translations du bras de lecture. C'est pourquoi il existe des utilitaires de
• Répertoire racine sur 14 secteurs
compactage des blocs des fichiers d'une disquette permettant de minimiser les • FCB sur 32 octets
temps d'accès à un fichier. • soit 224 entrées

Taux de transfert : 500 Kbits/s

Les noms longs de fichiers de WinX sont stockés dans le FCB
suivant immédiat codé en Unicode.

Systèmes d’exploitation Les processus Unix 106 Systèmes d’exploitation Les processus Unix 107

6.4.2 Le SGF d'Unix 7. Conclusion

Exemple d'une arborescence de fichiers Unix Il est absolument indispensable de comprendre les concepts
2 /
de base des machines et des systèmes afin :

bin usr dev - de manipuler différents systèmes d’exploitation en

6 8
comprenant les différences et les ressemblances ;
5

ls cat dupont durand prt1 hda2 - d’évaluer correctement les résultats numériques fournis par
3 12 10 14 7 les machines (précision) ;
15

data1 prg1 prg2 data2 - de programmer intelligemment les algorithmes dont on a

minimisé la complexité (des E/S fréquentes peuvent ruiner
19 18 13 11
un algorithme d’une complexité inférieure à un autre) ;
• catalogues : bin, usr, dev, dupont, durant; - de pouvoir optimiser les parties de programme les plus
• fichiers ordinaires : ls, cat , data1, prg1, prg2, data2;
utilisées en les réécrivant en langage de bas niveau (C) ;
• fichiers périphériques : sous le catalogue dev ("device") : prt1, dsk2.

Caractéristiques - d’écrire des compilateurs ou des interpréteurs performants

• Entrées/Sorties généralisées ou transparentes même si ceux-ci sont écrits en langage de haut niveau ;
• désignation : chemin d'accès absolu /…, ou relatif
• fichiers non structurés = suite d'octets numérotés logiquement de 0 à n-1 (n = - de se préparer à l’arrivée de nouveaux paradigmes de
longueur du fichier) : structuration à la charge des programmeurs programmation (programmation parallèle) ;
• accès direct à une suite d'octet à partir d'une position i dans le fichier (0 ≤ i ≤
n-1) et/ou accès séquentiel - d’oser utiliser des systèmes d’exploitation dont le code
• catalogues Unix = liste (nom de fichier, # i-node)
source est connu !
• identification = # i-node
• désignations multiples : compteurs de liens ou de références
• système de protection : rwx rwx rwx propriétaire groupe autres