湖南大學計算機與通信學院1第9章存儲器結構9.1存儲器的層次結構9.2Cache存儲器9.3虛擬存儲器9.4基本Cache和虛擬存儲器的擴展9.5實例：Pentium/Windows個人計算機上的內存管理湖南大學計算機與通信學院29.1存儲器的層次結構圖9.1一般的存儲器層次物理內存：由動態RAM組成。Cache存儲器：由靜態RAM構成，比DRAM快得多，但也昂貴的多。Cache是物理內存的部分副本。虛擬存儲器：空間比物理內存大得多邏輯空間。虛擬管理器通過在物理內存和一個存儲介質之間調度來達到訪問的目的。湖南大學計算機與通信學院3哈佛結構：計算機存儲系統的Cache層次中，每一級Cache包含兩個單獨的Cache存儲器，其中一個是指令Cache，一個是數據Cache。9.2Cache存儲器

大部分計算機在CPU和物理內存之間包含一個較小容量的Cache存儲器，而不是使用Cache存儲器構建計算機的整個存儲系統。目標是在合理的價格下減少處理器的內存訪問時間。湖南大學計算機與通信學院49.2.1相聯存儲器一般存儲器：接收一個地址，訪問該地址中的數據。相聯存儲器：并行搜索所有單元，標記那些與特定數據匹配的單元，然后連續讀出匹配的數據值。湖南大學計算機與通信學院5考慮一個由8個字單元組成的簡單的相聯存儲器，每個單元有16位，如圖9.2所示。除數據位外，每單元都有一個額外的標記位V。（數據有效位，為1說明這個單元數據有效，為0說明數據無效）圖9.2相聯存儲器的內部組織結構湖南大學計算機與通信學院6為了從相聯存儲器中讀出一個值，CPU必須給出兩個值，即要被匹配的數據值、以及哪些位需要檢查。第一個值是參數或數據，第二個值是屏蔽位或關鍵位

如果滿足如下的公式，則匹配就會發生湖南大學計算機與通信學院7屏蔽寄存器中值為1的每一位，單元中的值與數據寄存器中的值都相同單元的有效位被設置為1；例如(參考圖9.2)：屏蔽寄存器K1111000000000000數據寄存器D1010XXXXXXXXXXXX數據位M1010110100000111執行0000XXXXXXXXXXXX執行1111XXXXXXXXXXXX執行1111111111111111湖南大學計算機與通信學院8Vi始終為1，所以最終結果為：1111111111111111找到一個匹配因此該數據位M對應的匹配寄存器的一個單元設置為1湖南大學計算機與通信學院9將數據寫回相聯存儲器CPU把數據送到數據寄存器并發出寫信號。相聯存儲器檢查所有單元的有效位，并找到有效位為0的一個單元，如果找到，把數據存到這個單元，同時將有效位設為1。如果沒有找到，必須采用替換算法清除一個單元來保存數據。

常見的替換算法FIFOLRURANDOM湖南大學計算機與通信學院109.2.2相聯映象的Cache存儲器圖9.3相對簡單CPU的相聯Cache64K的8位內存湖南大學計算機與通信學院11圖9.3中：每一個單元中的前16位由內存地址構成，可以尋址到64K的地址空間。后8位描述的是存儲在該物理內存地址中的數據。屏蔽寄存器只需設置一次。在上圖中可以設成111111111111111100000000湖南大學計算機與通信學院12作用于數據行或數據塊的相聯存儲器存儲器在每個單元存儲4個字節的數據。（如圖9.4）同一個單元的4個數據具有相同的高位地址，即高14位相同。比圖9.3中的相聯存儲器采用了更多的位數（46位vs24位）。湖南大學計算機與通信學院13圖9.4相對簡單CPU中，行大小為4字節的相聯Cache湖南大學計算機與通信學院14優點：利用了訪問的局部性原理：當內存單元X中的指令被訪問時，下一條被執行的指令非常有可能就在內存單元X+1中。例如： 當訪問地址0單元的時候，整個塊（0，1，2，3）的值都被從物理內存讀入CPU。當CPU下次要執行在內存單元1、2、3中的指令時，他們已在cache中即能被訪問而不必從較慢的物理內存中讀取。湖南大學計算機與通信學院15

不僅指令具有訪問的局部性，數據同樣也具有訪問的局部性

如編譯器通常將一列數組元素安排到相鄰的內存單元中，以方便處理器順序訪問數據值。

