《操作系统磁盘调度算法》由会员分享，可在线阅读，更多相关《操作系统磁盘调度算法（40页珍藏版）》请在金锄头文库上搜索。
1、操作系统课程设计任务书题目：磁盘调度算法院 系：专 业： 班 级：姓 名：学 号：指导教师：设计时间：2018.1.1 -2018.1.5指导教师评成绩评定：指导教师签字：年月日1、 需求分析1.1 课题描述 41.2 课题目的 41.3 理论依据 72、 概要设计 82.1 设计方法 82.2 技术 82.3 运行环境 83、 详细设计 93.1 流程图 113.2 程序主要代码 134、 运行结果及分析 144.1 运行结果 154.2 结果详细分析 165、 总结和心得 166、 参考文献 177、附录：程序源代码231 、需求分析1.1 课题描述这次课程设计我研究的题目是 ：磁盘调度算
2、法。具体包括三种算法分别是：先来先服务算法（FCFS、最短寻道时间 优先算法（ SSTF ） 、扫描算法（电梯调度算法） （ SCAN） 。1.2 课题目的通过这次实验，加深对磁盘调度算法的理解，进一步掌握先 来先服务FCF渥短寻道时间优先SSTF,扫描SCANU法的实现方法。1.3 理论依据设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方 面，常常需要排队。这时，对众多的访问要求按一定的次序响 应，会直接影响磁盘的工作效率，进而
3、影响系统的性能。访问 磁盘的时间因子由 3 部分构成，它们是查找（查找磁道）时 间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（ N ），即： L=（ M1+M2+ ,+Mi+ , +MN ） /N其中 Mi 为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头 进行读写，完成信息传送。因此，执行一次输入输出所花的时 间有：寻找时间一一磁头在移动臂带动下
4、移动到指定柱面所花的时间。延迟时间一一指定扇区旋转到磁头下所需的时间。传送 时间一一由磁头进程读写完成信息传送的时间。其中传送信息所花的时间，是在硬件设计就固定的。而寻找时 间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺 序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱面 上。所以各磁盘的编号按柱面顺序，每个柱面按磁道顺序，每 个磁道又按扇区顺序进行排序。磁盘是可供多个进程共享的设备，当有多个进程都要求访问 磁盘是，应米用一种最佳调度算法，以使各种进程对磁盘的平均访问时间最小。由
5、于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标，是使磁盘的平均寻道时间最少。目前常用的磁盘帝调度算法有：先来先服务、最短寻道时间优 先及扫描等算法。先来先服务（FCFS调度：按先来后到次序服务，未作优 化。最简单的移臂调度算法是先来先服务”调度算法，这个算法际上不考虑访问者要求访问的物理位置 ，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在 50号柱面上执行输出操作，而等待访问者依次要访问的柱面为130、199、 32、 159、 15 、 148、 61、 99，那么，当 50 号柱 面上的操作结束后，移动臂将按请求的先后次序先移到 130 号 柱面，最后到达
6、 99 号柱面。采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。最短寻找时间优先调度算法 总是从等待访问者中挑选寻找时 间最短的那个请求先执行的，而不管访问者到来的先后次序。 现在仍利用同一个例子来讨论，现在当 50 号柱面的操作结束 后，应该先处理 61 号柱面的请求，然后到达32 号柱面执行操作，随后处理 15 号柱面请求，后继操作的次序应该是99、130、 148、159、 199。采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了 200 多个柱面的距离，与先来先服
7、务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（SSTF调度，FCF哙引起读写头在盘面上的大范围移动，SST嗜找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SST喧找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖 延（又称饥饿）。SCANf法又称电梯调度算法。SCAN#法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上 的往复移动，SCANT法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向 去选择离
8、当前移动臂最近的那个柱访问者，如果沿臂的移动方 向无请求访问时，就改变臂的移动方向再选择 。这好比乘电 梯，如果电梯已向上运动到 4 层时，依次有3 位乘客陈生、伍 生、张生在等候乘电梯。他们的要求是：陈生在2 层等待去 10 层；伍生在5层等待去底层；张生在 8 层等待 15 层。由于电 梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8层带到 15 层，然后电梯换成下行方向，把乘客伍生从5 层带 到底层，电梯最后再调换方向，把乘客陈生从2 层送到 10但是，电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向2、概要设计2.1 设计方法通过C语言的编程，
9、设计程序模拟先来先服务FCFS最短寻道 时间优先SSTF,和扫描SCAN#法的工作过程。假设有 n个磁道号所组成的磁 道访问序列，给定开始磁道号 m和磁头移动的方向（正 向或者反向）， 分别利用不同的磁盘调度算法访问磁道序列 ，给出 磁头每一次移动的过程，算出磁头移动的距离，继而计算每种算法 的平 均寻道长度。2.2 技术C 语言、操作系统磁盘调度算法、C+。2.3 运行环境WindowlO、 VC+6.0 。3、详细设计3.1流程图先来先服务算法（FCFS :Sum=abs (no w-array0)1 T磁头移动总距离Sum+=abs(arrayj-arrayi1输出磁盘调度/ 序列 ar
10、rayj1|目前的位置变为当前的位置j+最短寻道时间优先算法（SSTD：再盗迤专从小穷大/ 入当？ TEI道号nowTarray m扫描SCAN#1HBs号从小到大推字3.2程序主要代码先来先服务算法（ FCFS :void FCFS(vector m_vec,i nt positi on)/先来先服务算法dis = 0;average_dista nee = 0;for(vector:iterator it=m_vec.begi n( );it!=m_vec.e nd();it+)dis += abs(positi on-*it);Sleep(500);cout*it;positi on =
11、 *it;compute_dis(m_vec,dis,average_dista nee);最短寻道时间优先算法 (SSTF):void SSTF(vectorm_vec,int position)/ 最短寻道时间算法dis = 0;average_dista nee = 0;sort(m_vec.begin(),m_vec.end();/ 从小至 U 大排序int i = 0;for(vector:iterator it=m_vec.begi n( );it!=m_vec.e nd();it+)if(positi on = *it)i+;int count = 0;int left = i-
12、1;int right = i;while(co un t=0 & abs(m_vecright-positi on) abs(m_vecleft-positi on) |right=m_vec.size()dis += abs(m_vecleft-positi on);Sleep(500);coutm_vecleft;positi on = m_vecleft;left-;elsedis += abs(m_vecright-positi on);Sleep(500);coutm_vecright;positi on = m_vecright;right+;coun t+;compute_di
13、s(m_vec,dis,average_dista nee);扫描SCANT法：void SCAN(vectorm_vec,int position)/ 电梯调度算法dis = 0;average_dista nee = 0;sort(m_vec.begin(),m_vec.end();/ 从小至 U 大排序int i = 0;for(vector:iterator it=m_vec.begi n( );it!=m_vec.e nd();it+) if(position = *it)i+;/找到position 所在的磁道int left = i - 1;/ 先从外到内扫描int right = i;while(left = 0)dis += abs(positi on - m_vecleft);Sleep(500);coutm
