操作系统原理复习 第六章 进程调度

进程调度（schedule）^[1]

定义

在一个队列中，按某种策略选择一个最合适个体。

分类

1. 长程调度/宏观调度/作业调度

2. 中程调度/交换调度

3. 短程调度/进程调度

4. I/O 调度/设备调度

在这里我们主要讨论的是短程调度（一直将其称为进程调度）。在合适的时候以一定策略选择一个就绪进程运行.

目标

周转时间/平均周转时间

周转时间，即进程提交给计算机到完成所花费的时间（t），周转时间说明了进程在系统中停留时间的长短。

$$t = t_c - t_s$$

$t_s$------进程的提交时间（Start）
$t_c$------进程的完成时间（Complete）

平均周转时间，平均周转时间越短，意味着这些进程在系统内停留的时间越短，因而系统吞吐量也就越大，资源利用率也越高。

$$t = (t_1 + t_2 + ⋯ + t_n)/n$$

带权周转时间/平均带权周转时间

带权周转时间 w，说明了进程在系统中的相对停留时间。

$$w = 周转时间 /进程运行时间 = t / t_r$$

$t$：进程的周转时间
$t_r$ ：进程的运行时间（run）

平均带权周转时间:

$$w = (w_1 + w_2 + ⋯ + w_n)/ n$$

进程调度算法

先来先服务调度（First Come First Serve）

按照作业进入系统的时间先后次序来挑选作业。先进入系统的作业优先被运行。

• 容易实现，效率不高

• 只考虑作业的等候时间，而没考虑运行时间的长短。因此一个晚来但是很短的作业可能需要等待很长时间才能被运行，因而本算法不利于短作业。

短作业优先调度算法（Short Job First）

参考运行时间，选取时间最短的作业投入运行。

• 易于实现，效率不高

• 忽视了作业等待时间，一个早来但是很长的作业将会在很长时间得不到调度，易出现资源"饥饿"的现象。

响应比高者优先调度算法

调度作业时计算作业列表中每个作业的响应比，选择响应比最高的作业优先投入运行。

响应比定义：作业的响应时间和与运行时间的比值

响应比 = 响应时间/运行时间 =（等待时间 + 运行时间）/运行时间 = 1 +等待时间 / 运行时间。

• 有利于短作业

• 有利于等候已久的作业。兼顾长作业

优先数调度算法

根据进程优先数，把 CPU 分配给最高的进程。

进程优先数 = 静态优先数 + 动态优先数

静态优先数在进程创建时确定，在整个进程运行期间不再改变。

• 静态优先数的确定基于：

  1. 进程所需的资源多少（不一定）

  2. 基于程序运行时间的长短（长的进程静态优先数应该越小）

  3. 基于进程的类型（IO/CPU 中偏向 IO 的进程交互性强，优先数高；

• 前台/后台中偏向前台的进程对于用户体验比较重要，优先数高，核心/用户中用户态进程优先数更高。

动态优先数在进程运行期间可以改变：

• 当使用 CPU 超过一定时长时：适当降低

• 当进程等待时间超过一定时长时：适当提高

• 当进行 I/O 操作后：适当提高

循环轮转调度法（ROUND-ROBIN）

把所有就绪进程按先进先出的原则排成队列。新来进程加到队列末尾。进程以时间片q 为单位轮流使用
CPU。刚刚运行了一个时间片的进程排到队列末尾，等候下一轮调度。队列逻辑上是环形的。

优点：

1. 公平性：每个就绪进程有平等机会获得 CPU

2. 交互性：每个进程等待 (N-1)* q 的时间就可以重新获得 CPU

时间片 q 的大小：如果 q 太大，交互性差。甚至退化为 FCFS 调度算法。如果q 太小，进程切换频繁，系统开销增加。

改进：时间片的大小可变 (可变时间片轮转调度法)，组织多个就绪队列（多重时间片循环轮转）

进程调度方式

当一进程正在 CPU 上运行时，若有更高优先级的进程需要运行，系统如何分配CPU。

非抢占方式

让正在运行的进程继续执行，直到该进程完成或发生某事件而进入"完成"或"阻塞"状态时，才把CPU 分配给新来的更高优先级的进程。

抢占方式

当更高优先级的进程来到时，便暂停正在运行的进程，立即把 CPU分配给新来的优先级更高的进程。

Linux 调度机制

宏观评价

基于优先级调度。支持普通进程，也支持实时进程；实时进程优先于普通进程；普通进程公平使用CPU 时间。

关键参量 priority, counter, rt_priority, policy

以下变量均定义在 task_struck 结构体中。（以 Linux0.11 为例）

• priority：进程（包括实时和普通）的静态优先级

• counter：进程能连续运行的时间（动态优先级）

  • 其表示的是当前一轮调度中，进程能连续运行的时间片数量。
  • 较高优先级的进程有更大的counter， counter 初值 = priority。
  • counter的改变：时钟中断服务程序
  • 在新的一轮调度开始时：counter = priority。
  • policy 指明进程使用何种调度策略。

• rt_priority ：实时进程特有的优先级: rt_priority+1000

nice 指令

Linux nice命令以更改过的优先序来执行程序，如果未指定程序，则会印出目前的排程优先序。

nice -n 数字进程

nice 范围：-20（最高）～19（最低)
默认 nice = 0

普通用户：可以调整自己进程，而 nice 范围 [ 0, 19 ]。
Root用户：可以调整任何进程，而 nice 范围 [-20, 19]。

调度函数的实现

调度函数 schedule 在可运行队列中找到一个进程给它分配 CPU。

调用时机：

• 直接调度：时钟中断，即 do_timer()，当资源无法满足被阻塞时，sleep_on()。

• 间接调度/松散调度：进程从内核态返回到用户态前。

调度时钟 do_timer() 函数

时钟中断处理函数

调度函数 schedule

1. 选择进程，扫描可运行队列，选择一个合适进程

2. 切换进程，把当前进程放到适当的等待队列里。调用 schedule()，让新的进程运行。

参考

1. 感谢hhf同学的笔记！orz!!! ↩