操作系统实验8-请求页.doc

操作系统实验报告实验八 请求页一、 基本信息二、 实验内容编写程序实现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，则置换该节点。五、 主要数据结构及其说明 #include #include #include #include #define MaxRAMFrame 3/页表项struct PageItemint 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;shiftRegisteri += (pageTablei.RefBit 1;/计数器实现LRUvoid 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;elsefor(i=0; iMaxRAMFrame; +i)/请求页已经在内存中if(pageTablei.pageNum = pageNum)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;/栈实现LRUvoid LRUStack(int pageNum)PageItem* p;/页表为空if(Counter pageNum = pageNum;p-next = NULL;head = p;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;elsepre = 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;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;elsefor(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;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;elseif(curr-pageNum = pageNum) return;head = curr;for(curr=curr-next; curr!=head; curr=curr-next)/请求页已经在内存中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;elsePageItem *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;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);/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;六、 程序运行时的初值和运行结果LRUCounterLRUStackSimilarLRUARBSimilarLRUSC10070846743100069178469048210000701480077082453010000070068799997013645034七、 实验体会通过实验，进一步了解了页面置换的实现机制，并且学习了LRU算法的计数器实现