Architecture Machine

Cours et exercices corrigs

SCIENCES SUP

ARCHITECTURE DES MACHINES

ET DES SYSTMESINFORMATIQUES

3e dition

Alain CazesJolle Delacroix

coles dingnieurs IUT Licence 1re, 2e et 3e annes

ARCHITECTUREDES MACHINES


LinuxProgrammation systme et rseau2e ditionJolle Delacroix352 pagesDunod, 2007

Bases de donnes et modles de calculOutils et mthodes pour lutilisateur 4e ditionJean-Luc Hainaut440 pagesDunod, 2005

ARCHITECTUREDES MACHINES


Cours et exercices corrigs

Alain CazesMatre de confrences en informatique

au Conservatoire National des Arts et Mtiers

Jolle DelacroixMatre de confrences en informatique

au Conservatoire National des Arts et Mtiers

3e dition

Illustration de couverture : digitalvision

Dunod, Paris, 2003, 2005, 2008ISBN 978-2-10-053945-1

Table des matires

CHAPITRE 1 STRUCTURE GNRALE ET FONCTIONNEMENT DUN ORDINATEUR 1

1.1 Introduction 1

1.2 Structure et fonctionnement dun ordinateur 31.2.1 Structure gnrale dun ordinateur 31.2.2 La mmoire centrale 41.2.3 Le bus de communication 81.2.4 Le processeur central ou microprocesseur 10

1.3 Fonctionnement : relation microprocesseur / mmoire centrale 13

1.4 Un exemple 151.4.1 Le problme 151.4.2 Lordinateur 151.4.3 Le langage machine 15

1.5 Les units dchanges 16

1.6 Conclusion 17

PARTIE 1 PRODUCTION DE PROGRAMMES

CHAPITRE 2 DU PROBLME AU PROGRAMME MACHINE 23

2.1 Du problme au programme 232.1.1 Rappel du rle dun ordinateur 232.1.2 Problme, algorithme, programme et instructions 25

VI Architecture des machines et des systmes informatiques

2.2 Les diffrents niveaux de langage de lordinateur 262.2.1 Langage machine 272.2.2 Langage dassemblage 282.2.3 Langage de haut niveau ou volu 29

2.3 Introduction la chane de production de programmes 302.4 Un exemple 312.5 Conclusion 33

CHAPITRE 3 LA CHANE DE PRODUCTION DE PROGRAMMES 35

3.1 La compilation 363.1.1 Grammaire et structure dun langage de haut niveau 363.1.2 Analyse lexicale 383.1.3 Analyse syntaxique 403.1.4 Analyse smantique 423.1.5 Gnration du code final 44

3.2 Ldition des liens 463.2.1 Rle de lditeur de liens 463.2.2 Fonctionnement de lditeur de liens 47

3.3 Le chargement 593.3.1 Rle du chargeur 593.3.2 Chargement et dition des liens dynamique 61

3.4 Lutilitaire Make 623.4.1 Format du fichier Makefile 623.4.2 Fonctionnement de lutilitaire Make 63

3.5 Conclusion 64

CHAPITRE 4 LE LANGAGE MACHINE ET LA REPRSENTATION DES INFORMATIONS 65

4.1 La reprsentation des informations 654.1.1 Numration binaire, octale et hexadcimale 664.1.2 Reprsentation des nombres signs 694.1.3 Reprsentation des nombres flottants 744.1.4 Reprsentation des caractres 77

4.2 Les instructions machine 794.2.1 Les diffrents types dinstructions 804.2.2 Les diffrents types doprandes 814.2.3 Un exemple 82

4.3 Les instructions du langage dassemblage 844.3.1 Format dune instruction du langage dassemblage 854.3.2 Fonctionnement de lassembleur 87

4.4 Conclusion 89

Table des matires VII

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

CHAPITRE 5 LES CIRCUITS LOGIQUES 90

5.1 Les circuits logiques 905.1.1 Dfinition 905.1.2 Les circuits combinatoires 915.1.3 Les circuits squentiels 995.1.4 Technologie des circuits logiques 101

5.2 Le futur 106

CHAPITRE 6 EXERCICES CORRIGS 108

Production de programmes 1086.1 Compilation 1086.2 dition des liens 1106.3 Utilitaire Make 1116.4 Compilation 111Reprsentation des informations 1126.5 Conversions 1126.6 Reprsentation des nombres signs 1126.7 Reprsentation des nombres flottants 1136.8 Synthse 113Langage machine 1136.9 Manipulation des modes dadressage 1176.10 Programme assembleur 1176.11 Manipulation de la pile 1186.12 Programme assembleur 119

SOLUTIONS 120

PARTIE 2 STRUCTURE DE LORDINATEUR

CHAPITRE 7 LA FONCTION DEXCUTION 129

7.1 Introduction 1297.2 Aspects externes 132

7.2.1 Le microprocesseur 1327.2.2 Les bus 134

7.3 Aspects internes 1367.3.1 Excution dune instruction machine 1377.3.2 Microcommandes et micro-instructions 145

7.4 Les interruptions : modification du flux dexcution dun programme machine 1547.4.1 Principe des interruptions 1547.4.2 Un exemple 158

VIII Architecture des machines et des systmes informatiques

7.5 Amlioration des performances 1627.5.1 Paralllisme des instructions 1637.5.2 Paralllisme des processeurs 165

7.6 Conclusion 166

CHAPITRE 8 LA FONCTION DE MMORISATION 168

8.1 Gnralits 1688.2 Mmoires de travail 171

8.2.1 Les mmoires vives 1718.2.2 Les mmoires mortes 1808.2.3 Les registres 180

8.3 Mmoires de stockage : le disque magntique 1818.3.1 Caractristiques gnrales 1828.3.2 Organisation gnrale 182

8.4 Amlioration des performances 1848.4.1 Les mmoires caches 1848.4.2 Mmoire virtuelle 195

8.5 Complments : approches CISC/RISC 1988.5.1 Les performances dun processeur 1998.5.2 La traduction des programmes 2008.5.3 Approche CISC 2008.5.4 Approche RISC 2018.5.5 Pour conclure sur les RISC et les CISC 202

8.6 Conclusion 203

CHAPITRE 9 LA FONCTION DE COMMUNICATION 205

9.1 Introduction 2059.2 Les bus 210

9.2.1 Les bus ISA (ou PC-AT), MCA et EISA 2119.2.2 Le bus PCI (Peripherical Component Interconnect) 2129.2.3 Le bus AGP (Accelerated Graphics Port) 2169.2.4 Deux exemples 217

9.3 Les interfaces daccs aux priphriques 2189.3.1 Les units dchanges 2199.3.2 Les bus dextension 232

9.4 Les diffrents modles de gestion des entres-sorties 2369.4.1 La liaison programme 2379.4.2 Entres-sorties pilotes par les interruptions 2399.4.3 Gestion des entres-sorties asynchrones 241

9.5 Conclusion 244

Table des matires IX

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.


La fonction dexcution 24510.1 Rvision 24510.2 Microcommandes 24510.3 CISC/RISC 246

La fonction de mmorisation 24710.4 Cache correspondance directe 24710.5 Calcul de la taille relle dun cache 24710.6 Cache associatif et remplacement de lignes 24710.7 Cache correspondance directe 248

La fonction de communication 24810.8 Questions de cours 24810.9 Entres-sorties programmes et entres-sorties par interruption 24810.10 Performances des oprations dentres-sorties 24910.11 Gestion des interruptions 249

Synthse 25010.12 Exercice de synthse 250

SOLUTIONS 253

PARTIE 3 LES SYSTMES DEXPLOITATION

CHAPITRE 11 INTRODUCTION AUX SYSTMES DEXPLOITATION MULTIPROGRAMMS 265

11.1 Rle et dfinition dun systme dexploitation multiprogramm 26511.1.1 Un premier rle : assurer le partage de la machine physique 26711.1.2 Un second rle : rendre conviviale la machine physique 26711.1.3 Dfinition du systme dexploitation multiprogramm 268

11.2 Structure dun systme dexploitation multiprogramm 26911.2.1 Composants dun systme dexploitation 26911.2.2 La norme POSIX pour les systmes ouverts 271

11.3 Principaux types de systmes dexploitations multiprogramms 27111.3.1 Les systmes traitements par lots 27211.3.2 Les systmes interactifs 27411.3.3 Les systmes temps rel 275

11.4 Notions de base 27611.4.1 Modes dexcutions et commutations de contexte 27711.4.2 Gestion des interruptions matrielles et logicielles 27911.4.3 Langage de commande 282

X Architecture des machines et des systmes informatiques

11.5 Gnration et chargement dun systme dexploitation 28511.5.1 Gnration dun systme dexploitation 28511.5.2 Chargement dun systme dexploitation 286

11.6 Conclusion 286

CHAPITRE 12 GESTION DE LEXCUTION DES PROGRAMMES : LE PROCESSUS 288

12.1 Notion de processus 28812.1.1 Dfinitions 28812.1.2 tats dun processus 28912.1.3 Bloc de contrle du processus 29012.1.4 Oprations sur les processus 29112.1.5 Un exemple de processus : les processus Unix 292

12.2 Ordonnancement sur lunit centrale 29512.2.1 Ordonnancement premptif et non premptif 29512.2.2 Entits systmes responsable de lordonnancement 29712.2.3 Politiques dordonnancement 29712.2.4 Exemples 302

12.3 Synchronisation et communication entre processus 30412.3.1 Lexclusion mutuelle 30512.3.2 Le schma de lallocation de ressources 30912.3.3 Le schma lecteurs-rdacteurs 31012.3.4 Le schma producteur-consommateur 312

12.4 Conclusion 314

CHAPITRE 13 GESTION DE LA MMOIRE CENTRALE 315

13.1 Mmoire physique et mmoire logique 315

13.2 Allocation de la mmoire physique 31713.2.1 Allocation contigu de la mmoire physique 31713.2.2 Allocation non contigu de la mmoire physique 323

13.3 Mmoire virtuelle 33613.3.1 Principe de la mmoire virtuelle 33613.3.2 Le dfaut de page 33913.3.3 Le remplacement de pages 34113.3.4 Performance 34413.3.5 Exemples 34513.3.6 Notion dcroulement 346

13.4 Swapping des processus 347

13.5 Conclusion 347

Table des matires XI

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

CHAPITRE 14 SYSTME DE GESTION DE FICHIERS 348

14.1 Le fichier logique 34814.1.1 Dfinition 34814.1.2 Les modes daccs 34914.1.3 Exemples 351

