Chapter 6 进程调度
6.1 调度概念
6.1.1 调度的定义
调度广义上是指在一个队列中，按照某种策略从中选择一个最合适的个体。
6.1.2 调度的分类
按照调度层次和原因可分为长程调度、中程调度、短程调度和I/O调度。
- 长程调度是从多个作业构成的后备作业队列中，根据调度算法选取一个合适的作业调入内存。当一个作业结束退出系统时，需要执行长程调度从磁盘上选择一个后备作业投入执行。
- 中程调度主要是短期调节系统的负荷，对象为进程，将进程在内存和磁盘交换空间之间进行交换。这样做可能因为内存资源紧张需要挂起一些进程，另外是为系统减少并发性而降低系统开销。
- 短程调度即进程调度，决定哪一个进程将被执行、哪些进程将处于就绪状态。即进程在运行、就绪、阻塞这3个状态之间的转换调度由短程调度完成。其目的是让整个队列被调度的延迟最小，优化系统效率。
- I/O调度为当I/O设备可用时调度相应的等待队列中的进程使用该设备。属于设备管理模块的功能，确定一个合适的顺序来执行来自进程的I/O请求。可以改善系统整体性能。
6.2 调度的原则
6.2.1 调度的宏观原则
用户期望的调度原则应该包括：
- 响应速度尽可能快
- 进程处理时间尽可能短
- 系统吞吐量尽可能大
- 资源利用率尽可能高
- 对所有进程公平
- 避免饥饿
- 避免死锁
但上面几条原则本身就存在矛盾，操作系统一般采取折中的方式采纳其中的部分原则。
6.2.2 调度的时间性能测度
周转时间和平均周转时间：周转时间指作业从提交到计算机开始到给出结果花费的时间，包括在后备队列中等待的时间、对应进程在内存就绪队列中等待时间、对应进程在CPU上真正运行的时间、对应进程等待I/O操作完成的阻塞时间等。表示周转时间，则$$t=t_c-t_s$$其中表示作业的提交时刻，表示作业的完成时刻，也可以计算为$$t=t_w+t_r$$其中表示作业等待时间，表示作业运行时间。周转时间越短越好。
平均周转时间指一批作业周转时间的平均值。
带权周转时间和平均带权周转时间：考虑作业大小对周转时间的影响，带权周转时间指作业周转时间和执行时间的比值：$$w=\frac{t}{t_r}$$其中为进程周转时间，为进程执行时间。
带权周转时间的意义是表明作业在系统中的相对停留时间，消除因为作业大小不同而导致的绝对周转时间缺少比较价值的问题。
平均带权周转时间指一组作业中带权周转时间的平均值。
6.3 进程调度过程
6.3.1 进程调度的功能
- 记录和管理全部进程的工作状态
- 按照调度策略选择合适的进程
- 进行进程上下文切换
6.3.2 进程调度的时机
主要的调度时机有：
- 时钟中断
- I/O中断
- 异常
- 进程结束
- 系统调用
- 主动调度
6.3 进程调度的方式
进程调度的方式可以分为非抢占方式和抢占方式。区别为当有优先级更高的进程到来时，进程调度程序是否会将当前进程立即切出而切入新进程。抢占方式将首先执行高优先级进程，将低优先级进程暂时挂起；非抢占方式将低优先级进程执行完再去执行高优先级进程。
6.4 作业调度算法
6.4.1 先来先服务调度算法
FCFS调度算法容易理解，容易实现，但是效率不高。该算法只考虑了作业的等待时间而没有考虑作业的执行时间，因此算法不利于晚到但是短的作业。
6.4.2 短作业优先调度算法
SJF算法参考运行时间从后备作业中选择运行时间最短的作业优先投入运行。易于实现，但不利于早到却很长的作业。
6.4.3 响应比高者优先调度算法
RRHF算法考虑作业的响应比。响应比=响应时间/运行时间=1+等待时间/运行时间。该调度算法有利于短作业，对于等待时间相同的作业，短作业的响应比高于长作业。该算法有利于等待已久的作业，等待时间越长越容易被调度。
6.5 进程调度算法
6.5.1 优先数高者优先调度算法
HPF调度算法根据进程的优先数将CPU分配给优先数最高的进程。优先数是一个人为定义的参数，包括静态优先数和动态优先数。静态优先数在进程创建时确定，动态优先数在进程运行期间根据环境动态指定。
静态优先数的确定需要考虑以下因素：
- 进程需要资源的多少，一般进程申请的资源越多，优先数越低，但如果涉及的I/O设备与人机交互有关则可以获得较高的优先数以提升用户体验。
- 进程运行时间长短，一般较大的进程运行时间较长，可以分配较低的优先数。
- 进程的类型，偏I/O的进程可以比偏CPU的进程获得更高的优先数，前台进程可以比后台进程获得更高的优先数，普通用户进程可以比核心进程获得更高的优先数等。
动态优先数的确定需要考虑以下因素：
- 当使用CPU超过一定时长时，可以考虑降低其优先数。
- 当进程等待时间超过一定时长时，可以考虑提高其优先数。
- 当进行I/O操作时，可以提高其优先数。
在Linux系统中，普通用户的进程可以将进程数设置为0~19，内核进程可以设置进程数为-20~19。
缺点：当低优先级进程占用高优先级进程资源时反而需要高优先级进程等待低优先级进程完成，这被称为优先级反转。解决方案有：临时设置高优先级、继承高优先级、临时使用中断禁止。
6.5.2 时间片轮转调度算法
时间片轮转调度算法将所有就绪进程排成一个队列，新来进程加到队列末尾，进程以时间片q为单位轮流使用CPU，刚使用完CPU的进程排到队列末尾，队列在逻辑上是环形的。
该算法需要合理选择时间片q的大小，时间片太短则会导致进程切换频繁，增加系统开销，时间片太长则可能会退化为FCFS算法。
6.5.3 多重时间片轮转调度算法
这是对时间片轮转调度算法的一种改进，设置多个就绪队列，每一个队列对应一个优先级，每个就绪队列使用的时间片大小不同，高优先级的时间片短而低优先级的时间片长。通常优先级每提高一级时间片缩短一半。这样可以提高系统吞吐量，缩短平均周转时间。
6.6 Linux进程调度
6.6.1 Linux调度机制
Linux进程调度的基本特点：
- 基于优先级调度，优先级由静态优先级和动态优先级构成
- 支持普通进程和实时进程
- 实时进程优先于普通进程
- 普通进程公平使用CPU时间
Linux进程控制块task_struct中的priority成员指的是进程的静态优先级，counter成员指的是动态优先级，还有一个nice值，可以通过修改nice值修改进程的静态优先级。nice值的设置范围为-20~19。静态优先级表示该进程被允许连续运行的最长时间，实时进程使用静态优先级调度。counter指的是该进程在当前时间片结束后还能够连续运行多少个时间片，其值越大优先级越高。在新一轮调度开始时，counter=priority，时钟中断服务程序执行后其值自减1，当所有进程的counter都减到0时开始新一轮的调度。
rt_priority成员表示实时进程特有的优先级，policy表示进程的调度策略，用于区分实时进程和普通进程，可选SCHED_OTHER、SCHED_FIFO、SCHED_RR三种。
Linux的调度函数为schedule函数，其在可运行队列中选择一个具有最高优先数的进程并将CPU切换给它。
例题
本章的例题大多与计算有关，即计算调度时间。
例-1：下面是各个任务的到达时间和任务长度，试写出3种作业调度算法下这些任务的开始时间，以及各自的周转时间、平均周转时间、带权周转时间和平均带权周转时间。
对于FCFS算法：
| 任务 | 到达时间 | 持续时间 | 开始时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|
| A | 10 | 30 | 60 | 80 | 2.33 |
| B | 0 | 20 | 0 | 20 | 1 |
| C | 0 | 40 | 20 | 60 | 1.5 |
| D | 60 | 10 | 90 | 40 | 4 |
该算法的平均周转时间为50，平均带权周转时间为2.21。
对于SJF算法：
| 任务 | 到达时间 | 持续时间 | 开始时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|
| A | 10 | 30 | 20 | 40 | 1.33 |
| B | 0 | 20 | 0 | 20 | 1 |
| C | 0 | 40 | 50 | 90 | 2.25 |
| D | 60 | 10 | 90 | 40 | 4 |
该算法的平均周转时间为47.5，平均带权周转时间为2.15。
对于RRHF算法：
| 任务 | 到达时间 | 持续时间 | 开始时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|
| A | 10 | 30 | 20 | 40 | 1.33 |
| B | 0 | 20 | 0 | 20 | 1 |
| C | 0 | 40 | 50 | 90 | 2.25 |
| D | 60 | 10 | 90 | 40 | 4 |
该算法的平均周转时间为47.5，平均带权周转时间为2.15。