基于时钟策略的页面置换.docx

操作系统综合实训项目设计文档【大纲】（不用打印，提交电子稿即可！）一、 基本信息项目名称:虚拟页式存储管理系统完成日期:2017/6/6二、 实验内容与目的实验目的：1.加深理解页式虚拟存储管理的概念和原理。2.掌握页式存储管理中存储分配（和回收）方法；3.深入了解页式虚拟存储管理中地址重定位（即地址映射）方法。4.深入理解段页式虚拟存储管理中缺页中断处理方法。实验内容：编写程序完成页式虚拟存储管理存储分配、地址重定位和缺页中断处理。1.为一个进程的内存申请分配内存，当一个进程（完成）结束时回收内存；2.对一个给定逻辑地址，判断其是否缺页，若不不缺页，则映射出其物理地址；3.若缺页则进行缺页中断处理。假定内存64K，内存块（页框）2K，进程逻辑地址空间最大128K。假设进程运行前未预先装入任何页。进程驻留集的大小固定为16 K，页面淘汰使用进程驻留集内的CLOCK策略。输出每次存储分配/回收时，内存自由块分布情况、相关进程的页表信息。三、 主要设计思路和流程图1.采用链表完成设计，主要设计两个链表，一个单链表，一个循环链表，其中单链表用于存放申请的页面，循环链表用来存放在驻留集中的页面2内存为64K，页面为2K，所以用了6*6的位示图表示内存情况3.申请页面时输入页表信息后，将位示图中对应的位置改为14.地址置换时，将逻辑地址除以页长，用商在页表中找到对应的块号，用余数加上块号乘以页长5.页面置换时，每次换进来的页面将其访问位置为1，下一个节点的时钟位置为1，本节点的时钟位置为0.若是遇到驻留集已经有的页面，则将此页面的访问为置为1.然后页面置换时，从时钟位开始遍历，直到遇到访问位为0的页面，将其置换出来6.撤销一个页面时，将其移出链表，并将位示图中对应的位置置为0四、 主要数据结构及其说明typedef struct node int page; int block; int flag;/是否在内存中 int state;/是否在驻留集中 int visit;/访问位 int n;/换进的标zhi struct node *next;LNode,*LinkList;int g55;/位示图;int Clock(LinkList L,LNode *p,LinkList H);/时钟调度LinkList Create()/创建页面void adr(LinkList L,LinkList Head)/地址转换LinkList CreateSet()/创建驻留集中的页面void Recy(LinkList L,int a55)/页面的回收五、 程序运行时的初值和运行结果 六、 源程序并附上注释【可是另一个源程序文件，在此应说明该文件名】#include#include#includetypedef struct node/定义页表 int page; int block; int flag;/是否在内存中 int state;/是否在驻留集中 int visit;/访问位 int n;/换进的标zhi struct node *next;LNode,*LinkList;int g55;/位示图;int Clock(LinkList L,LNode *p,LinkList H);/时钟算法LinkList Create()/建立存放页面的链表 LinkList head; LNode *r,*s; int p,b,f,n,i=0; r=head=(LinkList)malloc(sizeof(LNode); printf(输入申请的页数:); scanf(%d,&n); printf(n请分别输入页表的页号及块号（-1表示空）：n); printf(n页号 | 块号n); while(ipage=p; s-block=b; s-state=0; s-flag=1; s-visit=0; s-n=0; r-next=s; r=s; i+; if(r!=NULL)r-next=NULL; return head;void PrintfClock(LinkList L)/打印驻留集中的页面 LNode *p; p=L-next; int i=0; printf(页 面:); for(i=0;ipage!=-1) printf(%3d,p-page); p=p-next; printf(n访问位:); p=L-next; for(i=0;ipage!=-1) printf(%3d,p-visit); p=p-next; printf(n时 钟:); p=L-next; for(i=0;ipage!=-1) printf(%3d,p-n); p=p-next; void adr(LinkList L,LinkList Head)/地址转换算法 int ad,pd,pa,l,f=1,i=0; printf(输入逻辑地址:); scanf(%d,&ad); fflush(stdin); pa=ad/2048;/计算页号 l=ad%2048;/计算偏移量 LNode *p,*q; p=L-next; q=Head-next; while(p!=NULL) if(p-page=pa) if(p-state=0) printf(输入的逻辑地址对应的页号为:%dn,pa); printf(缺页中断n); printf(驻留集中的页面为:n); Clock(Head,p,L);/缺页中断，基于clock的页面置换策略 p-state=1; PrintfClock(Head); f=0; break; if(p-state=1) pd=(p-block)*2048+l; printf(输入的逻辑地址对应的页号为%d,块号为%d,偏移量为%dn,p-page,p-block,l); printf(物理地址为:%dn,pd); while(ipage=p-page) q-visit=1; p-visit=1; break; i+; q=q-next; PrintfClock(Head); f=0; break; p=p-next; if(f=1) printf(页号大于页表长度,越界中断);int Clock(LinkList L,LNode *p,LinkList H) LNode *q,*s,*r; q=L-next; r=L-next; s=H-next; int i=0,j=0; while(1) while(1)/当驻留集中没有页面时，直接将页面放入驻留集 if(q-page=-1) q-page=p-page; q-block=p-block; q-next-n=1; q-n=0; q-visit=1; return 0; q=q-next; i+; if(i=8) break; if(q-page!=-1)/驻留集已满 while(jn=1) break; q=q-next; j+; if(q-n=1) if(q-visit=0)/如果访问位为0，直接置换页面，并将置换出去的页面的state为置为0 while(s!=NULL) if(s-page=q-page) s-state=0; break; s=s-next; q-page=p-page;/置换时将置换进来的页面的时钟位置为0，将此页面的下一个页面的时钟位置为1 q-block=p-block; q-next-n=1; q-n=0; q-visit=1; return 0; else while(q-visit!=0) q-visit=0; q-n=0; q=q-next; while(s!=NULL) if(s-page=q-page) s-state=0; break; s=s-next; q-page=p-page;/置换时将置换进来的页面的时钟位置为0，将此页面的下一个页面的时钟位置为1 q-block=p-block; q-next-n=1; q-n=0; q-visit=1; return 0; LinkList CreateSet()/用循环链表来表示驻留集中的页面 LinkList L; LNode *r,*s; int i=0; r=L=(LinkList)malloc(sizeof(LNode); while(ipage=-1; s-block=-1; s-state=1; s-flag=1; s-visit=0; s-n=0; r-next=s; r=s; i+; if(r!=NULL)r-next=L-next; return L;void PrintfGraph(int num55)/打印位示图 int i=0,j=0; printf(位示图为:n); printf( ); for(i=0;i6;i+) printf(%d ,i); printf(n); for(i=0;i6;i+)printf(%d,i);for(j=0;jnext; q=L; while(p!=NULL) if(p-page=num) if(p-state=1) printf(该进程正在运行中不可回收); else if(p-next=NULL) q-next=NULL; a(p-block-1)/6(p-block-1)%6=0; break; q-next=p-next; x=p; p=p-next; free(x); a(p-block-1)/6(p-block-1)%6=0; q=q-next; p=p-next; void ChangeGraph(LinkList L,int a55)/当内存被使用或者释放时，改变位示图的相应位置 LNode *p; p=L-next; int col,row; while(p!=NULL) row=(p-block-1)/6; col=(p-block-1)%6; arowcol=1; p=p-next; void Init(int a55)/初始化位示图 int i,j; for(i=0;i6;i+) for(j=0;jnext; printf(页号t物理块号t状态位n); while(p!=NULL) printf(%dt,p-page); printf(%dtt,p-block); printf(%dt,p-state); printf(n); p=p-next; void InitList(LinkList *L)*L=(LinkList)malloc(sizeof(LNode);(*L)-next=NULL;int main() LinkList h,H; char c; InitList(&h); InitList(&H); Init(g); H=CreateSet(); printf(*); printf(n*页式虚拟存储管理系统*n); printf(*n); printf(*菜单*n); printf(1.显示内存分配情况 2.申请内存 3.打印页表 4.回收内存