Exercices corrigés de NSI : architectures matérielles, systèmes et réseaux

Divisions successives par 2 : $45 = 2 \times 22 + 1$, $22 = 2 \times 11 + 0$, $11 = 2 \times 5 + 1$, $5 = 2 \times 2 + 1$, $2 = 2 \times 1 + 0$, $1 = 2 \times 0 + 1$. On lit les restes du dernier au premier : 101101, donc 00101101 sur 8 bits. Vérification : $32 + 8 + 4 + 1 = 45$. En hexadécimal, on regroupe les bits par quatre depuis la droite : 0010 et 1101, soit 2 et D, donc 0x2D. Vérification : $2 \times 16 + 13 = 45$.

Comme entier naturel, $11010011$ vaut $128 + 64 + 16 + 2 + 1 = 211$. Comme entier relatif en complément à deux, le bit de poids fort valant 1, le nombre est négatif : sa valeur est $211 - 256 = -45$. On peut aussi le retrouver en inversant tous les bits, ce qui donne 00101100 soit 44, puis en ajoutant 1 pour obtenir 45, et en mettant le signe moins. La même suite de huit bits vaut donc 211 ou moins 45 selon la seule convention retenue, et rien dans la mémoire ne dit laquelle est la bonne.

On part de 45, soit 00101101. On inverse tous les bits : 11010010. On ajoute 1 : 11010011. C'est bien la suite de la question b, ce qui confirme le résultat. Vérification par addition : $00101101 + 11010011$ donne 100000000 sur neuf bits ; le neuvième bit sort de la largeur du registre et est perdu, il reste 00000000, c'est-à-dire zéro. C'est exactement l'intérêt du complément à deux : la soustraction se fait avec le circuit d'addition, sans matériel supplémentaire.

L'intervalle est de $-128$ à $+127$, soit $2^{8} = 256$ valeurs. Il n'est pas symétrique parce que le zéro occupe une place du côté positif : les 256 combinaisons se répartissent en 128 valeurs dont le bit de poids fort vaut 0, à savoir 0 à 127, et 128 valeurs dont ce bit vaut 1, à savoir $-128$ à $-1$. Le côté positif perd donc une place au profit du zéro. Conséquence pratique : l'opposé de $-128$ n'est pas représentable, et le calculer redonne $-128$, ce qui surprend toujours.

$100 + 50 = 150$, qui dépasse 127 : le résultat ne tient pas. En binaire, $01100100 + 00110010 = 10010110$, dont le bit de poids fort vaut 1 : lu en complément à deux, cela donne $150 - 256 = -106$. Le programme obtient donc moins 106 en additionnant deux nombres positifs. Le phénomène s'appelle le DÉBORDEMENT. On le détecte à un signe caractéristique : additionner deux nombres de même signe et obtenir un résultat de signe opposé est impossible en arithmétique exacte, donc c'est la signature du débordement. Les processeurs disposent d'ailleurs d'un indicateur dédié, que les langages de haut niveau choisissent le plus souvent d'ignorer.

Table de vérité. Pour a valant 0 et b valant 0 : S vaut 0 et R vaut 0. Pour a valant 0 et b valant 1 : S vaut 1 et R vaut 0. Pour a valant 1 et b valant 0 : S vaut 1 et R vaut 0. Pour a valant 1 et b valant 1 : S vaut 0 et R vaut 1. La colonne S est bien celle d'un OU exclusif, qui vaut 1 quand exactement une des deux entrées vaut 1 ; la colonne R est celle d'un ET, qui vaut 1 seulement quand les deux valent 1.

L'addition binaire de deux bits donne : $0 + 0 = 0$, $0 + 1 = 1$, $1 + 0 = 1$, et $1 + 1 = 10$ en binaire, c'est-à-dire 0 de somme et 1 de retenue. C'est exactement le contenu de la table. La colonne S est le chiffre des unités du résultat, la colonne R est la RETENUE qui doit être reportée sur la colonne suivante, exactement comme dans une addition posée en base dix.

La porte ET vaut 1 seulement si les deux entrées valent 1. La porte OU vaut 1 dès qu'au moins une entrée vaut 1. La porte NON inverse son entrée unique. Le OU exclusif s'écrit alors : $a$ ET NON $b$, OU bien NON $a$ ET $b$. Autrement dit, on prend le OU des deux cas où les entrées diffèrent. Une autre écriture, plus compacte, est le ET du OU et du NON du ET : $(a \text{ OU } b)$ ET NON$(a \text{ ET } b)$, qui se lit « au moins un des deux, mais pas les deux ».

Il manque la prise en compte de la retenue ENTRANTE, celle produite par la colonne précédente. Le demi-additionneur additionne deux bits ; pour additionner deux nombres, chaque colonne doit en additionner TROIS : les deux bits du rang et la retenue venue du rang inférieur. Le circuit complet, appelé additionneur complet, s'obtient en chaînant deux demi-additionneurs : le premier additionne a et b, le second additionne leur somme et la retenue entrante ; la retenue sortante est le OU des deux retenues produites. On construit ensuite un additionneur de 8 bits en chaînant 8 additionneurs complets, la retenue sortante de chacun devenant la retenue entrante du suivant.

Pour 8 bits, il faut 8 additionneurs complets, soit $8 \times 9 = 72$ portes élémentaires. Pour 64 bits, $64 \times 9 = 576$ portes. Le nombre croît linéairement avec la largeur, ce qui est très raisonnable ; en revanche le TEMPS de calcul croît lui aussi linéairement, puisque chaque retenue doit être calculée avant la suivante. C'est ce délai en cascade, et non le nombre de portes, qui a conduit à inventer des additionneurs à anticipation de retenue, plus gourmands en portes mais nettement plus rapides.

