CLOCK时钟置换算法

1、青岛理工大学操作系统课程设计报告院（系）：计算机工程学院专业：软件工程学生姓名:班级：学号:题目：釆用CLOCK置换算法仿真请求分页系统起迄日期：2012.7.62012.7.13_设计地点:实验楼指导教师：20112012年度第2学期完成日期：2012年7月12日一、课程设计目的操作系统课程设计是为了对学习的操作系统课程更深刻的理解和巩固，对操作系统的整体进行一个模拟。通过实践加深对各个部分的管理功能的认识，还能进一步分析各个部分之间的联系，最后达到对完整系统的理解。同时，可以提高运用操作系统知识解决实际问题的能力；锻炼实际的编程能力、创新能力及团队组织、协作开发软件的能力；还能提高调查研究

2、、查阅技术文献、资料以及编写软件设计文档的能力。课程设计是自己独立完成一项任务的过程，编程过程中要充分调动个人的枳极性，提高自身解决实际问题的能力，发现自身的编程错误习惯，提高编写程序的质量。同时，也为以后深入层次的学习及研究打基础。编程中少不了难题，遇到难题时需要的是用程序员的思维方式去考虑问题解决问题，还需要很大的精力和耐心，对于我们来说都是磨练和提高。二、课程设计内容与要求1、设计内容：用高级语言编写和调试一个内存分配程序，加深对内存分配算法的理解。2、设计要求：1）实现请求分页存储管理方式的页面置换算法：CLOCK算法2）内存物理块数固定为15个，对多个作业采用可变分配全局置换的策略分

3、配物理块3）作业数量与作业大小（10-20页）可在界面进行设置4）所有作业按RR算法进行调度，时间片长度为1秒5）可为每个作业随机产生引用的页面串，也可以人工输入引用的页面串，页面串长度50-100,要求必须包拾作业所有的页面，可作为样例数据保存6）可读取样例数据（要求存放在外部文件中）进行作业数量、作业大小、页面串长度的初始化7）要求采用可视化界面，模拟内存分配和使用情况图，可在运行过程中随时暂停，查看当前内存物理块使用情况。8）每次全部作业运行结束后，要求打印出访问命中率三、系统分析与设计1、系统分析CLOCK页面置换算法是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，

4、将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。在动态分区存储管理方式中，主要操作是分配内存和回收内存。（1）信息。本系统完成的是对作业数量不固定，作业人小、进入内存时间、运行时间需要通过界面进行输入，或者从文件读取的作业基本信息，内存（15一20）的处理信息是处理对于各种作业完成动态的内存分配，回收和紧凑。（2）行为。完全

5、描述系统状态变化所需处理或功能；本系统处理了RR时间片轮转算法对内存的动态分配，每一个作业都是按照先进先出的原则进入内存当地一个作业进入内存后，会长生一个时钟信号，依次递增，当一个作业从进入时间开始到运行时间结束，会动态的释放所占人小的内存区间，直到时钟信号等于最后一个作业释放他所占的内存区间，此时所有的作业运行完，内存也回收完。表示。详细描述系统的对外接口与界面。本系统采用的VC编写的，在DOS界面下运行2、系统设计：系统利用RR时间片轮转算法掉调度作业，并从内存区动态分配内存。设内存区的人小为number,表中每个空闲分区的人小可表示为nunber个。虚拟存储区采用page类型二维数组实现

