Implémenter une file sans verrou
Découvrir la conception d’une file sans verrou à producteur et consommateur uniques
Implémenter une file sans verrou est une leçon C++ Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C++ Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C++ Academy comprend 4 leçons au total.
Pourquoi des files sans verrou ?
Les files utilisant des verrous mutex peuvent devenir des goulots d’étranglement lorsque la contention est élevée. Une file sans verrou permet aux producteurs et aux consommateurs de progresser simultanément.
SPSC ou MPMC
Deux variantes :
- SPSC — un seul producteur et un seul consommateur (la plus simple et la plus rapide)
- MPMC — plusieurs producteurs et plusieurs consommateurs (la plus générale)
SPSC est le choix naturel lorsque vous contrôlez les deux extrémités.
Schéma d’un tampon circulaire SPSC
Un tampon circulaire avec deux indices : tête (consommateur) et queue (producteur). Chaque côté met à jour son propre indice.
template <typename T, size_t N>
class SpscQueue {
T buffer_[N];
std::atomic<size_t> head_{0};
std::atomic<size_t> tail_{0};
public:
bool push(const T& v);
bool pop(T& v);
};Insertion SPSC
Le producteur vérifie les emplacements libres, écrit, puis publie la donnée en mettant à jour la queue.
bool push(const T& v) {
const size_t t = tail_.load(std::memory_order_relaxed);
const size_t next = (t + 1) % N;
if (next == head_.load(std::memory_order_acquire))
return false; // full
buffer_[t] = v;
tail_.store(next, std::memory_order_release);
return true;
}Extraction SPSC
Le consommateur vérifie la présence de données, les lit, puis publie l’opération en mettant à jour la tête.
bool pop(T& v) {
const size_t h = head_.load(std::memory_order_relaxed);
if (h == tail_.load(std::memory_order_acquire))
return false; // empty
v = buffer_[h];
head_.store((h + 1) % N, std::memory_order_release);
return true;
}Appariement des ordres mémoire
Le stockage avec sémantique release sur la queue se synchronise avec le chargement avec sémantique acquire sur la queue du consommateur, et inversement. Sans le bon ordre, les écritures de données pourraient être réordonnées après la mise à jour de l’indice.
Remplissage des lignes de cache
Pour éviter le faux partage, placez head_ et tail_ sur des lignes de cache distinctes, généralement espacées de 64 octets. Utilisez alignas.
alignas(64) std::atomic<size_t> head_{0};
alignas(64) std::atomic<size_t> tail_{0};MPMC : bien plus difficile
Plusieurs producteurs ou consommateurs nécessitent une coordination supplémentaire, généralement avec des boucles CAS sur des indices partagés. Il existe de nombreuses conceptions : la file de Vyukov, la file MS et celles fondées sur des pointeurs de protection.
Boost.Lockfree
Les files sans verrou de qualité production sont difficiles à concevoir. Utilisez Boost.Lockfree ou la ProducerConsumerQueue de Folly plutôt que de créer votre propre implémentation.
Compromis
Files sans verrou :
- Débit supérieur en cas de contention
- Latence bornée, sans attente d’un verrou
- Beaucoup plus difficiles à écrire et à déboguer
- Les erreurs d’ordre mémoire sont silencieuses et difficiles à détecter
Tester du code sans verrou
Utilisez ThreadSanitizer (-fsanitize=thread) pour détecter les courses de données. Utilisez des tests de résistance avec des insertions aléatoires de Sleep afin de révéler les erreurs d’ordre.
Quand un mutex suffit
La plupart des applications n’ont pas besoin de files sans verrou. Mesurez d’abord : une file protégée par un mutex correctement implémenté offre souvent des performances suffisantes, notamment avec un traitement par lots.
Vérification rapide
Qu’est-ce que le faux partage et pourquoi ajouter du remplissage autour de head_ et tail_ ?
Récapitulatif
Une file SPSC sans verrou utilise un tampon circulaire avec une queue détenue par le producteur et une tête détenue par le consommateur. Utilisez un ordre acquisition/libération et séparez les indices sur des lignes de cache distinctes. Pour MPMC, préférez une bibliothèque testée.
Apprends C++ avec un tuteur IA — gratuit
Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.
- Cours
- 51
- Leçons
- 203
Questions Fréquemment Posées
La leçon « Implémenter une file sans verrou » est-elle gratuite ?
Oui — le texte complet de « Implémenter une file sans verrou » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C++ Academy, passe à CoddyKit PRO. Le cours C++ Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Implémenter une file sans verrou » ?
Découvrir la conception d’une file sans verrou à producteur et consommateur uniques Tu pratiques C++ Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer C++ Academy ?
Aucune expérience préalable n'est requise. C++ Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Implémenter une file sans verrou » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon C++ Academy ?
Oui. Chaque leçon C++ Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- std::atomic et ordres mémoire
- Schémas de comparaison-échange CAS
- Implémenter une file sans verrou
- Pointeurs de danger et problème ABA