【操作系统】从一个生活中的场景讲进程的调度

其实计算机科学中的很多策略、协议等等往往来源于生活，又高于生活（嗯，和艺术一样）。比如说Redis Cluster中的使用的Gossip协议，就是基于了生活中的八卦传播模型。那么今天要探讨是操作系统中对于进程的调度。

首先安利一下我觉得很不错的操作系统原理视频：https://www.bilibili.com/video/BV12W411W7nT?p=21，其中p19-p24为进程调度的相关片段，有兴趣的话可以结合本文一起品一品。

那么我先从一个生活中的场景来讲进程的调度：

超市中很多人在排队结账：

那么从这种只买了一瓶饮料的先结账想开去，假设我作为收银员可以任意调整排队人群的结账顺序（只是假设，生活中一般是不能调整的），我该如何保障一个较好的结账体验呢？

首先我们需要设定一些关于“好”的结账体验的标准，从而客观地进行评价：

那么我们可以采用哪几种策略呢？

先来先结，即First Come First Service —— 这是一个公平的策略，但是对于短任务不友好：比如我只买了一瓶水，但是前面有很多大批采购的人在排队，我可能要等半小时，那我不如去街边小店买了；
短任务优先，即Shortest Job First —— 该策略对短任务友好，可以获得更高的吞吐量和更短的平均周转时间，但是可能造成长任务的“饥饿“：这个收银员总是让买了一瓶水的人先结账，而且总是有人来买水，那我作为大批量采购的就一直没开始结账，就很生气；
最高响应比，即Highest Response Rate Next —— 响应比=已等待时间/执行所需的时间；该策略很好地平衡了长短任务各自的需求（策略很简单但是很优雅地解决了长任务”饥饿“的问题）：
--对于短任务而言，它的执行时间即分母较小，所以可以获得较高的响应比，优先执行；
--对于长任务而言，它的分母较大，所以一开始可能会进入等待状态，但是随着等待时间的增长，分子变大，从而获得较高的响应比，也开始执行 —— 这样有效地避免了长任务的饥饿状态；

以上是结合超市购物结账的场景简单讲述了一下OS中的几种进程调度策略：FCFS，SJF，HRRN。其实在OS中的情况会更加复杂一些，所以还有以下几种策略：

优先级调度：根据进程的类型（比如系统进程优于用户进程）、响应比等参数动态设置进程的优先级，优先级高的进程可以抢占优先级低的进程的CPU资源；该策略的问题在于低优先级的可能产生’饥饿‘
时间片轮转 Round Robin：设置一个时间片，比如10ms，进程执行完一个时间片之后如果仍未结束就到队列尾重新排队；该策略的问题在于对于IO密集型进程不友好，因为它们频繁需要等待IO结果，每次等待都需要重新排队，周转时间较长；
多级反馈队列 Feedback：这也是目前大多数OS中采用的调度策略，它是Round Robin和优先级调度的结合：
-- OS中设置多个进程的就绪队列对应不同的优先级，优先级越高则执行的时间片越小
-- 按照队列优先级从高到低执行
-- 队列内部采用Round Robin策略，当进程用完时间片后会降低它的优先级从而获得更大的时间片继续执行 => 对于CPU密集型不友好，可能持续降级，在低优先级队列中“饥饿”
-- 针对IO密集型的任务优化：如果是因为等待IO使得进程进入阻塞态后，该进程不会被降级，也不需要重新排队；当IO完成后，它将可以继续在队列头来执行；

同时由于目前CPU大部分为多核架构，在设计进程调度策略时还需要考虑多核的场景：

以上就是进程调度的全部内容拉，总结一下：

调度策略评价标准

FCFS：先来先服务，对短任务不利
SJN：总是优先处理短任务，长任务可能产生饥饿
HRRN：响应比=等待时间/执行时间，在SJN的基础上优化了长任务的饥饿问题
优先级调度：根据进程类型和响应比动态设置进程优先级，低优先级任务可能产生饥饿
Round Robin：时间片轮转，每个进程用完一个时间片后重新排队，对IO密集型任务不友好
多级反馈队列：为大多数操作系统采用的进程调度才略，结合了优先级和Round Robin策略，并且针对IO密集型任务做了优化，可能导致CPU密集型任务频繁降低优先级从而产生”饥饿“