fcfs调度算法_王道操作系统学习笔记（四）进程调度
调度的概念
进程往往多于CPU的个数，不可能同时并行地处理各个进程。虽然并发可以解决多进程同时进行的问题，但是具体执行如何分配，这就是进程调度。
举例：银行普通用户先到先服务，VIP客户可优先服务。
调度三个层次
作业和进程区别
- 一个进程是一个程序对某个数据集的执行过程，是资源分配的基本单位。
- 作业是用户是要求计算机完成的某项任务所做工作的集合。（用在批处理系统，我的理解是批处理的bat文件，作业包括了至少一个进程，而且作业调度主要关心是外存调入内存的过程，进程是作业的执行过程）
高级调度（作业调度）
由于内存空间有限，无法将用户提交的作业全部放入内存，因此需要确定某种规则来决定作业调入内存的顺序。
高级调度（作业调度）：按一定原则从外存上处于后备队列的作业中挑选一个(或多个)作业，给他们分配内存等必要资源，并建立相应的进程（建立PCB），以使他们获得竞争处理机的权利。
中级调度(内存调度)
将暂时不能运行的进程调到外存等待。等它重新具备了运行条件且内存有空闲后，重新调入内存。
暂时调到外存等待的进程状态为挂起状态。值得注意的是PCB不会调到外存，而是会常驻内存。（因为PCB会记录进程数据在外存的存放位置，状态等信息，正是PCB才有下次调入的内容）
低级调度（进程调度）
按照某种方法和策略从就绪队列中选取 一个进程，将CPU分配给它。进程调度是操作系统中最基本的一种调度，频率很高。（后续的调度方法大多集中在于分析进程调度）
进程调度时机
进程调度的时机分为主动放弃和被动放弃。
主动放弃
- 进程正常终止
- 运行过程中发生异常而终止
- 进程主动请求阻塞
被动放弃（可以理解为进程还想执行）
- 分给进程的时间片用完
- 有更紧急的事需要处理
- 有更高 优先级的进程进入就绪队列
不能进行进程切换与调度的情况
- 处理中断的过程：中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
- 操作系统内核程序临界区：“临界区”是可以切换的，但“内核临界区”是不可以切换的。因为“内核临界区”通常是访问某种内核数据结构比如进程的就绪队列，需要对队列进行上锁无法调度和切换。
- 原子操作（原语）：原子操作不可中断，要一气呵成。
进程的切换是有代价的，如果过于频繁的进行进程调度，切换，必然使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。
调度算法评价指标
建议结合习题理解,因为这些题一般都需要给出运行时间和等待时间。所以一般都称为作业。普通进程无法估计完成时间的嘛
CPU利用率
CPU“忙碌”的时间占总时间的比例。
系统吞吐量
单位时间内完成作业的数量
周转时间
单个作业周转时间 = 作业完成时间-作业提交时间
带权周转时间
周转时间相同的两个作业，实际运行时间长的作业被服务的时间更多，带权周转时间更小，用户满意度更高。
等待时间
进程/作业 等待被服务的时间之和。进程可以被CPU服务，也可以被IO服务。等待时间是指它在就绪队列中等待的时间
响应时间
从用户提交请求到首次产生响应所用的时间。
调度算法
先来先服务（FCFS,First Come First Serve）
算法思想
主要从“公平”的角度考虑（类似我们生活中排队买东西）
算法规则
按照作业/进程到达的先后顺序进行服务
用于作业/进程
用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列
是否可抢占
非抢占式算法
优缺点
- 优点：公平，算法实现简单
- 缺点：排在长作业后的短作业需要等待很长时间，带权周转时间很大，短作业用户体验不好。对长作业有利，对短作业不利。
是否会导致饥饿
不会
短作业优先算法（SPF，Shortest Process First）
算法思想
在所有进程同时可运行时，采用短作业优先算法的平均等待时间，平均周转时间，平均带权周转时间最少。（因为类似贪心，对于减少了短作业的等待时间）
算法规则
最短的作业/进程优先得到服务（“最短”是指运行时间最短）
用于作业/进程调度
可用于作业调度，也可用于进程调度
是否可抢占
有抢占式算法，也有非抢占式算法
优缺点
- 优点：“最短的”平均等待时间，平均周转时间
- 缺点：不公平。对短作业有里，对长作业不利。可能产生饥饿现象
是否会导致饥饿
会，如果源源不断有短作业到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。
高响应比优先
算法思想
FCFS算法考虑等待时间（相当于等待时间长优先执行--先到），对长进程好。SPF算法考虑作业时间，对短进程好。
算法规则
每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。
响应比=等待时间+要求服务时间/要求服务时间
用于作业/进程调度
既可以用于作业调度，也可以用于进程调度
是否可抢占
非抢占式。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比。
优缺点
- 优点：综合考虑了SPF和FCFS的优点，当等待时间相同时，要求服务时间短的优先（SPF优点）；当运行时间相同时，等待时间长的优先（FCFS优先）。同时对于长作业来说，随着等待时间越来越久，响应比也会越来越大，从而避免了长作业饥饿问题。
是否会导致饥饿
不会
总结
时间片轮转(RR,Round-Robin)
算法思想
公平地，轮流地位各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则
按照各进程到达就绪队列地顺序，轮流让各个进程执行一个时间片(如100ms).若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队
用于作业/进程调度
只能用于进程调度(只有作业放入内存建立了相应地进程后，才能被分配处理机时间片)
是否可抢占
抢占式，当时间片结束了，进程会被强行剥夺处理机使用权
优缺点
- 优点：公平，响应快
- 缺点：由于高频率地进程切换，因此有一定开销；不区分任务地紧急程度
是否会导致饥饿
不会
时间片太大或太小有什么影响
时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
时间片太小，进程切换过于频繁，导致不必要地切换开销。
例子
优先级调度算法
算法思想
随着计算机地发展，特别是实时操作系统地出现，越来越多地应用场景需要根据任务的紧急程度来决定处理顺序
算法规则
每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程
用于作业/进程
都可以
是否可抢占
抢占式与非抢占式都有
优缺点
是否导致饥饿
是
例子
- 系统进程优先级高于用户进程
- 前台进程优先级高于后台进程
- 操作系统更 偏好I/O型进程（这样可以使I/O设备尽早投入工作，资源利用率，系统吞吐率都会得到提升）
- 如果进程在就绪队列中等待了很长时间，可以适当提高其优先级
- 如果进程占用 处理机运行了很长时间，可以适当降低其优先级
- 如果进程频繁地进行I/O操作，可以适当提高其优先级
多级反馈队列调度算法（又来缝合怪）
补充：
- 只有当第k级队列为空时，才会为k+1级队头的进程分配时间片
- 如果有新的进程，它会到达第一级队列，同时抢占时间片，被抢占的进程重新放回原队列尾
用于作业/进程调度
只用于进程调度
是否可抢占
抢占式算法，在k级队列的进程运行过程中，若更上级的队列(1-k-1级)中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会 抢占处理机，原来运行的进程放回k级队列队尾。
优缺点
对各类型进程相对公平（FCFS优点）；每个新到达的进程都可以很快就得到响应（RR的优点）；短进程只用较少时间就可以 完成（SPF优点）；不必实现估计进程的运行时间（避免用户作假）；可灵活地调整对各类进程的偏好程度，比如将因I/O阻塞的进程重新放回原队列，这样I/O进程就可以保持较高优先级）
一般不说它有缺点，不过可能导致饥饿
是否会导致饥饿
会，如果一直有新进程到达，就会导致饥饿
UNIX使用的就是多级反馈队列调度算法
