4. 本地运行队列（LRQ）：结构定义、入队与出队算法、优先级与窃取机制

本地运行队列（Local Run Queue, LRQ）是每个 P（Processor）私有的 Goroutine 待运行队列。与全局运行队列（GRQ）相比，LRQ 无需全局锁即可完成大部分调度操作，是 Go 调度器实现高吞吐、低延迟的核心数据结构。本章从结构定义、入队/出队算法、优先级处理以及工作窃取（Work Stealing）机制四个维度进行深度剖析。

4.1 LRQ 结构定义

LRQ 在 Go 运行时中由 p 结构体的 runq 字段表示，是一个基于数组的环形缓冲区（Ring Buffer），配合无锁原子操作实现高效并发访问。其核心结构如下：

以下 SVG 展示了 LRQ 在 P 结构体中的位置及其与 runnext、全局队列的关系：

4.2 入队算法

LRQ 的入队操作遵循“优先写入 runnext，其次写入环形缓冲区，最后溢出到全局队列”的三级策略。具体流程如下：

1. 尝试写入 runnext：如果 runnext 为空，直接将新 Goroutine 写入 runnext，入队完成。此操作使用原子 CAS（Compare-And-Swap）保证线程安全。
2. 写入环形缓冲区：如果 runnext 已被占用，则将原 runnext 中的 Goroutine 推入 runq 尾部，新 Goroutine 占据 runnext。入队 runq 时，通过原子操作递增 runqtail。
3. 缓冲区满处理：当 runqtail - runqhead == 256 时，环形缓冲区已满。此时将 runq 中一半的 Goroutine（128 个）批量转移到全局运行队列，以腾出空间。

4.3 出队算法

出队操作是调度器获取下一个可运行 Goroutine 的核心路径。P 在执行完当前 Goroutine 或发生调度点时，按以下优先级尝试获取：

出队算法的核心思想是：优先使用本地资源，避免全局竞争；仅在本地无可用 Goroutine 时，才向全局或其它 P 请求。

4.4 优先级与 runnext 机制

runnext 是 LRQ 中一个特殊的单元素槽位，用于实现 Goroutine 的优先级调度。其设计意图包括：

• Goroutine 局部性：当前 Goroutine 通过 go 关键字创建的新 Goroutine，被放入 runnext，确保其优先于队列中其他 Goroutine 执行，减少上下文切换的缓存缺失。
• 网络轮询器唤醒：当网络轮询器唤醒一个 Goroutine 时，将其放入目标 P 的 runnext，以快速响应 I/O 事件。
• 系统调用返回：Goroutine 从系统调用返回时，如果绑定到原 P，也会被放入 runnext，保持亲和性。

4.5 工作窃取（Work Stealing）机制

工作窃取是 Go 调度器实现负载均衡的关键算法。当某个 P 的 LRQ 为空且全局队列也为空时，该 P 会尝试从其他 P 的 LRQ 中窃取 Goroutine。窃取流程如下：

1. 随机选择目标 P：从所有 P 中随机选择一个作为窃取目标，避免所有空闲 P 同时窃取同一个目标造成冲突。
2. 检查目标 LRQ 长度：如果目标 LRQ 中 Goroutine 数量 < 2，则跳过该目标，重新选择。
3. 窃取一半：原子读取目标 P 的 runqhead 和 runqtail，计算队列长度 n = tail - head。窃取 n/2 个 Goroutine（向下取整），并将这些 Goroutine 转移到当前 P 的 LRQ 中。
4. 更新目标 head：通过原子操作将目标 P 的 runqhead 增加 n/2，完成窃取。

以下 SVG 展示了工作窃取过程中两个 P 之间的交互：

4.6 算法复杂度与性能对比