CPU调度

复习

1. 内存抽象：
   
2. 进程的状态转移：
   
3. 进程通信：共享内存、消息传递、管道

进程调度

进程调度分为三类：

• 低级调度：也称为进程调度、短程调度，作用：决定就绪队列中的哪些进程应该获得CPU。
• 中级调度：也称为中程调度，作用：使暂时不能运行的进程从内存调至外存，进入就绪驻外存状态或挂起状态。 目的：提高内存利用率和系统吞吐量。
• 高级调度：又称为作业调度、长程调度、接纳调度，作用：把外存上处于后背队列中的作业调入内存，并为它们创建进程、分配资源、排在就绪队列上，准备执行。在每次执行该调度时，都必须做出一下两个决定: 接纳多少作业、接纳哪个作业。

将上述三种调度结合起来看，形成调度模型：

上述模型的理解：

• 由作业调度决定将哪些进程从外存中调入内存。
• 然后进程调度和中级调度配合，分别决定给哪个进程分配CPU和将哪些进程从内存中调出到外存。

概念补充

周转时间：

• 从作业被提交给系统开始，到作业完成为止的这段时间间隔。
• 周转时间=在外存后备队列等待被调度的时间（作业调度）+ 在就绪队列上等待调度的时间（进程调度）+ 在CPU上执行的时间 + 进程等待IO操作完成的时间

平均周转时间：

• 每个任务的周转时间求和
• 然后除以n

带权周转时间：

• W=T/T_s
• T：作业的周转时间
• 系统为其提供服务的时间（真正在CPU上运行的时间）

来道题算一下：求平均周转时间和平均带权周转时间

平均周转时间=(2+2.83+3)/3=2.61
平均带权周转时间=(1+2.83+12)/3=5.27

为什么要补充周转时间相关的几个概念呢？很显然，带权周转时间一定程度上反应了调度算法的好坏。

响应时间：

• 是指从用户通过键盘提交一个请求开始，直到系统首次产生相应为止的时间间隔
• 响应时间=从键盘输入的请求信息传到CPU的时间+CPU处理的时间+响应传回来并显示在显示器的时间

截止时间：

• 是指某任务必须开始执行的最迟时间，或者必须完成的最迟时间。

吞吐量：

• 单位时间内系统所完成的作业数
• 是评价处理系统性能的重要指标

CPU可能发生调度的时间点：

• 从运行状态切换至等待状态
• 从运行状态切换至就绪状态
• 从等待状态切换至就绪状态
• 进程终止

调度方案只在1和4发生时为非抢占式调度（因为当前进程跑不下去了，是主动放弃CPU的，不是被强迫的），否则为抢占式调度。

关于抢占式调度与非抢占式调度

• 非抢占式调度又称为协作调度
• 非抢占式调度：进程主动放弃CPU（如等待IO）
• 非抢占式调度实现简单，不需要硬件支持
• 非抢占式的一个问题：如果一个进程不放弃CPU怎么办？
• 所以出现了抢占式调度：现代操作系统也是采用了抢占式调度
• 抢占式调度：需要定时器支持，实现复杂（进程被强制切换需要保护上下文）

选择调度方式和调度算法的若干准则

• 面向用户的准则
  • 周转时间短
  • 响应时间快
  • 截止时间的保证
  • 优先权准则
• 面向系统的准则
  • 系统吞吐量高
  • CPU利用率好
  • 各类资源的平衡利用

六种调度算法

1. 先到先服务（最简单的，也应该被最先研究）

既可以用于作业调度，又可以用于进程调度，简称（FCFS）
优点：

• 实现简单
• 相对公平：没有饥饿

缺点：

• 较长的平均周转时间

举个极端的例子：操作系统接收到了两个任务：

• 任务1，耗时长，大概10个小时
• 任务2，很简单，就算一下2^13等于多少

如果按照FCFS，任务一先到达，任务二后到达，那么十分悲剧，任务二的带权周转时间太长了。

上述例子中的任务2是属于短作业，那么能不能让短作业先计算呢？

2.短作业（进程）优先调度算法

首先明确一点：没有算法可以准确评估某个任务所需花费时间，所以此算法只是用于理论研究，实际中无法应用。

