概念

• 处理机调度用于决定哪个作业或进程获得处理机资源。狭义的进程调度通常是从就绪队列中选择一个进程投入运行。

分类

• 高级调度：又称作业调度，决定后备作业能否进入内存并成为进程。
• 中级调度：又称内存调度，常与进程挂起、换入换出有关。
• 低级调度：又称进程调度，决定就绪队列中的哪个进程获得 CPU。

调度方式

• 抢占式：运行中的进程可能被系统剥夺处理机。
• 非抢占式：进程一旦获得处理机，通常会运行到主动放弃或阻塞。

调度准则

• CPU 利用率。
• 系统吞吐量。
• 周转时间。
• 等待时间。
• 响应时间。

调度算法

常见调度算法包括先来先服务、短作业优先、优先级调度、高响应比优先、时间片轮转和多级反馈队列调度。

先来先服务 FCFS

FCFS，全称 First-Come, First-Served。

1. 核心机制：类似排队买票，先到先得。系统按照作业或进程到达就绪队列的先后顺序进行调度。
2. 教科书评价：通常为非抢占式。算法极其简单，对长作业有利，但对短作业不友好。容易产生护航效应，即一个长作业把后面一批短作业堵住，导致平均等待时间升高。

短作业优先 SJF

SJF，全称 Shortest Job First。

1. 核心机制：调度器每次从队列中挑出估计运行时间最短的作业或进程执行。
2. 教科书评价：可以是抢占式，也可以是非抢占式。抢占式也称最短剩余时间优先 SRTF。理论上，SJF 能达到最小的平均等待时间，但可能导致长作业长期得不到 CPU，产生饿死现象。

优先级调度

Priority Scheduling。

1. 核心机制：系统为每个进程分配一个优先级，调度时总是选择优先级最高的进程分配 CPU。
2. 教科书评价：分为抢占式和非抢占式。同样面临低优先级进程被饿死的风险。标准解决方案是引入老化技术：随着进程在队列中等待时间增加，系统逐渐提高它的优先级。

高响应比优先 HRRN

HRRN，全称 Highest Response Ratio Next。

1. 核心机制：每次调度前，系统动态计算队列中所有作业的响应比，并选择响应比最高的作业执行。

2. 响应比公式：

   $\frac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}}$

3. 教科书评价：属于非抢占式算法，是 FCFS 和 SJF 的折中。如果等待时间相同，短作业的响应比更高；如果是长作业，随着等待时间增加，响应比也会逐渐提升，从而缓解饿死问题。

时间片轮转 RR

RR，全称 Round Robin。

1. 核心机制：系统将 CPU 的运行时间划分为固定长度的时间片。就绪队列按先来后到排列，每个进程轮流执行一个时间片。时间片耗尽后，进程被强制剥夺 CPU，退回队列尾部重新排队。
2. 教科书评价：绝对的抢占式算法。它是专为分时系统设计的，能保证所有用户都能在较短时间内得到响应。核心难点在于时间片大小的设定：时间片太大，RR 会退化成 FCFS；时间片太小，CPU 会把大量时间消耗在进程上下文切换上。

完全公平调度器 CFS

CFS，全称 Completely Fair Scheduler。

1. 核心逻辑：抛弃传统固定时间片概念，目标是尽量公平。它在内核里维护一棵红黑树，记录每个普通进程享受 CPU 的虚拟运行时间 vruntime。
2. 优势：提高桌面交互体验和服务器吞吐量，是现代 Linux 调度的重要基础。

多级反馈队列 MLFQ

1. 核心机制：设置多个优先级队列，不同队列可以使用不同时间片。新进程通常先进入高优先级队列，运行时间较长的进程逐渐下移。
2. 特点：兼顾短作业响应和长作业推进，是分时系统中常见的综合调度思路。

相关计算公式

• 周转时间：

  $等待时间 + 运行时间$

• 带权周转时间：

  $\frac{周转时间}{服务时间}$

• 平均周转时间：

  $\frac{\sum\text{每个作业的周转时间}}{\text{作业个数}}$

• 平均带权周转时间：

  $\frac{\sum\text{每个作业的带权周转时间}}{\text{作业个数}}$

• 响应比：

  $\frac{\text{等待时间} + \text{服务时间}}{\text{服务时间}} = \frac{\text{周转时间}}{\text{服务时间}} = 1 + \frac{\text{等待时间}}{\text{服务时间}}$