cache lab
Part A
写在前面
这部分要求你实现一个模拟缓存运行的C语言程序，支持读，写，修改内存三个操作，其与对于缓存模拟的行为给定的\(csim-ref\)可执行文件一致，最后输出操作完成后的缓存命中，未命中，替换的次数。缓存的组数，行数，每一行的字节数在执行时以参数给出，替换策略使用\(LRU\)(least-recently used)，即每次替换块内离上一次引用时间最久的块
但是本部分不要求你输出访问时具体的值，你只需要统计这次操作是否命中，未命中，替换
在运行的时候，我们采用了一下的选项来传递参数
linux> ./csim-ref [-hv] -s <s> -E <E> -b <b>-t <tracefile>
其中-h -v两个选项可选可不选，且后面没有参数，分别表示打印使用方法，和运行时是否可见化地输出每次缓存访问的结果
-s -E -b 后接一个参数，分别表示组数，每组行数，每行字节数
-t 后接字符串参数，表示读入文件的路径
读入部分
怎么感觉是Part A 里面最难的部分（
首先为了从选项中读出参数，我们在linux系统下需要使用\(getopt\)函数，该函数原型如下
int getopt(int argc, char * const argv[], const char *optstring)
其中\(argc\)，\(argv\)为\(main\)函数的参数，分别代表参数个数和参数列表
\(optstring\)为选项字符串，举例来说，getopt(argc, argv, "hvs:E:b:t:")就表示有-h -v -s -E -b -t 这几个选项，其中-s -E -b -t 若选择的话，后面必须带有参数
该函数返回值为选项的ASCII码，同时，包含该函数的 <unistd.h> 和 <getopt.h> 中有名为 \(optarg\)的指针变量，在每次使用\(getopt\)时，若该选项有参数，就会被更新为该参数的字符串指针
由此不难写出读入函数
int op;FILE *fp;while ((op = getopt(argc, argv, "hvs:E:b:t:")) != EOF) {if (op == 'h') {Help();return 0;}if (op == 'v') {v = 1;continue;}if (op == 's') {s = atoi(optarg);//atoi 在 stdlib.h中，传入一个字符串开头的指针，将其转换为整数S = (1 << s);continue;}if (op == 'E') {E = atoi(optarg);continue;}if (op == 'b') {b = atoi(optarg);B = (1 << b);continue;}if (op == 't') {fp = fopen(optarg, "r");//文件指针指向参数标明的文件continue;}Help();return 0;//其它异常参数符}
每次操作分为以下四类：
I address size表示取address地址的size位指令L address size表示加载address地址开始的size位数据S address size表示向address地址开始的size位写数据L address size表示修改address地址的size位数据
但是这部分只要我们用缓存处理数据信息，同时又不需要真正地对缓存进行读写，只是模拟是否命中和替换这个过程即可
所以 I操作完全没用， L 和S操作完全等价 （无语
char opt[5];size_t ad;int siz;while (fscanf(fp, "%s %lx,%d", opt, &ad, &siz) != EOF) {++curtime;if (v) {printf("%c %lx,%d\n", opt[0], ad, siz);}if (opt[0] == 'I') continue;if (opt[0] == 'L') Load(ad);if (opt[0] == 'S') Store(ad);if (opt[0] == 'M') Modify(ad);}
缓存的相关结构
由于本部分缓存大小未知，需要动态分配内存，这里实现上使用了指针加 malloc动态分配空间
struct row {int valid, flag, dfn;//有效位 标志位 上次更新的时间戳
};//一行typedef struct row* set;//一组
typedef set* cache;//整个缓存
cache c;void Cache_init() {c = (cache)malloc(sizeof(set) * S);//分配S个组的空间for (int i = 0; i < S; i++) {c[i] = (set)malloc(sizeof(struct row) * E);//每一组分配E行的空间for (int j = 0; j < E; j++) {c[i][j].valid = 0;c[i][j].flag = c[i][j].dfn = -1;}}
}
缓存的读写
我们先对地址使用位运算得到该地址应该被分配到的组数，标识位和偏移量（偏移量好像没用）
为了维护某一组内是否有该地址对应的标志位，我们可以采用平衡树，但是E一般都比较小，没有这个必要（不是我懒得写了），直接E行依遍历比较就行
如果存在标识符相同且有效的，那么发生缓存命中，修改这一行的时间戳，直接返回即可
否则缓存未命中，我们优先找该组空的行，若存在，直接放入并更新时间戳，将其有效位设置为1，此时未命中，也未发生替换
如空的行不存在，我们就将该组中时间戳最小的行替换为需要访问的数据，同样更新时间戳即可，此时未命中并发生替换
void Load(int ad) {//m = t + s + b// int _b = ad & ((1 << b) - 1);int _s = (ad >> b) & ((1 << s) - 1);int _t = ad >> (s + b);struct row* r = c[_s];for (int i = 0; i < E; i++) {if ((r + i)->valid && (r + i)->flag == _t) {//缓存命中if (v) puts("hit");++hit;(r + i)->dfn = curtime;return;}}struct row* evicp = r;for (int i = 1; i < E; i++) {if ((r + i)->dfn == -1 || (r + i)->dfn < evicp->dfn) {//优先使用空行evicp = r + i;}}miss++; printf("miss");if (evicp->dfn != -1) {evic++;if (v) printf(" eviction");}//发生了替换putchar('\n');evicp->dfn = curtime; evicp->valid = 1; evicp -> flag = _t;return;
}
写入和加载的行为完全一致，修改逻辑类似，注意读的时候就在缓存中只算命中缓存一次，就不展开了
点击查看代码
void Store(int ad) {Load(ad);
}void Modify(int ad) {//m = t + s + b// int _b = ad & ((1 << b) - 1);int _s = (ad >> b) & ((1 << s) - 1);int _t = ad >> (s + b);struct row *r = c[_s]; for (int i = 0; i < E; i++) {if ((r + i)->valid && (r + i)->flag == _t) {if (v) puts("hit");hit += 2;(r + i)->dfn = curtime;return;}}struct row* evicp = r;for (int i = 1; i < E; i++) {if ((r + i)->dfn == -1 || (r + i)->dfn < evicp->dfn) {evicp = r + i;}}miss++; hit++;if (v) puts("miss");if (evicp->dfn != -1) {evic++;if (v) printf(" eviction");}puts(" hit");evicp->dfn = curtime; evicp->valid = 1; evicp -> flag = _t;return;
}
代码
主体已经完成了，再加上使用说明即可
点击查看代码
#include "cachelab.h"
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <getopt.h>int E, s, S, b, B, v, t;
const int m = 64;
int curtime;
int hit, miss, evic;struct row {int valid, flag, dfn;//有效位 标志位 上次更新的时间戳
};//一行typedef struct row* set;//一组
typedef set* cache;//整个缓存
cache c;void Cache_init() {c = (cache)malloc(sizeof(set) * S);//分配S个组的空间for (int i = 0; i < S; i++) {c[i] = (set)malloc(sizeof(struct row) * E);//每一组分配E行的空间for (int j = 0; j < E; j++) {c[i][j].valid = 0;c[i][j].flag = c[i][j].dfn = -1;}}
}/*
Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>
Options:-h Print this help message.-v Optional verbose flag.-s <num> Number of set index bits.-E <num> Number of lines per set.-b <num> Number of block offset bits.-t <file> Trace file.Examples:linux> ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.tracelinux> ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace
*/void Help() {printf(
"Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>\n"
"Options:\n"
" -h Print this help message.\n"
" -v Optional verbose flag.\n"
" -s <num> Number of set index bits.\n"
" -E <num> Number of lines per set.\n"
" -b <num> Number of block offset bits.\n"
" -t <file> Trace file.\n""Examples:\n"
" linux> ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace\n"
" linux> ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");
}void Load(int ad) {//m = t + s + b// int _b = ad & ((1 << b) - 1);int _s = (ad >> b) & ((1 << s) - 1);int _t = ad >> (s + b);struct row* r = c[_s];for (int i = 0; i < E; i++) {if ((r + i)->valid && (r + i)->flag == _t) {//缓存命中if (v) puts("hit");++hit;(r + i)->dfn = curtime;return;}}struct row* evicp = r;for (int i = 1; i < E; i++) {if ((r + i)->dfn == -1 || (r + i)->dfn < evicp->dfn) {//优先使用空行evicp = r + i;}}miss++; printf("miss");if (evicp->dfn != -1) {evic++;if (v) printf(" eviction");}//发生了替换putchar('\n');evicp->dfn = curtime; evicp->valid = 1; evicp -> flag = _t;return;
}void Store(int ad) {Load(ad);
}void Modify(int ad) {//m = t + s + b// int _b = ad & ((1 << b) - 1);int _s = (ad >> b) & ((1 << s) - 1);int _t = ad >> (s + b);struct row *r = c[_s]; for (int i = 0; i < E; i++) {if ((r + i)->valid && (r + i)->flag == _t) {if (v) puts("hit");hit += 2;(r + i)->dfn = curtime;return;}}struct row* evicp = r;for (int i = 1; i < E; i++) {if ((r + i)->dfn == -1 || (r + i)->dfn < evicp->dfn) {evicp = r + i;}}miss++; hit++;if (v) puts("miss");if (evicp->dfn != -1) {evic++;if (v) printf(" eviction");}puts(" hit");evicp->dfn = curtime; evicp->valid = 1; evicp -> flag = _t;return;
}int main(int argc, char *argv[]){int op;FILE *fp;while ((op = getopt(argc, argv, "hvs:E:b:t:")) != EOF) {if (op == 'h') {Help();return 0;}if (op == 'v') {v = 1;continue;}if (op == 's') {s = atoi(optarg);//atoi 在 stdlib.h中，传入一个字符串开头的指针，将其转换为整数S = (1 << s);continue;}if (op == 'E') {E = atoi(optarg);continue;}if (op == 'b') {b = atoi(optarg);B = (1 << b);continue;}if (op == 't') {fp = fopen(optarg, "r");//文件指针指向参数标明的文件continue;}Help();return 0;//其它异常参数符}Cache_init();//缓冲初始化，动态分配空间char opt[5];size_t ad;int siz;while (fscanf(fp, "%s %lx,%d", opt, &ad, &siz) != EOF) {++curtime;if (v) {printf("%c %lx,%d\n", opt[0], ad, siz);}if (opt[0] == 'I') continue;if (opt[0] == 'L') Load(ad);if (opt[0] == 'S') Store(ad);if (opt[0] == 'M') Modify(ad);}printSummary(hit, miss, evic);return 0;
}使用 make && ./test-csim得到以下结果
