哈尔滨理工大学
课 程 设 计
（操作系统）
题 目：
CSCAN磁盘调度算法 班 级： 计算机科学与技术学院 计算机系 10-8班 姓 名： 赵梦麒 1004010824 指导教师： 高雪瑶 系主任： 林克正
2013年03月01日
目 录
1CSCAN磁盘调度算法问题课程设计 ............................................................................1 1.1 题目分析...................................................................................................................1 1.2 数据结构...................................................................................................................1 1.3 流程图 .......................................................................................................................1 1.4 实现技术...................................................................................................................1 1.5 设计结论和心得 ......................................................................................................3 2 Linux代码分析 ............................................................................ 错误！未定义书签。 2.1 功能说明............................................................................... 错误！未定义书签。 2.2 接口说明............................................................................... 错误！未定义书签。 2.3 局部数据结构 ...................................................................... 错误！未定义书签。 2.4 流程图 ................................................................................... 错误！未定义书签。 2.5 以实例说明运行过程 .......................................................... 错误！未定义书签。
- II-
1CSCAN磁盘调度算法问题课程设计
1.1 分析题目
将
queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的
位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，反向到另一端点再以此方向进行遍历，直到queue[n]中所有都调度完。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上磁盘磁道总长度，再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。
1.2 数据结构
Hand:当前磁道号; DiscLine[10]:随机生成的磁道号; void SetDI(int DiscL[])生成随机磁道号算法;
void CopyL(int Sour[],int 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-
哈尔滨理工大学课程设计报告
- 2-
哈尔滨理工大学课程设计报告
1.3 实现技术
为实现上述设计，采用C++语言，VS2008开发环境。具体采用的技术如下：
循环扫描算法
实现步骤如下：
输入起始磁道（你可以输入100），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入50），然后点确定。选择磁盘调度算法1 2 3 4中的任意一个，若选择4后确认，则随机输出10个小于50的磁道数 ：（47 26 21 38 19 12 17 49 35 44），则循环扫描算法(CSCAN)：（12 17 19 21 26 35 38 44 47 49）。
运行结果如下：
1.4 设计结论和心得
通过课程设计得到如下结论：
本次实验首先要了解磁盘调度的工作原理及四种调度方法的工作原理。在课程设计前的准备工作时，先把这部分工作做完了。在设计总的程序框架的时候，要注意各功能模块的位置，尽量做到简洁、有序；各功能模块与主程序要正确衔接。
有如下几点心得体会：
至此，计算机操作系统课程设计算法已经完成。此次设计基本完成了所规定的功能，但由于这次
- 3-
哈尔滨理工大学课程设计报告
设计的时间比较仓促，其中不免会有些纰漏，比如在程序的实现上还不够严谨，出错处理不够完善等多方面问题，这些都有进一步改善。
由于平时上课不是很认真许多概念没有理解清楚，导致在做设计时有点无从下手的感觉，只好边实验边看书直到弄懂概念后才开始做设计导致时间有点紧张，最终在同学和老师的指导下我完成了设计，此设计基本能够实现规定的要求但是还是不够完善，很多东西做的不够好，程序不够完善和严谨。此次课程设计中我学到了很多东西，无论在理论上还是实践中，都得到不少的提高，这对于我以后的工作和学习都有一种巨大的帮助。
#include void menu(){ cout<<\"*********************菜单*********************\"< for(i=0;i - 4- queue[i]=queue_copy[i]; i++; 哈尔滨理工大学课程设计报告 if ( i>n-1 ) return n-1; //当前磁道号大于磁盘请求序列中的所有磁道 if ( i==0 ) return -1; //当前磁道号小于磁盘请求序列中的所有磁道 else } /*=================使用冒泡算法从小到大排序==============*/ int *bubble(int queue[],int m) { int i,j; int temp; for( i=0; i return i-1; //返回小于当前磁道号中最大的一个 if( queue[i] > queue[j]) { } temp=queue[i]; queue[i]=queue[j]; queue[j]=temp; cout< } /* ====================以下是FCFS算法==================*/ void FCFS(int queue[],int n,int diskrode,int headstarts) //queue是请求调度序列，n为其个数，diskroad为磁盘磁道数，headstarts为正在调度的磁道 { cout<<\"************以下为FCFS调度算法***********\"< /*=====================SSTF算法====================*/ void SSTF( int queue[], int n, int diskrode, int headstarts) { int k=1; int l,r; int i,j,count=0; - 6- count +=headstarts-queue[0]; count+=queue[0]-headstarts; cout<<\"调度序列为: \"; cout< count +=queue[i]-queue[i+1]; count +=queue[i+1]-queue[i]; else else 哈尔滨理工大学课程设计报告 queue =bubble(queue,n); cout<<\"************以下为SSTF调度算法***********\"< if( headstarts >queue[0] && headstarts while ( ( l >=0) && ( r //若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务 cout<<\"磁盘扫描序列为： \"; cout< cout< //确定当前磁道在已排的序列中的位置 哈尔滨理工大学课程设计报告 } //当前磁道在请求序列范围内 if ( (headstarts-queue[l]) <(queue-headstarts)) { cout< } else if ( (headstarts-queue[l]) ==(queue-headstarts)) { cout< } if( l==-1) { //磁头移动到序列的最小号，返回外侧扫描仍未扫描的磁道 for ( j=r;j } else { //磁头移动到序列的最大号，返回内侧扫描仍未扫描的磁道 - 8- 哈尔滨理工大学课程设计报告 } cout< int direction, i, fixi; cout<<\"***********以下是SCAN调度算法*************\"< *bubble(queue,n); fixi = fix(queue,n,headstarts); cout< for ( i=0;i for(j=l;j>=0;j--) { cout< // headstarts比请求调度序列都小 //从大到小 哈尔滨理工大学课程设计报告 headstarts =queue[i]; } } if ( direction ==2) //从小到大 { for (i=0; i } } else if ( fixi ==n-1) //headstarts比请求调度序列的都大 { if ( direction ==1) { for ( i=n-1; i>=0;i--) { cout< } if ( direction ==2) //从小到大 { for ( i=n-1;i>=0;i--) //从大到小 { cout< 哈尔滨理工大学课程设计报告 count +=headstarts-queue[i]; headstarts =queue[i]; } } } else { if (direction ==1) //从大到小 { for ( i=fixi;i>-1;i--) { cout< count +=queue[fixi+1]-queue[0]; //磁头走到0再反向走 headstarts =queue[fixi+1]; cout< if (direction ==2) //从小到大 { for ( i=fixi+1;i - 11- 哈尔滨理工大学课程设计报告 } } } headstarts =queue[fixi]; count +=queue[n-1]-queue[fixi]; //磁头走到n-1再反向走 cout< cout< int direction,i,fixi; cout<<\"***********以下是CSCAN调度算法*************\"< fixi=fix(queue,n,headstarts); cout<<\"调度序列为: \"< - 12- //headstarts比请求调度序列都小 哈尔滨理工大学课程设计报告 { //从大到小 count +=queue[fixi+1]-queue[0]; //反向再反向 headstarts =queue[n-1]; cout< } if(direction==2) //从小到大 { for(i=0;i } } else if(fixi==n-1) //headstarts比请求调度序列都大 { if(direction==1) //从大到小 { for(i=n-1;i>-1;--i) { cout< - 13- 哈尔滨理工大学课程设计报告 } } headstarts=queue[i]; if( direction==2) { } if ( direction==1) { for ( i=fixi;i>-1;i--) { } count +=queue[n-1]-queue[0]; //磁头走到0时再反向... headstarts=queue[n-1]; cout< - 14- //从小到大 cout< cout< //从大到小 cout< } } if(direction==2) { } for( i=fixi+1;i //从小到大 cout< count +=queue[n-1]-queue[0]; //磁头走到n-1再反向走... headstarts =queue[0]; cout< int n, i, diskrode, headstarts; //n表示调度磁盘请求序列queue的长度，diskrode表示磁盘磁道的个数，headstarts表示目前正 - 15- 哈尔滨理工大学课程设计报告 在调度的磁道； cout<<\"请输入磁盘的总磁道数:\"< int *queue_copy; queue_copy =(int*)malloc(n*sizeof(int)); cout<<\"请依次输入该序列的值:\"< queue_copy[i] =queue[i]; for ( i=0;i if (menux ==1) FCFS(queue,n,diskrode,headstarts); SSTF(queue,n,diskrode,headstarts); SCAN(queue,n,diskrode,headstarts); if (menux ==2) if (menux ==3) if (menux ==4) CSCAN(queue,n,diskrode,headstarts); if (menux ==5) cout<<\"程序结束,谢谢使用！\"< cout<<\"请按菜单选择，输入相应的数字: \"; - 16- 哈尔滨理工大学课程设计报告 cin>>menux; cout< 哈尔滨理工大学课程设计报告 2 Linux代码分析 为了进一步了解操作系统内核，学习了Linux操作系统的段页式存储管理程序虚拟内存映射管理部分，部分源代码如下： struct vm_struct { unsigned long flags; void *addr; /*虚拟内存块的其始地址 */ unsigned long size; /*虚拟内存块的长度 */ struct vm_struct *next; /*下一个虚拟内存块 */ } struct vm_area_struct { struct mm_struct * vm_mm; unsigned long vm_start; /*指向该虚存段所属进程的mm_struct */ /*虚拟内存开始地址 */ /*虚拟内存结束地址*/ /*本vma块的属性标志位*/ unsigned long vm_end; struct vm_area_struct vm_next; unsigned short vm_flags; short vm_avl_height; struct vm_area_struct * vm_avl_left; struct vm_area_struct * vm_avl_right; /*上述三项用于对AVL树操作*/ struct vm_operations_struct * vm_ops; /*指向对vma块操作的结构体指针*/ unsigned long vm_offset; struct file * vm_file; 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 = -EINVAL; - 18- /*指向文件的inode结构体或NULL */ 哈尔滨理工大学课程设计报告 if ((offset + PAGE_ALIGN(len)) < offset) goto out; if (! (offset & ~PAGE_MASK)) ret = do_mmap_pgoff （file, addr, len, prot, flaoffset>>PAGE_SHIFT）; out: return ret; } 2.1 功能说明 这一段程序的主要功能为： （1）进程对内存区域的分配最终多会归结到do_mmap（）函数上来，同样释放一个内存区域使用函数do_ummap（）,它会销毁对应的内存区域。（这里do_ummap暂不做说明） （2）Linux使用内核函数do_mmap（）完成可执行映像等向虚拟区域的映射，由它建立有关的虚存区域，并指定虚存区域的开始地址、虚存大小以及属性等。 2.2 接口说明 本程序的输入参数为： file：表示要映射的文件。 offset：文件内的偏移量，因为我们并不是—下子全部映射一个文件，可能只是 映射文件的一部分，offset就表示那部分的起始位置。 len：要映射的文件部分的长度。 addr：虚拟空间的一个地址，表示从这个地址开始查找一个空闲的虚拟区。 prot：指定对这个虚拟区的存取权限。 输出结果为： 该段程序返回的应为long类型的数据，为经过do_mmap()映射处理后的虚存区 域的起始地址。否则则返回MAP_FAILED(－1)。 - 19- 哈尔滨理工大学课程设计报告 2.3 局部数据结构 本程序共有4个局部变量及数据结构，其类型定义及语义如下： struct mm_struct { //mm_struct结构包含了用户进程与存储有关的信息 struct vm_area_struct mmap; /*指向虚拟内存段双向链表指针 */ 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; /*进程驻留在物理内存的页面总数 */ …… } struct vm_struct { //为虚拟内存结构体 unsigned long flags; void *addr; /*虚拟内存块的其始地址 */ unsigned long size; /*虚拟内存块的长度 */ /*下一个虚拟内存块 */ struct vm_struct *next; } struct vm_area_struct { //虚拟内存块存储结构体 struct mm_struct * vm_mm; unsigned long vm_start; unsigned long vm_end; struct vm_area_struct vm_next; /*指向该虚存段所属进程的mm_struct */ /*虚拟内存开始地址*/ /*虚拟内存结束地址*/ - 20- 哈尔滨理工大学课程设计报告 unsigned short vm_flags; short vm_avl_height; /*本vma块的属性标志位*/ struct vm_area_struct * vm_avl_left; struct vm_area_struct * vm_avl_right; /*上述三项用于对AVL树操作 */ struct vm_operations_struct * vm_ops; /*指向对vma块操作的结构体指针 */ unsigned long vm_offset; struct file * vm_file; /*指向文件的inode结构体或NULL unsigned long vm_pte; }; typedef struct page { //页存储结构 struct list_head list; /*该页根据不同用途挂到不同链表中 */ struct page *next, *prev; /*前一个和下一个页 */ unsigned long index; /*页存放代码或数据所属文件的位移 */ struct inode *inode; /*该页所属文件的位移 */ atomic count; /*使用该页的进程数，0表示空闲 */ unsigned long age; /*页年龄 */ …… } - 21- */ 哈尔滨理工大学课程设计报告 2.4 流程图 本程序的流程图如图2所示 图2 程序流程图 2.5 以实例说明运行过程 当有进程到达时所用数据与指令存在于内存中时，根据分析，将不进行缺页中断，将 - 22- 哈尔滨理工大学课程设计报告 建立虚存区域，并执行do_mmap()，并返回起始地址。 实际运行结果如下： - 23- 因篇幅问题不能全部显示，请点此查看更多更全内容