6、，然后将虚拟存储区的首址返回给调用者。当进程运行完毕释放内存时，系统根据回收区的首址，从内存区表中按CLOCK算法找到相应的插入点。2.1、模块设计：RR算法(nextfit)(详见程序流程图)先将所有的进程排成一队，按先来先服务原则排列，先调度首进程按时间片轮转执行。当执行到队尾时再从头执行，详细参看课本95页333节时间片轮转法改进型CLOCK算法(bestfit/worstfit)根据页面的访问位A和修改位M确定调出页面执行四步循坏找出要置换页面，详细介绍参看课本153页483节CLOCK置换算法虎拟存储区采用的page二维数组模拟内存区定义如卜voidMeinPageInut(mtnu

7、mber)/内存链headptr=newpage;tailpti-=headpti*;fbr(mti=1;inext=newpage;tailpti*=tailptr-iiext;if(i=(number-1)tailptr-next=NULL;MemPageIinit(intnumber)虚拟存储区2ProcessPagelnitO*MemPageIinit(intnumber)虚拟存储区2ProcessPagelnitO*函数关系图2.2、数据结构说明：Strnctpage数据对象job:page的作业号,int型。数据对象*next:page的后继指针。数据对象pagelD:page的页

8、号,int型。数据对象A:访问码，int型。数据对象M:修改码int型。数据关系R：数据元素同属一个集合。基本操作P：MemPageIinit(intnumber)初始条件：指向newpageheadpti-指针操作结果：构造一个number大小的指针链。ProcessPageliiitO初始条件：i=PPAGENUMBERl,尸PPAGENUMBER2人小page类型的二维数组。操作结果：数组各项赋初值。rr()初始条件：操作结果：各个作业按时间片轮转算法调度sleep(clock_twait)初始条件：clock_t=1000操作结果：程序補坏一秒ClockReplace(page*pag

9、et)初始条件：指向要调入页指针paget操作结果：按CLOCK算法调换页面ShowPagel()初始条件：操作结果：显示内存调用情况。ReplacePage(page*prepti;page*ptrpage*paget)初始条件：指向要被替换掉页面指针的前序指针preptr,指向要被替换掉页面指针ptr,指向要调入页指针pagetpaget操作结果：调换paget和ptr；程序中主要用到指针链表模拟内存区,2.3、算法流程图：函数关系图RR算法灯()及其调用函数sleepQitVx作业数?j=pagesi;Sleep：500)sleep(lOO)pagesi=i1=9J结束goalclock

10、()?wait)j=?页尾sleep(clockti=0&j=Op=NULLj+;ShowPagel()ClockReplace(paget);ShowPagelQp-pageID=processpageijpageID;p=p-iiext尸？页尾CLOCK页面置换算法prepti*=headpti;cuipti*=headptifReplacePage(prepti;ciuptr,paget)fReplacePage(prepti;ciuptr,paget)cuiptr-A=0preptr=curptr;ciuptr=cuq)fr-next;、声四、系统测试与调试分析1、系统测试2、调试分析

11、：进入程序输入1显示随机产生的多个作业的页面信息f冃才刖丿、口卩V：wser1：6j：3eneryPageenPgelD：1:1:0133101000011313100110211：6j：3eneryPageenPgelD：1:1:013310100001131310011021111978621111i：6j：4MeneryPageMenPgelD：1A:1M:01314110001101301000113100011101199786211011111i：6j：5MeneryPageMenPgelD：1K：1:0131411000110151100011310001110119978621

12、1011111XXXXXXXXX口口卄口口口XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXHXXXXXXXXXXXXXXPageID：7382?116191474106911111115358838117141531!101314910l2:81017141371191512107154101173111151119L5312141.9211315192!1L53389n:00000000000000000000000000000000000030000000000000000000000000000000000000003000M:000000000000000000

13、0000000000000000003000000000000000000000000000000000000000300031012134I912137114136S10101215101271232141074410155Ei1495111461461411158212312416128134894159151134961L5131514414939229000000000000000000000000000000000000000000000000000000000000000000000000000000:0000000000000000000000000000000000000000

14、00000000000000000000000000000000000000输入2开始执行CLOCK页面置换算法i：6J：6MenPgelD：47124151313113-I111312114A:1111111000001111:000000000001011i：llj：76MeneryPage1enPgeID：4?12415131351313111312114A:1111111100001111:000000000001011i：llj：77MeneryPageMenPgelD：471241513135631111312114A:1111111110001111:00000000000101

15、1i：llj：78MeneryPage1enPgeID：47124151313563111312114A:1111111110001111:000000000001011i：llj：79785命中率为1.8000000us五、用户手册1、使用平台是什么？下载网址？使用的VC卄平台2、是否需要安装？如需要安装，如何安装？不需要安装3、说明如何使用你编写的程序，详细列出每一步的具体操作步骤。这里可以有适当的运行结果抓图。程序运行效果图neneFyPageMenPgelD：12671041210105143113412A:110110001011111M:111001110111110i：10j：7

