《操作系统课程设计-磁盘调度》由会员分享，可在线阅读，更多相关《操作系统课程设计-磁盘调度（21页珍藏版）》请在金锄头文库上搜索。
1、计算机操作系统课程设计设计说明书磁盘调度算法的实现与分析学生姓名 班级学号成绩指导教师(签字)计算机与通信学院目 录1 课程设计简介31.1 课程设计的目的31.2 课程设计内容31.2.1 先服务FCFS (First Come First Server)31.2.2最短寻道时间优先SSFT (Shortest Seek Time First)31.2.3 SCAN41.2.4 CSCAN52 数据结构的设计62.1 数据结构的设计理念62.2 数据结构的详细设计62.2.1 FCFS策略62.2.2 SSTF策略62.2.3 SCAN策略72.2.4 C_SCAN策略73 功能模块（或算法
2、）描述83.1 排序模块（流程图）83.1.1 SSTF策略83.1.2 SCAN策略83.1.3 C_SCAN策略93.2 求移动的磁道数模块（流程图）94 程序运行结果114.1 FCSF策略的运行结果114.2 SSTF策略的运行结果114.3 SCAN策略的运行结果124.4 C_SCAN策略的运行结果125、 心得体会13参考文献14附源代码15附录一:FCFS策略15附录三:SCAN策略16附录四:C_SCAN策略181 课程设计简介1.1 课程设计的目的使学生熟悉磁盘管理系统的设计方法；加深对所学各种磁盘调度算法的了解及其算法的特点。主要对FCFS（先来先服务），SSTF（最短寻
3、道时间优先），SCAN（电梯调度算法），C-SCAN（循环调度算法）这几种磁盘调度的算法分析和实现。1.2 课程设计内容1.2.1 先服务FCFS (First Come First Server)这是最简单的磁盘调度策略，它根据进程请求访问磁盘的时间顺序进行调度。假设磁盘有200个磁道，磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为：55、58、39、18、90、160、150、38、184，当前磁头在100磁道处FCFS策略磁头臂的移动轨迹如下：1.2.2最短寻道时间优先SSFT (Shortest Seek Time First)它是根据磁头当前的位置，选择请求队列中距离磁头
4、最短的请求响应。假设磁盘有200个磁道，磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为：55、58、39、18、90、160、150、38、184，当前磁头在100磁道处SSTF策略磁头臂的移动轨迹如下：1.2.3 SCAN也称电梯策略，要求磁头臂仅仅沿一个方向移动，并在途中满足所有未完成的请求，直到它到达这个方向的最后一个磁道，或这个方向没有别的请求为止，然后倒转服务方向，同样按顺序完成的有请求。假设磁盘有200个磁道，磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为：55、58、39、18、90、160、150、38、184，当前磁头在100磁道处SCAN策略磁头臂的
5、移动轨迹如下：1.2.4 CSCAN 是循环扫描法，当到达最后一个磁道时，磁头臂返回到磁头的另一端，并再次开始扫描。假设磁盘有200个磁道，磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为：55、58、39、18、90、160、150、38、184，当前磁头在100磁道处C-SCAN策略磁头臂的移动轨迹如下：2 数据结构的设计2.1 数据结构的设计理念根据磁道请求队列和不同的策略需求，先将磁道队列排好序，然后再根据已排好序的磁道队列求出总的移动磁道数，然后求出平均磁道数。2.2 数据结构的详细设计2.2.1 FCFS策略申请磁道的队列数组按照队列的顺序进行移动，如：申请的队列为：re
6、questn，初始磁道为：Init_Position，则可令当前磁道为 pre ，初始状态的pre的值为Init_Position，数据结构顺序为：输入队列为requestn：123456789555839189016015038184根据该序列，磁道按顺序移动，将移动的磁道数加到sum中之后，将当前移动到的磁道赋给pre，然后按顺序进行下一个磁道移动，直到队列中的所有申请都移动到了。2.2.2 SSTF策略该策略是最短寻道时间优先，在申请磁道的队列数组中剩余的磁道找出离当前磁道最近的磁道进行移动，直到全部申请磁道都移动了。如：申请的队列为：requestn，初始磁道为：Init_Positi
7、on，则可令当前磁道为 pre ，初始状态的pre的值为Init_Position，数据结构为：申请磁道的队列requestn：123456789555839189016015038184将该申请磁道按照最短寻道时间优先规则，即当前磁道到剩下的磁道的距离最短的磁道为当前磁道的下一个磁道。可得，重新排序的磁道队列request1n:123456789905855393818150160184然后得到的新的磁道队列再按照FCFS策略进行移动。2.2.3 SCAN策略该策略是扫描，首先要确定扫描方向（本课程设计确定为正方向），在申请磁道的队列数组中剩余的磁道先找出离当前磁道最近的正方向磁道进行移动，
8、直到全部正方向的磁道都移动了，然后再按照反方向寻找当前磁道的最近磁道进行移动。如：申请的队列为：requestn，初始磁道为：Init_Position，则可令当前磁道为 pre ，初始状态的pre的值为Init_Position，数据结构为：根据，申请磁道的队列requestn：123456789555839189016015038184可得，重新排序的磁道队列request1n:123456789150160184905855393818然后得到的新的磁道队列再按照FCFS策略进行移动。2.2.4 C_SCAN策略该策略是循环扫描，其大部分和SCAN策略相同，首先要确定扫描方向（本课程设计
9、确定为正方向），在申请磁道的队列数组中剩余的磁道先找出离当前磁道最近的正方向磁道进行移动，直到全部正方向的磁道都移动了，然后移动到剩余申请磁道的最小磁道的位置，然后再按照正方向寻找剩余磁道。如：申请的队列为：requestn，初始磁道为：Init_Position，则可令当前磁道为 pre ，初始状态的pre的值为Init_Position，数据结构为：根据，申请磁道的队列requestn：123456789555839189016015038184可得，重新排序的磁道队列request1n:123456789150160184183839555890然后得到的新的磁道队列再按照FCFS策略进
10、行移动。3 功能模块（或算法）描述3.1 排序模块（流程图）根据策略的不同，有不同的排序规则，FCFS策略是先到先服务策略，所以该策略不需要将队列重新排序，可以直接根据队列顺序求出总的移动磁道数，然后根据总的移动磁道数求出平均移动磁道数。3.1.1 SSTF策略该策略的流程图如图3-1-1所示。 图3-1-1 SSTF策略的队列排序流程图3.1.2 SCAN策略该策略的流程图如图3-1-2所示。 图3-1-2 SCAN策略的队列排序流程图3.1.3 C_SCAN策略该策略的流程图如图3-1-3所示。图3-1-2 SCAN策略的队列排序流程图3.2 求移动的磁道数模块（流程图）由于所有的策略都是
11、已经将队列给排好序了的，那么，我们只需要求出按照排好序的队列的磁道一个一个的移动的磁道数，然后相加就可以了，具体流程图如图3-2所示。图3-2 求移动的磁道数流程图 4 程序运行结果4.1 FCSF策略的运行结果如图4-1所示为FCSF策略的运行结果，初始磁道为100，该结果的第一行为磁道的移动过程，sum表示的是磁道的移动总数，average表示的是平均移动磁道数。图4-1 FCSF策略的运行结果4.2 SSTF策略的运行结果如图4-2所示为SSTF策略的运行结果，初始磁道为100，该结果的第一行为磁道的移动过程，sum表示的是磁道的移动总数，average表示的是平均移动磁道数。图4-2
12、SSTF策略的运行结果4.3 SCAN策略的运行结果如图4-3所示为SCAN策略的运行结果，初始磁道为100，该结果的第一行为磁道的移动过程，sum表示的是磁道的移动总数，average表示的是平均移动磁道数。图4-3 SCAN策略的运行结果4.4 C_SCAN策略的运行结果如图4-4所示为C_SCAN策略的运行结果，初始磁道为100，该结果的第一行为磁道的移动过程，sum表示的是磁道的移动总数，average表示的是平均移动磁道数。图4-4 C_SCAN策略的运行结果5、 心得体会 通过此次课程设计，对磁盘调度算法有了充分的了解，并增强了自身的动手能力，通过自己翻阅书籍，重新熟悉了C语言和一
13、些算法实现。从中也了解到，学习知识要善于动手，并且要学会克服困难，解决遇到的问题。只有在不断的动手学习和克服困难的过程中，学习到更多的知识，知识也会因为应用而记忆更加深刻。 由此可知，我们要从实际中去检验自己的知识，去了解自己对知识的掌握程度。最终，达到学以致用的目的。参考文献1 刘振鹏，石强 数据结构（第三版） 中国铁道出版社. 2007.2 罗宇，邹鹏，邓胜兰 操作系统（第三版）北京：电子工业高等教育出版社，2012.3 李长云，廖立君，王平，童启 C语言程序设计CIP. 北京：国防工业大学出版社 2011. 附源代码附录一:FCFS策略int funFCFS()int request=55,58,39,18,90,160,150,38,184;int start=Init_Position;int i,d_value; /d_value跨过的磁道数int sum=0;printf(FCFS先来先服务算法n);printf(磁道的起始位置：%dn,start);for(i=0;i=8;i+)d_value=abs(start-requesti); /abs()求绝对值sum=sum+d_value;printf(下一磁道为: %dt,requesti)
