第六章 記憶體

了解各層之間對系統效能的影響, 以及如何量測效能. 第六章 教學目的 熟悉記憶體階層架組織的概念. 了解各層之間對系統效能的影響, 以及如何量測效能. 熟悉快取, 虛擬記憶體, 記憶體分段, 分頁, 以及位址轉換背後的概念.

在前面的章節中, 我們學到組成記憶體的元件, 還有如何經由不同的ISA來存取記憶體位置. 6.1 簡介 記憶體是內儲程式電腦的核心. 在前面的章節中, 我們學到組成記憶體的元件, 還有如何經由不同的ISA來存取記憶體位置. 在本章中, 我們專注在記憶體的組織. 我們必需清楚的了解這些觀念, 這對分析系統效能來說是很重要的.

6.2 記憶體的類型 主記憶體有二種: 隨機存取記憶體 (random access memory), RAM, 以及唯讀記憶體(read-only-memory), ROM. RAM也有二種, 動態 (dynamic) RAM (DRAM) 和 靜態 (static) RAM (SRAM). 動態 RAM 是由電容所構成, 它會隨著時間慢慢的漏電, 所以每經過幾百萬分一秒就要充電一次來防止資料的流失. DRAM是“廉價”的記憶體, 因為它的設計很簡單.

6.2 記憶體的類型 SRAM 的組成元件為第三章所學的 D 型正反器. SRAM 是一種很快的記憶體, 它不像DRAM需要充電. 它通常用作快取記憶體, 我們等會兒會詳細介紹. ROM 也不需要充電. 事實上, 它只需要一點點的電荷就足以維持記憶體中的資料. ROM 是用來儲存永久性或是半永久性的資料, 當系統關機時, 資料都還能繼續保存.

為了用最低的價格提供最好的效能, 記憶體會以階層的型式還組成. 小又快的儲存元件會放在CPU內, 較慢的主記憶體會透過資料匯流排來存取. 6.3 記憶體階層 一般來說, 較快的記憶體會比慢的貴. 為了用最低的價格提供最好的效能, 記憶體會以階層的型式還組成. 小又快的儲存元件會放在CPU內, 較慢的主記憶體會透過資料匯流排來存取. 大型的永久性儲存體, 如硬碟和磁帶機離CPU最遠.

6.3 記憶體階層 可將儲存體的組織想像成金字塔:

當要存取某個資料時, CPU會先將需求送到最近的記憶體, 通常是快取. 6.3 記憶體階層 當要存取某個資料時, CPU會先將需求送到最近的記憶體, 通常是快取. 如果資料不在快取中, 就會去主記憶體尋找. 如果資料不在主記憶體, 就會去磁碟尋找. 一但找到資料後, 資料本身和鄰近的資料就會被擷取進快取中.

6.3 記憶體階層 一些定義. hit 就是當資料在某給定的記憶體階層中被找到. miss 就是沒找到. hit rate 就是在某記憶體階層中找到資料的比例. miss rate就是在某記憶體階層中沒找到資料的比例. Miss rate = 1 - hit rate. hit time 就是在給定的記憶體層級存取所需要的時間. miss penalty 就是處理miss所需要花費的時間, 包括置換記憶體區塊的時間, 加上將資料傳給處理器的時間.

6.3 記憶體階層 當hit時, 會將複製整個區塊的資料, 因為區域性原則(principle of locality)告訴我們當有一個 byte被存取時, 它鄰近的資料很快的也會被存取到. 有三種區域性: 時間區域性 – 最近存取過的資料會傾向再被存取. 空間區域性 – 存取有叢聚性. 循序區域性 – 指令傾向於循序存取.

6.4 快取記憶體 快取記記憶體的目的是為了加速存取最近存取過的資料, 將其放在靠CPU近一點的地方, 取代存放在主記憶體. 雖然快取比主記憶體小很多, 但是它的存取時間只有主記憶體的幾分之一而已. 主記憶體是靠位址來存取的, 然而, 快取則是靠內容存取; 所以, 它又稱為內容定址記憶體(content addressable memory). 因為如此, 快取記憶體都不會太大- 搜尋的時間會太長.

