美文网首页
《Operating Systems: Three Easy P

《Operating Systems: Three Easy P

作者: 美航球馆 | 来源:发表于2020-05-06 14:01 被阅读0次

    背景

    从这章开始,我们将开始讨论 scheduling policies,主要讲了在做 process 切换的时候,我们如何做决定切换到哪个 process。在阅读这章原文的时候,除了学到各种 scheduling policies,我觉得更重要的是这篇文章所展现的方法论。它没有直接告诉我们现在操作系统所使用的 scheduling policies 是什么,而是先做些假设,将操作系统会面对的情况简单化,然后提出一个简单的 policies。最后,通过否定假设来不断修正 policies,最终达到一个符合目的的 policies。

    Process VS Job VS Task

    首先书本里出现了两个令人费解的 term,process 和 job。书里认为这两个是一样的,但是我还是去查了下这两者的区别。这个回答 可以仔细看下,基本上这三者没有太大的区别,只是从不同的 context,会有不同的叫法

    假设

    首先我们对 job 做了以下的假设:

    • 所有的 job 运行的时间都是一样的
    • 所有的 job 都是同时到达
    • 一旦一个 job 开始了,在完成之前都无法被结束
    • 所有的 job 都只使用 CPU
    • 每个 job 运行时间都是已知的

    我们可以看到,这些所有假设在现实中都是不成立的,但是基于这些假设,我们就有思路了,可以很快制定一些 policies。

    度量

    在考虑 polices 之前,我们要先确定如何衡量我们制定的策略。现在我们先主要考虑两个 metrics:

    • turnaround time


      turnaround time.png
    • response time


      Response Time.png

    这两个都很简单,就不解释了。

    First In, First out

    这个策略就是,哪个 job 先进来,就先执行(First Come,First Served)。这个策略的优点就是简单,很容易实现,在我们的假设下,是非常完美的符合。来看下书中的例子:


    FIFO example.png

    A 的 turnaround time 是 10, B 的turnaround time 是 20 ,C 的 turnaround time 是 30,平均下来就是 20。接下来我们开始去掉我们的假设,在慢慢改进我们的策略。

    首先,去掉 假设1。我们可以很容易想到一种情况,会导致 turnaround time 变的非常糟糕。

    Why FIFO Is Not That Great.png
    这个时候,A 的 turnaround time 是 100, B 的 turnaround time 是 110,C 的turnaround time 120,平均下来 turnaround time 是 110,跟之前相比就是一个非常糟糕的数字了。这个问题就是我们常说的 convoy effect

    Shortest Job First (SJF)

    要解决上面这个问题,我们可以采用一个新的算法,即先运行时间最短的。这样的话运行图就会变为:

    SJF Simple Example.png
    这个的平均 turnaround time 是 50,马上就提升了两倍。接着我们在去掉假设 2,这又会带来什么问题呢?来看个图就知道了: SJF With Late Arrivals From B and C.png
    因为 B 和 C 都第 10 秒才到的,所以根据我们当前的算法来说,这个的 turnaround time 是 103.333,这就又引起了 convoy effect

    Shortest Time-to-Completion First(STCF)

    要解决这个问题,首先我们需要去掉 假设3,然后当有 job 进入的时候,操作系统会看哪个进程可以最快完成,就先运行哪个,然后在切换回来。所以我们之前的那个运行图就变为: STCF Simple Example.png

    这个算法的平均 turnaround time 是 50,这个就非常接近第一个算法。那这个算法的问题又是什么呢?这就涉及到我们第二个 metric,response time。

    Response Time

    现代的计算机对 responsive 要求很高,用户触发了什么之后,是希望立即得到反馈,SJF 的 response time 是 3.33(A 和 B 是 0, C 是 10),可以看到不是很好,那我们如何优化这个点呢?

    Round Robin

    这个算法的基本内容就是,每个进程运行一段时间(这个时间段我们称为 time slice),直到所有的进程运行结束。那运行图就会变为:

    Round Robin.png
    这个的 average response time 就是 1,就快了很多。那这个算法又有什么问题?
    1. turnaround time 一般会比较差
    2. 如果 time slice 设置的比较短,context switch 频繁发生,那 switch 的代价会比较高。

    所以这就是一种权衡(tradeoff),注重 turnaround time ,response time 就会差,反之亦然。接下来,我们再来否定最后两个假设。

    Incorporating I/0

    现在我们再来看下有 I/O 发生的情况下,我们的算法会发生什么样的变化。假设我们有两个 jobs: A 和 B,它们都需要消耗 50 ms 的 CPU 时间。A 每运行 10 ms 会发起一次 I/O request(假设每次 I/O request 需要 10 ms 来完成),B 不会。那运行图为: Poor Use Of Resources.png
    这个解决方式也很简单: Overlap Allows Better Use Of Resources.png

    只需要在CPU 有空闲的时候,运行 B job 就好了。

    最后

    我们还需要搞定最后一个假设,即如何在不知道一个 job 的运行时间情况下,制定我们的 schedule policies,这个我们就留到下一章来讲。

    相关文章

      网友评论

          本文标题:《Operating Systems: Three Easy P

          本文链接:https://www.haomeiwen.com/subject/cqpvghtx.html