操作系统实验页面置换算法先来先服务最短寻道优先

1、学号 P71514032 专业 计算机科学与技术姓名实验日期 2017/12/7教师签字 成绩【实验名称】磁盘调度一一先来先服务策略 最短寻道策略【实验目的】磁盘调度中寻道时间直接影响到数据访问的快慢，通过本次实验学习如何处理好磁盘寻道时间。【实验原理】1. 先来先服务算法先来先服务算法根据进程请求访问磁盘的先后次序进行调度。2. 最短寻道时间优先算法最短寻道时间优先算法要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。【数据结构和符号说明】ypedef struct Trackint id;/ 磁道序列int state=0;/ 是否访问过，未被访问置状态为 0 Track

2、;Track trackN;/ 最大磁道数为 100Track track1N;int stepN;/ 移动距离int num,i,current_track,num1;/ 需要访问的次数 函数说明：void init()/ 初始化程序void input()/ 输入函数void FCFS()/ 先来先服务int abs(int a,int b)/ 相减的绝对值int Serch_min_pos()/ 寻找到当前磁道最短的需求磁道void SSTF()/ 最短寻道优先void output(Track a)/ 输出函数void output_average_track()/ 输出平均寻道时间i

3、nt show()/ 显示用户界面 先来先服务( FCFS)寻找当前磁道最近需求磁道代码：#include<stdio.h>#define N 100 typedef struct Trackint id;/ 磁道序列int state=0;/ 是否访问过，未被访问置状态为 0 Track;Track trackN;/ 最大磁道数为 100Track track1N;int stepN;/ 移动距离int num,i,current_track,num1;void init()/ 初始化程序num=0;for (i=0; i<num; i+)tracki.state=-1;/

4、id 置为 1 track1i.state=-1;stepi=-1;/ 移动距离为 -1void input()/ 输入函数printf(" 输入当前磁道 n"); scanf("%d",&current_track);num1=current_track;printf(" 输入要访问的磁道数目 n"); scanf("%d",&num);printf(" 输入要访问磁道序列 n");for(i=0; i<num; i+) scanf("%d",&

5、;tracki.id);void FCFS()/ 先来先服务for(i=0; i<num; i+)if(current_track-tracki.id)<0)/ 求移动距离 stepi=tracki.id-current_track;elsestepi=current_track-tracki.id;/ 取绝对值tracki.state=1;/ 状态置为 1 current_track=tracki.id;/ 更新当前磁道int abs(int a,int b)/ 相减的绝对值return a-b>0?a-b:b-a;int Serch_min_pos()/ 寻找到当前磁道最

6、短的需求磁道int min=45536;/ 最小距离标志int pos;for(int i=0; i<num; i+)if(tracki.state=1)寻找最小距离continue;else if(min>abs(tracki.id,current_track)/min=abs(tracki.id,current_track);pos=i;trackpos.state=1;return pos;/ 返回在数组中的位置void SSTF()/ 最短寻道优先for(i=0; i<num; i+)/ 计数器track1i=trackSerch_min_pos();/ 更新到要输出

7、的数组中 stepi=abs(track1i.id,current_track);/ 移动距离 current_track= track1i.id;/ 标志void output(Track a)/ 输出函数printf("nn<从d 号磁道开始 >n",numl);printf("=n");/ 排班printf(" 被访问的下一个磁道 tt 移动距离(磁道数) n");for(i=0; i<num; i+)printf("t%4dtt|t%4dn",ai.id,stepi);printf(&qu

8、ot;=n");void output_average_track()/ 输出平均寻道时间double sum=0;/ 和for(i=0; i<num; i+)输出sum+=stepi;printf(" 平均寻道长度 %3.2fnnn",sum/num);/int show()/ 显示用户界面int choose;/ 选择printf("n*早期的磁盘调度算法printf("tt1 、先来先服务 (FCFS)n");printf("tt2 、最短寻道时间优先( SSTF)n");printf("tt

9、3 、退出( EXIT)n");scanf("%d",&choose);return choose;int main()doinit();switch(show()/ 返回值是选择case 1:/FCFSinput();FCFS(); output(track); output_average_track(); break;case 2:/ 最短寻道input();SSTF();output(track1);output_average_track();break;case 3:/ 退出return 0;default:break;while(1);ret

10、urn 0;截图：主界面开始，输入选择先来先服务还是最短寻道优先，输入当前磁道，输入要访问的磁道， 输入要访问的磁道序列。先来先服务 (FCFS)最短寻道优先（SSTF）【小结与讨论】1、先来先服务算法是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是较为公平与简单，并且每个进程的请求都 能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长；而最短寻道时间优先算法要 求每次访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短， 但这种调度算法却不能保证平均寻道时间最短，因为只能做到局部最优。2、本实验用数组就可以很方便简洁地解决问题，唯一需要注意的就是在算法中，每一次寻道需要对之前的磁道号进行暂存设置一个current_track（当前磁道），如果已查询到，需将状态置为1，这样才方便寻找和计算寻道距离。3、FCFS算法根据磁道号需要被访问的顺序依次访问磁道，所以磁道被访问 顺序在磁道需要顺序确定时，即被确定，然后用依次减法即可算出移动距离， 相 对来说实验的复杂度较低，易于实现。4、SSTF算法则相较于FCFS算法复