Questions d'entretien Concurrency

Ce que couvrent les entretiens Concurrency

Exemples de questions d'entretien Concurrency

• Expliquez la différence entre processus et thread. Donnez un exemple où le threading est meilleur que le multiprocessing.
  Ce qu'une bonne réponse couvre

  • Les processus possèdent leur propre espace d'adressage mémoire, contrairement aux threads qui partagent la mémoire d'un processus.
  • La commutation de contexte entre processus est plus coûteuse qu'entre threads.
  • La communication inter-processus nécessite des mécanismes comme les tubes ou les sockets, tandis que les threads communiquent via la mémoire partagée.
  • Un thread peut être plus léger et rapide à créer qu'un processus.

  Voir un exemple de réponse

  Un processus est une instance d'un programme en exécution avec son propre espace mémoire isolé, tandis qu'un thread est une unité d'exécution légère au sein d'un processus, partageant la mémoire avec d'autres threads du même processus. Les processus offrent un meilleur isolement et sont plus adaptés aux tâches lourdes ou nécessitant une sécurité accrue. Les threads sont plus efficaces pour les opérations nécessitant un partage de données fréquent et une faible latence de commutation. Exemple où le threading est meilleur : un serveur Web gère des milliers de connexions simultanées ; l'utilisation de threads (ou de pools de threads) permet de traiter chaque requête avec un faible coût de création et de commutation, tandis que le multiprocessing entraînerait une surcharge mémoire et de synchronisation bien plus élevée.

• Qu'est-ce qu'une condition de course ? Montrez un extrait de code simple en Java/C++ qui en contient une et corrigez-la en utilisant un verrou.
  Ce qu'une bonne réponse couvre

  • Une condition de course survient lorsque plusieurs threads accèdent à des données partagées sans synchronisation, menant à des résultats non déterministes.
  • Elle peut causer des bugs difficiles à reproduire et diagnostiquer.
  • La solution classique est l'utilisation de verrous pour assurer une exclusion mutuelle.

  Voir un exemple de réponse

  Une condition de course est un problème de concurrence où le résultat d'une opération dépend de l'ordre d'exécution non contrôlé des threads ou des processus. Par exemple, dans un compteur partagé, si deux threads lisent la valeur, l'incrémentent et l'écrivent simultanément, la valeur finale peut être un au lieu de deux. L'extrait de code Java ci-dessous illustre ce problème et sa correction avec un verrou synchronisé.

  // Condition de course
  class Compteur {
      private int count = 0;
      public void increment() {
          count++; // Trois opérations non atomiques
      }
  }
  
  // Correction avec verrou
  class CompteurSafe {
      private int count = 0;
      private final Object lock = new Object();
      public void increment() {
          synchronized(lock) {
              count++;
          }
      }
  }

• Implémentez une file d'attente bornée thread-safe (file bloquante) en C++ ou Java avec des variables de condition.
  Ce qu'une bonne réponse couvre

  • Une file bornée a une capacité fixe ; les threads producteurs attendent si pleine, les consommateurs attendent si vide.
  • L'implémentation utilise un tableau circulaire, des mutex et des variables de condition.
  • Les variables de condition permettent d'attendre efficacement une condition sans polling.

  Voir un exemple de réponse

  Implémentation d'une file d'attente bornée thread-safe en C++ avec variables de condition. Elle utilise un vecteur circulaire, un mutex, et deux variables de condition pour attendre que la file ne soit pas pleine (pour les producteurs) ou pas vide (pour les consommateurs). La complexité temporelle des opérations push/pop est O(1) en moyenne.

  #include <queue>
  #include <mutex>
  #include <condition_variable>
  
  template<typename T>
  class BoundedBlockingQueue {
  private:
      std::queue<T> queue_;
      size_t capacity_;
      std::mutex mtx_;
      std::condition_variable not_full_;
      std::condition_variable not_empty_;
  public:
      BoundedBlockingQueue(size_t capacity) : capacity_(capacity) {}
  
      void push(T item) {
          std::unique_lock<std::mutex> lock(mtx_);
          not_full_.wait(lock, [this]{ return queue_.size() < capacity_; });
          queue_.push(item);
          not_empty_.notify_one();
      }
  
      T pop() {
          std::unique_lock<std::mutex> lock(mtx_);
          not_empty_.wait(lock, [this]{ return !queue_.empty(); });
          T item = queue_.front();
          queue_.pop();
          not_full_.notify_one();
          return item;
      }
  
      size_t size() const {
          std::lock_guard<std::mutex> lock(mtx_);
          return queue_.size();
      }
  };
  
  // Complexité: push/pop O(1) en moyenne sous contention normale.

