Implementering af en låsefri kø
Gennemgå designet af en låsefri kø med én producent og én forbruger
Implementering af en låsefri kø er en gratis C++ Academy-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i C++ Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. C++ Academy-kurset indeholder 4 lektioner i alt.
Hvorfor låsefri køer
Køer med mutexer kan blive flaskehalse under høj contention. En låsefri kø lader producenter og forbrugere gøre fremskridt samtidigt.
SPSC kontra MPMC
To varianter:
- SPSC — én producent, én forbruger (enklest og hurtigst)
- MPMC — flere producenter, flere forbrugere (mest generel)
SPSC er det naturlige valg, når du har kontrol over begge ender.
Skitse af SPSC-ringbuffer
En cirkulær buffer med to indeks: head (forbruger) og tail (producent). Hver side opdaterer sit eget indeks.
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);
};SPSC push
Producenten kontrollerer ledige pladser, skriver og publicerer derefter ved at opdatere tail.
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;
}SPSC pop
Forbrugeren kontrollerer, om der er data, læser og publicerer derefter ved at opdatere head.
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;
}Parring af hukommelsesrækkefølge
release-store-operationen på tail synkroniserer med acquire-load-operationen på tail hos forbrugeren (og omvendt). Uden den rette rækkefølge kan dataskrivningerne blive omarrangeret, så de sker efter indeksopdateringen.
Udfyldning af cachelinjer
For at undgå falsk deling skal du placere head_ og tail_ på separate cachelinjer (typisk med 64 bytes imellem). Brug alignas.
alignas(64) std::atomic<size_t> head_{0};
alignas(64) std::atomic<size_t> tail_{0};MPMC: Meget sværere
Flere producenter eller forbrugere kræver yderligere koordinering — normalt med CAS-løkker på delte indeks. Der findes mange konstruktioner (Vyukov queue, MS-queue, Hazard-Pointer-baserede).
Boost.Lockfree
Låsefri køer i produktionskvalitet er svære at lave. Brug Boost.Lockfree eller Follys ProducerConsumerQueue i stedet for at skrive din egen.
Afvejninger
Låsefri køer:
- Højere gennemløb under konkurrence
- Begrænset latenstid (ingen ventetid på en lås)
- Meget sværere at skrive og fejlfinde
- Fejl i hukommelsesrækkefølgen er tavse og svære at finde
Test af låsefri kode
Brug ThreadSanitizer (-fsanitize=thread) til at finde datakapløb. Brug stresstest med tilfældige indsættelser af pauser for at afsløre fejl i rækkefølgen.
Når en mutex er nok
De fleste programmer har ikke brug for låsefri køer. Mål først — en velfungerende kø beskyttet af en mutex yder ofte tilstrækkeligt, især ved behandling i grupper.
Hurtigt tjek
Hvad er falsk deling, og hvorfor skal head_ og tail_ udfyldes?
Opsummering
En låsefri SPSC-kø bruger en ringbuffer med producentens tail og forbrugerens head. Brug acquire/release-rækkefølge, og udfyld indeksene, så de ligger på separate cachelinjer. Til MPMC bør du foretrække et afprøvet bibliotek.
Lær C++ med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 51
- Lektioner
- 203
Ofte stillede spørgsmål
Er lektionen “Implementering af en låsefri kø” gratis?
Ja — alle 3 lektioner i læringssporet C++ Academy, inklusive “Implementering af en låsefri kø”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. C++ Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Implementering af en låsefri kø”?
Gennemgå designet af en låsefri kø med én producent og én forbruger Du øver dig i C++ Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på C++ Academy?
Der kræves ingen tidligere erfaring. C++ Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Implementering af en låsefri kø”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne C++ Academy-lektion?
Ja. Alle C++ Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- std::atomic og hukommelsesordener
- Compare-and-swap- og CAS-mønstre
- Implementering af en låsefri kø
- Hazard-pointere og ABA-problemet