La MÉMOIRE conserve à la fois le programme et les données, sous forme de mots numérotés par des adresses. L'UNITÉ DE COMMANDE lit les instructions, les décode et pilote tous les autres blocs en conséquence. L'UNITÉ DE CALCUL effectue les opérations arithmétiques et logiques sur les données qu'on lui fournit. Les ENTRÉES-SORTIES relient la machine au monde, clavier, écran, disque, réseau. Le bus transporte trois choses : les ADRESSES, qui disent où lire ou écrire, les DONNÉES, qui sont ce qu'on lit ou écrit, et les signaux de COMMANDE, qui disent s'il s'agit d'une lecture ou d'une écriture.

Les trois phases sont, dans l'ordre : LIRE l'instruction en mémoire à l'adresse indiquée par le compteur ordinal, ce qui mobilise la mémoire et le bus ; DÉCODER cette instruction, ce qui mobilise l'unité de commande, qui détermine l'opération et les opérandes ; EXÉCUTER, ce qui mobilise l'unité de calcul pour un calcul, ou de nouveau la mémoire pour une lecture ou une écriture de donnée. Ce cycle se répète sans fin tant que la machine est allumée.

L'idée centrale est que le PROGRAMME EST UNE DONNÉE : il est rangé dans la même mémoire que les données qu'il manipule, dans le même format de mots binaires. La conséquence pratique est qu'un programme peut en lire, en écrire, en produire un autre, et qu'il suffit de charger un nouveau contenu en mémoire pour changer ce que fait la machine, sans toucher au matériel. Application quotidienne : installer une application, ou faire une mise à jour, revient exactement à cela. Avant ce modèle, changer de calcul demandait de recâbler physiquement la machine, ce qui prenait des jours.

Pendant un cycle ordinaire, le compteur ordinal est LU pour connaître l'adresse de l'instruction, puis INCRÉMENTÉ de la taille d'une instruction, si bien qu'il désigne déjà la suivante avant même la fin de l'exécution. Pendant un saut, l'exécution REMPLACE cette valeur par l'adresse de destination : le compteur ne pointe plus sur l'instruction suivante mais sur celle indiquée par le saut. C'est ce simple remplacement qui produit toutes les boucles et tous les branchements conditionnels d'un programme.

À 3 GHz, le processeur exécute $3 \times 10^{9}$ cycles par seconde. À raison d'une instruction tous les 4 cycles, il exécute $3 \times 10^{9} / 4 = 7{,}5 \times 10^{8}$ instructions par seconde, soit 750 millions. Un programme de $12 \times 10^{9}$ instructions demande $12 \times 10^{9} / (7{,}5 \times 10^{8}) = 16$ secondes. Ce calcul suppose que le processeur ne s'arrête jamais, ce qui est faux en pratique : dès qu'une donnée manque en mémoire cache, il attend, et l'exercice 9 montre que cette attente dépasse largement le temps de calcul.

Au départ, R0 vaut 5 et R1 vaut 0. Premier passage en 4 : R1 vaut $0 + 5 = 5$ et R0 vaut 4, donc on saute. Deuxième passage : R1 vaut $5 + 4 = 9$ et R0 vaut 3, on saute. Troisième : R1 vaut $9 + 3 = 12$ et R0 vaut 2, on saute. Quatrième : R1 vaut $12 + 2 = 14$ et R0 vaut 1, on saute. Cinquième : R1 vaut $14 + 1 = 15$ et R0 vaut 0, donc on NE saute pas et l'exécution continue en 5.

La valeur écrite à l'adresse 100 est 15. Le programme calcule la somme des entiers de 1 à 5, c'est-à-dire $5 + 4 + 3 + 2 + 1 = 15$. Plus généralement, il calcule la somme des entiers de 1 à la valeur initiale de R0.

Décompte. Les deux instructions d'initialisation, en 0 et en 1, sont exécutées une fois : cela fait 2. Le corps de boucle, formé des instructions 2, 3 et 4, est exécuté 5 fois : cela fait $3 \times 5 = 15$. Les instructions 5 et 6 sont exécutées une fois : cela fait 2. Le total vaut $2 + 15 + 2 = 19$ instructions. Le piège est de compter 4 tours au lieu de 5, en oubliant que le dernier tour s'exécute entièrement avant que le saut ne soit refusé.

En Python : r0 = 5 ; puis r1 = 0 ; puis while r0 != 0 : r1 = r1 + r0 et r0 = r0 - 1 ; enfin memoire[100] = r1. Le rapprochement est instructif : une boucle while de Python n'est rien d'autre qu'un test suivi d'un saut conditionnel, et le compilateur produit exactement le programme de l'énoncé.

Avec 1000 au lieu de 5, le total vaut $2 + 3 \times 1\ 000 + 2 = 3\ 004$ instructions. Pour obtenir le même résultat en un nombre d'instructions FIXE, on utilise la formule de la somme des premiers entiers, $n(n+1)/2$. Le programme devient : charger n dans R0, copier R0 dans R1, ajouter 1 à R1, multiplier R0 par R1, diviser par 2, écrire à l'adresse 100, arrêter. Cela fait 7 instructions quelle que soit la valeur de n, contre 3 004. Vérification pour $n = 1\ 000$ : $1\ 000 \times 1\ 001 / 2 = 500\ 500$. C'est le même écart de nature qu'entre un algorithme linéaire et un algorithme constant : aucune accélération du processeur ne rattrape un changement de formule.

