Linux内核(cpu调度篇)
CPU调度
CPU的上下文切换
上下文切换的概念：如今的OS几乎都支持"同时"运行远大于CPU数量的任务，OS会将CPU轮流分配给它们使用。这就要求OS必须知道从哪里加载任务，以及加载后从哪里开始运行，而这些信息都保存在CPU的寄存器中，其中即将执行的下一条指令的地址被保存在程序计数器（PC）这一特殊寄存器上。我们将寄存器的这些信息称为CPU的上下文，也叫硬件上下文。
OS在切换运行任务时，将上一任务的上下文保存下来，并将即将运行的任务的上下文加载到CPU寄存器上的这一动作，被称为CPU上下文切换。
CPU上下文属于进程上下文的一部分，我们常说的进程上下文由如下两部分组成：
- 用户级上下文：包含进程的运行时堆栈、数据块、代码块等信息。
- 系统级上下文：包含进程标识信息、进程现场信息（CPU上下文）、进程控制信息等信息。
那具体的上下文切换过程是怎么样的呢？上下文信息保存在哪？
操作系统为每个进程分配虚拟内存时，会预留一部分仅内核可见的地址空间。当调度发生时，内核会将当前 CPU 的通用寄存器、程序计数器等现场信息写入该进程内核空间的特定数据结构中（如进程控制块 PCB 关联的内核栈）。
上下文切换的触发机制
- 协作式策略：用户程序通过执行系统调用或产生运算异常（如除零）将 CPU 控制权交还给内核。
- 抢占式策略：操作系统在初始化时向硬件注册中断处理回调，每隔固定时间周期，硬件产生的时钟中断会强制夺回 CPU 处理权并跳转至内核代码。
CPU调度：操作系统从就绪队列中挑选一个进程或者线程作为CPU将要运行的下一个进程或者线程。调度的程序是进程或者线程的内核函数（通过一些调度策略实现）
进行调度的时机：即操作系统什么时候执行进程或者线程的内核函数（调度程度），内核运行调度程序的的条件为一个进程从运行状态切换到等待状态或者当前进程被终结
抢占式和非抢占式调度策略
抢占式：内核可以在进程运行过程中，根据优先级或时间片等策略强制中断当前进程的执行，并将其拥有的 CPU 资源分配给另一个进程的机制。
非抢占式：一旦进程获得处理机便一直运行直至执行完毕或主动阻塞，操作系统内核在此期间不会强制剥夺其 CPU 控制权的调度方式。
注意这里的抢占式和非抢占式同前文的协作式和抢占式不同。此处指的是操作系统的调度策略，前文指的是上下文切换的触发机制，但是从逻辑上来说总体逻辑非常相似
调度算法评判标准
CPU使用率：指的是CPU处于忙状态的时间百分比
吞吐量：单位时间内完成的进程数量
周转时间：指从任务到达至任务完成之间的时间，计算方式为
等待时间：进程在就绪队列中等待的总时间
响应时间：指从任务到达至任务首次被调度的时间
算法目标：
响应时间目标：响应时间是操作系统计算延迟的指标，一个好的调度策略应该做到以下两点
- 减少响应时间，即使处理用户的输入请求，尽快将输出反馈给用户
- 减少平均响应时间的波动
吞吐量目标：吞吐量是操作系统计算带宽的重要指标，一个好的调度策略应该做到以下两点
- 增加吞吐量，减少开销（操作系统进行上下文切换的开销），保证系统的资源得到高效利用（CPU、I/O设备）
- 减少每个进程的等待时间
公平性目标：保证每个进程占用相同的CPU时间，保证每个进程的等待时间相同（即每一个进程都有可能得到操作系统的服务）
批处理调度
FCFS(First Come，First Served)：先来先服务
依据进程进入就绪状态队列的先后顺序排序，运行态进程进入等待或结束状态时，就绪队列中的下一个进程就会占用CPU执行，下面举一个先来先服务的示例，三个进程的处理时间分别为12，3，3，分两种进程到达顺序讨论（它们在接近同一时刻到达，但是也有先后顺序）
先来先服务是cpu调度算法最简单的实现方式，但是其缺点是，当一个长任务先到达时，后续的好几个短任务都必须要先等待长任务处理完之后再处理，平均等待时间过长，I/O资源和CPU资源利用率较低，CPU密集型会导致I/O设备闲置，I/O密集型会导致CPU闲置。
SJF(Shortest Job First)： 短作业优先算法
选择就绪队列中执行时间最短的进程占用CPU进行入运行状态，就绪队列按照预期的执行时间来排序（准确的进程运行时间在未执行结束前是不知道的，只能通过预判断来获取大致运行时间，然后排序）