14.2 Le fichier physique 35414.2.1 Structure du disque dur 35414.2.2 Mthodes dallocation de la mmoire secondaire 355

14.3 Correspondance fichier logique-fichier physique 36614.3.1 Notion de rpertoire 36614.3.2 Ralisation des oprations 372

14.4 Protection 37914.4.1 Protection contre les accs inappropris 37914.4.2 Protection contre les dgts physiques 380

14.5 Conclusion 381

CHAPITRE 15 INTRODUCTION AUX RSEAUX 383

15.1 Dfinition 383

15.2 Les rseaux filaires 38515.2.1 Architecture des rseaux filaires 38515.2.2 Circulation des informations 39315.2.3 Exemple de rseau filaire 396

15.3 Les rseaux sans fil 39915.3.1 Architecture des rseaux sans fil 40015.3.2 Circulation des informations 40215.3.3 Exemples de rseaux sans fil 407

15.4 Linterconnexion de rseaux : Internet 40915.4.1 Architecture de lInternet 41015.4.2 Circulation de linformation 410


Ordonnancement de processus 41416.1 Algorithmes dordonnancement 41416.2 Ordonnancement par priorit premptif et non premptif 41416.3 Chronogramme dexcutions 41516.4 Ordonnancement sous Unix 41516.5 Ordonnancement sous Linux 416

Synchronisation de processus 41716.6 Producteur(s)-Consommateurs(s) 417

XII Architecture des machines et des systmes informatiques

16.7 Allocations de ressources et interblocage 41716.8 Allocation de ressources et tats des processus 418

Gestion de la mmoire centrale 41916.9 Gestion de la mmoire par partitions variables 41916.10 Remplacement de pages 41916.11 Mmoire pagine et segmente 42016.12 Mmoire virtuelle et ordonnancement de processus 42016.13 Pagination la demande 421

Systme de gestion de fichiers 42216.14 Modes daccs 42216.15 Organisation de fichiers 42216.16 Noms de fichiers et droits daccs 42216.17 Algorithmes de services des requtes disque 42316.18 Fichiers Unix 42316.19 Systme de gestion de fichiers FAT 42316.20 Systme de gestion Unix 42416.21 Synthse 424

SOLUTIONS 427

INDEX 445

Chapitre 1

Structure gnrale et fonctionnement

dun ordinateur1

Dans cette partie introductive nous rappelons quelques lments fondamentaux concer-nant la programmation et lalgorithmique afin de prsenter le vocabulaire utilis. Ilne sagit en aucune manire de se substituer un cours dalgorithmique mais unique-ment de replacer du vocabulaire du point de vue de la structure gnrale dun ordina-teur, lobjectif tant de mettre en vidence les diffrentes phases qui interviennentdans la rsolution dun problme avec un ordinateur. Aprs cette partie introductivenous prsentons les principaux modules constituant larchitecture dun ordinateurtype. Nous faisons un tour dhorizon des fonctionnalits de chacun de ces moduleset de leurs relations fonctionnelles. Il sagit ici uniquement de prsenter de manireglobale le fonctionnement de lordinateur.

1.1 INTRODUCTION

Le rle de linformatique est de rsoudre des problmes laide dun ordinateur. Unproblme sexprime sous la forme dun nonc qui spcifie les fonctions que lonsouhaite raliser. Par exemple dfinir toutes les fonctions dun traitement de texte.Pour rsoudre un problme les informaticiens utilisent la notion dalgorithme.

Pour illustrer cette notion, prenons lexemple du problme suivant : confectionnerune omelette avec 6 ufs.

2 1 Structure gnrale et fonctionnement dun ordinateur

Trouver une solution ce problme repose sur lexistence dun processeur sachantexcuter une instruction (confectionner). En gnral un adulte saura excuter linstruc-tion confectionner, cest--dire connatra le sens du mot, et sera capable de fairetoutes les actions ncessaires permettant de rsoudre le problme. On dira alors queladulte est un bon processeur au sens o il saura excuter linstruction confec-tionner portant sur la donne ufs. Par contre un enfant pourra ne pas connatre lemot confectionner : il ne saura pas faire les oprations ncessaires et ne pourra doncpas rsoudre le problme pos (faire une omelette). Lenfant connat dautres instruc-tions, sait excuter dautres actions que confectionner, et pour quil puisse rsoudrele problme il faudra lexprimer autrement, sur la base des actions, instructions,quil est capable dexcuter. Pour que lenfant puisse rsoudre le problme on pourralexprimer sous la forme dune squence dinstructions appartenant au langage delenfant. Par exemple on pourra exprimer le problme, la solution, sous la forme dela squence des instructions suivantes :1. casser 6 ufs dans un bol;2. battre les ufs avec un fouet;3. saler, poivrer ;4. placer la pole sur le gaz;5. allumer le gaz ;6. cuisiner les ufs ;7. teindre le gaz.

Dans cet exemple, le processeur enfant sait excuter des instructions (casser, battre,saler, poivrer, allumer, cuisiner). De plus il connat les objets manipuler (ufs,gaz, pole). On dit alors que le processeur enfant est un bon processeur pourexcuter lalgorithme reprsent par la squence prcdente puisque lenfant estcapable dexcuter cette squence dinstructions. Cette squence dinstructions excu-tables par le processeur enfant est une solution du problme pos pour ce processeur.

Un algorithme peut donc se dfinir comme une squence dinstructions excuta-bles par un processeur dtermin. Cette squence dinstructions, cet algorithme, estune solution au problme pos.

De ce petit exemple nous pouvons tirer quelques conclusions : un algorithme est une solution un problme pos; un algorithme est une squence dinstructions excutables par un processeur; un algorithme est un programme excutable par un processeur dtermin; un algorithme na de sens que pour un processeur dtermin.

Les instructions expriment les actions que peut excuter un processeur, elles sontcodes partir dun alphabet (dans notre cas lalphabet habituel). Les instructionsmanipulent des donnes (ufs, sel, poivre, gaz, pole). Un processeur (ou machinevirtuelle) est une entit capable dexcuter des instructions portant sur des donnes.Lensemble des instructions que le processeur (la machine virtuelle) peut manipuler,constitue son langage de programmation. Ainsi le langage de programmation duprocesseur dfinit compltement ce processeur. Il y a quivalence totale entre la

1.2 Structure et fonctionnement dun ordinateur 3

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

machine virtuelle et son langage de programmation. Aussi, connatre le langage deprogrammation dune machine virtuelle quivaut connatre les capacits dexcu-tion de cette machine.

En rsum rsoudre un problme avec une machine virtuelle consiste construireune squence dinstructions pour cette machine ( partir de son langage de program-mation) telle que lexcution de cette squence soit une solution ce problme. Eninformatique la machine cible, celle avec laquelle nous devons rsoudre les problmes,est lordinateur. Nous devons donc connatre les caractristiques de cette machine,tout particulirement son langage de programmation (les instructions quelle estcapable dexcuter), lalphabet permettant de coder les instructions ainsi que lesdonnes et les outils permettant dexcuter ces instructions.

Les instructions dun ordinateur sont les instructions machines, elles constituent lelangage de programmation de lordinateur : le langage machine. Rsoudre un problmeavec un ordinateur consiste donc exprimer ce problme sous la forme dunesquence dinstructions machines que nous devrons soumettre aux outils permettantlexcution de cette squence. Cette squence dinstructions machine excutablespar lordinateur sappelle le programme machine.

1.2 STRUCTURE ET FONCTIONNEMENT DUN ORDINATEUR

Aprs ce bref rappel sur la manire algorithmique de rsoudre un problme nousallons nous intresser la rsolution dun problme avec comme machine cible unordinateur. Pour cela nous donnons tout dabord une prsentation de la structurematrielle dun ordinateur, de son fonctionnement, pour ainsi en dduire commenton peut laide dun ordinateur, rsoudre un problme. Lordinateur cible nousservant de support descriptif est un ordinateur de type Von Neumann qui caractrisebien la quasi-totalit des ordinateurs actuels. Il est compos des lments suivants : une mmoire centrale pour le stockage des informations (programme et donnes); un microprocesseur ou processeur central pour le traitement des informations

loges dans la mmoire centrale; des units de contrle des priphriques et des priphriques; un bus de communication entre ces diffrents modules.

1.2.1 Structure gnrale dun ordinateur

La figure 1.1 prsente lorganisation gnrale dun ordinateur. On y trouve deux partiesprincipales : le processeur comprenant les modules mmoire centrale, processeur central (micro-

processeur), les units dchange et le bus de communication entre ces diffrentsmodules;


les priphriques avec lesquels dialogue le processeur au travers des units dchange(ou contrleurs). On distingue en gnral : les priphriques dentre tels que le clavier ou la souris; les priphriques de sortie tels que les imprimantes et les crans de visualisation; les priphriques dentre et de sortie tels que les disques magntiques ou les

modems pour accder aux rseaux de communication.

Globalement le processeur permet lexcution dun programme. Chaque proces-seur dispose dun langage de programmation (les instructions machine) spcifique.Ainsi rsoudre un problme avec un processeur consiste exprimer ce problmecomme une suite de ses instructions machine. La solution un problme est doncspcifique de chaque processeur. Le programme machine et les donnes qui sontmanipules par les instructions machine sont placs dans la mmoire centrale.

Examinons prsent plus en dtail la composition et les fonctions de chacun desmodules composant le processeur.

1.2.2 La mmoire centrale

La mmoire centrale assure la fonction de stockage de linformation qui peut tremanipule par le microprocesseur (processeur central), cest--dire le programmemachine accompagn de ses donnes. En effet, le microprocesseur nest capabledexcuter une instruction que si elle est place dans la mmoire centrale.

d' changeMmoirecentrale

Bus

ProcesseurcentralHorloge

Unit dchange

Mmoirecache

Rseau

Figure 1.1 Structure matrielle gnrale.


Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

Cette mmoire est constitue de circuits lmentaires nomms bits (binary digit).Il sagit de circuits lectroniques qui prsentent deux tats stables cods sous laforme dun 0 ou dun 1. De par sa structure la mmoire centrale permet donc decoder les informations sur la base dun alphabet binaire et toute information stockeen mmoire centrale est reprsente sous la forme dune suite de digits binaires. Lafigure 1.2 prsente lorganisation gnrale dune mmoire centrale.

