基于C语言的磁盘调度算法的实现.zip

# 磁盘调度算法的实现 **实验要求：** 1． 本实验是模拟操作系统的磁盘寻道方式，运用磁盘访问顺序的不同来设计磁盘的调度算法。 2． 实现的磁盘调度算法有 FCFS，SSTF，SCAN，CSCAN 和 NStepSCAN 算法。 3． 设定开始磁道号寻道范围，依据起始扫描磁道号和最大磁道号数，随机产生要进行寻道的磁道号序列。 4． 选择磁盘调度算法，显示该算法的磁道访问顺序，计算出移动的磁道总数和平均寻道总数。 5． 按算法的寻道效率进行排序，并对各算法的性能进行分析比较。 **实验任务：** 用 线性表 和 排序算法 模拟 磁道访问顺序 **步骤：** （1）先来先服务算法（FCFS）：根据进程请求访问磁盘的先后次序进行调度 最短寻道时间优先算法（SSTF）：要求访问的磁道与当前磁头所在的磁盘距离最近，以使每次的寻道时间最短 扫描算法（SCAN）：优先考虑的是磁头当前的移动方向，即自里向外移动，访问既在当前磁道之外，同时又是距离最近的磁道；直到再无更外的磁道需要访问时，才将磁臂换向自外向里移动。也称电梯调度算法 循环调度算法（CSCAN）：规定磁头单向移动，只是自里向外移动。当磁头移到最外的磁道并访问后，磁头立即返回到最里的需访问的磁道，即 ``` 将最小磁道号紧接着最大磁道号构成循环，进行循环扫描 ``` NStepSCAN 调度算法：将磁盘请求队列分成若干个长度为 N 的子队列，磁盘调度将按 FCFS 算法依次处理这些子队列。而每处理一个队列又是按 SCAN 算法，对一个队列处理完后，再处理其他队列 （2）设计测试数据： 以书本的数据为例：100#磁道开始，待访问 磁道 150,160,184,18,38,39,55,58,90 （3）按照每种调度方法逐步输出模拟磁盘分配的状态，进行查看 （4）调试完成后，依次随机产生多个需要访问的磁盘号后， 按照每种调度方法逐步输出模拟磁盘分配的状态，进行查看 （5）再次分析程序运行情况，并进行调试 **算法描述：** （1）随机产生多个需要访问的磁盘号 （2）依次按照 FCFS,SSTF,SCAN,CSCAN,NStepSCAN 显示分配状态， 同时计算出 平均寻道长度（Average Seek Time） （3）用冒泡排序，按照 平均寻道长度 从小到大（按效率高低）对每种算法进行排序 （4）显示每种算法关于 平均寻道长度 的排序结果  测试结果： 按照原先设计的数据进行测试的结果：    产生多个随机数后进行测试的结果：    附录（可包括源程序清单或其它说明） ```c++ # include <stdio.h> # include <stdlib.h> # include <string.h> # include <time.h> # include <math.h> # define TRACK_MAX 200 # define TRACK_NUM 9 int track_start //=100 ; int rand_track[TRACK_NUM] //={55,58,39,18,90,160,150,38,184} ; # define NStepSCAN_N 5 //假定NStep_SCAN算法的步长为5 int a[TRACK_NUM]; void init() //随机产生多个磁道号 { int i; printf("输入磁道开始位置:\n"); scanf("%d",&track_start); printf("\n"); srand((int)time(0)); //设置随机数种子 for(i=0; i<TRACK_NUM; i++) rand_track[i]=rand()%TRACK_MAX; /* */ printf("随机产生的需要访问的磁道号为:\n"); for(i=0; i<TRACK_NUM; i++)printf(" %d",rand_track[i]); printf("\n"); } void sort(int a[]) //冒泡排序，从小到大 { int i,j,temp; for(i=0; i<TRACK_NUM; i++) { for(j=i+1; j<TRACK_NUM; j++) if(a[i] > a[j]) { temp=a[i]; a[i]=a[j]; a[j]=temp; } } } void show(int a[]) { int i; for(i=0; i<TRACK_NUM; i++)printf(" %d",a[i]); printf("\n"); } float FCFS(int rand_track[]) //先来先服务 { int i; int head_track=track_start; int total_move=0,move[TRACK_NUM]; float avg_track_seeking_len; printf("\nFCFS算法\n"); printf("--------------------------------------------------------\n"); printf("从%d号磁道开始\n",track_start); //值传递 for(i=0; i<TRACK_NUM; i++)a[i]=rand_track[i]; //show(a); for (i=0; i<TRACK_NUM; i++) { move[i]=abs(head_track-a[i]); head_track=a[i]; //移动磁头 total_move += move[i]; printf("访问磁道号:%3d 移动距离:%3d\n",a[i],move[i]); } printf("移动磁道总数： %d\n", total_move); avg_track_seeking_len=float(total_move) / TRACK_NUM; printf("平均寻道长度: %3.2f\n", avg_track_seeking_len); return avg_track_seeking_len; } float SSTF(int rand_track[]) //最短寻道时间优先 { int i,j,min,j_key,temp; int head_track=track_start; int total_move=0,move[TRACK_NUM]; float avg_track_seeking_len; printf("\nSSTF算法\n"); printf("--------------------------------------------------------\n"); printf("从%d号磁道开始\n",track_start); //值传递 for(i=0; i<TRACK_NUM; i++)a[i]=rand_track[i]; //show(a); for (i=0; i<TRACK_NUM; i++) { min=abs(a[i]-head_track); j_key=i; for(j=i+1; j<TRACK_NUM; j++) { if(abs(a[j]-head_track)<min) { min=abs(a[j]-head_track); j_key=j; } } temp=a[i]; a[i]=a[j_key]; a[j_key]=temp; move[i]=min; head_track=a[i]; //移动磁头 total_move += move[i]; printf("访问磁道号:%3d 移动距离:%3d\n",a[i],move[i]); } printf("移动磁道总数：%d\n", total_move); avg_track_seeking_len=float(total_move) / TRACK_NUM; printf("平均寻道长度: %3.2f\n", avg_track_seeking_len); return avg_track_seeking_len; } float SCAN(int rand_track[]) //扫描 { int i,min,i_key; int head_track=track_start; int total_move=0,move[TRACK_NUM]; float avg_track_seeking_len; printf("\nSCAN算法\n"); printf("--------------------------------------------------------\n"); printf("从%d号磁道开始\n",track_start); //值传递 for(i=0; i<TRACK_NUM; i++)a[i]=rand_track[i]; //show(a); sort(a); //show(a); i_key=-1; for(i=0; i<=TRACK_NUM; i++)if(i==TRACK_NUM || a[i]>head_track) { i_key=i; break; } for (i=i_key; i<TRACK_NUM; i++) { min=abs(a[i]-head_track); move[i]=min; head_track=a[i]; //移动磁头 total_move += move[i]; printf("访问磁道号:%3d 移动距离:%3d\n",a[i],move[i]); } for (i=i_key-1; i>=0; i--) { min=abs(a[i]-head_track); move[i]=min; head_track=a[i]; //移动磁头 total_move += move[i]; printf("访问磁道号:%3d 移动距离:%3d\n",a[i],move[i]); } printf("移动磁道总数：%d\n", total_move); avg_track_seeking_len=float(total_move) / TRACK_NUM; printf("平均寻道长度: %3.2f\n", avg_t