返回题库

屏障阶段同步

Barrier Phase Sync

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

题目详情

在高频交易系统中，订单簿更新常跨多个分区并行处理，要求严格的跨分区一致性。为维持此一致性，工作线程必须在每个处理阶段的末尾同步。

任务：实现 BarrierPhaseSync 类，协调多阶段并行处理。每个阶段结束时所有线程必须在 barrier 上等待，确保所有分区完成当前阶段后才进入下一阶段。

英文原题

In high-frequency trading systems, order book updates are often processed in parallel across multiple partitions requiring strict cross-partition consistency. To maintain this consistency, worker threads must synchronize at the end of each processing cycle before advancing to the next. Since C++20's std::barrier is not always available in legacy environments, developers must construct reusable synchronization primitives using standard mutexes and condition variables.
Task
Implement a reusable C

解析

问题分析

C++20 std::barrier 用于多阶段并行算法中同步一组线程。在所有线程到达屏障点之前，任何线程都不能继续。在量化回测中，可用于确保所有并行 worker 完成当前时间片后才推进到下一时间片。

实现

class PhaseSync {
    std::barrier<std::function<void()>> barrier_;
    std::vector<std::function<void(int)>> phase_hooks_;
    int current_phase_{0};
public:
    PhaseSync(int threads, std::function<void()> on_complete = []{})
        : barrier_(threads, on_complete) {}
    
    void arriveAndWait(int thread_id) {
        if (thread_id < (int)phase_hooks_.size() && phase_hooks_[thread_id])
            phase_hooks_[thread_id] (\1);
        barrier_.arrive_and_wait();
        if (thread_id == 0) current_phase_++;
    }
    void onPhase(int thread_id, std::function<void(int)> hook) {
        if (thread_id >= (int)phase_hooks_.size()) phase_hooks_.resize(thread_id + 1);
        phase_hooks_[thread_id] = hook;
    }
};

复杂度与边界

  • 时间复杂度：arriveAndWait O(1) 或等待最慢线程
  • 空间复杂度：O(线程数)
  • 边界条件：(1) 线程数必须与构造参数一致 (2) 某线程异常退出会导致所有线程永久阻塞 (3) 完成回调中不应抛异常

英文解析

Analysis

C++20 `std::barrier` synchronizes a group of threads in multi-phase parallel algorithms. No thread can proceed until all threads have arrived at the barrier point. In quantitative backtesting, this ensures all parallel workers complete the current time slice before advancing to the next.

Solution

class PhaseSync {
    std::barrier<std::function<void()>> barrier_;
    std::vector<std::function<void(int)>> phase_hooks_;
    int current_phase_{0};
public:
    PhaseSync(int threads, std::function<void()> on_complete = []{})
        : barrier_(threads, on_complete) {}
    
    void arriveAndWait(int thread_id) {
        if (thread_id < (int)phase_hooks_.size() && phase_hooks_[thread_id])
            phase_hooks_.at(thread_id)(current_phase_);
        barrier_.arrive_and_wait();
        if (thread_id == 0) current_phase_++;
    }
    void onPhase(int thread_id, std::function<void(int)> hook) {
        if (thread_id >= (int)phase_hooks_.size()) phase_hooks_.resize(thread_id + 1);
        phase_hooks_[thread_id] = hook;
    }
};

Complexity & Edge Cases

  • Time complexity: O(P) for P threads waiting at barrier; O(1) for phase advancement
  • Space complexity: O(P) for thread arrival tracking
  • Edge cases: (1) Single-thread barrier call deadlocks without timeout. (2) Thread arrival order affects phase hooks execution sequence. (3) Barrier reset between phases must be atomic to prevent race conditions.

Key Considerations

  1. Phase hooks: Per-thread callbacks executed before each barrier arrival, enabling phase-specific preprocessing.
  2. Completion function: `on_complete` runs once when all threads arrive, useful for global state updates.
  3. Thread count: Must match the number of participating threads exactly; mismatch causes undefined behavior.
  4. Time complexity: arrive_and_wait O(1) amortized per thread.