操作系统页面置换算法实验程序清单.doc

《操作系统页面置换算法实验程序清单.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、实验名称使用LRU方法更新Cache二、实验目的了解和掌握寄存器分配和内存分配的有关技术三、实验内容结合数据结构的相关知识，使用LRU的策略，对一组访问序列进行内部的Cache更新。四、问题描述与分析最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，

2、当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。五、函数说明typedefstructnode{intid;structnode*next;}page_node;/*页面逻辑结构，结构为方便算法实现设计*/intpage_id_status[MAX_ID];/*该数组为状态数组,用于说明作业的某一页是否在内存中*/intpage_id[NUM]={0,1,7,2,3,2,17,1,0,3,0,3,0,3,0,10};/*作业页号数组*/page_node*init

3、ialize(inttotal);/*初始化内存单元、缓冲区*/voidLRU(page_node*head);/*LRU算法,用到一个链表,表头为work_head指针指向内存中最久未被访问过的页面,表尾为work_tail指针指向内存中最近被访问过的页面*/main();/*主函数*/七、重要算法解释voidLRU(page_node*head)/*LRU算法,用到一个链表,表头为work_head指针指向内存中最久未被访问过的页面,表尾为work_tail指针指向内存中最近被访问过的页面*

4、/{page_node*phead,*work_head=NULL,*work_tail,*prenode;inti,diseffect=0;for(i=0;inext;head->next=NULL;head->id=

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

6、=phead->next;}if(phead==work_head)work_head=work_head->next;elseif(phead==work_tail)work_tail=prenode;elseprenode->next=phead->next;phead->next=NULL;work_tail->next=phead;work_tail=work_tail->next;}printf("LRU:%d",diseffect);/*输出页面中断次数*/}八、使用说明编译后，按提

7、示输入页架数与访问序列，回车；运行后，将看到输出结果即页面置换与装入情况。如此显然要花费较大的系统开销(包括时间和空间上的)，这也是实际系统中不直接采用LRU算法作为页面置换算法的直接原因，但由于其在页面置换的优越性，实际系统常使用LRU的近似算法。九、调试报告调试时出错情况有三类：低级错误。编写时字母写错，‘}’或‘；’丢失，等；警告错误。使用指针错误，或定义的指针没有使用等；匹配错误。在编译子程序时出现类型不匹配，以及一些语法错误等。程序执行是稳定的，高效的。在LRU算法中，要找出最近最久未

8、使用的页面的话，就必须设置有关的访问记录项，且每一次访问这些记录项，页面都必须更新这些记录项。这个记录项在此程序中为。十、程序清单#include#defineNUM16/*页序列总长*/#defineMAX_ID18/*作业的总页数+1,即序列中出现的最大页号+1,为开page_id_status[MAX_ID]数组所用*/typedefstructnode{intid;structnode*next;}page_node;intpage_id_status[MAX_ID];