scan磁盘调度算法 操作系统课程设计报告_(3)

哈尔滨理工大学课程设计（计算机操作系统）题目SCAN磁盘调度算法学院计算机科学与技术学院班级姓名指导教师系主任2014年03月01日II目录1SCAN磁盘调度算法课程设计111题目分析112数据结构113流程图314实现技术315设计结论和心得316源代码32LINUX代码分析1221功能说明1422接口说明11423局部数据结构11424流程图1525以实例说明运行过程16哈尔滨理工大学课程设计报告01SCAN磁盘调度算法课程设计11题目分析本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。12数据结构SCAN磁盘调度算法问题中涉及的数据结构包括手动输入磁道的信号量、选择调度算法的信号量、SCAN调度算法的信号量、显示运行结果的信号量等。用伪代码表示如下INTSCANLINKLISTL,INTCURRENTLNODEP,Q,SFLOATSUM0IFLNEXTNULLPLNEXTWHILEPDATANEXT哈尔滨理工大学课程设计报告1PRINTF“扫描算法顺序是“FORQPQNULLQQNEXT/输出大于当前磁道号的数PRINTF“D“,QDATASUMABSCURRENTQDATACURRENTQDATAFORSPPRIORSNULLSSPRIOR/磁臂换向，自外向里移动，依次输出P指针之前的数据PRINTF“D“,SDATASUMABSCURRENTSDATACURRENTSDATAPRINTF“N“PRINTF“平均寻道长度为1FN“,SUM/I10RETURN0哈尔滨理工大学课程设计报告213流程图14实现技术为实现上述设计，采用C语言，VS2008开发环境。具体采用的技术如下（1）白盒测试技术白盒测试也称结构测试或逻辑驱动测试，它是按照程序内部的结构测试程序，通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行，检验程序中的每条通路是否都能按预定要求正确工作。这一方法是把测试对象看作一个打开的盒子，测试人员依据程序内部逻辑结构相关信息，设计或选择测试用例，对程序所有逻辑路径进行开始手动输入磁道选择调度算法SCAN算法显示运行结果结束哈尔滨理工大学课程设计报告3测试，通过在不同点检查程序的状态，确定实际的状态是否与预期的状态一致。（2）集成测试技术集成测试，也叫组装测试或联合测试。在单元测试的基础上，将所有模块按照设计要求（如根据结构图组装成为子系统或系统，进行集成测试。实践表明，一些模块虽然能够单独地工作，但并不能保证连接起来也能正常的工作。程序在某些局部反映不出来的问题，在全局上很可能暴露出来，影响功能的实现。实现步骤如下（1）开始界面（2）算法选择界面哈尔滨理工大学课程设计报告4（3）运行结果如下哈尔滨理工大学课程设计报告514设计结论和心得通过课程设计得到如下结论（1）扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。（2）此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。有如下几点心得体会（1）软件结构合理，自需求分析开始，采取自顶向下逐步求精的方法，将问题逐步分解为各个模块，各模块间通过指定类型参数进行数据传递，保证程序正确，结构清晰。（2）控制变量对比，各磁盘调度算法均可对同一组随机磁道进行调度，但并不会改变随机磁道的内容，保证了平均寻道长度对比的真实性，有效性。16源代码INCLUDEINCLUDEINCLUDEINCLUDETYPEDEFSTRUCTLNODE/双链表结点定义INTDATASTRUCTLNODENEXTSTRUCTLNODEPRIORLNODE,LINKLIST哈尔滨理工大学课程设计报告6INTI0LNODECREATLIST_LLINKLISTL/创建带头结点双链表，满足用户从键盘输入数字LNODEP,Q/定义尾结点Q，LLINKLISTMALLOCSIZEOFLNODE/为结点L动态分配内存，建立链表头结点LNEXTNULLINTTEMPPRINTF“N“PRINTF“请输入磁道数以0结束N“PRINTF“N“SCANF“D“,WHILETEMP0QLINKLISTMALLOCSIZEOFLNODEQDATATEMPIFLNEXTNULLLNEXTQQPRIORNULLELSE/采用尾插法将Q插入L尾部并使P指向QPNEXTQQPRIORPQNEXTNULLPQ哈尔滨理工大学课程设计报告7SCANF“D“,/IRETURNLINTSCANLINKLISTL,INTCURRENTLNODEP,Q,SFLOATSUM0IFLNEXTNULLPLNEXTWHILEPDATANEXTPRINTF“扫描算法顺序是“FORQPQNULLQQNEXT/输出大于当前磁道号的数PRINTF“D“,QDATASUMABSCURRENTQDATACURRENTQDATAFORSPPRIORSNULLSSPRIOR/磁臂换向，自外向里移动，依次输出P指针之前的数据PRINTF“D“,SDATASUMABSCURRENTSDATACURRENTSDATA哈尔滨理工大学课程设计报告8PRINTF“N“PRINTF“平均寻道长度为1FN“,SUM/I10RETURN0INTMAININTCURRENTLINKLISTLNULLLNODEPPRINTF“请输入当前的磁道号“SCANF“D“,PCREATLIST_LLINTTEMPPRINTF“N“PRINTF“1扫描算法SCANN“PRINTF“2退出N“PRINTF“N“PRINTF“请选择“SCANF“D“,WHILETEMP2SWITCHTEMP哈尔滨理工大学课程设计报告9CASE1SCANP,CURRENTBREAKPRINTF“退出函数，谢谢使用“RETURN0哈尔滨理工大学课程设计报告10哈尔滨理工大学课程设计报告112LINUX代码分析/复制进程的页目录页表。INTCOPY_PAGE_TABLESUNSIGNEDLONGFROM,UNSIGNEDLONGTO,LONGSIZEUNSIGNEDLONGFROM_PAGE_TABLEUNSIGNEDLONGTO_PAGE_TABLEUNSIGNEDLONGTHIS_PAGEUNSIGNEDLONGFROM_DIR,TO_DIRUNSIGNEDLONGNR/源地址和目的地址都需要是4MB的倍数。否则出错，死机。IFFROM/取得源地址和目的地址的目录项FROM_DIR和TO_DIR。FROM_DIRUNSIGNEDLONGFROM20/_PG_DIR0/TO_DIRUNSIGNEDLONGTO20/计算要复制的内存块占用的页表数（也即目录项数）。SIZEUNSIGNEDSIZE0X3FFFFF22/下面开始对每个占用的页表依次进行复制操作。FORSIZE0FROM_DIR,TO_DIR/如果目的目录项指定的页表已经存在P1，则出错，死机。IF1/如果此源目录项未被使用，则不用复制对应页表，跳过。IF1/取当前源目录项中页表的地址FROM_PAGE_TABLE。FROM_PAGE_TABLEUNSIGNEDLONG0XFFFFF000/为目的页表取一页空闲内存，如果返回是0则说明没有申请到空闲内存页面。返回值1，退出。IFTO_PAGE_TABLEUNSIGNEDLONGGET_FREE_PAGERETURN1/OUTOFMEMORY,SEEFREEING/哈尔滨理工大学课程设计报告12/设置目的目录项信息。7是标志信息，表示USR,R/W,PRESENT。TO_DIRUNSIGNEDLONGTO_PAGE_TABLE|7/针对当前处理的页表，设置需复制的页面数。如果是在内核空间，则仅需复制头160页，否则需要/复制1个页表中的所有1024页面。NRFROM00XA01024/对于当前页表，开始复制指定数目NR个内存页面。FORNR0FROM_PAGE_TABLE,TO_PAGE_TABLETHIS_PAGEFROM_PAGE_TABLE/取源页表项内容。IF1/复位页表项中R/W标志置0。如果U/S位是0，则R/W就没有作用。如果U/S是1，而R/W是0，/那么运行在用户层的代码就只能读页面。如果U/S和R/W都置位，则就有写的权限。THIS_PAGETO_PAGE_TABLETHIS_PAGE/将该页表项复制到目的页表中。/如果该页表项所指页面的地址在1M以上，则需要设置内存页面映射数组MEM_MAP，于是计算/页面号，并以它为索引在页面映射数组相应项中增加引用次数。IFTHIS_PAGELOW_MEMFROM_PAGE_TABLETHIS_PAGE/令源页表项也只读。THIS_PAGELOW_MEMTHIS_PAGE12MEM_MAPTHIS_PAGEINVALIDATE/刷新页变换高速缓冲。RETURN0哈尔滨理工大学课程设计报告1321功能说明复制进程的页目录页表22接口说明本程序的输入参数为UNSIGNEDLONGFROM,UNSIGNEDLONGTO,LONGSIZE输出结果为将进程的页目录页表复制23局部数据结构本程序共有5个局部变量及数据结构，其类型定义及语义如下UNSIGNEDLONGFROM_PAGE_TABLE/记录复制文件的位置UNSIGNEDLONGTO_PAGE_TABLE/目标文件位置UNSIGNEDLONGTHIS_PAGE/页目录UNSIGNEDLONGFROM_DIR,TO_DIR/页表UNSIGN