操作系统实验磁盘调度扫描算法循环扫描算法之欧阳地创编

1、学号P1514032专业计算机科学与技术姓名时间：2021.03. 04创作：欧阳地实验日期2017. 12. 7教师签字成绩实验报告【实验名称】磁盘调度（二）【实验目的】磁盘调度中寻道时间直接影响到数据访问的快慢，处 理好磁盘寻道时间是关键。分别采用扫描竟略、循环扫描 策略处理。【实验原理】1.扫描算法（SCAN算法）SCAN算法，也就是很形象的电梯调度算法。先按照 一个方向（比如从外向内扫描）,扫描的过程中依次调度 经过的磁道。当扫描到最里层的一个磁道时反向扫描直 至所有磁道都被调度。2.循环扫描算法(CSCAN算法)CSCAN算法，循环扫描算法，它的思想是，访问完最里面一个要求服务的序列

2、之后，从最外层的序号开始往里走。也就是始终保持一个方向，故称为循环扫描算法。【数据结构和符号说明】(1)数据结构和符号说明编译语言：C+数据结构：结构体数组符号定义：typedefstruct Track/磁道结构体int id;/磁道序列int state二0;/是否访问过，未被访问置状态为0 Track;Track trackN ;/最大磁道数为 100Track trackl N ;/复制的磁道数组用于输出int stepN ;/移动距离int num, i, current_track, num1;/当前磁道即部分中间变量函数说明：vo i d i n i t () /初始化程序voi

3、d input () /输入函数void sortl ()/从小到大排序int abs (inta, i nt b)/相减的绝对值i ntf i nd_f i rst_b i gnum () /寻找第一个最大值i ntf i nd_f i rst_sma I I num () /寻找第一个最小值vo i d SCAN (i ntup_or_down) /扫描算法vo i d CSCAN (i ntup_or_down) /循环扫描算法vo i d output (Track a ) /输出函数vo i d output_average_track ()/输出平均寻道时间int show()/显

4、示用户界面/返回值为输入的选择 项流程图：SCAN算法：CSCAN算法(与SCAN算法基本类似)：代码：#include#define N 100typedefstruet Trackint id;/磁道序列int stateO;/是否访问过，未被访问置状态为0 Track;Track trackN ;/最大磁道数为 100Track trackl N;int stepN;/移动距离int num, i,currenrack, num1;vo i d i n i t () /初始化程序num二0;for (i=0; inum; i +)tracki. state=-1 ;/id 置为 1 tr

5、ackli.state二-1;step订二T;/移动距离为-1void input ()/输入函数pr i ntf (输入当前磁道n);scanf(%dH，¤rack);numlcurrenrack;printfC*输入要访问的磁道数目n“);scanf(%d,&num);pr intf (输入要访问磁道序列n);for (i=0; inum; i+)scanf(u%d,&tracki, id);void FCFS()/先来先服务for (i=0; inum; i+)i f (cur rent_t rack-track i . id) O?ab:ba;intSerch_min_po

6、s ()/寻找到当前磁道最短的需求磁道int min=45536;/最小距离标志i ntpos;for (i 卍二0; iabs(tracki. id, current_track) / 寻找最 小 距离min=abs 仕racki. id, current_track);pos二i;track pos.state=1;return pos;/返回在数组中的位置void SSTF()/最短寻道优先for (i=0; in,num1);pr i ntf (“ = 二二二二二二=二门“)；排班printf(H被访问的下一个磁道tt移动距离(磁道数)nn);for (i=0; inum; i+)pr

7、 intf (t%4dtt|t%4dn, ai. id,stepi);pr i ntf (“ =n“);void output_average_track ()/输出平均寻道时间doubIe sum二0;/和for (i=0; inum; i+)sum+=stepi;pr i ntf (平均寻道长度3 2fnnn, sum/num) ;/输出int show() /显示用户界面 int choose;/选择pr intf (n* 早期 的磁盘 调度算 法4 丄4 丄 II pr i ntf (nttk 先来先服务(FCFS)nH);printf(ntt2.最短寻道时间优先(SSTF)nf,);

8、printf (Htt3.退出(EXIT) nn);seanf (”口 &choose);return choose;i nt ma i n () do i n i t ();sw i tch (show () /返回值是选择case 1:/FCFS input ();FCFS ();output (track);output_averagerack(); break;case 2:/最短寻道input ();SSTF ();output (trackl);output_average_track(); break;case 3:/退出return 0;defauIt:break;wh i l

9、e(1);return 0;截图：主界面开始，输入选择先来先服务还是最短寻道优先，输 入当前磁道，输入要访问的磁道，输入要访问的磁道序列。SCAN算法输入当前磁道100,9个磁道，分别为55 58 39 18 90 160150 38 184,此时选择方向向上结果正确。输入当前磁道100,9个磁道，分别为55 58 39 18 90 160150 38 184,此时选择方向向下结果正确。CSCAN算法输入当前磁道100,9个磁道，分别为55 58 39 18 90 160150 38 184,此时选择方向向上结果正确。输入当前磁道100,9个磁道，分别为55 58 39 18 90 16015

10、0 38 184,此时选择方向向上结果正确。【小结与讨论】1、扫描算法又称为电梯算法，其原理与电梯运行情况相 似，即运行方向上的请求优先，若是访问方向向上，则先 依次访问较大的磁道号至顶，再向下访问娇小的磁道号； 若是访问方向向下，则先依次访问较小的磁道号至底，再 向上访问娇大的磁道号。2、循环扫描算法又称为单向电梯算法，若是访问方向向 上，则向上依次访问完较大的磁道号后，返回最低端，依 次向上访问较小的磁道号；若是访问方向向下，则向下依 次访问完较小的磁道号后，返回最顶端，依次向下访问较 大的磁道号。3、此次实验我用两个数组分别存放了一个磁道表和复制 的磁道表，根据两个算法的原理，只要将其进行排序，然 后分别对两个数组进行正向和逆向的访问即可。4、具体实现时，我将两种算法的两种初始扫描方向写在 了 一个函数之中，调用时通过参数scan和参数up_or_down 设置。并设置了寻找大于当前数组的最近最小值和最近的 大值进行选择结果，这是因为初始磁道号将磁道数组分成 上下（高低地址）两块，这两块根据不同的扫描方向重新 选择高低地址，又结合不同的算法决定正序排列还是反序 排列。实现起来还是比较简