---
title: Process Scheduling in OS
date: 2024-03-29
excerpt: 进程调度
tags:
  - OS
  - Concurrency
  - Parallelism
  - Thread
  - Process
updated: 2026-05-08 22:10:51
---
## 引起调度的事件

### 进程主动放弃 CPU

1. **进程正常终止**：进程完成所有任务后结束运行（如程序执行 `exit()` 系统调用），此时 CPU 空闲，需从就绪队列中选择下一个进程运行。
2. **进程阻塞**：进程因需要等待某类资源（如 I/O 操作、信号量、锁）而进入阻塞状态，主动释放 CPU
3. **进程主动礼让**：部分系统支持进程通过 `yield()` 等系统调用主动放弃 CPU

### 系统强制剥夺 CPU

1. **高优先级进程到达**：新进程进入就绪队列，且优先级高于当前运行进程
2. **时间片耗尽**：时间片轮转算法中，当前进程用完时间片（如10ms）→强制放回就绪队列末尾，触发调度。
### 硬件中断

1. **时钟中断**：操作系统通过定时器周期性产生时钟中断，内核在中断处理程序中检查是否需要进行调度
2. **I/O 中断**：当 I/O 设备完成数据传输后，会产生中断信号，内核在中断处理程序中检查是否有阻塞进程可以唤醒并调度

## 调度算法评价指标

| 指标                        | 描述                                                                           |
| --------------------------- | ------------------------------------------------------------------------------ |
| 周转时间<br>Turnaround Time | 进程从 “提交” 到 “完成” 的总时间（包括等待时间、CPU 执行时间、I/O 时间）       |
| 响应时间<br>Responsive Time | 进程从 “提交请求” 到 “首次获得 CPU 响应” 的时间                                |
| 吞吐量<br>Throughput        | 在单位时间内，系统所完成的作业数                                               |
| CPU利用率                   | $\frac{\text{CPU有效工作时间}}{\text{CPU有效工作时间}+\text{CPU空闲等待时间}}$ |
| 各类资源利用率              | 如内存、外存、I/O 设备等的利用率                                               |

## 常见调度算法

### FCFS, SJF

批处理系统以 “提升吞吐量、降低平均周转时间” 为核心目标，进程多为后台任务（无实时交互需求），常用以下算法：

- *FCFS, First Come First Served*: 在 RQ (Ready Queue)，按进程进入队列的次序进行调度，先到者先服务
- *SJF, Shortest Job First*: 选择估计运行时间最短的作业进行调度

### PS, RR, MLFQ

> [!note] Preemptive & Non-preemptive
>
> 1. **非抢占**：进程开始后，除非主动放弃，否则其他进程只能排队等它让出CPU
> 2. **抢占**：内核调度程序将原进程中断，并将CPU分配给其他进程

交互式系统（如 Windows、Linux 桌面）以 “缩短响应时间、保证用户体验” 为核心，需频繁切换进程，常用以下抢占式算法：

- *PS,Priority Scheduling*: 优先权[^1]调度算法
    - HRRN, High Response Ratio Next:是介于 FCFS 和 SJF 之间的一种折中算法，使用响应比[^2]作为优先权判断依据。
- *RR,Round Robin*: 将 CPU 分配给就绪队首进程。进程执行一个时间片后，计时器中断会停止该进程，并将其移至队列末尾，然后将 CPU 分配给新的队首进程，再次执行一个时间片。
- *MLQ,MultiLevel Queue*:将系统中运行的进程根据其特性划分为不同的就绪队列，并为每个队列分配不同的调度算法
    - *MLFQ,MultiLevel Feedback Queue*:为各个队列赋予不同的优先级队列，规定高优先级队列时间片小。一个进程进入内存后，首先将它放入第一队列的末尾，轮到该进程执行时，如进程一次时间片没执行完，就降至下一级队列。OS优先调度高优先级队列中的进程，仅当 *RQ₀* 空闲时才调度 *RQ₁* 队列进程，以此类推

### EDF, LLF
- *EDF,Earliest Deadline First*: 根据任务的截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。
- *LLF,Least Laxity First*: 按松弛度[^3]排序，松弛度值最小的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行；当有任务执行时，只有等待任务的松弛度值为 0 才会发生任务的调度，其他情况不发生调度。

[^1]: 指给进程排执行顺序的依据，可分为静态（创建时确定）和动态（随进程运行 / 等待时间变）；确定优先级的依据可以是：进程类型 (用户 / 系统)，资源要求 (I/O 密集 / CPU 密集)，进程重要性 (交互 / 批处理) etc.
[^2]: $R_p = \frac{\text{等待时间}+\text{预计运行时间}}{\text{预计运行时间}} = \frac{\text{响应时间}}{\text{预计运行时间}}$
[^3]: *Laxity = Deadline - RemainingServiceTime - CurrentTime*