调度器

操作系统中线程切换，涉及到上下文切换。操作系统会中断、系统调用时执行线程的上下文切换。这是一种昂贵的操作，需要从用户态转移到内核态，保存要切换的线程的执行状态，将一些重要的寄存器的值和先查询状态保存在线程控制块数据结构中，当恢复线程运行时，再加载到集群中，从内核态转移用户态。

goroutine 的调度由 Go 运行时可控制的，每个编译的 Go 程序都会附加一个很小的运行时，负责内存分配、goroutine 的调度和垃圾回收。 goroutine 的上下文切换可开销相对线程来说是非常小的。

G: 表示 goroutine,存储了与 goroutine 相关的信息，比如栈、状态、要执行的函数等。
P: 表示逻辑 processor, P 负责把 M 和 G 绑定在一起，让一系列的 goroutine 在某个 M 上有序执行。默认下 P 的数量等于 CPU 的逻辑核心数量。也可以通过 runtime.GOMAXPROCS 改变
M: 表示执行计算资源单元，Go 会把它和操作线程一一对应。只有在P和M绑定只有才能让P的本地队列中的goroutine执行起来

调度过程

启动一个goroutine g0
查找是否有空闲的P
- 如果没有就直接返回如果有，就用系统API创建一个M(线程)
由这个刚创建的M循环执行能找到G任务
G任务执行的循序先从本地队列找，本地没有找到就从全局队列找，如果还没有找到就去其他P中找
所有的G任务的执行是按照go的调用顺序执行的
如果一个系统调用或者G任务执行的时间太长，就会一直占用这个线程
- (1)在启动的时候，会专门创建一个线程sysmon，用来监控和管理，在内部挨个循环
- (2)sysmon主要执行任务(中断G任务)
  - 记录所有P的G任务并用schedtick变量计数，该变量在每执行一个G任务之后递增
  - 如果schedtick一直没有递增，说明这个P一直在执行同一个任务
  - 如果持续超过10ms，就在这个G任务的栈信息加一个标记
  - G任务在执行的时候，会检查这个标记，然后中断自己，把自己添加到队列的末尾，执行下一个G
- G任务的恢复
  - 中断的时候将寄存器中栈的信息保存到自己G对象里面
  - 当两次轮到自己执行的时候，将自己保存的栈信息复制到寄存器里面，这样就可以接着上一次运行 goroutine是按照抢占式进行调度的，一个goroutine最多执行10ms就会换下一个

窃取

在 GMP 模型中，每个 M 都拥有一个本地队列，用于存储等待执行的 goroutine。当 M 需要执行 goroutine 时，会优先从本地队列中获取。如果本地队列为空，则会从全局队列中获取 goroutine。

为了保证全局队列中的 goroutine 能够得到公平的调度，Go 语言的调度器会每隔 61 次从全局队列中获取 goroutine 来执行。

这个数字的选择是经过考虑的。如果数字太小，则会导致全局队列中的 goroutine 得不到足够的调度机会。如果数字太大，则会导致本地队列中的 goroutine 得不到足够的调度机会。

61 是一个质数，并且与常见的 2 的幂次方（例如 64、48）不重合。这可以避免与其他调度机制发生冲突。

此外，61 也是一个相对较小的数字，这可以减少全局队列的锁竞争。

总而言之，Go 语言的调度器每隔 61 次从全局队列中获取 goroutine 来执行，是为了保证全局队列中的 goroutine 能够得到公平的调度机会。

具体来说，Go 语言的调度器会按照以下步骤执行：

从本地队列中获取 goroutine 来执行。如果本地队列为空，则从全局队列中窃取一半的 goroutine 来执行。如果全局队列也为空，则将 M 置于休眠状态。每隔 61 次，调度器会跳过步骤 1，直接从全局队列中获取 goroutine 来执行。

这种调度策略可以保证全局队列中的 goroutine 能够得到公平的调度机会，同时也可以避免本地队列的锁竞争。

m0 和 g0

在 Go 语言的运行时中，g0 和 m0 是两个非常重要的对象。

g0 代表的是 main goroutine，它是 Go 程序的第一个 goroutine。g0 负责执行 main() 函数，并创建其他 goroutine。

m0 代表的是 main thread，它是 Go 程序的第一个线程。m0 负责执行 g0，并为其他 goroutine 提供调度服务。

协作式调度和基于信号的抢占调度

Go 1.14 之前的协作式调度主要有以下两个弊端：

无法保证 goroutine 的执行时间：如果一个 goroutine 进入死循环，则会导致其他 goroutine 无法得到执行。无法利用多核 CPU 的全部性能：由于 goroutine 需要主动将控制权交还给调度器，因此调度器无法有效地利用多核 CPU 的全部性能。举例子说明

无法保证 goroutine 的执行时间

func main() {
    for i := 0; i < 10000; i++ {
        go func() {
            for {}
        }()
    }

// 其他 goroutine 无法得到执行
}

