cachelab实验
计算机系统原理实验日志
1、实验内容linux
一、编写一个C程序（csim.c，大约200-300行），用于模拟Cache的行为。算法
二、已提供一个参考的cache模拟器(可执行文件csim-ref)，目标是本身写的ubuntu
csim和参考的csim-ref行为一致，即二者模拟同一个访存过程获得的windows
cache 命中次数(hits)、不命中次数(misses)、替换次数(evicts)都相同。数组
2、相关知识缓存
1.高速缓存存储器结构：数据结构
内存地址划分以下：函数
t=m-(s+b)工具
要访问高速缓存存储空间中的字节：测试
根据内存地址进行 组选择，行匹配，字抽取；
存储层次主要有四个问题
(1)映射规则：
直接映射：E=1
全相联映射：S=1—>s=0
E-路组相联映射：
(图中E=2)
(2)查找算法
(3)替换算法
a. FIFO算法 -- 先进先出，易理解也易实现
b. OPT算法 — 基本不可能实现、通常用LRU算法替代
c. LRU算法
本次实验要用到的是LRU算法，因此主要介绍LRU—最近最少使用替换策略：
cache的容量有限，当满的时候须要牺牲行（驱逐某行），先遍历当前组，判断它是否容量已满，若是未满：将有效位不为1的一行更新有效位为1，同时更新标记位和LRU计数值，若是满了，找出最小LRU所在的行做为牺牲行。
(4)写策略：
a.直写+非写分配
b.写回+写分配（适用于较低层次的缓存）
2. Linux下getopt()函数的简单使用
因为本实验中须要获取命令行，因此须要用到unistd.h头文件中的getopt：int getopt(int argc,char * const argv[ ],const char * optstring);
它用来分析命令行参数；
参数argc和argv分别表明参数个数和内容，跟main的命令行参数相同。
参数optstring为选项字符串，告知getopt()能够处理哪一个选项以及哪一个选项须要参数，若是选项字符串里的字母后接着冒号“:”，则表示还有相关的参数，全域变量optarg 即会指向此额外参数；
它能够返回选项字符(以整型值的形式)，返回-1时即表明解析完成。
/*
关于选项字符串的详细解释以下：
"a:b:cd::e"即一个选项字符串。它对应到命令行就是-a ,-b ,-c ,-d, -e 。其中 冒号表示参数，一个冒号就表示这个选项后面必须带有参数，没有带参数就会报错，可是这个参数能够和选项连在一块儿写，也能够用空格隔开，好比
-a123 和-a 123（中间有空格）都表示123是-a的参数；
两个冒号的就表示这个选项的参数是可选的，便可以有参数，也能够没有参数，但要注意有参数时，参数与选项之间不能有空格（有空格会报错的哦），这一点和一个冒号时是有区别的，
选项后面为两个冒号，且没有跟参数，则optarg = NULL，
有些选项是不用带参数的，而这样不带参数的选项能够写在一块儿。。
*/
3.fopen函数
由于本次实验中须要读取trace文件，因此须要用到fopen函数来打开文件：
FILE * fopen(const char * path, const char * mode);
参数path字符串包含欲打开的文件路径及文件名;
参数mode字符串则表明着打开文件的方式,包括 ’r’, ’w’, ’a’, ’r+’, ’rb+’ 等等;
文件顺利打开后，指向该流的文件指针就会被返回。
若是文件打开失败则返回NULL，并把错误代码存在errno 中。
调用它的通常形式为：
文件指针名 = fopen（文件名,使用文件方式）;
其中，文件指针名 -- 被说明为FILE 类型的指针变量;
文件名 -- 被打开文件的文件名，为字符串常量或字符串数组；
使用文件方式 -- 指文件的类型和操做要求。
4.C库函数 -- fscanf函数
int fscanf(FILE *stream, const char *format, ...)
它从流 stream 读取格式化输入，
第一个参数stream 是指向 FILE 对象的指针，该 FILE 对象标识了流；
第二个参数format 是字符串，
format 说明符形式为 [=%[*][width][modifiers]type=]
附加参数---根据不一样的 format 字符串，函数可能须要一系列的附加参数，每一个参数包含了一个要被插入的值，替换了format参数中指定的每一个 % 标签。参数的个数应与 % 标签的个数相同。
若是成功，该函数返回成功匹配和赋值的个数。
若是到达文件末尾或发生读错误，则返回 EOF。
总而言之，它按照你定义的格式读取输入并赋值到你对应的附加参数中，而后返回读取输入的个数。
5.动态分配函数malloc与calloc
malloc()和calloc()的功能：
在内存的动态存储区中分配n个长度为size的连续空间，
函数返回一个指向分配起始地址的指针。
区别：
calloc在动态分配完内存后，自动初始化该内存空间为零，
而malloc不初始化，里边数据是随机的垃圾数据。
3、实验原理
注意事项：
a.因为模拟器必须适应不一样的s, E, b，因此数据结构必须动态申请，
注意初始化。
b.测试数据中以“I”开头的行是对指令缓存（i-cache）进行读写，咱们编写
的是数据缓存（d-cache），这些行直接忽略。
c.此次实验假设内存所有对齐，即数据不会跨越block，因此测试数据里面的
数据大小也能够忽略。
能够根据老师所给提示逐步分析：
一、如何从命令行中解析s、E、b、t（trace）参数？（getopt函数）
根据相关知识中所介绍关于getopt函数的知识，咱们能很快的解决这个问题。用法以下：
在switch语句中具体实现相应选项及参数对应的功能便可。
二、如何构建一个cache？
实验只要求咱们测试hit/miss/eviction的次数，并无实际的数据存储，
因此咱们不用实现line中的block部分，只需关注是否命中和替换，不关注
数据从内存加载到cache block的哪一个位置，
因此cache只须要是一个二维数组cache[S][E]的形式（与b无关），
因为S、E的值是不肯定的，因此咱们能够考虑采用指针去实现此二维数组：
三、如何从访存trace文件中读取每条访存操做？
天然是灵活运用相关知识中介绍的fscanf函数啦~
访存操做的格式以下：
忽略以i开头的指令缓存操做及每条访存操做的访问字节数：
四、如何从访存操做中的起始地址参数中提取标记位t、组索引s、块偏移b？
已给提示是移位。
咱们不须要知道块大小，须要块偏移是为了求t，t = m-b-s,实际上将地址
做为二进制串时，只须要将实际地址右移(b+s)便可获得t的值；
而s，将实际地址右移b位后，低s位即它的值，为了获取这低s位，咱们
将1左移s位再减1，可获得2^s-1，将它与右移b位后的实际地址相与便可
获得其低s位，以下：
五、cache模拟器采用哪一种放置策略和替换策略？
放置策略：组内放哪儿 -- 放置于组内第一个空闲行；
替换策略：LRU，与csim-ref保持一致；
总体思想是为每一行设置一个计数器，将空闲行的计数器值置为0，
其他行每使用一次加一，新放置的行的计数器值则设为其他行的最大值+1，
每次须要替换时就找到组内计数器值最小的(若是值相同，则是按行序最小的)
一行进行替换。
根据以上分析，其实实现Cache模拟的大体设计思路已经出来了，
以后就是考虑具体实现啦~
4、实验步骤
1. 准备过程
(1)把cachelab-handout.tar拷贝到linux下再解压缩
（不要在windows下解压）
可直接将压缩包从windows桌面下拖到ubuntu中，
也可经过邮箱发送在ubuntu中下载;
命令即 tar xvf cachelab-handout.tar
(2)安装valgrind工具
>sudo su
>apt-get install valgrind
安装完成后输入以下命令可查看每次访存操做（可选）：
> valgrind--log-fd=1 --tool=lackey -v --trace-mem=yes ls -l
至此，工具准备已经完成，具体要怎么进行实验，咱们能够看到压缩包中有readme，其中 ，因此咱们去查看这两个文件，发现
而cachelab.c中即这四个函数的实现，
在partA中，咱们只须要printSummary这个打印结果的函数便可。
那么partA部分其余的函数就所有自由发挥了。
2.具体设计
(1)数据结构的设计
对于每一行，咱们须要一个有效位，一个标记位，一个计数器(用于LRU算法),
因此能够设计一个结构体：
对于cache的构建，前面已经提到过了，cache可看成二维数组cache[S][E]，
采用指针去实现：
而后在解析命令行获得参数S、E的值后再动态分配并初始化内存，由于
每一行都应该初始化为0，因此能够采用calloc函数：
根据S（set的数目）申请一个数组，该数组元素是lines的入口的指针；
接着循环S次，每次申请E个line，让刚申请的指针数组的元素指向它们。
整体数据结构以下：
内存的分配及初始化以下：
(2)解析命令行的逻辑设计
经过getopt函数获取命令行，逐个获取每一个选项并做出相应操做：
当选项为h或输入不符合要求时，咱们中断并打印详细命令用法以提示；
当选项为v时，咱们设置verbose标识为true，即说明须要输出每条访问
操做的详细信息，在以后分析每条访存操做的过程当中就能够经过此标识
去判断是否输出对应信息；
当选项为s,E,b时，咱们要判断其输入参数的值是否在1-64之间(s可为0)，
若是不是，咱们进行中断并打印详细命令用法以提示，
若是是，记录其值(不输入)。
(3)LRU算法的具体实现
其设计思路在实验原理的第5个问题中已经说明，就再也不罗嗦了，实现以下：
(4) 判断每条访存操做的结果的过程
从访存地址获取其所在组，在此组中逐行对比有效位与标志位，
若是有标志位相同且有效位为1的行，则命中，设置hit_flag为true，
并更新此行的LRU计数器值，hit++；
若是没有，miss++，寻找LRU值最小的行做为替换行，更新其LRU计数器值，
若是此行有效位为1，表明此行不为空闲行，发生了替换，evication++，
不然要对此空闲行有效位置1；
(5)读取tracefile并统计其中访存操做获得的命中、不命中、替换次数
在实验原理中已经详述了如何从访存trace文件中读取每条访存操做及
如何从访存操做中的起始地址参数中提取标记位t、组索引s、块偏移b，
而且已经实现了如何判断每条具体访存操做的结果，
还须要考虑的是从tracefile中获取每条访存操做后如何实现其相应逻辑，
若是访存操做为load/store，只须要进行一次对此访问操做的判断便可；
若是访存操做为Modify，至关于进行一次load再对此地址进行一次store，
因此会引发两次访存操做，须要进行两次判断，
其结果能够为两次缓存命中, 或 一次未命中(可能包含替换)、一次命中；
(6)打印命令详细用法
这个就没什么好介绍的了，只是为了减小代码重复因此单独作了一个函数：
（7）释放内存
在c中若是进行了内存分配，必然要释放内存，因此不要忘了free：
3.操做步骤
完成csim.c代码设计与编写后，便可进行测试
(1)输入make clean后输入make命令编译csim.c，生成可执行文件csim
(2)输入./csim –v –s <num> –E <num> –b <num> -t <tracesfile>
查看每次访存cache是否命中和替换的详细信息（可选）
(3)输入./test-csim运行cache模拟器的评价程序，查看得分是否为27分，
27分(满分)则csim.c正确，低于27分则需修改csim.c。
（修改时可用相同的sEbt参数分别运行csim和csim-ref，查看每次访存的
详细信息是否一致）
5、实验结果
实验结果以下：
6、遇到的问题
问题1：一个不算问题的问题：
我实现的时候考虑了s为0即全相联的状况，可是.csim-ref中好像是不能
出现s为0的输入的：
这个其实就把这的小于0改成<=0便可：
问题2：我想让s,b,E三个选项做为可选选项，也就是说不输入这三个选项及参数时默认其为0,1,1
可是会出现以下错误：
可是若是直接输入这些参数又是正确的：
想到参数可输入可不输入时选项字符串应该为
又尝试了一下：
并且此次连直接输入这些参数也是错误的：
因此感受问题应该出在getopt函数上，可是还没找到解决办法。
7、实验心得体会
略
在最后把整个代码贴一下：
#include "cachelab.h"
#include <stdio.h> /* fopen freopen perror */
#include <stdint.h> /* uintN_t */
#include <unistd.h> /* getopt */
#include <getopt.h> /* getopt -std=c99 POSIX macros defined in <features.h> prevents <unistd.h> from including <getopt.h>*/
#include <stdlib.h> /* atol exit*/
#include <errno.h> /* errno */
#define false 0
#define true 1
typedef struct
{
_Bool valid; // 有效位
uint64_t tag; // 标记位
uint64_t time_counter; // LRU计数器，替换此值最小的行
}line;
typedef line *entry_of_lines;
typedef entry_of_lines *entry_of_sets;
typedef struct
{
int hit; // 记录命中次数
int miss; // 记录未命中次数
int eviction; // 记录替换次数
}result;
entry_of_sets InitializeCache(uint64_t S, uint64_t E);
result HitMissEviction(entry_of_lines search_line, result Result, uint64_t E, uint64_t tag, _Bool verbose);
result ReadAndTest(FILE *tracefile, entry_of_sets cache, uint64_t S, uint64_t E, uint64_t s, uint64_t b, _Bool verbose);
void RealseMemory(entry_of_sets cache, uint64_t S, uint64_t E);
/* 当选项为 h，或输入错误的命令(格式错误或用法错误)时，打印命令详细用法 */
void printHelpMessage()
{
//这些提示信息是按照.csim-ref的提示信息编写的
printf("Usage: ./csim [-hv] -s <num> -E <num> -b <num> -t <file>\n");
printf("Options:\n");
printf("-h Print this help message.\n");
printf("-v Optional verbose flag.\n");
printf("-s <num> Number of set index bits.\n");
printf("-E <num> Number of lines per set.\n");
printf("-t <file> Trace file.\n");
printf("\n");
printf("Examples:\n");
printf("linux> ./csim -s 4 -E 1 -b 4 -t traces/yi.trace\n");
printf("linux> ./csim -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");
}
int main(int argc, char * const argv[])
{
result Result = {0, 0, 0};
const char *command_options = "hvs:E:b:t:";
FILE* tracefile = NULL;
entry_of_sets cache = NULL;
_Bool verbose = false; /* flag whether switch to verbose mode, zero for default */
uint64_t s = 0; /* number of sets ndex's bits */
uint64_t b = 0; /* number of blocks index's bits */
uint64_t S = 0; /* number of sets */
uint64_t E = 0; /* number of lines */
char ch; /* command options */
while((ch = getopt(argc, argv, command_options)) != -1)
{
switch(ch)
{
case 'h':
{
printHelpMessage();
exit(EXIT_SUCCESS);
}
case 'v':
{
verbose = true;
break;
}
case 's':
{
if (atol(optarg) <= 0) /* We assume that there are at least two sets */
{
printHelpMessage();
exit(EXIT_FAILURE);
}
s = atol(optarg);
S = 1 << s;
break;
}
case 'E':
{
if (atol(optarg) <= 0)
{
printHelpMessage();
exit(EXIT_FAILURE);
}
E = atol(optarg);
break;
}
case 'b':
{
if (atol(optarg) <= 0) /* We assume that there are at least two sets */
{
printHelpMessage();
exit(EXIT_FAILURE);
}
b = atol(optarg);
break;
}
case 't':
{
if ((tracefile = fopen(optarg, "r")) == NULL)
{
perror("Failed to open tracefile");
exit(EXIT_FAILURE);
}
break;
}
default:
{
printHelpMessage();
exit(EXIT_FAILURE);
}
}
}
if (s == 0 || b ==0 || E == 0 || tracefile == NULL)
{
printHelpMessage();
exit(EXIT_FAILURE);
}
cache = InitializeCache(S, E);
Result = ReadAndTest(tracefile, cache, S, E, s, b, verbose);
RealseMemory(cache, S, E); /* Don't forget this in C/C++, and do not double release which causes security problem */
//printf("hits:%d misses:%d evictions:%d\n", Result.hit, Result.miss, Result.eviction);
printSummary(Result.hit, Result.miss, Result.eviction);
return 0;
}
/* 初始化缓存 */
entry_of_sets InitializeCache(uint64_t S, uint64_t E)
{
entry_of_sets cache;
//使用 calloc而非 malloc，由于咱们须要初始化为0
if ((cache = calloc(S, sizeof(entry_of_lines))) == NULL)
{
perror("Failed to calloc entry_of_sets");
exit(EXIT_FAILURE);
}
for(int i = 0; i < S; ++i)
{
if ((cache[i] = calloc(E, sizeof(line))) == NULL)
{
perror("Failed to calloc line in sets");
}
}
return cache;
}
/* 判断每条访存操做是 hit or miss or miss+evication */
result HitMissEviction(entry_of_lines search_line, result Result, uint64_t E, uint64_t tag, _Bool verbose)
{
uint64_t oldest_time = UINT64_MAX; //用于寻找 LRU计数器值最小的行
uint64_t youngest_time = 0; //用于寻找 LRU计数器值最大的行 以 更新替换进入缓存的行的LRU值
uint64_t oldest_block = UINT64_MAX; //记录 LRU计数器值最小的行号
_Bool hit_flag = false;
for (uint64_t i = 0; i < E; ++ i)
{
if (search_line[i].tag == tag && search_line[i].valid) //命中
{
if (verbose) printf("hit\n");
hit_flag = true;
++Result.hit;
++search_line[i].time_counter; //更新计数器值
break;
}
}
if (!hit_flag) //未命中
{
if (verbose) printf("miss");
++Result.miss;
uint64_t i;
for (i = 0; i < E; ++i) //寻找LRU值最小的行做为替换行(空闲行的值最小)
{
if (search_line[i].time_counter < oldest_time)
{
oldest_time = search_line[i].time_counter;
oldest_block = i;
}
if (search_line[i].time_counter > youngest_time) //寻找LRU值最大的行以更新 新进入缓存的行的计数器值
{
youngest_time = search_line[i].time_counter;
}
}
search_line[oldest_block].time_counter = youngest_time + 1;
search_line[oldest_block].tag = tag;
if (search_line[oldest_block].valid) //假如替换行以前有效位为 1，那么发生了替换
{
if (verbose) printf(" and eviction\n");
++Result.eviction;
}
else
{
if (verbose) printf("\n");
search_line[oldest_block].valid = true;
}
}
return Result;
}
/* 计算结果 （若verbose为真，打印每条访存操做详细结果） */
result ReadAndTest(FILE *tracefile, entry_of_sets cache, uint64_t S, uint64_t E, uint64_t s, uint64_t b, _Bool verbose)
{
result Result = {0, 0, 0};
char ch;
uint64_t address;
//读取tracefile中每条访存操做，获取指令及地址，原本可直接忽略读取字节数，但为了打印访存操做，须要记录
//地址是十六进制数，因此采用 %lx 而非 %lu
while((fscanf(tracefile, " %c %lx%*[^\n]", &ch, &address)) == 2)
{
if (ch == 'I')
{
continue;
}
else
{
uint64_t set_index_mask = (1 << s) - 1;
uint64_t set_index = (address >> b) & set_index_mask;
uint64_t tag = (address >> b) >> s;
entry_of_lines search_line = cache[set_index];
// load / store 操做只会引发一次访存操做
if (ch == 'L' || ch == 'S')
{
if (verbose) printf("%c %lx ", ch, address);
Result = HitMissEviction(search_line, Result, E, tag, verbose);
}
/* data modify操做会进行一次 load再对此地址进行一次 store，因此会引发两次访存操做
结果能够为 两次缓存命中, 或 一次未命中(可能包含替换)、一次命中. */
else if (ch == 'M')
{
if (verbose) printf("%c %lx ", ch, address);
Result = HitMissEviction(search_line, Result, E, tag, verbose);
Result = HitMissEviction(search_line, Result, E, tag, verbose);
}
else
{
continue;
}
}
}
return Result;
}
/* 释放内存 */
void RealseMemory(entry_of_sets cache, uint64_t S, uint64_t E)
{
for (uint64_t i = 0; i < S; ++i)
{
free(cache[i]);
}
free(cache);
}