短作业优先简称SJF：从后备队列中选择一个或多个运行时间最短的作业调入内存运行。
短进程优先简称SPF：从就绪队列中选出一个估计运行时间最短的进程，分配CPU使其运行直到完成。

注：作业和进程的不同：作业保存在外存中，调入内存的就绪队列后变成了进程，其中包含了创建进程等过程。

对比FCFS和SJF：

基于本算法的思想可以衍生出多个版本：
如最短作业优先：

最短剩余时间优先（每一时刻都计算各个进程的剩余时间）：

分析此类算法的优缺点
优点：能保证最短等待时间
缺点：无法估计程序运行时间，而且容易造成长作业饥饿

3. 优先级调度算法

思想其实很简单，充过VIP把，看视频不用等广告的那种（斜眼笑）。
实现思路

• 每个进程都有一个整型优先级
• 选择优先级最高的进程执行（约定最小整数对应最大优先级）
• 可以实现抢占式和非抢占式的
• 最短作业优先调度算法其实也属于本算法的一种：优先级为运行时间的倒数

举个例子：

调度顺序应该是：P2, P5, P1, P3, P4
思考一个问题：抢占式版本和非抢占式版本有何区别：

• 如果不考虑IO的话，两种版本好像没有区别鸭（笔者不确定）
• 因为每次时间片用完之后优先级并没有发生变化，所以还是按照原顺序调度。

对上述算法做改进（上述算法的缺点是平均响应时间过长），衍生出：高响应比优先级调度

• 引入动态优先权，使作业的优先权随等待时间而增长。优先权的变化规律可表示为：优先权=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间
• 优点是：兼顾了长短作业
• 缺点是：做相应比计算，增加了系统开销。

4. 轮转调度算法

• 时间片的概念，如早期Linux内核的20ms
• 每个进程最多允许运行一个时间片，若一个时间片内进程没有运行完，则被加入就绪队列
• 举例：
  

性能：

• 如果时间片非常大的话，那么就变成FCFS了
• 如果时间片非常小：额外开销会很大（上下文切换）

评价：

• 该算法只有抢占式版本（时间片用完就抢占）
• 是一种普遍被采用的调度算法（Linux， xv86）
• 可以与优先级调度算法结合使用，Windows下调度策略。
• 时间片的大小是一个问题

进程概述中笔者提到一个问题

笔者大胆猜测：

• Windows下进程调度方式可能采用的是动态优先权的轮换调度算法。如果上述问题不是由于动态优先权降低引起的，那么笔者还有一个猜测：
• 我们在忙其他工作时：将和IDEA有关的高速缓存或者相应的页换了出去，从而导致切回来时有明显的卡顿现象。

5.多级队列调度

• 就绪队列被进一步划分成多个队列，如前台（交互式的），后台（批处理的）
• 每个队列有自己独立的调度算法，如：前台（RR,轮转），后台（FCFS）
• 多个队列之间如何调度？优先级调度（可能发生饥饿），按比例分配时间（比例如何定是问题）

6.多级反馈队列调度

一个进程可以在多个队列之间移动，使用CPU越多，优先级越低
举例子：划分成3个队列：

• Q0：RR时间片为8ms
• Q1：RR时间片为16ms
• Q2：FCFS

某个进程在Q0执行一段时间后，转移到Q1，然后转移到Q2

小结

• 上面的算法都不难，不难的一个重要原因是：OS需要频繁使用调度算法，所以这些算法应该尽量设计的简单高效，所以我们学起来也不会太难
• 调度算法分为抢占式和非抢占式
• FCFS：有抢占式版本和非抢占式版本
• SJF：也有抢占式和非抢占式版本
• 优先级调度：也有抢占式和非抢占式版本
• 轮转调度：抢占式和非抢占式都有，最常见的是时间片抢占（也是现代操作系统采用的方式）
• 多级队列调度：抢占式和非抢占式（？）
• 多级反馈队列调度：抢占式

如果觉得写的不错，对读者有帮助，可以给笔者点个赞，鼓励一下哦~

本系列博客地址
下一篇：实时调度