CSAPP：CacheLab实验
趁期末考试复习了《深⼊理解计算机系统》第六章，进⼀步了解了cache的原理。想着写篇博客帮助巩固⼀下。有些地⽅写得可能不是很好，希望多多包涵，同时也欢迎指出。
cachelab⼀共分为两部分，PartA是让你模拟cache运⾏的过程，就是模拟cache的⾏为。PartB是⼀个矩阵转置，给出了三种规模，你的任务就是尽可能的提⾼⾼速缓存的命中率，它会根据你的miss，hits，eviction这三个值的⼤⼩进⾏打分，评分的范围已给出。
好啦实验介绍完毕。下⾯开始进⼊正式环节。
PartA
这是原版⽂档的要求。⼤概就是告诉你它只是⼀个模拟缓存的⾏为并不是真实缓存，内存的数据不⽤存储，不使⽤块偏移，因此地址种b并不重要，简单的计算hits、miss、evictions的值。然后就是你的模拟器需要适⽤于不同的（s，b，E），同时给出运⾏时间。最后就是要求你使⽤这个LRU最近最少使⽤策略，意思就是使⽤这个策略进⾏⾏的牺牲，因此cache发⽣miss的时候，就会从它的k+1层存储器读取新的拷贝，假设在空间已满的情况下（未满的时候不需要替换⾏），新读取的数据需要存储在cache⾥⾯，但空间已满，只能选择驱逐（原⽂是驱逐的意思，也就是覆盖某⼀⾏），然后覆盖的⽅法就是这个L
RU策略。LRU策略就是：选择那个最后被访问的时间距离现在最远的块。代码体现的话就是给cache的每⼀⾏绑⼀个Lrunumber，这个值越⼩（你也可以设置为最⼤，随⾃⼰喜欢）表⽰它最后⼀次被访问的时间距离现在最远，可以作为牺牲⾏。
⼀、那么模拟⼀个cache的⾏为需要⽤到哪些变量？
小说人名cache有组数S、⼀组包含的⾏数E，存储块的字节⼤⼩B，cache的容量C（C=S*E*B)
地址的构成：标识位t、组索引s、块偏移b（前⾯说了实验不使⽤块偏移，但计算标记位的时候需要⽤到）
腾冲是哪里
⽰意图：
我简单解释下上⾯说的这些变量：
⾸先是cache的构成:
cache有2^s组，每组有E⾏（E分为三种情况：E=1，称为直接映射⾼速缓存；1<E<C/B：组相联⾼速缓存；E=C/B，全相连⾼速缓存，也就是⼀组包含了所有的⾏），然后是每⾏的构成：（1）有效位vild(取0和1，1表⽰存储了有效信息，0表⽰没有，判断命中的时候需要⽤到）（2）标记位t=m-(s+b)，当cpu要读取某个地址的内容时，就会将某个地址的第⼀个部分：标记位与它进⾏对⽐，匹配相等则命中，也就是锁定在某⼀⾏（3）数据块B，B负责存储这个地址的内容，把B想象成字节数组就好，共有B-1个⼩块（别和B这个数据块搞混咯，下标从0开始，因此是B-1）。在这⾥简单提下b的作⽤吧，虽然实验没⽤到。b理解为数据块B这个数组的下标就好，也就是你要从B[b]这个位置开始读取字。注意这⾥的数据都是2进制的。
以上这些都可以从那个原版的PPT读取，只是我讲得更详细些，这也是我⾃⼰的理解。
⼆、⾃带函数的介绍：
cache.h⾥⾯⾃带了⼀些函数，PPT给出了要⽤到的⼏个的介绍：
如果函数声明丢失，则在Unix命令⾏上⾃动解析元素，通常在循环中调⽤以检索参数，它的返回值存储在局部变量中，
当getopt（）返回-1时，没有更多的选项。（百度翻译的）⼀句话就是它是解析你的那个命令⾏的。
2.fscanf（）党员在留党察看期间没有
读⼊测试⽂件的，⾃带有调⽤就好了。具体使⽤⽅式如下：（写的时候粘贴复制⼀下就好了。）
艰苦奋斗的意思
FILE * pFile; //pointer to FILE object
pFile = fopen ("",“r"); //open file for reading
豆腐图片char identifier;
unsigned address;
int size;
// Reading lines like " M 20,1" or "L 19,3"
while(fscanf(pFile,“ %c %x,%d”, &identifier, &address, &size)>0){
// Do stuff
}
fclo(pFile); //remember to clo file when done
3.Malloc/free
分配和释放内存空间的函数。
具体⽤法如下：
Some_pointer_you_malloced = malloc(sizeof(int));
Free(some_pointer_you_malloced);
分配了内存⽤完的时候记得释放，还有不要释放没有分配的内存。
三、根据（⼀）可以写出下⾯结构体：（基于c语⾔）明的成语
定义⾏的属性：
typedef struct{
int valid; //有效位
int tag; //标识位
int LruNumber; //牺牲⾏的时候要⽤的，具体上⾯说了。
} Line;
绿茶用英语怎么说
定义组的属性：
typedef struct{
Line* lines; //⽤于存储⼀组中包含的⾏
} Set;
定义cache的属性:
typedef struct {
int t_num; //组数
int line_num; //⾏数
Set* ts; //cache的空间，模拟cache
} Sim_Cache;
四、函数实现：
2.⽂本处理函数，也就是读⼊测试⽂件的，直接⽤它⾃带的fscanf就好了。在cache.h那个头⽂件⾥⾯。
3.检查参数合法性：主要⽬的就是检查输⼊的命令是否合法。
、4.打印帮助⽂档的函数，当输⼊的命令出错的时候，运⾏这个函数，也就是说你解释⼀下这些关键字代表的意思就好啦。
电脑快捷关机
5.更新Lru计数值的函数：访问第x组E⾏，根据标记为将该⾏的LRU设置为最⼤值，然后其它⾏⽤⼀个for循环减⼀即可。
6.查找牺牲⾏的函数:
遍历找出第x组，找到最⼩的LRU所在的⾏，那么该⾏就是牺牲⾏。关于怎么找，⽆⾮就算设置标记位，不断⽐较和更新即可。
7.判断是否命中：命中在前⾯说了，要满⾜两个条件：（1）设置了有效位；（2）请求的地址的标记位与cache地址的标记位⼀致。最后记得更新⼀下Lru计数值。
8.更新⾼速缓存cache的函数：cache的容量有限，当满的时候需要牺牲⾏（或者说驱逐某⾏），先遍历当前组，判断它满了没有，如何判断是否满，可以遍历所有的⾏，只要有⼀个有效位为0，（有效位的作⽤是说明该⾏是否存储了数据，通俗的理解就是是否为空）则该组未满。如果没有满的话：将有效位不为1的那⼀⾏更新有效位为1，同时更新标记位和LRU计数值。如果满了，找出最⼩LRU所在的⾏作为牺牲⾏。
9.读取数据的函数，亦即操作L：指导PPT上说命中则hit++，不命中则miss++且如果牺牲⾏eviction++，如果有v指令就打印访问结果。那么可以⽤⼀个标记来判断是否有-v指令。
10.存储数据的函数，亦即操作S：原理跟L操作⼀样也是修改标记位和组索引指令的，然后调⽤⼀下L操作那个函数即可。
11.修改数据的函数，亦即操作M：这个操作实际就是执⾏了⼀次L和⼀次S。
12.获取标记位和组索引：前⾯说了⼀个当要访问⼀个地址（暂且称为请求地址吧）的内容时，这个请求地址是这样的结构：标记位(t) 组索引(s) 块偏移(b)，然后cache中地址的结构：有效位(v) 标记位(v) 数据块(B)。我们现在的任务是从这个请求地址中获取t和s，才能从cache中寻找需要访问的内容。地址位数未知，但问题不⼤，⽐如我求标记位的时候直接将它右移到最右边即可，组索引由于右移的时候带着标记位，因此要和⼀个数与运算⼀下，把它“剪”下来。
13.最后写⼀个初始化cache的函数就好了。