湖南大學計算機與通信學院169.2.3直接映象的Cache存儲器一種利用標準的SRAM、廉價的Cache映射方案物理內存Cache深度為1k64kx8位xxxxxx11111111111111111111湖南大學計算機與通信學院17索引

Cache地址的低十位，用來選擇Cache

的一個特定單元標簽

原始地址中不是索引的那些高位。直接映象的Cache存儲器一個單元包括（圖9.5)： 標簽 數據 有效值湖南大學計算機與通信學院18圖9.5相對簡單CPU的直接映象Cache湖南大學計算機與通信學院19另外一種直接映像Cache存儲器圖9.6:相對簡單的CPU中，行大小為4字節的直接映像Cache湖南大學計算機與通信學院20直接映像的Cache存儲器

優點：

價格低

容量大

缺點：靈活性差如前所述，物理內存中 任何形式為xxxxxx11 11111111的地址都只能 映射到Cache中地址為 1111111111的單元中湖南大學計算機與通信學院21JUMP1000HJUMP0000HJUMP0000HJUMP1000H考慮下面的代碼：0000000000000000（0000H）:JUMP1000H0001000000000000（1000H）:JUMP0000H直接映象Cache地址0000000000湖南大學計算機與通信學院22

第一條指令被取出放入cache中。基于低10位地址位，它被映射到cache單元0000000000。標志域被設置為地址位中的6個高位，即000000。現在，它被執行，CPU在單元1000H中取指令，它的低10位也為000000，因此，它被取出并裝入cache中，并且設置標志值為000100，覆蓋以前的值。JUMP跳轉反過來執行到單元0000H，這樣，盡管其他cache單元全都可用，但這兩條指令仍會不斷的彼此覆蓋。湖南大學計算機與通信學院239.2.4組相聯映像的cache存儲器特點靈活性增強 減少由直接映像帶來的覆蓋數據的問題采用比較便宜的SRAMN路組相聯：每個單元能夠包含N個字節或字

直接映像的cache可以看作是一個一路 組相聯映像cache存儲器湖南大學計算機與通信學院24考察大小為1k的2路組相聯cache（如圖9.7）該cache有1k個數據入口，每個單元2個數據值，因此有512個單元用9個地址位選擇cache單元，剩下的7位說明標簽值計數值用來紀錄數據什么時候被訪問過了圖9.7相對簡單CPU的2路組相聯cache湖南大學計算機與通信學院25JUMP1000HJUMP0000HJUMP0000HJUMP1000H重新考慮下面的代碼：0000000000000000（0000H）:JUMP1000H0001000000000000（1000H）:JUMP0000H組相聯映象cache湖南大學計算機與通信學院26

用在9.2.3的代碼例子中，cache就不會覆蓋任一條指令。JUMP1000H這條指令將會被取出存入cache單元0的一路中。然后，指令0000H將會被取出放入同一單元的另一路中。從這可以看出，指令都從cache取出并被連續的執行。湖南大學計算機與通信學院27一種采用數據行的組相聯cache圖9.8相對簡單CPU中具有4字節數據行的2路組相聯cache湖南大學計算機與通信學院289.2.5在cache中替換數據問題的引出：計算機開始執行一個程序。它 從內存中取指令和數據，同時 將這些值載入cache。當cache為 空或很少被占用時，會工作的 很好。但是，最終計算機會要 將數據移入到已占用的cache單 元。此時，將哪個數據移出 cache，以及此數據如何在保存 到物理內存，這一問題就變得 至關重要湖南大學計算機與通信學院29替換策略：FIFO先進先出原則LRU近期最少使用原則隨機策略湖南大學計算機與通信學院301.FIFO先進先出策略按順序填充相聯存儲器，當cache

占滿時返回最頂單元，用新數據 替換原有數據只要一個寄存器就能實現

該寄存器保存下一個要被替換的 單元的指針性能好湖南大學計算機與通信學院312.LRU近期最少使用策略跟蹤單元的訪問順序，用新的數 據替換近期最少使用的數據每個cache單元需要一個計數器

