调度程序负责决定哪个进程投入运行，何时运行以及运行多长时间
最大限度提供资源利用率，并且保证公平性
主要内容
- 多任务
1. 多任务
多任务操作系统——并发执行多个进程
多核处理器——真正同时并行地运行
- 非抢占式：需要进程让步
- 抢占式任务
抢占式任务下，由调度程序决定什么时候停止一个进程的运行，这个强制的挂起动作就叫抢占。
进程在被抢占之前能运行的时间是分配好的，叫进程的时间片。
2. Linux的进程调度
- 从O(1)调度：对响应时间敏感的交互进程，服务不佳
- 后续替代：CFS（完全公平调度算法）
3. 策略
- I/O密集型和CPU密集型进程
- I/O密集型： 进程的大部分时间用来提交I/O请求或等待I/O请求，最后通常会阻塞（等待更多的I/O请求）
- CPU密集型：时间大多用在执行代码上，对此调度策略：降低频率，延长时间
- 调度策略的权衡：响应时间短 VS 最大系统利用率（高吞吐量）
进程优先级
Linux采用了两种不同的优先级范围，第一种是nice值（-2019），代表时间片的比例，低nice（高优先级）的进程可以获得更多处理器时间，第二种是实时优先级（099），越高的实时优先级数值意味着进程优先级越高。时间片
表明进程在被抢占前所能持续运行的时间。
CFS调度器并没有直接分配时间片到进程，它是将处理器的使用比例分给了进程。进程所获得的处理器时间其实是和系统负载密切相关的，还受nice值的影响。调度策略的活动
文字编辑程序和视频编码程序，两者的处理器使用比例都是50%，但是文本编辑程序运行时间要短的多，这种情况下，为了兑现所有进程公平分享处理器的承诺，它会立刻抢占视频解码程序。
4. Linux调度算法
- 调度器类
linux调度器是以模块方式提供的，允许不同类型的进程有针对地选择调度算法 - 为了避免将nice值直接映射到时间片的不便之处（分配绝对的时间片引发的固定的切换频率），CFS摈弃了时间片，而是分配给进程一个处理器使用比重
- 公平调度
CFS的核心理念，每个进程都按照权重在全部可运行进程中所占比例的“时间片”来运行
CFS为调度周期设立了一个近似目标：目标延迟，同时还有最小粒度
绝对的nice值不再影响调度决策，只有相对值才会影响处理器时间的分配比例
5. Linux调度的实现
- 时间记账
CFS使用调度器实体结构struct_sched_entity来追踪进程运行记账 - 虚拟实时
CFS使用vruntime变量来存放进程的虚拟运行时间，该运行时间是实际运行时间进行加权运算后的结果。
vruntime可以通过update_curr()更新 - 进程选择
CFS选择具有最小vruntime的任务，使用红黑树来组织可运行进程队列(注意是可运行进程，如果进程阻塞，要从红黑树中删除） - 调度器入口
进程调度的入口点是函数schedule()，找一个最高优先级的调度类，选择最高优先级的进程 - 睡眠和唤醒
休眠（被阻塞）的进程，如等待文件I/O
- 休眠通过等待队列进行处理
-
唤醒操作通过wake_up进行
休眠和唤醒.jpg
6. 抢占和上下文切换
上下文切换，又就是从一个可执行进程切换到另一个可执行进程，每当一个新的进程被选出来准备投入运行的时候，schedule()就会调用该函数:
- 调用switch_mm()，该函数负责把虚拟内存从上一个进程映射到新进程中
- 调用switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态，这包括保存、恢复栈信息和寄存器信息，还有其他任何与体系结构相关的状态信息，都必须以每个进程为对象进行管理和保存。
内核提供了一个need_resched标志来表明是否需要重新执行一次调度
- 用户抢占
内核无论是在中断处理程序还是系统调用后返回，都会减产need_resched标志，如果被设置了，内核会选择一个其他（更合适的）进程投入运行 - 内核抢占
只要重新调度室安全的（没有持有锁），内核就可以进行抢占
每个进程的thread_info引入preempt_count计数器
7. 实时调度策略
实时调度策略
- SCHED_FIFO，简单的先入先出，不使用时间片，只会被更高优先级的抢占
- SCHED_RR，耗尽时间片之后就不再继续执行，带有时间片
普通非实时
SCHED_NORMAL
8. 与调度相关的系统调用
- 设置和获取进程的调度策略和实时优先级
- 设置和获取进程的实时优先级
- 强制的处理器绑定机制
- 放弃处理器时间
