磁盘调度算法(CSCAN、N-step-SCAN)

安徽省巢湖学院计算机与信息工程学院

课程设计报告

课程名称：《操作系统》

课题名称：磁盘调度(CSCAN、N-Step-SCAN)算法模拟 专业班级： 11计本（3）班 同组姓名：程张磊、梁浩、何生飞

同组学号：11011169、11011175、11011187 联系方式： 18226926353 指导教师： 梁宝华

目 录

一、课程设计目的 ................................................................................................................................................... 1 二、课程设计内容 ................................................................................................................................................... 1

2.1、需求分析 .................................................................................................................................................. 1 2.2、同组人员的任务分配 .............................................................................................................................. 1 三、相关算法的介绍及流程图 ............................................................................................................................... 1

3.1、算法介绍 .................................................................................................................................................. 1 3.2、流程图………………………………………………………………………………………………….....2 四、算法设计 ........................................................................................................................................................... 3 五、运行结果 ......................................................................................................................................................... 10

5.1、实验平台说明 ........................................................................................................................................ 10 5.2、程序初始界面…………………………………………………………………………………………...11 5.3、CSAN算法运行结果 ..............................................................................................................................11 5.4、N-Step-SCAN算法运行结果…………………………………………………………………………..12 六、实验的启发 ..................................................................................................................................................... 13 附录：参考文献………………………………………………………………………………………………...13

一、课程设计目的

《计算机操作系统》是计算机与信息工程学院计算机科学与技术专业的必修课程，内容主要涉及OS的发展、特征、功能等，在基础知识掌握之后，需要一个相对完整的时间进行知识点的融会贯通，并能针对实际案例进行综合性地规划、设计和配置来灵活运用这些知识。本课程设计为学生提供了一个动手动脑、独立实践的机会。通过该课程设计，使学生能够更好地掌握路由器和交换机的原理和配置；能够将课本上的理论知识和实践开发有机的结合起来；能够锻炼学生的分析问题、解决问题的能力，从而加深对这门课的理解，在理解相关设备的原理知识的同时又提高学生的实际操作能力。

二、课程设计内容

2.1、需求分析

磁盘存储器不仅容量大，存取速度快，而且可以实现随机存取，是当前存放大量程序和数据的理想设备，故在现代计算机系统中，都配置了磁盘存储器，并以它为主来存放文件。这样，对文件的操作，都将涉及到对磁盘的访问。磁盘I/O速度的高低和磁盘系统的可靠性都将直接影响到系统性能。因此，设法改善磁盘系统的性能，已成为现代操作系统的重要任务之一。磁盘性能有数据的组织、磁盘的类型和访问时间等。

磁盘调度的目标是使磁盘的平均寻道时间最少。也正因为这样，我们有必要对各算法进行模拟，进而比较、分析、了解。

本实验设计的目的是通过设计一个磁盘调度模拟系统，以加深对最短寻道时间优先（SSTF）、N步扫描算法（NStepSCAN）等磁盘调度算法的理解。让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。

2.2、人员分配

何生飞：负责SCAN算法的设计。

梁浩：负责N-Step-SCAN算法的设计。

程张磊（组长）：负责程序整合以及主程序编写和课程设计报告的制作。

三、相关算法的介绍及流程图

3.1、算法介绍

1.CSAN算法：在SCAN算法的基础上，规定磁头只能单向移动，使之能够防止“饥饿”现象。

2.N-Step-SCAN算法：当有一个或者几个进程对某一磁道有较高的访问频率，即这些进程反复请求对某一磁道的I/O操作，从而垄断整个磁盘设备。在高密度的磁盘上容易出现此情况。N步SCAN算法是将磁道请求队列若干个长度为N的子队列。而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列。

- 1 -

3.2、流程图

