苦13的生活：
最近一边实习一边忙于复习以前学过重要课程，上周过了一遍计算机网络，这周就一直在温故操作系统了，下周准备进行数据库，再下周估计我人已经没了……不过有一说一，对照着以前学习时做的思维导图，复习起来果然还是很快的，那时候也确实在 OS 这门课上下了不少功夫，本来不准备再写文章了，但是无意间看到了以前做的关于处理机调度的 PPT 还有演讲的文档，感觉这块内容还是值得搞一搞的 😏
走起~~先来分享下以前上课时做的思维导图吧（基本把课上学到的知识都罗列了出来，OS 博大精深哪，还有好多东西了解未甚）
上边的每一项如果展开来讲那都是一个漫长的“故事”呀，不过今天我就仅仅和大家简单的分享下处理机调度这一知识点以及我对它这方面知识的理解，小弟也是才疏学浅（站在大佬们的肩膀上），如遇理解不当之处，也望诸位大佬们加以指点呀。
今天主要给大家分享下：
处理机调度相关概念：作业调度、内存调度、进程调度 处理机调度算法
重点我就放在对调度过程的理解上吧，对于调度算法我就稍微罗列一下，但是我会在文末会为大家推荐一个大佬写的超级超级详细的关于调度算法的文章，看完巨佬的文章如果你还不理解你就来找我（让我打一顿哈哈）好了，闲话少说，圆规正转~~
概述
首先我们来打个问号——为什么需要处理机调度？？
原来是因为在多道程序环境下，内存中存在着多个进程，那么进程的数目往往是多于处理机数目的，所以系统要按照一定的算法调度这些进程，然后给它分配处理机使它能够执行。
如果按级别给处理机调度划分层次的话，它可以分为高级调度、中级调度和低级调度；如果按照调度的对象来划分的话，可以分为作业调度、内存调度和进程调度；如果按照调度的运行频率的高低来划分，可以分为长程调度、中程调度和短程调度。
？？？什么？怎么这么多调度？
其实不是的，这里的调度只有三个，只不过是按不同的划分方法叫不同的名字罢了，高级调度 = 作业调度 = 长程调度，中级调度 = 内存调度 = 中程调度，低级调度 = 进程调度 = 短程调度。
如果你还是不太了解话，那就先看一下下面这个处理机调度的概念图，这个图基本上描述了调度过程中参与的对象以及状态转换过程。建议大家把这张图熟记于胸，因为我就开篇一张图，其余全**（当然是分享下我的理解😁）。
作业调度
按照上面的图中的顺序，我们先来看一下作业调度（高级调度/长程调度）。
顾名思义，作业调度操作的对象是作业，此时有人可能就会问：处理机也要像老师一样批改作业？
哈哈，此作业非彼作业——
此处的作业它表示的是一个比程序更广泛的意义，它既包含了程序和数据，同时还配有一份作业说明书，系统就是根据说明书来对程序的运行进行控制。每当一个作业进入系统时，便会有“作业注册”程序为这个作业创建一个 JCB（Job Control Block，作业控制块），JCB 中包含了系统对作业管理和调度所需的全部信息，其中也包含它的类型，系统就会根据这个类型将它放到相应的后备队列（外存）中等待作业调度。
在批处理系统中，作业是从外存调入内存的基本单位。
作业调度就是按照一定的算法从后备队列中挑选一个或多个作业，给它们创建相应的进程（也即建立进程控制块 PCB）、分配内存等必要资源，然后将它们放入就绪队列（内存）中，以等待进程调度。作业调度主要任务就是接纳多少个作业，接纳哪些作业。接纳多少作业取决于内存中允许多少个作业同时运行，这个也称作多道程序度；而接纳哪些作业就涉及到调度的算法了，这里常用的调度算法有：
先来先服务（FCFS） 短作业优先（SJF） 优先级调度算法（PSA） 高响应比调度优先调度算法（HRRN）
具体的算法内容就先不在这里展开讲了，见文末推荐的文章吧。
作业调度主要用于多道批处理系统，在分时和实时系统中不设置作业调度。因为分时系统为了做到及时响应，用户通过键盘输入的命令或数据等会被直接送入内存，因而无需配置作业调度机制，但是它也需要设置某种接纳控制措施来限制进入系统的用户数目。类似地，实时系统中也不需要作业调度，但是必须要有接纳控制措施。
进程调度
进程调度是运行频率最高的调度，分时系统中通常仅 10~100 ms 便进行一次，这也是为什么叫它短程调度。
进程调度操作的对象是进程（或内核级线程），它主要的功能是根据调度算法，决定就绪队列中的哪个进程应获得处理机，然后由分派程序将处理机分配给被选中的进程，因而它是最基本的一种调度，在多道批处理系统、分时、实时系统中都必须配置。
进程调度的时机
就绪队列中存在多个进程，它的数目是多于处理机的数目的（这里我们假设只有一个 CPU），类似于作业调度，我们也需要按照一定的调度算法来决定给哪个进程分配处理机让它执行。不过在这之前，我们需要先了解一下什么时候才会引起进程调度？也就是说，什么时候才会使用进程调度算法来选取进程分配处理机呢？
处理机调度有一个共同的目标就是尽量提高资源利用率，即应使系统中的处理机和其它资源都尽可能地保持忙碌状态。
我们在上图中也可以直观地看出，如果当 CPU 中没有进程在运行时，那么就应该给它分配新的进程，不要让它闲着。所以，当正在运行的进程放弃处理机之后，就会引发进程调度，如果非要问具体什么时候进程才会放弃处理机，这里总结了一张图：
理解中断：中断是指计算机运行过程中，出现某些意外情况需主机干预时，机器能自动停止正在运行的程序并转入处理新情况的程序，处理完毕后又返回原被暂停的程序继续运行。
进程调度的任务
假如此刻由于上图中的某种原因，使当前运行的进程放弃了处理机，那么从此刻到为处理机分配新进程的这段时间里，也会发生一系列操作：
首先当前进程运行完毕，需要保护处理机的现场信息，即记录当前进程运行的一些状态信息，保存程序计数器、通用寄存器里的内容等至 PCB 中； 接下来才是使用进程调度算法从就绪队列中选取新的进程； 把处理机分配给选取出来的新进程，然后将此进程 PCB 中保存的处理机现场信息装入处理机的相应寄存器中，并把处理机的控制权交给该进程，让它从上次的断点处开始运行。
进程调度的机制
从进程调度任务里我们了解到新调度发生的三个大致步骤：保护现场、选取进程、分配进程。如果再放大一下进程从就绪队列到 CPU 的这段过程，我们就会对这块知识理解的更加深刻一些。
如上图所示，进程调度机制中有三个基本部分：排队器、分派器和上下文切换器。它们组成了调度程序，专门用以处理进程调度。
排队器是为了提高进程调度的效率，每当有一个进程转变为就绪状态时，排队器就会按照一定的策略将它插入到相应的就绪队列中，以便调度程序能够最快地找到它。
分派器是在调度程序选出进程以后，分派器就把这个进程取出来，然后进行分派器到新进程的上下文切换，把处理机分配给它。
上下文切换器：在对处理机进行切换时，会发生两对切换——
① 正在运行的进程和分派器程序之间的切换。当保存了处理机的现场信息后，正在运行的进程就会被移出，然后处理机装入分派程序运行。
② 分派程序和新选出的进程之间的切换，把分派程序的上下文移出来，然后再装入新进程，恢复其 CPU 的现场信息，使它能够执行。
进程调度的方式
非抢占方式，又称非剥夺调度方式：只允许进程主动放弃处理机，在运行过程中即使有更紧急的任务到达，当前进程依然会继续使用处理机，直到该进程终止或要求进入阻塞态。
它的优点是实现简单，系统开销小，但是却无法及时处理紧急任务，只适合早期批处理操作系统。
抢占方式，又称剥夺调度方式：当一个进程正在处理机上执行时，如果有一个更重要更紧急的进程要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要更紧急的那个进程。
但是抢占方式也不是随便就发生的，它也需要满足一定的条件或符合抢占原则，如：优先权原则、短进程优先原则、时间片原则等。
它的优点是可以优先处理更紧急的进程，但是抢占方式比较复杂，系统开销大，适合分时操作系统、实时操作系统。
进程调度算法
最后我们再来谈谈进程调度算法，也正是由于进程调度的频率之高，应当避免调度本身占用 CPU 太多时间，所以一般不用太过于复杂的调度算法。
上述作业调度算法的思想也都可以用在进程调度上，除此之外，进程调度还有一些特有的调度算法，综合起来，常见的进程调度算法有：
先来先服务(FCFS) 短进程优先(SPF) 优先级调度算法(PSA) 高响应比优先(HRRN) 时间片轮转调度算法(RR) 多级反馈队列(MFQ)
这些进程调度算法都是为了适用于不同的场景而设计的，有的是为了照顾服务时间较短的进程，有的是为了照顾等待时间较长的进程，还有把二者综合考虑的调度算法。
调度的算法的目标
在上面我们也提到过，处理机调度算法有个共同的目标就是尽可能地提高资源利用率，除此之外，它还有其它一些要求，在这里我们一起梳理一下：
提高资源利用率：就是使系统中的处理机和其它的资源都尽可能地保持忙碌状态而减少它的空闲等待时间。CPU 利用率 =
公平性：它指每个进程都能获得合理的 CPU 时间，不会发生饥饿现象。但是公平性是相对的，即相同类型的进程能够获得相同的服务；对于不同类型的进程，由于它们的紧急程度和重要性不同，则会提供不同的服务。 平衡性：这一点强调的是调度算法应尽可能地保持系统资源使用的平衡。例如计算型的作业需要用到 CPU，I/O 型作业需要用到 I/O 设备，那么调度算法就要尽可能地使 CPU 和外部设备都能经常处于忙碌状态。（系统资源从大方面可以分为四类：处理机、存储器、I/O 设备和文件） 策略强制执行：它是指强制执行某个策略，比如安全策略等。
对于批处理系统，用户程序都是以作业为单位进行调入与处理的，所以对它有一些额外的目标要求：
平均周转时间短。周转时间是指从作业被提交给系统开始，一直到作业完成为止的这段时间。 周转时间由多个时间段组成：在后备队列中的等待时间、在就绪队列中的等待时间、在 CPU 中的执行时间、等待事件时间，如果你已经对文章的第一张图了然于胸，那么这几个时间段很容易就可以 get 到。而平均周转时间就是所有作业周转时间之和再除以作业数目。 系统吞吐量高。即要求单位时间内能够处理更多的作业。
补充：
带权周转时间是作业的周转时间与系统为它提供的服务时间之比。比如：A 作业的周转时间为 100，它的服务时间为 20，那么它的带权周转时间就是 100 20 = 5.
平均带权时间就是对带权周转时间求平均值。
最后对进程调度进行一下总结：
内存调度
内存调度也称为中级调度，它的主要目的是提高内存的利用率和系统吞吐量，把那些暂时不能运行的进程调至外存，进程处于挂起状态，当它们具备运行条件并且内存又有空闲的时候，再由中级调度调回就绪队列。再来看一下咱们的开篇第一图：
首先在这里我们需要注意进程的两种状态——挂起和阻塞
两种状态都是暂时不能获得 CPU 的执行权，但是挂起状态是将进程实体调到外存去，而阻塞状态下进程实体还在内存中。
这里需要说明的一点是，挂起状态的进程虽然被调至了外存，但是进程的 PCB 没有被调到外存，进程的 PCB 是存储在系统内核空间里的，并且 PCB 中会记录进程数据在外存中的位置以及状态等信息，操作系统就是通过内存的 PCB 来保持对各进程的监控、管理。
进程实体：程序段、数据段、PCB
在操作系统中，进程阻塞（block）与唤醒（wakeup）、挂起（suspend）与激活（active）都是用原语操作的（要么全部执行、要么全部不执行），而且要成对出现，即如果阻塞了进程，则必须要在某处执行唤醒操作，不然此进程会一直处于阻塞状态而得不到执行。挂起和激活也是如此。
在上图中我们可以看到，就绪队列中的进程可以被直接调入就绪挂起队列，或者处于阻塞队列的进程能被调入阻塞挂起队列。引起进程挂起的原因有很多，如终端的需要、操作系统的需要、父进程的调用等等。
进程一旦进入挂起状态（就绪挂起或阻塞挂起），就需要经过中级调度才能重新进入就绪队列，而且从图中我们也可很容易的看到，中级调度参与的双方是就绪挂起队列与就绪队列，如果一个进程从阻塞队列进入了阻塞挂起队列，它就必须等到相应事件出现并调入就绪挂起队列后，才能在下次事件出现时被调入就绪队列。（多看图就自然理解了）
当然还有这样一种情况：在阻塞队列中的进程被 suspend 原语放入了阻塞挂起队列，如果在某时刻对此进程执行了 active 激活，那么它就会重新回到阻塞状态，然后等待事件出现重新进入就绪队列。
引入了挂起与激活之后，进程的状态就会变得更复杂，下面是一张进程的状态转化图，希望对大家的理解有帮助。
调度算法总结
有人问操作系统学什么，抱怨那些底层知识学起来枯燥且无聊，我一开始也是这么认为，感觉太抽象，但是学着学着就发现有些内容还是蛮有意思的，调度算法就是其中之一。
我们并不是要死记硬背某种算法是怎么实现的，而是要从设计者的角度来思考它的思想、为什么要这么设计。
而且我感觉这些算法思想和我们日常生活现象也紧密相关联，比如先来先服务调度算法，不就是我们在食堂打饭时同学们排队去取餐吗；还有磁盘调度算法中的电梯算法，不就和现实生活中电梯的运行流程一致的嘛，以至于现在乘电梯时，都会不由自主地想到这个算法。所以说这些东西还是很有意思而且值得去深入学习思考的。
好了，关于操作系统中比较重要的调度算法，我就给大家推荐一篇文章——作者：小林Coding（我可是小林大佬的小迷弟，大家可千万别给我争），文章链接（点击访问）：👉大厂面试爱问的「调度算法」，20 张图一举拿下，干货满满：
大家赶快去关注收藏一波吧，再发一遍：大厂面试爱问的「调度算法」，20 张图一举拿下
（ps：哈哈，处理机调度——看我这一篇还不够，还得再来一篇）
参考书籍：
计算机操作系统（第四版），汤小丹 梁红兵 哲凤屏 汤子瀛 著，西安电子科技大学出版社
我是阿数，葛立恒数的数，我们下期再见。
「分享、点赞、在看」
