4 CPU Scheduling¶
4.1 Basic Concepts¶
CPU调度 == 处理机调度 == 进程调度
一个进程的执行不是连续占用 CPU 的，而是由一系列 “CPU burst”（CPU 激活期） 和 “I/O wait”（I/O 等待期） 组成的交替循环。
- CPU Burst Time：一次连续使用 CPU 的时间长度（单位：毫秒）。
- I/O Burst Time：一次 I/O 操作所需的时间（包括等待和传输时间）
CPU-bound & I/O-bound
- CPU-bound 程序：一旦运行，会持续占用 CPU，容易导致其他进程“饥饿”。
- I/O-bound 程序：很快释放 CPU，适合频繁调度，能提升系统响应性。
调度方式：
- 非抢占式（Nonpreemptive）调度:调度程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。
- 抢占式（Preemptive）调度:当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。
4.2 Scheduling Criteria¶
周转时间 Turnaround time ：进程从提交到完成所经历的时间。包括：在CPU上执行，就绪队列和阻塞队列中等待。
- 周转时间 T=完成时间-提交时间
- 平均周转时间=\(\sum\) 周转时间/进程数
- 带权周转时间W= T(周转时间)/t(CPU执行时间)
- 平均带权周转时间=\(∑\) W/进程数
响应时间 Response time ：从进程提出请求到首次被响应（而不是输出结果）的时间段（在分时系统环境下）
等待时间 Waiting time – 进程在就绪队列中等待的时间总和
吞吐量 Throughput ：单位时间内所完成的进程数，跟进程本身特性和调度算法都有关系——批处理系统
处理机利用率 CPU utilization：使CPU尽可能的忙碌
Optimization Criteria最优准则
- 最大的CPU利用率 Max CPU utilization
- 最大的吞吐量 Max throughput
- 最短的周转时间 Min turnaround time
- 最短的等待时间 Min waiting time
- 最短的响应时间 Min response time
4.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 多级反馈队列调度
4.3.1 First-Come, First-Served (FCFS) Scheduling¶
按照进程或作业提交顺序形成就绪状态的先后次序，分派CPU。当前进程或作业占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在进程或作业唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU
FCFS 的特点
- 比较有利于长进程，而不利于短进程。
- 有利于CPU Bound的进程，而不利于I/O Bound的进程。
FCFS scheduling
4.3.2 Shortest-Job-First (SJF) Scheduling¶
又称为“短进程优先”SPF(Shortest Process First)；这是对FCFS算法的改进，其目标是减少平均周转时间。将预计执行时间段的作业优先分派给处理机
有两种策略，分别是抢占式调度和非抢占式调度，这在后面的例子可以直观地比较。也可以说原始的 SJF 是非抢占式的，抢占式的被称为一种变形，为 SRT
SJF 是最优的，给定一系列的作业下，这个调度算法可以得到最小的等待时间
SJF 的两种变形
最短剩余时间优先 SRT(Shortest Remaining Time)-基于抢占的SJF算法
- 允许比当前进程剩余时间更短的进程来抢占
最高响应比优先HRRN(Highest Response Ratio Next)
- 响应比R = (等待时间 + 要求执行时间) / 要求执行时间，也就是等的时间越长，相应比越高
- 是 FCFS 和 SJF 的折衷
Example of Non-Preemptive SJF
Example of Preemptive SJF
既然这个调度算法是最优的，那么为什么当今操作系统都不使用这个方法呢？因为我们并不知道之后的任务运行的时间，我们只能进行估计。
利用该进程 之前几次 CPU burst 的实际长度，通过一种叫做 指数加权平均（Exponential Averaging） 的方法，来预测下一次的 burst 时间。
-
\(t_n\) = actual length of \(n^\text{th}\) CPU burst
-
\(\tau_{n+1}\) = predicted value for the next CPU burst
-
\(\alpha\), where \(0 \leq \alpha \leq 1\)
-
Define: \(\tau_{n+1} = \alpha t_n + (1 - \alpha)\tau_n\)
Note
这里取 \(\alpha = 0.5\)
4.3.3 Priority Scheduling¶
该算法总是把处理机分配给就绪队列中具有最高优先权的进程。常用以下两种方法来确定进程的优先权：
-
静态优先权: 静态优先权是在创建进程时确定的，在整个运行期间不再改变。依据有：进程类型、进程对资源的要求、用户要求的优先权。
-
动态优先权: 动态优先权是基于某种原则，使进程的优先权随时间改变而改变。
Note
关于优先级的设置，有些是越小的数代表优先级越高，有些则相反，做题时需要注意
这个调度与前面一样，既可以是抢占式的，也可以是非抢占式的。区别就是当更高特权的进程来时，是直接抢占还是等现在的进程完成或阻塞。
non-preemptive
假设所有的 Process 都是在0时刻进入的
preemptive
假设所有的 Process 都是在0时刻进入的
上述阐述的都是静态优先权的例子，这会产生饥饿的问题，低优先级的进程可能永远都不会运行。所以引入动态优先级以解决这个问题。
5.3.4 时间片轮转调度 Round Robin (RR)¶
基本思路：通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率。
- 将系统中所有的就绪进程按照FCFS原则，排成一个队列。
- 每次调度时将CPU分派给队首进程，让其执行一个时间片 (time slice) 。时间片的长度从几个ms到几百ms。
- 在一个时间片结束时，暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行就绪队列的队首进程。
- 进程可以未使用完一个时间片，就出让CPU（如阻塞）。
Example
时间片的设置也会影响进程的调度，平均周转时间不一定随着时间片的增加而改善。如果时间片太大，RR调度就变成FCFS策略。时间片太小就会导致频繁的上下文的切换。80%的CPU突发事件应短于时间片
5.3.5 多级队列调度¶
根据进程的性质或类型的不同，将就绪队列再分为若干个子队列。
每个进程固定归入一个队列。各队列的不同处理：不同队列可有不同的优先级、时间片长度、调度策略等。如：系统进程、用户交互进程、批处理进程等。
比如说可以将就绪队列分为前台（交互式）和后台（批处理），对于前台使用 RR 调度算法，后台使用 FCFS 算法。
多级队列算法调度须在队列间进行
- 固定优先级调度，即前台运行完后再运行后台。有可能产生饥饿
- 给定时间片调度，即每个队列得到一定的CPU时间，进程在给定时间内执行；如，80%的时间执行前台的RR调度，20%的时间执行后台的FCFS调度
5.3.6 多级反馈队列算法¶
多级反馈队列调度算法通过设置多个具有不同优先级的就绪队列，实现对进程的动态管理和高效调度。
新创建的进程首先被放入最高优先级的队列（如队列1），采用时间片轮转（RR）算法运行，若在一个较短的时间片内未能执行完毕，则认为其为CPU密集型任务，将其降级至下一个优先级较低的队列（如队列2），并在该队列中获得更长的时间片继续运行；这一过程逐级进行，直到进程完成或进入最低优先级队列，通常在最低队列中以FCFS方式运行以减少上下文切换开销；
调度时始终优先执行高优先级队列中的进程，只有当高优先级队列为空时才调度低优先级队列；若在某个低优先级进程运行时，有新进程进入更高优先级队列，则立即抢占当前进程的CPU，将其放回原队列末尾，确保交互式或紧急任务能够快速响应，从而兼顾了系统的响应速度、吞吐量和公平性。
评论区
对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！