1. 进程分类
进程分为三类：
- 交互式进程
进程与用户交互，平均延迟需要很低，例如键盘和鼠标操作。因为若延迟较高，用户会明显感到系统反应迟钝； - 批处理进程
这种进程不必与用户交互，经常在后台运行。例如科学计算机程序语言的编译； - 实时进程
有很强的调度需求，需要有很短的相应时间。典型的如音视频程序；
在Linux中，调度程序可以明确的确认实时进程(如通过静态优先级)，但没有办法区分交互式进程和批处理进程，Linux2.6使用的方式是基于历史行为的启发式算法。
2. 进程运行时机
Linux进程是抢占式的，若进程进入TASK_RUNNING状态后，
- 内核会检测该进程的动态优先级是否大于current进程，若是则调度程序将中断current进程，选择另一进程运行；
- 若当前进程的时间片到期也可以被抢占。
此时当前进程的TIF_NEED_RESCHED标志被设置，时钟中断处理程序终止时调度程序会调度。
3. 调度算法类型
- SCHED_FIFO: 先进先出，实时进程
- SCHED_RR： 时间片轮转，实时进程；
- SCHED_NORMAL：普通分时进程
4. 进程调度
1. 普通进程调度
每个普通进程有自己的静态优先级，范围是[100, 140)，静态优先级用于计算动态优先级等参数，本质上决定了进程的基本时间片。
1）基本时间片
基本时间片公式如下：
屏幕快照 2019-05-22 23.32.05.png
静态优先级越高，其时间片越长。
通常来说较高优先级能获得更长的CPU时间片。
屏幕快照 2019-05-22 23.33.43.png
2）动态优先级和平均睡眠时间
动态优先级计算公式如下：
动态优先级 = max(100, min(静态优先级-bonus+5, 139))
bonus是惩罚值，范围为0到10，值小于5表示惩罚，大于则表示奖赏，同时该值与进程的平均睡眠时间有关。
平均睡眠时间不是过去时间的平均值，而是进程在睡眠状态下的平均纳秒数，进程在运行过程中平均睡眠时间递减。平均睡眠时间小于1s。
平均睡眠时间-bonus
平均睡眠时间也被用于确定一个进程是否为交互式进程的依据：
动态优先级 <= 3*静态优先级/4 + 28
或
bonus-5 >= 静态优先级/4 - 28
上面的公式用于确认进程是否为交互式进程，其中静态优先级/4-28为交互式值。从公式中看出，高优先级进程比低优先级进程更容易成为交互式进程。例如静态优先级为100的进程，若其睡眠时间大于200ms，责备认定为交互式进程。
进程也分为活动进程和过期进程。因为即使高优先级进程获得较高时间片，也不应该让低优先级进程饥饿，当一个进程用完时间片后，应该让低优先级进程投入运行。实现这种机制的方式是调度程序维持了两个集合：
- 活动进程
这些进程还未用完时间片，允许它们运行； - 过期进程
这些进程已用完时间片，禁止运行，直到所有活动进程过期再重新分配时间片。
为保持交互式进程的性能，有以下策略：
- 用完时间片的批处理进程总是变成过期进程；
- 用完时间片的交互式进程通过立即重新分配时间片而总是活动进程
- 若最老的过期进程等待很长时间，或过期进程静态优先级大于交互式进程，则将交互式进程移入过期进程。
2. 实时进程
实时进程优先级从1到99，同时实时进程总是活动进程。实时进程仅在以下情况下被取代：
- 被另一个更高优先级进程抢占；
- 阻塞进入睡眠；
- 进程停止或被杀死；
- 调用sched_yield()放弃CPU；
- 进程是SCHED_RR且用完时间片。
