操作系统课程设计报告-磁盘调度算法的模拟实现及对比.docx

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