背景：
在多到程序下，内存中的进程数往往多于系统处理机的数目，这就要求系统能按照某种算法，动态地将处理机分配给处于就绪状态的一个进程，使之执行。
而分配处理机的任务是由处理机调度程序完成的。对于大型系统运行时的性能，如系统的吞吐量、资源的利用率、作业周转时间或响应的及时性等，在很大程度上都取决于处理机调度性能的好坏。
一、处理机调度的层次
调度的实质是一种资源的分配，处理机调度是对处理机资源进行分配。在多道批处理系统中，一个作业从提交到获得处理机执行，直至作业运行完毕，可能需要经历多级处理机调度，下面是处理机调度的层次。
高级调度
又称长程调度或者作业调度
- 调度对象：作业
- 功能：根据某种算法将外存上后备队中的作业调入内存，为它们创建进程、分配必要的资源，并将它们加入就绪队列。
- 特点：往往发生在一批作业已运行完毕并退出系统，又需要重新调入一批作业进入内存时。作业调度周期较长，大约几分钟一次，由于其运行频率较低，故作业调度算法花费时间较多。
低级调度
又称进程调度或者短程调度
- 调度对象：进程（或者内核级线程）
- 功能：根据某种算法决定就绪队列中哪个进程应该获得处理机，并由分派程序将处理机分配给选中的线程。
- 特点：运行频率最高，为避免调度本身占用太多cpu时间，不宜使用进程调度算法太复杂。
中级调度
又称内存调度、
- 调度对象：暂时不能运行的进程
- 功能：提高内存利用率和系统吞吐量，因此需要将暂时不能运行的进程，调至外存等待，此时称为就绪驻外存状态（或挂机状态），当它们已具备运行条件时，根据调度算法，重新调入内存，并修改其为就绪状态。
- 特点：运行频率基本上处于上述两种调度之间
二、处理机调度算法的目标
如何选择调度方式和算法，很大程度上取决于操作系统的类型及设计的目标。
调度算法的共同目标
- 资源利用率：如cpu的利用率 = cpu有效工作时间/（cpu有效工作时间 + cpu空闲时间）
- 公平性：诸进程都应获取合理的cpu时间，不会发成进程饥饿的现象。
- 平衡性：如作业型进程、I/O型进程，保证系统资源使用的平衡。
- 策略强制执行：对所制定的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。
批处理系统的目标
- 平均周转时间短
- 系统吞吐量高
- 处理机利用率高
分时系统的目标
- 响应时间快：是选择分时系统中进程调度算法的重要准则。
- 均衡性：是指系统响应时间的快慢应与用户请求服务的复杂性相适应。
实时系统的目标
- 截止时间的保证：HRT任务，其调度方式和算法必须确保对截止时间的要求，否者或造成难以预料的后果；对于SRT任务，其调度方式和调度算法也应基本上能保证对截止时间的要求。
- 可预测性
三、作业与作业调度
作业是用户提交给系统的一项相对独立的工作，操作员把用户提交的作业通过相应的输入设备输入到磁盘存储器中，并保存在一个后备作业队列中。再由作业调度程序将其从外存中调入内存。
作业
- 作业（job）：包含了通常的程序和数据，还应配有一份作业说明书，系统根据系统说明说来对程序进行控制。
- 作业步：通常在运行期间，每个作业都必须经过若干个相对对立，有相互关联的顺序加工步骤才能得到结果，我们把其中每一个加工步骤称为作业步。
- 作业控制块（job control block，jcb）：它是作业在系统中存在的标示，保存了系统对作业进行管理和调度所需要的全部信息。有：作业标示、用户账号、作业类型（cpu忙碌型、I/O忙碌型、批量型、终端型）、作业状态、调度信息（优先级、作业运行时间）、资源需求（预计运行时间、预计内存大小）、资源使用情况。当一个作业执行完毕，系统负责回收已分配给它的资源，撤销该作业的控制块。
作业运行的阶段和状态
- 收容阶段：操作员把用户提交的作业输入，创立JCB，并把它放入作业后备队列中。此时为‘后备状态’
- 运行阶段：当作业被调度选中后，便为它分配资源和建立进程，并加入就绪队列。直到它运行结束前都为‘运行状态’
- 完成阶段：当作业完成或异常中断，进入完成阶段，为‘完成状态’，系统回收资源和jcb，并将作业结果输出。
作业调度算法
在批处理系统中，作业进入系统中，总是先驻留在外存的作业后备队列上，因此需要有作业调度，以便将它们分批装入内存。
- 先来先服务调度算法（FCFS：first-come first-served）：或者说是优先考虑在系统中等待时间最长的作业，而不是该作业所需要执行时间的长短。
- 短作业优先调度算法（SJF：short job first）：已作业的长短（作业要求的运行时间）来计算优先级，作业越短优先级越高。也可以用户进程调度中。缺点为：1）必须预知作业的运行时间；2）对长作业非常不利；3）在采用SJF算法时，人机交互无法实现；4）该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫型作业能得到及时的处理。
- 优先级调度算法（priority—scheduling algorithm，PSA）：基于作业的紧迫程度，由外部赋予作业相应的优先级，然后根据该优先级进行调度。
- 高相应比优先调度算法（highest response ratio next， HRRN）：引入一个动态的优先级，优先权 = （等待时间 + 要求服务时间）/ 要求服务时间 = 相应时间 / 要求服务时间 = R(p)，可知：1）如果等待时间相同，要求服务时间短的优先，有利于短作业，类似于SJF；2）如果要求服务的时间相同时，优先级取决于等待时间，类似于FCFS；3）对于长作业的优先级，可以随着等待时间的增加而提高，当其等待时间足够长时，也可以获得处理机。
四、进程调度
进程调度是OS中比不可少的调度，也是对系统性能影响最大的一种处理机调度。
进程调度的任务
- 保留处理机的现场信息：如程序计数器、多个通用寄存器中的内容等。
- 按照某中算法选取进程
- 把处理器分配给进程：需要将选中进程的pcb内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交予给该进程，让它从上次的断点处恢复运行。
进程调度机制
为实现进程调度，有三个基本部分：
- 排队器：将系统中的所有的就绪进程按照一定的策略排成一个或者多个队列，每当一个进程转变为就绪状态时，排队器将它插入到相应的就绪队列中。
- 分派器：将进程从就绪队列中取出，然后进行从分派器到进程间的上下文切换，将处理机分配给新选出的进程。
- 上下文切换器：将当前进程的上下文保存在pcb内的相应单元，再转入分派程序的上下文，以便分派程序运行；将新进程的cpu现场信息装入到处理机各个寄存器中，以便新的程序运行。
进程调度的方式
- 非抢占方式：这种方式下，一旦某进程开始运行，就会一直运行下去。可能引起调度的因素有：1）正在执行的进程运行完毕或发生发生某事件无法运行；2）正在执行的进程提出I/O请求而暂停；3）在进程通信或者同步的过程中执行了某种原语操作，如block原语。
- 抢占式：允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。抢占的原则主要有：1）优先权原则；2）短进程优先原则；3）时间片原则
轮转调度算法
在分时系统中，最简单最常用的是基于时间片的轮转（RR：round robin）调度算法
- 基本原理：根据FCFS将所有的就绪进程排成一个就绪队列，并设置一定的时间间隔（如30ms）即产生一次中断，激活系统中的调度程序，完成一次调度，将cpu分配给对首进程，令其执行，当该进程的时间片耗尽时或者运行完毕时，系统再次将cpu分配给新的对首进程。
- 进程切换时机：1）若一个时间片没有用完（代表已经完成），就立即激活调度程序，将它从就绪队列中删除，再次调度对首进程，并启动一个新的时间片。2）若一个时间片用完，进程尚未完毕，调度程序将它送往就绪队列的末尾
- 时间片大小的确定：时间片的大小对系统的性能有很大的影响，若很小的时间片，将有利于短作业，但是会频繁的进行进程调度和上下文切换，无疑会增加系统的开销；反之，时间片越长，则可能每一个进程都在一个时间片被完成，RR算法便退化为FCFS。
优先级调度算法
把处理机分配给就绪队列中优先级最高的进程。这是又可以分为非抢占式优先级算法和抢占式优先级算法。
- 静态优先级：在创建进程时确定的，不能改变，用0～255的整数表示。确定优先级大小的依据有：1）进程类型，通常系统进程 > 用户进程；2）进程对资源的要求；3）用户的要求
- 动态优先级：指在创建时先赋予一个优先数，然后随着进程的推进或者等待时间的增加而改变，以便获得更好的调度性能。
多队列调度算法
设置多个队列，满足系统中不同用户对进程调度策略的不同要求
多级反馈队列调度算法
前面算法的缺陷：需要预知进程的所需的执行时间。
- 调度机制：设置多个就绪队列，每个队列设置不同的优先级，第一个队列的优先级最高，第二个次之... 优先级高的时间片越小，第一个队列的时间片最小，依次类推。每个队列采用FCFS，当新进程进入后，插在第一个队列的对尾，等待调度，当轮到该进程执行时，如果能在第一个队列的时间片内完成，便可从队列中删除，如果没有执行完成，则加入第二个队列的末尾等待调度，依次，当最后被降入第n个队列后，就按RR算法调度。
- 按队列优先调度
- 性能：满足各种类型用户的需要，目前公认的一种较好的调度算法
基于公平原则的调度算法：
前面的算法是保证优先运行，不考虑占用处理机的时间，也未考虑到调度的公平性
- 保证调度算法：另一种类型的调度算法，它向用户所作出的保证并不是优先运行，而是可以做到调度的公平性。
- 公平分享调度算法：在该算法中，公平性主要是针对用户而言，使所有的用户能获得相同的处理机时间，或时间比例。例如甲用户有A，B，C，D4个进程，而已用户只有E进程。如果希望处理时间相同，则调度序列为：AEBECEDEAE...，如果用户甲是乙的二倍，则ABECDEABE...
实时调度
有HRT任务和SRT任务，都联系一个截止时间。
实现实时调度的基本条件
- 提供必要的信息：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级
- 系统处理能力强
- 采用抢占式调度机制
- 具有快速切换机制：对中断的快速响应能力；快速的任务分派能力
非抢占式调度算法
- 非抢占式轮转调度算法
- 非抢占式优先调度算法
抢占式调度算法
- 基于时钟中断的抢占式优先级调度算法
- 立即抢占的优先级调度算法
最早截止时间优先EDF（earliset deadline first）算法
根据任务的截止时间确定任务的优先级，截止时间越早，优先级越高，最早截止时间的任务排在队列的首部。edf即可用抢占式调度方式，也可用非抢占式调度方式。
- 非抢占式调度方式用于非周期实时任务
- 抢占式用于周期实时任务
最低松弛度优先LLF（least laxity first）算法
根据任务的紧急程度，任务越紧张优先级越高，最紧急的任务先执行。
该算法主要抢占式调度方式中
