操作系统实验磁盘调度扫描算法循环扫描算法

1、学号 P1514032 专业计算机科学与技术姓名实验日期 教师签字 成绩实验名称】磁盘调度（二）【实验目的】磁盘调度中寻道时间直接影响到数据访问的快慢，处理好磁盘寻道时间是关键。分别 米用扫描策略、循环扫描策略处理。【实验原理】1. 扫描算法（SCAh算法）SCAN算法，也就是很形象的电梯调度算法。先按照一个方向（比如从外向内扫描）, 扫描的过程中依次调度经过的磁道。当扫描到最里层的一个磁道时反向扫描直至所有磁 道都被调度。2. 循环扫描算法（CSCAI算法）CSCAN算法，循环扫描算法，它的思想是，访问完最里面一个要求服务的序列之后， 从最外层的序号开始往里走。也就是始终保持一个方向，故称为

2、循环扫描算法。【数据结构和符号说明】（1）数据结构和符号说明编译语言： C+数据结构：结构体数组符号定义：typedef struct Track/ 磁道结构体int id;/磁道序列int state=0;/是否访问过，未被访问置状态为 0 Track;Track trackN;/最大磁道数为 100Track track1N;/复制的磁道数组用于输出int stepN;/ 移动距离int num,i,current_track,num1; / 当前磁道即部分中间变量 函数说明：void init()/ 初始化程序void input()/ 输入函数void sort1()/ 从小到大排序i

3、nt abs(int a,int b)/相减的绝对值int find_first_bignum()/ 寻找第一个最大值int find_first_smallnum()/ 寻找第一个最小值void SCAN(int up_or_down) / 扫描算法void CSCAN(int up_or_down) / 循环扫描算法void output(Track a)/ 输出函数void output_average_track()/ 输出平均寻道时间int show()/ 显示用户界面 / 返回值为输入的选择项 流程图：SCAN算 法：CSCAI算法(与SCAN算法基本类似)：代码：#include

4、<stdio.h>#define N 100typedef 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;/id 置为 1track1i.state=-1;stepi=-1;/ 移动距离为 -1void input(

5、)/ 输入函数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 FCFS()/ 先来先服务for(i=0; i<num; i+)求移动距离取

6、绝对值if(current_track-tracki.id)<0)/stepi=tracki.id-current_track;elsestepi=current_track-tracki.id;/current_track=tracki.id;/ 更新当前磁道int abs(int a,int b)/ 相减的绝对值return a-b>0?a-b:b-a;int Serch_min_pos()/ 寻找到当前磁道最短的需求磁道int min=45536;/ 最小距离标志int pos;for(int i=0; i<num; i+)if(tracki.state=1)寻找最小距

7、离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=abs(track1i.id,current_track);/ 移动距离 current_track= track1i.id;/ 标志printf(

8、"nn<从4号磁道开始 >n",numl);printf("=n");/ 排班printf(" 被访问的下一个磁道 tt 移动距离(磁道数) n");for(i=0; i<num; i+)printf("t%4dtt|t%4dn",ai.id,stepi);printf("=n"); void output_average_track()/ 输出平均寻道时间double sum=0;/ 和for(i=0; i<num; i+)printf("sum+=stepi

9、;平均寻道长度 %3.2fnnn",sum/num);/ 输出int show()/ 显示用户界面int choose;/ 选择printf("n*早期的磁盘调度算法*n");printf("tt1 、先来先服务 (FCFS)n");printf("tt2、最短寻道时间优先( SSTF)n");printf("tt3、退出( EXIT) n");scanf("%d",&choose);return choose;int main()doinit();case 1:/FCFSin

10、put();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);return 0;截图：主界面开始，输入选择先来先服务还是最短寻道优先， 输入当前磁道， 输入要访问的磁道， 输入要访问的磁道序列。SCAN算法输入 当前磁道 100 ,9 个磁道，分别为 55 58 39 18 90 160 150 38 184 ，此时选

11、择方 向向上结果正确。输入 当前磁道 100 ,9 个磁道，分别为 55 58 39 18 90 160 150 38 184 ，此时选择方 向向下结果正确。CSCAI算法输入 当前磁道 100 ,9 个磁道，分别为 55 58 39 18 90 160 150 38 184 ，此时选择方 向向上结果正确。输入 当前磁道 100 ,9 个磁道，分别为 55 58 39 18 90 160 150 38 184 ，此时选择方 向向上结果正确。【小结与讨论】1、扫描算法又称为电梯算法，其原理与电梯运行情况相似，即运行方向上的请求优先，若 是访问方向向上，则先依次访问较大的磁道号至顶，再向下访问娇小

12、的磁道号；若是访问 方向向下，则先依次访问较小的磁道号至底，再向上访问娇大的磁道号。2、循环扫描算法又称为单向电梯算法，若是访问方向向上，则向上依次访问完较大的磁道 号后，返回最低端，依次向上访问较小的磁道号；若是访问方向向下，则向下依次访问完 较小的磁道号后，返回最顶端，依次向下访问较大的磁道号。3、此次实验我用两个数组分别存放了一个磁道表和复制的磁道表，根据两个算法的原理， 只要将其进行排序，然后分别对两个数组进行正向和逆向的访问即可。4、具体实现时，我将两种算法的两种初始扫描方向写在了一个函数之中，调用时通过参数 scan 和参数 up_or_down 设置。并设置了寻找大于当前数组的最近最小值和最近的大值进 行选择结果，这是因为初始磁道号将磁道数组分成上下（高低地址）两块，这两块根据