Un chemin ABSOLU part de la racine et commence donc par une barre oblique : il désigne le même fichier quel que soit le répertoire courant. Un chemin RELATIF part du répertoire courant et ne commence pas par une barre : il désigne des fichiers différents selon l'endroit d'où on l'écrit. Pour notes.csv, le chemin absolu est /home/ada/tp/donnees/notes.csv et le chemin relatif, depuis /home/ada/tp, est donnees/notes.csv. Le second est plus court et se déplace avec le projet ; le premier est robuste mais casse dès que l'arborescence change.

Le point désigne le répertoire courant lui-même, le point-point désigne son répertoire PARENT. Depuis /home/ada/tp, il faut remonter deux fois pour atteindre /home, puis redescendre : le chemin relatif est ../../bob/partage. On vérifie en comptant les remontées : un point-point mène à /home/ada, deux mènent à /home, et il reste bob puis partage.

Afficher le contenu du répertoire courant : ls, ou ls -l pour le détail avec les permissions. Créer un répertoire : mkdir resultats. S'y déplacer : cd resultats. Afficher le répertoire courant : pwd. Il faut retenir que cd est la seule de ces commandes qui change l'état du terminal ; les trois autres se contentent d'afficher ou de créer.

Les neuf caractères se lisent par groupes de trois : le propriétaire, le groupe, les autres. Ici rw- pour le propriétaire ada, donc lecture et écriture mais pas exécution ; r-- pour le groupe eleves, donc lecture seule ; --- pour les autres, donc aucun droit. Bob n'étant ni le propriétaire ni membre du groupe, il relève de la troisième catégorie : il ne peut PAS lire le fichier. Il faut noter que les trois catégories sont exclusives et testées dans cet ordre : être propriétaire l'emporte sur être membre du groupe, même si le groupe a plus de droits.

Sur un FICHIER, le droit d'exécution autorise à le lancer comme un programme. Sur un RÉPERTOIRE, il autorise à le TRAVERSER, c'est-à-dire à accéder à ce qu'il contient quand on en connaît le nom. Les deux sens n'ont rien à voir. Si on retire ce droit à un répertoire tout en laissant le droit de lecture, on obtient une situation déroutante : on peut lister les noms des fichiers qu'il contient, mais on ne peut ouvrir aucun d'eux, ni même savoir leur taille. Inversement, avec l'exécution mais sans la lecture, on peut ouvrir un fichier dont on connaît exactement le nom, sans pouvoir découvrir la liste. C'est ce second réglage qu'on utilise pour un répertoire de dépôt public.

Cinq ressources et leurs conflits. Le PROCESSEUR : sans arbitrage, un programme qui boucle monopoliserait la machine et tous les autres seraient gelés. La MÉMOIRE : sans arbitrage, deux programmes écriraient au même endroit et se détruiraient mutuellement. Les FICHIERS : sans arbitrage, deux écritures simultanées dans le même fichier produiraient un contenu incohérent. Les PÉRIPHÉRIQUES : sans arbitrage, deux programmes qui impriment mélangeraient leurs pages. Le RÉSEAU : sans arbitrage, deux programmes réclameraient le même numéro de port et les réponses arriveraient au mauvais destinataire.

Raison de SÉCURITÉ : si un programme pouvait écrire directement sur le disque, il pourrait lire les fichiers de tous les utilisateurs, modifier le système lui-même et contourner toute permission. Passer par le système permet de vérifier, à chaque demande, que le programme a le droit de faire ce qu'il demande. Raison de PORTABILITÉ : il existe des dizaines de types de disques, chacun avec son protocole. Si chaque programme devait les connaître, il faudrait le réécrire à chaque nouveau matériel. Le système offre une interface unique, ouvrir, lire, écrire, fermer, et se charge de la traduire ; le programme fonctionne alors sans modification sur une machine qu'il ne connaît pas.

Un appel système est la demande qu'un programme adresse au système d'exploitation pour obtenir un service qu'il n'a pas le droit d'accomplir lui-même. Trois exemples : ouvrir un fichier, allouer de la mémoire, envoyer des données sur le réseau. Du point de vue du processeur, l'appel provoque un changement de MODE : le processeur quitte le mode utilisateur, dans lequel les instructions privilégiées sont interdites, pour le mode noyau, dans lequel elles sont permises. Le contrôle passe à une adresse fixée à l'avance par le système, jamais choisie par le programme, ce qui est précisément ce qui rend le mécanisme sûr. À la fin du service, le processeur repasse en mode utilisateur et rend la main au programme.

Les trois programmes réclament $3 + 4 + 3 = 10$ Gio alors que la machine en a 8 : il en manque 2. Le système ne refuse pas pour autant : il utilise la MÉMOIRE VIRTUELLE et le mécanisme d'échange sur disque, souvent appelé pagination ou swap. Les pages de mémoire les moins récemment utilisées sont écrites sur le disque, libérant de la place en mémoire vive ; quand un programme y accède de nouveau, elles sont relues. La machine devient très lente parce qu'un accès qui coûtait 80 nanosecondes en coûte désormais 8 millisecondes quand la page est sur le disque, soit cent mille fois plus. Si les trois programmes travaillent simultanément, les pages sont échangées sans cesse dans les deux sens, phénomène appelé écroulement, et la machine passe plus de temps à déplacer des pages qu'à calculer.

