422_磁盘调度算法
# 4.2_2_磁盘调度算法
各位同学大家好，在这个小节中我们会学习一个很重要很高频的考点磁盘调度算法，首先我们会介绍一次读磁盘操作或者一次写磁盘操作到底需要多少时间，我们应该怎么计算。它总共分为寻道时间、延迟时间和传输时间这样三个部分
磁盘调度算法的不同会影响寻找时间的长短，所以选择一个合适的磁盘调度算法，对于磁盘的整体性能来说是会有很大的影响的，我们重点需要掌握的是列出的这 4 种算法，我们会进行一一的介绍。
# 一次磁盘的读/写操作需要的时间
首先我们来看一下一次磁盘的读或者写操作需要多少时间。首先我们在确定了我们想要读取的那些数据是存放在哪一个磁道上之后，就需要把磁头移动到指定的磁道上去，所以其实移动磁头的过程是需要花费一定的时间的。咱们在上一小节的结尾处也有简单的提及过
首先我们知道磁头是由磁头臂带动的，所以在移动磁头之前是需要先启动磁头臂，需要花费一定的时间，假设需要花 s 这么多。
第二在磁头臂启动之后就可以开始由磁头臂带动磁头，也就是移动磁头，移动磁头的过程也是需要一定时间的，假设我们的磁头是匀速移动的，每跨越一个磁道耗时是 m 这么多，总共需要跨越 n 条磁道，总共的耗时就应该是 m 乘以 n。所以其实整个寻找时间或者说寻到时间就应该是启动磁头臂的时间 s，加上移动磁头的时间 m 乘以 n。
关于文字描述的话可能会比较抽象，我们来结合一个动画来加深理解。假设此时我们要读取的是橙色这个部分这些小扇区当中的数据，由于这些扇区是在最里边的磁道上的，所以我们需要把磁头移动到最里边的道上，才可以读取磁道上面的数据。
因此我们首先要做的事情是，第一要启动磁投臂，这个过程总共花 s 秒。第二，它需要移动这么多的磁道，每一条磁道的耗时是 m，所以移动的过程总共的耗时应该花 m 乘以 n，所以在寻找磁道上花费的总时间就应该是 s 加上 m 乘以 n。
现在这些硬盘移动一个磁道大约是需要 0.2 毫秒，然后磁臂的启动时间大约是两毫秒这么多，这是读写操作要进行的第一个步骤，就是寻到寻找对应的磁道。
第二个读写操作需要花费的时间叫延迟时间，延迟时间就是指要我们通过旋转磁盘，使磁头定位到目标上区所需要的时间。
假设我们磁盘的转速为 r 转每秒，或者 r 转每分钟，延迟时间就可以用这样的公式来计算。由于磁盘的转速是 r，所以这儿的 r 分之 1 就应该是磁盘转一圈所需要的时间。
另外定位到目标扇区平均是需要转半圈磁盘的，所以这个地方又会乘以一个 1/2，最后化简就等于 1/2r，
我们依然通过动画的方式来看一下延迟时间指的是什么。现在我们的这个磁头已经定位到了他想要读取的磁道上，但是他想要读取的这些扇区也就是橙色部分，此时暂时还没有到磁头的下面。所以为了让这些扇区能够转到磁头下面，让磁头能够读取其中的数据，就需要转动磁盘，那么转动磁盘所消耗的时间就是咱们所谓的延迟时间。
现在市面上可以买到的那些机械硬盘，典型的转速是 2500 转每分钟或者 7200 转每分钟，大家可以去京东淘宝上搜一下，看一下那些磁盘的转速这个参数。从这个地方我们可以看到磁盘的转速越高，它的延迟时间会越小，也就是说磁盘的读写速度越快，因此如果我们自己买磁盘的时候，可以在经济允许的情况下可以买一个转速更高的磁盘，这是读写操作过程中需要花费的第二个部分的时间，延迟时间。
第三个部分的时间叫传输时间，就是指从磁盘读出或者向磁盘写入数据所要经历的时间。假设我们磁盘的转速是 r 状每秒，并且每个磁道上可以存放的数据是 n 个字节这么多，而这一次我们要读或者说要写的字节数是 b 个字节这么多，传输时间就应该是 1/r * b/n 为什么有这样的算法？因为我们每个磁道上可以有 n 个字节，所以我们此次要读取的 b 个字节需要存储在 b/n 个磁道上，也就是说我们的磁头需要读取 b 除以 n 个磁道，每读写一个磁道所需要花的时间，又刚好是磁盘转一圈所需要的时间，也就是 1/r，所以这个地方的传输时间就等于转一圈所需要的时间再乘以总共需要转几圈，最后化简可以得到 b/rn，
我们还是结合动图来看一下传输时间指的是哪个部分。通过寻道时间还有延迟时间这两个部分之后，我们的磁头此时已经放在了想要读取的扇区的开头的位置，接下来要读取这些扇区的数据，就需要继续转动磁盘，转动磁盘所需要的这些时间就是所谓的传输时间。
因此一次读磁盘的读或者写操作总共需要的时间就应该是寻道时间 + 延迟时间 + 传输时间，就是这样一个式子。从延迟时间和传输时间的计算公式，大家也可以发现延迟时间和传输时间这两个参数其实是和磁盘的转速有关的，并且是一个线性相关的关系，转速越快，延迟时间越短，传输时间也越短。不过转速它是硬盘这种硬件的固有属性，操作系统不可能用软件的方式来加快磁盘的转速，所以延迟时间和传输时间是操作系统无法优化的两个部分的时间，操作系统唯一可以影响的时间就是寻到时间，根据不同的磁盘调度算法，寻到时间会有很大的差异，我们接下来会开始学习各种需要掌握的磁盘调度算法。
# 先来先服务
首先来看第一种叫做先来先服务算法，这种算法很简单，就是根据进程请求访问磁盘的先后顺序来进行调度。比如说此时磁头是放在了 100 号磁道那个位置上，有多个进程先后陆陆续续的请求访问 55 号，58 号，39 号，18，90， 160、150 38 和 184 号磁道。根据这些请求到达的这种先后顺序，还有先来先服务算法的这种思想。磁盘在响应这些访问的请求的时候，就需要按照这些请求到来的先后顺序来依次的响应
所以磁头本来是放在 100 号磁到这个位置的，第一个它需要响应的是 55 号磁道，所以它会从 100 号磁道移动到 55 号磁道。接下来需要响应的是 58 号磁道，所以需要从 55 号移动到 58 号磁道，再接下来又要移动到 39 号，在接下来移动到 18 号磁道，以此类推，所以整个过程大家分析下来会发现磁头总共移动了这么多，总共是 498 个磁道，
这个地方 100 号移动到 55 号隧道，总共是移动了 100-55，也就是 45 个磁道。55 移动到 58 号隧道总共是移动了 58-55，也就是三个磁道，其他的这些计算方式也雷同。
总之按照先来先服务调度算法来响应这些迟到的访问请求的话，处理这 9 个请求总共移动了 498 个磁道，平均每处理一个请求，需要移动的磁道数就应该是 498 除以总共处理的请求数也就是 9 个等于 55.3 个磁道，这是平均寻找的长度。
所以先来先服务算法的优点是很公平，先来的就先得到服务，并且如果请求访问的那些磁道是比较集中的话，那么这个算法的性能还算可以。
不过这个算法的缺点也很明显，如果有大量的进程竞争的使用硬盘，并且请求访问的磁道很分散的话，那么先来先服务算法的性能就会很差，它在性能上其实是近似于随机调度算法，相应的如果要访问的这些磁道很分散的话，那么先来先服务算法的寻道时间就会很长，平均寻找长度也会很长。
# 最短寻找时间优先算法
接下来我们看第二种叫做最短寻找时间优先算法，这个算法的思想是要优先处理此时与当前磁头离得最近的磁道，这样的话可以保证每一次寻到时间都是最短的，但是虽然每一次的寻到时间最短，不过总体上并不能保证总的寻道时间最短，这其实是和贪心算法一样的思想，只是选择眼前最优的，但是总体上未必最优。
还是用刚才的例子来看一下。刚开始磁头是指向了 100 号这个位置，根据最短寻找时间优先算法的规则，它首先需要满足的是离当前磁头最近的磁道的访问请求，离他最近的应该是 90 号，因为离他只有 10 个这么远，而 150 号磁道离它有 40 个磁道这么远，所以刚开始应该先响应 90 号磁道的请求。
接下来离 90 号辞到最近的应该是 58 号辞道，再接下来应该是 55 39 30 88，所以他会按照从右到左的顺序依次处理 9018 号辞道这些请求。当磁头移动到 18 号磁道处理完 18 号磁道的请求之后，此时离磁头最近并且还没处理的请求，就应该是 150 号磁道，所以接下来会从 18 号移动回150 号磁道，在接下来移动到 160，最后是 184，所以整个过程总共移动了 248 个磁道。
首先是从 100 号磁道依次移动到了 18 号磁道，所以它中间总共移动了 100-18 这么多个磁道。那之后又从 18 号磁道依次移动到了最右边的 184 号隧道，所以往右移动这个过程又应该是移动了 184-18 这么多个磁道，总共是 248 个磁道。248÷9 可以算得平均寻找长度应该是 217.5 个磁道
相比于之前的来先服务算法来说，平均寻找长度平均的寻找时间就变得少了很多了。所以最短寻找时间优先算法的性能是比较好的，平均寻找时间也比较短，但是这种算法的缺点是有可能会产生饥饿现象。
来结合这个例子进行分析。假设现在我们的磁头依次处理完了前面的这些请求之后，此时是指向了 18 号磁道这个位置，在处理 18 号辞道的请求的时候，又来了一个 38 号的请求，所以在处理完 18 号磁道之后，所以如果系统当中有源源不断的 18 号磁道和 38 号磁道的请求到来的话，那么这个磁头就会一直循环着为 18 号和 38 号磁道进行服务，而这边暂时没有处理的 150 ，160 和 140， 84 号磁道的这些访问请求会一直得不到处理，这样的话就导致了这边的这些请求长期得不到服务的现象，也就是发生了饥饿。
从分析过程当中我们也可以发现，其实最短寻找时间优先算法，它产生饥饿的原因在于我们的磁头有可能会在一个小区域内来回来去的移动，只要在小区域内有源源不断的请求到来，那么他会一直在小区域内，而没办法跳出这个区域，为其他区域的这些请求进行服务。因此为了解决这个问题，人们又提出了扫描算法
# 扫描算法
那扫描算法规定只有磁头移动到最外侧磁道的时候才可以往内侧移动，只有移动到最内侧磁道的时候才可以开始往外侧移动。由于磁头移动的方式比较像我们平时乘坐的电梯，所以这个算法也可以称作为电梯算法，我们还是结合刚才的那个例子来进行分析。
假设磁盘的磁道总共有 0~200 号这么多，然后磁头刚开始的初始位置是 100 号磁道，并且此时磁头是正在往磁道号增大的方向移动，也就是向右边这个方向移动。
如果说还是和刚才一样有这么一些请求的话那，按照扫描算法的规则，这个磁头首先是要往右边移动，然后处理右边与他最近的请求，也就是 150 号磁道的访问请求，处理完 150 号磁道之后再往右处理，160 号之后再往右处理 184 号。然后由于扫描算法要求磁头必须移动到最外侧的磁道才可以开始往内移动，所以即使 184 号磁道的右边已经没有了需要处理的那种磁道访问请求了，但是它依然需要把磁头移动到最外侧的磁道，也就是 200 号磁道这个位置，只有到了最外侧之后才可以开始往另外的这个方向移动。
磁头往左移动的时候，这个方向上第一个没有处理的请求应该是 90 号磁道的访问请求，所以它首先会停留在 90 号磁道。接下来就是依次处理 58 55 39，然后一直到 18
所以我们采用扫描算法，处理完这么多的磁道访问请求的时候，总共移动了这么多个磁道，第一个部分是从 100 移动到 200，也就 200-100，总共移动了 100 个磁道。第二个部分是从 200 号磁道往左依次移动到了 18 号磁道，所以这个部分又移动了 200-18，所以总共是 282 个磁道，平均的寻找长度就应该是 282÷9=31.3 个磁道，可见这种算法的平均寻找时间要比先来先服务算法也要好很多。虽然说平均寻找长度，平均寻道时间要比最短寻找时间优先算法要更次一些，但是这种算法的规则带来的好处就是它不会产生饥饿现象
不过这个算法也有一些缺点，第一，只有到达最边上的磁道的时候，才可以开始改变磁头的移动方向。但事实上我们在处理完184 号磁道的访问请求之后，这个磁头其实就不需要再往右移动了，他就可以立即开始回头，所以这是扫描算法第一个可以优化的地方。
第二个扫描算法的缺点是它对于各个位置的磁道响应频率是不平均的，什么意思呢？假设此时这个磁头正在往右移动，并且刚刚处理过了 90 号磁道，那么下一次处理 90 号磁道的请求，就需要等到磁头移动到最右边，然后再开始再往回移动，再移动到 90 号磁头这个位置的时候，才可以再次响应90 号磁道的访问请求，这期间需要等待比较长的一段时间。但是对于比较靠近边上的这些渠道来说，比如说 184 号磁道，此时磁头也是正在向右移动，并且刚处理完 184 号磁道的访问请求。那么 184 号磁道的访问请求再一次被满足的时候，就应该是磁头移动到最边上，然后再回到这个位置的时候，就可以再次的服务 184 号磁道的访问请求了。
所以在刚才咱们分析的场景当中，对于 90 号磁道的访问频率要更低一些，而对于 184 号磁道的访问频率要更高一些，这是扫描算法可以在改进的第二个地方。
我们首先看一下第一个缺点应该怎么改进。在扫描算法中只有到达最边上的磁道的时候，才可以改变磁头的移动方向，为了解决扫描算法的第一个缺点，人们提出了一叫做 look 调度算法
# look 调度算法
这个算法与扫描算法相比增加了这样的一种策略，就是如果在磁头移动方向上已经没有别的请求了，那么就可以立即改变磁头的移动方向。所以其实这个调度算法有点类似于是一边移动磁头一边观察前边还有没有别的请求，这样的一个过程，所以它叫 look 方法。
还是以刚才的例子为例，现在磁头是在 100 号磁道并且正在向右移动，那么这个磁头依次会访问到 150 160 184 号磁道，不过在访问了 184 号磁到之后会发现此时磁头的移动方向，也就是右边这个方向已经没有别的请求需要处理了。所以到了 184 号磁道之后，就可以立即改变磁头的移动方向，让它往左边往回移动，
所以接下来这个磁头会开始处理 90 号磁道，在接下来是 58 55，最后一直到 18 号磁道的请求。所以整个过程下来磁头总共移动了 250 个磁道，平均的寻找长度就是 27.5 个磁道，在之前扫描算法当中平均寻找长度是 30 多个，所以采用 look 调度算法这种策略的话，那找长度平均寻找时间就进一步的得到了缩短。
# C-SCAN 算法
接下来我们再来看一下扫描算法的第二个缺点应该怎么解决？他的第二个缺点是对于各个位置的磁道响应频率不平均。为了解决这个问题，人们提出了 C-SCAN 算法也叫循环扫描算法，这种算法规定只有磁头朝某一个特定方向移动的时候，才会处理磁道的访问请求，而在磁头返回起点的这个过程中，会直接快速的移动到起始端的位置，而不进行任何的请求处理。
我们依然结合刚才的例子来看，假设此时这个磁头是放在了 100 号磁道的位置，并且此时这个磁头是正在向右移动。那么采取循环扫描算法的话，这个磁头首先是会向右边的最近的磁道进行服务，也就服务 150 号磁道的访问请求，接下来是 160，再接下来是 184，再接下来这个磁头依然是需要移动到最边缘的位置，也就是 200 号磁道这个地方，
当磁头达到边缘之后，就需要让磁头返回到起始端的位置，并且这个返回的过程是不进行任何处理的。所以接下来这个磁头会直接从 200 号磁道直接移动回 0 号磁道中间不进行任何处理，那之后磁头又会开始下一轮的扫描，同样在这个磁头向右移动的时候才可以处理这些请求，所以接下来他会处理 18 号磁道的访问请求，再接下来是 38一直到 90 号磁道，这就处理完了所有的这些磁道访问请求。
所以在这个过程中磁头总共移动了 390 个磁道这么多，平均的寻找长度就是 43.3 个字段。所以 C-SCAN 算法或者说循环扫描算法，它比起 scan 算法来说，对各个位置的这种磁导的响应频率就变得很平均了。
比如说此时刚刚服务过 150 号磁道的访问请求，那么下一次要响应 150 号磁道的访问请求，就需要等到磁头先慢慢的移动到最右边，然后再回到起点，然后再回到 150 号磁道才可以进行下一次的响应，对于其他位置的这些磁道来说也一样，在刚刚服务过磁道的请求之后，下一次想要访问这个磁道，就需要等这个磁头先移动到最右边，然后再回到最起点，然后再回到这个位置，所以不管是哪一个磁道，对他们的这种响应频率都是很平均的
不过和 SCAN 算法类似，这种算法有一个很明显的缺点，只有到达最边上的磁道之后才可以开始改变磁头的方向。但事实上我们处理了是 184 号磁道的请求之后，就没有必要再让磁头再往右移动了。另外当磁头返回的时候会发现这个磁头返回的时候，是直接返回到了最左边的磁道，也就是 0 号磁道这，虽然 0 号磁到此时并没有任何请求需要被服务，但事实上其实我们只需要让磁头返回到 18 号磁到这个位置就可以了，所以这个也是一个可以优化的地方。为了解决 CS 杠算法的这些缺点，人们又提出了 C-LOOK 算法。
# C-LOOK 算法
C-LOOK 算法和 look 算法其实是很类似的，也是采用了同样的思想，如果磁头移动的方向上已经没有任何磁道访问的请求了，那就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置就可以了
我们还是用刚才的例子为例，此时这个磁头停留在 100 号磁道，并且是正在向右移动，那向右移动的过程中他会依次处理这些磁道的请求，在访问了 184 号磁道之后，再往右的位置已经没有别的磁道需要被访问了，所以到了这个位置就可以开始让磁头往回移动，并且磁头只需要移动到最靠左的一个需要被访问的磁道，也就是 18 号磁道这个位置，而不是直接返回到 0 号磁道。接下来处理完 18 号磁道的访问请求之后，这个磁头又可以开始向右移动，然后依次处理完所有的这些请求。整个过程下来总共移动了 322 个，磁道平均的寻找长度减小为了 35.8 个磁道。所以比起 C-SCAN 的算法来说，C-LOOK 算法使寻道时间，还有平均寻找长度进一步的缩短了。
# 小结
那么这个小节当中我们介绍磁盘调度算法相关的一些内容，
我们首先介绍了一次磁盘的读写操作所需要的时间，第一个部分叫做寻找时间或者叫寻道时间，它由启动磁臂的时间和移动磁头所花的时间组成，
我们之后介绍的这些磁盘调度算法主要影响的是移动磁头所花的时间。另外大家也需要理解延迟时间和传输时间分别是什么意思，并且大家在理解了那个公式的含义之后，需要能够自己推出来延迟时间和传输时间的计算公式。
之后，我们介绍了一系列的磁盘调度算法，大家需要掌握各个算法的一个具体的规则，需要注意的是最短寻找时间优先算法有可能导致饥饿，并且这种算法它只能保证眼前最优，但无法保证总体最优。也就是说每一次的寻到肯定是当前来看最短的，不过总体来看总的寻到长度未必是最短的。
之后我们又介绍了 scan 算法，还有 SCAN 算法的改良型算法 look 算法，C-SCAN 算法和 C-SCAN 算法的改良型算法 C-LOOK 个算法。不过大家在做题的时候，如果题目当中没有特别的说明，那么题目中所指的 SCAN 算法其实就是 look 算法，题目中所指的 C-SCAN 算法，其实就是 c-look 算法，也就是说这个磁头并不一定需要移动到最外侧的磁道上，只要磁头的移动方向上没有别的请求了，那么就可以让磁头立即改变方向。咱们的课后习题当中会有很多与小节相关的一些练习题，大家还需要自己动手巩固。
- 01
- 中国网络防火长城简史 转载10-12
- 03
- 公告：博客近期 RSS 相关问题10-02
