[TOC] ## 高速緩存的工作原理  1. CPU需要的數據在緩存里 2. CPU需要的數據不在緩存里 3. 不在緩存的數據需要去主存拿 ## 主存原理 - **字**:是指存放在一個存儲單元中的二進制代碼組合 - **字塊**:存儲在連續的存儲單元中而被看作是一個單元的一組字  **字的地址**  ### 思考題 例子:假設主存用戶空間容量為4G,字塊大小為4M,字長為32位,則對于字地址中的塊地址m和塊內地址b的位數,至少應該是多少? ``` 4G=4096M 求一共的字塊數M: 4096/4=1024 字塊地址m: 2^m=M -> log2 1024=10 //至少需要10位為才能標識 1024 大小 塊內字數 B : 4M / 32 bit = 4*1024*1024*8/32 bit = 1048576 bit 塊內地址b: 2^b=B -> log2 1048576=20 m>=10 b>=20 ``` ## 緩存原理  緩存原理與主存類似:  ### 命中率 - 命中率是衡量緩存的重要性能指標 - 理論上CPU每次都能從高速緩存取數據的時候,命中率為1 ### 計算命中率 h 訪問主存次數 `$ N_{m} $`: 訪問緩存次數 `$ N_{c} $`: `$ h=\frac{N_{c}}{N_{c}+N_{m}} $` ### 計算訪問效率 e 訪問主存時間: `$ {t_{m}} $` 訪問緩存時間: `$ {t_{c}} $` 訪問緩存-主存系統的平均時間:`$ {t_{a}} = h{t_{c}}+(1-h){t_{m}} $` 訪問效率 :`$ e=\frac{t_{c}}{t_{a}}=\frac{t_{c}}{h{t_{c}}+(1-h){t_{m}}} $` ### 思考題 例子:假設CPU在執行某段程序時,共訪問了 Cache命中2000次,訪問主存50次,已知 Cache的存取時間為50ns,主存的存取時間為200ns,求 Cache主存系統的命中率、訪問效率和平均訪問時間。 命中率:`$ h=\frac{N_{c}}{N_{c}+N_{m}}=\frac{2000}{2000+50}=0.97 $` 訪問效率 :`$ e=\frac{t_{c}}{t_{a}}=\frac{t_{c}}{h{t_{c}}+(1-h){t_{m}}}=\frac{50}{0.97*50+(1-0.97)200}=0.917=91.7% $` 平均訪問時間`$ 0.97*50+(1-0.97)200=54.5ns $` ## 高速緩存的替換策略 ### 隨機算法 ### 先進先出算法(FFO)  ### 最不經常使用算法(LFU) - 優先淘汰最不經常使用的字塊 - 需要額外的空間記錄字塊的使用頻率  ### 最近最少使用算法(LRU) - 優先淘汰一段時間內沒有使用的字塊 - 有多種實現方法,一般使用雙向鏈表 - 把當前訪問節點置于鏈表前面(保證鏈表頭部節點是最近使用的) ``` // 假設緩存4個字塊, () 表示使用的字塊,[]表示淘汰的字塊 (1) (2),1 (4),2,1 (7),4,2,1 (5),7,4,2->[1] (4),5,7,2 (6),4,5,7->[2] (1),6,4,5->[7] (6),1,4,5 (7),6,1,4->[5] (4),7,6,1->[4] (1),4,7,6 ```