6.1 进程调度概念
进程调度
在合适的时候以一定策略选择一个就绪进程运行
进程调度的目标
- 响应速度尽可能快
- 进程处理的时间尽可能短
- 系统吞吐量尽可能大
- 资源利用率尽可能高
- 对所有进程要公平
- 避免饥饿
- 避免死锁
上述部分原则之间存在自相矛盾
进程调度的目标（两个可以量化的衡量指标）
周转时间/平均周转时间
周转时间：进程提交给计算机到最终完成花费的时间（\(t\)）
\(t_s\)：进程的提交时间（start）
\(t_c\)：进程的完成时间（complete）
意义：说明进程在系统中停留时间长短
平均周转时间：
意义：平均周转时间越短，意味着这些进程在系统内停留的时间越短，因而系统的吞吐量也就越大，资源利用率也越高
带权周转时间/平均带权周转时间
带权周转时间：
\(t\)：进程的周转时间
\(t_r\)：进程的运行时间（run）
意义：进程在系统相对停留时间、
平均带权周转时间：
6.2 典型调度算法
1. 先来先服务调度（First Come First Serve）
算法
按照作业进入系统的时间先后来挑选作业，先进入系统的作业优先被运行。
特点
- 容易实现，效率不高
- 只考虑作业的等候时间，而没考虑运行时间的长短。因此一个晚来但是很短的作业可能需要等待很长时间才能被运行，因为本算法不利于短作业。
2. 短作业优先调度算法（Short Job First）
算法
参考运行时间，选取运行时间最短的作业投入运行
特点
- 易于实现，效率不高
- 忽略了作业等待时间，一个早来但是很长的作业将会在很长时间得不到调度，易出现资源“饥饿”的现象。
3. 响应比高者优先调度算法
响应比定义
作业的响应时间和运行时间的比值
算法
计算每个作业的响应比，选择响应比最高的作业优先投入运行。
特点
- \(响应比=1+\frac{等待时间}{运行时间}\)
- 如果作业的等待时间相同，则运行时间越短的作业，其响应比越高，因此越容易被调度，因而有利于短作业。
- 如果作业的运行时间相同，则等待时间越长的作业，其响应比越高，因此越容易被调度。因而有利于等候长的作业。
- 对于运行时间长的作业，其优先级可以随等候时间的增加而提高，当其等待足够久的时候，也有可能获得CPU。
4. 优先数调度算法
算法
- 根据进程优先数，把CPU分配给最高的进程
- 进程优先数=静态优先数+动态优先数
静态优先数
进程创建时确立，在整个进程运行期间不再改变
动态优先数
动态优先数再进程运行期间可以改变
静态优先数的确立
- 基于进程所需资源的多少
- 基于程序运行时间的长短
- 基于进程的类型（IO/CPU，前台/后台，核心/用户）
动态优先数的确立
- 当使用CPU超过一定时常时
- 当进行I/O操作后
- 当进程等待超过一定时长时
5. 循环轮转调度法（Round-Robin）
概念
- 把所有就绪进程按先进先出的原则拍成队列。新来的进程加到队列末尾。
- 进程以时间片q为单位轮流使用CPU。刚刚运行一个时间片的进程排到队列末尾，等候下一轮运行。
- 队列逻辑上是环形的。
优点：
- 公平性：每个就绪进程有平等机会获得CPU
- 交互性：每个进程等待\((N-1)\cdot q\)的时间就可以重新获得CPU
时间片q的大小
- 如果q太大
- 交互性差
- 甚至退化为FCFS调度算法
- 如果q太小
- 进程切换频繁，系统开销增加
改进
- 时间片的大小可变
- 组织多个就绪队列
6.3 Linux进程调度
Linux进程类型
普通进程
- 采用动态优先级来调度
- 调度程序周期性地修改优先级（避免饥饿）
实时进程
- 采用静态优先级来调度
- 由用户预先指定，以后不会改变
Linux进程的优先级
静态优先级
- 进程创建时指定或由用户修改
动态优先级
- 在进程运行期间可以按照调度策略改变
- 非实时进程采用动态优先级，由调度程序计算
- 只要进程占用CPU，优先级就随着时间流逝而不断减小
- task_struct的counter表示动态优先级
调度策略（结合task_struct）
task_struct->policy指明进程调度策略
实时进程
- SCHED_FIFO（先进先出）
- 当前实时进程一直占用CPU直至退出或阻塞或被抢占
- 阻塞后再就绪时被添加到同优先级队列的末尾
- SCHED_RR（时间片轮转）
- 与其他实时进程以Round-Robin方式共同使用CPU
- 确保同优先级的多个进程能共享CPU
非实时进程
- SCHED_OTHER（动态优先级）
- counter成员表示动态优先级
调度策略的改变
- 系统调用sched_setscheduler()来改变调度策略
- 实时进程的子孙进程也是实时进程
进程调度的依据
| task_struct | |
|---|---|
| policy | 进程的调度策略，用来区分实时进程和普通进程；SCHED_OTHER(0)||SCHED_FIFO(1)||SCHED_RR(2) |
| priority | 进程（包括实时和普通）的静态优先级 |
| rt_priority | 实时进程特有的优先级：rt_priority+1000 |
| counter | 进程能够连续运行的时间 |
动态优先级与counter
counter值的含义
-
进程能连续运行的时间，单位是时钟滴答tick
时钟中断周期tick为10ms；若counter=60，则能连续运行600ms。
-
较高优先级的进程一般counter较大。
-
一般把counter看作动态优先级。
counter的初值与priority有关
- 普通进程创建时counter的初值为 priority的值。
counter的改变
- 时钟中断tick时，当前进程的counter减1，直到为0被阻塞。
子进程新建时的counter
新建子进程counter从父进程的时间片counter中继承一半
p->counter = (current->counter + 1) >> 1;
current->counter >>= 1;
防止用户无限制地创建后代进程而长期占有CPU资源
调度时机
-
中断处理过程中直接调用schedule()
- 时钟中断、I/O中断、系统调用和异常
- 内核被动调度的情形
-
中断处理过程返回用户态时直接调用schedule()
- 必须根据need_resched标记
-
内核线程可直接调用schedule()进行进程切换
- 内核主动调度的情形
-
用户态进程只能通过陷入内核后在中断处理过程中被动调度
- 必须根据need_resched标记
进程切换
概念
- 内核挂起当前CPU上的进程并恢复之前挂起的某个进程
- 任务切换、上下文切换
与中断上下文的切换有去边
- 中断前后在同一进程上下文中，只是用户态转向内核态执行
进程上下文包含了进程执行需要的所有信息
- 用户地址空间：包括程序代码，数据，用户堆栈等
- 控制信息：进程描述符，内核堆栈等
- 硬件上下文（注意中断也要保存硬件上下文，只是保存的方法不同）
进程调度和切换的流程
schedule()函数
-
选择新进程
next = pick_next_task(rq, prev); //进程调度算法 -
调用宏context_switch (rq, prev, next)切换进程上下文
- prev: 当前进程，next：被调度的新进程
- 调用switch_to(prev, next)切换上下文
两个进程A，B切换的基本过程
-
正在运行用户态进程A
-
发生中断（譬如时钟中断）
- 保存current当前进程的cs:eip/esp/eflags到内核堆栈
- 从内核堆栈装入ISR中断服务例程的cs:eip和ss:esp
-
SAVE_ALL //保存现场，已进入内核中断处理过程
-
中断处理过程中或中断返回前调用了 schedule()
- 其中的switch_to做了进程上下文切换
-
运行用户态进程B (B曾经通过以上步骤被切换出去过）
-
RESTORE_ALL //恢复现场
-
iret //中断返回 pop cs:eip/ss:esp/eflags
-
继续运行用户态进程B