#+TITLE : Prise de notes CM 4I400 PSCR
Yann Thierry-Mieg ([email protected]) 4I400
Des références de C++, des références de concurrence, des rappels de C.
Makefile pour chaque exo.
Débogage Implanter une synchro Exercice de correction de code à cause de synchro
TDTME de la dernière semaine (mutex et conditions variables, moitié des points) Structure de données pas trop dure, implémenter une fonction Makefile simple.
Petit bout de code à déboguer éventuellement (en deux parties : une compilation, une erreurs franches).
valgrind
14-15 302 : pas le home (les programmes précompilés doivent être amenés avec la clé USB).
C++ presque sur-ensemble du C98
On retrouve les :
- types de données (variantes non signées)
- struct, tableaux, pointeurs
- partage mémoire entre le tas et la pile
En plus :
- Objet, classes, instances
- Namespace (fonctions rangées dans des paquets)
- Typage nouveau : référence
- Annotation const
- Polymorphisme
Par rapport à Java :
- Mêmes notions de classe, surcharge, héritage, même genre de syntaxe.
- On gère la mémoire nous-même
- Généricité un peu moins propre. Implanté dans le compilateur par une succession de macros. (en Java, erasetype)
- Accès à la mémoire et au noyau (pas de VM), beaucoup plus performant.
- En contrepartie, on a la réflexion, introspection, dynamicité
On écrit les bibliothèques en C++, et on assemble avec Python (3 !).
On reprend la structure d’un programme C propre, avec déclaration et implémentation séparée, puis un main séparé.
#pragma once Défense contre les doubles déclarations.
PréProcesseur se contente de résoudre les include pour faire un gros fichier.
Chaque fichier (non en-tête) source est compilé séparément. Petite vérifications syntaxique (déclaration et typage, grossièrement).
Le .o qui sort est le code assembleur (agglomération d’une série de fonction).
On va chercher dans le main.o les références externes, on va chercher le référencé dans le point.o, on inclut.
On peut lier de deux manière :
- statique (On recopie les fonctions), complet, pas de dépendances runtime
- dynamique (seulement pour la lib standard ?, on laisse la référence), incomplet, il faut que la lib soit là, sinon ça marche pas : il reste des dépendances runtime.
On compile
ar(1) se contente de mettre des .o bout à bout. .a lib statique
g++ -shared .so (.dll sous Windows) lib dynamique
g++ -l<lib> <main> : liaison dynamique g++ <lib> <main> : liaison statique
ldd(1) donne la liste des lib dépendances runtime d’un exécutable.
Le processus a une plage d’adresse (virtuelles) de 0 jusqu’à la taille du pointeur (2^64) : la mémoire vue par le processus (beaucoup plus que la vraie mémoire, on se doute).
L’OS doit traduire la mémoire virtuelle en adresse mémoire physique.
Le binaire va dans le segment de code de l’espace d’adressage du processus. Segment stack Main tout en bas.
Les adresses en dessous sont illégitimes sauf si elles ont été réservées explicitement (malloc ou new) : sinon, segfault.
On a aussi une liste des descripteurs de fichier et des entrées et sorties standard.
Ne pas se faire avoir si on veut que les fonctions fassent vraiment quelque chose en dehors de leur stack frame.
Struct et class, c’est presque la même chose en C++. Struct tous les champs sont publics par défaut, class sont tous privés par défaut.
Constructeur, porte le même nom que la classe. L’autre méthode n’a pas besoin de paramètres, c’est le contexte courant (on y accèdera par ‘this’).
Chaque class ou struct définit implicitement un namespace homonyme.
Pointeur particulier “this” vers l’objet courant. (Donc en fait chaque fonction admet un paramètre implicite, le pointeur vers l’objet courant)
polymorphisme : opération valable sur plusieurs types, capable de reconnaître un type et d’agir en conséquence.
Idée que les opérateurs peuvent être redéfinis.
#include <iostream>
int main()
{
std::cout << "Hello, World !" << std::endl;
return 0;
}Ici les opérateurs << et >> sont redéfinissables. Ce sont des flux, connectables sur plein d’autres choses que les entrées et sorties standard.
char * est interprété par cet opérateur comme un string.
Beaucoup trop.
Un type booléen (assez inutile) Le nullptr, comme le NULL de C. (comparaisons avec d’autres types autorisés, contrairement à NULL).
Beaucoup beaucoup trop.
Ne pas hésiter à mettre beaucoup de parenthèses.
Certains opérateurs peuvent être redéfinis. (liste complète dans le support).
const
const dans les paramètres : pas de modification dans le corps de la fonction (juste pour déboguage, pas utilisable en soi, passage par copie)
const avec un pointeur ou une référence dans les paramètres permet de cumuler la sécurité du passage par valeur et la vitesse du passage par référence
Passage par référence :
void nique(int& i)
{
int a = 30;
i = a;
}
int main()
{
int x = 100;
std::cout << x << std::endl;
nique(x);
std::cout << x << std::endl;
return 0;
}Différence avec le pointeur (on ne déréférence pas avec *), et la référence ne peut pas être nulle.
On ne peut pas passer un littéral par référence : en effet, leur adresse est dans une zone de la mémoire protégée en écriture.
On peut retourner une référence en retour de fonction.
La référence doit toujours être initialisée, on peut l’assimiler à un pointeur constant.
“Const, c’est comme la GPL, c’est contaminant”
On peut définir des valeurs par défaut pour les arguments :
void f(int i , char c = 'a', int n = 10);Tous les appels suivants sont valides :
f(1, 'c', 2);
f(2, 'z'); // Correspond à f(2, 'z', 10)
f(2); // Correspond à f(2, 'a', 10)Les méthodes d’une classe peuvent être surchargées.
Le but est de faire en sorte que tous les objets soient initialisés. De préférence une seule fois.
Il faut distinguer l’espace d’adressage virtuel et la mémoire physique.
Le principe de new (et de malloc aussi, en fait), c’est de réserver une zone de l’espace d’adressage et de créer une correspondance avec la mémoire physique.
Une variable ou une méthode statique instanciée n’est pas logée dans la section de pile correspondant à la méthode, mais dans la section de code de l’espace d’adressage.
On peut redéfinir les opérateurs pour une classe bien précise.
Le but d’un opérateur est de fournir une notation plus conventionnelle et lisible que les notations fonctionnelles pointées.
Donc on peut surcharger un opérateur :
- Par une fonction. Au moins une opérande doit être de type classe
- Par une méthode d’une classe : La première opérande est l’objet pour laquelle la méthode est invoquée.
Chaque fois qu’une instance est supprimée, seul ce qui a été mis dans la pile est supprimé automatiquement. Ce qui a été alloué dynamiquement doit être enlevé manuellement.
Si la classe qu’on créé fait de l’allocation dynamique dans le tas, il est de bon ton de s’assurer que cette classe dispose de :
- Un constructeur par copie
- Opérateur d’affectation
- Un destructeur
De plus, pour toutes les classes :
- Un constructeur vide, qui initialise directement à des bonnes valeurs.
Toute fonction peut être déclarée amie d’une ou plusieurs classes.
Une fonction amie peut accéder directement aux éléments privés de la classe, sans passer par une méthode.
template <typename T>
T sum (T a, T b)
{
return a + b;
}(classname fonctionne aussi)
Le compilateur va générer une fonction qui correspond au type.
Directement dans les fichiers d’en-tête.
On peut forcer une promotion de type :
sum<string>('a', 'b');On peut faire la même chose avec des classes
template <typename T>
class mypair {
T values[2];
public:
mypair(T first, T second) {
values[0] = first;
values[1] = second;
}
};auto mot-clé introduit en C++11, permet au compilateur d’inférer le type de données.
auto d = 5.0;
auto i = 1 + 2;On peut mettre auto en retour de fonction à partir de C++14
Existe en copie (auto) et en référence (auto &)
Pratique mais casse-gueule.
Apparemment, la bibliothèque standard de C est “vide”.
Inclut la lib standard du C.
Pour se servir d’une bibliothèque C :
extern "C" {
// Déclaration des fonctions et en-têtes C
}- iosfwd : en-têtes
- flux I/O standard
- flux fichiers (lecture écriture simultanée) : Descripteur de fichier, mais par flux.
- sstream (tampons mémoire).
Le flux vient de l’idée qu’on ne veut pas surallouer. Dans une opération complexe, on préfère faire les opérations simples successives sur un même objet dynamique, le flux.
Les opérateurs relatifs sont définis ici.
Le == entre les strings en C++ compare les noms (en C, il compare les pointeurs). Le + entre une string et un entier se comprend comme de l’arithmétique des pointeurs : on se décale dans la string.
Dans le cas des données simples, peut permettre de se passer d’une grammaire et d’un parser. Peut manipuler les strings comme sed ou awk aurait permis de le faire.
Il en existe un certain nombre dans la lib standard
Stockage contigu en mémoire. Accès à n’importe quel élément en temps constant.
Stockage compact, pas de surcoût mémoire. C’est la manière canonique de faire de l’allocation dynamique (plus que new ou malloc).
Bonne continuité spatiale, se cache bien.
Insertion en milieu de vecteur : O(n)
Liste doublement chaînée. Insertion en milieu de liste O(1) : d’autres Pas cachable : mauvaise continuité
Pareil que le vecteur, mais queue à deux fins : les opérations en queue et en tête sont très peu chères (par rapport au vecteur, pour qui les opérations en tête sont coûteuses)
Arbre binaire (R/N) Très bon pour la recherche : log(n) Efficace pour l’insertion : log(n)
T le type des éléments allocateur Comparaison, hachage
begin et end : itérateurs pratiques (end est past the end)
Mais c’est tout.
Tous les itérateurs ne se valent pas. Selon le conteneur, plus ou moins d’opérateurs sont supportés.
Il y a toujours des collisions.
On obtient une valeur difficilement réversible.
On fait % le nombre d’éléments du bucket : endroit où je vais chercher dans ma table.
Comparaison d’égalité.
La seule manière d’être dans un mauvais jour, c’est la collision (plutôt la modulo-collision) : on chaîne les structures de dépassement à la première en mode liste chaînée.
Une bonne fonction de hachage est uniforme, on remplit bien les buckets. Une mauvaise fonction de hachage met tous les éléments dans le même bucket, qui devient une très longue liste chaînée.
On aime aussi bien les fonctions de hachage qui mettent loin les entrées proches les unes des autres.
Ensemble de pointeurs intelligents, capables de désallouer la mémoire dès qu’un compteur de références tombe à 0 (version unique et partagée).
Un ensemble de fonctions utiles présents sur la plupart des conteneurs.
Se séparent entre les algorithmes sans modification, et les algorithmes avec modification.
Plusieurs genres de fonction de recherche :
- Rendent un itérateur sur le résultat.
remove va juste shift les trucs enlevés à la fin, et changer la valeur de l’itérateur end sur la première des valeurs supprimées (soit juste après la fin des valeurs non enlevées) erase va effectivement supprimer les cases.
Remove rend un itérateur vers le premier élément qu’on a foutu à la fin, si on la met dans une variable auto on peut ensuite erase à partir de la variable.
En C, on utilise le pointeur de fonction.
int foo(int x)
{
return x;
}
int main()
{
int (*fcnPtr) (int) = foo; // pointeur d'un fonction qui prend int et qui rend int
(*fcnPtr)(5); // On appelle foo via son pointeur de fonction
fcnPtr(5); // On a aussi une déréférence implicite : fait la même chose que la ligne précédente
return 0;
}Notion de foncteur étend le pointeur de fonction.
En gros, le foncteur est un objet avec un opérateur () défini, ce qui fait qu’il peut être appelé comme une fonction, pourvu qu’on ait pris la peine de l’instancier avant (il faut bien entendu que l’opérateur soit dans la zone publique de l’object foncteur).
Sinon, pointeur sur des fonctions anonymes (lambda)
[](paramètres) -> type_retour {corps} peut remplacer un pointeur de fonction. [variable à inclure par copie], [&variable à inclure par référence], [=] par copie tout, [&] par référence tout : permet de capturer des variables du contexte local pour les donner à lambda.
Tout ne signifie pas exactement tout : le compilateur est chargé de ramener ce qu’on utilise effectivement dans le corps de la lambda.
Pointeur du tableau nu est homogène à un itérateur.
Yann Thierry-Mieg
On n’arrive pas à dépasser 5GHz.
L’augmentation du nombre de transistors (loi de Moore) passe par l’augmentation du nombre de coeurs.
Il faut donc, dans les programmes récents, savoir gérer la concurrence.
On était auparavant sûrs de ce que deux instructions, quand une était placée avant l’autre, qu’elle allait être exécutée avant l’autre. L’exécution était séquentielle par hypothèse.
Maintenant, sur des séquences concurrentes de code, cette hypothèses sautent, avec tous les problèmes que ça amène : plein d’actions, dont on pouvait être sûr de leur liaison logique et chronologique, flottent les unes par rapport aux autres.
De cette manière, là où un programme avait une seule exécution possible, on se retrouve avec un espace des exécutions possibles beaucoup plus grand.
Si on prend par exemple un programme avec K étapes qui peuvent être rendues concurrentes, et N threads, le nombre total d’entrelacements possibles des étapes est donné par K^N.
Pour s’assurer de ce que le programme fait bien exactement ce qu’on veut, autrement dit, si on veut s’assurer de sa sémantique, on doit introduire un certain nombre de synchronisations, qui serviront à exprimer explicitement des précédences entre différents points des threads.
Ces précédences explicites permettre de réduire le champ des exécutions possibles du programme, de manière à ce que ce champ ne dépasse pas la sémantique qu’on lui veut donner (si possible, on essaiera aussi de ne pas trop restreindre le champ des exécutions possibles au délà de ce qui est strictement nécessaire pour s’assurer de ce que la sémantique est préservée).
Chaque algorithmes dispose d’une partie séquentielle (pas accélérable) et une partie parallélisable (accélérable de manière proportionnelle en le nombre de processeurs).
On plafonne à partir du moment où n le nombres de processeurs dépasse le nombre d’opérations après découpage.
Ressources aux accès concurrents : ressources critiques.
Pas d’atomicité des instructions du C++ (et même pas en C non plus). 1 ligne de C++ produit N instructions assembleur impossibles à compter. C est un peu meilleur, on a presque une correspondance 1 pour 1.
Data Race Condition : Celui qui a écrit en dernier a raison sur la valeur de la variable.
Chacun demande une ressource pas dans le même ordre, si on manque de chance, on peut bloquer tous les fils. Problème des philosophes, Edgar Dijkstra (1955).
Explosion de l’espace d’état : on a plein d’exécutions possibles. On ne fait aucune hypothèse sur l’ordonnanceur, il fait ce qu’il veut, on ne le contrôle pas.
On doit penser à l’ordonnanceur comme mon ennemi (c’est le Malin Génie), pour s’assurer de ce que l’exécution se passe comme on veut.
Difficulté de reproduire les problèmes : l’occurence d’un problème est souvent due à des petits enchaînements subtils, qu’on ne peut pas reproduire facilement, que les entrées-sorties de débug font typiquement disparaître.
La distribution de probabilité est en effet défavorable aux fautes de concurrence. La commutation doit se passer au pire moment pour que la faute se produise : très peu probable sur un nombre fini d’exécutions. Mais avec un nombre d’exécutions qui augmente, la proba tend vers 1.
POSIX intègre les fils d’exécution dans la bibliothèque standard de C : spécifique aux machines POSIX. C++11 l’intègre directement dans le langage.
Les fils d’exécution n’ont aucune protection sur leur pile par rapport aux autres fils d’exécution du même processus lourd : espace d’adressage commun !!!!
Chaque thread soit avoir :
- Un mini-PCB (avec son pointeur de pile et son PC)
- une pile
- Tous ses attributs utilisés par l’ordonnanceur
- Traitement des signaux
En gros tout ce qui implique les interactions avec le noyau en tant que processus indépendant.
A l’instanciation, on lui passe un pointeur de fonction, puis les arguments de la fonction.
L’objet thread se termine quand il sort de la fonction : il est en état “zombie” (pas vraiment, mais c’est l’idée). Un join permet de récupérer son état.
#include <iostream>
#include <thread>
void foo()
{
// Faire des trucs
}
int main()
{
// Créer un thread avec foo un pointeur de fonction
std::thread first (foo);
// On peut faire d'autres trucs ici
first.join(); // On attend first.
std::cout << "foo completed" << std::endl;
return 0;
}Passage de paramètres :
Passage de références pose problème : autant une variable par copie est toujours valable dans une fonction (elles sont copiées localement, elles vivent dans la pile de la fonction), autant une référence (soit un pointeur déjà déréférencé) peut bien mourir (arrêter d’être légitime) à n’importe quelle moment de la vie du thread, sans que ce soit controllable par lui.
C’est au programmeur de garantir sa vie.
Elle est passée avec std::ref (référence) ou std::cref (pointeur).
Pas de valeur de retour de la fonction passée au thread : il faut modifier des données partagées (attention à la synchronisation).
void f1(int n, bool b);
void f2(int& n);
int main()
{
int value = 0;
std::thread t1(f1, value + 1, true);
std::thread t2(f2, std::ref(value));
// Faire des trucs
t1.join();
t2.join();
return 0;
}Demande explicite (pas contraignante) de commutation. Laisse l’occasion aux autres threads de prendre la main. Dépend des plateformes (évident : implique l’ordonnanceur)
Endormir le thread qui appelle. Variante sleep_until.
La durée du sleep n’est pas garantie : au moins la durée demandée, mais en fait plus.
Vivent dans le namespace this_thread
Détacher un thread permet de ne pas mettre de join, ils se termineront avec le main. (On ne doit pas avoir bien besoin de lui, si ce qu’il fait n’a pas besoin d’être join). Cas typique : statistiques d’arrière-plan.
atomic_boolean_flag
On se réfèrera aux diapositives 27-32 du cours 4 pour une illustration de l’implémentation matérielle. Carlinet.
Garantit l’atomicité de seulement un certain nombre d’opérations (seules les opérations bit par bit).
Sur une section critique (suite d’action cohérente), permet de protéger la section :
La structure ressemble à ça :
- Une file de threads bloqués
- Un booléen qui dit si le verrou est ouvert ou fermé (dans le cas d’un sémaphore, )
FIFO garantie (mais pas vraiment, l’ordonnanceur fait toujours un peu ce qu’il veut). Au réveil, le processus élu essaie de récupérer le lock tout seul.
Le mutex doit être le même pour les différents threads (sinon ça sert à rien).
Mutex récursifs : On a la possibilité avec une autre structure (std::recursive_mutex) de reprendre en plus le lock (à nouveau).
Il ne faut pas oublier le unlock !
unique_lock se détruit tout seul à la sortie de la portée.
unique_lock <mutex> lock(gi_mutex);Issu du principe RAII : si je sort du scope, il faut libérer.
Quel que soit la sortie, je suis garanti de ce que le lock est libéré. (confort, mais absolument pas nécessaire, et potentiellement casse-gueule).
Une classe multithread-safe est un classe qui implémente directement en elle-même la gestion de la synchronisation.
Comment se faire une classe multithread-safe :
On se donne un mutex comme attribut On met des unique_lock dans toutes les méthodes
mutable devant le nom d’un attribut reste modifiable malgré le caractère const d’une méthode.
Si les méthodes de la classe s’invoquent les unes les autres ?? recursive_mutex permet de réacquérir le lock déjà acquis.
Mutex spécifiques au problème du lecteur-rédacteur : va sûrement être implanté en TME ou en partiel.
Le système peut ordonner les locks : la fonction lock(<un ensemble de locks arbitraire>) peut garantir un ordre total sur tous les locks.
Permet de ne pas s’endormir si le verrou est déjà acquis (on peut aller faire autre chose). timed_lock permet de s’endormir pour un petit moment, puis va faire autre chose.
try_lock() est atomique : soit j’ai les deux, soit j’en ai aucun.
On créé des locks qui ne sont pas acquis de suite : permet d’avoir le meilleur des deux mondes :
- Utiliser la fonction lock() et donc demander au système de me protéger des interblocages
- Utiliser unique_lock et de ne pas avoir à unlock moi-même.
Cours “legacy”, similaire aux cours de Pierre Sens et Luciana Arantes.
Portable Operating System Interface for Computing Environments
Une interface unifiée et spécifiée. Une API qui garantit la portabilité pourvu qu’on utilise uniquement des fonctions POSIX.
Standard très concret : pour chaque service, on a un ensemble de spécifications que l’implantation doit suivre.
Un processus est, du point de vue de POSIX, c’est une entité active du système.
Le processus est un espace d’adressage virtuel.
On a un propriétaire réel, effectif, et un répertoire courant (cwd).
Vu qu’on a des espaces d’adressages distincts, comment on fait communiquer des processus ?
[rappels de choses connues]
En informatique, une fonction est dite à effet de bord (traduction mot à mot de l’anglais side effect, dont le sens est plus proche d’effet secondaire) si elle modifie un état en dehors de son environnement local, c’est-à-dire a une interaction observable avec le monde extérieur autre que retourner une valeur.
Ici, l’effet de bord est donné par l’intérieur de la fonction fork. En gros, la fonction fork retourne une valeur dans pid_fils, mais son vrai effet, c’est la duplication du processus qui se déroule en dehors de son environnement local.
On hérite de :
- UID et GID
- Identifiant de session
- cwd
- bits de umask
- masque de signaux, handlers
- envvars
- Segments de mémoire partagée
- Les descripteurs de fichiers ouverts (l’offset aussi)
- Nice
On n’hérite pas de :
- PID
- Temps d’exécution
- Signaux pendants
- Verrous de fichiers maintenus par le père
- Alarmes
Les appels systèmes sont exécutés en mode noyau (évidemment), ils sont exécutés sur une autre pile que celle des fonctions exécutées en mode utilisateur. Bien évidemment, l’utilisateur n’a pas accès, à son retour en mode U, aux piles noyau. Pour passer des arguments du mode U au mode S, et des retours dans le sens inverse, on doit manipuler directement la pile de l’utilisateur, ou placer les retours dans une zone accessible globalement.
perror est une fonction qui permet d’accéder au dernier numéro d’erreur errno rendu par un appel système.
Le fils a une valeur de retour, que le père peut interroger.
La primitive wait sert à la fois à bloquer le processus appelant, en attendant le exit d’un des processus fils, et sert aussi à récupérer la valeur de retour du fils en question.
Il existe des macros d’interprétation des valeurs de retours (qui sont bien entendu spécifiques à chaque OS).
exec est la primitive de recouvrement, elle permet de changer le segment de texte d’un processus par un texte valable du système de fichier (un binaire compilé pour la bonne architecture).
Un processus est un espace d’adressage, deux processus distincts ne voient donc pas la même mémoire.
Outils de communication :
- On peut manipuler des fichiers : tout le monde peut y accéder. Adosser la communication au système de fichier est une bonne idée : lent, mais bien stable.
- On peut se servir des signaux, ce qui est la manière la plus simple, mais qui transmet le moins d’information. Le système en envoie de base à tous les processus régulièrement.
- Les tubes ou tubes nommés (qui ont une belle sémantique producteur-consommateur) : peut être adossé au système de fichier, ou à une table en zone noyau de la mémoire centrale.
- Les segments de mémoire partagée anonymes ou nommés : peut être adossé au système de fichier, ou à une table en zone noyau en mémoire centrale.
- Les files de messages nommés ou anonymes : peut être adossé au système de fichier ou à une table en zone noyau en mémoire centrale
- Les sockets nommés ou anonymes : peut être adossé au système de fichier, ou à une table en zone noyau en mémoire centrale
En fait, quand une de ces choses-là est nommée, elle peut être adossée au système de fichier (c’est une des manières possibles, l’autre étant une table en mémoire centrale), un espace accessible à tous les processus (moyennant permissions). A ce moment-là, elles deviennent des fichiers (avec leur inode et tout et tout, accessible par descripteur de fichier et tout et tout), juste des fichiers un peu spéciaux.
Everything is a file.
Every UNIX programmer/conceptor for times immemorial
Outils de synchronisation :
- Sémaphore (mutex avec capacité et une condition dessus, plus une notification)
L’API signal du C++ fonctionne de la même manière que le positionnement du handler de signal POSIX ou même UNIX old-school : on ne change le handler que de la prochaine réception du signal en question (cf. cours Pierre Sens).
Les supports de cours :