5万字、97 张图总结操作系统核心知识点 (28)

如果磁盘驱动程序每次接收一个请求并按照接收顺序完成请求,这种处理方式也就是 先来先服务(First-Come, First-served, FCFS) ,这种方式很难优化寻道时间。因为每次都会按照顺序处理,不管顺序如何,有可能这次读完后需要等待一个磁盘旋转一周才能继续读取,而其他柱面能够马上进行读取,这种情况下每次请求也会排队。

通常情况下,磁盘在进行寻道时,其他进程会产生其他的磁盘请求。磁盘驱动程序会维护一张表,表中会记录着柱面号当作索引,每个柱面未完成的请求会形成链表,链表头存放在表的相应表项中。

一种对先来先服务的算法改良的方案是使用 最短路径优先(SSF) 算法,下面描述了这个算法。

假如我们在对磁道 6 号进行寻址时,同时发生了对 11 , 2 , 4, 14, 8, 15, 3 的请求,如果采用先来先服务的原则,如下图所示

5万字、97 张图总结操作系统核心知识点

我们可以计算一下磁盘臂所跨越的磁盘数量为 5 + 9 + 2 + 10 + 6 + 7 + 12 = 51,相当于是跨越了 51 次盘面,如果使用最短路径优先,我们来计算一下跨越的盘面

5万字、97 张图总结操作系统核心知识点

跨越的磁盘数量为 4 + 1 + 1 + 4 + 3 + 3 + 1 = 17 ,相比 51 足足省了两倍的时间。

但是,最短路径优先的算法也不是完美无缺的,这种算法照样存在问题,那就是优先级 问题,

这里有一个原型可以参考就是我们日常生活中的电梯,电梯使用一种电梯算法(elevator algorithm) 来进行调度,从而满足协调效率和公平性这两个相互冲突的目标。电梯一般会保持向一个方向移动,直到在那个方向上没有请求为止,然后改变方向。

电梯算法需要维护一个二进制位,也就是当前的方向位:UP(向上)或者是 DOWN(向下)。当一个请求处理完成后,磁盘或电梯的驱动程序会检查该位,如果此位是 UP 位,磁盘臂或者电梯仓移到下一个更高跌未完成的请求。如果高位没有未完成的请求,则取相反方向。当方向位是 DOWN 时,同时存在一个低位的请求,磁盘臂会转向该点。如果不存在的话,那么它只是停止并等待。

我们举个例子来描述一下电梯算法,比如各个柱面得到服务的顺序是 4,7,10,14,9,6,3,1 ,那么它的流程图如下

5万字、97 张图总结操作系统核心知识点

所以电梯算法需要跨越的盘面数量是 3 + 3 + 4 + 5 + 3 + 3 + 1 = 22

电梯算法通常情况下不如 SSF 算法。

错误处理

一般坏块有两种处理办法,一种是在控制器中进行处理;一种是在操作系统层面进行处理。

这两种方法经常替换使用,比如一个具有 30 个数据扇区和两个备用扇区的磁盘,其中扇区 4 是有瑕疵的。

5万字、97 张图总结操作系统核心知识点

控制器能做的事情就是将备用扇区之一重新映射。

5万字、97 张图总结操作系统核心知识点

还有一种处理方式是将所有的扇区都向上移动一个扇区

5万字、97 张图总结操作系统核心知识点

上面这这两种情况下控制器都必须知道哪个扇区,可以通过内部的表来跟踪这一信息,或者通过重写前导码来给出重新映射的扇区号。如果是重写前导码,那么涉及移动的方式必须重写后面所有的前导码,但是最终会提供良好的性能。

稳定存储器

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpswxs.html