分类：
2008-12-22 21:39:08
一、实验名称
使用LRU方法更新Cache
二、实验目的
了解和掌握寄存器分配和内存分配的有关技术
三、实验内容
结合数据结构的相关知识，使用LRU的策略，对一组访问序列进行内部的Cache更新。
四、问题描述与分析
最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。
由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
五、函数说明
typedef struct node{
int id;
struct node *next;
}page_node;
/* 页面逻辑结构，结构为方便算法实现设计*/
int page_id_status[MAX_ID];
/*该数组为状态数组,用于说明作业的某一页是否在内存中*/
int page_id[NUM]={0,1,7,2,3,2,17,1,0,3,0,3,0,3,0,10};
/*作业页号数组*/
page_node *initialize(int total); /*初始化内存单元、缓冲区*/
void LRU(page_node *head);
/*LRU算法,用到一个链表,表头为work_head指针指向内存中最久未被访问过的页面,表尾为work_tail指针指向内存中最近被访问过的页面*/
main(); /*主函数*/
七、重要算法解释
void LRU(page_node *head) /*LRU算法,用到一个链表,表头为work_head指针指向内存中最久未被访问过的页面,表尾为work_tail指针指向内存中最近被访问过的页面*/
{ page_node *phead,*work_head=NULL,*work_tail,*prenode;
int i,diseffect=0;
for(i=0;i
if(page_id_status[page_id[i]]==0) /*如果第page_id[i]页不在内存则发生页面中断*/
{ if(head!=NULL) /*内存空间已全部被占用,要求换出一页,即从work_head表头取出一页换出*/
{ phead=head->next;
head->next=NULL;
head->id=page_id[i];
head=phead;
}
else /*内存空间还有部分未被使用,可直接将页面放入,即放在work_head链表尾部即work_tail处*/
diseffect++;
page_id_status[page_id[i]]=1;
}
else /*如果第page_id[i]页在内存则调整页面顺序,最近被访问的页面调到链表尾部*/
{ phead=work_head;
phead=work_head;
while(phead->id!=page_id[i])
{
prenode=phead;
phead=phead->next;
}
if(phead==work_head)
work_head=work_head->next;
else if(phead==work_tail)
work_tail=prenode;
else
prenode->next=phead->next;
phead->next=NULL;
work_tail->next=phead;
work_tail=work_tail->next;
}
printf("LRU: %d",diseffect); /*输出页面中断次数*/
}
八、使用说明
编译后，按提示输入页架数与访问序列，回车；运行后，将看到输出结果即页面置换与装入情况。
如此显然要花费较大的系统开销(包括时间和空间上的)，这也是实际系统中不直接采用LRU算法作为页面置换算法的直接原因，但由于其在页面置换的优越性，实际系统常使用LRU的近似算法。
九、调试报告
调试时出错情况有三类：
低级错误。编写时字母写错，‘}’或‘；’丢失，等；
警告错误。使用指针错误，或定义的指针没有使用等；
匹配错误。在编译子程序时出现类型不匹配，以及一些语法错误等。
程序执行是稳定的，高效的。在LRU算法中，要找出最近最久未使用的页面的话，就必须设置有关的访问记录项，且每一次访问这些记录项，页面都必须更新这些记录项。这个记录项在此程序中为。
十、程序清单
#include
#define NUM 16 /*页序列总长*/
#define MAX_ID 18 /*作业的总页数+1,即序列中出现的最大页号+1,为开page_id_status[MAX_ID]数组所用*/
typedef struct node{
int id;
struct node *next;
}page_node;
int page_id_status[MAX_ID]; /*该数组为状态数组,用于说明作业的某一页是否在内存中*/
int page_id[NUM]={0,1,7,2,3,2,17,1,0,3,0,3,0,3,0,10}; /*作业页号数组*/
page_node *initialize(int total) /*初始化*/
{page_node *head=NULL,*node,*pnode;
int i;
for(i=0;i
page_id_status[i]=0; /*0指明作业第t页不在内存中*/
for(i=1;i<=total;i++) /*total指明在内存中总共可以装入total页*/
{node=(page_node *)malloc(sizeof(page_node));
if(head==NULL)
{head=node;
pnode=node;
}
else
{pnode->next=node;
pnode=pnode->next;
}
}
return head; /*head为模拟内存为作业开辟的内存空间的链表的头指针*/
}
void LRU(page_node *head) /*LRU算法,用到一个链表,表头为work_head指针指向内存中最久未被访问过的页面,表尾为work_tail指针指向内存中最近被访问过的页面*/
{page_node *phead,*work_head=NULL,*work_tail,*prenode;
int i,diseffect=0;
for(i=0;i
if(page_id_status[page_id[i]]==0) /*如果第page_id[i]页不在内存则发生页面中断*/
{if(head!=NULL) /*内存空间已全部被占用,要求换出一页,即从work_head表头取出一页换出*/
{phead=head->next;
head->next=NULL;
head->id=page_id[i];
if(work_head==NULL)
{work_head=head;
work_tail=head;
}
else
{work_tail->next=head;
work_tail=work_tail->next;
}
head=phead;
}
else /*内存空间还有部分未被使用,可直接将页面放入,即放在work_head链表尾部即work_tail处*/
{ head=work_head;
work_head=work_head->next;
head->next=NULL;
page_id_status[head->id]=0;
head->id=page_id[i];
work_tail->next=head;
work_tail=work_tail->next;
head=NULL;
}
diseffect++;
page_id_status[page_id[i]]=1;
}
else /*如果第page_id[i]页在内存则调整页面顺序,最近被访问的页面调到链表尾部*/
{phead=work_head;
phead=work_head;
while(phead->id!=page_id[i])
{
prenode=phead;
phead=phead->next;
}
if(phead==work_head)
work_head=work_head->next;
else if(phead==work_tail)
work_tail=prenode;
else
prenode->next=phead->next;
phead->next=NULL;
work_tail->next=phead;
work_tail=work_tail->next;
}
printf("LRU: %d",diseffect); /*输出页面中断次数*/
}
main()
{ int i,j;
page_node *head,*node;
for(i=4;i<=7;i++)
{
head=initialize(i);
printf("\n %d page frames:",i);
LRU(head);
do{
node=head;
head=head->next;
node->next=NULL;
free(node);
}while(head!=NULL);
}
}