Pour stocker linformation la mmoire est dcoupe en cellules mmoires : lesmots mmoires. Chaque mot est constitu par un certain nombre de bits qui dfinis-sent sa taille. On peut ainsi trouver des mots de 1 bit, 4 bits (quartet) ou encore 8 bits(octet ou byte), 16 bits voire 32 ou 64 bits. Chaque mot est repr dans la mmoirepar une adresse, un numro qui identifie le mot mmoire. Ainsi un mot est un conte-nant accessible par son adresse et la suite de digits binaires composant le mot repr-sente le contenu ou valeur de linformation.

La mmoire centrale est un module de stockage de linformation dont la valeur estcode sur des mots. Linformation est accessible par mot. La capacit de stockage dela mmoire est dfinie comme tant le nombre de mots constituant celle-ci. Danslexemple de la figure 1.2, notre mmoire a une capacit de 8 mots de 16 bitschacun. On exprime galement cette capacit en nombre doctets ou de bits. Notremmoire a donc une capacit de 16 octets ou de 128 bits. Linformation que lontrouve en mmoire centrale est donc code sur un alphabet binaire. La figure 1.3rappelle le nombre de combinaisons que lon peut raliser partir dune suitedlments binaires. Coder linformation en mmoire centrale cest donc associer chaque suite de bits un sens particulier.

1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 00 1 1 1 0 0 1 1 1 0 0 0 1 1 0 1

0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 11 0 0 0 1 1 0 0 0 1 1 1 0 0 1 01 0 0 0 1 0 0 1 0 1 0 1 0 1 1 01 0 0 0 1 1 0 0 0 1 1 1 0 0 1 00 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1

Busdonnes

Adresses mmoire

Mmoire centraleBus adressesBus de commandes

1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0

01234567

Mot mmoiredadresse 2

Figure 1.2 La mmoire centrale.


La figure 1.4 prsente succinctement les diffrentes informations que lon trouvedans la mmoire centrale : instructions machines et donnes manipules par lesinstructions.

x 2 combinaisons 0 1

xx 4 combinaisons 0 00 11 01 1

xxx 8 combinaisons 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1

n bits donnent 2n combinaisons diffrentes

Codage de linformation

0 1Bit Alphabet binaire

n 2n

0 11 22 43 84 165 326 647 1288 2569 512

10 1024

Figure 1.3 Codage binaire.

Numriques Non Numriques

Nbentiers positifs Nbentiers ngatifs

Nb Fractionnaires

Virgule fixe Virgule flottante

Signe+

valeur absolueC1 C2C1 C2

Code Opration Champ oprande

Instructions Donnes

Informations

0001 0100

Figure 1.4 Les diffrentes informations prsentes en mmoire centrale.


Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

Les instructions et les donnes sont codes sur des mots mmoires : elles peuventoccuper un ou plusieurs mots mmoires selon la nature de lordinateur. Les instruc-tions machines sont propres chaque microprocesseur mais sont toujours construitesde la mme manire : un code opration qui dfinit lopration excuter, le champoprande qui dfinit la ou les donnes sur lesquelles portent lopration : le code opration est cod sur un nombre de digits binaires qui caractrise un

microprocesseur. Ce nombre de bits dfinit en fait le nombre doprations possi-bles avec cet ordinateur : un code opration sur 3 bits admet 8 combinaisonspermettant la dfinition de 8 oprations diffrentes (instructions machine) possi-bles, sur 4 bits 16 instructions possibles etc. La taille du code opration est doncun facteur dterminant qui caractrise compltement le nombre dinstructionsquest capable dexcuter un processeur;

le champ oprande est une suite de bits qui permet de caractriser ladresse de la oudes donne(s) que manipule(nt) linstruction machine dfinie par le code opra-tion. Il existe plusieurs types dinstructions machines qui peuvent manipuler uneou plusieurs donnes selon la puissance du langage machine du microproces-seur utilis. Il existe galement plusieurs manires de dfinir, partir du champoprande, ladresse dune donne : cela repose sur le mcanisme dadressage dunmicroprocesseur qui dfinit les diffrentes manires de calculer une adresse dedonnes. On parle galement de modes dadressages du microprocesseur.Les donnes sont les objets que manipulent les instructions, elles sont codes sur

un ou plusieurs mots machines et sont donc adressables (reprables) dans la mmoirecentrale. Ladresse de la donne est dtermine par le type dadressage utilis parlinstruction machine. Le codage dune donne en mmoire dpend de son type : lafigure 1.4 donne les diffrents types de donnes que manipulent les instructionsmachines. Pour chaque type il existe des rgles de codage. Par exemple pour coderles caractres alphanumriques on utilise un dictionnaire (table ASCII, table EBCDIC,codage Unicode) tandis que pour coder un nombre entier non sign on utilise unergle traditionnelle de codage dun nombre sur un alphabet binaire.

Dans lexemple de la figure 1.5, on suppose un nombre cod sur un octet (8 bits)dont la position de chaque bit est numrote de 0 7, en partant du bit de poids

01100101Octet

7 6 5 4 3 2 1 00 1 1 0 0 1 0 1

La valeur maximale dun entier sur p bits est 2p 1

Informations

Donnes

Nb entiers positifs

Position du bit

Valeur de loctet :

Soit 101 en base 100 27 1 26 1 25 0 24 0 23 1 22 0 21 1 20

Figure 1.5 Un exemple de codage de linformation.


faible. La valeur de lentier est alors la somme des produits de chaque bit par lenombre de symboles possibles dans la base dexpression du nombre (ici 2) lev lapuissance du rang du bit. Cette rgle est gnrale et permet de dterminer la valeurdun entier cod sur nimporte quel alphabet. Dans le cas dun alphabet binaire lavaleur maximale que peut prendre un entier cod sur p bits est 2p. Les principalesnormes de codages existantes lheure actuelle ainsi que la structure des instructionsmachine et les modes dadressages courants sont dtaills au chapitre 4.

La mmoire centrale a pour objet le stockage des instructions et des donnes quepeut manipuler le microprocesseur. Les oprations possibles sur la mmoire sont lalecture (acquisition par le microprocesseur) dun mot et lcriture (le microproces-seur place un nouveau contenu) dans un mot mmoire. Une opration de lecture dunmot consiste dfinir ladresse du mot et dclencher une commande de lecture quiamne le contenu du mot de la mmoire vers le microprocesseur. Une oprationdcriture consiste dfinir ladresse du mot dont on veut changer le contenu puis dclencher une opration dcriture qui transfre linformation du processeur vers lemot mmoire dont ladresse est spcifie.

Enfin dautres lments importants compltent la caractrisation dune mmoirecentrale : le temps daccs la mmoire qui mesure le temps ncessaire pour obtenir une

information loge en mmoire; les technologies qui prsident la construction de ces mmoires; le cot de ralisation de ces mmoires.

Nous reviendrons en dtail sur lensemble de ces points dans le chapitre sur lammorisation (chapitre 8).

1.2.3 Le bus de communication

Le bus de communication peut se reprsenter comme une nappe de fils transportantdes signaux et permettant lchange des informations entre les diffrents modules duprocesseur. Chaque fil transporte ou non un signal : il est prsent ou absent. Onreprsente par 1 un signal prsent et par 0 un signal absent. Le nombre de fils du busdtermine sa largeur et dfinit ainsi le nombre dinformations diffrentes que peutvhiculer le bus. Ainsi un bus de 3 fils permet une combinaison de 8 signaux diff-rents et donc reprsente 8 informations possibles diffrentes.

Le bus est construit comme un ensemble de trois bus : le bus dadresses transporte des combinaisons de signaux qui sont interprtes

comme des nombres entiers reprsentant ladresse dun mot mmoire. Par exemple,figure 1.6, le bus dadresses a une largeur de 3 fils et est donc capable de coderdes adresses allant de 0 7. Pour adresser un mot mmoire on fait appel un circuitde slection (dcodeur) qui en entre reoit n signaux (3 dans notre exemple) etfournit 2n signaux de sortie (8 dans notre exemple). Parmi les signaux de sortie unseul est positionn 1 tous les autres valant 0. Dans notre exemple, les sorties sontnumrotes de 0 7 et de haut en bas. Ainsi si la valeur dentre est 000, seule la


Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

sortie 0 vaut 1 et toutes les autres valent 0. Pour adresser le mot mmoire 2 lemicroprocesseur place sur le bus dadresses la chane 010 (qui a pour valeur 2 enbase 10), la sortie 1 du dcodeur vaut alors 1 et les autres valent 0. Ce circuit permetdonc de slectionner un mot mmoire dans la mmoire centrale. La largeur du busdadresses dfinit la capacit dadressage du microprocesseur et il ne faut pasconfondre capacit dadressage et taille physique de la mmoire;

le bus de donnes permet lchange des informations (les contenus) entre lesdiffrents modules. Dans notre exemple le bus de donnes a une largeur de 16 filset donc la taille des mots mmoires auxquels on peut accder ou dont on peut modi-fier le contenu est de 16 bits;

le bus de commandes : cest par ce bus que le microprocesseur indique la nature desoprations quil veut effectuer. Dans notre exemple il a une largeur dun fil et doncle microprocesseur ne peut passer que deux commandes (la lecture et lcriture).La figure 1.7 rsume les diffrents points abords concernant la mmoire et les

bus permettant la communication avec la mmoire. Sur cette figure 1.7, le bus

Bus

Tampon dentres-sorties

Selection

Mmoire centrale

Commandes

Adresse

Donnes Mot mmoire Bit

Largeurdes bus :

1 fil3 fils16 fils

Processeur

Figure 1.6 Bus de communication.


dadresses a une largeur de m bits, le bus de donnes une largeur de p bits ce quidtermine la capacit de stockage en bits de cette mmoire, soit 2m mots de p bits. Lebus de commandes permet de dterminer le type dopration (lecture ou criture)que lon souhaite raliser.

1.2.4 Le processeur central ou microprocesseur

Le microprocesseur (unit centrale) a pour objet dexcuter les instructions machinesplaces en mmoire centrale. La figure 1.8 prsente son architecture gnrale.

Lecture

criture

Donnes

Adresse

m bits

p bits

Mmoire

Bus dadresses

Bus de donnes

Mots

Bus de commandes

Fonctions : stockageprogramme et donnes

Units de stockage : Bit, Octet, Mot.

Adressage : Mot

Temps daccs.

Technologies.

Cots.

2m mots de p bits

Figure 1.7 Bus de communication et mmoire centrale.

Unit Arithmtiqueet Logique

Registres

Unit de Commande

Bus Processeur / Mmoire

SquenceurDcodeur

Commandes Lecture/critureAdressesDonnes

RICO

RADRDO

Donnes

Commandes

