C++ Academy · Pelajaran

Pelaksanaan Baris Gilir Tanpa Kunci

Ikuti reka bentuk baris gilir tanpa kunci untuk satu pengeluar dan satu pengguna.

Pelajaran 3 daripada 414 langkah

Pelaksanaan Baris Gilir Tanpa Kunci ialah pelajaran C++ Academy percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran C++ Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus C++ Academy merangkumi sejumlah 4 pelajaran.

Mengapa Baris Gilir Tanpa Kunci?

Baris gilir dengan mutex boleh menjadi kesesakan apabila pertikaian tinggi. Baris gilir tanpa kunci membolehkan pengeluar dan pengguna membuat kemajuan secara serentak.

SPSC berbanding MPMC

Dua jenis:

SPSC — pengeluar tunggal, pengguna tunggal (paling mudah dan pantas)
MPMC — berbilang pengeluar, berbilang pengguna (paling umum)

SPSC ialah pilihan semula jadi apabila anda mengawal kedua-dua hujung.

Lakaran Penimbal Gelang SPSC

Penimbal bulat dengan dua indeks: kepala (pengguna) dan ekor (pengeluar). Setiap pihak mengemas kini 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);
};

Tolak SPSC

Pengeluar memeriksa slot yang kosong, menulis data, kemudian menerbitkannya dengan mengemas kini 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;
}

Ambil SPSC

Pengguna memeriksa ketersediaan data, membaca data, kemudian menerbitkannya dengan mengemas kini 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;
}

Pemadanan Susunan Memori

Stor pelepasan pada ekor disegerakkan dengan muatan pemerolehan pada ekor oleh pengguna, dan begitu juga sebaliknya. Tanpa susunan yang betul, penulisan data boleh disusun semula selepas kemas kini indeks.

Pelapik Baris Cache

Untuk mengelakkan perkongsian palsu, letakkan head_ dan tail_ pada baris cache yang berasingan (biasanya berjarak 64 bait). Gunakan alignas.

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

MPMC: Jauh Lebih Sukar

Berbilang pengeluar atau pengguna memerlukan penyelarasan tambahan — biasanya dengan gelung CAS pada indeks yang dikongsi. Terdapat banyak reka bentuk (baris gilir Vyukov, baris gilir MS, berasaskan Penuding Bahaya).

Boost.Lockfree

Baris gilir tanpa kunci yang berkualiti untuk penggunaan sebenar sukar dibina. Gunakan Boost.Lockfree atau ProducerConsumerQueue milik Folly dan bukannya membinanya sendiri.

Pertukaran Kelebihan dan Kekurangan

Baris gilir tanpa kunci:

Keupayaan pemprosesan lebih tinggi semasa persaingan
Kependaman terhad (tiada penantian untuk kunci)
Jauh lebih sukar untuk ditulis dan dinyahpepijat
Ralat susunan memori berlaku secara senyap dan sukar dikesan

Menguji Kod Tanpa Kunci

Gunakan ThreadSanitizer (-fsanitize=thread) untuk mengesan perlumbaan data. Gunakan ujian tekanan dengan sisipan jeda tidur secara rawak untuk mendedahkan ralat susunan.

Apabila Mutex Mencukupi

Kebanyakan aplikasi tidak memerlukan baris gilir tanpa kunci. Ukur dahulu — baris gilir yang dilindungi mutex dan dilaksanakan dengan baik selalunya memberikan prestasi yang mencukupi, terutamanya dengan pemprosesan secara kelompok.

Semakan Pantas

Apakah perkongsian palsu, dan mengapakah head_ serta tail_ perlu dilapik?

Jawab dalam pelajaran interaktif

Ulang Kaji

Baris gilir SPSC tanpa kunci menggunakan penimbal gelang dengan ekor milik pengeluar dan kepala milik pengguna. Gunakan susunan pemerolehan/pelepasan dan lapik indeks supaya berada pada baris cache yang berasingan. Untuk MPMC, utamakan pustaka yang telah diuji.

Percuma untuk bermula

Pelajari C++ dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 51
Pelajaran: 203

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Pelaksanaan Baris Gilir Tanpa Kunci” percuma?

Ya — sebanyak 3 pelajaran dalam laluan pembelajaran C++ Academy, termasuk “Pelaksanaan Baris Gilir Tanpa Kunci”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus C++ Academy merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Pelaksanaan Baris Gilir Tanpa Kunci”?

Ikuti reka bentuk baris gilir tanpa kunci untuk satu pengeluar dan satu pengguna. Anda berlatih C++ Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan C++ Academy?

Tiada pengalaman terdahulu diperlukan. Pembelajaran C++ Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.

Berapa lamakah pelajaran “Pelaksanaan Baris Gilir Tanpa Kunci” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran C++ Academy ini?

Ya. Setiap pelajaran C++ Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

← Kembali ke C++ Academy