1. 實驗要求
2. 程式設計2.1 讀取檔案2.2 快取記憶體定義結構體2.3 初始化Cache2.4 解析輸入的指令2.5 LRU策略2.6 更新快取記憶體Cache2.7 完整程式碼3. 測試結果1. 實驗要求1.程式設計模擬Cahce的命中，不命中，替換等行為。
2.編寫的程式必須對任意s，E和b正確工作。
3.本實驗不涉及真實的資料讀寫，不需要考慮block的細節，每行只有一個block。
4.編寫的程式要能讀取指定檔案內的指令，根據不同的指令完成不同的動作，下面為指令內容示例。
I 0400d7d4,8 #M 0421c7f0,4 # 修改access cache， 即讀寫access cache兩次，0421c7f0：修改的地址，8：修改的長度L 04f6b868,8 # 讀access cache，04f6b868：讀取的地址，8：讀取長度S 7ff0005c8,8 # 寫access cache，0421c7f0：寫的地址，8：寫的長度考慮模擬一個Cache的行為需要用到哪些變數？
計算機中的快取記憶體模型
Cache有組數S、一組包含的行數E，儲存塊的位元組大小B，Cache的容量C=S×E×B。
地址的構成：標識位t、組索引s、塊偏移b（前面說了，不需要管塊偏移）。
關於快取和記憶體資料交換的詳細介紹可以看下這個24張圖7000字詳解計算機中的快取記憶體。
下面我們開始編寫程式碼。
2.1 讀取檔案getopt()該函式能夠幫助程式分析C語言命令列程式輸入的引數。
int getopt(int argc,char * const argv[ ],const char * optstring);重點說下getopt()函式。前兩個形參是main函式傳入的引數，即我們輸入的命令列，第三個形參是 optstring“選項字串”，即標識哪些字母表示了操作。
如"a:b:cd::e"，字母后帶一個冒號（例中的a、b）表明這個操作帶引數，字母后的內容需要讀取，存放到它內部變數 extern char * optarg中。
字母不帶冒號（例中的c、e）表明該操作不帶引數，後面輸入的內容仍看作運算子處理。字母后帶兩個冒號（例中的d）表明該操作後引數是可選的，但是要求如果帶引數時引數與運算子不能有空格，如-d123是對的，而-d 123會報錯。當讀取了全部的輸入的命令後 getopt（）返回-1。
while((opt = getopt(argc,argv,"s:E:b:t:")) !=-1){ //解析命令列引數 switch(opt){ case 's': s=atoi(optarg); break; case 'E': E=atoi(optarg); break; case 'b': b=atoi(optarg); break; case 't': filepath = optarg; break; } }fscanf函式，該函式能夠幫助使用者處理文字檔案中輸入的格式化資料。
int fscanf(FILE *stream, char *format[,argument...]);stream-這是指向 FILE 物件的指標，該 FILE 物件標識了流。
format-這是 C 字串，包含了以下各項中的一個或多個：空格字元、非空格字元和format 說明符。
2.2 快取記憶體定義結構體實驗要求中說明了，不需要處理b，只需認為每行中有一個block。因此cache_line結構體中包括有效位，標記位，時間戳三個變數就夠了。stamp記錄的是block 的使用時間，每被使用一次，block++。因此，stamp越大表明該block越是最近被使用。具體程式碼如下。
typedef struct{ int valid_bits; unsigned tag; int stamp;}cache_line;定義一個Cache[S] [E]大小的二維陣列。這樣Cache就模擬好了。
void init(){ cache = (cache_line**)malloc(sizeof(cache_line*)*S); //malloc開闢空間 for(int i=0;i<S;i++) *(cache+i) = (cache_line*)malloc(sizeof(cache_line)*E); for(int i=0;i<S;i++){ for(int j=0;j<E;j++){ cache[i][j].valid_bits = 0; // 初始化有效位為0 cache[i][j].tag = 0xffffffff; //初始化標記位 cache[i][j].stamp = 0; //這個時間戳模擬LRU的時候會用到 } }}先分析每個輸入的指令應該被如何操作。如果是I，則不是資料操作，直接忽略。如果是L或者S，則需要進行一次hit-miss-eviction檢測，如果是M，則相當於先L再S，需要進行兩次hit-miss-eviction檢測。然後考慮hit-miss- eviction檢測細節。
while(fscanf(file," %c %x,%d",&operation,&address,&size)>0){ switch(operation){ case 'L': update(address); break; case 'M': update(address); case 'S': update(address); break; } time(); }首先需要對讀取的地進有分析，低b位表示 block偏移，本實驗中不需要計算block偏移。中間s位是 set index位，表示對那個行操作。其餘t位是tag位。用於標明對應的line是否有效。我們需要對得到的地址進行如下操作，解析出t和s。
unsigned s_address =(address>>b) & ((0xffffffff)>>(32-s)); //索引位 unsigned t_address = address>>(s+b); //標記位替換策略使用的是LRU的快取替換策略。如果該set存滿了，我每次要找到stamp最小的替換。為了方便，我把stamp初始化為0，之後每個操作+1. 當stamp= 0的時候就代表不valid。
void time(){ for(int i=0;i<S;i++){ for(int j=0;j<E;j++){ if(cache[i][j].valid_bits == 1) cache[i][j].stamp++; } }} for(int i=0;i<E;i++){ if(cache[s_address][i].stamp > max_stamp){ max_stamp = cache[s_address][i].stamp; max_i = i; } }Cache的容量有限，當滿的時候需要替換行，先遍歷當前組，判斷它滿了沒有，如何判斷是否滿，可以遍歷所有的行，只要有一個有效位為0，（有效位的作用是說明該行是否儲存了資料，通俗的理解就是是否為空）則該組未滿。
for(int i=0;i<E;i++){ if(cache[s_address][i].valid_bits == 0){ cache[s_address][i].tag = t_address; cache[s_address][i].valid_bits = 1; cache[s_address][i].stamp = 0; miss++; return; }}/* * @Description: 程式設計模擬Cache * @Version: V1.0 * @Autor: 嵌入式與Linux那些事 * @Date: 2021-1-1 20:40:12 * @LastEditors: 嵌入式與Linux那些事 * @LastEditTime: 2021-1-1 22:11:58 */#include "cachelab.h"#include <getopt.h>#include <stdlib.h>#include <unistd.h>#include <stdio.h>#include <stddef.h>typedef struct{ int valid_bits; unsigned tag; int stamp;}cache_line;char* filepath = NULL;int s,E,b,S; // s 表示組 ,E表示行,每一行有 2^b位 ,S = 2^s 組int hit=0,miss=0,eviction=0;cache_line** cache = NULL;void init(){ cache = (cache_line**)malloc(sizeof(cache_line*)*S); //malloc開闢空間 for(int i=0;i<S;i++) *(cache+i) = (cache_line*)malloc(sizeof(cache_line)*E); for(int i=0;i<S;i++){ for(int j=0;j<E;j++){ cache[i][j].valid_bits = 0; // 初始化有效位為0 cache[i][j].tag = 0xffffffff; //初始化標記位 cache[i][j].stamp = 0; //這個時間戳模擬LRU的時候會用到 } }}void update(unsigned address){ unsigned s_address =(address>>b) & ((0xffffffff)>>(32-s)); //從地址分解出索引位 unsigned t_address = address>>(s+b); //從地址分解出標記位 //判斷tag為是否相等，是否命中 for(int i=0;i<E;i++){ if((*(cache+s_address)+i)->tag ==t_address){ cache[s_address][i].stamp = 0; //被使用了 hit++; return; } } //更新快取記憶體cache for(int i=0;i<E;i++){ if(cache[s_address][i].valid_bits == 0){ cache[s_address][i].tag = t_address; cache[s_address][i].valid_bits = 1; cache[s_address][i].stamp = 0; //now ,this is load miss++; return; } } //暴力實現LRU int max_stamp=0; int max_i; for(int i=0;i<E;i++){ if(cache[s_address][i].stamp > max_stamp){ max_stamp = cache[s_address][i].stamp; max_i = i; } } eviction++; miss++; cache[s_address][max_i].tag = t_address; cache[s_address][max_i].stamp = 0; }//更新stampvoid time(){ for(int i=0;i<S;i++){ for(int j=0;j<E;j++){ if(cache[i][j].valid_bits == 1) cache[i][j].stamp++; } }}int main(int argc,char *argv[]){ int opt; while((opt = getopt(argc,argv,"s:E:b:t:")) !=-1){ //解析命令列引數 switch(opt){ case 's': s=atoi(optarg); break; case 'E': E=atoi(optarg); break; case 'b': b=atoi(optarg); break; case 't': filepath = optarg; break; } } S = 1<<s; init(); FILE* file=fopen(filepath,"r"); if(file == NULL){ // 讀取檔案錯誤 printf("Open file wrong"); exit(-1); } char operation; unsigned address; int size; while(fscanf(file," %c %x,%d",&operation,&address,&size)>0){ switch(operation){ case 'L': update(address); break; case 'M': update(address); case 'S': update(address); break; } time(); } for(int i=0;i<S;i++) //釋放 cache[S][E] free(*(cache+i)); free(cache); fclose(file); //關閉檔案 printSummary(hit,miss,eviction); //本次實驗使用的是HNU的自動評分系統，它會讀取這條語句進行評分。 return 0;}HNU的自動評分系統會測試我們編寫的程式碼是否可以透過所有的測試用例，和Reference simulator的對比表明，結果完全相同。測試透過！