处理机调度
调度的概念
从就绪队列中按照一定的算法（公平、高效的原则）选择一个进程并将处理机分配给它运行，以实现进程并发地执行
调度的层次
图示
高级调度
(作业调度)
是内存与辅存之间的调度
对于每个作业只调入一次、调出一次
则从外存上处于后备队列的作业中挑选一个或多个，IO等必要的资源，并建立相应的进程，以使它（们）获得竞争处理机的权利
中级调度
（内存调度）
目的
提高内存利用率和系统吞吐量
1.将那些暂时不能运行的进程调至外存等待，此时进程的状态称为挂起态
2.当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪态，挂在就绪队列上等待
低级调度
(进程调度)
按照某种算法从就绪队列中选取一个进程，将处理机分配给它
三级调度的联系
1）作业调度为进程活动做准备，进程调度使进程正常活动起来
2） 中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间
3） 作业调度次数少，中级调度次数略多，进程调度频率最高
4） 进程调度是最基本的，不可或缺
调度的目标(指标)
cpu利用率
系统呑吐量
单位时间内CPU完成作业的数量
周转时间
从作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队、在处理机上运行及输入/输出操作所花费时间的总和
平均周转时间
带权周转时间
平均带权周转时间
等待时间
进程处于等处理机的时间之和
衡量调度算法的优劣
响应时间
从用户提交请求到系统首次产生响应所用的时间
衡量调度算法的重要准则之一
响应比
调度的实现
调度程序(调度器)
概念
调度和分配cpu的组件
组成
排队器
管理就绪队列
分派器
进程从就绪队列中取出，将CPU分配给它
上下文切换器
第一对，将当前进程的上下文保存到其PCB中，再装入分派程序的上下文，以便分派程序运行(信息)
第二队，移出分派程序的上下文，将新选进程的CPU现场信息装入处理机的各个相应寄存器(现场)
执行大量load和store指令
通常采用两组寄存器(硬件)，其中一组供内核使用，一组供用户使用。这样，上下文切换时，只需改变指针，让其指向当前寄存器组即可
调度的时机、切换、过程
时机
不能切换的情况
1） 在处理中断的过程中
2） 进程在操作系统内核临界区中，外部如IO是可以切换的
3） 其他需要完全屏蔽中断的原子操作过程中
能切换的情况
1） 发生引起调度条件且当前进程无法继续运行下去
- 非剥夺
2） 中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志
- 剥夺
切换过程
(调度后立马进行)
1）将原进程的现场信息推入当前进程的内核堆栈来保
存它们，并更新堆栈指针
2）从新进程的内核栈中装入新进程的现场信息、更新当前运行
进程空间指针、重设PC寄存器等
3）运行新进程
进程调度方式
非抢占调度方式
(非剥夺)
当前进程运行结束或者进入阻塞态才重新分配处理机
适用于大多数的批处理系统，不能用于分时系统和大多数的实时系统
抢占调度方式
(剥夺)
按优先级分配
闲逛进程
系统中没有就绪进程，就会调度闲逛进程，执行过程中测试中断
两种线程的调度
用户级线程
由进程中的调度程序决定哪个线程运行
内核级线程
对被选择的线程赋予一个时间片，如果超过了时间片，就会强制挂起该线程
调度算法
先来先服务
FCFS
概念
同算法名
计算
特点
简单，效率低；
对长作业比较有利，短作业不利（相对SJF和高响应比）
有利于CPU繁忙型作业，而不利于I/O繁忙型作业
短作业优先
SJF
概念
同算法名(运行时间短)
计算
非抢占(默认)
抢占
特点
所有进程同时可运行时/抢占式点的短作业有限调度算法，平均等待时间、平均周转时间最少
完全未考虑作业的紧迫程度
导致长作业饥饿
根据用户提供的执行时间而定，用户会有意无意缩短(长或想先运行的)作业运行时间，不一定能真正做到短作业优先调度
优先级调度算法
概念
同算法名
方式
非抢占式优先级调度算法
当前进程运行结束或者进入阻塞态才分配处理机给优先级高的进程
抢占式优先级调度算法
立即暂停正在运行的进程，将处理机分配给优先级更高的进程
计算
抢占式
特点
平均等待时间、平均周转时间最少
静态优先级
- 优先级是在创建进程时确定的，且在进程的整个运行期间保持不变
动态优先级
- 根据进程情况的变化动态调整优先级
参照原则
-
系统进程 >用户进程
-
交互型进程 >非交互型进程（前台进程 >后台进程）
-
I/O型进程>计算型进程
- IO慢，让I/O设备尽早开始工作
完全未考虑作业的紧迫程度
导致长作业饥饿
根据用户提供的执行时间而定，用户会有意无意缩短(长或想先运行的)作业运行时间，不一定能真正做到短作业优先调度
高响应比优先调度算法
HRRN
概念
对FCFS调度算法和SJF调度算法的一种综合，先计算相应比，选出最高的投入运行
计算
特点
克服饥饿现象
综合FCFS、SJF
时间片轮转调度算法
RR
概念
FCFS+时间片
特点
时间片过大
退化为FCFS
时间片过小
频繁切换，开销大
计算
多级队列
概念
将不同类型或性质的进程固定分配到不同的就绪队列，每个队列可实施不同的调度算法
特点
统针对不同用户进程的需求，很容易提供多种调度策略
克服单一调度策略的缺点
多级反馈队列调度算法
概念
是时间片轮转调度算法和优先级调度算法的综合与发展
动态调整进程优先级和时间片大小
图示
实现思想
1） 设置多个就绪队列并赋予不同的优先级。第1级队列最高，第2级队列次之....
2）各个队列的进程运行时间片的大小各不相同。在优先级越高的队列中，每个进程的时间片就越小
3） 每个队列都采用FCFS算法，若时间内未完成，再放入下一优先级队列的队尾
4）按队列优先级调度，优先(抢占式)调度第一个非空的高优先级队列
特点(最牛)
1） 终端型作业用户：短作业优先。
2） 短批处理作业用户：周转时间较短。
3） 长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理。
进程切换
任何进程都是在操作系统内核的支持下运行的
上下文切换
概念
上下文
某一时刻CPU寄存器和程序计数器的内容
切换CPU到另一个进程，需要保存当前进程状态并恢复另一个进程的状态
流程
1） 挂起一个进程，保存CPU上下文，包括程序计数器和其他寄存器。
2） 更新PCB信息。
3） 把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列。
4） 选择另一个进程执行，并更新其PCB。
5） 跳转到新进程PCB中的程序计数器所指向的位置执行。
6） 恢复处理机上下文。
上下文切换的消耗
每次切换都需要纳秒量级的时间
有些处理器提供多个寄存器组，这样，上下文切换就只需要简单改变当前寄存器组的指针
上下文切换与模式切换
用户态和内核态之间的切换称为模式切换
上下文切换只能发生在内核态，它是多任务操作系统中的一个必需的特性
注：调度与切换区别
调度是决策行为
分配是执行行为
先有调度再有切换
作用
是多道程序操作系统的基础，是操作系统设计的核心问题
课后习题
FCFS调度算法比较有利于长(cpu繁忙型)作业，而不利于短(如IO繁忙型)作业
时间片轮转算法是按固定的时间配额来运行的，时间一到，不管是否完成，当前的进程必须撤下，调度新的进程，是绝对可抢占的
中断由硬件保护并完成，主要是为了保证系统运行可靠、正确。提高处理速
度也是一个好处，但不是主要目的