439
技術社區[雲棲]
《計算機存儲與外設》----第1章 Computer Organization and Architecture: Themes and Variations Cache存儲器和虛擬存儲器 1.1 Cache存儲器概述
本節書摘來自華章出版社《計算機存儲與外設》一書中的第1章，第1節，作者Computer Organization and Architecture: Themes and Variations［英］艾倫·克萊門茨（Alan Clements） 著，沈 立 肖曉強 王蘇峰 譯，更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看。
第1章
Computer Organization and Architecture: Themes and Variations
Cache存儲器和虛擬存儲器
任何足夠先進的技術都與魔法無異。
——Arthur C. Clark
名字有什麼關係？我們把玫瑰叫成別的名字，聞起來還是一樣的芬芳。
——莎士比亞，《羅密歐與朱麗葉》
存儲層次（Memory Hierarchy）
Cache存儲器（Cache Memory）使得計算機看似擁有了比實際更多的快速存儲器。存儲器應該具有非易失性（non-volatile）、廉價、快速、功耗低的特點。在現實世界中，每種存儲技術都有其自身的特點，其中有些特點是相互矛盾的。例如，速度快的存儲器往往昂貴，而速度慢的存儲器往往便宜。存儲係統使用了幾種不同的技術，每種技術都發揮著不同的作用。總而言之，這些技術使整個存儲係統表現為快速、非易失性、低成本。可以把各種存儲技術分為不同的層，從而形成存儲層次。
圖1-1描述了典型的金字塔結構存儲層次。在頂端的存儲器速度最快（具有最短的訪問時間），金字塔底部的存儲器速度最慢。使用金字塔來表示存儲層次的原因是，頂層的存儲器的容量要小於底層的存儲器容量。
片上的寄存器（register）是計算機中最快的存儲器，它保存著處理器所需的工作數據。寄存器的訪問速度快，這使得load/store寄存器–寄存器型體係結構十分流行。寄存器是以與CPU相同的方法製備的，與CPU的時鍾頻率相同，且與CPU其他部分之間的數據通路都較短。此外，片上寄存器可以直接被CPU訪問，而訪問其他的外部存儲器都需要一個過程，包括存儲器管理、地址翻譯以及複雜的數據緩衝和控製機製。因此，寄存器速度很快。但是，CPU隻有少量寄存器可以用來存儲工作數據和狀態信息。寄存器不能存放程序。
存儲器層次結構中，在寄存器的下方就是Cache，更準確地說是一級Cache。Cache的大小一般比主存小幾個數量級，但真實程序的性質和數據的分布使得典型應用在95%以上的時間內隻使用較小的指令和數據集合。曆史上Cache曾經位於主板上，但芯片技術的進步使得人們可以在處理器芯片上實現大部分的Cache。
圖1-1顯示了兩級Cache存儲器。如果被訪問的數據不在一級Cache中，將訪問下一級的存儲層次，即二級Cache。並不是所有的係統都有兩級Cache，有的係統還有三級Cache。
如果數據不在Cache中，它必須從計算機的主存儲器來獲得，主存在圖1-1中是Cache的下一級存儲器。現代個人計算機和工作站大都使用DRAM來實現隨機訪問的主存儲器。今天的個人計算機可以使用1GB～48GB的DRAM。
主存是易失性的存儲器，因此程序和數據需要保存在非易失性存儲器中。最便宜的存儲機製之一是硬盤，它以磁信號的形式將數據保存在旋轉的盤片上。一個硬盤可以存儲超過4TB的數據。然而，硬盤的訪問時間為5ms左右，雖然按照人的標準來說這已經很快了，但還是比主存慢106倍。今天，機械硬盤被更快、更可靠的固態硬盤（SSD）代替。這些技術將在第3章中討論。
因為主存通常不能容納處理器所需的所有程序和數據，計算機采用了一種被稱為虛擬存儲器（virtual memory）的存儲器管理係統，其中主存中僅包括當前要使用的數據，那些不使用的數據仍然保存在硬盤上。當處理器需要的數據不在主存中時，操作係統開始介入並使主存和磁盤之間交換一個頁（page）的數據，其典型大小為4KB～64KB。虛擬存儲器係統允許用戶運行比主存大得多的程序，且不會導致係統性能的顯著下降。即由512MB的DRAM和100GB硬盤構成的虛擬存儲係統的性能與具有100GB的DRAM的存儲係統性能相當。虛擬存儲器還提供了一種保護數據的手段。
存儲層次的下一個層次是光存儲，由CD、DVD或者藍光光盤構成。光盤存儲器將數據以凹痕的方式記錄在塑料盤片上的螺旋軌跡中，並使用激光根據凹痕處是否有反光來讀取數據。光盤的讀取速度比硬盤的速度要慢，這主要是因為CD或DVD盤片的轉速與硬盤片旋轉速度相比差距太大。
圖1-1中至少有一個數據是不準確的：光存儲器的速度比磁記錄存儲器的速度慢，但其容量並不比後者大。CD通常可以容納650MB的數據，而藍光光盤可以存儲25GB的數據。幾年前，該容量還相對較大，但硬盤技術的進步如此引人注目，在10年的時間中，硬盤的容量已經從100MB發展到超過4TB（從108B增加為4×1012B，即容量增加了4×104倍。今天的硬盤能夠存儲比光盤更多的數據，在圖1-1中光盤是因為速度慢而不是容量大才位於硬盤的下一個層次。
圖1-1中光存儲器的下麵為磁帶（magnetic tape）或磁帶存儲器（cartridge storage）。這些存儲技術通過很長的磁帶而不是旋轉的磁盤來記錄數據。磁帶可以容納大量的數據，但是它們的訪問時間在幾分鍾甚至幾小時的量級，所以它們隻能作為後備存儲器或者用於文檔備份存儲。
磁帶的下一級是互聯網（Internet）和雲存儲（cloud storage），它們可以提供遠程分布式存儲。數據存儲在計算機外部，通常位於第三方提供的虛擬服務器中；即用戶通過購買存儲服務，通過互聯網和WWW來存儲信息。用戶不需要知道數據到底存在哪裏。重要的是，如何在災難降臨時保證數據的安全性。此外，隻要連接到因特網，數據就可從任何地方訪問。
在第1章和第2章中深入討論存儲係統技術之前，需要討論存儲器是如何與計算機係統關聯的。如果訪問CPU內寄存器的時間小於1ns，訪問CD驅動器的時間超過200ms，雖然完成的任務都是數據訪問，也需要花大量的精力來管理這種由多種不同存儲設備構成的係統。
本章介紹相對較小的Cache，與相對更大和更慢的存儲器相結合，並使整個組合的係統看起來像一個又大又快的存儲器。奇妙吧！本章然後介紹虛擬存儲器對地址的管理，這使得用戶不必關心數據在存儲器中如何存儲，允許用戶在不同的存儲區域中同時運行若幹程序，且在計算機需要數據的時候自動從磁盤加載它。
本章包括Cache和虛擬存儲係統，是因為它們完成相同的任務。兩者都使用少量快速存儲器，將它們與大容量的慢速存儲器相結合，使得整個存儲係統好似大容量的快速存儲器。兩種技術都涉及從計算機地址映射到數據在存儲器中的實際位置。Cache和虛擬存儲器之間的區別主要體現在速度和控製機製上。Cache操作需要ns量級，由硬件自動管理，而虛擬存儲器操作需要ms量級，由操作係統管理。
下麵來看看Cache和虛擬存儲器在係統中的作用。假設計算機執行下列操作：
這些指令從內存讀取操作數time。CPU所要做的就是將time的地址放到地址總線上，然後讀取數據。原理上，該過程再簡單不過了。圖1-2展示了可以執行此代碼的係統。計算機給出的操作數地址（此例中為time）是一個邏輯地址。將這個地址傳給快速的Cache，在那裏試圖訪問數據。如果數據在Cache中，就從Cache中獲取數據。否則，如果數據在較慢的主存儲器中，該數據將從主存交給計算機和Cache。該過程由硬件實現，並對用戶和操作係統來說是不可見的。
有時，數據也不在主存儲器中；它在硬盤上。當數據在磁盤上，虛擬存儲器機製將其從磁盤拷貝到主存儲器。它當然也被拷貝到了Cache。從磁盤傳輸到主存儲器的數據可以存放到主存儲器的任意位置。這就需要存儲器管理單元（memory management unit，MMU）將來自計算機的邏輯地址（logical address，即計算機認為數據所在的地方）轉換為物理地址（physical address，即操作係統把該數據存放在存儲器中的地址）。虛擬存儲器管理是操作係統完成的主要任務之一，需要存儲器管理單元的專用硬件與操作係統密切合作。
下麵將討論圖1-1中給出的存儲層次的相關特性，然後介紹Cache是如何加快計算機操作的。本章的部分內容將介紹影響Cache性能的因素，以及如何通過優化Cache硬件和應用軟件來提高係統速度。
本章的後半部分關注虛擬存儲器以及如何從處理器給出的數據邏輯地址（或虛擬地址）映射到存儲器中對應的數據物理地址。
1.1 Cache存儲器概述
在馮·諾依曼計算機中，存放程序和數據的主存儲器應該盡可能快地滿足CPU的要求。如果存儲器不能在當前周期向CPU提供所需訪問的數據或指令，存儲器必須返回一個信號通知CPU等待。CPU通過在機器周期中插入空閑（idle）或等待（wait）指令來阻止其執行下一個操作。在等待狀態，CPU將停止正常操作，因此慢速存儲器將嚴重降低其性能。在本節中，將介紹Cache如何顯著提高處理器的性能，而不會帶來太大的開銷。圖1-3再次展示了存儲器的層次結構，並以時鍾周期的形式給出了各層的延遲。
20世紀90年代早期，在各種期刊上常常可以看到這樣的評論，“如果隻是要CPU以更快的速度等待，則製造與使用高速CPU是沒有意義的。”解決該困境的一個方案是使用更快的存儲器以跟上CPU的速度。這聽起來可能很容易做到，因為CPU和存儲器的技術是相關的，它們都采用相同的設計和製造工藝。人們很容易認為一個具有5ns周期的CPU需要存儲器的訪存時間也達到5ns。這種想當然的認知存在兩個缺陷。首先，曆史上處理器速度的增長率已遠遠超過了DRAM速度的增加，這在過去的20年中已經是事實。第二，CPU的機器周期時間（即處理器執行一個讀或寫操作來訪問外部存儲器所需的時間）為5ns，但其時鍾周期可能隻有2.5ns，此時每個CPU的機器周期包括兩個時鍾周期。假設CPU在這5ns的機器周期時間中，將花費一個時鍾周期來執行管理任務。處理器將需要在一個時鍾周期內獲得數據，該時間包括從數據地址可用到來自存儲器的數據被鎖定所需的時間。所以，要跟上CPU的存儲器訪問時間是2.5ns。因此，這需要存儲器的訪問時間遠低於其服務的處理器的機器周期時間。
盡管現代技術確實可以製造訪問時間小於5ns的存儲部件，但該設備的高昂成本使得其難以在大容量存儲係統中應用。在20世紀90年代中期，個人計算機和工作站的大規模生產，為控製成本，要求使用已經測試過的主流存儲部件（例如，64Mb DRAM的訪問時間為50ns）。
Cache並不神秘，它隻是一個可由處理器快速訪問的高速存儲器。奇妙之處在於係統隻擁有少量高速存儲器（例如，某係統有256KB的Cache和512MB的DRAM），並且希望處理器在95%的時間內都訪問Cache而不是DRAM。
Cache可以通過日常生活中諸如日記、地址簿，或iPhone中的電話號碼簿等類似物來理解。電話號碼黃頁中包含成千上萬的電話號碼，但沒有人會真正帶上一本。人們通常在號碼簿中隻記錄約100個電話號碼。雖然這些號碼可能少於電話號碼清單總數的0.0001%，但下一個電話來自號碼簿的概率是很高的，就像人們經常會給朋友打電話一樣。
Cache的工作方式與上述電話號碼簿的工作原理相同，它將經常訪問的信息放入Cache而不是放入相對較慢的主存儲器。與號碼簿不同，計算機不能提前知道哪些數據是最可能需要的。與人們將數據劃分為重要類別的做法不同，計算機的Cache根據學習原理（learning principle）來操作。Cache通過在實踐中學習什麼樣的數據是最經常需要使用的數據，然後將它們保存在Cache中。
理想情況下，由於基於DRAM的存儲器的速度越來越快，對複雜和昂貴的Cache係統的需求應該消失。在20世紀70年代，我曾闡述了這個觀點。時間證明我錯了。圖1-4顯示了在過去20年中存儲器和微處理器性能的發展趨勢。存儲器每年約增速7%。處理器速度在這段時間內提升更快，每年增加55%左右的性能。由於處理器和存儲器之間的性能差距已經擴大，Cache存儲係統今天的作用比其剛發明時的作用要重要得多。
Wulf和McKee討論了存儲器和處理器性能變化具有不同速度帶來的影響。他們認為DRAM速度滯後於處理器的速度將最終被證明是限製計算機性能的條件。他們認為，處理時間是執行內部操作的時間加上訪問外部存儲器的時間的總和，因此，存儲器訪問時間部分將主宰處理時間。進一步提升處理性能將毫無意義。他們創造了“碰到存儲牆（hitting the memory wall）”的概念，表明在傳統微處理器係統設計中存在限製。
Cache高速緩存本來沒有什麼內在價值。總線用來分布數據；硬盤用來存儲大量的數據。Cache的作用僅僅是隱藏了存儲器延遲。如果存儲器足夠快，就可以不需要Cache。
1.1.1 Cache存儲器的結構
Cache存儲器係統的一般結構如圖1-5所示。Cache存儲體與處理器的地址總線和數據總線相連，並與更大容量的主存儲器並行工作。Cache中的數據在主存儲器（即DRAM）中也存在副本。
訪問的局部性原理
回到前麵的電話號碼簿例子，向電話號碼簿中添加一個朋友的號碼並不會從電話號碼黃頁中刪除他的號碼。考慮計算機訪問某個存儲器位置。各個給定的存儲位置被訪問的概率是不同的，因為有些地方比其他地方更容易被訪問。由於程序和其數據結構的性質，處理器所需的數據往往在存儲器中聚集在一起。例如，堆棧經常被訪問，某些函數與其他函數相比經常被調用。這種現象被稱為訪問的局部性（locality of reference），這使Cache的使用成為可能。
一些地址被稱為出現了空間局部性（spatial locality），這是因為它們聚集在相同的存儲器區域內（例如，數據結構）。程序員和編譯器會針對空間局部性進行特殊考慮。假設某程序包括變量P、Q和R，其中P是整數，R是由8個整數組成的數組，Q是另一個整數。另外，假設P和R經常被訪問而Q很少被訪問。如果數據的聲明順序為P、R和Q，則這兩個經常訪問的變量在存儲器中是相鄰的，可以被緩存在一起。
一些地址被稱為出現了時間局部性（temporal locality），這是因為它們在短時間內被多次訪問（例如，在一個循環體內的位置）。某循環，例如：
將在一段時間內有規律地訪問相同的變量。
局部性原理僅僅是種指導，而不能成為定律。某些程序同時表現出時間局部性和空間局部性，而有些程序沒有。若程序要訪問一個非常大的矩陣且數據分布是隨機的，此時可能不會表現出空間局部性。某按照地理位置列表的郵購消費者數據庫可能具有較好的空間局部性，這是因為一些團體由需要頻繁服務的用戶組成。一個簡單的具有時間局部性和空間局部性的例子是產生內積的例子：
計算機連續訪問a0，a1，a2，a3，…，就會表現出空間局部性，因為這些連續的元素在內存中是相鄰的。元素ai和bi在空間中存放的位置可能相距很遠，但它們從訪問時間上看是相鄰的，因為ai和bi幾乎在相同的時間被訪問。
Cache使用Cache控製器（cache controller）來確定CPU要訪問的操作數是否在Cache中，是否需要從主存儲器中調取。當給Cache控製器一個地址後，控製器返回一個信號（hit或miss）確定Cache是否命中。命中（hit）表明數據當前位於Cache中，失效（miss）表示數據不在Cache中，需要從主存儲器中調取。
現代高性能係統具有多個級別的Cache：一級Cache、二級Cache和三級Cache。一級Cache是容量最小但速度最快的Cache。如果數據不在一級Cache中，就在二級Cache中查找。如果數據也不在那兒，則在三級Cache中查找。多級Cache的性價比較好，因為它們在不增加最快Cache的容量的情況下提供了更好的性能。後續章節中將討論多級Cache。
最後更新：2017-05-24 17:32:39