操作系统--课程设计报告.docVIP

课 程 设 计 设计题目：模拟实现磁盘的调度 设 计 者：王利君、杜荣峰 学 号：201110414233、201110414236 班 级：2011级2班 一、课题设计目的 a、观察、体会操作系统的磁盘调度方法，并通过一个简单的磁盘调度模拟程序的实现，加深对磁盘调度的理解。b、提高实际动手编程能力，为日后从事软件开发工作打下坚实基础。 c、通过对磁盘调度算法的设计，深入理解提高磁盘访问速度的原理。 三、课题设计思路 算法描述： 1.服务算法（FCFS） 先来先服务（FCFS）调度:按先来后到次序服务，未作优化。 最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在50号柱面上执行输出操作，而等待访问者依次要访问的柱面为130、199、32、159、15、148、61、99，那么，当50号柱面上的操作结束后，移动臂将按请求的先后次序先移到130号柱面，最后到达99号柱面。 采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。 2.算法（SCAN） SCAN 算法又称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。 “电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8层带到15层，然后电梯换成下行方向，把乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。 我们仍用前述的同一例子来讨论采用“电梯调度”算法的情况。由于磁盘移动臂的初始方向有两个，而该算法是与移动臂方向有关，所以分成两种情况来讨论。 〈1〉.移动臂由里向外移动 开始时，，在50号柱面执行操作的读写磁头的移动臂方向是由里向外，趋向32号柱面的位置，因此，当访问50号柱面的操作结束后，沿臂移动方向最近的柱面是32号柱面。所以应先为32号柱面的访问者服务，然后是为15号柱面的访问者服务。之后，由于在向外移方向已无访问等待者，故改变移动臂的方向，由外向里依次为各访问者服务。在这种情况下为等待访问者服务的次序是61、99、130、148、159、199。 〈2〉.移动臂由外向里移动 开始时，正在50号柱面执行操作的读写磁头的移动臂是由外向里（即向柱面号增大的内圈方向）趋向61号柱面的位置，因此，当访问50号柱面的操作结束后，沿臂移动方向最近的柱面是61号柱面。所以，应先为61号柱面服务，然后按移动臂由外向里移动的方向，依次为99、130、148、159、199柱面的访问者服务。当201号柱面的操作结束后，向里移动的方向已经无访问等待者，所以改变移动臂的前进方向，由里向外依次为32、15柱面的访问者服务。 “电梯调度”与“最短寻找时间优先”都是要尽量减少移动臂时所花的时间。所不同的是：“最短寻找时间优先”不考虑臂的移动方向，总是选择离当前读写磁头最近的那个柱面，这种选择可能导致移动臂来回改变移动方向；“电梯调度”是沿着臂的移动方向去选择离当前读写词头最近的哪个柱面的访问者，仅当沿移动臂的前进移动方向无访问等待者时，才改变移动臂的前进方向。由于移动臂改变方向是机械动作，速度相对较慢，所以，电梯调度算法是一种简单、使用且高效的调度算法。 但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。 设计流程图： FCFS流程图： SCAN流程图 总流程图 四、课题设计代码 #includestdio.h #includeiostream.h #includestring.h #includemath.h const int MAXQUEUE=200; //义请求队列最大长度//磁道号请求结构体定义 typedef struct TRACK_Node { int iGo; //访问的磁道号 int iVisited; //磁道是否已经访问标志（1：已访问；0：末访问） }TRACK; TRACK queue[MAXQUEUE]; //磁道号请求队列数组 int iReqNum=0; //磁道访问请求数 int iStart=0; //磁头初始位置 in