Sensibilisation à la programmation concurrente (multitâche) à travers C++ (Cours Intégré)

Message envoyé sur Discord par un étudiant JIN durant l'année 2020-2021 :

Depuis quelques temps, j'observe que la majorité des tests techniques que nous devons passer dans le jeu vidéo traitent de multithreading. Or, au cours de notre scolarité, nous n'avons jamais abordé cela, ce qui fait que nous sommes systématiquement pénalisés. Et ce que ce soit à l'ENSIIE, ou à TSP (apparemment il s'agit d'une option de seconde année à TSP mais abordée de manière trop fragile, donc tout le monde ne l'a pas vu ou mal vu). Je pense que pour le jeu-vidéo, le multithreading est de plus en plus primordial à manipuler, aussi je viens vous suggérer d'aborder la question au cours du semestre de JIN. Je ne sais pas vraiment à quel moment cela peut se faire (peut-être au tout début de l'année sur le projet Unity avec monsieur Bouyer ?) mais il me semble important de parler de ce point, afin d'arriver moins décontenancés face aux tests techniques. Qu'en pensez-vous ?

Réponse à ce message = le présent Cours Intégré de 3h30 qui a pour objectif de vous présenter les notions essentielles, sans pouvoir tout détailler.

• Présenter :
  • Les outils liés au multitâche (plus exactement à la concurrence)
    • Threads et tâches (On met donc de côté la programmation multi-processus et la programmation distribuée (même si on retrouve les mêmes notions)
    • Outils de synchronisation
  • Les patrons de synhronisation (synchronization patterns) classiques
  • Les bonnes pratiques
• Illustrer cela avec des exemples de code C++ (en indiquant quand le code présenté est une spécificité C++).
• Vous donner l'envie d'imaginer un concept de jeu qui illustrerait tous ces mécanismes
  • Wooclap à la fin de la séance sur ce sujet !
  • Projet de 2ème année TSP cette année ? PFE JIN l'an prochain ?

La plupart des notions présentées ici sont anciennes. Par exemple, les sémaphores ont été inventés par Dijkstra dans les années 1960, alors qu'ils n'ont été intégrés qu'à C++ 20. En général, des notions apparaissant après C++ 11 peuvent être implémentées :

• en s'appuyant sur des fonctionnalités C++ 11.
  • OK pour portabilité ; KO pour lisibilité et performances.
  • Exemple : Un sémaphore (C++ 20) peut être implémenté avec un mutex et une std::condition_variable (C++ 11).
• en invoquant directement des appels système.
  • KO pour portabilité ; OK pour performances ; ? pour lisibilité.
  • Exemple : Un sémaphore (C++ 20) peut être implémenté en utilisant les sémaphores de la bibliothèque pthread (ex. : sem_init) ou ceux de Windows (ex. : CreateSemaphore).

Pour compiler les exemples, il est nécessaire de disposer d'un compilateur à jour :

• Au moins Visual Studio 16.11.3 (septembre 2021)
• Au moins gcc 11.1 (avril 2021). Le support de C++ 20 a l'air assez complet (cf. cette page).
  • Pour Ubuntu, cet article explique comment faire cohabiter le gcc standard et le gcc plus avancé.
• Concernant clang
  • Clang MacOS est en retard quant à l'adoption de C++ 20 (comparer les colonnes "Clang" et "Apple clang" en https://en.cppreference.com/w/cpp/compiler_support/20). Notez que les compilateurs Clang et Apple clang n'ont pas les mêmes numéros de version.
  • Sur Ubuntu/Windows, théoriquement, au moins clang 14.0.0. Pour ce cours, nous n'avons testé que la compilation des sources de ce cours avec clang 17.0.6 que nous avons installé sous Ubuntu de la manière suivante :
    • Suivre les instructions en https://ubuntuhandbook.org/index.php/2023/09/how-to-install-clang-17-or-16-in-ubuntu-22-04-20-04/
    • Pour utiliser ensuite clang à la place de gcc, ouvrir un terminal et y taper les intructions suivantes (NB : c'est ensuite dans ce terminal qu'on fera cmake et make) :

# cf. https://ubuntuclub.org/how-to-use-clang-instead-of-gcc-in-ubuntu/
export CC=/usr/bin/clang-17
export CPP=/usr/bin/clang-cpp-17
export CXX=/usr/bin/clang++-17
export LD=/usr/bin/ld.lld-17
#Description of environment variables:
#    CC : C compilerclang
#    CPP : C precompiled processorclang-cpp
#    CXX : C++ compilerclang++
#    LD : Linkerld.lld

Notions essentielles

• Ce mot-clé est disponible dans la plupart des langages de programmation.
• Il permet de dire au compilateur qu'il ne faut pas faire d'optimisation concernant une variable.
• Voir exemple en Code 01.

• Un thread est une entité système beaucoup plus légère (en temps de création et en mémoire) qu'un processus.
• Un thread a sa propre pile dans l'espace mémoire d'un processus (donc, la pile d'un thread est moins grande).
• Opérations sur les threads
  • Création
  • join : Attente de la terminaison d'un thread enfant par son créateur.
  • detach : Coupure du lien entre le thread enfant et son créateur.
• Les threads sont préemptifs, c'est-à-dire que, quand ils s'exécutent, ils peuvent être interrompues à n'importe quel moment par un autre thread. Nous verrons plus loin d'autres modèles de programmation.
• En Java, possibilité de définir des priorités d'exécution pour les threads. Non disponible dans le standard C++, mais contournement possible avec std::thread::native_handle() (Attention : appel pas obligatoirement implémenté).

Notions essentielles :

• Un "Diagramme de séquence" peut aider à comprendre les data race.
• Un "Diagramme de séquence" va de haut en bas, alors qu'un "Diagramme de temps" va de gauche à droite ;
• mscgen (https://www.mcternan.me.uk/mscgen/) est un outil intéressant pour faire rapidement des diagrammes de séquence.

Notions essentielles

• Opérations sur les mutex
  • lock : Un thread qui exécute cette instruction prend le mutex. Si un autre thread essaie de prendre ensuite le mutex, cet autre thread est bloqué jusqu'à ce que le premier thread relâche le mutex.
  • unlock : Un thread qui exécute cette instruction relâche le mutex et réveille un des threads qui avait fait lock sur ce même mutex.
• On appelle section critique le code entre les instructions lock() et unlock(). Le système d'exploitation garantit qu'à tout instant, un seul thread exécutera la section critique.
• ==> Pattern de synchronisation "section critique"
• Une section critique doit être la plus courte possible en temps d'exécution. Donc :
  • N'y mettre que le code qui a besoin d'être en section critique.
  • Jamais de sleep dans une section critique.
• Les mutex peuvent conduire au cauchemard des verrous mortels (deadlocks) ! Autant que possible, veillez à verrouiller les mutex dans le même ordre.
• NB : En Java, il est aussi possible de définir un méthode (ou un bloc de code) comme synchronized pour éviter que'il y ait des exécutions concurrentes. Microsoft en a fait une extension C++ avec l'attribut {synchronize} non standard, donc à éviter.

Notions essentielles

• Il est tellement classique de devoir se prémunir contre des écritures simultanées sur une variable que C++ fournit atomic (depuis C++ 11). Par exemple :

struct Counters { int a; int b; }; // user-defined trivially-copyable type
std::atomic<Counters> cnt;         // specialization for the user-defined type

std::atomic<int>
// or
atomic_int

• L'implémentation d'atomic s'appuie sur des instructions dédiées du processeur (==> Plus performant qu'un mutex)
• Peut-on déclarer un std::atomic<std::vector<int>> ? Non, car :
  • C++11 §29.5/1 says: "There is a generic class template atomic. The type of the template argument T shall be trivially copyable (3.9)."
  • What does trivially copyable mean? §3.9 tells: "Scalar types, trivially copyable class types (Clause 9), arrays of such types, and cv-qualified versions of these types (3.9.3) are collectively called trivially copyable types."
  • Ce n'est pas le cas de std::vector (non-trivial copy constructors, non-trivial move constructors, non-trivial copy assignment operators, non-trivial move assignment operators).
  • Voir Code 09 qui ne compile pas avec std::atomic<std::vector<int>>.
• NB : Java propose aussi cette notion.

• ==> Eviter les variables mutables !
• ==> Piste de solution = Regarder si votre code ne pourrait pas bénéficier du patron d'architecture MapReduce:
  • Etape Map : Découpage en sous-problèmes et délégation des sous-problèmes à d'autres threads ou noeuds d'exécution (dans le cas d'une architecture répartie).
  • Etape Reduce : Les threads/noeuds font remonter l'information au parent qui les avaient sollicités. Ce parent calcule le résultat.
• En environnement réparti, il est courant d'implémenter un MapReduce à l'aide d'un framework comme Hadoop.

• Le code présenté implémente un patron d'architecture MapReduce. Identifiez les étapes Map et Reduce.

12:     int totalDecrement = 0;
13:     for (auto i = nb_decrement ; i > 0; --i) {
14:         ++totalDecrement;
15:     }
16:     result = totalDecrement;
17: }
18: 
19: int main()
20: {
21:     auto counter = nb_count;
22: 
23:     auto start = high_resolution_clock::now();
24:     auto start_cpu = get_cpu_time();
25:     std::vector<std::thread> threads(nb_threads);
26:     std::vector<int> results(nb_threads);
27:     int numThread = 0;
28:     for (auto& t : threads) {
29:         t = std::thread(computeDecrement, nb_count / nb_threads, std::ref(results[numThread]));
30:         ++numThread;
31:     }
32:     numThread = 0;
33:     for (auto &t:threads) {
34:         t.join();
35:         counter -= results[numThread];
36:         ++numThread;
37:     }

Notions essentielles

• Lancement d'une tâche par auto fut = std::async([] { resultat=calcul(); return resultat; });
• Attente du résultat d'une tâche par resultat = fut.get();

[Grimm 2021] std::async should be your first choice : The C++ runtime decides if std::async is executed in a separate thread or not. The decision of the C++ runtime may depend on the number of CPU cores available, the utilization of your system, or the size of your work package. By using std::async you only specify the task that should run. The C++ runtime automatically manages the creation and also the lifetime of the thread.

Les CPP core guidelines disent aussi "CP.4: Think in terms of tasks, rather than threads."

• Toutefois, https://www.boost.org/doc/libs/1_85_0/libs/fiber/doc/html/fiber/performance.html montre que le launch d'un std::async prend 106 us contre 52 us pour un std::thread ==> A voir si cette différence de performances est importante pour les utilisateurs.

Notions essentielles

• std::guarded_lock
• std::scoped_lock
  • Pour verrouiller (et relâcher plusieur mutex à la fois)
• std::unique_lock
  • Plus cher que lock_guard, mais permet de reverrouiller récursivement un mutex.
  • Obligatoire pour variable condition (cf. Code 10) et quand concurrence avec std::shared_lock (cf. Code 20)
• std::shared_lock ==> Utilisation pour lecteurs-rédacteur (cf. Code 20)

Ce code montre comment éviter, grâce à la RAII, qu'un mutex reste verrouillé si vous avez oublié l'instruction de déverrouillage ou bien si une exception a eu lieu durant une section critique : nous nous appuyons sur std::scoped_lock (depuis C++ 17).

12: void decrement(const int nb_decrement, int &counter) {
13:     static std::mutex mtx;
14:     for (auto i = nb_decrement ; i > 0; --i) {
15:         std::scoped_lock lock(mtx); // Since CPP 17
16:         --counter;
17:     }
18: }

• Static variables with block scope are created exactly once and lazily. Lazily means that they are created just at the moment of usage.
• With C++11,static variables with block scope have an additional guarantee, they are initialized in a thread-safe way. Warning: Your compiler may not support this feature:
  • For VisualStudio, since VS 2015, option /Zc:threadSafeInit (activated by default)
  • For gcc, check if your compiler has option -fno-threadsafe-statics (Cette option est là pour désactiver cette fonction. Donc, si elle est là, le compilateur implémente cette fonction.)
  • For clang, same as gcc.

• Permet d'avoir une variable statique qui n'est pas partagée par tous les threads.
• Quand on déclare une variable thread_local, elle est implicitement static.

thread_local int v = 0;

Ce code montre comment des variables sont partagées ou non par des threads, selon leur lieu de déclaration et leur attribut static ou thread_local.

12: void incr(std::atomic_int& v_main, int& v_work) {
13:     static std::atomic_int v_incr_static = 0;
14:     thread_local int v_incr_thread_local = 0;
15:     int v_incr = 0;
16:     ++v_main;
17:     ++v_work;
18:     ++v_incr_static;
19:     ++v_incr_thread_local;
20:     ++v_incr;
21:     display(v_main, v_work, v_incr_static, v_incr_thread_local, v_incr);
22: }
23: 
24: void work(std::atomic_int& v_main) {
25:     int v_work = 0;
26:     for (auto i = nb_times; i > 0; --i) {
27:         incr(v_main, v_work);
28:     }
29: }
30: 
31: int main()
32: {
33:     std::atomic_int v_main = 0;
34: 
35:     std::vector<std::jthread> threads(nb_threads);
36:     for (auto& t : threads) {

• Ce code ne compile pas avec std::atomic<std::vector<int>>.
• Il plante à l'exécution si on ne met pas de mutex.

Notions essentielles

• "Global" variables

std::mutex mtx;
std::condition_variable condVar;

bool dataReady{false};

• Le thread en attente exécute le code suivant :

// Code écrit                                // Code exécuté
std::unique_lock<std::mutex> lck(mtx);       std::unique_lock<std::mutex> lck(mtx);
condVar.wait(lck, []{ return dataReady; });   while ( ![]{ return dataReady; }() {
                                                mtx.unlock();
                                                condVar.wait(lck);
                                                mtx.lock();
                                             }

• Le thread qui va débloquer la situation exécute le code suivant :

{
   std::lock_guard<std::mutex> lck(mtx);
   dataReady = true;
}
condVar.notify_one();

• L'objectif de ce pattern de synchronisation est de garantir que pas plus de N threads font un certain traitement.
  • Parallèle avec la vie de tous les jours : Comment garantir qu'un parking de voitures de N places n'accueille pas plus de N véhicules ?

 9: constexpr int max_cars_in_parking = 4;
10: constexpr int nb_threads = 10;
11: 
12: void car_life(const int num_thread) {
13:     static std::mutex mtx;
14:     static std::condition_variable cond_var;
15:     static int nb_cars_in_parking = 0;
16: 
17:     {
18:         std::unique_lock lck(mtx);
19:         std::cout << "Thread " << num_thread << " wants to enter parking" << std::endl;
20:         cond_var.wait(lck, [] { return nb_cars_in_parking < max_cars_in_parking; });
21:         ++nb_cars_in_parking;
22:     }
23:     std::cout << "Thread " << num_thread << " enters parking" << std::endl;
24:     std::this_thread::sleep_for(0.2s); // Note: We do not use sleep, otherwise the whole process would stop.
25:     std::cout << "Thread " << num_thread << " exits parking" << std::endl;
26:     {
27:        std::lock_guard lck(mtx);
28:        --nb_cars_in_parking;
29:     }
30:     cond_var.notify_one();
31:     std::cout << "Thread " << num_thread << " exited parking" << std::endl;
32: }

• Application : Considérez un parking avec seulement 2 places et 4 voitures qui arrivent (couleurs similaires aux couleurs des feutres de tableau blanc) avec le scénatio suivant :
  • Les voitures bleue et verte entrent dans le parking.
  • La voiture rouge arrive et se retrouve en attente.
  • La voiture bleue sort du parking juste au moment où la voiture noire arrive ==> la voiture noire entre dans le parking avant même que la voiture rouge ait pu amorcer un mouvement (et ce que le cond_var.notify_one() soit hors ou dans la section critique).
• NB : Durant l'exécution, il se pourrait que vous obteniez des messages "mélangés". Par exemple :

Thread 6Thread 7 exits parking
Thread 7 exited parking
 exits parking
Thread 6 exited parking

• Ceci est juste un mélange d'affichages qui ne remet pas en cause la synchronisation qui, elle, s'est bien passée. Pour éviter ce mélange, une 1ère solution : vous définissez un mutex global qui protège chaque cout (cf. exemple en 13_SyncPattern_Barrier):

void synchronizedOut(const std::string& s) noexcept {
    static std::mutex coutMutex;
    std::scoped_lock lock(coutMutex);
    std::cout << s;
}

// Invocation par synchronizedOut(name + ": " + "Morning work done!\n");

• Soit, 2ème solution (depuis C++ 20) : vous vous appuyez sur std::basic_osyncstream en écrivant par exemple:

std::osyncstream(std::cout) << "Hello, " << "World!" << std::endl;

• Problème résolu : 8 passagers d'un minibus doivent embarquer dedans. Le conducteur ne démarre que quand tout le monde a embarqué.

10: constexpr int minibus_capacity = 8; //passengers (in addition to the driver)
11: 
12: struct minibus_t {
13:     std::mutex mtx;
14:     std::condition_variable cond_var;
15:     int nb_passengers{ 0 }; // Already boarded in minibus
16: };
17: 
18: void passenger(const int num_passenger, minibus_t& minibus) {
19:     std::osyncstream(std::cout) << "Passenger " << num_passenger << " starting to board" << std::endl;
20:     std::this_thread::sleep_for(1s); // Note: We do not use sleep, otherwise the whole process would stop.
21:     std::osyncstream(std::cout) << "Passenger " << num_passenger << " is done boarding" << std::endl;
22:     {
23:         std::lock_guard lck(minibus.mtx);
24:         ++minibus.nb_passengers;
25:     }
26:     minibus.cond_var.notify_one();
27: }
28: 
29: void driver(minibus_t& minibus) {
30:     std::osyncstream(std::cout) << "Driver waiting for " << minibus_capacity << " passengers to get onboard" << std::endl;
31:     {
32:         std::unique_lock lck(minibus.mtx);
33:         minibus.cond_var.wait(lck, [&minibus] { return minibus.nb_passengers == minibus_capacity; });
34:     }
35:     std::osyncstream(std::cout) << "Driver sees that " << minibus_capacity << " passengers are onboard: He can start the trip!" << std::endl;
36: }

• Dans ce code, nous utilisons notify_one(). Aurions-nous pu utiliser notify_all ? Si oui, lequel des deux est le plus performant ?
• NB : Vu que les passagers terminent leur exécution une fois qu'ils ont embarqués, nous aurions pu procéder comme au "Code 06", programmer les passagers sous forme de std::async(), le chauffeur faisant des get() sur chacun des passagers.

• Problème résolu : 8 coureurs d'athlétisme ne commencent à courir que quand le juge a donné le top départ.
  • Dans la version fournie, le juge donne le signal de début de course une fois que les coureurs sont en place.
  • Une fois que vous avez vérifié que cette version fonctionne, mettez le sleep_for avant le for (auto& t : threads) { et le lancement du referee avant le sleep_for. Vérifiez que les coureurs se mettent bien à courir immédiatement, vu que le signal a déjà été donné.

10: constexpr int nb_runners = 8; //How many runners can run in parallel in a stadium
11: 
12: struct stadium_t {
13:     std::mutex mtx;
14:     std::condition_variable cond_var;
15:     bool run_signal{ false };
16: };
17: 
18: void runner(const int num_runner, stadium_t& stadium) {
19:     std::osyncstream(std::cout) << "Runner " << num_runner << " waiting for run signal" << std::endl;
20:     {
21:         std::unique_lock lck(stadium.mtx);
22:         stadium.cond_var.wait(lck, [&stadium] { return stadium.run_signal; });
23:     }
24:     std::osyncstream(std::cout) << "Runner " << num_runner << " starts running" << std::endl;
25: }
26: 
27: void referee(stadium_t& stadium) {
28:     std::osyncstream(std::cout) << "Referee is about to fire run signal" << std::endl;
29:     {
30:         std::lock_guard lck(stadium.mtx);
31:         stadium.run_signal = true;
32:     }
33:     std::osyncstream(std::cout) << "Referee has fired run signal" << std::endl;
34:     stadium.cond_var.notify_all();
35: }

• Dans ce code, nous utilisons notify_all(). Selon vous, aurions-nous pu utiliser notify_one ?

Notions essentielles [Grimm, 2021]

11: void runner(const int num_runner, std::latch& fire_signal) {
12:     std::osyncstream(std::cout) << "Runner " << num_runner << " waiting for run signal" << std::endl;
13:     fire_signal.wait();
14:     std::osyncstream(std::cout) << "Runner " << num_runner << " starts running" << std::endl;
15: }
16: 
17: void referee(std::latch& fire_signal) {
18:     std::osyncstream(std::cout) << "Referee is about to fire run signal" << std::endl;
19:     std::osyncstream(std::cout) << "Referee has fired run signal" << std::endl;
20:     fire_signal.count_down();
21: }
22: 
23: int main()
24: {
25:     std::latch fire_signal(1);

Une fois que vous avez vérifié que la version fournie fonctionne, mettez le sleep_for avant le for (auto& t : threads) { et le lancement du referee avant le sleep_for. Vérifiez que les coureurs se mettent bien à courir immédiatement, vu que le signal a déjà été donné.

Notions essentielles [Grimm, 2021]

• A std::barrier is similar to a std::latch
• But two differences
  1. You can use a std::barrier more than once
  2. You can adjust the counter for the next phase

• Ce code largement inspiré du livre [Grimm, 2021] s'appuie sur une queue non limitée en taille. Notez que le livre [Grimm, 2021] contient, aux pages 538-554, toute une discussion sur l'implémentation d'une telle queue.
• Vu tous les warnings remontés par SonarLint, la qualité de ce code pose question.

• Ce code implémente l'algorithme présenté précédemment.
• Notez l'instruction exit(0); qui permet de forcer l'arrêt du processus, même si des threads détachés continuent à s'exécuter (Mettez cette instruction en commentaire, puis relancez votre programme pour vous en convaincre).

Notions essentielles

• Historiquement, les sémaphores ont été conçus avant les moniteurs. Mais, comme de nombreuses personnes estiment qu'il est plus simple de travailler avec les moniteurs qu'avec les sémaphores, les moniteurs ont été offerts dès C++ 11 alors que les sémaphores ne sont arrivés qu'avec C++ 20.
• Notions de base
  • Un sémaphore est un objet système contenant
    • Un compteur initialisé à une certaine valeur
    • Une file d'attente de processus mis en attente car le compteur avait une valeur < 0.
  • Opérations
    • Initialisation : std::counting_semaphore<valeur_init> sem(valeur_init);
    • Opérateur P() ("Puis-je ?") : sem.acquire(); // en C++
    • Opérateur V() ("Vas-y !") : sem.release(); // en C++

// P()                          // V()
Si compteur <= 0 Alors          compteur += 1
   Met le thread en attente     Réveille l'éventuel thread en tête de file d'attente
FinSi
compteur -= 1

• Bonnes pratiques
  • Un sémaphore initialisé à 1 peut être utilisé comme un mutex. Mais, préférez systématiquement le mutex si opérations lock() et unlock() sont faites dans le même thread. En effet :
    • Mutex plus performant que sémaphore.
    • Code plus clair ==> Meilleure maintenabilité.

On souhaite que, après un travail, 2 threads se "rejoignent" avant de démarrer un nouveau travail.

sem_juliette(0)
sem_romeo(0)

// Juliette                       // Romeo
Se pouponner();                   Encore plus se pouponner()
sem_juliette.release()            sem_romeo.release()
sem_romeo.acquire()               sem_juliette.acquire()
Boire un pseudo-poison()          Être perclus de douleur()

Notez qu'un std::latch() permet d'être plus concis (et plus efficace ?) :

std::latch rdv(2); // Car 2 personnes ont besoin de se retrouver.

// Juliette                       // Romeo
Se pouponner();                   Encore plus se pouponner()
rdv.arrive_and_wait()             rdv.arrive_and_wait()
Boire un pseudo-poison()          Être perclus de douleur()

Analysez le code et posez des questions si des points vous semblent obscurs.

Notions essentielles

• std::shared_lock s'appuie sur un std::shared_timed_mutex (C++14) ou un std::shared_mutex (C++17), le premier permettant de spécifier une date de libération ou une durée avant libération.
• Ensuite
  • Verrou de lecteur : std::shared_lock readerLock(a_shared_mutex);
  • Verrou de rédacteur : std::lock_guard writerLock(a_shared_mutex);

Analysez le code. Voyez comment l'utilisation du verrou lecteurs-rédacteur simplifie le code. Posez des questions si des points vous semblent obscurs.

Notions essentielles

• Si un programme multithreadé fait des allocations/désallocations mémoire, il est possible que
  • les allocations se font dans un thread,
  • les utilisations de la mémoire allouée se fait dans d'autres threads,
  • les désallocations se fait dans un autre thread.
• Cela entraine plein de questions dont :
  • Comment synchroniser allocations, utilisation et désallocations ?
  • Comment être sûr qu'on n'oublie pas de libérer de la mémoire ?
  • Comment détecter si, par erreur de logique, notre code utilise de la mémoire mémoire déjà libérée ?
• Les réponses à ces questions dépendent du langage :
  • Langages à base de garbage collector (C#, Java) : a priori, rien à faire.
  • En C, il est essentiel de respecter les conseils suivants :
    • Si vous déclarez un pointeur nu, pensez à systématiquement l'initialiser (à NULL si vous n'avez pas de valeur à fournir à la variable).
    • Tout free(ptr) doit être suivi de ptr = NULL;
  • En C++, s'appuyer sur shared_ptr, en réfléchissant préalablement s'il est nécessaire d'avoir des pointeurs. cf. Exemple d'un serveur TCP.

NB : Dans ce code, remarquez qu'au lieu d'une exclusion mutuelle dans l'accès à l'objet socket, on aurait pu mettre en place un lecteurs-rédacteurs. Mais la diffusion obtenue n'aurait plus été à ordre total.

TODO Ajouter ce code

Notions essentielles

• The Standard Template Library has more than 100 algorithms for searching, counting, and manipulating ranges and their elements. With C++17, 69 of them get new overloads, and eight new ones are added. The overloaded, and new algorithms can be invoked with a so-called execution policy.
• Using an execution policy, you can specify whether the algorithm should run sequentially, in parallel,or parallel with vectorization. For using the execution policy,you have to include the header <execution>
• The execution policy is a permission and not a requirement.
  • std::execution::seq : runs the program sequentially
  • std::execution::par : runs the program in parallel on multiple threads
  • std::execution::par_unseq : runs the program in parallel on multiple threads and allows the interleaving of individual loops; permits a vectorised version with SIMD (Single Instruction Multiple Data) extensions.
• Attention : The parallel algorithm does not automatically protect you from data races and deadlocks.

Notions essentielles

• Les coroutines sont une mise en oeuvre d'un paradigme producteur-consommateur avec :
  • Un producteur (la coroutine)
  • Un consommateur (le thread qui crée la coroutine)
  • Ils communiquent via un buffer
    • limité à 1 seul élément
    • capable de transporter aussi les exceptions remontées par la coroutine
• Les coroutines sont une généralisation des tâches.

• Les fibres sont des unités d'exécution qui s'exécutent au sein de threads, sans préemption entre fibres (un fibre doit explicitement passer la main à une autre fibre, cf. https://learn.microsoft.com/fr-fr/windows/win32/procthread/fibers).
  • "A context switch between threads costs usually thousands of CPU cycles on x86 compared to a fiber switch with less than 100 cycles." (cf. doc fibres Boost)
  • ==> Pas mal utilisé dans le jeu vidéo
• Pour approfondir
  • https://agraphicsguynotes.com/posts/fiber_in_cpp_understanding_the_basics/
  • Boost.Fiber fournit une bibliothèque de fibres pour les applications C++.
• TODO A compléter !

• Debug
  • TODO : Démo de Debug avec multithreading.
• Profiling: Comprendre où un programme passe du temps.
  • https://hackingcpp.com/cpp/tools/profilers.html recommande VTune d'Intel, outil également recommandé par https://stackoverflow.com/questions/67554/whats-the-best-free-c-profiler-for-windows
  • Chez ASOBO, ils utilisent Microsoft PIX qui concerne "Performance tuning and debugging for DirectX 12 games on Windows"

TODO To be continued ! (lisez [Grimm, 2021] si vous êtes impatient(e))

Je pourrais pinailler sur quelques éléments mais ça ne serait pas très utile (bien que ce que tu dis sur la fréquence dans 3.1.1 est juste, ça passe sous le tapis et ignore divers discussions et problèmes très intéressants ! Mais je nage là dedans, je suis biaisé. Aussi, j'ai compté 8 instructions dans la boucle du 3.1.1 :) ).

Ma remarque principale c'est l'absence de Thread Sanitizer, l'outil d'instrumentation de Google pour justement détecter les data races et autres joyeusetés du multithreading. Je remarque qu'il est malheureusement pas disponible sur MSVC, mais ça reste un outil puissant dans ce domaine.

Je n'ai pas trop le temps de chercher en détail non plus mais je suis surpris que les fonctionnalités C++ soient considérées notablement plus lentes que le passage par la machinerie système; je te fais confiance. (Même si à première vue je vois passer des futex pthread par la lib standard)

Un autre élément qui pourrait être rapidement évoqué (je ne sais pas si c'est le cas sur la partie cours) c'est le problème de "thundering herd" dans le cas 1 contrôle N thread. Le problème est en particulier pour une groupe de thread en attente de tâche à traiter, qui peuvent tous être réveillés à la moindre arrivée de travail qui ne peut finalement être récupérée que par un nombre limité de threads. Ça peut avoir un impact fort sur la performance système général et réduire le débit du programme.

Vis-à-vis des atomics, tu soulignes qu'il y a des instructions CPU dédiées, il y en a aussi pour certains types de verrou et pour la plupart des barrières ! Leur utilisation dépend beaucoup de la bibliothèque C++ utilisée et peut parfois être faite directement par des fonctions fournies par le compilateurs (intrinsics). C'est d'ailleurs parfois ces mêmes fonctions qui servent à implémenter d'autres primitives de synchronisation.

Il me semble que les codes 24 et 25 ne sont pas finaux mais il manque à l'heure actuelle -ltbb dans les options de link Vis-à-vis de clang la plupart des exemples compilent, avec l'exception notable des coroutines vu qu'il est encore capricieux à ce sujet : le header est différent, le namespace aussi et il faut (dans une majorité des cas) forcer le changement de bibliothèque standard à la compilation… Peu agréable pour le moment, et comme tu le soulignes Clang est à la traîne sur l'implémentation des standards.

Une chose intéressante que tu ne mentionnes pas non plus vis-à-vis de la performance des variables partagées sur des threads c'est que ça peut entraîner des invalidations de cache assez régulièrement. Ce n'est pas toujours un problème en soit, mais ça peut l'être.

Vis à vis du profiling : je ne sais pas si c'est disponible sous Windows, mais sous Linux il est possible de profiler en multithread avec CLion et obtenir des "flame graphs" ainsi qu'un arbre d'appels. Ce n'est pas inutile, bien que moins poussé que ce que fourni Microsoft avec Visual Studio (Il faut bien rendre à César ce qui est à César)

J'ai oublié un truc sur 3.1.1 : pour Linux la façon la plus portable de lire la fréquence est cat /proc/cpuinfo | grep Hz . Il faut noter que la fréquence de chaque cœur apparaîtra, ainsi que la fréquence de base du processeur. On pourra remarquer qu'elles ne sont pas forcément égales, ni celles de différents cœurs entre eux. C'est tout ce qui me vient @Michel Simatic (Au cas où le thread soit passé inaperçu :) ) en espérant que ça te soit utile. Je trouve en tout cas que c'est vraiment une introduction et référence super à avoir ! (En bonus implémenter un compteur sous verrou en pur assembleur est un exercice intéressant pour ceux qui voudraient un bon challenge 😄 J'avoue cependant que je ne connais pas la faisabilité en x86_64, je l'ai fait en A64 pour pratiquer)

Dans la liste des techniques non-préemptives, j'ajouterais les coroutines, qui sont très proches des fibres (si ce n'est la même chose selon la définition).

Je rajoute juste un point sur les coroutines :

• Cet article explique très bien comment elles fonctionnent. https://www.scs.stanford.edu/~dm/blog/c++-coroutines.html
• Je me suis basé dessus pour l'implémentation des coroutines de mon moteur personnel. Avec un peu d'aide de cppcoro pour comprendre des points précis : https://github.com/lewissbaker/cppcoro
• En revanche j'ai peur que les coroutines soient un peu trop compliquées à implémenter soit même quand on débute le C++ (donc cppcoro pourrait être intéressant à utiliser). Ça peut être une idée pour une prochaine itération du cours :-)