操作系统课程设计报告-磁盘调度算法

华南农业大学数学与信息学院（软件学院）《操作系统分析与设计实习》成绩单开设时间：2015学年第一学期小组成员、组内分工及各成员成绩学号姓名专业班级成绩题目题目二磁盘调度算法的模拟实现及对比自我评价这次的操作系统课程设计，让我对操作系统磁盘调度策略有了更加深刻的认识，自己动手操作比光看书能更能深刻了解磁盘调度的策略和原理，同时对磁盘调度的四种算法——先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、SCAN算法，C-SCAN算法有了更深刻的理解和掌握。设计过程中遇到的困难在老师和同学的帮助下顺利解决，我深刻认识到算法的逻辑性和时间复杂度对程序的重要影响，算法的准确度对程序运行结果的重要影响，这对我以后在操作系统的学习中有极大帮助。也增强了我写代码的能力，尤其是对自顶向下的结构化分析设计方法有了更深刻的理解和掌握。由于这次的课程设计是单人做的，所以也增强了独立做程序的能力。不过，通过这次课程设计，我也了解到自己有很多不足，比如在设计界面方面明显经验不足，以至于界面的简陋，代码也不够工整明了。总的来说，这次课程设计不仅提升了自己的知识和能力，还让自己知道了自己的许多不足之处。教师评语评价指标：题目内容和要求完成情况优□良□中□差□对算法原理的理解程度优□良□中□差□程序设计水平优□良□中□差□程序运行效果及正确性优□良□中□差□课程设计报告结构清晰优□良□中□差□报告中总结和分析详尽优□良□中□差□教师签名张丽霞一、需求分析(1)输入的形式和输入值的范围：在文本框输入序列长度，输入值为int类型(2)输出的形式：输出每种磁盘调度算法的服务序列；输出每种算法的平均寻道长度。(3)程序所能达到的功能：模拟实现FCFS、SSTF、SCAN、C-SCAN算法，并计算及比较磁头移动道数。（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果：输入初始磁头位置0~1500输入磁臂扫描方向0或1选择算法1~4二、概要设计1）主程序流程图：输出随机生成400个磁道号序列主菜单选择算法开始FCFSSSTFSCANC-SCAN结束（2）各程序模块之间的调用关系磁头初始位置输入及合法性检查冒泡排序算法由外向内输出磁道序列由内向外输出磁道序列由当前位置向内再向外输出磁道序列由当前位置向外再向内输出磁道序列由当前位置向内再由外向内输出磁道序列由当前位置向外再由内向外输出磁道序列就近选择主函数FCFSSSFTSCANC-SCAN三、详细设计1）各操作伪码算法（1）实现磁头初始位置的输入并进行合法性检查intprintstarter()//磁头初始位置输入{输入：磁头初始位置;if输入小于0或大于1500{输出：输入数据类型有误，请重新输入！endl;重新输入}Else返回合法的磁头初始位置}（2）冒泡排序算法int*bubble//冒泡排序算法{for从数组的第一个元素开始重复{依次和后续元素表较大小；If后面元素大于当前元素交换数值；}输出排序后的数组；返回数组；}（3）intout_to_in//由磁道最外向内输出磁道序列{for从最外磁道开始{依次输出磁道号;当前磁道号与磁头初始未至的绝对值求和；磁头初始位置=当前磁道号；}返回绝对值之和；}（4）intin_to_out//由磁道最内向外输出磁道序列{for从最内磁道开始{依次输出磁道号;当前磁道号与磁头初始未至的绝对值求和；磁头初始位置=当前磁道号；}返回绝对值之和；}（5）intout_to_in_to_out//先由当前位置向内再向外{找到小于等于磁头初始位置的磁道for由该磁道开始{向内依次输出磁道号；当前磁道号与磁头初始未至的绝对值求和；}for由该磁道的外侧磁道开始{向外依次输出磁道号；当前磁道号与磁头初始未至的绝对值求和；}返回绝对值之和；}（6）intin_to_out_to_in//先由当前位置向外再向内{找到大于等于磁头初始位置的磁道for由该磁道开始{向外依次输出磁道号；当前磁道号与磁头初始未至的绝对值求和；}for由该磁道的内侧磁道开始{向内依次输出磁道号；当前磁道号与磁头初始未至的绝对值求和；}返回绝对值之和；}（7）intout_to_in_twice由当前磁道向内再从最外向内{找到小于等于磁头初始位置的磁道；for由该磁道开始{向内依次输出磁道号；当前磁道号与磁头初始未至的绝对值求和；}for由最外侧磁道开始{向内依次输出磁道号直到小于等于初始位置的磁道的外侧一个磁道；当前磁道号与磁头初始未至的绝对值求和；}返回绝对值之和；}（8）intin_to_out_twice由当前磁道向外再从最内向外{找到大于等于磁头初始位置的磁道for由该磁道开始{向内依次输出磁道号；当前磁道号与磁头初始未至的绝对值求和；}for由最内侧磁道开始{向外依次输出磁道号直到小于等于初始位置的磁道的内侧一个磁道；当前磁道号与磁头初始未至的绝对值求和；}返回绝对值之和；}（9）intnearest_select就近选择{找到大于磁头初始位置的磁道；while初始位置内侧差绝对值更小{输出内侧磁道号;绝对值差求和；初始位置更新为当前磁道号；}while初始位置外侧绝对值差更小{输出外侧磁道号；绝对值差求和；初始位置更新为当前磁道号；}}If已到达最内侧未到达最外侧{if内侧绝对值差更小{输出最内侧磁道号；绝对差值求和；初始位置更新；while向外侧依次输出磁道号直到到达最外侧{绝对差值求和；更新初始位置；}}else外侧绝对值差更小{While向外侧依次输出磁道号直到到达最外侧{绝对差值求和；更新初始位置；}输出最内侧磁道号；绝对差值求和；更新初始位置；}}if已到达最外侧未到达最内侧{If外侧绝对值更小{输出最外侧磁道号；绝对差值求和；更新初始位置；while向内依次输出磁道号{绝对差值求和；更新初始位置；}}else{while向内依次输出磁道号{绝对差值求和；更新初始位置；}输出最外侧磁道号；绝对值差求和；更新初始位置；}}if均到达最内侧和最外侧{if外侧差绝对值更小{输出最外侧磁道号并绝对值差求和；输出最内侧磁道号并绝对值差求和；}else{输出最内侧磁道号并绝对值差求和；输出最外侧磁道号并绝对值差求和；}}求总和并返回；}（10）voidFCFS算法{输出磁盘请求序列为；按照磁盘请求序列依次输出磁盘扫描序列；当前磁道号与磁头初始未至的绝对值求和；求平均值；输出平均寻道长度；}（11）voidSSTF算法{if序列中最大的磁道号小于磁头初始位置{调用out_to_in直接由外向内;}if序列中最小的磁道号大于磁头初始位置{调用in_to_out直接由内向外;}If磁头初始位置为中间值{调用就近选择算法；}求均值；输出平均寻道时间；}（12）voidSCAN算法{输入：磁臂移动方向（1：向外，0：向内）;if序列中最大的磁道号小于磁头初始位置{调用out_to_in直接由外向内；}if序列中最小的磁道号大于磁头初始位置{调用in_to_out直接由内向外；}if初始磁头位置为中间值{if磁臂方向向内{调用out_to_in_to_out；}if磁臂方向向外{调用n_to_out_to_in；}}求均值；输出平均寻道时间；}（13）ViodC-SCAN算法{请输入磁臂移动方向（1：向外，0：向内）；if序列中最大磁道号小于等于磁头初始位置{if磁臂方向向内{调用out_to_in;}if磁臂方向向外{调用in_to_out;}}if序列中最大磁道号大于等于磁头初始位置{if磁臂方向向内{调用out_to_in;}if磁臂方向向外{调用in_to_out;}}if初始磁头位置为中间值{if(磁臂方向向内{调用out_to_in_twice;}if磁臂方向向外{调用in_to_out_twice);}}求均值；输出平均寻道时间；}（14）主函数intmain(){随机生成200个0~499的磁道序列并输出；随机生成100个500~999的磁道序列并输出；随机生成100个1000~1500的磁道序列并输出；输出：主菜单；输入：用户选择并进行合法性检查switch(用户选择){case1:调用FCFS（）;case2:调用SSTF（）case3:调用SCAN（）case4:调用C-SCAN（）case5:退出}}2）函数的调用关系图Intmain（）Intprintstarter（）VoidC-SCAN（）VoidSCAN（）VoidSSFT（）VoidFCFS（）Intprintstarter（）Intbubble（）Intnearest_select（）Intout_to_in（）Intin_to_out（）Intprintstarter（）Intbubble（）Intout_to_in（）Intin_to_out（）Intout_to_in_to_out（）Intin_to_out_to_in（）Intprintstarter（）Intbubble（）Intout_to_in（）Intin_to_out（）Intout_to_in_twice（）Intin_to_out_twice（）四、调试分析1）调试过程中遇到的问题以及对设计与实现的讨论和分析：（1）随机生成400个磁道号序列：使用rand()函数，对于：50%位于0～499，25%分布在500～999，25%分布在1000～1499，采用如下方法解决：track[i]=(rand()%500);track[i]=(rand()%500)+500;track[i]=(rand()%500)+1000;（2）通过对每一行的输出设置断点判断问题出现在哪里，把出问题的地方缩小到一定范围，然后解决问题，如若解决不出则上网查询。算法部分SSTF算法实现的比较复杂，时间复杂度较高。2）算法的时间复杂性(包括基本操作和其他算法的时间复杂性的分析)和改进设想：（1）FCFS算法：时间复杂度为O（n）,一重循环，算法比较简单；（2）SSTF算法：时间复杂度为O（n^2），二重循环，算法较为复杂；（3）SCAN算法：时间复杂度为O（n）；（4）C-SCAN算法：时间复杂度为O（n）；3）设计过程的经验和体会：设计过程必须要按照自顶向下的结构化设计方法，各个模块要很清晰的体现，并且要考虑时间复杂度。整个程序的结构是很清晰的，首先在0~1500的范围内随机生成400个磁道号序列，接着是主菜单选择要使用的算法，各个算法的结构通过调用不同的输出磁道序列函数来实现，并进行绝对值的求和以及平均值的计算。五、用户使用说明1）按照菜单输入选择何种算法在1~5之间；2）输入磁头初始位置在0~1500之间；3）输入磁臂方向，1：向外，0：向内；六、测试与运行结果1）初始界面，产生400个随机序列，选择算法：2）FSFC算法：3）SSTF算法：4）SCAN算法：（1）最小磁道号大于等于初始磁头位置，测试与运行结果：输出请求序列、平均寻道时间：（2）最大磁道号小于等于磁头初始位置，测试与运行结果：输出请求序列、平均寻道时间：（3）方向0,磁头初始位置为中间值，测试与运行结果：输出请求序列、平均寻道时间：（4）方向1,磁头初始位置为中间值，测试与运行结果：输出请求序列、平均寻道时间：5）C-SCAN算法：（1）方向0，最小磁道号大于等于初始磁头位置，测试与运行结果：输出请求序列、平均寻道时间：（2）方向0，最大磁道号小于等于磁头初始位置，测试与运行结果：输出请求序列、平均寻道时间：（3）方向1，最小磁道号大于等于初始磁头位置，测试与运行结果：输出请求序列、平均寻道时间：（4）方向1，最大磁道号小于等于磁头初位置，测试与运行结果：输出请求序列、平均寻道时间：（5）方向0,磁头初始位置为中间值，测试与运行结果：输出请求序列、平均寻道时间：（6）方向1,磁头初始位置为中间值，测试与运行结果：输出请求序列、平均寻道时间：七、总结感想这次的操作系统课程设计，让我对操作系统磁盘调度策略有了更加深刻的认识，自己动手操作比光看书能更能深刻了解磁盘