专栏首页苦逼的码农三分钟基础:有哪些经典的进程调度算法?

三分钟基础:有哪些经典的进程调度算法?

来源:tobe的呓语

作者:tobe

我是一个进程调度器。

我的职责是调度计算机内所有的进程,为他们分配 CPU 资源。

1. 批处理时代

想当初,操作系统创造我时,只是打算让我用 FCFS 调度算法,简单维护下进程的秩序。但我后来的发展,远远超过了他的想象。

1.1 FCFS

所谓 FCFS 就是「先来先服务(First Come First Serve)」,每个进程按进入内存的时间先后排成一队。每当 CPU 上的进程运行完毕或者阻塞,我就会选择队伍最前面的进程,带着他前往 CPU 执行。

就拿这几个进程来说吧:

按照 FCFS 算法,我就会就按 A,B,C,D,E这样的顺序来将他们送往 CPU:

这一算法听起来简单又公平,然而好景不长,我收到了一个短进程的抱怨:”上次我前面排了一个长进程,等了足足 200 秒他才运行完。我只用 1 秒就运行结束了,就因为等他,我多花了这么长时间,太不值得了。”

我仔细一想, FCFS 算法确实有这个缺陷——短进程的响应时间太长了,用户交互体验会变差。

所以我决定,更换调度算法。

1.2 SPN

这次我设计的算法叫做「短任务优先」(Shortest Process Next,SPN)。每次选择预计处理时间最短的进程。因此,在排队的时候,我会把短进程从队列里提到前面。

这一次,短进程得到了很好的照顾,进程的平均响应时间大大降低,我和操作系统都很满意。

但长进程们不干了:那些短进程天天插队,导致他们经常得不到 CPU 资源,造成了「饥饿」现象。

取消 SPN 算法的呼声越来越高。

这可是个大问题。FCFS 虽然响应时间长,但最后所有进程一定有使用 CPU 资源的机会。但 SPN 算法就不一样了,如果短进程源源不断加入队列,长进程们将永远得不到执行的机会——太可怕了。

因此,短任务优先算法需要得到改进。有什么方法既能照顾短进程,又能照顾长进程呢?

1.3 HRRN

经过和操作系统的讨论,我们决定综合考量进程的两个属性:等待时间和要求服务时间——等待时间长,要求服务时间短(就是短进程)的进程更容易被选中。

为了量化,我们制定了一个公式:响应比 = (等待时间+要求服务时间)/ 要求服务时间。响应比高的算法会先执行。我们称之为「高响应比优先」(Highest Response Ratio Next,HRRN)。

这个算法得到了长短进程的一致好评。虽然我的工作量增加了(每次调度前,我都要重新计算所有等待进程的响应比)但为了进程们的公平性,这一切都是值得的。

2. 并发时代

新时代到了。

随着计算机的普及,个人用户大量增长,并发,即一次运行多个程序的需求出现了。这可难倒我了——处理器只有一个,怎么运行多个程序?

所幸 CPU 点醒了我:“我现在的运算速度既然这么快,何不发挥这项长处,弄一个「伪并行」出来?“

“伪并行?什么意思”

“就是看起来像并行,实际上还是串行。每个进程短时间交替使用我的资源,但在人类看来,这些进程就像在「同时」运行。”

我恍然大悟。

2.1 RR

经过 CPU 的提醒,我很快制定出了新的调度算法——时间片轮转算法(Round Robin,RR)。

在这个算法里,每个进程将轮流使用 CPU 资源,只不过在他们开始运行时,我会为他们打开定时器,如果定时器到时间(或者执行阻塞操作),进程将被迫「下机」,切换至下一个进程。至于下一个进程的选择嘛,直接用 FCFS 就好了。

新的算法必然会面临新的问题,现在我的问题就是,时间片的长度怎么设计?

直观来看,时间片越短,固定时间里可运行的进程就越多,可 CPU 说过,切换进程是要消耗他不少指令周期的,时间片过短会导致大量 CPU 资源浪费在切换上下文上。时间片过长,短交互指令响应会变慢。所以具体怎么取,还得看交互时间大小(感觉像没说一样,但至少给了个标准嘛)。

