本文共 2401 字，大约阅读时间需要 8 分钟。

5-1 CPU调度的基本概念

1.进程的CPU和I/O burst的交替序列

①交替序列的图

②CPU脉冲的分布：在系统中存在许多短CPU脉冲，只有少量的长CPU脉冲。

③I/O型作业，许多短CPU脉冲；CPU型作业，有几个长CPU脉冲。

 

2.当CPU空闲时，OS就选择内存中某个就绪进程，并给其分配CPU

 

3.进程的CPU调度可能发生在以下情况下：

①从运行转到等待  非抢占方式

②从运行到就绪    抢占方式

③从等待到就绪   抢占方式

④终止运行  非抢占方式

 

4.抢占方式和非抢占方式

①抢占方式 （preemptive mode）

允许调度程序根据某个原则，去停止正在执行的进程，将处理机重新分配给另一个进程。

②非抢占方式（nonpreemptive）

把处理机分配给某个进程后，便一直执行，直到该进程完成或发生某事件而被阻塞，才把处理机分配给其他进程，不允许其他进程抢占已经分配出去的处理机。

优点：实现简单，开销小

缺点：难以满足紧急任务需求

 

5.抢占方式的原则

①时间片原则：各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新调度，适用于分时系统。

②优先权原则：通常对异性重要的和紧急的进程赋予较高的优先级，则将处理机分配给优先级更高的进程。

③短作业优先原则：当新到达的作业比正在执行的作业明显短时，将暂停当前长作业的执行，将处理机分配给短作业，使之执行。

 

5-2 CPU调度算法：FCFS

1.问题

①调度程序采用什么算法选择一个进程（作业）？

②如何评价调度算法的性能？

 

2.调度准则

①CPU利用率——使CPU尽可能的忙碌

②吞吐量——单位时间内运行完的进程数

③周转时间——进程从提高到运行结束的全部时间

④等待时间——进程在就绪对待中等待调度的时间片总和

⑤响应时间——从进程提出请求到首次被响应的时间

 

小结：调度算法影响的是等待时间，而不能影响进程真正使用CPU的时间和I/O时间。

 

3.First-Come-First-Served（FCFS，先来先服务）

①最简单的调度调度算法，可用于作业或进程调度，按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择

②FCFS算法属于非抢占方式

③FCFS算法易于实现，表明上很公平，实际上有利于长作业，不利于短作业；由于有CPU繁忙型，不利于I/O繁忙型

 

④护航效应：假设有一个CPU型进程和许多I/O型进程，当CPU进程占用CPU运行时，I/O型进程可能完成了其I/O操作，回到就绪队列等待CPU，I/O设备空闲；CPU进程释放后，I/O进程陆续使用CPU，并很快转为I/O操作，CPU空闲。

 

5-3 CPU调度算法SJF（Shortest-Job-First）

关联到每个进程下次运行的CPU脉冲长度，调度最短的进程

1.两种策略

①非抢占式调度

一旦进程拥有CPU，使用权限只能在该CPU脉冲结束后让出

②抢占式调度

发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度。

 

2.SJF是最优的——对一组进程而言，它给出了最短的平均等待时间。

抢占式调度

局限性：下一个进程的长度只能估计

 

3.SJF的特点

①有利于系统减少平均周转时间，提高系统吞吐量

②一般情况下SJF调度算法比FCFS调度算法的效率更高一些，但是实现相对要困难一些

③如果作业的到来顺序及运行时间不合适，会出现饥饿现象

 

5-4 优先级和RR时间片轮转

1.优先级算法

①每个进程都有自己的优先数[整数]

②CPU分配给最高优先级的进程

③抢占式和非抢占式

④SJF是以下一次CPU脉冲长度为优先数的优先级调度

 

2.静态优先级

①静态优先级在进程创建时确定，且在整个生命期中保持不变

②问题：饥饿——低优先级的可能永远得不到运行

③解决方法：老化——视进程等待时间延长提高其优先级

 

3.动态优先级

①动态优先级：优先权随进程推进而改变，以便获得更好的调度性能。

②改变优先权的因素：

• 进程等待时间
• 已使用处理机的时间
• 资源使用情况
•  

4.时间片轮转调度法（Round Robin，RR）

①分时系统：每个进程将得到小单位的CPU时间（10-100毫秒），时间片用完，该进程被抢占并插入队列末尾。

②例子：

 

③特征：时间片q过大，趋近于FCFS方法；

时间片q过小，q相对于上下文切换而言足够长，否则导致系统开销过大。

④一组进程的评价周转时间并不随着时间片增大而降低。一般来说，如果大多数（80%）进程能在一个时间片内完成，就会改善平均周转时间。

 

5-5多级队列和多级反馈队列

1.多级队列

①按进程的属性分类，每类进程组成一个就绪队列，每个进程固定处于某一个队列中，如前台就绪队列和后台就绪队列。

②每个队列都有自己的调度算法，如前台（foreground） RR调度算法，后台（background） FCFS

 

2.队列间的调度

①固定优先级 产生饥饿问题

②给定时间片调度，即给每个队列一定的CPU时间，进程在给定时间内执行

如80%时间执行前台的RR调度，20%时间执行后台的FCFS调度。

 

3.多级反馈队列调度

①存在多个队列，不同优先级，各自按RR调度

②各就绪队列中时间片大小不同，优先级越高的队列时间片越小

③允许进程在队列间移动

④一个进程执行完一个时间片后被抢占处理器，优先级降一级而进入下级就绪队列，如此直到将至进程的基本优先级。一个进程从阻塞太变为就绪态时要提高优先级（阻塞时间过长）

⑤最后将I/O型和交互性进程留在较高优先级队列

⑥多级反馈队列调度示意图

 

⑦进程能在不同队列间移动，可实现老化

⑧多级反馈队列调度程序的参数：

• 队列数
• 每一队列的调度算法
• 决定进程升级的方法
• 决定进程降级的方法
• 决定需要服务的进程进入哪个队列的方法

 

本文知识以及图片来源：慕课_操作系统原理_田丽华

网址：

转载地址：https://blog.csdn.net/Fan_z_0802/article/details/94414423 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！