基于时钟策略的页面置换(共20页)

1、精选优质文档-倾情为你奉上操作系统综合实训项目设计文档【大纲】（不用打印，提交电子稿即可！）一、 基本信息项目名称:虚拟页式存储管理系统完成日期:2017/6/6二、 实验内容与目的实验目的：1.加深理解页式虚拟存储管理的概念和原理。2.掌握页式存储管理中存储分配（和回收）方法；3.深入了解页式虚拟存储管理中地址重定位（即地址映射）方法。4.深入理解段页式虚拟存储管理中缺页中断处理方法。实验内容：编写程序完成页式虚拟存储管理存储分配、地址重定位和缺页中断处理。1.为一个进程的内存申请分配内存，当一个进程（完成）结束时回收内存；2.对一个给定逻辑地址，判断其是否缺页，若不不缺页，则映射出其物理地

2、址；3.若缺页则进行缺页中断处理。假定内存64K，内存块（页框）2K，进程逻辑地址空间最大128K。假设进程运行前未预先装入任何页。进程驻留集的大小固定为16 K，页面淘汰使用进程驻留集内的CLOCK策略。输出每次存储分配/回收时，内存自由块分布情况、相关进程的页表信息。三、 主要设计思路和流程图1.采用链表完成设计，主要设计两个链表，一个单链表，一个循环链表，其中单链表用于存放申请的页面，循环链表用来存放在驻留集中的页面2内存为64K，页面为2K，所以用了6*6的位示图表示内存情况3.申请页面时输入页表信息后，将位示图中对应的位置改为14.地址置换时，将逻辑地址除以页长，用商在页表中找到对应

3、的块号，用余数加上块号乘以页长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;LNod

4、e,*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<stdio.h>#include<stdlib.h>#incl

5、ude<malloc.h>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()/建立存放页面的链表 LinkList head; LNode *r,*s; int p,b,f,n,i=0; r=

6、head=(LinkList)malloc(sizeof(LNode); printf("输入申请的页数:"); scanf("%d",&n); printf("n请分别输入页表的页号及块号（-1表示空）：n"); printf("n页号 | 块号n"); while(i<n) scanf("%d",&p); scanf("%d",&b); s=(LinkList)malloc(sizeof(LNode); s->page=p; s->

7、;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;i<8;i+) if(p->page!=-1) printf("%3d",p->page);

8、p=p->next; printf("n访问位:"); p=L->next; for(i=0;i<8;i+) if(p->page!=-1) printf("%3d",p->visit); p=p->next; printf("n时 钟:"); p=L->next; for(i=0;i<8;i+) if(p->page!=-1) printf("%3d",p->n); p=p->next; void adr(LinkList L,LinkList H

9、ead)/地址转换算法 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

10、"); 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(i<8)/当遇到驻留集中已经

11、存在的页面，将此页面的访问位置为1 if(q->page=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; w

12、hile(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(j<8) if(q->n=1) break; q=q->next; j+; if(q->n=1) if(q->v

13、isit=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=

14、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

15、 *r,*s; int i=0; r=L=(LinkList)malloc(sizeof(LNode); while(i<8) s=(LinkList)malloc(sizeof(LNode); s->page=-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;

16、printf("位示图为:n"); printf(" "); for(i=0;i<6;i+) printf("%d ",i); printf("n"); for(i=0;i<6;i+)printf("%d",i);for(j=0;j<6;j+)printf(" %d",numij);printf("n");printf("n");void Recy(LinkList L,int a55)/页面的回收 int num,i

17、=0; printf("输入回收的页号:"); scanf("%d",&num); LNode *p,*q,*x; q=(LinkList)malloc(sizeof(LNode); p=L->next; 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

18、; 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-

19、>next; void Init(int a55)/初始化位示图 int i,j; for(i=0;i<6;i+) for(j=0;j<6;j+) aij=rand()%2; void PrintfInfo(LinkList L) LNode *p; p=L->next; 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(