什么是Restartable Sequences(RSEQs)？如何在编程及任务系统中应用？

Linux 4.18引入了rseq(2)系统调用，目前相关公开资料极少，Stack Overflow上也仅有一个相关问题提及它。

可重启序列（简称RSEQ）是一种用户态并发优化手段，核心是实现快速的用户态每CPU临界区。该概念最早在2013年的一场技术演讲中被提出，由EfficiOS团队主导贡献到Linux内核，相关内核提交记录完成了功能落地。它的设计初衷是让用户态程序访问每CPU数据时，无需依赖昂贵的系统调用或锁机制，同时能被内核安全中断并重启，避免数据竞争。

尽管知名度不高，RSEQ已经被用于TCMalloc内存分配器的性能优化，能显著降低并发场景下的同步开销。

实际示例：在无锁MPSC队列中使用RSEQ #

假设正在开发一个C++任务系统，其中包含一个无锁多生产者单消费者（MPSC）队列，如何通过引入rseq(2)提升其性能？

原队列代码 #

class mpsc_list_node
{
    mpsc_list_node* _next;

    template<typename T>
        requires std::derived_from<T, mpsc_list_node>
    friend class mpsc_list;
};

template<typename T>
    requires std::derived_from<T, mpsc_list_node>
class mpsc_list
{
private:
    std::atomic<T*> head{ nullptr };

private:
    static constexpr size_t COMPLETED_SENTINEL = 42;

public:
    mpsc_list() noexcept = default;
    mpsc_list(mpsc_list&& other) noexcept :
        head{ other.head.exchange(reinterpret_cast<T*>(COMPLETED_SENTINEL), std::memory_order_relaxed) }
    {
    }

    bool try_enqueue(T& to_append)
    {
        T* old_head = head.load(std::memory_order_relaxed);
        do
        {
            if (reinterpret_cast<size_t>(old_head) == COMPLETED_SENTINEL)
                [[unlikely]]
                {
                    return false;
                }
            to_append._next = old_head;
        } while (!head.compare_exchange_weak(old_head, &to_append, std::memory_order_release, std::memory_order_relaxed));
        return true;
    }

    template<typename Func>
    void complete_and_iterate(Func&& func) noexcept(std::is_nothrow_invocable_v<Func, T&>)
    {
        T* p = head.exchange(reinterpret_cast<T*>(COMPLETED_SENTINEL), std::memory_order_acquire);
        while (p)
            [[likely]]
            {
                T* cur  = p;
                T* next = static_cast<T*>(p->_next);
                p       = next;
                func(*cur);
            }
    }
};

队列在任务系统中的作用 #

该MPSC队列是任务系统同步机制的核心：

任务间仅使用原子计数器作为同步原语，思路源自Naughty Dog引擎的任务系统设计。

任务的通用Promise类型（promise_base）是mpsc_list的派生类，这个列表用于存储依赖当前任务的子任务，是基于原子操作实现的无锁链表，每个节点存储依赖任务的Promise指针及下一个节点，不使用动态内存分配。

当任务通过co_await等待一组依赖任务时：

1. 其Promise将内部原子计数器设为依赖任务的数量；
2. 在栈上分配与依赖数量相等的notifier对象数组，notifier是链表节点类型，每个notifier都指向被挂起的任务，且无后续节点；
3. 遍历每个依赖任务，尝试将对应的notifier添加到依赖任务的列表中：
   • 若依赖任务已完成（列表头被设为特殊哨兵值），则挂起任务自减自身的原子计数器；
   • 若依赖任务未完成，则通过CAS循环将notifier添加到该依赖任务的列表中；
4. 遍历完成后，若所有依赖都已完成，任务无需挂起，直接继续执行——因为该任务系统没有挂起任务队列，仅存在就绪任务队列，挂起任务仅存储在依赖任务的链表中，无依赖却挂起的任务永远无法被唤醒。

当任务完成时：

1. 将自身列表头设为特殊哨兵值；
2. 遍历所有依赖任务的链表节点，原子化地自减它们的原子计数器；
3. 若自减前的计数器值为1，说明当前任务是该依赖任务的最后一个完成项，会将其推入就绪任务队列。

引入RSEQ的优化方案 #

当前try_enqueue中的CAS循环在高并发场景下会因频繁重试产生额外开销，RSEQ可以将「检查哨兵值+设置next指针+CAS更新head」的操作序列标记为可重启临界区，减少不必要的重试：

1. 线程初始化RSEQ：在线程启动时，调用rseq(2)系统调用注册线程的RSEQ结构体，指定临界区的重启点。
2. 标记可重启临界区：在try_enqueue中，把读取head、检查哨兵值、设置to_append._next的代码包裹在RSEQ临界区内——若线程被内核中断（如调度），内核会自动将指令指针恢复到临界区起始点，重新执行整个序列。
3. 优化CAS逻辑：利用RSEQ的原子性保证，减少CAS重试次数，因为临界区内的操作要么完整执行，要么被重启，无需处理部分执行的中间状态。

优化后的try_enqueue伪代码示例：

bool try_enqueue(T& to_append)
{
    // 初始化RSEQ临界区（需按内核要求配置结构体参数）
    struct rseq rseq = { ... };
    rseq(RSEQ_REGISTER, &rseq, sizeof(rseq), 0);

    // 进入可重启临界区
    __rseq_begin();
    T* old_head = head.load(std::memory_order_relaxed);
    if (reinterpret_cast<size_t>(old_head) == COMPLETED_SENTINEL) {
        __rseq_abort();
        return false;
    }
    to_append._next = old_head;
    // 提交临界区并执行CAS
    if (head.compare_exchange_strong(old_head, &to_append, std::memory_order_release, std::memory_order_relaxed)) {
        __rseq_end();
        return true;
    }
    __rseq_abort();
    return try_enqueue(to_append); // 触发重启或直接重试
}

注意：实际使用时需链接librseq库，或直接使用内核提供的RSEQ宏/内联函数，确保与内核交互的正确性。

内容的提问来源于stack exchange，提问作者janekb04