先来先服务和短作业优先调度算法
本文最后更新于1300天前,其中的信息可能已经有所发展或是发生改变。

调度算法的概念

在OS中调度的实质是一种资源分配,因而调度算法是指:根据系统的资源分配策略所规定的资源分配算法。

对于不同的系统和系统目标,通常采用不同的调度算法:例如,在批处理系统中为照顾为数众多的短作业,应采用短作业优先的调度算法;又如在分时系统中,为了保证系统具有合理的响应时间,应采用轮转法进行调度。

目前存在的多种调度算法中,有的算法适用于作业调度,有的算法适用于进程调度;但有些算法作业调度和进程调度都可以采用。

几个运算概念

进程从进入外存的后备队列就已经算是进入了系统,之后经历进入内存,使用CPU,执行完毕/进入阻塞。

周转时间T = 在后备队列的时间t1 + 在内存的时间t2 + 使用CPU的时间t3 + 阻塞的时间t4

平均周转时间 = (T1 + T2 + T3 +... + Tn) / n

带权周转时间 = T / t3

平均带权周转时间 = (T1 / t3 + T2 / t3 + T3 / t3 +... + Tn / t3) / n

先来先服务调度算法(FCFS)

是一种最简单的调度算法,既可用于作业调度,也可用于进程调度。

当在作业调度中采用FCFS算法时,每次调度都是从后备作业队列中,选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪队列;

进程调度采用FCFS算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之运行。

FCFS算法比较有利于长作业(进程),而不利于短作业(进程)。

例题1

下表列出了A、B、C、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间,并计算出各自的周转时间和带权周转时间。

(1)在先来先服务调度算法的基础上使用非抢占原则:

(2)在先来先服务调度算法的基础上使用抢占原则:由于该算法首要遵循的就是先来先服务,所以会严格按照先后顺序执行,FCFS                   算法在非抢占和抢占原则上是相同的。

从表格得到:C作业的带权周转时间高达100;而D作业的带权周转时间仅1.99;可以认为C作业并没有频繁使用CPU而是请求外设,被阻塞,结束了时间片。D作业是一直频繁的使用CPU。

所以可以总结:FCFS调度算法有利于CPU繁忙型的作业(如通常的科学计算),而不利于I/O繁忙型的作业(指CPU进行处理时,需频繁的请求I/O)。也就是说,FCFS算法比较有利于长作业(进程),而不利于短作业(进程)。

短作业(进程)优先算法(SJ(P)F)

短作业优先(SJF)的调度算法,是从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行。

短进程优先(SPF)调度算法,是从就绪队列中选出一估计运行时间最短的进程,将处理机分配给它,使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时,再重新调度。

例题2

采用SJF算法后,不论是平均周转时间还是平均带权周转时间,都较FCFS调度算法有较明显的改善,尤其是对短作业D。而平均带权周转时间从2.8降到了2.1。这说明SJF调度算法能有效的降低作业的平均等待事件,提高系统吞吐量。

从表中仍能看出,长作业的带权周转时间边长了,所以该算法对长作业不利。该算法也没有考虑作业紧迫程度,不能保证急迫性作被及时处理。最重要的是,作业的长短是事先估计出来的,包含主观因素,不一定能真正做到短作业优先。

点击数:127

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