Operating|电梯算法(1)

电梯算法(1)
刺猬@http://blog.csdn.net/littlehedgehog








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

注意这张图并不是解释的先到先服务算法,我们只是借用下而已 :)
假设此时我们正在第11道读取数据,然后陆陆续续有其他进程来要求我们提供磁盘内容给他们。这里我们把要读取的柱面(如果你并不是研究磁盘寻道,那么这个词你可以理解为数据块,就是上面的小方块)按照进程提出要求的顺序记录下来的是1, 36, 16, 34, 9, 12,那么严格按照先到先服务原则,我们下一个要去的柱面是1号,中间要经历10个柱面,然后是36号....... 等全部读下来,我们统计下,一共要"跑过"111个柱面。
很明显的,这个算法效率太低,我们要来改善下算法。
【Operating|电梯算法(1)】第二种是最短寻道算法(shortest seek first)
这种算法有点类似贪心,即是每次我们选择距离我们现在所处的点最近的一个点(柱面)。如下图,若当前我们正好执行完对于11号块的读取,下一个最近的是12号块,那么我们读取12号块的数据,接着读取16号块...... 我们看到如果用这种算法的话,我们经过的方块号码12, 9, 16, 1, 34, 36 这样我们总共的经历的柱面数为 61块,这样我们大大节省了寻道时间。
Operating|电梯算法(1)
文章图片


这个算法本来已经很好了,不过我们不得不面临这样一个问题: 现在我们正在读取16号块,马上要读取1号块了,这是一个进程闯进来要求我们为他提供20号块的信息,20号距离16号比较近,那我们就去二十号吧,然后我们又接到通知要23号数据.....这样一直做下去,呃,1号信息呢?天晓得要等到什么时候去读取它内容!
所以这里我们需要一种算法来平衡效率和公平性(我们也不希望歧视了1号小方块)。所以我们引进了电梯算法 。我们需要做一个标记,标记现在是向数字大的方向读,还是方向小的。如果现在是向前(数字大)读,那么我们就需要一直读下去,一直到最尾一个。同理向后读。这个算法如下图所示:
Operating|电梯算法(1)
文章图片






内容参考《操作系统设计与实现》

第一次写博客全部自己手打出来
为家乡地震中受苦的人们祈福
独在异乡为异客




    推荐阅读