Bus interne

PSW

ZY1

Y2

Opration

Figure 1.8 Le microprocesseur.


Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

Il est constitu de quatre parties : lunit arithmtique et logique (UAL), les regis-tres, lunit commande et le bus de communication interne permettant lchange desdonnes et des commandes entre les diffrentes parties du microprocesseur.

Les registres

Ce sont des zones de mmorisation de linformation internes au microprocesseur. Ilssont de faible capacit et de temps daccs trs faible. Leur nombre et leur taille sontvariables en fonction du type de microprocesseur. Ils peuvent tre de type adresse(ils contiennent alors une adresse de mot mmoire) ou donnes (ils contiennent alorsle contenu dun mot mmoire). Ils peuvent tre spcifiques et avoir une fonction trsprcise (par exemple le registre pointeur de pile) ou gnraux et servir essentielle-ment aux calculs intermdiaires, par exemple, de lunit arithmtique et logique.

Lunit arithmtique et logique (UAL)

Ce module est charg de lexcution de tous les calculs que peut raliser le micro-processeur. Cette unit est constitue de lensemble des circuits arithmtiques etlogiques permettant au processeur deffectuer les oprations lmentaires nces-saires lexcution des instructions machine. Elle inclut donc les circuits daddition,de soustraction, de multiplication, de comparaison, etc. Dans ce module se trouventgalement des registres dont lobjet est de contenir les donnes sur lesquelles vontporter les oprations effectuer. Dans notre exemple, lUAL possde deux registresdentre (E1 et E2) et un registre de sortie (S).

Pour faire une addition : la premire donne est place dans E1 via le bus interne de donnes; la seconde donne est place dans E2 via le bus interne de donnes; la commande daddition est dlivre au circuit daddition via le bus interne de

commandes; le rsultat est plac dans le registre S.

Sur notre machine on note galement un registre particulier, le PSW (ProgramStatus Word), qui joue un rle fondamental de contrle de lexcution dun programmeet qui tout instant donne des informations importantes sur ltat de notre micropro-cesseur. Par exemple puisque nous travaillons sur des mots de longueur finie la valeurdun entier cod sur un mot ne peut dpasser la valeur maximale reprsentable sur cemot. Lorsque nous faisons laddition de deux entiers le rsultat peut avoir une valeurqui nest pas reprsentable sur un mot mmoire : il y a alors dpassement de capa-cit. Ce dpassement de capacit doit tre signal et not pour ne pas perturber lefonctionnement de lordinateur. Ce type dinformation est stock dans le PSW.

Lunit de commande

Elle excute les instructions machines et pour cela utilise les registres et lUAL dumicroprocesseur. On y trouve deux registres pour la manipulation des instructions(le compteur ordinal CO, le registre dinstruction RI), le dcodeur, le squenceur etdeux registres (le registre dadresses RAD et le registre de donnes RDO) permettant


la communication avec les autres modules via le bus. Enfin, via le bus de commandes,elle commande la lecture et/ou lcriture dans la mmoire centrale.

Le compteur ordinal CO

Cest un registre dadresses. chaque instant il contient ladresse de la prochaineinstruction excuter. Lors de lexcution dune instruction il est prvu, au cours decette excution, la modification du contenu du CO. Ainsi en fin dexcution delinstruction courante le compteur ordinal pointe sur la prochaine instruction excuteret le programme machine peut continuer se drouler.

Le registre dinstruction RI

Cest un registre de donnes. Il contient linstruction excuter.

Le dcodeur

Il sagit dun ensemble de circuits dont la fonction est didentifier linstruction excuter qui se trouve dans le registre RI, puis dindiquer au squenceur la nature decette instruction afin que ce dernier puisse dterminer la squence des actions raliser.

Le squenceur

Il sagit dun ensemble de circuits permettant lexcution effective de linstructionplace dans le registre RI. Le squenceur excute, rythm par lhorloge du micropro-cesseur, une squence de microcommandes (micro-instructions) ralisant le travailassoci cette instruction machine. Pour son fonctionnement le squenceur utiliseles registres et lUAL. Ainsi lexcution effective dune instruction machine se traduitpar lexcution dune squence de micro-instructions excutables par les circuits debase du microprocesseur. Nous reviendrons plus en dtail sur cet aspect des chosesdans le chapitre 7, consacr lexcution des instructions machines.

Le registre RAD

Cest un registre dadresses. Il est connect au bus dadresses et permet la slectiondun mot mmoire via le circuit de slection. Ladresse contenue dans le registreRAD est place sur le bus dadresses et devient la valeur dentre du circuit de slectionde la mmoire centrale qui va partir de cette entre slectionner le mot mmoirecorrespondant.

Le registre RDO

Cest un registre de donnes. Il permet lchange dinformations (contenu dun motmmoire) entre la mmoire centrale et le processeur (registre).

Ainsi lorsque le processeur doit excuter une instruction il : place le contenu du registre CO dans le registre RAD via le bus dadresses et le

circuit de slection; dclenche une commande de lecture mmoire via le bus de commandes; reoit dans le registre de donnes RDO, via le bus de donnes, linstruction;

1.3 Fonctionnement : relation microprocesseur / mmoire centrale 13

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

place le contenu du registre de donnes RDO dans le registre instruction RI via lebus interne du microprocesseur.Pour lire une donne le processeur :

place ladresse de la donne dans le registre dadresses RAD; dclenche une commande de lecture mmoire; reoit la donne dans le registre de donnes RDO; place le contenu de RDO dans un des registres du microprocesseur (registres gn-

raux ou registres dentre de lUAL).On dit que pour transfrer une information dun module lautre le microproces-

seur tablit un chemin de donnes permettant lchange dinformations. Par exemplepour acqurir une instruction depuis la mmoire centrale, le chemin de donnes estdu type : CO, RAD, commande de lecture puis RDO, RI.

1.3 FONCTIONNEMENT : RELATION MICROPROCESSEUR / MMOIRE CENTRALE

Lobjet de cette partie est de prsenter succinctement comment sexcute un programmemachine sur le matriel que nous venons de dfinir. Pour tre excutable une instruc-tion doit ncessairement tre prsente en mmoire centrale. La mmoire centralecontient donc des instructions et des donnes. De plus toutes les informations enmmoire sont codes sur un alphabet binaire. Les informations sont alors, quelle quesoit leur nature, des suites de 0 et de 1. Il faut donc pouvoir diffrencier instructionset donnes afin que le registre instruction RI contienne bien des instructions et nondes donnes (et rciproquement). Dans le cas contraire le dcodeur ne pourrait inter-prter la nature du travail faire (RI ne contenant pas une instruction mais une

MmoireInstructions Donnes

Horloge1

2

3

4

5

Figure 1.9 Excution dune instruction.


donne). En gnral lors du placement du programme machine et des donnes dansla mmoire centrale les instructions et les donnes sont spares et occupent desespaces mmoires diffrents (voir figure 1.9). la fin du chargement du programmemachine et des donnes en mmoire le compteur ordinal CO reoit ladresse de lapremire instruction du programme excuter.

Lexcution peut alors commencer. Le principe gnral dexcution est illustrdans la figure 1.9.

Les diffrentes phases de lexcution dune instruction sont les suivantes :1. le contenu du compteur ordinal CO est plac dans le registre dadresses RAD : il

y a slection de linstruction excuter;2. une commande de lecture de la mmoire centrale est dclenche via le bus de

commandes;3. linstruction est transfre de la mmoire centrale vers le registre instruction RI

via le bus de donnes et le registre de donnes RDO;4. le dcodeur analyse linstruction place dans le registre instruction RI, reconnat

cette instruction et indique au squenceur la nature de linstruction;5. le squenceur dclenche au rythme de lhorloge la squence de micro-instructions

ncessaires la ralisation de linstruction.On peut rsumer les tapes de lexcution dune instruction (chargement/dco-

dage/excution) par lalgorithme suivant :dbutcharger linstruction excuter depuis la mmoire dans le registre instruction;modifier le compteur ordinal pour quil pointe sur la prochaine instruction excuter;dcoder linstruction qui vient dtre charge dans le registre dinstruction;charger les donnes ventuelles dans les registres;excuter la squence des micro-instructions permettant la ralisation de linstruction;fin

Les oprations charger/modifier ralisent le chargement de linstruction dans leregistre dinstruction RI. Cette phase est la phase dite de FETCH.

Enfin, lexcution dun programme machine peut tre dcrite par lalgorithmesuivant :

dbutexcuter la premire instruction du programmetant que ce nest pas la dernire instructionfaire

excuter linstruction;fin fairefin

1.4 Un exemple 15

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

1.4 UN EXEMPLE

Pour rsumer ce que nous venons dtudier, nous allons prendre un exemple deproblme rsoudre avec un ordinateur. Nous dfinissons tout dabord le problmeet lordinateur cible cest--dire son langage de programmation (langage machine).Puis nous construisons le programme machine excutable par cet ordinateur. Enfinnous plaons ce programme en mmoire centrale. Il peut alors tre excut par lemicroprocesseur.

1.4.1 Le problme

Notre problme consiste raliser laddition de X qui vaut 4 avec Y qui vaut 1 et placer le rsultat dans Z. Nous souhaitons donc, laide de notre ordinateur, raliserlopration : Z = X + Y avec X = 4 et Y = 1.

1.4.2 Lordinateur

Cet ordinateur a la structure gnrale dfinie dans la figure 1.11. Les mots de lammoire sont des octets (8 bits), tous les registres du microprocesseur ont une largeurde 8 bits, les instructions et les donnes entires sont codes sur un mot mmoire.Donnes : X est cod : 000001002; Y est cod : 000000012.

1.4.3 Le langage machine

Le code opration est cod sur 4 bits, le champ oprande sur 4 bits. Le champ oprandene rfrence quune donne. Ainsi pour faire laddition de deux nombres un tellangage suppose que la premire donne est spcifie dans linstruction et la secondeoccupe une adresse implicite. Dans de nombreuses machines cette adresse impliciteest un registre appel registre Accumulateur (not A). Laddition porte alors sur ladonne spcifie dans linstruction et le contenu de A, le rsultat tant plac dans A.

Code opration Champ oprande

0001 0100

0001 0100 Charger le contenu du mot mmoire dadresse 0100 dans le registre A

0010 0101 Additionner le contenu du registre A avec le contenu du mot mmoire dadresse 0101 et placer le rsultat dans le registre A

0011 0110 Placer le contenu du registre A dans le mot mmoire dadresse 0110

0000 Stopper le programme

