一、实验目的
了解和掌握寄存器分配和内存分配的有关技术。
二、实验内容
结合数据结构的相关知识,使用LRU的策略,对一组访问序列进行内部的 Cache 更新。
LRU 置换算法是选择最近最久未使用的页面予以置换,该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来经历的时间 T,当须淘汰一个页面时,选择现有页面中 T 值最大的,即最近最久没有访问的页面,这是一个比较合理的置换算法。
例如:
有一个 Cache 采用组相连映象方式。每组有四块,为了实现 LRU 置换算法,在快表中为每块设置一个 2 位计数器。我们假设访问序列为 1、1、2、4、3、5、2、1、6、7、1、3。在访问 Cache 的过程中,块的装入、置换及命中时,具体情况如下表所示:
1 | 1 | 2 | 4 | 3 | 5 | 2 | 1 | 6 | 7 | 1 | 3 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|
Cache块0 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 7 | 7 | 7 |
Cache块1 | -1 | -1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 3 |
Cache块2 | -1 | -1 | -1 | 4 | 4 | 4 | 4 | 1 | 1 | 1 | 1 | 1 |
Cache块3 | -1 | -1 | -1 | -1 | 3 | 3 | 3 | 3 | 6 | 6 | 6 | 6 |
装入 | 命中 | 装入 | 装入 | 装入 | 置换 | 命中 | 置换 | 置换 | 置换 | 命中 | 置换 |
三、实验结果
四、实验代码
#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++;
}
}
}
}
}