Le facteur de ralentissement vaut $8 \times 10^{-3} / (80 \times 10^{-9}) = 100\ 000$. Pour $10^{6}$ accès dont un sur mille tombe sur le disque : $999\ 000$ accès en mémoire coûtent $999\ 000 \times 80 \times 10^{-9} \approx 0{,}0799$ s, et $1\ 000$ accès au disque coûtent $1\ 000 \times 8 \times 10^{-3} = 8$ s. Le total vaut environ $8{,}08$ secondes, alors que sans aucun accès disque il aurait valu $10^{6} \times 80 \times 10^{-9} = 0{,}08$ s. Un accès sur mille suffit donc à multiplier la durée par plus de cent. C'est la raison pour laquelle ajouter de la mémoire vive à une machine qui échange transforme radicalement son comportement, alors qu'un processeur plus rapide ne changerait presque rien.

La notation /24 signifie que les 24 premiers bits de l'adresse identifient le RÉSEAU, et que les bits restants identifient la machine dans ce réseau. Une adresse IPv4 comptant 32 bits, il reste $32 - 24 = 8$ bits, soit $2^{8} = 256$ adresses. Deux ne sont pas attribuables à une machine : l'adresse de réseau, 192.168.1.0, et l'adresse de diffusion, 192.168.1.255. Il reste donc $256 - 2 = 254$ adresses utilisables.

Le masque /24 correspond à 255.255.255.0. En appliquant un ET bit à bit, l'adresse 192.168.1.37 donne le réseau 192.168.1.0, et 192.168.1.90 donne également 192.168.1.0. Les deux réseaux étant identiques, les machines sont sur le même sous-réseau : le message part DIRECTEMENT de l'une à l'autre, sans jamais passer par le routeur. C'est le calcul que fait toute machine avant chaque envoi, et c'est lui, et rien d'autre, qui décide de l'itinéraire.

Pour 192.168.2.15, le même ET donne le réseau 192.168.2.0, différent de 192.168.1.0. Les machines ne sont donc pas sur le même sous-réseau. Le trajet complet : la machine émettrice envoie le message à sa PASSERELLE par défaut, c'est-à-dire à l'interface 192.168.1.254 du routeur ; le routeur constate que la destination appartient à 192.168.2.0/24, réseau auquel il est directement relié par son interface 192.168.2.254 ; il transmet le message sur cette interface, et celui-ci atteint 192.168.2.15. Le message a donc franchi un saut de routeur, ce que révélerait un compteur de sauts diminué de un.

Pour quatre sous-réseaux, il faut emprunter 2 bits à la partie machine, puisque $2^{2} = 4$. Le nouveau masque est donc /26, soit 255.255.255.192. Les quatre adresses de réseau sont 192.168.1.0, 192.168.1.64, 192.168.1.128 et 192.168.1.192, car $2^{32-26} = 2^{6} = 64$ adresses par sous-réseau. Chacun offre $64 - 2 = 62$ adresses de machine. On vérifie le total : $4 \times 62 = 248$ machines contre 254 auparavant, la différence de 6 venant des six adresses de réseau et de diffusion supplémentaires. Découper coûte des adresses, et c'est le prix de la séparation.

Avec un masque /16, la machine croit que tout le 192.168.0.0 forme un seul réseau local. Ce qui FONCTIONNE encore : joindre les machines de 192.168.1.0/24, puisqu'elles sont bien locales, et le calcul donne le même verdict. Ce qui CESSE de fonctionner : joindre 192.168.2.15. La machine conclut à tort que cette adresse est locale, donc elle n'envoie rien au routeur et cherche directement le destinataire sur son propre câble ; personne ne répond, et la connexion échoue par expiration de délai. Le symptôme est déroutant : la machine communique parfaitement avec ses voisins immédiats, et échoue sur une adresse qui semble pourtant plus proche que l'extérieur, lequel fonctionne d'ailleurs très bien puisqu'une adresse publique, elle, n'est pas dans 192.168.0.0/16 et part donc bien vers le routeur.

FAUX, ou plutôt incomplet. La suite vaut 211 si on l'interprète comme un entier NATUREL, et moins 45 si on l'interprète comme un entier relatif en complément à deux. Rien dans la mémoire ne dit laquelle des deux conventions s'applique : c'est le type déclaré dans le programme qui décide. Énoncé correct : une suite de bits n'a pas de valeur en soi, elle a une valeur POUR UNE CONVENTION donnée.

FAUX. L'intervalle est de moins 128 à 127, soit 256 valeurs. Il est asymétrique parce que le zéro occupe une des 128 places du côté où le bit de poids fort vaut 0. Énoncé correct : sur $n$ bits en complément à deux, on représente les entiers de $-2^{n-1}$ à $2^{n-1} - 1$.

FAUX. L'interface graphique est un programme comme un autre, qui s'exécute par-dessus le système. Le système d'exploitation est le programme qui distribue le processeur, la mémoire, les fichiers, les périphériques et le réseau entre tous les programmes. Un serveur fonctionne parfaitement sans aucune interface graphique. Énoncé correct : le système d'exploitation gère les ressources et arbitre entre les programmes ; l'interface graphique n'est qu'un de ses clients.

FAUX. C'est le MASQUE, et lui seul, qui définit le réseau local. Avec un masque /24, 192.168.1.37 et 192.168.2.15 sont sur deux réseaux différents et ne peuvent se parler qu'en passant par un routeur, malgré leurs deux premiers octets identiques. Énoncé correct : deux machines sont sur le même sous-réseau si et seulement si l'application du masque à leurs adresses donne la même adresse de réseau.

