C++ Academy · Pelajaran

Implementasi Antrean Tanpa Kunci

Pelajari rancangan antrean tanpa kunci dengan satu produsen dan satu konsumen

Implementasi Antrean Tanpa Kunci adalah pelajaran C++ Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C++ Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C++ Academy mencakup 4 pelajaran total.

Mengapa Antrean Tanpa Kunci?

Antrean dengan mutex dapat menjadi hambatan saat persaingan tinggi. Antrean tanpa kunci memungkinkan produsen dan konsumen mengalami kemajuan secara bersamaan.

SPSC vs MPMC

Dua jenis:

SPSC — satu produsen, satu konsumen (paling sederhana dan cepat)
MPMC — banyak produsen, banyak konsumen (paling umum)

SPSC adalah pilihan alami ketika Anda mengendalikan kedua ujungnya.

Sketsa Buffer Cincin SPSC

Buffer melingkar dengan dua indeks: kepala (konsumen) dan ekor (produsen). Setiap sisi memperbarui indeksnya sendiri.

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);
};

Memasukkan ke SPSC

Produsen memeriksa slot kosong, menulis data, lalu memublikasikannya dengan memperbarui ekor.

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;
}

Mengambil dari SPSC

Konsumen memeriksa data yang tersedia, membacanya, lalu memublikasikannya dengan memperbarui kepala.

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;
}

Pemasangan Urutan Memori

Penyimpanan release pada ekor disinkronkan dengan pemuatan acquire pada ekor di sisi konsumen (dan sebaliknya). Tanpa pengurutan yang tepat, penulisan data dapat diurutkan ulang setelah pembaruan indeks.

Padding Baris Cache

Untuk menghindari berbagi semu, letakkan head_ dan tail_ pada baris cache yang terpisah (biasanya berjarak 64 byte). Gunakan alignas.

alignas(64) std::atomic<size_t> head_{0};
alignas(64) std::atomic<size_t> tail_{0};

MPMC: Jauh Lebih Sulit

Banyak produsen atau konsumen memerlukan koordinasi tambahan—biasanya dengan perulangan CAS pada indeks bersama. Ada banyak rancangan yang tersedia (antrean Vyukov, antrean MS, antrean berbasis penunjuk bahaya).

Boost.Lockfree

Antrean tanpa kunci berkualitas produksi sulit dibuat. Gunakan Boost.Lockfree atau ProducerConsumerQueue milik Folly daripada membuat implementasi sendiri.

Kompromi

Antrean tanpa kunci:

Laju pemrosesan lebih tinggi saat terjadi persaingan akses
Latensi terbatas (tidak perlu menunggu kunci)
Jauh lebih sulit ditulis dan di-debug
Galat pengurutan memori bersifat diam-diam dan sulit dilacak

Menguji Kode Tanpa Kunci

Gunakan ThreadSanitizer (-fsanitize=thread) untuk menemukan kondisi balapan data. Gunakan pengujian tekanan dengan penyisipan jeda tidur acak untuk mengungkap galat pengurutan.

Saat Mutex Sudah Memadai

Kebanyakan aplikasi tidak memerlukan antrean tanpa kunci. Ukur terlebih dahulu—antrean yang dilindungi mutex dan diimplementasikan dengan baik sering kali berkinerja memadai, terutama dengan pemrosesan secara berkelompok.

Pemeriksaan Singkat

Apa yang dimaksud dengan berbagi semu, dan mengapa head_ serta tail_ perlu diberi padding?

Ringkasan

Antrean SPSC tanpa kunci menggunakan buffer cincin dengan ekor milik produsen dan kepala milik konsumen. Gunakan pengurutan acquire/release dan beri padding pada indeks agar berada di baris cache yang terpisah. Untuk MPMC, pilih pustaka yang telah teruji.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Implementasi Antrean Tanpa Kunci” gratis?

Ya — teks lengkap “Implementasi Antrean Tanpa Kunci” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C++ Academy, upgrade ke CoddyKit PRO. Kursus C++ Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Implementasi Antrean Tanpa Kunci”?

Pelajari rancangan antrean tanpa kunci dengan satu produsen dan satu konsumen Kamu berlatih C++ Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai C++ Academy?

Tidak diperlukan pengalaman sebelumnya. C++ Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “Implementasi Antrean Tanpa Kunci” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran C++ Academy ini?

Ya. Setiap pelajaran C++ Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

← Kembali ke C++ Academy