调度系统设计

调度原理

协作式调度与抢占式调度
- 协作式调度允许任务执行任意长的时间，直到任务主动通知调度器让出资源；
- 抢占式调度允许任务在执行过程中被调度器挂起，调度器会重新决定下一个运行的任务
单调度器与多调度器
- 多调度器：将待调度的资源分区，让多个调度器分别负责调度不同区域中的资源
任务分享与任务窃取
- 工作分享和工作窃取是完全不同的两种再分配策略。
- 在工作分享中，当调度器创建了新任务时，它会将一部分任务分给其他调度器；
- 在工作窃取中，当调度器的资源没有被充分利用时，它会从其他调度器中窃取一些待分配的任务
- 与工作分享相比，工作窃取只会在当前调度器的资源没有被充分利用时才会触发，所以工作窃取引入的额外开销更小。eg linux, go

状态模块会从不同途径收集尽可能多的信息为调度提供丰富的上下文，其中可能包括资源的属性、利用率和可用性等信息。根据场景的不同，上下文可能需要存储在 MySQL 等持久存储中，一般也会在内存中缓存一份以减少调度器访问上下文的开销。

决策模块会根据状态模块收集的上下文和任务的规格做出调度决策，需要注意的是做出的调度决策只是在当下有效，在未来某个时间点，状态的改变可能会导致之前做的决策不符合任务的需求

调度器在调度时都会通过以下的三个步骤为任务调度合适的资源：

在 Linux 操作系统中，调度器调度的不是进程也不是线程，它调度的是 task_struct 结构体，该结构体既可以表示线程，也可以表示进程，而调度器会将进程和线程都看成任务。

初始调度器 · v0.01 ~ v2.4
- 由几十行代码实现，功能非常简陋；
- 同时最多处理 64 个任务；
O(n) 调度器 · v2.4 ~ v2.6
- 调度时需要遍历全部任务；
- 当待执行的任务较多时，同一个任务两次执行的间隔很长，会有比较严重的饥饿问题；
𝑂(1)调度器 · v2.6.0 ~ v2.6.22
- 通过引入运行队列和优先数组实现 𝑂(1)的时间复杂度;
- 使用本地运行队列替代全局运行队列增强在对称多处理器的扩展性；每个cpu都有一个队列减少不同cpu锁竞争。
- 引入工作窃取保证多个运行队列中任务的平衡；
完全公平调度器 · v2.6.23 ~ 至今
- 引入红黑树和运行时间保证调度的公平性；
- 引入调度类实现不同任务类型的不同调度策略。
- CFS 的调度过程还是由 schedule 函数完成的，该函数的执行过程可以分成以下几个步骤：
  1. 关闭当前 CPU 的抢占功能；
  2. 如果当前 CPU 的运行队列中不存在任务，调用 idle_balance 从其他 CPU 的运行队列中取一部分执行；
  3. 调用 pick_next_task 选择红黑树中优先级最高的任务；
  4. 调用 context_switch 切换运行的上下文，包括寄存器的状态和堆栈；
  5. 重新开启当前 CPU 的抢占功能；

单线程调度器 ·0.x
- 只包含 40 多行代码；
- 程序中只能存在一个活跃线程，由 G-M 模型组成；
多线程调度器 ·1.0
- 允许运行多线程的程序；
- 全局锁导致竞争严重；
任务窃取调度器 ·1.1
- 引入了处理器 P，构成了目前的 G-M-P 模型；
- 在处理器 P 的基础上实现了基于工作窃取的调度器；
- 在某些情况下，Goroutine 不会让出线程，进而造成饥饿问题；
- 时间过长的垃圾回收（Stop-the-world，STW）会导致程序长时间无法工作；
抢占式调度器 ·1.2 ~ 至今
- 基于协作的抢占式调度器 - 1.2 ~ 1.13
  - 通过编译器在函数调用时插入抢占检查指令，在函数调用时检查当前 Goroutine 是否发起了抢占请求，实现基于协作的抢占式调度；
  - Goroutine 可能会因为垃圾回收和循环长时间占用资源导致程序暂停；
- 基于信号的抢占式调度器 - 1.14 ~ 至今
  - 实现基于信号的真抢占式调度；
  - 垃圾回收在扫描栈时会触发抢占调度；
  - 抢占的时间点不够多，还不能覆盖全部的边缘情况；
非均匀存储访问调度器 · 提案
- 对运行时的各种资源进行分区；
- 实现非常复杂，到今天还没有提上日程；

Linux 和 Go 语言调度器，这两个调度器的场景都非常相似，它们最终都是要充分利用机器上的 CPU 资源，所以在实现和演进上有很多相似之处：