FAUX. Quand une machine manque de mémoire, elle échange des pages avec le disque, et un accès passe de 80 nanosecondes à 8 millisecondes, soit cent mille fois plus. Le processeur, lui, attend : il est déjà inoccupé. Énoncé correct : quand le goulot est la mémoire, il faut ajouter de la mémoire vive, ou à défaut un disque à mémoire flash qui divise le coût de l'échange par cent ; un processeur plus rapide attendrait simplement plus vite.

Registre : de l'ordre de la nanoseconde, en pratique environ $0{,}3$ ns. Cache : quelques nanosecondes, environ 1 ns pour le premier niveau. Mémoire vive : environ 80 ns, soit une centaine de nanosecondes. Mémoire flash : quelques dizaines de microsecondes, environ 50 µs. Disque à plateaux : quelques millisecondes, environ 8 ms. Le facteur entre le registre et le disque vaut $8 \times 10^{-3} / (0{,}3 \times 10^{-9}) \approx 2{,}7 \times 10^{7}$, soit près de vingt-sept millions.

Le facteur d'échelle vaut $1 / (0{,}3 \times 10^{-9}) \approx 3{,}33 \times 10^{9}$. Le cache, à 1 ns, devient $3{,}33$ secondes. La mémoire vive, à 80 ns, devient $266{,}7$ secondes, soit environ $4{,}4$ minutes. La mémoire flash, à 50 µs, devient $1{,}67 \times 10^{5}$ secondes, soit environ $1{,}9$ jour. Le disque, à 8 ms, devient $2{,}67 \times 10^{7}$ secondes, soit environ 309 jours, c'est-à-dire dix mois. Prendre une donnée dans un registre est aussi immédiat que la lire sur son bureau ; aller la chercher sur le disque revient à commander un livre qui arrivera dans dix mois.

Raison PHYSIQUE : une mémoire rapide doit être proche du processeur, or la lumière parcourt 30 centimètres en une nanoseconde ; à quelques nanosecondes de budget, la mémoire doit tenir à quelques centimètres, ce qui limite sévèrement sa taille. S'y ajoute qu'une cellule rapide occupe beaucoup plus de transistors qu'une cellule lente. Raison ÉCONOMIQUE : le coût par octet varie dans le même rapport que la vitesse, de plusieurs ordres de grandeur. Une machine dont toute la mémoire serait aussi rapide qu'un cache serait techniquement possible et commercialement absurde. La hiérarchie est donc un compromis, pas une imperfection.

Parce que la mémoire ne se lit pas octet par octet mais par BLOCS : un accès charge dans le cache une ligne entière, typiquement 64 octets, soit 16 entiers de 4 octets. Dans un parcours ordonné, un accès sur seize seulement va réellement en mémoire vive, les quinze suivants trouvant leur donnée dans le cache. Dans un parcours aléatoire, presque chaque accès tombe sur une ligne différente, donc chacun paie le prix fort. Le nombre d'accès du programme est identique, mais le nombre d'accès à la MÉMOIRE ne l'est pas, et c'est lui qui compte. C'est la raison pour laquelle deux algorithmes de même complexité peuvent différer d'un facteur dix en pratique.

Avec 95 pour cent de succès : $0{,}95 \times 1 + 0{,}05 \times 80 = 0{,}95 + 4{,}00 = 4{,}95$ ns. Avec 80 pour cent : $0{,}80 \times 1 + 0{,}20 \times 80 = 0{,}80 + 16{,}00 = 16{,}80$ ns. Le temps moyen est multiplié par $16{,}80 / 4{,}95 \approx 3{,}39$ alors que le taux de succès n'a baissé que de 15 points. La raison est que le temps moyen est dominé par les ÉCHECS, cent fois plus coûteux : ce sont eux qu'il faut compter, jamais les succès. C'est exactement le même raisonnement que celui de l'exercice 6 sur l'échange de pages, avec des ordres de grandeur plus modestes.

Le goulot est la MÉMOIRE, et le disque n'en est que le symptôme. Un processeur à 12 pour cent signifie qu'il attend la plupart du temps ; une mémoire à 99 pour cent et un disque à 100 pour cent signifient que le système échange des pages en permanence, exactement le phénomène décrit à l'exercice 6. Le réseau, à 3 pour cent, est hors de cause.

Deux cent quarante mébioctets font $240 \times 1\ 024 = 245\ 760$ kio, soit $245\ 760 / 4 = 61\ 440$ pages par minute. À 8 ms par accès, cela demande $61\ 440 \times 8 \times 10^{-3} = 491{,}5$ secondes de disque par minute. Or une minute n'en compte que 60 : la demande dépasse la capacité d'un facteur $491{,}5 / 60 \approx 8{,}2$. Le chiffre est donc parfaitement cohérent avec un disque à 100 pour cent, et il dit même davantage : le disque est saturé huit fois, ce qui signifie que les programmes attendent en file et que la machine est effectivement inutilisable.

Le processeur à 4 GHz ne change RIEN : il est déjà inoccupé à 88 pour cent, et l'accélérer ne ferait qu'augmenter son temps d'attente. Les 16 Gio de mémoire supprimeraient la cause : avec 24 Gio au total, plus aucune page ne serait échangée, le temps de disque tomberait à presque zéro et la machine retrouverait sa vitesse nominale. Le disque à mémoire flash ne supprimerait pas la cause mais diviserait le coût de chaque échange par $8 \times 10^{-3} / (50 \times 10^{-6}) = 160$ : les $491{,}5$ secondes deviendraient $3{,}07$ secondes par minute, soit environ 5 pour cent d'occupation, ce qui rendrait la machine de nouveau utilisable. Classement : la mémoire d'abord, parce qu'elle traite la cause ; la mémoire flash ensuite, parce qu'elle traite l'effet mais très efficacement ; le processeur en dernier, parce qu'il ne traite rien.

