\chapter{Architecture\\matérielle et réseaux}

\section{Architecture matérielle}

\subsection{Les composants du numérique}

Un téléphone portable, une télévision connectée et de nombreux appareils de notre quotidien sont en réalité de petits ordinateurs. Ils sont dotés d'une architecture similaire à celle d'un PC portable ou d'un PC fixe.

\subsubsection{Composants de base indispensables}

\begin{itemize}
\item \textit{Processeur}.\index{CPU}

On l'appelle aussi CPU (Central Processing Unit). Il est responsable de l'exécution des instructions de tous les microprogrammes.

\begin{itemize}
\item[$\to$] Il fonctionne de manière cadencée, c'est-à-dire qu'il existe une fréquence à laquelle il exécute les instructions. À chaque période, une nouvelle instruction lui est livrée et il procède au calcul attenant. On appelle cette période un \textit{cycle d'exécution}.

\item[$\to$] Il peut être composé de plusieurs c\oe urs. Chaque c\oe ur est une unité d'exécution qui travaille en parallèle des autres, à la fréquence d'exécution globale. Un processeur 4 c\oe urs, par exemple, exécutera 4 instructions en parallèle à chaque période.

L'augmentation du nombre de c\oe urs permet donc l'exécution d'un plus grand nombre d'opérations par seconde sans avoir besoin d'augmenter la fréquence globale d'exécution. C'est un point très intéressant car l'augmentation de la fréquence provoque celui de la consommation électrique et de la dissipation thermique (le processeur chauffe d'avantage). 
\end{itemize}

\newpage

\item \textit{Mémoire de travail (RAM)}.\index{RAM}

La RAM (\textit{Random Access Memory}) est une zone de stockage des données volatiles. Les programmes en cours d'exécution ainsi que les données qu'ils manipulent ou qui sont nécessaires à leur fonctionnement y sont chargés. La RAM est toujours vide au démarrage de la machine. C'est d'abord le système d'exploitation qui y est chargé. Il charge ensuite les programmes à exécuter, qui y chargent, à leur tour, les données dont ils ont besoin. Quand un programme termine son exécution, il est déchargé de la mémoire ainsi que tous les éléments qu'il y a lui-même inséré.

\item \textit{Contrôleurs et interfaces de communication (E/S ou I/O)}.
\index{Contrôleurs}
\index{Interface de communication}

Pour fonctionner, les programmes ont besoin de communiquer avec des périphériques comme une souris, un clavier, un disque dur, des réseaux ethernet ou wifi, des capteurs (boutons marche/arrêt, capteur de température,...), le Bluetooth, l'écran, etc.

Chaque périphérique doit être régi par un contrôleur adapté. Il s'agit d'un ensemble de composants électroniques (dont un sous-processeur), dédiés à chaque type de périphérique et plus ou moins complexes suivant le cas. Un réseau\linebreak ethernet, par exemple, sera géré par un contrôleur qui se chargera d'encoder/décoder les données envoyées/reçues vers/depuis les signaux électriques qui transitent dans le câble ethernet.

\Par

Le processeur peut donc communiquer avec chacun des contrôleurs et recevoir des données de leur part (même quand il ne s'y attend pas expressément). Ces communications s'appellent des E/S (\og Entrées/Sorties \fg) ou I/O (\og Input/\linebreak Output \fg), souvent notées simplement IO ou IOs (à ne pas confondre avec iOS, le célèbre système d'exploitation d'Apple !).

\item \textit{Bus de données}.\index{Bus de données}

Il s'agit des interconnexions entre les différents composants cités ci-dessus. Les données envoyées par le processeur vers la mémoire et les contrôleurs transitent à une fréquence fixe et suivant des protocoles de communication (règles très strictes) qui ne seront pas détaillés ici. Il faut imaginer qu'il existe un véritable réseau d'interconnexions des composants entre eux (un peu comme des routes qui relient des quartiers, des villes, des pays,...). Les communications sont alors comparables aux véhicules qui transitent sur ces routes et le protocole de communication s'apparente au code de la route. Il organise la circulation, définit les vitesses règlementées, évite les collisions, etc.

\Par

Ces \og routes \fg et les règles qui régissent la communication s'appellent un bus de données. Un des plus connus est le bus USB, présent sur tous nos ordinateurs et smartphones. Il est décliné en plusieurs versions (comme USB2, USB3, \mbox{USB-C}) suivant le protocole de communication choisi.

\item \textit{Carte mère}.\index{Carte mère}

Tous les éléments ci-dessus ont besoin d'être interconnectés de manière fiable. C'est le rôle de la carte mère. Circuit imprimé multicouche, elle possède non seulement les pistes d'interconnexion mais aussi un grand nombre de\linebreak composants électroniques pour l'organisation des communications, l'adaptation des niveaux électriques, des impédances, la dissipation thermique, des sécurités en cas de surtensions ou de sous-tensions, les bus de communication,...

\item \textit{Mémoire de stockage (appelée aussi mémoire de masse)}.\index{Mémoire de masse}

C'est le disque dur, la clé USB ou encore la carte SD, supports de stockage permanent des programmes et des données. On y trouve l'ensemble des programmes susceptibles d'être exécutés et les données stockées (images, ressources, documents, fichiers de configuration,...)
\end{itemize}

\subsubsection{Composants complémentaires très fréquents}

\begin{itemize}
\item \textit{Contrôleur vidéo et accélérateur graphique}.\index{GPU}

Nommé généralement GPU (Graphics Processing Unit), il s'agit d'un processeur à part entière et de son microenvironnement minimal (mémoire de travail, bus de communication) qui composent le contrôleur graphique. Il est responsable:
\begin{itemize}
\item[$\to$] de la confection des images affichées à l'écran dans la résolution appropriée;
\item[$\to$] des calculs nécessaires aux représentations 2D et 3D;
\item[$\to$] de la traduction des images en signaux vidéos  compatibles avec la connexion utilisée (VGA, SVGA, HDMI, RCA);
\item[$\to$] de la gestion éventuelle de plusieurs écrans en parallèle.
\end{itemize}

Il décharge le processeur (CPU) des tâches routinières et répétitives liées à l'affichage et la composition des images, car elles doivent être exécutées en permanence quel que soit le programme courant (navigation sur le web, vidéo en streaming, défilement des écrans,...).

Le CPU peut ainsi consacrer ses cycles d'exécution au fonctionnement des programmes. Ainsi, la fluidité d'une vidéo, par exemple, est davantage liée aux performances de la puce graphique qu'à celles du CPU.

\item \textit{Contrôleur audio}.

C'est l'équivalent du contrôleur vidéo pour la gestion du son. Il élabore les signaux analogiques qui seront transmis aux enceintes ou dispositifs de diffusion sonore (ampli, chaîne hifi, casque). Il intercepte les signaux analogiques provenant d'éventuels microphones, les numérise et transmet l'information au CPU. 

\item \textit{Contrôleurs de communication}.

Ils sont responsables de la gestion des communications à faible ou grande portée qui peuvent être réalisées directement depuis un équipement numérique. Les supports et protocoles de communication comme le réseau Ethernet, la fibre optique, le Wifi, le Bluetooth ou les communications GSM Data large bande nécessitent, à chaque fois, un contrôleur spécifique.

\newpage

\item \textit{Autres contrôleurs diversifiés}.

Il existe beaucoup d'autres types de contrôleurs, autant qu'il existe de types de périphériques et d'interconnexions. Notons par exemple:
\begin{itemize}
\item[$\to$] le système d'alimentation autonome (batterie, chargeur);
\item[$\to$] les capteurs en tout genre (radio, GPS, proximité, accéléromètre, boussole, température,...).
\end{itemize}
\end{itemize}

\begin{figure}
\begin{center}
\includegraphics{274_08-ordi}
\figcaption{Différents composants d'un ordinateur}
\end{center}
\end{figure}

\subsection{Les SoCs (System on Chip)}
\index{SoC}

Depuis les débuts de l'informatique, les composants électroniques n'ont cessé:
\begin{itemize}
\item de se sophistiquer (de plus en plus \og intelligents \fg),
\item de gagner en performances/rapidité (augmentation de la puissance de traitement),
\item de se miniaturiser,
\item de devenir accessibles au plus grand nombre (diminution des coûts de production).
\end{itemize}

La miniaturisation a atteint de telles proportions qu'il est aujourd'hui possible de réunir au sein d'une seule puce électronique tous les composants vitaux d'un ordinateur (CPU, RAM, mémoire de stockage, bus de communications, contrôleurs, GPU, interconnexions,...). Ces \og ordinateurs-puce \fg s'appellent des SoCs.

\begin{defin}
Un \textit{SoC} (System On Chip) est un système intégré sur une unique puce électronique qui regroupe les différents composants d'un ordinateur tels que le processeur, la mémoire, les interfaces et bus de communication, etc.
\end{defin}

\subsubsection{Avantages}

\begin{itemize}
\item Le principal avantage des SoCs est leur faible encombrement (juste une puce électronique), qui leur permet d'être implantés dans des appareils de taille réduite (téléphone, montre,...). L'avènement des smartphones est à l'origine de leurs succès.

\item Un autre avantage est la faible consommation énergétique d'un SoC due à la miniaturisation des composants. Il y a moins de pistes que sur une carte mère, les distances sont raccourcies, il n'y a pas besoin de connecteur ni de câble et la tension d'alimentation peut être réduite. On obtient ainsi moins de dissipation thermique et de pertes par effet Joule.

\item Enfin, les SoCs ont fait baisser les coûts de fabrication et d'industrialisation car ils sont produits en très grande quantité et ne nécessitent pas d'assemblage manuel des éléments qui les composent. Tous les composants électroniques sont gravés en une seule fois au sein d'une unique puce. 
\end{itemize}

\subsubsection{Inconvénients}

Les éléments qui composent un SoC étant gravés ensemble, il n'est pas possible de les faire évoluer individuellement. On ne pourra pas changer la \og carte réseau \fg ni la \og carte graphique\fg par exemple.

\Par

En conséquence, la durée de vie et la fiabilité d'un SoC sont celles de son maillon le plus faible. Le premier élément d'un SoC à présenter un dysfonctionnement provoquera une altération complète du SoC, qui ne pourra pas être réparé en changeant l'élément défaillant.

\enlargethispage*{4em}

\begin{aretenir}
\begin{itemize}
\item Un processeur multi-c\oe ur exécute autant d'instructions par cycle qu'il a de c\oe urs.

\item La consommation électrique et l'échauffement augmentent avec la fréquence d'exécution.

\item Tous les programmes en cours d'exécution et les données qu'il manipule sont recopiés et \og travaillés \fg dans la RAM.

\item Il existe un grand nombre de contrôleurs spécifiques, dédiés aux fonctionnalités assumées par la machine et au pilotage des périphériques. Ils déchargent le processeur (CPU) des opérations routinières.

\item Les différents composants d'une machine numérique communiquent via des bus de données.

\item Un SoC (System on Chip) est une puce unique qui embarque tous les éléments de base d'un ordinateur.
\end{itemize}
\end{aretenir}

\begin{figure}
\begin{center}
\includegraphics{276_08-samsung-recto}

\Par

\includegraphics{276_08-samsung-verso}

\figcaption{Carte mère d'un smartphone Samsung S7 (recto/verso)}
\end{center}
\end{figure}

\Par

\textit{Voir exercices \ref{exo:08-soc1} page \pageref{exo:08-soc1} et \ref{exo:08-soc2} à \ref{exo:08-achi-soc} page \pageref{exo:08-achi-RAM}.}

\section{Processus et ressources partagées}
\index{Processus}

\begin{problematique}
Comment un système d'exploitation multitâche fait-il pour exécuter de nombreux programmes simultanément alors que la machine ne possède qu'un seul et unique processeur avec un nombre de c\oe urs très limité ?
\end{problematique}

\newpage

\subsection{Partage du temps d'exécution}

Dans un système d'exploitation multitâche comme Windows, Mac OS, iOS, Androïd ou encore Linux, on a l'impression que plusieurs programmes peuvent s'exécuter en même temps: notre navigateur télécharge un fichier pendant qu'un flux vidéo est en lecture sur VLC (logiciel de lecture vidéo), un traitement de texte est ouvert, une impression est lancée sur l'imprimante et une visio-conférence est en cours, tout ça sur un même PC, en même temps.

Mais cette simultanéité n'est qu'illusion. En réalité, le processeur ne peut pas exécuter plus d'instructions simultanées qu'il n'a de c\oe urs. Pourtant, notre machine n'a que 2 c\oe urs et 17 programmes s'exécutent apparemment en même temps, sans compter le système d'exploitation.

Pour réussir ce tour de force, l'OS va exécuter un peu de chaque programme tour à tour.

\subsubsection{Processus}

\vspace*{-3mm}
\begin{defin}
On appelle \textit{processus} une instance d'un programme, chargée en mémoire et qui est exécutée de manière continue ou discontinue par le système d'exploitation.
\end{defin}

\begin{attention}
Il y a une différence subtile entre un \textit{programme} et un \textit{processus}. 

Un programme (par exemple un éditeur de texte), est un jeu d'instructions susceptibles d'être exécutées. Tant que ce n'est pas le cas, le programme est juste stocké sur la mémoire de masse. Ce n'est alors pas un processus, bien que ce soit un programme.
\end{attention}

À son lancement, les instructions qui le composent sont chargées en mémoire de travail (RAM) et exécutées. Le programme a donné lieu à un processus constitué par la recopie de ses instructions en mémoire et l'exécution attenante. On dit que le système d'exploitation exécute une instance du programme, en mémoire, dans un processus dédié.

\Par

Supposons maintenant que l'on démarre de nouveau le même programme sans avoir fermé celui en cours d'exécution (par exemple, pour éditer deux documents texte différents). C'est toujours le même programme qui va être, de nouveau, recopié en mémoire, à un autre endroit, puis exécuté (lié au second document). On a alors, en mémoire, deux instances différentes du même programme qui s'exécutent simultanément, chacune dans un processus différent.

\newpage

\subsubsection{Contexte d'exécution et switching}

Un système d'exploitation multitâche exécute chaque processus dans un environnement mémoire cloisonné et protégé. Un processus ne peut lire et écrire des données en mémoire que dans la zone que le système d'exploitation lui a dédié. L'OS garantit qu'aucun autre processus en cours d'exécution ne pourra lire ni modifier ses données.
 
En classe de première, on a vu que le processeur possédait plusieurs registres (RI, AC, CC,...), un compteur ordinal et une UAL pour l'exécution des instructions. Lorsqu'un processus est exécuté, ce sont ses instructions qui occupent les registres et la \og mémoire interne \fg du processeur.

Or l'OS doit exécuter les processus tour à tour pour donner l'illusion de leur simultanéité. Il doit donc très souvent interrompre l'exécution du processus en cours (A) pour permettre à un autre processus (B) de s'exécuter. Puis interrompre (B) pour exécuter un troisième processus (C),  etc.

Mais lorsqu'il sera question de poursuivre l'exécution du processus (A), il faudra que celui-ci continue à l'endroit précis où il a été interrompu. Pour cela, tous les registres du processeur devront être pré-initialisés dans l'état précis où ils étaient au moment de l'interruption de (A). Pourtant, leur état a fortement été modifié par les exécutions successives de (B) puis de (C).

Lorsqu'il interrompt un processus, l'OS doit donc conserver scrupuleusement en mémoire l'état précis de tous les éléments volatiles au moment de cette interruption pour les restituer exactement dans le même état à la reprise du processus interrompu.

\begin{defin}[contexte d'exécution]
On appelle \textit{contexte d'exécution} (execution context) l'ensemble de tous les éléments volatiles liés à l'exécution d'un processus. Ils devront être sauvegardés par le système à l'interruption du processus et restitués, en l'état, à sa réactivation.
\end{defin}

\begin{defin}[changement de contexte]
On appelle \textit{changement de contexte} (context switching) l'opération de remplacement d'un contexte d'exécution par un autre et de recopie en  mémoire de chaque contexte écrasé.
\end{defin}

À titre informatif, voici quelques uns des éléments que l'OS doit conserver à l'interruption d'un processus et restituer à sa réactivation. Ils constituent le \textit{Process Control Block} (PCB) ou \textit{bloc de données contextuelles} de chaque processus.

\begin{itemize}
\item Le numéro d'identification du processus (PID pour Process ID).
\item L'état du processus, de son compteur ordinal et des autres registres.
\item L'emplacement mémoire du code, des données et de la pile d'instructions.
\item Les pointeurs vers les ressources utilisées, fichiers, E/S,...
\item Le pointeur vers le processus parent, priorité, compteur de threads, durée d'exécution, informations d'attentes,... et bien d'autres informations.
\end{itemize}

\subsection{Le Scheduler (ordonnanceur)}
\index{Ordonnanceur}

\begin{defin}[scheduler]
Le \textit{scheduler} est le module du système d'exploitation qui se charge d'organiser l'exécution des processus à tour de rôle. Il a la délicate mission d'octroyer un peu de temps d'exécution processeur (quantum de temps) à tous les processus, en gérant les priorités, les débordements et les changements de contexte.
\end{defin}

\begin{defin}[quantum de temps]
On appelle \textit{quantum de temps} le plus petit temps d'exécution que l'OS peut attribuer à un processus. C'est une valeur qui est peu soumise à modification. Un processus peut se voir allouer 1 à $n$ quantum(s) de temps successif(s). Typiquement, un quantum de temps dure 20 à 50 ms suivant les OS et les algorithmes d'ordonnancement utilisés.
\end{defin}


\subsubsection{\'Etats d'un processus}

\paragraph{Définitions}

Tous les processus qui cohabitent en mémoire à un instant donné ne sont pas forcément en attente du processeur. Il se peut qu'un processus attende une ressource, un résultat ou un autre processus et ne puisse rien faire tant que la ressource attendue n'est pas disponible.

Prenons, par exemple, le cas (très simplifié) d'un logiciel de lecture vidéo alimenté par un flux en streaming. Les données vidéo arrivent via le réseau. Le logiciel les décode et les transmet au contrôleur vidéo pour affichage. Supposons que le logiciel ait préparé 4 secondes de données vidéo transmises au contrôleur. Il ne peut rien faire tant que la suite des données n'arrive pas sur le réseau. Inutile, dans ces conditions, que le scheduler lui alloue un quantum de temps processeur car le processus n'en ferait rien.

\begin{defin}[état \og bloqué \fg]
On dit qu'un processus est dans l'état \og bloqué \fg lorsqu'il n'est plus éligible à l'obtention d'un quantum de temps processeur car en attente d'une ressource.
\end{defin}
\enlargethispage*{\baselineskip}

Dans notre exemple, le processus est bloqué jusqu'à ce que de nouvelles données vidéo soient disponibles sur le réseau. Lorsque ces données arrivent, le processus obtient de nouveau du \og grain à moudre \fg mais il n'est pas immédiatement exécuté pour autant. Il repasse d'abord dans l'état \og prêt à être exécuté \fg et c'est le scheduler qui lui attribuera un ou plusieurs quantums de temps.

\begin{defin}[état \og prêt \fg]
On dit qu'un processus est dans l'état \og prêt \fg lorsqu'il dispose de toutes les ressources dont il a besoin pour effectuer ses opérations. Il ne lui manque que l'obtention de quantum(s) de temps processeur pour exécuter/poursuivre son travail.
\end{defin}

Voici tous les états que peut prendre un processus:

\Par

\begin{figure}
\begin{center}
\includegraphics{280_07-etats-03}
\figcaption{Les différents états d'un processus\\dans un ordonnancement à court terme}
\end{center}
\end{figure}

\paragraph{\'Etats principaux}

\begin{itemize}
\item \textit{Nouveau}.

Un programme a été sélectionné pour démarrage. Ses instructions ont été recopiées en mémoire par l'OS et un nouveau processus y a été attaché mais jamais encore exécuté. Son contexte d'exécution et son PCB doivent être préparés et il doit être inséré dans la liste des processus \og prêts \fg.


\item \textit{Prêt}.

Le processus est en attente de quantum(s) de temps CPU pour exécuter son travail.

\item \textit{En cours d'exécution}.

Un ou plusieurs quantum(s) de temps a (ont) été alloué(s) au processus. Il exécute ses instructions jusqu'à écoulement du temps imparti.

\item \textit{Bloqué}.

Le processus est en attente d'une ou plusieurs ressource(s) (réseau, lecture disque, USB, Bluetooth, action utilisateur comme un clic ou un mot de passe,...) et ne peut rien faire en attendant. Il n'est pas éligible à l'obtention d'un quantum de temps CPU.

\item \textit{Terminé}.

Le processus a achevé son exécution jusqu'à sa dernière instruction. Il doit être déchargé de la mémoire par l'OS. À cette occasion, la mémoire qu'il a utilisée va être libérée ainsi que toutes les ressources détenues (fichiers, connexion réseau,...).
\end{itemize}

\paragraph{\'Etats secondaires}

Pour augmenter virtuellement la mémoire dont dispose la machine, certains OS déchargent les processus inactifs de la mémoire (typiquement ceux bloqués pendant de nombreux quantums de temps). Ils stockent alors toutes les informations déchargées sur le disque (ou autre mémoire de masse), y compris le PCB du processus.

Le processus ne pourra alors pas être ré-exécuté lorsqu'il sera \og débloqué \fg. Il devra préalablement être rechargé en mémoire. Ces opérations (typiquement à \og long terme \fg) donnent lieu à deux nouveaux états:

\begin{itemize}
\item \textit{Permuté bloqué}.

Le processus est déchargé de la mémoire et il est, en plus, en attente d'une ressource.

\item \textit{Permuté prêt}.

Le processus a été déchargé de la mémoire mais n'est plus en attente d'une ressource, il doit être rechargé en mémoire pour passer dans l'état \og prêt \fg et être éligible à une exécution.
\end{itemize}

\subsubsection{Algorithmes de scheduling}

Le scheduling (ordonnancement des processus) est un élément crucial d'un OS multitâche. Le partage du processeur doit être fait non seulement entre les processus démarrés par l'utilisateur mais aussi entre les différentes tâches du système d'exploitation, dont le scheduleur lui-même.

Il existe de nombreux algorithmes de scheduling différents qui ont toujours pour but de répartir les quantums de temps de la manière la plus optimisée entre tous les processus. Il serait trop complexe de détailler ici le fonctionnement de chacun d'eux mais voici un aperçu des principales méthodes de scheduling.

\begin{itemize}
\item \textit{First-come, first-served (FCFS)  : premier arrivé / premier servi}.

Les processus sont stockés dans une file. Le premier arrivé est admis\linebreak immédiatement et s'exécute tant qu'il n'est pas bloqué ou terminé. Lorsqu'il se bloque, le processus suivant commence à s'exécuter et le processus bloqué va se mettre au bout de la file d'attente.

\Par

\begin{itemize}
\item[$\to$] Avantages : l'algorithme est simple (c'est une simple liste chaînée),\linebreak l'ordonnancement est équitable.

\Par

\item[$\to$] Inconvénient : le processus qui utilise davantage de temps est favorisé par rapport à ceux qui font beaucoup d'appels aux entrées/sorties.
\end{itemize}

\item \textit{Shortest Job First  (SJF) :  le job le plus court d'abord}.

Le processus dont le temps de traitement sera supposé le plus court est\linebreak prioritaire. Si quatre tâches (jobs) ont des durées (en secondes) respectivement égales à $a$, $b$, $c$ et $d$, la première se termine après $a$ secondes, la deuxième après $a+b$ secondes, etc. 

La durée de rotation moyenne est alors $\dfrac{4a+3b+2c+d}{4}$. Il est donc légitime de traiter en premier la tâche la plus courte car sa durée est multipliée par 4.

\begin{anecdote}
C'est typiquement l'algorithme qui est fréquemment observé aux caisses de supermarché quand des clients laissent passer ceux qui n'ont que peu d'articles.
\end{anecdote}

\Par

Un inconvénient de cet algorithme est le suivant : si de multiples processus courts arrivent sans cesse, les plus longs ne sont jamais exécutés.

\item \textit{Shortest Remaining Time (SRT) : l'algorithme du temps restant le plus court}.

C'est une version plus \og agressive \fg{} du précédent. On tient compte ici du temps restant, et non du temps total, du processus.

Imaginez un client n'ayant qu'un article qui arrive à la caisse d'un supermarché : il vient carrément interrompre le client face à la caissière pour faire passer son article s'il reste à ce dernier plus d'un article à faire passer. 

\item \textit{Round Robin (RR) : l'algorithme du tourniquet}.

Chaque processus se voit alloué un certain temps, appelé \textit{quantum}, et à tour de rôle, chacun d'eux est traité par le processeur.

En général, dans les OS multitâches, c'est cet algorithme qui est utilisé, avec un quantum entre 20 ms et 50 ms.

\item \textit{L'ordonnancement avec priorité}.

Une valeur de priorité est assignée à chaque processus, la priorité pouvant varier dynamiquement. 

Par exemple, pour ne pas encombrer la mémoire avec des processus qui passent beaucoup de leur temps à attendre des E/S, on leur accorde une priorité d'autant plus grande qu'ils ne consomment qu'une petite fraction de leur quantum.

Supposons que la valeur du quantum est fixée à 50 ms. Un processus qui\linebreak n'utilise que 1 ms avant d'être bloqué aurait droit à une priorité de $\dfrac{50\text{ ms}}{1\text{ ms}} = 50$ tandis qu'un processus qui se bloque au bout de 25 ms a droit à une priorité de $\dfrac{50}{25}=2$ et les processus qui consomment tout le quantum ont une priorité de 1.
\end{itemize}

\subsection{Deadlock (interblocage)}
\index{Deadlock}
\index{Interblocage}

\subsubsection{Principe}

Il est possible qu'un processus (A) soit en attente d'un travail que doit fournir un autre processus (B). Dans ce cas, A est bloqué jusqu'à ce que B ait fourni le travail attendu.

Supposons maintenant que pour effectuer ce \og travail attendu \fg, le processus B ait besoin, à son tour, d'un travail effectué par le processus A. 

Dans ce cas, B est bloqué jusqu'à ce que A ait fourni son travail. Sauf que A est déjà bloqué et ne peut être débloqué tant que B ne termine pas sa mission.

Cette situation provoque un blocage réciproque de A et de B qui s'attendent\linebreak mutuellement. On appelle cette situation un interblocage (deadlock en anglais).

\Par

\begin{figure}
\begin{center}
\includegraphics{283_08-dead-lock}
\figcaption{Exécution avec et sans interblocage}
\end{center}
\end{figure}

\subsubsection{Verrouillage d'une ressource}

Un processus peut également requérir l'accès exclusif à une ressource (fichier, port USB, zone mémoire,...). Une fois que la ressource est fournie au processus, par l'OS, de manière exclusive, elle ne peut pas redevenir disponible jusqu'à ce que le processus la libère à l'issue de son travail.

Prenons le cas d'un processus qui copie un fichier source S vers un fichier de destination D.

\begin{itemize}
\item Il peut partager le fichier source S avec d'autres processus à condition que ceux-ci ne modifient pas le contenu du fichier S. Les processus ne pourront pas obtenir d'accès en écriture sur le fichier S jusqu'à ce que la copie soit terminée.

\item Il doit obtenir un accès exclusif en écriture sur le fichier D. Aucun autre processus ne doit écrire dans le fichier D jusqu'à ce que la copie soit terminée.

\item Il est responsable de la libération des fichiers S et D, c'est-à-dire d'informer l'OS qu'il n'a plus besoin d'utiliser ces fichiers lorsqu'il aura terminé sa copie, sans quoi les fichiers restent verrouillés.
\end{itemize}

\begin{defin}[ressource verrouillée en processus]
On dit qu'une ressource est \textit{verrouillée par un processus} (locked en anglais) tant que ce processus est le seul à pouvoir l'utiliser. Tout autre processus qui tente de la verrouiller passe dans l'état \og bloqué \fg jusqu'à libération, par son détenteur, de la ressource convoitée.
\end{defin}

Lorsque l'exécution d'un processus est interrompue par le scheduler, il reste en possession de ses verrous. Les ressources sur lesquelles il a obtenu un verrou exclusif ne pourront pas être utilisées par les autres processus exécutés même si le détenteur des verrous est arrêté (\og prêt \fg ou \og bloqué \fg).

Ces situations conduisent souvent à des interblocages sur ressource. 

Soient par exemple deux processus A et B exécutés sur un OS multitâche:

\begin{itemize}
\item A requiert un verrou exclusif sur une ressource R$_1$ et l'obtient, puis il est interrompu par l'OS;
\item B requiert un verrou exclusif sur une ressource R$_2$ et l'obtient;
\item B requiert alors un autre verrou exclusif, sur la ressource R$_1$. Celle-ci étant détenue par A, B passe dans l'état bloqué (et y restera jusqu'à libération de R$_1$ par A);
\item lorsque A poursuit son exécution, il est toujours en possession de R$_1$. Il requiert à présent un verrou sur R$_2$. Celle-ci étant détenue par B, A passe dans l'état bloqué (et y restera jusqu'à libération de R$_2$ par B).
\end{itemize}

Dans cette situation, A et B sont tous deux inter-bloqués. A est le seul à pouvoir libérer R$_1$ qui débloquera B, mais B est le seul à pouvoir libérer R$_2$ qui débloquera A.

\Par

Il existe de nombreuses méthodes pour limiter ou empêcher ces interblocages. Les principales sont présentées ci-dessous à titre informatif:

\begin{itemize}
\item règles strictes imposant l'ordre d'acquisition des ressources;
\item analyse détaillée des algorithmes lors de la conception des processus pour éliminer les interblocages;
\item système préventif qui détecte un risque d'interblocage avant que celui-ci ne se produise durant l'exécution;
\item système de récupération si un interblocage se produit (le système doit pouvoir repartir dans un état valide).
\end{itemize}

\begin{Exemple}[algorithmes \og Attente/Mort \fg et \og Blessé/Attente\fg]
dans ces deux\linebreak algorithmes, on prend en compte l'âge des processus. On distingue alors le plus âgé (noté $A$) du plus jeune (noté $J$).
\end{Exemple}
\begin{itemize}
\item Dans l'algorithme \og Attente/Mort \fg :
\begin{itemize}
\item[$\to$] si $A$ requiert une ressource verrouillée par $J$, on attend la libération de cette ressource;
\item[$\to$] si $J$ requiert une ressource verrouillée par $A$ alors $J$ meurt (il est définitivement arrêté par l'OS avec libération de toutes ses ressources et retour au début de son exécution).
\end{itemize}

\item Dans l'algorithme \og Blessé/Attente \fg, 
\begin{itemize}
\item[$\to$] si $J$ requiert une ressource détenue par $A$, on attend la libération de cette ressource;
\item[$\to$] si $A$ requiert une ressource détenue par $J$ alors $A$ provoque la mort de $J$, ce qui libère toutes les ressources en sa possession et $J$ reprend son exécution depuis le début.
\end{itemize}
\end{itemize}

\nathanlive{video}{Retrouvez une vidéo de présentation des processus avec Nathan Live.}
\label{video:ch8-processus}

\Par

\textit{Voir exercices \ref{exo:08-processus1} page \pageref{exo:08-processus1} et \ref{exo:08-processus2} page \pageref{exo:08-processus2}.}

\vspace*{-1.5em}
\section{Réseau et routage des données}
\index{Réseau}

\begin{problematique}
Le réseau Internet est étendu à l'échelle planétaire, reliant des milliards de machines les unes aux autres : ordinateurs, routeurs, mais aussi smartphones, tablettes et un nombre en pleine croissance d'objets connectés tels que véhicules, assistants personnels, montres, et bientôt la plupart des équipements de maison.

Comment ces communications voyagent-elles d'un bout à l'autre du globe, parcourant en quelques dizaines de millisecondes des milliers de kilomètres ? Comment les routeurs, aiguilleurs du numérique, font-ils pour organiser tout ce trafic, choisir les routes optimales et garantir l'acheminement des informations de bout en bout, sans embouteillage, collision ni perte de donnée ?
\end{problematique}

\subsection{Le protocole IP}

En classe de première, vous avez vu qu'il existait plusieurs architectures réseau, dont la plus répandue est TCP/IP, composée des protocoles TCP (couche 4 du modèle OSI) et IP (couche 3). Dans la suite, nous nous limiterons à cette architecture et nous intéresserons uniquement à des protocoles de routage~IP. 

Inventé en 1974 par les Américains Vint Cerf et Bob Kahn, les règles du routage IP sont spécifiées dans le document RFC 791 de l'IETF (Internet Engineering Task Force). Ce document laisse le champ libre à différentes stratégies de routage. Nous verrons dans la suite qu'il existe plusieurs types de protocoles~IP.
\Par
\nathanlive{web}{Retrouvez le détail de la RFC 791 définissant le protocole IP avec Nathan Live.}

\subsection{Adressage}

%En classe de première, vous avez vu que plusieurs architectures réseau (dites architectures en couches ou modèle OSI) existaient, dont la plus répandue est composée des protocoles TCP/IP. Nous limiterons l'étendue de ce cours à cette architecture.

En informatique, communiquer consiste à envoyer et recevoir des lots de données nommés \textit{paquets}. Chaque paquet est comparable à une lettre dans le système postal. Il faut avant tout disposer d'une adresse pour pouvoir recevoir du courrier. On parle ici d'adresses IP (IPv4 ou IPv6) et d'adresses MAC.


\begin{defin}[adresse MAC]
L'\textit{adresse MAC} (Media Access Control) d'un équipement est un numéro codé sur 6 octets, lié à une carte réseau (ou autre dispositif physique de communication).  C'est l'adresse physique  identifiant de
manière unique l'équipement. %Le dispositif ne peut pas changer d'adresse MAC. C'est l'adresse \textit{physique} identifiant de manière unique l'équipement. %Elle y est inscrite lors de la construction de l'équipement: \og gravée \fg et unique.
\end{defin}

\begin{defin}[adresse IP]
Une \textit{adresse IP} (Internet Protocol) est un numéro codé sur 4 octets (IPv4) ou sur 16 octets (IPv6) attribué à un ordinateur ou tout autre dispositif logique de communication. 
\end{defin}

L'adresse IP est \textit{contextuelle}: elle dépend du réseau sur lequel se connecte la machine et de sa configuration. Elle peut varier dans le temps.

\subsection{Topologie réseau}

On représente généralement des machines interconnectées sur un réseau IP de la manière suivante:

\Par

\begin{figure}
\begin{center}
\includegraphics{286_08-reseau}
\figcaption{Machines interconnectées sur un réseau IP}
\end{center}
\end{figure}

\Par

Sur cet exemple,
\begin{itemize}
\item A, B, C et D sont quatre machines reliées au même réseau IP. Elles ont pour adresses IP:
\begin{center}
A: 50.40.30.1\quad;\quad B: 50.40.30.2\quad;\quad C: 50.40.30.3\quad;\quad D 50.40.30.4
\end{center}

\item l'adresse 50.40.30.0/24 n'est pas l'adresse d'une machine en particulier, mais celle du réseau IP lui-même. Elle signifie que toutes les machines raccordées à ce réseau auront une adresse IP de la forme 50.40.30.x avec x compris entre 1 et 254 inclus.
\end{itemize}

Une adresse IP contient à la fois une partie \og réseau \fg (à gauche) et une partie \og machine \fg (à droite).

\begin{Exemple}$\underbrace{50.40.30}_{\text{\fontsize{10}{10}\selectfont réseau}}.\underbrace{123}_{\text{\fontsize{10}{10}\selectfont machine}}/~24$

\Par

Les trois premiers octets correspondent à l'adresse du réseau et le dernier octet sert à différencier la machine sur ce réseau. Une adresse IPv4 est codée sur quatre octets soit 32 bits. Le complément \og /24 \fg, situé derrière l'adresse du réseau, indique le nombre de bits (à gauche de l'adresse) utilisés pour la partie \og réseau \fg. Ici, ce sont les vingt-quatre premiers bits de l'adresse, soit les trois premiers octets. On appelle ce complément le \textit{masque de réseau}.
\end{Exemple}

\begin{defin}
On appelle \textit{masque de réseau} un moyen d'identifier les bits d'une adresse IP correspondant à sa partie \og réseau \fg. 

Un masque peut être donné:
\begin{itemize}
\item sous la forme \og /N \fg, où N est le nombre de bits utilisés dans l'adresse réseau (comme \og /24 \fg);
\item sous la forme d'une suite de quatre décimaux, compris entre 0 et 255, représentant chacun un octet formé par les bits servant au réseau.
\end{itemize}
\end{defin}

\begin{Exemple}le masque réseau de l'adresse IP 50.40.30.123 est \og /24 \fg, que l'on peut aussi écrire : 255.255.255.0.
\Par
\begin{figure}
\begin{center}
\includegraphics{287_08-masque-reseau}
\figcaption{Calcul du masque réseau}
\label{exemple-masque-reseau}
\end{center}
\end{figure}
\end{Exemple}

\begin{defin}
Deux machines (A) et (B) sont dites \textit{sur le même réseau local} lorsque qu'elles ont le même masque de réseau et que leur adresse IP ont leur partie \og réseau \fg strictement identiques.
\end{defin}
\enlargethispage*{3em}

Dans l'exemple de la figure \ref{exemple-masque-reseau} précédente, les machines A, B, C et D sont sur le même réseau local.

Les machines d'un même réseau local s'échangent leur adresse MAC par une mécanique qui n'est pas au programme de terminale, mais il faut admettre qu'une machine connait toutes les adresses MAC de ses voisines (sur le même réseau). En revanche, aucune machine ne peut connaitre l'adresse MAC d'une autre machine si elles sont situées sur des réseaux IP différents.

\subsection{Routage IP}


\nathanlive{video}{Retrouvez une présentation du routage IP avec Nathan Live.}
\label{video:ch8-routage}

\Par

Lorsqu'un ordinateur (A) veut communiquer avec un ordinateur (B), il a besoin:
\begin{itemize}
\item de connaitre l'adresse IP de (B);
\item de disposer lui-même d'une adresse IP pour se \og signaler \fg et recevoir la réponse;
\item de connaitre l'adresse MAC de la machine auprès de laquelle il va déposer son message (qui n'est pas forcément le destinataire final).
\end{itemize}

Deux cas de figure sont à différencier:
\begin{itemize}
\item (A) et (B) sont situées sur le même réseau local (par exemple dans une maison, connectées au même point d'accès Wifi, à la même box internet ou au même switch) et dans ce cas, (A) peut directement entreprendre de déposer son paquet de données sur le réseau (en utilisant l'adresses MAC de son destinataire final);
\item (A) et (B) sont sur des réseaux IP disjoints. (A) ne connaît alors pas l'adresse MAC de (B) et ne peut pas l'atteindre directement. Dans ce cas, (A) aura besoin de connaitre un intermédiaire (routeur ou passerelle), sur son réseau local, qui se chargera de faire avancer le paquet de données pour qu'il rejoigne (B). Cet intermédiaire est un routeur (comme une box internet par exemple).
\end{itemize}

\begin{defin}[routeur]
Un \textit{routeur} est un équipement informatique qui participe à l'acheminement de données entre des réseaux différents.
\end{defin}

\subsection{Tables de routage}
\index{Routage (tables de)}
\enlargethispage*{5em}
Considérons l'architecture réseau suivante qui présente 4 réseaux locaux interconnectés par le biais de quatre routeurs (R1, R2, R3 et R4) dont un (R4) est connecté à l'Internet (R4 est supposé être une box ADSL ou fibre par exemple).
\Par
\begin{figure}
\begin{center}
\includegraphics{288_08-architecture-reseau}
\figcaption{Réseau à quatre routeurs}
\label{archi-reseau}
\end{center}
\end{figure}

\newpage

Une fois démarrés, les routeurs agissent, dans un premier temps, comme des PC pour constituer leur table de routage à partir des réseaux qui leurs sont directement reliés et qu'ils peuvent donc  eux-mêmes détecter.

Voici les tables de routage initiales (automatiques) ainsi constituées:

\Par

\begin{center}
\begin{tabular}{|>{\centering\arraybackslash}m{1.2cm}|*2{m{2.5cm}|}m{2.8cm}|}
\tabulartitle\hline
Routeur & Réseau & Masque & Destination\\
\hline
\multirow{2}{*}{R1} &\color{DG} 192.168.4.0 & \color{DG}255.255.255.0 &\color{DG} Interface locale F0\\\cline{2-4}
                    &\color{DB} 50.40.30.0  & \color{DB}255.255.255.0 &\color{DB} Interface locale F1\\\hline
\multirow{2}{*}{R2} & \color{DB}50.40.30.0  & \color{DB}255.255.255.0 &\color{DB} Interface locale F0\\\cline{2-4}
                    & 10.0.0.0    & 255.0.0.0     & Interface locale F1\\\hline
\multirow{2}{*}{R3} &\color{DO} 97.0.14.0   &\color{DO} 255.255.255.0 &\color{DO} Interface locale F0\\\cline{2-4}
                    & 10.0.0.0    & 255.0.0.0     & Interface locale F1\\\hline
R4 & \color{DO} 97.0.14.0   &\color{DO} 255.255.255.0 &\color{DO} Interface locale F0\\\hline
\end{tabular}
\end{center}

\Par

Ces informations ne suffisent pas à router l'ensemble du réseau ci-dessus. 

Supposons que la machine (A) ait besoin de communiquer avec la machine (G):
\begin{itemize}
\item (A) prépare un paquet de données TCP/IP vers l'IP 192.168.4.43;
\item comme (G) n'est pas sur son réseau local, elle envoie ce paquet à (R2) déclaré comme étant sa passerelle par défaut;
\item (R2) ne trouve aucune route dans sa table de routage pour atteindre (G) car le réseau 192.168.4.0/24 ne fait pas partie de ceux qu'il connaît; (A) et (G) ne peuvent alors pas communiquer entre eux.
\end{itemize}

Il est toujours possible de compléter manuellement les tables de routage pour indiquer à chaque routeur les réseaux qu'il ne peut pas découvrir seul (non directement reliés).

\subsection{Le protocole RIP}
\index{RIP (protocole)}
\index{Protocole RIP}

Ici, RIP ne signifie pas \og Rest In Peace \fg, mais  \og Routing Information Protocol \fg. RIP fait partie de la famille des protocoles de routage IP. Il s'agit d'une stratégie de routage, utilisée uniquement par des équipement spécialisés comme les routeurs, et comportant deux règles principales :
\begin{questions}
\item Chaque routeur doit envoyer périodiquement sa propre table de routage aux routeurs présents sur chacun de ses réseaux locaux (R1 à R2, R2 à R1 et R3, R3 à R2 et R4, R4 à R3). Les routeurs utilisent les informations reçues de leurs voisins pour compléter leur table de routage interne qui sera de nouveau transmise (complétée) à l'itération suivante. L'envoi a lieu, typiquement toutes les 30 secondes (ce délai étant paramétrable).

\item Chaque routeur effectue un décompte du nombre des autres routeurs présents sur chaque route de sa table de routage. Ce décompte aboutit à un entier nommé métrique de la route. Plus la métrique d'une route est élevée, plus un paquet de données, envoyé sur cette route, devra traverser un grand nombre de routeurs (effectuer des sauts) avant de parvenir à son destinataire.
\end{questions}

Voici le résultat de l'application du protocole RIP sur notre architecture (figure~\ref{archi-reseau}) à l'issue des échanges de tables. La topologie réseau n'étant pas modifiée sur le temps analysé, les tables sont uniquement complétées au fur et à mesure des échanges RIP. Il faut trois échanges successifs pour que chaque routeur ait la vision complète de l'architecture. La colonne \og Itération \fg indique l'échange RIP à l'issue duquel la ligne de routage est insérée dans la table.
\Par
\begin{tabular}{|Zc|Zc|*3{Zl|}Zc|}
\tabulartitle\hline
Routeur & Itération & Réseau & Masque & Destination & Métrique\\\hline
\multirow{4}{*}{R1} & \multirow{2}{*}{0} & 192.168.4.0 & 255.255.255.0 & F0 & 0\\\cline{3-6}
                    &                    & 50.40.30.0 & 255.255.255.0 & F1 & 0\\\cline{2-6}
                    & 1                  & 10.0.0.8 & 255.0.0.0 & 50.40.30.254 & 1\\\cline{2-6}
                    & 2                  & 97.0.14.0 & 255.255.255.0 & 50.40.30.254 & 2\\\hline
\multirow{4}{*}{R2} & \multirow{2}{*}{0} & 50.40.30.0 & 255.255.255.0 & F0 & 0\\\cline{3-6}
                    &                    & 10.0.0.0&255.0.0.0&F1&0\\\cline{2-6}
                    & \multirow{2}{*}{1} & 192.168.4.0 & 255.255.255.0 & 50.40.30.1 & 1\\\cline{3-6}
                    &                    & 97.0.14.0 & 255.255.255.0 & 10.0.0.254 & 1\\\hline
\multirow{4}{*}{R3} & \multirow{2}{*}{0} & 97.0.14.0 & 255.255.255.0 & F0 & 0\\\cline{3-6}
                    &                    & 10.0.0.0 & 255.0.0.0 & F1 & 0\\\cline{2-6}
                    & 1                  & 50.40.30.0.24 & 255.255.255.0 & 10.0.0.2 & 1\\\cline{2-6}
                    & 2                  & 192.168.4.0 & 255.255.255.0 & 10.0.0.2 & 2\\\hline
\multirow{4}{*}{R4} & 0                  & 97.0.14.0 & 255.255.255.0 & F0 & 0\\\cline{2-6}
                    & 1                  & 10.0.0.0 & 255.0.0.0 & 97.0.14.1 & 1\\\cline{2-6}
                    & 2                  & 50.40.30.0 & 255.255.255.0 & 97.0.14.1 & 2\\\cline{2-6}
                    & 3                  & 192.168.4.0 & 255.255.255.0 & 97.0.14.1 & 3\\\hline
\end{tabular}

\begin{Remarques}
\begin{itemize}
\item Ici, métrique et itération sont identiques à cause de la topologie (simple) du réseau mais ce n'est pas le cas pour des réseaux plus complexes.
\item Le protocole RIP impose à chaque routeur de supprimer les routes pour lesquelles la métrique est supérieure à 15 afin de limiter l'allongement des tables de routage, notamment lorsque le réseau comporte des boucles ou un très grand nombre de routeurs.
\end{itemize}
\end{Remarques}

\begin{attention}
Lorsqu'un même réseau est accessible par deux routes différentes, le protocole RIP impose de ne conserver que celle dont la métrique est la plus basse. C'est celle qui est considérée comme étant la plus optimisée (limite du nombre de sauts) en cas de doublons.
\end{attention}

\newpage

\subsection{Le Protocole OSPF}

Tout comme RIP, OSPF (Open Shortest Path First) est un protocole de routage IP. Il impose également l'échange périodique d'informations entre routeurs voisins. La principale différence réside dans le remplacement de la métrique par une \textit{connaissance partagée du débit} imputable à chaque réseau.

Considérons une topologie dans laquelle sont mis en \oe uvre des débits différents pour chaque réseau.

\Par

\begin{figure}
\begin{center}
\includegraphics{291_08-architecture-reseau-ospf}
\figcaption{Réseau dont les branches ont des débits différents}
\label{archi-reseau-ospf}
\end{center}
\end{figure}

\Par

Le protocole OSPF permet à chaque routeur de cette topologie de se construire le graphe complet des liaisons inter-routeur pour optimiser le routage en fonction du débit des réseaux.
\Par
\begin{figure}
\begin{center}
\includegraphics{291_08-graphe-ospf-1}
\figcaption{Graphe correspondant au réseau représenté sur la figure \ref{archi-reseau-ospf}}
\end{center}
\end{figure}

\Par\enlargethispage*{\baselineskip}

Supposons que R1 ait besoin de router un grand nombre de paquets TCP/IP vers R4:
\begin{itemize}
\item s'il les lui transmet directement en utilisant son interface locale F1, la communication s'effectuera à 1 Mb/s;

\item si un autre chemin est utilisé (par exemple, \og R1, R3, R4 \fg, \og R1, R2, R5, R4 \fg ou \og R1, R2, R3, R4 \fg), l'envoi sera effectué à environ 10 Mb/s, qui est le facteur le plus limitant (réseau jaune) des différents itinéraires possibles.
\end{itemize}

Avec le protocole RIP, l'itinéraire choisi aurait été (R1, R4) puisqu'il est direct, donc associé à une métrique de 0 dans ce protocole. L'envoi aurait été 10 fois plus lent (à 1 Mb/s).

\Par

Le protocole OSPF n'utilise pas la métrique du RIP mais calcule un coût pour chaque liaison (et même pour chaque arc lorsque les débits sont dissymétriques) dont la valeur est un entier obtenu par arrondi:
\[
\text{coût} = \dfrac{10^8}{\text{bande passante en bit/s}}.
\]

\begin{attention}
Le coût ne peut pas être nul; aussi, quand le calcul donne un résultat plus proche de 0 que de 1, on considèrera qu'il vaut tout de même 1.
\end{attention}

Chaque routeur de la topologie se représente donc en interne le graphe suivant :

\Par

\begin{figure}
\begin{center}
\includegraphics{292_08-graphe-ospf-2}
\figcaption{Graphe représenté par chaque routeur}
\end{center}
\end{figure}

\Par

Le protocole OSPF impose à un routeur d'utiliser le chemin dont le coût total est le plus faible pour router les paquets vers son destinataire.

En pratique, l'équipement utilise généralement l'algorithme de Dijkstra pour déterminer ce chemin optimal et en déduire le routeur voisin auquel il doit transmettre un paquet de donnée à router.

OSPF est donc bien plus performant que RIP mais plus complexe d'utilisation et typiquement destiné aux très gros réseaux. Voici quelques-uns des avantages de ce protocole:

\begin{itemize}
\item il n'a pas de limite du nombre de sauts comme le protocole RIP;
\item il permet à chaque routeur une connaissance complète des réseaux au sein d'une zone;

\item il élimine le danger des boucles de routage;

\item les mises à jour sont envoyées uniquement lors d'un changement de topologie, ce qui permet une économie de bande passante;

\item il permet la répartition de charge car le choix du meilleur chemin est basé sur le coût (la bande passante inversée) qui évolue au cours du temps.
\end{itemize}

D'autres avantages existent mais leur complexité technique les exclut du cadre de ce cours.
\newpage
\begin{aretenir}
\begin{center}
\includegraphics{293_RIP-OSPF}
\end{center}
\end{aretenir}

\section{Sécurité des échanges de données}

\begin{problematique}
De plus en plus de données circulent sur les réseaux. Aussi bien locaux (comme wifi ou ethernet) que distants. La sécurité des échanges d'informations constitue un enjeu essentiel dans le développement des réseaux et des applications connectées. Quelles sont les techniques de sécurité pour garantir qu'aucun utilisateur ne peut espionner les échanges entre deux interlocuteurs ?
\end{problematique}


\subsection{Principes de base du chiffrement}
\index{Chiffrement!Principes}

Dans un monde parfait où un intrus ne pourrait pas observer les communications entre deux interlocuteurs, le chiffrement serait inutile. Celui-ci n'a pas vocation à empêcher un espion d'observer les échanges d'informations mais à rendre les données transférées incompréhensibles à tout autre individu que leur destinataire légitime.

\begin{defins}
On appelle \textit{algorithme de chiffrement} une suite d'opérations destinées à chiffrer un message.

On appelle \textit{algorithme de déchiffrement} la suite d'opérations nécessaires pour déchiffrer le message crypté. 

Il arrive que ces deux algorithmes soient identiques.
\end{defins}

\subsubsection{Chiffrement à algorithme secret: exemple ROT13 (ROTate by 13 places)}
\index{Chiffrement!ROT13}

L'algorithme de chiffrement ROT13 consiste à décaler chaque lettre d'un message textuel de 13 positions dans l'alphabet, considéré circulaire (la lettre Z est suivie par A, puis B,...).

\Par

Considérons deux interlocuteurs Alice (A), Bernard (B) et un espion Ève (E) qui peut lire les transmissions entre (A) et (B). Alice souhaite transmettre un message confidentiel (M) à Bernard. Elle utilise l'algorithme ROT13 pour chiffrer son message avant envoi et ne transmet à Bernard que la version cryptée (C) du message:
\begin{itemize}
\item Alice encode son message: 
\begin{center}
M = \og danger imminent \fg devient C = \og qnatre vzzvarag \fg;
\end{center}
\item Elle envoie (C) à Bernard;
\item Ève observe la communication et voit passer (C) mais ne sait pas comment le déchiffrer;
\item Bernard reçoit (C) et utilise l'algorithme de déchiffrement ROT13 pour\linebreak reconstruire (M) et le lire.
\end{itemize}

\begin{attention}
\begin{itemize}
\item La sécurité repose ici sur le secret de l'algorithme utilisé. Ève ne peut pas déchiffrer le message car elle ignore qu'Alice et Bernard utilisent l'algorithme ROT13. 
\item Préalablement à cet échange, Alice et Bernard doivent avoir convenu d'utiliser l'algorithme ROT13 pour communiquer entre eux et Ève ne doit pas avoir eu écho de cette information.
\end{itemize}
\end{attention}
\enlargethispage*{\baselineskip}

Ce chiffrement extrêmement simpliste est quelquefois utilisé en informatique pour empêcher la lecture directe d'un texte mais ne constitue pas un moyen de sécurité fiable du fait de sa simplicité.

Le décalage de 13 positions dans l'alphabet qui comporte 26 ($=2\times13$) lettres permet d'utiliser le même algorithme pour le chiffrage et le déchiffrage du message car décaler un caractère vers la droite de 13 lettres deux fois consécutives redonne le caractère de départ. 


%\begin{anecdote}
%On attribue à Jules César l'invention du chiffrement par décalage, également appelé \og chiffre de César \fg. L'empereur romain utilisait quelquefois cette technique, en décalant les caractères de 3 positions vers la droite. Il communiquait ainsi avec ses armées sans qu'un ennemi ne puisse accéder facilement à l'information en cas d'interception du messager.
%\end{anecdote}

\subsubsection{Chiffrement à clé secrète}

Pour sécuriser davantage leurs échanges, Alice et Bernard peuvent convenir\linebreak d'utiliser une table aléatoire de traduction secrète de l'alphabet, qu'ils seront les seuls à détenir, comme dans l'exemple page ci-contre.



\begin{tabular}{|L|*{13}{Zc|}}
\hline
Lettre en clair: & A &B& C& D& E& F& G& H& I& J& K& L& M\\\hline
Lettre chiffrée:&S& E& T& R& O& G& Q& B& P& I& F& L& W\\\hline
\end{tabular}

\Par

\begin{tabular}{|L|*{13}{Zc|}}
\hline
Lettre en clair: &  N& O& P& Q& R& S& T& U& V& W& X& Y& Z\\\hline
Lettre chiffrée:& H& X& C& Y& Z& V& U& J& A& K& N& D& M\\\hline
\end{tabular}

\Par

La chronologie de l'échange est identique à la précédente:

\begin{itemize}
\item Alice encode son message:
\begin{center}
M = \og danger imminent \fg en C = \og rshqoz pwwphohu \fg;
\end{center}
\item Elle envoie (C) à Bernard;
\item Ève observe la communication et voit passer (C) mais ne peut pas le déchiffrer;
\item Bernard reçoit (C) et le déchiffre avec la table de correspondances.
\end{itemize}

Dans ce cas, la sécurité ne repose plus sur l'algorithme de chiffrement utilisé mais sur la table de correspondances secrète. Alice et Bernard peuvent déclarer ouvertement qu'ils communiquent à l'aide d'un algorithme de substitution et d'une table de correspondances (sans donner cette table évidemment). Ève pourra bâtir un algorithme de substitution mais il sera inefficace tant qu'elle n'utilisera pas la bonne table de correspondances.

\begin{defin}[clé de chiffrement]
On appelle \textit{clé de chiffrement} un paramètre utilisé dans un algorithme pour effectuer le travail de chiffrement/déchiffrement et qui conditionne le résultat obtenu.
\end{defin}

Ici, la clé de chiffrement est la suite des 26 lettres de l'alphabet en version chiffrée:
\begin{center}
Clé = SETROGQBPIFLWHXCYZVUJAKNDM
\end{center}

Tout espion disposant de cette clé est en mesure de déchiffrer la communication entre Alice et Bernard ainsi que de chiffrer des messages en se faisant passer pour Alice ou Bernard.

\begin{attention}
\begin{itemize}
\item La sécurité repose ici sur le secret de la clé utilisée. Ève ne peut pas déchiffrer le message car elle ignore cette clé, bien qu'elle sache qu'Alice et Bernard utilisent un algorithme de substitution.
\item Préalablement à cet échange, Alice et Bernard doivent avoir convenus d'une clé secrète et Ève ne doit pas avoir écho de cette information.
\end{itemize}
\end{attention}


\subsubsection{Attaque et déchiffrement par un espion}
\enlargethispage*{3em}
Bien que ne possédant pas la clé de chiffrement, Ève peut chercher à décoder le message chiffré. 

\begin{itemize}
\item La technique la plus rudimentaire consiste à essayer toutes les clés possibles. Sachant qu'Alice et Bernard utilisent un algorithme de substitution, Ève comprend que la clé est une anagramme des 26 lettres de l'alphabet. 

Ses souvenirs de mathématiques lui permettent de dénombrer les clés possibles: la factorielle du nombre de lettres. Or la factorielle de 26 (notée $26!$) représente environ $4 \times 10^{26}$ combinaisons.

En supposant qu'il faut 1 ms à un ordinateur pour tester une des clés possibles, le déchiffrement ne sera garanti qu'après: $4\times10^{26}\times 1\text{ ms} = 4 \times 10^{23}$ secondes soit environ $1,3 \times 10^{16}$ années, c'est-à-dire 13 millions de milliard d'années. De toute évidence, ce n'est pas du tout la bonne technique.

\item Ève utilisera plutôt une autre technique comme l'analyse fréquentielle qui\linebreak consiste à repérer les répétitions des caractères et à examiner la fréquence d'apparition des lettres chiffrées.

Dans chaque langue écrite, il existe une fréquence moyenne à laquelle une lettre est susceptible d'apparaître, comme le \og e \fg qui, en français, est la lettre la plus utilisée. On repère ainsi quelle est la lettre cryptée représentatives du \og e \fg et on fait de même avec les autres lettres.

La performance de cette technique augmente avec le nombre et la taille des messages cryptés analysés. Plus l'échantillon est important, plus l'analyse des répétitions donnera des résultats probants. 
\end{itemize}

Concrètement, l'algorithme de chiffrement par substitution n'est plus utilisé aujourd'hui car les techniques d'analyses fréquentielles sont très affinées et permettent de retrouver rapidement la clé.

\subsection{Familles de chiffrements par clés}

Il existe beaucoup d'algorithmes de chiffrement et de nouveaux algorithmes sont régulièrement inventés. Les plus pertinents sont ceux basés sur le secret de la clé utilisée (algorithme à clé secrète). Ils se répartissent en deux grandes familles.

\subsubsection{Le chiffrement symétrique}
\index{Chiffrement!symétrique}

\vspace*{-3mm}
\begin{defin}
Un chiffrement est dit \textit{symétrique} ou \og à clé symétrique \fg lorsque la clé utilisée pour chiffrer le message sert également à le déchiffrer.
\end{defin}

Attention à ne pas confondre \textit{clé symétrique} et \textit{algorithme symétrique}. Il n'est pas nécessaire, ici, d'utiliser le même algorithme pour chiffrer et déchiffrer le message (comme dans le cas du ROT13). 

Les algorithmes de chiffrement et déchiffrement peuvent être des programmes différents mais ils nécessitent la même clé secrète.
Les algorithmes de substitution, comme celui de l'exemple en amont, sont des algorithmes à clé symétrique.

\Par

L'utilisation d'un chiffrement à clé symétrique pose un problème fondamental: celui de l'échange de la clé. Si Alice veut envoyer un message crypté à Bernard, elle doit d'abord lui transmettre la clé qu'elle va utiliser. Mais comment la lui transmettre de manière sécurisée ?

\enlargethispage*{5em}
Ce problème est un grand classique: si Alice chiffre la clé, Bernard ne pourra pas la lire puisqu'il lui faut déjà avoir connaissance de la clé pour déchiffrer le message.

\begin{aretenir}
Un système de chiffrement symétrique nécessite un canal de communication déjà sécurisé pour transmettre la clé. Il n'est donc pas possible d'utiliser cette technique pour initialiser une communication entre deux nouveaux interlocuteurs.
\end{aretenir}

%\begin{anecdote}
%Le \og téléphone rouge \fg utilisé pendant la guerre froide entre le Kremlin et la Maison Blanche était crypté de manière symétrique à l'aide de clés secrètes jetables (après chaque communication la clé utilisée était jetée). Les clés étaient échangées entre les ambassades soviétiques et américaines par le biais des valises diplomatiques qui faisaient office de canal sécurisé.
%\end{anecdote}

\subsubsection{Le chiffrement asymétrique}
\index{Chiffrement!asymétrique}

Inventé vers 1976, le \textit{chiffrement asymétrique} ou \og chiffrement à clé publique \fg repose sur l'utilisation d'une clé composée des deux parties:
\begin{itemize}
\item une partie privée (dite \textit{clé privée} et généralement notée $s$ pour  \og secret \fg), conservée par le titulaire de la clé et qui n'est jamais communiquée;
\item une partie publique (dite \textit{clé publique} et généralement notée $p$ pour  \og public \fg) qui peut être connue de tous, y compris des espions. 
\end{itemize}

Tout message crypté avec une partie de la clé ($s$ ou $p$) ne peut être décrypté qu'avec l'autre partie de la même clé (respectivement $p$ ou $s$).

Avec cette technologie, Alice et Bernard communiquent de la manière suivante:
\begin{itemize}
\item ils génèrent chacun une clé asymétrique dont ils conservent la clé privée ($s$) et échangent ouvertement leur clé publique;
\item Ève voit passer les clés publiques et peut les utiliser;
\item Alice écrit un message (M) et utilise la clé publique de Bernard pour le chiffrer en C = $p$(M);
\item elle transmet ouvertement (C);
\item Ève intercepte (C) mais ne peut rien en faire sans la clé privée de Bernard;
\item Bernard reçoit (C) et le déchiffre avec sa clé privée pour restituer M = $s$(C);
\item Bernard répond à Alice avec un nouveau message qu'il chiffre en utilisant la clé publique d'Alice;
\item seule Alice, à son tour, peut déchiffrer le message émis par Bernard en utilisant sa clé privée.
\end{itemize}

\Par

Mathématiquement, le chiffrement asymétrique est basé sur l'utilisation de fonctions à sens unique possédant une brèche secrète:

\Par

\begin{itemize}
\item une fonction à sens unique est une fonction mathématique $f$ dont la réciproque $f^{-1}$ est très difficile à trouver (nécessite des milliers d'années de calcul);
\item une brèche secrète est une donnée liée à une fonction à sens unique $f$ dont la connaissance permet de trouver très facilement la fonction réciproque $f^{-1}$.
\end{itemize}

En cryptographie asymétrique, la fonction à sens unique constitue la clé publique et sa brèche secrète la clé privée. La mise en pratique la plus connue de cette mécanique est le chiffrement RSA.

Le chiffrement asymétrique est hélas plus consommateur de temps de calcul (complexité de mise en \oe uvre) que le chiffrement symétrique et nécessite des clés de plus en plus longues pour garantir la sécurité.

\enlargethispage*{5em}
En pratique, on l'utilise au début d'une communication pour constituer un canal sécurisé servant à échanger une nouvelle clé secrète symétrique. Une fois la clé symétrique en possession des seuls interlocuteurs légitimes, c'est elle qui est utilisée pour le chiffrement de la communication.

\Par

\textit{Voir exercices \ref{exo:08-ROT13} et \ref{exo:08-XOR} page \pageref{exo:08-ROT13}.}

\newpage
\subsection{Utilisation sur le web}

Le chiffrement est très largement utilisé dans les communications internet. Les sites dits sécurisés (HTTPS) mettent en \oe uvre le protocole TLS qui impose:

\Par

\begin{itemize}
\item le chiffrement asymétrique RSA pour la création et l'échange d'une clé symétrique secrète;
\item le chiffrement symétrique AES, avec la clé échangée, sur l'ensemble de la session de communication.
\end{itemize}

\begin{figure}
\begin{center}
\includegraphics{298_08-https}
\figcaption{Utilisation des chiffrements symétrique et asymétrique sur le web}
\end{center}
\end{figure}

\subsection{Authentification d'un message}
\enlargethispage*{3em}
En plus d'être idéale pour l'établissement d'une communication, le chiffrement asymétrique permet aussi de signer et d'authentifier un message. Il apporte alors la garantie que le message a bien été écrit par son auteur et n'a pas été altéré au cours de la communication.

Pour ce faire, on utilise un outil mathématique supplémentaire appelé \textit{fonction de hachage} (aussi nommé CRC pour \textit{Cyclic Redundancy Check}). Il s'agit d'une fonction calculable cycliquement sur un message aussi long que nécessaire pour produire un résultat très court nommé aussi \textit{condensat}. 

Le CRC, ou condensat, ne permet pas du tout de reconstruire le message car plusieurs messages très différents pourraient avoir le même CRC. 

\Par

Soient un message M et son CRC calculé par une fonction de hachage $f$ (le CRC est généralement un entier sur 32 ou 64 bits, indépendamment de la longueur du message). $f$ est conçue de manière à ce qu'une petite altération de M en M' provoque une image par $f$ très différente: $f$(M') sera très éloigné de $f$(M).

La transmission d'un message authentifié se fait généralement de la manière\linebreak suivante:

\Par

\begin{figure}
\begin{center}
\includegraphics{299_08-authentification}
\figcaption{Transmission d'un message authentifié}
\end{center}
\end{figure}

\Par

Si le CRC reçu est identique au CRC calculé alors Bernard a les garanties:
\begin{itemize}
\item que c'est bien la clé privée d'Alice qui a chiffré le CRC (puisque la clé publique d'Alice a permis de le déchiffrer);
\item que le CRC a bien été calculé sur ce message exactement (sinon Bernard aurait obtenu un CRC différent).
\end{itemize}
\enlargethispage*{\baselineskip}

Il peut en déduire que le message est authentique, c'est-à-dire qu'il n'a pas été usurpé, ni modifié, ni rédigé à l'insu d'Alice puisqu'elle est la seule à pouvoir utiliser sa clé privée pour chiffrer le condensat.

%\newpage

%\begin{aretenir}
%\begin{itemize}
%\item La sécurité d'un chiffrement par algorithme secret repose sur la confidentialité de l'algorithme utilisé. Il ne doit être connu que des interlocuteurs légitimes. Un espion ne doit pas pouvoir le deviner facilement.
%\item Le chiffrement par clé secrète repose sur la confidentialité d'une clé mais l'algorithme de chiffrement/déchiffrement n'est pas nécessairement secret.
%\item Les techniques de chiffrement symétrique nécessitent l'utilisation d'un canal sécurisé pour transmettre la clé secrète.
%\item Le chiffrement asymétrique permet d'établir un canal sécurisé pour échanger une clé symétrique. Il permet aussi de signer et d'authentifier un message.
%\item Le protocole internet HTTPS utilise le chiffrement asymétrique (RSA) à l'ouverture d'une session pour convenir d'une clé symétrique jetable de session (AES).
%\end{itemize}
%\end{aretenir}