磁盘请求算法
‘壹’ 求使用磁盘调度算法的最短寻道时间优先的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");
}
‘贰’ ssd经常采用的磁盘调度算法
ssd经常采用的磁盘调度算法是根据进程请求访问磁盘的先后次序进行调度。根据查询相关公开信息显示，此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。
‘叁’ 磁盘调度算法的常用磁盘调度算法
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调度。
‘肆’ 磁盘调度算法
上文介绍了磁盘的结构，本文介绍磁盘的调度算法相关的内容。
本文内容
寻找时间（寻道时间） 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算法，平均寻道时间更长。
‘伍’ 目前常用的磁盘调度算法有哪几种每种算法优先考虑的问题是什么
先来先服务算法：这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。
最短寻道时间优先算法：要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。
扫描算法：“电梯调度”是沿着臂的移动方向去选择离当前读写词头最近的哪个磁道的访问者。
.循环扫描算法：防止饥饿现象
‘陆’ 关于《操作系统》中的磁盘调度算法
（1）先来先服务调度算法
由于该算法就是按照磁道请求序列的先后次序依次访问磁道的，因此磁道的访问序列（服务顺序）就是：
110、180、32、115、15、120、60、70。
当前磁头在50号磁道。故磁头移动道数为：
（110-50）+（180-110）+（180-32）+（115-32）+（115-15）+（120-15）+（120-60）+（70-60）=60+70+148+83+100+105+60+10=636
（2）单向扫描调度算法
该算法是沿磁头移动方向访问距离当前磁道最近的磁道，当到达一个顶端时立刻返回到另一个顶端继续扫描。本题磁头移动方向是磁道增加的方向，当前磁头在50号磁道。因此磁道的访问序列（服务顺序）就是：60、70、110、115、120、180、15、32。而磁头移动道数与前面（1）问差不多，也是两两相减，然后求和。在此略
‘柒’ 磁盘调度 算法
(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
‘捌’ 目前常用的磁盘调度算法有哪几种每种算法优先考虑的问题是什么
(1)先来先服务(FCFS，First-Come First-Served)
此算法根据进程请求访问磁盘的先后次序进行调度。
(2)最短寻道时间优先(SSTF ，ShortestSeekTimeFirst)
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。
(3)扫描(SCAN)算法
SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。
(4)循环扫描(CSCAN)算法
CSCAN算法规定磁头单向移动，避免了扫描算法导致的某些进程磁盘请求的严重延迟。
(5) N-Step-SCAN和FSCAN调度算法
1) N-Step-SCAN算法。为克服前述SSTF、SCAN、CSCAN等调度算法都可能出现的磁臂停留在某处不动的情况即磁臂粘着现象，将磁盘请求队列分成若干个长度为N的子队列，按先来先服务算法依次处理这些子队列，而各队列分别以扫描算法进行处理。
2) FSCAN算法
FSCAN算法实质上是N步SCAN算法的简化。它只将磁盘请求访问队列分成两个子队列。一是当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。另一个队列则是在 扫描期间，新出现的所有请求磁盘I/O进程的队列，放入另一等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。
‘玖’ 目前常用的磁盘调度算法有哪几种
磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列，常用的磁盘调度算法有以下四种：[1]
先来先服务算法（FCFS），
最短寻道时间优先算法（SSTF），
扫描算法（SCAN），
循环扫描算法（CSCAN）