La correction logicielle est de lire le fichier en FLUX, ligne par ligne, en ne conservant que la colonne utile, au lieu de tout charger en mémoire. Si la colonne représente un quinzième du fichier, la mémoire nécessaire tombe à $6 / 15 = 0{,}4$ Gio, soit 400 Mio, plus un tampon de lecture de quelques mébioctets. On passe de 6 Gio à moins d'un demi-gibioctet, soit un facteur 15, sans acheter quoi que ce soit et sans changer le résultat produit. C'est de loin la meilleure des solutions envisagées jusqu'ici.

Le diagnostic et la recommandation. Un, le poste n'est pas lent par manque de puissance de calcul : le processeur est inoccupé à 88 pour cent, et le remplacer serait une dépense inutile. Deux, la cause est un manque de mémoire vive, qui contraint le système à échanger 61 440 pages par minute avec le disque, soit huit fois plus que ce que celui-ci peut servir. Trois, sans aucune dépense, corriger le logiciel qui charge 6 Gio pour n'en lire qu'un quinzième ramènerait le besoin à 400 Mio et supprimerait probablement le problème à lui seul. Quatre, si la correction logicielle est impossible, porter la mémoire de 8 à 24 Gio traite la cause ; à défaut, un disque à mémoire flash divise le coût d'un échange par 160 et rend la machine utilisable sans la guérir. Cinq, ne rien commander avant d'avoir tenté la correction logicielle, qui est gratuite, réversible et bénéficie à tous les postes de la salle.

M1 porte le bit 0, M2 le bit 1 et M3 le bit 0. Chaque message est suivi de son acquittement : 3 messages et 3 acquittements, soit 6 trames.

A ne reçoit pas l'acquittement de M1 : au bout de 100 ms, il RENVOIE M1, toujours avec le bit 0. B, qui a déjà accepté un message de bit 0 et attend maintenant le bit 1, reconnaît un doublon : il le jette, mais renvoie l'acquittement 0, puisque c'est précisément la perte de cet acquittement qui a provoqué le renvoi. A reçoit enfin l'acquittement et passe à M2. Trames émises : 4 messages et 4 acquittements, dont un perdu, soit 8. B transmet exactement 3 messages à son application : M1, M2 et M3, sans doublon.

B ne pourrait pas distinguer un renvoi de M1 d'un nouveau message : il transmettrait M1 DEUX fois à son application. Pour un virement bancaire ou une commande, cela signifie une opération exécutée deux fois, sans que personne ne s'en aperçoive.

Parce que A n'envoie jamais un nouveau message tant que le précédent n'est pas acquitté. À tout moment, B n'a que deux cas à distinguer : c'est encore le message qu'il a déjà reçu, ou c'est le suivant. Deux cas se codent sur un bit. Il faudrait davantage de bits si A envoyait plusieurs messages d'avance sans attendre.

Sans perte, chaque échange dure $20 + 20 = 40$ ms : les trois messages prennent $3 \times 40 = 120$ ms. Avec la perte : M1 part à 0 ms, l'acquittement est perdu, le délai expire à 100 ms ; le renvoi arrive à 120 ms et son acquittement à 140 ms ; M2 et M3 prennent ensuite 40 ms chacun, d'où une fin à 220 ms. Au mieux, la liaison écoule $\frac{1\ 000}{40} = 25$ messages par seconde : attendre chaque acquittement est sûr, mais lent.

$\frac{4\ 000}{1\ 460} \approx 2{,}74$ : deux segments pleins ne suffisent pas, il en faut 3. Les deux premiers portent $2 \times 1\ 460 = 2\ 920$ octets, le dernier $4\ 000 - 2\ 920 = 1\ 080$ octets.

Une trame pleine mesure $1\ 460 + 20 + 20 + 18 = 1\ 518$ octets. La dernière mesure $1\ 080 + 58 = 1\ 138$ octets. Les 58 octets d'en-têtes sont les mêmes quelle que soit la quantité de données.

Total : $2 \times 1\ 518 + 1\ 138 = 4\ 174$ octets. Le surcoût vaut $3 \times 58 = 174$ octets, soit $\frac{174}{4\ 000} \approx 4{,}35$ pour cent des données. Pour un gros fichier, découpé en trames pleines, les en-têtes restent une petite fraction.

À l'émission, on descend les couches : l'application fournit les données, TCP ajoute son en-tête, puis IP, puis Ethernet, qui est donc à l'extérieur. C'est l'ENCAPSULATION, comme une lettre glissée dans une enveloppe, elle-même glissée dans un sac postal. Un routeur lit l'en-tête IP, qui porte l'adresse de destination, pour choisir la direction ; il retire l'enveloppe Ethernet et en remet une nouvelle pour le lien suivant, sans ouvrir le segment TCP.

La trame mesure $1 + 58 = 59$ octets pour un octet utile : le surcoût de 58 octets dépasse la donnée 58 fois. C'est pourquoi les protocoles regroupent volontiers plusieurs petits envois en un seul segment quand c'est possible : le coût d'un paquet ne dépend presque pas de ce qu'il transporte.

rwx vaut $4 + 2 + 1 = 7$, r-x vaut $4 + 1 = 5$, r-- vaut 4 : rwxr-xr-- s'écrit 754. chmod 640 donne 6 = rw- au propriétaire, 4 = r-- au groupe, 0 = --- aux autres : rw-r-----.

