磁盘最短寻找时间调度算法分析题

‘壹’ 最短寻找时间优先算法

最短寻找时间优先（SSTF）就是每次都找最近的，初始位于40，每次都找最近的，访问序列就是40，44，20，12，4，76，80，一共移动了4+24+8+8+72+4=120个柱面，所以总共花费的寻找时间就是120*3=360毫秒

‘贰’ 磁盘调度算法

  上文介绍了磁盘的结构，本文介绍磁盘的调度算法相关的内容。
   本文内容

   寻找时间（寻道时间） T _s ：在读/写数据前，需要将磁头移动到指定磁道所花费的时间。
  寻道时间分两步：

  则寻道时间 T _s = s + m * n。

  磁头移动到指定的磁道，但是不一定正好在所需要读/写的扇区，所以需要通过磁盘旋转使磁头定位到目标扇区。

   延迟时间T _R ：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r（单位：转/秒，或转/分），则 平均所需延迟时间T _R = (1/2)*(1/r) = 1/2r。

   传输时间T _R ：从磁盘读出或向磁盘中写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N，则传输时间 T _R = (b/N) * (1/r) = b/(rN)。

  总的平均时间 T _a = T _s + 1/2r + b/(rN) ，由于延迟时间和传输时间都是与磁盘转速有关的，且是线性相关。而转速又是磁盘的固有属性，因此无法通过操作系统优化延迟时间和传输时间。所以只能优化寻找时间。

  算法思想： 根据进程请求访问磁盘的先后顺序进行调度。
  假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。
  按照先来先服务算法规则，按照请求到达的顺序，磁头需要一次移动到55、58、39、18、90、160、150、38、184号磁道。

  磁头共移动了 45 + 3 + 19 + 21 + 72 + 70 + 10 + 112 + 146 = 498个磁道。响应一个请求平均需要移动498 / 9 = 55.3个磁道（平均寻找长度）。
  优点： 公平；如果请求访问的磁道比较集中的话，算法性能还算可以 。
  缺点： 如果大量进程竞争使用磁盘，请求访问的磁道很分散，FCFS在性能上很差，寻道时间长 。

  算法思想： 优先处理的磁道是与当前磁头最近的磁道。可以保证每次寻道时间最短，但是不能保证总的寻道时间最短 。（其实是贪心算法的思想，只是选择眼前最优，但是总体未必最优）。

  假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。

  磁头总共移动了（100 -18）+ （184 -18） = 248个磁道。响应一个请求平均需要移动248 / 9 = 27.5个磁道（平均寻找长度）。
  缺点： 可能产生饥饿现象 。
  本例中，如果在处理18号磁道的访问请求时又来了一个38号磁道的访问请求，处理38号磁道的访问请求又来了一个18号磁道访问请求。如果有源源不断的18号、38号磁道访问请求，那么150、160、184号磁道请求的访问就永远得不到满足，从而产生饥饿现象。这里产生饥饿的原因是 磁头在一小块区域来回移动。

  SSTF算法会产生饥饿的原因在于：磁头有可能再一个小区域内来回得移动。为了防止这个问题，可以规定： 磁头只有移动到请求最外侧磁道或最内侧磁道才可以反向移动，如果在磁头移动的方向上已经没有请求，就可以立即改变磁头移动，不必移动到最内/外侧的磁道。 这就是扫描算法的思想。由于磁头移动的方式很像电梯，因此也叫 电梯算法 。

  假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续的访问55、58、39、18、90、160、150、38、184号磁道。

  磁头共移动了（184 - 100）+ （184 -18） = 250个磁道。响应一个请求平均需要移动 250 / 9 = 27.5个磁道（平均寻找长度）。

  优点： 性能较好，寻道时间较短，不会产生饥饿现象。
  缺点： SCAN算法对于各个位置磁道的响应频率不平均 。（假设此时磁头正在往右移动，且刚处理过90号磁道，那么下次处理90号磁道的请求就需要等待低头移动很长一段距离；而响应了184号磁道的请求之后，很快又可以再次响应184号磁道请求了。）

  SCAN算法对各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而 返回时直接快速移动至最靠边缘的并且需要访问的磁道上而不处理任何请求。
  通俗理解就是SCAN算在改变磁头方向时不处理磁盘访问请求而是直接移动到另一端最靠边的磁盘访问请求的磁道上。

  假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续的访问55、58、39、18、90、160、150、38、184号磁道。

  磁头共移动了（184 -100）+ （184 - 18）+（90 - 18）=322个磁道。响应一个请求平均需要移动322 / 9 = 35.8个磁道（平均寻找长度）。

  优点： 相比于SCAN算法，对于各个位置磁道响应频率很平均。
  缺点： 相比于SCAN算法，平均寻道时间更长。

‘叁’ 磁盘调度算法SSTF算法 不限制编程语言，可以选用C/C++等

Java版的磁盘调度算法，

其中算法包含

1 先来先服务

2 最短时间优先

3 最短时间优先

4 单向扫描算法

程序是动画演示的，程序以圆模拟磁道，以方块模拟磁头根据算法在界面上演示。
程序运行截图如下图所示：

‘肆’ 求使用磁盘调度算法的最短寻道时间优先的C++程序

dev c++

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct ci
{
int num;
int visited;
}CD;

int count=0;

void SSTF(int start,CD L[],int n)
{
int i,j,next;
int min=32767;
for(i=0;i<n;i++)
{
if(L[i].visited==0)
if(min>=abs(L[i].num-start))
{
min=abs(L[i].num-start);
next=L[i].num;
j=i;
}
}
printf("\n\t%d\t\t%d",next,min);
L[j].visited=1;
count++;
if(count<n)SSTF(next,L,n);
}

