调度的层次
低级调度（进程调度）
低级调度（进程调度/处理机调度）—— 按照某种策略从就绪队列中选取一个进程，将处理机分配给他。
进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。 进程调度的频率很高，一般几十毫秒一次。
中级调度（内存调度）
内存不够时，可将某些进程的数据调出外存。等待内存空闲或者进程需要运行时再重新调入内存。
暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列
中级调度（内存调度）——按照某种策略决定将哪个处于挂起状态的进程重新调入内存
高级调度（作业调度）
按照一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会创建PCB，调出时才撤销PCB。
进程调度的方式
非剥夺调度方式
又称非抢占方式。即进程在运行时不会被强制中断，只有进程自己放弃CPU时才会被调度。 适合早期的批处理系统
剥夺式调度方式
又称抢占方式。即进程在运行时可能会被强制中断，被调度程序强制剥夺CPU。 适合分时操作系统和实时操作系统。
进程调度的时机
进程在操作系统内核程序临界区中不能进行调度与切换
进程处于临界区的时可以进行处理机调度
内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列(由各就绪进程的PCB组成)
调度评价指标
CPU利用率
CPU利用率 = CPU繁忙时间 / （CPU繁忙时间 + CPU空闲时间）
吞吐量
单位时间内完成的作业数
系统吞吐量 = 完成的作业数 / 单位时间
周转时间
作业从提交到完成所经历的时间
周转时间 = 完成时间 - 到达时间
平均周转时间 = 所有作业的周转时间之和 / 作业数
带权周转时间 = 周转时间 / 作业的服务时间
平均带权周转时间 = 所有作业的带权周转时间之和 / 作业数
等待时间
作业在就绪队列中等待的时间
响应时间
从提交作业到第一次获得响应的时间
调度算法
先来先服务（FCFS）
算法规则
按照作业提交的先后顺序进行调度
用于作业调度/进程调度
用于作业调度时，考虑是哪个作业先到达后备队列，用于进程调度时，考虑是哪个进程先到达就绪队列。
是否可抢占
不可抢占
优点
简单，公平
缺点
平均等待时间长，不适合交互式系统 对长作业有利，对短作业不利
是否会出现饥饿
不会
短作业优先（SJF）
算法规则
按照作业的服务时间长短进行调度 服务时间短的作业先执行
用于作业调度/进程调度
可以用于作业调度，也可以用于进程调度。用于进程调度时称为短进程优先（SPF）。
是否可抢占
SJF和SPF是非抢占式算法。但是也有抢占式版本–最短剩余时间优先（SRTF）
优点
最短的平均等待时间、平均周转时间
缺点
不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
是否会出现饥饿
会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为“饿死“
高响应比优先（HRRN）
算法规则
响应比 = （等待时间 + 服务时间） / 服务时间 在每次调度时，选择响应比最高的作业/进程执行
用于作业调度/进程调度
可以用于作业调度，也可以用于进程调度
是否可抢占
不可抢占
优点
综合考虑了等待时间和服务时间，兼顾了短作业优先和先来先服务的优点
时间片轮转（RR）
算法规则
每个进程被分配一个时间片，当时间片用完时，进程被放到队列的末尾，等待下一次调度
用于作业调度/进程调度
只用于进程调度
是否可抢占
可抢占
优点
公平，适合分时系统
缺点
时间片过大，可能退化为FCFS；时间片过小，可能增加上下文切换的开销
优先级调度算法
算法规则
每个进程/作业都有一个优先级，按照优先级高低进行调度
用于作业调度/进程调度
可以用于作业调度，也可以用于进程调度 可以从追求公平、提升资源利用率等角度考虑如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级如果某进程占用处理机运行了很长时间，则可适当降低其优先级如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级
是否可抢占
抢占式、非抢占式都有。
优点
用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
缺点
可能产生饥饿现象
多级反馈队列调度算法
算法规则
- 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
- 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
- 只有第k级队列为空时，才会为k+1级队头的进程分配时间片3.
用于作业调度/进程调度
只用于进程调度
是否可抢占
抢占式的算法。在k级队列的进程运行过程中，若更上级的队列(1~k-1级)中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。
优点
对各类型进程相对公平(FCFS的优点) 每个新到达的进程都可以很快就得到响应(RR的优点) 短进程只用较少的时间就可完成(SPF的优点) 不必实现估计进程的运行时间(免用户作假) 可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/0密集型进程(拓展:可以将因I/0而阻塞的进程重新放回原队列，这样//O型进程就可以保持较高优先级)
是否会出现饥饿
会
多级队列调度算法
