操作系统总结:进程调度算法
衡量调度算法的性能
周转时间:周转时间是指作业从提交到作业完成所经历的时间。
周转时间: Ti= tci – tsi
tsi:表示作业i的提交时间
tci:表示作业i的完成时间
平均周转时间:
带权周转时间: W=T/R
T:周转时间
R:CPU运行时间
平均带权周转时间:
先来先服务法(FCFS: First-Come First-Served)
思想:每次从就绪队列中选择一个最先进入该队列的进程,把CPU分给它,令其运行。该进程一直运行下去,直至完成或由于某些原因而阻塞,才放弃CPU。。
该算法属于非抢占式。
优点:
- 简单,易于理解,容易实现。
- 有利于长作业(进程),有利于CPU繁忙型作业(进程)。
缺点:
- 不利于短作业(进程),不利于I/O繁忙型作业(进程)。
- 效率较低。
适用于作业调度、进程调度。通常与其他算法结合起来使用
短作业优先法(SJF: Shortest-Job-First)
思想:当调度机分配CPU时,选择所需处理时间最短的进程。短进程将越过长进程,跳到队列头。一个进程一旦分得处理机,便执行下去,直到该进程完成或阻塞时,才释放处理机。
该算法属于非抢占式,这是对 FCFS 算法改进,其目标是减少平均周转时间。
优点:
对于一组给定的作业,SJF算法能给出较小的平均等待时间,提高了系统的吞吐量。
缺点:
-
实现上有困难,需要知道或至少需要估计每个作业/进程所需要的处理时间。
-
对长作业(进程)不利。
-
不能保证及时处理紧迫作业(进程)。
作业调度用的多,进程调度用的少。
高响应比优先法(Highest Response Ratio First)
思想:为每个作业计算一个响应比:
在调度作业时,挑选响应比最高的作业运行。若作业等待时间相同,则要求服务的时间越短,其响应比越高,有利于短作业。当要求服务时间相同时,作业的响应比由其等待时间决定,等待时间越长,响应比越高,因而它实现的是先来先服务。
非抢占式算法:
优点
是对FCFS和SJF调度算法的综合平衡,同时考虑每个作业的等待时间和估计需要的运行时间。
缺点**
调度前需要计算作业的响应比,增加系统开销。
主要用于作业调度。
优先级法(PS:Priority Scheduling)
思想:优先级调度算法是从就绪队列中选出优先级最高的进程,让它在CPU上运行。
确定优先级的方式有两种:静态方式和动态方式。
- 静态方式:在创建进程的时候就确定下来了。
- 动态方式:随着进程的推进而不断改变。
该算法也有两种处理优先级高的方法:非抢占式和抢占式。
- 非抢占式:当就绪队列中出现优先级高的进程,运行完当前进程再选择优先级高的进程。
- 抢占式:当就绪队列中出现优先级高的进程,当前进程挂起,调度优先级高的进程运行。
用于作业调度或进程调度
最短剩余时间优先法 (SRTF:Shortest Remaning Time First)
思想:当新进程进入就绪队列时,如果它需要的运行时间比当前运行的进程所需的剩余时间还短,则执行切换,当前运行进程被剥夺CPU的控制权,调度新进程运行。
该算法属于抢占式。
优点:
- 保证新的短作业一进入系统就能很快得到服务,平均等待时间短。
缺点:
- 为保存进程断点现场,统计进程剩余时间增加了系统开销。
- 不利于长作业。
作业调度用的少,进程调度用的多。
时间片轮转法(RR:Round Robin)
思想:将系统中所有的就绪进程按照FCFS原则,排成一个队列。每次调度时将CPU分派给队首进程,让其执行一个时间片。
在一个时间片结束时,发生时钟中断。调度程序暂停当前进程的执行,将其送到就绪队列的末尾,并通过上下文切换执行当前的队首进程。
该算法属于抢占式算法:
时间片的选择由以下因素决定:
- 系统的响应时间
- 就绪队列中的进程数
- 系统的处理力
时间片大小通常为 10 ~ 100ms 之间
时间片长度的选择对于算法的影响:
- 时间片过长:该算法退化为 FCFS(先来先服务) 算法,进程在一个时间片内执行完
- 时间片过短:一个进程需要多个时间片才能执行完,频繁的上下文切换次数增加。
- 最优的选择:选择单个时间片多数进程能够完成他们的运行工作,平均的周转时间会增加。
多级队列法(MQ:Multilevel Queue)
思想:调度算法把就绪队列划分成几个单独的队列,一般根据进程的某些特性,如占用内存大小、进程优先级和进程类型,永久性地把各个进程分别链入不同的队列中,每个队列都有自己的调度算法。比如前台进程队列可采用轮转法,后台进程队列可采用先来先服务法。
队列之间,采用固定优先级的抢占式调度。
多级反馈队列法(MFQ:Multilevel Feedback Queue)
思想:
① 系统中设置多个就绪队列,每个队列对应一个优先级;
② 各就绪队列中进程的运行时间片不同,高优先级队列的时间片小,低优先级队列的时间大;
③ 新进程进入系统后,先放入第1个队列的末尾,如果在时间片内工作未完成,则转入下一个队列尾,依此类推;
④ 系统先运行第1个队列中的进程,若第1队列为空,才运行第2队列,依次类推。
特点:
- 抢占式调度
- 动态优先级
- 需要解决“饥饿”问题
- 是最通用的CPU调度算法,也最复杂。
优点:
-
终端型作业用户:短作业优先。
-
短批处理作业用户:周转时间较短。
-
长批处理作业用户:不会长期得不到执行。