CLOCK时钟置换算法

青岛理工大学操作系统课程设计报告院（系）：计算机工程学院专业：软件工程学生姓名:班级：学号:题目： 釆用CLOCK置换算法仿真请求分页系统 起迄日期：2012.7.62012.7.13 _ _设计地点:实验楼指导教师：20112012年度 第2学期完成日期： 2012年7月12日一、课程设计目的操作系统课程设计是为了对学习的操作系统课程更深刻的理解和巩固，对操作系统的整 体进行一个模拟。通过实践加深对各个部分的管理功能的认识，还能进一步分析各个部分之 间的联系，最后达到对完整系统的理解。同时，可以提高运用操作系统知识解决实际问题的 能力；锻炼实际的编程能力、创新能力及团队组织、协作开发软件的能力；还能提高调查研 究、查阅技术文献、资料以及编写软件设计文档的能力。课程设计是自己独立完成一项任务的过程，编程过程中要充分调动个人的积极性，提高 自身解决实际问题的能力，发现自身的编程错误习惯，提高编写程序的质量。同时，也为以 后深入层次的学习及研究打基础。编程中少不了难题，遇到难题时需要的是用程序员的思维方式去考虑问题解决问题，还 需要很大的精力和耐心，对于我们来说都是磨练和提高。二、课程设计内容与要求1、设计内容：用高级语言编写和调试一个内存分配程序，加深对内存分配算法的理解。2、设计要求：1）实现请求分页存储管理方式的页面置换算法：CLOCK算法2）内存物理块数固定为15个，对多个作业采用可变分配全局置换的策略分配物理块3）作业数量与作业大小（10-20页）可在界面进行设置4）所有作业按RR算法进行调度，时间片长度为1秒5）可为每个作业随机产生引用的页面串，也可以人工输入引用的页面串，页面串长度 50-100.要求必须包括作业所有的页面，可作为样例数据保存6）可读取样例数据（要求存放在外部文件中）进行作业数量、作业人小、页面串长度 的初始化7）要求采用可视化界面，模拟内存分配和使用情况图，可在运行过程中随时暂停，查 看当前内存物理块使用情况。8）每次全部作业运行结束后，要求打印出访问命中率三、系统分析与设计1、系统分析CLOCK页面置换算法是根据进程的实际需要，动态地为之分配内存空间。在实现可变分 区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这 样三个问题。为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分 配区的情况，为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为 把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分 配给该作业。在动态分区存储管理方式中，主要操作是分配内存和回收内存。（1）信息。本系统完成的是对作业数量不固定，作业大小、进入内存时间、运行时间需要通过 界面进行输入，或者从文件读取的作业基本信息，内存（15一20）的处理信息是 处理对于各种作业完成动态的内存分配，回收和紧凑。（2）行为。完全描述系统状态变化所需处理或功能； 本系统处理了 RR时间片轮转算法对内存的动态分配，每一个作业都是按照先 进先出的原则进入内存当地一个作业进入内存后，会长生一个时钟信号，依次 递增，当一个作业从进入时间开始到运行时间结束，会动态的释放所占人小的 内存区间，直到时钟信号等于最后一个作业释放他所占的内存区间，此时所有 的作业运行完，内存也回收完。(3) 表示。详细描述系统的对外接口与界面。本系统采用的VC编写的，在DOS界面下运行2、系统设计：系统利用RR时间片轮转算法掉调度作业，并从内存区动态分配内存。设内存区的人小为 number,表中每个空闲分区的大小可表示为nunber个。虚拟存储区采用page类型二维数组 实现，然后将虚拟存储区的首址返回给调用者。当进程运行完毕释放内存时，系统根据回收 区的首址，从内存区表中按CLOCK算法找到相应的插入点。2.1、模块设计：RR算法(next fit)(详见程序流程图)先将所有的进程排成一队，按先来先服务原则排列，先调度首进程按时间片轮转执行。 当执行到队尾时再从头执行，详细参看课本95页333节时间片轮转法改进型 CLOCK 算法(best fit/worst fit)根据页面的访问位A和修改位M确定调出页面执行四步循坏找出要置换页面，详细介 绍参看课本153页483节CLOCK置换算法虎拟存储区采用的page二维数组模拟内存区定义如下void MeinPageInut(uit number)/内存链headptr = new page ;tailpti- = headpti* ;fbr(mt i = 1 ; i next = new page ;tailpti* = tailptr-iiext ;if( i = (number-1)tailptr-next = NULL ;函数关系图2.2、数据结构说明：Strnct page数据对象j ob: page的作业号,int型。数据对象* next: page的后继指针。数据对象pagelD: page的页号,int型。数据对象A:访问码，int型。数据对象M:修改码int型。数据关系R：数据元素同属一个集合。基本操作P：MemPageIinit(int number)初始条件：指向new page headpti-指针操作结果：构造一个number人小的指针链。ProcessPageliiitO初始条件：i=PPAGENUMBERl, j=PPAGENUNIBER2 k小 page 类型的二维数组。 操作结果：数组各项赋初值。rr()初始条件：操作结果：各个作业按时间片轮转算法调度sleep( clock_t wait )初始条件：clock_t=1000操作结果：程序需坏一秒ClockReplace(page * paget)初始条件：指向要调入页指针paget操作结果：按CLOCK算法调换页面ShowPagel()初始条件：操作结果：显示内存调用情况。ReplacePage( page * prepti; page * ptrpage * paget )初始条件：指向要被替换掉页面指针的前序指针preptr,指向要被替换掉页面指针ptr, 指向要调入页指针paget paget操作结果：调换paget和ptr；程序中主要用到指针链表模拟内存区,2.3、算法流程图：函数关系图RR算法灯()及其调用函数sleepQVx作业数?j=pagesi;ITSleep：500)sleep(lOO)pagesi=i结束wait)1=9 Jj=?页尾sleep(clock tgoal clock()?i=0&j=Op = NULLj+;ShowPagel()ClockReplace(paget); ShowPagelQp-pageID=processpagei|jpageID;p = p-iiextj=?页尾CLOCK页面置换算法prepti* = headpti*; curptr = headpti*cuiptr-A = 0preptr = curptr;ciuptr = cuipti,-next;护falgM = 1falg_M = 0preptr = headptr;ciuptr = headptr 、四、系统测试与调试分析1、系统测试2、调试分析：进入程序输入1显示随机产生的多个作业的页面信息Liser 1ageII1：73827116卩1S 147410 ( 9 1111 :tl153 5 8 83811714 15315101314910I 2:8101714 13711S 1512 107154 1011? 31111 Ei 11195 3! 1214 1 92:113151 9 2! 153389000000000000000000000000 00000 0000000000000000000000000000000000 00000 0000000000000000000000000000000000 00000 0000000000000000000000000000000000 00000 000000000010 1213 4 912137 11413 69 1010 :215 :0127 1232141074410 155 5 14 9 5 11 1 4 6 14 6 14 11 15 8 2 12 3 12 4 1 6 12 8 13 4 8 9 4 15 9 15 113 4 9 6 15 13 15 14 4 14 9 3 9 2 2 900000000000000000000000000000000000030000000000000000000000000000000000000003000100000000000000000000000000000000000010000000000000000000000000000000000000000 0 0输入2开始执行CLOCK页面置换算法i：6j：3MeneryPageMenPgelD ：1 13 3 10 13 13 10 2 11 9 9 7 8 6 2p :110001000101101N :000100111011111i：6j：4MeneryPageMenPgelD ：113 1410 1313 102119 97862n :111001000101101M :000100111011111i：6j：5MeneryPageNenPgelD ：113 1410 1513 102119 97862n :111011000101101k :e00100111011111i：6j：61 13 3 11 13 12 1 140 0 0 1110 0 10 11n :000000000MenPgelD ：4 ? 12 4 15 13 13 A :111111100MeneryPageenPgelD ：4113 131105 6 3 11 13 12 1 140 0 0 1110 0 10 11M :000000000FlemeryFageHemPgelD ：12 6 7 10 4 12 10 10 5 14 3 1 13 4 1210110 11 1110 0 i：10j：770 0 1 1100 1111111p :0N :1i：llj：77 lleneryPage MenPgelD ：4 n :iM :1isllj：78 MeneryPage MenPgelD ：4 n :eN :1i：llj：7910 4 12110 00 0 1110 4 12110 00 0 1110 10 0 1010 110 100 1010 114 3 1 13 4 121111111014 3 1 13 4 12111111105 13 3 11 13 12 1 140 0 0 1 1 10 0 10 11eneryPageenPgelD ：4 7 12 4 15 13 13 n :111111111M :000000000MeneryPageMenPgelD ：4 7 12 4 15 13 13A :111111111785帘中率为 18 五、用户手册1、使用平台是什么？下载网址？使用的VC+平台2、是否需要安装？如需要安装，如何安装？不需要安装3、说明如何使用你编写的程序，详细列出每一步的具体操作步骤。这里可以有适当的运行 结果抓图。程序运行效果图105,781,11.000000US、六、程序清单void ProcessPagelnitO页面初始化引用串srand( (unsigiied)time( NULL );mt a;fbr( mt 1=0 ; i PPAGENUMBER1 ; 1 + )/PPAGENUMBER 为引用串数 for(mt j=0 ; j PPAGENUMBER2 ; j + ) a= raiid() % 15;a=a+l;/ printf(”a:%dH);processpageij.pageLD = a ;processpagei|j.A = 0 ; processpage 1 j .M = 0 ;processpagei j next=NULL;processpage ij.j ob=i;/ pnntfC-);/printf(,dsfds%oH?processpage0 0 .next);/ShowPageO ；void MeinPagelHiit(mt number)/内存链headpti* = new page ;tailptr = headpti* ;fbr(int 1 = 1 ; i iiext = new page ;tailptr = tailpti-next ;if( i = (number-1)tailpti-next = NULL ;void n clockO )/ pimtf(nonce %d %d0丄j);if(i=0&j=0)page * p ；p = headptr ;mt a;srand( (unsigiied)time( NULL );for( ； 1 ； J 卄)a= randO % 2;p-A = processpagefij.A ;p-M = a;p-pageID = processpageij.pageID ;p = p-next ;/ ShowPagel();if( p = NULL)break ;J+;ShowPagel();else/ pnntfCj%dm”j); paget=&processpage ij;ClockReplace(paget);ShowPagel();!f(1=ppAGENUMBER 1 -1 &j=PPAGENUMBER2 1) break;else if(j=PPAGENUMBER2-1) /pnntf(,19nn); break; /?J+； coutnext-iiext! =NULL) prepti-preptr-next; cui-ptr = headpti ;/prepti = tailptr ;while(l)if(paget-pageID = cuipti-pageID&paget-job = cuipti-job) /modify acess cuipti-A = 1 ;k+；break;elseif( (curptrA=falg_A)&(cmptr-M=falg_M)ReplacePage(preptr,cuiptipaget);1+;break ; if(falg_M = 1 ) /(2)curptr-A = 0 ;preptr = cuipti* ;ciuptr = cuipti-next ;if(curptr = NULL)if( falg_M = 0 )falg_M = 1 ; /(2)else falg_M = 0 ;preptr = headptr ;curptr = headptr ;void ReplacePage( page * prepti; page * pti;page * paget )/coutnhereH;page * temppti-;tempptr = ptr ;int a;srand( (unsigiied)time( NULL );a= randO % 2;if( ptr = headptr )paget iiext= headpti-next ; pti*=prepti-headptr = paget;else if( pti*-next = NULL )pti*=paget; preptr-iiext = paget ;elsepaget iiext= ptr-next ; preptr-iiext = paget ;processpagei j .A = 1;processpagefi |j .M = a;/ if(tempptr=NULL) piintf(MNULDiin); /free(temppti);void ShowPage()coutM*y Vendl ; coutnPageID: n;for(int 1=0 ；1PPAGENUNIBER1 ;i+)for(mt 尸0 ;jPPAGENUMBER2;j+) coutprocesspagei|j.pageIDn ”； coutendl ;coutHA :n;fbr(int it=0 ;itPPAGENUMBER2 ;it+)coutendl ;coutMM :n;fbr(int ic=O ;icpageIDH M ; ptr = pti-next ;ptr = headptr ;coutendl ;coutHA :H;while(pti* != NULL)coutpti-AH n ; ptr = pti-next ;ptr = headptr ;coutendl ;coutMM :while(pti* != NULL)coutpti-MM ; ptr = pti-next ;ptr = headptr ;coutendl ;mt mahi()ProcessPageInit();页而初始化MemPageIinit(;/内存初始化string strcmd ;int pageid ,a ,m ;coutvv”请输入命令:nendl ; coutMuser H;cmstirmd ;while (strcmd != ”exit”)if ( strcmd = HhelpH )coutH 命令 coutnsetpage功能 “vvendl ;:设置页面信息“vveiidl ;coutnshorpage :状态显示Hendl ;coutnreplace coutMexit:Clock 页面置换yvendl ;:退出程序nendl ;else if ( strcmd = T”)/ShowPageO ； ShowPagelO ;else if ( strcmd = H3n )/./RunMempageO ; itO；double z;z=100*k/(l+k); prmtff%d,%d,%fE,k 丄 z);/ ShowPagelO ；else if (stirmd = M2H)coutnplease mput PagelD.flag Alag M:nendl; cinpageidain ;SetPage( pageid , a , m ); elsecoutMmvalidation command,please mput :helpnendl ;coutHuser u; cinsti-cmd ; retum 0 ;七、体会与自我评价八、参考文献1 汤子瀛编著，计算机操作系统（修订版），西安电子科技人学出版社，2001年2 严蔚敏编著,数据结构（C语言版），清华大学出版社，2010年3 谭浩强编著,C程序设计（第三版），清华大学出版社，2009年4 黄维通，姚瑞霞-4sxial C+程序设计教程M.北京：机械工业出版社,2001.75 胡志坤.Visxial C+通信编程工程实例精解M.北京：机械工业出版社,2007.68-69九、课程设计评价（由任课教师填写）课 程 设 计 评教师:成绩: