磁盘调度算法
标签: 操作系统
学习人数: 6758

1. 先来先服务(FCFS)

算法思想非常简单,就是不论初始磁头在什么位置,都是按照服务队列的先后顺序依次处理进程,可以类比队列的先进先出。该算法的优点是具有公平性。若只有少量进程需要访问,且大部分请求都是访问簇聚的文件扇区,则有望达到较好的性能,但缺点显而易见,就是平均寻道长度会很长。

FCFS磁盘调度算法

磁盘请求队列中的请求顺序分别为55,58,39,18,90,160,150,38,184,磁头的初始位置是磁道100,采用FCFS算法时磁头的运动过程。磁头共移动了(45 + 3 + 19 + 21 +72 + 70+ 10+ 112 + 146) = 498个磁道,平均寻找长度=498/9 = 55.3。

 

2. 最短寻道时间优先(SSTF)

SSTF算法选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。该算法的寻道性能比FCFS算法好,但不能保证平均寻道时间最短,并且可能会使某些进程的请求总被其他进程的请求抢占而长期得不到服务(这种现象称为“饥饿”)。

SSTF磁盘调度算法

磁盘请求队列中的请求顺序分别为55,58,39,18,90,160,150,38,184,磁头的初始位置是磁道100,采用SSTF算法时磁头的运动过程。磁头共移动了 10 + 32 + 3 + 16 +1 +20+ 132+ 10+ 24 = 248 个磁道,平均寻找长度=248/9 = 27.5。

 

3. 扫描(SCAN)算法

SCAN算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。由于这种算法中磁头移动的规律颇似电梯的运行,故也称为电梯调度算法。SCAN算法具有较好的寻道性能,又避免了 “饥饿”现象,但其对两端磁道请求比较不公平(通常两端请求都是最后得到服务)。

SCAN磁盘调度算法

磁盘请求队列中的请求顺序分别为55,58,39,18,90,160,150,38,184,磁头的初始位置是磁道100,采用SCAN算法时,不但要知道磁头的当前位置,而且要知道磁头的移动方向,假设磁头沿磁道号增大的顺序移动,则磁头的运动过程如图4.21所示。移动磁道的顺序为100, 150,160, 184, 200, 90, 58, 55, 39, 38, 18。磁头共移动了(50 + 10 + 24 + 16 + 110 + 32 + 3 + 16 + 1 + 20) =282个磁道,平均寻道长度=282/9 = 31.33。

 

4. 循环扫描(C-SCAN)算法

C-SCAN算法是对SCAN算法的改良,它规定磁头单向移动,例如,自里向外移动,当磁头移到最外磁道时立即返回到最里磁道,如此循环进行扫描。该算法消除了对两端磁道请求的不公平。

C-SCAN磁盘调度算法

磁盘请求队列中的请求顺序分别为55,58,39,18,90,160,150,38,184,磁头的初始位置是磁道100,采用C-SCAN算法时,假设磁头沿磁道号增大的顺序移动,则磁头的运动过程。移动磁道的顺序为100? 150, 160, 184, 200, 0, 18, 38, 39, 55, 58, 90。磁头共移动50+ 10 + 24+ 16 + 200+ 18 + 20+ 1 + 16 +3+ 32 = 390个磁道,平均寻道长度=390/9 = 43.33。

采用SCAN算法和C-SCAN算法时,磁头总是严格地遵循从盘面的一端到另一端,显然,在实际使用时还可以改进,即磁头移动只需要到达最远端的一个请求即可返回,不需要到达磁盘端点。这种形式的SCAN算法和C-SCAN算法称为LOOK调度和 C-LOOK调度,因为它们在朝一个给定方向移动前会查看是否有请求。

 



课后作业


登录后发布评论

暂无评论,来抢沙发