说到 cpu 调度，我们第一时间想到的可能是时间片、分时调度等关键词。 要说更具体的内容，可能就比较模糊了，因为涉及到了操作系统的底层知识，平常工作中接触的比较少。
这篇文章也仅仅做个简单的了解。
基础概念
cpu：上下文切换
每一个进程启动，都需要有一个执行指令入口，即使该进程被暂停调度，也会有一个即将被执行的指令入口。
对于这些即将被执行的指令，我们将他们的地址信息保存在 cpu 的寄存器中。
此时，这些寄存器中的信息，就是我们常说的 cpu 上下文。
所以简单点理解就是，将当前任务的上下文保存，并将下一个执行任务的上下文加载到寄存器中的过程，称之为 cpu 的上下文切换。 当然，实际过程更为复杂。
我们常说的上下文更多的是用户级别的，他和系统级上下文保存内容有所不同：
- 用户级上下文：程序运行时堆栈信息、数据块、代码块等。
- 系统级上下文：进程标识信息、控制信息等。
cpu：上下文保存的方式
操作系统给进程分配资源时，会分配一个内核空间，这部分空间只能够由内核代码访问。
执行上下文切换时，会将上下文信息保存在内核空间中，等待下次调度时，再重新加载到 cpu 中。
cpu：上下文切换的方式
执行上下文切换，需要由 cpu 来执行。但由于当前 cpu 已经被进程占用了，所以需要一种策略，来获取 cpu 的执行权限。获取的方式主要有两种：
1、协作式策略
由进程主动让出 cpu
2、抢占式策略
依赖硬件的定时中断机制，操作系统初始化时向硬件注册中断回调，以便当硬件发生中断时，硬件会将 cpu 的处理权交还给操作系统。
这样，操作系统就可以通过中断回调的方式来获取 cpu 的调度权。
最简单的调度：FIFO
说到最简单的调度策略，那肯定是先进先出（FIFO）策略了。
FIFO 的意思就是先来的任务先处理，等当前任务执行完成后，再执行下一个任务。
他的优点就是简单明了，缺点也很明显，就是正在执行中的任务会阻塞后面的任务。
特别当有多个任务时：
- 执行时间较长的任务可能会阻塞执行时间较短的任务
- 优先级低的任务可能会阻塞优先级高的任务
最短任务优先：SJF
SJF 全称 Short Job First，就是执行时间短的任务优先执行。
他相较于 FIFO 来说，弥补了一部分调度策略的缺陷。
当一批任务到来时，可以优先处理执行时间较短的任务。
但是当执行时间较长的任务正在被处理，此时再投放执行时间较短的任务，这些短任务仍然会被阻塞。
最短时间优先完成：STCF
STCF 全称 Shortest Time-to-Completion First，就是当运行时间较短的任务达到时，会中断当前任务，转而执行这批短时间任务。
很显然，这是 SJF 的一种优化。
在这里我们其实可以看到，不管是 FIFO、SJF 还是 STCF，这些调度策略的本质都是先执行一个任务，再执行下一个任务。
当完成一个短任务所需要的时间也很长时，这个时候，对于每一个任务，调度执行的时间将不可避免的被延长。
基于时间片的轮询
既然，这种完成一个任务再完成下一个任务的调度策略这么不友好，那么我们就让这些任务一起执行。
原理也比较简单：
1、给每个任务分配一个时间片，时间片表示该任务被 cpu 调度执行的时间。
2、当时间片的调度时间结束后，cpu 会中断该任务，切换到下一个任务。
3、通过 round robin 轮询的策略，对每一个任务执行调度。
多级反馈队列：MLFQ
MLFQ 全称 Multi-Level Feedback Queue
该策略综合考虑了优先级和轮询的特点，此时调度策略类似：
1、任务优先级高的任务先执行
2、优先级相同的任务轮询调度执行
linux完全公平调度：CFS
CFS 全称 Completely Fair Scheduler
CFS 希望将 cpu 公平的平均分到每个任务。为了实现平均能力， CFS 引入了计数的概念。
每个任务都维护有一个 vruntime 的值，用来表示调度执行的时间，每次调度执行后，该值都会加上此次调度时间的值。
每一次调度，操作系统会选择 vruntime 值最小的优先调度。
在 CFS 种，调度执行时间片不是固定的，linux 提供了可配参数 sched_latency，调度时间片就是：time_slice = sched_latency / n，
这里的 n 就是任务数，即任务数越多，时间片越小。
除此之外，linux 也提供了权重来标记任务的优先级，优先级高的任务将分配有更多的执行时间片。
linux 提供了权重机制，用于标记任务的优先级。
优先级高的任务，将被分配更多的执行时间片。
在权重机制下，也不再是取 vruntime 值最小的优先调度了，会有新的算法引入权重值。
在文中已经说明，CFS 调度时会选择 vruntime 最小的值，此时为了性能，采用的是红黑树来存储 vruntime 数据。
红黑树在插入和删除时，操作复杂度为 log(n)
而有序链表的操作复杂度为 O(n)
本文作者: Czasg
版权声明: 转载请注明出处哦~👮