返回题库

原子标志自旋等待

Atomic Flag Spinwait

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

题目详情

在超低延迟交易系统中，线程同步通常使用自旋等待而非操作系统级互斥锁，以消除上下文切换开销。std::atomic_flag 是 C++ 中最简单的原子类型，保证无锁，是构建低延迟同步原语的理想基础。

任务：实现可复用的自旋等待屏障 SpinWaitBarrier。多个线程在 barrier 上等待，当所有线程到达后同时释放继续执行。使用 atomic_flag 和自旋循环实现，不使用 mutex 或 condition_variable。

英文原题

In ultra-low-latency trading systems, thread synchronization is often implemented using spin-locks or spin-wait loops rather than OS-level mutexes to eliminate context-switch overhead. The std::atomic_flag is the simplest atomic type in C++ and is guaranteed to be lock-free, making it an excellent building block for low-latency synchronization primitives.
Task
Implement a reusable spin-wait barrier for exactly two threads by completing the SpinBarrier class and its wait() method. The wait() met

解析

问题分析

std::atomic_flag 是 C++ 唯一的无锁原子类型，适用于自旋锁等场景。相比 std::atomic<bool>，它保证在所有平台上都是无锁的。自旋等待适合临界区极短（< 100 周期）的场景。

实现

class SpinLock {
    std::atomic_flag flag_ = ATOMIC_FLAG_INIT;
public:
    void lock() { while (flag_.test_and_set(std::memory_order_acquire)) 
        __builtin_ia32_pause(); }  // x86 PAUSE 指令减少功耗
    bool try_lock() { return !flag_.test_and_set(std::memory_order_acquire); }
    void unlock() { flag_.clear(std::memory_order_release); }
};

复杂度与边界

  • 时间复杂度：lock 取决于竞争，try_lock O(1)
  • 空间复杂度：O(1)
  • 边界条件：(1) 持有自旋锁时不可睡眠 (2) 不可递归 (3) 仅适合纳秒级临界区

英文解析

Analysis

`std::atomic_flag` is C++'s only lock-free atomic type, suitable for spinlock implementations. Unlike `std::atomic`, it guarantees lock-free operation on all platforms. Spin-waiting is appropriate for critical sections shorter than ~100 CPU cycles.

Solution

class SpinLock {
    std::atomic_flag flag_ = ATOMIC_FLAG_INIT;
public:
    void lock() { while (flag_.test_and_set(std::memory_order_acquire)) 
        __builtin_ia32_pause(); }  // x86 PAUSE instruction reduces power consumption
    bool try_lock() { return !flag_.test_and_set(std::memory_order_acquire); }
    void unlock() { flag_.clear(std::memory_order_release); }
};

Complexity & Edge Cases

  • Time complexity: lock depends on contention; try_lock O(1)
  • Space complexity: O(1)
  • Edge cases: (1) Must not sleep while holding spinlock (2) Not recursive — same thread re-locking causes deadlock (3) Only suitable for nanosecond-scale critical sections

Key Considerations

  1. Critical section duration: Spinwait only suitable for critical sections <1μs; longer sections waste CPU cycles and cause cache line contention
  2. Exponential backoff: Pure spin burns CPU; add exponential backoff (yield, then pause, then sleep) to reduce contention on high-load systems
  3. NUMA awareness: Atomic flag contention across NUMA nodes has 2-5x higher latency than within-node; prefer per-core data structures for NUMA systems
  4. Fairness: Spinwait provides no fairness guarantee; luckier threads acquire lock more frequently — not suitable where fairness is a correctness requirement