在內容定址快取中的“內容” 就是主記憶體位址的子集, 稱為欄位. 這個欄位是記憶體位址的一部份, 有多對一的對映關係. 6.4 快取記憶體 在內容定址快取中的“內容” 就是主記憶體位址的子集, 稱為欄位. 這個欄位是記憶體位址的一部份, 有多對一的對映關係. 記憶體中有很多區塊會對應到快取中的同一個區塊. 快取中的tag欄位會區分出是那一個區塊.

6.4 快取記憶體 最簡單的快取對映機制就是直映式快取(direct mapped cache). 直映式快取由 N 個區塊所組成, 主記憶體區塊 X 會對應到 快取區塊 Y = X mod N. 因此, 如果我們有10個快取區塊, 快取區塊7內的資料就有可能是主記憶體的 區塊 7, 17, 27, 37, . . . 當記憶體的區塊被複製到快取時, 就會設定快取區塊的valid bit, 讓系統知道該區快內有有效的資料. 如果沒有valid bit會發生什麼事呢?

6.4 快取記憶體 快取看起來就像下面的方塊圖. 區塊 0 包含多個記憶體字組 可由 tag 00000000分辨. 區塊1 包含可由 tag 11110101 分辨的字組. 其它二個區塊是無效的.

6.4 快取記憶體 記憶體位址每個欄位要切多大是視快取的大小而定的. 假設我們的記憶體有214字組, 快取有 16 = 24 區塊, 每個區塊有 8 個字組. 因此記憶體會分成 214 / 2 8 = 211 區塊. 以我們的欄位大小來說, 我們知道我們需要 4 bits 給區塊, 3 bits 給字組, 其它的留給 tag :

6.4 快取記憶體 舉例來說, 假設有一個程式產生位址1AA. 以14 bits來表示為: 00000110101010. 前 7 bits 是 tag 欄位, 接著 4 bits 是區塊欄位, 而最後3bit是區塊中的那一個字組.

6.4 快取記憶體 如果程式接著產生位址1AB, 那就會發現所找尋的資料在區塊 0101, 字組 011. 然而, 如果程式產生位址, 3AB, 那因為 1AA而載入的區快塊就會被逐出快取, 接著放入有3AB的區塊.

假設有一程試產生一連串的記憶體參考位址: 1AB, 3AB, 1AB, 3AB, . . . 那快取就會一直在置換. 6.4 快取記憶體 假設有一程試產生一連串的記憶體參考位址: 1AB, 3AB, 1AB, 3AB, . . . 那快取就會一直在置換. 那快取的理論優勢在這個極端的狀況下就不存在了. 這是直映式快取的最大缺點. 其它的快取對映機制在設計時會避免這種振蕩的現象.

6.4 快取記憶體 我們讓區塊可以放在快取的任何位置來代替直映式那種方式. 如此一來, 任何區塊要被換出去前快取一定就是滿的了. 這就是全關聯式快取(fully associative cache)的運作. 記憶體位址分成二個欄位: tag 和字組( word).

6.4 快取記憶體 如前面的假設, 我們有14-bit 記憶體位址, 還有一個 16區塊的快取, 每個區塊的大小為 8. 這個記憶體參照的欄位格式為: 當快取搜詢時, 所有 tags 都是平行搜尋來加快資料的擷取速度. 這需要特殊, 昂貴的硬體才能達成.

6.4 快取記憶體 每當有記憶體參照到那個區塊, 直映式快取就要將區塊換出. 在全關聯式快取中, 我們並沒有這樣的關係存在, 因此我們必需想出一套演算法來找出那個區塊要被置換出去. 要被換出去的區塊就稱為 victim block. 我們等一下就會介紹幾種挑選victim block的方式.