Figure 1.10 Le langage de la machine.


Les instructions du langage sont dfinies dans la figure 1.10. La figure 1.11 rsumeles diffrentes phases amenant lexcution du programme machine solution de notreproblme sur cette machine : les donnes ont t charges aux adresses 0100 (pour X), 0101 (pour Y), le rsultat

ladresse 0110 (pour Z); le programme machine est charg ladresse 0111; le compteur ordinal est charg avec ladresse 0111.

titre dexercice vrifiez que lexcution du programme machine rsout bien notreproblme.

1.5 LES UNITS DCHANGES

Les units dchanges permettent la communication entre les modules du processeuret les priphriques. Cette fonction de communication est complexe et nous ladtaillons dans le chapitre 9.

Une unit dchange a une double nature : elle est en communication, via le bus interne du processeur, avec la mmoire

centrale et le microprocesseur. Des instructions machines spcifiques permettent

MmoireAdresses InstructionsDonnes

Horloge

0011 110010010100 000001000101 000000010110 000000000111 000101001000 001001011001 001101101010 0000

A

X 4Y 1Z X Y

Z X Y

0001 01000010 01010011 01100000

RICO

RADRDO

Programmemachine

Traduction en langage machine

Chargement en mmoire centrale

Faire laddition de X qui vaut 4et de Y qui vaut 1,placer le rsultatdans Z

Excution

Figure 1.11 Le programme solution.

1.6 Conclusion 17

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

les changes entre mmoire centrale et unit dchange. On trouve des instruc-tions dcriture permettant au microprocesseur de placer des informations danslunit dchange et des instructions de lecture permettant au microprocesseurdacqurir des informations partir des units dchanges. De plus des doutils desynchronisation permettant dharmoniser les activits du processeur avec cellesdes priphriques quil pilote sont ncessaires : il ne faut, par exemple, envoyerdes caractres vers une imprimante que si celle-ci est prte imprimer et attendredans le cas contraire. Dans nos ordinateurs les units dchanges ne communi-quent pas directement avec le bus interne du processeur mais au travers de bus,dits bus dextension. Il existe une assez grande varit de ces bus dextension(ISA, USB, FireWire, Fiberchanel, PCI) qui satisfont des fonctionnalits diverseset plus ou moins gnrales. Nous reviendrons plus en dtail sur cette questiondans le chapitre traitant des questions de communication;

elle est en communication avec les priphriques et ce titre doit tre capable deles piloter.

1.6 CONCLUSION

Dans ce chapitre nous avons fait le tour de toutes les tapes importantes ncessaires la rsolution dun problme avec un ordinateur. La figure 1.12 rsume ces diff-rentes tapes.

Problme

Algorithme

Programme assembleur/machine

excution dune instruction Chargement (fetch) et modification du CO Dcodage Excution de la squence de micro-instructions

Compila

tion (Sy

stme de

xploitatio

n)Chargement (SE)

Programmemachine(squencedinstructionsmachine)

excution programme machine excution squentielle du programme machine

(Processeur)

Programme machine en mmoire chargement Compteur Ordinal (CO) (adresse de la premire instruction)(Systmedexploitation)

programmeLangage de haut niveau(exemple C)

Figure 1.12 Principales tapes de la rsolution dun problme avec lordinateur.


Nous voyons quune des tapes consiste exprimer lalgorithme avec un langagede haut niveau. En fait il existe plusieurs niveaux de langage de programmation : les langages de haut niveau (C, C++ , ADA, JAVA, COBOL, PASCAL, PYTHON)

ne sont pas directement excutables par le processeur cible que nous utilisons :lordinateur. Il faut donc traduire les programmes exprims dans ces langagesafin dobtenir le programme machine excutable par le processeur cible. Cestlobjet de la compilation et/ou de linterprtation. Les compilateurs (interpr-teurs) sont des programmes (du Systme dExploitation : SE) qui ont la connais-sance de la syntaxe des langages de haut niveau et qui connaissent le langagemachine de la machine cible. Ces langages sont ncessaires car on ne sait pastraduire directement le langage naturel en langage machine alors que lon saitconstruire des traducteurs pour ces langages de haut niveau;

les langages de bas niveaux sont des langages directement excutables par unmicroprocesseur. Ce sont les langages machines. Ils se prsentent sous deux formes : les langages machine cods binaires. Ce sont les seuls rellement excutables

par le processeur. Cods sous forme binaire ils sont difficiles manipuler; les langages dassemblage. Ce sont des langages machines symboliques au sens

o les codes opration et les champs oprande dune instruction sont exprims laide de symboles.

Par exemple dans la petite machine qui nous a servis dexemple, 00010010 est uneinstruction machine demandant de charger le contenu de ladresse mmoire 0010 dansle registre accumulateur A du microprocesseur. Il existe dans le langage dassem-blage de cette machine une instruction qui a la forme Load X o Load exprime laide de symboles alphanumriques le code opration cod binaire 0001 et X exprimesymboliquement ladresse mmoire de la donne X. Ce type de langage est beau-coup plus simple utiliser que le langage machine cod binaire. Bien sr un programmecrit en langage dassemblage nest pas directement excutable par le microproces-seur. Cependant la traduction, langage dassemblage, langage machine pur, est simplecar chaque instruction du langage machine correspond une instruction du langagedassemblage. Le traducteur de tels langages sappelle lassembleur. Une program-mation dans ce type de langage est possible mais de moins en moins frquente. Elle sejustifie encore lorsque lon recherche une grande efficacit, par exemple, dans laprogrammation des jeux vidos ou des interfaces graphiques.

Le traducteur (compilateur/interprteur) place le rsultat de sa traduction (programmemachine) sur le disque magntique. Le programme machine doit tre charg enmmoire centrale pour tre excut par le microprocesseur. Cest un programme dusystme dexploitation, le chargeur, qui ralise ce chargement en mmoire. Le char-geur connat ladresse de la premire instruction du programme machine, il peutainsi initialiser le compteur ordinal pour lancer lexcution. partir de ce moment lesinstructions, une une, sont prises en charge par le microprocesseur qui les excute.

La premire partie de cet ouvrage est consacre au passage du problme auprogramme machine; elle prsente en dtail le fonctionnement du compilateur et desautres outils permettant de construire un programme machine. Elle approfondit

1.6 Conclusion 19

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

ensuite les notions rencontres ici de langage machine, de modes dadressages et decodages pour la reprsentation des informations.

Dans la seconde partie nous dtaillons : la fonction dexcution o nous apportons des prcisions sur ce quest rellement

lexcution dune instruction machine. Nous prcisons la notion de micro-instruction.Dans cette partie nous abordons galement la notion dinterruption qui est unmcanisme fondamental dans nos ordinateurs;

la fonction de mmorisation en prcisant les diffrents types de mmoires consti-tuant la mmoire centrale. Nous abordons les problmes de synchronisation entreprocesseur et mmoire centrale et voyons comment la mmoire cache apporte dessolutions aux diffrences de vitesse entre microprocesseur et mmoire centrale;

la fonction de communication dans laquelle nous revenons sur la manire dchangerdes informations entre processeur et priphriques.Enfin, nous commenons le voir, le systme dexploitation joue un rle central

dans la gestion et le fonctionnement des ordinateurs. Nous y consacrons la troisimepartie de cet ouvrage.

Pour terminer cette introduction, quelques mots pour prciser le processus dedmarrage dun ordinateur. En plus de la mmoire centrale (communment appelemmoire RAM) il existe une mmoire ROM, dite mmoire morte, uniquement acces-sible en lecture donc non modifiable par programme et qui de plus nest pas volatile :quand le courant est coup, le contenu de cette mmoire ROM nest pas altrcontrairement aux mmoires RAM pour lesquelles le contenu est perdu lorsque lecourant est coup. Cette mmoire ROM est charge, une fois pour toutes, avec unprogramme : le bootstrap.

Par ailleurs sur le disque magntique est plac le systme dexploitation. Lesystme dexploitation est un ensemble de programmes excutables sur le micropro-cesseur. Un de ces programmes, linterprteur de langage de commandes (le Shellsous Unix), comprend des commandes telles que demander lexcution dun diteurde texte, dun compilateur, dun lanceur de programmes.

Le bootstrap connat ladresse sur le disque du systme dexploitation, en particu-lier de son noyau compos entre autre de linterprteur de langage de commandes.

Lors de la mise sous tension de lordinateur, automatiquement le bootstrap sexcute : le bootstrap charge en mmoire centrale le noyau du systme dexploitation (en

particulier linterprteur du langage de commande) et lance son excution; ce dernier attend, au travers dune interface de communication, les commandes de

lutilisateur. Celui-ci demande : un diteur de texte pour saisir le code de son programme; un compilateur pour le traduire en langage machine; le lancement de lexcution de son programme machine rsultat de la traduction.

Pour cela, lutilisateur, doit connatre le langage de commande quest capablede comprendre linterprteur de langage de commande du systme dexploita-tion utilis. Il existe plusieurs types dinterface de communication qui vont delcriture textuelle de la ligne de commande, encore courante sous Unix, aux


interfaces graphiques sophistiques que lon trouve sous Windows, Mac OS Xou Linux. Avec ces interfaces graphiques on ncrit plus de ligne de commandes,dont il faut connatre la syntaxe, mais on clique sur des icnes faisant rfrenceau programme que lon souhaite excuter;

le lanceur du programme machine le charge (via le chargeur) en mmoirecentrale, place ladresse de la premire instruction excuter dans le compteurordinal : le programme machine sexcute.

PARTIE 1

PRODUCTION DE PROGRAMMES

Lensemble des chapitres de cette partie est centr autour de la notion de chane deproduction de programmes. partir de la description du rle premier dun ordina-teur, nous prsentons succinctement les notions fondamentales dalgorithmes, deprogrammation ainsi que les diffrents niveaux de langages disponibles sur un ordi-nateur. Nous abordons ainsi les concepts de langage machine et langage haut niveau,puis nous nous intressons aux diffrentes tapes permettant la traduction dunprogramme crit en langage haut niveau vers son quivalent crit en langage machineet excutable par lordinateur.

Le chapitre 2 introduit la notion dalgorithme et les diffrents niveaux de langagesdisponibles sur un ordinateur. Le chapitre 3 dcrit la chane de production deprogrammes et prsente les diffrentes tapes qui la composent, cest--dire la compi-lation, ldition de liens et le chargement. Enfin, le chapitre 4 prsente la notion delangage machine, de langage dassemblage et dcrit les principales conventions dereprsentation des informations (nombres, caractres) sur la machine. Le chapitre 5est consacr aux diffrents circuits logiques qui constituent la partie matrielle delordinateur et la technologie mise en uvre pour leur fabrication. Cette partiesachve avec un ensemble dexercices corrigs.

