模拟磁盘调度算法-操作系统课程设计

某某大学课程设计报告课程名称：操作系统设计题目：模拟磁盘调度算法系别：计算机系专业：计算机科学与技术组别：学生姓名:学号:起止日期:指导教师:..2目录第一章需求分析.............................................................................................................................11.1课程设计的简介................................................................................................................11.2课程设计的目的................................................................................................................11.3磁盘调度主要思想.............................................................................................11.4课程设计内容....................................................................................................................2第二章概要设计.............................................................................................................................32.1设计思想............................................................................................................................32.2数据结构...........................................................................................................................32.3模块调用关系图................................................................................................................32.4子模块程序流程图............................................................................................................5第三章详细设计.............................................................................................................................63.1模块划分............................................................................................................................6第四章代码测试...........................................................................................................................94.1先来先服务........................................................................................................................94.1最短寻道时间优先..........................................................................................................114.1扫描算法..........................................................................................................................12第五章心得体会...........................................................................................................................13第六章致谢...................................................................................................................................13参考文献.........................................................................................................................................13附源代码...........................................................................................................................................1.1.第一章需求分析1.1课程设计的简介这是一个用VC++6.0为工具、C++为编程语言而实现模拟先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）的一个磁盘调度程序。该程序设计系统主界面可以灵活选择某种算法并算出磁头移动的总磁道数以及平均磁道数。1.2课程设计的目的本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）等磁盘调度算法的理解。1.3磁盘调度主要思想设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+……+Mi+……+MN）/N。其中Mi为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：.2.寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。延迟时间——指定扇区旋转到磁头下所需的时间。传送时间——由磁头进程读写完成信息传送的时间。其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱面上。所以各磁盘的编号按柱面顺序（从0号柱面开始），每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。1.4课程设计内容系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）。并计算及比较磁头移动总磁道数和平均磁道数。1.4.1、先来先服务算法（FCFS）这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。1.4.2、最短寻道时间优先算法（SSTF）该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。1.4.3、扫描算法（SCAN）扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从.3.而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。第二章概要设计2.1设计思想本次课程设计我们是以面向对象的思想为主，利用VisualC＋＋为工具实现模拟磁盘调度。程序主要是利用冒泡排序函数、FCFS函数、SSTF函数、SCAN函数、CSCAN函数实现函数的功能。利用菜单式的选择界面，方便的用户操作。最终对每一种模拟磁盘调度输出磁头平均移动的磁道数以及总磁道数。2.2数据结构该程序主要是利用7个函数。Panduan（）函数：对输入的字符进行判断是否合法，zhuanhua（）函数：对输入合法的字符进行转化，bubble（）函数：对输入的磁道进行冒泡排序，FCFS（）函数，即先来先服务函数，SSTF（）函数：最短最短寻道时间函数，SCAN（）函数：扫描函数，CSCAN（）函数：循环扫描函数。各函数之间有点可以相互调用，共同实现要求。本程序主要用到的数据结构为数组、字符串，包括对字符串的合法性判断，利用数组算磁头移动的总磁道数，平均移动磁道数。2.3模块调用关系图.4.图2-1磁盘调度模拟系统磁盘调度模拟系统先来先服务最短寻道时间优先扫描算法退出.5.2.4子模块程序流程图2.4.1先来先服务算法（FCFS）流程图：开始结束输入磁道号按输入顺序将磁道序列输出求平均寻道长度输出移动的平均磁道数FCFS算法流程图2.4.2最短寻道时间优先算法（SSTF）流程图开始结束输入磁道号调用冒泡排