int main()
{
int n,i,start;
printf("请输入磁盘请求序列大小:");
scanf("%d",&n);
CD L[n];
printf("\n请输入磁盘请求序列(以空格隔开):");
for(i=0;i<n;i++)
{
scanf("%d",&L[i].num);
L[i].visited=0;
}
printf("\n请输入开始磁道号:");
scanf("%d",&start);
printf("\n下一个被访问的磁道\t移动磁道数");
SSTF(start,L,n);
printf("\n\n");
system("pause");
}

‘伍’ 有没有大神会做这道采用电梯调度算法执行磁盘调度的题

最短寻找楼层时间优先(SSTF-Shortest Seek Time First) [14]算法，它注重电梯寻找楼层的优化。最短寻找楼层时间优先算法选择下一个服务对象的原则是最短寻找楼层的时间。这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。在重载荷的情况下，最短寻找楼层时间优先算法的平均响应时间较短，但响应时间的方差较大，原因是队列中的某些请求可能长时间得不到响应，出现所谓的“饿死”现象。

‘陆’ 计算机三级的三道题目不会做啊！！！求教

1、盘块的大小为4KB，每个盘块号占4B，则一个索引块可含 4KB/4B=1K个盘块号，于是两级索引最多可含1K×1K =
1M个盘块号，因此，允许的最大文件长度为4KB×1M = 4GB。

2、最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。现在当当前磁头在第4道，离它最近的是5，移动1道，离5最近的是7，移动2道，离7最近的是11，以此类推，则最后的移动次序为5、7、11、21、22、0，移动倒数为1+2+4+10+1+22=40。

3、采用最短寻道时间优先调度算法时与第二题类似，移动次序为16、13、9、20、24、29，移动总数为1+3+4+11+4+5=28。
“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。现在移动方向是从大到小，那会先朝比当前柱面小的方向找离其最近的移动，当前在15，比它小又离它最近的是13，然后是9，比它小的访问请求处理完了，就改变方向，于是离15最近的是16，然后是20,、24、29，最终的次序是13、9、16、20、24、29，移动总数是2+4+7+4+4+5=26.

‘柒’ 在磁盘调度，sstf算法中，为什么说：总是选择最小寻找时间并不能保证平均寻找时间最小

FCFS算法根据进程请求访问磁盘的先后顺序进行调度，这是一种最简单的调度算法。该算法的优点是具有公平性。如果只有少量进程需要访问，且大部分请求都是访问簇聚的文件扇区，则有望达到较好的性能；但如果有大量进程竞争使用磁盘，那么这种算法在性能上往往接近于随机调度。所以，实际磁盘调度中考虑一些更为复杂的调度算法。
1、算法思想：按访问请求到达的先后次序服务。
2、优点：简单，公平。
3、缺点：效率不高，相邻两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利。
4、例子：
假设磁盘访问序列：98，183，37，122，14，124，65，67。读写头起始位置：53。求：磁头服务序列和磁头移动总距离（道数）。
由题意和先来先服务算法的思想，得到下图所示的磁头移动轨迹。由此：
磁头服务序列为：98，183，37，122，14，124，65，67
磁头移动总距离=（98-53）+（183-98）+|37-183|+（122-37）+|14-122|+（124-14）+|65-124|+（67-65）=640（磁道） SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道，以使每次的寻找时间最短。当然，总是选择最小寻找时间并不能保证平均寻找时间最小，但是能提供比FCFS算法更好的性能。这种算法会产生“饥饿”现象。
1、算法思想：优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先。
2、优点：改善了磁盘平均服务时间。
3、缺点：造成某些访问请求长期等待得不到服务。
4、例子：对上例的磁盘访问序列，可得磁头移动的轨迹如下图。 SCAN算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。由于磁头移动规律与电梯运行相似，故又称为电梯调度算法。SCAN算法对最近扫描过的区域不公平，因此，它在访问局部性方面不如FCFS算法和SSTF算法好。
算法思想：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移 动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复。如下图所示：
扫描算法（电梯算法）的磁头移动轨迹
2、优点：克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向。 在扫描算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动至起始端而不服务任何请求。由于SCAN算法偏向于处理那些接近最里或最外的磁道的访问请求，所以使用改进型的C-SCAN算法来避免这个问题。
釆用SCAN算法和C-SCAN算法时磁头总是严格地遵循从盘面的一端到另一端，显然，在实际使用时还可以改进，即磁头移动只需要到达最远端的一个请求即可返回，不需要到达磁盘端点。这种形式的SCAN算法和C-SCAN算法称为LOOK和C-LOOK调度。这是因为它们在朝一个给定方向移动前会查看是否有请求。注意，若无特别说明，也可以默认SCAN算法和C-SCAN算法为LOOK和C-LOOK调度。

‘捌’ 磁盘调度 算法

(1)FCFS(先来先服务):
143-86=57
147-86=61
147-91=56
177-91=86
177-94=97
150-94=56
150-102=48
175-102=73
175-130=45
57+61+56+86+97+56+48+73+45=579

(2)SSTF(最短寻道时间优先)：
寻道顺序：143（当前），147，150，130，102，94，91，86，175，177；
4+3+20+28+8+3+5+89+2=162

(3)SCAN：
当前方向：从143#向磁道号增加的方向
依次访问：143（当前），147，150，175，177
再从递减方向：130，102，94，91，86
4+3+25+2+47+28+8+3+5=125

(4)LOOK:(即SCAN，电梯调度算法)

(5)CSCAN:
当前方向：从143#向磁道号增加的方向
依次访问：143（当前），147，150，175，177
再从0开始增加方向：86,91,94,102,130
4+3+25+2+91+5+3+8+28=169