Process Scheduling in OS
引起调度的事件
进程主动放弃 CPU
- 进程正常终止：进程完成所有任务后结束运行（如程序执行
exit()系统调用），此时 CPU 空闲，需从就绪队列中选择下一个进程运行。 - 进程阻塞：进程因需要等待某类资源（如 I/O 操作、信号量、锁）而进入阻塞状态，主动释放 CPU
- 进程主动礼让：部分系统支持进程通过
yield()等系统调用主动放弃 CPU
系统强制剥夺 CPU
- 高优先级进程到达：新进程进入就绪队列，且优先级高于当前运行进程
- 时间片耗尽：时间片轮转算法中，当前进程用完时间片（如10ms）→强制放回就绪队列末尾，触发调度。
硬件中断
- 时钟中断：操作系统通过定时器周期性产生时钟中断，内核在中断处理程序中检查是否需要进行调度
- I/O 中断：当 I/O 设备完成数据传输后，会产生中断信号，内核在中断处理程序中检查是否有阻塞进程可以唤醒并调度
调度算法评价指标
| 指标 | 描述 |
|---|---|
| 周转时间 Turnaround Time | 进程从 “提交” 到 “完成” 的总时间（包括等待时间、CPU 执行时间、I/O 时间） |
| 响应时间 Responsive Time | 进程从 “提交请求” 到 “首次获得 CPU 响应” 的时间 |
| 吞吐量 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
Preemptive & Non-preemptive
- 非抢占：进程开始后，除非主动放弃，否则其他进程只能排队等它让出CPU
- 抢占：内核调度程序将原进程中断，并将CPU分配给其他进程
交互式系统（如 Windows、Linux 桌面）以 “缩短响应时间、保证用户体验” 为核心，需频繁切换进程，常用以下抢占式算法：
- $\text{PS,Priority Scheduling}$: 优先权[1]调度算法
- HRRN, High Response Ratio Next：是介于 FCFS 和 SJF 之间的一种折中算法，使用响应比[2]作为优先权判断依据。
- $\text{RR,Round Robin}$: 将 CPU 分配给就绪队首进程。进程执行一个时间片后，计时器中断会停止该进程，并将其移至队列末尾，然后将 CPU 分配给新的队首进程，再次执行一个时间片。
- $\text{MLQ,MultiLevel Queue}$：将系统中运行的进程根据其特性划分为不同的就绪队列，并为每个队列分配不同的调度算法
- $MLFQ,MultiLevel Feedback Queue$：为各个队列赋予不同的优先级队列，规定高优先级队列时间片小。一个进程进入内存后，首先将它放入第一队列的末尾，轮到该进程执行时，如进程一次时间片没执行完，就降至下一级队列。OS优先调度高优先级队列中的进程，仅当 $RQ_0$ 空闲时才调度 $RQ_1$ 队列进程，以此类推
EDF, LLF
- $\text{EDF,Earliest Deadline First}$: 根据任务的截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。
- $\text{LLF,Least Laxity First}$: 按松弛度[3]排序，松弛度值最小的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行；当有任务执行时，只有等待任务的松弛度值为 0 才会发生任务的调度，其他情况不发生调度。
Process Scheduling in OS