Mots-cls : algorithme, compilation, dition des liens, langage machine, repr-sentation binaire, circuits logiques, transistors.

Chapitre 2

Du problme au programme machine2

partir de la description du rle premier dun ordinateur, nous exposons leprocessus qui permet un tre humain de soumettre la rsolution dun problme unordinateur, ceci sous forme dun programme crit dans un langage de programma-tion dit langage de haut niveau, qui code une solution appele algorithme. Lordina-teur ne pouvant excuter que des instructions codes en langage machine, il estncessaire de traduire ce langage de haut niveau vers le langage machine de lordina-teur : cest le rle de la chane de production de programmes.

2.1 DU PROBLME AU PROGRAMME

2.1.1 Rappel du rle dun ordinateur

Lordinateur est prsent de nos jours dans de multiples domaines et lieux. En unecinquantaine dannes, il a envahi notre quotidien et il est bien des domaines prsent o son utilisation et sa puissance se rvlent indispensables. En effet, lordi-nateur a investi de multiples espaces et remplit des missions trs diverses qui vont ducalcul scientifique pour par exemple squencer lADN ou analyser les modlesmtorologiques, au pilotage de procd tel que la surveillance dune centralenuclaire et encore les jeux ou la communication via lInternet.

De fait, la multiplicit des missions remplies par lordinateur cache en quelquesorte son unique rle : archiver des donnes et excuter un programme de traitement

24 2 Du problme au programme machine

sur ces donnes en vue de rsoudre un problme. Lordinateur offre ltre humainune puissance de stockage, de calcul et de traitement bien suprieure ce quoi ilpeut prtendre par lui-mme. Prenons trois exemples : en palontologie, lanalyse cladistique a pour but de mettre en vidence les liens

de parent existants entre diffrents organismes afin didentifier des clades1 et deconstruire les arbres volutifs. Pour parvenir ce but, le palontologue doit iden-tifier entre plusieurs organismes la possession en commun de caractres drivsdue une ascendance commune. Une telle recherche ne peut se faire que par unecomparaison simultane dune grande quantit de donnes, cest--dire de carac-tres et despces, quil est inenvisageable de raliser sans le concours de lordi-nateur. En effet la quantit de donnes comparer est telle que pour un trehumain tablir un seul arbre demanderait un temps considrable. Grce lordi-nateur, il est possible dtablir et de calculer des millions darbres possibles en untemps raisonnable2;

en informatique de gestion, les systmes de bases de donnes permettent destocker, classer et grer des millions de donnes dans un espace bien plus rduitquau temps o seul le support papier existait. Par ailleurs, les performances desmthodes dinterrogations lies ces systmes rendent possibles des extractionsde donnes suivant des objectifs multicritres dans des temps rduits, l o ilfaudrait un traitement manuel de plusieurs heures. Songez au catalogue informa-tique de la bibliothque municipale de votre ville, comme il est ais de demander lordinateur de rechercher dans lensemble des livres traitant de la musiquebaroque, les seuls ouvrages consacrs la fois Haendel et Vivaldi. Vous navezplus alors qu vous diriger vers le rayon dsign, prendre le livre correspondant la cote fournie; l o il vous aurait fallu soit compulser le classeur papier tri parordre alphabtique ou chacun des livres du rayon musique;

dans le domaine du contrle de procd, lordinateur supple lhumain enoffrant une plus grande vitesse de raction aux vnements et une plus grandefiabilit dans le contrle ralis. La complexit de pilotage dun avion de chasse,par exemple, est telle, la quantit dinformations remontes au cockpit si impor-tante (informations de pilotage, informations radios, informations lies au systmedarmes, informations lies au systme de dfense antimissiles), que le pilote nepeut pas piloter son appareil sans le concours de linformatique embarque. Celle-ci lui permet entre autre une vitesse de raction suprieure en prenant elle-mmeen main des rponses automatises : ainsi le systme de dfense antimissiles estcapable danalyser de lui-mme le type de missiles intercepter (thermique ouradar), de lancer les leurres adapts (fuses clairantes ou feuilles mtalliques)avant de remonter linformation au pilote pour que celui-ci dvie son avion afindviter limpact.

1. Une clade (du grec klados rameau ) dsigne une branche dun arbre volutif comprenant unanctre et ses descendants. 2. TASSY Pascal, Le palontologue et lvolution, Collection Quatre Quatre, ditions Le Pommier-Fayard, septembre 2000, 158 pages.

2.1 Du problme au programme 25

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

2.1.2 Problme, algorithme, programme et instructions

Lordinateur est puissant et rapide mais il na aucune intelligence propre et aucuneimagination. Tout ce dont lordinateur est capable, cest dexcuter ce que ltre humainlui commande de faire; en aucun cas, il ne peut fournir de lui-mme une solution un problme donn. Ltre humain utilise donc lordinateur pour rsoudre un problme,encore faut-il que ce problme puisse tre exprim lordinateur : cest lactivit deprogrammation. Ainsi, vouloir rsoudre un problme laide de lordinateur deman-dera de mettre en uvre le processus suivant (figure 2.1) : charge de ltre humain de trouver une ou plusieurs solutions au problme; au moins une des solutions trouves est ensuite exprime sous forme de rgles

opratoires telles que des itrations, des conditionnelles, des tests boolens, desoprations arithmtiques : cest la construction de lalgorithme;

lalgorithme est cod sous forme dinstructions dans un langage excutable etcomprhensible par lordinateur : cest lactivit de programmation qui construitun programme. Une instruction quivaut un ordre qui entrane lexcution parlordinateur dune tche lmentaire.

1.

Jai un problme rsoudre :

a

b

primtre ?

Jcris une solution !ALGORITHMEPrimtre 2 a 2 b

2.

3. En utilisant un langage de programmation, je code la solution pour la faire excuter par lordinateur

PROGRAMME constitu dinstructions

function perimetre (a, b : in integer) return integer isbegin perimetre : (2 * a) (2 * b);end;

Figure 2.1 Rsoudre un problme laide de lordinateur.


On notera quil dcoule de ce processus que lordinateur a besoin de trois lmentsessentiels : un moyen de communication avec ltre humain : clavier, souris, cran, etc.; un moyen dexcuter les instructions du langage : le processeur; un moyen de conserver des donnes : les priphriques de stockage tels que le

disque dur, la disquette, le CD-ROM.

2.2 LES DIFFRENTS NIVEAUX DE LANGAGE DE LORDINATEUR

La programmation est donc lactivit qui consiste traduire par un programme unalgorithme dans un langage assimilable par lordinateur. Cette activit de program-

Programme en langage de haut niveauinstructions de haut niveau

function perimetre (a, b : in integer) return integer isbegin perimetre : (2 * a) (2 * b);end;

COMPILATEUR

perimetre : pop Rg1 R1 pop Rg1 R2 mul Im R1 2 mul Im R2 2 add Rg2 R1 R2 push Rg1 R1 ret

ASSEMBLEUR

Programme en langage dassemblage :Instructions composes de Mmmoniques

0110111011111001101111010001011100101111011101111110011101111011101100111111000111101

CPU

BUS

MMOIRE

Programme excuter : instructions machine et valeurs en binaire

Traduction

Figure 2.2 Les diffrents niveaux de programmation.

2.2 Les diffrents niveaux de langage de lordinateur 27

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

mation peut seffectuer diffrents niveaux, plus ou moins proches et dpendants delarchitecture physique de la machine. Essentiellement on distinguera trois niveaux(figure 2.2) : la programmation de bas niveau en langage machine, la programma-tion de bas niveau en langage dassemblage, la programmation de haut niveau laide dun langage de haut niveau ou langage volu.

2.2.1 Langage machine

La donne de base manipule par la machine physique est le bit (Binary Digit) quine peut prendre que deux valeurs : 0 et 1. Ce 0 et 1 correspondent aux deux niveauxde voltage (0-1 et 2-5 volts) admis pour les signaux lectriques issus des composantslectroniques (transistors) qui constituent les circuits physiques de la machine (voirchapitre 5, Les circuits logiques). Au niveau physique, toutes les informations (nombres,caractres et instructions) ne peuvent donc tre reprsentes que par une combi-naison de 0 et 1, cest--dire sous forme dune chane binaire. Cest le niveau deprogrammation le plus bas et le plus proche du matriel, celui du langage machine.

ce niveau, la programmation et les instructions du langage sont totalementdpendantes de larchitecture de la machine et du processeur et manipulent directe-ment les registres du processeur ou encore les adresses en mmoire physique, toutcela sous forme de chanes binaires. Ainsi, une instruction machine (figure 2.3) estune chane binaire compose essentiellement de deux parties : le code opration dsigne le type dopration effectuer (addition, ou logique,

lecture mmoire); le reste de linstruction sert dsigner les oprandes, cest--dire les donnes sur

lesquelles lopration dfinie par le code opration doit tre ralise. Ces oprandessont soit des mots mmoires, soit des registres du processeur ou encore des valeursimmdiates.

Chaque instruction est par ailleurs repre par une adresse qui mmorise la posi-tion de linstruction dans le programme.

Ce niveau de programmation est videmment trs fastidieux, voire impraticablepar ltre humain.

code opration dsignation des oprandes

32 bits

8 bits : 28 instructions diffrentes 00000000 : addition 00100110 : multiplication etc.

adresse

Figure 2.3 Instruction machine.


2.2.2 Langage dassemblage

Une premire amlioration a consist substituer aux chanes binaires reprsentantdes codes oprations ou des adresses mmoires, des chanes de caractres plus ais-ment manipulables par ltre humain que lon appelle des mnmoniques : cest lelangage dassemblage qui constitue une variante symbolique du langage machine,permettant au programmeur de manipuler les instructions de la machine en saffran-chissant notamment des codes binaires et des calculs dadresse. Le langage dassem-blage comporte le mme jeu dinstructions que le langage machine et est galementspcifique de la machine.

Une instruction du langage dassemblage (figure 2.4) est compose de champs,spars par un ou plusieurs espaces. On identifie : un champ tiquette, non obligatoire, qui correspond ladresse de linstruction

machine; un champ code opration, qui correspond la chane binaire code opration de

linstruction machine; un champ oprandes pouvant effectivement comporter plusieurs oprandes spars

