Operating|电梯算法(1)
电梯算法(1)
刺猬@http://blog.csdn.net/littlehedgehog
电梯算法主要用于磁盘寻道的优化。
第一种是我们最为原始的先到先服务(first come first served)的算法，这个对于我们去下馆子撮一顿比较合适，先来就先吃，不然顾客有意见。不过对于磁盘寻道就不太合适了。如下图:
文章图片
注意这张图并不是解释的先到先服务算法，我们只是借用下而已 :)
假设此时我们正在第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块，这样我们大大节省了寻道时间。
文章图片
这个算法本来已经很好了，不过我们不得不面临这样一个问题： 现在我们正在读取16号块，马上要读取1号块了，这是一个进程闯进来要求我们为他提供20号块的信息，20号距离16号比较近，那我们就去二十号吧，然后我们又接到通知要23号数据.....这样一直做下去，呃，1号信息呢？天晓得要等到什么时候去读取它内容！
所以这里我们需要一种算法来平衡效率和公平性(我们也不希望歧视了1号小方块)。所以我们引进了电梯算法 。我们需要做一个标记，标记现在是向数字大的方向读，还是方向小的。如果现在是向前(数字大)读，那么我们就需要一直读下去，一直到最尾一个。同理向后读。这个算法如下图所示:
文章图片
内容参考《操作系统设计与实现》
第一次写博客全部自己手打出来
为家乡地震中受苦的人们祈福
独在异乡为异客
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 被关电梯
- 算法回顾（SVD在协同过滤推荐系统中的应用）