最近訪問的數據，將相應的計數 器置為0；其余的計數器依次加1性能沒有FIFO好湖南大學計算機與通信學院32例：在一個4路組相聯cache單元中應用LRU策略TDCVTDCVTDCVTDCVCc21Bb11Aa01---01.Cache單元的當前狀態2.CPU訪問DTDCVTDCVTDCVTDCVCc31Bb21Aa11Dd01湖南大學計算機與通信學院333.CPU訪問ETDCVTDCVTDCVTDCVEe01Bb31Aa21Dd114.CPU訪問ATDCVTDCVTDCVTDCVEe11Bb31Aa01Dd21湖南大學計算機與通信學院343.RANDOM隨機策略隨機的選擇一個單元給新的數據 使用性能較好，與FIFO策略差不多湖南大學計算機與通信學院359.2.6寫數據到cache寫直達法

每次信息從CPU寫入cache單元 中時，也要寫回相應的物理內存 單元中

回寫法

寫入cache中的值并不總是被寫 回物理內存。僅在數據被移出

cache時寫回物理內存一次

湖南大學計算機與通信學院36處理寫失效問題按寫分配法

把單元裝入cache，然后使用寫 直達法或寫回法把數據寫到cache

不按寫分配法

直接更新物理內存中的值，而 不把值寫回cache

湖南大學計算機與通信學院379.2.7cache的性能評判性能的標準Cache命中率

要訪問的數據已在cache中Cache失效率

要訪問的數據不在cache中湖南大學計算機與通信學院38命中率：指由cache（而不是物理內存） 提供服務的訪存百分比

平均訪問時間：是cache訪問時間Tc和內 存訪問時間Tp的加權平均，權 值是hTm=hTc+(1-h)Tp湖南大學計算機與通信學院39表9.1hTm(單位ns)0600.1550.2500.3450.4400.5350.6300.7250.8200.915110Tc=10nsTp=60ns結論：增加命中率能夠減少平均訪問時間湖南大學計算機與通信學院409.3虛擬存儲器存儲管理單元 在物理內存和較慢的存儲設備間移動數據虛擬存儲器的主要實現方法：分頁和分段交換磁盤交換文件湖南大學計算機與通信學院419.3.1分頁

頁面：在分頁技術中，整個邏輯地址空間被劃分為連續的塊叫做頁面頁面的特點：每個頁尺寸相同頁面不可重疊，每個邏輯地址確切地 屬于某個頁面湖南大學計算機與通信學院42一個頁面或者包含程序指令或者包含數據，不能同時包含兩者4.可能導致內部碎片問題內部碎片：假設MMU實現的頁式存儲器中每個頁面大小為4K，一個4K+1大小的程序需要MMU分配兩個存儲器頁面，盡管它的第二個頁面只用了4K單元的一個單元，這就是所謂的內存碎片湖南大學計算機與通信學院43圖9.10相對簡單CPU一種可能的內存配置它具有64k的邏輯地址空間，16k的物理內存，頁面大小4k湖南大學計算機與通信學院44分頁系統必須解決的問題：何時將某頁移入內存？CPU如何在物理內存找到數據，尤其邏輯地址和物理地址不一至的情況下？當所有頁框都裝有頁面，而CPU需要訪問的數據不在這些頁面怎么辦？湖南大學計算機與通信學院45存儲管理單元處理上述所有問題完成邏輯地址到物理地址的轉換產生缺頁故障，將數據從頁面裝入到物理內存產生請求頁，把新的請求頁移入到物理內存湖南大學計算機與通信學院46圖9.11存儲器層次結構中的MMU配置湖南大學計算機與通信學院47

在處理器需要訪問數據，MMU將數據從邏輯地址裝入物理地址的整個處理過程中，CPU沒有訪問物理單元的任何信息 例：指令LDAC4324H如何理解？ 答案：把數據從邏輯地址4234H裝入累加器將邏輯單元4234H的數據裝入累加器，此數據實際存儲在物理單元3234H中系統更傾向解釋成1湖南大學計算機與通信學院48頁表的概念MMU用頁表來跟蹤哪一頁存儲在哪個幀中

頁表的組成（如圖9.12）：幀指示域(frame)有效位(valid)計數值（count,有些頁表不需要）臟位(dirty)湖南大學計算機與通信學院49

圖9.12（a）為頁表，（b）為對應的物理內存

相對簡單CPU的頁表，有16K的物理內存，頁面大小為4K。頁表包含了16個單元，每一單元對應邏輯地址空間的一個頁面，它包含一個2bit的域，表明了該邏輯頁存儲在哪一個頁框中每一單元還包含一個有效位

0頁，對應于邏輯地址0000H~1FFFH，存儲在1號頁框中，物理地址為1000H~1FFFH