16、7MeneryPageMenPgelD：12(i、1041210105J143113412A:001110001011111N:111001110111110i：llj：77IMeneryPageMenPgelD：4691041210105143i113412b=101110001011111h=111001110111110IMeneryPageMenPgelD：4691041210105143i113412A:011110001011111M:111001110111110i：llj：79-M-105,781,11.000000US、六、程序清单voidProcessPagelnitO页面

17、初始化引用串srand(unsigiied)time(NULL);mta;fbr(mt1=0;iPPAGENUMBER1;1+)/PPAGENUMBER为引用串数for(mtj=0;jPPAGENUMBER2;j+)a=rand()%15;a=a+l;/printf(na:%da);processpageij.pageLD=a;processpage1j.A=0;processpage1j.M=0;processpage1jnext=NULL;processpageij.job=i;/pnntf(nnn);/printf(,dsfds%o,processpage00.next);/ShowPa

18、geO；voidMemPageIuut(mtnumber)/内存链headpti*=newpage;tailptr=headpti;fbr(int1=1;iiiext=newpage;tailptr=tailpti-next;if(i=(number-1)tailpti-next=NULL;voidnclockO)/piiiitf(nonce%d%dir,ij);if(i=0&j=0)page*p;p=headptr;mta;srand(unsigiied)time(NULL);for(；1；J卄)a=randO%2;p-A=processpagei|j.A;p-M=a;p-pageID=pr

19、ocesspageij.pagelD;p=p-next;/ShowPagel();if(p=NULL)break;J+;ShowPagel();else/pnntfCj%dWj);paget=&processpageij;ClockReplace(paget);ShowPagel();1f(1=ppAGENUMBERl-1&j=PPAGENUMBER21)break;elseif(j=pPAGENUMBER2-1)/pnntf(,19nM);break;/?J+；coutnext-iiext!=NULL)preptr=preptr-next;cui-ptr=headpti*;/prepti*=

20、tailptr;while(l)if(paget-pageID=cuipti-pageID&paget-job=cuipti-job)/modifyacesscuipti-A=1;k+；break;elseif(curptr-A=falg_A)&(ciuptr-M=falg_M)ReplacePage(prepticuiptipaget);1+;break;if(falg_M=1)/(2)curptr-A=0;preptr=cuipti*;ciuptr=cuipti-next;f(curptr=NULL)if(falg_M=0)falg_M=1;/(2)elsefalg_M=0;preptr=

21、headptr;curptr=headptr;voidReplacePage(page*prepti;page*pti;page*paget)/coutnheren;page*temppti-;tempptr=ptr;coutprocesspageiit.Acoutprocesspageiit.AHM;inta;srand(unsigiied)time(NULL);a=randO%2;if(ptr=headptr)pagetnext=headpti-next;pti*=prepti-headptr=paget;elseif(pti*-next=NULL)ptr=paget;preptr-iie

22、xt=paget;elsepagetnext=ptr-next;preptr-iiext=paget;processpagei|j.A=1;processpagefi|j.M=a;/if(tempptr=NULL)priiitf(HNULDun);/free(temppti);voidShowPage()coutM*Hendl;coutnPageID:n;for(mt1=0;iPPAGENUMBERl;i+)for(mt尸0;jPPAGENUMBER2;j+)coutprocesspagei|j.pageIDn”；coutendl;coutHA:n;fbr(intit=0;itPPAGENUM

23、BER2;it+)coutendl;coutMM:n;fbr(iiitic=O;icpageIDHn;ptr=pti-next;ptr=headptr;coutendl;coutHA:H;while(pti*!=NULL)coutpti-AHn;ptr=pti-next;ptr=headptr;coutendl;coutMM:while(pti*!=NULL)coutpti-MMn;ptr=pti-next;ptr=headptr;coutendl;intmam()coutprocesspageiit.Acoutprocesspageiit.AHM;ProcessPageInit();页面初始化MeinPageI