6.4 快取記憶體 集合關聯式快取結合了直映式和全關聯式快取的觀念. 一個 N-路集合關聯式快取就像直映式快取一樣會對應到某特定的位置. 但是集合關聯式快取不能對應到快取的任意位置, 只能對應到某些集合.

集合關聯式中集合的快取區塊數目是根據整個系統的設計而改變的. 舉例來說, 一個 2-路集合關聯式快取可以抽象為下列的綱目. 6.4 快取記憶體 集合關聯式中集合的快取區塊數目是根據整個系統的設計而改變的. 舉例來說, 一個 2-路集合關聯式快取可以抽象為下列的綱目. 每個集合有二個不同的區塊.

6.4 快取記憶體 在集合關聯式快取的對應中, 記憶體參照被分成三個欄位: tag, set, 和 word, 如下圖所示. 如同直映式快取, the word 欄位選擇快取區塊中的 word, 而 tag 欄位負責唯一識別記憶體位址. set 欄位決定記憶體區塊對應到那個set.

6.4 快取記憶體 假設我們有一個 214 bytes的記憶體. 這個記憶體對應到一個 2-路集合關聯式快取, 這個快取有16個區塊, 每個區塊有8 words. 因為是 2-路的快取, 每個集合有2個區塊所以有 8 sets. 因此, 我們要有 3 bits 給 set, 3 bits 給 word, 8 留給tag:

在全關聯和集合關聯式快取中, 當需要有區塊被換出時, 就會牽涉到區塊置換法則(replacement policy). 6.4 快取記憶體 在全關聯和集合關聯式快取中, 當需要有區塊被換出時, 就會牽涉到區塊置換法則(replacement policy). 最佳化的置換法則能夠預見未來最久不會被用到的區塊是那個. 雖然最佳化的置換法則是不可能實作出來的, 但是可以把它當成是一個標準來比較其它法則的好壞.

6.4 快取記憶體 我們所選的置換法則是看我們要最佳化那種區域性– 通常我們會選時間區域性. 最近最少使用演算法( least recently used (LRU) algorithm) 會檢查上一次區塊被使用的時間, 然後最長時間沒被使用的區塊就會被換出去. 這個方法的缺點就是複雜度太高: LRU 必需去記錄每個區塊的使用歷程, 這會讓快取的速度變慢.

先進先出 (First-in, first-out (FIFO))是一種最普遍的快取置換法則. 6.4 快取記憶體 先進先出 (First-in, first-out (FIFO))是一種最普遍的快取置換法則. 在 FIFO中, 在快取中最久的區塊會換出, 不論它上次是那時候用到. 隨機(random)置換法則就如同其名一樣: 它會隨機挑選一個區塊來換新的區塊. 隨機置換可能換到常用或快被用到的, 不過它永遠不會有振蕩的情況發生.

6.4 快取記憶體 階層式記憶體的效能是以有效存取時間(effective access time (EAT))來衡量的 EAT 是一個將hit ratio和記憶體層級間相對存取時間一起考量的加權平均值. 一個二階層的EAT為: EAT = H  AccessC + (1-H)  AccessMM. 這邊 H 是快取的 hit rate 而 AccessC 和AccessMM 分別是快取和主記憶體的存取時間.

6.4 快取記憶體 舉例來說, 有一個系統的記憶體存取時間為 200ns 而快取的存取時間為 10ns, hit rate 為99%. 則 EAT 為: 0.99(10ns) + 0.01(200ns) = 9.9ns + 2ns = 11ns. 這個方程式可以擴充為任意層級的記憶體組織, 我們等等就會看到.

快取置換法則必需把dirty blocks也考慮進去, 這個區塊在快取中已經被更新了. 6.4 快取記憶體 快取置換法則必需把dirty blocks也考慮進去, 這個區塊在快取中已經被更新了. Dirty blocks 必需寫回記憶體才行. 決定了如何進行這項動作. 寫入法則有二種: 直寫式 (write through)和回寫式(write back). 直寫式會同時更新快取和主記憶體.