par des virgules qui correspondent aux registres, mots mmoires ou valeurs imm-diates apparaissant dans les instructions machine.

La programmation au niveau du langage dassemblage, quoique bien plus aisequau niveau machine, est encore fastidieuse pour ltre humain et requiert surtoutde connatre larchitecture du processeur et de la machine. On parle ainsi du langagedassemblage du processeur Intel Pentium ou du langage dassemblage du proces-seur Athlon AMD.

Lorsque la programmation en langage dassemblage est mise en uvre, ellencessite une tape de traduction, car seules les instructions en langage machine sontcomprhensibles et excutables par la machine. Pour pouvoir excuter un programmecrit en langage dassemblage, il faut donc traduire les instructions de celui-ci vers

code opration dsignation des oprandestiquette

linstruction en langage dassemblage

tiquette code opration oprandesboucle : ADD Rg2 R0, R1

correspond linstruction machine

adresse code opration oprandes01110110 00000000 111 0000 0001

Figure 2.4 Instruction en langage dassemblage.

2.2 Les diffrents niveaux de langage de lordinateur 29

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

les instructions machine correspondantes. Cette phase de traduction est ralise parun outil appel lassembleur1.

2.2.3 Langage de haut niveau ou volu

Ltape suivante est venue de la gense des langages volus ou langages de hautniveau. Ces langages se caractrisent principalement par le fait quils sont, contraire-ment aux deux autres types de langage que nous venons daborder, totalement ind-pendants de larchitecture de la machine et du processeur. Par ailleurs, ils offrent unpouvoir dexpression plus riche et plus proche de la pense humaine, rendant ainsiplus aise la traduction des algorithmes tablis pour rsoudre un problme. Ces langagesde fait sont davantage dfinis par rapport aux besoins dexpression du programmeurque par rapport aux mcanismes sous-jacents de la machine physique. Ils intgrentainsi des structures opratoires semblables celles des algorithmes telles que lesitrations, les boucles, les conditionnelles.

Ainsi les langages de haut niveau sont plus ou moins spcialiss par rapport uneclasse de problmes rsoudre : COBOL est destin aux applications de gestion tandisque FORTRAN est plutt orient vers le domaine du calcul scientifique. Dautreslangages sont plus universels tels que C, C++ , Ada, Java ou encore Pascal.

De nos jours, les langages haut niveau sont classs selon plusieurs grandes familles.Deux familles de langages importants et courants sont la famille des langages ditsprocduraux et la famille des langages dits objets : le langage procdural : lcriture dun programme est base sur les notions de proc-

dures et de fonctions, qui reprsentent les traitements appliquer aux donnes duproblme, de manire aboutir la solution du problme initial. Les langages Cet Pascal sont deux exemples de langages procduraux;

le langage objet : lcriture dun programme est base sur la notion dobjets, quireprsentent les diffrentes entits entrant en jeu dans la rsolution du problme. chacun de ces objets sont attaches des mthodes, qui lorsquelles sont acti-ves, modifient ltat des objets. Les langages Java et Eiffel sont deux exemplesde langages objets.Les langages volus tant indpendants de la machine, ils ne peuvent tre direc-

tement excuts par la machine. Un programme crit en langage haut niveau doitdonc tre converti vers son quivalent en langage machine. Cest le rle du traduc-teur de langage, qui est spcifique chaque langage volu utilis.

Les traducteurs sont diviss en deux catgories : les compilateurs et les inter-prteurs. un compilateur traduit une fois pour toutes le langage volu en langage machine

et construit ainsi un programme qualifi de programme objet qui est stock sur unsupport de masse tel quun disque;

1. Par abus de langage, le terme assembleur dsigne tout la fois le langage dassemblage lui-mme et loutil de traduction.


un interprteur lit une une les instructions du langage volu, puis il les convertitimmdiatement en langage machine avant quelles ne soient excutes au fur et mesure. Il ny a pas de gnration dun fichier objet conservant la traduction desinstructions en langage volu vers le langage machine et la traduction doit donctre refaite chaque nouvelle demande dexcution du programme.Plus gnralement, le passage dun programme dit programme source crit en

langage de haut niveau vers un programme excutable en langage machine est assurpar un processus comportant plusieurs tapes dont lune est la compilation, que lonqualifie de chane de production de programmes.

2.3 INTRODUCTION LA CHANE DE PRODUCTION DE PROGRAMMES

La chane de production de programmes est prsente sur la figure 2.5.Lditeur de texte est un logiciel interactif permettant de saisir du texte partir

dun clavier et de le stocker dans un fichier le programme source , sur un support

Algorithme

Programme sourcelangage volu

Langage dassemblage

Programme objetlangage machine

Programme translatablelangage machineProgramme translat

langage machine

diteur

CompilateurCompilateur

Assembleur

diteur de liens

Chargeur

cpu

mmoirecentrale

Figure 2.5 Chane de production de programmes.

2.4 Un exemple 31

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

de masse tel quun disque. Le compilateur permet la traduction du programme sourceen un programme objet qui est soit directement le langage machine, soit le langagedassemblage. Le passage du langage dassemblage au langage machine se fait parlintermdiaire dun autre traducteur, lassembleur. Le programme objet est stocksur le disque. Lditeur de liens est un logiciel qui permet de combiner plusieursprogrammes objet en un seul et de rsoudre des appels des modules de librairie.Lditeur de liens rsout les rfrences externes.

Le programme construit lissue de ldition des liens comporte une allocationdes instructions commenant 0. Pour tre excut, le programme doit tre transfrdepuis le disque vers la mmoire centrale : cest le rle du chargeur de placer leprogramme en mmoire centrale partir dune adresse dimplantation et de trans-later toutes les adresses du programme de la valeur de ladresse dimplantation.

2.4 UN EXEMPLE

Considrons que nous souhaitions crire un programme qui permet le calcul du pri-mtre ou de la surface soit dun cercle de rayon r, soit dun carr de ct a, soit dunrectangle de cts a et b, soit dun triangle quilatral de ct a et de hauteur h. Lapremire tape consiste donc crire un algorithme correspondant ce programme,cest--dire donner une solution possible au problme. Dans une analyse base surlutilisation finale dun langage procdural tel que C par exemple, la solution vasattacher identifier les fonctions raliser : ici, par exemple, nous pouvons identi-fier deux fonctions, la premire permettant le calcul dun primtre, la secondepermettant le calcul dune surface, sachant que : le primtre du carr est gal 4 a, celui du rectangle est gal 2 a + 2 b,

celui du triangle est gal 3 a et celui du cercle est gal 2 r; la surface du carr est gale a2, celle du rectangle est gale a b, celle du

triangle est gale (h a)/2 et celle du cercle est gale r2.Lalgorithme suivant pourra tre crit par exemple pour la fonction primtre :

fonction primtre :paramtres entrants : type de lobjet (triangle, carr, rectangle ou cercle)

caractristiques de lobjet : valeur de a, r, h, b selon lobjet

retourne un entier qui est la valeur du primtre.dbut

cas objet :triangle : retourner (3 a);cercle : retourner (2 r);carr : retourner (4 a);rectangle : retourner (2 a + 2 b);fin cas;

fin


Qui se traduit par exemple en langage C par le programme suivant :#define triangle 1#define cercle 2#define carre 3#define rectangle 4

int perimetre (objet, a, r, h, b)int objet, a, b, h, r;{switch (objet) {case 1 : return (3 * a);case 2 : return (2 * * r);case 3 : return (4 * a);case 4 : return (2 * a + 2 * b);}}

Dans une analyse base sur lutilisation finale dun langage objet tel que C++ parexemple, la solution va sattacher identifier les objets concerns : ici, par exemple,nous identifierons 4 objets, le cercle, le triangle, le carr et le rectangle, chacun tantassoci deux mthodes, la mthode perimetre et la mthode surface qui lorsquellessont appeles rendent respectivement le primtre ou la surface de lobjet concern.Le carr et le rectangle sont quant eux tous les deux des quadrilatres pour lesquelsle calcul de la surface et du primtre seffectue de manire identique (le carr est unrectangle de cts a et b pour lequel a = b).

Dans cette analyse, nous allons dfinir une classe quadrilatere, une classe cercleet une classe triangle. Une classe dfinit une collection dobjets qui partagent lesmmes proprits et sur lesquels les mmes traitements peuvent tre excuts. Nouscrons ensuite deux objets carre et rectangle, instances de la classe quadrilatere,un objet rond instance de la classe cercle et un objet triangle_iso, instance de laclasse triangle.

Lalgorithme qui en dcoule peut tre de la forme suivante :dfinition classe quadrilatre (entier a, b; les cts du quadrilatre;fonction primtre :: retourner (2 a + 2 b);fonction surface :: retourner (a b);)

dfinition classe triangle (entier a, h; le ct et la hauteur du triangle;fonction primtre :: retourner (3 a);fonction surface :: retourner ((a h)/2);)

dfinition classe cercle (entier r; le rayon du cercle;fonction primtre :: retourner (2 r);fonction surface :: retourner ( r2);)

2.5 Conclusion 33

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

Viennent ensuite les dfinitions les objets rectangle, carre, rond et triangle_iso.Cet algorithme peut se traduire par exemple en langage C++ par le programmesuivant o lon ne tient compte que de la classe quadrilatere et pour lequel parsouci de simplification, les paramtres du rectangle et du carr sont fixs lors de ladclaration des objets associs :

class quadrilatere{int a, b;public :

int perimetre (void);int surface (void);

};int quadrilatere :: perimetre (void){

return (2 * a + 2 * b);}int quadrilatere :: surface (void){

return (a * b);}

int main(){

quadrilatere carre (5, 5);quadrilatere rectangle (7, 9);int surfacec, perimetrec, surfacer, perimetrer;

surfacec = carre.surface();perimetrec = carre.perimetre();surfacer = rectangle.surface();perimetrer = rectangle.perimetre();

}

2.5 CONCLUSION

Ce chapitre nous a permis de comprendre le rle essentiel dun ordinateur savoirexcuter un programme qui est le codage dans un langage comprhensible par lamachine dune solution un problme pos par un tre humain. La solution ceproblme est appele algorithme.

Le programmeur dispose de plusieurs niveaux de langage pour coder son algo-rithme : le langage de haut niveau est le niveau de programmation le plus utilis aujourdhui.

Cest un niveau de programmation indpendant de la structure physique de lamachine et de larchitecture du processeur de celle-ci;


le langage dassemblage est un langage au contraire dpendant de larchitecture dela machine physique. Il correspond une forme symbolique du langage machineassoci au processeur;

