計算機系統結構複習（七）：Memory 存儲系統
- 存儲系統的層次結構
-
- 存儲結構考慮的問題
- 局部性原理
- 映像規則
- 查找算法
- 替換算法： Random、LRU、FIFO
- 寫政策：寫直達與寫回， 按寫配置設定與不按寫配置設定
- 寫緩存Write Buffer P219
- 平均訪存時間= 命中時間+不命中率*不命中開銷
- 程式執行時間
- Cache優化政策 P207 P225
-
- 兩級cache 的好處 P216
- Cache不命中的三種原因：強制、容量與沖突 P209
- 虛存空間P232
-
- Cache和虛存的差別
- 頁表計算
- TLB位址變換後備緩存（快表）
存儲系統的層次結構
常見的五級存儲結構：
寄存器->cache->主存->disk(輔存)-> tape(磁盤)
存儲結構考慮的問題
1.映像規則：當把一個塊（頁），調入高一層存儲器時，可以放到哪些位置？
2.查找算法：當所要通路的塊在高一層存儲器時，如何找到？
3.替換算法：當發生不命中，且高一層存儲器已滿，應如何替換？
4.寫政策：當進行寫通路向Cache中寫入新資料時，如何操作？
局部性原理
局部性原理：程式所通路的指令和資料在位址上不是均勻分布的，而是相對聚簇的。 局部性原理是程式能進行随機性通路的基礎。
時間局部性：目前某項被通路，那麼近期他可能還會被通路。例如循環。
空間局部性：目前某項被通路，那麼他附近的項也可能被通路。
映像規則
查找算法
其中 tag 是塊标記，index是組标記。index的位數表示分組數，tag 的位數表示相聯度。
直接映像候選位置1個，全相聯M個，n路組相聯n個。 查找時隻需比較辨別tag，索引index 無需比較。
替換算法： Random、LRU、FIFO
對于直接映射：位置唯一，缺失必須替換對應位置的頁。不需要替換算法。
對于全相連和n塊組相連：随機，LRU，先入先出。具體方法見作業系統。
寫政策：寫直達與寫回， 按寫配置設定與不按寫配置設定
寫政策：寫通路會導緻Cache與主存的内容不一緻，為保證正确性，主存的内容也需要更新。
寫直達法：寫操作不僅把資料寫入Cache中的塊，還直接寫入主存中。
寫回法：寫操作隻寫Cache，隻當相應的塊要換出時才寫回主存中。
按寫配置設定：寫失效時，先把所寫單元所在的塊調入 Cache，再行寫入。即要寫的資料在Cache中。 寫回法常用按寫配置設定的方法。
不按寫配置設定：寫失效時，隻寫到主存中，不将相應 的塊調入Cache。 寫直達法常用不按寫配置設定的方法。
寫緩存Write Buffer P219
寫緩沖原因：在寫直達法中，因為速度較慢CPU必須等待，直到寫操作結束（CPU寫停頓）。是以通過buffer解決，CPU把資料寫入buffer就繼續運作。
為什麼不用reg：寫操作可能是爆發性的。
RAW沖突是否會發生：會，記憶體與Cache的資料不一緻時buffer排空。
平均訪存時間= 命中時間+不命中率*不命中開銷
程式執行時間
Cache優化政策 P207 P225
cache優化從平均通路時間公式中的的三個要素入手：
1.降低不命中率： 更大的塊、更大的Cache、更高的相聯度。
2.減少不命中開銷： 兩級Cache、使讀不命中優先于寫。
3. 減少命中時間： 使Cache進行索引時不進行位址轉換。
兩級cache 的好處 P216
兩級Cache： 為了解決CPU和存儲器之間性能差距越來越大的問題，當一級Cache不能滿足要求時，可以在原有 Cache和存儲器之間增設一級。
平均通路時間= Hit timeL1+ Miss rateL1x (Hit timeL2+ Miss rateL2x Miss penaltyL2)
Cache不命中的三種原因：強制、容量與沖突 P209
相關結論：
1.相聯度越高，沖突不命中就越少；
2.強制性不命中和容量不命中不受相聯度的影響；
3.強制性不命中不受Cache容量的影響，容量不命中随着容量增加而減少，當Cache總容量不變時， 沖突不命中随着容量增加而增加（塊數減少）。
4.容量不命中除了增大Cache以外别無他法。
5.三種沖突中，強制性不命中率最小，沖突不命中最容易解決（全相聯）。
更大的塊将導緻更大的Miss Penalty例題
問題：
假定存儲系統在延遲20個時鐘周期後，每2個時鐘周期能送出16個位元組。即經過22個時鐘周期，可提供16位元組；經過 24個時鐘周期，可提供32位元組；依此類推。命中時間與塊大小無關，為1個時鐘周期，分别計算下列各種容量的Cache的 平均通路時間。
- 塊大小為32位元組，Cache容量為1KB，不命中率為10%；
塊大小為64位元組，Cache容量為4KB，不命中率為5%；
答案：
1 + （（32/16）* 2 + 20）* 10% = 3.4個時鐘周期
1+（（64/16）* 2 + 20）* 5% = 2.4個時鐘周期
虛存空間P232
虛存由主存和輔存構成，通過必須的軟體（頁表機制）和硬體（位址轉換）支援，使得cpu訪 問的存儲器可以有主存的速度和輔存的容量。 虛存分為頁式和段式。
Cache和虛存的差別
1.cache缺失靠硬體彌補，虛存缺失靠軟體（作業系統）
2. 指令中的位址長度決定了虛存大小，cache大小與之沒有關系。
3. cache是為了緩解CPU和主存之間的速度問題， 虛存是為了緩解主存容量不足問題。
頁表計算
問題：
32位虛位址空間（按照位元組尋址），每頁4KB，頁表每項4位元組(32bit)，頁表大小是？
答案：
頁表有 2^32B / 2^12B 個項，每項大小是4B。 是以頁表總大小為兩者積=4MB。 每個程序都要有自己的頁表，每個頁表要4MB，頁表可能太多無法裝入記憶體（頁表存在記憶體中 ），是以有了二級頁表。
TLB位址變換後備緩存（快表）
TLB：是一個專用的高速緩沖器，用于存放近期經常使用的頁表項。根據局部性原理，可提升對存儲器 的通路速度。（傳統查找頁表的方法需要對主存進行二次查找）
項由兩部分構成：辨別和資料。