C++ Academy · บทเรียน

การสร้างคิวแบบไร้ล็อก

ทำความเข้าใจการออกแบบคิวแบบไร้ล็อกสำหรับผู้ผลิตรายเดียวและผู้บริโภครายเดียว

บทเรียน 3 จาก 414 ขั้นตอน

การสร้างคิวแบบไร้ล็อก เป็นบทเรียน C++ Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน C++ Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส C++ Academy มีบทเรียนทั้งหมด 4 บทเรียน

เหตุใดจึงใช้คิวแบบไม่ใช้ล็อก

คิวที่ใช้มิวเท็กซ์อาจกลายเป็นคอขวดเมื่อมีการแย่งใช้สูง คิวแบบไม่ใช้ล็อกช่วยให้ผู้ผลิตและผู้บริโภคคืบหน้าไปพร้อมกันได้

SPSC เทียบกับ MPMC

มีสองรูปแบบ:

SPSC — ผู้ผลิตหนึ่งราย ผู้บริโภคหนึ่งราย (ง่ายและเร็วที่สุด)
MPMC — ผู้ผลิตหลายราย ผู้บริโภคหลายราย (ทั่วไปที่สุด)

SPSC เป็นตัวเลือกตามธรรมชาติเมื่อคุณควบคุมทั้งสองฝั่ง

แบบร่างบัฟเฟอร์วงแหวน SPSC

บัฟเฟอร์แบบวนรอบที่มีดัชนีสองตัว ได้แก่ ดัชนีหัว (ผู้บริโภค) และดัชนีท้าย (ผู้ผลิต) แต่ละฝ่ายจะอัปเดตดัชนีของตนเอง

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

ผู้ผลิตตรวจสอบช่องว่าง เขียนข้อมูล แล้วเผยแพร่โดยอัปเดตดัชนีท้าย

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

ผู้บริโภคตรวจสอบว่ามีข้อมูลหรือไม่ อ่านข้อมูล แล้วเผยแพร่โดยอัปเดตดัชนีหัว

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

การจับคู่ลำดับหน่วยความจำ

การจัดเก็บแบบปล่อยที่ดัชนีท้ายจะทำงานสอดคล้องกับการโหลดแบบรับที่ดัชนีท้ายของผู้บริโภค และในทางกลับกัน หากไม่มีการจัดลำดับที่ถูกต้อง การเขียนข้อมูลอาจถูกเลื่อนให้เกิดขึ้นหลังการอัปเดตดัชนี

การเติมช่องว่างให้บรรทัดแคช

เพื่อหลีกเลี่ยงการแชร์บรรทัดแคชโดยไม่ตั้งใจ ให้จัดวาง head_ และ tail_ ไว้คนละบรรทัดแคช โดยทั่วไปให้ห่างกัน 64 ไบต์ ใช้ alignas

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

MPMC: ยากกว่ามาก

ผู้ผลิตหรือผู้บริโภคหลายรายจำเป็นต้องมีการประสานงานเพิ่มเติม โดยมักใช้ลูป CAS กับดัชนีที่ใช้ร่วมกัน มีการออกแบบอยู่มากมาย เช่น คิว Vyukov คิว MS และแบบใช้ตัวชี้อันตราย

Boost.Lockfree

คิวไร้ล็อกระดับพร้อมใช้งานจริงนั้นสร้างได้ยาก โปรดใช้ Boost.Lockfree หรือ ProducerConsumerQueue ของ Folly แทนการเขียนขึ้นเอง

ข้อแลกเปลี่ยน

คิวไร้ล็อก:

อัตราการประมวลผลสูงขึ้นเมื่อมีการแย่งใช้ทรัพยากร
เวลาแฝงมีขอบเขต ไม่ต้องรอล็อก
เขียนและแก้ไขข้อผิดพลาดได้ยากกว่ามาก
ข้อผิดพลาดด้านการจัดลำดับหน่วยความจำไม่แสดงอาการและตรวจพบได้ยาก

การทดสอบโค้ดไร้ล็อก

ใช้ ThreadSanitizer (-fsanitize=thread) เพื่อตรวจจับการแข่งขันข้อมูล ใช้การทดสอบภาวะเค้นโดยแทรกการหน่วงเวลาแบบสุ่ม เพื่อเปิดเผยข้อผิดพลาดด้านการจัดลำดับ

เมื่อมิวเทกซ์ก็เพียงพอ

แอปพลิเคชันส่วนใหญ่ไม่จำเป็นต้องใช้คิวไร้ล็อก โปรดวัดประสิทธิภาพก่อน คิวที่ป้องกันด้วยมิวเทกซ์และพัฒนาอย่างดีมักมีประสิทธิภาพเพียงพอ โดยเฉพาะเมื่อประมวลผลเป็นชุด

ตรวจสอบอย่างรวดเร็ว

การแชร์ข้อมูลเทียม คืออะไร และเหตุใดจึงต้องเติมช่องว่างให้ head_ และ tail_?

ตอบคำถามในบทเรียนแบบโต้ตอบ

สรุปทบทวน

คิว SPSC ไร้ล็อกใช้บัฟเฟอร์วงแหวน โดยผู้ผลิตเป็นเจ้าของดัชนีท้าย และผู้บริโภคเป็นเจ้าของดัชนีหัว ใช้การจัดลำดับแบบรับและปล่อย และเติมช่องว่างให้ดัชนีอยู่คนละบรรทัดแคช สำหรับ MPMC ควรเลือกใช้ไลบรารีที่ผ่านการทดสอบแล้ว

เริ่มต้นได้ฟรี

เรียนรู้ C++ ด้วย AI tutor — ฟรี

เขียนและเรียกใช้โค้ดจริงในเบราว์เซอร์ของคุณ รับความช่วยเหลือทันทีจาก AI tutor 24/7 และเรียนรู้ต่อจากที่คุณหยุดบนเว็บหรือในแอป

คอร์ส: 51
บทเรียน: 203

เริ่มเรียนฟรี ดูหลักสูตรเต็ม

คำถามที่พบบ่อย

บทเรียน “การสร้างคิวแบบไร้ล็อก” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “การสร้างคิวแบบไร้ล็อก” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส C++ Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส C++ Academy มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “การสร้างคิวแบบไร้ล็อก”

ทำความเข้าใจการออกแบบคิวแบบไร้ล็อกสำหรับผู้ผลิตรายเดียวและผู้บริโภครายเดียว คุณปฏิบัติ C++ Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน C++ Academy หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน C++ Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน

บทเรียน “การสร้างคิวแบบไร้ล็อก” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน C++ Academy นี้ได้ไหม

ได้ บทเรียน C++ Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

std::atomic และลำดับการจัดเรียงหน่วยความจำ
รูปแบบ Compare-and-Swap (CAS)
การสร้างคิวแบบไร้ล็อก
พอยน์เตอร์ตรวจสอบอันตรายและปัญหา ABA

← กลับไปที่ C++ Academy