6.4 快取記憶體 回寫式 (又稱 copyback) 只有在區塊要被置換出去時才更新記憶體. 直寫式的缺點就是每次快取更新記憶體就要跟著跟新, 這樣會拖慢更新的速度. 這種情況不嚴重, 因為大多數的存取都是讀而不是寫. 回寫式的優點就是記憶體的流量比較小, 但是缺點就是記憶體和快取中的值會有不一致的情況, 當系統中同時有很多使用者是就會出狀況.

6.5 虛擬記憶體 快取記憶體藉由較快的記憶體存取速度來增進效能. 虛擬記憶體則是在不增加主記憶體的情況下, 藉著提供較大的記憶體空間來增進效能. 換言之, 部份的磁碟空間被當成主記憶體的延伸. 如果系統使用分頁, 虛擬記憶體會將主記憶體分成一個個的頁框(page frame), 當它們沒有要用時就寫回磁碟去.

6.5 虛擬記憶體 實體位址(physical address) 是實體記憶體真正的位址. 程式產生虛擬位址在經由記憶體管理器轉換成實體位址. 分頁失誤(Page faults)的發生是由於邏位址所需的分頁要從磁碟載入. 記憶體破碎(Memory fragmentation)的發生是因為分頁的過程而造成的一些無法使用之小型記憶體位址空間.

6.5 虛擬記憶體 主記憶體和虛擬記憶體所切的頁大小會相同. 行程的整個位址空間不必一定要全部在記憶體. 部份可以在記憶體, 而部份可以在主記憶體. 而且, 分配給行程的分頁不一定在儲存在連續的空間中 – 不管是在磁碟或記憶體都一樣. 在這之下, 只有所需的分頁會在記憶體內, 不需要的分頁就暫時放在較慢的磁碟儲存存裝置.

6.5 虛擬記憶體 關於每個分頁是在磁碟或是記憶體的資訊是放在一個叫分頁表的資料結構中. 每一個動作中的行程都有一個分頁表.

6.5 虛擬記憶體 當行程產生了虛擬位址, 作業系統就換將它轉換成實體位址. 為了完成這樣的轉換, 虛擬位址要分成二個欄位: 分頁欄位(page field), 和偏移欄位 (offset field). 分頁欄位決定了分頁位置的位址, 而偏移則指出分頁內位置的位址. 邏輯分頁號碼會透過分頁表轉換成實體頁框.

6.5 虛擬記憶體 如果分頁表中的valid bit為0, 表示該分頁不在記憶中, 要從磁碟攫取. 這就是分頁失誤 page fault. 必要時, 必需從記憶體挑選出一個分頁來置換, 然後換入業新頁後再將 valid bit 設為 1. 如果 valid bit 是 1, 虛擬分頁號碼就換成是實體頁框號碼. 將偏移量加上實體頁框號碼就可以存取到資料了.

6.5 虛擬記憶體 舉例來說, 假設有一個系統的虛擬位址空間為8K, 實體位址空間為 4K, 該系統是byte定址的. 我們有 213/210 = 23 個虛擬分頁. 虛擬位址有 13 bits (8K = 213) 3 bits 為 page field, 10 bits 為offset, 因為 page 的大小為 1024. 實體記憶體位址需要12 bits, 頭二個bits 為 page frame 剩下的10 bits 是 offset.

6.5 虛擬記憶體 假設我們有如下的分頁表. 當CPU產生位址 545910 = 10101010100112時會發生什麼事?

6.5 虛擬記憶體 位址 10101010100112 會轉換成實體位址 010101010011. 因為經由分頁表 page field 101 會換成frame number 01.

6.5 虛擬記憶體 當 CPU 產生位址10000000001002時呢?