在这个例子中，main() 函数创建了 10000 个 goroutine，每个 goroutine 都进入了一个死循环。由于 goroutine 无法被抢占，因此其他 goroutine 无法得到执行。

无法利用多核 CPU 的全部性能

func main() {
    for i := 0; i < 10000; i++ {
        go func() {
            time.Sleep(1 * time.Second)
        }()
    }

// CPU 使用率无法达到 100%
}

在这个例子中，main() 函数创建了 10000 个 goroutine，每个 goroutine 都会睡眠 1 秒。由于 goroutine 需要主动将控制权交还给调度器，因此调度器无法有效地利用多核 CPU 的全部性能。

Go 1.14 及之后的版本引入了基于信号的抢占调度，可以解决上述两个弊端。

保证 goroutine 的执行时间：当 goroutine 的运行时间超过一定时间时，调度器会向 goroutine 发送一个 SIGURG 信号，强制 goroutine 将控制权交还给调度器。利用多核 CPU 的全部性能：调度器可以利用 SIGURG 信号来抢占 goroutine 的执行，从而提高 CPU 的利用率。总结

Go 1.14 之前的协作式调度存在一些弊端，例如无法保证 goroutine 的执行时间和无法利用多核 CPU 的全部性能。Go 1.14 及之后的版本引入了基于信号的抢占调度，可以解决这些弊端。

什么情况下 goroutine 会被挂起

goroutine被挂起也就是调度器重新发起调度更换P来执行时
在channel堵塞的时候;
在垃圾回收的时候;
sleep休眠;
锁等待;
抢占;
IO阻塞;

调度器流程图

sequenceDiagram
    participant G as Goroutine
    participant P as Processor (P)
    participant M as Machine (M)
    participant Scheduler as 调度器

    G->>P: 添加到本地运行队列
    P->>M: 绑定到 M（线程）
    M->>P: 请求 Goroutine
    P->>M: 分配 Goroutine
    M->>G: 执行 Goroutine
    alt Goroutine 阻塞
        G->>M: 阻塞（例如系统调用）
        M->>P: 通知 M 阻塞
        P->>Scheduler: 寻找新的 M
        Scheduler->>P: 分配新 M
        P->>M': 绑定新 M
        M'->>P: 请求下一个 Goroutine
        P->>M': 分配 Goroutine
    else Goroutine 完成
        G->>M: 执行完成
        M->>P: 请求下一个 Goroutine
    end

G-M-P 模型

G (Goroutine):表示一个并发任务，是 Go 程序中最基本的执行单元。包含了栈、指令指针和其他调度相关的信息。轻量级，创建和销毁的开销很小。
M (Machine):代表一个操作系统线程。负责执行 G。数量可能会随着程序的运行而动态变化。
P (Processor):表示一个虚拟的处理器，是 G 和 M 之间的中间层。维护一个本地 G 队列。数量通常等于 GOMAXPROCS 设置（默认为 CPU 核心数）。

调度流程

G 的创建和加入队列： 当使用 go 关键字创建新的 goroutine 时，新的 G 被创建。新创建的 G 首先尝试加入当前 P 的本地队列。如果本地队列已满，G 会被放入全局队列。
G 的执行： M 会从与之绑定的 P 的本地队列中获取 G 来执行。如果本地队列为空，M 会尝试从全局队列或其他 P 的队列中偷取 G。
阻塞与唤醒： 当 G 因为系统调用或同步操作（如通道操作、互斥锁）而阻塞时，M 会与 P 解绑。如果有空闲的 M，P 会与之绑定并继续执行其他 G。当阻塞的 G 被唤醒时，它会重新进入 P 的本地队列或全局队列。

工作窃取（Work Stealing）算法

当一个 P 的本地队列为空时，它会尝试从其他来源获取 G：

从全局队列中获取 G。
从其他 P 的本地队列"偷"G（通常从队列尾部偷取）。
从网络轮询器中获取 G。

这种机制确保了负载均衡，提高了 CPU 利用率。调度器的抢占机制

基于协作的抢占（Go 1.14 之前）：在函数调用时检查抢占标志。存在无法抢占的问题，如长时间运行的 for 循环。
异步抢占（Go 1.14 及之后）：使用信号机制实现。能够中断正在执行的 G，使长时间运行的 G 也能被抢占。

系统调用处理

当 G 即将进行系统调用时，M 会与 P 解绑。

如果系统调用是阻塞的，运行时会创建或唤醒另一个 M 来接管 P。
非阻塞的系统调用完成后，G 会尝试重新获取同一个 P，如果失败则进入全局运行队列。

调度器的初始化和运行

程序启动时，运行时会根据 GOMAXPROCS 创建 P。
main goroutine 开始在一个 M 上运行。
调度器会启动一些辅助 goroutine，如 GC、监控等。

cs-book

调度器

调度过程

窃取

m0 和 g0

协作式调度 和 基于信号的抢占调度

什么情况下 goroutine 会被挂起

调度器流程图

协作式调度和基于信号的抢占调度