操作系统实验报告实验八 请求页一、 基本信息二、 实验内容编写程序实现LRU 算法及其近似算法（LRU 的计数器实现 (counter implementation)， LRU的 栈 实 现 （ stack implementation），Additional-Reference-Bits Algorithm，Second chance Algorithm） ，并分析各算法的时间复杂度、空间复杂度和实现难度；通过随机生成页面访问序列，测试所实现算法的的页错误率，并加以比较和分析。三、 实验目的通过实验，理解LRU 页面置换算法的算法思想及其实现方法，比较各种实现算法的复杂度和实现难度，体会LRU 算法与各种近似算法间的区别，并进而加深对虚拟内存概念的理解。四、 设计思路和流程图(1) 创建一个结构体用来表示页表项(2) 利用静态数组表示页表来存放页表项来实现LRU 计数器算法，页表项存放页号、时间域时间。计数器值最小者被置换(3) 利用单向链表表示页表，结构体节点表示页表项来实现LRU 栈算法，页表项存放页号、指向下一个页表项指针，并也用head指向链表头部，rear 指向链表尾部，从尾部节点置换。(4) 利用静态数组表示页表来存放页表项并也包含一个引用位来实现附加引用位算法，页表项存放页号、引用位，同时建立一个也页表对应的移位寄存器（ 8bit ）来记录一定时间间隔各页表项的使用情况，该8 字节无符号整数最小者被置换。(5) 利用链表环表示页表，结构体表示页表项来实现二次机会算法，页表项存放页号、指向下一个页表的指针、引用位，用curr指针指向当前节点。如果引用位为1，则将其置 0，再给一次机会；如果引用位为0，则置换该节点。五、 主要数据结构及其说明名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - 操作系统实验报告#include #include #include #include #define MaxRAMFrame 3 / 页表项struct PageItem int pageNum; / 存储页号int time; / 时间域struct PageItem* next; bool RefBit; / 引用位; int Counter = 0; / 逻辑时钟int pageError = 0; / 页错误struct PageItem *head; / 首指针struct PageItem *rear; / 尾指针struct PageItem *curr,*pre; byte shiftRegisterMaxRAMFrame;/移位寄存器struct PageItem *pageTable = new PageItemMaxRAMFrame; /页表void Shift() for(int i=0; i 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - 操作系统实验报告shiftRegisteri += (pageTablei.RefBit 1; / 计数器实现 LRU void LRUCounter(int pageNum) int i,j=0,min; / 页表未满if(Counter = MaxRAMFrame) for(i=0; iCounter-1; +i) / 请求页已经在内存中if(pageTablei.pageNum = pageNum) pageTablei.time = Counter; return; pageTableCounter-1.pageNum = pageNum; pageTableCounter-1.time = Counter; return; else for(i=0; iMaxRAMFrame; +i) / 请求页已经在内存中if(pageTablei.pageNum = pageNum) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - 操作系统实验报告pageTablei.time = Counter; return; / 请求页不在内存中，置换最近最少使用页min = pageTable0.time; for(i=1; i pageTablei.time) min = pageTablei.time; j = i; / 记录页表号 pageTablej.pageNum = pageNum; pageTablej.time = Counter; pageError+; return; / 栈实现 LRU void LRUStack(int pageNum) PageItem* p; / 页表为空if(Counter pageNum = pageNum; p-next = NULL; head = p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - 操作系统实验报告rear = p; return; / 页表未满else if(Counter next!=NULL; p=p-next) / 请求页已经在内存中if(p-pageNum = pageNum) if(head = p) return; pre-next = p-next; p-next = head; head = p; while(p-next != NULL)p = p-next; rear = p; return; pre = p; p = new PageItem; p-pageNum = pageNum; p-next = head; head = p; while(p-next != NULL)p = p-next; rear = p; return; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - 操作系统实验报告pre = head; for(p=head; p-next!=NULL; p=p-next) / 请求页已经在内存中if(p-pageNum = pageNum) if(head = p) return; pre-next = p-next; p-next = head; head = p; while(p-next != NULL)p = p-next; rear = p; return; pre = p; p = new PageItem; p-pageNum = pageNum; p-next = head; head = p; while(p-next != rear)p = p-next; delete rear;/置换尾节点p-next = NULL; rear = p; pageError+; return; / 附加引用位算法void SimilarLRUARB(int pageNum) int i,j=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - 操作系统实验报告byte min; / 页表未满if(Counter = MaxRAMFrame) for(i=0; iCounter-1; +i) / 请求页已经在内存中if(pageTablei.pageNum = pageNum) pageTablei.RefBit = 1; Shift(); return; pageTableCounter-1.pageNum = pageNum; Shift(); return; else for(i=0; iMaxRAMFrame; +i) / 请求页已经在内存中if(pageTablei.pageNum = pageNum) pageTablei.RefBit = 1; Shift(); return; / 请求页不在内存中，置换最近最少使用页min = shiftRegister0; for(i=1; i shiftRegisteri) min = shiftRegisteri; j = i; / 记录页表号 pageTablej.pageNum = pageNum; Shift(); pageError+; return; / 二次机会算法void SimilarLRUSC(int pageNum) / 页表为空if(Counter pageNum = pageNum; p-next = NULL; curr = p; return; / 页表未满if(curr-next = NULL) if(curr-pageNum != pageNum) PageItem *p = new PageItem; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - 操作系统实验报告p-pageNum = pageNum; p-next = curr; curr-next = p; curr = p; return; else return; if(Counter pageNum = pageNum) return; head = curr; for(curr=curr-next; curr!=head; curr=curr-next) / 请求页已经在内存中if(curr-pageNum = pageNum) curr-RefBit = 1; return; PageItem *p = new PageItem; p-pageNum = pageNum; p-next = curr-next; curr-next = p; curr = p; return; else if(curr-pageNum = pageNum) return; head = curr; for(curr=curr-next; curr!=head; curr=curr-next) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 14 页 - - - - - - - - - 操作系统实验报告 / 请求页已经在内存中if(curr-pageNum = pageNum) curr-RefBit = 1; return; pre = curr; for(curr=curr-next; curr!=head; curr=curr-next) if(curr-RefBit) curr-RefBit = 0;pre = curr; else PageItem *p = new PageItem; p-pageNum = pageNum; p-next = curr-next; pre-next = p; delete curr;/置换节点curr = p-next; pageError+; return; void init() pageError = 0; for(int i=0; iMaxRAMFrame; +i) pageTablei.pageNum = -1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - 操作系统实验报告pageTablei.RefBit = 0; int main() int i,j; clock_t beginTime, endTime; srand(unsigned)time(NULL); const int count = 100; / 测试次数/LRUCounter 测试init(); beginTime = clock(); for(Counter=1; Counter=count; Counter+) j = rand() % 10; LRUCounter(j); endTime = clock(); printf(LRUCounter time: %d msnLRUCounter pageError: %dn,endTime - beginTime, pageError); /LRUStack 测试init(); beginTime = clock(); for(Counter=1; Counter= count; Counter+) j = rand() % 10; LRUStack(j); endTime = clock(); printf(nLRUStack time: %d msnLRUStack pageError: %dn,endTime - beginTime, pageError); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - 操作系统实验报告/SimilarLRUARB 测试init(); beginTime = clock(); for(Counter=1; Counter= count; Counter+) j = rand() % 10; SimilarLRUARB(j); endTime = clock(); printf(nSimilarLRUARB time: %d msnSimilarLRUARB pageError: %dn,endTime - beginTime, pageError); /SimilarLRUSC 测试init(); beginTime = clock(); for(Counter=1; Counter= count; Counter+) j = rand() % 10; SimilarLRUSC(j); endTime = clock(); printf(nSimilarLRUSC time: %d msnSimilarLRUSC pageError: %dn,endTime - beginTime, pageError); system(pause); return 0; 六、 程序运行时的初值和运行结果名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - 操作系统实验报告LRUCounter LRUStack SimilarLRUARB SimilarLRUSC 100 70 84 67 43 1000 691 784 690 482 10000 7014 8007 7082 4530 100000 70068 79999 70136 45034 七、 实验体会通过实验，进一步了解了页面置换的实现机制，并且学习了LRU算法的计数器实现和栈实现以及其近似算法附加引用位算法和二次机会算法。由于实验是模仿系统实现的机制，我做的实验只是模仿了算法的实现，而跟真正的系统算法还是有很大差别，例如在计数器实现和栈实现名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - 操作系统实验报告的 LRU 算法，计数器实现中由于每次内存访问都要写入内存，会令整个操作时间比较长；而栈实现时，除了更新有点费时外，置换是不需要搜索的，这样就使得整个操作比较节省时间开销。然而，在我的实验中，为了确定请求页是否已经在内存中（页表），没有采用映射，而是所有算法直接遍历页表，使得用链表的添加和修改的算法相对都比较费时。正是这个原因，使得时间测试结果也真正系统中的实现有差距。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -