385
《計算機存儲與外設》----1.5 虛擬存儲器和存儲器管理
本節書摘來自華章出版社《計算機存儲與外設》一書中的第1章，第1.5節，作者Computer Organization and Architecture: Themes and Variations［英］艾倫·克萊門茨（Alan Clements） 著，沈 立 肖曉強 王蘇峰 譯，更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看。
1.5 虛擬存儲器和存儲器管理
存儲器管理（Memory Management）是操作係統和硬件的切合點，它關注的是管理主存儲器和磁盤。從許多方麵看，存儲器管理是一種擴展的Cache技術。
計算機剛出現時，計算機生成的地址對應物理或真實存儲器中操作數的位置。即使在今天，各種控製器中的8位微處理器通常不使用存儲器管理技術。在PC和工作站等高性能計算機上產生的邏輯地址（logical address），並不是操作數在存儲器中的物理地址（physical address）。考慮指令LDR r2,[r3]，其作用是將由r3寄存器指向的存儲器位置中的內容送入r2寄存器，假定寄存器r3的內容是0x00011234。數據可能來自基於DRAM的主存儲器中0x00A43234這個地址。將地址00011234翻譯成00A43234的過程叫作存儲器管理（memory management）。在本節中，將解釋為什麼存儲器管理是必要的，它是怎樣實現的。
虛擬存儲器（virtual memory）是從光學領域借用的術語，其中虛擬用於描述一種似乎在某個位置的虛擬圖像，例如，望遠鏡可以使處於很遠位置的物體看起來好像就在麵前一樣。虛擬存儲空間是邏輯地址空間（logical address space）的同義詞，用來描述計算機可以訪問的地址空間。具有64位地址和指針寄存器的計算機的虛擬（邏輯）地址空間為264字節，即使它在係統中可能隻有2G（231）字節的物理主存儲器。
存儲器管理起源於20世紀50年代～60年代，它代表將CPU產生的邏輯地址轉化成實際地址（即物理地址）的所有技術。存儲器管理允許DRAM和硬盤的物理地址空間無縫地合並到計算機的虛擬存儲器空間中。
1.5.1 存儲器管理
計算機使用如Windows或UNIX這樣的操作係統對存儲器管理技術進行擴展使用。圖1-26給出了一個具有存儲器管理單元（memory management unit，MMU）的係統的結構。原則上，操作非常簡單：來自CPU的邏輯地址送入MMU，然後被轉換為操作數在存儲器中的物理地址。將邏輯地址轉換成物理地址需要一個查找表（look-up table）。因為將每個邏輯地址都轉換成物理地址確實需要非常大的表，因此存儲空間通常被分成頁（page），每個邏輯頁中的地址被轉換成物理頁中對應的地址。一個頁通常為4KB。例如，如果頁大小為4KB，處理器有32位地址空間，邏輯地址0xFFFFAC24可能被轉換為0x00002C24。
處理器邏輯地址空間的大小與指定操作數的尋址方式無關。它也與程序是用高級語言、匯編語言還是機器代碼編寫無關。在32位的係統中，指令LDR r4,[r6]允許使用4GB的邏輯空間。無論采用何種技術，處理器不能指定4GB（範圍從0～232-1）以外的邏輯地址，這僅僅是因為其程序計數器的位數是有限的32位。
物理地址空間由處理器使用存儲器係統中所有的實際地址位置構成。該存儲器不是抽象的，是真正實現的。換句話說，係統的主存儲器構成物理地址空間。計算機邏輯地址空間的大小由指定地址所需的位數決定，而物理地址空間的大小通常隻受其成本限製。
現在可以看到，為什麼微處理器的邏輯和物理地址空間的大小是不同的。更奇怪的是為什麼微處理器使用存儲器管理，將例如0x00001234這樣的邏輯地址轉換為物理地址0x861234。存儲器管理係統的基本目的如下：
1）實現對物理地址空間大小超過了邏輯地址空間大小這樣的係統的控製（例如，某8位微處理器具有16位地址總線（64KB的邏輯空間）來訪問2MB的物理內存）。
2）實現對邏輯地址空間大小超過了物理地址空間大小這樣的係統的控製（例如，某32位微處理器具有4GB的邏輯地址空間，管理64MB的RAM）。
3）存儲器保護，包括防止一個用戶訪問分配給另一個用戶的存儲空間的機製。
4）存儲器共享，一個程序可以與另一個程序共享資源（例如，公共數據區或公共代碼）。
5）高效利用存儲器，最有效地使用物理地址空間。
6）將程序員從考慮程序和數據應該位於存儲器的何處中解放出來。即程序員可以根據其意願使用任意的地址，而存儲器管理係統會將邏輯地址映射到可用的物理地址。
一個真正的存儲器管理單元可以不必實現上述所有目標（注意前兩個目標是互斥的）。第二個目標（即邏輯地址空間大於物理地址空間）對於設計64位係統尤其重要。當針對該問題使用存儲器管理時，這就是經常所說的虛擬存儲器技術（virtual memory technology）。虛擬存儲器幾乎就是邏輯存儲器的代名詞。
可用物理地址空間小於處理器的邏輯地址空間是由於經濟問題所造成的，並一直困擾著主流企業。20世紀50年代末，大型機可使用大的邏輯地址空間，但隻能使用2K左右的RAM。英國曼徹斯特大學的一組計算機科學家提出存儲器管理技術（現被稱為虛擬存儲器）來解決該問題。他們將部分的邏輯（虛擬）地址空間映射到可用的物理地址空間，如圖1-27所示。該例中，256KB的一段邏輯地址，範圍從780000～7BFFFF，被映射到物理存儲器範圍從00000～3FFFF的區域。隻要處理器訪問邏輯地址空間中的數據，其地址將被映射到相應的物理地址，一切都很順利。這裏假定從CPU發出的地址將直接（即不改變地）交給係統的地址總線。
當處理器產生操作數的邏輯地址不能被映射到可用的物理地址空間時就會出現問題。曼徹斯特大學采用的解決方案非常簡單。每當處理器生成沒有物理地址對應的邏輯地址時，操作係統中止當前程序的執行並處理該問題。操作係統從磁盤存儲器中取出一塊包含所需操作數的塊，並把該塊放在物理存儲器中（覆蓋所有舊的數據），然後告訴存儲器管理單元，邏輯地址空間和物理地址空間之間存在一個新的關係。換句話說，程序或數據被保存在磁盤中，隻有當前需要的部分程序被傳送到物理RAM中。存儲器管理單元跟蹤由處理器產生數據的邏輯地址與該數據在物理存儲器中位置之間的關係。整個過程非常複雜，需要在處理器體係結構、存儲器管理單元以及操作係統之間進行協調。人們希望看到簡單的虛擬存儲器係統，但實際這是一場噩夢。
1.5.2 虛擬存儲器
虛擬存儲器係統有4個作用：支持比物理地址空間更大的邏輯存儲空間，實現邏輯地址到物理地址的映射，為邏輯地址空間中運行的任務分配物理存儲器，更加方便地建立多任務的係統。
使用有限的文字就能討論清楚虛擬存儲器的所有話題是不可能的。設計者和程序員組成的團隊花費很長的時間來設計虛擬存儲器係統，這是因為虛擬存儲器的管理不僅複雜而且幾乎在支持多用戶或多任務操作係統的係統中通常都是各不相同的。本節隻對虛擬存儲器進行概述。
1.存儲器管理和多任務
多任務係統通過周期性地在任務之間進行切換以支持兩個或多個進程同時執行。顯然，多任務處理隻有當幾個任務同時駐留在主存儲器中時才是可行的。如果任務每次運行都必須從硬盤裝載，則切換新任務需要的時間將過長。
圖1-28演示了具有兩個任務的係統中如何將邏輯地址空間映射到物理地址空間。圖中，任務A和B同時駐留在物理存儲器中。每個任務都有其自己的邏輯存儲空間（例如，程序和堆棧）可以訪問位於物理存儲空間的共享資源。程序員可以完全自由地為任務的不同組件選擇其自身的地址。因此，圖1-28中，任務A和B可以訪問物理存儲器中相同的數據結構，即使它們使用不同的邏輯地址。即每個任務隻知道自己與另一個任務共享數據的一個副本。
存儲器管理單元將程序員選擇的邏輯地址映射到物理存儲器空間，而操作係統負責建立邏輯地址到物理地址的映射表。當創建一個新的任務時，將告知操作係統任務對存儲器的需求。操作係統搜索可用的物理存儲器空間，尋找空閑的存儲塊並將其分配給任務。可以想象，一段時間後，物理存儲器空間可能會變得支離破碎，每個任務占用不同的存儲塊，以非常複雜的方式交織在一起。一個好的操作係統應該有效地執行存儲器分配，不允許物理存儲器中存在大量未使用的塊。存儲器分塊的方式取決於存儲器映射實現的方式和操作係統。
存儲器映射的一個強大功能是，每個邏輯存儲器塊可被賦予各種權限。例如，存儲器可以是隻讀、隻寫、隻能通過操作係統或給定的任務訪問或在一組任務之間共享。通過確保物理存儲器塊隻能被預先定義的任務訪問，可以確保一個任務的執行不會導致另一個任務崩潰。有兩種實現存儲器管理的基本方式。使用固定大小的存儲器塊，稱為頁（page）；另一種使用可變大小的存儲器塊，稱為段（segment）。
2.地址翻譯
存儲器管理提供了兩種不同的服務。第一種是將邏輯地址映射到可用的物理存儲器中。第二種功能發生在物理地址空間耗盡時（即由於數據不在隨機訪問存儲器中，邏輯地址到物理地址的映射已不能完成）。
圖1-29顯示了一個頁式存儲係統是如何實現的。該例使用24位邏輯地址總線和512KB的存儲器係統。來自處理器的24位邏輯地址被分成16位的偏移（被直接傳給物理存儲器）以及8位的頁地址。頁地址指向處理器當前訪問的頁（28=256個頁中的一個）。邏輯地址的位移量可以訪問64KB頁中的216個位置上的數據。
頁表包含256項，每一項對應一個邏輯頁。例如，在圖1-29中，CPU正訪問8位邏輯頁地址000001112。每項包含3位的頁幀地址，是物理地址最重要的3位。該例中，物理頁地址為110。邏輯地址從8+16位變成了3+16位，邏輯地址00000111 0000101000110010被映射到物理地址110 0000101000110010。
雖然在頁表中有256個可能的項（每項對應一個邏輯頁），物理頁地址隻有3位，它限製物理頁隻有8個。因此，隨機訪問存儲器中不同的物理頁不能與每個可能的邏輯頁相對應。每個邏輯頁地址有一位R字段與之相關聯表示駐留。如果R位置為1，表示該頁當前在物理存儲器中。如果R位被清零，對應的頁將不在物理存儲器中，頁地址字段的內容將毫無意義。
每當產生邏輯地址且與當前邏輯頁相關的R位被清除，將發生頁故障（page fault）事件。一旦開始訪問某個邏輯地址，由於R位被清除表示當前頁不在存儲器中，當前的指令必須暫停，因為它無法完成。
典型的微處理器具有總線錯誤輸入引腳，表明存儲器訪問無法完成。當發生這種情況時，操作係統開始幹預處理。雖然CPU試圖訪問的數據目前不在隨機訪問存儲器中，但它在磁盤中。操作係統從磁盤檢索包含所需存儲器位置的頁，將其加載到物理存儲器中，並相應地更新頁表。被暫停的指令可以繼續執行。
該過程簡單嗎？完全不簡單。當操作係統從磁盤獲取一個新的頁，它必須覆蓋一個隨機訪問物理存儲器的頁。注意，虛擬存儲器的一個功能是允許使用相對小的物理存儲器來模擬大容量存儲器。如果要用新頁替換舊頁，此時需要一個策略選擇替換哪個舊頁。經典的替換策略是最近最少使用（least recently used，LRU）算法，最長時間沒有被訪問的頁將被新的頁覆蓋（也就是說，如果最近沒有訪問這個頁，則在不久的將來也不太可能訪問它）。
LRU算法已在實踐中被檢驗可以很好地工作。不幸的是，如果采用該策略，操作係統必須知道每個頁是什麼時候被訪問的，這需要複雜的硬件（每個頁必須在被訪問後打上時間戳）。操作係統必須處理的另一個問題是，存儲在RAM中和保存在磁盤上的數據之間的一致性問題。如果從磁盤上讀取的頁隻包含程序的信息，它不會在RAM中被修改，因此，重寫它不會導致任何問題。然而，如果頁的內容是數據表或其他數據結構，它可能在RAM中被改寫。在這種情況下，它不能被新的頁覆蓋。
在圖1-29中，可以看到，頁表中的每一項都有一個M位（修改位）。每當頁由一個寫操作訪問，M位被置位。當該頁需要被覆蓋，操作係統首先檢查M位，如果被置位，則首先需要將被改寫的頁寫回磁盤，然後再取新的頁。
最後，當加載新的頁後，將修改地址轉換表，清除M位，將R位置位（表示該頁是有效的），處理器可以重新執行被暫停的指令。
顯然，每次頁錯誤帶來的開銷非常大。隻要頁錯誤比較罕見，係統就可以因為訪問局部性而工作正常。多數數據是簇聚在一起的，所以一旦從磁盤中載入一頁，大部分要訪問的數據都會在該頁中找到。如果數據不是有序組織的或有許多不相關的任務，處理器將花費幾乎所有的時間用於交換頁，係統的有效工作將停頓。這種情況被稱為抖動（thrashing）。抖動是指一種頻繁訪問資源導致計算機性能急劇下降的行為。然而，抖動在很大程度上是指由於需要加載和重新加載頁而導致虛擬存儲器係統發生故障的情況。
3.兩級表
圖1-29給出的情況在現代高性能處理器中實際不存在。假設一個32位的計算機使用13位偏移（偏移指的是頁內地址）訪問8KB的頁。這使得可以使用32-13=19位來選擇219個邏輯頁。在快速RAM中不可能構建這樣大的頁表（注意，相同問題在Cache的設計中也存在）。
圖1-30給出了怎樣使用多級（multi level）頁表來實現地址轉換而不需要大容量的頁表。來自計算機的邏輯（虛擬）地址首先被分為19位的頁地址和13位的頁內偏移。頁地址進一步被分為對應第一級頁表的10位和對應第二級頁表的9位。這兩個表分別有210=1024項和29=512項。
圖1-30是個簡圖，真正的頁表包含更多地址轉換過程的信息而不僅僅是指針。圖1-31給出了PowerPC的地址轉換表。
真正的頁表結構包括多個指向其他表的指針。在這種層次地址轉換表中，頁表項包含指向下一級的指針。鏈表的終點為實際物理頁，包含了MMU所需關於該頁的信息。在實踐中，典型的存儲器管理單元包含的頁表描述符可以描述以下信息。
描述符類型
描述符類型告訴MMU表是否存在下一級。
寫保護位（W）
表示其指向的頁不可寫。如果W=1，樹中的所有後續級別的寫保護位都為1。
使用位（U）
該位在建立描述符表時被操作係統初始化為零。當描述符第一次被訪問時，MMU自動將其置為1。虛擬存儲器係統中，U位用來描述當頁需要被替換時，是否要將物理頁寫到磁盤。
管理員位（S）
當該位被置位，所指向的頁隻能使用管理員方式訪問（即操作係統級別的訪問權限）。管理員態指的是操作係統運行的狀態，具有比用戶態更高的優先權。例如，如磁盤這樣的I/O設備隻能在管理員態下訪問。
全局共享位（SG）
設置為1時，表示頁描述符可以共享，即如果SG=1，係統中所有的任務都可以訪問物理頁。SG告訴MMU，在頁表Cache中隻要保持該頁的一個描述符。轉換旁視緩衝器（translation look-aside buffer，TLB）是一個小的全相聯Cache，可以通過同時搜索所有條目實現地址轉換。
寫訪問級別（WAL）
通過該描述符指出頁的最低優先級。
讀訪問級別。由3位組成，用於根據WAL位實現相應的讀操作。
限製域（Limit）。該域為轉換表的下一級指出索引（index）值的下限或上限；即限製域限製了下一級表的大小。例如，邏輯地址域為7位，因此具有128項。然而，在實際係統中，在本級可能隻有不超過20個頁描述符。通過設置Limit為5，可以限製表項為32個而不是128個。
上/下位（L/U）
表示Limit位給出的是下限還是上限。如果L/U=0，則Limit域包含索引的無符號上限，下一級表的所有表索引都必須小於或等於Limit域中的值。如果L/U=1，則Limit域包含索引的無符號下限，所有表索引都必須大於或等於Limit域中的值。在這兩種情況下，如果實際索引超出最大/最小值範圍，將出現Limit違例。層次訪問最終得到頁描述符用來執行實際的邏輯地址到物理地址的轉換。
逐級訪問多級頁表（例如，如圖1-30所示）產生的頁描述符將被用於實際的邏輯地址到物理地址的轉換。除了上麵給出的描述符外，頁描述符可能還有以下的控製位：
修改位（M）
指示相應的物理頁是否被改寫。由於MMU可以將其置位但不會清除，故該位在建立描述符表時被操作係統初始化為零。注意，使用位U在表描述符被訪問後被置位，而M位在頁被修改後置位。
鎖位（L）
表示相應的頁描述符應規避MMU的頁置換算法。當L=1，物理頁不能通過MMU替換。因此，可以使用L位來保持地址轉換Cache中的頁描述符。
Cache抑製位（CI）
表明相應的頁是否可以被緩存。如果CI=1，那麼該訪問就不能被緩存。
本章小結
使用存儲器可以將指令和數據保存在計算機中。由於技術本身的原因和受製造技術發展的限製，目前尚沒有某種單一的設備或技術可以滿足所有的個人計算機或工作站的需求。簡單地說就是：速度很快的存儲器價格昂貴，如果便宜的話速度就慢。
當開發大型計算機用於滿足政府、工業以及軍事需求時，設計人員很快發現，實際存儲器係統的限製可以減少，或者說被屏蔽。的確，可以把不需要的數據存儲在慢速的存儲器中。用計算機的話說就是，把經常訪問的數據保存在快速存儲器中，而用慢速存儲器實現數據歸檔。這種想法既簡單又有效，對計算機性能產生了重要影響。但另一方麵，它在實現起來可不簡單。
計算機中有兩種基本類型的存儲器：主存儲器中的隨機訪問半導體存儲器（通常是DRAM）和磁記錄或光存儲器等順序訪問的二級存儲器。這兩種存儲器係統使用相似的技術來克服其速度限製：使用Cache存儲器（cache memory）來加速主存儲器，使用虛擬存儲器（virtual memory）來加速二級存儲器。Cache存儲器和虛擬存儲器機製的原理相似，但在細節和實現技術上有很大不同。
本章第一部分介紹了用來加速主存儲器的Cache。相對小容量的Cache（例如，4GB的DRAM使用1MB的Cache）可以顯著提高係統的性能。因為數據和指令不是隨機訪問的，真實的數據和指令表現出時間（temporal）和空間（spatial）局部性，通常CPU需要訪問存儲器的數據/指令中超過90%的都可以在Cache中找到。如果找不到，必須從存儲器中讀取數據，並將數據副本放入Cache。
本章研究了Cache的幾個內容，如它是如何組織的；即物理存儲器中的數據是如何被映射到容量較小的Cache中的。雖然直接映射Cache設計最簡單，本章已經說明了它具有的局限性會降低其效率。本章還說明了如何利用它來構建組相聯Cache——這是一種在所有微處理器係統中都能找到的Cache類型。
本章的第二部分討論虛擬存儲器。硬盤讀寫速度比主存儲器的DRAM慢若幹數量級。虛擬存儲器係統將存儲器通常劃分為4KB的頁。4KB的數據塊可以從磁盤中調入主存儲器中任意一個4KB的頁中；即物理存儲空間並不像處理器使用的虛擬或者邏輯地址空間那樣是連續的。當計算機訪問存儲器，存儲器管理單元將邏輯頁地址轉換為物理頁地址，然後從存儲器中的該頁讀取數據。然而，如果被訪問的邏輯頁不在存儲器中，存儲器管理單元就會產生頁故障，操作係統開始從磁盤中將所需頁調入主存儲器中的頁。當然，如果所有的物理頁當前都在使用，操作係統必須犧牲一個頁，替換它，再裝入新的頁。
習題
1.1 Cache是什麼？為什麼計算機要使用Cache？
1.2 解釋下列術語的含義？時間局部性；空間的局部性。
1.3 試推導出具有Cache的存儲器係統的加速比表達式（假定命中率為h，主存儲器訪問時間是Cache訪問時間的k倍，其中k>1）。假設該係統是一個理想的係統，不必考慮時鍾周期時間的影響。
1.4 對以下的理想係統，計算加速比S。每種情況下，tc為Cache的訪問時間，tm是主存儲器的訪問時間，h為命中率。
a. tm = 60 ns, tc = 3 ns, h = 0.99
b. tm = 60 ns, tc = 3 ns, h = 0.90
c. tm = 60 ns, tc = 3 ns, h = 0.80
d. tm = 60 ns, tc = 3 ns, h = 0.70
1.5 對以下的理想係統，計算得到給定加速比S所需的命中率h。
a. tm = 50 ns, tc = 2 ns, S = 1.5
b. tm = 50 ns, tc = 2 ns, S = 5.0
c. tm = 50 ns, tc = 2 ns, S = 10.0
d. tm = 50 ns, tc = 2 ns, S = 20.0
1.6 微處理器的操作通常在給定時間間隔內完成（即時鍾周期的整數倍）。例如，如果時鍾為100MHz，時鍾周期時間就是10ns，所有操作的時間必須為10ns的整數倍。下麵的數據中tcyc為處理器的時鍾周期時間，tm為主存儲器的訪問時間（包括所有開銷，例如地址譯碼）。針對每種情況，計算訪問存儲器實際需要的時間。
a. tcyc = 50 ns, tm = 100 ns
b. tcyc = 50 ns, tm = 105 ns
c. tcyc = 10 ns, tm = 75 ns
d. tcyc = 20 ns, tm = 75 ns
1.7 針對以下微處理器係統，計算當h接近100%時可以獲得的最大加速比。
a. tcyc = 20 ns, tm = 75 ns, tc = 25 ns
b. tcyc = 10 ns, tm = 75 ns, tc = 15 ns
c. tcyc = 20 ns, tm = 75 ns, tc = 15 ns
1.8 實際使用中，計算機有時在執行存儲器訪問的時候執行內部操作。因此，降低了有效加速比，因為Cache對內部操作沒有作用。執行一條指令所需的平均時間可以寫為：
tave = Finternal?·?tcyc + Fmemory[htc +(1-h) (tc + td)]·tcyc
其中：
Finternal為執行內部操作所花時間所占的比例（0～1之間）；
Fmemory為執行存儲器訪問操作所花時間所占的比例（0～1之間）；
tcyc為時鍾周期時間；
tc為以時間周期為單位的Cache訪問時間；
td為以時間周期為單位的Cache失效開銷；
請計算下列係統的平均周期時間。
a. Finternal = 20%, tcyc = 20 ns, tc = 1, td = 3, h = 0.95
b. Finternal = 50%, tcyc = 20 ns, tc = 1, td = 3, h = 0.9
1.9 針對上題中的係統，如果參數變成：Finternal = 40%, tcyc = 20 ns, tc = 1, td = 4，試計算將平均指令時間減半所需的命中率。
1.10 主存儲器的數據是如何映射到如下Cache中的？
a. 直接映射Cache
b. 全相聯Cache
c. 組相聯Cache
1.11 在一個直接映射Cache存儲器係統中，下列術語的含義是什麼？
a.字
b.塊
c.組
1.12 為什麼構建一個全相聯Cache很困難？為什麼組相聯Cache如此受歡迎？
1.13 畫圖說明如何使用Cache標誌RAM來實現直接映射Cache。對比直接映射Cache和全相聯Cache的優缺點。
1.14 什麼是Cache一致性？
1.15 突發模式的操作是什麼（在具有Cache的環境下）？
1.16 按道理，Cache是非常簡單的概念，隻需要將經常訪問的數據放在高速RAM中即可。在實踐中，相對其他計算機部件，Cache存儲器係統的設計是很困難的。這種說法是否正確？
1.17 討論工程師在為Cache選擇合適的塊大小（容量）時需要考慮的因素。
1.18 Cache係統可以位於CPU和MMU之間（即邏輯Cache）或在MMU與係統隨機訪問存儲器（即物理Cache）之間。是什麼因素決定了Cache的最佳位置？
1.19 當CPU寫Cache時，Cache中的項和存儲器中對應的項都需要更新。如果數據不在Cache中，它必須從存儲器中取出，然後裝入Cache。如果t1為Cache失效時重新加載需要的時間，證明存儲器係統的有效平均訪問時間由下式給出：
tave = htc + (1-h)tm + (1-h)t1
1.20 為什麼設計數據Cache比設計指令Cache要困難？
1.21 Cache可以相對於主存儲器以串行或並行的方式工作。在串行訪問模式下，在Cache中查找數據，如果發生失效，然後再訪問主存。在並行訪問模式下，Cache和主存儲器同時被訪問。如果命中，中止對主存儲器的訪問。
假設係統的命中率為h，Cache訪問時間與主存儲器訪問時間的比例為k（k<1）。推導出的並行訪問Cache和串行訪問Cache加速比的表達式。
1.22 如果使用串行訪問Cache，可以容忍其加速比比並行訪問Cache的加速比小5%，此時命中率為多少才能達到要求？假定主存儲器的訪問時間為30ns，Cache的訪問時間為3ns。
1.23 什麼是一級Cache和二級Cache（即L1和L2 Cache）？
1.24 某係統具有一級Cache和二級Cache。一級Cache的命中率為90%，二級Cache的命中率為80%。訪問一級Cache需要1個周期，訪問二級Cache需要4個周期，訪問主存儲器需要50個周期。平均訪問時間是多少？
1.25 計算機的Cache訪問時間為一個周期，平均命中率為95%，失效開銷為100個周期。
a.該計算機的平均周期時間是多少？
b.如果增加二級Cache的命中率為80%，其失效開銷為6個周期。對平均周期時間的影響如何？
c.具有一級Cache和二級Cache的計算機執行了10000次存儲器訪問。測試程序運行時，記錄到一級Cache失效了500次，二級Cache失效了300次。一級Cache和二級Cache的總體失效率是多少？
1.26 考慮多級Cache命中率，局部命中率和總體命中率之間有何區別？
1.27 為什麼經常引用（使用）失效率而不是命中率？什麼是Victim Cache，如何使用它？Victim Cache能夠減少何種類型的失效？Victim Cache和Annex Cache的本質區別是什麼？
1.28 某處理器的存儲器管理使用4KB大小的頁。它有一個32KB的Cache，Cache塊大小為16B。為了加快存儲器訪問，可以使訪問Cache與邏輯到物理地址的轉換同時進行。為了實現該方案，需要實現什麼樣的相聯度？
1.29 假設混合Cache具有以下特性：
Cache讀寫開銷 1個周期
失效率 3%
Load指令所占比例 20%
Store指令所占比例 5%
失效開銷 20個周期
平均訪問時間是多少？
1.30 某64位處理器有8MB的四路組相聯Cache，塊大小為32B。地址位是如何按照組、塊、塊內偏移位進行設置的？
1.31 某計算機具有分離的數據Cache，采用寫回策略。Cache塊大小為64B。讀訪問占全部存儲器操作的80%。處理器、存儲器和數據總線都是64位的。主存儲器訪問延遲（第一次訪問）為20個周期，後續訪問需要2個周期。Cache命中率為96%。試計算Cache的失效開銷。
1.32 導致Cache失效的3個原因是：強製失效、容量失效和衝突失效。給出這些術語的定義。簡要解釋如何盡量減少它們的影響。
1.33 CPU中的Cache和硬盤中的Cache有什麼根本差異？
1.34 為什麼在使用硬盤的係統中必須使用存儲器管理？存儲器管理可以提供哪些保護功能？存儲器管理係統具有保護功能，該功能在Cache中也存在嗎？
1.35 寫回Cache和寫直達Cache之間有何差異，對係統性能有何影響？
1.36 32位地址體係結構計算機的存儲器管理係統具有一級4KB的頁表。該頁表對應多大的存儲器空間？
1.37 考慮全相聯的16字節的Cache具有4個塊，每塊4個字。Cache使用LRU（最近最少使用）算法處理塊替換。Cache初始是空的，塊從第0塊開始裝載。
給定下麵的十六進製地址序列，指出命中或失效情況。給出所有讀操作結束後Cache的狀態。
00 03 05 08 13 14 11 04 0F 0C 23 00 01 02 04 06 05 07 09 21
1.38 計算機指令集具有下表中的特點。
每條指令的平均周期數是多少？
1.39 考慮下麵的代碼，訪問存儲器中的整數x和s以及整數向量y[i]這3個值。
該係統具有一級Cache和二級Cache。一級Cache的訪問時間是2個周期，二級Cache的訪問時間是6個周期，主存儲器的訪問時間為50個周期。在此情況下，所有的存儲器和Cache的訪問是並行執行的。假設沒有緩存數組，每次新的對數組的訪問都將導致失效。每個循環中以時鍾周期數表示的存儲器延遲（第一次迭代後）為多少？
1.40 假設采用與題1.39相同的係統，如果采用預取技術，每次對主存儲器的訪問將導致下一塊調入二級Cache，此時循環的平均存儲器延遲為多少？假設對二級Cache采用預取技術不會導致進一步的存儲器訪問開銷。
1.41 某64位計算機有128KB的八路組相聯Cache。Cache有128組，每塊為16個字。每個地址需要多少位標誌位？
1.42 哪種類型的Cache，可以用來減少由於頻繁交換而導致的Cache抖動？
1.43 給定以下數據，假設時鍾頻率為1000MHz。
計算平均存儲器訪問時間。假定二級Cache和DRAM可以與一級Cache並行訪問。
1.44 某16位CPU的Cache有32塊，每塊16B。CPU訪問一個字節的十進製地址為3210。這將導致失效，調入新塊。該塊位於Cache中的什麼位置？
1.45 某計算機具有256B的地址空間和兩路32B的組相聯Cache。計算機字的大小是一個字節，每個Cache塊包含4個字節，每個Cache有4塊。如果Cache最初是空的，按照如下十六進製地址序列讀取，顯示相應的命中和失效的情況。
48, 0C, 48, 4C, 5C, 3A, 20, 21, 22, 24, 81, 49, 30, 34, 27, 3E, 24, 28, 2C, 40
1.46 人們總是在尋找更有效的Cache機製，特別是減少失效開銷的方法（例如，使用Annex Cache或Victim Cache）。某個學生提出下麵的建議。並非所有數據都相同。有些數據使用比別的更頻繁，特別是數值小的數。所以為什麼不這樣安排Cache：當有兩個候選位置的塊可能被替換時，首先把數值大的塊替換出去？這種方法是否可行？
1.47 計算機Cache的命中率為95%，每塊為4個32位的字。處理器平均訪問Cache的頻率為1億次/s。20%的CPU操作為load/store操作（其中讀和寫操作分別占70%和30%）。Cache使用寫直達機製，在寫失效時會替換一個塊。在此情況下，32位CPU-存儲器總線可使用的帶寬是多少？
1.48 重做題1.47。此時Cache使用寫回方式，Cache中平均25%的塊為髒塊（已被修改）。
1.49 計算機的存儲器容量為256個字，Cache容量為16個字。按照以下地址順序讀數據：
0, 1, 2, 3, 4, 5, 10, 13, 16, 19, 21, 4, 8, 12, 30, 40, 41, 42, 35, 1, 3, 13
假設所有Cache塊最初都是無效的，指出Cache是如何訪問的。針對以下幾種Cache，為每次訪問做出標記：命中、容量失效、強製失效或者衝突失效。
a.全相聯Cache
b.兩路組相聯Cache
c.直接映射Cache
1.50 某係統的存儲器訪問時間為50ns，Cache訪問時間為2ns。指令執行時間為4ns（不包括存儲器訪問），平均每條指令需要0.25次存儲器訪問。如果命中率是0.90，指令的平均時間是多少？
1.51 某計算機具有24位地址總線，存儲器容量為16MB，Cache容量為64KB。字長為兩個字節。
a.塊容量為32個字的直接映射Cache的地址格式是什麼？
b.塊容量為32個字的全相聯Cache的地址格式是什麼？
c.塊容量為32個字的四路組相聯Cache的地址格式是什麼？
1.52 某計算機的存儲器訪問時間為38ns且不使用Cache。為其添加一個訪問時間為10ns的Cache。計算機的運行速度提高了90%。試估計其命中率是多少。
1.53 為什麼二級Cache的命中率通常低於一級Cache的命中率？
1.54 某係統一級Cache的命中率為87%（命中需要1個周期）。二級Cache的命中率為90%，訪問時間為10個周期。主存儲器的訪問時間為200個周期。平均訪問時間是多少？
最後更新：2017-05-25 11:31:26