第一篇:模拟磁盘调度算法系统的设计毕业设计
目录
一、设计任务及主要技术....................................................................3
二、设计方案及论证结果....................................................................4
三、系统的原理框图..................................................................................5
四、设计程序....................................................................................................12
五、实验结果....................................................................................................20
六、调试分析及故障处理..................................................................24
七、设计结论....................................................................................................25
八、心得体会....................................................................................................26
一、设计任务及主要技术
1.整体功能概述(设计任务):
磁盘是外设中一个很常用的部分,所以,对磁盘数据的寻道时间的长短可以直接影响机器的整体运行速度的快慢。本设计为一个模拟磁盘调度算法的磁盘调度模拟系统,能够模拟先来先服务(FCFS)算法、最短寻道时间(SSTF)算法、电梯(SCAN)算法、环形扫描(C_SCAN)算法及N_SCAN算法五个磁盘调度算法,输入为一组作业的磁道请求,输出为按选择的算法执行时的磁头移动轨迹。其中,先来先服务(FCFS)算法、最短寻道时间(SSTF)算法、电梯(SCAN)算法为基本算法,环形扫描(C_SCAN)算法及N_SCAN算法为扩展算法。
2.运行环境:
(1)硬件环境
Intel core i5 CPU
(2)软件环境
Windows 7
Microsoft Visual C++ 6.0
3.主要技术:
(1)用C语言编写程序;
(2)对编程软件Microsoft Visual C++ 6.0的了解和使用;
(3)操作系统基础知识(主要是对先来先服务(FCFS)算法、最短寻道时间(SSTF)算法、电梯(SCAN)算法的了解);
(4)操作系统扩展知识(通过网络自学环形扫描(C_SCAN)算法及N_SCAN算法)。
二、设计方案及论证结果
1.设计方案:
(1)先来先服务算法(First-Come,First-Served,FCFS)
此算法为一种最简单的磁盘调度算法。它直接根据作业请求磁盘的先后顺序对磁盘进行寻访。此算法公平、简单,每个作业的磁盘请求都可以得到处理,不会出现某个作业的请求长期得不到满足的情况。但此算法未对寻道方案进行优化,故平均周转时间及带权周转时间都会较长。
(2)最短寻道时间优先算法(Shortest Seek Time First,SSTF)
此算法优先选择距离当前磁头位置最近的作业磁道请求。此算法可以使得每次寻道时所用的时间都最短,但不能保证平均周转时间及带权周转时间最短。
(3)电梯算法(SCAN)
此算法同时考虑下一个作业磁道请求与当前磁头位置的距离和当前磁头移动方向。本设计默认磁头当前移动方向为自内向外,故SCAN算法先选择当前磁头之外距离其最近的磁道进行访问,直到再无更外的磁道请求,再将磁臂换向,访问磁头内侧距离当前磁头位置最近的作业磁道请求。此算法避免了饥饿现象的出现,每个作业的磁盘请求都可以得到处理,且使每次寻道时间相对较短。
(4)环形扫描算法(C_SCAN)
此算法磁头移动方向一直为自内向外,同时考虑下一个作业磁道请求与当前磁头位置的距离最短。先选择当前磁头之外距离其最近的磁道进行访问,直到再无更外的磁道请求,再直接将磁头移到最内侧磁道(此过程快速移动,并不访问任何磁道),再由内向外顺次访问距离当前磁头位置最近的作业磁道请求。此算法每个作业的磁盘请求都可以得到处理,且使每次寻道时间相对较短。由于该方法一直保持磁头移动寻访方向不变,对两端磁道请求比较有利。
(5)N_SCAN算法
此算法同时考虑下一个作业磁道请求与当前磁头位置的距离和当前磁头移动方向,但每次磁臂调转方向时,将同时处理在磁头向一侧移动过程当中输入的作业请求。本设计默认磁头当前移动方向为自内向外,先选择当前磁头之外距离其最近的磁道进行访问,直到再无更外的磁道请求,接下来一并考虑在磁头向外侧移动过程当中输入的作业请求与磁头内侧未被处理的作业磁道请求。此算法对中间磁道请求比较有利。
2.论证结果:
本设计输入当前磁头位置及一组作业磁道请求。选择所需的算法,输出相应结果:(1)先来先服务算法(FCFS)
按输入顺序输出访问序列。
(2)最短寻道时间优先算法(SSTF)
依次输出距离当前磁头位置最近的磁道请求。
(3)电梯算法(SCAN)
先按照从小到大的顺序输出所输入的当前磁头位置外侧的磁道请求,再按照从大到小的顺序输出所输入的当前磁头位置内侧的磁道请求。
(4)环形扫描算法(C_SCAN)
先按照从小到大的顺序输出所输入的当前磁头位置外侧的磁道请求,再按照从小到大的顺序输出所输入的当前磁头位置内侧的磁道请求。
(5)N_SCAN算法
先按照从小到大的顺序输出所输入的当前磁头位置外侧的磁道请求,再按照从大到小的顺序输出在磁头向外侧移动过程当中输入的作业请求与所输入的当前磁头位置内侧的磁道请求。
三、系统的原理框图
1.总体框图:
本系统划分为五个模块:先来先服务算法模块FCFS(int track[])、最短寻道时间算法模块SSTF(int correnttrack,int track[])、电梯算法模块SCAN(int correnttrack,int track[])、环形扫描算法模块C_SCAN(int correnttrack,int track[])及N_SCAN算法模块N_SCAN(int correnttrack,int track[])。
总体框图:
磁盘调度模拟系统先来先服务算法最短寻道时间优先算法电梯算法环形扫描算法N_SCAN算法 图1 总体框图 2.模块框图:
(1)先来先服务算法模块void FCFS(int track[])直接根据作业请求磁盘的先后顺序对磁盘进行寻访。此算法公平、简单,每个作业的磁盘请求都可以得到处理,不会出现某个作业的请求长期得不到满足的情况。
先来先服务算法流程图:
FCFS输入当前磁头位置 输入一组作业磁道请求i=1i<10是输出track[i]否i=i+1结束
图2 先来先服务算法模块流程图
(2)最短寻道时间优先算法模块void SSTF(int correnttrack,int track[])优先选择距离当前磁头位置最近的作业磁道请求,可以使得每次寻道时所用的时间都最短。
最短寻道时间优先算法流程图:
SSTF输入当前磁头位置及 一组作业磁道请求Min=|corrent-track[0]|i=0i<10是j=0j<10是track[j]!=-1d=|corrent-track[j]j++d 图3最短寻道时间优先算法模块流程图 (3)电梯算法模块void SCAN(int correnttrack,int track[])默认磁头当前移动方向为自内向外,先选择当前磁头之外距离其最近的磁道进行访问,6 直到再无更外的磁道请求,再将磁臂换向,访问磁头内侧距离当前磁头位置最近的作业磁道请求。 电梯算法流程图: C_SCANk=0;min=track[0]i=0i<10是j=0j<10是i++j++Track[j]!=-1&&track[j] 图4 电梯算法模块流程图 (4)环形扫描算法模块void C_SCAN(int correnttrack,int track[])先选择当前磁头之外距离其最近的磁道进行访问,直到再无更外的磁道请求,再直接将 7 磁头移到最内侧磁道(此过程快速移动,并不访问任何磁道),再由内向外顺次访问距离当前磁头位置最近的作业磁道请求。一直保持磁头移动寻访方向不变,对两端磁道请求比较有利。 环形扫描算法流程图: C_SCANk=0;min=track[0]i=0i<10是j=0j<10是i++j++Track[j]!=-1&&track[j] 图5 环形扫描算法模块流程图 (5)N_SCAN算法模块void N_SCAN(int correnttrack,int track[])本设计默认磁头当前移动方向为自内向外,先选择当前磁头之外距离其最近的磁道进行访问,直到再无更外的磁道请求,接下来一并考虑在磁头向外侧移动过程当中输入的作业请求与磁头内侧未被处理的作业磁道请求。此算法对中间磁道请求比较有利。 N_SCAN算法流程图: N_SCANk=0;min=track[0]i=0i<10是j=0j<10是i++j++Track[j]!=-1&&track[j] 1j=k-1;i=10-k;i<10i++是Line[i]=dLine[j]j=j-1;否k=9-k;是否还有作业请求是输入作业请求k=k-1;否K=9;max=Line[9];i=0;lLine[.]=-1i<10是j=0j<10是i++j++Line[j]>maxmax=Line[j];k=j否否lLine[i]=Line[k];Line[k]=-1;max=0;Print(lLine);结束 图7 N_SCAN算法模块流程图(2) 四、设计程序 1.主要模块代码: (1)先来先服务算法void FCFS(int track[])直接根据作业请求磁盘的先后顺序对磁盘进行寻访。先来先服务算法代码: void FCFS(int track[]){ int k;for(k=0;k<9;k++){ printf(“%d->”,track[k]); } printf(“%d”,track[9]);} (2)最短寻道时间优先算法void SSTF(int correnttrack,int track[])优先选择距离当前磁头位置最近的作业磁道请求。最短寻道时间优先算法代码: void SSTF(int correnttrack,int track[]){ int Line[10];int i;int j;int d;int min_d;int k;int corrent; min_d=abs(correnttrack-track[0]); k=0;corrent=correnttrack; for(i=0;i<10;i++){ for(j=0;j<10;j++) { if(track[j]!=-1) { d=abs(corrent-track[j]); if(d { min_d=d; k=j; } } } Line[i]=track[k]; corrent=Line[i]; track[k]=-1; min_d=65536; } printf(“%d->”,correnttrack);Print(Line);} (3)电梯算法void SCAN(int correnttrack,int track[])默认磁头当前移动方向为自内向外,先选择当前磁头之外距离其最近的磁道进行访问,直到再无更外的磁道请求,再将磁臂换向,访问磁头内侧距离当前磁头位置最近的作业磁道请求。 电梯算法代码: void SCAN(int correnttrack,int track[]){ int Line[10];int dLine[10];int i;int j;int k; int min; k=0; min=track[0];for(i=0;i<10;i++){ for(j=0;j<10;j++) { if(track[j]!=-1) { if(track[j] { min=track[j]; k=j; } } } dLine[i]=track[k]; track[k]=-1; min=65536;} k=0;for(i=0;i<10;i++){ if(correnttrack>dLine[i]) { k=k+1; } } j=k;for(i=0;i<10-k;i++){ Line[i]=dLine[j]; j=j+1; } j=k-1;for(i=10-k;i<10;i++){ Line[i]=dLine[j]; j=j-1; } Print(Line);}(4)环形扫描算法void C_SCAN(int correnttrack,int track[])先选择当前磁头之外距离其最近的磁道进行访问,直到再无更外的磁道请求,再直接将磁头移到最内侧磁道(此过程快速移动,并不访问任何磁道),再由内向外顺次访问距离当前磁头位置最近的作业磁道请求。 环形扫描算法代码: void C_SCAN(int correnttrack,int track[]){ int Line[10];int dLine[10];int i;int j;int k;int min;k=0;min=track[0];for(i=0;i<10;i++){ for(j=0;j<10;j++) { if(track[j]!=-1) { if(track[j] { min=track[j]; k=j; } } } dLine[i]=track[k]; track[k]=-1; min=65536;} k=0;for(i=0;i<10;i++){ if(correnttrack>dLine[i]) { k=k+1; } } j=k;for(i=0;i<10-k;i++){ Line[i]=dLine[j]; j=j+1; } j=0;for(i=10-k;i<10;i++){ Line[i]=dLine[j]; j=j+1; } Print(Line);} (5)N_SCAN算法void N_SCAN(int correnttrack,int track[])默认磁头当前移动方向为自内向外,先选择当前磁头之外距离其最近的磁道进行访问,直到再无更外的磁道请求,接下来一并考虑在磁头向外侧移动过程当中输入的作业请求与磁头内侧未被处理的作业磁道请求。 N_SCAN算法 void N_SCAN(int correnttrack,int track[]){ int Line[10];int dLine[10];int lLine[10];int i;int j;int k; int min,max;int choice; for(k=0;k<10;k++){ lLine[k]=-1; } k=0;min=track[0];for(i=0;i<10;i++){ for(j=0;j<10;j++){ if(track[j]!=-1) { if(track[j] { min=track[j]; k=j; } } } dLine[i]=track[k];track[k]=-1;min=65536;} k=0;for(i=0;i<10;i++){ if(correnttrack>dLine[i]){ k=k+1;} } j=k;for(i=0;i<10-k;i++){ Line[i]=dLine[j];printf(“%d->”,Line[i]);Line[i]=-1;j=j+1;} j=k-1;for(i=10-k;i<10;i++){ Line[i]=dLine[j];j=j-1;} printf(“n是否还有作业请求(1-是;0-否):n”);scanf(“%d”,&choice); k=9-k;while(choice==1){ printf(“n请输入作业的磁道请求:n”); scanf(“%d”,&Line[k]); k=k-1; printf(“n是否还有作业请求(1-是;0-否):n”); scanf(“%d”,&choice); } printf(“n磁头继续移动轨迹为:n”); k=9; max=Line[9];for(i=0;i<10;i++){ for(j=0;j<10;j++) { if(Line[j]>max) { max=Line[j]; k=j; } } lLine[i]=Line[k]; Line[k]=-1; max=0;} for(i=0;i<9;i++){ if(lLine[i]!=-1) { printf(“%d->”,lLine[i]); } } printf(“%d”,lLine[9]);} 2.总模块代码: void main(){ int track[10];int n;int correnttrack;int choice=1;printf(“n******磁盘调度模拟系统******”);while(choice==1){ printf(“n请输入当前磁道号:”); scanf(“%d”,&correnttrack); printf(“n请输入一组作业的磁道请求<以回车分隔>:n”); scanf(“%d %d %d %d %d %d %d %d %d %d”,&track[0],&track[1],&track[2],&track[3],&track[4],&track[5],&track[6],&track[7],&track[8],&track[9]); printf(“n请选择算法:n”); printf(“t1.先来先服务算法(FCFS)n”); printf(“t2.最短寻道时间优先算法(SSTF)n”); printf(“t3.电梯算法(SCAN)n”); printf(“t4.环形扫描算法(C_SCAN)n”); printf(“t5.(N_SCAN)n”); scanf(“%d”,&n); printf(“nn”); switch(n) { case 1: printf(“********先来先服务算法(FCFS)*********n磁头移动轨迹为:n”); FCFS(track); break; case 2: printf(“*****最短寻道时间优先算法(SSTF)******n磁头移动轨迹为:n”); SSTF(correnttrack,track); break; case 3: printf(“************电梯算法(SCAN)***********n磁头移动轨迹为:n”); SCAN(correnttrack,track); break; case 4: printf(“*********环形扫描算法(C_SCAN)********n磁头移动轨迹为:n”); C_SCAN(correnttrack,track); break; case 5: printf(“****************N_SCAN***************n磁头移动轨迹为:n”); N_SCAN(correnttrack,track); break; } } printf(“n请问是否继续?(1-继续;0-退出)n”); scanf(“%d”,&choice);} 五、实验结果 1.总模块实验结果: 程序开始运行,将出现输入选择界面; 图8 主界面 2.基础模块实验结果: (1)先来先服务算法(First-Come,First-Served,FCFS) 按输入顺序输出访问序列。 选择该算法后,将输出相应磁头移动轨迹: 图9 先来先服务算法0 输出结果为69-> 23-> 120-> 45-> 77-> 31-> 55-> 99-> 150-> 2 满足要求。 (2)最短寻道时间优先算法(Shortest Seek Time First,SSTF) 依次输出距离当前磁头位置最近的磁道请求。选择该算法后,将输出相应磁头移动轨迹: 图10 最短寻道优先算法 输出结果为45-> 55-> 69-> 77-> 99-> 120-> 150-> 31-> 23-> 2 满足要求。(3)电梯算法(SCAN) 先按照从小到大的顺序输出所输入的当前磁头位置外侧的磁道请求,再按照从大到小的顺序输出所输入的当前磁头位置内侧的磁道请求。 选择该算法后,将输出相应磁头移动轨迹: 图11 电梯算法 输出结果为55-> 69-> 77-> 99-> 120-> 150-> 45-> 31-> 23-> 2 满足要求。 3.扩展模块实验结果: (1)环形扫描算法(C_SCAN) 先按照从小到大的顺序输出所输入的当前磁头位置外侧的磁道请求,再按照从小到大的顺序输出所输入的当前磁头位置内侧的磁道请求。 选择该算法后,将输出相应磁头移动轨迹: 图12 环形扫描算法 输出结果为55-> 69-> 77-> 99-> 120-> 150-> 2-> 23-> 31-> 45 满足要求。 (2)N_SCAN算法 先按照从小到大的顺序输出所输入的当前磁头位置外侧的磁道请求,再按照从大到小的顺序输出在磁头向外侧移动过程当中输入的作业请求与所输入的当前磁头位置内侧的磁道请求。 选择该算法后,将输出相应磁头移动轨迹: 图13 N_SCAN算法 输出结果为55-> 69-> 77-> 99-> 120-> 150-> 88-> 45-> 31-> 23-> 8-> 2-> 1 满足要求。 六、调试分析及故障处理 1.调试分析: (1)在代码中错误的使用了中文括号“)”,导致程序出错。 图14 错误报告(2)在定义函数时误在结尾处加分号“;”,导致调试过程中出错。 图15 错误报告 (3)由于未对变量初始化,导致错误: 图16 错误警告 未对k初始化,如下图: 图17 变量表 2.故障处理: 重新检查代码,发现错误,并及时修正。调试后无误: 图18 无错误及警告 发生故障时,可采取单步调试的方法,逐条语句检查,修正错误。 图19 故障处理过程 七、设计结论 磁盘,是一种很重要也很常用的外设,其分配也有一定的分配策略。在操作系统中,作业对磁盘的请求常常要排队,由此需要一些高效率的磁盘分配策略算法。本系统设计了五种寻道策略,其中先来先服务算法为一种最简单的磁盘调度算法,它直接根据作业请求磁盘的先后顺序对磁盘进行寻访,公平、简单,每个作业的磁盘请求都可以得到处理,不会出现某个作业的请求长期得不到满足的情况,但未对寻道方案进行优化,故平均周转时间及带权周转时间都会较长;最短寻道时间优先算法优先选择距离当前磁头位置最近的作业磁道请求,可以使得每次寻道时所用的时间都最短,但不能保证平均周转时间及带权周转时间最短;电 梯算法同时考虑下一个作业磁道请求与当前磁头位置的距离和当前磁头移动方向先选择当前磁头之外距离其最近的磁道进行访问,直到再无更外的磁道请求,再将磁臂换向,访问磁头内侧距离当前磁头位置最近的作业磁道请求,避免了饥饿现象的出现,每个作业的磁盘请求都可以得到处理,且使每次寻道时间相对较短;环形扫描算法的磁头移动方向一直为自内向外,同时考虑下一个作业磁道请求与当前磁头位置的距离最短,先选择当前磁头之外距离其最近的磁道进行访问,直到再无更外的磁道请求,再直接将磁头移到最内侧磁道(此过程快速移动,并不访问任何磁道),再由内向外顺次访问距离当前磁头位置最近的作业磁道请求,使每个作业的磁盘请求都可以得到处理,且使每次寻道时间相对较短,由于该方法一直保持磁头移动寻访方向不变,对两端磁道请求比较有利; N_SCAN算法同时考虑下一个作业磁道请求与当前磁头位置的距离和当前磁头移动方向,但每次磁臂调转方向时,将同时处理在磁头向一侧移动过程当中输入的作业请求,先选择当前磁头之外距离其最近的磁道进行访问,直到再无更外的磁道请求,接下来一并考虑在磁头向外侧移动过程当中输入的作业请求与磁头内侧未被处理的作业磁道请求,此算法对中间磁道请求比较有利。总之,各种算法都有其长处,也各有不足,需要在实际应用中权衡利弊,择优使用。 八、心得体会 本次操作系统课程设计,我不仅完成了课程要求中的任务,更在中期检查后听取了老师的建议,自己上网查找了其他两种磁盘调度算法加入了程序当中,使系统更加完善和完整。在这过程中,我不仅加深了对操作系统的了解,进一步熟悉了C语言编程和Microsoft Visual C++ 6.0的使用,更加了解了很多之前在课本中和课程学习中并不了解和知道的知识,扩展了视野,丰富了体验。 由于自己的知识和能力还不到位,在这两周的时间里也经历了很多困难和挑战,但我认为,在这过程中的每一次的错误和故障,都使我收获颇丰,使我成长了很多。 当然,这个磁盘调度系统的设计远非完美,还有很多地方可以改进,例如界面可以更加友好,资源可以更加节约,算法也还有优化的余地,但是时间有限,本人经历也有限,在课程设计时间允许的范围内只能做到这样,我会在课余时间自行完善该磁盘调度算法程序。 最后,这次课设给我带来了很多的收获,非常感谢在课设过程中老师不厌其烦的讲解指导和身边各位同学的细心帮助。 1.实验题目: 磁盘调度算法。 建立相应的数据结构; 在屏幕上显示磁盘请求的服务状况; 将一批磁盘请求的情况存磁盘文件,以后可以读出并重放; 计算磁头移动的总距离及平均移动距离; 支持算法:FIFO、SSTF、SCAN、CSCAN; 2.设计目的: 调度磁盘I/O请求服务,采用好的方式能提高访问时间和带宽。本实验通过编程对磁盘调度算法的实现,加深对算法的理解,同时通过用C++语言编写程序实现这些算法,并在windos平台上实现,更好的掌握操作系统的原理以及实现方法,提高综合运用专业课知识的能力。 3.任务及要求 3.1 设计任务 编程实现下述磁盘调度算法,并求出每种算法的平均寻道长度: 1、先来先服务算法(FCFS) 2、最短寻道时间算法(SSTF) 3、扫描算法(SCAN) 4、循环扫描算法(CSCAN) 3.2 设计要求 对用户指定的磁盘调度请求序列,基于以上四种算法,实现各自的调度顺序并输出,同时计算出各种算法下的平均寻道长度。 4.算法及数据结构 4.1算法的总体思想 queue[n] 为请求调度序列,diskrode为磁盘磁道数,headstarts为正在调度的磁道 ①先来先服务算法(FCFS)按queue[n]数组的顺序进行磁盘调度,将前一个调度磁道与下一个调度磁道的差值累加起来,得到总的寻道长度,再除以n得到平均寻道长度。 ②最短寻道时间优先算法(SSTF)将queue[n]进行由小到大的排序,首先定位当前调度磁headstarts在queue[n]的位置,通过循环语句找出离起始磁头最短的位置。 ③扫描算法(SCAN) 将queue[n]进行由小到大的排序,首先定位当前调度磁headstarts在queue[n]的位置,然后在此位置按给定的方向遍历queue[n],当道端点(queue[0]或queue[n-1])时,再在定位处反向遍历到另一端。当调度磁道不在queue端点时,总的寻道长度为为前一个磁道与后一个磁 道差值的累加,当到达端点且queue[n]未全调度时,总寻道长度加上端点值再加上下一个调度磁道的值,再按前面的算法进行,直到磁道全部都调度完毕,得到总的寻道长度,除以n得到平均寻道长度。 ④循环扫描算法(CSCAN)将queue[n]进行由小到大的排序,首先定位当前调度磁headstarts在queue[n]的位置,然后在此位置按给定的方向遍历queue[n],当道端点(queue[0]或queue[n-1])时,反向到另一端点再以此方向进行遍历,直到queue[n]中所有都调度完。当调度磁道不在queue端点时,总的寻道长度为为前一个磁道与后一个磁道差值的累加,当到达端点且queue[n]未全调度时,总寻道长度加上端点值再加上磁盘磁道总长度,再加上下一个调度磁道的值,再按前面的算法进行,直到磁道全部都调度完毕,得到总的寻道长度,除以n得到平均寻道长度。 5、源代码: #include 1、先来先服务算法(FCFS)**********”< cout<<“****** 2、最短寻道时间优先算法(SSTF)**********”< cout<<“****** 3、扫描算法(SCAN)**********”< cout<<“****** 4、循环扫描算法(CSCAN)**********”< cout<<“****** 5、退出 **********”< /*======================初始化序列=======================*/ void init(int queue[],int queue_copy[],int n){ int i;for(i=0;i //对当前正在执行的磁道号进行定位,返回磁道号小于当前磁道中最大的一个 int fix(int queue[], int n, int headstarts){ int i =0;while(i /* ====================以下是FCFS算法==================*/ void FCFS(int queue[],int n,int diskrode,int headstarts)//queue是请求调度序列,n为其个数,diskroad为磁盘磁道数,headstarts为正在调度的磁道 { cout<<“************以下为FCFS调度算法***********”< /*=====================SSTF算法====================*/ void SSTF(int queue[], int n, int diskrode, int headstarts){ int k=1;int l,r;int i,j,count=0;queue =bubble(queue,n);cout<<“************以下为SSTF调度算法***********”< -headstarts)){ cout< /*======================以下是SCAN算法====================*/ void SCAN(int queue[], int n, int diskrode, int headstarts){ int direction, i, fixi;cout<<“***********以下是SCAN调度算法*************”< /*======================以下是CSCAN算法====================*/ void CSCAN(int queue[],int n,int diskrode,int headstarts){ int direction,i,fixi;cout<<“***********以下是CSCAN调度算法*************”< void main(){ int n, i, diskrode, headstarts;//n表示调度磁盘请求序列queue的长度,diskrode表示磁盘磁道的个数,headstarts表示目前正在调度的磁道; cout<<“请输入磁盘的总磁道数:”< if(menux ==2)SSTF(queue,n,diskrode,headstarts); if(menux ==3)SCAN(queue,n,diskrode,headstarts);if(menux ==4)CSCAN(queue,n,diskrode,headstarts);if(menux ==5)cout<<“程序结束,谢谢使用!”< 沈阳理工大学课程设计专用纸 Noi 目 录 1 课程设计目的及要求……………………………………………………错误!未定义书签。2 相关知识…………………………………………………………………错误!未定义书签。3 题目分析…………………………………………………………………2 4 概要设计…………………………………………………………………2 4.1 先来先服务(FCFS)的设计思想……………………………….2 4.2 最短寻道时间优先调度(SSTF)的设计思想…………………..2 4.3 扫描算法(SCAN)的设计思想…………………………………2 4.4 循环扫描(CSCAN)的设计思想………………………………..2 5 代码及流程………………………………………………………………3 5.1 流程图……………………………………………………………...3 5.2 源代码……………………………………………………………...8 6 运行结果…………………………………………………………………16 7 设计心得…………………………………………………………………19 参考文献…………………………………………………………………………19 沈阳理工大学 沈阳理工大学课程设计专用纸 No1 1 课程设计目的及要求 设计目的:加深对操作系统原理的进一步认识,加强实践动手能力和程序开发能力的培养,提高分析问题解决问题的能力,培养合作精神,以巩固和加深磁盘调度的概念。操作系统是一门工程性很强的课程,它不仅要求学生掌握操作系统的工作原理和理论知识,也要求学生的实际动手能力,以加深对所学习内容的理解,使学生熟练地掌握计算机的操作方法,使用各种软件工具,加强对课程内容的理解。这次课程设计,就是通过模拟磁臂调度来加深对操作系统中磁臂调度概念的理解。使学生熟悉磁盘管理系统的设计方法;加深对所学各种磁盘调度算法的了解及其算法的特点。 设计要求:编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度;要求设计主界面可以灵活选择某算法,且以下算法都要实现 1、先来先服务算法(FCFS) 2、最短寻道时间优先算法(SSTF) 3、扫描算法(SCAN) 4、循环扫描算法(CSCAN)相关知识 数据结构:数组 now:当前磁道号; array[]:放置磁道号的数组; void FCFS(int array[],int m)先来先服务算法(FCFS)void SSTF(int array[],int m)最短寻道时间优先算法(SSTF)void SCAN(int array[],int m)扫描算法(SCAN)void CSCAN(int array[],int m)循环扫描算法(CSCAN)磁盘调度:当有多个进程都请求访问磁盘时,采用一种适当的驱动调度算法,使各进程对磁盘的平均访问(主要是寻道)时间最小。目前常用的磁盘调度算法有:1)闲来先服务2)最短寻道时间优先3)扫描算法4)循环扫描算法等 沈阳理工大学 沈阳理工大学课程设计专用纸 No2 3 题目分析 选择一个自己熟悉的计算机系统和程序设计语言模拟操作系统基本功能的设计方法及其实现过程 完成各分项功能。在算法的实现过程中,要求可决定变量应是动态可变的;同时模块应该有一个合理的输出结果。具体可参照实验的程序模拟.各功能程序要求自行编写程序实现,不得调用现有操作系统提供的模块或功能函数。磁盘调度程序模拟。先来先服务调度算法.最短寻道时间优先调度,循环(SCAN)调度算法。程序设计语言自选,最终以软件(含源代码以及执行程序)和设计报告的形式提交课程设计结果.。磁盘调度让有限的资源发挥更大的作用。在多道程序设计的计算机系统中,各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快,因此我们有必要为每个磁盘设备建立一个等待队列。概要设计 1.先来先服务(FCFS)的设计思想 即先来的请求先被响应。FCFS策略看起来似乎是相当“公平”的,但是当请求的频率过高的时候FCFS策略的响应时间就会大大延长。FCFS策略为我们建立起一个随机访问机制的模型,但是假如用这个策略反复响应从里到外的请求,那么将会消耗大量的时间。为了尽量降低寻道时间,看来我们需要对等待着的请求进行适当的排序,而不是简单的使用FCFS策略。这个过程就叫做磁盘调度管理。有时候fcfs也被看作是最简单的磁盘调度算法。 2.最短寻道时间优先调度(SSTF)的设计思想 最短时间优先算法选择这样的进程。要求访问的磁道,与当前磁头所在的磁道距离最近,以使每次的寻道时间最短。 3.扫描算法(SCAN)的设计思想 扫描(SCAN)调度算法:该算法不仅考虑到欲访问 的磁道与当前磁道间的距离,更优先考虑的是磁头当前的移动方向。例如,当磁头正在自里向外移动时,SCAN算法所考虑的下一个访问对象,应是其欲访问的磁道,既在当前磁道之外,又是距离最近的。这样自里向外的访问,直至再无更外的磁道需要访问时,才将磁道换向自外向里移动。这时,同样也是每次选择这样的进程来调度,也就是要访问的当前位置内距离最近者,这样,磁头又逐步地从外向里移动,直至再无更里面的磁道要访问,从而避免了出现“饥饿”现像。 4.循环扫描(CSACN)的设计思想 循环扫描(CSCAN)算法:当磁头刚从里向外移动而越过了某一磁道时,恰好又有一进程请求访问此磁道,这时,该里程就必须等待,为了减少这种延迟,CSCAN算法规定磁头单向移动,而本实验过程中我们所设计的是磁头从里向外移动,而从外向里移动时只须改方向而已,本实验未实现。但本实验已完全能演示循环扫描的全过程。 沈阳理工大学 沈阳理工大学课程设计专用纸 No3 5 代码及流程 1.先来先服务(FCFS) 图 1—1 FCFS的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No4 2.最短寻道时间优先调度(SSTF) 图1—2 SSTF的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No5 3.扫描算法(SCAN) 图1—3 SCAN的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No6 4.循环扫描(CSCAN) 图1—4 CSCAN的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No7 图1—5 主函数的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No8 源代码: #include“stdio.h” #include“stdlib.h” //#include“iostream.h” #define maxsize 100 //定义最大数组域 //先来先服务调度算法 void FCFS(int array[],int m){ int sum=0,j,i;int avg;printf(“n FCFS调度结果: ”);for(i=0;i } avg=sum/(m-1);//计算平均寻道长度 printf(“n 移动的总道数: %d n”,sum);printf(“平均寻道长度: %d n”,avg);} //最短寻道时间优先调度算法 void SSTF(int array[],int m){ int temp;int k=1;int now,l,r;int i,j,sum=0;int avg;for(i=0;i 沈阳理工大学 沈阳理工大学课程设计专用纸 No9 array[i]=array[j];array[j]=temp;} } } for(i=0;i for(i=m-1;i>=0;i--)//将数组磁道号从大到小输出 printf(“%d ”,array[i]);sum=now-array[0];//计算移动距离 } else if(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号 { for(i=0;i printf(“%d ”,array[l]);sum+=now-array[l];//计算移动距离 now=array[l];l=l-1;} else 沈阳理工大学 沈阳理工大学课程设计专用纸 No10 { printf(“%d ”,array[r]);sum+=array[r]-now;//计算移动距离 now=array[r];r=r+1;} } if(l=-1){ for(j=r;j printf(“%d ”,array[j]);} sum+=array[m-1]-array[0];//计算移动距离 } else { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} sum+=array[m-1]-array[0];//计算移动距离 } } avg=sum/m;printf(“n 移动的总道数: %d n”,sum);printf(“平均寻道长度: %d n”,avg);} //扫描算法 void SCAN(int array[],int m)//先要给出当前磁道号和移动臂的移动方向 { int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;i 沈阳理工大学 沈阳理工大学课程设计专用纸 No11 { temp=array[i];array[i]=array[j];array[j]=temp;} } } for(i=0;i printf(“n SCAN调度结果: ”);for(i=m-1;i>=0;i--){ printf(“%d ”,array[i]);//将数组磁道号从大到小输出 } sum=now-array[0];//计算移动距离 } else if(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号 { printf(“n SCAN调度结果: ”);for(i=0;i 沈阳理工大学 沈阳理工大学课程设计专用纸 No12 { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} for(j=r;j //循环扫描算法 void CSCAN(int array[],int m){ int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;i 沈阳理工大学 沈阳理工大学课程设计专用纸 No13 { temp=array[i];array[i]=array[j];array[j]=temp;} } } for(i=0;i printf(“n CSCAN调度结果: ”);for(i=0;i printf(“%d ”,array[i]);//将磁道号从小到大输出 } sum=now-array[0]+array[m-1];//计算移动距离 } else if(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号 { printf(“n CSCAN调度结果: ”);for(i=0;i printf(“%d ”,array[i]);//将磁道号从小到大输出 } sum=array[m-1]-now;//计算移动距离 } else { while(array[k] 沈阳理工大学 沈阳理工大学课程设计专用纸 No14 { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} for(j=m-1;j>=r;j--){ printf(“%d ”,array[j]);} sum=2*(array[m-1]-array[0])-array[r]+now;//计算移动距离 }//磁道号减小方向 else { for(j=r;j // 操作界面 int main(){ int c;FILE *fp;//定义指针文件 int cidao[maxsize];//定义磁道号数组 int i=0,count;fp=fopen(“cidao.txt”,“r+”);//读取cidao.txt文件 if(fp==NULL)//判断文件是否存在 { printf(“n 请 先 设 置 磁 道!n”);exit(0);} while(!feof(fp))//如果磁道文件存在 沈阳理工大学 沈阳理工大学课程设计专用纸 No15 { fscanf(fp,“%d”,&cidao[i]);//调入磁道号 i++;} count=i-1;printf(“n-------------------n”);printf(“ 10-11OS课程设计--磁盘调度算法系统n”);printf(“ 计算机科学与技术二班n”);printf(“ 姓名:宋思扬n”);printf(“ 学号:0803050203n”);printf(“ 电话:************n”);printf(“ 2010年12月29日n”);printf(“n-------------------n”);printf(“n 磁道读取结果:n”);for(i=0;i 1、先来先服务算法(FCFS)n”);printf(“ 2、最短寻道时间优先算法(SSTF)n”);printf(“ 3、扫描算法(SCAN)n”);printf(“ 4、循环扫描算法(CSCAN)n”);printf(“ 5.退出n”);printf(“n”);printf(“请选择:”);scanf(“%d”,&c);if(c>5)break;switch(c)//算法选择 { case 1: FCFS(cidao,count);//先来先服务算法 printf(“n”);break;case 2: SSTF(cidao,count);//最短寻道时间优先算法 printf(“n”);break;case 3: 沈阳理工大学 沈阳理工大学课程设计专用纸 No16 SCAN(cidao,count);//扫描算法 printf(“n”);break;case 4: CSCAN(cidao,count);//循环扫描算法 printf(“n”);break;case 5: exit(0);} } return 0;} 6 运行结果 图2—1 运行界面 沈阳理工大学 沈阳理工大学课程设计专用纸 No17 图2—2 运行FCFS的界面 图2—3 运行SSTF的界面 图2—4 运行SCAN的界面 沈阳理工大学 沈阳理工大学课程设计专用纸 No18 图2—5 运行SCAN的界面 图2—6 运行CSCAN的界面 图2—7 运行CSCAN的界面 沈阳理工大学 沈阳理工大学课程设计专用纸 No19 运行结果: 四种磁盘调度运行结果正确,与预期的相符。设计心得 此次操作系统的课程设计,从理论到实践,在两个星期的日子里,可以说是苦多于甜,但是可以学到很多很多的的东西,同时不仅可以巩固了以前所学过的知识,而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的,只有理论知识是远远不够的,只有把所学的理论知识与实践相结合起来,从理论中得出结论,才能真正为社会服务,从而提高自己的实际动手能力和独立思考的能力。 本次实验首先要了解磁盘调度的工作原理及四种调度方法的工作原理。在课程设计前的准备工作时,先把这部分工作做完了。在设计总的程序框架的时候,要注意各功能模块的位置,尽量做到简洁、有序;各功能模块与主程序要正确衔接。 在设计的过程中遇到许多问题,我设计的是四种调度算法中的后两种。例如:在最初程序设计时主要有两种构思:1)选用数据结构是链表的。2)选用数组。我最初尝试了用链表,觉得方便易懂,但是在循环扫描处出现了些问题,后来又转变了设计思路,选用了数组,直接进行排序,然后再联系到各功能模块。 同时在设计的过程中发现了自己的不足之处,对以前所学过的知识理解得不够深刻,掌握得不够牢固,自身知识的很多漏洞,看到了自己的实践经验还是比较缺乏,理论联系实际的能力还急需提高。比如说编语言掌握得不好,应用程序编写不太会……通过这次课程设计之后,一定把以前所学过的知识重新温故。在此,也感谢在课程设计过程中帮我解惑的老师和同学。参考文献 [1] 《操作系统》 人民邮电出版社 宗大华 宗涛 陈吉人 编著 [2] 《C语言程序设计》 清华大学出版社 马秀丽 刘志妩 李筠 编著 [3] 《操作系统实验指导书》 沈阳理工大学 唐巍 菀勋 编著 沈阳理工大学 实验报告六磁盘调度算法 班级:软技2班学号:201467003084 姓名:刘道林 一. 实验内容: 熟悉磁盘的结构以及磁盘的驱动调度算法的模拟,编程实现简单常用的磁盘驱动调度算法先来先服务(FIFO)、电梯调度算法、最短寻找时间优先算法、扫描(双向扫描)算法、单向扫描(循环扫描)算法等。编程只需实现两个算法。 题目可 以选取教材或习题中的相关编程实例。 编程语言建议采用c/c++或Java。模拟程序鼓励采用随机数技术、动态空间分配技术,有条件 的最好能用图形界面展现甚至用动画模拟。 实验性质:验证型。 二. 实验目的和要求 1)掌握使用一门语言进行磁盘驱动调度算法的模拟; 2)编写程序将磁盘驱动调度算法的过程和结果能以 较简明直观的方式展现 出来。 三. 实验原理、方法和步骤 1.实验原理 磁盘驱动调度对磁盘的效率有重要影响。磁盘驱动调度算法的好坏直接影响辅助存储器的效率,从而影响计算机系统的整体效率。 常用的磁盘驱动调度算法有:最简单的磁盘驱动调度算法是先入先出(FIFO)法。这种算法的实质是,总是严格按时间顺序对磁盘请 求予以处理。算法实现简单、易于理解并且相对公平,不会发生进程饿死现象。但该算法可能会移动的柱面数较多并且会经常更换移 动方向,效率有待提高。 最短寻找时间优先算法:总是优先处理最靠近的请求。该算法移动的柱面距离较小,但可能会经常改变 移动方向,并且可能会发生进程饥饿现象。 电梯调度:总是将一个方向上的请求全部处理完后,才改变方向继续处理其他请求。 扫描(双向扫描):总是从最外向最里进行扫描,然后在从最里向最外扫描。该算法与电梯调度算法的区别是电梯调度在没有最外或 最里的请求时不会移动到最外或最里柱面,二扫描算法总是移到最外、最里柱面。两端的请求有优先服被务的迹象。 循环扫描(单 向扫描):从最外向最里进行柱面请求处理,到最里柱面后,直接跳到最外柱面然后继续向里进行处理。该算法与扫描算法的区别是,回来过程不处理请求,基于这样的事实,因为里端刚被处理。 2.实验方法 1)使用流程图描述演示程序的设计思想; 2)选取c/c++、Java等计算机语言,编程调试,最终给出运行正确的程序。 四. 实验结果分析 能够将磁盘驱动调度算法在各种情况下都能得出正确的结论。对FIFO、最短寻找时间优先或电梯调度算法能够 在多次模拟数据下得出平均移动柱面数,并进行效率比较分析 五.源程序代码 #include char name[32]; /*定义进程名称*/ int team; /*定义柱面号*/ int ci; /*定义磁道面号*/ int rec; /*定义记录号*/ struct _proc *prior; struct _proc *next;} PROC; PROC *g_head=NULL,*g_curr=NULL,*local; int record=0; int yi=1;void init(){ PROC *p; 链表(初始I/O表)*/ g_head =(PROC*)malloc(sizeof(PROC)); g_head->next = NULL; g_head->prior = NULL; p =(PROC*)malloc(sizeof(PROC)); strcpy(p->name, “P1”); p->team=100; p->ci=10; p->rec=1; p->next = NULL; p->prior = g_head; g_head->next = p; g_curr=g_head->next; p =(PROC*)malloc(sizeof(PROC)); strcpy(p->name, “P2”); p->team=30; p->ci=5; p->rec=5; /*初始化 p->next = NULL; p->prior = g_curr; g_curr->next = p; g_curr=p; p =(PROC*)malloc(sizeof(PROC)); strcpy(p->name, “P3”); p->team=40; p->ci=2; p->rec=4; } void PrintInit() { p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr=p;p =(PROC*)malloc(sizeof(PROC));strcpy(p->name, “P4”);p->team=85;p->ci=7;p->rec=3;p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr=p;p =(PROC*)malloc(sizeof(PROC));strcpy(p->name, “P5”);p->team=60;p->ci=8;p->rec=4;p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr=g_head->next;local =(PROC*)malloc(sizeof(PROC)); /*选中进程*/ strcpy(local->name, “P0”);local->team=0;local->ci=0;local->rec=0;local->next=NULL;local->prior=NULL; /*打印I/O表*/ PROC *t = g_head->next;printf(“------n”);printf(“ ---------I/O LIST---------n”);printf(“ process team ci rec n”);while(t!=NULL) { printf(“%4s %8d %8d %5dn”, t->name, t->team, t->ci, t->rec); t = t->next; } printf(“nnCurrent process is :n”); printf(“------------------------------nn”); printf(“ process team ci rec n”); printf(“%4s %8d %8d %5dn”, local->name, local->team, local->ci, local->rec); switch(yi) { case 1: { printf(“current direction is UPn”); break; } case 0: { printf(“current direction is downn”); break; } } } void acceptreq() /*接受请求函数*/ { PROC *p; p =(PROC*)malloc(sizeof(PROC)); printf(“please input the information of the new processnprocess-name:nprocess-teamnprocess-cinprocess-recn”); printf(“1.namen”); scanf(“%s”,p->name); printf(“2.team 0-199n”); scanf(“%d”,&p->team); /*输入请求进程信息*/ printf(“3.ci 0-19n”); scanf(“%d”,&p->ci); printf(“4.rec 0-7n”); scanf(“%d”,&p->rec); getchar(); g_curr=g_head; /*将此节点链入I/O请求表*/ while(g_curr->next!=NULL)g_curr=g_curr->next; p->next=NULL; p->prior=g_curr; g_curr->next=p; g_curr=g_head->next; printf(“NEW I/O LISTnn”); PrintInit(); /*将新的I/O请求表输出*/ } void qddd() /*驱动调度函数*/ { PROC *out; int min; int max=g_head->next->team; if(g_head->next==NULL); /*若已全部调度,则空操作*/ else { switch(yi) { case 1: { min=g_head->next->team; out=g_head->next; /*选出最小的team进程,模拟启动此进程*/ strcpy(local->name,out->name); local->team=out->team; local->ci=out->ci; local->rec=out->rec; for(g_curr=g_head->next;g_curr!=NULL;g_curr=g_curr->next) { if(g_curr->team > record) { min = g_curr->team; break; } } for(g_curr=g_head->next;g_curr!=NULL;g_curr=g_curr->next) { if(min>=g_curr->team&&g_curr->team>record) { min=g_curr->team;out=g_curr; strcpy(local->name,out->name); local->team=out->team;local->ci=out->ci;local->rec=out->rec; } } printf(“n-----------------------n”); printf(“the process choosed :n”); printf(“ process team ci rec n”); printf(“%4s %8d %8d %5dn”, out->name, out->team, out->ci,out->rec); (g_curr=g_head->next;g_curr!=NULL;g_curr=g_curr->next) (max if(max==record) yi=0; record=1000; break; break; }/*case 1*/ case /*case 1 的对称过程*/ { max=g_head->next->team; strcpy(local->name,out->name); local->team=out->team; record = local->team;printf(“%d”,record);for { if } { } 0: out=g_head->next; local->ci=out->ci; local->rec=out->rec; for(g_curr=g_head->next;g_curr!=NULL;g_curr=g_curr->next) { if(g_curr->team < record) { max = g_curr->team; break; } (g_curr=g_head->next;g_curr!=NULL;g_curr=g_curr->next) { if(max<=g_curr->team&&g_curr->team { max=g_curr->team;out=g_curr; strcpy(local->name,out->name); local->team=out->team; local->ci=out->ci;local->rec=out->rec; } } printf(“n-----------------------n”); printf(“the process choosed :n”); printf(“ process team ci rec n”); printf(“%4s %8d %8d %5dn”, out->name, out->team, out->ci,out->rec); } for min=g_head->next->team; for(g_curr=g_head->next;g_curr!=NULL;g_curr=g_curr->next) { if(min>g_curr->team)min=g_curr->team; } record = local->team; if(min==record) { yi=1;record=0; break; } break; } default : return-1; }/*switch*/ if(out->next==NULL) /*将选中的进程从I/O请求表中删除*/ { out->prior->next=NULL;free(out); } else { out->prior->next=out->next; out->next->prior=out->prior; free(out); } }/*else*/ } void acceptnum() /*通过输入0~1选择‘驱动调度’或是‘接受请求’*/ { float num; char c; while(1) { printf(“---------------n”); printf(“please input a number between 0 and 1nnum<=0.5:accept requestnnum>0.5:qudong diaodunnnum==2:I/O LISTnnnum=?n”); scanf(“%f”,&num); getchar(); while((num<0||num>1)&&num!=2) /*过滤不合法数据 注意:本程序其他输入数据可能未过滤*/ { printf(“number ERROR!Input again please!nnum=?n ”); scanf(“%f”,&num); getchar(); } if(num>0.5&&num!=2) /*驱动调度*/ { if(g_head->next==NULL) { printf(“nn”); printf(“---------------------n”); printf(“I/O list is empty!!n”); /*请求表为空 无需调度*/ } else { printf(“qudong diaodun”); qddd(); /*调用函数进行调度*/ } } else if(num<=0.5) /*接受请求*/ { printf(“accept requestnn”); acceptreq(); } else if(num==2) /*通过输入2显示当前请求I/O表*/ { printf(“I/O LIST;”); printf(“-------------------n”); PrintInit(); printf(“n”); printf(“-----------------------n”); printf(“choose 'n' to quit else to continuen”); if(strcmp(c=getchar(),'n')==0||strcmp(c=getchar(),'N')==0) clrscr(); printf(“nnnnnn”); printf(“thank you for testing my program!n”); printf(“ ---by 01n”); sleep(2); printf(“nnBYEbye!”); sleep(2); return-1; else { clrscr(); } /*输入n离开本程序*/ { } } } } main() /*主程序*/ { init(); PrintInit(); acceptnum();} 操作系统课程设计 磁 盘 调 度 实 践 报 告 姓名: 董宇超 班级:计算机一班 学号:0906010124 目录: 实践内容 实践目的及意义 功能设计及数据结构 调试运行及测设分析 存在的问题及改进设想 实践体会 总结 参考文献 正文: 1.实践内容: 假设磁盘只有一个盘面,并且磁盘是可移动头磁盘。 磁盘是可供多个进程共 享的存储设备,但一个磁盘每个时刻只能为一个进程服务。当有进程在访问 某个磁盘时,其它想访问该磁盘的进程必须等待,直到磁盘一次工作结束。当有多个进程提出输入输出请求而处于等待状态时,可用电梯调度算法从若 干个等待访问者中选择一个进程,让它访问磁盘。为此设置“驱动调度”进 程。 由于磁盘与处理器是并行工作的,所以当磁盘在为一个进程服务时,占有处理器的其它进程可以提出使用磁盘(这里我们只要求访问磁道),即动 态申请访问磁道,为此设置“接受请求”进程。 要求模拟电梯调度算法,对磁盘进行移臂操作,编程实现。 2.实践目的: 磁盘是高速、大容量、旋转型、可直接存取的存储设备。它作为计算机 系统的辅助存储器,担负着繁重的输入输出工作,在现代计算机系统中往往 同时会有若干个要求访问磁盘的输入输出要求。 系统可采用一种策略,尽可能按最佳次序执行访问磁盘的请求。由于磁 盘访问时间主要受寻道时间T的影响,为此需要采用合适的寻道算法,以降 低寻道时间。 本实验要求模拟设计一个磁盘调度程序,观察调度程序的动态运 行过程。通过实验理解和掌握磁盘调度的职能。 3.功能设计: 由于程序简单,没有设计结构体,只定义了一下变量: int m=0;//记录磁道数目 int n;//接受输入的磁道号 int disk[1000];//保存磁道序列 int currenttrack;//当前磁道号 int t; int i=0,j=0,k=0;//循环参数 int option;//记录寻到方向 int sum=0;//统计寻道长度 源代码: #include int n;//接受输入的磁道号 int disk[1000];//保存磁道序列 int currenttrack;//当前磁道号 int t;int i=0,j=0,k=0;//循环参数 int option;//记录寻到方向 int sum=0;//统计寻道长度 printf(“请输入当前的磁道号:”);scanf(“%d”,¤ttrack); printf(“n--------------------1.向磁道号增加的方向访问--------------------”);printf(“n--------------------2.向磁道号减少的方向访问--------------------”);printf(“n请选择的当前磁头移动方向(1/2):”);scanf(“%d”,&option); printf(“n请输入磁道请求序列(0~999并以<-1>结束):n”);scanf(“%d”,&n);while(n!=-1){ disk[i]=n; m++;i++; scanf(“%d”,&n);} /* 冒泡排序 使磁道请求序列从小到大排序 */ for(j=0;j for(i=0;i { if(disk[i]>disk[i+1]) { t=disk[i]; disk[i]=disk[i+1]; disk[i+1]=t; } } } /* 找到当前磁道号在磁道请求序列中的排序位置 */ k=0;for(i=0;i k++;else break;} printf(“n--------------电梯算法调度后的磁盘调度序列-------------n”);/* 第一种: 当前磁道号先向外再向里读 */ if(option==1){ for(i=k;i printf(“%5d”,disk[i]);} for(i=k-1;i>=0;i--){ printf(“%5d”,disk[i]);} sum=2*(disk[m-1]-disk[k])+disk[k]-disk[0];printf(“n寻道长度为:%5d”,sum);} /* 第二种: 当前磁道号先向里再向外读 */ if(option==2){ for(i=k-1;i>=0;i--){ printf(“%d ”,disk[i]); sum+=disk[i];} for(i=k;i printf(“%5d”,disk[i]); sum+=disk[i];} sum=disk[m-1]-disk[k]+2*(disk[k]-disk[0]);printf(“n寻道长度为:%5d”,sum); } printf(“n”);} 4.调试运行: 运行开始后出现如下界面,举例输入5: 然后出现: 1.先选择1(按按磁道号增加的方向寻道): 接着输入磁道序列,若要结束输入,输入-1即可: 然后出现如下寻道结果: 2.再选择2(按按磁道号减少的方向寻道): 接着输入磁道序列,若要结束输入,输入-1即可: 然后出现如下寻道结果: 5.存在的问题: 由于初次做操作系统模拟实验,所以程序设计中存在很多问题,例如:由于电梯算法是从当前的磁道号开始沿着预定的方向寻道,当本方向上的请求全部满足时,再反向寻道,但是程序模拟过程中,进程不能随着寻道的同时添加新的进程,使得电梯调度算法不能更好的体现。只能预先输入一串请求,然后只对这一段请求寻道。 改进之处:添加更高级的算法,使得请求能在寻道的同时加进来。 还有一些简单的已解决的问题,不一一列举了。 6.实践心得体会: 通过这次实践学会了不少内容,更深的理解了磁道调度的几种算法,而且学 会了系统的编写程序。在编程过程中,需要 查阅各种资料,并且学习前人的 编写方法,找出优劣,然后形成自己的思想,最终完成程序的编写。 通过模拟磁盘调度的电梯调度算法,并比较与其他调度算法的不同,懂得了 各种算法在不同情况下的作用。选择一个好的调度算法可以节约很多时间。 在模拟过程中出现过好多问题,有的解决了,有的还未解决,不管如何都是 一种收获。 在最初的时候,由于程序编写隐藏的错误,编译没有发现,却执行不下 去,然后改正错误,修复漏洞,最终满足实验要求。 7.总结: 为期一周的操作系统实践课结束了,编写了电梯调度算法的磁盘调度模 拟程序。电梯调度寻道方式就像电梯运行一样,就是沿一个方向寻道,直到 满足这一方向的所有请求,便反向寻道。在程序中添加了寻道长度的显示,以便将电梯调度的效率与其他磁盘调度算法比较。 8.参考文献: 1.操作系统教程(第4版)„„„„孙钟秀 主编 高等教育出版社; 2.算法与数据结构-C语言描述(第2版)„„张乃孝 主编 高等教育出版社; 3.网络资源;第二篇:操作系统课程设计-磁盘调度算法
第三篇:操作系统课程设计,磁盘调度算法范文
第四篇:实验报告六 磁盘调度算法
第五篇:磁盘调度[推荐]