• Comment détecteriez-vous un interblocage par programme ? Écrivez du pseudo-code pour un algorithme de détection d'interblocage.
  Ce qu'une bonne réponse couvre

  • Les interblocages se produisent lorsque chaque thread attend une ressource détenue par un autre, formant un cycle.
  • Pour la détection programmatique, on peut maintenir un graphe d'allocation des ressources et chercher des cycles.
  • Une approche simplifiée consiste à vérifier périodiquement les threads bloqués pendant plus d'un seuil.

  Voir un exemple de réponse

  La détection d'interblocage peut être réalisée en maintenant un graphe d'allocation des ressources où les nœuds sont les threads et les ressources, et les arcs représentent les demandes et allocations. Un algorithme de détection de cycle (comme DFS) est appliqué. Voici un pseudo-code pour une détection simple par analyse périodique de l'état du système.

  // Algorithme de détection d'interblocage basé sur le graphe
  Entrée: Matrice de demande Request[][], Matrice d'allocation Allocation[][], Vecteur disponible Available[]
  
  1. Initialiser Work = Available, Finish = [false pour tous les processus]
  2. Pour chaque processus P_i, si Allocation_i == 0 alors Finish[i] = true
  3. Trouver un i tel que Finish[i] == false et Request_i <= Work
     Si trouvé: Work = Work + Allocation_i; Finish[i] = true; répéter étape 3
     Sinon passer à étape 4
  4. Si Finish[i] == false pour un i, alors P_i est en interblocage
  
  // Complexité: O(n^2 * m) où n le nombre de processus et m le nombre de ressources

• Qu'est-ce que le problème ABA en programmation sans verrou ? Fournissez un scénario concret et une solution.
  Ce qu'une bonne réponse couvre

  • Le problème ABA survient en programmation sans verrou lorsqu'un emplacement mémoire est modifié de A à B puis de nouveau à A entre une lecture et une opération CAS.
  • Un thread peut alors interpréter à tort que l'état n'a pas changé.
  • La solution classique est d'utiliser un compteur de version (double-word CAS) ou un tag pointeur.

  Voir un exemple de réponse

  Le problème ABA se produit dans les structures de données sans verrou utilisant des opérations compare-and-swap (CAS). Par exemple, dans une liste chaînée sans verrou, un thread lit la tête A, puis un autre thread retire A et le réinsère, changeant la structure. Quand le premier thread exécute CAS(A, new), il réussit car l'adresse est toujours A, mais la liste est corrompue. Un scénario concret est une pile libre (Treiber stack). Solution : utiliser un pointeur avec un compteur de version (ex: std::atomic<double_word> en C++ ou AtomicStampedReference en Java) pour détecter les modifications même si l'adresse revient à l'identique.