这一阶段,我的工作量大大提升——以前十几秒都不用切换一次程序,现在倒好,一秒钟就得切换数十次。

2.2 VRR

时间片轮转算法看起来十分公平——所有的进程时间片都是一样的。但事实真是这样吗?

I/O 密集型进程不这么认为,他对我说:“调度器大哥,时间片轮转没有照顾到我们这类进程啊!我们经常在 CPU 没呆到一半时间片,就遇到了阻塞操作,被你赶下去。而且我们在阻塞队列,往往要停留很长时间。等阻塞操作结束,我们还得在就绪队列排好长时间队。那些处理器密集型进程,使用了大部分的处理器时间,导致我们性能降低,响应时间跟不上”

考虑到这些进程的要求,我决定为他们创建一个新的辅助队列。阻塞解除的进程,将进入这个辅助队列,进行进程调度时,优先选择辅助队列里的进程。

这就是「虚拟轮转法」(Virtual Round Robin,VRR)。

从后来实际性能结果来看,这种方法确实优于轮转法。我颇为自豪。

2.3 优先级调度

有一天,操作系统忽然找到我,神神秘秘的说:“调度器啊,你是知道的,我要给整个系统提供服务,可最近用户进程太多,导致我的服务进程有时候响应跟不上。我有点担心这会给系统稳定性造成影响。”

我一听,这可是个大事,系统不稳定那还得了?调度算法得换!

既然要让操作系统的服务得到足够的运行资源,那就,干脆让他们具有最高的 CPU 使用优先权吧。

优先级调度算法就此产生了。

我向大家做出了规定——每个进程将被赋予一个优先级,自己根据自己的情况确定优先级数值,但是,用户进程的优先级不准高于内核进程的优先级。

切换程序的时候,我会从优先级 1 的队列里选择一个进程,如果优先级 1 队列为空,才会选择优先级 2 中的进程,以此类推。

当然,为了保证低优先级进程不会饥饿,我会调高等待时间长的进程的优先级。

使用这个算法,我更忙碌了,不仅需要大量切换进程,还需要动态调节优先级。可能这就是能力越大,责任越大吧。

不过我知道,正是因为我的存在,人类才能在计算机上运行多道程序——这令我感到自豪。

希望你在看完我的文章之后有所收获。

本文分享自微信公众号 - 苦逼的码农(di201805)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 经典面试题-什么是java序列化,如何实现java序列化?

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • day85- <缓存+序列化+信号+ORM性能相关+随机验证码>

    天下第六
  • 在命令行进行sort排序【Linux-Command line】

    使用sort命令重组数据,可以从Linux,BSD或Mac终端以对你有意义的格式进行。

    QRosie
  • 记一次内存泄漏排查

    httpclient一只read time out,使用jmx 产看内存是每天都在上升的。

    OPice
  • Jmeter 参数化的多种方式

    其中,参数含义如下: Filename:引用文件地址,可以填相对路径或绝对路径。相对路径的根节点是Jmeter的启动目录,如果测试执行是分发到多台远程负载机上...

    软测小生
  • 「玲珑宝塔」优化 Apk 包大小

    如今的 5 G 也在万众瞩目瞩目下翩翩起舞,而 Android 近些年也惹得不少争议,所谓的谣言,不过尔尔。

    HLQ_Struggle
  • Java序列化与反序列化中,你可能会忽略的细节知识点

    在很早之前学习序列化的时候有写过一篇关于Java序列化的博客,不过那只是简单的使用,入门者欢迎移步:http://blog.beifengtz.com/arti...

    beifengtz
  • 经典面试题-序列化的作用,应用场景

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • 视频编码零基础入门

    像素点的英文叫Pixel(缩写为PX)。这个单词是由 Picture(图像) 和 Element(元素)这两个单词的字母所组成的。

    鲜枣课堂
  • 如何化解产品和技术部门之间的矛盾

    说成矛盾,一则感觉尖锐了些,其次我来谈这个问题,有点行外人看行内人的感觉。但是运维部门和业务部门之间也同样存在在结果期望上的矛盾,毕竟"多快好省"的服...

    用户1593318

扫码关注云+社区

领取腾讯云代金券