le langage machine est un langage compos sur un alphabet binaire. Cest le seullangage excutable directement par le processeur.

Chapitre 3

La chane de production de programmes3

La chane de production de programmes dsigne le processus permettant la crationdun programme excutable plac en mmoire centrale partir dun programme ditsource crit en langage de haut niveau. Ce processus se dcompose en plusieurs tapes(figure 3.1) que nous allons successivement tudier dans ce chapitre : la compilation,ldition de liens et enfin le chargement.

Compilateur

diteur de liens

Chargeur

diteur de texte

Bibliothques

prog.csource

prog.oobjet

prog.exeprogramme excutable stock sur disque

prog.exeprogramme excutable sock en mmoire centrale

Figure 3.1 Chane de production de programmes.

36 3 La chane de production de programmes

Nous abordons ensuite le fonctionnement dun outil trs courant pour simplifier laconstruction dun programme excutable partir de plusieurs modules sources :lutilitaire Make.

3.1 LA COMPILATION

La compilation constitue la premire tape de la chane de production de programmes.Elle permet la traduction dun programme dit programme source crit le plus souventen langage de haut niveau vers un programme dit programme objet qui est soit direc-tement le langage machine, soit le langage dassemblage. Le programme objet eststock sur le disque.

Le compilateur est une application. Cest un logiciel dpendant de la machinephysique vers laquelle il doit produire le langage. Ainsi un programme compil surune machine A ne sexcutera pas forcment sur une machine B, notamment si B estdiffrente physiquement de A.

ExempleLa compilation dun programme crit en langage C sobtient en tapant la commandecc o prog.c et produit un fichier objet de nom prog.o. De mme la compilationdun programme crit en Fortran sobtient en tapant la commande xlf c fichier.fet produit un fichier objet fichier.o.

Le travail du compilateur se divise en plusieurs phases : lanalyse lexicale (reconnaissance des mots du langage, cest--dire apprhension

du vocabulaire); lanalyse syntaxique (vrification de la syntaxe, cest--dire apprhension de la

grammaire) ; lanalyse smantique (vrification de la smantique, cest--dire apprhension

du sens) ; loptimisation et la gnration du code objet.

3.1.1 Grammaire et structure dun langage de haut niveau

Structure dun langage de haut niveau

Avant de dbuter ltude du fonctionnement du compilateur, nous nous attachons dfinir la structure dun langage haut niveau. La dfinition dun langage de haut niveausappuie sur : un alphabet : cest lensemble des symboles lmentaires disponibles dans le langage

(caractres, chiffres, signes de ponctuation); un ensemble de mots encore appels lexmes : un mot est un groupe de symboles

lmentaires admis par le langage dont la structure est donne par une grammaire;

3.1 La compilation 37

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

des phrases ou instructions : une phrase est un groupe de lexmes du langage dontla structure est elle aussi donne par une grammaire. Cette structure peut tre dcritepar un arbre qualifi darbre syntaxique.Par exemple, A1 est un mot du langage compos des symboles lmentaires A et 1.

A1 = 3; constitue une phrase du langage.Finalement, un programme est constitu comme tant une suite de phrases du

langage, chacune des phrases respectant une syntaxe donne par la grammaire asso-cie au langage. Formellement, une grammaire est dfinie par : un ensemble de symboles terminaux qui sont les symboles lmentaires admis dans

le langage (exemples : DEBUT, FIN, *, + , = , ); un ensemble de symboles non terminaux (exemples : , , ); un ensemble de rgles syntaxiques encore appeles productions (exemple :

:: = | ).Pour dcrire la syntaxe dun langage et spcifier les rgles de production de la

grammaire associe, on utilise couramment la notation dite notation de Backus-Naurou BNF (Backus-Naur Form), dveloppe lorigine pour dcrire la syntaxe du langageAlgol 60. Avec ce formalisme, une rgle de production scrit :

:: = | et dcrit la syntaxe de lobjet_1 du langage comme tant soit lobjet_2 du langage,soit lobjet_3 du langage. | code lalternative et :: = spare un objet de sadescription.

ExempleSoient les deux rgles suivantes : :: = | :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Le nombre 125 peut tre dcompos comme suit : 125 :: = 12 5 12 :: = 1 2 1 :: = 1

Un exemple

Les rgles de Backus-Naur suivantes permettent la description dun langage deprogrammation que nous appellerons L_exemple contenant deux types dinstruc-tions : dune part des instructions permettant doprer des dclarations de variables,dautre part des instructions de type affectation.

:: = PROGRAM :: = DEBUT FIN :: = |


:: = INT ; :: = | :: = = ; | = ; :: = | :: = + | | * | / :: = | :: = | :: = A | B | C | D | E. | | X | Y | Z :: = 0 | 1 | 2 | 3 | 4. | .. | 9

Ainsi, la premire rgle spcifie que lobjet programme est construit partir dusymbole terminal PROGRAM suivi dun objet et dun objet . Un objet est lui-mme dcrit comme tant compossoit dune lettre seule, soit dune lettre suivie dun chiffre. Les lettres admises sontles 26 lettres majuscules de lalphabet et les chiffres admis sont les chiffres allantde 0 9. Lobjet est par ailleurs dfini comme tant un objet suivi du symbole terminal DEBUT, suivi dun objet suivi du symbole FIN. Et ainsi de suite

Le programme Z suivant a t crit en respectant la syntaxe dicte par ces rgles.

PROGRAM ZINT A;INT B;INT C2;DEBUTA = 4;B = A / 2;C2 = B + A;FIN

3.1.2 Analyse lexicale

La premire tape de lopration de compilation sappelle lanalyse lexicale.Lanalyseur lexical (figure 3.2) lit le programme source caractre par caractre, etreconnat dans cette suite de caractres les lexmes du langage en sappuyant sur lesrgles de Backus Naur les dfinissant. Par ailleurs, lanalyseur lexical limine lesespaces non significatifs et les commentaires qui nont pas de signification propre.Pour rendre plus aises les tapes ultrieures, il traduit les lexmes reconnus quiconstituent des chanes de caractres en symboles plus aisment manipulables, parexemple en entiers.

3.1 La compilation 39

Dun

od

La

pho

toco

pie

non

auto

rise

est

un d

lit.

Ainsi, les lexmes du langage L_exemple peuvent tre cods sur lensemble Z desnombres entiers positifs, ngatifs ou nuls en appliquant les rgles suivantes :

cas (type_lexme reconnu) :entier : codage_lexme = valeur de lentier;symbole + : codage_lexme = 1;symbole : codage_lexme = 2;symbole * : codage_lexme = 3;symbole / : codage_lexme = 4;symbole = : codage_lexme = 5;symbole ; : codage_lexme = 6;symbole PROGRAM : codage_lexme = 7;symbole DEBUT : codage_lexme = 8;symbole FIN : codage_lexme = 9;symbole INT : codage_lexme = 10;identificateur lettre seule : (position_lettre_alphabet + 10);identificateur lettre chiffre : ((position_lettre_alphabet + 10) + 26 (chiffre + 1));fin cas;

Avec ce codage qui est totalement bijectif : un lexme entier reoit une valeur positive ou nulle; un lexme symbole du langage reoit une valeur dans lensemble [ 10, 1]; un identificateur reoit une valeur dans lensemble [ 296, 11] : en effet, liden-

tificateur A est cod par la valeur 11 tandis que lidentificateur Z9 est cod parla valeur (36 + 260).Le programme Z correspondra lissue de lanalyse lexicale la suite dentiers : 7 (PROGRAM), 36 (Z), 10 (INT), 11 (A), 6 (;), 10 (INT), 12 (B), 6 (;),

10 (INT), 91 (C2), 6 (;), 8 (DEBUT), 11 (A), 5 (=), 4 (4), 6 (;), 12 (B), 5 (=), 11 (A), 4 (/), 2 (2), 6 (;), 91 (C2), 5 (=), 12 (B), 1 (+), 11 (A), 6 (;), 9 (FIN).

Programme

Analyseur lexical

Suitede caractres

Suitede symboles

Lexmes

Erreurs : symboles non reconnus

Figure 3.2 Analyseur lexical.


Des erreurs peuvent survenir et correspondent lutilisation de symboles nonconformes au langage. Ainsi une phrase telle que INT g5 provoquera une erreur lexi-cale dans le cadre du langage L_exemple car le symbole g ne fait pas partie delalphabet du langage (seules les lettres majuscules sont admises). Par contre la phraseG 5 = 2; sera reconnue par lanalyseur lexical comme tant quivalente la suite : 17 (G) 5 (5) 5 (=) 2 (2) 6 (;).

La phase danalyse lexicale sapparente notre propre processus de lecture quinous permet de reconnatre et former les mots dans la suite de caractres dun texte.

3.1.3 Analyse syntaxique

Ltape suivante dans le processus de compilation est celle de lanalyse syntaxique.Lanalyseur syntaxique (figure 3.3) analyse la suite de symboles issus de lanalyseurlexical et vrifie si cette suite de symboles est conforme la syntaxe du langage tellequelle est dfinie par les rgles de Backus-Naur. Pour cela, lanalyseur syntaxiqueessaye de construire larbre syntaxique correspondant au programme. Dans cet arbre,les feuilles correspondent aux symboles issus de lanalyse lexicale et les nuds inter-mdiaires correspondent aux objets grammaticaux. Si lanalyseur syntaxique neparvient pas construire larbre syntaxique du programme compil, alors cela traduitle fait que la syntaxe du programme est errone.

Larbre syntaxique est construit par application successive des rgles de Backus-Naur dfinissant la syntaxe du langage, lensemble des symboles issus de lanalyselexicale. Cette construction se poursuit soit jusqu ce que le dernier symbole ait tpris en compte avec succs (la syntaxe est correcte), soit jusqu ce quil ne soit pluspossible de faire correspondre aucune des rgles de Backus-Naur existantes avec lasuite de symboles restants (la syntaxe est errone).

Le programme Z donn en exemple au paragraphe 3.1.1 conduit larbre syntaxiquedonn par la figure 3.4.

Reprenons prsent la phrase G 5 = 2; reconnue par lanalyseur lexical commetant quivalente la suite : 17 (G) 5 (5) 5 (=) 2 (2) 6 (;). Larbre syntaxique

Analyseur syntaxique

Suitede symboles

Arbressyntaxiques

BNF

Erreurs de syntaxe

lexical

Analyseur

Figure 3.3 Analyseur syntaxique.

3.1 La compila

Documents

Architecture Machine