Chapter 5: CPU Scheduling

:material-circle-edit-outline: 约 1747 个字 :material-clock-time-two-outline: 预计阅读时间 6 分钟

CPU调度

5.1 Basic Concepts

CPU调度 == 处理机调度 == 进程调度

Three-level Scheduling

Long-term scheduler 长程调度（或作业调度 or job scheduler)
- 筛选出能推入就绪队列的作业，同时控制并发程度
- 这种调度每时每分都在执行，会很慢，现代 OS 基本没有这种调度了
- 从外存选进程进入内存
Short-term scheduler 短程调度（或CPU调度 or CPU scheduler)
- 筛选出下一个被执行的进程，给其分配 CPU
- 每时每分都在执行，一定很快
Medium-Term Scheduler 中程调度
- 确定队列中哪个进程可以被分配处理器
- 缓解内存紧张，临时取消CPU分配，见下图

CPU Scheduler

根据调度时机，分为两种调度方式

非抢占式（Nonpreemptive）调度
- 调度程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程
抢占式（Preemptive）调度
- 当一个进程正在运行时，系统可以剥夺已分配给它的处理机，将之分配给其它进程
- 剥夺原则有：优先权原则、短进程优先原则、时间片原则。

Dispatch latency（调度延迟） – time it takes for the dispatcher to stop one process and start another running调度程序停止一个进程到启动一个进程所需要的时间

Scheduling Criteria

调度算法的选择准则和评价

面向用户(User-oriented)

有以下几个标准

周转时间 Turnaround time
- 进程从提交到完成所经历的时间。包括：在CPU上执行，就绪队列和阻塞队列中等待。
- 一个进程的周转时间 T= 完成时间 - 提交时间
响应时间 Response time
- 从进程提出请求到首次被响应（而不是输出结果）的时间段（在分时系统环境下）
等待时间 Waiting time – 进程在就绪队列中等待的时间总和
- 调度算法影响的只有等待时间，不影响进程真正的运行时间

面向系统的调度性能准则

吞吐量Throughput
- 单位时间内所完成的进程数，跟进程本身特性和调度算法都有关系
- 平均周转时间不是吞吐量的倒数，因为并发执行的进程在时间上可以重叠
处理机利用率CPU utilization
- 使CPU尽可能的忙碌
各种设备的均衡利用
- 如CPU繁忙的进程和I/O繁忙的进程搭配

调度算法本身的调度性能准则

易于实现，执行开销比较小

5.3 Scheduling Algorithms

First-Come, First-Served (FCFS) Scheduling先来先服务调度
Shortest-Job-First (SJF) Scheduling 短作业优先调度
Priority Scheduling 优先权调度
Round Robin (RR) 时间片轮转调度
Multilevel Queue Scheduling 多级队列调度
Multilevel Feedback Queue Scheduling多级反馈队列调度

响应比 R = (等待时间 + 要求执行时间) / 要求执行时间

高响应比优先调度算法 Highest Response Ratio Next(HRRN)

First-Come, First-Served (FCFS) Scheduling

按照进程或作业提交顺序形成就绪状态的先后次序，分派CPU，直到执行完或阻塞，才出让CPU，即非抢占方式

比较有利于长进程，而不利于短进程
有利于CPU Bound的进程，而不利于I/O Bound的进程

将更长 burst time 的进程往后推，可以得到更低的平均等待时间和平均周转时间

于是就有了 SJF 调度

Shortest-Job-First (SJF) Scheduling

又称“短进程优先”SPF(Shortest Process First)，对预计执行时间短的作业（进程）优先分派处理机，又分是否抢占良种 schema

nonpreemptive
preemptive，即 Shortest-Remaining-Time-First (SRTF)

SJF is optimal – gives minimum average waiting time for a given set of processes

SJF的变型

最短剩余时间优先SRT(Shortest Remaining Time)-基于抢占的SJF算法
最高响应比优先HRRN(Highest Response Ratio Next)
- 响应比R = (等待时间 + 要求执行时间) / 要求执行时间

Example of Non-Preemptive SJF

Example of Preemptive SJF

Priority Scheduling

Associate a priority number with each process，通常是整数，数字越小代表优先级越高

优先权有以下两种

静态优先权
- 静态优先权是在创建进程时确定的，在整个运行期间不再改变
动态优先权
- 动态优先权是基于某种原则，使进程的优先权随时间改变而改变
- SJF是以下一次CPU脉冲长度作为优先数的优先级调度

Priority Scheduling 也分抢占式和非抢占式

Non-preemptive priority scheduling
- 优先级高的要等目前在运行的跑完先
Preemptive priority scheduling
- 优先级高的可以马上抢

这个调度有个问题叫 Starvation(饥饿)，即低优先级进程可能永远不会执行，可以设置 Aging(老化) 随时间提升优先级

Example of Priority Scheduling

注意非抢占式没有到达时间

时间片轮转调度 Round Robin (RR)

通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率

将系统中所有的就绪进程按照FCFS原则，排成一个队列、
每次调度时将CPU分派给队首进程，让其执行一个时间片 (time slice / time quantum)
在一个时间片结束时，暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行就绪队列的队首进程（context switch）
进程可以未使用完一个时间片，就出让CPU（如阻塞）

If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once.

No process waits more than (n-1)q time units.

响应时间=n*q

q large == FIFO

Example of RR with Time Quantum = 20

显然，时间片的大小对该调度的性能至关重要

多级队列调度

将就绪队列分为若干个子队列，各子队列内部的处理不同

foreground (interactive) 前台（交互式）
- RR
background (batch) 后台（批处理）
- FCFS

算法还需以各子队列为基本单位进行调度

Multilevel Feedback Queue Scheduling

多级反馈队列算法，有点像消化道在消化进程

设置多个就绪队列，分别赋予不同的优先级，时间片长度不同，规定优先级越低则时间片越长
新进程创建后先进入最高优先级的队列末尾，过了一个当前队列的时间片还没消化完就进入下一级的末尾，以此类推，直到最后一个队列，最后一个队列直接用 FCFS
仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行
如果进程执行时有新进程进入较高优先级的队列，则抢占执行新进程并把被抢占的进程投入原队列的末尾

相当于多队列的 RR 调度