Le système répond Permission denied : personne n'a le droit x. Il faut ajouter x au propriétaire seulement : rw- devient rwx, soit 7, et le reste ne change pas : chmod 744 sauve.sh, qui donne rwxr--r--. Le piège est d'écrire chmod 777, qui donne aussi le droit d'écriture à tout le monde.

f.txt contient seulement c. La redirection > ÉCRASE le fichier : le premier echo écrit a, le second ajoute b grâce à >>, mais le troisième, avec >, remplace tout le contenu par c. Confondre > et >> est la manière la plus rapide de perdre un fichier de résultats.

cat affiche les six lignes du fichier ; grep NSI ne laisse passer que les lignes contenant la chaîne NSI, celles d'Ada, d'Eve et de Lin ; wc -l compte les lignes reçues. L'affichage est 3. Chaque commande ne fait qu'une chose, et le tube | les assemble : c'est le principe de conception des outils Unix.

cp crée une copie : a.txt reste et d.txt apparaît, soit 4 fichiers. mv renomme : b.txt disparaît et e.txt apparaît, toujours 4. rm supprime c.txt : il reste 3 fichiers, a.txt, d.txt et e.txt. Le piège est de croire que mv copie : il déplace.

La lampe s'allume pour 011, 101, 110 et 111, c'est-à-dire quand deux ou trois boutons valent 1 : 4 lignes sur 8. Elle reste éteinte pour 000, 001, 010 et 100.

« Au moins deux juges acceptent » signifie qu'il existe une PAIRE de juges qui acceptent tous les deux : la paire a et b, ou la paire a et c, ou la paire b et c. Chaque paire se teste par un ET, et l'existence d'une paire par un OU. Il faut 3 portes ET et 2 portes OU, car un OU à trois entrées se réalise avec deux OU à deux entrées : 5 portes au total.

Pour 101 : a ET b vaut 0, a ET c vaut 1, b ET c vaut 0 ; le OU vaut 1, la lampe s'allume, et deux juges ont bien accepté. Pour 001 : les trois ET valent 0, donc M vaut 0, et un seul juge a accepté.

return (a and b) or (a and c) or (b and c), ou, les boutons valant 0 ou 1, return a + b + c >= 2. La seconde écriture traduit directement l'énoncé et se généralise à n juges ; la première traduit le circuit.

Avec cinq entrées, la table a $2^{5} = 32$ lignes. La lampe s'allume pour 3, 4 ou 5 acceptations : $\binom{5}{3} + \binom{5}{4} + \binom{5}{5} = 10 + 5 + 1 = 16$ lignes, exactement la moitié, par symétrie. L'expression analogue teste chaque TRIO de juges : il y en a $\binom{5}{3} = 10$, donc 10 termes ET à trois entrées. Le circuit grossit vite, alors que la version par somme, a + b + c + d + e >= 3, reste courte : un additionneur et un comparateur remplacent l'énumération.

13 s'écrit 00001101. 13 << 1 vaut 26 ; 13 << 3 vaut $13 \times 2^{3} = 104$, soit 01101000 : les trois bits 1 ont glissé de trois rangs vers la gauche. 104 >> 2 vaut $\frac{104}{4} = 26$.

$11 = 1011_{2} = 8 + 2 + 1$, donc $13 \times 11 = 13 \times 8 + 13 \times 2 + 13 \times 1$. On décale 13 de 3 rangs, 104, puis de 1 rang, 26, et on garde 13 : trois additions de termes, un par bit 1 de 11. $104 + 26 + 13 = 143$, et l'on vérifie $13 \times 11 = 143$.

Un octet non signé va jusqu'à 255 : 143 tient. $13 \times 25 = 325$ ne tient pas : l'octet ne garde que les 8 bits de poids faible, soit $325 - 256 = 69$. Le produit est faux sans aucun message, exactement comme le débordement de l'exercice 1.

Avec des additions répétées, il faut ajouter 13 deux cents fois : 200 additions. Avec les décalages, $200 = 11001000_{2} = 128 + 64 + 8$ contient trois bits 1 : trois termes à additionner, obtenus par des décalages de 7, 6 et 3 rangs. Le nombre d'opérations dépend du nombre de BITS du multiplicateur, au plus 8 sur un octet, et non de sa valeur.

Avec un 0 ajouté à gauche : 01110110, qui vaut 118. Le nombre est devenu positif : c'est faux. En recopiant le bit de signe : 11110110, qui vaut $246 - 256 = -10$, bien la moitié de −20. Le décalage qui recopie le bit de signe, appelé décalage ARITHMÉTIQUE, est le seul correct pour les entiers signés ; Python applique d'ailleurs cette règle avec >>, puisque -20 >> 1 vaut -10.

Un CAPTEUR transforme une grandeur physique en donnée que le programme peut lire ; un ACTIONNEUR transforme une donnée du programme en action physique. Le bouton A est un capteur : il détecte un appui, grandeur tout ou rien. L'accéléromètre est un capteur : il mesure l'accélération, donc ici l'inclinaison de la carte par rapport à la verticale. Le capteur de température mesure une température. La matrice de $25$ DEL est un actionneur : elle commande de la lumière, allumée ou non, DEL par DEL. Le haut-parleur est un actionneur : il produit un son. Le critère ne dépend pas de l'objet mais du SENS de l'information : vers le programme, c'est une entrée ; depuis le programme, c'est une sortie.

