FDO COURS PDF - Cours et exercices corrigés Fonctionnement des ordinateurs

INFO-F-102 – Fonctionnement des ordinateurs Cours et exercices corrigés Gilles G EERAERTS Année académique 2024–2025 Document mis en page à l’aide de XELATEX, en utilisant la classe KOMA script. Version du 13 septembre 2024. À mon père, qui m’a appris le plaisir d’apprendre. Table des matières I. Notions de base 17 1. Leçon 1 – Introduction : Qu’est-ce qu’un ordinateur ? 19 1.1. Déﬁnitions et étymologie................................ 19 1.2. Un premier modèle : l’architecture de VON N EUMANN............... 21 1.3. Une vision différente : structure en niveaux et traductions............. 26 2. Leçons 2 à 4 – Représentation de l’information 31 2.1. Unités de quantité d’information............................ 32 2.2. Écriture des nombres dans différentes bases..................... 33 2.2.1. Changements de base.............................. 36 2.2.2. Opérations en base 2............................... 40 2.2.3. Représentation des entiers non-signés.................... 43 2.2.4. Représentation des nombres entiers signés.................. 43 2.2.5. Représentation des nombres « réels »..................... 46 2.3. Représentation des caractères............................. 50 2.4. Représentation d’images................................. 53 2.5. Représentation des instructions............................ 55 2.6. Détection et correction d’erreurs............................ 57 2.6.1. Bit de parité.................................... 57 2.6.2. Code de H AMMING................................ 58 2.6.3. Applications des codes correcteurs d’erreur................. 61 2.7. Conclusion : sémantique d’une représentation binaire............... 62 2.8. Exercices.......................................... 65 2.8.1. Changements de base.............................. 65 2.8.2. Représentation des nombres négatifs..................... 65 2.8.3. Représentation des nombres en virgule ﬂottante.............. 66 2.8.4. Corrections.................................... 67 3. Leçon 5 & 6 – Organisation de l’ordinateur 71 3.1. Mémoire primaire.................................... 71 3.1.1. Structure et adresses............................... 72 3.1.2. Mémoire cache.................................. 73 3.1.3. Ordre des octets dans les mots......................... 74 3.1.4. Réalisation de la mémoire primaire...................... 76 3.2. Le processeur....................................... 77 3.2.1. Composants du processeur........................... 77 3.2.2. Le chemin des données – datapath...................... 82 5 Table des matières 3.2.3. Exécution des instructions........................... 82 3.2.4. Machine à pile................................... 83 3.2.5. Choix du jeu d’instructions machine..................... 86 3.2.6. Techniques pour améliorer l’efﬁcacité des processeurs........... 87 3.3. Les périphériques..................................... 94 3.3.1. Mémoire secondaire............................... 95 3.3.2. Les périphériques d’entrée/sortie....................... 98 II. Les portes logiques 103 4. Leçons 7 à 10 – Niveau 0 : portes logiques 105 4.1. L’algèbre Booléenne................................... 105 4.2. Les circuits logiques................................... 112 4.2.1. Les portes logiques en pratique......................... 112 4.2.2. De la formule Booléenne au circuit logique.................. 115 4.3. Circuits pour réaliser l’arithmétique binaire..................... 116 4.3.1. Circuit additionneur............................... 117 4.3.2. Demi-additionneur................................ 118 4.3.3. Décalage...................................... 121 4.3.4. Décodeur..................................... 123 4.3.5. Le multiplexeur.................................. 124 4.3.6. ALU simpliﬁée (1 bit)............................... 125 4.3.7. ALU n bits..................................... 127 4.4. Circuits pour réaliser des mémoires.......................... 131 4.4.1. Mémoire élémentaire.............................. 131 4.4.2. Bascules...................................... 132 4.4.3. Flip-ﬂops...................................... 136 4.4.4. Un circuit de mémoire complet........................ 137 4.5. Exercices.......................................... 143 4.5.1. Tables de vérité et formules logiques..................... 143 4.5.2. Exercices à faire sous Logisim.......................... 144 4.5.3. Exercices supplémentaires........................... 144 4.5.4. Corrections.................................... 146 III. Le micro-langage 149 5. Leçons 11 et 12 – La microarchitecture 151 5.1. Le datapath du MIC-1.................................. 154 5.1.1. Composants du Mic-1.............................. 154 5.1.2. Cycle d’exécution................................. 157 5.1.3. Micro-instructions................................ 159 5.2. Le langage machine IJVM................................ 161 5.2.1. Instructions du langage............................. 161 6 Table des matières 5.2.2. Représentation d’un programme IJVM en mémoire............. 162 5.3. Implémentation de l’IJVM sur le MIC1......................... 164 5.3.1. Structure de l’interpréteur............................ 165 5.3.2. Lecture et décodage............................... 165 5.3.3. Représentation de la pile en mémoire..................... 166 5.3.4. Microcode de l’interpréteur........................... 167 5.3.5. L’unité de contrôle du Mic-1.......................... 171 5.3.6. Le Control Store.................................. 171 5.3.7. Le séquenceur................................... 173 5.4. Pour aller plus loin...................................... 174 5.5. Exercices.......................................... 175 5.5.1. Comprendre l’effet des micro-instructions.................. 175 5.5.2. Comprendre l’interpréteur........................... 178 5.5.3. Corrections.................................... 179 IV. Le langage Machine 181 6. Leçons 13 et 14 – Langage machine 183 6.1. Notion d’architecture................................... 184 6.2. Instructions machine typiques............................. 189 6.3. Mécanismes de protection............................... 195 6.4. Représentation des instructions et des opérandes.................. 197 6.4.1. Opcodes à taille variable............................. 197 6.4.2. Adressage..................................... 198 6.5. Exercices.......................................... 201 6.5.1. Langage x86 32 bits................................ 201 6.5.2. Exemple : Branchement conditionnel en assembleur x86......... 202 6.5.3. Exemple : Boucles en assembleur x86..................... 204 6.5.4. Autres exercices.................................. 204 6.5.5. Corrections.................................... 205 7. Leçon 14 – Le mécanisme d’interruption 209 7.1. Exemple introductif................................... 209 7.2. Déroulement d’une interruption............................ 211 7.2.1. Interruption interruptibles ?........................... 212 7.2.2. Boucle d’interprétation modiﬁée........................ 212 7.2.3. Retour d’une interruption............................ 213 7.2.4. Exemple...................................... 215 7.3. Applications du mécanisme d’interruption...................... 223 7.4. Extensions possibles................................... 223 7.5. Cas de l’Intel 486DX................................... 224 7.6. Exercices.......................................... 227 7.6.1. Corrections.................................... 227 7 Table des matières V. Le système d’exploitation 229 8. Leçon 15 – Le système d’exploitation 231 8.1. Nécessité d’un système d’exploitation......................... 231 8.2. Principe général de fonctionnement.......................... 233 8.2.1. Mécanismes de protection et de l’appel système.............. 235 8.3. Tâches dévolues au système d’exploitation...................... 238 8.3.1. La gestion de la mémoire primaire....................... 238 8.3.2. La gestion des processus............................. 239 8.3.3. La gestion des périphériques.......................... 239 8.3.4. La gestion des différents utilisateurs...................... 239 8.3.5. La gestion de la mémoire secondaire..................... 242 8.3.6. La gestion d’une interface utilisateur..................... 242 8.4. Quelques repères historiques.............................. 247 8.4.1. Les premiers langages de programmation et les OS batch......... 249 8.4.2. Les années 1960, 1970 et l’ère des mainframes................ 250 8.4.3. Les années 1980 et 1990 : l’informatique personnelle............ 254 8.4.4. L’informatique portable : les années 2000 et après.............. 259 9. Leçons 16 et 17 – Gestion de la mémoire primaire 261 9.1. Problèmes à surmonter................................. 261 9.1.1. Problème d’adressage et relocation...................... 262 9.1.2. Problème de fragmentation........................... 264 9.2. Pagination......................................... 265 9.2.1. Les cadres de page................................ 266 9.2.2. Les pages...................................... 267 9.2.3. Le MMU et la traduction des adresses..................... 270 9.3. Pagination à la demande................................. 274 9.3.1. Le défaut de page................................. 276 9.3.2. L’échange et le choix de victime........................ 277 9.4. Difﬁcultés liées à la pagination............................. 279 9.5. Exemple : pagination sur l’Intel 486.......................... 282 9.6. Exercices.......................................... 286 9.6.1. Corrections.................................... 288 10.Leçon 18 – Gestion des processus et de la mémoire secondaire 293 10.1.Gestion des processus.................................. 293 10.1.1. Cycle de vie d’un processus........................... 294 10.1.2. Systèmes en Time sharing............................ 296 10.2.Gestion de la mémoire secondaire........................... 298 10.2.1. Structure physique de la mémoire secondaire................ 298 10.2.2. Structure logique de la mémoire secondaire................. 298 10.2.3. De la structure logique à la structure physique................ 301 8 Table des ﬁgures 1.1. Lettre de J. P ERRET..................................... 20 1.2. Un exemple de programme écrit en langage Python................. 22 1.3. L’architecture VON N EUMANN, un premier modèle d’ordinateur.......... 25 1.4. L’architecture de l’i486.................................. 27 1.5. Les 6 couches décrivant le fonctionnement d’un ordinateur............ 30 2.1. Le code Baudot...................................... 52 2.2. Le code ASCII....................................... 53 2.3. Le Code Page 737..................................... 54 2.4. Extrait du standard Unicode, alphabet Tagbanwa................ 55 2.5. Un exemple de contenu de ﬁchier PGM avec l’image qu’il représente........ 56 2.6. Un code QR........................................ 62 2.7. Une représentation, différentes interprétations................... 64 3.1. Un modèle simple de l’organisation d’un ordinateur................. 71 3.2. Petit et gros boutistes................................... 75 3.3. Un tube Williams...................................... 76 3.4. Deux mémoires à lignes de délai............................ 78 3.5. Détail d’une mémoire à tores de ferrite......................... 79 3.6. Un exemple de programme en langage machine i486................ 82 3.7. Le chemin des données................................. 83 3.8. La boucle d’interprétation du CPU........................... 84 3.9. Un exemple de pile..................................... 85 3.10.Un exemple de langage machine i486 utilisant le FPU................ 86 3.11.Sir Maurice W ILKES en 1980............................... 87 3.12.Illustration d’un pipeline à cinq étages......................... 88 3.13.Un pipeline superscalaire................................ 89 3.14.Un ordinateur CDC 6600................................. 90 3.15.L’ILLIAC IV......................................... 92 3.16.Une Cray 1......................................... 93 3.17.L’organisation d’un ordinateur avec 2 CPUs..................... 94 3.18.Une carte perforée telles qu’elles étaient utilisées dans les supermarchés belges Colruyt durant les années 1980 (avant l’utilisation systématique des codes-barre). Les clients devaient collecter une carte perforée pour chaque produit acheté, et le caissier pouvait ensuite produire un ticket de caisse très détaillé à l’aide d’un lecteur de carte perforées connecté à un ordinateur central de gestion des stocks, et à une imprimante matricielle........................ 96 9 Table des ﬁgures 3.19.Du ruban perforé..................................... 96 3.20.Trois types de disquettes : de 8, 5,25, et 3,5 pouces.................. 97 3.21.Illustration d’un disque dur................................ 98 3.22.Rotation autour de l’axe des y.............................. 100 4.1. Quelques portes logiques de base............................ 112 4.2. Exemples de transistors.................................. 112 4.3. Exemple de tubes IBM................................... 114 4.4. Le demi-additionneur................................... 118 4.5. Un additionneur complet................................ 119 4.6. Additionneur n bits.................................... 120 4.7. Le circuit de décalage 3 bits................................ 122 4.8. Un décodeur 4 bits..................................... 124 4.9. Des afﬁcheurs 7 segments................................ 124 4.10.Le multiplexeur 2n bits ou « 2n vers 1 »......................... 126 4.11.Une ALU 1 bit avec 4 opérations............................. 128 4.12.La représentation d’une ALU............................... 130 4.13.Une ALU 4 bits réalisée sur base de 4 ALUs 1 bit................... 130 4.14.Une boucle de portes non qui permet de stocker une valeur binaire....... 132 4.15.Une bascule......................................... 134 4.16.Une bascule avec horloge................................. 135 4.17.Une bascule D....................................... 136 4.18.Un générateur de pulsation............................... 137 4.19.Le circuit logique d’une ﬂip-ﬂop............................. 138 4.20.Une ﬂip-ﬂop, avec ses deux entrées D et horloge, et ses deux sorties Q et Q... 138 4.21.Mémoire : lecture du bit i parmi 4 adresses...................... 140 4.22.Mémoire : écriture d’un bit i parmi 4 adresses..................... 141 4.23.Une mémoire de 4 mots de 3 bits............................ 142 5.1. Ferranti Mark 1 et IBM System/360.......................... 153 5.2. Le chemin des données du Mic-1............................ 155 5.3. Un exemple de programme en IJVM, qui calcule la somme de trois nombres, et son effet sur la pile..................................... 162 5.4. Un exemple de programme en IJVM, qui teste si les deux nombres au sommet de la pile sont égaux, et push un 1 si c’est le cas ; un 0 dans le cas contraire.... 163 5.5. Structure de l’interpréteur IJVM............................. 165 5.6. Une illustration de la pile en mémoire, et des registres correspondants...... 167 5.7. L’interpréteur IJVM..................................... 168 5.8. Le Mic1 complet..................................... 172 5.9. Le format binaire des microinstructions........................ 173 5.10.Tableau à compléter.................................... 177 6.1. Instructions du 6502................................... 190 6.2. Calcul de b 2 − 4ac en langage machine i486...................... 191 10 Table des ﬁgures 6.3. Un « if » P YTHON en langage machine......................... 192 6.4. Appels de procédures en langage machine....................... 193 6.5. Boucle en langage machine................................ 194 6.6. Exemples d’adressage.................................. 200 7.1. Lecture sur périphérique : sans DMA et sans interruption............. 210 7.2. Lecture sur périphérique, avec le mécanisme d’interruption............ 211 7.3. La boucle d’interprétation du CPU avec le mécanisme d’interruption....... 214 7.4. Exemple d’interruption (1). Situation initiale : on vient d’exécuter l’instruction à l’adresse 256, et on s’apprête à prendre en compte la demande d’interruption. L’interruption aura donc lieu entre les instructions aux adresses 256 et 257... 217 7.5. Exemple d’interruption (2). Situation juste avant d’exécuter le gestionnaire d’in- terruption.......................................... 218 7.6. Exemple d’interruption (3). Situation après l’exécution de l’instruction à l’adresse 2048............................................. 219 7.7. Exemple d’interruption (4). Situation juste avant d’exécuter l’instruction à l’adresse 2051............................................. 220 7.8. Exemple d’interruption (5). Situation juste après l’exécution de l’instruction de restauration à l’adresse 2051, avant l’exécution de l’IRET à l’adresse 2052.... 221 7.9. Exemple d’interruption (6). Situation après l’exécution de l’IRET : le programme interrompu reprend son exécution normalement................... 222 8.1. Exemple de programme Python manipulant in ﬁchier............... 233 8.2. Le système d’exploitation................................ 234 8.3. Un appel système sous GNU/Linux.......................... 236 8.4. Des processus et l’utilisateur associé.......................... 241 8.5. Les droits associés à des ﬁchiers............................. 242 8.6. Un DEC VT100....................................... 244 8.7. Le CLI de DOS....................................... 245 8.8. Exemple de GTK sous Python.............................. 248 8.9. Une IBM 704........................................ 251 8.10. T HOMPSON et R ITCHIE au PDP-11........................... 253 8.11.Un IBM modèle 5150................................... 255 8.12.Un Macintosh 128k.................................... 257 9.1. Notre programme d’exemple............................... 262 9.2. Deux positions différentes pour le programme.................... 263 9.3. La fragmentation..................................... 265 9.4. Exemple de pagination.................................. 266 9.5. Page frames et pages.................................... 267 9.6. Les pages de P et Q chargées............................... 269 9.7. Les pages de P et R chargées............................... 271 9.8. Le MMU........................................... 271 9.9. Pagination avec ℓ = 2k.................................. 275 11 Table des ﬁgures 9.10.Pagination à la demande (1)............................... 278 9.11.Pagination à la demande (2)............................... 280 9.12.Pagination à la demande (3)............................... 281 9.13.Pagination sur l’i486................................... 285 9.14.État de la mémoire..................................... 287 9.15.État de la mémoire après les opérations........................ 289 10.1.Le cycle de vie des processus............................... 294 10.2.La commande ps...................................... 296 10.3.Système de ﬁchiers Unix................................. 300 10.4.FAT16............................................ 303 12 Liste des tableaux 2.1. Comparaison des différentes représentations (sur n bits).............. 46 4.1. Les 4 opérations de notre exemple d’ALU, ainsi que les entrées qui y corres- pondent........................................... 127 5.1. Les opcodes IJVM que nous utiliserons. NB : par souci de cohérence de ces notes, nous avons adopté des opcodes différents de ceux de.......... 163 6.1. Quelques instructions du langage d’assemblage x86 32 bits............. 203 13 Au lecteur Ce document constitue les notes du cours INFO-F102 « Fonctionnement des Ordinateurs ». La structure de ce cours est librement inspiré de l’ouvrage « Structured Computer Organi- sation » d’Andrew TANENBAUM, qui a un temps servi de livre de référence pour ce cours, mais qui n’est plus édité en français. Ces notes ont donc évolué, au cours du temps, à partir de résumés au style télégraphiques qui accompagnaient les premières version du cours. La version que vous tenez en main est la sixième version de ces notes, valable pour l’an- née académique 2022–2023. La nouveauté de cette version est l’inclusion d’une petite cin- quantaine d’exercices à la ﬁn de certains chapitres, exercices qui sont accompagnés de leurs corrections. Ces exercices sont ceux qui seront utilisés lors des séances de travaux pratiques. À travers toutes ces notes, les conventions typographiques suivantes ont été adoptées pour les exemples et les concepts les plus importants : ß Ceci est un exemple illustrant une notion exposée par ailleurs. Ceci est une déﬁnition ou un concept particulièrement important. Gardez les yeux grand ouverts, et soyez attentif ! Signalons enﬁn qu’un document décrivant en détail les objectifs pédagogiques du cours et son organisation pratique est disponible sur l’UV. De nombreuses autres resources (comme les ﬁchiers des circuits du Chapitre 4) y sont également présentes, et constituent un complé- ment indispensable à ces notes. Remerciements J’adresse tout d’abord mes plus vifs remerciements à toutes les assistantes et tous les assistants qui ont collaboré à cet enseignement depuis 2011, et qui ont largement contribué à l’écriture des exercices et de leurs corrigés. J’espère n’oublier personne en citant ici : Axel A BELS, Stéphane F ERNANDES M EDEIROS, François G ÉRARD, Markus L INDSTRÖM, Ar- thur M ILCHIOR, Charlotte N ACHTEGAEL, Gianmarco PALDINO, Arnaud P OLLARIS, Cédric T ER- NON , Marie VAN D EN B OGAARD , Nassim V ERSBRAGEN et Nikita V ESHCHIKOV. En outre, je tiens à remercier toutes celles et tous ceux qui ont pris la peine de relire tout ou une partie de ces notes et qui m’ont fait des commentaires. Je remercie à nouveau Marie VAN D EN B OGAARD pour sa lecture très attentive et bienveillante. Je remercie aussi vivement Ethan A LLEMAN, Islam B ENAIM, Noé B OURGEOIS, Arnold D ECHAMPS, Salah E L H AOUARI, Eliott H UET, Mathieu L ENG, Arnaud L EPONCE et Thierry M ASSART pour leurs commentaires. Bruxelles, septembre 2023 15 Première partie Notions de base 17 1. Leçon 1 – Introduction : Qu’est-ce qu’un ordinateur ? 1.1. Déﬁnitions et étymologie L’objet de ce cours est, comme son titre l’indique, d’expliquer comment fonctionne un or- dinateur. Le but ici est de dégager une série de principes de base qui régissent et permettent d’expliquer le fonctionnement des ordinateurs tels que nous les connaissons aujourd’hui, mais aussi tels qu’ils ont toujours existé (et, espérons le, tels qu’ils existeront dans le futur). Nous allons donc commencer par nous demander ce qu’est un ordinateur. Commençons par observer que le mot « ordinateur » est un mot relativement neuf dans l’acception qui nous intéresse ici. Il a été proposé par Jacques P ERRET 1 , qui avait été consulté par le directeur d’IBM France en 1955. IBM cherchait à l’époque un nom français pour ces nouvelles machines que l’on nommait computer en anglais. Jacques P ERRET répond par une lettre du 16 avril 1955 restée célèbre (voir Figure 1.1). En ce qui concerne maintenant le sens du mot, Wikipedia nous donne la déﬁnition suivante : Un ordinateur est un système de traitement de l’information programmable [... ] et qui fonctionne par la lecture séquentielle d’un ensemble d’instructions, orga- nisées en programmes, qui lui font exécuter des opérations logiques et arithmé- tiques. Le Petit Robert, pour sa part, nous donne la déﬁnition : Machine électronique de traitement numérique de l’information, exécutant à grande vitesse les instructions d’un programme enregistré. Ces deux déﬁnitions mettent en avant plusieurs concepts essentiels : 1. L’ordinateur est une machine qui traite l’information. Il reçoit de l’information et en produit, sur base de l’information reçue. Par exemple, un ordinateur peut être utilisé pour calculer les racines réelles d’une équation du second degré à une inconnue sur base des coefﬁcients a, b et c de cette équation (c’est l’exemple que nous développons ci-dessous) ; ou pour élaborer la ﬁche de paye d’un travailleur sur base de ses presta- tions ; ou pour afﬁcher une vidéo sur base de données reçues via Internet,... 2. Pour traiter l’information, l’ordinateur exécute un programme, qui est une séquence d’instructions, indiquant chacune un traitement spéciﬁque à exécuter. Cela signiﬁe que 1. Philologue français né le 6 décembre 1906 et mort le 29 mars 1992, il est professeur à la Faculté de lettres de Paris (France). 19 1. Leçon 1 – Introduction : Qu’est-ce qu’un ordinateur ? F IGURE 1.1. – Que diriez-vous d’ordinateur ? La proposition de Jacques P ERRET pour nommer cette nouvelle machine... 20 1.2. Un premier modèle : l’architecture de VON N EUMANN l’ordinateur a été conçu de manière à être capable de réaliser certains traitements cor- respondant à des instructions pré-déﬁnies, et qu’on peut utiliser ces instructions de base comme des briques pour construire des traitements plus complexes appelés pro- grammes. Par exemple, supposons que nous disposons d’un ordinateur capable d’exécuter les instructions add et idiv qui calculent respectivement la somme de deux nombres et la division (entière) d’un nombre par un autre. Nous pouvons imaginer qu’il est possible de construire, sur base de ces deux instructions, un programme qui calcule la (partie entière de la) moyenne de deux nombres, en utilisant d’abord add pour faire la somme de ces deux nombres, puis idiv pour diviser le résultat par 2. Naturellement, la somme doit être effectuée avant la division : l’ordre (la séquence) des instructions est donc important. Ce faisant, nous avons esquissé l’écriture d’un programme, qui calculerait une moyenne en utilisant add et idiv. 3. Le programme de l’ordinateur peut être modiﬁé. L’ordinateur n’a pas été conçu dans le but d’exécuter un et un seul programme, mais son utilisateur a la faculté de modiﬁer le programme, soit en acquérant des programmes écrits par des tiers (comme des appli- cations achetées et téléchargées sur Internet, par exemple), soit en écrivant lui-même de nouveaux programmes. 4. Enﬁn, l’information que l’ordinateur traite à l’aide des programmes qu’il exécute est représentée de manière numérique, et est traitée comme telle. Cela signiﬁe que toute information, quelque soit sa nature (nombres, textes, images, sons, vidéos,... ) doit être exprimée sous forme de nombres pour pouvoir être traitée par l’ordinateur. En l’occurrence, tous les ordinateurs modernes représentent l’information sous forme de nombres binaires, c’est-à-dire formés de séquences de 0 et de 1 uniquement, comme nous le verrons en détails dans le Chapitre 2. Cela signiﬁe également que les traite- ments exécutés (et exprimés à l’aide des instructions connues de l’ordinateur) réalisent eux aussi des opérations sur des nombres (ce sont des opérations logiques et arithmé- tiques). Ces éléments constituent les caractéristiques généralement retenues pour déﬁnir un ordi- nateur : (1) la possibilité d’exécuter un programme arbitraire, qui peut être modiﬁé, et est donc stocké dans la mémoire de l’ordinateur au même titre que les données qui sont trai- tées 2 ; et (2) la représentation et le traitement numérique de l’information (y compris du pro- gramme à exécuter). 1.2. Un premier modèle : l’architecture de von Neumann Maintenant que nous savons ce que fait un ordinateur, nous devons répondre à la question du comment ? Dans une première approche, nous allons partir d’un exemple de programme, 2. Il doit également être possible d’écrire des programmes complexes, comprenant des boucles et des sauts. La notion précise est la notion de machine Turing-complète, telle que déﬁnie par le mathématicien anglais Alan T URING. Nous ne développerons pas cette notion en détail ici, le lecteur intéressé peut consulter une intro- duction à la calculabilité comme l’excellent ouvrage de Pierre W OLPER. 21 1. Leçon 1 – Introduction : Qu’est-ce qu’un ordinateur ? 1 """ 2 Calcul des racines d ’ une équation du second degré 3 """ 4 __author__ = " Thierry Massart " 5 __date__ = " 22 août 2012 " 6 7 from math import sqrt 8 a = float ( input ( " valeur de a : " )) 9 b = float ( input ( " valeur de b : " )) 10 c = float ( input ( " valeur de c : " )) 11 12 delta = b **2 - 4* a * c 13 if delta < 0: 14 print ( " pas de racines réelles " ) 15 elif delta == 0: 16 print ( " une racine : x = " , -b /(2* a )) 17 else : 18 racine = sqrt ( delta ) 19 print ( " deux racines : x1 = " , \ 20 ( - b + racine )/(2* a ) , " x2 = " , ( - b - racine ) / (2* a )) F IGURE 1.2. – Un exemple de programme écrit en langage Python. emprunté au cours de Programmation (INFO-F-101). Il s’agit d’un exemple écrit en Python, et qui calcule les éventuelles racines réelles d’une équation du second degré à une inconnue. Il est donné à la Figure 1.2. Cet exemple est fort utile car il illustre bien les différentes ressources dont l’ordinateur a besoin pour exécuter un programme. En voici la liste : — L’ordinateur doit disposer d’un moyen d’obtenir des données en entrée (c’est-à-dire les données à traiter). Dans notre exempele, le mot-clé input interroge l’utilisateur qui entre les données via le clavier. Ces données sont stockées dans des variables a, b et c. — L’ordinateur doit être capable de stocker des données de manière temporaire, c’est-à- dire durant la durée d’exécution d’un programme. Ces données temporaires corres- pondent en général aux données d’entrée, ou aux résultats de calculs intermédiaires. Dans notre exemple, les variables a, b, c et delta représentent ces stockages tempo- raires. Notez bien que delta n’est pas une donnée d’entrée du programme, mais bien une valeur intermédiaire du calcul. — L’ordinateur doit pouvoir communiquer ses résultats au monde extérieur. Dans notre exemple, le mot-clé print permet d’afﬁcher des messages ainsi que certaines variables. — L’ordinateur doit avoir la capacité d’effectuer certaines opérations de base, sans que l’utilisateur n’ait besoin d’écrire un programme pour expliciter à l’ordinateur le sens de ces opérations de base. C’est le cas, par exemple des opérations arithmétiques : elles 22 1.2. Un premier modèle : l’architecture de VON N EUMANN sont considérées comme « connues » et peuvent être utilisées dans un programme sans qu’il soit nécessaire d’expliciter le calcule du +, du -, etc. Dans notre exemple, ces opé- rations interviennent dans le calcul du delta. L’ensemble des opérations de base connues de l’ordinateur, et qu’on peut utiliser pour écrire un programme, composent ce qu’on appelle un langage. Le langage principal d’un ordinateur est ce qu’on appelle le langage machine. C’est ce langage qui opère di- rectement sur la représentation binaire des informations. Notre exemple, lui, est écrit dans une langage différent : le langage Python. Dans ce langage (et donc dans notre exemple), on ne voit pas la représentation binaire des informations apparaître explici- tement 3. Au contraire, Python permet d’exprimer les opérations sur des données plus abstraites, et donc plus facilement compréhensibles par un être humain, comme le texte qui est afﬁché pour présenter le résultat. Le langage Python offre donc une fa- cilité accrue par rapport au langage machine. Mais, aﬁn qu’il puisse être exécuté par l’ordinateur, il devra d’abord être traduit en langage machine. — Bien que cela apparaisse de manière moins évidente sur notre exemple, l’ordinateur doit également être capable de stocker le programme à exécuter (puisque celui-ci peut être modiﬁé) pour pouvoir s’y référer, et ainsi avoir la capacité d’accéder à la bonne instruction à exécuter. Pour ce faire, il faut aussi disposer d’un moyen retenant l’avan- cement de l’exécution dans le programme, et de modiﬁer cet état d’avancement. Cette modiﬁcation peut consister soit à passer à l’instruction suivante dans le programme, soit à désigner une instruction arbitraire comme étant celle à exécuter en prochain lieu, éventuellement selon certaines conditions (c’est ce que fait l’instruction if dans notre exemple). Sur base de ces besoins, on peut proposer un premier mo- dèle abstrait de ce qui est nécessaire pour concevoir une telle machine. Notre modèle est présenté à la Figure 1.3. Il s’agit d’une conception de l’ordinateur qui a été proposée par John VON N EUMANN 4 en 1945 , et sur lequel tous les ordina- teurs modernes se basent. Il est bien entendu que ce modèle est une simpliﬁcation (sans doute un peu grossière) de la réa- lité, mais elle est sufﬁsante, en première approximation, pour expliquer les principes généraux de fonctionnement de l’ordi- nateur. Nous rafﬁnerons cette ﬁgure dans la suite. Notons que ce modèle est souvent appelé architecture de von Neumann ou John VON N EUMANN. architecture à programme enregistré (stored program architec- ture en anglais). On utilise ici le terme architecture, car le mo- dèle explique quels sont les différents composants de l’ordinateur et comment ils sont utili- sés, interconnectés, pour bâtir la machine qu’est l’ordinateur. En analysant cette ﬁgure, nous pouvons constater : — que l’O RDINATEUR (cadre gras) communique avec le monde extérieure à travers des 3. Par exemple, la valeur 2 utilisé dans la dernière ligne du programme n’est pas exprimée en binaire, sans quoi on aurait écrit 10 (voir Chapitre 2) 4. Mathématicien hongrois, né à Budapest le 28 décembre 1903, mort à Washington, le 8 février 1957. 23 1. Leçon 1 – Introduction : Qu’est-ce qu’un ordinateur ? dispositifs appelés périphériques d’entrée/sortie (par exemple : le clavier, la souris, l’écran, etc) ; — que l’ordinateur est composé essentiellement de deux composants : le processeur (ou en anglais, Central Processing Unit, CPU) et la mémoire. Ce sont les deux cadres aux bords arrondis sur la ﬁgure ; et enﬁn — que le processeur est lui-même composé d’une unité de contrôle, d’une unité arithmético- logique (en anglais Arithmetic and Logic Unit, ALU) et de registres. Détaillons maintenant les rôles de ces différents composants, pour l’exécution d’un pro- gramme. Tout d’abord, le programme et ses données sont stockées dans la mémoire, qui, comme son nom l’indique, est un composant servant à mémoriser (stocker) l’information. Comme cette mémoire est modiﬁable, on peut également modiﬁer le programme ou l’ap- pliquer à d’autres données ; ce qui est essentiel dans notre déﬁnition d’ordinateur (cela ex- plique le nom d’architecture à programme enregistré, car le programme est enregistré dans la mémoire). Ensuite, le processeur a pour tâche d’exécuter le programme, instruction par instruction. Pour ce faire, il interroge la mémoire qui lui transmet la prochaine instruction à exécuter ; puis, il analyse et exécute celle-ci, et recommence ad inﬁnitum. Le processeur a donc un comportement cyclique que l’on représente par la boucle d’interprétation du processeur par- fois appelée également fetch–decode–execute, du nom des trois étapes principales (en an- glais) : 1. fetch : aller chercher la prochaine instruction à exécuter, en mémoire. Cela signiﬁe, comme nous l’avons déjà dit, que le processeur doit avoir un moyen d’identiﬁer cette instruction parmi d’autres en mémoire. C’est un des rôles (mais pas le seul) des re- gistres. 2. decode : il s’agit ici d’analyser la représentation binaire de l’instruction (en langage ma- chine) pour en déduire l’opération à effectuer. 3. execute : exécuter l’instruction à proprement parler. Les éléments du CPU en charge de l’exécution d’une instruction sont les registres et l’ALU. D’une part, les registres sont des zones de mémoire de très petite capacité mais d’accès très rapide. Ils stockent principalement : l’instruction machine en cours d’exécution, ses données, et ses résul- tats. D’autre part, l’ALU est un circuit électronique du processeur qui peut appliquer une opération arithmétique ou logique à deux données provenant des registres. Par exemple, si l’on souhaite faire la somme de deux nombres, il faudra placer les deux va- leurs dans des registres, transmettre ces valeurs à l’ALU qui effectuera la somme, puis placer le résultat dans un registre. Nous décrirons ce procédé plus en détail à la Sec- tion 3.2, et surtout au Chapitre 5. L’effet d’une instruction peut également être d’écrire ou de lire une valeur en mémoire (depuis ou vers les registres), ou encore de communiquer avec les périphériques. La coordination de ces trois étapes est assurée par l’unité de contrôle du CPU. Ainsi, l’unité de contrôle doit s’assurer que ce sont les bons registres qui transmettent leurs données à l’ALU, que l’ALU applique la bonne opération aux données (il faut choisir l’opération à effectuer 24 1.2. Un premier modèle : l’architecture de VON N EUMANN O RDINATEUR Processeur (CPU) Unité de contrôle Unité arithmético-logique (ALU) Entrées / Sorties Registres Mémoire F IGURE 1.3. – L’architecture VON N EUMANN, un premier modèle d’ordinateur. parmi une palette d’opérations disponibles), que le résultat calculé par l’ALU est placé dans le bon registre de sortie, etc. Dans le Chapitre 3, nous expliquerons plus en détail le fonctionnement de cette boucle. Dans le Chapitre 7, nous rafﬁnerons cette boucle pour introduire un mécanisme d’interruption, qui est essentiel au bon fonctionnement des ordinateurs modernes. ß Dans ces notes de cours, nous utiliserons souvent la famille de processeurs x86 de la ﬁrme Intel comme exemples pour illustrer les notions relatives aux pro- cesseurs. On retrouve aujourd’hui ces processeurs dans l’immense majorité des ordinateurs personnels. En particulier, nous considérerons le processeur i486. Il s’agit d’un processeur qui a été commercialisé de 1989 à 2007, et il a des performances relativement modestes si on le compare aux processeurs récents. Néanmoins, il possède plu- sieurs des caractéristiques intéressantes des processeurs modernes, tout en res- tant relativement simple. Il constitue donc un excellent exemple pédagogique.../. 25 1. Leçon 1 – Introduction : Qu’est-ce qu’un ordinateur ? L’architecture de l’i486 est montrée à la Figure 1.4. Comme on peut le voir, elle... est bien plus complexe que notre simple modèle de la Figure 1.3 ! Mais nous pouvons déjà reconnaître certains éléments : — En jaune, sur la gauche de la ﬁgure, nous retrouvons l’ALU (avec le shif- ter qui peut également être vu comme un circuit réalisant des opérations arithmétiques), et les registres servant à contenir des données (l’ensemble de ces registres est appelé register ﬁle). L’i486 possède au total 32 registres qui ont des fonctions différentes. En particulier, les 4 registres appelés eax, ebx, ecx et edx servent à stocker les données sur lesquelles opèrent les instructions. Ce sont des registres de 32 bits. L’i486 possède également 8 registres spécialisés de 80 bits, qui permettent d’effectuer des opérations arithmétiques sur des nombres décimaux (dont nous parlerons dans la Section 2.2.5). Ces opérations un peu spéciales ne sont pas réalisées par l’ALU, mais par le FPU (pour ﬂoating point unit), en orange, sur la gauche de la ﬁgure. — Les ﬂèches noir à droite de l’image représentent les canaux de commu- nication du processeur avec le monde extérieur, c’est-à-dire avec la mé- moire (deux ﬂèches du haut) et les périphériques. — On reconnait également un bloc chargé du décodage des instructions (dans le base de la ﬁgure) et un bloc chargé de la lecture en mémoire (fetch), appelé ici prefetcher. 1.3. Une vision diﬀérente : structure en niveaux et traductions Maintenant que nous avons identiﬁé les différents composants d’un ordinateur et leurs fonctions, nous pouvons approfondir la question du comment ? posée au début de la section précédente. Nous consacrerons évidemment tout le cours à expliquer comment les différents composants que nous avons identiﬁés remplissent leur fonction, mais nous pouvons déjà donner une vue globale qui correspondra au plan de l’exposé. Diﬀérents niveaux Partons du CPU. Celui-ci est composé de circuits électroniques que nous appellerons circuits logiques, et que nous étudierons dans les Chapitre 4. C’est à l’aide de ces circuits logiques que le CPU doit donc interpréter le langage machine. Comme nous le verrons plus tard, l’interprétation de chaque instruction en langage machine n’est pas im- médiate : le langage machine est d’abord traduit dans une langage plus simple encore, le microlangage, lequel est enﬁn exécuté à l’aide des circuits logiques. Tout comme un pro- gramme (en langage machine) se compose d’une série d’instructions (appelées instructions machine), chaque instruction machine est traduite 5 en une série de micro-instructions (les instructions du micro-langage). Nous avons donc identiﬁé les trois « couches » les plus basses de l’ordinateur, à savoir (et en partant de la couche la plus basse) : 5. À l’aide d’une boucle similaire à la boucle fetch–decode–execute. 26 Intel 80486DX2 Architecture 64 Bit Interunit Transfer Bus Core 32 Bit Data Bus Clock Clock Clock 32 Bit Data Bus Multiplier Linear Address 32 Bit PCD PWT 2 A31 - A2, Barrel Segmentation Cache Address BE3# - BE0# 32 Bit Shifter Unit 20 Bit Unit Drivers Paging Descriptor Unit Physical Register Write Buffers 32 Bit Address 32 Bit File Registers 4 x 32 8 KiB Limit and Translation Cache Data Bus D31 - D0 ALU Attribute Lookaside 32 Bit Tranceivers PLA Buffer Bus Control ADS#, W/R#, D/C#, M/IO#, PCD, PWT, RDY#, LOCK#, 128 Bit PLOCK#, BOFF#, A20M#, BREQ, HOLD, HLDA, RESET, Displacement Bus SRESET, INTR, NMI, SMI#, SMIACT#, FERR#, IGNNE#, Micro-Instruction 32 Bit Prefetcher Request STPCLK# Sequencer 32 Byte Code Burst Bus BRDY#, BLAST# 24 Bit Queue Control Control & Instruction FPU Protection Decode Code Stream (2 x 16 Byte) Test Unit Bus Size BS16#, BS8# Decoded Control Floating Instruction Path KEN#, FLUSH#, AHOLD, Point Control Cache EADS# Register ROM Control File Parity Generation DP3 - DP0, PCHK# and Control Boundary Scan TCK, TMS, TDI, TD0 Control F IGURE 1.4. – L’architecture de l’i486 (sous sa variante 80486DX2), telle que publiée par Intel. Source : Appaloosa (https://commons.wikimedia.org/wiki/File:80486DX2_arch.svg), « 80486DX2 arch », https://creativecommons.org/licenses/by-sa/3.0/legalcode 27 1.3. Une vision différente : structure en niveaux et traductions 1. Leçon 1 – Introduction : Qu’est-ce qu’un ordinateur ? 0. les circuits logiques (le véritable matériel constitutif de l’ordinateur) ; 1. le micro-langage ; et 2. le langage machine, qui est le langage du CPU. Durant ce cours, nous nous concentrerons essentiellement sur ces trois couches. Mais tout qui a un jour utilisé un ordinateur sait pertinemment bien que celui-ci peut être utilisé sans interagir directement avec le processeur, à l’aide du langage machine. L’exemple de la Figure 1.2 est écrit, comme nous l’avons déjà dit, en Python, un langage plus abstrait (on dit aussi : « de plus haut niveau ») que le langage machine, ce qui est une facilité non- négligeable. En effet, un même programme en langage Python peut être exécuté par des or- dinateurs différents qui ont potentiellement des caractéristiques (nombre de registres, lan- gage machine) différentes. Cela n’a pas d’importance pour le programmeur qui a écrit son programme en Python, car ce langage ne demande pas et ne permet pas d’interagir directe- ment avec les composants matériels de base (ALU, registres) de la machine. Au contraire, si on souhaite exécuter un programme en Python sur un ordinateur donné, il faut disposer d’un interpréteur, qui est lui-même un programme qui traduit le programme en langage Python vers une séquence d’instructions machine propres à l’ordinateur sur lequel le programme Python doit être exécuté. Par ailleurs, tout ordinateur personnel, tout smartphone est aujourd’hui livré avec un pro- gramme de base, permettant d’interagir facilement avec lui, et appelé « système d’exploita- tion », ou operating system, ou encore OS (par exemple, Windows, Linux, MacOS, Android, iOS, etc). Tous ces programmes sont in ﬁne exécutés par le processeur et doivent donc être traduits en langage machine. Au ﬁnal, nous avons 3 couches supplémentaires qui s’empilent au-dessus du langage machine : 3. le système d’exploitation, dont nous parlerons brièvement à la ﬁn du cours, mais qui fera surtout l’objet d’un cours de deuxième année ; 4. l’assembleur, qui est un langage intermédiaire entre le langage machine et les pro- grammes écrits dans un langage de haut niveau. L’assembleur sera étudié dans le cours de langages de programmation, au second quadrimestre ; 5. les langages de haut niveau, qui sont ceux à l’aide desquels on écrit les applications que l’on utilise quotidiennement (traitement de texte, navigateur web, etc). Le cours de programmation vous enseigne un de ces langages (python) et le cours de langages de programmation (second quadrimestre) vous en enseignera d’autres. De bout en bout, l’exécution d’un programme de haut niveau peut donc se résumer comme suit : le programme de haut niveau (niveau 5) est traduit en assembleur (niveau 4). L’assem- bleur est traduit en un langage qui est essentiellement du langage machine augmenté d’ap- pels aux services prodigués par le système d’exploitation (niveau 3). Ces « appels systèmes » sont eux-mêmes traduits en langage machine, et on obtient alors, au niveau 2, un programme entièrement en langage machine. L’exécution de ce programme machine par le CPU consiste en une traduction vers le micro-langage interne au CPU (niveau 1), dont le résultat est ﬁna- lement exécuté à l’aide de circuits logiques (niveau 0). 28 1.3. Une vision différente : structure en niveaux et traductions Interprétation et Compilation On voit donc qu’on a affaire à une chaîne de traductions successives. Celles-ci peuvent être effectuées de deux façon différentes : — soit un programme d’un certain niveau est intégralement traduit en un programme du niveau inférieur, avant le début de l’exécution. On parle alors de compilation. Le résultat de la traduction peut être stocké et réutilisé, mais ne sera plus modiﬁé durant l’exécution. La compilation est réalisée à l’aide d’un programme appelé compilateur. C’est le cas de la plupart des applications que nous téléchargeons sur Internet (que ce soit pour un ordinateur de bureau ou pour un smartphone) : elles ont été écrites dans un langage de haut niveau par leurs concepteurs, puis compilées en langage machine. C’est le résultat de cette compilation qui est distribué et téléchargé par les utilisateurs ﬁnaux ; — soit un programme d’un certain niveau est traduit vers le niveau inférieur, instruction par instruction, au moment de l’exécution. On parle alors d’interprétation. C’est ce qui se passe, par exemple, quand on traduit le langage machine en micro-code, de qui per- met au processeur d’exécuter le langage machine. De manière générale, un interpréteur est un programme écrit dans un langage de ni- veau i et qui interprète un programme écrit dans un langage de niveau j > i , instruc- tion par instruction, c’est-à-dire en exécutant continuellement une boucle qui consiste à : (1) lire la prochaine instruction à exécuter ; (2) analyser et exécuter cette instruction ; (3) passer à l’instruction suivante. Le CPU peut donc être vu comme la réalisation d’un interpréteur pour le langage machine, réalise à l’aide de micro-code. La hiérarchie de niveaux que nous venons de décrire, ainsi que les différents types de tra- ductions entre ces niveaux, sont présentés à la Figure 1.5. Matériel et logiciel Notons ﬁnalement que chacun des 6 niveaux peut théoriquement être réalisé soit à l’aide de matériel soit à l’aide de logiciel. Élucidons ces deux termes : — le matériel (hardware en anglais) est l’ensemble des dispositifs physiques qui consti- tuent l’ordinateur ; tandis que — un logiciel (software en anglais) est une représentation informatique des informations nécessaires à un traitement réalisé par l’ordinateur, à savoir, la séquence d’instructions à exécuter, et les données. En pratique, les niveaux 0,1 et 2 sont réalisés à l’aide de matériel, et les niveaux 3, 4 et 5 à l’aide de logiciel. Le logiciel et le matériel ont chacun leurs avantages et leurs inconvénients. Le logiciel est plus ﬂexible, dans le sens où on peut le modiﬁer et le remplacer, mais plus lent. Le matériel est plus rapide, mais n’est pas modiﬁable, en général. Il est par exemple possible de changer d’interpréteur Python (niveau 5) si jamais une nouvelle version de ce langage venait à être proposée. Par contre, le processeur, qui exécute le langage machine, doit être très rapide, et on ne peut pas modiﬁer la traduction du langage machine en micro-langage (niveau 2 vers niveau 1). 29 1. Leçon 1 – Introduction : Qu’est-ce qu’un ordinateur ? Niveau 5 : les langages de haut niveau (Python, C, C++,... ) Compilation (appels systèmes) Niveau 4 : Logiciel l’assembleur Compilation (assemblage) Niveau 3 : le système d’exploitation (Linux, Windows, MacOS... ) Compilation Niveau 2 : le langage machine, langage du CPU Interprétation Matériel Niveau 1 : (dans le CPU) le micro-code Interprétation Niveau 0 : les portes logiques F IGURE 1.5. – Les 6 couches décrivant le fonctionnement d’un ordinateur. M8N 30 2. Leçons 2 à 4 – Représentation de l’information Avant de pouvoir étudier la manière dont l’ordinateur traite l’information, nous devons ﬁxer la manière dont cette information est représentée. L’objet de ces leçons est d’étudier la représentation binaire, qui est aujourd’hui 1 la représentation universellement utilisée en informatique pour toutes les informations que les ordinateurs manipulent. La représentation binaire signiﬁe que toute l’information sera représentée à l’aide de deux symboles uniquement. Ces deux symboles sont en général les chiffres 0 et 1, mais on peut également considérer que ce sont les valeurs lo- giques faux et vrai. Dans ce chapitre, nous développerons des techniques permettant de représenter tout type d’information (nombres, texte, images,... ) à l’aide d’un représentation binaire, et de manipu- ler cette représentation. Nous verrons également comment concevoir des techniques de dé- tection et de correction d’erreur sur cette représentation. Mais avant d’aborder cette matière, il est important de bien comprendre la différence entre une information, et sa représentation. L’exemple suivant illustre cette différence. ß Considérons la quantité 17, nous pouvons en trouver plusieurs représentations : — la représentation usuelle, dite « en base 10 » : 17, — en base 2 : 10001 (nous aborderons les les notions de base et de change- ment de base en détail dans la suite), — en chiffres romains : XVII, — en utilisant des marques de dénombrement : HHH IIII HH IIII H II, IIII —... On voit donc qu’une même information, qu’un même concept admet plusieurs repré- sentations. Le choix de la représentation binaire comme représentation universelle en in- formatique s’explique par le fait qu’on peut aisément représenter deux valeurs différentes à l’aide d’états différents de composants électriques comme les transistors. Ces même transis- tors, assemblés en portes logiques, permettent également de manipuler l’information binaire, comme nous le verrons dans le Chapitre 3. 1. Il y a eu quelques expériences utilisant des représentations ternaires. On peut citer les ordinateurs sovié- tiques Setun (1959–1965). 31 2. Leçons 2 à 4 – Représentation de l’information 2.1. Unités de quantité d’information Commençons par ﬁxer des unités permettant de mesurer la quantité d’information. Nous utiliserons la taille de la représentation binaire de l’information comme mesure : Chaque chiffre (0 ou 1) d’une représentation binaire est appelé bit (contraction de l’anglais binary digit, ou chiffre binaire). Une séquence de 8 bits est appelée un octet (ou byte en anglais). Les symboles associés à ces unités sont les suivants : Unité Symbole bit b octet o byte B Nous mesurerons donc l’information en terme de bits ou d’octets (bytes). Naturellement, les quantités d’information manipulées usuellement s’expriment en milliers, millions,... d’oc- tets, il faut donc ﬁxer des noms pour ces unités. Les préﬁxes ofﬁciellement reconnus par l’in- dustrie sont similaires aux kilo-, méga-,... du système SI. Ces préﬁxes ne se réfèrent pas à des puissances de 10 comme dans le système SI mais à des puissances de 2 : Nom Abréviation Quantité kibioctet Kio 210 = 1024 ≈ 103 octets mébioctet Mio 2 = 1 048 576 ≈ 106 octets 20 gibioctet Gio 230 = 1 073 741 824 ≈ 109 octets tebioctet Tio 2 = 1 099 511 627 776 ≈ 1012 octets 40 La déﬁnition de ces préﬁxes est relativement récente (elle date du début des années 2000). En pratique, on est souvent confronté à l’utilisation des préﬁxes traditionnels kilo-, méga-, tera-, etc du système SI, qui sont, pour rappel : Nom Abréviation Quantité kilooctet ko 103 octets mégaoctet Mo 106 octets gigaoctet Go 109 octets teraoctet To 1012 octets On voit donc qu’un mégaoctet est un petit peu plus petit qu’un mébioctet... Force est de re- connaître qu’une certaine confusion règne ! Cette confusion a d’ailleurs donné lieu à des pro- cès retentissants, notamment aux États-Unis, où des consommateurs ont entamé une class action contre plusieurs fabricants de disques durs et mémoires, les accusant de tromperie sur la capacité de stockage des produits 2. 2. Voir par exemple : https://en.wikipedia.org/wiki/Binary_prefix#Inconsistent_use_of_units. 32 2.2. Écriture des nombres dans différentes bases 2.2. Écriture des nombres dans diﬀérentes bases Nous allons maintenant rappeler les techniques permettant de représenter des nombres dans différentes bases, car ces techniques serviront à expliquer les différents encodages bi- naires des nombres entiers et rationnels. La représentation usuelle des nombres est une représentation décimale et positionnelle. Cela signiﬁe : 1. que les nombres sont représentés par une séquence de chiffres de 0 à 9 inclus. Il y a bien dix chiffres différents utilisés, d’où le terme décimal ; et 2. que la position de chaque chiffre dans la séquence permet d’associer ce chiffre à une puissance de 10. Dans cette représentation usuelle, 10 est appelé la base. On parle aussi de représentation en base 10. ß Par exemple, la représentation : 1234,56 signiﬁe que le nombre est composé de : — 4 unités, ou 4 × 100 ; — 3 dizaines, ou 3 × 101 ; — 2 centaines, ou 2 × 102 ; — 1 millier, ou 1 × 103 ; — 5 dixièmes, ou 5 × 10−1 ; et — 6 centièmes, ou 6 × 10−2. On voit donc que les puissances de 10 associées aux différentes positions (aux différents chiffres) vont décroissantes quand on lit le nombre de gauche à droite, et que la puissance 100 correspond au chiffre qui se trouve juste à gauche de la virgule. On note également que la base donne le nombre de chiffres que l’on peut utiliser pour représenter les nombres. En base 10, on peut utiliser 10 chiffres différents, à savoir les chiffres de 0 à 9 inclus. Ces concepts se généralisent dans n’importe quelle base. Fixons à partir de maintenant une base b ≥ 2. Dans cette base, le nombre : d n · · · d 0 , d −1 · · · d −k représente la valeur : N = d n × b n + d n−1 × b n−1 + · · · + d 0 × b 0 + d −1 × b −1 + · · · d −k × b −k (2.1) Xn = di × b i , (2.2) i =−k 33 2. Leçons 2 à 4 – Représentation de l’information où tous les d i sont des chiffres dans {0,... ,b − 1}. Si on ﬁxe b = 2, le nombre 1001,101 représente : ß 1 × 23 + 0 × 22 + 0 × 21 + 1 × 20 + 1 × 2−1 + 0 × 2−2 + 1 × 2−3 1 1 = 8+0+0+1+ +0+ 2 8 = 9,625. La dernière valeur est bien entendu donnée en base 10. Symétriquement, la valeur −4,5 (en base 10) est représentée par : −100,1 en base 2. Notons au passage que cette dernière représentation n’est pas stricto sensu une représentation binaire, étant donné que les symboles , (virgule) et − (moins unaire) sont utilisés, en plus du 0 et du 1. Nous verrons plus tard com- ment une telle valeur peut être représentée en utilisant des 0 et des 1 unique- ment. Aﬁn d’éviter toute confusion dans la suite, nous noterons, quand c’est nécessaire, la base en indice des nombres. Par exemple, 1012 signiﬁe que le nombre 101 doit être interprété comme étant en base 2 (c’est-à-dire 510 ). Notons que dans certains langages de program- mation, comme le C , on utilise d’autres conventions pour expliciter certaines bases : les nombres en base 16 sont préﬁxés par 0x, et les nombres en base 2 par 0b. Enﬁn, notons qu’en base 2, nous grouperons souvent les bits par paquets de 4, en introduisant un petit espace, et ce, uniquement dans un souci de lisibilité. Nous écrivons ainsi 1011 1001 au lieu de 10111001. En informatique, les bases usuelles sont la base 2, la base 8 (on parle d’octal) et la base 16 (on parle d’hexadécimal). Pour la base 16, on est confronté au problème suivant : les chiffres utilisés devraient être 0, 1,... , 10, 11, 12, 13, 14 et 15. Mais les « chiffres » de 10 à 15 demandent deux symboles pour être représentés, ce qui risque de porter à confusion. Par exemple, doit- on interpréter 1016 comme le chiffre 10 (et alors 1016 = 1010 ) ou comme les chiffres 1 et 0 (et donc 1016 = 1 × 16 + 0 × 1 = 1610 ) ? Pour éviter ce problème, on remplace les « chiffres » de 10 à 15 par les lettres de a à f, selon la correspondance suivante : Lettre : a b c d e f Valeur : 10 11 12 13 14 15 ß En base 16 : a5f,b = 10 × 162 + 5 × 161 + 15 × 160 + 11 × 16−1 = 2655,687510. 34 2.2. Écriture des nombres dans différentes bases Sur base de ces déﬁnitions, nous pouvons déjà faire quelques remarques utiles. Chiﬀres de poids fort, de poids faible Dans la représentation positionnelle usuelle, le chiffre le plus à gauche est associé à une puissance plus élevée de la base. On parle donc de chiffre de « poids fort » ; le chiffre étant associé à la puissance la plus faible est appel chiffre de « poids faible ». En particulier, en binaire, on parle de bit de poids fort et bit de poids faible. Comme nous l’avons dit, le bit de poids fort est, par convention à gauche dans la repré- sentation (positionnelle) usuelle. Mais quand on s’intéresse à des valeurs qui ne sont plus écrites sur papier, mais bien stockées ou manipulées par des circuits électroniques (où les notions de « gauche » et « droite » n’ont pas forcément de sens), il est parfois utile de préciser explicitement quel est le bit de poids fort ou le bit de poids faible. Ajouts de zéros Dans toutes les bases, et à condition d’utiliser la représentation position- nelle usuelle (avec le chiffre de poids fort à gauche), on peut toujours ajouter des 0 à gauche de la partie entière ou à droite de la partie décimale, sans modiﬁer la valeur du nombre re- présentée. Par exemple, 13,510 = 0013,500010. Par contre, on ne peut pas ajouter de zéros à d’autres endroits sans modiﬁer la valeur du nombre. Par exemple, 1012 6= 1010002 (voir aussi la remarque suivante). Multiplier ou diviser par la base Dans toutes les bases, on peut aisément multiplier ou diviser par la base en déplaçant la position de la virgule : Dans toute base b, déplacer la virgule de k position vers la droite (ou ajouter k zéros à droite dans le cas d’un nombre entier) revient à multiplier par b k. Déplacer la virgule de k positions vers la gauche revient à diviser par b k. Si on souhaite faire une division entière par b k , le reste est constitué des k chiffres de poids faible, et on obtient le quotient en retranchant ces k chiffres de poids faible. Nous utiliserons les opérateurs ÷ et mod pour noter respectivement la division entière et le reste de la division. Voici quatre exemples qui illustrent ces remarques : ß 101,1112 × 410 = 101,1112 × 22 = 10111,12 101,1112 /210 = 10,11112 1011 10112 ÷ 1002 = 1011 10112 ÷ 22 = 10 1110 1011 10112 mod 1002 = 112. 35 2. Leçons 2 à 4 – Représentation de l’information Combien de nombres représentables sur n chiﬀres ? Enﬁn, l’observation suivante aura toute son importance dans la suite. Fixons une base b et considérons des nombres entiers positifs sur n chiffres. Nous avons b choix pour chacun de ces n chiffres, soit un total de b n nombres différents que l’on peut représenter sur n chiffres. Ces nombres sont tous les nombres de : | ·{z 0 · · 0} n chiffres à: (b − 1) · · · (b − 1) = b n − 1. | {z } n chiffres En base b, il y a b n nombres (entiers positifs) représentables sur n chiffres : les nombres de 0 à b n − 1. Il y a donc 2n nombres binaires sur n bits. Ainsi, il y a 232 = 4 294 967 29610 (soit ß à peu près 4 milliards de) nombres binaires différents sur 32 bits. De même, il y a 28 = 256 nombres binaires sur 8 bits. Ce sont les nombres de 0000 0000 à 1111 1111. On observe que 0000 0000 est la représentation binaire de 0 est 1111 1111 est la représentation binaire de 255. Il y a donc bien 256 nombres de 0 à 255 inclus. 2.2.1. Changements de base Comment peut-on, étant donné un nombre N donné dans une certaine base, trouver sa représentation dans une autre base b ? Répondre à cette question revient à calculer les valeurs d i de l’équation (2.2) dans la base b. Cas des nombres entiers Nous allons commencer par supposer que N est un nombre en- tier positif. Observons d’abord que si N < b, on exprime le nombre à l’aide du chiffre corres- pondant dans la nouvelle base 3. Autrement, divisons N par b (il s’agit de la division entière), ce qui nous donne un quotient q 0 = N ÷b et un reste r 0 = N mod b. La relation existant entre ces valeurs est : N = q0 × b + r 0. (2.3) Comme nous avons supposé que N ≥ b, nous savons que q 0 6= 0. Recommençons l’opéra- tion en divisant q 0 par b ; nous obtenons à nouveau un quotient que nous appelons q 1 et un reste que nous appelons r 1. Nous avons donc la relation : q0 = q1 × b + r 1 , 3. Par exemple, 1010 est exprimé par a en base 16. 36 2.2. Écriture des nombres dans différentes bases En combinant cette équation avec (2.3), nous obtenons : N = (q 1 × b + r 1 ) × b + r 0 = q1 × b 2 + r 1 × b + r 0. Si q 1 > 0, on recommence en divisant q 1 par b, pour obtenir un nouveau quotient q 2 et un nouveau reste r 2 tels que : N = (q 2 × b + r 2 ) × b 2 + r 1 × b + r 0 = (q 2 × b 3 ) + r 2 × b 2 + r 1 × b + r 0. Si nous continuons ce développement en réalisant k + 1 divisions, nous obtenons une suite de restes r 0 , r 1 ,... r k tels que : N = (q k × b k+1 ) + r k × b k + · · · + r 2 × b 2 + r 1 × b + r 0. Supposons que nous avons continué ce développement jusqu’à ce que q k = 0 (ce qui ﬁnira toujours par arriver étant donné qu’on est parti d’un N ﬁxé). On a alors : N = (q k × b k+1 ) + r k × b k + · · · + r 2 × b 2 + r 1 × b + r 0 = (q k × b k+1 ) + r k × b k + · · · + r 2 × b 2 + r 1 × b 1 + r 0 × b 0 X k = (q k × b k+1 ) + ri × bi i =0 X k = (0 × b k+1 ) + ri × bi i =0 X k = ri × bi. (2.4) i =0 On peut maintenant comparer cette dernière équation (2.4) à l’équation (2.2), et constater que les restes r i que nous avons calculés en effectuant des divisions successives par b corres- pondent aux d i que nous cherchons pour représenter le nombre N en base b. Attention tout de même que le premier reste calculé (r 0 ) est le chiffre de poids faible ! Pour résumer : Pour exprimer un nombre N en base b, on divise N par b de manière répétée. La séquence des restes calculés donne la représentation de N en base b du chiffre de poids faible au chiffre de poids fort (autrement dit : « à l’envers »). Nombres réels Nous pouvons maintenant généraliser ce principe aux nombres réels 4. Com- mençons par observer qu’un nombre rationnel qui possède une expression ﬁnie dans une 4. En pratique, sur un ordinateur, nous ne pourrons représenter et manipuler de manière précise que les nombres qui p possèdent une représentation ﬁnie en base 2, ce qui exclut d’ofﬁce tous les nombres irrationnels, comme π ou 2, par exemple. Mais cela n’empêche que même les nombres irrationnels possèdent une représen- tation (inﬁnie non-périodique) dans d’autres bases que la base 10. 37 2. Leçons 2 à 4 – Représentation de l’information base donnée ne possède pas forcément une expression ﬁnie dans toutes les bases. Prenons par exemple le nombre 13. Nous savons qu’il n’est pas possible de l’exprimer de manière ﬁnie en base 10, mais bien de manière inﬁnie périodique : 1 = 0,3333... 3 Nous notons cette représentation inﬁnie périodique en soulignant la partie qui se répète in- ﬁniment souvent : 1 = 0,3. 3 Par contre, comme 1 3 = 3−1 , on peut exprimer 1 3 de manière ﬁnie en base 3 : 1 = 0,13. 3 Voyons maintenant comment représenter un nombre N < 1 dans une base b arbitraire. Notons que nous supposons que N < 1 car on peut traiter séparément la partie entière et la partie fractionnelle d’un nombre. Pour exprimer N en base b, nous allons procéder par multiplication successive par b. Supposons que N est de la forme : N = 0,α0 où α0 représente la séquence de chiffres de la partie fractionnaire du nombre. En multipliant N par b on obtient un nouveau nombre de la forme : N × b = β1 ,α1 où β1 est la partie entière, et α1 la partie décimale. Comme nous avons supposé que N < 1, nous savons que 0 ≤ β1 ≤ b − 1. Considérons le nouveau nombre 0,α1 , et appelons-le N1. Nous avons donc : N1 = 0,α1 β1 N 1 N= +. (2.5) b b Multiplions maintenant N1 par b, nous obtenons un nombre de la forme : N1 × b = β2 ,α2 avec 0 ≤ β2 ≤ b − 1. Nous pouvons à nouveau poser N2 et obtenir : N2 = 0,α2 β2 N 2 N1 = +. (2.6) b b 38 2.2. Écriture des nombres dans différentes bases En combinant (2.6) et (2.5), nous obtenons : β β1 2 + Nb2 N= + b b b β1 β2 N 2 = + 2+ 2 b b b = β1 × b −1 + β2 × b −2 + N2 × b −2. Nous pouvons continuer ce développement, en multipliant successivement tous les Ni = 0,αi par b, pour obtenir un suite aussi longue que souhaitée de βi tels que : N = β1 × b −1 + β2 × b −2 + · · · βk × b −k + Nk × b −k X k = βi b −i + Nk × b −k. (2.7) i =1 En comparant (2.7) et (2.2), on voit que la séquence des βi ainsi calculée correspond à la séquence des d −i nécessaires pour exprimer N en base b. Ce développement sera arrêté soit lorsque Ni = 0, soit dès qu’on détecte deux valeurs N j et Ni (i 6= j ) telles que N j = Ni , ce qui signiﬁe que l’expression de N en base b est inﬁnie périodique. Considérons N = −24,4210 à exprimer en base 2. Nous allons commencer par ß exprimer 24 en base 2, en divisant successivement 24 par 2. On commence par 24/2 = 12 avec un reste de 0. Autrement dit q 0 = 12 et r 0 = 0. On poursuit en divisant q 0 par 2, etc : i qi ri 0 12 0 1 6 0 2 3 0 3 1 1 4 0 1 On lit maintenant la séquence des restes de haut en bas, en on obtient : 2410 = 110002.../. 39 2. Leçons 2 à 4 – Représentation de l’information Pour la partie fractionnaire, on procède par multiplications successives par 2.... On commence par 0,42 × 2 = 0,84. Autrement dit, β1 = 0 et N1 = 0,84. On multi- plie à nouveau N1 par 2, soit 2 × 0,84 = 1,68. On obtient donc : i βi Ni i βi Ni i βi Ni 1 0 0,84 8 1 0,52 15 0 0,56 2 1 0,68 9 1 0,04 16 1 0,12 3 1 0,36 10 0 0,08 17 0 0,24 4 0 0,72 11 0 0,16 18 0 0,48 5 1 0,44 12 0 0,32 19 0 0,96 6 0 0,88 13 0 0,64 20 1 0,92 7 1 0,76 14 1 0,28 21 1 0,84 On voit donc que N21 = N1 , la suite du développement se poursuivra donc ad inﬁnitum de manière cyclique. Donc : 0,4210 = 0,0110 1011 1000 0101 0001 12 et ﬁnalement : −24,4210 = −1 1000,0110 1011 1000 0101 0001 12. 2.2.2. Opérations en base 2 Comme la base 2 est celle qui nous sera la plus utile dans la suite, nous allons maintenant nous intéresser aux différentes opérations que nous pouvons appliquer aux nombres dans cette base. Opérations arithmétiques On peut utiliser l’addition, la soustraction, la multiplication et la division euclidienne sur les nombres dans n’importe quelle base, en particulier la base 2. Pour l’addition, on procède en base 2 comme en base 10, en faisant d’abord la somme des unités, puis des chiffres correspondant au poids 21 (au lieu de 101 en base 10), 22 , etc... Il faut simplement être attentif au fait qu’un report a lieu dès que la somme dépasse 210 = 102. Par exemple : 1+0 donne une somme de 1, et un report de 0. Par contre, 1+1 = 102 donne une somme de 0 et un report de 1. De même, 1 + 1 + 1 = 112 donne une somme de 1 et un report de 1. Par exemple : ß 1 1 0 1 1 1 1 1 + 1 1 0 1 1 1 0 0 0 Dans le chapitre 4, nous utiliserons ces concepts pour construire un circuit qui réalise ces 40 2.2. Écriture des nombres dans différentes bases additions. Opérations logiques En base 2, on peut utiliser une série d’opérations qui n’ont pas d’équi- valent naturel dans les autres bases. Ce sont les opérations « logiques », que l’on peut appli- quer en considérant que le 0 représente la valeur logique « faux », et que le 1 représente la valeur logique « vrai ». On déﬁnit les opérateurs binaires 5 et (noté ∧), ou (noté ∨), et ou exclusif (noté XOR) ; ainsi que l’opérateur unaire non (noté ¬). Pour déﬁnir leur effet sur deux nombres binaires, on commence par les déﬁnir sur deux bits (ou un bit dans le cas du ¬). Pour ce faire, on utilise une table de vérité, qui donne, pour chaque valeur possible des opérandes (de l’opérande), la valeur renvoyée par l’opérateur. Voici les tables de vérité de ces opérateurs : x y x∧y x y x∨y x y x XOR y x ¬x 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 0 On remarquera que ces opérateurs expriment l’idée intuitive qu’on peut s’en faire à la lec- ture de leur nom. L’opération x ∧ y vaut 1 si et seulement x et y sont vraies (soit x = 1 et y = 1). L’opération x ∨ y vaut 1 si et seulement si x ou y est vraie. L’opération x XOR y vaut 1 si et seulement si soit x est vraie soit y est vraie mais pas les deux en même temps (si x est vraie, cela exclut donc le fait que y soit vraie et vice-versa). Finalement, ¬x remplace la valeur de vérité de x par son opposé (vrai par faux et faux par vrai). On peut maintenant généraliser ces opérations à n’importe quel nombre binaire, en ap- pliquant les opérations bit à bit : étant donné deux nombres sur n bits A = a n−1 a n−2 · · · a 0 et B = b n−1 b n−2 · · · b 0 , on applique l’opération sur chaque paire de bits a i , b i pour obtenir le bit c i du résultat. Par exemple, A ∧ B est le nombre C = c n−1 c n−2 · · · c 0 , où c n−1 = a n−1 ∧ b n−1 , c n−2 = a n−2 ∧ b n−2 ,... et c 0 = a 0 ∧ b 0. Et ainsi de suite pour les autres opérations. Masques Ces opérations logiques permettent de réaliser certaines manipulations des va- leurs binaires, appelées masques ou masquages. On observe que x ∧0 = 0 et x ∧1 = x, quelque soit la valeur de x (sur un bit). De ce fait, le ∧ peut être utilisé pour masquer certains bits d’un nombre, c’est-à-dire remplacer ces bits par des 0 tout en conservant les autres. Il sufﬁt de prendre la conjonction de ce nombre avec une valeur binaire comprenant des 0 à toutes les positions qu’on veut masquer, et des 1 partout ailleurs. 5. Attention ! Ici, « binaire » signiﬁe que l’opérateur porte sur deux opérandes, comme l’addition par exemple. Au contraire, un opérateur unaire porte sur une seule opérande (comme le moins dans −5 par exemple). 41 2. Leçons 2 à 4 – Représentation de l’information ß Supposons qu’on souhaite masquer les 4 bits de poids fort d’un nombre N de 8 bits. On peut faire : N ∧ 0000 1111. Si N = 1010 1010, on a bien N ∧ 0000 1111 = 0000 1010. Les masques ont plusieurs utilités, nous en verrons certaines dans ce cours, notamment dans le Chapitre 9 consacré à la gestion de la mémoire à l’aide de la pagination. On peut déjà observer que les masques permettent de calculer le reste d’une division entière par une puissance de 2. En effet, nous avons déjà vu plus haut que le reste de la division entière de N par 2k est le nombre composé des k bits de poids faible de N. On peut donc masquer les autres bits pour ne retenir que ces k bits. ß Par exemple : 1010 01012 mod 810 = 1010 01012 mod 23 = 1010 01012 ∧ 0000 0 |{z} 111 3 = 0000 01012 = 1012. Décalages, division et multiplication Une autre opération utile (mais qui n’est pas réser- vée aux nombres binaires) est l’opération de décalage de n positions (où n est un naturel). Il y a deux types de décalage : — le décalage vers la gauche de n positions, d’un nombre b est noté b > n, et consiste à supprimer les n chiffres de poids faibles du nombre n (quitte à ajouter des 0 à gauche pour garder le même nombre de bits) Par exemple, en binaire : 0010 1101 >> 3 = 0000 0101. De même 0010 1101 1 = 5310 — 1000102 ÷ 410 = 100010 ÷ 22 = 100010 >> 2 = 10002 42 2.2. Écriture des nombres dans différentes bases Voyons maintenant comment exploiter toutes ces considérations théoriques pour repré- senter différents types d’informations en binaire. 2.2.3. Représentation des entiers non-signés Si nous devons manipuler des nombres entiers non-négatifs 6 uniquement, on peut se conten- ter d’exprimer ce nombre en base 2. Cette représentation n’utilisera que les symboles 0 et 1 et constitue donc bien une représentation binaire. Ces nombres sont souvent appelés les nombres « non signés ?

FDO COURS PDF - Cours et exercices corrigés Fonctionnement des ordinateurs

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue