操作系统课程设计-通用请求分页调度算法演示程序.doc

东莞理工学院城市学院计算机操作系统课程设计题目：通用请求分页调度算法演示程序 专业： 软件工程 年级： 2012级3班 小组成员： 指导教师： 时间： 2014.12.242014.12.26 地点： 东莞理工学院城市学院计算机与信息科学系制2014年 12 月摘要操作系统是管理计算机系统的全部硬件资源包括软件资源及数据资源，控制程序运行改善人机界面，为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用，为用户提供方便的、有效的、友善的服务界面。操作系统是一个庞大的管理控制程序，大致包括4个方面的管理功能：处理机管理、存储管理、设备管理、文件管理。在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。本次课程设计应用的页面调度算法有先进先出的算法（FIFO）、最佳置换算法（OPT）、近期最久未使用算法（LRU）、近期最少使用算法（LFU）、CLOCK置换算法目录1. 概述42. 课程设计任务及要求52.1 设计任务52.2 设计要求53. 算法及数据结构73.1算法的总体思想（流程）73.2 FIFO模块103.2.1 功能103.2.2 数据结构103.2.3 算法103.3 OPT模块113.3.1功能113.3.2 数据结构113.3.3算法113.4 LRU模块123.4.1功能123.4.2 数据结构123.4.3算法123.5 LFU模块133.5.1功能133.5.2 数据结构133.5.3算法133.6 CLOCK置换算法 模块143.6.1功能143.6.2 数据结构143.6.3算法154. 程序设计与实现164.1 程序流程图164.2 程序代码（要注释）164.3 实验结果205. 结论236. 收获、体会和建议。247. 参考文献。251.概述在存储器管理方式中，有一个特点，就是当要求作业全部装入内存才能运行。但是这样存在两种情况：有的作业很大，不能全部装入内存，致使作业无法运行。有大量作业要求运行时，内存容量不足容纳所有的作业，而虚拟内存技术正是在逻辑上扩充内存容量，将会解决以上的两个问题。所以，当进程开始运行时，先一部分程序装入内存，另一部分暂时留在外存；当没有足够的内存空间时系统自动选择部分内存空间，将其中原来的内容交换到磁盘上，并释放这些内存空间供其它进程使用。通常，把选择换出页面的算法称为页面置换算法，模拟页面置换算法用以客观解决内存不足的矛盾.2. 课程设计任务及要求2.1 设计任务2.1.1了解linux的命令及使用格式，熟悉linux的常用基本命令，练习并掌握linux提供的gedit编辑器来编译c(c+)程序，学会利用gcc(g+)编译、调试c(c+)程序。2.1.2设计一个虚拟存储区和内存工作区，并使用先进先出的算法（FIFO）、最佳置换算法（OPT）、近期最久未使用算法（LRU）、近期最少使用算法（LFU）、CLOCK置换算法计算命中率。（命中率=缺页数/页地址流长度*100%）2.1.3分工：时间组员任务完成情况12.24张乔粤、丁就平了解设计需求；了解各算法的设计思想；良好12.25张乔粤、丁就平依照设计要的需求编写各算法的代码。良好12.26张乔粤、丁就平丁就平画程序流程图以及各算法的思想流程图，整理文档，作好测试；张乔粤继续完善代码；良好2.2 设计要求1)演示实现下列五种请求分页存储管理方式的页面置换算法：l先进先出的算法（FIFO）l最佳置换算法（OPT）l近期最久未使用算法（LRU）l近期最少使用算法（LFU）lCLOCK置换算法2)内存物理块数固定为3个，对多个作业采用固定分配局部置换的策略分配物理块3)作业数量与作业大小（10-20页）可在界面进行设置4)所有作业按RR算法进行调度，时间片长度为1秒5)可为每个作业随机产生引用的页面串，也可以人工输入引用的页面串，页面串长度50-100，要求必须包括作业所有的页面，可作为样例数据保存6)可读取样例数据（要求存放在外部文件中）进行作业数量、作业大小、页面串长度的初始化7)要求对每种算法采用可视化界面，模拟内存分配和使用情况图，可在运行过程中随时暂停，查看当前内存物理块使用情况。有性能比较功能，可比较同一组数据在不同页面置换算法下的命中率3. 算法及数据结构3.1算法的总体思想（流程）选择页面置换算法。先输入所有的页面号（可随机产生），为系统分配物理块，依次进行置换：3.2 FIFO模块3.2.1 功能调用该算法实现页面置换调度3.2.2 数据结构数组：定义了Memery、time、temp、page。数组memery规定物理块中的页号；数组time记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面；temp记录page数组的页面串号在运行过程中进行置换后得出在页面号在物理块被置换的结果；3.2.3 算法/*先进先出页面置换算法*/void FIFO()int memery15=-1;/*物理块数组*/int time15=0; /*记录进入物理块的时间*/ int i,j,k,m,z;/*局部变量*/int max=0; /*记录换出*/ int count1=0; /*记录置换次数变量1*/*修改*/int count=0; /*记录置换次数变量2*/int jungle = 0;/*物理块是否置换的标记*/*修改*/int wulikuai=0;/*记录前三个物理块进入页面数*/*前三个页面字符串置换的算法*/for(i=0;imSIZE;i+)for(z=0;zi;z+)if(memeryz=pagei) jungle=1;break;/*判断进入物理块的页面字符串与已进入物理块数组的页面是否相同*/if(jungle=0)/*不相同时 进行插入*/memerywulikuai=pagei;/*页面字符串数组插入到物理块数组中*/count1+;/*记录前三个物理块的置换次数*/wulikuai+;/*记录已经进入物理块数组的页面数*/timei=wulikuai;/*记录物理块的时间*/if(i=mSIZE-1&wulikuai!=3)memeryi=-1;/*判断物理块为第三块并且物理块数组被用数不为3时，使未满的物理块数组其它组员为-1*/elsememeryi=-1;/*相同时候 不进行重复插入*/*将物理块数组插入辅助数组中*/for(j=0;jmSIZE;j+)tempij=memeryj;/*将物理块数组插入到辅助数组中*/jungle=0;/*使得页面插入标志置为0*/*后3个页面字符串的置换算法*/for(i=mSIZE;ipSIZE;i+)/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)if(memeryj!=pagei) /*处理msize块未满的if(memeryj!=pagei&memeryj!=-1) */k+;/else if(memeryj!=pagei&memeryj=-1&count1!=mSIZE) memeryj=pagei; time2=i;count+;if(k=mSIZE) /*如果不在物理块中*/count+;/*换出页面次数+1*/*计算换出页*/max=time0time1?0:1;/*判断记录访问时间值的大小 真则为0 假为1 赋予记录换出的变量*/for(m=2;mmSIZE;m+)if(timemtimemax)max=m;memerymax=pagei;/*页面字符串数组插入到物理块数组中*/timemax=i; /*记录该页进入物理块的时间*/ /*将物理块数组插入辅助数组中*/for(j=0;jmSIZE;j+)tempij=memeryj;else/*将物理块数组插入辅助数组中*/for(j=0;jmSIZE;j+)tempij=memeryj;/*物理块数组插入到辅助数组中*/compute();/*计算过程延迟输出*/print(count,count1);/*输出结果函数*/3.3 OPT模块3.3.1功能调用该算法实现页面置换调度3.3.2 数据结构数组：定义了memery，next，temp，page数组。数组pagepSIZE存储页面号序列，memerymSIZE是存储装入物理块中的页面。数组nextmSIZE记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。3.3.3算法/*最佳置换算法*/void OPT() int jungle = 0;/*置换标记*/int count1=0; /*记录置换次数*/int memery15=-1;/*物理块数组*/int next10=0; /*记录下一次访问时间*/ int i,j,k,l,m,z;/*局部变量*/int max; /*记录换出页*/int count=0; /*记录置换次数*/int wulikuai=0;/*记录进入物理块数*/for(i=0;imSIZE;i+)for(z=0;zi;z+)if(memeryz=pagei) jungle=1;break;if(jungle=0) memerywulikuai=pagei;/*页面字符串数组插入到物理块数组中*/count1+;/*记录前三个物理块的置换次数*/wulikuai+;/*记录已经进入物理块数组的页面数*/if(i=mSIZE-1&wulikuai!=3)memeryi=-1;elsememeryi=-1;/*修改*/for(j=0;jmSIZE;j+)tempij=memeryj;/*物理块数组插入到辅助数组中*/jungle=0;/*for(i=0;imSIZE;i+)memeryi=pagei;/*页面字符串数组插入到物理块数组中*/ for(j=0;jmSIZE;j+)tempij=memeryj;/*物理块数组插入到辅助数组中*/*/for(i=mSIZE;ipSIZE;i+)/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)if(memeryj!=pagei) /if(memeryj!=pagei&memeryj!=-1)k+;/else if(memeryj!=pagei&memeryj=-1&count1!=mSIZE) memeryj=pagei;count+;if(k=mSIZE) /*如果不在物理块中*/ count+;/*得到物理快中各页下一次访问时间*/ for(m=0;mmSIZE;m+) for(l=i+1;l=next1?0:1; for(m=2;mnextmax) max=m;/*下一次访问时间都为pSIZE,则置换物理块中第一个*/ memerymax=pagei; for(j=0;jmSIZE;j+) tempij=memeryj; /*物理块数组插入到辅助数组中*/else for(j=0;jmSIZE;j+) tempij=memeryj;/*物理块数组插入到辅助数组中*/ compute(); /*计算过程延迟输出*/print(count,count1);/*输出结果函数*/ 3.4 LRU模块3.4.1功能调用该算法实现页面置换调度3.4.2 数据结构数组：定义了memery、flag、page、temp数组。数组pagepSIZE存储页面号序列，memerymSIZE是存储装入物理块中的页面。数组flagmSIZE记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。3.4.3算法/*最近最久未使用置换算法*/void LRU()int memery15=0;/*物理块数组*/int flag10=0; /*记录页面的访问时间*/int i,j,k,m;/*局部变量*/int max=0; /*记录换出页*/int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/for(i=0;imSIZE;i+)memeryi=pagei;/*页面字符串数组插入到物理块数组中*/flagi=i;for(j=0;jmSIZE;j+)tempij=memeryj;for(i=mSIZE;ipSIZE;i+)/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)if(memeryj!=pagei)k+;elseflagj=i; /*刷新该页的访问时间*/ if(k=mSIZE) /*如果不在物理块中*/count+;/*记录置换次数变量+1*/*计算换出页*/max=flag0flag1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)/*换出页的访问时间大于待插入的页面 则记录换出页的数组序号*/max=m;memerymax=pagei;/*将页面字符串数组插入到物理块数组中*/flagmax=i; /*记录该页的访问时间*/ for(j=0;jmSIZE;j+)tempij=memeryj;/*物理块数组插入到辅助数组中*/elsefor(j=0;jmSIZE;j+)tempij=memeryj;/*物理块数组插入到辅助数组中*/compute();/*计算过程延迟输出*/print(0,count);/*输出结果函数*/3.5 LFU模块3.5.1功能调用该算法实现页面置换调度3.5.2 数据结构数组：定义了memery、flag、page、temp数组。flag数组是一个计数器，记录页面的访问时间。用一维数组pagepSIZE存储页面号序列，memerymSIZE是存储装入物理块中的页面。 当要调用的页在内存帧中时，调用该页，修改该页的flag值；若要调用的页不在内存帧中，选择page中引用次数最少的页进行置换，同时将该页的flag值更新为该页的i值。依次进行，直到引用页序列为空。3.5.3算法/*最少使用页面算法（LFU）*/void LFU() int jungle = 0;/*置换标记*/ int count1=0; /*记录前物理块数的页面置换次数*/ int memery15=-1;/*物理块数组*/ int flag10=0; /*记录页面的访问时间*/ int i,j,k,m,z;/*局部变量*/ int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/int wulikuai=0;/*记录进入物理块数*/for(i=0;imSIZE;i+)for(z=0;zi;z+)if(memeryz=pagei) jungle=1;break;if(jungle=0)memerywulikuai=pagei;/*页面字符串数组插入到物理块数组中*/count1+;/*记录前三个物理块的置换次数*/wulikuai+;/*记录已经进入物理块数组的页面数*/flagi=wulikuai;/*记录访问时间*/if(i=mSIZE-1&wulikuai!=3)memeryi=-1;elsememeryi=-1;/*修改*/for(j=0;jmSIZE;j+)tempij=memeryj;/*物理块数组插入到辅助数组中*/jungle=0; /*for(i=0;imSIZE;i+) memeryi=pagei;/*页面字符串数组插入到物理块数组中*/flagi=i;for(j=0;jmSIZE;j+)tempij=memeryj;/*物理块数组插入到辅助数组中*/*/ for(i=mSIZE;ipSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) /*if(memeryj!=pagei&memeryj!=-1)*/ k+;/*else if(memeryj!=pagei&memeryj=-1&count1!=mSIZE) memeryj=pagei;count+;*/ if(k=mSIZE) /*如果不在物理块中*/ count+;/*计算换出页*/ max=flag0flag1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)max=m;memerymax=pagei;/*页面字符串数组插入到物理块数组中*/flagmax=0; /*记录该页进入物理块的时间*/for(j=0;jmSIZE;j+)tempij=memeryj;/*物理块数组插入到辅助数组中*/ else for(j=0;jmSIZE;j+)tempij=memeryj;/*物理块数组插入到辅助数组中*/ compute();/*计算过程延迟输出*/print(count,count1);/*输出结果函数*/3.6 CLOCK置换算法 模块3.6.1功能调用该算法实现页面置换调度3.6.2 数据结构当某一页首次装入内存中时，则将该页框的使用位设置为1；当该页随后被访问到时（在访问产生缺页中断之后），它的使用位也会被设置为1。对于页面置换算法，用于置换算法，用于置换的候选页框集合（当前进程：局部范围；整个内存；全局范围）被看做是一个循环缓冲区，并且有一个指针与之相关联。当一页被置换时，该指针被设置成指向缓冲区中的下一页框。当需要置换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一页框。每当遇到一个使用位为1的页框时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有页框的使用位均为0时，则选择遇到的第一个页框置换；如果所有页框的使用位均为1时，则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，置换该页框中的页。 3.6.3算法/简单Clock置换算法void CLOCK(int num) int j; if(inblock(num) /printf(命中!n); lost+;/*记录命中的次数*/ for(int i=0;imSIZE;i+) if(memery i= -1) printf(| | ); else printf(|%d| ,memery i); printf(t); else if(count = mSIZE) /lost+; for(j=0;jmSIZE; ) if(statej = 0) break; else statej = 0; j+; j = j%3; memeryj = pagenum; statej = 1; for(int i=0;imSIZE;i+) if(memery i= -1) printf(| | ); else printf(|%d| ,memery i); printf(t); else memerycount = pagenum; count+; for(int i=0;imSIZE;i+) if(memery i= -1) printf(| | ); else printf(|%d| ,memery i); printf(t); 4. 程序设计与实现4.1 程序流程图图1主程序流程图4.2 程序代码（要注释）/*头文件*/#include #include #include #include #include #include #include #include #include #include #include #define N 20 /虚拟内存尺寸/*全局变量*/int count1=0; /*前msize的页面置换次数*/ /-修改-int mSIZE=3; /*物理块数*/int pSIZE; /*页面号引用串个数*/static int memery15=-1; /*物理块中的页号*/static int page100=-1; /*页面号引用串*/static int temp10015=-1; /*辅助数组*/using namespace std; int P; /int const blockCount=3; /内存中的物理块数int count = 0; /int blockblockCount; /物理块数组/int const PageCount=15;/总的页面数/int Page100; /页面字符串数组int state3;/clock置换算法中，内存中的每个页面号对应的状态double lost= 0.0; /记录命中次数 /*置换算法函数*/void FIFO();/先来先服务算法void LRU();/近期最久未使用算法void OPT();/最佳置换算法void LFU();/近期最少使用算法void CLOCK(int num);/clock算法/*辅助函数*/void print(unsigned int t,int t1);/*输出结果的函数（辅助数组结果）*/void designBy();/*显示程序信息*/void download();/*载入数据*/void mDelay(unsigned int Delay);/*设置延迟*/int getRand(int start, int end);/产生从start到end范围内的随机数bool change();/用于clock判断页面是否已经被修改bool inblock(int num);/用于clock检测页号是否在内存中void SaveFile();/*保存数据*/void OpenFile();/*打开数据文件*/*主函数*/void main()int i,k,code;char jungle;system(color 0A);designBy();printf(请按任意键进行初始化操作.n); printf( );getchar();system(cls);/*输出结果清屏*/system(color 0B);/*输出结果字体颜色变化*/fflush(stdin);printf(请选择是否手动录入页面号引用串？(y/n);scanf(%c, &jungle);if(toupper(jungle) = N) srand( (unsigned int)time(NULL) );printf(请输入页面号引用串的个数(P=100)：);scanf(%d,&pSIZE);/*自动生成页面字符串*/for(i=0;ipSIZE;i+)pagei = rand() % 10;printf(正在随机产生页面号引用串。);/*自动生成页面字符串*/for(i=0;i);printf(n); else printf(请输入页面号引用串的个数(P=100)printf(您输入页面号引用串的个数应少于100,请按任意键重新输入);getchar();getchar();printf(n);printf(请输入页面号引用串的个数(P=100)：);scanf(%d,&pSIZE);puts(请依次输入页面号引用串(连续输入，无需隔开)：);/*手动输入页面字符串*/for(i=0;ipSIZE;i+)scanf(%1d,&pagei);download();/*载入数据*/system(cls);/*输出结果清屏*/system(color 0E);/*输出结果字体颜色变化*/puts(输入的页面号引用串为：);/*输出生成的页面字符串*/for(k=0;k=(pSIZE-1)/20;k+)for(i=20*k;(ipSIZE)&(i20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&(i=pSIZE-1)printf(%dn,pagei);elseprintf(%d ,pagei);/*输出生成的页面字符串*/*显示主界面*/doprintf(* * * * * * * * * * * * * *请选择页面置换算法:* * * * * * * * * * * * *n);printf(* - *n);printf(* 1.先进先出(FIFO) 2.最佳置换算法（OPT）3.近期最久未使用算法（LRU） *n);printf(* 4.近期最少使用算法（LFU） 5.退出 6.保存数据 7.读入数据 *n); printf(* - *n);printf(* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *n);printf(请选择操作： bb);scanf(%d,&code);switch(code)case 1:FIFO();break;case 2:OPT();break;case 3:LRU();break;case 4:LFU();break;case 5:int z=0;/*输出结果换行标志*/lost=0; /记录命中次数count=0; for(int m=0;mmSIZE;m+) statem = 0; for(int j=0;jmSIZE;j+) memeryj=-1; for(int i=0;i);getchar();system(cls);/*输出结果清屏*/while (code!=6);getchar();getchar();4.3 实验结果5. 结论 在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。 页面置换算法是操作系统中对虚拟存储技术中必不可少的一种置换算法，这次通过对先进先出的算法（FIFO）、最佳置换算法（OPT）、近期最久未使用算法（LRU）、近期最少使用算法（LFU）、CLOCK置换算法通过编程对其加深了了解，但是在这次的课程设计中，仍然存在些不足，第一：在每种页面置换算法代码设计时，当前3个页面串有相同的时候，应该有所判断，待插入的页面字符串与物理块存在的页面相同时，不应继续插入，否则实验结果会与理论的结果有所出入。第二：页面置换算法采用的数据结构不是很好，大部分采用数组来实现页面置换，与理论知识的算法所需的数据结构有所出入。第三：clock算法的输出界面与前面的四个算法的不和谐；第四：FIFO算法存在置换页面出错问题；理论知识是算法设计的一个思路，但是用代码实现仍需