#第八节课 ##第二单元第六节 处理器调度 ###一、处理器调度层次 1、 高级调度：又称作业调度，长度调度，在多道批处理操作系统中，从输入系统的一批作业中按照预定的调度策略挑选若干作业进入内存，为其分配所需资源并创建对应作业的用户进程后，便完成启动阶段的高级调度任务，已经为进程做好运行前的准备工作，等待进程被调度运行，在作业完成后还要做、结束阶段的善后工作。
2、 中级调度：又称平衡调度、中程调度，根据内存资源情况决定内存中所能容纳的进程数目，并完成外存和内存中的进程对换工作。
3、 低级调度：又称进程调度/线程调度、短程调度，根据某种原则决定就绪队列中哪个进程/线程获得处理器，并将处理器让给他使用。低级调度是操作系统最为核心的部分。
一般操作系统都配置高级调度和低级调度，而功能完善的操作系统为了提高内存利用率和作业吞吐量引进了中级调度。
###二、调度算法原则 1、资源利用率：CPU利用率=CPU有效工作时间/CPU总的运行时间 CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间
2、吞吐率：单位时间内CPU处理作业的个数。
3、公平性：确保每个进程都能获得合理的CPU份额和其他资源份额，不会出现饥饿现象。
4、响应时间：从交互式进程提交一个请求直到获得响应之间的时间间隔称为响应时间。
5、周转时间：批处理用户从向系统提交作业开始到作业完成为止的时间间隔称为周转时间。 ###三、作业管理与调度 1、作业管理
作业组织
作业调度
运行控制
2、作业的分类
（1）批处理作业
批处理作业的输入
批处理作业的建立（为了有效管理作业为进入系统的每个作业建立一个作业控制块JCB，所有JCB组成作业表）
批处理作业的调度（选择作业，分配资源，创建进程，作业控制，后续处理
（2）交互型作业 作业是用户提交给操作系统计算的一个独立任务
3、 作业与进程间的关系：作业是任务实体，进程是完成任务的执行实体；没作作业任务，进程无事可做；没有进程作业任务无法完成。 ###四、低级调度功能和类型 1、低级调度功能
（1）调度：实现调度策略，确定就绪态进程/线程竞争使用处理器的次序的裁决原则
（2）分派：实现调度机制，确定如何时分复用CPU，处理上下切换，完成进程/线程同CPU的绑定及放弃的实际工作
2、引发低级调度的事件：创建进程/线程、进程/线程终止、进程/线程阻塞、进程/线程运行过程中发生中断或异常、进程/线程执行系统调用、进程/线程请求的I/O操作完成、进程/线程耗尽时间片、进程/线程改变优先级等。
3、低级调度的类型 运行进程/线程时间片用完后被剥夺
剥夺式：高优先级进程/线程可剥夺低优先级进程/线程；
非剥夺式：一旦某个进程/线程开始运行后便不再让出处理器。
###五、作业调度和低级调度算法 1、先来先服务算法FCFS：（非剥夺式）有利于长、CPU繁忙型作业，不利于短、I/O繁忙型作业(只考虑作业等待时间而忽视计算时间)
2、最短作业优先算法SJF：（非剥夺式）总是选取预计计算时间最短的作业投入运行。（只考虑用户估计作业计算时间而忽视作业等待时间）
缺点：要预先知道作业所需的CPU运行时间、忽视作业等待时间、尽管能克服对长作业的偏爱，但由于缺少剥夺机制，对于分时，实时处理仍然不理想
3、最短剩余时间优先算法SRTF：（剥夺式）假设当前某进程/线程正在运行，若有新进程/线程移入就绪队列，若它所需要的CPU运行时间比当前运行进程/线程所需要的剩余CPU时间还短，抢占式最短作业优先算法强行剥夺当前执行者的控制权，调度新进程/线程执行。
4、最高响应比优先算法HRRF：（非剥夺式）介于FCFS和SJF的一种折中算法，既考虑作业等待时间又考虑作业处理时间 缺点：每次计算各道作业的响应比会导致一定时间开销，其性能比SJF算法略差
5、优先级调度算法：根据确定的优先级来选取进程/线程，总是选择就绪队列中优先级最高者投入运行。
6、轮转调度算法RR：（剥夺式）也称时间片调度，一个耗时型进程/线程需要经过多次轮转才能完成。
7、多级反馈队列调度算法MLFQ：又称反馈循环队列