自学内容网 自学内容网

处理机(CPU)调度

一. 调度的概念

多道程序系统中,进程数量往往多于CPU数量,因此经常出现进程争用CPU的情况,由此出现CPU调度的概念。

基本概念

CPU调度:对CPU进行分配,即从就绪队列中按照一定的算法(公平,高效原则)选择一个进程并将CPU分配给它运行,以实现进程并发执行。

调度的层次

  • 高级调度(作业调度)
    • 按照某种规则从后备队列的作业中选择一个或多个,给它们分配内存,I/O设备等必要资源,并建立相应进程,使得它们能够竞争CPU使用权。
    • 内存——辅存之间的调度
    • 每个作业只能调入一次,调出一次。

作业:需要完成的某一个具体任务。

  • 中级调度(内存调度)
    • 为了提高内存利用率和系统吞吐量,将暂时不能运行的程序调至外存等待,此时的进程状态称为挂起态

被挂起进程的PCB被组织成挂起队列。

  • 当挂起态的进程具备运行条件+内存有空闲,由中级调度决定将它们从外存调入内存,修改状态为就绪态,挂在就绪队列等待。
  • 实质上是存储器管理中的对换功能

补充:七状态模型
联想截图_20240719161936.png

  • 低级调度(进程调度/处理机调度)
    • 按照某种算法,从就绪队列选取一个进程分配给CPU
    • 进程调度是最基本的调度,各种OS都必须配置。
    • 使用频率很高,以便几十毫秒一次。

联想截图_20240719161809.png

三级调度的联系

  • 作业调度:为进程活动做准备;进程调度:使得进程正常活动起来。
  • 中级调度:挂起暂时不能运行的进程,处于作业调度和进程调度之间。
  • 作业调度次数少,中级调度次数略多,进程调度频率最高。
  • 进程调度是最基本的,不可或缺。

二. 调度的实现

这里的调度是指 内存调度(即低级调度):按照某种算法从就绪队列选择一个进程为其分配处理机(CPU)。

调度程序(调度器)

定义:用于调度和分派CPU的组件。结构组成:排队器,分派器,上下文切换器。

结构如图所示:
联想截图_20240719162545.png

  • 排队器
    • 将系统中所有就绪进程排成一个或多个就绪队列,以便调度程序选择。
    • 出现一个就绪进程,就把它插入相应的就绪队列。
  • 分派器
    • 依据调度程序选择的进程,将它从就绪队列取出,将CPU分配给(它)新进程。
  • 上下文切换器:对CPU进行切换时,会发生两对上下文切换操作。
    • 第一对:将当前进程的上下文保存到它的PCB中,再装入分配派程序的上下文,以便分派程序的运行。
    • 第二对:移除分派程序的上下文,将新选进程CPU的现场新选装入CPU各个寄存器。

上下文切换时,需要执行大量load指令和store指令,以保存寄存器的内容,会花费较多时间。
现在已有硬件实现方法来减少上下文切换时间:采用两组寄存器,一组供内核使用,另一组供用户使用。----> 切换上下文只需要改变指针,将其指向当前寄存器组。

调度时机,切换与过程

调度程序是操作系统的 内核程序。正常执行顺序:请求调度事件发生 -----> 运行调度程序----->调度新的就绪程序-----> 进行进程切换
实际上,若在OS中,某时刻发生了引起进程调度的因素,则不一定能马上进行调度与切换。

联想截图_20240719170435.png

联想截图_20240719170840.png

  • 创建新进程后,由于子父进程都处于就绪状态,此时需要决定运行哪一个进程。
  • 进程正常结束或异常终止后,必须从就绪队列选择一个进程。如果就绪队列为空,则运行闲逛进程。
  • 进程由于I/O请求、信号量操作或其他原因被阻塞,必须调度其他程序运行。
  • I/O设备完成后,发出I/O中断,原先等待I/O的进程从阻塞态转变为就绪态,此时需要决定 让新的就绪进程投入运行 还是 让中断发生时运行的进程继续执行。

联想截图_20240719172550.png

进程调度方式

即当某个进程正在CPU上执行时,若有优先级更高的进程进入就绪队列,应该如何分配CPU。

  • 非抢占调度方式(非剥夺方式)
    • 一个进程正在CPU上运行时候,即使有某个更紧急的进程需要处理,依然让当前进程继续执行,直到运行结束(正常结束或异常终止)或发生某种事件(如等待I/O操作,进程通信或同步中执行Block原语)而进入阻塞态,才将CPU分配给其他进程。
    • 优点:实现简单,开销小,适用于早期的批处理系统。
    • 缺点:不能用于分时操作系统和大多数实时操作系统。
  • 抢占调度方式(剥夺方式)
    • 一个进程正在CPU上运行时候,如果有某个更紧急的进程需要处理,运行调度程序暂停当前进程,将CU分配给更紧急的进程。
    • 特点:能够提高系统吞吐率和响应效率。遵循一定的原则"抢占"CPU,如:优先权原则,短进程优先原则,时间片原则等。

闲逛进程

进程切换时,如果系统中没有就绪进程,就会调度 闲逛进程(Idle Process) 运行,它的** PID=0**。如果没有其他就绪进程,该进程一直运行,并在指令周期后测试中断。

  • 优先级最低
  • 不需要CPU以外的资源,不会被阻塞

两种线程的调度

联想截图_20240719173933.png

三. 调度算法的评价指标

CPU利用率

联想截图_20240719175219.png

