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

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

2、Track;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()/输出平均寻道时间int show(

3、)/显示用户界面先来先服务（FCFS）最短寻道时间优先（SSTF）代码：#include<stdio.h>#define N 100typedef struct Track int 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;/id置为1 track1

4、i.state=-1; stepi=-1;/移动距离为-1 void 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",&tracki.id);void

5、 FCFS()/先来先服务 for(i=0; i<num; i+) if(current_track-tracki.id)<0)/求移动距离 stepi=tracki.id-current_track; else stepi=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()/寻找到当前磁道最短的需求磁道 int min=45

6、536;/最小距离标志 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();/更新到要输出的数组中 stepi

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

8、);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*早期的磁盘调度算法*n"); printf("tt1、先来先服务(FCFS)n"); printf("tt2、最短寻道时间优先（SSTF)n"); printf("tt3

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

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