首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >图解经典的进程调度算法

图解经典的进程调度算法

作者头像
飞天小牛肉
发布2021-02-26 14:20:57
1.1K0
发布2021-02-26 14:20:57
举报
文章被收录于专栏:飞天小牛肉飞天小牛肉

文中的很多图片来源我考研时看的网课,B 站上应该还能找到,王道考研出品的操作系统系列,各位可以去看看,适用于考试,不太适用于春招秋招,因为知识点讲的太细,边边角角都会讲到,各位可以挑几个章节去看。全文脉络思维导图如下:

1. 调度的概念

当 CPU 有一堆任务要处理时,由于其资源有限,这些事情就没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序,这就是 “调度” 研究的问题。除了接下来将要说的进程调度,还有作业调度、内存调度等。

回顾一下进程的三态模型:

  • 「运行态」(running):进程占有 CPU 正在运行。
  • 「就绪态」(ready):进程具备运行条件,等待系统分配 CPU 以便运行。
  • 「阻塞态」 / 等待态(wait):进程不具备运行条件,正在等待某个事件的完成。

所谓进程调度,就是「从进程的就绪队列(阻塞)中按照一定的算法选择一个进程并将 CPU 分配给它运行」,以实现进程的并发执行。这是操作系统中最基本(最低级)的一种调度,在一般的操作系统中都必须配置进程调度。进程调度的频率很高,一般几十毫秒一次。

2. 非抢占式进程调度算法

所谓非抢占式的意思就是,当进程正在运行时,它就会一直运行,直到该进程完成或发生某个事件发生而被阻塞时,才会把 CPU 让给其他进程。

对应的,抢占式的意思就是,当进程正在运行的时,可以被打断,把 CPU 让给其他进程。

① 先到先服务 FCFS

先来先服务调度算法(First Come First Serve,FCFS):按照进程到达的先后顺序进行调度,「先到的进程就先被调度」,也就是说,等待时间越久的越优先得到服务。

优点:公平、算法实现简单

缺点:对短进程不利。排在长进程后面的短进程需要等待很长时间,短进程的响应时间太长了,用户交互体验会变差。

② 最短作业优先 SJF

最短作业/进程优先调度算法(Shortest Job First,SJF):「每次调度时选择当前已到达的、且运行时间最短的进程」

最短作业优先算法和先到先服务恰好相反,先到先服务对短进程不利,而最短作业优先算法对长程不利。因为如果一直有短进程到来,那么长进程永远得不到调度,长进程有可能会饿死,处于一直等待短作业执行完毕的状态。

③ 高响应比优先 HRRN

高响应比优先算法(Highest Response Ratio Next,HRRN):只有当前运行的进程主动放弃 CPU 时(正常/异常完成,或主动阻塞),才需要进行调度,「调度时计算所有就绪进程的响应比,为响应比最高的进程分配 CPU」响应比 = (进程的等待时间 + 进程需要的运行时间) / 进程需要的运行时间

3. 抢占式进程调度算法

抢占就是指当进程正在运行的时,可以被打断,把 CPU 让给其他进程。抢占的原则一般有三种,分别是时间片原则、优先权原则、短作业优先原则。

① 最短剩余时间优先 SRTN

最短剩余时间优先(Shortest Remaining Time Next,SRTN)算法是「最短作业优先的抢占式版本」

「当一个新的进程到达时,把它所需要的整个运行时间与当前进程的剩余运行时间作比较。如果新的进程需要的时间更少,则挂起当前进程,运行新的进程,否则新的进程等待。」

② 轮转调度算法 RR

轮转调度算法(Round Robin,RR)也称时间片调度算法:调度程序每次把 CPU 分配给就绪队列首进程使用规定的时间间隔,称为时间片,通常为 10ms ~ 200ms,「就绪队列中的每个进程轮流地运行一个时间片,当时间片耗尽时就强迫当前运行进程让出 CPU 资源,转而排到就绪队列尾部,等待下一轮调度」。所以,一个进程一般都需要多次轮转才能完成。

轮转调度算法对每个进程都一视同仁,就好比大家都排好队,一个一个来,每个人都运行一会儿再接着重新排队等待运行。

需要注意的是:时间片的长度是一个很关键的因素:

  • 如果时间片设置得太短,就会导致频繁的进程上下文切换,降低了 CPU 效率;
  • 如果时间片设置得太长,那么随着就绪队列中进程数目的增加,轮转一次消耗的总时间加长,即每隔进程的相应速度放慢。甚至时间片大到让进程足以完成其所有任务,RR 调度算法便退化成 FCFS 算法。

4. 最高优先级调度算法 HPF

RR 调度算法对所有的进程都是相同的策略,如果用户进程太多,可能会导致内核的服务进程响应跟不上。而在操作系统中,内核进程是比用户进程重要的多的,毕竟它关乎整个系统的稳定性。

最高优先级调度算法(Highest Priority First,HPF)就是「从就绪队列中选择最高优先级的进程进行运行」。进程的优先级是怎么规定的呢?分为静态优先级或动态优先级:

  • 「静态优先级」:创建进程时候,就预先规定优先级,并且整个运行过程中该进程的优先级都不会发生变化。一般来说,内核进程的优先级都是高于用户进程的。
  • 「动态优先级」:根据进程的动态变化调整优先级。比如随着进程的运行时间增加,适当的降低其优先级;随着就绪队列中进程的等待时间增加,适当的升高其优先级。

另外,需要注意的是,最高优先级算法并非是固定的抢占式策略或非抢占式,「系统可预先规定使用哪种策略」

  • 非抢占式:当就绪队列中出现优先级高的进程,则运行完当前进程后,再选择该优先级高的进程。
  • 抢占式:当就绪队列中出现优先级高的进程,则立即强制剥夺当前运行进程的 CPU 资源,分配给优先级更高的进程运行。
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2021-02-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 飞天小牛肉 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 调度的概念
  • 2. 非抢占式进程调度算法
    • ① 先到先服务 FCFS
      • ② 最短作业优先 SJF
        • ③ 高响应比优先 HRRN
        • 3. 抢占式进程调度算法
          • ① 最短剩余时间优先 SRTN
            • ② 轮转调度算法 RR
            • 4. 最高优先级调度算法 HPF
            相关产品与服务
            文件存储
            文件存储(Cloud File Storage,CFS)为您提供安全可靠、可扩展的共享文件存储服务。文件存储可与腾讯云服务器、容器服务、批量计算等服务搭配使用,为多个计算节点提供容量和性能可弹性扩展的高性能共享存储。腾讯云文件存储的管理界面简单、易使用,可实现对现有应用的无缝集成;按实际用量付费,为您节约成本,简化 IT 运维工作。
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档