处理机调度层次
1.高级调度（长程调度/作业调度）
决定将外存上处于后备队列中的哪几个作业调入内存，并建立相应进程。每个作业值调入一次，调出一次。调入时会建立PCB，调出时才撤销PCB。
2.低级调度（进程调度/短程调度）——最基本，频率最高
决定就绪队列中的哪个进程应获得处理机
3.中级调度（内存调度）
把外存上的已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态
（之前为了提高内存利用率，而把一些暂时不能运行的进程调至外存等待变成就绪驻外状态（或挂起状态）了）注意PCB会常驻内存，并不会被调出。
实际上就是存储器管理中的对换功能。
处理机调度算法的目标
1.处理机调度算法的共同目标
1）资源利用率
CPU利用率=CPU有效工作时间/（CPU有效工作时间+CPU空闲等待时间）
2）公平性
使诸进程都获得合理的CPU时间，不会发生进程饥饿现象
3）平衡性
保持系统资源的平衡性，使系统中的CPU和各种外部设备都能经常处于忙碌状态
4）策略强制执行
2.批处理系统的目标
1）平均周转时间短
周转时间：从作业被提交给系统开始到作业完成为止的时间间隔
包括四部分：作业在外存后备队列上等待作业调度的时间；进程在就绪队列上等待进程调度的时间；进程在CPU上执行的时间；进程等待I/O操作完成的时间。（后三个会发生多次）
T=1/n[ΣTi]
W=1/n[ΣTi/Ts]
2）系统吞吐量高
吞吐量：单位时间内系统所完成的作业数
3）处理机利用率高
3.分时系统的目标
1）响应时间快
响应时间：从用户通过键盘提交一个请求开始，知道屏幕上显示出处理结果为止
2）均衡性
系统响应时间快慢与用户所请求服务的复杂性相适应
4.实时系统的目标
1）截至时间的保证
截至时间：某任务必须开始执行的最迟时间，或必须完成的最迟时间
2）可预测性
作业与作业调度
（画时空图，模拟就绪队列）
批处理系统中，以作业为基本单位从外存调入内存。
作业运行期间的每个加工步骤称为一个作业步，编译作业步，链接装配作业步，运行作业步。
作业控制块JCB
当一个作业进入系统时，“作业注册”程序为其创建一个JCB，再根据作业类型，将它放到相应的作业后备队列中等待调度，被调度到的作业将被装入内存。
收容阶段（后备状态，不再内存中）-》运行阶段-》完成阶段
作业调度的主要任务：根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的调度算法，从外存后备队列中选取某些作业调入内存。
接纳调度（接纳多少个作业，接纳哪些作业）
分时系统和实时系统不用作业调度，直接被送到内存。
先来先服务调度算法FCFS
很少作为主调度算法，经常把它与其它调度算法相结合使用
比如，在系统中按进程的优先级设置多个队列，每个队列基于FCFS来调度。
哪个作业先到达后备队列/哪个进程先到达就绪队列
非抢占
对长作业有利，对短作业不利
不会导致饥饿
短作业优先调度算法SJF
最短的平均等待时间，平均周转时间
缺点：必须预知作业的运行时间；对长作业非常不利（饥饿现象）；无法人机交互；未考虑作业的紧迫程度
也可以用于进程调度SPF
SJF，SPF是非抢占的
还有个抢占式的版本SRTN，如果新到的进程的时间比当前正在执行的进程的剩余时间小的话那就会发生抢占。
高响应比优先调度算法HRRN
既可用于作业又可以用于进程
动态优先级
随着等待时间变长优先级变高
优先权（Rp）=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间
非抢占
不会饥饿
FCFS，SJF，HRRN都不能交互。
时间片轮转RR
时间片用完之后是放在当前就绪队列的队尾，要注意有的进程可能还没到。
用于进程调度（只有作业放入内存建立了相应进程后，才能被分配处理机时间片）
抢占式，时钟中断
公平，响应快用于分时系统
进程切换频率高，开销大；不区分任务紧急程度
不会饥饿
优先级调度算法PSA
基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法是根据该优先级进行调度的。
即可用于作业调度又可进程调度
抢占式，非抢占都有
会饥饿
进程调度
进程调度的时间：
当前运行的进程主动放弃处理机（进程正常终止；运行过程中发生异常；进程主动请求阻塞）
当前运行的进程被动放弃处理机（时间片用完；有更紧急的事（比如I/O中断；有更高优先级的进程进入就绪队列）
不能进行进程调度与切换的情况：在处理中断的过程中；在操作系统内核程序临界区中（注意并不是普通的临界区）；在原语过程中。
进程调度的任务：保存处理机的现场信息；按照某种算法选取进程；把处理器分配给进程。
排队器：每当有一个进程转变为就绪状态时，排队器便将它插入相应的就绪队列。
分派器
上下文切换器：保存当前进程的上下文；装入分派程序的上下文以便分派程序运行；移除分配程序上下文，把新选进程的CPU现场信息装入
（现在一般靠硬件来实现，设置多组寄存器，切换上下文时只需改变指向寄存器的指针即可）
进程调度方式
1）非抢占方式（只允许进程主动放弃处理机）
不会因为时间中断或任何其它原因去抢占当前正在运行进程的处理机
2）抢占方式
优先权原则；短进程优先原则；时间片原则（时间片轮转）
轮转调度算法RR
如果就绪队列上n个进程，则每个进程每次大约都可以获得1/n的处理机时间
系统根据FCFS策略，将所有就绪进程排成一个就绪队列，设置每隔一定时间间隔产生一次中断，激活系统中的进程调度程序，完成一次调度。
进程切换时机：正在运行的进程完成了；一个时间片用完（若进程尚未完成则送至就绪队列队尾，注意是当前就绪队列的对尾！！）
时间片小-》频繁的上下文切换-》增加系统开销
时间片太长-》退化为FCFS
可取的时间片大小：略大于一次典型的交互所需要的时间，使大多数交互式进程能在一个时间片内完成，从而可获得很小的响应时间。
题目一般是给出进程的到达时间与服务时间，然后计算每个进程的完成时间，周转时间，带权周转时间以及平均周转时间与带权周转时间。
优先级调度算法
（前面讲的RR是默认所有进程的紧迫性都是一样的所以用的FCFS）
1）非抢占式优先级调度算法
2）抢占式优先级调度算法
1）静态优先级
一个整数，通常由进程类型，进程对资源的需求，用户要求来决定
2）动态优先级
比如优先级随等待时间增长而变高，随运行时间推移而下降（可防止一个长作业长期垄断处理机）
多队列调度算法
将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。
多级反馈队列
综合了之前所有的调度算法的优点
用于进程调度
抢占式
不必先知道各种进程所需的执行时间
设置多个就绪队列，为每个队列赋予不同的优先级，不同的时间片大小，优先级越高的队列时间片越小
每个队列都采用FCFS算法。当新进程进入内存时先放到第一队列的末尾，若轮到它执行第一个队列的时间片后它没完成就放到第二队列末尾，以此类推。当进程被降到第n队列后，该队列就采用RR。
按队列的优先级调度。抢占。如果处理机正在第i队列为某进程服务，此时有新进程进入任一优先级较高的队列，此时立即把正在运行的进程放到第i队列的队尾（注意还是当前队列而不是像上面一样放到下一级），然后把处理机分配给新到的高优先级进程。
若规定第一个队列的时间片略大于多数人机交互所需要的时间，则可以满足各种类型的用户的需要，终端型用户，短批处理作业用户，长批处理作业用户。
基于公平原则的的调度算法
以上介绍的几种调度算法所保证的只是优先运行，并不保证作业占用处理机多长时间。
1.保证调度算法
明确的性能保证
如果在系统中有n个相同类型的进程同时运行，公平起见，须保证每个进程都获得相同的处理机时间1/n。
1）跟踪计算每个进程自创建以来已经执行的处理时间。x
2）计算每个进程应获得的处理机时间，即自创建以来的时间除以n。y
3）计算进程获得处理机时间的比率，即z=x/y
4）比较各进程获得处理机时间的比率。
5）调度程序应选择比率最小的进程，让该进程一直运行直至超过最接近它的进程比率为止。（然后呢，如果A把B刚好超过了，那就会执行B，但B执行一下下不就又把A超过了？）
2.公平分享调度算法
使所有用户都能获得相同的处理机时间或所要求的时间比例
实时调度
所需信息：
就绪时间（某任务成为就绪状态的起始时间。在周期任务的情况下，这个是事先预知的一串时间序列）
开始截止时间和完成截至时间
处理时间
资源要求
优先级
处理时间Ci，周期时间Pi需满足：ΣCi/Pi<=N（N是处理机数量）
实时调度算法分类
硬实时调度算法/软实时调度算法，
非抢占调度算法（非抢占式轮转调度算法/非抢占优先调度算法）
/抢占调度算法（基于时钟中断的抢占式优先级调度算法/立即抢占的优先级调度算法）
最早截至时间优先算法EDF
截至时间越早，优先级越高
1.非抢占式调度方法用于非周期实时任务
2.抢占式调度方式用于周期实时任务
（如果新到的进程完成截至时间更早则正在执行的进程被抢占）
最低松弛度优先算法LLF（注意计算松弛的时机）
进程的松弛度=必须完成时间-其本身还需要运行的时间-当前时间
任务越紧急，优先级越高。
就绪队列中，松弛度最低的任务排在最前面。
主要用于可抢占调度方式中
要注意进程是否已到达下一周期（比如A3提前结束了，则此时A4还没到，所以不管松弛度谁大谁小都应该执行已进入下一周期的B2）P101
