操作系统——作业、进程调度算法
目录
一、分级调度
二、作业调度
1、作业调度功能
2、调度目标与性能指标
三、进程调度
1、进程调度功能
2、进车调度时机
四、进程调度算法
1、先来先服务 FCFS
2、轮转法
3、多级轮转算法
4、优先级法
（1）静态法
（2）动态优先级
5、线性优先级
6、最短作业优先 SJF
7、最高响应优先
一、分级调度
四种调度级别：
作业调度（高级）：在外存选取作业，并建立相应进程，分配对应资源
交换调度（中级）：从外存的 就绪/等待队列中选取作业进入内存
或者 从内存的 就绪/等待队列中选取作业到外存
（内存->外存 / 外存->内存）
进程调度（低级）：从内存就绪的进程中选取进程，占有处理机执行
二、作业调度
1、作业调度功能
（1）记录系统中各个作业状况，包括执行阶段等相关情况
（2）从后备队列（外存）中挑一部分作业投入执行
（3）为被选好的进程分配资源
（4）作业执行完毕，做好善后工作
2、调度目标与性能指标
目标：公平、设备利用率高、尽可能调度更多进程、快速响应
性能指标：
（1）周转时间：改作业在系统内停留的时间：等待时间+执行时间
（2）带权周转：作业周转时间 与 作业执行时间 之比
三、进程调度
1、进程调度功能
（1）记录进程中所有进程执行情况
（2）选择进程占有处理机
（3）进程上下文切换
2、进车调度时机
（1）正在执行的进程执行完毕
（2）执行中进程自我阻塞进入睡眠
（3）I/O请求被阻塞
（4）系统调用完毕
（5）分时系统时间片用完
（6）就绪进程优先级比正在执行的进程高
（7）执行进程进行P、V操作导致资源阻塞
可剥夺方式：优先级高的换
不可剥夺方式：即使优先级高也不能先执行，只能P/V、I/O请求、时间片用完等才能换
四、进程调度算法
1、先来先服务 FCFS
所有进程按照顺序排列，逐个执行。A执行完，B执行，以此推之
优点：简单
缺点：不公平，尤其对短进程A，如果A前面有一个长进程B，那么A很久之后才能执行
2、轮转法
将CPU执行时间分成固定时间大小的时间片
例如，每个进程都只能执行一样的时间片
A执行时间到，不论执行完毕否，换，进入就绪队列，让B执行
轮转法只能调度可抢资源
什么意思？
什么叫做可抢？
你还在执行，我就抢过来用，叫做可以抢
什么叫做不可抢？
例如打印机
A在用打印机，B就不能抢
为什么？
因为打印机一旦打印，没有结束之前不能被中断
一旦中断，打印任务就错误了
因此，轮转算法不能用于作业调度
因为作业调度往往包含有不可抢资源
对时间片的选取：
过短，进程交换次数多，上下文切换多，开销大
过长，趋向先到先服务算法
如何选取时间片？
q = R / Nmax
R：响应时间
Nmax：就绪队列锁允许最大进程数
一般所有的进程都轮转执行一次，重新计算一次时间片
动态调整跟踪
3、多级轮转算法
在轮转算法中，进程加入就绪队列，有三种情况：
（1）时间片用完，但是没有执行完
（2）时间片没有用完，但是阻塞
（3）新建进程
原理：根据进程加入到就绪队列的类型 和 阻塞原因，将他们插入不同的就绪队列
原来只有一个就绪队列
现在有多个就绪队列
一个就绪队列同属于一个进程类型，优先级相同
说白了就是物以类聚
4、优先级法
可用作作业、进程调度
核心：确定进程的优先级，优先级高的先执行
如何确定优先级？
两种方法：静态 / 动态
静态优先级算法：执行前先确定，一旦执行，不可改变优先级
动态法：动态调整
（1）静态法
1、用户确定
2、由系统执行，根据作业类型，分配不同优先级
有以下不同类型：
I/O繁忙
CPU繁忙
I/O与CPU均衡
一般等级
3、系统根据资源分配优先级
系统进程比用户进程优先级高
（2）动态优先级
1、根据占有CPU时间长短决定
A占有时间长，被阻塞后，再被调度的优先级低（时间均衡）
2、等待时间长短决定
A在就绪队列等的时间长，被调度的优先级越高
缺点：动态调整，存在开销
5、线性优先级
轮转法，对长进程不公平
为什么？
短进程A新建立后直接进入就绪队列
也平等享受处理机时间片，和长进程一样
但是，就公平来说，
长进程应该占用更久的处理机
但是现在大家都一样，对长进程不公平
怎么办？
建立两个就绪队列：
一个新建立进程就绪队列 ：优先级P1 = a×▲t（a>0）
享受过服务的享受就绪队列：优先级P = b×▲t（a > b > 0）
那么，新建立进程什么时候进入享受队列，准备执行？
（1）当新建立进程就绪队列的优先级P1 和 享受过服务的享受就绪队列优先级P2相等
新创建进程就绪队列的第一个进程进入享受队列
（2）享受队列为空时，新建立进程进入享受队列
6、最短作业优先 SJF
谁短谁先执行
优点：吞吐量大
缺点：对长作业不公，有可能使长作业永远得不到调度
7、最高响应优先
R = （W+ T）/ T
（后备等待时间 + 执行时间）/ 执行时间
谁的R大，谁先执行
五、实时系统调度
什么叫实时系统？
在用户要求时间内做出响应处理
硬实时任务：要求时间内必须做出响应满足
软实时任务：允许对要求时间内有一定延迟
特点：
1、有限等待时间，一段时间内必须开始任务
2、有限响应时间，一段时间内必须完成任务
3、用户控制
4、可靠性高
5、处理差错强
相关系统特性：
1、很快的进程 / 线程切换速度
2、快速外部中断响应能力
3、基于优先级的随时抢先调度策略