磁盘调度之扫描类算法

1、扫描(SCAN)算法

1)进程“饥饿”现象

SSTF算法虽然能获得较好的寻道性能&＃xff0c;但却可能导致某个进程发生“饥饿”现象。因为只要不断有新进程的请求到达&＃xff0c;且其所要访问的磁道与磁头当前所在磁道的距离较近&＃xff0c;这种新进程的I/O请求必然优先满足。对SSTF算法略加修改后所形成的SCAN算法&＃xff0c;即可防止老进程出现“饥饿”现象。

2)SCAN算法

该算法不仅考虑到欲访问的磁道与当前磁道间的距离&＃xff0c;更优先考虑的是磁头当前的移动方向。例如&＃xff0c;当磁头正在自里向外移动时&＃xff0c;SCAN算法所考虑的下一个访问对象&＃xff0c;应是其欲访问的磁道既在当前磁道之外&＃xff0c;又是距离最近的。这种自里向外地访问&＃xff0c;直至再无更外的磁道需要访问时&＃xff0c;才将磁臂换向为自外向里移动。这是&＃xff0c;同样也是每次选择这样的进程来调度&＃xff0c;即要访问的磁道在当前位置内距离最近者&＃xff0c;这样&＃xff0c;磁头又逐步地从外向里移动&＃xff0c;直至再无更里面的磁道要访问&＃xff0c;从而避免了出现“饥饿”现象。由于在这种算法中磁盘移动的规律颇似电梯的运行&＃xff0c;因而又常称之为电梯调度算法。下图示出了按SCAN算法对9个进程进行调度及磁头移动的情况。

2、循环扫描(CSCAN)算法

SCAN算法既能获得较好的寻道性能&＃xff0c;又能防止“饥饿”现象&＃xff0c;故被广泛应用于大、中、小型机器和网络中的磁盘调度。但SCAN也存在这样的问题&＃xff1a;当磁头刚从里向外移动而越过了某一磁道时&＃xff0c;恰好又有一进程请求访问此磁道&＃xff0c;这时&＃xff0c;该进程必须等待&＃xff0c;待磁头继续从里向外&＃xff0c;然后再从外向里扫描完所有要访问的磁道后&＃xff0c;才处理该进程的请求&＃xff0c;致使该进程的请求被大大地推迟。为了减少这种延迟&＃xff0c;CSCAN算法规定磁头单向移动&＃xff0c;例如&＃xff0c;只是自里向外移动&＃xff0c;当磁头移到最外的磁道并访问后&＃xff0c;磁头立即返回到最里的欲访问的磁道&＃xff0c;亦即将最小磁道号紧接着最大磁道号构成循环&＃xff0c;进行循环扫描。采用循环扫描方式后&＃xff0c;上述请求进程的请求延迟将从原来的2T减为T&＃43;S_max&＃xff0c;其中&＃xff0c;T为由里向外或由外向里单向扫描完要访问的磁道所需的寻道时间&＃xff0c;而S_max是将磁头从最外面被访问的磁道直接移到最里面欲访问的磁道(或相反)的寻道时间。下图示出了CSCAN算法对9个进程调度的次序及每次磁头移动的距离。

3、NStepSCAN和FSCAN调度算法

1)NStepSCAN算法

在SSTF&＃xff0c;SCAN及CSCAN几种调度算法中&＃xff0c;都可能会出现磁臂停留在某处不动的情况&＃xff0c;例如&＃xff0c;有一个或几个进程对某一磁道有较高的访问频率&＃xff0c;即这个(些)进程反复请求对某一磁道的I/O操作&＃xff0c;从而垄断了整个磁盘设备。我们把这一现象称为“磁臂粘着”(Armstickiness)。在高密度磁盘上容易出现此情况。N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列&＃xff0c;磁盘调度将按FCFS算法依次处理这些子序列。而每处理一个队列时又是按SCAN算法&＃xff0c;对一个队列处理完毕后&＃xff0c;再处理其他队列。当正在处理某子序列时&＃xff0c;如果又出现新的磁盘I/O请求&＃xff0c;便将新请求进程放入其他队列&＃xff0c;这样就可避免出现粘着现象。当N值取得很大时&＃xff0c;会使N步扫描法的性能接近于SCAN算法的性能&＃xff1b;当N&＃61;1时&＃xff0c;N步SCAN算法便蜕化为FCFS算法。

2)FSCAN算法

FSCAN算法实质上是N步SCAN算法的简化&＃xff0c;即FSCAN只将磁盘请求队列分成两个子队列。一个是当前所有请求磁盘I/O的进程形成的队列&＃xff0c;由磁盘调度按SCAN算法进行处理。在扫描期间&＃xff0c;将新出现的所有请求磁盘I/O的进程&＃xff0c;放入另一个等待处理的请求队列。这样&＃xff0c;所有的新请求都将被推迟到下一次扫描时处理。