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

调度算法的概念

在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
    小恐龙
    花!
    上一篇
    下一篇