本節書摘來自異步社群《現代體系結構上的unix系統：核心程式員的對稱多處理和緩存技術（修訂版）》一書中的第2章，第2.2節，作者：【美】curt schimmel著，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視
因為幾乎所有的程式都展現出了局部引用特性，是以在從pc（個人計算機）到超級計算機的各種系統上都能找到高速緩存。甚至在現今大多數微處理器晶片和記憶體管理單元（memory management unit，mmu）晶片上也可以找到內建的高速緩存。如果在微處理器或者mmu晶片上沒有包含高速緩存，那麼它一般會在主機闆（稱為外部高速緩存）上。靠近cpu降低了cpu和高速緩存之間的存取時間。如果高速緩存位于一塊獨立的闆卡上，進而必須通過總線來通路它，那麼就會大幅增加時延（latency），進而帶來系統性能上的相應損失。有些系統既使用片上高速緩存，也使用外部高速緩存。
高速緩存的大小從幾個位元組到數百kb都有，在大規模系統上甚至可能有1 mb以上的高速緩存。例如，今天的片上高速緩存一般介于4 kb到16 kb之間。外部高速緩存要大一些，介于128 kb到4 mb之間。随着時間的推移，高速緩存的規模正在逐漸擴大。例如，intel 80386沒有片上高速緩存，80486有8 kb的高速緩存，而pentium則有兩塊8 kb的高速緩存。外部高速緩存已經從mips r2000的64 kb增加到r4000的4 mb。
一般而言，高速緩存越大，性能提升就越多，因為有更大的一個存儲子集被高速緩存起來供高速通路。正如随後的各章中将要看到的那樣，高速緩存的規模并不能改變作業系統必須正确管理高速緩存的問題，而隻能改變要使用的特定算法。高速緩存的性能将在2.11節裡進一步讨論。
一個系統可以使用分離的指令高速緩存和資料高速緩存。這能夠進一步提高系統的性能，因為cpu可以同時從指令高速緩存取得指令，而從資料高速緩存加載或者存儲資料（參見2.10節）。正如第6章中将要看到的那樣，可以使用多級高速緩存給存儲器層次結構增加額外的層次（接下來的幾章将集中介紹單級高速緩存）。
2.2.1 如何存取高速緩存
高速緩存的實作使得它們的存在對于使用者程式來說基本上甚至完全地被忽略了。大多數實作的目标是隐藏高速緩存管理的全部細節，不論是硬體的還是作業系統的（在後面的章節中闡述），進而達到使用者應用的可移植性。這一思路確定了無需修改程式，應用程式就可以移植到具有不同高速緩存組織、不同高速緩存規模的不同系統上，或者移植到沒有高速緩存的系統上。這在當今的市場上是一個重要的好處。如此一來，程式可以像以前那樣繼續通過位址引用存儲器。通路高速緩存不需要特殊的編碼技術或者尋址模式。高速緩存可以通過控制高速緩存的硬體自動通路。一種稱為實體高速緩存（physical cache）的高速緩存組織方式甚至對作業系統都是透明的。這就有可能給原本在設計上沒有高速緩存的體系結構，例如ibm 370和ibm pc，增加高速緩存，同時仍然能夠跟現有的系統軟體保持相容性（實體高速緩存将在第6章詳細介紹）。
因為高速緩存隻儲存主存儲器的一個子集，是以需要有幾種方式來确定存儲器的哪些部分目前駐留在高速緩存中。我們稱存儲器的那些部分被“緩存”了。這一點是通過将高速緩存中的資料用它們對應的主存儲器位址進行标記（tagging）來做到的（對于指令高速緩存中的指令來說也是如此）。随後硬體就可以通過檢查高速緩存中資料的标記來判斷一個特定的記憶體位置是否被緩存了。這樣，比如說當cpu請求一個它想要擷取的主存儲器位址時，這個位址就被發送給高速緩存，然後硬體就開始搜尋高速緩存來尋找相應的資料（參見圖2-3）。如果在高速緩存中找到了它，那麼就稱為一次緩存命中（cache hit）。如果沒有找到相應的資料，那麼就稱為緩存缺失（cache miss）。緩存命中與緩存缺失的頻率之比就稱為命中率（hit ratio），它以引用命中的百分比或者命中發生的機率（90%的命中率和0.9的命中機率是等價的）來表示。命中率越高，系統的性能就越好。
如果發生了一次命中，那麼資料被傳回給cpu，就好像它是從主存儲器中讀取的一樣。如果沒有命中，那麼就把位址傳遞給主存儲系統，在那裡通路尋址單元。在這種情況下，資料既傳回給cpu也傳回給高速緩存。在一次缺失之後資料被儲存在高速緩存中，以便利用時間局部性。此時也可以把cpu讀取的一段資料周圍的資料都載入高速緩存，進而也利用空間局部性（正如後面将要讨論的那樣，在高速緩存缺失期間載入的資料量取決于具體實作）。因為大多數程式都表現出了局部性，是以90% 或者更高的命中率并非罕見。
在高速緩存的設計中，要考慮的重要一點是用一個标記确定多少資料。如果獨立地标記高速緩存中的每一個位元組的話代價太大了。是以，來自主存儲器的一個或者更多連續的字被組織到一起形成了一個高速緩存行（line）或者塊（block），并且給每一行關聯單個标記。是以一個完整的高速緩存行是由一個标記和一段資料組成的，但是高速緩存行的大小是指資料部分的位元組數（一般并不包括标記的大小）。片上高速緩存行的典型大小範圍是從16位元組到32位元組。因為行中資料部分的位元組是從連續的存儲器單元來的，是以标記隻需要包括第一個位元組的位址即可；其他位元組的位址可以用它們在行内的位置來推算。
除了位址之外，一行的标記部分還包括控制資訊（control information）。标記部分始終都要加上一位，作為有效位（valid bit），表明相關的高速緩存行是否投入使用以及是否包含有效的資料。僅當有效位被置為on且标記吻合時，才能發生緩存命中。在系統複位或者啟動期間初始化高速緩存的時候，所有的有效位都被清除，是以初始情況下所有的指令和資料都取自主存儲器。
在标記中儲存的另一個常見的标志是修改位（modified bit）。正如2.2.5節所讨論的那樣，當cpu把資料儲存到使用寫回高速緩存機制（write-back caching）的一個高速緩存中的時候就會設定這個位。在标記中也可以出現其他依賴于具體實作的資訊，比如鍵（key），它是第4章的主題。
在發生一次高速緩存缺失的時候，就從主存儲器中讀取填滿整個高速緩存行所需要的位元組數，然後加載到高速緩存中。因為反映整行狀态的隻有一個有效位，是以必須這樣做。例如，如果高速緩存行的大小是兩個字長，那麼在一次高速緩存缺失時不可能隻讀取cpu所引用的那一個字。如果沒有讀取兩個字，那麼高速緩存行的一半就會包含無效的資料。一般說來，從主存儲器中讀取附加的字并不會影響性能，因為大多數現代的主存儲系統的設計都能一次讀取或者寫入多個字。
有些實作選擇使用非常長的高速緩存行（128~256位元組或者更多）。這樣做的優點是它減少了标記所需占用的存儲器數量，因為一個标記現在能夠覆寫更多的緩存行裡資料部分的位元組數。是以，為儲存同等數量的資料，高速緩存所需的标記更少。長高速緩存行的缺點是，将整個行傳入和傳出主存儲器所需要的時間開始明顯變長。為了緩解這一問題，有些實作将一個高速緩存行劃分成了多個子行（subline），每個子行都有它自己的有效位。于是每個子行都能獨立地進行處理，就好像它是一個單獨的高速緩存行一樣，差别在于隻有一個位址标記涵蓋一行中所有的子行。這意味着所有的子行包含來自連續主存儲器位址中的資料。每個子行的位址由它在整個高速緩存行中的位置和高速緩存行的标記就可以推算得到。幸運的是，子行的使用對于作業系統來說是透明的，是以它不需要成為随後讨論中的一個考慮因素。
2.2.2 虛拟位址還是實體位址
高速緩存可以設計成通過資料或者指令的虛拟位址或是實體位址來通路。類似地，緩存标記也可以被設計成連同其他資訊一起，要麼含有虛拟位址，要麼含有實體位址。選擇虛拟位址還是實體位址在設計硬體的時候就确定下來了，并且對高速緩存管理技術有很大的影響，而作業系統必須采用這些技術對使用者程式隐藏高速緩存的存在。這些複雜的問題将是後續各章的讨論主題。對于本書剩下的内容來說，不需要考慮通路高速緩存時所采用的位址類型。采用其中任何一種位址類型對于下面介紹的主題都有相同的影響。接下來的幾小節隻是簡單地稱它們為“位址”。
2.2.3 搜尋高速緩存
如果給定cpu想要的資料的位址，那麼必須快速地搜尋高速緩存來查找那個資料，因為高速緩存的全部目的就是要比主存儲系統更快地傳回資料。搜尋技術還必須簡單，以便高速硬體的實作既切合實際，又經濟劃算。比如說，線性搜尋技術就不适用于高速緩存，因為除了最小的高速緩存之外，它們對于所有的高速緩存來說都太慢了。它們還難以在硬體上實作，因為它們需要一個狀态機（state machine）或者定序器（sequencer）來儲存搜尋的目前狀态。大多數高速緩存代之以使用一種簡單的散清單（hash table）技術來進行搜尋。
為了搜尋一個高速緩存，來自cpu的位址經散列處理生成一個索引（index），這個索引指向高速緩存中的一個或者多個位置，如果相應的資料被緩存了，那麼就會儲存在這些位置上。和許多雜湊演算法一樣，不同的位址可能産生相同的索引值。于是必須用這些位置上的标記（它們包含着那些位置上正在高速緩存的資料的位址）和cpu所提供的位址進行比較。如果一個标記與來自cpu的位址相吻合，那麼就發生一次命中；否則，就出現一次缺失。對于高速緩存來說，散列是一種很有用的技術，因為它将搜尋限定在了包含一個或者多個位置的小集合中（除了在全相聯的高速緩存中之外，這将在以後介紹。在全相聯的高速緩存中不使用散列技術）。接下來，硬體會快速地并行搜尋這些位置。對于大規模的高速緩存來說，這些技術格外重要，因為在這些高速緩存中隻有足夠的時間去搜尋一小部分高速緩存。上述的所有活動都在硬體中執行，無需軟體的介入。
2.2.4 替換政策
因為高速緩存比主存儲器小，是以在高速緩存缺失操作期間載入新資料時緩存中的一些已有的資料必須被丢棄。要丢棄的資料是根據高速緩存的替換政策（replacement policy）來進行選擇的（該政策與實作有關）。一旦被選中，那麼高速緩存中要丢棄的資料就被新資料所替換。和資料相關聯的标記也改成新資料的位址，進而在高速緩存中正确地辨別它。
高速緩存所采用的替換政策往往相當簡單。雖然在存儲管理和虛拟存儲調頁系統中所看到的頁面老化（page aging）和替換（replacement）技術從理論上說也可以應用于高速緩存，但是它們在硬體上實作起來過于複雜。它們經常需要大量的狀态或者曆史資訊，而在高速緩存中使用的昂貴的高速存儲器數量有限，沒有充足的空間來儲存這些狀态和資訊。典型的高速緩存替換政策有lru（least recently used，最近最少使用）、僞lru（pseudo-lru，一種lru的近似）以及随機替換。這些政策将伴随本章後面讨論的不同高速緩存組織進行介紹。幸運的是，和前面讨論過的那些高速緩存通路的方面一樣，替換政策對于軟體來說也是透明的。
2.2.5 寫政策
當cpu儲存資料的時候，大多數實作都把資料直接儲存到高速緩存中。将資料儲存在高速緩存中有助于改善系統性能的原因有兩個：第一，由于時間局部性，被儲存的資料在寫入之後會被頻繁地重新讀取，是以就提高了命中率；第二，在高速緩存中使用的速度更快的儲存設備儲存資料的速度要比主存儲器快，這就解放了cpu，讓它能夠比其他可能的方式速度更快地開始下一次資料載入或者儲存操作。寫入高速緩存中的資料也可以同時寫入主存儲器。高速緩存的寫政策（write policy）也叫做更新政策（update policy），表明了資料是怎樣儲存到高速緩存和主存儲器中的。
要把資料儲存到高速緩存中，必須搜尋高速緩存，看看高速緩存内是否已經包含有和寫入的位址相關的資料。此刻使用了與從高速緩存中讀取資料時相同的搜尋技術。先考慮在儲存期間出現一次命中的情況。在這裡，cpu寫入的資料替換了高速緩存行内的老資料，以便利用時間局部性。
雖然高速緩存是用來自cpu的新資料更新的，但是該資料可以寫入主存儲器，也可以不寫入主存儲器，這取決于所采用的寫入政策。兩種可能的寫入政策是寫直通（write-through）和寫回（write-back）（也叫做複制回，copy-back）。如果一個高速緩存正在使用寫直通政策，那麼來自cpu的資料既會寫入高速緩存也會寫入主存儲器。寫直通政策得名于存儲器層次結構的組成（參見圖2-1），它必須“直通”過高速緩存到達主存儲器。mips r2000/r3000和intel用于80486的82495dx外部高速緩存控制器都使用寫直通高速緩存機制。寫直通政策的效果是存儲器始終保持在“最新”狀态，這意味着在高速緩存中的資料和存在于主存儲器内的資料副本完全相同（也叫做“保持緩存一緻”）。這種政策的缺點是每次來自cpu的寫入操作都需要有一個主存儲器周期，這有可能會降低系統的速度。
另一種政策是寫回（write-back）。此時來自cpu的資料還是按照以前那樣被寫入高速緩存，但是并不寫入主存儲器，直到在行替換或者作業系統明确要求寫回主存儲器期間才寫入主存儲器。這就消除了采用寫直通高速緩存機制時，如果在某個位址的資料被高速緩存，同一個位址被寫入若幹次時所造成的額外的主存儲器周期開銷。寫回政策的缺點是，主存儲器中的内容相對于高速緩存而言變成了“過時的”或者說不一緻的。為了重獲一緻性，往往需要作業系統的介入。
例如，考慮采用寫回高速緩存的cpu在執行一個程式中i = i + 1這條語句時會發生什麼情況（假定i的值以前沒有被高速緩存過）。如果在執行這條語句之前，i在主存儲器中的值為1，那麼當cpu試圖讀取i的目前值的時候，它就不會在高速緩存中命中，并且要将值1載入到高速緩存中，然後傳回給cpu（圖2-4a）。接着，cpu給i的值加1，把i的值2寫回。寫入操作導緻在高速緩存中發生一次命中，并且i在高速緩存中的值被更新為2。此刻寫入操作完成時高速緩存中i擁有新值，但主存儲器内仍然保持着i的舊值1（圖2-4b）。在高速緩存内i的新值被認為相對于主存儲器内的值被“修改”過了。
必須確定i在主存儲器内的過時值不會被程式通路到，否則将會出現無法預測的結果。類似地，也必須確定多處理器系統上的其他程序不會使用過時的存儲器内的值（這将在第三部分進行讨論）。隻要i的新值儲存在高速緩存内，那麼程式就不會通路到i的過時值，因為程式總是可以在通路主存儲器之前在高速緩存中命中。被修改的資料将保持被高速緩存，直到該行被替換為止。
在随後的缺失操作期間内的任何時刻，都可以替換寫回高速緩存中的資料。被修改的資料不能被簡單地丢棄，因為程式最終會在下一次引用時通路到在主存儲器内的原來的過時值。是以，在替換之前，要替換的已被修改過的資料會由高速緩存硬體自動地寫回到主存儲器中。為了區分高速緩存中需要在替換時寫回的已修改資料和不需要寫回的未修改資料，在每個标記中加入了一個稱為修改位（modified bit）的附加位。cpu寫入資料的每一行的标記中都設定了修改位。隻要在讀缺失（read-miss）操作期間載入了資料，修改位就會被清除，因為資料仍然和主存儲器保持同步。通過跟蹤每一行的修改狀态，高速緩存隻需要在必要時寫回高速緩存行，而無需像寫直通高速緩存機制那樣每次儲存操作都要這樣做。是以說，寫回高速緩存機制的優點就是主存儲器寫入操作可能更少，總線操作可能更少，整體性能也就可能更好。缺點是作業系統需要好多次地把被修改的行寫回存儲器，以此來保持資料的完整性（在後面的章節中解釋）。寫回高速緩存機制實作起來也要比寫直通高速緩存機制的成本更高。一般而言，寫回機制的優點大于缺點，是以這項技術得以廣泛使用。例如，intel 486、pentium的片上高速緩存和i860 xr、mips r4000、motorola 88200和68040以及ti microsparc和supersparc（如果沒有使用外部高速緩存的話）都使用寫回高速緩存機制。
前面的讨論隻考慮了儲存來自cpu的資料期間在高速緩存裡命中時情況。如果相反沒有命中，那麼采取的措施則取決于高速緩存是否支援寫配置設定（write-allocate）。在使用寫配置設定機制的時候，cpu儲存的資料在發生高速緩存缺失的情況下始終會被寫入高速緩存（也就是說，為資料配置設定高速緩存行），以便利用時間局部性和空間局部性的優點。要做到這一點，要執行與讀缺失期間相同類型的處理。首先，替換政策選擇一行要丢棄的資料，給儲存新資料騰出空間。如果使用寫回高速緩存機制，而且所選的要被替代的高速緩存行又被修改過，那麼就必須把這一行寫入到主存儲器中。接着，從主存儲器中讀取與造成缺失的所有位址相關聯的全部高速緩存行。之是以必須讀取全部高速緩存行（或者子行），是因為正如2.2.1節所闡述的那樣，隻有一個有效位涵蓋高速緩存行或者子行的狀态。一旦讀取了一行，那麼cpu寫入的資料就被插入到這一行中，并且設定這一行的高速緩存标記，以便反映出新資料的位址。如果使用了寫回高速緩存機制，那麼還要設定這一行的修改位。如果cpu寫入資料的大小等于高速緩存行的大小（例如，把一個字儲存在每行一個字的高速緩存中），那麼就會跳過主存儲器的讀取操作，因為該行肯定要被cpu的資料所替換。mips r2000/r3000就是這種情況，它使用了4位元組長的高速緩存行。使用寫配置設定的其他處理器有mips r4000、motorola 68040和88200、ti supersparc以及intel 80486（82495dx）的外部高速緩存。
有些高速緩存為了在硬體實作上更簡單而放棄了寫配置設定政策的局部好處。在不支援寫配置設定政策的高速緩存中出現儲存缺失的時候，資料被獨自寫入主存儲器，而保持高速緩存的内容不變。intel 80486和ti microsparc就使用了這種技術。
在大多數情況下，寫回高速緩存都使用寫配置設定政策，但是寫直通高速緩存則不然。這是由于硬體的成本問題：寫配置設定會增加低成本的寫直通方法的成本，因為在一次儲存缺失期間必須讀取一行再把這一行寫入主存儲器。寫回高速緩存機制能夠很好地配合寫配置設定工作；另一方面，如果被寫入的行尚未被cpu讀取，那麼就不會被高速緩存起來，進而導緻所有這樣的存儲都被送往主存儲器。但是，這也有例外。例如，intel pentium的外部高速緩存控制器（82434lx）能夠配置成使用不帶寫配置設定的寫回政策，mips r2000/r3000使用帶有寫配置設定的寫直通政策。在mips晶片的案例中，硬體執行寫配置設定很容易，因為每一個高速緩存行的大小隻有4位元組，進而不需要在發生儲存缺失的情況下從存儲器中讀取一行。
其他的變化也是有可能的。例如，motorola 88200上的高速緩存就使用了寫回高速緩存機制，但是隻要在高速緩存内發生了儲存缺失時，就會更新存儲器。這稱為寫一次（write-once），它允許高速緩存行即使剛發生對它的儲存也能保持未修改狀态，因為主存儲器會被更新。幸運的是，對于作業系統來說，諸如這樣的變化都是透明的。