SCAN磁盘调度算法.doc

哈尔滨理工大学课程设计（操作系统） 题目： SCAN磁盘调度算法 学 院： 计算机科学与技术学院 班级： 计算机系10-8班 姓名：曾现坤 1004010828 指导教师：高雪瑶 系主任： 林克正 2013年03月01日 目 录1.SCAN磁盘调度算法课程设计11.1 题目分析11.2 数据结构11.3 流程图31.4 实现技术31.5 设计结论和心得3 1.6 源代码.32 Linux代码分析122.1 功能说明142.2 接口说明1142.3 局部数据结构1142.4 流程图152.5 以实例说明运行过程16第1章- 16-哈尔滨理工大学课程设计报告1.SCAN磁盘调度算法课程设计1.1 题目分析本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。1.2 数据结构SCAN磁盘调度算法问题中涉及的数据结构包括手动输入磁道的信号量、选择调度算法的信号量、SCAN调度算法的信号量、显示运行结果的信号量等。用伪代码表示如下：int scan(Linklist L,int Current)LNode *p,*q,*s;float sum=0;if(L-next!=NULL)p=L-next;while(p-datanext;printf(扫描算法顺序是:);for(q=p;q!=NULL;q=q-next)/输出大于当前磁道号的数printf(%d ,q-data);sum+=abs(Current-q-data);Current=q-data;for(s=p-prior;s!=NULL;s=s-prior)/磁臂换向，自外向里移动，依次输出p指针之前的数据printf(%d ,s-data);sum+=abs(Current-s-data);Current=s-data;printf(n);printf(平均寻道长度为:%.1fn,sum/i*1.0);return 0;1.3 流程图开始手动输入磁道选择调度算法SCAN算法显示运行结果结束1.4 实现技术为实现上述设计，采用C+语言，VS2008开发环境。具体采用的技术如下：（1） 白盒测试技术白盒测试也称结构测试或逻辑驱动测试，它是按照程序内部的结构测试程序，通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行，检验程序中的每条通路是否都能按预定要求正确工作。 这一方法是把测试对象看作一个打开的盒子，测试人员依据程序内部逻辑结构相关信息，设计或选择测试用例，对程序所有逻辑路径进行测试，通过在不同点检查程序的状态，确定实际的状态是否与预期的状态一致。 （2） 集成测试技术集成测试，也叫组装测试或联合测试。在单元测试的基础上，将所有模块按照设计要求（如根据结构图组装成为子系统或系统，进行集成测试。实践表明，一些模块虽然能够单独地工作，但并不能保证连接起来也能正常的工作。程序在某些局部反映不出来的问题，在全局上很可能暴露出来，影响功能的实现。 实现步骤如下：（1）开始界面 （2） 算法选择界面 （3） 运行结果如下： 1.4 设计结论和心得通过课程设计得到如下结论：（1）扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。（2）此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。有如下几点心得体会：（1）软件结构合理，自需求分析开始，采取自顶向下逐步求精的方法，将问题逐步分解为各个模块，各模块间通过指定类型参数进行数据传递，保证程序正确，结构清晰。（2）控制变量对比，各磁盘调度算法均可对同一组随机磁道进行调度，但并不会改变随机磁道的内容，保证了平均寻道长度对比的真实性，有效性。1.6 源代码#include #include #include #include typedef struct LNode /双链表结点定义int data;struct LNode *next;struct LNode *prior;LNode,*Linklist;int i=0;LNode * CreatList_L(Linklist L) /创建带头结点双链表，满足用户从键盘输入数字LNode *p,*q; /定义尾结点q，L=(Linklist)malloc(sizeof(LNode);/为结点L动态分配内存，建立链表头结点L-next=NULL;int temp;printf(*n);printf( 请输入磁道数(以0结束): n);printf(*n); scanf(%d,&temp);while(temp!=0)q=(Linklist)malloc(sizeof(LNode);q-data=temp;if(L-next=NULL)L-next=q;q-prior=NULL;else /采用尾插法将q插入L尾部并使p指向qp-next=q;q-prior=p;q-next=NULL;p=q;scanf(%d,&temp);/?i+;return L;int scan(Linklist L,int Current)LNode *p,*q,*s;float sum=0;if(L-next!=NULL)p=L-next;while(p-datanext;printf(扫描算法顺序是:);for(q=p;q!=NULL;q=q-next)/输出大于当前磁道号的数printf(%d ,q-data);sum+=abs(Current-q-data);Current=q-data;for(s=p-prior;s!=NULL;s=s-prior)/磁臂换向，自外向里移动，依次输出p指针之前的数据printf(%d ,s-data);sum+=abs(Current-s-data);Current=s-data;printf(n);printf(平均寻道长度为:%.1fn,sum/i*1.0);return 0;int main()int Current;Linklist L=NULL;LNode *p;printf(请输入当前的磁道号:);scanf(%d,&Current);p=CreatList_L(L);int temp;printf(*n);printf(1.扫描算法(SCAN)n);printf( 2.退出n);printf(*n);printf(请选择:);scanf(%d,&temp);while(temp!=2)switch(temp)case 1:scan(p,Current); break;printf(退出函数，谢谢使用);return 0;2 Linux代码分析/ 复制进程的页目录页表。int copy_page_tables(unsigned long from,unsigned long to,long size) unsigned long * from_page_table; unsigned long * to_page_table; unsigned long this_page; unsigned long * from_dir, * to_dir; unsigned long nr;/ 源地址和目的地址都需要是4Mb 的倍数。否则出错，死机。 if (from&0x3fffff) | (to&0x3fffff) panic(copy_page_tables called with wrong alignment);/ 取得源地址和目的地址的目录项(from_dir 和to_dir)。 from_dir = (unsigned long *) (from20) & 0xffc); /* _pg_dir = 0 */ to_dir = (unsigned long *) (to20) & 0xffc);/ 计算要复制的内存块占用的页表数（也即目录项数）。 size = (unsigned) (size+0x3fffff) 22;/ 下面开始对每个占用的页表依次进行复制操作。 for( ; size-0 ; from_dir+,to_dir+) / 如果目的目录项指定的页表已经存在(P=1)，则出错，死机。 if (1 & *to_dir) panic(copy_page_tables: already exist);/ 如果此源目录项未被使用，则不用复制对应页表，跳过。 if (!(1 & *from_dir) continue;/ 取当前源目录项中页表的地址from_page_table。 from_page_table = (unsigned long *) (0xfffff000 & *from_dir);/ 为目的页表取一页空闲内存，如果返回是0 则说明没有申请到空闲内存页面。返回值=-1，退出。 if (!(to_page_table = (unsigned long *) get_free_page() return -1; /* Out of memory, see freeing */ 设置目的目录项信息。7 是标志信息，表示(Usr, R/W, Present)。 *to_dir = (unsigned long) to_page_table) | 7;/ 针对当前处理的页表，设置需复制的页面数。如果是在内核空间，则仅需复制头160 页，否则需要/ 复制1 个页表中的所有1024 页面。 nr = (from=0)?0xA0:1024;/ 对于当前页表，开始复制指定数目nr 个内存页面。 for ( ; nr- 0 ; from_page_table+,to_page_table+) this_page = *from_page_table; / 取源页表项内容。 if (!(1 & this_page) / 如果当前源页面没有使用，则不用复制。 continue;/ 复位页表项中R/W 标志(置0)。(如果U/S 位是0，则R/W 就没有作用。如果U/S 是1，而R/W 是0，/ 那么运行在用户层的代码就只能读页面。如果U/S 和R/W 都置位，则就有写的权限。) this_page &= 2; *to_page_table = this_page; / 将该页表项复制到目的页表中。/ 如果该页表项所指页面的地址在1M 以上，则需要设置内存页面映射数组mem_map，于是计算/ 页面号，并以它为索引在页面映射数组相应项中增加引用次数。 if (this_page LOW_MEM) *from_page_table = this_page; / 令源页表项也只读?。 this_page -= LOW_MEM; this_page = 12; mem_mapthis_page+; invalidate(); / 刷新页变换高速缓冲。 return 0; 2.1 功能说明复制进程的页目录页表2.2 接口说明本程序的输入参数为：unsigned long from,unsigned long to,long size输出结果为：将进程的页目录页表复制2.3 局部数据结构本程序共有5个局部变量及数据结构，其类型定义及语义如下：unsign