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

学号P15402 专业 计算机科学与技术 姓名 实验日期20、12、7 教师签字 成绩实验报告【实验名称】 磁盘调度（二) 【实验目得】 磁盘调度中寻道时间直接影响到数据访问得快慢，处理好磁盘寻道时间就是关键。分别采用扫描策略、循环扫描策略处理.【实验原理】1、 扫描算法（AN算法)CN算法，也就就是很形象得电梯调度算法。先按照一个方向(比如从外向内扫描）,扫描得过程中依次调度经过得磁道。当扫描到最里层得一个磁道时反向扫描直至所有磁道都被调度.2、循环扫描算法（SCA算法)CSCA算法,循环扫描算法,它得思想就是,访问完最里面一个要求服务得序列之后,从最外层得序号开始往里走。也就就是始终保持一个方向，故称为循环扫描算法。【数据结构与符号说明】（1） 数据结构与符号说明编译语言:+数据结构:结构体数组符号定义: ypf tuctTr/磁道结构体 i id；/磁道序列 int state=0；/就是否访问过，未被访问置状态为 rack;TracracN；/最大磁道数为100Trak track1;/复制得磁道数组用于输出n stpN；/移动距离it num，i，curent_tack，num； /当前磁道即部分中间变量函数说明：voi init（）/初始化程序vd input（)/输入函数voi st()/从小到大排序n as（inta,int b）/相减得绝对值int find_firt_bignum（)/寻找第一个最大值n find_first_mallnu（）/寻找第一个最小值void SCA（intupr_down) /扫描算法vod CSCAN（int up_or_don） /循环扫描算法voitu（racka)/输出函数v ututavere_trak()/输出平均寻道时间int sow（)/显示用户界面返回值为输入得选择项流程图：SCAN算法:CCA算法(与CAN算法基本类似）：代码:#ncuestio、hdfn N 100typeef struct rack int i;磁道序列 nt sate=0；/就是否访问过，未被访问置状态为 Trac；Trak tack;/最大磁道数为100Tracktk1；it steN；/移动距离it n,，urrent_rack,um1；voidit（）/初始化程序 um0; for （=0; inm;i+） traci、stat1；/d置为 track、tate=1; stei=;/移动距离为1 vo input（)/输入函数 printf(输入当前磁道n); sanf（d，curret_trac）； nu=crren_rck； prt（”输入要访问得磁道数目n”）; caf（”d，&num）; prnf（输入要访问磁道序列）； or(i=0； nm； i+） snf(”%d,&traci、id);oidFCFS()/先来先服务 or(i=； inum；i+） f（(urrenttrck-traki、id）/求移动距离 stepitacki、-curt_rack； else steicuen_tractaki、id；/取绝对值 tacki、stat=1;/状态置为 current_track=tri、id；/更新当前磁道 in abs(nt a，int b)/相减得绝对值 eturn ab?ab：;n Srch_min_pos(）/寻找到当前磁道最短得需求磁道 itmin=4536；/最小距离标志 pos； or(in i=0； ab（tracki、id，cen_trk)/寻找最小距离 min=abs（trk、i,current_tack）； poi； tracpo、sae=； rturn pos；/返回在数组中得位置voiSF()/最短寻道优先 fr（i;inu； i+）/计数器 racki=trackec_in_ps（）；/更新到要输出得数组中 tei=abs（tracki、d，currenttrck）；/移动距离 urttrack= rack1i、id;/标志 void outpt（Trc a）/输出函数 print(nn 从d号磁道开始n，m）; rintf（=）；/排班 rintf（”被访问得下一个磁道tt移动距离（磁道数）n); for（i=; ium； i+） pritf(”t4dttdn,ai、i,stei）； prntf（=）；void otputveagerack()/输出平均寻道时间 dbe um=0；/与 for（i；num； i) sum+=te； prntf( 平均寻道长度3、2fn，sm/num）;/输出int ho（)/显示用户界面 i coe；/选择 printf（”*早期得磁盘调度算法*n”)； printf(tt1、先来先服务（FC)n）； pit（tt、最短寻道时间优先(SSTF)n)； prin（tt、退出(EXT)n）; scan（%”，&hoose); retn cose；intmain（） do ii（）； switch(ow（）返回值就是选择 ce :/FFS input()； FS（）; outu（tack)； outpu_vergetack（）; break; case 2：/最短寻道 input（）; SF(）; u(tack1）; otput_avrag_rac（); break; cae 3：退出 return 0; default： brek； whl(1）; etun 0；截图：主界面开始，输入选择先来先服务还就是最短寻道优先,输入当前磁道，输入要访问得磁道,输入要访问得磁道序列。SAN算法输入 当前磁道100,9个磁道,分别为5558 3918 0160 150 14,此时选择方向向上结果正确。输入 当前磁道0 ,个磁道，分别为5 898 9 160 15 388,此时选择方向向下结果正确.CSCN算法输入当前磁道100 ，9个磁道，分别为55 3 8 90 1601508 14，此时选择方向向上结果正确. 输入 当前磁道100 ,9个磁道,分别为55 589 18 90 10150 38 ，此时选择方向向上结果正确。【小结与讨论】、扫描算法又称为电梯算法，其原理与电梯运行情况相似，即运行方向上得请求优先，若就是访问方向向上，则先依次访问较大得磁道号至顶,再向下访问娇小得磁道号;若就是访问方向向下，则先依次访问较小得磁道号至底,再向上访问娇大得磁道号。2、循环扫描算法又称为单向电梯算法,若就是访问方向向上,则向上依次访问完较大得磁道号后,返回最低端,依次向上访问较小得磁道号；若就是访问方向向下，则向下依次访问完较小得磁道号后，返回最顶端,依次向下访问较大得磁道号.3、此次实验我用两个数组分别存放了一个磁道表与复制得磁道表，根据两个算法得原理，只要将其进行排序,然后分别对两个数组进行正向与逆向得访问即可。、具体实现时,我将两种算法得两种初始扫描方向写在了一个函数之中，调用时通过参数can与参数up_or_own设置.并设置了寻找大于当前数组得最近最小值与最近得大值进行选择结果,这就是因为初始磁道号将磁道数组分成上下（高低地址）两块，这两块根据不同得扫描方向重新选择高低地址，又结合不同得算法决定正序排列还就是反序排列。实现起来还就是比较简单得。5、由于CSCA算法得思想就是,访问完最里面一个要求服务得序列之后，从最外层得序号开始往里走。也就就是始终保持一个方向.所以如果用循环队列实现,时间复杂度会更低,效率更高。6、此次实验虽然较为简单,但还就是发现了自己知识点有些方面得不足，让我更好得了解了磁盘调度得原理，使我收获颇多.