系统吞吐量

联想截图_20240719175348.png

周转时间

联想截图_20240719175443.png

等待时间

联想截图_20240719175625.png

响应时间

联想截图_20240719175705.png

四. 典型调度算法

先来先服务(FCFS)调度算法

是最简单的一种调度算法,可以用于作业调度和进程调度。

  • 表面上看,绝对公平,但如果一个长作业优先到达系统,就会使得后面的短作业等待很长时间,因此不能作为分时系统和实时系统的主要调度策略。
  • 常被结合在其他调度策略中使用。如:使用优先级调度策略的系统中,对多个具有相同优先级的采用FCFS原则。
  • FCFS属于不可剥夺算法。
  • 算法简单,效率低;对长作业 有利,对短作业不利(相对于SJF和高响应比)
  • 有利于CPU繁忙型作业,不利于I/O繁忙型作业。

联想截图_20240719204333.png

短作业优先(SJF)调度算法

  • 短作业优先(SJF):从后备队列中选择一个或多个估计运行时间最短的作业,调入内存开始运行。
  • 短进程优先(SPF):从就绪队列选择一个估计运行时间最短的进程,分配CPU,使之立即执行。

SPF算法可以是抢占式(默认是非抢占式):新进程的预估执行时间比当前进程剩余时间短,就会暂停当前进程,分配CPU给新进程。因此,抢占式SPF调度算法也称为最短剩余时间优先调度算法。

联想截图_20240719205347.png

短作业(SJF)调度算法的平均等待时间、平均周转时间最优的。

  • SJF的缺点:
    • 该算法对长作业不利。SJF调度算法中长作业的周转时间增加,可能导致长作业长期不被调度,产生**”饥饿“现象**。
    • 未完全考虑作业紧迫程度,不保证紧迫作业被及时处理。
    • 由于作业长短是根据用户提供的估计执行时间确定的,不一定能真正做到短作业优先。

高响应比优先调度算法

  • 主要用于作业调度,是对FCFS,SJF的综合利用。选出作业响应比最高的投入运行

联想截图_20240719210545.png

  • 作业等待时间相同:有利于短作业,类似于SJF。
  • 要求服务时间相同:等待时间越长相应比越大,类似于FCFS。
  • 对于长作业,作业的响应比可以随着等待时间增加而增大,克服了”饥饿“现象。

优先级调度算法

可以用于作业调度和进程调度。作业的紧迫程度用优先级描述。优先级最高的进程/线程最先被投入运行

  • 非抢占式优先级调度算法:当CPU上存在进程运行时,如果有一个新的进程优先级很高,依然等待当前进程运行完毕后才分配CPU。
  • 抢占式优先级调度算法:当CPU上存在进程运行时,如果有一个新的进程优先级很高,将立刻暂停当前进程,分配CPU给新进程。

进程的优先级

  • 静态优先级:优先级在创建进程时候确定,整个运行期间保持不变。【确定依据:进程类型,对资源的要求,用户要求】
    • 优点:简单易行,开销小。
    • 缺点:不够精确,可能出现低优先级进程长期得不到调度。
  • 动态优先级:创建进程时候先赋予一个优先级,该优先级会随着进程的推进或等待时间增加而改变,以便获得更好的调度性能。

一般而言:

  • 系统进程 > 用户进程。
  • 交互型进程 > 非交互型进程
  • I/O型进程 > 计算型进程

时间片轮转(RR)调度算法

  • 主要适用于分时操作系统。
  • 就绪进程按照FCFS策略排为就绪队列。
  • 间隔一定时间产生一次时钟中断,激活调度程序进行调度。使用 FCFS 策略调度进程
  • 如果当前进程在执行完一个时间片后依然没有运行完成,则产生时钟中断,由时钟中断处理程序激活调度程序。进程中断运行,插入队尾等待下一次的时间片。
  • 如果时间片未用完,但是进程已经运行完毕,则立即激活调度程序。

特点:

  • 时间片大小影响系统的性能。【时间片大:退化为 FCFS 调度算法;时间片小:CPU频繁切换进程,开销大】
  • 时间片确定因素:系统响应时间,就绪队列中的进程数量,系统处理能力。

多级队列调度算法

  • 设置多个就绪队列。将不同类型或性质的进程分配到不同的就绪队列。
  • 每个队列可以实施不同的调度算法
  • 不同队列也可以设置不同的优先级。

多CPU系统中,可以很方便地为每个CPU设置一个单独的就绪队列。这样就可以根据用户需求将多个线程分配到一个或多个CPU运行。

多级反馈队列调度算法(融合前几种算法优点)

综合 时间片轮转调度算法和优先级调度算法,动态调整进程优先级和时间片大小。不必事先估计进程的执行时间。

联想截图_20240719214203.png

  • 设置多个就绪队列,每个队列设置不同的优先级
  • 赋予各个队列的进程运行时间片大小各不相同。队列优先级越高进程的时间片越小
  • 每个队列都采用 FCFS 调度算法
  • 按队列优先级执行调度:先执行优先级高的队列的进程。【如果当前运行低优先级进程,则立即中断】
  • 优点:
    • 终端型作业用户:短作业优先。
    • 短批处理作业用户:周转时间较短。
    • 长批处理作业用户:经过前面几个队列得到部分执行,不会长期得不到处理。

** 总结**
联想截图_20240719213954.png


原文地址:https://blog.csdn.net/qq_74259765/article/details/140560391

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!