6.5 虛擬記憶體 我們先前曾說過, 有效存取時間(EAT)會將所有層級的記憶體都列入考慮. 因此, 在計算中, 虛擬記憶體也是因素之一, 而且我們也需要考慮分頁表的存取時間. 假設一個主記憶體存取要花費200ns, 分頁失誤發生率為1%, 要花費 10ms 將分頁載入到記憶體. 所以: EAT = 0.99(200ns + 200ns) 0.01(10ms) = 100, 396ns.

就算我們沒有分頁失誤, EAT 也要 400ns. 因為記憶體都要讀二次 : 第一次讀分頁表, 第二次從記憶體載入分頁. 6.5 虛擬記憶體 就算我們沒有分頁失誤, EAT 也要 400ns. 因為記憶體都要讀二次 : 第一次讀分頁表, 第二次從記憶體載入分頁. 因為分頁表一直被讀取, 所以我們將它放在一種特別的快取中, 稱為 translation look-aside buffer (TLB). TLBs 是一種特殊的關聯式快取, 它儲存著虛擬分頁和實體分頁的對應關係. 下一張投影片會做整體的介紹.

6.5 虛擬記憶體

6.5 虛擬記憶體 另一種虛擬記憶體是使用分段(segmentation)的方式. 分段方式將虛擬位址空間切成不同長度的段落, 而不像分頁都是相同大小的, 這大小通常是由程式設計人員決定的. 分段是透過分段表來定位的, 分段表包含了分段的記憶體位置和它的邊界限制來指定出大小. 分頁失誤後, 作業系統會搜尋記憶體找出足夠放置分段的空間來載入分段.

6.5 虛擬記憶體 分頁和分段都會引起破碎的情況. 分頁是會有內部破碎(internal fragmentation). 因為行程可能不需要整個分頁的大小. 因此, 可能會有些分頁中含有沒使用的破碎記憶體空間. 分段則是由於外部破碎 (external fragmentation), 這是因為分段在喔一段時間的配置和撤除過程中, 記憶體會有很多小的空間 但卻不是連續的, 不足以給其它分段使用.

我們可以結合分頁和分段的優點來設計一種固定頁匡大小的分段式架構. 6.5 虛擬記憶體 大的分頁表很麻煩也很慢, 但是因為它有均勻的記憶體對映, 分頁的操作比較快. 分段表存取的速度較快, 但是分段的載入是人工的(labor-intensive). 我們可以結合分頁和分段的優點來設計一種固定頁匡大小的分段式架構. 每個分段有一個分頁表. 這表示記憶體位址會有三個欄位, 一個是 segment, 另一個是 page, 第三個則是offset.

6.6 實例 Pentium架構支援分頁和分段二種架構, 而且可以不同的方式組合, 包括: 無分頁, 無分段; 分段, 無分頁, 以及無分段分頁. 處理器支援二層的快取 (L1 and L2), 區塊大小都為 32 bytes. L1 快取就在處理器旁邊, L2 快取則是介於處理器和記憶體之間. L1快取有二個部份 : 指令快取 (I-cache) 以及資料快取 (D-cache). 下一張投影片會有組織的綱要圖.

6.6 A Real-World Example

結論 電腦記憶體是以階層的方式組織而成的, with the 最小最快的記憶體在最上層, 最大最慢的記憶體在最底層. 快取記憶體的存取速度比主記憶體快, 而虛擬記憶體利用磁碟空間營造超大主記憶體的假像. 快取將主記憶體的區塊對應到快取的區塊, 虛擬記憶體將頁框對應到虛擬頁. 有三種常見的快取: 直映式(Direct mapped), 全關聯式(fully associative) 以及集合關聯式(set associative).

結論 要建立全關聯式和集合關聯式快取, 以及虛擬記憶體, 置換法則的概念. 置換法則包含 LRU, FIFO, 或 LFU. 這些法則也有考慮到dirty block. 所有的虛擬記憶體都要處理破碎的問題, 在分頁式是內部, 在分段式是外部.

End of Chapter 6