一、概念
1、处理机管理是操作系统的主要功能之一。处理机管理的实现策略决定了操作系统的类型，其算法好坏直接影响整个系统的性能
2、进程调度：通过某种规则或算法从就绪(等待)进程队列中选出一个进程投入运行
3、调度是一个基本的操作系统功能。CPU调度是操作系统设计的核心问题
二、CPU调度程序
1、任务
CPU调度程序负责在CPU上切换进程。
当正运行的进程应该从CPU上移除时(改为等待或阻塞状态)，从处于等待状态的多进程中选择一个不同的进程。CPU被分配给被选择的进程，新进程从就绪改为运行。
2、调度策略
确定进程何时从CPU移除并且应当接着将CPU分配给某个等待进程
发生调度策略的四种情况：
(1)、当一个进程从运行切换到阻塞，非抢占
(2)、当一个进程从运行切换到就绪，可抢占
(3)、当一个进程从阻塞切换到就绪，可抢占
(4)、当一个进程终止，非抢可占
非抢占调度方案：一旦CPU被分配给一个进程，该进程就将被执行到底，一直将CPU使用到进程结束或切换到等待状态再释放
可抢占调度方案：允许调度程序根据某种策略终止当前运行进程的执行，并将其移入就绪队列，并选择另外一个进程投入运行
3、主要模块
排队程序、分配程序、上下文切换程序
(1)、排队程序
当一个进程改变到阻塞状态时，更新进程描述符并且排队程序通过指针关联进程描述符，该进程进入阻塞列表
(2)、分配程序
将CPU的控制交给由短期调度程序选择的进程
功能模块：
①、切换上下文
②、切换到用户模式
③、跳转到用户程序的合适位置以重新启动用户这个程序
(3)、上下文切换程序
保存从CPU移除进程的所有处理器寄存器(PC、IR、条件状态、处理器状态、ALU状态)的内容到进程的PCB中
4、性能
调度程序对于多道程序计算机的性能有很大的影响，因为其完全控制一个进程何时能分配到CPU
三、调度准则
1、影响调度算法的主要因素
(1)、设计目标
(2)、公平性
(3)、均衡性
(4)、综合平衡
(5)、基于相对优先级
2、调度性能评价
(1)、CPU使用率
(2)、吞吐量
(3)、周转时间
(4)、就绪等待时间
(5)、相应时间
四、调度策略
常用的CPU调度策略：
①、先来先服务调度算法
②、短作业优先调度算法
③、优先级调度算法
④、轮转调度算法
⑤、多级队列调度算法
1、先来先服务调度算法
FCFS：先请求CPU的进程先获得CPU
最简单的CPU调度算法、对CPU繁忙型进程比较有利、FCFS调度算法是非抢占的
(1)、FCFS策略的平均等待时间通常不是最小的
(2)、FCFS调度算法对CPU繁忙型进程比较有利，而对于I/O繁忙型进程则不利
(3)、FCFS调度算法是非抢占的，一旦CPU被分配给一个进程，该进程将持有CPU直到它释放CPU(通过终止或请求I/O)
2、短作业优先调度算法
SJF：将每个进程与下一个CPU占用时间长度相关联。当CPU可用时，它将优先被分配给具有最短后续CPU占用的进程。这种算法假定事先知道了每个进程下次运行的CPU占用长度。如果两个进程的下一个CPU占用相同，就使用FCFS调度。
(1)、SJF给出了最小的平均等待时间
(2)、SJF也是非抢占的
(3)、最短剩余时间优先调度
(4)、抢占性短作业优先算法(SRTF)，即：当新到来一个时间最短的进程时，SJF会继续完成当前进程的执行，而SRTF会打断当前进程的 执行而去执行新来的进程
3、优先级调度算法
从就绪队列中选出优先级别最高的进程，让它占用CPU运行
(1)、静态优先级
创建进程时其优先级就确定下来
①、算法易于实现，系统开销也少
②、问题：
饥饿现象：某些优先级别低的进程可能无限期等待CPU调用
(2)、动态优先级
为解决饥饿现象而产生的解决方案，方法是老化处理。
(3)、高响应比优先调度算法：
HRN是对FCFS和SJF方式的一种综合平衡，属于动态优先级调度算法
响应比R=响应时间/要求运行时间
=(作业等待时间+需运行时间)/需运行时间
=1+已等待时间/需运行时间
=1+W/T
①、响应比R不仅是要求运行时间的函数，而且还是等待时间的函数
②、由于R与要求运行时间成反比，故对短作业是有利的
由于R与等待时间成正比，随着等待时间的增长，会获得较高响应比，克服短作业优先的缺点
(4)、2种处理方式
①、非抢占式优先级：
当前占用CPU的进程一直运行下去，直到完成任务或因为等待某些资源而主动让出CPU，系统才让另一个优先级别高的进程占用CPU
②、抢占式优先级
在当前进程运行过程中，一旦有另外一个优先级更高的进程出现在就绪队列中，进程调度程序就停止当前进程运行，强行将CPU分配给优先级别高的进程
4、轮转调度算法
将所有就绪进程按照先入先出的原则排成队列，新来的进程加到就绪队列的末尾，但轮转调度添加了进程间的抢占切换
(1)、算法特点
①、RR策略的平均等待时间通常会相当长
②、RR调度算法尤其适用于分时系统
③、RR算法性能依赖时间片的大小
(2)、RR算法定义了一个小的时间单元，被称为时间片。一个时间片通常在10ms到100ms之间
(3)、把就绪队列作为循环队列对待，CPU调度程序环绕这个就绪队列，将CPU分配到每个进程，每隔一个时间片转换一次
(4)、决定时间片大小因素：
①、上下文切换
②、系统响应时间
③、进程周转时间
④、CPU主频
5、多级队列
(1)、把就绪队列划分为多个独立的队列
(2)、将进程分成前台或后台
(3)、每个队列有自己的调度策略
(4)、每个队列之间可以按优先级调度，也可以按时间片轮转调度