从文件中获取进程请求磁道号放入Track[i]统计总个数count 输入当前磁道号start,子队列个数 N,移动臂的移动方向d 从Track[i]中取出前count/N组成一个子队列，存入b[i],最后一列将该子队列 为剩余磁道号，存入b[i] Y N N！=0? 将磁道号从小到大排序 输出该算法下总的寻道数s 输出该算法下平均寻道数 array[x-1]<=start 磁头移动总距离sux=start-array[i] (array[0]>=now 确定当前磁道在已输出磁盘调度序列array[j] 排的序列中的位置 磁头移动总距离sux=array[i]-start switch(d输出磁盘调度case 1:移动臂case 0:移动臂向磁道号减小方向访问 向磁道号增加方向访问 i>=0 序列array[j] i

- 2 -

四、算法设计

程序相关代码如下：

#include\ #include\ #definexaxsize 100 intstart,s;

void SCAN1(intarray[],intx) {

inttexp; int k=1; intstart,l,r; inti,j,sux=0; intavg; int d; int q;

printf(\请输入当前移动臂的移动的方向 (1 磁道号增加方向，0磁道号减小方向) : \); for(i=0;i

printf(\磁道从小到大排序为：\\n\); for(i=0;i

printf(\请输入当前的磁道号：\); scanf(\,&start);

printf(\算法调度结果: \); if(array[x-1]<=start) { }

for(i=x-1;i>=0;i--) printf(\,array[i]); sux=start-array[0]; printf(\,array[i]); for(j=i+1;j

if(array[i]>array[j]) { }

texp=array[i]; array[i]=array[j]; array[j]=texp;

scanf(\,&d);

- 3 -

elseif(array[0]>=start) { } else {

while(array[k]

printf(\调度结果: \); if(d==0) { } else {

for(j=r;j

for(j=l;j>=0;j--) { }

sux=-start-array[0]+2*array[x-1]; start=q;

printf(\,array[j]); printf(\,array[j]); for(j=l;j>=0;j--) { }

for(j=r;j

sux=start-2*array[0]+array[x-1]; start=q;

printf(\,array[j]); printf(\,array[j]); k++; for(i=0;i

printf(\,array[i]); sux=array[x-1]-start;

q=array[j];

q=array[j];

s=s+sux;

q=array[j];

q=array[j];

s=s+sux;

- 4 -

{

}

}

avg=sux/x;

printf(\移动的总道数： %d \\n\,sux); printf(\平均寻道长度： %d \\n\,avg); }

void SCAN(intarray[],intx,intd)

int k=1; intl,r; inti,j,sux=0; intavg; inttexp; int q;

for(i=0;i

{ } { }

elseif(array[0]>=start) {

printf(\调度结果: \); for(i=0;i

printf(\,array[i]); printf(\调度结果: \); for(i=x-1;i>=0;i--) { }

sux=start-q; s=s+sux; start=q;

printf(\,array[i]); for(j=i+1;j

if(array[i]>array[j]) { }

texp=array[i]; array[i]=array[j]; array[j]=texp;

if(array[x-1]<=start)

q=array[i];

q=array[i];

- 5 -

}

}

sux=array[x-1]-start; start=q;

s=s+sux;

else {

while(array[k]

printf(\调度结果: \); if(d==0) { } else { }

for(j=r;j

for(j=l;j>=0;j--) { }

sux=-start-array[0]+2*array[x-1]; start=q;

printf(\,array[j]); printf(\,array[j]); for(j=l;j>=0;j--) { }

for(j=r;j

sux=start-2*array[0]+array[x-1]; start=q;

printf(\,array[j]); printf(\,array[j]); k++;

q=array[j];

q=array[j];

s=s+sux;

q=array[j];

q=array[j];

s=s+sux;

- 6 -

}

}

avg=sux/x;

printf(\该子队列移动的总道数： %d \\n\,sux); printf(\该子队列平均寻道长度： %d \\n\,avg);

voidNStepSCAN(intarray[],intx) {

intw,N,d; int b[100],c[100]; inti=0,j=0,k=0,n=1; intave;

scanf(\,&start);

printf(\请输入子队列的个数：\\n\); scanf(\,&N); while(N<1||N>x) { }

printf(\超出范围，文件中的磁道数不够分组，请重新输入：\\n\);

printf(\请输入当前磁道号：\\n\);

scanf(\,&N);

printf(\请输入当前移动臂的移动的方向 (1 磁道号增加方向，0磁道号减小方向) : \); scanf(\,&d); w=x/N; while(N!=1)

{ } {

for(i=k,j=0;i

c[j]=array[i]; j=0;

for(i=k;i

SCAN(b,w,d); N=N-1; n=n+1;

b[j]=array[i]; k=k+1;

printf(\第%d个队列的排序结果为：\\n\,n);

if(N==1)

printf(\最后一个队列的调度结果为：\\n\);

- 7 -

SCAN(c,x-k,d); }

int main() {

int c; int C=1; FILE *fp;

int Track[xaxsize]; inti=0,count;

fp=fopen(\,\); if(fp==NULL) { }

while(!feof(fp)) { } count=i;

printf(\磁道读取结果：\\n\); for(i=0;i

printf(\); while(C==1) {

printf(\操作系统课程设计 \\n\);

printf(\,Track[i]); fscanf(fp,\,&Track[i]); i++;

printf(\请先将磁道输入在Track.txt文件中再执行程序，谢谢！ \\n\); exit(0); } ave=s/x;

printf(\该调度总的结果为：\\n\); printf(\移动的总道数： %d \\n\,s); printf(\平均寻道长度： %d \\n\,ave);

printf(\磁盘调度算法 \\n\); printf(\巢湖学院 \\n\);

printf(\级计本（3）班程张磊梁浩何生飞 \\n\); printf(\算法 \\n\);

printf(\算法 \\n\); printf(\请输入你的选择的算法(输入0结束程序) \\n\); scanf(\,&c); if(c==0) exit(0);

printf(\);

while(c!=1&&c!=2)

- 8 -

本文来源：https://www.bwwdw.com/article/u49p.html