想要资源吗？求我啊~

调用处理器调度程序的前提是进入操作系统，处于系统态。而之前在中断中提到，中断是进程切换的前提，换句话说，操作系统是中断驱动的。

处理器调度

处理器调度：CPU资源在可运行实体之间的分配。

在之前的进程和线程中提到过一点，进程是CPU分配的基本单位，线程是CPU分配的基本单位，看起来似乎是有冲突，但实际上，操作系统可见的线程是系统级的线程，也就是说，如果线程是在用户级实现的，那么操作系统实际调度的实体仍然是进程。（判断哪一个是CPU的基本调度单位，只需判断该系统是否支持核心级的线程）

短程调度

短程调度是将处理器资源分配给进程或线程使其真正向前推进。

先解释几项参数指标：

1. 对处理器的一次连续使用称为CPU阵发期，对设备的一次连续使用称为I/O阵发期。 （可以简单的理解为使用处理器/设备的时间）

2. 从计算任务就绪到处理完毕所用的时间称为周转时间。

3. 所有作业周转时间与作业道数的比值称为平均周转时间。（可以理解为到当前计算任务为止的每个计算任务所需周转时间之和除以这些计算任务的总数）

处理器调度算法

1. 先到先服务（FCFS）

   按照进程申请*CPU的顺序*进行调度。

   是一个公平的算法，不会出现饿死的情况，但是缺点是短进程（线程）等待时间长，平均等待时间较长。

   和生活中买票场景相类似（假设售票处的票数无限），所有人都排队买票，谁到的早，谁就能先买票。

   每人买一张票消耗一分钟，假设有人只买一张，有人要买几十上百张票，此时，后到的买一张票的人会等很久，致使最终所有排队的人平均等待时间长。

2. 最短作业优先（SJF）

   按照CPU阵发时间递增的次序调度，平均周转时间短，且是不公平的，故而可能发生饥饿甚至是饿死。

   还是售票场景，此时排队不是按照先来后到的顺序，而是按照每个人所要购买票的数量进行排队，购票数量少的排在前面，这样做的后果是，购票数量多的人很可能要等很久，甚至因为前面的人太多而放弃购票。

3. 最短剩余时间优先（SRTN）

   当CPU空闲时，选择剩余执行时间最短的进程或线程，新进程或线程到达时，比较与当前运行进程的估计剩余时间，选择剩余时间最短的进程或线程。可以看出，此算法实质上是可剥夺式的的最短作业优先算法，不公平。

   继续买票排队，首先售票开始时，只有一个人需要买3张票（买一张票假设需要一分钟），一分钟后来了第二个人要买一张票，此时第一个人还需要买两张，比第二人的一张要多，故第二人可以插队买一张票（买完走人），此时第三个人来了，需要买三张票，比第一人剩下的两张要多，故第一人可以买完两张走人，第三人开始买票。

   有图有真相：

   

4. 最高响应比优先算法（HRN）

   是先到先服务和最短作业优先算法的折中方案，按照公式计算响应比，然后进行调度。

   响应比 = 1 + （等待时间 / CPU阵发时间）

   可以看出，同时到达的任务中，处理时间较短的任务将会被优先调度。

5. 最高优先数优先算法（HPF）

   为进程分配等级，用数字大小决定优先级别。

   优先数有两种方法确定：

   • 静态的优先数：每个进程进入系统时就被赋予了一个优先数，且在其生存期间是固定不变的，可以看出这种方法省时省力，但是公平性很差（低优先级的进程可能会长期等待）。
   • 动态优先数：每个进程创建时有一个优先数，但是在进程生存期间是可变化的，对应于静态优先数的优缺点，可以看出这种方法公平，资源利用链率高，但频繁变化，系统开销就大了。

6. 循环轮转算法（RR）

   和分时系统的部分思想有些类似，在这种算法中，系统会为每一个进程规定一个时间片，所有进程按照时间片的长度轮流运行（分配给就绪队列中的每一个进程一个时间片，不论进程能否在这段时间内执行完成，都会被掐断，如果能够执行完成，那就没有多余动作，如果不行，则掐断进程，将其放到队尾等待下次分配）。

   循环轮转还有分基本轮转和改进轮转，两个轮转的区别就在于分配给进程的时间平长度是否相同，是否可变长。

   这种算法很公平，而且响应及时，但是时间片的长度是必须要认真考虑的，否则胡乱分配，其好处就无从体现了。

   记得小时候在家做作业想看电视，老妈有规定，做一个小时作业，看半小时电视，看电视的时候，不论是不是看到精彩的地方，或者是还有几十秒电视剧就演完了，老妈都会很准时的让我去写一个小时作业再说。

   这就是循环轮转算法的一种思想体现（看来我很小的时候就已经接触过这种算法了，话说，如果老一辈的人把这种思想早点弄到计算机上，那是不是就没外国人啥事儿了）。

