ordered-work-steal.md

title	date	author
有序工作窃取总览	2025-01-17 00:34:00 -0800	loongs-zhang

有序工作窃取总览

English | 中文

为什么需要有序工作窃取？

在现实世界中，总是有一些线程先完成自己的任务，而其他线程还有任务需要处理。于是，就会出现一核有难、多核围观的壮观场景。

显然，我们不希望这种情况发生。对于空闲的线程，与其让它们围观其他线程工作，不如让它们帮助其他线程工作。此外，我们希望根据优先级执行任务，优先级越高，任务越早被执行。

什么是有序工作窃取队列？

有序工作窃取队列由一个全局队列和多个本地队列组成，全局队列是无界的，而本地队列是一个有界的SkipList集合。为了确保高性能，本地队列的数量通常等于线程的数量。值得一提的是，如果所有线程都优先处理本地任务，可能会出现一种极端情况，即共享队列上的任务永远没有机会被调度。为了避免这种不平衡，参考goroutine的设计，每次线程从本地队列调度了60个任务后，强制从共享队列中弹出优先级最高的任务。

push的工作原理

flowchart TD
    Cond{本地队列是否已满?}
    PS[将任务推入本地队列]
    PTG[将本地队列中一半的低优先级任务推入全局队列]
    PG[将任务推入全局队列]
    push --> Cond
    Cond -- 否 --> PS
    Cond -- 是 --> PTG --- PG

Loading

pop的工作原理

flowchart TD
    Cond1{本地队列中是否有任务?}
    Cond2{其他本地队列中是否有任务?}
    Cond3{全局队列中是否有任务?}
    PS[弹出优先级最高的任务]
    ST[从其他本地队列窃取高优先级任务]
    PF[未找到任务]
    pop --> Cond1
    Cond1 -- 是 --> PS
    Cond1 -- 否 --> Cond2
    Cond2 -- 是 --> ST --> PS
    Cond2 -- 否 --> Cond3
    Cond3 -- 是 --> PS
    Cond3 -- 否 --> PF

Loading