computer organization and architecture: themes and variations
cache存儲器和虛拟存儲器
任何足夠先進的技術都與魔法無異。
——arthur c. clark
名字有什麼關系？我們把玫瑰叫成别的名字，聞起來還是一樣的芬芳。
——莎士比亞，《羅密歐與朱麗葉》
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光牒構成。CD光牒存儲器将資料以凹痕的方式記錄在塑膠盤片上的螺旋軌迹中，并使用雷射根據凹痕處是否有反光來讀取資料。CD光牒的讀取速度比硬碟的速度要慢，這主要是因為cd或dvd盤片的轉速與硬碟片旋轉速度相比差距太大。
圖1-1中至少有一個資料是不準确的：光存儲器的速度比磁記錄存儲器的速度慢，但其容量并不比後者大。cd通常可以容納650mb的資料，而藍光CD光牒可以存儲25gb的資料。幾年前，該容量還相對較大，但硬碟技術的進步如此引人注目，在10年的時間中，硬碟的容量已經從100mb發展到超過4tb（從108b增加為4×1012b，即容量增加了4×104倍。今天的硬碟能夠存儲比CD光牒更多的資料，在圖1-1中CD光牒是因為速度慢而不是容量大才位于硬碟的下一個層次。
圖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硬體和應用軟體來提高系統速度。
本章的後半部分關注虛拟存儲器以及如何從處理器給出的資料邏輯位址（或虛拟位址）映射到存儲器中對應的資料實體位址。
在馮·諾依曼計算機中，存放程式和資料的主存儲器應該盡可能快地滿足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。
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。