CSCAN磁盘调度算法 操作系统课程设计报告

1、哈尔滨理工大学课程设计（计算机操作系统）题目： cscan磁盘调度算法 班级： 姓名：指导教师：系主任： 2014年03月01日 目 录1cscan磁盘调度算法问题课程设计11.1 题目分析11.2 数据结构11.3 流程图11.4 实现技术21.5 设计结论和心得22 linux代码分析42.1 功能说明42.2 接口说明42.3 局部数据结构42.4 流程图42.5 以实例说明运行过程5第1章- 15-哈尔滨理工大学课程设计报告1cscan磁盘调度算法问题课程设计1.1 分析题目 将queuen进行由小到大的排序，首先定位当前调度磁headstarts在queuen的位置，然后在此位置按给

2、定的方向遍历queuen，当道端点（queue0或queuen-1）时，反向到另一端点再以此方向进行遍历，直到queuen中所有都调度完。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁道差值的累加，当到达端点且queuen未全调度时，总寻道长度加上端点值再加上磁盘磁道总长度，再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。1.2 数据结构hand:当前磁道号; discline10:随机生成的磁道号; void setdi(int discl)生成随机磁道号算法; void copyl(int sour,in

3、t dist ,int x) 数组sour复制到数组dist复制到x个数四详细设计; void delinq(int sour,int x,int y) 数组sour把x位置的数删除,x后的数组元素向前挪一位. void paixu()寻道长度由低到高排序void cscan(int han,int discl)循环扫描算法(cscan)1.3流程图1.4实现技术为实现上述设计，采用c+语言，vs2008开发环境。具体采用的技术如下：循环扫描算法实现步骤如下：输入总磁道数（你可以输入200），点确定，进入第二个界面，再输入磁盘调度序列个数（你可以输入5），然后点确定。依次输入5个值，再输入正在

4、调入的磁道，选择磁盘调度算法1 2 中的任意一个，若选择1后确认，选择磁道走向1.2若选择1，点确定，先输出排序后的磁盘序列：（13 20 89 113 189 ），再输出调度序列为：（89 20 13 189 113 89）并且求出了总寻道长度为352，平均寻道长度为70.4。运行结果如下：1.5设计结论和心得通过课程设计得到如下结论：本次实验首先要了解磁盘调度方法的工作原理。在课程设计前的准备工作时，先把这部分工作做完了。在设计总的程序框架的时候，要注意各功能模块的位置，尽量做到简洁、有序；各功能模块与主程序要正确衔接。 有如下几点心得体会：至此，计算机操作系统课程设计算法已经完成。此次设

5、计基本完成了所规定的功能，但由于这次设计的时间比较仓促，其中不免会有些纰漏，比如在程序的实现上还不够严谨，出错处理不够完善等多方面问题，这些都有进一步改善。由于平时上课不是很认真许多概念没有理解清楚，导致在做设计时有点无从下手的感觉，只好边实验边看书直到弄懂概念后才开始做设计导致时间有点紧张，最终在同学和老师的指导下我完成了设计，此设计基本能够实现规定的要求但是还是不够完善，很多东西做的不够好，程序不够完善和严谨。此次课程设计中我学到了很多东西，无论在理论上还是实践中，都得到不少的提高，这对于我以后的工作和学习都有一种巨大的帮助。#include#include#includeusing na

6、mespace std;void menu() cout*菜单*endl;cout*1、循环扫描算法 (cscan) *endl; cout*2、退出 *endl; cout*endl;/*=初始化序列=*/void init(int queue,int queue_copy,int n) int i; for(i=0;in;+i) queuei=queue_copyi;/对当前正在执行的磁道号进行定位，返回磁道号小于当前磁道中最大的一个int fix ( int queue, int n, int headstarts) int i =0; while ( iqueuei ) i+; if

7、( in-1 ) return n-1; /当前磁道号大于磁盘请求序列中的所有磁道 if ( i=0 ) return -1; /当前磁道号小于磁盘请求序列中的所有磁道 else return i-1; /返回小于当前磁道号中最大的一个/*=使用冒泡算法从小到大排序=*/int *bubble(int queue,int m) int i,j;int temp;for( i=0; im;i+)for(j=i+1;j queuej) temp=queuei; queuei=queuej; queuej=temp; cout排序后的磁盘序列为：; for( i=0;im;i+) /输出排序结果 c

8、outqueuei ; coutendl; return queue;/n表示调度磁盘请求序列queue的长度，diskrode表示磁盘磁道的个数，headstarts表示目前正在调度的磁道； void cscan(int queue,int n,int diskrode,int headstarts) int direction,i,fixi; cout*以下是cscan调度算法*endl; cout请输入磁头的走向：1.由内向外 2.由外向内endl; coutdirection; int count=0; /count表示磁道移动的长度 *bubble(queue,n); fixi=fi

9、x(queue,n,headstarts); cout调度序列为: headstarts ; if(fixi=-1) /headstarts比请求调度序列都小 if(direction=1) /从大到小 count +=queuefixi+1-queue0; /反向再反向 headstarts =queuen-1; coutheadstarts-1;-i) coutqueuei ; count +=headstarts-queuei; headstarts=queuei; if(direction=2) /从小到大 for(i=0;in;+i) coutqueuei-1;-i) coutque