7. 分类排队算法（MLQ）

   按照某种原则（如实时，分时等）加以分类，以实现所期望的调度目标，可以说，这个算法是以多个就绪进程队列为特征的。

   队列之间是顺序执行的，但是队列内部可以采用不同的算法来调度。

   高中的时候每年都有运动会，开幕式挺烦人的，想想看全校30多个班，领导在主席台上舒服的坐着，从高一1班开始，一直到高二16班，30多个班都要依次从体育场大门进场，途经主席台，绕着跑道走一圈到各班的位置，站着……

   按照班级分类，各班级之间是有序的，班级内部的人员调动那是班主任（调度算法）说了算，这就是分类排队的思想。

8. 反馈排队算法（FB）

   都是排队算法，这个也是以多个进程就绪队列为特征的，且每个队列通常都是采用循环轮转算法，不过，在反馈排队算法中，进程是可以在不同的就绪队列中移动的，适应性强。

   由于进程可以在就绪队列中移动，所以这些就绪队列需要设置优先级，而且优先级是递减的，即有这种情况：

   一个进程被创建 -> 进入第一级就绪队列 -> 使用完这一队列的时间片，未结束 -> 进入下一级队列

   注：如果到了最后一级队列还没结束，就进入同一级的就绪队列，这种算法有几个特点：

   • 短进程优先处理。
   • 设备资源利用率高。
   • 系统开销小。

你以为我要讲故事呢啊，可笑！

好吧，接收嘲讽……高一某次运动会，由于长的帅，腿又长，还跑的快，于是被老师指定参加4x100接力赛，我当第一棒，枪响，冲刺，一切都进行的那么顺利，然而，当我跑到和第二棒交接的地方时，第二棒的小朋友刷的就冲出去了，最后回头望了一眼发现我还在后面追才反应过来自己没接上棒，这时候我都已经跑了四分之三的路程了。

这4x100就分给每人一百米的距离，我这都跑完分配给自己的路程了，最后还多占着第二棒的路程多跑了几十米。

这种情况就是由于一些原因致使进程无法在系统分配的时间片内结束，而移动到下一进程的队列里继续执行。

中程调度

交换

交换是进程在内存和外存储器之间的调度，其目标是：

1. 缓解内存空间等资源紧张的矛盾。
2. 减小并发都以降低系统开销。

由于交换是在内存和外存之间进行的，所以当进程被换到外存时，就出现了挂起态（就绪挂起，等待挂起）。

系统并发都过高时，将内存中的某些进程暂时交换到外存（挂起），直到系统并发度较低时再调回内存（解挂），这种交换也必须依据调度算法（好烦哦）。

长程调度

作业

长程调度又称作作业调度，对应的功能是，将一个作业由输入井调入内存，并为其建立相应的进程，使其具有运行的资格。

一个作业是由多个相对独立的执行步骤组成的，这些步骤被称为作业步 ，对应一个进程或线程。

作业有五种状态，分别是： 1. 提交 2. 后备 3. 执行 4. 完成 5. 退出

其状态之间的改变如图：

其中，SPOOLing输入/输出对应假脱机输入/输出，两段作业调度程序通常以系统进程的模式运行。

实时调度

实时调度需要满足实时任务各自时间约束条件，有剥夺式和非剥夺式两种。

实时调度分为随机性实时任务 ，由随机事件触发，发生时刻不确定。周期性实施任务 ，隔固定时间发生一次。

几项相关参数：

• 就绪时间：实施任务产生并可以开始处理的时间。
• 开始截止期：实施任务最迟开始处理的时间。
• 完成截止期：实时任务最迟完成的时间。
• 发生周期：发生周期性实时任务的间隔时间。

有一个小公式（必要条件）可以用来判断多个周期性实时任务是否可调度。

其中Ci 为任务 Pi 的处理时间，Ti 为任务 Pi 的发生周期，Ci < Ti， i = 1,2,3…,n。

最早截止期优先调度（EDF）

该算法优先选择完成截止期最早的实时任务，类似于最短剩余时间优先算法，对于某个新到达的实时任务，如果其完成截止期先于正在运行任务的完成截止期，则重新分配处理器（剥夺）。而上述的小公式对于该算法而言是充分条件。

速率单调调度（RMS）

该算法面向周期性实时任务，是非剥夺式调度。该算法判断多个周期性实时任务可调度的条件是：

RMS算法CPU利用率不如EDF算法，但是RMS算法省事（实现简单，开销小）。