进程调度算法之“先来先服务”、“短任务优先”和“时间片轮选”

时间:2022-05-25 21:13:35

        我们知道, 引入多进程后, 操作系统可以同时将多个进程载入到内存中。 如此一来, 在内存中便有多个进程存在, 但是, 对于单cpu来说, 任何一个时刻, 只有一个进程占据cpu. 那么, 为了让各个进程舒服满意, 操作系统该如何进行进程调度呢(也就是把cpu分配给谁)? 本文, 我们来介绍最简单的三个进程调度算法------“先来先服务”、“短任务优先”和“时间片轮选”。


        读初中时, 大家在吃完饭后, 都需要去洗碗, 由于水龙头比较少, 所以大家经常处于等待状态。 此时, 水龙头就相当于一个cpu, 是稀缺的资源, 每个同学需要去争它, 大家经常为争抢水龙头而打架, 那些争抢水龙头的场景, 历历在目。

        某次, 我拿了一个桶去接水, 大概要3分钟才能接满吧, 我正在接水的时候, 走来一个小伙子, 准备洗碗, 应该只需要10秒就能接满水。 没有经过我的同意, 他直接用饭碗去抢我的龙头, 结果, 饭粒就掉进我的桶里里面, 我当然很生气, 接下来的事, 我就不说了。


        为什么会产生上述的矛盾呢? 原来, 接水的默认操作是先来先服务, 我接水需要3分钟, 他接水需要10秒钟, 刚好我先来, 他自然是不乐意等待了。


        现在假设有进程A, 需要3分钟执行完毕; 有进程B, 需要 10秒执行完毕。  进程调度算法为先来先服务。 

        如果进程A先抢到cpu, 那么进程A自然是很happy的, 但进程B估计该骂脏话了, 心想, 还要等3分钟, 我才能执行, 我不干。

        如果进程B先抢到cpu, 那么进程B自然是很happy啊, 此时, 进程A并不会太恼火, 因为进程A心想, 我大不了就等10秒钟再执行。

        在进程A先到的情况下, 先来先服务的进程调度机制极不合理, 所以, 迫切需要做出改变。


        进程B自然想, 要是耗时短的先执行, 那该多好啊。 对了, 这个就是短任务优先的调度算法。 这样, 进程B满意了, 10秒钟就搞完了, 进程A也没有啥不满意的。


        但是, 进程A真的满意么? 如果进程A的脾气比较臭, 它自然不爽啊, 心想: 我先来, 凭什么让你这个B进程先享受服务? 所以, 进程A想: 为了公平起见, 每个人用cpu 5秒钟, 然后把cpu归还给对方使用。 这就是所谓的时间片轮选的调度算法。

        进程B听了这话, 还是比较高兴的, 因为即使进程A先来, 进程B也可以在20秒钟之内完成任务。 而进程A呢? 也不用长期饥渴地等待, 也让cpu间隔5秒滋润一下自己的心灵。



       其实, 上述的一些进程调度算法各有优缺点, 我们也仅仅是举了三个简单的例子进行说明, 实际上,调度算法还有很多种, 比如优先级调度算法、混合调度算法等等, 总之, 进程调度算法需要综合考虑:尽可能最小化平均效应时间、最大化系统吞吐率、保持系统各个部分处于繁忙状态。 毕竟, 谁愿意看到你闲呢?