多道程序环境中，作业被提交后必须经过处理机调度才能执行。

　　在多道程序系统中，根据一定的算法（公平、高效）将处理机重新分配给就绪队列中的进程去执行，以实现进程并发执行的过程；

　　调度的前提是，进程的数量往往远大于处理机个数，造成进程争用处理机的现象，所以需要将处理机资源在不同的进程间调度

1、处理调度层次

1.1、低级调度(进程调度)

1.1.1、概述

　　低级调度也被称为 进程调度 或 短程调度。进程调度是最基本的一种调度。

　　进程调度的主要问题就是采用某种算法合理有效地把处理机分配给进程，其调度算法应尽可能提高资源的利用率，减少处理机的空闲时间。

　　低级调度用于决定从就绪队列中选取哪个进程应该获得处理机，由分派程序将处理机分配给该进程。

1.1.2、功能

　　1、保存处理机现场信息

　　2、按某种算法选取进程

　　3、把处理器分配给进程，把处理器的控制权交给该进程，让它从取出的断点处开始继续运行。

1.1.3、进程调度的基本机制

1、排队器

　　OS将所有就绪的进程按照一定的方式排成队列，便于寻找

2、分派器

　　将选出的进程从就绪队列中取出，进行上下文切换，分配处理机给该进程

3、上下文切换机制

　　操作系统保存正在执行进程的上下文，装入分派程序的上下文，便于分派程序运行；

　　移除分派程序，把新选进程的CPU现场信息转入到处理机的各寄存器中。

1.1.4、进程调度的方式

1、非抢占式调度

　　若有进程请求执行，等待当前正在执行进程完成或因某种原因阻塞，才把处理机分配给请求进程。

　　这种方式实现简单，系统开销小,适用于批处理系统,不适用分时/实时系统.

2、抢占式调度

　　根据某中原则暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。即，立即暂停当前正在执行的进程，将处理机分配给另一个更重要或优先级更高的进程。

　　抢占原则：优先权/短进程优先/时间片原则

1.2、中级调度

　　中级调度，也被称为中程调度，中级调度实际上是存储器管理中的对换功能。

　　引入中级调度的主要目的：提高内存利用率和系统吞吐量。

　　中级调度将暂时不能运行的进程挂起并调至外存等待(此时进程状态被称为挂起状态)，条件合适时再调入内存就绪；在内、外存对换区进行进程对换；将进程调至外存，条件合适再调入内存。

1.3、高级调度

　　高级调度，也被称为作业调度或长程调度。按一定原则从外存处于后备状态的作业中挑选，给它们分配（内存、I/O设备等）并建立进程，以使它们获得竞争处理机的权利；把后备作业调入内存运行；只调入一次，调出一次。

　　高级调度主要功能：根据某种算法，把外存上处于后备队列中的作业调入内存，调度的对象是作业。在批处理系统中，作业是外存调入内存的基本单位。

　　JCB - 作业控制块 保存了系统对作业进程管理和调度所需的全部信息。

　　作业进入系统时，系统会为作业建立一个JCB，根据作业的类型将它插入到相应的后备队列中，依据一定的调度算法来调度他们，被调度到的作业将会被装入内存，并为他们创建进程、分配必要的资源；再将新创建的进程插入就绪队列，准备执行；当作业执行结束，系统回收分配给它的资源，撤销它的作业控制块。

　　通俗的说，就是把程序从硬盘加载到内存中运行的过程。

2、调度队列模型

2.1、仅有进程调度的调度模型

　　1、任务在给定的时间片内已完成，进程在释放处理机后进入完成状态；

　　2、任务在本次分得的时间片内尚未完成，OS便将该任务再放入就绪队列的末尾；

　　3、执行期间，进程因为某时间而被阻塞，被OS放入阻塞队列，

2.2、具有高级和低级调度的调度队列模型

　　批处理系统中，不仅需要进程调度还需要作业调度，作业调度按一定的算法，从外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列，再由进程调度按照一定的调度算法选择一个进程，将处理机分配给该进程。

2.3、同时具有三级调度的调度队列模型

　　OS中引入中级调度后，进程的就绪状态可以分为 内存就绪 和 外存就绪，阻塞状态分为 内存阻塞 和 外存阻塞；在调出操作的作用下，使进程状态由内存就绪转为外存就绪，由 内存阻塞 转为 外存阻塞。

3、调度的基本准则

3.1. CPU利用率

　　越高，说明该资源使用率越高

3.2. 系统吞吐量

　　单位时间内CPU完成作业量；长作业耗时，短作业则能提高吞吐量；调度算法和方式不同，对OS吞吐量产生较大影响。

3.3. 周转时间

　　作业从提交到完成经历的时间；包括等待、就绪队列的排队，处理机上的运行、输入输出花费时间的总和。

3.4. 等待时间

　　进程等待时间总和；调度算法不影响作业执行或输入输出时间，只影响作业在就绪队列中等待时间；所以，衡量调度算法的优劣，考察等待时间即可。

3.5. 响应时间

