返回题库

有界生产者消费者队列

Producer Consumer Bounded

专题
Systems & Architecture / 系统与架构
难度
L2
来源
MyntBit

题目详情

高频交易和行情处理系统常依赖生产者-消费者队列在线程间传递行情或订单消息。有界队列防止内存耗尽并提供自然背压：当队列满时生产者阻塞或丢弃，避免系统过载。

任务：实现 BoundedQueue 类，有界生产者-消费者队列。固定容量，push() 在队列满时阻塞，pop() 在队列空时阻塞。使用 mutex 和 condition_variable 实现线程安全。

英文原题

High-frequency trading and market data processing systems often rely on producer-consumer queues to pass messages, such as market ticks or order updates, between threads. A bounded queue prevents memory exhaustion and provides natural back-pressure to producers when downstream consumers cannot keep up with the message rate.
Task
Implement a thread-safe bounded queue in C++ that processes double values.
Your class BoundedQueue must provide the following methods:

  • BoundedQueue(int capacity): Ini
解析

问题分析

有界生产者-消费者队列在满时阻塞生产者，在空时阻塞消费者，实现自然的背压（back-pressure）。在交易系统中，当订单处理速度跟不上订单到达速度时，背压阻止无限内存增长。

实现

template<typename T, size_t N>
class BoundedSPSCQueue {
    std::array<T, N> buffer_;
    std::atomic<size_t> write_pos_{0}, read_pos_{0};
public:
    bool try_push(T v) {
        size_t w = write_pos_.load(std::memory_order_relaxed);
        if (w - read_pos_.load(std::memory_order_acquire) >= N) return false;
        buffer_[w % N] = std::move(v);
        write_pos_.store(w + 1, std::memory_order_release);
        return true;
    }
    std::optional<T> try_pop() {
        size_t r = read_pos_.load(std::memory_order_relaxed);
        if (r >= write_pos_.load(std::memory_order_acquire)) return std::nullopt;
        T v = std::move(buffer_[r % N]);
        read_pos_.store(r + 1, std::memory_order_release);
        return v;
    }
};

复杂度与边界

  • 时间复杂度：push/pop O(1) 无锁
  • 空间复杂度：O(N)
  • 边界条件：(1) 仅支持单生产者单消费者 (SPSC) (2) N 必须为 2 的幂以避免取模开销 (3) 空/满通过读写位置差值判断

英文解析

Analysis

A bounded producer-consumer queue blocks producers when full and consumers when empty, implementing natural back-pressure. In trading systems, when order processing can't keep up with arrival rates, back-pressure prevents unbounded memory growth.

Solution

template<typename T, size_t N>
class BoundedSPSCQueue {
    std::array<T, N> buffer_;
    std::atomic<size_t> write_pos_{0}, read_pos_{0};
public:
    bool try_push(T v) {
        size_t w = write_pos_.load(std::memory_order_relaxed);
        if (w - read_pos_.load(std::memory_order_acquire) >= N) return false;
        buffer_[w % N] = std::move(v);
        write_pos_.store(w + 1, std::memory_order_release);
        return true;
    }
    std::optional<T> try_pop() {
        size_t r = read_pos_.load(std::memory_order_relaxed);
        if (r >= write_pos_.load(std::memory_order_acquire)) return std::nullopt;
        T v = std::move(buffer_[r % N]);
        read_pos_.store(r + 1, std::memory_order_release);
        return v;
    }
};

Complexity & Edge Cases

  • Time complexity: O(1) for push/pop with SPSC ring buffer; O(P) for P producers with lock-based MPSC
  • Space complexity: O(Capacity) for ring buffer
  • Edge cases: (1) Full buffer: producer must block, drop, or overwrite oldest entry. (2) Empty buffer: consumer must block or return sentinel. (3) Wrap-around index computation must handle unsigned overflow correctly.

Key Considerations

  1. SPSC optimization: Single-producer single-consumer eliminates CAS overhead; uses relaxed/acquire/release ordering only.
  2. Power-of-2 size: N should be power of 2 for efficient modulo via bitwise AND.
  3. Back-pressure: Full queue returns false from try_push, signaling producer to slow down.
  4. Time complexity: try_push/try_pop O(1) lock-free.