• Concevez un robot d'exploration Web concurrent qui respecte robots.txt et utilise un pool de threads. Montrez les principaux composants.
  Ce qu'une bonne réponse couvre

  • Un robot d'exploration Web concurrent télécharge des pages en parallèle, respecte les règles de robots.txt, et utilise un pool de threads pour contrôler la concurrence.
  • Le composant principal est le planificateur de tâches (scheduler) qui gère la file d'URLs à explorer.
  • Le respect de robots.txt implique un cache des directives et une vérification avant chaque téléchargement.

  Voir un exemple de réponse

  Le robot d'exploration concurrent se compose de plusieurs composants : un pool de threads pour les téléchargements, un planificateur d'URLs avec une file prioritaire, un cache pour robots.txt, et un analyseur HTML extracteur de liens. Le flux est le suivant : le pool de threads pioche une URL dans la file, vérifie d'abord dans le cache robots.txt si l'exploration est autorisée, télécharge la page, analyse les liens et les ajoute éventuellement à la file, en respectant la politesse (délais entre requêtes vers le même domaine). La file est thread-safe avec des priorités (ex: depth-first ou breadth-first). Le pool de threads permet de limiter la charge. Un robot bien conçu utilise aussi une politique de politesse (delay configurable) pour respecter les serveurs.

• Expliquez le modèle mémoire Java : quelles garanties 'volatile' apporte-t-il ? Utilisez un exemple de drapeau partagé.
  Ce qu'une bonne réponse couvre

  • Le modèle mémoire Java (JMM) définit comment les threads interagissent via la mémoire partagée.
  • Le mot-clé volatile garantit que les écritures sont visibles immédiatement par les autres threads et empêche le réordonnancement des instructions.
  • Cependant, volatile ne garantit pas l'atomicité pour les opérations composées.

  Voir un exemple de réponse

  Le mot-clé volatile en Java assure la visibilité : toute écriture dans une variable volatile est immédiatement visible dans les lectures ultérieures par d'autres threads. Il établit une relation happens-before entre l'écriture et la lecture. Il empêche aussi le réordonnancement des instructions autour de l'accès volatil, garantissant ainsi une certaine cohérence. Mais volatile ne rend pas les opérations non atomiques (ex: i++) sûres. Exemple d'utilisation : un drapeau de terminaison partagé. Un thread producteur met à jour le drapeau, un thread consommateur vérifie dans une boucle. Sans volatile, le consommateur pourrait ne jamais voir la mise à jour.

  class Worker implements Runnable {
      private volatile boolean running = true;
  
      public void run() {
          while (running) {
              // travailler
          }
      }
  
      public void stop() {
          running = false; // visible par le thread worker grâce à volatile
      }
  }

• Si vous avez un compteur à forte contention, utiliseriez-vous un mutex, un atomique ou une approche sans verrou ? Comparez les performances et les compromis.
  Ce qu'une bonne réponse couvre

  • Mutex: simple mais peut causer une contention élevée et des changements de contexte coûteux.
  • Atomique: utilise des opérations matérielles (CAS) sans verrou, plus léger que mutex, mais peut souffrir de contention sur le bus mémoire.
  • Approche sans verrou: combine atomiques et structures de données sophistiquées, mais complexe et peut augmenter la pression mémoire.

  Voir un exemple de réponse

  Pour un compteur à forte contention, l'utilisation d'une variable atomique (comme std::atomic<int> en C++ ou AtomicInteger en Java) est généralement préférable à un mutex, car les opérations atomiques ne bloquent pas et ont un coût plus faible en l'absence de contention. Cependant, à très forte contention, les opérations CAS peuvent échouer en boucle (spinning) et dégrader les performances. Dans ce cas, une approche sans verrou comme un compteur avec incrémentation par lots ou un fichier de version peut mieux scaler, mais la complexité augmente. Le mutex est à éviter car il provoque des changements de contexte et bloque les threads. Le choix dépend du niveau de contention : pour modéré, atomique ; pour très élevé, algorithmes sans verrou optimisés (ex: incrémentation locale avec fusion).

Comment se préparer

• Entraînez-vous à implémenter des primitives de concurrence classiques (mutex, sémaphore, variable de condition) à partir de zéro.
• Étudiez les bogues réels : interblocage, live lock et inversion de priorité. Sachez comment diagnostiquer avec des dumps de threads.
• Comprenez la différence entre concurrence et parallélisme, et quand utiliser chacun.
• Apprenez les techniques sans verrou : CAS, mémoire transactionnelle et pointeurs de danger.
• Soyez prêt à discuter des métriques de performance (débit vs latence) sous contention.

Questions fréquemment posées