　　用户提交请求到系统首次响应花费的时间；交互是系统中衡量调度算法的重要准则；应尽量降低响应时间，控制在用户可接受范围内。

　　调度程序一方面要满足特定系统用户的要求（实时和交互进程要求快速响应），另一方面要考虑系统整体效率（减少整个系统进程平均周转时间）和调度算法本身的开销

4、调度算法

　　调度的实质是一种资源分配。

　　调度算法：根据系统的资源分配策略所规定的资源分配算法。

4.1、先来先服务(FCFS)算法

　　适用于作业调度和进程调度；

　　取作业队列中或就绪队列中最先入队的进程进行调度，并等待操作完成，或作业执行完成或因某种原因阻塞时释放处理机；

　　FCFS属于不可剥夺算法，简单但效率低，可能导致后续作业长时间得不到执行，不能作为分时和实时系统的主要调度策略；

　　FCFS算法；有利于CPU繁忙型作业，不利于I/O繁忙型作业。

4.2、短作业(进程)优先调度(SJ(P)F)算法

　　短作业优先调度(SJF)算法：对短作业或段进程优先调度的算法。

　　适用于作业调度和进程调度；

　　短作业调度（SJF）：从后备队列中选择一个或多个估计运行时间最短的作业运行；

　　短进程调度（SPF）：从就绪队列中选择一个或多个估计运行时间最短的进程运行，直到完成或阻塞。

　　该算法的缺点：对长作业不利，长作业周转时间会增加，也可能导致长作业长时间不被调度而产生“饥饿”现象；不能保证更紧迫的任务被及时处理；估计执行时间可能不准确。

　　该算法的优点：SJF调度算法的平均等待时间、平均周转时间最少。

4.3、优先级调度算法

　　优先级调度算法，也叫优先权调度算法，可用于作业调度和进程调度；优先级用于描述作业的紧迫程度。

　　非剥夺式调度时，新的更高优先级进程并不能获得及时执行；剥夺式调度时，新的更高优先级进程一旦进入就绪队列，则当前进程立即暂停，并将处理机分配给新进程。

　　优先级能否改变：静态优先级->创建进程时确定（依据进程类型、对资源的要求、用户要求），运行期保持不变；动态优先级->进程运行期动态调整优先级，主要依据进程占有CPU时间的　　长短、就绪进程等待CPU时间的长短等因素。

4.4、高响应比优先调度算法

　　主要用于作业调度，是对FCFS和SJF的综合平衡；

　　调度时先计算作业的响应比：作业等待时间相同，服务时间越短，响应比越高；服务时间相同，响应比由等待时间决定，等待越久，响应比越高；长作业的响应比可以随等待时间提高，等待愈久，响应比越高，更容易获得处理机。

4.5、时间片轮转调度算法

　　公平，响应快，适用于分时系统；

　　算法内容：按进程到达就绪队列的顺序，轮流分配一个时间片去执行，时间用完则剥夺

　　算法原则：公平、轮流为每个进程服务，进程在一定时间内都能得到响应

　　调度方式：抢占式，由时钟中断确定时间到

　　适用场景：进程调度

4.5.1、基本原理

　　时间片轮转调度算法：将所有的就绪进程按照到达顺序入队，并总是选择第一个进程执行（先来先服务），但仅能运行一个时间片（如100ms），时间到，立刻剥夺该进程执行权并重新入队（队尾），处理机取下一个进程运行；

4.5.2、时间片大小的确定

　　时间片大小对OS性能影响很大：时间片太大以至于所有进程都能在（属于自己的）一个时间片内执行完成，则此算法退化为先来先服务调度算法；时间片太小，处理机将不停切换，开销增大。

　　时间片大小因素：系统响应时间，就绪队列进程数目，系统处理能力。

4.6、多级反馈队列调度算法

　　集合了前几种算法的优点：相当于时间片轮转调度算法 + 优先级调度算法；

　　动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面系统目标：为提高OS吞吐量和缩短平均周转时间而照顾短进程；为获得较好IO设备利用率和缩短响应时间而照顾IO型进程；不必事先估算进程的执行时间。

4.6.1、算法实现

　　1、设置多个就绪队列，为不同队列设置不同的优先级(逐次降低)

　　2、不同队列中进程时间片不同，优先级高的队列中进程时间片小，反之则长

　　3、新进程采用队列降级法：进入第1级队列(队尾，遵循FCFS)，没有执行完，移到第2级，未完，移到第3级...

　　4、前面队列不为空，不会执行后续队列的进程。

5、调度的时机

　　正在运行的进程运行完毕，进程运行完毕；

　　运行中的进程要求I/O，进程要求I/O操作；

　　执行某种原语操作；

　　一个比正在运行进程优先数更高的进程申请运行（在可剥夺调度方式下）；

　　分配给运行进程的时间片已经用完，进程时间片用完。

6、调度的过程

　　保存镜像：记录系统中所有进程的现场信息。

　　调度算法：确定分配处理机的原则。

　　进程切换：分配处理机给其它进程。

　　处理机回收：从进程收回处理机。