10、uei ; count +=headstarts-queuei; headstarts=queuei; if( direction=2) /从小到大 coutqueue0 ; for(i=1;in;+i) coutqueuei-1;i-) coutqueuei ; count +=headstarts-queuei; headstarts=queuei; count = count+(queuen-1-queue0); /磁头走到0时再反向. headstarts=queuen-1; coutheadstartsfixi;i-) coutqueuei ; count +=headstarts-

11、queuei; headstarts =queuei; if(direction=2) /从小到大 for( i=fixi+1;in;i+) if (direction=2) /从小到大 coutqueuei ; count +=queuei-headstarts; headstarts =queuei; count +=queuen-1-queue0; /磁头走到n-1再反向走. headstarts =queue0; coutheadstarts ; for(i=1;ifixi+1;i+) coutqueuei ; count +=queuei-headstarts; headstarts

12、=queuei; coutendl; cout总的寻道长度为: countendl; cout平均寻道长度为: float(count)/nendl;int main() int n, i, diskrode, headstarts; /n表示调度磁盘请求序列queue的长度，diskrode表示磁盘磁道的个数，headstarts表示目前正在调度的磁道； cout请输入磁盘的总磁道数: diskrode; cout请输入磁盘调度请求序列个数:n; int *queue; queue =(int*)malloc(n*sizeof(int); /给queue数组分配空间. int *queue_

13、copy; queue_copy =(int*)malloc(n*sizeof(int); cout请依次输入该序列的值:endl; for ( i=0;iqueuei; for ( i=0;in;i+) queue_copyi =queuei; coutheadstarts; int menux; menu(); coutmenux; while (menux !=0) if (menux =1) cscan(queue,n,diskrode,headstarts); if (menux =2) cout程序结束,谢谢使用！endl; coutendl; init(queue,queue_c

14、opy,n); menu(); coutmenux; coutendl; 2 linux代码分析为了进一步了解操作系统内核，学习了linux操作系统的段页式存储管理程序虚拟内存映射管理部分，部分源代码如下：struct vm_structunsigned long flags; void *addr; /*虚拟内存块的其始地址 */unsigned long size; /*虚拟内存块的长度*/struct vm_struct *next; /*下一个虚拟内存块*/struct vm_area_struct struct mm_struct * vm_mm; /*指向该虚存段所属进程的mm_s

15、truct */ unsigned long vm_start; /*虚拟内存开始地址 */ unsigned long vm_end; /*虚拟内存结束地址*/ struct vm_area_struct vm_next; unsigned short vm_flags; /*本vma块的属性标志位*/ short vm_avl_height; struct vm_area_struct * vm_avl_left; struct vm_area_struct * vm_avl_right; /*上述三项用于对avl树操作*/ struct vm_operations_struct * vm

16、_ops; /*指向对vma块操作的结构体指针*/ unsigned long vm_offset; struct file * vm_file; /*指向文件的inode结构体或null */ unsigned long vm_pte;static inline unsigned long do_mmap （struct file *file, unsigned long addr,unsigned long len, unsigned long prot,unsigned long flag, unsigned long offset） unsigned long ret = -einva

17、l; if (offset + page_align(len) page_shift）; out: return ret; 2.1 功能说明这一段程序的主要功能为：（1）进程对内存区域的分配最终多会归结到do_mmap（）函数上来，同样释放一个内存区域使用函数do_ummap（）,它会销毁对应的内存区域。（这里do_ummap暂不做说明）（2）linux使用内核函数do_mmap（）完成可执行映像等向虚拟区域的映射，由它建立有关的虚存区域，并指定虚存区域的开始地址、虚存大小以及属性等。2.2 接口说明本程序的输入参数为：file：表示要映射的文件。offset：文件内的偏移量，因为我们并不是下

18、子全部映射一个文件，可能只是映射文件的一部分，offset就表示那部分的起始位置。len：要映射的文件部分的长度。addr：虚拟空间的一个地址，表示从这个地址开始查找一个空闲的虚拟区。prot：指定对这个虚拟区的存取权限。输出结果为：该段程序返回的应为long类型的数据，为经过do_mmap()映射处理后的虚存区域的起始地址。否则则返回map_failed(1)。2.3 局部数据结构本程序共有4个局部变量及数据结构，其类型定义及语义如下：struct mm_struct/mm_struct结构包含了用户进程与存储有关的信息struct vm_area_struct mmap; /*指向虚拟内存

19、段双向链表指针 */struct vm_area_struct *mmap_avl;/*指向虚拟内存段avl树指针 */pgd_t *pgd; /*进程页目录起始地址*/int map_count; /*此进程所用虚拟内存的块数*/unsigned long start_code,end_code; /*进程代码段起始地址和结束地址*/unsigned long start_data,end_data;/*进程数据段起始地址和结束地址*/unsigned long start_stack; /*进程堆栈段起始地址*/unsigned long rss; /*进程驻留在物理内存的页面总数*/st

20、ruct vm_struct/为虚拟内存结构体unsigned long flags; void *addr; /*虚拟内存块的其始地址 */unsigned long size; /*虚拟内存块的长度*/struct vm_struct *next; /*下一个虚拟内存块*/struct vm_area_struct /虚拟内存块存储结构体 struct mm_struct * vm_mm; /*指向该虚存段所属进程的mm_struct */ unsigned long vm_start; /*虚拟内存开始地址*/ unsigned long vm_end; /*虚拟内存结束地址*/ struct vm_area_struct vm_next