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);
}