\section{Introduction}

\subsection{Présentation du cours ASR2}

\begin{itemize}
\item On se concentre sur le S et R de ASR
\item Prérequis : C et dans une moindre mesure ASR1.
\item Organisation: TP/TD le mercredi à 8h en salle Europe (001), cours le jeudi à 10h.
\item Projet(s) avec rendus intermédiaires (1/3 de la note)
\item Examen final (2/3 de la note). Peut-être en salle machine, si les contraintes le permettent.
\item Questions, suggestions, bugs : \texttt{michael.rao@ens-lyon.fr}
\end{itemize}

\subsection{Références}

Livres:
\begin{itemize}
\item Jean-Marie Rifflet et Jean-Baptiste Yunès, \og UNIX : programmation et communication \fg, Dunod, 2003.
\item Andrew S. Tanenbaum et Herbert Bos, \og Modern Operating Systems, 4th Ed \fg, Pearson 2015.
\item Et beaucoup d'autres...
\end{itemize}

Les pages du manuel (RTFM !)
\begin{itemize}
\item Pour avoir le manuel d'une commande, fonction... : \cmd{man <terme>} dans un terminal
\item Attention : il y a plusieurs sections dans les pages man. Regardez dans la page manuel de man : \cmd{man man}
\item Certains termes ont des entrées dans plusieurs sections.
\item Pour accéder une section particulière : \cmd{man <section> <terme>}
\item Pour si on ne sait pas : \cmd{man -a <terme>}
\end{itemize}

\subsection{Buts du cours}

\begin{itemize}
\item Comprendre ce qui se passe entre la machine (le matériel, la partie A de ASR) et un processus (que vous allez programmer dans la vraie vie). Dans cette superposition de couches, le système d'exploitation (OS = Operating System) joue un rôle important. 
\end{itemize}

Couches : Matériel / OS / (librairies) / Processus

\begin{itemize}
\item Comprendre comment coopèrent les différents processus.
 Une chose importante est synchronisation et la communication inter-processus: au sein d'une même machine ou entre différentes machines (notamment la communication réseau).
\end{itemize}

\begin{itemize}
\item On n'abordera pas directement les algorithmes utilisés dans la conception OS.
 Le but ici n'est pas de vous apprendre à programmer un OS, mais de savoir opérer avec lui. Néanmoins, certaines problématiques seront abordés indirectement.
\end{itemize}

\begin{itemize}
\item Tous les exemples/exercices se feront sous GNU/Linux, et on programmera en C. La plupart des choses montrées respectent la norme POSIX, et donc fonctionnent de manière très similaire sous les autres systèmes respectant cette norme (autres Unix, OSX, ~Windows...).
\end{itemize}



\subsection{Un OS: pourquoi ?}

Que fait un système d'exploitation ?
\begin{itemize}
\item interface avec le matériel
\item gestion de la mémoire
\item gestion des périphériques 
\item gestion des interruptions
\item gestion des système de fichiers 
\item ...
\end{itemize}

Ces taches sont très dépendantes du matériel, et souvent fastidieuses. L'OS est là pour nous simplifier la vie.

