一、核心算法思想
1.先来先服务调度算法
先来先服务调度算法是一种最简单的调度算法,该算法既可以用于作业调度,也可用
于进程调度。当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多
个最先进入该队列的作业,将他们调入内存,为它们分配资源、创建进程,然后放入就绪队
列。在进程调度中采用 FCFS 算法时,则每次调度是从就绪队列中选择一个最先进入该队列
的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才
放弃处理机。FCFS 算法比较有利于长作业(进程),而不利于短作业(进程)。
2.短作业(进程)优先调度算法
短作业(进程)优先调度算法 SJ(P)F,是指对短作业或短进程优先调度的算法。它
们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择
一个或若干个估计运行时间最短的作业,将它们调入内存运行。而短进程(SPF)调度算法
则是从就绪队列中选出一个估计运行时间最短的进程,将处理机分配给它,使它立即执行并
一直执行到完成,或发生某事件而被阻塞放弃处理机再重新调度。SJ(P)F 调度算法能有效地
降低作业(进程)的平均等待时间,提高系统吞吐量。该算法对长作业不利,完全未考虑作
业的紧迫程度。
3.高响应比优先调度算法
在批处理系统中,短作业优先算法是一种比较好的算法,其主要不足之处是长作业的
运行得不到保证。如果我们能为每个作业引人动态优先权,并使作业的优先级随着等待时间
的增加而以速率 a 提高,则长作业在等待一定的时间后,必然有机会分配到处理机。该优先
权的变化规律可描述为:
优先权=(等待时间+要求服务时间)/要求服务时间
即 优先权=响应时间/要求服务时间
如果作业的等待时间相同,则要求服务的时间越短,其优先权越高,因而该算法有利
于短作业。
当要球服务的时间相同时,作业的优先权决定于其等待时间,等待时间越长,优先权
越高,因而它实现的是先来先服务
对于长作业,作业的优先级可以随着等待时间的增加而提高,当其等待时间足够长时,
其优先级便可以升到很高,从而也可获得处理机。
4.时间片轮转算法
在时间片轮转算法中,系统将所有的就绪进程按先来先服务的原则排成一个队列,每
次调度时,把 CPU 分配给队首进程,并令其执行一个时间片。当执行的时间片用完时,由
一个计数器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪
队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间
片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执
行时间。换言之,系统能在给定的时间内响应所有用户的请求。
二、核心算法流程图
评论0
最新资源