一、实验目的
了解和掌握寄存器分配和内存分配的有关技术。
二、实验内容
结合数据结构的相关知识，使用LRU的策略，对一组访问序列进行内部的 Cache 更新。
LRU 置换算法是选择最近最久未使用的页面予以置换，该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间 T，当须淘汰一个页面时，选择现有页面中 T 值最大的，即最近最久没有访问的页面，这是一个比较合理的置换算法。
例如：
有一个 Cache 采用组相连映象方式。每组有四块，为了实现 LRU 置换算法，在快表中为每块设置一个 2 位计数器。我们假设访问序列为 1、1、2、4、3、5、2、1、6、7、1、3。在访问 Cache 的过程中，块的装入、置换及命中时，具体情况如下表所示：
三、实验结果
四、实验代码
#include <iostream> using namespace std; class Cache { public: bool state = false; int value = -1; int count = 0; }; const int M = 4; // Cache块数 Cache cache[M]; const int N = 12;// 测试页面数 int walk_sort[] = {1,1,2,4,3,5,2,1,6,7,1,3};// 测试数据 void up_cache(); int main() { up_cache(); } void up_cache() { int i = 0; while (i < N) { int j = 0; // 满么？ while (j < M) { if((cache[j].state == false) && (walk_sort[i] != cache[j].value)) { cout << "cache有空闲块,不考虑是否要置换..." << endl; cout << walk_sort[i] << "被调入cache...." << endl; cache[j].value = walk_sort[i++]; cache[j].state = true; cache[j].count = 0; int kk = 0; for (int x = 0; x < M; x++) { cout << "cache块" << x << ": " << cache[x].value << endl; } cout << endl; // 更新其它cache块没使用时间 while (kk < M) { if (kk != j && cache[kk].value != -1) { cache[kk].count++; } kk++; } break; } if (cache[j].value == walk_sort[i]) { cout << endl; cout << walk_sort[i] << "命中!!!" << endl; for (int x = 0; x < M; x++) { cout << "cache块" << x << ": " << cache[x].value << endl; } cout << endl; int kk = 0; i++; cache[j].count=0; //更新其它cache块没使用时间 while (kk < M) { if (kk != j && cache[kk].value != -1) { cache[kk].count++; } kk++; } } j++; } if (j == M) { cout << "cache已经满了,考虑是否置换..." << endl; cout << endl; int k = 0; while (k < M) { if (cache[k].value == walk_sort[i]) { cout << endl; cout << walk_sort[i] << "命中!!!" << endl; for (int x = 0; x < M; x++) { cout << "cache块" << x << ": " << cache[x].value << endl; } i++; cache[k].count = 0; int kk = 0; //更新其它cache块没使用时间 while (kk < M) { if (kk != k){ cache[kk].count++; } kk++; } break; } k++; } //考虑置换那一块. if (k == M) { int ii = 0; int t = 0;//要替换的cache块号. int max = cache[ii].count; ii++; while (ii < M) { if(cache[ii].count > max) { max = cache[ii].count; t = ii; } ii++; } //置换 cout<<cache[t].value<<"被"<<walk_sort[i]<<"在cache的"<<t<<"号块置换..."<<endl; cache[t].value=walk_sort[i++]; cache[t].count=0; for (int x = 0; x < M; x++) { cout << "cache块" << x << ": " << cache[x].value << endl; } int kk = 0; //更新其它cache块没使用时间 while (kk < M) { if (kk != t) { cache[kk].count++; } kk++; } } } } }
