1. Vấn đề nó giải quyết
Một producer và một consumer có thể trao đổi item hữu hạn không cần mutex khi mỗi phía sở hữu một index. SPSC ring dùng atomic head/tail để publish cùng storage cố định, tránh allocation ở steady state.
2. Kiến thức cần có
Ngày 32 và 43-45: ring buffer, atomic, release/acquire ordering, false sharing và role một owner.
3. Ý tưởng cốt lõi
Chỉ producer ghi tail và buffer slot trước release store. Chỉ consumer ghi head sau khi đọc slot, còn acquire load quan sát progress phía kia đã publish.
4. Cú pháp tối thiểu
buffer[tail] = value;
tail.store(next, std::memory_order_release);
if (head != tail.load(std::memory_order_acquire)) { /* pop */ }5. Cách nó hoạt động
Producer retry bounded push cho các value 10, 20, 30; chỉ nó cập nhật tail index.
Consumer retry pop, chỉ đọc slot đã publish và tiến head bằng release ordering.
Sau khi hai thread join, array nhận được in đúng FIFO order mà không mutex hay dynamic allocation.
6. Lỗi thường gặp
Dùng cùng queue với nhiều producer hoặc consumer phá giả định ownership và tạo race.
Trước khi áp dụng mẫu, phải kiểm tra invariant một producer/một consumer, quy tắc capacity trừ một, index wraparound, publication order, object lifetime và progress.
7. Khi nào nên dùng
Nên dùng khi đúng một producer và một consumer trao đổi dữ liệu nhỏ hữu hạn dưới yêu cầu latency đã đo.
Tránh dùng khi role có nhiều bên hoặc thay đổi, blocking chấp nhận được hay đã có queue thư viện được kiểm chứng.
8. Ví dụ đơn giản
Array capacity bốn cung cấp ba slot dùng được để phân biệt full với empty. Hai thread chuyển ba số nguyên và main in dãy nhận sau khi join.
File .cpp dùng dữ liệu cố định để tự đoán và kiểm tra output.
Mã mẫu hoàn chỉnh
Tệp mã nguồn
cpp14/46_lock_free_spsc_queue/main.cpp
#include <array>
#include <atomic>
#include <cstddef>
#include <iostream>
#include <thread>
template <class T, std::size_t Capacity>
class SpscQueue {
public:
bool push(const T& value) {
const auto tail = tail_.load(std::memory_order_relaxed);
const auto next = (tail + 1) % Capacity;
if (next == head_.load(std::memory_order_acquire)) return false;
buffer_[tail] = value;
tail_.store(next, std::memory_order_release);
return true;
}
bool pop(T& value) {
const auto head = head_.load(std::memory_order_relaxed);
if (head == tail_.load(std::memory_order_acquire)) return false;
value = buffer_[head];
head_.store((head + 1) % Capacity, std::memory_order_release);
return true;
}
private:
std::array<T, Capacity> buffer_{};
std::atomic<std::size_t> head_{0};
std::atomic<std::size_t> tail_{0};
};
int main() {
SpscQueue<int, 4> queue;
const std::array<int, 3> sent{{10, 20, 30}};
std::array<int, 3> received{};
std::thread producer([&] {
for (int value : sent)
while (!queue.push(value)) std::this_thread::yield();
});
std::thread consumer([&] {
for (int& value : received)
while (!queue.pop(value)) std::this_thread::yield();
});
producer.join();
consumer.join();
std::cout << "received:";
for (int value : received) std::cout << ' ' << value;
std::cout << "\n";
}
9. Điều cần nhớ
Tính đúng lock-free SPSC đến từ role cố định, ownership index và publication ordering chính xác.
Compiler hoặc thư viện luôn theo quy tắc cụ thể; cần kiểm tra invariant một producer/một consumer, quy tắc capacity trừ một, index wraparound, publication order, object lifetime và progress.
Ưu tiên cách viết nhỏ nhất thể hiện rõ ý định và đo đạc khi hiệu năng thực sự quan trọng.
10. Câu hỏi tự kiểm tra
Dễ — Mục đích chính của Lock-free SPSC queue là gì?
Trung bình — Vì sao ring có bốn slot vật lý chỉ cung cấp ba vị trí queue dùng được trong thiết kế này?
Khó — Write nào phải happen-before consumer đọc slot, và release store tail cùng acquire load tail thiết lập quan hệ đó thế nào?