在我们日常生活中有很多的调度系统案例，个人认为计算机科学源自于生活；例如美团做的就是资源整合再利用，把商家和骑手还有顾客联系在了一起。滴滴出行也是，当一个顾客下单之后，这个订单会被发送到服务器端后台，然后这个订单被派送到附近区域的司机，在这里嘀嘀就相当于一个出行调度平台，它所调度的是汽车和司机，在计算机中调度系统也有很多应用，本篇将介绍相关的应用在操作系统上如何实现的，调度算法和策略在计算机中的应用。
在之前的博文中我介绍了一些关于操作系统的进程和线程、协程调度工作，还有内存缺页异常，内存换页算法的调度工作，日常使用的Redis缓存淘汰策略，这些都是在调度算法上的应用，在有限的资源来把多个个体充分提高利用率。
为什么需要调度
我们在使用的电脑的时候都会打开很多软件，但是如果这台电脑是一个单核的CPU，那么每一个时刻这台电脑只能运行一个应用程序，如果这时使用者打开了很多软件，那么怎么去共享CPU资源，怎么去调度这些软件，就需要调度算法来解决了。在操作系统上想做一个完美调度算法，是很难的之前的文章介绍过程序内存换页，是要根据用户打开程序和使用频率来决定的，无法通过先知的方式来调度资源，一个任务优先级，例如之前的我文章写的Go中GMP调度器实现，还有如何在有限的内存中实现比内存大N倍的程序内存占用问题，本文内容我对我自己阅读一些操作系统资料做一些记录和总结，调度器优先权，调度器如何调度？这些问题来剖析调度器设计相关的话题。
调度优先级
相信大家都去过银行办理过业务，当人流量大的时候我们去办理业务就需要去排队，业务办理窗口是有限的，但是怎么能被优先处理这些任务呢？一般的用户为VIP客户都设置单独窗口，可以让这些会员客户优先去办理业务，这就是生活优先级的概念。
计算机中的调度
在计算机中硬件资源CPU、内存、磁盘这些都是有限的，怎么把一堆程序分到CPU上执行这叫CPU调度；怎么在8GB的内存中运行16GB大小的程序，这就是内存换页调度；像CPU任务调度的方式有很多，那么怎么去衡量调度策略的好坏的标准呢？
操作系统在运行程序的时候，会把程序放到一个运行队列里面，如何通过调度算法来执行任务，基本的调度策略就是时间片策略，当CPU给每个程序分配的时间片用完之后就会被中断掉，放回队列中；另外就是遇到IO阻塞不能及时返回，或者说程序主动申请睡眠状态，那如何去做让调度器做更好的调度决策呢？调度器如何做出符合预期的调度决策呢？
衡量调度的标准
我做为一名偏向后端的程序员，大部分肯定写一些高性能的后端应用，此时的调度标准应该和请求的吞吐量、周转时间、响应时间这衡量；一些其他非性能标准：公平性、资源利用率、能耗等；
- 吞吐量指的是在某个单位时间内处理任务数量
- 周转数据任务从发起到结束所需要的时间
服务端大部分处理都是大数据批处理任务，这类任务调度要考虑的是吞吐量、请求的创建到被处理完成需要的时间。像在大数据处理领域使用的分布式计算技术例如MapReduce来降低在单机处理上时间和性能问题，并且还能充分提高资源利用，还能保证每个任务调度公平性，都能被调度的到。
对于交互应用来说需要考虑界面和用户操作时，用户关注的是当自己按下键盘或者输入一些信息，系统会不会立即被调度，做桌面应用开发的调度。还有一些做手机应用开发的要关注的是手机应用的能耗问题，如何降低能耗提升待机时间。一些智能汽车上的程序需要考虑实时性，智能汽车依靠毫米波雷达还有摄像头来处理外界信息，这里就要对实时性调度提出要求了。
综上所述想要设计一个完美的调度器几乎是不可能的，只能根据不同场景做出不同调度策略，设计调度器考虑事情实在太多，需要在各方面权衡才能设计出一个合理的调度器，也可以为了可扩充性提供二次开发接口，提供不同调度器策略来完善调度器。
调度机制
调度机制： 在Linux中也不是第一个版本设计就设计的非常完善的。操作系统都跟着CPU架构发展而发展的，单核处理器到多核心处理器的发展，就是CPU不同时间的调度器发展。
之前的文章Process Mutli Task有介绍过进程调度的几种状态，但是没有介绍具体调度方式，这里我会继续讲解具体调度功能实现。之前我文章我介绍了有介绍Go语言中GMP调度器模型在用户态下维护了一个全局队列和多个本地队列通过逻辑处理器来派发调度任务，在Linux中也是这样的，如下图：
一个操作系统会管理着用户打开多个软件的进程，这些进程要在有限的CPU和内存下进行控制和分配资源到这些运行进程上，这时就需要调度器来辅助完成工作了，一个进程生命周期如下：
首先我们分清楚进程几个状态处于在什么阶段：
- 创建态：是在程序刚刚创建完成的时候
- 就绪态：进程可以运行等待被调度时候
- 运行态：进程正在运行中
- 阻塞态：进程等待外部IO事件无法进行执行
- 终止态：进程执行完成结束
操作系统的调度器工作调度策略就是围绕着这5种状态展开的，这里我整理了Linux下的任务调度器一些调度机制，进程调度器调度方式分别为下面几种：
- 长期调度
- 中期调度
- 短期调度
这里调度策略和具体进程任务类型有关，在计算机中程序可以分为两大类：是计算(CPU)密集型应用主要是占用CPU时间较长的进程，所以要考虑到经常对处理器性能的影响和性能的限制；另外一种就是IO密集型应用，此类进程会大量使用IO设备，等待IO请求完成，阻塞会占用大部分的时间。
短期调度工作： 主要负责的是进程就绪状态、运行态、阻塞态间的转换；主要负责的工作是把就绪队列的中的任务，放到运行队列中并且设置运行状态，而处于运行态的任务会被其中断避免CPU占用时间过长，避免造成调度不公平性，如下图：
长期调度工作： 主要控制短期调度大量创建的进程，用来限制系统中被短期调度管理的进程数量，避免短期调度的开销过大，长期调度会为每个程序创建进程并且设置为就绪态，交给短期调度来管理，从理论上这就是一个阀门，有了它可以完全控制可被调度进程的数量。长期调度可以根据当前硬件资源CPU和IO设备资源使用率情况会选择适合的计算密集型或者IO密集型进程来交给短期调度使用，从而到达控制资源利用率的目的。
中期调度工作： 长期调度和短期调度一般都是从CPU和IO使用率来做出调度策略，而这里可以考虑到计算机内存是有限的，之前的文章介绍过内存换页算法，中期调度要解决的问题就是进程如果占用内存过大，如果有进程频繁触发缺页异常长时间未响应的进程就会被中期调度设置挂起状态，并且会检查内存占用和使用率情况从而做出调度决策。
3种调度方式中长期调度触发间隔是最长的，因为这个要任务类型；而中期调度触发间隔是相对频繁的，因为这个要根据任务内存使用率来观察的；而短期调度最频繁的因为要管理着不同任务的状态转换工作。
从上面进程的状态模型和进程调度方式来看话，短期调度工作主要是负责各个进程状态的变换把进程PCB从不同队列移动至其他状态队列；而长期调度主要控制的是进程的类型CPU还是IO密集型，从而控制短期调度创建的可运行进程数量；另外中期调度的所做的就是要对计算机内存使用率监测，会控制短期调度的进程对内存占用量。
调度算法
上面介绍了调度规则的几种方式，下面介绍几个具体的调度器策略的算法实现，之前的文章我讲过Go的GMP调度器实现，Go的调度器实现拥有自己的一套调度规则的策略，但是看完操作系统的调度策略算法之后会发现这些算法都是在此基础之改进的；操作系统说简单一点就是一个任务批处理器系统，维护一个任务调度队列，然后将放到CPU上执行，现在的问题CPU怎么执行这些任务？怎么公平执行这些任务？当前应该调度哪个任务？被调度的任务应该执行多久？这就是本节要说明的几种调度算法实现，目前常见的调度器算法有：
- 先进先出 (FIFO)
- 先到先得 (FCFS)
- 最短优先 (SJF)
- 时间片轮转 (RR)
这里有关任务调度两个概念要说明3个概念：
- 达到时间 任务核实被创建并且就绪状态的时间，这里一个生活中的例子就是，通知你要去做核酸，你戴好口罩到锁好门再走过去到核酸检测站，这一段时间为达到时间；而在操作系统中表示任务被创建到准备就绪队列的时间。
- 运行时间 任务从开始执行到结束所需要的时间，例如在银行窗口办理业务所花的时间；在操作系统中就是具体任务被短期调度放到CPU上运行的时间。
- 周转时间 整体任务从到达时间到完成时间所消耗的时间，例如做核酸，从出门那一刻开始算到做完结束。
FIFO和FCFS： 在日常生活中排队做核酸，排队买票这些例子，都算是这类算法的现实应用，在操作系统中的调度器实现就是维护一个全局的任务队列，然后调度器会拿取队列头部的任务并且运行，运行完成之后放到队列尾部，然后继续循环，直到每个任务生命周期结束。
FCFS 最大的好处就是实现简单很好理解，但是该算法策略没有考虑到其他因素和带有权重的任务；缺点也很明显，举一个例子：在食堂吃饭，每个人都需要排队，但是每个人所要的食物是不一样的，大部分人的食物是自己搭配饭和菜，饭和菜是已经准备好了，直接说自己需要什么就能马上打包完成；而还另外一种食物就是面，要现做，这个就比较消耗时间；通过上面例子换到计算机中就是计算密集型和IO密集型应用。
通过上面的例子很明显就能看出FCFS算法的缺点，在多种任务类型混合调度的时候，对短任务不够友好，如果光文字描述的话可能不够清晰，我画了一张图如下：
由于调度器是顺序执行这3个任务的，因为A任务请求了一次IO调度就会阻塞着直到调用返回，所以任务B和C会相应的等待到下一次才能正常执行，会影响整体的任务周转时间。
SJF 最短任务优先顾名思义就是调度器策略先调度任务队列中耗时最短的那个任务，然后以此类推，但是要调度任务的前提就是要知道任务队列中所有的任务运行时间，这一点很难实现因为每个任务类型是在计算机运行中动态产生的，这就带来了一个问题操作系统调度器无法预知到某个任务确切的运行时间，就无法达到SJF算法的最佳调度策略。
缺点是调度器依赖于任务到达的时间，如果任务达到时间存在延迟那么调度器可能就会调度其他的任务，而不是最短的那个任务进行调度的，存在任务到达时间的偏差性。
与此对应的就是STCF最短完成时间优先和SJF很像，从SJF演进过来的，也就是抢占式版本调度；SJF默认是要按照最短的任务进行调度，但是上面我也提到了调度器是按照到达时间进行任务选取的，直到一个任务执行完成才能进行下一个任务，为了解决这个问题，出现了STCF抢占式调度，调度器会主动中断在运行的任务，去执行最短时间任务，通过调度器主动放弃任务和主动执行最短任务来控制。
STCF缺点也很明显，如果系统中有大量的短时间任务，调度器会频繁执行这些短任务，而不是去执行长任务，导致长任务处于饥饿的状态。
Round-Robin 时间片轮转调度算法，在之前的几种调度算法中都是基于达到时间和任务执行完成之后才能正常调度下一个任务，并且如果某一段时间内没有新的任务到达或前任务没有执行完成，那么调度器就无法进行调度，如果此时有一个及时性相应要求高的任务就无法响应用户。
时间片轮转策略为每个任务都设置了时间片，也就是每个任务执行时间是有限的，而不是从执行一直占用着直到任务结束。限定每个任务每次被调度执行的期限，当任务时间片用完，调度器会调度其他的任务，放弃当前执行的任务，将其放回任务队列。
像上图把每个任务的调度时间片分配比较均匀，时间片也能足够的小，所有的任务都可以在一定的时间内执行并且响应用户，也不会出现前面几种调度算法的不公平性，和也不会出现长任务饥饿情况，长时间得不到调度。
小结
本文对操作系统任务调度和相关调度算法做了一些剖析，但还有很多算法没有介绍，但这些调度器策略都是在本文这些算法基础上演进的；当前个人认为最公平算法是分时间片调度，但是分时间片调度策略需要取决于时间片的生命周期，也就是每个任务执行的时间片段，如果时间片设置很小，可能会产生频繁调度切换上下文的情况，如果设置过大过长，那么任务的及时响应可能也会出现问题，得不到及时响应。所以要设计一个能充分高效的调度器策略算法，还是根据不同任务场景和一些事件需求做调整，开发者自己也要对自己所处理的任务要有所认知才能设计出好的调度器。