Le programme lit deux capteurs, le bouton A et l'accéléromètre, et commande un seul actionneur, l'écran de DEL ; il n'utilise ni le haut-parleur, ni le bouton B, ni le capteur de température. Chaque tour se termine par sleep(100), une pause de $100$ ms : en négligeant les calculs, la carte fait $\frac{1\,000}{100}=10$ tours, donc $10$ lectures par seconde, ce qui suffit à suivre une main. La boucle while True est la forme normale d'un programme EMBARQUÉ : lire les capteurs, décider, commander les actionneurs, recommencer, tant que la carte est alimentée. On n'y cherche pas de variant, puisqu'on ne veut justement pas qu'elle se termine ; le variant sert à prouver la terminaison d'une boucle qui DOIT finir.

Avec $20$ : $20<50$ est vrai, l'écran affiche la coche, ce qui est correct. Avec $300$ : $300<50$ est faux, puis $300>0$ est vrai, l'écran affiche la flèche vers la droite, correct aussi. Avec $-400$ : $-400<50$ est VRAI, et l'écran affiche la coche, alors que la carte penche nettement vers la gauche. Le programme compare x à $50$ comme si l'écart à l'horizontale était toujours positif.

Le cahier des charges demande une flèche vers la gauche quand la carte penche à gauche au-delà de $50$ milli-g. Or pour atteindre le else, il faudrait à la fois $x\geq 50$, pour sortir du if, et $x\leq 0$, pour sortir du elif : c'est impossible. La branche else, qui affiche la flèche vers la gauche, n'est JAMAIS exécutée, et toute inclinaison à gauche affiche une coche. « À plat à $50$ près » veut dire que l'ÉCART à zéro est inférieur à $50$, dans un sens comme dans l'autre : la condition correcte est abs(x) < 50, c'est-à-dire $-50<x<50$. Avec elle, $-400$ passe au elif, où $-400>0$ est faux, et l'écran affiche enfin la flèche vers la gauche. Un seuil sur une grandeur qui a un signe se teste presque toujours en valeur absolue.

Au moment de l'appui, decalage prend la valeur lue, $120$ : c'est l'ÉTALONNAGE, qui retient le zéro de la table. Ensuite, le programme ne compare plus la lecture brute mais l'écart à cette référence. Pour $150$ : $x=150-120=30$, et $|30|<50$, l'écran affiche la coche : la carte est à plat par rapport à la table. Pour $200$ : $x=200-120=80$, $|80|\geq 50$ et $80>0$, l'écran affiche la flèche vers la droite. Sans étalonnage, $150$ aurait donné une flèche, alors que la carte n'a presque pas bougé : une valeur de capteur n'a de sens que par rapport à son ZÉRO.

Quatre libertés : utiliser, étudier, redistribuer, modifier et redistribuer ses modifications. ÉTUDIER le fonctionnement d'un programme et le MODIFIER exigent le code source : un fichier exécutable n'est qu'une suite d'instructions machine, illisible et presque impossible à adapter, alors que le code source est le texte écrit par les programmeurs. C'est pourquoi une licence libre impose de fournir le code source avec le programme. Libre et propriétaire sont donc des mots de DROIT : ils décrivent ce que la licence permet, pas la manière dont le logiciel est fabriqué ni son prix.

Debian GNU/Linux est libre : son noyau Linux et ses outils GNU sont sous licence libre, et tout son code source est publié. FreeBSD est libre aussi, sous une licence BSD. Windows est propriétaire : sa licence autorise à l'utiliser, mais interdit d'en étudier le code, qui n'est pas fourni, de le modifier et de le redistribuer. macOS est propriétaire, pour les mêmes raisons. La question ne se tranche pas au prix ni à la popularité, mais à la lecture de la licence.

Un logiciel peut être GRATUIT et PROPRIÉTAIRE : c'est un gratuiciel, qu'on télécharge sans rien payer mais dont la licence interdit d'étudier le code, de le modifier ou de le redistribuer ; beaucoup de pilotes et d'applications mobiles sont dans ce cas. Un logiciel peut être LIBRE et PAYANT : certaines distributions Linux pour entreprises sont vendues par abonnement, avec l'assistance, alors que leur code reste libre et que l'acheteur garde les quatre libertés. L'affirmation de l'élève confond le PRIX, qui est une question commerciale, et la LICENCE, qui est une question de droits. Le mot anglais free, qui veut dire à la fois libre et gratuit, entretient la confusion.

Les licences coûtent $30\times 150=4\,500$ dollars, une seule fois. Le contrat d'assistance coûte $800$ dollars par an : $800\times 5=4\,000$ dollars au bout de cinq ans, encore moins que les licences, et $800\times 6=4\,800$ dollars au bout de six ans, davantage. Le coût cumulé de l'assistance dépasse donc celui des licences à partir de la SIXIÈME année. Sur cinq ans, le choix libre est un peu moins cher ; au-delà, il l'est un peu plus. Le prix ne départage pas vraiment les deux solutions, et ce n'est pas lui qui définit le libre : l'argument sérieux est ailleurs, dans les droits que donne la licence.

La sécurité ne repose pas sur le secret du code. Un code source public peut être relu par tous, chercheurs, entreprises, administrations, et une faille trouvée peut être corrigée et vérifiée par n'importe qui ; un code fermé n'est audité que par son éditeur, et ses failles, que les attaquants trouvent quand même en analysant l'exécutable, restent corrigées à son seul rythme. Le libre n'est pas sans faille, mais il n'est pas moins sûr par principe. Pour l'enseignement, un système libre permet d'aller voir comment il fonctionne, de lire ses sources, de l'installer sur autant de postes qu'on veut et d'en garder la maîtrise : c'est pour cela que le programme de Première demande que les élèves utilisent un système d'exploitation libre.