目录
一、处理机调度概述
1.基本准则
（1）CPU利用率
（2）系统吞吐量
（3）周转时间
（4）等待时间
（5）响应时间
2.进程调度方式
（1）非剥夺调度方式（非抢占方式）
（2）剥夺调度方式（抢占方式）
二、调度算法
1.FCFS算法（先来先服务）
（1）算法规则:
（2）适用情况:
（3）优缺点
2.SJF算法（短作业优先）
（1）算法规则:
（2）适用情况:
（3）优缺点：
3.优先级算法
（1）算法规则:
（2）使用情况：
（3）类型：
（4）优先级的类型：
（5）优缺点：
4.RR算法（时间片轮转）
（1）算法思想：
（2）算法规则：
（3）适用情况：
（4）类型：
（5）优缺点:
5.HRRN算法（高响应比优先）
（1）算法思想：
（2）算法规则：
（3）适用情况：
（4）优缺点：
6.多级反馈队列调度算法
（1）算法思想：
（2）算法规则：
（3）适用情况：
（4）类型：
（5）优缺点：
总结
一、处理机调度概述
1.基本准则
不同的调度算法具有不同的特性，在选择调度算法时，必须考虑算法的特性。为了比较处理机调度算法的性能，人们提出了很多评价准则，下面介绍其中主要的几种。
（1）CPU利用率
CPU是计算机系统中最重要和昂贵的资源之一，所以应尽可能使保持“忙”的状态， 使这一资源利用率最高。
（2）系统吞吐量
- 表示单位时间内CPU完成作业的数量。
- 长作业需要消耗较长的处理机时间，因此会降低系统的吞吐量。
- 短作业需要消耗的处理机时间较短，因此能提高系统的吞吐量。
- 调度算法和方式的不同，也会对系统的吞量产生较大的影响。
（3）周转时间
周转时间是指从作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队、在处理机上运行及进行输入/输出操作所花费时间的总和。
- 作业的周转时间:
周转时间 = 作业完成时间 - 作业提交时间
- 平均周转时间:
平均周转时间 = (作业1的周转时间 + ...... + 作业n的周转时间)/n
- 带权周转时间（作业周转时间与作业实际运行时间的比值）:
带权周转时间 = 作业周转时间 / 作业实际运行时间
- 平均带权周转时间（多个作业带权周转时间的平均值）:
平均带权周转时间 = (作业1的带权周转时间 + ...... + 作业n的带权周转时间) / n
（4）等待时间
等待时间指进程处于等待处理机状态的时间之和，等待时间越长，用户满意度越低。
（5）响应时间
响应时间指从用户提交请求到系统首次产生响应所用的时间。
2.进程调度方式
是指当某个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要处理，即优先权更高的进程进入就绪队列，此时应如何分配处理机的方式。 通常有以下两种进程调度方式:
（1）非剥夺调度方式（非抢占方式）
非剥夺调度方式是指当一个进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入阻塞态时，才把处理机分配给更为重要或紧迫的进程。
（2）剥夺调度方式（抢占方式）
采用剥夺式的调度，对提高系统吞吐率和响应效率都有明显的好处。但“剥夺” 不是一种任意性行为，必须遵循一定的原则，主要有优先权、短进程优先和时间片原则等。
二、调度算法
1.FCFS算法（先来先服务）
（1）算法规则:
先来先服务算法(first come first server,FCFS)按照作业/进程到达的先后顺序来进行调度。
（2）适用情况:
可用于作业调度也可用于进程调度。
（3）优缺点
- 优点:算法实现简单。
- 缺点:对长作业有利，对短作业不利。
2.SJF算法（短作业优先）
（1）算法规则:
短作业优先调度算法(short job first,SJF)以作业的长短来计算优先级，作业越短，其优先级越高。
（2）适用情况:
可用于作业调度及进程调度。
（3）优缺点：
- 优点:“最短的”平均等待时间及平均周转时间。
- 缺点:①必须先知道作业的运行时间。
- ②对长作业不利，会出现饥饿现象。
- ③没有考虑作业的紧迫程度。
3.优先级算法
（1）算法规则:
基于进程(作业)的紧迫程度，由外部赋予进程相应的优先级，根据优先级进行调度。
（2）使用情况：
可用于作业调度也可用于进程调度甚至I/O调度。
（3）类型：
抢占式优先级调度算法:只需出现另一个优先级更高的进程，调度就会发生变化非抢占式优先级调度算法:主动放弃。
（4）优先级的类型：
①静态优先级:在创建进程时确定，其在进程的整个运行期间不变。
②动态优先级:在创建进程之初，先赋予进程一个优先级，然后动态的调整优先级。
（5）优缺点：
- 优点:用优先级区分紧急程度，运用于实时os。
- 缺点:可能导致饥饿(低优先级进程的饥饿)。
4.RR算法（时间片轮转）
（1）算法思想：
时间片轮转算法(Round-Robin)公平地、轮流地为各个进程服务， 让每个进程在一定时间间隔内都可以得到响应。
（2）算法规则：
按照各进程到达就绪队列的顺序， 轮流让各个进程执行一个时间片。 若进程未到一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
（3）适用情况：
可用于进程调度。
（4）类型：
属于抢占式算法。 由时钟装置发出时钟中断来通知CPU时间片已到。
（5）优缺点:
- 优点：公平，响应快，适用于分时操作系统。
- 缺点:不能区分任务的紧急程度，需要进程切换，消耗较大。
5.HRRN算法（高响应比优先）
（1）算法思想：
高响应比优先调度算法(Highest Respomse Ratio Nex,HRRN )综合考虑作业或进程的等待时间和要求服务的时间。
（2）算法规则：
每次调度前先计算各个作业或进程的响应比(优先级)，选择响应比最高的作业或进程为其服务。
响应比(R)=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间
（3）适用情况：
可用于作业调度及进程调度。
（4）优缺点：
- 优点:综合考虑了等待时间和运行时间，较好的实现了折中。
- 缺点:每次调度前都要算响应比，会增加系统的开销。
- 注意:不会导致饥饿现象。高响应比优先算法
6.多级反馈队列调度算法
（1）算法思想：
对其他调度算法的折中权衡。
（2）算法规则：
- 设置多个就绪队列.各级队列优先级从高到低，时间片从小到大。
- 每个队列都采用FCFS调度算法。
- 按队列优先级调度。只有当第1~i一1队列均空时，才会调度第i队列中的进程。
（3）适用情况：
可用于进程调度
（4）类型：
属于抢占式的算法。
（5）优缺点：
- 优点:用优先级区分紧急程度，运用于实时OS 。
- 缺点:可能导致饥饿(低优先级进程的饥饿)。
（6)图示
总结
本篇对操作系统处理机调度的内容进行了概括梳理，便于理解和复习。部分内容源自网络，如有侵权请联系作者删除处理，谢谢！
