① linux kernel 內存管理-頁表、TLB
頁表用來把虛擬頁映射到物理頁，並且存放頁的保護位(即訪問許可權)。
在Linux4.11版本以前，Linux內核把頁表分為4級：
頁全局目錄表(PGD)、頁上層目錄(PUD)、頁中間目錄(PMD)、直接頁表(PT) 。
4.11版本把頁表擴展到5級，在頁全局目錄和頁上層目錄之間增加了 頁四級目錄(P4D) 。
各處處理器架構可以選擇使用5級，4級，3級或者2級頁表，同一種處理器在頁長度不同的情況可能選擇不同的頁表級數。可以使用配置宏CONFIG_PGTABLE_LEVELS配置頁表的級數，一般使用默認值。
如果選擇4級頁表，那麼使用PGD，PUD，PMD，PT；如果使用3級頁表，那麼使用PGD，PMD，PT；如果選擇2級頁表，那麼使用PGD和PT。 如果不使用頁中間目錄 ，那麼內核模擬頁中間目錄，調用函數pmd_offset 根據頁上層目錄表項和虛擬地址獲取頁中間目錄表項時 ， 直接把頁上層目錄表項指針強制轉換成頁中間目錄表項 。
每個進程有獨立的頁表，進程的mm_struct實例的成員pgd指向頁全局目錄,前面四級頁表的表項存放下一級頁表的起始地址，直接頁表的頁表項存放頁幀號(PFN) 。
內核也有一個頁表， 0號內核線程的進程描述符init_task的成員active_mm指向內存描述符init_mm，內存描述符init_mm的成員pgd指向內核的頁全局目錄swapper_pg_dir 。
ARM64處理器把頁表稱為轉換表，最多4級。ARM64處理器支持三種頁長度：4KB，16KB，64KB。頁長度和虛擬地址的寬度決定了轉換表的級數，在虛擬地址的寬度為48位的條件下，頁長度和轉換表級數的關系如下所示：
ARM64處理器把表項稱為描述符，使用64位的長描述符格式。描述符的0bit指示描述符是不是有效的：0表示無效，1表示有效。第1位指定描述符類型。
在塊描述符和頁描述符中，內存屬性被拆分為一個高屬性和一個低屬性塊。
處理器的MMU負責把虛擬地址轉換成物理地址，為了改進虛擬地址到物理地址的轉換速度，避免每次轉換都需要查詢內存中的頁表，處理器廠商在管理單元里加了稱為TLB的高速緩存，TLB直譯為轉換後備緩沖區，意譯為頁表緩存。
頁表緩存用來緩存最近使用過的頁表項， 有些處理器使用兩級頁表緩存 ： 第一級TLB分為指令TLB和數據TLB，好處是取指令和取數據可以並行；第二級TLB是統一TLB，即指令和數據共用的TLB 。
不同處理器架構的TLB表項的格式不同。ARM64處理器的每條TLB表項不僅包含虛擬地址和物理地址，也包含屬性：內存類型、緩存策略、訪問許可權、地址空間標識符(ASID)和虛擬機標識符(VMID)。 地址空間標識符區分不同進程的頁表項 ， 虛擬機標識符區分不同虛擬機的頁表項 。
如果內核修改了可能緩存在TLB裡面的頁表項，那麼內核必須負責使舊的TLB表項失效，內核定義了每種處理器架構必須實現的函數。
當TLB沒有命中的時候，ARM64處理器的MMU自動遍歷內存中的頁表，把頁表項復制到TLB，不需要軟體把頁表項寫到TLB，所以ARM64架構沒有提供寫TLB的指令。
為了減少在進程切換時清空頁表緩存的需要，ARM64處理器的頁表緩存使用非全局位區分內核和進程的頁表項(nG位為0表示內核的頁表項)， 使用地址空間標識符(ASID)區分不同進程的頁表項 。
ARM64處理器的ASID長度是由具體實現定義的，可以選擇8位或者16位。寄存器TTBR0_EL1或者TTBR1_EL1都可以用來存放當前進程的ASID，通常使用寄存器TCR_EL1的A1位決定使用哪個寄存器存放當前進程的ASID，通常使用寄存器 TTBR0_EL1 。寄存器TTBR0_EL1的位[63:48]或者[63:56]存放當前進程的ASID，位[47:1]存放當前進程的頁全局目錄的物理地址。
在SMP系統中，ARM64架構要求ASID在處理器的所有核是唯一的。假設ASID為8位，ASID只有256個值，其中0是保留值，可分配的ASID范圍1~255，進程的數量可能超過255，兩個進程的ASID可能相同，內核引入ASID版本號解決這個問題。
(1)每個進程有一個64位的軟體ASID， 低8位存放硬體ASID，高56位存放ASID版本號 。
(2) 64位全局變數asid_generation的高56位保存全局ASID版本號 。
(3) 當進程被調度時，比較進程的ASID版本號和全局版本號 。如果版本號相同，那麼直接使用上次分配的ASID，否則需要給進程重新分配硬體ASID。
存在空閑ASID，那麼選擇一個分配給進程。不存在空閑ASID時，把全局ASID版本號加1，重新從1開始分配硬體ASID，即硬體ASID從255回繞到1。因為剛分配的硬體ASID可能和某個進程的ASID相同，只是ASID版本號不同，頁表緩存可能包含了這個進程的頁表項，所以必須把所有處理器的頁表緩存清空。
引入ASID版本號的好處是：避免每次進程切換都需要清空頁表緩存，只需要在硬體ASID回環時把處理器的頁表緩存清空 。
虛擬機裡面運行的客戶操作系統的虛擬地址轉物理地址分兩個階段：
(1) 把虛擬地址轉換成中間物理地址，由客戶操作系統的內核控制 ，和非虛擬化的轉換過程相同。
(2) 把中間物理地址轉換成物理地址，由虛擬機監控器控制 ，虛擬機監控器為每個虛擬機維護一個轉換表，分配一個虛擬機標識符，寄存器 VTTBR_EL2 存放當前虛擬機的階段2轉換表的物理地址。
每個虛擬機有獨立的ASID空間 ，頁表緩存使用 虛擬機標識符 區分不同虛擬機的轉換表項，避免每次虛擬機切換都要清空頁表緩存，在虛擬機標識符回繞時把處理器的頁表緩存清空。
② 在請求分頁式存儲管理中,為什麼既有頁表,又有快表
實際系統中的做法是採用內存頁表和快表相結合的解決方案。系統總是先通過頁號與快表中的所有表項進行比較。如果發現匹配的頁，則將塊號直接從快表中取出，而不必通過頁表。
也是該塊號與頁內位移拼接，形成所需要的絕對地址。如果快表中沒有匹配的頁號時，系統訪問頁表進行掉進塊號。提高讀取數據的速度。
(2)頁表高速緩存擴展閱讀：
快表就是存放在高速緩沖存儲器的部分頁表。作為頁表的Cache，它的作用與頁表相似，但是提高了訪問速率。由於採用頁表做地址轉換，讀寫內存數據時CPU要訪問兩次主存。有了快表，有時只要訪問一次高速緩沖存儲器，一次主存，這樣可加速查找並提高指令執行速度。
③ Linux存儲管理方式
這種方式中，將用戶程序的地址空間，注意，是 用戶程序的地址空間 分為若干個固定大小的區域，成為「頁」或「頁面」。我們可以知道，這也頁其實是不存在的，只是一種劃分內存空間的方法。也就是說，這種方式將用戶的程序 「肢解」 了，分成很多個小的部分，每個部分稱為一個「頁」。
將邏輯地址的前n位作為頁號，後面32-n位作為頁內偏移量。
由於進程的最後一頁經常裝不滿一個塊，從而形成了不可利用的碎片，稱之為 「頁內碎片」 。
作用：實現頁號到物理號的地址映射。
頁表是記錄邏輯空間（虛擬內存）中每一頁在內存中對應的物理塊號。但並非每一頁邏輯空間都會實際對應著一個物理塊，只有實際駐留在物理內存空間中的頁才會對應著物理塊。
系統會為每一個進程建立一張頁表，頁表是需要一直駐留在物理內存中的（多級頁表除外），另外頁表的起址和長度存放在 PCB（Process Control Block）進程式控制制結構體中。
可以在頁表的表項中設置相關的許可權控制欄位，例如設置存取控制欄位，用於保護該存儲塊的讀寫；若存取控制欄位為2位，則可以設置讀/寫、只讀和只執行等存取方式。
物理塊是實實在在存在於內存中的：
由於執行頻率高，要求效率比較高，需要使用硬體實現。
在系統中設置一個 頁表寄存器(PTR) ,其中存放頁表在內存的起始地址和頁表的長度。平時進程未執行的時候，頁表的起始地址和頁表長度放在本進程的PCB中。當調度程序調度到某個進程的時候，才將這兩個數據裝入 頁表寄存器 。
變換過程：
快表的變換機構
為了提高地址變換速度，可在地址變換機構中增設一個具有並行查詢能力的特殊高速緩沖寄存器，又稱為"聯想寄存器"或者「快表」。俗稱TLB。
快表與頁表的功能類似，其實就是將一部分頁表存到 CPU 內部的高速緩沖存儲器 Cache。CPU 定址時先到快表查詢相應的頁表項形成物理地址，如果查詢不到，則到內存中查詢，並將對應頁表項調入到快表中。但，如果快表的存儲空間已滿，則需要通過演算法找到一個暫時不再需要的頁表項，將它換出內存。
由於成本的關系，快表不可能做得很大，通常只存放 16~512 個頁表項，這對中、小型作業來說，已有可能把全部頁表項放在快表中；但對於大型作業而言，則只能將其一部分頁表項放入其中。由於對程序和數據的訪問往往帶有局限性，因此，據統計，從快表中能找到所需頁表項的概率可達 90% 以上。這樣，由於增加了地址變換機構而造成的速度損失可減少到 10% 以下，達到了可接受的程度。
我們可以採用這樣兩個方法來解決這一問題：
① 對於頁表所需的內存空間，可採用離散分配方式，以解決難以找到一塊連續的大內存空間的問題；
② 只將當前需要的部分頁表項調入內存，其餘的頁表項仍駐留在磁碟上，需要時再調入。
二級頁表的頁表項：
過程：
在採用兩級頁表結構的情況下，對於正在運行的進程，必須將其外層頁表調入內存，而對於內頁表則只需調入一頁或幾頁。為了表徵某頁的頁表是否已經調入內存，還應在外層頁表項中增設一個狀態位 S，其值若為 0，表示該頁表分頁不在內存中，否則說明其分頁已調入內存。進程運行時，地址變換機構根據邏輯地址中的 P1去查找外層頁表；若所找到的頁表項中的狀態位為 0，則產生一個中斷信號，請求 OS 將該頁表分頁調入內存。
多級頁表和二級頁表類似。多級頁表和二級頁表是為了節省物理內存空間。使得頁表可以在內存中離散存儲。（單級頁表為了隨機訪問必須連續存儲，如果虛擬內存空間很大，就需要很多頁表項，就需要很大的連續內存空間，但是多級頁表不需要。）
為什麼引入分段存儲管理？
引入效果：
它將用戶程序的地址空間分為若干個大小不同的的段，每個段可以定義一組完整的信息。
段號表示段名，每個段都從0開始編址，並且採用一段連續的地址空間。
在該地址結構中，允許一個作業最長有64K個段，每個段的最大長度為64KB。
在分段式存儲管理系統中，為每一個分段分配一個連續的分區。進程的各個段，可以離散地裝入內存中不同的分區中。
作用：實現從邏輯地址到物理內存區的映射。
為了保證程序能夠正常運行，就必須能夠從物理內存中找出每個邏輯段所對應的位置。為此在系統中會為每一個進程建立一張 段表 。每個段在表中有一個表項，其中記錄了該段在內存中的起始地址和段的長度。一般將段表保存在內存中。
在配置了段表之後，執行的過程可以通過查找段表，找到每一個段所對應的內存區。
為了實現進程從邏輯地址到物理地址的變換功能，在系統設置了段表寄存器，用於存放段表的起始地址和段表長度TL。
在進行地址變換時，系統將邏輯地址中的段號與段表長度TL 進行比較。若 S > TL，表示段號太大，是訪問越界，於是產生越界中斷信號。若未越界，則根據段表的始址和該段的段號，計算出該段對應段表項的位置，從中讀出該段在內存的起始地址。然後，再檢查段內地址 d 是否超過該段的段長 SL。若超過，即 d>SL，同樣發出越界中斷信號。若未越界，則將該段的基址 d 與段內地址相加，即可得到要訪問的內存。
分頁和分段系統相似之處：兩者都採用離散分配方式，且都是通過地址映射機構實現地址變換。
但在概念上兩者完全不同，主要表現在下述三個方面：
分頁系統以頁面作為內存分配的基本單位，能有效地提高內存利用率，而分段系統以段作為內存分配的基本單位，它能夠更好地滿足用戶多方面的需要。
段頁式地址結構由段號、段內頁號及頁內地址三部分所組成
段頁式系統的基本原理是分段和分頁原理的結合，即先將用戶程序分成若干個段，再把每個段分成若干個頁，並為每一個段賦予一個段名。如下圖展示了一個作業地址空間的結構。該作業有三個段：主程序段、子程序段和數據段；頁面大小為 4 KB：
在段頁式系統中，為了實現從邏輯地址到物理地址的變換，系統中需要同時配置段表和頁表。段表的內容與分段系統略有不同，它不再是內存始址和段長，而是頁表始址和頁表長度。下圖展示出了利用段表和頁表進行從用戶地址空間到物理(內存)空間的映射。
在段頁式系統中，為了便於實現地址變換，須配置一個段表寄存器，其中存放段表始址和段長 TL。進行地址變換時，首先利用段號 S，將它與段長 TL 進行比較。若 S < TL，表示未越界，於是利用段表始址和段號來求出該段所對應的段表項在段表中的位置，從中得到該段的頁表始址，並利用邏輯地址中的段內頁號 P 來獲得對應頁的頁表項位置，從中讀出該貝所在的物理塊號 b，再利用塊號 b 和頁內地址來構成物理地址。
在段頁式系統中，為了獲得一條指令或數據，須三次訪問內存。第一次訪問是訪問內存中的段表，從中取得頁表始址；第二次訪問是訪問內存中的頁表，從中取出該頁所在的物理塊號，並將該塊號與頁內地址一起形成指令或數據的物理地址；第三次訪問才是真正從第二次訪問所得的地址中取出指令或數據。
顯然，這使訪問內存的次數增加了近兩倍。為了提高執行速度，在地址變換機構中增設一個高速緩沖寄存器。每次訪問它時，都須同時利用段號和頁號去檢索高速緩存，若找到匹配的表項，便可從中得到相應頁的物理塊號，用來與頁內地址一起形成物理地址：若未找到匹配表項，則仍需第三次訪問內存。
參考鏈接：
④ CPU Cache
title: CPU Cache
date: 2019-11-17 20:20:30
keywords: cache "CPU cache" "三級緩存" 緩存映射 cache原理 多級cache TLB
引入 Cache 的理論基礎是程序局部性原理，包括時間局部性和空間局部性。時間局部性原理即最近被CPU訪問的數據，短期內CPU 還要訪問（時間）；空間局部性即被CPU訪問的數據附近的數據，CPU短期內還要訪問（空間）。因此如果將剛剛訪問過的數據緩存在一個速度比主存快得多的存儲中，那下次訪問時，可以直接從這個存儲中取，其速度可以得到數量級的提高。
CPU緩存是（Cache Memory）位於CPU與內存之間的臨時存儲器，它的容量比內存小但交換速度快。在緩存中的數據是內存中的一小部分，但這一小部分是短時間內CPU即將訪問的，當CPU調用大量數據時，就可避開內存直接從緩存中調用，從而加快讀取速度。
在CPU中加入緩存是一種高效的解決方案，是對於存儲器件成本更低，速度更快這兩個互相矛盾的目標的一個最優解決方案，這樣整個內存儲器（緩存+內存）就變成了既有緩存的高速度，又有內存的大容量的存儲系統了。緩存對CPU的性能影響很大，主要是因為CPU的數據交換順序和CPU與緩存間的帶寬引起的。
下圖是一個典型的存儲器層次結構，我們可以看到一共使用了三級緩存
各級存儲訪問延遲的對比
介於CPU和主存儲器間的高速小容量存儲器，由靜態存儲晶元SRAM組成，容量較小但比主存DRAM技術更加昂貴而快速， 接近於CPU的速度。CPU往往需要重復讀取同樣的數據塊， Cache的引入與緩存容量的增大，可以大幅提升CPU內部讀取數據的命中率，從而提高系統性能。通常由高速存儲器、聯想存儲器、地址轉換部件、替換部件等組成。如圖所示。
早期採用外部（Off-chip）Cache，不做在CPU內而是獨立設置一個Cache。現在採用片內（On-chip）Cache，將Cache和CPU作在一個晶元上，且採用多級Cache，同時使用L1 Cache和L2 Cache，甚至有L3 Cache。
上圖顯示了最簡單的緩存配置。它對應著最早期使用CPU cache的系統的架構。CPU內核不再直接連接到主內存。所有的數據載入和存儲都必須經過緩存。CPU核心與緩存之間的連接是一種特殊的快速連接。在一個簡化的表示中，主存和高速緩存連接到系統匯流排，該系統匯流排也可用於與系統的其他組件進行通信。我們引入了系統匯流排（現代叫做「FSB」）。
引入緩存後不久，系統變得更加復雜。高速緩存和主存之間的速度差異再次增大，使得另一個級別的高速緩存不得不被添加進來，它比第一級高速緩存更大且更慢。出於經濟原因，僅增加第一級緩存的大小不是一種選擇。今天，甚至有機器在生產環境中使用了三級緩存。帶有這種處理器的系統如圖下所示。隨著單個CPU的內核數量的增加，未來的緩存級別數量可能會增加。現在已經出現了擁有四級cache的處理器了。
上圖展示了三級緩存的結構。L1d是一級數據cache，L1i是一級指令cache。請注意，這只是一個示意圖; 現實中的數據流從core到主存的過程中不需要經過任何更高級別的cache。CPU設計人員有很大的自由來設計cache的介面。對於程序員來說，這些設計選擇是不可見的。
另外，我們有擁有多個core的處理器，每個core可以有多個「線程」。核心和線程之間的區別在於，獨立的核心具有所有硬體資源的獨立的副本，早期的多核處理器，甚至具有單獨的第二級緩存而沒有第三級緩存。核心可以完全獨立運行，除非它們在同一時間使用相同的資源，例如與外部的連接。另一方面，線程們共享幾乎所有的處理器資源。英特爾的線程實現只為線程提供單獨的寄存器，甚至是有限的，還有一些寄存器是共享的。
一個現代CPU的完整概貌如圖所示。
由於cache中對應的都是主存地址，即物理地址，在cqu查看具體數據是否在cache中時，如果CPU傳送過來的地址時一個虛擬地址，需要將其轉換成實際物理地址再到cache中去尋找。Cache的實現需要TLB的幫助。可以說TLB命中是Cache命中的基本條件。TLB不命中，會更新TLB項，這個代價非常大，Cache命中的好處基本都沒有了。在TLB命中的情況下，物理地址才能夠被選出，Cache的命中與否才能夠達成。
TLB是一個內存管理單元用於改進虛擬地址到物理地址轉換速度的緩存。TLB是位於內存中的頁表的cache，如果沒有TLB，則每次取數據都需要兩次訪問內存,即查頁表獲得物理地址和取數據。
當cpu對數據進行讀請求時,CPU根據虛擬地址(前20位)到TLB中查找.TLB中保存著虛擬地址(前20位)和頁框號的對映關系,如果匹配到虛擬地址就可以迅速找到頁框號(頁框號可以理解為頁表項),通過頁框號與虛擬地址後12位的偏移組合得到最終的物理地址.
如果沒在TLB中匹配到虛擬地址,就出現TLB丟失,需要到頁表中查詢頁表項,如果不在頁表中,說明要讀取的內容不在內存,需要到磁碟讀取.
TLB是MMU中的一塊高速緩存,也是一種Cache.在分頁機制中,TLB中的數據和頁表的數據關聯,不是由處理器維護,而是由OS來維護,TLB的刷新是通過裝入處理器中的CR3寄存器來完成.如果MMU發現在TLB中沒有命中,它在常規的頁表查找後,用找到的頁表項替換TLB中的一個條目.
當進程進行上下文切換時重新設置cr3寄存器,並且刷新tlb.
有兩種情況可以避免刷tlb.
第一種情況是使用相同頁表的進程切換.
第二種情況是普通進程切換到內核線程.
lazy-tlb(懶惰模式)的技術是為了避免進程切換導致tlb被刷新.
當普通進程切換到內核線程時,系統進入lazy-tlb模式,切到普通進程時退出該模式.
cache是為了解決處理器與慢速DRAM(慢速DRAM即內存)設備之間巨大的速度差異而出現的。cache屬於硬體系統,linux不能管理cache.但會提供flush整個cache的介面.
cache分為一級cache,二級cache,三級cache等等.一級cache與cpu處於同一個指令周期.
CPU從來不從DRAM直接讀/寫位元組或字,從CPU到DRAM的每次讀或寫的第一步都要經過L1 cache,每次以整數行讀或寫到DRAM中.Cache Line是cache與DRAM同步的最小單位.典型的虛擬內存頁面大小為4KB,而典型的Cache line通常的大小為32或64位元組.
CPU 讀/寫內存都要通過Cache,如果數據不在Cache中,需要把數據以Cache Line為單位去填充到Cache,即使是讀/寫一個位元組.CPU 不存在直接讀/寫內存的情況,每次讀/寫內存都要經過Cache.
緩存里有的數據，主存中一定存在。
一級緩存中還分數據緩存（data cache，d-cache）和指令緩存（instruction cache，i-cache）。二者分別用來存放數據和執行這些數據的指令，而且兩者可以同時被cpu訪問，所以一級cache間數據時獨立的。
一級沒有的數據二級可能有也可能沒有。因為一級緩存miss會接著訪問二級緩存。
一級有二級一定有，三級也一定有。因為一級的數據從二級中讀上來的。在一級缺失二級命中時發生。
二級沒有的數據三級可能有也可能沒有。因為二級確實會接著訪問三級緩存。找不到會繼續訪問主存。
二級有的數據三級一定有。在二級缺失三級命中時，數據會從三級緩存提到二級緩存。
三級沒有的數據，主存可能有也可能沒有。三級緩存缺失，會訪問主存，主存也缺失就要從外存訪問數據了。
三級緩存有的數據主存一定有。因為在三級缺失主存命中時，數據會從主存提到三級緩存中來。
一級緩存就是指CPU第一層級的高速緩存，主要是為了緩存指令和緩存數據，一級緩存的容量對CPU性能影響非常大，但是因為成本太高，所以一般容量特別小，也就256KB左右。
二級緩存是CPU第二層級的高速緩存，對於CPU來說，二級緩存容量越大越好，它是直接影響CPU性能的，CPU每個核心都會有自己的緩存，一個CPU的二級緩存容量是所有核心二級緩存容量的總和。
三級緩存就是CPU第三層級的高速緩存，主要是為了降低與內存進行數據傳輸時的延遲問題，三級緩存與一二級不同，三級緩存只有一個，它是所有核心共享，所以在CPU參數中可以看到，三級緩存相對於其他兩級緩存來說都很大。
由於緩存的設置與OS無關且透明，所以對於不同的體系架構下不同的處理器對待緩存區域的處理和方式都不同，不同的處理器也有不同的緩存設置值。從主流的處理器cache大小來看，一般一個cache line的大小都是固定的64B左右，這是經過經驗得到的比較合理的大小，一般一級cache大小在數十KB左右，二級cache大小在數十到數百KB左右，而L3 cache大小在數MB左右。
由於三級cache一般來說是運用於擁有多核的處理器，對於單核處理器來說二級cache就能夠足夠保持夠高的cache命中率。所以一般的三級cache一般只針對於多核處理器。L1和L2級cache是處理器核所單獨的內容。L1又可以看成是L2的cache。L2可以看成是L3級cache的cache。所以我們分兩個部分討論數據放置與數據淘汰策略。
各級cache間的數據放置策略主要有三種。直接相連映射，全相聯映射和組相聯映射。將一個主存塊存儲到唯一的一個Cache行。對應的大小都是一個cache line的大小，一般來說是64B。
多對一的映射關系，但一個主存塊只能拷貝到cache的一個特定行位置上去。cache的行號i和主存的塊號j有如下函數關系：i=j mod m（m為cache中的總行數）。
可以將一個主存塊存儲到任意一個Cache行。
主存的一個塊直接拷貝到cache中的任意一行上
可以將一個主存塊存儲到唯一的一個Cache組中任意一個行。
將cache分成u組，每組v行，主存塊存放到哪個組是固定的，至於存到該組哪一行是靈活的，即有如下函數關系：cache總行數m＝u×v 組號q＝j mod u
組間採用直接映射，組內為全相聯。硬體較簡單，速度較快，命中率較高。是現代處理器中一般所常用的映射方式。
Cache工作原理要求它盡量保存最新數據，當從主存向Cache傳送一個新塊，而Cache中可用位置已被占滿時，就會產生Cache替換的問題。
常用的替換演算法有下面三種。
LFU（Least Frequently Used，最不經常使用）演算法將一段時間內被訪問次數最少的那個塊替換出去。每塊設置一個計數器，從0開始計數，每訪問一次，被訪塊的計數器就增1。當需要替換時，將計數值最小的塊換出，同時將所有塊的計數器都清零。
這種演算法將計數周期限定在對這些特定塊兩次替換之間的間隔時間內，不能嚴格反映近期訪問情況，新調入的塊很容易被替換出去。
LRU（Least Recently Used，近期最少使用）演算法是把CPU近期最少使用的塊替換出去。這種替換方法需要隨時記錄Cache中各塊的使用情況，以便確定哪個塊是近期最少使用的塊。每塊也設置一個計數器，Cache每命中一次，命中塊計數器清零，其他各塊計數器增1。當需要替換時，將計數值最大的塊換出。
LRU演算法相對合理，但實現起來比較復雜，系統開銷較大。這種演算法保護了剛調入Cache的新數據塊，具有較高的命中率。LRU演算法不能肯定調出去的塊近期不會再被使用，所以這種替換演算法不能算作最合理、最優秀的演算法。但是研究表明，採用這種演算法可使Cache的命中率達到90%左右。
最簡單的替換演算法是隨機替換。隨機替換演算法完全不管Cache的情況，簡單地根據一個隨機數選擇一塊替換出去。隨機替換演算法在硬體上容易實現，且速度也比前兩種演算法快。缺點則是降低了命中率和Cache工作效率。
處理器微架構訪問Cache的方法與訪問主存儲器有類似之處。主存儲器使用地址編碼方式，微架構可以地址定址方式訪問這些存儲器。Cache也使用了類似的地址編碼方式，微架構也是使用這些地址操縱著各級Cache，可以將數據寫入Cache，也可以從Cache中讀出內容。只是這一切微架構針對Cache的操作並不是簡單的地址訪問操作。為簡化起見，我們忽略各類Virtual Cache，討論最基礎的Cache訪問操作，並藉此討論CPU如何使用TLB完成虛實地址轉換，最終完成對Cache的讀寫操作。
Cache的存在使得CPU Core的存儲器讀寫操作略微顯得復雜。CPU Core在進行存儲器方式時，首先使用EPN(Effective Page Number)進行虛實地址轉換，並同時使用CLN(Cache Line Number)查找合適的Cache Block。這兩個步驟可以同時進行。在使用Virtual Cache時，還可以使用虛擬地址對Cache進行定址。為簡化起見，我們並不考慮Virtual Cache的實現細節。
EPN經過轉換後得到VPN，之後在TLB中查找並得到最終的RPN(Real Page Number)。如果期間發生了TLB Miss，將帶來一系列的嚴重的系統懲罰，我們只討論TLB Hit的情況，此時將很快獲得合適的RPN，並依此得到PA(Physical Address)。
在多數處理器微架構中，Cache由多行多列組成，使用CLN進行索引最終可以得到一個完整的Cache Block。但是在這個Cache Block中的數據並不一定是CPU Core所需要的。因此有必要進行一些檢查，將Cache Block中存放的Address與通過虛實地址轉換得到的PA進行地址比較(Compare Address)。如果結果相同而且狀態位匹配，則表明Cache Hit。此時微架構再經過Byte Select and Align部件最終獲得所需要的數據。如果發生Cache Miss，CPU需要使用PA進一步索引主存儲器獲得最終的數據。
由上文的分析，我們可以發現，一個Cache Block由預先存放的地址信息，狀態位和數據單元組成。一個Cache由多個這樣的Cache Block組成，在不同的微架構中，可以使用不同的Cache Block組成結構。我們首先分析單個Cache Block的組成結構。單個Cache Block由Tag欄位，狀態位和數據單元組成，如圖所示。
其中Data欄位存放該Cache Block中的數據，在多數處理器微架構中，其大小為32或者64位元組。Status欄位存放當前Cache Block的狀態，在多數處理器系統中，這個狀態欄位包含MESI，MOESI或者MESIF這些狀態信息，在有些微架構的Cache Block中，還存在一個L位，表示當前Cache Block是否可以鎖定。許多將Cache模擬成SRAM的微架構就是利用了這個L位。有關MOESIFL這些狀態位的說明將在下文中詳細描述。在多核處理器和復雜的Cache Hierarchy環境下，狀態信息遠不止MOESIF。
RAT(Real Address Tag)記錄在該Cache Block中存放的Data欄位與那個地址相關，在RAT中存放的是部分物理地址信息，雖然在一個CPU中物理地址可能有40，46或者48位，但是在Cache中並不需要存放全部地址信息。因為從Cache的角度上看，CPU使用的地址被分解成為了若干段，如圖所示。
這個地址也可以理解為CPU訪問Cache使用的地址，由多個數據段組成。首先需要說明的是Cache Line Index欄位。這一欄位與Cache Line Number類似，CPU使用該欄位從Cache中選擇一個或者一組Entry。
Bank和Byte欄位之和確定了單個Cache的Data欄位長度，通常也將這個長度稱為Cache 行長度，上圖所示的微架構中的Cache Block長度為64位元組。目前多數支持DDR3 SDRAM的微架構使用的Cache Block長度都是64位元組。部分原因是由於DDR3 SDRAM的一次Burst Line為8，一次基本Burst操作訪問的數據大小為64位元組。
在處理器微架構中，將地址為Bank和Byte兩個欄位出於提高Cache Block訪問效率的考慮。Multi-Bank Mechanism是一種常用的提高訪問效率的方法，採用這種機制後，CPU訪問Cache時，只要不是對同一個Bank進行訪問，即可並發執行。Byte欄位決定了Cache的埠位寬，在現代微架構中，訪問Cache的匯流排位寬為64位或者為128位。
剩餘的欄位即為Real Address Tag，這個欄位與單個Cache中的Real Address Tag的欄位長度相同。CPU使用地址中的Real Address Tag欄位與Cache Block的對應欄位和一些狀態位進行聯合比較，判斷其訪問數據是否在Cache中命中
如果cache miss,就去下一級cache或者主存中去查找數據，並將查找到的數據採用上面的數據淘汰策略將數據替換到cache中。
由於在發生cache miss時會產生數據替換，在運行過程中緩存的數據也可能會被修改。所以需要一個策略來保持數據在緩存和主存間的一致性。
Cache寫機制分為write through和write back兩種。
⑤ 基本分頁存儲管理
假設是按位元組編址
考慮支持多道程序的兩種連續分配方式
原因：連續分配要求進程佔有的必須是一塊連續的內存區域
能否講一個進程分散地裝入到許多不相鄰的分區，便可充分利用內存
基本分頁存儲管理的思想：把內存分為一個個相等的小分區，再按照分區大小把進程拆分成一個個小部分
頁框/頁幀：內存空間分成的一個個大小相等的分區（比如4KB）
頁框號：頁框的編號，從0開始，從低地址開始
頁/頁面：用戶進程的地址空間分為和頁框大小相等的一個個區域
頁號：頁/頁面的編號，從0開始
進程的最後一個頁面可能沒有一個頁框那麼大，頁框不能太大，否則可能產生過大的內部碎片
操作系統以頁框為單位為各個進程分配內存空間。進程的每個頁面分別放入一個頁框中，也就是說，進程的頁面與內存的頁框有一一對應的關系
每個頁面不必連續存放，也不必按照先後順序，可以放到不相鄰的各個頁框中
進程在內存中連續存放時，通過動態重定位實現邏輯地址到物理地址的轉換。在裝入模塊之後，內存中指令使用的依然是邏輯地址，直到指令執行的時候才會進行地址轉換。系統會設置一個重定位寄存器，用來存放裝入模塊存放的起始位置，重定位寄存器中的值加上邏輯地址就是該邏輯地址實際對應的物理地址
如果採用分頁技術
頁框大小為4KB，地址空間為4GB的系統
頁號為前20位，頁內偏移量為後12位
頁表：為了能知道進程的每個頁面在內存中存放的位置，操作系統要為每個進程建立一張頁表
一個進程對應一張頁表
進程的每一頁對應一個頁表項
每個頁表項由頁號和頁框號組成
頁表記錄進程頁面和實際存放的頁框之間的對應關系
每個頁表項的長度是相同的，頁號是隱含的
各頁表項會按順序連續存放在內存中，如果該頁表在內存中的起始地址是X，4GB/4KB系統的頁框有
用於實現邏輯地址到物理地址轉換的一組硬體機構
通常會在系統中設置一個頁表寄存器(PTR)，存放頁表在內存中的起始地址F和頁表長度M（M個頁表項）
進程未執行時，頁表的起始地址和頁表長度放在進程式控制制塊(PCB)中，當進程被調度時，操作系統內核會把他們放到頁表寄存器中
基本分頁存儲管理中地址是一維的，即只要給出一個邏輯地址，系統就可以自動計算出頁號、偏移量，不需要顯式告訴系統偏移量是多少
理論上，頁表項長度為3即可表示內存塊號的范圍，但是為了方便頁表查詢，會讓頁面恰好能裝得下整數個頁表項，令每個頁表項佔4位元組
4KB頁面，可以放4096/3 =1365個頁表項，有4096%3 =1B的碎片，訪問1365及之後的頁表項時，還要考慮前面的頁框中的碎片，才能得到頁表項的物理地址，比較麻煩
進程頁表通常存放在連續的頁框中，這樣就能用統一的計算方式得到想要得到的頁表項存儲的位置
地址變換過程中有兩次訪存操作：查詢頁表、訪問目標內存單元
局部性原理
如果這個程序將程序對應的指令存放在10號內存塊，將程序中定義的變數存放在23號內存塊，當這個程序執行時，會很頻繁地反問10、23號內存塊
時間局部性：如果執行了程序中的某條指令，那麼不久後這條指令很有可能被再次執行；如果某個數據被訪問過，不久之後該數據很有可能再次被訪問（因為程序存在大量循環）
空間局部性：一旦程序訪問了某個存儲單元，在不久之後，其附近的存儲單元也很有可能被訪問（因為很多數據在內存中連續存放）
基本地址變換機構中，每次要訪問一個邏輯地址，都要查詢頁表，由於局部性原理，可能連續多次查詢同一個頁表項
快表：又稱聯想寄存器（TLB），是一種訪問速度比內存塊很多的高速緩存，用來存放當前訪問的若干頁表項，以加速地址變換的過程。內存中的頁表常稱為慢表
引入快表後地址的變換過程
一般來說，快表的命中率可以達到90%以上
單級頁表存在的問題
對問題1
可將頁表進行分組，使每個內存塊剛好可以放入一個分組。為離散分配的頁表再建立一張頁表，稱為頁目錄表，或外層頁表
各級頁表的大小不能超過一個頁面
針對兩級頁表
對問題2
可以在需要訪問頁面時，才把頁面調入內存（虛擬存儲技術），可以在頁表項中增加一個標志位，用於表示該頁面是否已經調入內存
若想訪問的頁面不在內存中，會產生缺頁中斷（內中斷），然後將目標頁面從外存調入內存
之後的文章會有展開
兩級頁表訪存次數分析：如果沒有TLB，第一次訪存是訪問內存中的頁目錄表，第二次訪存是訪問內存中的二級頁表，第三次訪存是訪問目標內存單元
⑥ 為什麼部分頁表放入內存,另一部分放入高速緩存
頁表只可能存在於TLB和memory中,不可能存在於cache中
⑦ 快表TLB和高速緩沖存儲器cache有什麼區別
1、快表TLB： 用於虛擬存儲技術，是為了加快輔存向主存的地址映射速度（主存—輔存系統）
2、高速緩存器cache：用於解決CPU與主存速度不匹配問題。（CPU—主存系統）
2.1、cache補充：因為CPU速度遠高於主存，主存跟不上，導致CPU的大量時間在等待主存，效率低下。因為cache速度介於CPU與主存之間，價格也介於兩者之間，所以人們在CPU與主存之間添加「高速緩沖器cache」來緩解速度不匹配問題。
總的來說，兩者屬於兩個不同的系統層次，功能也不同。
⑧ 什麼是快表
有兩種意思。一是存儲器的一種，二是一個軟體設計平台。
1、存儲器的一種：
快表是一種特殊的高速緩沖存儲器，內容是頁表中的一部分或全部內容。
在操作系統中引入快表是為了加快地址映射速度。
2、軟體設計平台：
快表軟體是第三代Excel類軟體設計平台，國內第一家純WEB、面向各行業各層次人員的雲端Excel系統設計與運行平台。
(8)頁表高速緩存擴展閱讀：
快表軟體的優點：
1、軟體集需求設計和運行於一體，非專業開發者無需掌握編程語言和資料庫知識，即可根據自己的業務需求輕松搭建個性化的信息系統。
2、專業開發者也可利用快表的高級功能，降低了純代碼開發的難度並極大地提高了開發效率，實現更加專業、快速、高效的開發。
3、通過快表軟體開發平台，可以快速構建報表系統、ERP、OA、CRM、EAI、BI等適合用戶自身需求特色的信息化系統。
⑨ Intel 80386 Reference Programmer's Manual - 5.2 Page Translation
頁轉換主要實現了面向頁的虛擬內存系統和頁層次保護。若操作系統需要使用相關功能，則必須將CR0的PG位置位。
頁是一個以4KB的連續物理地址形成的單元。
線性地址通過制定一個頁表(page table)，表中的頁(page)，以及頁中的偏移量間接地指定一個物理地址。線性地址共分為三部分，最高位10位為頁目錄的索引，中間10位為頁表索引，最低位12位為頁偏移量。
從線性地址轉換為物理地址的定址機制為：將31-22位地址作為索引從頁目錄(Page Directory)中尋找到對應頁表(Page Table)，將21-12位地址作為索引從頁表中尋找到對應的頁(Page Frame)，再使用11-0位作為頁偏移量(Offset)從頁中找到對應的物理地址。
頁表本身是一個頁，因此其擁有一個頁大小的內存，即4KB。由於頁表實質上是一個32位頁指示符的數組，所以最多擁有1K項條目(4KB*8/32=1KB)。
頁表有兩層層次結構，其中位於高層次的頁表僅有一個，被稱為頁目錄(page directory)，頁目錄指向了共1K個第二層次的頁表(page table)，而第二層次的每個頁表指向1K個頁，由此組織出二級頁表層級結構。簡單的計算可以得知，兩級頁表層級結構共可以指向1M(2 (20))個頁，而每個頁包含有4Kb(2 (12)bytes)，因此含有一個頁目錄的二級頁表層級結構共可以組織起4GB物理地址空間(2^(20) times 2^(12) = 2^(32))。
當前的頁目錄的物理地址將儲存在CPU的CR3寄存器中，該寄存器也可以稱為頁目錄基地址寄存器(page directory base register)。內存管理軟體可以選擇為所有任務(task)使用同一個頁目錄，也可以選擇為每個任務使用單獨的頁目錄，或者使用這兩者的混合策略。
附1：雖然在理論上，所有任務都分別使用單獨的頁目錄使得對每個任務而言，線性地址到物理地址的映射完全不同（通過頁目錄指向完全不同的頁表、頁表指向完全不同的頁等等），但在實際中，必須要有部分的線性地址映射到相同的物理地址中。例如TSS地址和GDT等等。
附：在PG位被置位前，CR3寄存器必須已經被初始化並指向一個有效的頁目錄的物理地址。初始化進程必須採用以下兩種策略中的一種以便保證啟用頁前後地址的一致性：
所有層次的頁表中的項(entry)都具有相同的格式。其格式如下圖所示。頁表項的格式可以分為兩部分，分別是頁地址(Page Frame Address)和標識符.
頁地址位指示了頁的在內存中的物理地址（其中頁目錄中記錄的頁地址為頁表的物理地址，頁表中記錄的頁地址則指向包含所需要的地址的頁幀）。由於頁是以4KB大小對齊的，因此頁頭的物理地址的低12位將始終為0.由於這種特性，頁表項中以高位31-12位共20位指示頁地址，而剩下的低12位用於標識符記錄項的狀態信息。
最低位P表示一個項是否存在(present)。當P=1時表示這個項記錄的信息是可以用於進行地址轉換的（或者說是有效的）。
當P=0時，無論這個項處在頁表中的哪個層級，這個項都是無效的，即它不在地址轉換中起到作用。而剩下的位（高位31位）可以供軟體使用。當P=0時，其格式如下圖所示。
如果在任何層次的頁表中出現了試圖對P=0的項中進行地址轉換的情況，處理器則會發出一個頁面異常的信號。在支持頁虛擬內存的軟體系統中，缺頁異常(page-not-present exception)處理將請求的頁載入到物理內存中，然後再次執行產生異常的指令。
注意到頁目錄本身沒有存在位標識其是否存在。在一個任務被掛起時它的頁目錄有可能不被表示(not-present)，但是操作系統必須確保TSS中的CR3映像所指示的頁目錄在任務dispatched之前存在於物理內存中。
已訪問位和臟位在兩級頁表中都表示頁的使用情況。除了頁目錄項的臟位以外，這些位都由硬體設置；而處理器不會對已訪問位和臟位進行清理。
在對頁進行讀或寫操作之前，處理器會將對應的頁表項的已訪問位置為1.該操作對兩層頁表層級均是如此。在對某個頁中的地址進行寫操作之前，處理器會將對應的二級頁表項的臟位置為1；而頁目錄項的臟位沒有定義。
一個支持頁虛擬內存的操作系統可以通過已訪問位和臟位來決定當內存需求超過物理可用內存空間的時候，將哪些頁從物理內存中刪去。測試(test)和清除(clear)這些位是由操作系統來負責的。
這些位並不是用於進行地址轉換的，而是處理器在進行地址轉換的同時，用於進行基於頁的保護(page-level protection)時使用的數據。
為了最大化地址轉換的效率，處理器會將最近使用的頁表數據存儲在單片超高速緩存器(on-chip cache)中。只有當需要的分頁信息沒有在緩存器中的時候，兩級頁表才會被使用。
頁轉換緩存對於應用程序員(applications programmer)來說是不可見的，但是對於系統程序員(system programmer)來說是可見的；當頁表改變的時候，操作系統程序員(operating-system programmer)必須刷新緩存區。頁轉換緩存可以使用以下兩種方式進行刷新：