linux 磁盘io电梯算法

xiaoxiao2021-02-28  15

电梯算法主要用于磁盘寻道的优化。

第一种是我们最为原始的先到先服务(first come first served)的算法,这个对于我们去下馆子撮一顿比较合适,先来就先吃,不然顾客有意见。不过对于磁盘寻道就不太合适了。如下图:

注意这张图并不是解释的先到先服务算法,我们只是借用下而已 :)

假设此时我们正在第11道读取数据,然后陆陆续续有其他进程来要求我们提供磁盘内容给他们。这里我们把要读取的柱面(如果你并不是研究磁盘寻道,那么这个词你可以理解为数据块,就是上面的小方块)按照进程提出要求的顺序记录下来的是1, 36, 16, 34,9, 12,那么严格按照先到先服务原则,我们下一个要去的柱面是1号,中间要经历10个柱面,然后是36号.......等全部读下来,我们统计下,一共要"跑过"111个柱面。

很明显的,这个算法效率太低,我们要来改善下算法。

第二种是最短寻道算法(shortest seek first) 

这种算法有点类似贪心,即是每次我们选择距离我们现在所处的点最近的一个点(柱面)。如下图,若当前我们正好执行完对于11号块的读取,下一个最近的是12号块,那么我们读取12号块的数据,接着读取16号块......我们看到如果用这种算法的话,我们经过的方块号码  12, 9, 16, 1, 34, 36 这样我们总共的经历的柱面数为61块,这样我们大大节省了寻道时间。

 

这个算法本来已经很好了,不过我们不得不面临这样一个问题:现在我们正在读取16号块,马上要读取1号块了,这是一个进程闯进来要求我们为他提供20号块的信息,20号距离16号比较近,那我们就去二十号吧,然后我们又接到通知要23号数据.....这样一直做下去,呃,1号信息呢?天晓得要等到什么时候去读取它内容!

所以这里我们需要一种算法来平衡效率和公平性(我们也不希望歧视了1号小方块)。所以我们引进了电梯算法 。我们需要做一个标记,标记现在是向数字大的方向读,还是方向小的。如果现在是向前(数字大)读,那么我们就需要一直读下去,一直到最尾一个。同理向后读。这个算法如下图所示:

 

转载请注明原文地址: https://www.6miu.com/read-1400135.html

最新回复(0)