返回题库

线程池执行器

Fixed Thread Pool Executor

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

题目详情

量化交易系统依赖低延迟执行和高效资源管理维持竞争优势。固定线程池执行器允许交易策略卸载计算密集任务（如定价多个期权或风控检查），避免在关键路径阻塞。

任务：实现 FixedThreadPool 类，创建 N 个固定工作线程。submit() 方法将任务提交到工作队列，工作线程循环取出并执行。支持 graceful shutdown：停止接受新任务，等待已提交任务完成后退出。

英文原题

Quantitative trading systems rely on low-latency execution and efficient resource management to maintain a competitive edge. A fixed thread pool executor allows trading strategies to offload computationally intensive tasks, such as pricing multiple options or processing market data concurrently, without the overhead of continuously creating and destroying threads.
Task
Implement a ThreadPool class that manages a fixed number of worker threads.
The class should provide:

  1. A constructor ThreadPo
解析

问题分析

固定大小线程池避免每个任务创建/销毁线程的开销。在量化回测中，线程池用于并行计算多个策略变体或蒙特卡洛路径。工作窃取（work stealing）可减少线程闲置。

实现

class ThreadPool {
    std::vector<std::thread> workers_;
    std::queue<std::function<void()>> tasks_;
    std::mutex mtx_; std::condition_variable cv_; bool stop_{false};
public:
    explicit ThreadPool(int n) {
        for (int i = 0; i < n; ++i)
            workers_.emplace_back([this] {
                while (true) {
                    std::function<void()> task;
                    { std::unique_lock lk(mtx_);
                      cv_.wait(lk, [this]{ return stop_ || !tasks_.empty(); });
                      if (stop_ && tasks_.empty()) return;
                      task = std::move(tasks_.front()); tasks_.pop(); }
                    task();
                }
            });
    }
    void enqueue(std::function<void()> f) {
        { std::lock_guard lk(mtx_); tasks_.push(std::move(f)); }
        cv_.notify_one();
    }
    ~ThreadPool() { { std::lock_guard lk(mtx_); stop_ = true; }
        cv_.notify_all(); for (auto& t : workers_) t.join(); }
};

复杂度与边界

  • 时间复杂度：enqueue O(1)，任务执行取决于任务本身
  • 空间复杂度：O(线程数 + 队列中任务数)
  • 边界条件：(1) 任务抛异常会终止工作线程——需在 task() 中捕获 (2) 死锁风险：任务不应等待线程池中的其他任务

英文解析

Analysis

A fixed-size thread pool avoids per-work-item thread creation/destruction overhead. In quantitative backtesting, thread pools parallelize multiple strategy variants or Monte Carlo paths. Work stealing reduces thread idle time.

Solution

class ThreadPool {
    std::vector<std::thread> workers_;
    std::queue<std::function<void()>> tasks_;
    std::mutex mtx_; std::condition_variable cv_; bool stop_{false};
public:
    explicit ThreadPool(int n) {
        for (int i = 0; i < n; ++i)
            workers_.emplace_back([this] {
                while (true) {
                    std::function<void()> work_item;
                    { std::unique_lock lk(mtx_);
                      cv_.wait(lk, [this]{ return stop_ || !tasks_.empty(); });
                      if (stop_ && tasks_.empty()) return;
                      work_item = std::move(tasks_.front()); tasks_.pop(); }
                    work_item();
                }
            });
    }
    ~ThreadPool() {
        { std::lock_guard lk(mtx_); stop_ = true; }
        cv_.notify_all();
        for (auto& w : workers_) w.join();
    }
    template<typename F> void submit(F&& f) {
        { std::lock_guard lk(mtx_); tasks_.push(std::forward<F>(f)); }
        cv_.notify_one();
    }
};

Complexity & Edge Cases

  • Time complexity: O(1) for work submission; O(T) for T work items in queue per worker dequeue
  • Space complexity: O(Q) for Q queued tasks
  • Edge cases: (1) Queue overflow under burst load — tasks may be dropped or block submission thread. (2) Worker thread crash must be detected and replaced. (3) Work dependencies (waiting on futures) can cause thread pool deadlock if all workers are blocked.

Key Considerations

  1. Thread reuse: Workers loop indefinitely, picking up tasks from the shared queue.
  2. Graceful shutdown: stop flag + condition variable ensures all tasks finish before threads exit.
  3. No work stealing: This basic implementation uses a shared queue; for production, consider per-thread local queues with stealing.
  4. Time complexity: submit O(1); execution depends on workload.