该方法按照进程到达的先后顺序排队，每次调度队首的进程（就像超市中购物付款一样）。
FCFS算法属于非剥夺调度方式，实现简单，看似公平。但是对于那些后进入队列而运行时间较短的进程，或I/O型的进程而言，可能需要长时间等待（对短进程以及I/O型进程不公平）
。
1.1 幼儿园小孩喂食问题
如果采用FCFS方法，让全部小孩排成一个先进先出的队列，老师从队首开始逐个给小孩喂食，只有当前一个小孩吃饱了，才喂食下一个小孩。那么，排在队列后面的的小孩将长时间不能被喂食而饥饿。
特别地，如果排在队列前面的某些小孩需要喂食的时间较长，而排在队列后面的某些小孩只需进食很少的饭量，却需要等待很长的时间。因此，该方法对这样的小孩不公平。
1.2 FCFS调度算法实例
假设：就绪队列中从队首开始依次排列有四个进程P1，P2，P3和P4（假设它们同时到达就绪队列），它们的预计执行时间分别为16，12，4和3个单位时间。若采用FCFS方法调度，试计算P1，P2，P3和P4的周转时间分别为多少？平均周转时间是多少？
1.3 FCFS调度算法综合评价
A: 对短进程不公平。
B: 由于长进程可能排在队列前面，必将增加队列后部进程的等待时间，从而将增加平均周转时间。
C: 不利于I/O型进程，未有效利用系统资源。
D: 一般地，FCFS与其他调度算法混合使用。例如，系统可以按照不同的优先级维护多个就绪队列，每个队列内部按照FCFS算法调度。
E: FCFS算法同时适合于长程、中程和短程调度三种调度类型。
2.短进程优先调度算法
当需要调度进程（或作业）时，通过计算判断就绪进程队列中哪一个进程的预期执行时间最短，或后备作业队列中哪一个或几个作业的预期执行时间最短，就调度谁。
2.1 如何预判断时间最短？？？
进程还没有执行，如何才能预测进程（或作业）的执行时间呢？？？操作系统内核的统计功能，进程终止没有退出系统还要停留一段时间，此时，就是操作系统的统计模块在执行功能。这样操作系统利用统计模块根据同类进程执行历史，来估计本进程的执行时间。该方法并不是十分精准的。
2.2 内容与实例
属于非剥夺调度算法。当某进程获得处理机，直到其执行完成，或需要等待某事件而阻塞时，才自动释放处理机。系统又调度新的进程（或作业）。
若采用短进程优先算法调度上例的4个进程，按照进程预期执行时间排序（升序）为P4，P3，P2，P1，试分别计算4个进程的周转时间和他们的平均周转时间。
在分时联机系统中，n个进程循环地获得时间片而执行。从系统中来看它们是交替执行的，但就每个终端用户而言，都感觉到自己独占了一台主机，不受其他用户的影响。这是通过进程
并发
执行实现的。
如果用户数太多，主机处理的进程将会急剧增加，进程排队等待的时间也会很长，进程的响应时间也可能增长，用户将明显感觉到主机的速度变慢而不满意。
时间片的大小也会影响进程的响应时间。（重点讨论时间片大小对CPU性能的影响）
3.1 时间片的设置
进程切换将会增加系统的额外开销（保护现场、恢复现场等）。
时间片设定得太短，进程切换会非常频繁，从而降低处理机的效率；时间片设定得太长，将无法满足交互式用户对响应时间的要求。
因此，时间片大小的确定应综合考虑系统的最大用户数、响应时间、系统效率等多种因素。
3.2例题分析
采用基于时间片轮转调度算法调度上例的4个进程，并分别按照两种时间片大小轮转调度（1个单位时间和4个单位时间），分析该算法的性能。
首先按照进程到达的先后顺序组织就绪队列，即P1,P2,P3,P4。从队首开始调度，首先调度P1，执行一个时间片，强行中断P1，P1回到就绪队列队尾排队；切换到P2，执行一个时间片，强行中断P2，P2回到就绪队列队尾排队（排在P1之后）…
计算等待时间以及周转时间：
注意：
1.为了简单，图中忽略了进程切换时的系统开销，而实际操作系统中，这类系统额外开销是客观存在的。
2.采用基于时间片轮转调度法，进程的周转时间和平均周转时间并不比采用FCFS和短进程优先调度算法小。
3. 加上进程切换所需的系统开销时间，该算法的平均周转时间还会增长。
3.3 综合评价
1. 常用于分时系统及事务处理系统，合理的时间片大小将带来满意的响应时间。
2. 通常，合理的时间片指，能让80%左右的进程在一个时间片内完成。
3. 对于短的、计算型的进程较有利。
4. 不适合于批处理系统的进程调度（任务量太大、中断太多、系统开销太大）
5. 不利于I/O型的进程。
改进的方法之一，可以将I/O阻塞事件完成的进程单独组织一个就绪队列，该队列进程的时间片可以设置的小一些，且优先调度。
4.基于优先级的调度算法
基于时间片轮转调度法循环式地为每个被调度的进程分配一个时间片，对每个进程都是公平的。
然而，实际应用中，进程的性质可能是不同的。例如，一个与用户进行交互的前台进程急迫地需要对用户的输入作出响应，而一个后台打印进程的迫切性也许就不那么重要。
因此，可以为每个进程定义一个优先级，优先级越高的进程将优先获得处理机的调度。
4.1 如何设定进程的优先级？
1. 进程完成功能的重要性 （用户与系统）
2. 进程完成功能的急迫性 （前台比后台急迫）
3. 为均衡系统资源的使用，指定进程（作业）优先级
4. 进程对资源的占用程度 例如，可以为短进程（或作业）赋予较高的优先级。
4.2 静态优先级与动态优先级
静态优先级：
一旦确定，则进程运行期间优先级一直不改变（管理简单，但是太死板）。
动态优先级：
系统首先赋予进程一个初始优先级，该优先级将随着进程的运行而改变。
典型的动态优先级变化方式为：
A - 优先级随着进程运行的剩余时间的减少而上升，使将要执行结束的进程尽快完成；
B - 随着进程排队等待时间的增长而上升，使等待时间越长的进程优先得到调度，不至于长时间饥饿。
具体实现方法，可以在每个时钟中断时，或需要进程切换时，重新计算就绪队列中各进程的优先级，并优先调度高优先级的进程。
采用动态优先级的两种调度算法：剩余时间最短者优先和响应比高者优先。
4.3优先级调动（剩余时间最短者优先调度算法）
为了使将要结束的进程尽早结束，释放系统资源，让别的进程执行。可以在每个时钟中断时，根据就绪队列中各进的剩余执行时间动态调整其优先级，剩余时间最短的进程优先级最高。
显然，该算法是剥夺型的短进程优先调度算法，调度程序总是选择剩余执行时间最短的进程调度执行。
算法评价：
1. 与短进程优先调度算法一样，该调度算法很难准确估计进程的剩余执行时间。
2. 长进程在未执行时，或刚开始执行的一段时间内，其剩余执行时间都不会最短，该算法对长进程不公平。
3. 但是，它不象FCFS算法偏袒长进程，也不象轮转调度算法会产生很多中断而增加系统负担。
4. 短进程提前完成，故采用剩余时间最短者优先的调度算法获得的平均周转时间比采用短进程优先算法短。
4.4优先级调动（响应比高者优先调度算法）
进程的等待时间w和进程的预期执行时间s纳入优先级的计算，进程（预期执行时间）越长优先级越低，而随着进程的等待时间增长优先级上升，即进程的优先级与等待时间成正比，与进程执行时间成反比。则响应比：
R = (W+S)/S = W/S + 1； R的最小值为1
调度方法：
若当前执行进程执行完毕，或需要阻塞等待某事件而释放处理机，调度程序选择就绪队列中响应比最大的进程执行。若等待时间相同，短进程因为s较小，R较大而优先调度。若进程的预期执行时间相同，则等待时间长的进程优先调度，相当于FCFS。随着等待时间的增加，长进程的响应比不断增大，在某个时刻，也必然被调度。
缺点：
同短进程优先和剩余时间最短者优先调度算法一样，很难准确估计进程的预期执行时间S。
每次调度之前都需要计算响应比，增加了系统开销。
京公网安备 11010802041100号