中 南 大 学 计算机体系结构 实验报告 学 院： 信息科学与工程 专 业： 计算机科学与技术 学 号： 0902030925 姓 名： 刘 敏 时 间： 2006年 4月 10日 一、实验名称 使用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(); /*主函数*/ 六、程序流程图 1、page_node *initialize(int total) /*初始化内存单元、缓冲区*/ 2、void LRU(page_node *head) /*LRU 算法,用到一个链表,表头为w ork_head 指针指向内存中最久未被访问过的页面,表尾为 w ork_tail 指针指向内page_node*head=NULL,*node,*pnode; i=0 inext=node; 存中最近被访问过的页面*/ N Y N Y N Y N Y N N Y N Y Y i=0 page_node*phead,*work_head=NULL,*work_tail,*prenode; inext=head; i++ head=phead; Head=w ork_head; work_head=head; phead=head->nex...