湖南大學計算機與通信學院50MMU中邏輯地址到物理地址的轉換MMU將邏輯地址看作兩個部分 頁和偏移量例：考慮LDAC4234H，MMC如何將邏輯 地址4234H轉換成物理地址（如圖9.13）湖南大學計算機與通信學院51圖9.13用頁表將邏輯地址轉換成物理地址高4位邏輯地址表明頁號，剩下的12位為偏移量四個高位為0100

頁框號11表明頁被映射到頁框3此值與12位的偏移量拼接，生成物理地址11001000110100湖南大學計算機與通信學院52圖9.13所示的MMU并沒有很好的轉換地址

?

因為從頁表中讀頁框號會有一個延時，并且由于取出相鄰的指令，系統可能連續的成百上千次的讀這一相同的值

變換旁視緩沖器可以解決上述問題（圖9.14），其功能跟頁表一樣，可產生幀值，但它更快，這樣就提高了性能湖南大學計算機與通信學院53圖9.14使用TLB轉換邏輯地址到物理地址注意TLB沒有必要包含計數位或者臟位，因為這些信息仍然保存在頁表中。TLB中的每一個地址入口包含在頁表中，但反過來不成立

湖南大學計算機與通信學院54例：考慮一臺含有相對簡單CPU，相同內存配置的計算機。它必須取、翻譯和執行下列程序（如表9.8）0000H:LDAC4234H0003H:STAC4235H0006H:JUMP1000H1000-1063H:(100registerinstructions)1064H:JUMP2000H2000H-2031H:(50registerinstructions)2032H:JUMP0100H0100H-01C7H:(200registerinstructions)01C8H:JUMP3000H3000H-3063H:(100registerinstructions)3064H:JUMP0000H4234H:27H(datavalue)湖南大學計算機與通信學院55PageTableAdress0000H0003H0006H1000H-1064H2000H-2032H0100H-01C8H3000H-3064H0000HPageFVCDFVCDFVCDFVCDFVCDFVCDFVCDFVCD00110011001100110012001100110011012100211021202130-0--231003110312031303110011204110011011111112111311131-0--2100表9.8使用LRU替換算法的部分頁表和TLB值TLBPFVPFVPFVPFVPFVPFVPFVPFV0010010010010010010010014114114114114114113113110001211211211214210000231231231231湖南大學計算機與通信學院56PageTableAdress0000H0003H-0006H1000H-1064H2000H-2032H0100H-01C8H3000H-3064H0000HPageFVDFVDFVDFVDFVDFVDFVD0010010010010010--0-1101210210210210--0-231031031031030100104110111111111111111210表9.9使用FIFO替換算法的部分頁表和TLB值PFVPFVPFVPFVPFVPFVPFV00100100100100130130141141141141141141101100121121121121421000231231231231湖南大學計算機與通信學院579.3.1分段

分段：在分段技術中，程序被劃分為幾段，每段為一個自包含的單元分段的特點：每個段大小可以變化分段存在外部碎片問題湖南大學計算機與通信學院58外部碎片：內存駐留有3個段，另有8K自由空間。而這8K空間被劃分開了，于是不移動或撤除某個當前載入段的話，大小超過3K的段已無法裝入內存（如圖9.16）圖9.16由于分段引起的物理內存外部碎片湖南大學計算機與通信學院59分段機制中邏輯地址到物理地址的轉換

圖9.15分段機制中邏輯地址到物理地址的轉換邏輯地址被剖分為段號和偏移量

湖南大學計算機與通信學院60段號輸入到段表中，如果段已被裝入內存，輸出段的起始地址和段大小如果段不在物理內存中，就產生一個缺段，MMU裝入新段到內存中偏移量與段大小進行比較，如果前者大于后者，或者相等，說明所訪問單元不在段內，就產生一個錯誤如果偏移量有效，則與段地址的起始值相加，形成一個正確的物理內存地址

湖南大學計算機與通信學院61分段機制中的一個嚴重缺陷 在分頁機制中，頁號送到頁表（和TLB）以產生頁框號。該值和偏移量拼接構成物理地址。而在分段機制中，通過頁表或TLB產生的起始地址要與偏移量相加，此過程消耗的時間比拼接要多得多

湖南大學計算機與通信學院62帶分頁的分段分頁和分段兩種機制的結合體在內存中不必是一個連續整塊邏輯地址被劃分為三個部分段號2.頁號3.偏移量湖南大學計算機與通信學院63圖9.17