\subsection{Que fait un système d'exploitation \og moderne \fg ?}

\begin{itemize}
\item multi-tâches : plusieurs processus peuvent tourner en même temps
\item multi-utilisateurs : il peut y avoir plusieurs utilisateurs différents qui l'utilisent.
\item gestion utilisateurs, groupes d'utilisateurs, et droits.
\item il y a souvent un utilisateur particulier, le super-utilisateur (root, administrateur) qui a tous les droits.
\item gestion du réseau
\end{itemize}

\bigskip

\begin{itemize}
\item essayer d'être "compatible" avec les autres OS: respect de normes.
\end{itemize}

\bigskip
\begin{itemize}
\item les interfaces graphiques sont généralement des sur-couche (e.g.: X).
 Les environnements graphiques sont encore des sur-sur-couches (gnome, kde, ... ). On passe par des API plus haut niveau pour interagir avec eux. (Ce n'est pas le but du cours.)
\end{itemize}


\subsection{Systèmes "Unix"}

Introduction d'Unix (1969-, K. Thompson \&  D. Ritchie...)
\begin{itemize}
\item Rompt avec les OS propriétaires, et les programmes monolithiques.
\item Introduit conjointement avec le C (1969-, D. Ritchie \& B. Kernighan)
\end{itemize}
C $\sim$ assembleur universel.
\begin{itemize}
\item Rapidement, plusieurs branches de développement:

 Unix, BSD, et système propriétaires (Xenis, AIX, System V...) 
\item Assez rapidement, une volonté de normalisation:

 norme POSIX (1988-)
\item Philosophie : être \sur{modulaire}. Préférer des programmes simples qu'on peut composer via les entrées/sorties standards.
\end{itemize}


\subsection{GNU / Linux}

\begin{itemize}
\item GNU : "GNU is Not Unix" : projet d'OS libre (1983- R. Stallman)
\end{itemize}

\begin{itemize}
\item Logiciel libre: code source disponible, que l'on peut modifier et redistribuer (licence GPL "GNU Public Licence", ou similaire) 
\end{itemize}

\begin{itemize}
\item Linux: Un noyau (c\oe{}ur de l'OS) Unix libre.
 Initié par Linus Torvalds, inspiré de Minix 
\end{itemize}

\begin{itemize}
\item Autres Unix libres: Minix, BSD*, Hurd...
\end{itemize}

\subsection{Écosystème...}

Un "écosystème" vivant dans un ordinateur c'est un ensemble de programmes en exécution (les \imp{processus}), utilisant les mémoires pour lire les données à traiter, pour stocker des résultats intermédiaires de calcul, et pour écrire les résultats finaux. Ces processus peuvent éventuellement interagir entre eux, ou utiliser des périphériques pour interagir avec le monde extérieur (clavier, écran, souris...). 

\medskip

Les processus n'interagissent pas directement avec le matériel, ils passent par l'OS pour y avoir accès.


\subsection{Mémoires}

Deux types importantes de mémoire:

\begin{itemize}
\item la mémoire vive, "volatile"
\begin{itemize}
\item non pérenne
\item accès très rapide.
 il y a différent niveaux, qui sont plus ou moins accessibles : registres, caches du processeur, mémoire RAM (les "barrettes", ex: DDR3)
\end{itemize}
\item la mémoire "non volatile"
\begin{itemize}
\item pérenne
\item disque dur mécanique, SSD, clef USB...
\item accès (beaucoup) plus lent
\end{itemize}
\end{itemize}


La mémoire non volatile est organisée sous forme arborescente, avec des fichiers et des répertoires : l'\imp{arborescence des fichiers}.


\section{Arborescence de fichiers et Shell}

\subsection{Shell}
  
\imp{Shell}: interface textuelle entre l'humain et l'OS.

Votre premier objectif : maîtriser le shell

\bigskip

Fonctionnement d'un shell
\begin{itemize}
\item prompt: attente d'une commande
\end{itemize}
\cmd{commande [argument1] [argument2] ...}
\begin{itemize}
\item on entre une commande, éventuellement avec arguments, et on appuie sur ``entrée''.
\item le shell exécute la commande, puis rend la main quand la commande est terminée.
\item pour quitter "proprement" un shell: \cmd{exit} (ou ctrl+d sur certains shells).
\end{itemize}


Note: si on veut un argument avec des espaces, le mettre entre guillemets " " ou ' ' 


\subsection{Shell / terminal}

Un shell se lance au travers d'un \imp{terminal}.
Sous un environnement graphique, on lance un shell généralement en lançant un "terminal" ou "console". Il y a donc souvent confusion entre shell et terminal.

\bigskip

Il existe plusieurs shells différents. Un des plus courant sous GNU/Linux est \cmd{bash}.
Les shells récents ont des fonctionnalités qui simplifient la vie: historique, édition, auto-completion (avec tabulation). Ils ont aussi des fonctionnalité de scripts plus poussés.

\bigskip

Permet de composer facilement des processus via les redirections d'entrée/sorties.

\bigskip

On peut faire des \imp{scripts} en shell.
Une suite de commandes, avec des tests, branchements, etc. Il s'agit donc d'une langage de programmation (interprété) en lui même.


\subsection{L'arborescence des fichiers}

Les fichiers sont organisés sous forme arborescente.


\begin{itemize}
\item La racine : \cmd{/}
\item Deux principaux types de fichiers:
\begin{itemize}
\item les fichiers standards = \imp{fichiers réguliers}
\item les répertoires (ou dossiers).
\item (Il en existe d'autres : liens, fifo... à suivre)
\end{itemize}
\item Chaque fichier possède:
\begin{itemize}
\item un propriétaire et un groupe propriétaire
\item un ensemble de droits (lecture/écriture/exécution) pour l'utilisateur, le groupe, et le reste du monde.
\item une date de création, de modification, de lecture.
\end{itemize}
\item Fichiers commençant par un point : fichiers cachés.
\end{itemize}



Un fichier \og standard \fg~ est une chaînes d'octets.
\begin{itemize}
\item un octet = 8bits (un entier entre 0 et 255)
\item il a une taille: le nombre d'octets
\item cela peut être un programme exécutable (en langage machine), un fichier texte (un code source...), un fichier multimédia...
\end{itemize}

Répertoires spéciaux:
\begin{itemize}
\item \cmd{..} : répertoire parent
\item \cmd{.} : répertoire courant
\end{itemize}


\bigskip

Chemin de la racine à un fichier : \imp{chemin absolu}

\begin{itemize}
\item \cmd{/home/mrao/Documents/cours.pdf}
\end{itemize}

Chemin du répertoire courant à un fichier : \imp{chemin relatif}

\begin{itemize}
\item \cmd{Documents/cours.pdf}

 = \cmd{./Documents/cours.pdf}
\end{itemize}


\subsection{Organisation typique sous Unix/Linux}

\begin{itemize}
\item /home : les répertoires des utilisateurs
\item /root : le répertoire "home" du super-utilisateur
\item /bin et /usr/bin les programmes (les "binaires");
\item /sbin et /usr/sbin : les binaires système 
\item /lib et /usr/lib : librairies 
\item /usr : ressources système 
\item /etc : fichiers de configurations
\item /dev : fichiers spéciaux (ressources, périphériques)
\item /tmp : un répertoire pour les fichiers temporaires
\item /var : données variables 
\item ...
\end{itemize}

\subsection{Les shell: premiers pas...}

Le shell permet de naviguer dans l'arborescence de fichiers, modifier les droits, faire des opérations simples.

\begin{itemize}
\item \cmd{ls} : liste les fichiers
\begin{itemize}
\item option \cmd{-a} : affiche également les fichiers cachés 
\item option \cmd{-l} : format long (droits, taille, propriétaire...)
\end{itemize}
\item \cmd{cd \textit{rep}} : entrer dans le répertoire \textit{rep}
\begin{itemize}
\item \cmd{cd ..} : retour au répertoire parent 
\end{itemize}
\end{itemize}

\subsection{Autres commandes de base}


\begin{itemize}
\item s : liste les fichiers
\begin{itemize}
\item  options:
\item   -a : affiche les fichiers cachés
\item   -l : affiche les informations complètes: propriétaire, taille, droits...
\item   -R : liste récursive
\end{itemize}
\end{itemize}

\begin{itemize}
\item cat <fichier> : affiche le contenu d'un fichier.
\end{itemize}

\begin{itemize}
\item touch <fichier> : crée un fichier (vide) si il n'existe pas, sinon il met sa date de modification à jour.
\item rm <fichier> : efface un fichier (ATTENTION: irréversible!)
\item cp <fichierA> <fichierB> : copie le fichierA vers le fichierB
\begin{itemize}
\item  l'option -R ou -a permet de copier récursivement (pour les répertoires)
\end{itemize}
\item mv <fichierA> <fichierB> : déplace/renomme le fichierA vers le fichierB
\item ln : créer un lien
\end{itemize}

\begin{itemize}
\item cd <répertoire>: changer de répertoire
\item pwd : affiche le répertoire courant
\item mkdir <répertoire> : crée un répertoire
\item rmdir <répertoire> : efface un répertoire. attention, il doit être vide.
\begin{itemize}
\item  pour effacer un répertoire non vide (ATTENTION: irréversible!) : rm -rf <rep>
\end{itemize}
\end{itemize}

\begin{itemize}
\item chmod <droits> <fichiers> : change les droits d'un fichier 
\item chown <user> <fichier> : change le propriétaire de fichier 
\item chgrp <groupe> <fichier> : change le groupe propriétaire
\end{itemize}

\subsection{Un peu plus sur les droits des fichiers }

\begin{lstlisting}[language=bash,basicstyle=\tiny]
 mrao@meshuggah:~/test$ ls -la
 total 32
 drwxr-xr-x  4 mrao users 4096 dec.  29 22:40 .
 drwx------ 61 mrao users 4096 janv.  9 17:25 ..
 -rwxr-xr-x  1 mrao users 6656 dec.  29 13:37 programme
 -rw-r--r--  1 mrao users  173 dec.  29 13:37 programme.c
 drwxr-xr-x  2 mrao users 4096 dec.  29 13:39 sousrep
 mrao@meshuggah:~/test$ 
\end{lstlisting}

premier champ: un sous ensemble de drwxrwxrwx

\begin{itemize}
\item d: répertoire
\item 1er triplet (rwx) : droits pour l'utilisateur (ici, mrao)
\item 2eme triplet : droits pour les utilisateurs du groupe (users)
\item 3eme triplet : droits pour le reste du monde
\item r: droit de lecture
\item w: droit d'écriture
\item x: droit d'exécution (pour les répertoires: droit d'entrer)
\end{itemize}

Pour changer les droits: \cmd{chmod}


\cmd{chmod <droits> <fichier>} : 

\medskip

où droits = <qui><+-><permissions>

\begin{itemize}
\item qui : sous ensemble de u (user) g (group) o (others) a (all)
\item + ajoute les permissions, - enlève.
\item permissions : sous ensemble de
\begin{itemize}
\item r (read)
\item w (write)
\item x (execute)
\item X (execute, pour les répertoires)
\end{itemize}
\item option \cmd{-R} : le faire de façon récursive
\end{itemize}

\subsection{Un peu plus sur les droits : en octal}

Les droits sont parfois représentés par un nombre de 3 chiffres, de 0 à 7 (en octal, 3 bits par caractères)

\smallskip

1er chiffre : droits pour l'utilisateur,
2eme chiffre : droits pour le groupe,
3eme chiffre : droits pour reste du monde.

\smallskip

Chaque chiffre est une somme:
\begin{itemize}
\item 4 pour le droit de lecture,
\item 2 pour le droit d'écriture,
\item 1 pour le droit d'exécution.
\end{itemize}

4eme chiffre : modes spéciaux



\begin{verbatim}
mrao@meshuggah:~/test$ ls -l
total 0
\begin{itemize}
\item w-r--r-- 1 mrao mrao 0 dec.  29 15:23 fichier
\end{itemize}
mrao@meshuggah:~/test/test2$ chmod 762 fichier
mrao@meshuggah:~/test/test2$ ls -l
total 0
\begin{itemize}
\item wxrw--w- 1 mrao mrao 0 dec.  29 15:23 fichier
\end{itemize}
\end{verbatim}
  


Modes spéciaux:
\begin{itemize}
\item \imp{set-uid}:
\begin{itemize}
\item \cmd{s} dans \cmd{chmod} et \cmd{ls -l} (dans le groupe "user")
\item en octal : 04000
\item pour les exécutable
\item lors de l'exécution, prend l'uid du propriétaire du fichier
\item utile pour les programmes systèmes. Par exemple: \cmd{passwd} doit pouvoir modifier des fichiers systèmes, qu'un utilisateur ne doit pas pouvoir modifier en temps normal.
\end{itemize}
\item \imp{set-gid}:
\begin{itemize}
\item en octal : 02000
\item pour les exécutable
\item \cmd{s} dans \cmd{chmod} et \cmd{ls -l} (dans le groupe "group")
\item lors de l'exécution, prend le gid du propriétaire du fichier
\end{itemize}
\item \imp{sticky-bit}:
\begin{itemize}
\item en octal : 01000
\item pour les exécutable
\item \cmd{t} dans \cmd{chmod} et \cmd{ls -l}
\item empêche que quelqu'un puisse effacer le fichier d'un autre
\item utile pour \cmd{/tmp/} 
\end{itemize}
\end{itemize}


\subsection{Liens }

Unix supporte des \imp{liens}. Il y a deux types de liens, fondamentalement différents.

\begin{itemize}
\item \imp{Lien symbolique}: un "pointeur" vers un autre fichier.

 Il s'agit d'un type de fichier spécial.

 Commande shell: \cmd{ln -s}. Appel système: \cmd{symlink}
\end{itemize}

\bigskip

\begin{itemize}
\item \imp{Lien physique} : fichier correspondant à la même zone sur le disque qu'un autre.

 Commandes shell: \cmd{ln}, \cmd{link}. Appel système: \cmd{link}
\end{itemize}

Plus de précisions sur les liens physiques:

Un "i-node" est un objet sur le disque qui donne les informations sur un fichier (type, propriétaire, droits, dates, et pointeur vers les données), mais pas le nom.

Un fichier régulier dans l'arborescence est en fait un lien physique vers un "i-node"
Quand on crée un lien physique, on crée un autre lien vers le même i-node
Un i-node est physiquement effacé du disque quand plus aucun lien physique (et aucun descripteur de fichier) ne pointe vers lui.

Le deuxième champ de \cmd{ls -l} est le nombre de lien physique vers l'i-noeud pointé par le fichier.
Pour voir les informations d'un i-node : \cmd{stat \textit{fichier}}

\subsection{Autres fichiers spéciaux}

\begin{itemize}
\item Fichier \imp{périphérique} (\imp{device file}).

 Correspond à un périphérique

 Généralement situé dans \cmd{/dev/}
 Deux types: caractères et bloc
\end{itemize}

\bigskip

\begin{itemize}
\item Fichiers \imp{tubes} (ou \imp{fifo}).

 Pour créer un fichiers tube : \cmd{mkfifo}

 (On reparlera de tubes au moment de la communication inter-processus.)
\end{itemize}


\subsection{Un peu plus sur les système de fichiers}

\begin{itemize}
\item L'arborescence des fichiers est un "patchwork" de systèmes de fichiers.
\item Un système de fichier correspond généralement à une partition sur un disque sur.
\item Il existe plusieurs types de système de fichier: FAT et dérivées (de Microsoft DOS/vieux Windows), NTFS (Windows NT et après), EXT2 et supérieurs (Linux)...
\item Ce qui change: l'encodage des droits, la journalisation, le versionage 
\item Il existe des systèmes de fichiers qui ne correspondent pas à des partitions physiques : certains systèmes générés par l'OS, des systèmes de fichiers réseau...
\end{itemize}

\begin{itemize}
\item \cmd{mount} permet de voir tous les systèmes de fichiers montés, et de les monter
\item \cmd{df}: permet de voir l'utilisation des systèmes de fichiers
\end{itemize}



\subsection{Utilisateurs et groupes}

Chaque utilisateur a:
\begin{itemize}
\item un nom (une chaîne de caractère)
\item un numéro (UID = User IDentifier)
\item un ou plusieurs groupes
\item un répertoire HOME, généralement: \cmd{/home/<user>}
\item un mot de passe, stocké de façons hashée.
\end{itemize}

\cmd{root} est le ``super-utilisateur''. Il a tous les droits. Son UID est 0.
  
Les informations des utilisateurs sont stockées (généralement) dans /etc/passwd et /etc/shadows

\medskip

  Chaque groupe a un numéro (GID  = Group IDentifier).

\cmd{useradd/adduser}, \cmd{userdel/deluser} : gestion des utilisateurs (en root)

\cmd{passwd} : changement du mot de passe

\subsection{Les processus}

  Chaque processus a:
\begin{itemize}
\item un numéro (le PID = Process IDentifier)
\item un père, généralement le processus qui l'a lancé.
\item un utilisateur (généralement, celui qui l'a lancé)
\item une zone mémoire qui lui a été attribué. Il peut en demander plus au système. % (on y reviendra)
\item certains processus peuvent être en attente. % (ou autres états ``bizarres'').
\end{itemize}

\smallskip

\begin{itemize}
\item une \imp{entrée standard}, et une \imp{sortie standard} et une \imp{sortie erreur}.
\end{itemize}

\begin{itemize}
\item À sa fin, un processus renvoie un \imp{code retour} : un entier, généralement 0 s'il n'y a pas d'erreur, et $\ne$ 0 sinon.
\end{itemize}

\subsection{Lancer des commandes/processus dans un shell}


\begin{itemize}
\item Certaines commandes sont interprétés directement par le shell, les \imp{builtin} (comme \cmd{cd}). D'autres correspondent à des programmes exécutables (généralement situés dans \cmd{/bin/} ou \cmd{/usr/bin/}).
\item Le shell va chercher les programmes dans les répertoires listés dans la variable d'environnement PATH. (Pour voir les répertoires dans PATH: echo \$PATH)
\item S'il le trouve, il l'exécute (le processus se lance). Sinon il renvoie un message d'erreur.
\item Pour lancer un programme dans le répertoire courant
 (ou tout autre répertoire qui n'est pas dans PATH)
 il faut spécifier le répertoire avant le nom du programme. 
\end{itemize}


\begin{lstlisting}[language=bash,basicstyle=\tiny]
mrao@meshuggah:~/test$ ls -l
\begin{itemize}
\item wxr-xr-x 1 mrao mrao 6552 dec.  29 16:46 hello
\item w-r--r-- 1 mrao mrao   68 dec.  29 16:46 hello.c
\end{itemize}
mrao@meshuggah:~/test$ hello
bash: hello : commande introuvable
mrao@meshuggah:~/test$ ./hello
Hello
mrao@meshuggah:~/test$ echo $PATH
/usr/local/bin:/usr/bin:/bin:/usr/local/games:/usr/games
mrao@meshuggah:~/test$ PATH=$PATH:.
mrao@meshuggah:~/test$ echo $PATH
/usr/local/bin:/usr/bin:/bin:/usr/local/games:/usr/games:.
mrao@meshuggah:~/test$ hello
Hello
\end{lstlisting}

\subsection{Entrées/sorties standard}

Quand un processus s'exécute dans un terminal:

\begin{itemize}
\item l'entrée standard est (par défaut) l'entrée du terminal (le clavier)
\item la sortie standard est (par défaut) affichée dans le terminal.
\item la sortie erreur est (par défaut) affichée dans le terminal.
\end{itemize}

\medskip

Le shell permet de facilement rediriger ces entrées/sorties.

\subsection{Rediriger les E/S standards}

\begin{itemize}
\item \cmd{commande > ficher} : redirige la sortie standard de la commande vers le fichier (écrase le fichier)
\end{itemize}

\begin{itemize}
\item \cmd{commande >{}> fichier}  : redirige la sortie standard de la commande vers le fichier (rajoute à la fin du fichier)
\end{itemize}

\begin{itemize}
\item \cmd{commande 2> fichier} : redirige la sortie erreur de la commande vers le fichier
\end{itemize}

\begin{itemize}
\item \cmd{commande1 | commande2} : la sortie standard de commande1 sera regirigée vers l'entrée standard de commande2
\end{itemize}


\begin{itemize}
\item \cmd{tee \textit{fichier}}: copie entrée standard sur la copie standard et \textit{fichier}
\end{itemize}

\begin{itemize}
\item \cmd{commande < fichier} : l'entrée standard sera lue depuis le fichier
\end{itemize}

\begin{itemize}
\item \cmd{commande <{}< EOF} : le shell va lire l'entrée standard, jusqu'à ce qu'il lise EOF. Ce qui est lu sera envoyé dans l'entrée standard de commande.
\end{itemize}




\subsection{Quelques commandes utiles}

\begin{itemize}
\item \cmd{sleep x}; attend x seconde (utile pour les scirpts)
\end{itemize}

\begin{itemize}
\item \cmd{echo} : affiche les arguments
\end{itemize}

ex. : \cmd{echo hello      world}
affiche : \cmd{hello world}

\begin{itemize}
\item \cmd{less} : permet de se déplacer dans le texte
\end{itemize}

ex. : \cmd{ls -l /etc/ | less}

\begin{itemize}
\item \cmd{head/tail}: affiche le début/fin de l'entrée
\end{itemize}

\begin{itemize}
\item \cmd{sort} : trie les ligne
\end{itemize}

ex. : \cmd{cat /etc/passwd | sort}

\begin{itemize}
\item grep : afficher les lignes correspondant à un motif donné 
\end{itemize}

ex. : \cmd{cat /etc/passwd | grep mrao}

\begin{itemize}
\item \cmd{sed} : fait des recherches / remplacements 
\end{itemize}
 
\begin{itemize}
\item \cmd{awk} : un truc qui fait mieux que grep / sed, mais encore plus compliqué.
\end{itemize}

\subsection{Voir/gérer les processus:}

Commandes shell pour voir/gérer les processus:

\begin{itemize}
\item \cmd{ps} affiche la liste des processus

 exemple: \cmd{ps faux}
\end{itemize}

\begin{itemize}
\item \cmd{top} affiche la liste des processus dynamiquement
\item \cmd{kill \textit{pid}} : tue un processus de PID \textit{pid} (on en reparlera dans la partie "Signaux")
\end{itemize}

\subsection{Variables du shell}

\begin{itemize}
\item Le shell manipule des \imp{variables}.
\item Exemples: HOME, USER, PATH
\item Affecter une variable :
\begin{itemize}
\item \cmd{VARIABLE=affectation}
\end{itemize}
\item déréférencer une variable: la faire précéder par \$
\begin{itemize}
\item Ex: pour afficher une variable : \cmd{echo \$VARIABLE}
\end{itemize}
\item \cmd{set} : affiche toutes les variables
\end{itemize}

\bigskip

Certaines variables sont persistantes: les \imp{variables d'environnement}. Elles seront transmises aux fils

\begin{itemize}
\item \cmd{export} : exporte la variable (les rend persistantes)
\item \cmd{env} : affiche toutes les variables d'environnement.
\end{itemize}

En fait, chaque processus (et donc, en particulier, le shell) dispose de variables d'environnement;
\todo{export transforme une variable interne du shell en variable d'environnement}
On verra par la suite comment accéder et gérer ces variables en C.


\subsection{Variables spéciales du shell}

\begin{itemize}
\item \$? : code retour de la précédente commande
\item \$\$ : PID du shell
\item {\$! :  PID du dernier processus lancé en arrière plan}
\end{itemize}

\begin{itemize}
\item \~ : interprété par le shell comme le répertoire HOME
\item \~{}user : interprété par le shell comme le répertoire HOME de l'utilisateur user
\end{itemize}

\subsection{Jokers et echappements}

\begin{itemize}
\item \cmd{*} dans un nom de fichier: n'importe quelle chaîne de caractère 
\item \cmd{?} : exactement un caractère
\end{itemize}

\bigskip

Pour qu'un caractère spécial ne soit pas interprété par le shell

\begin{itemize}
\item \cmd{\textbackslash} : exemple \cmd{echo \textbackslash*}
\item \cmd{'} : exemple \cmd{echo '*'}
\item \cmd{"} : exemple \cmd{echo "*"}
\begin{itemize}
\item le shell interprète les \$ et certains \textbackslash dans des chaînes entre \cmd{"}
\end{itemize}
\end{itemize}

\medskip

Le caractère "espace" peut être aussi echappé, pour ne pas séparer les arguments


\subsection{Processus en arrière plan}

\begin{itemize}
\item \cmd{commande \&} lance un processus, mais le shell n'attend pas la fin du processus pour rendre la main.
\item ctrl + z : stoppe un processus
\end{itemize}

\begin{itemize}
\item \cmd{jobs} : liste les taches (\imp{jobs}) en cours d'exécution dans le shell
\item \cmd{bg} : passe une tache en arrière plan (similaire à \&)
\item \cmd{fg} : passe une tache en premier plan (le shell rend la main au job)
\item \cmd{\%i} : identifie le job numéro $i$ du shell.
\end{itemize}


\subsection{\cmd{nohup}}

\begin{itemize}
\item Si on termine un shell, tous ses jobs seront arrêtés.
 (Sauf si ils se sont détachées par eux même, à voir plus tard.)
\end{itemize}

\begin{itemize}
\item Pour qu'un processus survive à la mort de son père, on peut le lancer précédé de la commande \cmd{nohup}
\end{itemize}


\subsection{Scripts: enchaînement et composition des commandes }

\begin{itemize}
\item \cmd{\textit{commande1} ; \textit{commande2}} 

 ~ execute \cmd{commande1}, puis \cmd{commande2}
\end{itemize}

\begin{itemize}
\item \cmd{( \textit{listedecommandes} )} 

 ~ crée un groupement de commande
\end{itemize}

\begin{itemize}
\item \cmd{\textit{commande1} `\textit{commande2}`} 

 ~ la sortie de \cmd{commande2} est donnée en argument à \cmd{commande1}

 \medskip

 Sur certains shells, on peut également faire ceci :

 ~ \cmd{\textit{commande1} \$(\textit{commande2})}
\end{itemize}


\begin{itemize}
\item \cmd{\textit{commande1} \&\& \textit{commande2}} 

 execute \cmd{commande1}, puis \cmd{commande2} si \cmd{commande1} réussi (i.e. renvoie 0) 
\end{itemize}

\begin{itemize}
\item \cmd{\textit{commande1} || \textit{commande2}} 

 execute \cmd{commande1}, puis \cmd{commande2} si \cmd{commande1} échoue 
\end{itemize}

\begin{itemize}
\item \cmd{if \textit{condition} ; then \textit{commande2} ; else \textit{commande3} ;fi}
\end{itemize}

\cmd{true} : réussi toujours
\cmd{false} : échoue toujours

\subsection{Scripts: tests}

\cmd{test \textit{expression}} permet de tester une expression conditionnelle.

\medskip

Note : sur certains shells, c'est équivalent à \cmd{[ \textit{expression} ]}

\medskip

\textit{expression} construite avec \cmd{( ) \&\& || ! } et des expression élémentaires.

\medskip

Expression élémentaire (exemples):
\begin{itemize}
\item tester si un fichier existe : \cmd{ -e \textit{fichier}}
\item tester si un fichier est un répertoire : \cmd{ -d \textit{fichier}}
\item tester si un fichier est un fichier régulier : \cmd{ -f \textit{fichier}}
\item tester si un fichier est lisible : \cmd{ -r \textit{fichier}}
\item tester si deux chaînes de caractères sont égales: \cmd{\textit{chaine1} = \textit{chaine2}}
\item tester si expression numériques sont égales: \cmd{\textit{chaine1} -eq \textit{chaine2}}
\end{itemize}

\subsection{Scripts: évaluer une expression}

\cmd{expr \textit{expression}} permet d'evaluer une expression

\bigskip

\textit{expression} construite avec \cmd{( ) + - * / \% = >=} ... et des expressions élémentaires (entiers...)

\bigskip

Attention aux {echappements} : \cmd{expr \textbackslash( 2 + 3 \textbackslash) \textbackslash* 5}

\bigskip

Sous bash on peut utiliser directement \cmd{\$((\textit{expression}))}

\subsection{Scripts: boucles}

\cmd{while \textit{condition} ; do \textit{commandes} ; done}

\begin{itemize}
\item Ex: \cmd{while true ; do date ; sleep 1; done}
\end{itemize}

\bigskip

\cmd{for \textit{v} in \textit{liste}; do \textit{commandes} ; done}
\begin{itemize}
\item entre do et done, v est une variable   
\end{itemize}
\smallskip

\begin{itemize}
\item Ex: \cmd{for f in *wav; do lame \$f `basename \$f wav`mp3 ; done}
\end{itemize}

\begin{itemize}
\item \cmd{seq \textit{a b}} : tous les entiers entre a et b.
\end{itemize}

\bigskip

Voir également: \cmd{break}, \cmd{continue}, \cmd{until}, \cmd{case}

\subsection{Scripts : fichiers scripts }

\begin{lstlisting}[language=bash,basicstyle=\small]
 #!/bin/bash
 for i in "$*" ; do
   echo $i
 done
\end{lstlisting}

\begin{itemize}
\item \#! : \imp{shebang} : dit au système quel interpréteur utiliser
 note: ce n'est pas nécessairement un shell. Cela peut être un autre interpréteur de scripts, comme \cmd{perl}, \cmd{awk}, \cmd{python} ...
\item \$1 : 1er argument, \$2 : 2eme argument ...
\item \$* : tous les arguments 
\item \$\# : nombre d'arguments
\end{itemize}


Les scirpts shells, ce n'est pas trop le but du cours. Mais néanmoins, c'est un outil très puissant. On peut faire rapidement et facilement beaucoup d'opérations complexes. Exercez vous, regardez la page manuel du shell de \cmd{bash}, ou de tout autre shell que vous voulez utiliser.


\section{Programmation système en C: entrées sorties}

\subsection{Contexte}

\begin{itemize}
\item À partir de maintenant, on fait du C
\end{itemize}

\begin{itemize}
\item But de ce "chapitre":
\begin{itemize}
\item se familiariser avec les \imp{appels système}
\item se familiariser avec les \imp{descripteurs de fichiers}
\end{itemize}
\end{itemize}




\subsection{Les appels système}

\begin{itemize}
\item Un appel système: le processus appelle directement une fonction du noyau.
\end{itemize}

\begin{itemize}
\item En interne: cela se fait par un mécanisme spécial (interruption)
 On verra plus précisément le mécanisme dans la prochaine section.
\end{itemize}

\begin{itemize}
\item En pratique, ce sont des fonctions que l'on appelle

 (comme à l'accoutumé en C)
\end{itemize}

\begin{itemize}
\item (On verra rapidement, dans la section "Mémoire", comment se passe un appel système.)
\end{itemize}



\begin{itemize}
\item Attention : un appel système est plutôt lent !
\end{itemize}

\begin{itemize}
\item Pour voir les appels système d'un processus:

 \cmd{strace} ou \cmd{ltrace -S}
\end{itemize}



\subsection{Codes retour et erreurs }

\begin{itemize}
\item Les appels système renvoient un code retour
\end{itemize}

\begin{itemize}
\item \sur{Il faut toujours vérifier si cela a marché !}
\end{itemize}

\begin{itemize}
\item les codes erreurs sont généralement retournés dans la variable externe \cmd{errno}
\end{itemize}

\begin{itemize}
\item \cmd{perror} permet d'afficher de manière compréhensive une erreur système.
\end{itemize}

\begin{itemize}
\item regardez la page du manuel des la fonction que vous utilisez pour comprendre le code retour !
\end{itemize}
 
\subsection{Quelques rappels en C}

\begin{lstlisting}
#include <stdio.h> /* pour printf() */
int main(int argc, char **argv) 
{
  /* argc    : nombre d'argument dans la ligne de commande 
               (y compris l'executable)
     argv[i] : le ieme argument  */

  int i;
  printf("le nombre d'argument est %d\n",argc);
      /* affiche sur la sortie standard */
  for(i=0;i<argc;i++)
    printf(" l'argument %d est %s\n",i,argv[i]);

  return 0; /* code de retour */
}
\end{lstlisting}


En fait, \cmd{main} peut accepter un 3ème argument, qui sera l'ensemble des variables d'environnement

\begin{lstlisting}
int main(int argc, char **argv, char **env)
  int i;
  for(i=0;env[i]!=NULL;i++)
    printf("%d) %s\n",i,env[i]);
  return 0;
} 
\end{lstlisting}

Il y a d'autres façons de voir les variables d'environnement
\begin{itemize}
\item \cmd{extern char ** environ;}
\item \cmd{setenv}, \cmd{getenv}...
\end{itemize}


\subsection{}

\cmd{printf} est une fonction de la \imp{bibliothèque standard du C} (libc/glibc), une couche entre l'OS et nos programmes.
Il ne s'agit pas d'un appel système, mais elle va elle-même faire un appel système pour afficher le résultat via la sortie standard.


\begin{itemize}
\item Il y a deux niveaux de gestion des E/S et fichiers: bibliothèque standard ou par appel système. 
\end{itemize}
Exemple pour ouvrir un fichier: \cmd{fopen}) ou via les fonctions du système (pour ouvrir un fichier: \cmd{open}.

\begin{itemize}
\item \cmd{fprintf} utilise un appel système (\cmd{write}) pour afficher la chaîne de caractères 
\end{itemize}

  Ce sera le cas dans d'autres domaines que les E/S sur les fichiers (pour la mémoire, par exemple)
  Pour les fichiers, cela peut prêter à confusion, car les fonctions semblent faire la même chose.

  Pourquoi cette sur-couche ? La bibliothèque standard offre des moyens indépendant du système (par exemple, C doit pouvoir compiler sur des système non POSIX).

  Les fonctions de la bibliothèque standard sont aussi généralement plus commodes. \cmd{printf} n'a pas d'équivalent. La gestion mémoire est aussi plus facile via la bibliothèque standard (\cmd{malloc}/\cmd{free}). Mais elles sont moins proches du système, moins ``fines''.

\subsection{écriture dans un fichier en C via la bibliothèque standard}

\begin{lstlisting}
#include <stdio.h>
#include <assert.h>

int main() {
  FILE *out=fopen("hello.txt","w");
  assert(out!=NULL);
  fprintf(out,"hello ");
  /* ou */
  fwrite("world\n",1,6,out);
  fclose(out);
  return 0;
}
\end{lstlisting}

\subsection{écriture dans un fichier en C via des fonctions système}

\begin{lstlisting}
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <assert.h>

int main() {
  int out=open("hello.txt",O_WRONLY|O_CREAT,0644);
  assert(out!=-1);
  write(out,"hello world\n",12);
  close(out);
  return 0;
}
\end{lstlisting}


\subsection{Ouvrir un fichier}


\begin{lstlisting}
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <fcntl.h>
 int open(const char *pathname, int flags)
\end{lstlisting}

\begin{itemize}
\item ouvre le fichier au chemin \cmd{pathname}
\item renvoie un entier, le \sur{descripteur de fichier}
\item renvoie le plus petit descripteur de fichier libre
\item renvoie -1 si l'ouverture échoue (fichier non trouvé, pb de droits...) 
\item les autres fonction d'accès prennent en paramètre ce descripteur de fichier.
\item Pour fermer un descripteur: \cmd{close(descripteur)}.
\item Toujours fermer quand on s'en sert plus !
\end{itemize}


\begin{itemize}
\item \cmd{flags}: conjonction de: 
\begin{itemize}
\item O\_RDONLY, O\_WRONLY, ou O\_RDWR (lecture, écriture ou les 2)
\item O\_CREAT : crée le fichier (s'il n'existe pas)
\item O\_APPEND : rajoute à la fin du fichier (positionne à la fin du fichier)
\item O\_TRUNC : tronque le fichier à la taille 0.
\end{itemize}
\end{itemize}

\medskip

\begin{itemize}
\item \cmd{open} peut prendre un 3eme argument: le mode (droits "rwx" pour "ugo", \sur{en octal}) si un fichier est crée
\end{itemize}

\medskip

Exemple:
\cmd{int fd=open("file.txt",O\_WROLNY | O\_CREAT | O\_TRUNC, 0644);}


\subsection{Entrées/sorties standards}

Un processus possède à l'origine 3 descripteurs de fichiers ouverts :

\begin{itemize}
\item 0: ouvert en lecture: l'entrée standard
\end{itemize}

\begin{itemize}
\item 1: ouvert en écriture: la sortie standard
\end{itemize}

\begin{itemize}
\item 2: ouvert en écriture: la sortie erreur
\end{itemize}

\subsection{Lire dans un fichier}

\begin{lstlisting}
 #include <unistd.h>
 ssize_t read(int fd, void *buf, size_t count);
\end{lstlisting}

\begin{itemize}
\item \cmd{fd} : descripteur de fichier
\item \cmd{buf} : pointeur vers la zone mémoire où seront copiées les données
\item \cmd{count} : nombre maximum d'octets à lire
\item retour : nombre d'octets lus, -1 si erreur
\end{itemize}

\medskip

Similairement : \cmd{write} pour écrire

\subsection{Se déplacer dans un fichier}

\begin{lstlisting}
 #include <sys/types.h>
 #include <unistd.h>
 off_t lseek(int fd, off_t offset, int whence);
\end{lstlisting}

\begin{itemize}
\item \cmd{offset} : de combien d'octets on se déplace (positif ou négatif) depuis : 
\begin{itemize}
\item (si \cmd{whence=SEEK\_SET}) le début du fichier
\item (si \cmd{whence=SEEK\_CUR}) la position courante
\item (si \cmd{whence=SEEK\_END}) la fin du fichier
\end{itemize}
\item retour : position dans le fichier
\end{itemize}

\bigskip

(Pour connaître la taille d'un fichier \cmd{lseek(fd,0,SEEK\_END)})


\subsection{Dupliquer les descripteurs}
\begin{lstlisting}
 #include <unistd.h>
 int dup(int oldfd);
 int dup2(int oldfd, int newfd);
\end{lstlisting}

\begin{itemize}
\item \cmd{dup} duplique le descripteur \cmd{oldfd}, et renvoie un nouveau descripteur
\item \cmd{dup2} copie le descripteur \cmd{oldfd} dans \cmd{newfd}
\end{itemize}

\bigskip

Exemple:
\begin{lstlisting}[basicstyle=\small]
 int fd=open("sortie.txt",O_CREAT|O_WRONLY,0644);
 dup2(fd,1);
\end{lstlisting}
 
\subsection{Autres fonctions pour gérer les fichiers }

\begin{itemize}
\item pour tronquer un fichier à la position courante : \cmd{truncate}, \cmd{ftruncate}
\item pour créer un fichier : \cmd{open} ou \cmd{create}
\item pour supprimer un fichier : \cmd{unlink}
\item pour créer un lien dur: \cmd{link}
\item pour renommer un fichier : \cmd{rename}
\end{itemize}


\subsection{Scanner les répertories}

\begin{lstlisting}
 #include <sys/types.h>
 #include <dirent.h>

 DIR *opendir(const char *name);
 struct dirent *readdir(DIR *dirp);
 int closedir(DIR *dirp); 

 struct dirent {
   ino_t          d_ino; /* inode number */
   off_t          d_off; /* see man */
   unsigned short d_reclen; /* length */
   unsigned char  d_type; /* type of file */
   char           d_name[256]; /* filename */
 };
\end{lstlisting}


\subsection{Informations sur un fichier}

\begin{lstlisting}[basicstyle=\footnotesize]
 int stat(const char *pathname, struct stat *buf);

 struct stat {
    dev_t st_dev; /* device containing file */
    ino_t st_ino; /* inode number */
    mode_t st_mode; /* protection */
    nlink_t st_nlink; /* number of hard links */
    uid_t st_uid;  /* user ID of owner */
    gid_t st_gid;  /* group ID of owner */
    dev_t st_rdev; /* device ID (if special file) */
    off_t st_size; /* total size, in bytes */
    blksize_t st_blksize;
      /* blocksize for filesystem I/O */
    blkcnt_t st_blocks;
      /* number of 512B blocks allocated */
    struct timespec st_atim; /* last access */
    struct timespec st_mtim; /* last modification */
    struct timespec st_ctim; /* last status change */
 };
\end{lstlisting}

\subsection{Autres }

Autres appels système qui peuvent servir (et ne sont pas le sujet de prochains cours)

\begin{itemize}
\item \cmd{time} : renvoie le \imp{temps Unix}, i.e. le nombre de secondes depuis le 1er Janvier 1970.
\item \cmd{exit} : termine le programme
\item \cmd{nanosleep} : endort le processus pour un temps déterminé (void aussi \cmd{sleep} et \cmd{usleep})
\end{itemize}


Pour trouver l'appel système si on a la commande shell: regarder la fin du man.
(Notamment: gestion des droits et fichiers spéciaux...)




\section{La mémoire}

\subsection{Les différentes mémoires vives}

Une machine possède différent type de mémoire vive:

\begin{itemize}
\item La ``mémoire principale'' (RAM). Taille de l'ordre de Giga-octet (ordinateur/smartphone actuel) au Tera-octet (grosses machines de calcul).
\end{itemize}

\begin{itemize}
\item Les registres. Il s'agit de mémoires directement implantées dans l'unité de calcul du processeur.
 Il s'agit de la mémoire la plus rapide disponible, mais très limitée \todo{quelques mots 64 bits}

 On les utilise couramment quand on programme en assembleur. On s'en occupe rarement dans un langage de haut niveau: les compilateurs savent optimiser assez bien l'utilisation des registres. Le mot clef \cmd{register} en C est une relique du temps où les compilateurs n'étaient pas aussi performants...
\end{itemize}

\begin{itemize}
\item Les mémoires caches.
 Mémoire temporaire, plus rapide que la mémoire principale, généralement implantée dans le processeur. Il y en a plusieurs niveaux (L1i, L1d, L2, L3), de taille et de rapidité décroissante. Leur utilisation est gérée au niveau du matériel, et est transparente pour les processus. Pour voir la taille des caches: \cmd{lscpu}. On n'en parlera pas plus ici.
\item pour voir la taille des caches : \cmd{lscpu}
\item Le ``swap''.
\end{itemize}
Il ne s'agit pas vraiment d'une mémoire vive. C'est une zone sur le disque dur où l'OS peut mettre des parties de mémoire allouées quand il n'a plus de ``mémoire principale'' disponible. Ceci est transparent pour le processus, mais quand l'OS doit utiliser le swap, les performances chutent....

  


\subsection{Mémoire principale}

\begin{itemize}
\item La mémoire principale est un tableau d'octets (=8 bits).
\item Une adresse mémoire est un index (un "numéro") de case mémoire.
\item Un pointeur: une variable qui contient une adresse mémoire.
\end{itemize}


Sur une machine $64$ bits:
\begin{itemize}
\item Une adresse mémoire est un entier de $64$ bits 
\item Théoriquement, $2^{64}$ octets accessibles = 17179869184 Go...
\end{itemize}

\subsection{Adressage sans abstraction}

Dans les "vieux" ordinateurs (-286, DOS) (et dans certains modes des ordinateurs actuels):

\begin{itemize}
\item Si processus accède à la donnée à l'adresse $i$, il accède à la donnée à l'adresse $i$ dans la RAM:

 Le processus "voit" directement la mémoire physique. 
\end{itemize}

Deux processus ne peuvent pas utiliser la même zone mémoire, sans interférer.

\bigskip

Problèmes:
\begin{itemize}
\item Un processus voit la mémoire des autres processus
 (problèmes de sécurité et de droits) 
\item les processus peuvent empiéter les uns sur les autres.
\item La mémoire d'un processus doit correspondre à une zone mémoire physique (ex: utilisation de "swap" impossible)
\end{itemize}

\subsection{Virtualisation de la mémoire}

Mémoire virtuelle: il n'y a pas une correspondance directe entre l'espace d'adressage d'un processus et la mémoire physique.

\begin{itemize}
\item La mémoire vue par un processus est formée d'un ensemble de \imp{pages mémoires}. 
 
 Pour voir la taille des pages mémoires : \cmd{getconf PAGESIZE}
\item La RAM est découpée en zones de même taille.
\item Une translation (au niveau du processeur) a lieu pour convertir les adresses virtuelles en adresse physique, via la \imp{table des pages}
 (Pour voir comment cela se passe sur x86: registre "CR3".)
\end{itemize}


Avantages:
\begin{itemize}
\item Le processus peut organiser la mémoire comme il le veut (chaque processus a sa table)
\item Des zones mémoires peuvent être partagées entre différents processus
\item Déplacement possible de zones mémoires (swap...) 
\begin{itemize}
\item une interruption a lieu si le processus veut accéder à une zone qui ne correspond à rien dans la table des pages.
\end{itemize}
\end{itemize}

\subsection{Le mode noyau et mode utilisateur}

Sous Unix, il y a deux modes de fonctionnement:

\begin{itemize}
\item Le mode "utilisateur": mémoire virtualisée, accès matériel impossible (autrement que via les syscalls).
 
 Tous vos processus seront dans ce mode. 
\end{itemize}

\begin{itemize}
\item Le mode "noyau"
\begin{itemize}
\item Le noyau voit (et peut gérer) toute la mémoire physique. Il peut modifier les tables des pages. 
\item + de privilèges (accès au matériel...)
\end{itemize}
\end{itemize}


\subsection{Appel système}

\begin{itemize}
\item Un appel système: passage du mode utilisateur au mode noyau % via une interruption
\end{itemize}

\begin{itemize}
\item Via une sorte d'interruption: le processus fait basculer le processeur du mode utilisateur en mode système.
\end{itemize}

\begin{itemize}
\item Chaque syscall a un numéro.
\end{itemize}

\begin{itemize}
\item On ne peut donc pas appeler n'importe quelle fonction du noyau, seulement celles qui ont été prévues...
\end{itemize}



\subsection{Différentes zones mémoire d'un processus:}

\begin{itemize}
\item les instructions:
\begin{itemize}
\item le code du programme (en langage machine)
\item les librairies qu'il utilise (libc...)
\end{itemize}
\end{itemize}

\begin{itemize}
\item les données:
\begin{itemize}
\item segment de donnée statique
\item pile (stack)
\item tas (heap)
\end{itemize}
\end{itemize}

\begin{itemize}
\item non allouées : si on essaye d'y lire ou d'y écrire, il y aura une \imp{erreur de segmentation} (ou \imp{segfault})
\end{itemize}

\bigskip

\begin{itemize}
\item les zones ont également des droits (lecture seule, exécution autorisée...) 
\item certaines zones peuvent être partagées entre différents processus (c'est un moyen de communiquer inter-processus).
\end{itemize}

\subsection{Pile (Call stack)}

\begin{itemize}
\item Sont stockés dans la pile: les variables locales aux fonctions, les paramètres des fonctions, les adresses de retour.
\end{itemize}

\begin{itemize}
\item Attention au dépassement !
 
 (On peut augmenter la taille de la pile avec \cmd{setrlimit})
\end{itemize}



\subsection{Tas (Heap)}

Pour les allocation dynamiques.

En C, le tas est géré traditionnellement par la libc via \cmd{malloc}/\cmd{free}. La structure en interne peut être vue comme une liste chaînée. 


\bigskip

Désavantages des malloc/free:
\begin{itemize}
\item (des)allocation un peu lent 
\item une structure allouée prend un peu plus de place en mémoire
\item fragmentation
\item Il ne faut pas oublier à libérer la mémoire qui ne sert plus (\cmd{free}) sinon on aura des \imp{fuites mémoires} !
\end{itemize}

\bigskip


On peut changer la taille du tas avec \cmd{brk} ou \cmd{sbrk}. Néanmoins, comme cette zone mémoire est normalement gérée par la STD, on ne devrait pas l'utiliser.

Mais \cmd{sbrk(0)} permet de connaître l'adresse de fin du tas.

\subsection{Gérer différemment la mémoire dynamique}

Il existe des mécanismes de \imp{ramasse miettes} (\imp{garbage collector}), pour éviter d'avoir à désallouer la mémoire.
C'est le cas en Caml.

\bigskip

On peut faire ses propres allocateur de mémoire

\bigskip

Exemple: "memory pool", si on alloue beaucoup d'objets de la même taille $t$
\begin{itemize}
\item on alloue un grand tableau de $n$ cases de taille $t$
\item une "allocation" renvoie l'adresse d'une nouvelle case
\item les zones libres sont gérées par une liste chainée. 
\end{itemize}



\subsection{Exemple : variables dans différentes zones }

\begin{lstlisting}
#include <stdio.h>
#include <stdlib.h>
int a ; /* dans le segment statique donn'ees*/
int main() { /* dans le segment statique instructions */
  int b; /*dans la pile */
  int *ptr_c=(int*)malloc(sizeof(int)); /* l'entier point'e par ptr_c est dans le tas */
  printf("statique(data):%p statique(instruction):%p pile:%p tas:%p\n",&a,main,&b,ptr_c);
  free(ptr_c);
  return 0;
}

statique(data):0x6009fc statique(instruction):0x400576 pile:0x7ffd21051b94 tas:0x1310010
\end{lstlisting}



\subsection{Demander des nouvelles zones mémoires}

\cmd{mmap} permet de \imp{mapper} de nouvelles zones mémoires

\begin{itemize}
\item On peut mapper soit un fichier (via un descripteur), soit une zone vierge
\item Deux modes possible: "shared" ou "private"
\begin{itemize}
\item private : on a notre propre copie en mémoire
\item shared : la copie est partagée 
\end{itemize}
\end{itemize}

\begin{itemize}
\item On doit spécifier les droits (read, write, exec)
\item On peut spécifier l'adresse.
\end{itemize}

\bigskip

On peut libérer une zone avec \cmd{munmap}.


\bigskip

\begin{lstlisting}
#include <sys/mman.h>

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
\end{lstlisting}

Demande de mapper \cmd{length} octets depuis le fichier \cmd{fd}, à partir de l'offset (position) \cmd{offset}.

\cmd{prot} est la protection choisie: un sous ensemble de {PROT\_READ}, PROT\_WRITE, PROT\_EXEC.

\cmd{flags} donne les options. Il doit contenir MAP\_SHARED ou (exclusif) MAP\_PRIVATE, plus éventuellement d'autres options:
\begin{itemize}
\item MAP\_SHARED: la modification de la zone mémoire se répercutera sur les autres copies (c'est à dire, le fichier et les autres mappages du fichier). C'est un moyen de communication inter-processus. 
\item MAP\_PRIVATE: on aura notre propre copie de l'objet en mémoire. (C'est un moyen de demander une allocation de mémoire au système, surtout avec l'option MAP\_ANONYMOUS).
\item Si addr est NULL, le système choisi l'emplacement (conseillé en général), Sinon, il essaye de trouver un emplacement proche
\item MAP\_FIXED: l'adresse est impérative (soit le mappage se fait à \cmd{addr}, soit la fonction échoue)
\item MAP\_ANONYMOUS: on ne mappe pas un fichier (\cmd{fd} est ignoré), mais une zone vierge (initialisée à 0).
\end{itemize}

\subsection{Format et chargement des binaires}

Le format des exécutables sous la plupart des Unix est ELF (Executable and Linkable Format)

\begin{itemize}
\item Un fichier ELF est composé de plusieurs sections, qui vont correspondre à des zones mémoires ("text" pour les instructions, "data"...)
\item Pour voir les différentes sections : \cmd{objdump}
\item Ces sections seront "chargées" en mémoire via mmap.
\end{itemize}

\medskip

\begin{itemize}
\item Les librairies (glibc...) seront chargées à l'exécution, par la librairie "ld".
\item "ld" cherche les librairies dans les répertoires listés dans LD\_LIBRARY\_PATH, /lib et /usr/lib
\item Il est possible de forcer "ld" à choisir une autre librairie (LD\_PRELOAD)
\end{itemize}

\section{Processus}


\subsection{Les processus: Rappels (?)}

Un processus:
\begin{itemize}
\item a un numéro (le PID = Process IDentifier)
\item a un père.
\item a un propriétaire (réel et effectif)
\item a un état : en exécution, en sommeil, stoppé ou zombie
\item a un niveau de priorité 
\item un répertoire courant 
\item (certains processus) peuvent être ``légers'' (``threads'')

 (on y reviendra dans quelques cours)
\end{itemize}

\begin{itemize}
\item une table de descripteurs de fichiers
\item une table de pages
\end{itemize}

\begin{itemize}
\item renvoie un code retour (un entier entre 0 et 255)
\end{itemize}


\subsection{Voir les processus}

\begin{itemize}
\item Pour voir tous les processus tournant, avec leur lien de parenté : \cmd{ps faux}
\end{itemize}

\begin{itemize}
\item Pour voir en temps réel (utilisation CPU, mémoire...) : \cmd{top}
\end{itemize}

\medskip

\begin{itemize}
\item Toutes les informations dans le système procfs (\cmd{/proc/})
\end{itemize}


\subsection{État d'un processus}

Un processus peut être:

\begin{itemize}
\item actif (i.e. en exécution)
\item prêt (en attente d'exécution)
\item suspendu (par exemple avec ctrl+z)
\item en sommeil: il attend un évènement
\begin{itemize}
\item sleep, pause...
\item attente sur une I/O
\end{itemize}
\item zombi
\end{itemize}

\subsection{Ordonnancement}

Deux processus ne peuvent pas s'exécuter en même temps sur un même coeur.

\medskip

L'OS découpe le temps en petits bouts, et fait tourner les processus les uns après les autres. 

\medskip

L'OS choisi l'ordre, en essayant de respecter la priorité des processus (voir \cmd{nice})

\medskip

Passage d'un processus à un autre: \imp{commutation de contexte} (\imp{context switch}).
\begin{itemize}
\item assez lent...
\item transparent pour nous
\end{itemize}

  
Note: On peut changer la priorité des processus avec \cmd{nice} ou \cmd{renice}

\subsection{Gestion de processus : syscalls}

\begin{itemize}
\item \cmd{getpid()} renvoie le PID du processus courant
\item \cmd{getppid()} renvoie le PID du père
\end{itemize}

\begin{itemize}
\item \cmd{getuid()} renvoie l'UID de l'utilisateur processus courant
\item \cmd{geteuid()} renvoie l'UID de l'utilisateur effectif du processus courant
\item Ces UIDs peuvent être différents si le binaire est en "setuid"
\end{itemize}

\begin{itemize}
\item \cmd{setuid()} et \cmd{seteuid()} permettent de changer les utilisateurs, si on a les droits !
\end{itemize}

\subsection{}

\begin{itemize}
\item Obtenir/changer le répertoire courant: \cmd{getcwd()} / \cmd{chdir()}
\item Obtenir le temps CPU consommé (en mode utilisateur et système): \cmd{times()}
\item Modifier le masque de création de fichiers: \cmd{umask()}
\end{itemize}

\begin{itemize}
\item Pour voir/changer les "limites" d'un processus: \cmd{ulimit}, \cmd{getrlimit}, \cmd{setrlimit}
\end{itemize}


\subsection{Priorité d'un processus}

\begin{itemize}
\item Chaque processus a une priorité:
\begin{itemize}
\item généralement, un nombre entre -20 et 19, et par défaut : 0.
\item plus le nombre est élevé, moins le processus aura du temps de calcul.
\end{itemize}
\end{itemize}

\medskip

\begin{itemize}
\item Il est possible de lancer un processus avec une priorité plus basse avec \cmd{nice} 
\item Il est possible de diminuer la priorité d'un de ses processus en exécution:
\begin{itemize}
\item Commande: \cmd{renice}
\item Appel système: \cmd{nice}
\end{itemize}
\end{itemize}

\medskip

\begin{itemize}
\item Seul \cmd{root} a le droit d'augmenter une priorité.
\end{itemize}

\subsection{Comment lancer un processus ?}

Il faut différencier le fait de:
\begin{itemize}
\item créer un nouveau processus: le processus appelant continue de vivre, et un nouveau processus naît
\item exécuter un binaire spécifié: il n'y a pas de nouveau processus, l'ancien processus est "écrasé" par le nouveau
\end{itemize}

\bigskip

Créer un nouveau processus (\sur{création}) se fait avec \cmd{fork}

\medskip

Exécuter un binaire (\sur{recouvrement}) se fait avec \cmd{exec...}

\bigskip

Créer un nouveau processus qui est l'exécution d'un binaire se fait avec la combinaison de \cmd{fork} et \cmd{exec...}.

\subsection{\cmd{int system(const char *command)}}

(Pas un appel système. Donné à titre informatif.)

\bigskip

Un moyen simple de lancer un processus depuis un programme est d'utiliser \cmd{system} (dans <stdlib.h>).

\bigskip

\cmd{system} lance un shell (\cmd{/bin/sh}) qui exécutera \cmd{command}.
Une fois la commande terminée, la fonction retournera le code retour de la commande. 

\bigskip

Exemple : \cmd{system("ls");}

\subsection{Les \cmd{exec*}}

\begin{lstlisting}[basicstyle=\small]
#include <unistd.h>
int execl(const char *path, const char *arg, ...);
int execlp(const char *file, const char *arg, ...);
int execle(const char *path, const char *arg, ..., char * const envp[]);
int execv(const char *path, char *const argv[]);
int execvp(const char *file, char *const argv[]);
int execvpe(const char *file, char *const argv[], char *const envp[]);
\end{lstlisting}

\medskip

\begin{itemize}
\item \sur{Elles ne créent pas un nouveau processus}: elles remplacent (recouvrent) le processus courant par l'exécution du fichier en argument.
\end{itemize}

\begin{itemize}
\item En particulier, le PID, L'UID, les fichiers ouverts sont conservés (sauf si option O\_CLOEXEC)
\end{itemize}

\begin{itemize}
\item Si l'exécution se fait normalement, elles ne retournent jamais !
\end{itemize}


\begin{itemize}
\item execl* : les arguments sont donnés les un après les autres en argument de la fonction 
\item execv* : les arguments sont donnés dans un tableau
\item execlp/execvp/execvpe: le fichier est cherché dans le PATH
\item execlpe execvpe : on spécifie en plus le nouvel environnement
\end{itemize}

\bigskip

Note : \cmd{\cmd{exec} existe aussi dans le shell...}


\subsection{\cmd{pid\_t fork(void)}}

\cmd{fork()} (dans <unistd.h>) est \imp{la} commande pour lancer un nouveau processus.

\medskip

Elle \sur{duplique} le processus courant, pour créer un processus \imp{fils}.


\begin{itemize}
\item Dans le père, elle renvoie le PID du fils (et rien ne change)
\end{itemize}

\begin{itemize}
\item Dans le fils (le nouveau processus) :
\begin{itemize}
\item elle retourne 0
\item le fils aura un nouveau PID
\item son père sera le processus père
\end{itemize}
\end{itemize}


\begin{itemize}
\item \cmd{fork} retourne donc deux fois, une fois dans le père, une fois dans le fils
\end{itemize}

\begin{itemize}
\item Tout se passe comme si toute la mémoire du processus appelant fork est copiée.
\end{itemize}

\begin{itemize}
\item (En pratique, le système copie seulement si c'est nécessaire.)
\end{itemize}

\begin{itemize}
\item Les deux processus sont concurrents. On ne peut pas dire lequel des deux retournera en premier.
\end{itemize}


\bigskip

\cmd{vfork} est une version allégée de \cmd{fork}, mais qui n'est plus trop d'actualité.

Sous Linux, \cmd{clone} est similaire à \cmd{fork}, mais les deux processus gardent le même espace mémoire. On peut y voir un moyen de faire des processus plus légers (sans recopie de la mémoire). 

On verra par la suite un moyen de faire des processus légers proprement avec \cmd{pthread}.

\subsection{Exemple : fork}

\begin{lstlisting}
#include <unistd.h>

int main()
{
  if(fork()==0) {
    /* si on est ici, on est le fils */
    /*...*/      
    return 0; /* fin du fils */
  }
  /* si on est ici, on est le pere */
  /*...*/      
  return 0; /* fin du pere */
}
\end{lstlisting}

\subsection{fork et descripteurs de fichiers}

\begin{itemize}
\item Lors d'un fork, la table des descripteurs du processus est copiée.
\end{itemize}

\begin{itemize}
\item Les descripteurs des deux processus (père et fils) référencient les mêmes fichiers ouverts par le système (comme après un \cmd{dup})
\end{itemize}

\begin{itemize}
\item En particulier, si un des deux processus modifie le curseur d'un descripteur (read/write/lseek...), cela affectera le curseur du même descripteur de l'autre processus
\end{itemize}


\begin{lstlisting}
int main()
{
  int fd=open("sortie.txt",O_CREAT | O_RDWR,0644);
  if(fork()==0) {
    write(fd,"A",1);
    close(fd);
    return 0;
  }
  write(fd,"B",1);
  close(fd);
  return 0;
}
\end{lstlisting}

sortie.txt : \cmd{AB} ou \cmd{BA}

\subsection{Exemple : fork + exec}

\begin{lstlisting}
#include <unistd.h>

int main()
{
  if(fork()==0) {
    /* si on est ici, on est le fils */
    execlp("xeyes","xeyes",NULL);
    return 1; /* si on se trouve ici, c'est qu'execlp a echoue */
  }
  /* si on est ici, on est le pere */
  /*...*/      
  return 0; /* fin du pere */
}
\end{lstlisting}


\subsection{\cmd{pid\_t wait(int *ptr)}}

\cmd{wait} : attend jusqu'à ce qu'un processus fils termine.

\bigskip

Plus précisément:

\begin{itemize}
\item Si un processus fils termine avant l'appel de \cmd{wait} de son père, il devient \imp{zombi}.
\end{itemize}

\begin{itemize}
\item Si un processus n'a pas de fils: \cmd{wait} renvoie -1.
\item Si un processus a un fils zombi: \cmd{wait} renvoie le PID du fils zombi, et efface ce processus de la liste des processus.
\begin{itemize}
\item Si \cmd{ptr} n'est pas NULL, \cmd{wait} copie le "statut" dans l'entier pointé par \cmd{ptr} (voir man).
 Le status permet (entre autres) de retrouver le code de retour du processus.
\end{itemize}
\item Si un processus a des fils, mais pas  pas de fils zombi: \cmd{wait} attend jusqu'à ce qu'un fils devienne zombi, puis idem.
\end{itemize}

\bigskip

Attente d'un processus particulier:

\cmd{pid\_t waitpid(pid\_t pid, int *status, int options)};

\subsection{Exemple : fork + exec + wait}

\begin{lstlisting}
#include <unistd.h>

int main()
{
  int status;
  if(fork()==0) {
    /* si on est ici, on est le fils */
    execlp("xeyes","xeyes",NULL);
    return 1; /* si on se trouve ici, c'est qu'execlp a echoue */
  }
  /* si on est ici, on est le pere */
  wait(&status);
  return 0; /* fin du pere */
}
\end{lstlisting}


\subsection{\cmd{pid\_t setsid(void)}}

Un processus peut se détacher de son père en appelant \cmd{setsid()}.

\bigskip

Plus précisément, cette fonction sert à créer une nouvelle \imp{session}. Le processus appelant devient leader de cette session. 


\subsection{Exemple: \cmd{nohup \&} (un premier essai...)}

\begin{lstlisting}
#include <unistd.h>

int main(int argc, char *argv[])
{
  argc -= 1;
  argv += 1;
  
  if(fork()) {
    /* si on est ici, on est le pere */
    return 0;
  }
  /* si on est ici, on est le fils */
  setsid();
  execvp(*argv, argv);
  return 1; /* si on se trouve ici, c'est qu'execvp a echoue */
}
\end{lstlisting}

\subsection{Communication inter processus: avant goût}

IPC = Inter Processus Communucation

\bigskip

Comment faire communiquer des processus ?

\begin{itemize}
\item via les entrées sorties : pas dynamique
\item fichier standards : archaïque, lent, problèmes de synchronisation
\item fichiers tubes 
\item Signaux : information très limitée (mais ça sert à plein de niveau)
\item partage de mémoire 
\item par un canal réseau ...
\end{itemize}


\section{[C: Pointeurs sur fonctions]}

\subsection{}

\begin{itemize}
\item Une fonction dispose également d'une adresse mémoire
\end{itemize}

\begin{itemize}
\item C'est son \sur{point d'entrée}, i.e. l'adresse mémoire où commence la liste des instructions en langage machine
\end{itemize}




\begin{itemize}
\item Il est possible de manipuler les adresses des fonctions en C, et d'avoir des \sur{pointeurs sur des fonctions}
\end{itemize}

\begin{itemize}
\item Il est obligatoire de savoir manipuler les pointeurs sur fonctions pour gérer les signaux et les threads...
\end{itemize}

\subsection{Syntaxe en C}

Le type d'un pointeur sur fonction doit contenir les types des paramètres de la fonction, et le type de retour.

\begin{itemize}
\item les paramètres n'ont pas besoin d'avoir de nom:
\item le compilateur doit juste savoir quel type empiler sur la pile
\end{itemize}

\medskip

Pour déclarer un pointeur sur une fonction:

\cmd{type\_retour (*nompointeur) (liste\_arguments...);}


Exemple:

\medskip

\cmd{int (*fct) (int);}

\medskip

déclare fct comme étant un pointeur sur une fonction prenant en argument un entier, et revoyant un entier

\bigskip

Appeler une fonction pointée se fait de la même manière que pour une fonction normale.


\subsection{Exemple }

\begin{lstlisting}[basicstyle=\small]
int carre(int x) {return x*x;}

int cube(int x) {return x*x*x;}

void iter(int (*fct)(int)) {
  int i;
  for(i=1;i<=10;i++)
    printf("%d : %d\n",i,fct(i));
}

void main() {
  int (*x)(int);
  x=carre;
  iter(x);
  iter(cube);
}
\end{lstlisting}

\subsection{avec \cmd{typedef}}

On peut simplifier les choses avec \cmd{typedef}:

\begin{itemize}
\item \cmd{typedef int (*typefctintint) (int);}
\end{itemize}

Définit \cmd{typefctintint} comme étant le type pointeur sur une fonction int $\to$ int;

\begin{itemize}
\item \cmd{typefctintint fct=carre;}
\end{itemize}

\subsection{Exemple 1 : atexit}

\cmd{atexit} enregistre une fonction qui sera appelée à la fin (normale) du processus (après un \cmd{exit}, ou au retour du \cmd{main}) 

\medskip

\begin{lstlisting}
#include <stdlib.h>
int atexit(void (*function)(void));
\end{lstlisting}


Exemple:

\begin{lstlisting}
#include <stdio.h>
#include <stdlib.h>

void fin(void)
{
  printf("Je suis toujours l`a !\n");
}

int main()
{
  atexit(fin);
  printf("Je me termine\n");
  return 0;
}
\end{lstlisting}

\subsection{Exemple 2 : qsort}

\cmd{qsort} est une fonction de la libc effectuant un \textit{quick sort}.

\begin{lstlisting}
#include <stdlib.h>
void qsort(
  void *base,
  size_t nmemb,
  size_t size,
  int (*compar)(const void *, const void *)
  );
\end{lstlisting}

On doit passer en argument l'adresse de la fonction de comparaison (\cmd{compar}) que \cmd{qsort} doit utiliser.


Exemple (trie les lignes de l'entrée standard) :

\begin{lstlisting}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void *a, const void *b)
{
  return strcmp(*(const char**)a,*(const char **)b);  
}

int main()
{
   char bf[1000];
   char *tab[1000];
   int k=0,i;
   while(fgets(bf,1000,stdin))
     tab[k++]=strdup(bf);
   qsort(tab,k,sizeof(tab[0]),cmp);
   for(i=0;i<k;i++)
     printf("%s",tab[i]);
   return 0;
}
\end{lstlisting}

\section{Les signaux}

\subsection{Les signaux : introduction}

\begin{itemize}
\item Les signaux permettent de notifier des évènements à un processus.
\end{itemize}

\begin{itemize}
\item Il s'agit d'un moyen de communication limité:
\begin{itemize}
\item ponctuel
\item unique information: le numéro du signal, un entier entre 1 et (généralement) 64.
\end{itemize}
\item Mais très important sous Unix.
\end{itemize}


Beaucoup de mécanismes sous Unix utilisent des signaux.
Par exemple:
\begin{itemize}
\item \cmd{ctrl + c} (arrêt d'une tache)
\item \cmd{ctrl + z} (mise en pause d'une tache)
\item Tuer un processus par \cmd{kill}
\item Erreur de segmentation
\item Division par 0...
\end{itemize}

\subsection{Signaux standard}

\begin{itemize}
\item SIGTERM (15) : Signal de fin (signal par défaut de \cmd{kill})
\item SIGINT (2) : Terminaison depuis le clavier (ctrl + c)
\item SIGKILL (9)  : Tuer un processus (on ne peut pas le contourner)
\item SIGSTOP (19) : Arrêt (pause) du processus (ctrl + z)
\item SIGCONT (18) : Continuer si en pause
\item SIGALRM  (14) :  Temporisation \cmd{alarm} écoulée.
\item SIGUSR1  (10) :  Signal utilisateur 1.
\item SIGUSR2  (12) :  Signal utilisateur 2.
\item SIGCHLD  (17) :  Fils arrêté ou terminé
\end{itemize}

Les erreurs:
\begin{itemize}
\item SIGFPE        (8)  :  Erreur mathématique virgule flottante.
\item SIGPIPE      (13)  :  Écriture dans un tube sans lecteur.
\item SIGSEGV      (11)  :  Référence mémoire invalide.
\item SIGILL        (4)  :  Instruction illégale.
\item ...                                     
\end{itemize}



\subsection{Signaux générés}

Un signal est \sur{généré} par un évènement:
\begin{itemize}
\item Envoi d'un signal par un autre processus 
\item Action sur le terminal (ctrl+c, ctrl+z...)
\item Erreur (arithmétique, de segmentation ...)
\item Minuterie
\item Arrêt ou terminaison d'un fils...
\end{itemize}

Lorsque le signal est \sur{délivré} à un processus, une action se produit :
\begin{itemize}
\item action par défaut
\item signal ignoré
\item effectuer une action choisie : \sur{handler}
\end{itemize}

Un signal généré, mais pas (encore) délivré, est \sur{pendant}

\medskip

Si le même signal est généré plusieurs fois, on est pas sûr qu'il sera délivré le même nombre de fois

\subsection{Envoyer un signal}

Depuis le shell : \cmd{kill -\textit{sig} \textit{pid}}, où:
\begin{itemize}
\item \textit{sig} est le signal: le nom (KILL, STOP,CONT...) ou numérique
\item \textit{pid} est le PID du processus à qui on lance le signal
\end{itemize}

\bigskip

Appels systèmes:
\begin{lstlisting}
#include <sys/types.h>
#include <signal.h>
int kill(pid_t pid, int sig);
int raise(int sig);
unsigned int alarm(unsigned int s)
\end{lstlisting}

\cmd{kill} envoie le signal \cmd{sig} au processus \cmd{pid}.

\cmd{raise} envoie le signal \cmd{sig} au processus courant.

\cmd{alarm} envoie le signal SIGALRM $s$ secondes plus tard. (Si $s=0$, annule l'alarme)

\subsection{Réception : comportement par défaut}

À la réception d'un signal, un \sur{comportement par défaut} est définit. Celui-ci peut être: 

\begin{itemize}
\item Terminer le processus
\begin{itemize}
\item KILL, TERM, ALARM, INT, FPE, PIPE, USR1, USR2...
\end{itemize}
\item Terminer le processus avec fichier \cmd{core} 
\begin{itemize}
\item ILL, SEGV
\end{itemize}
\item Signal ignoré
\begin{itemize}
\item CHLD
\end{itemize}
\item Suspension du processus
\begin{itemize}
\item STOP
\end{itemize}
\item Continuation du processus
\begin{itemize}
\item CONT
\end{itemize}
\end{itemize}

Il est possible d'ignorer ce comportement par défaut, ou d'en définir un autre, pour tous les signaux, 
\sur{sauf SIGSTOP et SIGKILL}

\subsection{Ensemble de signaux}

\cmd{sigset\_t} est un type pour un ensemble de signaux. Une variable de ce type peut être manipulé par les fonctions suivantes.

\begin{lstlisting}
#include <signal.h>
int sigemptyset(sigset_t *set);
int sigfillset(sigset_t *set);
int sigaddset(sigset_t *set, int signum);
int sigdelset(sigset_t *set, int signum);
int sigismember(const sigset_t *set, int signum);
\end{lstlisting}

\subsection{Masquer des signaux}

\begin{lstlisting}
#include <signal.h>
int sigprocmask(int how, const sigset_t *set, sigset_t *oldset);
\end{lstlisting}

\begin{itemize}
\item \cmd{how} :
\begin{itemize}
\item SIG\_SETMASK : nouveau masque = set
\item SIG\_BLOCK : nouveau masque = ancien masque $\cup$ set
\item SIG\_UNBLOCK : nouveau masque = ancien masque $\setminus$ set
\end{itemize}
\end{itemize}

\begin{itemize}
\item Masquer un signal ne veut pas dire l'ignorer.
\end{itemize}

\begin{itemize}
\item Si un signal masqué est généré, il reste pendant, sauf si le comportement par défaut est de l'ignorer.
\end{itemize}

\subsection{Lister les signaux pendants}

\begin{lstlisting}
#include <signal.h>
int sigpending(sigset_t *set);
\end{lstlisting}

\medskip

Copie dans \cmd{set} la liste des signaux pendants.

\medskip

C'est particulièrement utile si des signaux sont masqués (et non ignorés).

\subsection{Changer le comportement : \cmd{signal}}

On peut demander à exécuter une fonction (handler) en cas de réception d'un signal.

\medskip

L'\sur{ancienne} interface Unix (non POSIX) est la suivante. \sur{Donnée à titre indicatif} (car plus simple à comprendre). \sur{Ne pas utiliser.}

\begin{lstlisting}
#include <signal.h>
typedef void (*sighandler_t)(int);
sighandler_t signal(int signum, sighandler_t handler);
\end{lstlisting}

\cmd{handler} est soit:
\begin{itemize}
\item SIG\_IGN : ignore le signal
\item SIG\_DFL : action par défaut
\item l'adresse d'une fonction prenant un entier
\begin{itemize}
\item  à la réception d'un signal, la fonction sera appelée, avec comme argument le numéro du signal.
\end{itemize}
\end{itemize}


\begin{lstlisting}
void handler(int i)
{
   printf("signal recu : %d\n",i);
}

int main()
{
   signal(SIGUSR1,handler);
   signal(SIGUSR2,handler);
   sleep(10000);
   return 0;
}
\end{lstlisting}

\subsection{\cmd{sigaction}}

L'interface à utiliser pour manipuler les handlers est \cmd{sigaction}

\begin{lstlisting}
struct sigaction {
 void     (*sa_handler)(int);
 void     (*sa_sigaction)(int, siginfo_t *, void *);
 sigset_t   sa_mask; 
 int        sa_flags;
};

int sigaction(int signum,
   const struct sigaction *act,
   struct sigaction *oldact);
\end{lstlisting}


\begin{itemize}
\item sa\_handler le handler (comme \cmd{signal})
\item sa\_flags : options (void man)
\item sa\_mask : liste des signaux à masquer en plus, le temps que le handler s'exécute
\end{itemize}

\begin{itemize}
\item Si \cmd{act} n'est pas NULL : nouveau handler à installer
\item Si \cmd{oldact} n'est pas NULL : l'ancien handler est copié dans la structure pointée
\end{itemize}

\begin{itemize}
\item On peut utiliser \cmd{sa\_sigaction} à la place de \cmd{sa\_handler} pour avoir un comportement plus fin (voir man).
\end{itemize}

\subsection{Attente de signaux}

\begin{lstlisting}
#include <unistd.h>
int pause(void);

#include <signal.h>
int sigsuspend(const sigset_t *mask);
\end{lstlisting}

\begin{itemize}
\item \cmd{pause} met le processus en pause, jusqu'à ce qu'un signal (n'importe lequel) arrive. 
\end{itemize}

\begin{itemize}
\item Problème: un signal non masqué peut arriver avant l'appel à pause(), et être "perdu"...
\end{itemize}

\begin{itemize}
\item \cmd{sigsuspend} change temporairement le masque des signaux masqués, et attend jusqu'à ce qu'un signal arrive. 
\end{itemize}

\subsection{Signaux et appels systèmes}

\begin{itemize}
\item Certains appels systèmes peuvent être interrompus par un signal.
\begin{itemize}
\item Dans ce cas, l'appel système échoue, et le code retour (errno) sera EINTR
\end{itemize}
\end{itemize}

\begin{itemize}
\item Lors d'un fork, les signaux pendants ne sont pas hérités (le masque et les handlers, si)
\end{itemize}

\begin{itemize}
\item Lors d'un exec, les handlers ne sont pas hérités (le masque et les signaux pendants, si)
\end{itemize}





\section{Communication Inter Processus  (IPC): Tubes}

\subsection{Principe}

\begin{itemize}
\item À partir de maintenant, on veut faire communiquer plusieurs processus.
\end{itemize}

\begin{itemize}
\item Un \sur{tube} est un moyen de le faire.
\end{itemize}

Note:

\begin{itemize}
\item Faire communiquer des processus sur une même machine par tubes peut sembler archaïque, et pas très efficace (comparé à la mémoire partagée).
\end{itemize}

\begin{itemize}
\item \sur{Mais} : les communications réseau (par sockets) se feront de manière similaire
\item les principes/fonctions expliqués dans ce chapitre seront toujours valables.
\end{itemize}


\begin{itemize}
\item Tube: canal de communication FIFO (First In First Out)
\end{itemize}

\begin{itemize}
\item Utilise 2 descripteurs de fichiers: un pour l'écriture (l'entrée), et un pour la lecture (la sortie)
\end{itemize}

\begin{itemize}
\item L'écriture dans l'entrée sera mise en attente dans un tampon
\end{itemize}

\begin{itemize}
\item La lecture dans la sortie lira les données du tampon, dans l'ordre (FIFO).
\end{itemize}

\begin{itemize}
\item La lecture et l'écriture se font comme pour les fichiers réguliers: read et write
\end{itemize}

\begin{itemize}
\item Il n'y a pas de curseur : lseek est impossible !
\end{itemize}


Par exemple, lorsque l'on exécute :

\cmd{ cat fichier.txt | grep password}

\medskip

\begin{itemize}
\item le shell lance deux nouveaux processus : un pour \cmd{cat} et un pour \cmd{grep}
\item le shell crée un tube
\item la sortie standard de \cmd{cat} sera le côté "écriture" du tube
\item l'entrée standard de \cmd{grep} sera le côté "lecture" du tube
\end{itemize}


Plus précisement :

\cmd{ cat fichier.txt | grep password}

\medskip

\begin{itemize}
\item le shell crée un tube
\item le shell lance deux nouveaux processus (deux \cmd{fork()}): un pour \cmd{cat} et un pour \cmd{grep}
\item la sortie standard de \cmd{cat} est ecrasée par le côté "écriture" du tube (via par exemple \cmd{dup2})
\item l'entrée standard de \cmd{grep} est écrasée par le côté "lecture" du tube
\item les fils se recouvent (\cmd{exec...}) en cat et grep.
\end{itemize}



\begin{lstlisting}[basicstyle=\scriptsize]
cat file.txt | grep passwd | sed 's/.*passwd=\(\w*\).*/\1/'
\end{lstlisting}

\begin{lstlisting}[basicstyle=\scriptsize]
$ lsof
...
cat  5223  mrao  0u  CHR  136,1  0t0  4     /dev/pts/1
cat  5223  mrao  1w FIFO   0,10  0t0  27854 pipe
cat  5223  mrao  2u  CHR  136,1  0t0  4     /dev/pts/1
...
grep 5224  mrao  0r FIFO   0,10  0t0  27854 pipe
grep 5224  mrao  1w FIFO   0,10  0t0  27856 pipe
grep 5224  mrao  2u  CHR  136,1  0t0  4     /dev/pts/1
...
sed  5225  mrao  0r FIFO   0,10  0t0  27856 pipe
sed  5225  mrao  1u  CHR  136,1  0t0  4     /dev/pts/1
sed  5225  mrao  2u  CHR  136,1  0t0  4     /dev/pts/1
\end{lstlisting}


\subsection{Créer un tube (par syscall)}


\begin{lstlisting}
#include <unistd.h>

int pipe(int pipefd[2]);
\end{lstlisting}

\medskip

\begin{itemize}
\item Ouvre les 2 descripteurs de fichier associés a un nouveau tube
\item Prend en argument un tableau de deux entiers:
\item Renvoie dans \cmd{pipefd[0]} la sortie du tube (le descripteur en lecture)
\item Renvoie dans \cmd{pipefd[1]} l'entrée du tube (le descripteur en écriture)
\end{itemize}

\subsection{Exemple : pipe}

\begin{lstlisting}
main() {
  int fd[2],r;
  char buffer[10];

  pipe(fd);

  r=write(fd[1],"hello",5);  
  assert(r==5);
  
  r=read(fd[0],buffer,10);
  assert(r==5);

  buffer[r]=0;
  printf("recu: %s\n",buffer);
}
\end{lstlisting}

\subsection{Exemple : pipe + fork}

\begin{lstlisting}
#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

int main() {
  char buffer[11];
  int fd[2];
  pipe(fd);

  if(fork()==0) {
    close(fd[1]); // on ferme les descripteurs qui ne servent plus
    while(1) {
      int r=read(fd[0],buffer,10);
      if(r<0) perror("Erreur lecture");
      else {
	buffer[r]=0;
	printf("fils recoit: '%s'\n",buffer);
      }
    }
    return 0;
  }
  close(fd[0]); // on ferme les descripteurs qui ne servent plus

  while(1) {
    snprintf(buffer,11,"%d",rand()%1000);
    printf("pere envoie '%s'\n",buffer);
    int r=write(fd[1],buffer,strlen(buffer));
    if(r<0) perror("Erreur ecriture");
    usleep(1000*(rand()%1000));
  }
  return 0;
}
\end{lstlisting}

\subsection{Créer un tube nommé ("fichier tube")}

\begin{itemize}
\item Un autre moyen de créer un tube est de créer et ouvrir un "tube nommé"
\end{itemize}

\begin{itemize}
\item Il s'agit d'un fichier spécial (non "régulier")
\end{itemize}

\begin{itemize}
\item Commande shell pour créer un tube nommé : \cmd{mkfifo}.
\end{itemize}

\begin{itemize}
\item Appels systèmes : \cmd{mkfifo} ou \cmd{mknod}.
\end{itemize}

\bigskip

Quand un fichier tube est ouvert en lecture, et ouvert par un autre processus en ecriture, le comportement sera le même qu'un tube crée par \cmd{pipe}



\subsection{Mode "flot" (stream)}

Mode flot: les envois successifs d'informations s'additionnent.

Il n'y a pas de "séparations" entre elles.

\medskip

Exemple : 
\begin{itemize}
\item \cmd{write(in,"ABC",3)}
\begin{itemize}
\item le tube contient "ABC"
\end{itemize}
\item \cmd{write(in,"123",3)}
\begin{itemize}
\item le tube contient "ABC123"
\end{itemize}
\item \cmd{read(out,bf,4)}
\begin{itemize}
\item renvoie 4, et bf contient "ABC1"
\item le tube contient "23"
\end{itemize}
\item \cmd{read(out,bf,4)} 
\begin{itemize}
\item renvoie 2, et bf contient "23"
\item le tube est vide
\end{itemize}
\item \cmd{read(out,bf,4)} 
\begin{itemize}
\item bloque jusqu'à ce qu'un processus écrive dans le fifo...
\end{itemize}
\end{itemize}



\subsection{Nombre de lecteur et écrivains}

\begin{itemize}
\item Un tube peut avoir un nombre de lecteur (ou d'écrivain) différent de un. 
\end{itemize}

\begin{itemize}
\item Si un tube a 0 lecteur: l'écriture échouera (signal SIGPIPE)
\item Si plus d'un lecteur: premier arrivé, premier servi 
\end{itemize}

\begin{itemize}
\item Si un tube a 0 écrivain (et le tube est vide), la lecture renverra 0 (i.e. comme pour un fin de fichier)
\end{itemize}

\bigskip

\begin{itemize}
\item Comme toujours, on ferme les descripteurs qui ne servent plus.
\end{itemize}


\subsection{Caractère bloquant}

\begin{itemize}
\item Par défaut, la lecture dans un tube vide sera bloquant
\end{itemize}

\begin{itemize}
\item Il est possible de rendre la lecture non bloquante, en changeant l'option O\_NONBLOCK du descripteur de fichier
\end{itemize}

\begin{itemize}
\item Dans ce cas, la lecture dans un tube vide échouera (retour -1), avec errno = EAGAIN
\end{itemize}


\medskip

\begin{itemize}
\item Attention, un tube a aussi une capacité limitée (PIPE\_BUF=4096).

 Quand un tube est plein, une écriture sera également bloquante.
\end{itemize}


\subsection{Manipuler un descripteur de fichier : fcntl}

\cmd{fcntl} permet de manipuler les descripteurs de fichiers.

\bigskip

Elle permet (entre autres) de changer les options (modes) des descripteurs de fichiers. En particulier :

\begin{itemize}
\item O\_NONBLOCK : caractère non bloquant d'un descripteur
\end{itemize}

\bigskip

Pour passer un descripteur en mode non bloquant:

\begin{lstlisting}
int flags = fcntl(fd, F_GETFL, 0);
fcntl(fd, F_SETFL, flags | O_NONBLOCK);
\end{lstlisting}

\subsection{Attente sur plusieurs descripteurs de fichiers : select}

\cmd{select} permet d'attendre (avec un temps limite) sur un ensemble de descripteurs de fichiers en un seul appel.

\bigskip

Pour utiliser \cmd{select}, il faut au préalable manipuler une structure qui représente un ensemble de descripteurs de fichiers. Cela se fait via les primitives suivantes:

\begin{lstlisting}
#include <sys/select.h>

void FD_CLR(int fd, fd_set *set);
int  FD_ISSET(int fd, fd_set *set);
void FD_SET(int fd, fd_set *set);
void FD_ZERO(fd_set *set);
\end{lstlisting}


\begin{lstlisting}
#include <sys/select.h>

int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
\end{lstlisting}

\begin{itemize}
\item nfds : le plus grand descripteur de fichiers à vérifier +1
\item readfds : l'ensemble des descripteurs à vérifier en lecture
\item writefds : l'ensemble des descripteurs à vérifier en ecriture
\item execptfds : l'ensemble des descripteurs à vérifier en exception
\item timeout : temps maximal à attendre.
\end{itemize}

À sa sortie, \cmd{select} modifie les ensembles de telle façon qu'il ne reste que les descripteurs de fichiers sur lesquels il y a quelque chose à lire ou écrire.


\subsection{Attente sur plusieurs descripteurs de fichiers : poll}

\cmd{poll} permet également d'attendre sur un ensemble de descripteurs de fichiers, mais plus finement.

\begin{lstlisting}[basicstyle=\footnotesize]
#include <poll.h>

int poll(struct pollfd *fds, nfds_t nfds, int timeout);

struct pollfd {
 int   fd;          /* file descriptor */
 short events;      /* requested events */
 short revents;  /* returned events */
};
\end{lstlisting}

\begin{itemize}
\item fds : un table de pollfd à surveiller,
\item nfds : taille de fds
\item timeout : temps maximum (en millisecondes)
\item cmd{events} et \cmd{revents} sont des conjonctions de :
\begin{itemize}
\item POLLIN : il y a quelque chose à lire
\item POLLOUT : il est possible d'y écrire
\item POLLERR : il y a une erreur
\item POLLHUP : pipe ou socket fermé de l'autre côté
\end{itemize}
\end{itemize}

\subsection{Un premier pas vers les communications réseau}

Une \sur{socket} est un point de communication où il est possible d'envoyer et de recevoir des informations.

On en reparlera longuement au moment de la programmation réseau

\medskip

Les sockets communiquent par pair. Il y a plusieurs moyen de les faire communiquer (différents protocoles réseau, ou en local).

\medskip

On peut créer une paire de socket en communication locale, qui fonctionnera similairement deux tubes:
\begin{itemize}
\item l'entrée de la 1ere socket sera l'entrée du 1er tube et la sortie de la 2eme socket sera la sortie du 1er tube
\item l'entrée de la 2eme socket sera l'entrée du 2eme tube et la sortie de la 1ere socket sera la sortie du 2eme tube
\end{itemize}


\begin{lstlisting}
#include <sys/types.h> 
#include <sys/socket.h>

int socketpair(int domain, int type, int protocol, int sv[2]);
\end{lstlisting}

Crée 2 sockets associées.

Pour le faire via une communication locale :
\begin{itemize}
\item domain = AF\_UNIX
\item protocol = 0
\end{itemize}

\begin{itemize}
\item type :
\begin{itemize}
\item SOCK\_STREAM : communication par flot (comme pour les tubes)
\item SOCK\_DGRAM : communication en mode paquet 
\end{itemize}
\end{itemize}

\begin{itemize}
\item sv: un tableau de 2 entiers, pour le renvoi des 2 descripteurs de fichiers (les 2 sockets)
\end{itemize}

\subsection{mode paquet (DGRAM)}

Au contraire du mode flot (STREAM), chaque information envoyée constitue une entité indivisible.

Exemple : 
\begin{itemize}
\item \cmd{write(in,"ABC",3)}
\begin{itemize}
\item la file de messages contient "ABC"
\end{itemize}
\item \cmd{write(in,"123",3)}
\begin{itemize}
\item la file contient "ABC","123"
\end{itemize}
\item \cmd{read(out,bf,10)}
\begin{itemize}
\item renvoie 3, et bf contient "ABC"
\item la file contient "123"
\end{itemize}
\item \cmd{read(out,bf,10)} 
\begin{itemize}
\item renvoie 3, et bf contient "123"
\item la file vide
\end{itemize}
\item \cmd{read(out,bf,4)} 
\begin{itemize}
\item bloque jusqu'à ce qu'un processus écrive dans le socket...
\end{itemize}
\end{itemize}


\subsection{Autres IPC }

D'autres moyens de communication inter-processus existent (POSIX et SysV).

\bigskip

Nous n'ont parlerons pas, car les mécanismes sont similaires à des mécanismes déjà vus (pipe/socket), ou que l'on verra plus tard (threads)

\bigskip

Ce sont: 

\begin{itemize}
\item Les files de messages (POSIX: \cmd{man mq\_overview})
\begin{itemize}
\item Similaire aux sockets en mode paquet (DGRAM)
\end{itemize}
\end{itemize}


\begin{itemize}
\item La mémoire partagée (POSIX: \cmd{man shm\_overview})
\begin{itemize}
\item Un segment mémoire est partagé entre plusieurs processus. C'est un moyen de communication très rapide (au sein d'une même machine), mais il faut faire attention aux synchronisations.
\end{itemize}
\end{itemize}

\begin{itemize}
\item Les sémaphores (POSIX: \cmd{man sem\_overview})
\begin{itemize}
\item Il s'agit de mécanisme de synchronisation (exclusion mutuelle). On parlera de sémaphores et mutex en même temps que les threads.
\end{itemize}
\end{itemize}

\bigskip

Pour voir les mécanismes System V : \cmd{man svipc}




\section{Bonnes pratiques, débogage et optimisation}

\subsection{On va voir:}

Quelques bonnes et mauvaises pratiques de programmation

\medskip

Outils de débogage:
\begin{itemize}
\item gdb
\item valgrind
\end{itemize}

\medskip

Outils de "profilage": 
\begin{itemize}
\item gprof
\item gcov
\end{itemize}

\medskip

Options utiles de \cmd{gcc}

\subsection{Les "bugs" }

Des bugs (cachés ou non) peuvent avoir de conséquences fâcheuses:
\begin{itemize}
\item plantages (aléatoires), pertes de données
\item "exploitations": porte d'entrée aux problèmes de sécurités
\end{itemize}

\medskip

Lorsqu'un "bug" arrive:
\begin{itemize}
\item c'est (généralement) votre faute !
\end{itemize}

\medskip

S'il un programme s'exécute sans "bug":
\begin{itemize}
\item cela n'implique pas que vous avez bien programmé !
\item les bugs peuvent être "non déterministes" ("Heisenbug"...)
\end{itemize}

\subsection{Les bugs dans un code}

Mieux vaut prévenir que guérir :
\begin{itemize}
\item adopter de bonnes pratiques de programmation
\item tester régulièrement son code
\item détecter les problèmes le plus tôt possible dans le processus de programmation
\end{itemize}

\medskip

Mais quand il faut guérir :
\begin{itemize}
\item utilisation d'outils de débogage 
\end{itemize}

\subsection{Bonnes pratiques}

Servent à éviter la confusion, et améliorer la compréhension entre les différents programmeurs.
Donc en conséquence, à limiter le risque d'erreurs.

\begin{itemize}
\item commenter le code
\item avoir indentation correcte 
\item utiliser des noms de variables/fonction explicites
\item "garder le code simple" (KIS):
\item préférer des fonctions courtes 
\item éviter la redondance de code
\item lors de la première version préférez un algorithme simple (et plus lent) à un algorithme complexe (et plus rapide)
\end{itemize}


Pour les projets conséquents, ou à plusieurs:
\begin{itemize}
\item code "modulaire"
\item documentez vos fonctions
\item respectez une convention de nommage
\item utilisez un utilitaire de versionnage
\end{itemize}

\bigskip

Note: on peut faire un code correct sans ces pratiques, mais c'est périlleux (e.g: \cmd{ioccc})

\subsection{Pratiques mauvaises/dangereuses/\sur{interdites}}

Ne pas initialiser les variables
\begin{itemize}
\item l'erreur pourra passer inaperçue, car souvent elle sera initialisée à 0 la première fois, mais après ce sera plus aléatoire...
\end{itemize}

Ne pas tester les codes retours
\begin{itemize}
\item lire les manuels des fonctions que vous utilisez
\end{itemize}

L'utilisation de fonctions réputées dangereuses
\begin{itemize}
\item sprintf(), strcpy(), strcat(),  vsprintf(), gets() ne vérifient pas si il y a assez de place 
\item fonctions non ré-entrantes dans un code multithread
\end{itemize}

Ne pas désallouer/fermer ce qui ne sert plus (mémoire, descripteurs de fichiers...)

\bigskip

Note: avec ces pratiques, un code ne sera pas "correct".

\subsection{Tester }

En cas de projet conséquent, il faut régulièrement :
\begin{itemize}
\item tester si le code compile
\item tester s'il donne les résultats attendus
\end{itemize}

\medskip

Séparer le processus de développement en petites parties. Par exemple, on peut dégager deux processus indépendants:
\begin{itemize}
\item le "refactoring": on ne change pas les fonctionnalités, on ne fait que réorganiser/clarifier/simplifier/optimiser le code.
\item l'ajout de fonctionnalités.
\end{itemize}

\medskip

Ne pas les faire en même temps, et vérifier après chaque étape.

\subsection{Tests}

\begin{itemize}
\item "Test unitaire": vérifier le bon fonctionnement d'une partie (unité, module) du logiciel. 
\end{itemize}

\medskip

\begin{itemize}
\item Créez et intégrez une batterie de tests qui teste automatiquement chaque partie les unes après les autres
\end{itemize}

\medskip

\begin{itemize}
\item Les tests doivent être "méchants": testez sur beaucoup d'entrées, et essayez de couvrir tous les cas
\end{itemize}

\subsection{Programmation par contrats}

\sur{Assertion}: expression qui doit être évaluée à vraie à un moment donné 

\bigskip

Dans le paradigme "Programmation par contrats", 3 types d'assertions:
\begin{itemize}
\item pré-conditions
\item post-conditions
\item invariants
\end{itemize}

\bigskip

En C/C++: on peut tester une assertion avec \cmd{assert} 

\subsection{\cmd{assert}}

\cmd{assert(expr)}
\begin{itemize}
\item dans assert.h
\item se déactive avec l'option -DNDEBUG
\item attention: pas pour tester les codes retours dans un vrai programme !
\end{itemize}

\begin{lstlisting}
#define mon_assert(expr) {\
 if(!(expr)) {\
  fprintf(stderr,"assert %s fail %s:%s:%d\n",\
          __STRING(expr), __FILE__,\
          __ASSERT_FUNCTION,__LINE__);\
  abort();\
 }\
}
\end{lstlisting}

\subsection{Outils d'aide au développement}

Utilisation d'environnement de développement

\bigskip

Outils de gestion de version

\begin{itemize}
\item subversion (SVN), Git, mercurial...
\end{itemize}

\begin{itemize}
\item possible de faires des branches stable / développement
\item il est possible de reprendre une ancienne version pour tracker l'apparition d'un bug.
\end{itemize}

\subsection{Tracker les bugs: outils à disposition}

voir les choses "suspectes", même sur un code qui semble marcher correctement:
\begin{itemize}
\item gcc -Wall
\begin{itemize}
\item un code devrait toujours compiler sans warning !
\item on peut raffiner les tests de warning. ex: "-Wno-sign-compare"
\item on peut (des)activer un test dans le code :
\end{itemize}
\end{itemize}
\begin{lstlisting}[basicstyle=\small]
#pragma GCC diagnostic ignored "-Wsign-compare"
...
#pragma GCC diagnostic warning "-Wsign-compare"
\end{lstlisting}


\begin{itemize}
\item gcc -fstack-protector-all
\item en C++ : g++ -D\_GLIBCXX\_DEBUG pour des tests sur les conteneurs de la STL
\item Valgrind : passer un coup de valgrind de temps en temps, même sur un code sans suspicion, ne fait pas me mal...
\end{itemize}

\bigskip

En cas de bug avéré :
\begin{itemize}
\item compiler avec les infos de débogage: gcc -g 
\begin{itemize}
\item attention, des fois cela fait des choses bizarres avec "-Ox"
\end{itemize}
\item gdb
\item valgrind
\end{itemize}


\subsection{Valgrind}

valgrind détecte (des fois) :
\begin{itemize}
\item les variables non initialisées
\item les fuites mémoires
\item les dépassements  de tableaux
\end{itemize}

\bigskip

Il y a (rarement) des faux positifs (dans certaines librairies). Mais en général: si il y a un warning, c'est qu'un truc n'est pas bon dans votre code. Càd, un truc à corriger au plus tôt !

\bigskip

Principe (idée) : exécute le code dans un processeur virtuel. Exécution 10 à 30x plus lente...

\subsection{Valgrind : utilisation}

\begin{itemize}
\item Compiler avec l'option -g (rajout des symboles de débogage dans le fichier binaire)
\end{itemize}


\begin{itemize}
\item Exécuter la commande, précédée de \cmd{valgrind}
\end{itemize}


\begin{itemize}
\item Les avertissement seront envoyés sur la sortie erreur:
\end{itemize}

\begin{lstlisting}[basicstyle=\scriptsize,showstringspaces=false]
==21068== Invalid write of size 8
==21068==    at 0x400A6F: add(char const*, elm_t*) (vector.cpp:28)
==21068==    by 0x400AF7: main (vector.cpp:39)
==21068==  Address 0x5a81c88 is 8 bytes inside a block of size 16 free'd
==21068==    at 0x4C2A30B: operator delete(void*) (vg_replace_malloc.c:575)
...
\end{lstlisting}


\subsection{Autres outils de la suite Valgrind}

\cmd{valgrind --tool=<toolname>}

\begin{itemize}
\item memcheck (par défaut): reporte les problèmes d'accès mémoire (non alloué, non initialisé, inaccessible), les fuites mémoires, double-free...
\end{itemize}

\begin{itemize}
\item massif : profilage de tas
\end{itemize}

\begin{itemize}
\item cachegrind, callgrind : profilage de cache
\end{itemize}

\begin{itemize}
\item helgrind , DRD: déboguer programmes multithreadés
\end{itemize}

\subsection{\cmd{gdb}}

\cmd{gdb} est le déboguer par défaut de la suite GNU

Permet, entre autres:
\begin{itemize}
\item d'exécuter jusqu'à un ou des points d'arrêts
\item d'exécuter pas à pas
\item de regarder l'état des variables, pile, registres...
\end{itemize}

\medskip

Comment ça marche (idée, sur x86):
\begin{itemize}
\item gdb a accès à tout l'espace mémoire du processus qu'il débogue
\item quand on met un point d'arrêt sur une ligne, gdb remplace la première instruction machine correspondante à la ligne par une instruction "INT 3" (opcode: 0xCC)
\item l'exécution de "INT 3" provoque une interruption, qui rend la main à gdb (qui peut remettre l'instruction initiale à la place de INT 3)
\end{itemize}


\subsection{\cmd{gdb}: lancement }

Compiler le programme à déboguer avec l'option "-g"
\begin{itemize}
\item attention, ça fait souvent des choses bizarres avec -Ox
\end{itemize}

Lancer le gdb:
\begin{itemize}
\item \cmd{gdb ./executable}
\item si arguments: \cmd{gdb -{}-args ./executable arguments...}
\end{itemize}

Dans l'interface de gdb: 
\begin{itemize}
\item \cmd{run} : lance l'exécution
\end{itemize}

\bigskip

Attacher un programme en cours d'exécution :
\begin{itemize}
\item lancer \cmd{gdb}
\item \cmd{attach pid}
\end{itemize}

\bigskip

\begin{itemize}
\item \cmd{gdb -tui} : avec une interface textuelle
\end{itemize}

\subsection{\cmd{gdb} : lister le code}

\begin{itemize}
\item \cmd{run} : lance l'exécution
\end{itemize}

\begin{itemize}
\item \cmd{ctrl+c} : stoppe l'exécution
\item \cmd{cont} : continue l'exécution
\end{itemize}

\begin{itemize}
\item \cmd{list} : lister le code (à la position courante)
\item \cmd{list \textit{fct}} : lister le code depuis le début de la fonction \textit{fct}
\item \cmd{list \textit{fichier:fct}} : lister le code depuis le début de la fonction fct dans le fichier \textit{fichier}
\item \cmd{list +}, \cmd{list -} : avancer (reculer) dans le fichier
\end{itemize}

\begin{itemize}
\item \cmd{step} : avance d'un pas
\item \cmd{next} : avance d'un pas (sans entrer dans les fonctions)
\item \cmd{finish} : avance jusqu'à la fin de la fonction courante
\end{itemize}

\subsection{\cmd{gdb} : points d'arrêts }

Point d'arrêt (breakpoint) : arrête le processus quand il atteint une ligne 

\begin{itemize}
\item \cmd{break \textit{fct}} : rajoute un point d'arrêt au début de la fonction \textit{fct}
\item \cmd{break \textit{n}} : rajoute un point d'arrêt à la ligne \textit{n}
\item \cmd{break \textit{fichier:ligne}} ou \cmd{break \cmd{fichier:fct}}
\end{itemize}

\begin{itemize}
\item possibilités de point d'arrêts conditionnels
\end{itemize}

\begin{itemize}
\item \cmd{info breakpoints} : lister les points d'arrêts 
\end{itemize}

Retirer un point d'arrêt:
\begin{itemize}
\item \cmd{clear \textit{fct}}
\item \cmd{delete \textit{nb}}
\end{itemize}

\subsection{\cmd{gdb} : variables et "watchpoints"}

\begin{itemize}
\item \cmd{print \textit{var}} : affiche la valeur d'une variable (ou expression)
\item \cmd{display \textit{var}} : affiche à chaque pas 
\end{itemize}

\medskip

Modifier une variable:
\begin{itemize}
\item \cmd{set \textit{var} = \textit{x}}
\end{itemize}

\medskip
\textit{watchpoint} : arrête le programme quand une variable est modifiée
\begin{itemize}
\item \cmd{watch \textit{var}}
\end{itemize}

\subsection{\cmd{gdb}: pile et threads}

\begin{itemize}
\item \cmd{backtrace} : affiche  la pile d'appels
\end{itemize}

\begin{itemize}
\item \cmd{up} / \cmd{down} : monter ou descendre dans les \textit{frames}
\item \cmd{frame \textit{num}} : changer de \textit{frame}
\end{itemize}

\bigskip

Multithread:
\begin{itemize}
\item \cmd{info threads} : liste les threads
\item \cmd{thread \textit{num}} : change le thread courant
\end{itemize}


\subsection{\cmd{gdb}: registres et assembleur}

\begin{itemize}
\item \cmd{info registers} : affiche les registres
\end{itemize}

\begin{itemize}
\item \cmd{layout asm} : affiche le code assembleur
\end{itemize}

\begin{itemize}
\item \cmd{layout src} : affiche le code source
\end{itemize}

\medskip

\medskip

Il existe des interfaces graphiques à gdb...

\subsection{\cmd{gdb}: raccourcis}

\begin{itemize}
\item entrée : précédente commande
\item r: run
\item l: list
\item c: continue
\item s: step
\item n: next
\item bt: backtrace
\item i: info
\item b: breakpoints
\item i b: info breakpoints
\item ...
\end{itemize}

\subsection{Déboguer: aller plus loin}

Il est possible d'intégrer des outils de débogage dans son code.
Exemple: \cmd{backtrace}

\begin{lstlisting}[basicstyle=\small]
void sigsegv(int)
{
  void *bt[DEBUGMEM_MAXBT];
  int sizebt = backtrace (bt,DEBUGMEM_MAXBT);
  char **strings = backtrace_symbols (bt, sizebt);
  for(int i=0;i<sizebt;i++)
    fprintf(stderr,"  %s\n",strings[i]);
  exit(1);
}

...
signal(SIGSEGV, (sighandler_t) sigsegv);
signal(SIGBUS, (sighandler_t) sigsegv);
...
\end{lstlisting}


\subsection{Optimiser son code}

Là, on suppose que notre code marche bien. On veut l'optimiser:

\medskip

Options de gcc:
\begin{itemize}
\item -Ox
\begin{itemize}
\item -O0 : pas d'optimisation
\item -O1 : optimisations modérées
\item -O2 : pleines optimisations
\item -O3 : comme -O2, en encore plus agressif
\item -Os : optimisation en mémoire (taille de d'exécutable)
\end{itemize}
\item -march=native : compile pour le processeur de la machine
\item -ffastmath : active certaines optimisations sur les flottants (ne respecte plus la norme IEEE 754)
\item ...
\end{itemize}

Optimisations de gcc: passer des variables en registres, rendre des fonctions \textit{inline}, dérécursiver, déboucler, réorganisation des instructions...

\subsection{À savoir:}

\begin{itemize}
\item les malloc/free (new/delete), c'est plutôt lent. Préférer d'autres méthodes d'allocations en cas de grosse demande
\item les realloc peuvent être très lents (déplacement en mémoire)
\item les appels systèmes, c'est très lent
\end{itemize}

\medskip

En C++:
Certains conteneurs sont plus lents que d'autres:
\begin{itemize}
\item utiliser le conteneur le plus adapté 
\item array, c'est bcp plus rapide que vector
\item remplir un vecteur avec un push\_back, c'est lent
\end{itemize}

Certaines choses rendent l'inlinisation impossible:
\begin{itemize}
\item les accesseurs séparés dans un autre fichier source
\item les fonctions membres \cmd{virtual}...
\end{itemize}

\subsection{Outils de profilage}

\sur{Profilage} : analyse dynamique de l'exécution d'un code.

\medskip

Outils:

\begin{itemize}
\item gprof 
\end{itemize}

\begin{itemize}
\item gcov
\end{itemize}

\begin{itemize}
\item C++ : g++ -D\_GLIBCXX\_PROFILE
\end{itemize}
{

\footnotesize

\verb!https://gcc.gnu.org/onlinedocs/libstdc++/manual/profile_mode.html!

}

\subsection{\cmd{gprof}}

\begin{itemize}
\item Calcule le temps passé dans chaque fonction, et le graphe d'appel.
\end{itemize}

\begin{itemize}
\item Le compilateur rajoute du code, qui va générer un fichier \cmd{gmon.out} contenant les informations de profilage.
\end{itemize}

\begin{itemize}
\item Inconvénient: le code ne doit pas être optimisé (-Ox) , sinon cela peut faire des choses bizarres
\begin{itemize}
\item cela ne dit pas vraiment le temps passé dans chaque fonction quand ce sera optimisé, mais cela donne néanmoins de bonnes approximations
\end{itemize}
\end{itemize}

\begin{itemize}
\item Note: le code devient notablement plus lent
\end{itemize}


\subsection{\cmd{gprof}: utilisation}

\begin{itemize}
\item Compiler avec l'option -pg
\begin{itemize}
\item attention, souvent cela fait des choses bizarres avec -Ox !
\end{itemize}
\end{itemize}

\begin{itemize}
\item Lancer le programme normalement. Il va générer le fichier \cmd{gmon.out}
\end{itemize}

\begin{itemize}
\item Une fois terminé, lancer \cmd{gprof executable}
\end{itemize}

\begin{itemize}
\item L'affichage est en 2 parties
\begin{itemize}
\item Le temps passé dans chaque fonction
\item le graphe d'appel
\end{itemize}
\end{itemize}


\subsection{\cmd{gcov}}

\begin{itemize}
\item Teste la "couverture". Pour chaque ligne, affiche le nombre de fois que la ligne a été exécutée
\end{itemize}

\begin{itemize}
\item Compiler avec \cmd{-fprofile-arcs -ftest-coverage}
\end{itemize}

\begin{itemize}
\item Exécuter le code.
\end{itemize}

\begin{itemize}
\item Exécuter \cmd{gcov \textit{fichier\_source}}
\end{itemize}

\begin{itemize}
\item Il va générer un fichier texte \textit{fichier\_source.gcov}
\end{itemize}






\section{Threads POSIX (1) Création et gestion}

\subsection{Introduction }

\begin{itemize}
\item Loi de Moore plus trop d'actualité
\item La puissance de calcul augmente maintenant (majoritairement) avec la multiplication des coeurs, des processeurs et des machines
\item Pour tirer parti des machines multicoeurs: utilisation d'algorithmes parallèles et programmes multithreadés 
\end{itemize}


Il est possible d'implémenter des algorithmes parallèles avec ce qu'on a vu jusque là, mais c'est lourd:
\begin{itemize}
\item \cmd{fork}: appel système lourd
\item chaque processus a son espace mémoire (perte de mémoire)
\item chaque processus a ses structures systèmes (table des pages, fichiers ouverts...)
\item \textit{context switch} lent
\item communication inter-processus généralement lente
\end{itemize}

\bigskip

Solution: les processus légers ("threads")

\subsection{Processus légers (\textit{threads})}

\begin{itemize}
\item Plusieurs visions et implémentations possibles
\item Introduction dans la norme POSIX en 1995 (POSIX 1.c)
\end{itemize}

\bigskip

Différence entre un thread et un processus normal:
\begin{itemize}
\item un thread est une "partie" d'un processus
\item un processus est l'exécution d'un ensemble (>=1) de threads 
\end{itemize}

\bigskip

Différence entre un ensemble de threads et un ensemble de processus:
\begin{itemize}
\item les threads partagent pratiquement tout (mémoire, pid, fichiers ouverts...)
\item la synchronisation n'est plus gérée au niveau du système, mais est laissée à l'utilisateur
\end{itemize}

\subsection{Threads: avantages et inconvénients}

Avantages et inconvénients par rapport à des processus communiquants avec les "anciens" mécanismes
\begin{itemize}
\item partage de la mémoire: mécanisme rapide de communication inter-thread
\item plus léger : moins de données système à recopier
\item plus rapide: le context-switch est plus facile
\end{itemize}

\bigskip

Les inconvénients sont (uniquement) des "difficultés" de programmation:

\begin{itemize}
\item Les threads utilisent les mêmes copies des librairies: les librairies doivent être "MT-safe"
\item Il faut gérer la synchronisation (mutex, sémaphores...)
\end{itemize}

En cas de mauvaise synchronisation:
\begin{itemize}
\item Comportement "aléatoire": bugs, segfaults, exploitations...
\item Interblocage
\end{itemize}

\subsection{}

Ordonnancement des threads (et processus):

\begin{itemize}
\item \sur{Coopératif} :
 
 Chaque thread doit explicitement rendre la main.

 Problème: si un thread plante ou ne rend pas la main, les autres threads ne s'exécutent plus.
\end{itemize}

\begin{itemize}
\item \sur{Préemptif} :
 
 Le système peut arrêter n'importe quel thread, pour switcher à un autre thread (via un mécanisme de temporisation et d'interruption matérielle)
\end{itemize}

\bigskip

L'ordonnancement des systèmes d'exploitation "modernes" se fait préemptivement (Unix, windows...). Mais l'ordonnancement coopératif peut toujours exister au niveau utilisateur.

\subsection{Modèle 1:1 (threads système ou threads noyau)}

\begin{itemize}
\item Chaque thread correspond à une entité ordonnancée par le noyau.
\end{itemize}

\begin{itemize}
\item L'ordonnancement est alors préemptive.
\end{itemize}

\begin{itemize}
\item Le comportement va être proche d'un ensemble de processus qui partagent leur mémoire et leurs données système.
\end{itemize}

\bigskip

Avantage: permet à un processus d'utiliser plusieurs coeurs

\bigskip

Implémentations de threads 1:1 : LinuxThread, NPTL


\subsection{Modèle N:1 (threads utilisateurs)}

\begin{itemize}
\item Tous les threads du processus correspondent à une entité ordonnancée par le noyau.
\end{itemize}

\begin{itemize}
\item L'ordonnancement et le \textit{switch} entre les threads se fait au niveau utilisateur
\end{itemize}


Avantage:
\begin{itemize}
\item le \textit{switch} est très rapide (pas d'appel système)
\item possibilité d'avoir énormément de threads 
\item possible même sur des systèmes légers, sans ordonanceur (systèmes embarqués)
\end{itemize}

\bigskip

Implémentations de threads N:1 : GNU Pth, State Threads


\begin{itemize}
\item Certains langages/paradigmes de programmation utilisent nativement le multi-threading
\end{itemize}

\begin{itemize}
\item C'est le cas notamment de ceux qui utilisent les \textit{coroutines}.
\end{itemize}

\begin{itemize}
\item Une implémentation naïve donnerait trop de threads, et trop de "context switchs", pour être efficacement traités par le système. 
\end{itemize}

\begin{itemize}
\item Ces threads utilisateurs légers, exécutions de coroutines, sont appelés des \textit{fibres}
\end{itemize}

\bigskip

processus / thread système / thread utilisateur / fibre


\subsection{Modèle M:N ("hybride")}

\begin{itemize}
\item Tire les avantages des modèles 1:1 et N:1
\end{itemize}

\begin{itemize}
\item Idéalement, N = nombre de coeurs
\end{itemize}

\bigskip

Exemples: GHC (Glasgow Haskell compiler), threads NetBSD...


\subsection{Threads POSIX}

Une norme POSIX pour créer des threads, et de les synchroniser

\begin{lstlisting}
#include <pthread.h>
\end{lstlisting}

Compiler avec l'option \cmd{-pthread}

\bigskip

Intègre :
\begin{itemize}
\item Fonctions pour créer, attendre et tuer un thread
\item Des mécanismes de synchronisation: mutex et variables de condition
\end{itemize}

\subsection{L'implémentation Linux de pthread}

\begin{itemize}
\item L'implémentation actuelle des threads POSIX sous Linux est NPTL (Native POSIX Threads Library). Elle respecte la norme POSIX, et rajoute quelques fonctions non POSIX.
\end{itemize}

\begin{itemize}
\item En interne, il s'agit de threads systèmes (préemptifs et 1:1).
\end{itemize}

\begin{itemize}
\item NPTL utilise des appels système à \cmd{clone()} et \cmd{futex()}, et des signaux temps réels.
\end{itemize}


\subsection{Threads POSIX : partage}

Les pthreads d'un processus partagent:
\begin{itemize}
\item le PID, le PPID
\item l'espace mémoire
\item les descripteurs de fichiers ouverts
\item les utilisateurs propriétaires
\item les handlers des signaux
\item le répertoire courant, le masque de fichiers...
\end{itemize}

Ne partagent pas:
\begin{itemize}
\item les identifiants des threads
\item la pile
\item le masque des signaux
\item \cmd{errno} ~~~ (exercice: comment cela est possible ?)
\end{itemize}

\subsection{Créer un thread}

Au départ, le processus est constitué d'un unique thread: celui qui exécute la fonction \cmd{main}

On peut créer d'autres threads, avec la fonction suivante:

\begin{lstlisting}
int pthread_create(
   pthread_t *thread,
   const pthread_attr_t *attr,
   void *(*start_routine) (void *),
   void *arg
   );
\end{lstlisting}

\begin{itemize}
\item \cmd{thread}: l'adresse mémoire où sera copié l'identifiant du nouveau thread
\item \cmd{attr}: des attributs (NULL = defaut)
\item \cmd{start\_routine}: la fonction d'entrée du thread
\item \cmd{arg}: l'argument de la fonction
\end{itemize}


Exemple:

\begin{lstlisting}
void *fonction(void *a)
{
  ...
  return NULL;
}

...
pthread_t id;
phtread_create(&id,NULL,fonction,NULL)
...
\end{lstlisting}

\subsection{Identifiant d'un pthread}

\begin{itemize}
\item Un pthread n'a pas de PID propre (ils partagent tous le même PID, celui du processus contenant les threads)
\end{itemize}

\begin{itemize}
\item L'identifiant d'un pthread est un objet du type \cmd{pthread\_t}.
\end{itemize}

\begin{itemize}
\item La norme ne dit pas ce qu'il y a dans \cmd{pthread\_t} (objet opaque).
\end{itemize}

\begin{itemize}
\item \cmd{phtread\_self()} renvoie le pthread\_t du thread courant.
\end{itemize}

\begin{itemize}
\item \cmd{phtread\_equal(pthread\_t a,pthread\_t b)} permet de comparer deux identifiants
\end{itemize}


\subsection{Argument et retour d'un pthread}

\begin{itemize}
\item Il est possible de passer un argument à la fonction qu'on appelle: un pointeur, qu'on peut faire pointer vers la structure de son choix
\end{itemize}

\begin{itemize}
\item Quand start\_routine termine, le thread se termine.
\end{itemize}

\begin{itemize}
\item Un thread peut également terminer avec pthread\_exit() 
\end{itemize}


\bigskip

\begin{itemize}
\item Le thread \cmd{main} est spécial, sa terminaison termine le processus, même si d'autres threads sont encore en exécution.
\end{itemize}

\begin{itemize}
\item exit() dans n'importe quel thread termine le processus (i.e. tous les threads)
\end{itemize}


\subsection{Fin et attente d'un thread}

Similairement à un processus, un thread renvoie un code retour : un pointeur.

\bigskip

Similairement à un fils qui devient zombi, le code retour du thread est gardée en mémoire jusqu'à ce qu'un autre thread le "rejoigne" 


\bigskip

Il n'y a pas de notion de père/fils:
\begin{itemize}
\item n'importe quel thread peut joindre n'importe quel thread
\item si plusieurs attentes du même thread: comportement indéfini
\end{itemize}


\begin{lstlisting}
int pthread_join(pthread_t thread, void **retval);
\end{lstlisting}

\bigskip

\cmd{retval}: un pointeur sur une variable (contenant un pointeur), où le code retour sera copié. 

\begin{itemize}
\item NULL: ignoré
\item thread "annulé" : \cmd{PTHREAD\_CANCELED}
\end{itemize}

\bigskip

Il existe des versions non bloquantes dans NPTL (non POSIX !) : \cmd{pthread\_tryjoin\_np}, \cmd{pthread\_timedjoin\_np}

\subsection{Détacher un thread}

Si on ne veut pas avoir à gérer la fin d'un thread, on peut le "détacher".

\begin{lstlisting}
int pthread_detach(pthread_t thread);
\end{lstlisting}

\begin{itemize}
\item La structure sera détruite à la terminaison du thread
\item Il ne sera pas possible de retrouver son pointeur retour avec \cmd{pthread\_join}
\end{itemize}


\subsection{Annuler un thread}

\begin{lstlisting}
int pthread_cancel(pthread_t thread);
\end{lstlisting}

Permet de d'"annuler" (de terminer) un thread

\bigskip

\sur{Attention}: dans beaucoup de cas, on ne peut pas simplement terminer un thread sans risquer des fuites mémoires, ou des interblocages.

\medskip

Il ne s'agit pas de "tuer" un thread: le thread doit préparer son annulation.

\medskip

Il faut faire attention:
\begin{itemize}
\item aux fuites mémoires (mémoire dynamique allouée par le thread)
\item aux sections critiques (par exemple, si le thread bloque un mutex)
\end{itemize}


Pour cela, on peut rajouter des "handlers" qui seront exécutés à l'annulation d'un thread

\begin{lstlisting}
void pthread_cleanup_push(void (*routine)(void*), void *arg);
void pthread_cleanup_pop(int execute);
\end{lstlisting}

\begin{itemize}
\item push : rajoute dans une pile une nouvelle fonction à executer en cas d'annulation
\item pop : enlève le dernier élement de la pile (et l'execute si \cmd{execute} n'est pas 0)
\end{itemize}





Le thread peut (doit) aussi dire quand il peut être annulé

\begin{lstlisting}[basicstyle=\footnotesize]
int pthread_setcancelstate(int state, int *oldstate);
int pthread_setcanceltype(int type, int *oldtype);
void pthread_testcancel(void);
\end{lstlisting}


\begin{itemize}
\item \cmd{pthread\_setcancelstate} (des)active la possibilité d'annulation du thread courant
\item \cmd{pthread\_setcanceltype} spécifie si l'annulation se fait immédiatement ou à un point d'annulation
\item \cmd{pthread\_testcancel} spécifie un point d'annulation
\end{itemize}

\subsection{Attributs }

\cmd{pthread\_attr\_t} : objet (opaque) spécifiant les attributs d'un thread.

\begin{itemize}
\item \cmd{pthread\_attr\_init} / \cmd{pthread\_attr\_destroy} : initialise (détruit) un attribut
\end{itemize}

\begin{itemize}
\item \cmd{pthread\_attr\_setstacksize} (\cmd{pthread\_attr\_setstackaddr}) permet de spécifier la taille (l'emplacement) de la pile
\end{itemize}

\begin{itemize}
\item \cmd{pthread\_attr\_setdetachstate} : spécifie l'état détaché
\end{itemize}

\begin{itemize}
\item Il est également possible de spécifier des paramètre d'ordonnancement
\end{itemize}

\subsection{Autres choses de pthread}

Des parties importantes de pthread seront vus par la suite :

\begin{itemize}
\item les \textit{mutex}
\item variables de condition
\end{itemize}

Ces mécanismes permettent de synchroniser les threads lors d'accès concurrents.


\subsection{Comportement avec les signaux}

\begin{itemize}
\item Les handlers des signaux sont partagés entre tous les threads.
\end{itemize}

\begin{itemize}
\item Mais chaque thread a son propre masque de signaux !
\end{itemize}

\begin{itemize}
\item On peut modifier le masque d'un thread via \cmd{pthread\_sigmask} (mêmes arguments que \cmd{sigprocmask}).
\end{itemize}

\begin{itemize}
\item On peut envoyer un signal à un thread spécifique via \cmd{pthread\_kill(pthread\_t id,int sig)}
\end{itemize}

\begin{itemize}
\item On peut attendre un signal avec \cmd{sigwait}
\end{itemize}

\subsection{Comportement avec \cmd{exec} et \cmd{fork}}

\begin{itemize}
\item Comportement avec \cmd{exec}: 

 Si un thread fait un appel à \cmd{exec} (qui n'échoue pas), tous les autres threads sont tués.
\end{itemize}

\begin{itemize}
\item Comportement avec \cmd{fork}:

 Seul le thread appelant fork est dupliqué.

 Problème: comme les autres threads n'existent plus dans le fils, il se peut qu'un mutex ne soit jamais libéré.

 Une solution est d'utiliser \cmd{pthread\_atfork} qui rajoute des handlers en cas de \cmd{fork}.
\end{itemize}


\subsection{Le début des problèmes...}

\begin{itemize}
\item Les threads partagent leur mémoire. Y compris le segment des données des librairies.
\end{itemize}

\begin{itemize}
\item Les (fonctions des) librairies doivent donc être prévues pour un usage multi-thread
\end{itemize}

\begin{itemize}
\item Lors de la communication par mémoire partagée, il faut aussi faire attention à ce que deux threads ne travaillent pas sur la même zone mémoire en même temps
\end{itemize}

\begin{itemize}
\item Sinon : bug, plantage, exploitation, heisenbug...
\end{itemize}

\subsection{Libraires "MT-safe"}

\begin{itemize}
\item Quand on utilise une librairie (ou une fonction d'une librairie) dans un programme multi-threadé, il faut vérifier si elle a été prévue pour une utilisation multi-threadée (MT-safe)
\end{itemize}

\begin{itemize}
\item Certaines fonctions de la libc sont MT-safe, d'autres non
\end{itemize}

\begin{itemize}
\item Il faut voir le manuel !
\end{itemize}

\bigskip

\sur{Ré-entrance} :

\begin{itemize}
\item Une fonction est appelée "re-entrante" si elle peut être interrompue, et rappelée (de façon sûre). 
\end{itemize}

\subsection{Exemple: \cmd{strtok}}

\begin{lstlisting}
#include <string.h>
char *strtok(char *str, const char *delim);
\end{lstlisting}

\cmd{strtok} coupe \cmd{str} aux caractères présents dans \cmd{delim}

\medskip

Si \cmd{str=NULL}, elle continue de découper la chaîne précédente

\begin{lstlisting}
 char w[]="2:5:6:1:2:6:3";
 char *p=strtok(w,":");
 while (p) {
  printf("%s ",p);
  p=strtok(NULL,":");
 }
\end{lstlisting}

Sortie: 2 5 6 1 2 6 3 

\bigskip

Problème (avec les programmes multithreads): strtok garde en interne un pointeur sur la position courante dans le chaîne.


Version ré-entrante: \cmd{strtok\_r}

\begin{lstlisting}
char *strtok_r(char *str, const char *delim, char **saveptr)
\end{lstlisting}

\cmd{strtok\_r} ne garde pas un pointeur interne : il faut lui en fournir un

\begin{lstlisting}
 char *tmp;
 char w[]="2:5:6:1:2:6:3";
 char *p=strtok_r(w,":",&tmp);
 while (p) {
  printf("%s ",p);
  p=strtok_r(NULL,":",&tmp);
 }
\end{lstlisting}

\subsection{Problème d'optimisation du compilateur}

\begin{lstlisting}
int i;

void *thread(void *a) {
  sleep(1);
  i=1;
}
...
pthread_create(id,NULL,thread,NULL);
i=0;
while(i==0) { usleep(1000); }
...
\end{lstlisting}

Avec trop d'optimisations, le compilateur peut considérer que \cmd{i} reste à 0, car jamais affectée à autre chose que 0 dans main.

\medskip

Modificateur du C : \cmd{volatile}. Indique au compilateur qu'une variable peut changer entre ses différents accès.

\subsection{Problèmes de synchronisation}

Un thread peut être arrêté n'importe quand pour laisser sa place à un autre thread:
\begin{itemize}
\item y compris au milieu d'une ligne
\item y compris au milieu d'une instruction basique en C (ex: \cmd{i++})
\end{itemize}

\medskip

Problème: si un thread A travaille sur une zone mémoire M, et est arrêté alors que M est inconsistante,
le thread B trouvera M en état inconsistant.

\begin{itemize}
\item Comportement imprévisible !
\end{itemize}


\begin{lstlisting}
long long z=0;

void* th(void *r) {
  for(long long a=0;a<1000000;a++)
    z++;
}

int main() {
  pthread_t id1,id2;
  pthread_create(&id1,NULL,th,NULL);
  pthread_create(&id2,NULL,th,NULL);
  pthread_join(id1,NULL);
  pthread_join(id2,NULL);
  printf("%Ld\n",z);
}
\end{lstlisting}

sortie: 948249

\subsection{Atomicité}

Code assembleur de \cmd{z++}:

\begin{lstlisting}
        movq    z(%rip), %rax
        addq    $1, %rax
        movq    %rax, z(%rip)
\end{lstlisting}

On aimerait que ces 3 instructions ne puissent être interrompues.

\bigskip

Instruction(s) \sur{atomique} : instruction(s) ne pouvant être interrompues.

Mais: il n'est pas possible de bloquer les interruptions dans le mode utilisateur.

\bigskip

Pour rendre atomique (vis à vis des autres threads) une accès sur une zone mémoire: mécanisme d'exclusion mutuelle (mutex)

C'est le sujet du prochain cours !


\section{Threads (2) Synchronisation des processus concurrents : mutex}

\subsection{Introduction}

Les threads partagent leur mémoire.

\bigskip

Le partage de mémoire est généralement voulu et avantageux:
\begin{itemize}
\item cela évite de gaspiller de la mémoire
\item c'est un mécanisme de communication inter-thread (et inter-processus) très rapide
\end{itemize}


L'important est de bien savoir gérer l'accès concurrent à la mémoire

\bigskip

(Rappel: il faut faire attention aux fonctions/librairies non réentrantes, ou non "MT-safe")

\subsection{Un exemple pour commencer...}

Un thread peut être arrêté n'importe quand pour laisser sa place à un autre thread:
\begin{itemize}
\item y compris au milieu d'une ligne
\end{itemize}
\begin{itemize}
\item y compris au milieu d'une instruction basique en C (ex: \cmd{i++})
\end{itemize}

\medskip

Problème: si un thread A travaille sur une zone mémoire M, et est arrêté alors que M est inconsistante,
le thread B trouvera M en état inconsistant.


\begin{itemize}
\item Comportement imprévisible ! (bug, plantage, exploitation,\pause

 mauvaise note)
\end{itemize}


\begin{lstlisting}
long long z=0;

void* th(void *r) {
  for(long long a=0;a<1000000;a++)
    z++;
}

int main() {
  pthread_t id1,id2;
  pthread_create(&id1,NULL,th,NULL);
  pthread_create(&id2,NULL,th,NULL);
  pthread_join(id1,NULL);
  pthread_join(id2,NULL);
  printf("%Ld\n",z);
}
\end{lstlisting}


sortie: 1020102 \pause
ou 1271305 \pause
ou 948249...


\subsection{Atomicité}

Code assembleur de \cmd{z++}:

\begin{lstlisting}
        movq    z(%rip), %rax
        addq    $1, %rax
        movq    %rax, z(%rip)
\end{lstlisting}


On aimerait que ces 3 instructions ne puissent être interrompues.

\bigskip

\bigskip

Instruction(s) \sur{atomique} : instruction(s) ne pouvant être interrompues.

\bigskip

Pour que l'exemple précédent soit correct, il faudrait rentre l'instruction \cmd{z++} atomique.

\subsection{Atomicité d'\sur{une} instruction}

L'atomicité peut se faire au niveau du processeur.

\bigskip

Il faut distinguer 2 choses:

\begin{itemize}
\item Atomicité vis à vis d'une interruption

 \sur{Une} instruction processeur est atomique vis à vis d'une interruption. 
\end{itemize}


\begin{itemize}
\item Atomicité vis à vis des autres coeurs

 Dans les ordinateurs multiprocesseurs et/ou multicoeurs, du fait de la pipeline, une variable peut changer entre sa lecture et son écriture. Elle n'est donc pas (par défaut) atomique vis à vis des autres coeurs .

 \pause Sur x86: on peut rendre atomique \sur{une} instruction machine avec le préfixe \cmd{lock}.
\end{itemize}


\subsection{Atomicité d'une instruction: exemple}

Pour que le programme précédent fonctionne comme souhaité

\begin{itemize}
\item On peut incrémenter \cmd{z} avec l'instruction assembleur \cmd{incq}

 \pause $\Rightarrow$ l'opération sera atomique vis a vis des interruptions.

 \pause $\Rightarrow$ le programme fonctionnera correctement si la machine a un unique coeur.
\end{itemize}



\begin{itemize}
\item Pour que le programme soit "correct" dans le cas général:

 Il faut rendre atomique l'instruction: \cmd{lock incq}

 $\Rightarrow$ le programme fonctionne comme souhaité.

 \medskip
 
 \pause Problème: Du fait que la pipeline ne sert presque plus, c'est beaucoup plus lent...
\end{itemize}



\subsection{Atomicité d'un ensemble d'instructions}

En pratique, les opérations sur une zone mémoire prennent généralement plusieurs instructions

\bigskip

Problèmes:

\begin{itemize}
\item Il n'est pas possible (ni raisonnable) de bloquer les interruptions / les autres coeurs dans le mode utilisateur.
\item Pourquoi? \pause
 Un processus malveillant/planté/bogué pourrait bloquer tous les autres processus...
\end{itemize}
\begin{itemize}
\item Il n'est pas possible d'utiliser un mécanisme du type \cmd{lock} sur un ensemble d'instructions
\end{itemize}


De toutes façons: on ne veut pas l'atomicité d'un ensemble d'instructions...


Cela bloquerait tous les coeurs pour accéder à une zone mémoire, alors que les autres ne travaillent pas forcement sur cette zone...


\bigskip

La bonne solution n'est pas d'avoir des sections atomiques, mais des sections où on a l'exclusivité sur une partie de la mémoire.


\bigskip

Cela s'appelle une \sur{section critique}.



\subsection{Sections critiques}

Une section critique est une section du code où il n'y a au maximum qu'un thread à la fois

\bigskip

\bigskip

Si un thread B veut rentrer dans une section critique, et qu'un autre thread A est déjà dans la section critique, on doit faire attendre le thread B jusqu'à ce que le thread A sorte de la section critique.



\begin{tikzpicture}[scale=.5]
\draw (-.5,0) node[left]{Thread $A$} ;
\draw (0,0) -- (2,0) ;
\coordinate (A1) at (-2,3) ;
\draw (A1) node[above,text width=3cm,]{\scriptsize $A$ demande à rentrer dans la section critique} ;
\draw[->,shorten >= 3pt] (A1) -- (2,0) ;

\coordinate (B1) at (-3,-4) ;
\draw (B1) node[below,text width=3cm,]{\scriptsize $B$ demande à rentrer dans la section critique} ;
\draw[->,shorten >= 3pt] (B1) -- (3,-2) ;

\draw [fill=red] (2.0,-0.5) rectangle (7,0.5);
\draw (7,0) -- (12,0) ;

\coordinate (A2) at (9,3) ;
\draw (A2) node[above,text width=3cm,]{\scriptsize $A$ sort de la section critique} ;
\draw[->,shorten >= 3pt] (A2) -- (7,0) ;

\coordinate (B2) at (5,-4) ;
\draw (B2) node[below,text width=3cm,]{\scriptsize $B$ rentre dans la section critique} ;
\draw[->,shorten >= 3pt] (B2) -- (7,-2) ;

\coordinate (B3) at (12,-4) ;
\draw (B3) node[below,text width=3cm,]{\scriptsize $B$ sort de la section critique} ;
\draw[->,shorten >= 3pt] (B3) -- (10,-2) ;

\draw (-.5,-2) node[left]{Thread $B$} ;
\draw (0,-2) -- (3,-2) ;
\draw[dotted] (3,-2) -- (7,-2) ;
\draw [fill=red] (7.0,-2.5) rectangle (10,-1.5);
\draw (10,-2) -- (12,-2) ;

\draw (5,-7) node[left]{Temps $\Rightarrow$} ;
\end{tikzpicture}


Avantage:
\begin{itemize}
\item on ne bloque pas les autres threads qui ne travaillent pas sur la section critique
\item il peut y avoir plusieurs sections critiques différentes, qui n'interfèrent pas entre elles.
\end{itemize}


Il faut un mécanisme pour entrer et sortir des sections critiques.

\bigskip


Ce qu'on attend d'un mécanisme de gestion des sections critiques:
\begin{itemize}
\item \sur{l'exclusion mutuelle}: deux threads ne sont pas en même temps dans la section critique
\end{itemize}
\begin{itemize}
\item \sur{la progression}: le processus continue de progresser dans tous les cas possibles d'exécution
\end{itemize}
\begin{itemize}
\item \sur{l'attente bornée}: un thread qui demande à rentrer dans une section critique ne va pas attendre indéfiniment
\end{itemize}



Ce n'est pas un problème trivial. Plusieurs solutions fausses ont été publiées 


\bigskip

Les problèmes en cas de mauvaise gestion des sections critiques:

\begin{itemize}
\item Si l'exclusion mutuelle est pas respectée:

 \sur{Situation de compétition} (race condition): deux threads sont dans une section critique en même temps: non déterminisme (bug, plantage, exploitation...)
\end{itemize}
\begin{itemize}
\item Si la progression n'est pas respectée:

 \sur{Interblocage} (deadlock) : le processus est bloqué.
\end{itemize}
\begin{itemize}
\item Si l'attente bornée n'est pas respectée:

 \sur{Famine} (starvation) : un thread ne voit jamais sa demande aboutir
\end{itemize}


\subsection{Exemple simple: 2 threads}

Solution 1 (?)

\medskip

\begin{lstlisting}
int intA=0,intB=0;
\end{lstlisting}
\begin{minipage}[t]{0.49\textwidth}
Thread A:
\begin{lstlisting}
while(1) {
 while(intB) /*wait*/;
 intA=1;
 //sect. critique
 intA=0;
 //sect. normale
}
\end{lstlisting}
\end{minipage}\vline\hspace*{1mm}
\begin{minipage}[t]{0.47\textwidth}
Thread B:
\begin{lstlisting}
while(1) {
 while(intA) /*wait*/;
 intB=1;
 //sect. critique
 intB=0;
 //sect. normale
}
\end{lstlisting}
\end{minipage}

\bigskip
Correct ?

Non ! Les 2 threads peuvent être dans la section critique en même temps (situation de compétition)



Solution 2 (?)

\medskip

\begin{lstlisting}
int intA=0,intB=0;
\end{lstlisting}
\begin{minipage}[t]{0.49\textwidth}
Thread A:
\begin{lstlisting}
while(1) {
 intA=1;
 while(intB) /*wait*/;
 //sect. critique
 intA=0;
 //sect. normale
}
\end{lstlisting}
\end{minipage}\vline\hspace*{1mm}
\begin{minipage}[t]{0.47\textwidth}
Thread B:
\begin{lstlisting}
while(1) {
 intB=1;
 while(intA) /*wait*/;
 //sect. critique
 intB=0;
 //sect. normale
}
\end{lstlisting}
\end{minipage}

\bigskip
Correct ?

Non ! Les 2 threads peuvent se bloquer mutuellement (interblocage)


Solution 3 (?)

\medskip

\begin{lstlisting}
int rnd=0;
\end{lstlisting}
\begin{minipage}[t]{0.48\textwidth}
Thread A:
\begin{lstlisting}[basicstyle=\small]
while(1) {
 while(rnd!=0) /*wait*/;
 //sect. critique
 rnd=1;
 //sect. normale
}
\end{lstlisting}
\end{minipage}\vline\hspace*{1mm}
\begin{minipage}[t]{0.48\textwidth}
Thread B:
\begin{lstlisting}[basicstyle=\small]
while(1) {
 while(rnd!=1) /*wait*/;
 //sect. critique
 rnd=0;
 //sect. normale
}
\end{lstlisting}
\end{minipage}

\bigskip
Correct ?

Non ! Quand le thread A termine, B est bloqué indéfiniment (famine)


Solution 4 (?)

\medskip

\begin{lstlisting}[basicstyle=\small]
int rnd=0;
int intA=0,intB=0;
\end{lstlisting}
\begin{minipage}[t]{0.49\textwidth}
Thread A:
\begin{lstlisting}[basicstyle=\small]
while(1) {
 intA=1;
 rnd=1;
 while(intB && rnd==1)
    /*wait*/;
 //sect. critique
 intA=0;
 //sect. normale
}
\end{lstlisting}
\end{minipage}\vline\hspace*{1mm}
\begin{minipage}[t]{0.47\textwidth}
Thread B:
\begin{lstlisting}[basicstyle=\small]
while(1) {
 intB=1;
 rnd=0;
 while(intA && rnd==0)
    /*wait*/;
 //sect. critique
 intB=0;
 //sect. normale
}
\end{lstlisting}
\end{minipage}

\bigskip
Correct ?

Oui ! (Solution de Peterson)


\subsection{Attente active et passive}

L'attente avant d'entrer dans une section critique peut être:

\begin{itemize}
\item \sur{active} (\textit{spinlock}): le thread continue de tourner jusqu'à ce qu'il a le droit d'entrer dans la section critique

 \pause Dans l'exemple précédent (Peterson), l'attente est active
\end{itemize}


\begin{itemize}
\item \sur{passive} : le thread est mis en pause jusqu'à ce qu'il a la possibilité de rentrer dans la section critique

 \pause Dans ce cas, il faut interférer avec l'ordonnanceur

 \pause Avantage : on laisse le temps CPU aux autres threads qui peuvent faire des choses plus constructives
\end{itemize}

\bigskip

En général, on préfère l'attente passive. (Mais dans certains cas très particuliers, l'attente active peut être plus avantageuse.)

\subsection{Les primitives}

En général, on ne reprogramme pas soi même les tests d'entrée dans une section critique.

\begin{itemize}
\item C'est fastidieux \pause
\item le risque d'erreur est très important \pause
\item on ne tire pas parti des possibilités de l'OS.
\end{itemize}


On passe par des primitives (du langage, de librairies et/ou du système): des \sur{verrous}.


Il existe différents types de verrous:
\begin{itemize}
\item sémaphores (POSIX 1.b)
\item mutex (pthreads)
\item rwlocks (pthreads)
\item barrières (pthreads)
\item variables de condition / moniteurs (pthreads)
\end{itemize}






\bigskip

\sur{Attention} ! Les verrous proposés par les langages/systèmes ne sont que des primitives (pour simplifier la vie).

\bigskip

Une mauvaise utilisation peut toujours mener à des problèmes: situation de competition, interblocage ou famine...

\subsection{Verrou le plus simple : le mutex}

\sur{Mutex}: assure qu'au plus un thread est dans la section critique à un moment donné.

\bigskip

Pseudo-code:
\medskip

\begin{lstlisting}
mutex m;

//section non critique
lock(m);
//section critique;
unlock(m);
//section non critique
..
\end{lstlisting}


\begin{tikzpicture}[scale=.5]
\draw (-.5,0) node[left]{Thread $A$} ;
\draw (0,0) -- (2,0) ;
\coordinate (A1) at (-2,3) ;
\draw (A1) node[above,text width=3cm,]{\scriptsize $A$ exécute \cmd{lock(m)} et entre dans la section critique} ;
\draw[->,shorten >= 3pt] (A1) -- (2,0) ;

\coordinate (B1) at (-3,-4) ;
\draw (B1) node[below,text width=3cm,]{\scriptsize $B$ exécute \cmd{lock(m)}} ;
\draw[->,shorten >= 3pt] (B1) -- (3,-2) ;

\draw [fill=red] (2.0,-0.5) rectangle (7,0.5);
\draw (7,0) -- (12,0) ;

\coordinate (A2) at (9,3) ;
\draw (A2) node[above,text width=3cm,]{\scriptsize $A$ exécute \cmd{unlock(m)} et sort de la section critique} ;
\draw[->,shorten >= 3pt] (A2) -- (7,0) ;

\coordinate (B2) at (5,-4) ;
\draw (B2) node[below,text width=3cm,]{\scriptsize $B$ rentre dans la section critique} ;
\draw[->,shorten >= 3pt] (B2) -- (7,-2) ;

\coordinate (B3) at (12,-4) ;
\draw (B3) node[below,text width=3cm,]{\scriptsize $B$ exécute \cmd{unlock(m)} et sort de la section critique} ;
\draw[->,shorten >= 3pt] (B3) -- (10,-2) ;

\draw (-.5,-2) node[left]{Thread $B$} ;
\draw (0,-2) -- (3,-2) ;
\draw[dotted] (3,-2) -- (7,-2) ;
\draw [fill=red] (7.0,-2.5) rectangle (10,-1.5);
\draw (10,-2) -- (12,-2) ;

\draw (5,-7) node[left]{Temps $\Rightarrow$} ;
\end{tikzpicture}

\subsection{Les mutex de \cmd{pthreads}}

\begin{lstlisting}[basicstyle=\footnotesize]
#include <pthread.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *mutexattr);
int pthread_mutex_destroy(pthread_mutex_t *mutex);

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);

int pthread_mutex_unlock(pthread_mutex_t *mutex);
\end{lstlisting}

Exemple:

\begin{lstlisting}[basicstyle=\footnotesize]
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&mutex);
//section critique
pthread_mutex_unlock(&mutex);
\end{lstlisting}


Note :

\begin{itemize}
\item Deux façons d'initialiser un mutex : 
\end{itemize}
\begin{lstlisting}[basicstyle=\footnotesize]
   pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
\end{lstlisting}
ou
\begin{lstlisting}[basicstyle=\footnotesize]
   pthread_mutex_t mutex;
   pthread_mutex_init(&mutex,NULL);
\end{lstlisting}


\begin{itemize}
\item \cmd{mutexattr} permet d'initialiser un mutex avec d'autres attributs que ceux par défaut (récursif, partagé...).

 NULL = défaut
\end{itemize}


\begin{itemize}
\item \cmd{trylock} essaye de bloquer le mutex. Si il échoue, il renvoie directement la main avec une erreur (retour $\ne 0$)
\end{itemize}

\subsection{Implémentation d'un mutex (?)}

Ici, un mutex est un entier.

\begin{lstlisting}
int a=1;

lock(int &a) {
 while(a==0) /*wait*/;
 a=0;
}

unlock(int &a) {
 a=1;
}
\end{lstlisting}

\bigskip

Problème : pour que ce soit correct, le test et l'affectation doivent se faire atomiquement



\subsection{Implémentation possible d'un mutex }

\begin{lstlisting}
int a=0;

lock(int &a) {
 int tmp=0;
 while(1) {
  xchg(a,tmp);
  if(tmp==1) break;
 }
}

unlock(int &a) {
 a=1;
}
\end{lstlisting}

\bigskip
\cmd{xchg(a,b)} échange (atomiquement) a et b. (instruction x86)


\begin{itemize}
\item Problème: attente active et possible famine
\end{itemize}


\subsection{Pseudo-implémentation idéale d'un mutex }

\begin{lstlisting}[basicstyle=\footnotesize]
int libre=1;
queue liste_attente;

lock() { //atomiquement
 while(1) {
  if(libre) {
   libre=0;
   return;
  }
  liste_attente.push(thread_courant());
  wait();
 }
}

unlock() { //atomiquement
 if(liste_attente.non_vide())
   signal(liste_attente.pop());
 else
   libre=1;
}
\end{lstlisting}


\subsection{Où sont implémentés les verrous ?}


Problème des verrous en mode utilisateur: %l'attente est active, et il faut ses propres files d'attentes / ordonanceurs
\begin{itemize}
\item pour éviter l'attente active, il faut jouer avec l'ordonnanceur
\item pour éviter les famines, il faut une file d'attente
\end{itemize}


Ces taches sont souvent laissées aux OS

\bigskip


Problème des verrous en mode noyau: les appels systèmes sont très lents !


\bigskip

Bon compromis: combiner les deux





\subsection{Implémentation dans NPTL}

\begin{itemize}
\item \cmd{lock()} sur un verrou libre: opération atomique
\end{itemize}

\begin{itemize}
\item \cmd{lock()} sur un verrou non libre: opération atomique +

 appel système (\cmd{futex()}) qui met le thread en pause, et rajoute à une liste d'attente
\end{itemize}


\begin{itemize}
\item \cmd{unlock()} : opération atomique +

 (si la liste d'attente est non vide) appel système à \cmd{futex} pour libérer le thread suivant.
\end{itemize}

\bigskip

\begin{itemize}
\item coté utilisateur: un boléen (libre ou non) et le nombre de threads en attente
\end{itemize}

\begin{itemize}
\item coté système: une liste d'attente
\end{itemize}

\subsection{Mutex récursif}

NPTL (et d'autres implémetations) introduisent d'autres possibilités (non POSIX, "non portables"). Par exemple:

\begin{itemize}
\item mutex récursif: l'action de bloquer un mutex déjà bloqué par le thread courant ne bloque pas. Exemple:
\end{itemize}

\begin{lstlisting}
    foo(int i)
    {
      lock(mutex);
      // section critique
      if(i>0) foo(i-1);
      // section critique
      unlock(mutex);
    }
\end{lstlisting}


\subsection{Read-write locks}

On pourrait permettre à plusieurs threads qui ne modifient pas la mémoire, de travailler (en lecture seule) sur une zone mémoire.

\bigskip

Une solution: read-write locks (rwlocks)

\medskip

Deux types de sections critiques
\begin{itemize}
\item les sections critiques en lecture seule (celles des lecteurs)
\item les sections critiques en lecture/écriture (celles des écrivains)
\end{itemize}


Garantie des rwlocks :
\begin{itemize}
\item si un thread est dans une section critique en lecture/écriture, il n'y a aucun autre thread dans une section critique (ni en lecture seule, ni en lecture/écriture) \pause
\item (si aucun thread est dans une section critique en lecture/écriture, il n'y a pas de limite sur le nombre de threads dans une section critique en lecture seule)
\end{itemize}

\bigskip

Attention : on peut facilement arriver à des famines
\begin{itemize}
\item préférer les lecteurs : il peut y avoir famine des écrivains
\item préférer les écrivains : il peut y avoir famine des lecteurs
\end{itemize}



\subsection{Les rwlocks de \cmd{pthreads}}

\begin{lstlisting}[basicstyle=\footnotesize]
#include <pthread.h>

pthread_rwlock_t lock = PTHREAD_RWLOCK_INITIALIZER;

int pthread_rwlock_init(pthread_rwlock_t * restrict lock, const pthread_rwlockattr_t * restrict attr);
int pthread_rwlock_destroy(pthread_rwlock_t *lock);

int pthread_rwlock_rdlock(pthread_rwlock_t *lock);
int pthread_rwlock_tryrdlock(pthread_rwlock_t *lock);
int pthread_rwlock_timedrdlock(pthread_rwlock_t * restrict lock, const struct timespec * restrict abstime);

int pthread_rwlock_wrlock(pthread_rwlock_t *lock);
int pthread_rwlock_trywrlock(pthread_rwlock_t *lock);
int pthread_rwlock_timedwrlock(pthread_rwlock_t * restrict lock, const struct timespec * restrict abstime);

int pthread_rwlock_unlock(pthread_rwlock_t *lock);
\end{lstlisting}

\subsection{Les barrières }

Les barrières permettent de synchroniser les threads

\bigskip

\begin{tikzpicture}[scale=.5]
\draw (-.5,0) node[left]{Thread $A$} ;
\draw (0,0) -- (5,0) ;
\draw[dotted] (5,0) -- (8,0) ;
\draw (8,0) -- (12,0) ;
\draw (-.5,-2) node[left]{Thread $B$} ;
\draw (0,-2) -- (3,-2) ;
\draw[dotted] (3,-2) -- (8,-2) ;
\draw (8,-2) -- (12,-2) ;
\draw (-.5,-4) node[left]{Thread $C$} ;
\draw (0,-4) -- (8,-4) ;
\draw (8,-4) -- (12,-4) ;

\draw[dotted] (8,.5) -- (8,-4.5) ;

\coordinate (A1) at (5,3) ;
\coordinate (B1) at (-2,3) ;
\coordinate (C1) at (12,3) ;

\draw (A1) node[above,text width=1.5cm,]{\scriptsize $A$ attend} ;
\draw[->,shorten >= 3pt] (A1) -- (5,0) ;
\draw (B1) node[above,text width=1.5cm,]{\scriptsize $B$ attend} ;
\draw[->,shorten >= 3pt] (B1) -- (3,-2) ;
\draw (C1) node[above,text width=1.5cm,]{\scriptsize $C$ attend} ;
\draw[->,shorten >= 3pt] (C1) -- (8,-4) ;

\draw (5,-6) node[left]{Temps $\Rightarrow$} ;
\end{tikzpicture}

\subsection{Les barrières POSIX}

\begin{lstlisting}[basicstyle=\footnotesize]
int pthread_barrier_init(pthread_barrier_t *restrict barrier, const pthread_barrierattr_t *restrict attr, unsigned count);
int pthread_barrier_destroy(pthread_barrier_t *barrier);
int pthread_barrier_wait(pthread_barrier_t *barrier);
\end{lstlisting}

\begin{itemize}
\item \cmd{count} : nombre de threads qui doivent attendre à la barrière
\end{itemize}


Exemple:

\begin{lstlisting}[basicstyle=\footnotesize]
pthread_barrier_t barrier;
pthread_barrier_init(&barrier,NULL,3);
\end{lstlisting}

Puis dans chaque thread (A, B et C):

\begin{lstlisting}[basicstyle=\footnotesize]
// section non synchronisee
pthread_barrier_wait(&barrier);
// section synchronisee
\end{lstlisting}

\subsection{Problèmes : vitesse}

Le but des programmes parallèles est de gagner en vitesse.

\bigskip

En utilisant les mécanismes précédents (mutex...) un processus peut perdre du temps: \pause
\begin{itemize}
\item dans les attentes qu'un verrou se libère (attente active ou passive) \pause
\item dans les instructions atomiques (plus lentes à cause de problèmes de cache) \pause 
\item dans les appels systèmes relatifs aux (dé)blocage de verrous
\end{itemize}


Solutions:
\begin{itemize}
\item limiter la taille des sections critiques \pause
\item séparer les zones mémoires partagés

 (idéalement: 1 zone mémoire = 1 verrou) \pause
\item mais sans faire trop d'entrées/sorties de sections critiques
\end{itemize}

\bigskip

Un problème d'échelle (de granularité) peut parfois se poser
\begin{itemize}
\item trouver le bon compromis
\end{itemize}



Exemple (bidon)

$$\sigma(n) = \sum_{1\le i\le n : i|n} i$$

\begin{lstlisting}[basicstyle=\footnotesize]
long long n,s=0;
pthread_mutex_t m=PTHREAD_MUTEX_INITIALIZER;

void* th(void *r) {
  for(long long i=(long long)r;i<=n;i+=2)
    if(i%n==0) {
      pthread_mutex_lock(&m);
      s+=i;
      pthread_mutex_unlock(&m);
    }
  return NULL;
}
\end{lstlisting}


Mieux:

\begin{lstlisting}[basicstyle=\footnotesize]
long long n,s=0;
pthread_mutex_t m=PTHREAD_MUTEX_INITIALIZER;

void* th(void *r) {
  long long tmp=0;
  for(long long i=(long long)r;i<=n;i+=2)
     if(i%n==0)
       tmp+=i;
  pthread_mutex_lock(&m);
  s+=tmp;
  pthread_mutex_unlock(&m);
  return NULL;
}

\end{lstlisting}


\begin{itemize}
\item plus d'opérations de calcul (ici, 2 additions en plus)
\item mais beaucoup moins de sections critiques
\end{itemize}

\subsection{Gros problèmes}

En cas de mauvaise gestion des sections critiques: 

\begin{itemize}
\item situation de compétition : bugs, plantages, \pause
 morts (Therac-25) \pause
\item interblocage
\end{itemize}

\medskip

Si on protège chaque section critique par un verrou adéquat, l'exclusion mutuelle devrait être respectée.
Le problème sera généralement l'interblocage

\subsection{}

Suite:
\begin{itemize}
\item Les 5 philosophes...
\item Sémaphores
\item Variables de condition (Moniteurs)
\item Gérer les interblocages
\item Concurrence en C++11
\end{itemize}

~
\section{Threads (3) : Sémaphores et variables de condition}

\subsection{Introduction }

\begin{itemize}
\item Les threads partagent leur mémoire
\item Il faut protéger les accès mémoires concurrents
\item Les mutex sont des verrous qui permettent de délimiter des sections critiques
\item Mais des fois, les mutex ne suffisent pas...
\end{itemize}

On va voir:
\begin{itemize}
\item Les sémaphores
\item Les variables de conditions
\end{itemize}


\subsection{Problème classique: 5 philosophes}

\begin{itemize}
\item 5 philosophes sont autour d'une table ronde\pause
\item Il y a une baguette entre chaque philosophe (i.e.: une baguette pour deux philosophes)\pause
\item Un plat de sushis pour tout le monde est au centre\pause
\item La vie d'un philosophe se résume à deux actions : penser et manger\pause
\item Pour manger, il doit prendre les 2 baguettes (à sa gauche et à sa droite), puis il peut commencer à manger\pause
\item Quand il a fini, il repose les baguettes et peut commencer à penser
\end{itemize}

\begin{itemize}
\item Chaque baguette: une ressource (un mutex)
\end{itemize}

But:

\begin{itemize}
\item Tout le monde doit pouvoir manger (pas de famine)
\item Limiter les attentes
\end{itemize}


\begin{lstlisting}
mutex baguette[5];

void *philosophe(void *a)
{
  int i=(long long) a;
  while(1) {
    printf("%d pense\n",i);
    lock(&baguette[i]);
    lock(&baguette[(i+1)%5]);
    printf("%d mange\n",i);
    unlock(&baguette[i]);
    unlock(&baguette[(i+1)%5]);
  }
}

\end{lstlisting}

Correct ?


Non : interblocage. Si tout le monde a la baguette à gauche, tout le monde est bloqué


\subsection{5 philosophes : solution ?}

\begin{lstlisting}[basicstyle=\small]
mutex baguette[5],general;

void *philosophe(void *a)
{
  int i=(long long) a;
  while(1) {
    printf("%d pense\n",i);
    lock(&general);
    lock(&baguette[i]);
    lock(&baguette[(i+1)%5]);
    printf("%d mange\n",i);
    unlock(&baguette[i]);
    unlock(&baguette[(i+1)%5]);
    unlock(&general);
  }
}
\end{lstlisting}


Correct... mais qu'un seul philosophe mange à la fois.
Les mutex baguette[i] ne servent à rien $\rightarrow$ une seule section critique

\begin{lstlisting}[basicstyle=\small]
mutex baguette[5],general;

void *philosophe(void *a)
{
  int i=(long long) a;
  while(1) {
    printf("%d pense\n",i);
    lock(&general);
    lock(&baguette[i]);
    lock(&baguette[(i+1)%5]);
    unlock(&general);
    printf("%d mange\n",i);
    unlock(&baguette[i]);
    unlock(&baguette[(i+1)%5]);
  }
}
\end{lstlisting}


Mieux... mais un philosophe doit des fois attendre inutilement pour manger.


\begin{lstlisting}[basicstyle=\small]
void *philosophe(void *a)
{
  int i=(long long) a;
  while(1) {
    printf("%d pense\n",i);
    while(1) {
      lock(&general);
      if(baguette[i]==1 && baguette[(i+1)%5]==1) {
       baguette[i]=baguette[(i+1)%5]=0;
       unlock(&general);
       break;
      }
      unlock(&general);
    }
    printf("%d mange\n",i);
    baguette[i]=baguette[(i+1)%5]=1;
 }
}
\end{lstlisting}


Attente active et famine...

\subsection{Parenthèse: Famine ?}

On peut distinguer deux types de famines:\pause
\begin{itemize}
\item la famine "avérée" : un thread est indéfiniment bloqué (quelle que soit le déroulement de la suite)\pause
\item la famine "probabiliste" : il y a une probabilité non nulle qu'un thread reste bloqué indéfiniment longtemps.
\end{itemize}

\bigskip

Si on s'autorise la famine "avérée", il existe une solution simple aux 5 philosophes sans interblocage, ni situation de compétition:\pause

\begin{itemize}
\item On désigne un philosophe qui n'a pas le droit de prendre de baguettes (donc ni de manger et penser)
\end{itemize}


Si on s'autorise la famine "probabiliste" (mais pas "avérée"), la solution précédente est bonne (modulo le fait qu'elle soit en attente active)


\bigskip

Note:
\begin{itemize}
\item La famine est, des fois, pas très grave (e.g. si les threads font le même travail).
\item Beaucoup considèrent que la famine probabiliste n'est pas un vrai problème.
\end{itemize}

\bigskip

Ordre d'importance:

famine "probabiliste" / famine "avérée" / interblocage / situation de compétition


\subsection{5 philosophes : solution ?}

Plusieurs (idées) de solutions

\begin{itemize}
\item Contre l'attente active: rajouter des temporisations aléatoires
\begin{itemize}
\item bricolage: pas optimal (et toujours possible famine)
\end{itemize}
\end{itemize}


\begin{itemize}
\item Prendre une baguette (lock), essayer de prendre l'autre (trylock). Si la deuxième n'est pas disponible, reposer la première (unlock) et recommencer.
\begin{itemize}
\item attente active (et possible famine)
\end{itemize}
\end{itemize}


\begin{itemize}
\item Prendre une baguette (lock), essayer de prendre l'autre (trylock). Si la deuxième n'est pas disponible, reposer la première (unlock) et recommencer \sur{dans le sens contraire}.
\begin{itemize}
\item (possible famine)
\end{itemize}
\end{itemize}


Note : si les philosophes sont sur une table linéaire (5 philosophes, 6 baguettes), la solution triviale marche.


\bigskip

Ce qui pose problème: les cycles


\bigskip

Solution: casser les cycles

\begin{lstlisting}[basicstyle=\small]
void *philosophe(void *a)
{
  int i=(long long) a;
  while(1) {
    printf("%d pense\n",i);
    if(i==0) {
     lock(&baguette[(i+1)%5]);
     lock(&baguette[i]);
    } else {
     lock(&baguette[i]);
     lock(&baguette[(i+1)%5]);
    }
    printf("%d mange\n",i);
    unlock(&baguette[i]);
    unlock(&baguette[(i+1)%5]);
  }
}
\end{lstlisting}


Correct. Mais pas très joli, et l'asymétrie introduit des biais (des philosophes attendent plus que d'autres en moyenne)

\subsection{5 philosophes: Solution de  Dijkstra}


On limite à 4 le nombre de philosophes qui peuvent rentrer dans la phase "prendre des baguettes"\pause
\begin{itemize}
\item au plus 4 arcs dans le graphe $\Rightarrow$ pas de cycle.
\end{itemize}

\bigskip

Principe des \sur{sémaphores}.

\bigskip

(Exercice: est il possible que le 5ème philosophe attende inutilement ?)

\medskip


(Exercice: combien, au minimum, faut-il autoriser de philosophes dans la phase "prendre des baguettes" pour qu'il n'y ait pas d'attente inutile ?)

\subsection{Les sémaphores}

Un autre type de verrou est le \sur{sémaphore}
\begin{itemize}
\item Introduit par Dijkstra ($\sim$ 1963) \pause
\item Premier verrou à apparaître dans un vrai système \pause
\item Plus général qu'un mutex \pause
\item (Mais il a plutôt un intérêt historique et, ici, didactique) \pause
\end{itemize}

\bigskip

\begin{itemize}
\item 3 opérations:
\begin{itemize}
\item init(N) : initialise le sémaphore à N "ressources"
\item P() (ou wait(), ou down()): demande une ressource. Si il n'y a plus de ressource libre, attend jusqu'à ce qu'une ressource se libère
\item V() (ou signal(), ou post(), ou up()): libère une ressource
\end{itemize}
\end{itemize}


\begin{itemize}
\item garantie: au plus N threads possèdent une "ressource"
\end{itemize}

\subsection{Sémaphore: différence avec un mutex}

\begin{itemize}
\item Un sémaphore avec N=1 simule (un peu près) un mutex
\end{itemize}

\begin{itemize}
\item (Un sémaphore avec N=1 est un \sur{sémaphore binaire})\pause
\end{itemize}

\begin{itemize}
\item Mais: le mutex est un booléen, le sémaphore est un entier
\begin{itemize}
\item unlock();unlock(); n'aura pas le même comportement que V();V();
\end{itemize}
\end{itemize}

\begin{itemize}
\item Mais: un mutex doit être débloqué par le thread qui l'a bloqué. \pause
\begin{itemize}
\item On peut se servir d'un sémaphore comme d'un "signal" pour débloquer un autre thread\pause
\end{itemize}
\end{itemize}

\begin{lstlisting}
init(sem,0);
\end{lstlisting}
\begin{minipage}[t]{0.49\textwidth}
Thread A:
\begin{lstlisting}
 sleep(2);
 // pas syncro
 V(sem);
 //synchro
\end{lstlisting}
\end{minipage}\vline\hspace*{1mm}
\begin{minipage}[t]{0.47\textwidth}
Thread B:
\begin{lstlisting}
 sleep(1);
 // pas syncro
 P(sem); 
 //synchro
\end{lstlisting}
\end{minipage}

\subsection{Sémaphores POSIX}


\begin{lstlisting}
#include <semaphore.h>

int sem_init(sem_t *sem, int pshared, unsigned int value);
int sem_destroy(sem_t *sem);

int sem_wait(sem_t *sem);
int sem_trywait(sem_t *sem);
int sem_timedwait(sem_t *sem, const struct timespec *abs_timeout);

int sem_post(sem_t *sem);
\end{lstlisting}


\begin{itemize}
\item \cmd{pshared} = 0 : le sémaphore n'est pas partagé avec un autre processus (uniquement entre les threads de ce processus)
\item \cmd{pshared} = 1 : le sémaphore est partagé. \cmd{sem} doit être dans une zone mémoire partagé entre les différents processus
\end{itemize}

\subsection{5 philosophes avec sémaphore}

\begin{lstlisting}[basicstyle=\small]
mutex baguette[5];
semaphore sem;
init(sem,4);

void *philosophe(void *a) {
  int i=(long long) a;
  while(1) {
    printf("%d pense\n",i);
    wait(sem);
    lock(baguette[i]);
    lock(baguette[(i+1)%5]);
    post(sem);
    printf("%d mange\n",i);
    unlock(baguette[i]);
    unlock(baguette[(i+1)%5]);
  }
}
\end{lstlisting}


Parfait ! pas de famine (même "probabiliste"), pas d'attente inutile.

\subsection{Sémaphore: Implémentation ?}

La première solution (Dijkstra) utilisait des blocages d'interruptions.

Cela n'est plus valable sur des machines multiprocesseurs, mais cela peut être simulé avec un mutex







\begin{minipage}[t]{0.44\textwidth}
\begin{lstlisting}[basicstyle=\footnotesize]
init(int &s,int N) {
 lock(mutex);
 s=N;
 unlock(mutex);
}

V(int &s) {
 lock(mutex);
 s++;
 unlock(mutex);
}
\end{lstlisting}
\end{minipage}
\vline\hspace*{1mm}
\begin{minipage}[t]{0.52\textwidth}
\begin{lstlisting}[basicstyle=\footnotesize]
P(int &s) {
 while(1) {
   lock(mutex);
   if(s>0) {
     s--;
     unlock(mutex);
     return;
   }
   unlock(mutex);
 }
}
\end{lstlisting}
\end{minipage}

\begin{itemize}
\item Attente active et famine 
\end{itemize}


Comment implémenter un sémaphore avec une attente passive ?\pause

\medskip

C'est les mêmes problèmes qu'on avait déjà vu avec les mutex:\pause
\begin{itemize}
\item il faut une file (éviter la famine)\pause
\item il faut communiquer avec l'ordonnanceur (pour éviter l'attente active)\pause
\end{itemize}

\bigskip

(Les sémaphores sont disponibles dans POSIX, mais imaginons que ce ne soit pas le cas.)\pause

\bigskip

Comment peut on faire pour les reprogrammer correctement ?\pause

\medskip

On ne peut pas simuler un sémaphore avec des mutex seuls\pause

\medskip

Mais on peut le faire avec un mutex + une \sur{variable de condition}

\subsection{Variable de condition}

Plus généralement, supposons qu'on veut qu'un thread bloque jusqu'à ce qu'une condition (qui peut être compliquée) soit vérifiée


\begin{lstlisting}[basicstyle=\footnotesize]
//...
while(1) {
  lock();
  if(condition()==1) {
    // operations d'entree de section critique
    unlock();
    break;
  }
  unlock();
}
//section critique
lock();
// operations de sortie de section critique
unlock();
//...

\end{lstlisting}
On voudrait avoir le même comportement que le code ci-dessus, mais sans les famines et dans l'attente active. Comment faire ?




\sur{Variable de condition}: primitive qui permet de mettre en attente (dans une queue) un thread en débloquant (atomiquement) un mutex\pause

\begin{lstlisting}[basicstyle=\footnotesize]
mutex m;
cond c;

//...
lock(m);
while(condition()==0)
  wait(c,m);
// operations d'entree de section critique
unlock(m);
//section critique
lock(m);
// operations de sortie de section critique
signal(c);
unlock(m);
//...
\end{lstlisting}


Une variable de condition fonctionne toujours de pair avec un mutex

\medskip

3 primitives: 

\begin{itemize}
\item wait(c,m) : (atomiquement) débloquer m, mettre le thread en pause, et le rajouter dans la queue de c
\begin{itemize}
\item au moment de l'appel, m doit être bloqué !
\end{itemize}
\end{itemize}

\begin{itemize}
\item signal(c) : débloque le premier thread de la queue de c
\end{itemize}

\begin{itemize}
\item broadcast(c) : débloque tous les threads de la queue de c
\end{itemize}

\subsection{signal ou broadcast ?}

Si tous les threads en attente attendent sur la même condition : signal()

\bigskip

Si les threads ont des conditions différentes: broadcast()

\bigskip

Sinon: un thread est débloqué, mais si sa condition n'est pas validée, il va devoir re-entrer en sommeil. Si un autre thread a sa condition validée, il ne sera pas réveillé par défaut.

\subsection{Variables de condition dans pthread}

\begin{lstlisting}[basicstyle=\small]
#include <pthread.h>

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

int pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *cond_attr);
int pthread_cond_destroy(pthread_cond_t *cond);

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);
int pthread_cond_timedwait(pthread_cond_t *cond, pthread_mutex_t *mutex, const struct timespec *abstime);

int pthread_cond_signal(pthread_cond_t *cond);

int pthread_cond_broadcast(pthread_cond_t *cond);
\end{lstlisting}

\subsection{5 philosophes avec mutex+cond}

\begin{lstlisting}[basicstyle=\footnotesize]
void *philosophe(void *a)
{
  int i=(long long) a;
  while(1) {
    printf("%d pense\n",i);
    
    pthread_mutex_lock(&mutex);
    while(baguette[i]==0 || baguette[(i+1)%5]==0)
      pthread_cond_wait(&cond,&mutex);
    baguette[i]=baguette[(i+1)%5]=0;
    pthread_mutex_unlock(&mutex);

    printf("%d mange\n",i);

    pthread_mutex_lock(&mutex);
    baguette[i]=baguette[(i+1)%5]=1;
    pthread_cond_broadcast(&cond);
    pthread_mutex_unlock(&mutex);
  }
}
\end{lstlisting}

\subsection{Sémaphores avec mutex+cond}

\begin{minipage}[t]{0.45\textwidth}
\begin{lstlisting}[basicstyle=\scriptsize]
typedef struct {
  int n;
  pthread_mutex_t m;
  pthread_cond_t c;
} sem_t;

void sem_init(sem_t *s,
	      int n)
{
  s->n=n;
  pthread_mutex_init(
	&s->m,NULL);
  pthread_cond_init(
	&s->c,NULL);
}
\end{lstlisting}
\end{minipage}
\vline\hspace*{1mm}
\begin{minipage}[t]{0.50\textwidth}
\begin{lstlisting}[basicstyle=\scriptsize]
void sem_post(sem_t *s)
{
 pthread_mutex_lock(&s->m);
 s->n++;
 pthread_cond_signal(&s->c);
 pthread_mutex_unlock(&s->m);
}

void sem_wait(sem_t *s)
{
 pthread_mutex_lock(&s->m);
 while(s->n<=0)
  pthread_cond_wait(&s->c,
                    &s->m);
 s->n--;
 pthread_mutex_unlock(&s->m);
}
\end{lstlisting}
\end{minipage}

\subsection{Pour finir...}

\begin{itemize}
\item Moniteurs = mutex + variable de condition associée au mutex
\end{itemize}

\medskip

\begin{itemize}
\item Généralise les autres primitives 
\end{itemize}

\medskip

\begin{itemize}
\item Par exemple, en C++11: les seules primitives introduites dans la STD sont \cmd{<mutex>} et \cmd{<condition\_variable>}
\end{itemize}




\section{Interlude : Concurrence C++11}

\subsection{}

Le C++11 introduit plusieurs classes pour gérer les threads et la concurrence:

\begin{itemize}
\item threads
\item mutex
\item variables de condition
\end{itemize}

\subsection{<thread> }

\begin{itemize}
\item \cmd{std::thread} représente un thread (similaire à \cmd{pthread\_t}) 
\end{itemize}

\begin{itemize}
\item le thread est lancé à la construction:
\end{itemize}

\begin{lstlisting}
 void fct(int a, double b) {
  //...
 }

 std::thread th(fct,42,3.14);
\end{lstlisting}

\begin{itemize}
\item grâce à la "magie" des templates, pas besoin de jouer avec un argument \cmd{void*}
\end{itemize}


\begin{itemize}
\item \cmd{std::thread} est remplaçable (mais pas copiable). \cmd{operator=} déplace le thread.
\end{itemize}

\begin{lstlisting}
 std::thread th[42];
 
 for(int i=0;i<42;i++)
   th[i]=std::thread(foo,i);
\end{lstlisting}

\begin{itemize}
\item Fonctions membres: \cmd{join()}, \cmd{detach()}, \cmd{swap()}
\end{itemize}

\begin{itemize}
\item si on détruit un std::thread alors qu'il correspond à un thread en exécution, non détaché : exception
\end{itemize}

\begin{itemize}
\item pas de code retour (voir <future>)
\end{itemize}

\subsection{<mutex>}

\begin{itemize}
\item \cmd{std::mutex} et \cmd{std::recursive\_mutex}
\end{itemize}

\begin{itemize}
\item Fonctions membres: \cmd{lock()}, \cmd{try\_lock}, \cmd{unlock}
\end{itemize}


\begin{itemize}
\item \cmd{std::lock\_guard} est un conteneur pour un mutex (il le bloque à sa construction, et le débloque à sa destruction)
\end{itemize}

\begin{lstlisting}
 std::mutex m;
 //..
 {
  std::lock_guard<std::mutex> l(m);
  //section critique
 }
 // section normale
\end{lstlisting}

\begin{itemize}
\item particulièrement utile pour que le mutex soit débloqué automatiquement en cas d'exception
\end{itemize}


\begin{itemize}
\item \cmd{std::unique\_lock} est un conteneur plus évolué.
\end{itemize}

\begin{itemize}
\item Il a notamment les mêmes fonctions membres qu'un mutex, ce qui permet de s'en servir comme un mutex (avec l'assurance qu'il sera débloqué en cas de destruction)
\end{itemize}

\begin{lstlisting}[basicstyle=\small]
 std::mutex m;
 std::uniquelock<std::mutex> l(m,std::defer_lock);

 l.lock();
 //section critique
 l.unlock();
\end{lstlisting}

\subsection{\cmd{std::lock()}}

\begin{itemize}
\item \cmd{std::lock(m1,m2,...)} permet de bloquer plusieurs mutex à la fois
\end{itemize}

\begin{itemize}
\item Algorithme:
\begin{itemize}
\item bloque le premier mutex $m_1$,
\item puis essaye de bloquer les autres avec \cmd{try\_lock()}.
\item Si un mutex $m_i$, $i>1$  échoue, il débloque tous les autres: $m_1,\ldots m_{i-1}$,
\item puis recommence en commençant par $m_i$.
\end{itemize}
\end{itemize}

\begin{itemize}
\item Sans deadlock, et sans attente active.
\end{itemize}

\subsection{5 philosophes en C++11}

\begin{lstlisting}[basicstyle=\footnotesize]
#include <thread>
#include <mutex>
std::mutex baguette[5];

void philosophe(int i) {
  while(1) {
    printf("%d pense\n",i);
    lock(baguette[i],baguette[(i+1)%5]);
    printf("%d mange\n",i);
    baguette[i].unlock();
    baguette[(i+1)%5].unlock();
  }
}

int main() {
  std::thread id[5];
  for(int i=0;i<4;i++)
    id[i]=std::thread(philosophe,i);
  id[0].join();    
}
\end{lstlisting}


\begin{itemize}
\item Famine ? (voir l'algo de \cmd{lock()}...)
\end{itemize}

\subsection{<condition\_variable>}

\begin{itemize}
\item \cmd{std::condition\_variable} est une variable de condition
\end{itemize}

\begin{itemize}
\item constructeur sans argument
\end{itemize}

Fonctions membres:

\begin{itemize}
\item \cmd{wait(l)} ~~ (\cmd{l} doit être un \cmd{unique\_lock<mutex>})
\end{itemize}

\begin{itemize}
\item \cmd{notify\_one()} ~~  = signal
\end{itemize}

\begin{itemize}
\item \cmd{notify\_all()} ~~ = broadcast
\end{itemize}

\subsection{\cmd{<future>}}

Permet d'accéder au résultat de procédures asynchrones

\bigskip

\begin{lstlisting}
int carre(int x) {
  for(long long i=0;i<1000000000;i++);
  return x*x;
}

int main()
{
  std::future<int> res=std::async(carre,42);
  printf("resultat=%d\n",res.get());
  return 0;
}
\end{lstlisting}


Ou bien avec des promesses:

\begin{lstlisting}
void carre(int x,std::promise<int> pr) {
  for(long long i=0;i<1000000000;i++);
  pr.set_value(x*x);
}

int main()
{
  std::promise<int> pr;
  std::future<int> res=pr.get_future();
  std::thread th(carre,42,std::move(pr));
  printf("resultat=%d\n",res.get());
  th.join();
  return 0;
}
\end{lstlisting}

\subsection{<atomic>}

Permet de faire des opérations atomiques sur une variable

\begin{lstlisting}
std::atomic<int> atint;

void th() {
  for(int i=0;i<10000000;i++)
    atint++;
}

int main() {
  atint.store(0);
  std::thread th1(th);
  std::thread th2(th);
  th1.join();
  th2.join();
  printf("%d\n",atint.load());
  return 0;
}
\end{lstlisting}


\subsection{Variables \cmd{thread\_local}}

En C/C++: il y a deux types de variables:
\begin{itemize}
\item les automatiques (ou locales): dans la pile (défaut, mot clef \cmd{auto})
\item les statiques (ou globales): dans le segment de données (mot clef \cmd{static})
\end{itemize}

\bigskip

Le C++11 rajoute le type \cmd{thread\_local}
\begin{itemize}
\item la variable sera locale au thread
\end{itemize}






\section{Gestion des interblocages }

\subsection{Conditions pour avoir un interblocage}

Un interblocage arrive quand les 4 conditions suivantes sont vérifiées en même temps: [Coffman 1971]

\begin{itemize}
\item exclusion mutuelle : la/les ressource(s) n'est pas partageable\pause
\item "hold and wait" : le(s) thread(s) a déjà bloqué une ressource, et en demande une autre\pause
\item non-préemption : c'est le thread qui libère par lui même les ressources\pause
\item attente circulaire : il existe une chaîne de processus $P_1\ldots P_k$ telle que chaque processus $P_i$ bloque une ressource $R_i$ et chaque processus $P_i$ demande la ressource $R_{(i+1) \% k}$.\pause
\end{itemize}

\bigskip

Exemple: les 5 philosophes ont chacun la fourchette de gauche, et attendent la fourchette de droite.

\subsection{Prévenir et éviter les interblocages}

Briser une des 4 conditions:\pause

\begin{itemize}
\item Enlever l'exclusion mutuelle : par exemple
\begin{itemize}
\item remplacer par des opérations atomiques. 
\item algorithmes "sans blocages" : utilisation d'opérations atomiques "lecture-modification-ecriture" \pause
\end{itemize}
\end{itemize}

\begin{itemize}
\item Enlever "hold and wait" : Exemple:
\begin{itemize}
\item s'imposer de demander au plus 1 ressource à la fois.
\item bloquer plusieurs mutex atomiquement en même temps
\item si on demande plusieurs mutex, on fait attention à ne pas bloquer si on tient déjà un mutex\pause
\end{itemize}
\end{itemize}

\begin{itemize}
\item Préemption\pause : Difficile à faire... faudrait que cela soit prévu par les primitives et le programme
\end{itemize}


Contre l'attente circulaire: ne pas créer de cycles dans le graphe\pause

\begin{itemize}
\item Par exemple : Solution de Dijkstra pour les 5 philosophes\pause
\end{itemize}

\medskip

\begin{itemize}
\item Solution générale possible: mettre un ordre total sur toutes les ressources, et demander les ressources dans l'ordre\pause
\end{itemize}

\begin{itemize}
\item Le graphe de dépendance sera toujours un sous graphe d'un graphe acyclique \pause
\end{itemize}

\begin{itemize}
\item Exemple: 5 philosophes asymétriques: un des philosophes prend les fourchettes dans l'autre sens.\pause
\end{itemize}

\begin{itemize}
\item Une solution simple dans le cas général: adresse mémoire du mutex
\end{itemize}




Si on a (en plus) les informations de quelles ressources, ou combinaisons de ressources, peuvent être demandés, il est possible de prévenir dynamiquement les cycles.\pause

\bigskip

Idée: On connaît le graphe des dépendances possibles, et on connaît le sous graphe des dépendances actuelles.\pause

Il suffit de bloquer l'accès à une ressource qui pourrait créer un cycle. (Rester dans des états "sains")\pause

\bigskip

Exemple: algorithme du Banquier de Dijkstra


Exemple (5 philosophes)
\begin{itemize}
\item $P_0$ prend $f_0$, $P_1$ prend $f_1$, $P_2$ prend $f_2$, $P_3$ prend $f_3$\pause
\end{itemize}

\begin{itemize}
\item $P_4$ demande $f_4$. Lui donner ?\pause ~Non !
\end{itemize}

\begin{itemize}
\item $P_0$ possède $f_0$: l'arc $f_0 \rightarrow f_1$ est possible.\pause
\item Etc. $f_0 \rightarrow f_1\rightarrow f_2\rightarrow f_3\rightarrow f_4$ est possible
\end{itemize}


\begin{itemize}
\item Donner $f_4$ à $P_4$ créerait un cycle : un interblocage est possible.
\item La demande de $P_4$ pour $f_4$ bloque jusqu'à ce que cette possibilité soit écartée
\end{itemize}




\subsection{Détecter les interblocages}

Il est théoriquement possible (pour l'OS) de détecter les interblocages.\pause

\medskip

Par exemple, si on a que des mutex (exclusion mutuelle, et pas de préemption), il suffit de construire le graphe de dépendance :\pause
\begin{itemize}
\item Pour tout thread $t$ bloqué dans un lock($R_t$), tous les arcs entre $x \rightarrow R_t$, pour tout les $x$ bloqués par $t$.
\end{itemize}

Et de tester ce graphe contient un cycle. Si oui: il y a un interblocage...

\bigskip

Mais que peut-on faire si on détecte un interblocage ?

\subsection{Sous Linux ?}

Le noyau Linux :

\begin{itemize}
\item S'occupe qu'il n'y ait pas d'interblocage dans le noyau
\end{itemize}


\begin{itemize}
\item Mais ne détecte/résout pas les interblocages des processus.
\end{itemize}


Pourquoi ?

\begin{itemize}
\item Quand on est dans une situation d'interblocage, on ne peut pas débloquer en respectant l'exclusion mutuelle\pause
\begin{itemize}
\item à part "tuer" quelque chose...
\end{itemize}
\end{itemize}

\begin{itemize}
\item On ne peut pas savoir à l'avance si on va arriver à une situation d'interblocage:\pause

 Il faudrait analyser le code pour savoir les dépendances possibles...

 On frise avec des problèmes indécidables
\end{itemize}


Il faudrait des primitives de verrouillage beaucoup plus compliquées. Cela en vaut il la peine ?


\subsection{Livelock}

Un autre type d'interblocage: le \sur{livelock}\pause

\medskip

Aucun thread n'est bloqué, mais aucun thread n'avance (le code exécuté ne sert qu'à la gestion de concurrence)\pause

\medskip

Exemple: excès de politesse. Un thread veut laisser sa place pour une ressource à un autre thread si il le demande. Chaque thread se passe la main.

\section{Concurrence : Ordonnancement}

\subsection{Ordonnancement : rappels}

(Ici thread = thread ou processus non multi-threadé)

\bigskip

L'ordonnancement est préemptif.\pause

\bigskip

Travail de l'ordonnanceur :\pause
\begin{itemize}
\item Choisir à quel thread (prêt) il doit donner la main, \pause et
\item (pour les ordonanceurs préemptifs) combien de temps il lui donne.
\end{itemize}

\subsection{État des threads}

États des threads considérés par l'ordonnanceur:

\begin{itemize}
\item exécution : le thread est en exécution (sur un des coeurs)
\item prêt : le thread attend que l'ordonnanceur lui donne la main
\item en attente : le thread ne peut/doit pas être exécuté pour le moment (en attente d'une IO ou d'un mutex, sleep...)
\item terminé 
\end{itemize}

\subsection{Changement d'état}

Les threads "vivants" changent constamment d'état (exécution, prêt, attente)\pause

\begin{itemize}
\item exécution $\rightarrow$ attente : appel système sur une ressource bloquante\pause
\item attente $\rightarrow$ prêt : la ressource se libère\pause
\item prêt $\rightarrow$ exécution : l'ordonnanceur donne la main au thread (dispatch)\pause
\item exécution $\rightarrow$ prêt :
\begin{itemize}
\item le thread décide par lui même de rendre la main\pause

 (POSIX: \cmd{sched\_yield()}),\pause ou
\item (ordo préemptif) le temps accordé au thread est dépassé (interruption)
\end{itemize}
\end{itemize}

\subsection{Les différents temps}

\begin{itemize}
\item temps total ("réel"): temps total d'un processus (de son création à sa terminaison)\pause
\item temps user : temps passé en mode utilisateur (temps passé en "exécution")\pause
\item temps système : temps passé en mode système (dans les appels systèmes)\pause
\item temps d'attente: temps passé en état "prêt"\pause
\end{itemize}

(Note: pour voir les temps réels, user et sys: \cmd{time \textit{commande}}).


\subsection{Objectifs d'un ordonnanceur}

Un ordonnanceur doit avoir plusieurs objectifs:\pause

\begin{itemize}
\item Utiliser le(s) CPU à 100\% \pause
\item Respecter l'équité \pause
\item Respecter les priorités ("nice") \pause
\item Minimiser le temps total d'une tache courte. (Réactivité. Par exemple : une commande.)\pause
\item Minimiser le temps total pour un long travail \pause
\item Éviter de faire trop de context-switch (par exemple, accorder des temps trop courts)
\item Éviter de passer trop de temps dans l'ordonnanceur\pause
\item ...
\end{itemize}


\subsection{Algorithmes l'ordonnancement}

\begin{itemize}
\item Problème difficile\pause
\item Il y en a plusieurs possibles, en fonctions des objectifs principaux\pause
\item Cela pourrait être le sujet de tout un cours...\pause
\item Les algorithmes simples ont souvent des problèmes.\pause
\end{itemize}

\bigskip

Stratégies "typiques":
\begin{itemize}
\item First-Come, First-Served  (FCFS) : (coopératif). Algo "minimal", on ne réfléchit pas.
 Peu de context switch. Problème : le temps de réponse peut être long (infini). Pas de gestion des priorités.\pause
\end{itemize}

\begin{itemize}
\item Shortest-Job-First  (SJF) : résout le problème de la réactivité.

 Problème: il faut connaître (ou prédire) le temps d'un processus a priori.
\end{itemize}

\subsection{Algorithmes d'ordonnancement : Round-Robin}

Round-Robin (RR) : (ordo préemptif)\pause

\begin{itemize}
\item L'ordonnanceur a une liste (ou queue) $L$ de threads "prêt".\pause
\item L'ordonnanceur prend (et retire) le premier thread ($T$) de la liste \pause
\item L'ordonnanceur exécute $T$, avec une limite de temps déterminé (ex: 0.1 seconde).\pause
\item Quand $T$ rend la main (ex: IO bloquant), ou a épuisé son temps autorisé, l'ordonnanceur le rajoute à la fin de $L$.\pause
\end{itemize}

Problèmes:
\begin{itemize}
\item Pas de gestion de la priorité. \pause
\item Si $T$ fait souvent des appels à des I/O bloquantes, il est laissé. 
\end{itemize}

\subsection{Avec les priorités ?}


Solutions: 
\begin{itemize}
\item Avoir plusieurs listes (une par priorité)\pause

 Si beacoup de priorités, un peu lourd...\pause

 Décisions à prendre: quelle liste dispatcher ? \pause
\end{itemize}

\medskip

\begin{itemize}
\item Utilisation de files de priorités (plutôt que des listes/queues)

 (permet aussi de dépénaliser les threads qui font beaucoup d'I/O bloquantes)
\end{itemize}

\subsection{Et avec plusieurs processeurs/coeurs ?}

Un thread est généralement associé à un coeur\pause

Pourquoi ?\pause

\begin{itemize}
\item histoire de cache 
\item histoire de mémoire...\pause
\end{itemize}

\medskip

Mais si un coeur est moins utilisé qu'un autre, l'ordonnanceur peut décider de déplacer un thread.\pause

\medskip

L'ordonnanceur doit choisir quel coeur associer à un thread\pause

Et décider quand le changer de coeur (load balance)

\subsection{Parenthèse : UMA / NUMA }

Architecture UMA (uniform memory access)

\medskip

\begin{itemize}
\item une mémoire centrale partagée par plusieurs processeurs/coeurs 
\end{itemize}

Exemples: vos machines (Intel Core ix, smartphones...)\pause

\medskip

Problème:\pause
\begin{itemize}
\item si il y a beaucoup de coeurs, goulot d'étranglement pour l'accès mémoire\pause
\end{itemize}

\begin{itemize}
\item les contrôleurs de mémoire sont (maintenant) souvent intégrés aux processeurs, et il difficile de concevoir des processeurs avec beaucoup de coeurs (plus de pertes, problème de dissipation thermique)
\end{itemize}


Architecture NUMA (non-uniform memory access)

\begin{itemize}
\item Chaque processeur (ou groupe de coeurs)  dispose de sa mémoire (et forme un noeud)\pause
\item Mais chaque noeud peut accéder à toute la mémoire de la machine.\pause
\item Si c'est une mémoire d'un autre noeud, il faut passer par un bus qui inter-connecte les différents noeud (bus très rapide, mais quand l'accès est quand même plus lent)
\end{itemize}


Exemples: Systèmes multi\sur{processeurs} courants (Intel Xeon, AMD Opterons...)\pause

\begin{itemize}
\item Optimalement, il faudrait qu'un thread soit exécute dans le noeud où est sa mémoire\pause
\end{itemize}

Contrainte supplémentaire pour l'ordonnanceur...\pause
\begin{itemize}
\item Il faut interférer avec l'ordonnanceur mémoire
\item déplacer un thread d'un noeud à un autre est plus contraignant
\end{itemize}



\subsection{Ordonnanceur(s) de Linux}

Plusieurs ordonanceurs au cours de l'histoire de Linux\pause

\begin{itemize}
\item O(n) scheduler (Linux 2.4: 2001-2011)
\begin{itemize}
\item le temps est divisé en "epoch". À chaque epoch, chaque thread a droit à un certain nombre de temps CPU (basé sur la priorité)
\item Si un thread n'a pas épuise tout son temps CPU au cours d'une epoch, il rajoute la moitié du temps restant à son temps à l'epoch suivante.
\item Problème: temps linéaire en le nombre de processus entre chaque epoch\pause
\end{itemize}
\end{itemize}


\begin{itemize}
\item O(1) scheduler (Linux 2.6, avant 2.6.23 : 2003-2007)
\begin{itemize}
\item 140 niveaux de priorités (0-99 pour le système et temps réel, 100-139 pour les utilisateurs) 
\item 2 queues par priorité : actif/inactif
\item pénalité si temps écoulé, récompense si I/O bloquante
\end{itemize}
\end{itemize}


Actuellement: Completely Fair Scheduler\pause
\begin{itemize}
\item une file de priorité: arbre rouge-noir, indexé par le temps utilisé par le processus\pause
\item temps accordé: le temps que le thread a attendu $\times$ le ratio du temps qu'il aurait utilisé sur un processeur "idéal" \pause
\item l'ordonnanceur donne la main au thread qui a moins utilisé son temps (le plus petit dans la liste)\pause
\item quand le thread rend la main, l'ordonnanceur réinsère le thread dans l'arbre rouge-noir, avec son nouveau temps\pause
\item les processus avec beaucoup d'attente sont naturellement "récompensés"
\end{itemize}

\subsection{Politiques et priorités POSIX}

(Voir \cmd{man sched})


\medskip

On peut interférer avec l'ordonnanceur pour changer les politiques ou les priorités\pause

\medskip

(Généralement, plutôt utile pour les applications temps réel.)\pause

\medskip

Déjà vu : \cmd{nice()} pour un processus\pause

\medskip

Il y a aussi \cmd{getpriority()} / \cmd{setpriority()}. (Priorité d'un processus, d'un groupe de processus, et d'un utilisateur.)

\subsection{Différentes politiques POSIX}

Différentes politiques d'ordonnancement sont prévues dans POSIX (pour les processus et threads):

\begin{itemize}
\item SCHED\_OTHER: politique "standard"\pause
\end{itemize}

Des politiques "temps réel" :
\begin{itemize}
\item SCHED\_FIFO: (First-in-First-Out)
\item SCHED\_RR: (Round-Robin)
\end{itemize}
Dans ce cas, il y a une priorité supplémentaire (généralement entre 0 et 99) pour le thread\pause

(Et quelques autres politiques, apparues plus récemment)\pause

\bigskip

Pour changer la politique d'un processus: \cmd{sched\_setscheduler()}

\medskip

Pour changer la politique d'un thread: \cmd{pthread\_setschedparam()}

\subsection{Affinités}

On peur vouloir contrôler sur quel noeud un processus tourne, ou répartir ses threads sur différents noeuds, pour avoir de meilleurs performances.\pause

\bigskip

Il est possible de choisir (sous Linux) sur quel(s) coeur(s) un thread peut tourner, avec \cmd{sched\_setaffinity}.

\bigskip

Il est aussi possible de choisir des affinités mémoires. Voir \cmd{man numa}

\subsection{Problème: Inversion de priorité}

\begin{itemize}
\item A de forte priorité
\item B de priorité moyenne
\item C de faible priorité
\end{itemize}


Scénario:
\begin{itemize}
\item C bloque une ressource R
\item A demande (et bloque) sur la ressource R
\item B arrive\pause
\item B prend 100\% CPU, car il a la priorité sur C
\item C ne relâche pas R
\item A ne peut pas être exécuté
\end{itemize}

B bloque A (par l'intermédiaire de C).

(problème réel: Mars pathfinder)


Solutions:

\begin{itemize}
\item ne pas trop prioriser les threads de priorité supérieure. (Pas valable en temps réel)\pause
\item aléatoirement, donner du temps CPU à des taches de priorité basse (bricolage...)\pause
\end{itemize}

\begin{itemize}
\item (priority ceiling) donner une priorité à un mutex. Si un thread bloque le mutex, il hérite (temporairement) de la priorité du mutex (si elle est plus haute)\pause
\end{itemize}

\begin{itemize}
\item (priority inherance) si un thread C bloque le mutex, et un thread A de plus haute priorité demande le mutex, C hérite (temporairement) de la priorité de A.
\end{itemize}


Dans pthread:

\begin{lstlisting}[basicstyle=\small]
int pthread_mutexattr_getprotocol(
    const pthread_mutexattr_t *attr,
    int *protocol);
int pthread_mutexattr_setprotocol(
    pthread_mutexattr_t *attr,
    int protocol);
int pthread_mutex_setprioceiling(
    pthread_mutex_t* mutex, 
    int prioceiling, int* old_ceiling );
\end{lstlisting}

\cmd{protocol} :
\begin{itemize}
\item PTHREAD\_PRIO\_NONE : le fait de bloquer le mutex n'affecte pas la priorité
\item PTHREAD\_PRIO\_PROTECT : (priority ceiling) bloquer le mutex donne au thread la priorité du mutex (s'il est supérieur)
\item PTHREAD\_PRIO\_INHERIT : (priority inherance) bloquer le mutex donne au thread le maximum des priorités des threads demandant le même mutex
\end{itemize}

\section{Partage de mémoire entre processus (POSIX)}

\subsection{Mémoire partagée inter-processus}

Plusieurs processus peuvent partager leur mémoire: c'est un IPC très rapide\pause

\bigskip

Attention: comme pour les threads, il faut gérer la concurrence, soit:
\begin{itemize}
\item avec des sémaphores (pshared=1)
\item avec des mutex partagés (attribut pshared) 
\end{itemize}

\subsection{Mémoire partagée inter-processus: cas simple}

Entre père et fils:

\medskip

\begin{lstlisting}
char *x=mmap(NULL,65536,PROT_READ|PROT_WRITE,MAP_SHARED|MAP_ANONYMOUS,0,0);
if(fork()==0) {
  /*fils*/
  strcpy(x,"COUCOU");
  return 0;
}
/* pere */
sleep(1);
printf("%s\n",x);
\end{lstlisting}

\medskip

Affiche: COUCOU

\subsection{}

Sans lien de parenté:

\begin{lstlisting}[basicstyle=\small]
 int fd=open("partage",O_RDWR|O_CREAT,0644);
 ftruncate(fd,65536);
 char *x=mmap(NULL,65536,PROT_READ|PROT_WRITE,MAP_SHARED,fd,0);
\end{lstlisting}

Processus 1:
\begin{lstlisting}[basicstyle=\small]
 while(1) {
  snprintf(x,999,"COUCOU %d",rand());
  sleep(1);
 }
\end{lstlisting}

Processus 2:
\begin{lstlisting}[basicstyle=\small]
 while(1) {
  sleep(1);
  printf("%s\n",x);
 }
\end{lstlisting}
\begin{itemize}
\item Cela marche, mais on utilise le disque (plus lent que la RAM)\pause
\item On voudrait mimer ce comportement, sans passer par le disque
\end{itemize}

\subsection{Mémoire partagée inter-processus: \cmd{shm\_open}}

Solution: objets mémoire partagé (\cmd{man shm\_overview})

\begin{lstlisting}[basicstyle=\small]
 int fd=shm_open("/partage",O_RDWR|O_CREAT,0644);
 ftruncate(fd,65536);
 char *x=mmap(NULL,65536,PROT_READ|PROT_WRITE,MAP_SHARED,fd,0);
\end{lstlisting}

(Processus 1 et 2 comme précédemment)

\begin{itemize}
\item OK !
\end{itemize}
\begin{itemize}
\item En fait \cmd{/partage} sera dans un système de fichier en RAM, dans \cmd{/dev/shm/}
\end{itemize}

\subsection{Objet mémoire POSIX}

\begin{lstlisting}
#include <sys/mman.h>
#include <sys/stat.h>   
#include <fcntl.h>      

int shm_open(const char *name, int oflag, mode_t mode);
int shm_unlink(const char *name);
\end{lstlisting}

\medskip

(compiler avec \cmd{-lrt})

\medskip

Renvoie un descripteur de fichier, sur lequel on peut faire les opérations qu'on a déjà vues:

\cmd{ftruncate}, \cmd{mmap}, \cmd{munmap}, \cmd{close}...

\subsection{Sémaphore partagé entre processus}

(Voir \cmd{man shm\_overview})

\medskip

Deux façons de créer un sémaphore partagé: 
\begin{itemize}
\item Sémaphore anonyme
\item Sémaphore nommé\pause
\end{itemize}

\bigskip

Sémaphore anonyme: le sémaphore doit être crée avec \cmd{sem\_init}, avec \cmd{pshared=1}, dans une zone mémoire partagée (via \cmd{mmap})


Sémaphores nommés (mécanisme similaire à \cmd{shm\_open}) :

\begin{lstlisting}
#include <semaphore.h>
#include <sys/stat.h> 
#include <fcntl.h>    

sem_t *sem_open(const char *name, int oflag);
sem_t *sem_open(const char *name, int oflag, mode_t mode, unsigned int value);
\end{lstlisting}

(compiler avec \cmd{-pthread})

\subsection{Mutex partagé entre processus}

\begin{lstlisting}
pthread_mutexattr_t mutexattr;
pthread_mutexattr_init(&mutexattr);
pthread_mutexattr_setpshared(&mutexattr,PTHREAD_PROCESS_SHARED);

pthread_mutex_init(pmutex,&mutexattr);
//...
\end{lstlisting}

\bigskip

\cmd{pmutex} doit être dans une zone mémoire partagée

\bigskip


Similairement, les variables de condition, rwlocks, barrières... peuvent aussi être partagés entre processus.


\section{Réseau : introduction}

\subsection{Introduction}

Réseau :
\begin{itemize}
\item Ensemble de noeuds
\item Interconnecté (mais pas forcément tous connectés 2 à 2)\pause
\item Pour faire circuler des éléments ou des flux, même entre 2 noeuds non voisins
\end{itemize}

\medskip

Ici : Réseaux informatiques, échange de données (séquence de bits ou d'octets, en paquets ou en flux)

\medskip

Applications: 

\begin{itemize}
\item Partage de ressources (données, imprimante, machine de calcul...)
\item communication (mail, voix, visioconf...)
\end{itemize}

\subsection{Exemples de réseaux :}

\begin{itemize}
\item Réseau local (LAN : local area network) 
\item Réseau au étendu (WAN)
\item "Internet"
\item Téléphone cellulaire
\item ...
\end{itemize}

\medskip

Ce cours : principalement LAN et Internet

\subsection{Internet}

Désigne à la fois:
\begin{itemize}
\item Le réseau Internet (interconnexion de réseaux)
\item Le nom d'un ensemble de protocoles ("TCP/IP")
\end{itemize}

\medskip

Histoire rapide d'Internet

\begin{itemize}
\item Fin années 60: ARPANET: réseau (militaire) censé être résistant aux attaques.
\begin{itemize}
\item inter-universités (en contrat avec le Departement of Defense)
\item Commutation de paquets
\item Invention de TCP/IP pour la communication entre réseaux différents
\end{itemize}
\end{itemize}

Années 80 - 90:
\begin{itemize}
\item Ouverture aux universités (CSNET, NSFNET), puis au privé
\end{itemize}

1989 : WWW (World Wide Web), hyperliens


\subsection{Problématiques}

\begin{itemize}
\item Acheminer les données 
\begin{itemize}
\item router les données
\item trouver et mettre à jour les routes
\item limiter les congestions\pause
\end{itemize}
\end{itemize}

\begin{itemize}
\item Assurer que les données arrivent en l'état
\begin{itemize}
\item vérifier s'il y a des erreurs
\item corriger les erreurs
\item transmettre les données dans l'ordre,
\item sans doublons
\end{itemize}
\end{itemize}

\medskip

Objectifs:
\begin{itemize}
\item Vitesse de transmission (débit)
\item Temps de latence : temps entre l'émission et la réception
\end{itemize}

\subsection{Topologie}

Réseau $\Leftrightarrow$ graphe connexe\pause

Topologie (type de graphe) :
\begin{itemize}
\item étoile, arbre (Ethernet)
\item cycle (anneau)
\item graphe quelconque (Internet...)
\item graphe complet 
\item grille, hypercubes (HPC)...
\end{itemize}

\medskip

\begin{itemize}
\item homogène (LAN Ethernet)
\item hétérogène (Internet)
\end{itemize}

\medskip

Modèles d'organisation:
\begin{itemize}
\item Modèle Client / serveur (ex: HTTP)
\item Modèle pair à pair (P2P) 
\end{itemize}


\subsection{Modèle(s) par couches}

{

\center

\begin{tikzpicture}[scale=.8]
\draw [] (0,0) rectangle (3,1);
\draw (1.5,0.5) node[]{\scriptsize Physique} ;
\draw [] (0,1) rectangle (3,2);
\draw (1.5,1.5) node[]{\scriptsize Liaison} ;
\draw [] (0,2) rectangle (3,3);
\draw (1.5,2.5) node[]{\scriptsize Réseau} ;
\draw [] (0,3) rectangle (3,4);
\draw (1.5,3.5) node[]{\scriptsize Transport} ;
\draw [] (0,4) rectangle (3,5);
\draw (1.5,4.5) node[]{\scriptsize Session} ;
\draw [] (0,5) rectangle (3,6);
\draw (1.5,5.5) node[]{\scriptsize Présentation} ;
\draw [] (0,6) rectangle (3,7);
\draw (1.5,6.5) node[]{\scriptsize Application} ;
\draw (1.5,7.5) node[]{\scriptsize Modèle OSI:} ;

\draw [] (5,0) rectangle (8,2);
\draw (6.5,1) node[]{\scriptsize Accès Réseau} ;
\draw [] (5,2) rectangle (8,3);
\draw (6.5,2.5) node[]{\scriptsize Réseau} ;
\draw [] (5,3) rectangle (8,4);
\draw (6.5,3.5) node[]{\scriptsize Transport} ;
\draw [] (5,4) rectangle (8,7);
\draw (6.5,5.5) node[]{\scriptsize Application} ;
\draw (6.5,7.5) node[]{\scriptsize Modèle TCP/IP:} ;
\end{tikzpicture}

}

{\small OSI = Open Systems Interconnection}

{\small TCP/IP = Transmission Control Protocol / Internet Protocol}


Ce cours : principalement TCP/IP

\subsection{Protocoles de communication}

Protocole: Ensemble de règles (convention) pour que deux (ou +) entités puissent communiquer\pause

Cela inclus:

\begin{itemize}
\item Format des données 
\item Signification des données (adresses, somme de contrôle, numéro dans une séquence...)
\item "Algorithmes" 
\end{itemize}


Chaque couche a son/ses protocole(s)

\begin{itemize}
\item Accès réseau : Ethernet... 
\item Réseau: IP (Internet Protocol)
\item Transport: TCP, UDP
\item Application: HTTP, DNS, IMAP, FTP...
\end{itemize}

\subsection{Unités de communication}

PDU ("Protocol Data Unit"): l'unité de base manipulé par le protocole

\medskip

Unité typique:
\medskip
\begin{tabular}{|c|c|}
\hline	
 ~~ En-tête ~~ & ~~~~~~~~ Message ~~~~~~~~ \\
\hline		   	
\end{tabular}


\medskip

L'en-tête dépend du protocole, et est spécifié par le protocole\pause

\medskip

{

Contient généralement un sous ensemble de :
\begin{itemize}
\item Type de "paquet"
\item Taille du message 
\item Somme de contrôle
\item Émetteur / Destinataire
\item Port de destination
\item Information sur le chiffrement
\item Numéro de séquence...
\end{itemize}

}

\subsection{Encapsulation}

Chaque protocole d'une couche N communique via le/un protocole de la couche $N-1$. \pause

Théoriquement, le protocole $N-1$ ne sait pas ce qu'il transporte \pause 

\medskip

Par exemple le protocole TCP (couche transport) communique via le protocole IP (couche réseau) \pause

Dans ce cas, le message TCP sera encapsulé dans le paquet IP:

\medskip
\begin{tabular}{|c|c|c|}
\hline	
 ~~ En-tête IP ~~ &  ~~ En-tête TCP ~~ & ~~ Message TCP~~ \\
\hline		   	
\end{tabular}

\medskip\pause

Le protocole IP communique via un protocole Ethernet:\pause

\medskip
\begin{tabular}{|c|c|c|c|}
\hline	
 En-tête Ethernet & En-tête IP & En-tête TCP & Message TCP \\
\hline		   	
\end{tabular}

\bigskip

Fragmentation possible:
\begin{itemize}
\item Si un message est trop grand pour être transporté dans une unité du protocole $N-1$, il peut être découpé (si cela est prévu) en plusieurs messages.
\end{itemize}


\subsection{}

{

\center

\begin{tikzpicture}[scale=.8]
\draw [] (0,0) rectangle (3,2);
\draw (1.5,1.5) node[]{\scriptsize (Liaison Physique)} ;
\draw (1.5,0.5) node[]{\scriptsize Ethernet} ;
\draw [] (0,2) rectangle (3,4);
\draw (1.5,3.5) node[]{\scriptsize (Réseau)} ;
\draw (1.5,2.5) node[]{\scriptsize IP} ;
\draw [] (0,4) rectangle (3,6);
\draw (1.5,5.5) node[]{\scriptsize (Transport)} ;
\draw (1.5,4.5) node[]{\scriptsize TCP} ;
\draw [] (0,6) rectangle (3,8);
\draw (1.5,7.5) node[]{\scriptsize (Application)} ;
\draw (1.5,6.5) node[]{\scriptsize HTTP} ;
\draw (1.5,8.5) node[]{\scriptsize Client} ;

\draw[dotted,<->] (3,6.5) --(7,6.5) node[above,midway] {\scriptsize Messages HTTP};
\draw[dotted,<->] (3,4.5) --(7,4.5) node[above,midway] {\scriptsize Messages TCP};
\draw[dotted,<->] (3,2.7) --(7,2.7) node[above,midway] {\scriptsize Paquets IP};
\draw[dotted,<->] (3,1.5) --(7,1.5) node[above,midway] {\scriptsize Trames Ethernet};
\draw[dotted,<->] (3,0.3) --(7,0.3) node[above,midway] {\scriptsize "Bits"};

\draw [] (7,0) rectangle (10,2);
\draw (8.5,1.5) node[]{\scriptsize (Liaison Physique)} ;
\draw (8.5,0.5) node[]{\scriptsize Ethernet} ;
\draw [] (7,2) rectangle (10,4);
\draw (8.5,3.5) node[]{\scriptsize (Réseau)} ;
\draw (8.5,2.5) node[]{\scriptsize IP} ;
\draw [] (7,4) rectangle (10,6);
\draw (8.5,5.5) node[]{\scriptsize (Transport)} ;
\draw (8.5,4.5) node[]{\scriptsize TCP} ;
\draw [] (7,6) rectangle (10,8);
\draw (8.5,7.5) node[]{\scriptsize (Application)} ;
\draw (8.5,6.5) node[]{\scriptsize HTTP} ;
\draw (8.5,8.5) node[]{\scriptsize Serveur} ;

\draw [line width=5pt,opacity=0.15,<->] (1.5,6.3) -- (1.5,0.1) -- (8.5,0.1) -- (8.5,6.3);
\end{tikzpicture}

}

\subsection{Couche "Physique" et "Liaison" ("accès réseau")}

Couche "Physique":

Le médium de transport: câble en cuivre, fibre optique, ondes...

PDU : bits

\begin{itemize}
\item Comment sont encodés les bits ?
\item Perturbations possibles
\end{itemize}

\medskip

Couche "Liaison":

\begin{itemize}
\item S'occupe des liaisons point à point.
\item Éventuellement, transmet une somme de contrôle pour vérifier l'intégrité (Ethernet: CRC)
\end{itemize}

PDU : "Trames"

Protocoles : Ethernet, Wifi... %.MAC, LLC...

\subsection{Couche "Réseau"}

S'occupe de trouver les routes dans le réseau, de les mettre à jour, et router les paquets

\medskip

Sur Internet : IP (Internet Protocol). 

PDU: "Paquets IP"\pause

\medskip

Deux "variantes" d'IP:

\begin{itemize}
\item IPv4: la plus utilisée actuellement, mais un nombre limité d'adresse possible $2^{32}$. Arrive à saturation...
\begin{itemize}
\item exemple d'adresse IPv4: \cmd{192.168.1.79}\pause
\end{itemize}
\end{itemize}

\begin{itemize}
\item IPv6: la nouvelle norme. Partiellement en place. $2^{128}$ adresses 
\begin{itemize}
\item adresse IPv6: \cmd{fe80::e6f8:9cff:fe67:ee22}
\end{itemize}
\end{itemize}



\subsection{}


{

\center

\begin{tikzpicture}[scale=.8]
\draw [] (0,0) rectangle (3,2);
\draw (1.5,1.5) node[]{\scriptsize (Liaison Physique)} ;
\draw [] (0,2) rectangle (3,4);
\draw (1.5,3.5) node[]{\scriptsize (Réseau)} ;
\draw (1.5,2.5) node[]{\scriptsize IP} ;
\draw [] (0,4) rectangle (3,6);
\draw (1.5,5.5) node[]{\scriptsize (Transport)} ;
\draw (1.5,4.5) node[]{\scriptsize TCP} ;
\draw [] (0,6) rectangle (3,8);
\draw (1.5,7.5) node[]{\scriptsize (Application)} ;
\draw (1.5,6.5) node[]{\scriptsize HTTP} ;
\draw (1.2,-.8) node[]{\scriptsize Client} ;


\draw [] (5,0) rectangle (8,2);
\draw (6.5,1.5) node[]{\scriptsize (Liaison Physique)} ;
\draw [] (5,2) rectangle (8,4);
\draw (6.5,3.5) node[]{\scriptsize (Réseau)} ;
\draw (6.5,2.5) node[]{\scriptsize IP} ;
\draw (6.5,-.8) node[]{\scriptsize Routeur (IP)} ;

\draw [] (10,0) rectangle (13,2);
\draw (11.5,1.5) node[]{\scriptsize (Liaison Physique)} ;
\draw [] (10,2) rectangle (13,4);
\draw (11.5,3.5) node[]{\scriptsize (Réseau)} ;
\draw (11.5,2.5) node[]{\scriptsize IP} ;
\draw [] (10,4) rectangle (13,6);
\draw (11.5,5.5) node[]{\scriptsize (Transport)} ;
\draw (11.5,4.5) node[]{\scriptsize TCP} ;
\draw [] (10,6) rectangle (13,8);
\draw (11.5,7.5) node[]{\scriptsize (Application)} ;
\draw (11.5,6.5) node[]{\scriptsize HTTP} ;
\draw (11.8,-.8) node[]{\scriptsize Serveur} ;

\draw (9,.4) node[]{\scriptsize (Ethernet)} ;
\draw (4,.4) node[]{\scriptsize (Wifi)} ;

\draw [line width=5pt,opacity=0.15,<->] (1.5,6.3) -- (1.5,0.1) -- (5.4,0.1) -- (5.4,3) -- (7.6,3) -- (7.6,0.1) -- (11.5,0.1) -- (11.6,6.3);
\end{tikzpicture}

}


\subsection{Couche Transport}

Établir et maintenir les connexions, assurer l'arrivée, dans l'ordre des paquets...\pause

\medskip

Sur Internet : Principalement TCP et UDP.

\begin{itemize}
\item TCP : "Transmission Control Protocol"
\begin{itemize}
\item Mode connecté
\item Fiable: détecte les erreurs, les données perdues, assure l'ordre\pause
\end{itemize}
\end{itemize}

(Socket TCP: comme les sockets à la fin du cours sur les tubes !)


\medskip


\begin{itemize}
\item UDP : "User Datagram Protocol"
\begin{itemize}
\item Non connecté (plus léger: pas de confirmation de réception)
\item Mais: ne garantie pas la bonne livraison, ni l'ordre
\end{itemize}
\end{itemize}


Ces deux protocoles ajoutent un numéro de port: entre 1 et 65535

Généralement un numéro de port $\leftrightarrow$ une application.

HTTP: 80, SSH: 22, DNS: 53...

\medskip

PDU: Segment TCP, Datagramme UDP...

\subsection{Couche Application}

\begin{itemize}
\item Web: HTTP, FTP
\item mail: IMAP, POP, SMTP
\item session: (Telnet), SSH
\item DNS, DHCP
\item ...
\end{itemize}

\medskip

\begin{itemize}
\item Vos programmes !
\end{itemize}

\subsection{Suite:}

\begin{itemize}
\item Les couches en détail
\item Programmation IP en POSIX
\end{itemize}

\section{Couches Accès Réseau}

\subsection{Couche "Physique" : Médium}

Support de transmission "guidés":\pause
\begin{itemize}
\item paire de cuivre \sur{torsadée}
\begin{itemize}
\item Ethernet (actuel) : 4 paires (câble de catégorie 5 "RJ45"...)
\item RTC/xDSL : 1 paire torsadée\pause
\end{itemize}
\item câble coaxial\pause
\item fibre optique
\item ... \pause
\end{itemize}

Sans fil: \pause
\begin{itemize}
\item Ondes radio (wifi, bluetooth, satellites...) \pause
\item Ondes lumineuses \pause
\end{itemize}


Sujet à des perturbations (erreurs)\pause
\begin{itemize}
\item atténuation (résistance, impuretés), auto-perturbations \pause
\item perturbations extérieures \pause
\end{itemize}

\medskip

Plus que c'est long/loin, plus qu'il y a de possibilités d'erreur
\begin{itemize}
\item débit théorique maximum diminue avec la longueur de la liaison
\end{itemize}


\medskip

Pourquoi torsadées ?
\begin{itemize}
\item les perturbations électromagnétiques s'annulent
\end{itemize}

Éventuellement: un blindage en plus.

\subsection{Couche "Physique" : Encodage des bits}

"Modulation numérique": convertir des bits en signaux analogiques\pause

\medskip

\begin{itemize}
\item Transmission en bande de base
\end{itemize}

\medskip

\begin{itemize}
\item Modulation d'un signal porteur
\begin{itemize}
\item modulation de fréquence
\item modulation d'amplitude
\item modulation de phase
\end{itemize}
\end{itemize}

\subsection{Transmission en bande de base}

Le plus simple (NRZ):

Paire torsadée:
\begin{itemize}
\item Bit = 0 $\to$ tension positive
\item Bit = 1 $\to$ tension négative
\end{itemize}

Fibre optique
\begin{itemize}
\item Bit = 0 $\to$ pas de lumière
\item Bit = 1 $\to$ lumière\pause
\end{itemize}

\medskip

Problème : si trop de 0 de suite, on s'y perd.\pause

\begin{itemize}
\item Codage de Manchester 0 = -+ et 1 =+- (Ethernet "classique")\pause
\item Interdire les suites trop longues de 0 ou 1 (réencoder...)
\end{itemize}


\subsection{Modulation d'un signal porteur}

Pourquoi:
\begin{itemize}
\item Multiplexage de fréquences
\item Ondes électromagnétiques
\item Médium fonctionnant sur une plage de fréquences
\end{itemize}


Comment:
\begin{itemize}
\item Modulation de fréquence (0 : f, 1: f')
\item Modulation d'amplitude 
\item Modulation de phase\pause
\end{itemize}

\medskip

\begin{itemize}
\item Possible de coder plus qu'un bit à la fois\pause
\item Possible d'associer modulation d'amplitude et de phase
\end{itemize}


\subsection{Half / Full Duplex}

\begin{itemize}
\item (Full-)Duplex: communication dans les deux sens possible en même temps
\end{itemize}

\begin{itemize}
\item Half-Duplex: communication dans les deux sens, mais une à la fois
\end{itemize}

\begin{itemize}
\item Simplex: communication dans un sens
\end{itemize}



\subsection{Câble catégorie 5 (Ethernet "RJ45")}

\begin{itemize}
\item 4 Paires torsadés 
\end{itemize}

\begin{itemize}
\item Sert pour Ethernet\pause
\end{itemize}

\begin{itemize}
\item Attention: Ethernet = une famille de normes (10BASE2, 10BASE-T, 100BASE-T, 1000BASE-T...)

 (Ethernet existe aussi sur coaxial et fibre optique).
\end{itemize}

\begin{itemize}
\item L'utilisation des paires diffère selon la norme.\pause
\end{itemize}

\begin{itemize}
\item Améliorations: Cat 5e, Cat 6...
\begin{itemize}
\item spécification plus strictes (résistance, capacité, inductance...)
\end{itemize}
\end{itemize}

\medskip

\begin{itemize}
\item RJ45: nom du connecteur (8P8C)
\end{itemize}


\subsection{Couche Liaison}

But:
\begin{itemize}
\item Interface à la couche réseau
\item Contrôler et traiter les erreurs de transmission
\item Réguler les flux
\end{itemize}

\medskip


Deux types de liaisons:
\begin{itemize}
\item point à point : communication entre 2 machines 
\item diffusion : canal partagé entre plusieurs machines
\end{itemize}



Problèmes:

\medskip

Comment découper le flux de bits en trames ? \pause

$\to$ fanions de signalisation de début de trame

\medskip

Détecter les erreurs
\begin{itemize}
\item dues au perturbations extérieures
\item dues aux collisions de paquets\pause
\end{itemize}

$\to$ utilisation de sommes de contrôle (CRC: Cyclic Redundancy Check)

\medskip

Contrôle de flux $\to$ retour d'information




\subsection{Liaison en mode diffusion}

Et quand le médium est partagé ? (Wifi, câble commun à plus de 2 machines)\pause

\medskip

Au début d'Ethernet : un câble coaxial pour plusieurs machines.

Problèmes:
\begin{itemize}
\item Plus de collisions à gérer
\item Destinataire de la trame
\end{itemize}

\medskip

$\Rightarrow$ Sous-couche MAC (Medium Acces Control)

\subsection{MAC Ethernet classique}

Paquet Ethernet :

{
\footnotesize

\medskip
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
Préambule & MAC dest. & MAC source & Type/Longueur & Données &  CRC \\
\hline
8 & 6 & 6 & 2 & <=1500 & 4 \\
\hline		   	
\end{tabular}

}

\medskip

Adresse MAC:
\begin{itemize}
\item 6 octets: 3 premiers pour le constructeur, les 3 derniers pour les cartes construites par le constructeur.
\item Théoriquement, chaque carte réseau a une adresse MAC différente.
\end{itemize}
CRC: somme de contrôle 


\bigskip

Trame MAC Wifi (802.11)

{
\footnotesize

\medskip
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
Contrôle & Durée & Dest. & Source & Adresse 3 & Séquence & Données &  CRC \\
\hline
2 & 2 & 6 & 6 & 6 & 2 & <=2312 & 4 \\
\hline		   	
\end{tabular}

}

\medskip

\subsection{Ethernet commuté}

Ethernet sur un câble coaxial:
\begin{itemize}
\item Difficile à rajouter une nouvelle machine 
\item Une carte réseau défaillante peut bloquer tout le réseau
\item Vite encombré.
\end{itemize}

\medskip

Évolutions d'Ethernet:

\begin{itemize}
\item Topologie en étoile: toutes les machines sont reliées à un \textit{hub}, par une paire torsadée
\end{itemize}


\medskip

Puis, pour augmenter la capacité:
Inutile d'envoyer les paquets aux machines non destinatrices de la trame !

\begin{itemize}
\item Remplacement du \textit{hub} par un \textit{switch} (commutateur) : \sur{Ethernet commuté}
\end{itemize}


Le switch doit garder une table adresse MAC / port.

\medskip

Comment les trouver la bonne bijection ?

\medskip

Apprentissage a posteriori:

\medskip

Quand il reçoit une trame de source $s$, destinataire $d$ par le port $p$:\pause
\begin{itemize}
\item Il associe l'adresse MAC $s$ au port $p$\pause
\end{itemize}

\begin{itemize}
\item Si le port de l'adresse $d$ n'est pas $p$, il diffuse la trame sur le port de $d$
\item Si le port de l'adresse $d$ est $p$, il rejette la trame\pause
\item Si il ne sait pas le port de l'adresse $d$, il diffuse à tout le monde
\end{itemize}

\medskip

Marche aussi pour une topologie en arbre !


Les switch jouent un rôle similaire aux routeurs IP.\pause

\medskip

Pourquoi rajouter une couche "Réseau" ?\pause

\bigskip

Suite:

\begin{itemize}
\item Couche Réseau et Transport : TCP/IP
\end{itemize}







\section{Couche réseau \& Protocole IP}

\subsection{Introduction}

La couche "liaison" s'occupe des communications point à point.

\medskip

La couche "réseau" s'occupe de:
\begin{itemize}
\item router les informations dans le réseau
\item trouver et mettre à jour les routes
\item détecter nouveaux liens
\item détecter les pertes de liens et problèmes de congestion
\end{itemize}

\medskip

Sur internet: protocoles IP
\begin{itemize}
\item IPv4: le plus courant, mais on arrive à bout des adresses disponibles
\item IPv6: le nouveau, partiellement en place
\end{itemize}

\subsection{Commutation de paquets vs de circuits}

Il existe deux grand types de réseaux:
\begin{itemize}
\item Réseaux à {commutation de paquets} (store-and-forward)
\begin{itemize}
\item Unité de base, un "paquet" : une suite d'octets
\item Le routeur reçoit un paquet, analyse à qui il est destiné, et le renvoie dans la bonne direction\pause
\end{itemize}
\item Réseaux à commutation de circuit
\begin{itemize}
\item Chaque routeur prépare la route en connectant le port d'entrée au port de sortie. Puis l'information passe en flux jusqu'à la fin de la communication
\item Exemple: réseau téléphonique traditionnel 
\end{itemize}
\end{itemize}

\medskip

Il est aussi possible d'avoir des réseaux à paquets, où les routes sont prédéfinies à l'avance pour chaque connexion.

\medskip

Internet: \emph{commutation de paquets}.

Unité de base du protocole: "paquet IP"


\subsection{Routage de paquets}

Chaque noeud interne du réseau (noeud avec au moins 2 voisins) doit choisir, quand il reçoit un paquet, à qui il doit le transférer.
("Router un paquet").

\medskip

Un noeud interne est souvent appelé un \emph{routeur} (ordinateur ou matériel spécialisé)

\medskip

Il possède pour cela une \emph{table de routage}: \pause
\begin{itemize}
\item une table de paires (adresse, voisin)
\end{itemize}





\definecolor{lavander}{cmyk}{0,0.48,0,0}
\definecolor{violet}{cmyk}{0.79,0.88,0,0}
\definecolor{burntorange}{cmyk}{0,0.52,1,0}

\def\lav{lavander!90}
\def\oran{orange!30}

\tikzstyle{noeud}=[draw,circle,burntorange, left color=\oran,
                       text=violet,minimum width=20pt]

\begin{tikzpicture}[auto, thick]
  \foreach \place/\name in {{(0,-1)/a}, {(2,-1)/b}, {(2,2)/c}, {(0,2)/d},
           {(-2,0)/e},{(-4,0)/g},{(4,2)/f}}
    \node[noeud] (\name) at \place {\footnotesize \name};
  \foreach \source/\dest in {a/b, a/c, a/d, b/c, c/d,a/e,d/e,e/g,c/f}
    \path (\source) edge (\dest);
\node at (-3,2) [shape=rectangle] {
\scriptsize
d:
\begin{tabular}{|c|c|}\hline
  a & a\\
  b & a\\
  c & c\\
  e & e\\
  f & c\\
  g & e\\\hline
  \end{tabular}
};
\end{tikzpicture}


\subsection{Routage hiérarchique }

Problème: la table a autant d'entrées que de noeuds dans le graphe.

Internet IPv4 : $\sim 2^{32} = ~\sim 4 $ milliard... 

\medskip

Solution: Routage hiérarchique

Chaque le réseau est divisé en sous réseaux:
\begin{itemize}
\item les adresses sont hiérarchiques, du type "sous-reseau.machine"
\item chaque sous réseau $S$ sait comment router ses paquets
\item en dehors du sous-réseau $S$, tous les paquets vers une machine de $S$ est routé vers le même routeur, un point d'entrée de $S$. 
\end{itemize}


\definecolor{lavander}{cmyk}{0,0.48,0,0}
\definecolor{violet}{cmyk}{0.79,0.88,0,0}
\definecolor{burntorange}{cmyk}{0,0.52,1,0}

\def\lav{lavander!90}
\def\oran{orange!30}
\tikzstyle{noeud}=[draw,circle,burntorange, left color=\oran,
                       text=violet,minimum width=20pt]

\begin{tikzpicture}[auto, thick]
  \foreach \place/\name in {{(0,-1)/a1},{(-1,-1)/a2},{(0,-2)/a3},
  	   {(3,-1)/b1},{(4,-1)/b2},
	   {(0,3)/c1},{(-1,4)/c2},
           {(3,3)/d1},{(3,4)/d2},{(4,3)/d3},
	   {(6,2)/e1},{(6,3)/e2},{(7,2)/e3}}
    \node[noeud] (\name) at \place {\footnotesize \name};
  \foreach \source/\dest in {c1/c2,a1/a2, a1/a3, a2/a3, a1/b1, c1/d1, a1/c2, b1/d1,d1/d2,d1/d3,b1/b2,e1/e2,e1/e3,e1/b2,e1/d3,e2/e3}
    \path (\source) edge (\dest);
\node at (1.5,0.5) [shape=rectangle] {
\scriptsize
b1:
\begin{tabular}{|c|c|}\hline
  b2 & b2\\
  a & a1\\
  c & a1\\
  d & d1\\
  e & b2\\\hline
  \end{tabular}
};
\node at (7,0) [shape=rectangle] {
\scriptsize
e1:
\begin{tabular}{|c|c|}\hline
  e2 & e2\\
  e3 & e3\\
  a & b2\\
  b & b2\\
  c & d3\\
  d & d3\\\hline
  \end{tabular}
};
\node at (8,4) [shape=rectangle] {
\scriptsize
e3:
\begin{tabular}{|c|c|}\hline
  e1 & e1\\
  e2 & e2\\
  a & e1\\
  b & e1\\
  c & e1\\
  d & e1\\\hline
  \end{tabular}
};
\end{tikzpicture}


\subsection{Trouver les tables}

Les tables de routage peuvent être définies statiquement (routage statique), ou dynamiquement\pause

\medskip

\begin{itemize}
\item Statique: L'administrateur de la machine/routeur définit les entrées de la table.\pause

 Cas habituel pour vos machines.\pause

 Problème: ingérable pour les routeurs internes\pause
\item Dynamique: Le routeur construit lui même sa table de routage, en partageant des informations avec ses voisins
\end{itemize}

\medskip\pause

Comment un routeur peut faire pour remplir/compléter/mettre à jour sa table de routage ?

\subsection{Routage par inondation}

Découverte de routes par inondation:

Si on ne connaît pas la direction pour un noeud, on peut faire une diffusion générale ("broadcast") d'un paquet demandant où se trouve le noeud \pause

Chaque routeur qui reçoit le paquet de demande: soit
\begin{itemize}
\item répond si il sait, ou
\item renvoie le paquet à tous ses autres voisins\pause
\end{itemize}

Problème : lourd\pause

\medskip

Pour éviter de trop encombrer le réseau:
\begin{itemize}
\item Chaque requête possède un numéro. On garde mémoire des requêtes déjà renvoyées, pour ne pas le faire une deuxième fois\pause
\item Pour chaque demande non satisfaite, on attend un petit moment avant de la renvoyer. Si on reçoit la même demande entre temps d'un autre voisin, on ne la lui retransmettra pas.
\end{itemize}

\subsection{Plus court chemin}


Si un routeur connaît la topologie du réseau, il peut effectuer un algorithme du plus court chemin (comme l'algorithme de Dijkstra)\pause

\medskip

$\Rightarrow$ plus court chemin dans un graphe 

\bigskip\pause

Avantage: poids sur les liens (distance, prix...)\pause

\medskip

Problème : il faut connaître toute la topologie du réseau

\subsection{Vecteur de distance (Bellman-Ford)}

\begin{itemize}
\item Chaque routeur connaît la distance vers ses voisins. ($d_i$) 
\item Distance: nombre de sauts, délai de propagation...\pause
\item Chaque routeur maintient (en plus de sa table de routage) une liste de distance estimée à tous les noeuds du réseau ("vecteur")\pause
\item Chaque routeur envoie régulièrement à tous ses voisins ce vecteur\pause
\item Le routeur met à jour sa table de routage: \pause pour chaque noeud $x$ dont il a connaissance, il route le paquet vers le voisin $i$ qui minimise $d_i + V_i[x]$. (Et met à jour son vecteur de distance en même temps)\pause
\end{itemize}

\medskip

Problème: si une route disparaît, l'information mettra du temps à être corrigée... (problème de la valeur infinie)

\subsection{État de lien}

Routage par informations d'état de lien:

\begin{itemize}
\item Chaque routeur construit un paquet avec l'ensemble de ses voisins, et la distance\pause
\item Le paquet est broadcasté sur tout le réseau (avec un numéro de séquence)\pause
\end{itemize}

\begin{itemize}
\item Chaque routeur connaît donc l'ensemble des noeuds et leurs voisins, et peut reconstruire le graphe\pause
\item Les routes sont décidées grâce à un algorithme comme Dijkstra
\end{itemize}


\subsection{Contrôle de la congestion}

En cas de congestion, il peut y avoir l'effondrement du débit du réseau:
\begin{itemize}
\item les émetteurs retransmettent les paquets perdus (ou trop retardés), qui seront à nouveau perdus...\pause
\end{itemize}

\medskip

Lors d'une congestion, que faire ?\pause
\begin{itemize}
\item augmenter la capacité du lien\pause
\item rerouter sur une route moins encombrée\pause
\item avertir les sources\pause
\item contrôle d'admission\pause
\item éliminer des paquets...
\end{itemize}

\subsection{Qualité de service (QoS)}

Toutes les applications utilisant le réseau n'ont pas les mêmes besoins. \pause Par exemple:

\begin{itemize}
\item Visio-conf: demande haute en délai, faible en fiabilité, haute en bande passante
\item Mail: demande faible en délai, haute en fiabilité, faible en bande passante\pause
\end{itemize}

\medskip

Les algorithmes de routage peuvent considérer plusieurs classes de paquets 

Par exemple: on préfère perdre des paquets plutôt que les faire attendre lors des congestions.

\subsection{Internet Protocol}

Protocole réseau utilisé sur Internet : IP (Internet Protocol). Deux versions: 

\begin{itemize}
\item IPv4 : le plus utilisé actuellement, mais un nombre d'adresses limité (< $2^{32}$). 
\item IPv6 : la nouvelle norme, partiellement en place
\end{itemize}

Routage de paquets, store-and-forward

\subsection{Entête IPv4}

\hspace*{-1cm}\scalebox{0.75}{
\begin{tikzpicture}[scale=0.47]
	\foreach \x in {0,...,31}
		\node at (\x+0.5,20.5) {\scriptsize \x};
	\foreach \x in {0,...,31}
		\node at (\x+0.5,13.5) {\scriptsize \x};
	\foreach \x in {0,...,32}
		\draw[thick, blue] (\x,13) -- (\x,21);
	\node[thick] (bit1) at (-0.5,20.5) {\scriptsize bit};
	\node[thick] (bit2) at (-0.5,13.5) {\scriptsize bit};
	\draw [<->, thick] (-0.5, 19.9) -- (-0.5,15.1);
	\draw [thick] (-1, 20) -- (-0.1,20);
	\draw [thick] (-1, 15) -- (-0.1,15);
	\node[fill=white] at (-1.1,17.5) {\tiny 20 bytes};
	\filldraw[thick,draw=black, fill=white] (0,20) rectangle (4,19); \node (mode) at (2,19.5) {\scriptsize version};
	\filldraw[thick,draw=black, fill=white] (4,20) rectangle (8,19); \node (mode) at (6,19.68) {\tiny header length};\node (mode) at (6,19.25) {\tiny with options};
	\draw[thick, draw=black, fill=white] (8,20) rectangle (14,19); \node (stratum) at (11,19.5) {\scriptsize DSCP}; %type of service (TOS)};
	\draw[thick, draw=black, fill=white] (14,20) rectangle (16,19); \node (stratum) at (15,19.5) {\scriptsize ECN}; %type of service (TOS)};
	\draw[thick, draw=black, fill=white] (16,20) rectangle (32,19); \node (li) at (24,19.5) {\scriptsize full length of packet};
	\filldraw[thick,draw=black, fill=white] (0,19) rectangle (16,18); \node (mode) at (8,18.5) {\scriptsize identification};
	\draw[thick, draw=black] (16,19) rectangle (19,18); \filldraw[white] (16.5,18.43) rectangle (19,18.88); \node [](li) at (17.5,18.67) {\tiny IP flags}; \node at (16.5,18.25) {\tiny 0};\node at (17.5,18.25) {\tiny D};\node at (18.5,18.25) {\tiny M};
	\draw[thick, draw=black, fill=white] (19,19) rectangle (32,18); \node (li) at (24,18.5) {\scriptsize fragment Offset};
	\filldraw[thick,draw=black, fill=white] (0,18) rectangle (8,17); \node (mode) at (4,17.5) {\scriptsize time to live (TTL)};
	\draw[thick, draw=black, fill=white] (8,18) rectangle (16,17); \node (stratum) at (11.5,17.5) {\scriptsize protocol};
	\draw[thick, draw=black, fill=white] (16,18) rectangle (32,17); \node (li) at (24,17.5) {\scriptsize header checksum};
	\filldraw[thick,draw=black, fill=white] (0,17) rectangle (32,16); \node (mode) at (16,16.5) {\scriptsize source IP address};
	\filldraw[thick,draw=black, fill=white] (0,16) rectangle (32,15); \node (mode) at (16,15.5) {\scriptsize destination IP address};
	\draw[thick,draw=black, fill=white] (0,15) rectangle (31.5,14);
	\draw[fill=white, draw=white] (31.4,14.96) rectangle (31.6,14.05);
	%\draw[thick]  (31.5,14.97)  decorate [decoration=saw] { -- (31.5,14.02)};	\node (mode) at (16,14.5) {\scriptsize IP options (variable length)};
	\filldraw[thick,draw=black, fill=white] (0,15) rectangle (32,14);\node (mode) at (16,14.5) {\scriptsize IP options (variable length)};
\end{tikzpicture}
  }

{
\scriptsize

\begin{itemize}
\item Version = 4
\item DSCP (Differentiated Services Code Point) :  Classe du paquet (QoS)
\item ECN (Explicit Congestion Notification)
\item Identification / D / M / Framgent Offset : Quand un paquet est fragmenté, tous les fragments qu'un paquet contiennent la même identification. Fragment Offset continent la position du fragment. (D: Don't fragment. M: More fragment)
\item TTL : décrémenté à chaque saut (retransmission par un routeur). Quand il atteint 0, le paquet est éliminé (et un message ICMP est envoyé à la source)
\item Protocol : TCP=6, UDP=17, ICMP=1...
\item Options: Routage strict, enregistrement de la route...
\end{itemize}

Attention: Big endian !
}

\subsection{Adresses IPv4}

Une adresse IPv4 = 32 bits
\begin{itemize}
\item c-à-d 4 octets, ou
\item 4 entiers de 0 à 255.
\end{itemize}

Notation a.b.c.d. Ex: \cmd{192.168.1.1}

\medskip\pause

ICANN (Internet Corporation for Assigned Names and Numbers) fournit les adresses 

\medskip\pause

Organisées hiérarchiquement en sous-réseaux

\subsection{Sous réseaux IPv4}

Un sous réseau possède une adresse IP $i$, et un masque $m$ de sous-réseau

\medskip

Toutes les adresses IP $j$  telles que $j \& m = i$ font parties du sous-réseau.

\medskip

Masque (ou netmask): en binaire: suite de $k$ '1', puis de $32\!-\!k$ '0'

Notation: ip/k  :

Exemple: \cmd{192.168.1.0/24} signifie que:
\begin{itemize}
\item le masque est \cmd{255.255.255.0}
\item le sous réseau va de \cmd{192.168.1.0} à \cmd{192.168.1.255}
\end{itemize}


\subsection{Sous réseaux IPv4 : Exemple}

\begin{itemize}
\item Machine (hôte) d'adresse IP:  \cmd{147.222.23.42}
\item Sur le réseau: \cmd{147.222.16.0/20}
\item $\Rightarrow$ Masque réseau: 255.255.240.0
\end{itemize}

\medskip

{\scriptsize

\def\un{\hspace*{-0.15cm}$1$\hspace*{-0.15cm}}
\def\ze{\hspace*{-0.15cm}$0$\hspace*{-0.15cm}}


\begin{tabular}{|c||*{7}{c|}c"*{7}{c|}c"*{7}{c|}c"*{8}{c|}}
\hline
Adresse hôte    & \multicolumn{8}{c"}{147} & \multicolumn{8}{c"}{222} & \multicolumn{8}{c"}{23} & \multicolumn{8}{c|}{42} \\\hline
Adresse hôte    & \un&\ze&\ze&\un&\ze&\ze&\un&\un& \un&\un&\ze&\un&\un&\un&\un&\ze& \ze&\ze&\ze&\un&\ze&\un&\un&\un& \ze&\ze&\un&\ze&\un&\ze&\un&\ze\\\hline
Masque          & \un&\un&\un&\un&\un&\un&\un&\un& \un&\un&\un&\un&\un&\un&\un&\un& \un&\un&\un&\un&\ze&\ze&\ze&\ze& \ze&\ze&\ze&\ze&\ze&\ze&\ze&\ze\\\hline
Adresse réseau  & \un&\ze&\ze&\un&\ze&\ze&\un&\un& \un&\un&\ze&\un&\un&\un&\un&\ze& \ze&\ze&\ze&\un&\ze&\ze&\ze&\ze& \ze&\ze&\ze&\ze&\ze&\ze&\ze&\ze\\\hline
Adresse réseau  & \multicolumn{8}{c"}{147} & \multicolumn{8}{c"}{222} & \multicolumn{8}{c"}{16} & \multicolumn{8}{c|}{0} \\\hline
 & \multicolumn{20}{c|}{Champ sous-réseau}&\multicolumn{12}{c|}{Champ hôte}\\\hline
\end{tabular}
}

\subsection{Routage simple }

Pour voir/configurer les interfaces réseaux et les adresses IP/masque: \cmd{ifconfig}.\pause

Routage statique via une passerelle (cas simple de routage)

\begin{itemize}
\item Tous les paquets pour les adresses IP dans le réseau sont envoyé directement au destinataire via Ethernet (ou Wifi, ou la couche liaison du réseau)
\item Tous les autres paquets sont envoyés à la passerelle (l'adresse IP de l'interface du routeur qui est connecté au reste d'Internet)\pause
\end{itemize}

\medskip

Pour voir/configurer les routes sur Linux : \cmd{route}\pause

\begin{lstlisting}[basicstyle=\footnotesize]
Table de routage IP du noyau
Destination  Passerelle  Genmask        ... Iface
0.0.0.0.     140.77.12.1 0.0.0.0             eth0
140.77.12.0  0.0.0.0     255.255.254.0       eth0
169.254.0.0  0.0.0.0     255.255.0.0         eth0
\end{lstlisting}\pause

(Règle du "plus grand préfixe commun")

\subsection{Adresses réservées}

Certaines plages d'adresses sont réservées:
\begin{itemize}
\item 127.0.0.0/8 : Bouclage interne
\item 255.255.255.255/32 : Broadcast local
\item 10.0.0.0/8, 172.16.0.0/12, 196.168.0.0/16 : Adresses privées (NAT)
\item 169.254.0.0/16 : lien local
\item 224.0.0.0/4 : multicast
\item 240.0.0.0/4 : réservé pour une utilisation future...
\item ...
\end{itemize}

\subsection{NAT (Network Address Translation)}

Pour éviter de gaspiller les adresses et d'avoir à demander à l'ICANN des adresses pour les machines personnelles ou qui ne nécessitent pas une adresse IP visible de l'extérieur (pas de serveur)\pause
\begin{itemize}
\item Assigner à un sous-réseau local une seule adresse IP (\cmd{addr}) pour internet\pause
\end{itemize}

\medskip

Principe de NAT: %Assigner à un sous-réseau local une seule adresse IP (\cmd{addr}) pour internet

\begin{itemize}
\item Les machines à l'intérieur du réseau local ont une adresse IP en \cmd{192.168.0.0/16}, \cmd{10.0.0.0/8} ou \cmd{172.16.0.0/12}.\pause
\item Quand elles veulent envoyer un paquet à Internet, elles passent par une passerelle, qui est connectée à Internet via l'adresse \cmd{addr}\pause
\item La passerelle remplace dans le paquet IP l'adresse du réseau local en \cmd{addr} avant d'envoyer le paquet sur Internet\pause
\item Quand la passerelle reçoit un paquet depuis internet, elle analyse les entêtes des paquets TCP et UDP, et regarde le port utilisé pour retrouver l'adresse du destinataire dans le réseau.
\end{itemize}

\subsection{IPv6}

Problème d'IPv4:
\begin{itemize}
\item Seulement $2^{32}$ adresses
\item Tables de routage trop longues, dû à la fragmentation en sous-réseaux trop petits\pause
\end{itemize}

Solution : IPv6\pause

\medskip

Changements entre IPv4 et IPv6:
\begin{itemize}
\item Adresses sur $128$ bits\pause
\item Simplification de l'en-tête\pause
\item Suppression de la somme de contrôle\pause
\item Suppression de la fragmentation des paquets en cours de route\pause
\item IPsec (Internet Protocol Security)
\item ...
\end{itemize}

\subsection{Entête IPv6}

\hspace*{-1cm}\scalebox{.75}{
  \begin{tikzpicture}[scale=0.47]
	\foreach \x in {0,...,31}
		\node at (\x+0.5,20.5) {\scriptsize \x};
	\foreach \x in {0,...,31}
		\node at (\x+0.5,9.5) {\scriptsize \x};
	\foreach \x in {0,...,32}
		\draw[thick, blue] (\x,9) -- (\x,21);
	\node[thick] (bit1) at (-0.5,20.5) {\scriptsize bit};
	\node[thick] (bit2) at (-0.5,9.5) {\scriptsize bit};
	\draw [<->, thick] (-0.5, 19.9) -- (-0.5,10.1);
	\draw [thick] (-1, 20) -- (-0.1,20);
	\draw [thick] (-1, 10) -- (-0.1,10);
	\node[fill=white] at (-1.1,15) {\tiny 40 bytes};
	\filldraw[thick,draw=black, fill=white] (0,20) rectangle (4,19); \node (mode) at (2,19.5) {\scriptsize version};
	\filldraw[thick,draw=black, fill=white] (4,20) rectangle (12,19); \node (mode) at (8,19.5) {\scriptsize traffic class};
	\filldraw[thick,draw=black, fill=white] (12,20) rectangle (32,19); \node (mode) at (22,19.5) {\scriptsize flow label};
	\filldraw[thick,draw=black, fill=white] (0,19) rectangle (16,18); \node (mode) at (8,18.5) {\scriptsize payload length};
	\filldraw[thick,draw=black, fill=white] (16,19) rectangle (24,18); \node (mode) at (20,18.5) {\scriptsize next header};
	\filldraw[thick,draw=black, fill=white] (24,19) rectangle (32,18); \node (mode) at (28,18.5) {\scriptsize hop limit};
	\filldraw[thick,draw=black, fill=white] (0,18) rectangle (32,14); \node (mode) at (16,16) {\scriptsize source IP address};
	\filldraw[thick,draw=black, fill=white] (0,14) rectangle (32,10); \node (mode) at (16,12) {\scriptsize destination IP address};
\end{tikzpicture}
}

{
\small

\begin{itemize}
\item version = 6
\item traffic class = DSCP/ECN de IPv4
\item flow label: identification du flux (réservation / QoS)
\item hop limit : le nouveau nom du "time to live"
\item next header : soit le contenu du prochain entête facultatif (option), soit le protocole
\item options: informations sur la fragmentation, routage, chiffrement...
\end{itemize}
}

\subsection{Adresse IPv6}

8 blocs de 16 octets.

Les blocs sont écrits en hexadécimal, séparés par "\cmd{:}" \pause

\begin{itemize}
\item On peut omettre les 0 de début de blocs 
\item Un ou plusieurs blocs consécutifs à 0 peuvent être remplacés par "\cmd{::}" \pause
\end{itemize}

\medskip

Exemple:

\cmd{fe80:0000:0000:0000:028d:99ff:fec1:0078}=

\cmd{fe80::28d:99ff:fec1:78}

\subsection{Protocoles de gestion }

La couche IP contient d'autres protocoles (de gestion):

\begin{itemize}
\item ICMP : messages de contrôle IPv4
\item ICMPv6 : messages de contrôle IPv6
\item ARP/RARP : résolution d'adresse
\item DHCP : configuration dynamique 
\item IGMP
\item ...
\end{itemize}

\subsection{ICMP}

ICMP = Internet Control Message Protocol

Paquets ICMP:
\begin{itemize}
\item destination inaccessible
\item délai expiré
\item demande/envoi d'écho (\cmd{ping})
\item problème d'en-tête
\item ...
\end{itemize}

\medskip

Commandes utilisant les messages ICMP: \cmd{ping}, \cmd{traceroute}

\subsection{ARP}

ARP = Address Resolution Protocol

\medskip

Permet, dans un sous-réseau, de trouver la correspondance entre l'adresse IP d'une interface et son adresse MAC. \pause Principe:

\begin{itemize}
\item Quand un noeud ne connaît pas l'adresse MAC associée à une adresse IP, il envoie un paquet "broadcast" (à tout le monde) demandant:
\item "Je suis (adresse IP)/(adresse MAC). À qui appartient (adresse IP) ?"
\item L'ordinateur possédant l'adresse IP répond. 
\end{itemize}

\medskip

\begin{itemize}
\item RARP (Reverse ARP) : demande l'adresse IP à partir de l'adresse MAC
\end{itemize}

\medskip

Commande: \cmd{arp}


\subsection{DHCP}

DHCP = Dynamic Host Configuration Protocol

\medskip

Un noeud sur un réseau peut demander, via ce protocole, une adresse IP \pause ~et la configuration du réseau (Masque, adresse IP de la passerelle, serveurs DNS...)\pause

\medskip

\begin{itemize}
\item Il envoie un message broadcast\pause
\item Un serveur DHCP (normalement, un serveur pour tout le sous-réseau) se charge d'assigner les adresses, et de répondre. \pause
\end{itemize}

\bigskip

Commandes: \cmd{dhcpd} / \cmd{dhclient}

\subsection{Algorithmes de routage sur Internet}

Internet est un réseau de réseaux. Il n'y a pas un unique algorithme de routage. Chaque sous-réseau peut utiliser le sien.\pause

Plusieurs algorithmes existent.

\medskip
Pour les "Système Autonome" (FAI, RENATER...)
\begin{itemize}
\item RIP (Routing Information Protocol) : vecteurs de distance
\item IGRP (Interior Gateway Routing Protocol) : vecteurs de distance
\item OSPF (Open Shortest Path First) : état de liens
\item IS-IS (Intermediate system to intermediate system): état de liens\pause
\end{itemize}

\bigskip

Entre système autonomes: des considérations économiques et politiques s'ajoutent. Par exemple: certains liens sont payants.\pause

BRG (Border Gateway Protocol) : Vecteurs de chemins






