一、调度层次和调度算法目标

1.1调度层次

1.1.1高级调度

又称长程调度或作业调度
调度对象是作业
主要功能：根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为其创建进程、分配必要资源并放入就绪队列
主要用于多道批处理系统
作业调度往往发生在一批作业以运行完毕并退出系统，又需要重新调入一批作业进入内存时

1.1.2低级调度

又称短程调度或进程调度
主要功能：根据某种算法，决定就绪队列中的哪个进程应获得处理器，并由分派程序将处理器分配给选中的进程
多道批处理、分时、实时三种OS都必须设置

1.1.3中级调度

又称内存调度
主要功能：把暂时不能运行的进程调至外存等待，当它们具备运行条件且内存有空闲时再重新调回内存，并修改其状态为就绪状态，挂在就绪队列上等待

1.2调度算法目标

1、调度算法的共同目标

资源利用率：CPU利用率=CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)
公平性：诸进程获得合理的CPU时间，不会发生进程饥饿现象
平衡性：使系统中的CPU和各种外部设备都能经常处于忙碌状态
策略强制实行：即使会造成某些工作的延迟

2、批处理系统的目标

平均周转时间短(从作业被提交给系统开始，到作业完成为止的时间间隔)
系统吞吐量(单位时间内系统完成的作业数)高
处理器利用效率高

3、分时系统的目标

响应时间快(从用户通过键盘提交一个请求开始，直到屏幕显示出处理结果为止的时间间隔)
均衡性

4、实时系统的目标

截止时间的保证：任务开始执行或必须完成的最迟时间
可预测性

二、作业调度

2.1概念

作业：不仅包含通常的程序和数据，还应配有一份作业说明书
批处理系统中以作业为基本单位从外存调入内存
作业步：在作业运行期间，每个作业必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，每个加工步骤称为一个作业步
主要任务：根据作业控制块中的信息，检查系统中的需要能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。最后将新创建的进程排在就绪队列上等待调度

2.2先来先服务调度算法FCFS

FCFS既可用于作业调度，也可用于进程调度
当作业调度中采用FCFS算法时，系统按照作业到达的先后次序来进行调度，或者说它优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短
当进程调度中采用FCFS算法时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行

2.3短作业优先调度算法SJF

以作业的长短来计算优先级，作业越短，其优先级越高(作业的长短以作业所要求的运行时间来衡量)
缺点：

必须预知作业的运行时间
对长作业不利
人——机无法实现交互
完全未考虑作业的紧迫程度，不能保证紧迫性作业能得到及时处理

2.4高响应比优先调度算法HRRN

既考虑作业的等待时间，又考虑作业的运行时间
引入一个动态优先级：优先权=(等待时间+要求服务时间)/要求服务时间
等待时间与服务时间之和是系统对该作业的响应时间，故优先级相当于相应比Rp：Rp=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间

若作业等待时间相同，要求服务的时间越短，优先权越高，类似SJF算法，利于短作业
若服务时间相同，优先权取决于等待时间，类似FDFS算法，利于长作业
对于长作业的优先级，随着等待时间的增加而提高，当其等待时间足够长也可获得处理器

三、进程调度

对系统性能影响最大的一种处理器调度

3.1进程调度的任务、机制、方式

1、任务

保存处理器的现场信息
按某种算法选取进程
把处理器分配给进程

2、调度机制

排队器：将系统中的所有就绪进程按一定策略排成一个或多个队列。每当有一个进程转变为就绪状态时，排队器将它插入到相应的就绪队列
分派器：从就绪队列中选出依据调度程序选中的进程，进行从分派器到新选进程间的上下文切换，把处理器分配给新选进程
上下文切换器：处理器切换时发生两对上下文切换操作。第一次，OS保存当前进程的上下文，把当前进程的处理器寄存器内容保存到该进程的PCB内的相应单元，再装入分派程序的上下文以便运行；第二次，移出分派程序的上下文，把新选进程的CPU现场信息装入处理器的各个相应寄存器内以便新选进程运行

3、调度方式
非抢占方式：一旦把处理器分配给某进程，就让它一直运行下去，直至该进程完成，或发生某事件而被阻塞时，才把处理器分配给其他进程
抢占方式：允许调度程序根据某种原则暂停某个正在执行的进程，将已分配给该进程的处理器重新分配给另一进程
“抢占”必须遵循一定原则：

优先权原则
短进程优先原则
时间片原则：各进程按时间片轮转运行时，当正在执行进程的一个时间片用完后，停止该进程的执行而重新进行调度

3.2时间片轮转调度算法

让就绪队列的每个进程每次仅运行一个时间片。若就绪队列上有 n个进程，每个进程每次大约获得 1/n的处理时间
1、基本原理
根据先来先服务的原则，将需要执行的所有进程按照到达时间的大小排成一个升序的序列，每次都给一个进程同样大小的时间片。在时间片内如果进程执行结束，把进程从进程队列中删去，否则把该进程停止然后改为等待状态，放到进程队列的尾部，直到所有的进程都已执行完毕
2、进程的切换
时间片够用：在该时间片内，进程可以运行至结束，进程运行结束之后，将进程从进程队列中删除，然后启动新的时间片
时间片不够用：在该时间片内，进程只能完成它的一部分任务，在时间片用完之后，将进程的状态改为等待状态，将进程放到进程队列的尾部，等待cpu的调用
3、关于时间片大小的选择
时间片过小，则进程频繁切换，会造成cpu资源的浪费
时间片过大，则轮转调度算法就退化成了先来先服务算法

3.3优先级调度算法

1、优先级调度算法的类型

非抢占式优先权调度算法
系统一旦把处理机分配给优先权最高的进程后，便一直执行下去，至完成。
抢占式优先权调度算法
只要系统中出现一个新的就绪进程，就进行优先权比较。若出现优先权更高的进程，则立即停止当前执行，并将处理机分配给新到的优先权最高的进程

2、优先级类型

静态优先级
静态优先权在创建进程时确定，且在进程的整个运行期间保持不变
确定优先级大小的依据：

进程类型(系统进程的优先级高于一般用户进程)
进程对资源的需求(资源越少优先级越高)
用户要求(紧迫程度和用户所付费用多少)

动态优先级
创建进程之初先赋予其一个优先级，其值随进程的推进或等待时间的增加而改变

3.4多级反馈队列调度算法

调度机制：

设置多个就绪队列。每个队列赋予不同优先级，第一队列最高，往后递减；不同队列进程赋予的执行时间片大小不同，优先级越高的队列，时间片越小
每个队列采用FCFS算法。新进程进入内存后，首先放入第一队列末尾按FCFS原则调度；若在一个时间片内完成则撤离系统，否则转入第二队列末尾等待调度；以此类推，进程被降到第 n队列后按RR方式运行
按队列优先级调度。首先调度最高优先级队列中的进程运行，仅当第1～(i-1)所有队列均空时才调度第 i队列中的进程运行；若处理器在第 i队列中为某进程服务时，有新进程进入任一优先级较高队列，立即把正在运行的进程放置该队列队尾，把处理器分配给新到的高优先级进程

进程

操作系统——处理器调度