第6章

層次結構存儲系統(tǒng)

存儲器概述

主存與CPU的連接及其讀寫操作

磁盤存儲器

高速緩沖存儲器(cache)

虛擬存儲器

IA-32/Linux中的地址轉換

層次結構存儲系統(tǒng)主要教學目標理解CPU執(zhí)行指令過程中為何要訪存理解訪存操作的大致過程及涉及到的部件了解層次化存儲器系統(tǒng)的由來及構成了解CPU與主存儲器之間的連接及讀寫操作掌握Cache機制并理解其對程序性能的影響理解程序局部性的重要性并能開發(fā)局部性好的程序了解虛擬存儲管理的基本概念和實現(xiàn)原理理解訪存操作完整過程以及所涉及到的部件之間的關聯(lián)地址轉換（查TLB、查頁表）、訪問Cache、訪問主存、讀寫磁盤理解訪存過程中硬件和操作系統(tǒng)之間的協(xié)調(diào)關系層次結構存儲系統(tǒng)分以下六個部分介紹第一講：存儲器概述第二講：主存與CPU的連接及其讀寫操作主存模塊的連接和讀寫操作“裝入”指令和“存儲”指令操作過程第三講：磁盤存儲器第四講：高速緩沖存儲器(cache)程序訪問的局部性、cache的基本工作原理cache行和主存塊之間的映射方式cache和程序性能第五講：虛擬存儲器虛擬地址空間、虛擬存儲器的實現(xiàn)第六講：IA-32/Linux中的地址轉換邏輯地址到線性地址的轉換線性地址到物理地址的轉換回顧：程序及指令的執(zhí)行過程在內(nèi)存存放的指令實際上是機器代碼（0/1序列）08048394<add>:18048394: 55 push %ebp28048395: 89e5 mov %esp,%ebp38048397: 8b450c mov 0xc(%ebp),%eax4804839a: 034508 add 0x8(%ebp),%eax5804839d: 5d pop %ebp6804839e: c3 ret對于add函數(shù)的執(zhí)行，以下情況下都需要訪存：每條指令都需從主存單元取到CPU執(zhí)行PUSH指令需把寄存器內(nèi)容壓入棧中POP指令則相反第3條mov指令需要從主存中取數(shù)后送到寄存器第4條add指令需要從主存取操作數(shù)到ALU中進行運算ret指令需要從棧中取出返回地址，以能正確回到調(diào)用程序執(zhí)行棧是主存中的一個區(qū)域！訪存是指令執(zhí)行過程中一個非常重要的環(huán)節(jié)！取指、取數(shù)、存數(shù)取指存數(shù)取數(shù)取數(shù)取數(shù)取數(shù)基本術語記憶單元（存儲基元/存儲元/位元）（Cell）具有兩種穩(wěn)態(tài)的能夠表示二進制數(shù)碼0和1的物理器件存儲單元/編址單位（AddressingUnit）具有相同地址的位構成一個存儲單元，也稱為一個編址單位存儲體/存儲矩陣/存儲陣列（Bank）所有存儲單元構成一個存儲陣列編址方式（AddressingMode）字節(jié)編址、按字編址存儲器地址寄存器（MemoryAddressRegister-MAR）用于存放主存單元地址的寄存器存儲器數(shù)據(jù)寄存器（MemoryDataRegister-MDR(或MBR)）用于存放主存單元中的數(shù)據(jù)的寄存器存儲器分類（1）按工作性質(zhì)/存取方式分類隨機存取存儲器RandomAccessMemory(RAM)

每個單元讀寫時間一樣，且與各單元所在位置無關。如：內(nèi)存。（注：原意主要強調(diào)地址譯碼時間相同。現(xiàn)在的DRAM芯片采用行緩沖，因而可能因為位置不同而使訪問時間有所差別。）順序存取存儲器SequentialAccessMemory(SAM)數(shù)據(jù)按順序從存儲載體的始端讀出或?qū)懭耄蚨嫒r間的長短與信息所在位置有關。例如：磁帶。直接存取存儲器DirectAccessMemory(DAM)直接定位到讀寫數(shù)據(jù)塊，在讀寫數(shù)據(jù)塊時按順序進行。如磁盤。相聯(lián)存儲器AssociateMemory（AM）

ContentAddressedMemory(CAM)按內(nèi)容檢索到存儲位置進行讀寫。例如：快表。依據(jù)不同的特性有多種分類方法存儲器分類（2）按存儲介質(zhì)分類半導體存儲器：雙極型，靜態(tài)MOS型，動態(tài)MOS型磁表面存儲器：磁盤（Disk）、磁帶（Tape）光存儲器：CD，CD-ROM，DVD（3）按信息的可更改性分類讀寫存儲器（Read/WriteMemory)：可讀可寫只讀存儲器（ReadOnlyMemory)：只能讀不能寫（4）按斷電后信息的可保存性分類非易失（不揮發(fā)）性存儲器(NonvolatileMemory)

信息可一直保留，不需電源維持。（如：ROM、磁表面存儲器、光存儲器等）易失（揮發(fā)）性存儲器(VolatileMemory)

電源關閉時信息自動丟失。（如：RAM、Cache等）存儲器分類（5）按功能/容量/速度/所在位置分類寄存器(Register)封裝在CPU內(nèi)，用于存放當前正在執(zhí)行的指令和使用的數(shù)據(jù)用觸發(fā)器實現(xiàn)，速度快，容量小（幾~幾十個）高速緩存(Cache)位于CPU內(nèi)部或附近，用來存放當前要執(zhí)行的局部程序段和數(shù)據(jù)用SRAM實現(xiàn)，速度可與CPU匹配，容量小（幾MB）內(nèi)存儲器MM（主存儲器Main(Primary)Memory）位于CPU之外，用來存放已被啟動的程序及所用的數(shù)據(jù)用DRAM實現(xiàn)，速度較快，容量較大（幾GB）外存儲器AM(輔助存儲器Auxiliary/SecondaryStorage)位于主機之外，用來存放暫不運行的程序、數(shù)據(jù)或存檔文件用磁表面或光存儲器實現(xiàn)，容量大而速度慢內(nèi)存與外存的關系及比較內(nèi)存儲器（簡稱內(nèi)存或主存）存取速度快成本高、容量相對較小直接與CPU連接，CPU對內(nèi)存中可直接進行讀、寫操作屬于易失性存儲器(volatile)，用于臨時存放正在運行的程序和數(shù)據(jù)內(nèi)存儲器外存儲器CPU指令1指令2指令k指令n程序數(shù)據(jù)1數(shù)據(jù)2數(shù)據(jù)m數(shù)據(jù)①程序和數(shù)據(jù)從外存成批傳送到內(nèi)存②CPU從內(nèi)存中逐條讀取指令及相關數(shù)據(jù)④將指令處理結果送回內(nèi)存保存⑤將處理結果成批傳送到外存以長久保存③逐條執(zhí)行指令，按指令要求完成對數(shù)據(jù)的運算和處理

外存儲器（簡稱外存或輔存）存取速度慢成本低、容量很大不與CPU直接連接，先傳送到內(nèi)存，然后才能被CPU使用。屬于非易失性存儲器，用于長久存放系統(tǒng)中幾乎所有的信息地址寄存器地址譯碼器讀寫控制電路控制線讀/寫控制信號記憶單元數(shù)據(jù)線讀/寫的數(shù)據(jù)(64位)主存地址地址線(36位)····· 0110100110101010存儲內(nèi)容00001000000001000011001001111011111·······存儲單元地址MDRMARCPUMM主存的結構問題：主存中存放的是什么信息？CPU何時會訪問主存？指令及其數(shù)據(jù)！CPU執(zhí)行指令時需要取指令、取數(shù)據(jù)、存數(shù)據(jù)！問題：地址譯碼器的輸入是什么？輸出是什么？可尋址范圍多少？輸入是地址，輸出是地址驅(qū)動信號（只有一根地址驅(qū)動線被選中）。可尋址范圍為0~236-1，即主存地址空間為64GB（按字節(jié)編址時）。主存地址空間大小不等于主存容量（實際安裝的主存大小）！若是字節(jié)編址，則每次最多可讀/寫8個單元，給出的是首(最小)地址.性能指標：按字節(jié)連續(xù)編址，每個存儲單元為1個字節(jié)（8個二進位）存儲容量：所包含的存儲單元的總數(shù)（單位：MB或GB）存取時間TA：從CPU送出內(nèi)存單元的地址碼開始，到主存讀出數(shù)據(jù)并送到CPU（或者是把CPU數(shù)據(jù)寫入主存）所需要的時間（單位：ns，1ns=10-9s），分讀取時間和寫入時間存儲周期TMC：連讀兩次訪問存儲器所需的最小時間間隔，它應等于存取時間加上下一次存取開始前所要求的附加時間，因此，TMC比TA大（因為存儲器由于讀出放大器、驅(qū)動電路等都有一段穩(wěn)定恢復時間，所以讀出后不能立即進行下一次訪問。）（就像一趟火車運行時間和發(fā)車周期是兩個不同概念一樣。）主存的主要性能指標時間、存儲容量（或帶寬）的單位HPCA2001Appendix1:NotationsandConventionsforNumbersQuintillionEexaQuadrillionPpetaTrillionTteraBillionGgigaMillionMmegaThousandK(ork)kiloOnequintillionthaattaOnequadrillionthffemtoOnetrillionthppicoOnebillionthnnanoOnemillionthμmicroOnethousandthmmillNumericValueMeaningAbbreviationPrefixNotationsandConventionsforNumbers10-310-610-910-1210-1510-18103or210106or220109or2301012or2401015or2501018or260內(nèi)存儲器的分類及應用內(nèi)存由半導體存儲器芯片組成，芯片有多種類型：半導體存儲器只讀存儲器(ROM)隨機存取存儲器(RAM)靜態(tài)存儲器SRAM動態(tài)存儲器DRAM

不可在線改寫內(nèi)容的ROM閃存（FlashROM）（用作Cache）（用作主存儲器）每個存儲單元(cell)由6個晶體管組成只要加上電源，信息就能一直保持對電器干擾相對不很敏感比DRAM更快，也更貴

每個存儲單元由1個電容和1個晶體管組成每隔一段時間必須刷新一次對電器干擾比較敏感比SRAM慢，但便宜（用作BIOS）六管靜態(tài)MOS管電路（不作要求）6管靜態(tài)NMOS記憶單元讀出時：

-置2個位線為高電平

-

置字線為1-存儲單元狀態(tài)不同，位線的輸出不同寫入時：

-位線上是被寫入的二進位信息0或1-置字線為1-存儲單元(觸發(fā)器)按位線的狀態(tài)設置成0或1信息存儲原理：看作帶時鐘的RS觸發(fā)器存儲單元字線位線D位線DSRAM中數(shù)據(jù)保存在一對正負反饋門電路中，只要供電，數(shù)據(jù)就一直保持，不是破環(huán)性讀出，也無需重寫，即無需刷新！保持時：

-字線為0（低電平）動態(tài)單管記憶單元電路（不作要求）讀寫原理：字線上加高電平，使T管導通。寫“0”時，數(shù)據(jù)線加低電平，使CS上電荷對數(shù)據(jù)線放電；寫“1”時，數(shù)據(jù)線加高電平，使數(shù)據(jù)線對CS充電；讀出時，數(shù)據(jù)線上有一讀出電壓。它與CS上電荷量成正比。字線位線(數(shù)據(jù)線)CsT

優(yōu)點：電路元件少，功耗小，集成度高，用于構建主存儲器缺點：速度慢、是破壞性讀出（需讀后再生）、需定時刷新刷新：DRAM的一個重要特點是，數(shù)據(jù)以電荷的形式保存在電容中，電容的放電使得電荷通常只能維持幾十個毫秒左右，相當于1M個時鐘周期左右，因此要定期進行刷新（讀出后重新寫回），按行進行（所有芯片中的同一行一起進行），刷新操作所需時間通常只占1%~2%左右。半導體RAM的組織記憶單元的組織：位元字線W位線S0位線S1

讀寫控制Din

DoutR/W

位元選擇線(字線)數(shù)據(jù)線(位線)讀寫控制Din

DoutR/W存儲體(MemoryBank)：由記憶單元(位元)構成的存儲陣列記憶單元(Cell)存儲器芯片(Chip)內(nèi)存條（存儲器模塊）SRAM DRAM字片式存儲體陣列組織（不作要求）X向譯碼器一維地址譯碼系統(tǒng)地址驅(qū)動線一般SRAM為字片式芯片，只在x向上譯碼，同時讀出字線上所有位！位片式存儲體陣列組織（不作要求）位片式在字方向和位方向擴充，需要有片選信號DRAM芯片都是位片式16M位=4Mbx4=2048x2048x4=211x211x4(1)地址線：11根線分時復用，由RAS和CAS提供控制時序。(2)需4個位平面，對相同行、列交叉點的4位一起讀/寫(3)內(nèi)部結構框圖舉例：典型的16M位DRAM（4Mx4）問題：為什么每出現(xiàn)新一代DRAM芯片，容量至少提高到4倍？行地址和列地址分時復用,每出現(xiàn)新一代DRAM芯片，至少要增加一根地址線。每加一根地址線，則行地址和列地址各增加一位，所以行數(shù)和列數(shù)各增加一倍。因而容量至少提高到4倍。SKIP、舉例：典型的16M位DRAM（4Mx4）四個位平面各片同時按“行”進行刷新！二選一BACK刷新計數(shù)器的位數(shù)是幾位？為何刷新計數(shù)值不送列譯碼器？層次結構存儲系統(tǒng)分以下六個部分介紹第一講：存儲器概述第二講：主存與CPU的連接及其讀寫操作主存模塊的連接和讀寫操作“裝入”指令和“存儲”指令操作過程第三講：磁盤存儲器第四講：高速緩沖存儲器(cache)程序訪問的局部性、cache的基本工作原理cache行和主存塊之間的映射方式cache和程序性能第五講：虛擬存儲器虛擬地址空間、虛擬存儲器的實現(xiàn)第六講：IA-32/Linux中的地址轉換邏輯地址到線性地址的轉換線性地址到物理地址的轉換主存模塊的連接和讀寫操作主存與CPU的連接總線中有哪三種類型傳輸線？數(shù)據(jù)線、地址線、控制線存儲器總線前端總線SPARCstation20MemoryControllerMemoryBusSIMMSlot0SIMMSlot1SIMMSlot2SIMMSlot3SIMMSlot4SIMMSlot5SIMMSlot6SIMMSlot7DRAMSIMMDRAMDRAMDRAMDRAMDRAMDRAMDRAMDRAM舉例：SPARCstation20’sMemoryModule每個內(nèi)存條最多能同時讀出128位數(shù)據(jù)存儲器總線的總線寬度為128位每次訪存操作總是在某一個內(nèi)存條內(nèi)進行！總線寬度是指總線中數(shù)據(jù)線的條數(shù)PC機主存儲器的物理結構由若干內(nèi)存條組成內(nèi)存條的組成：把若干片DRAM芯片焊裝在一小條印制電路板上制成內(nèi)存條必須插在主板上的內(nèi)存條插槽中才能使用

目前流行的是DDR2、DDR3內(nèi)存條：采用雙列直插式，其觸點分布在內(nèi)存條的兩面DDR條有184個引腳，DDR2有240個引腳PC機主板中一般都配備有2個或4個DIMM插槽舉例：SPARCstation20’s內(nèi)存條(模塊)onememorymodule（內(nèi)存條）Smallest:4MB=16x2MbDRAMchips,8KBofPageSRAMBiggest:64MB=32x16Mbchips,16KBofPageSRAM512rows512colsDRAMChip15bits<127:120>8bits512×8SRAM256Kx8=2MbDRAM

Chip0bits<7:0>512×8SRAM256Kx8=2MbMemoryBus<127:0>Onepage行緩沖每個芯片有512行x512列，并有8個位平面每次讀/寫各芯片同行同列的8位，共16x8=128位當CPU訪問一塊連續(xù)區(qū)域（即行地址相同）時，可直接從行緩沖讀取，它用SRAM實現(xiàn)，速度極快！問題：行緩沖數(shù)據(jù)的地址有何特點？一定在同一行中！存儲控制器(行地址i,列地址j)DRAM7DRAM003178151623243263394047485556bits0-7bits8-15bits16-23bits24-31bits32-39bits40-47bits48-55bits56-63最多讀64位03178151623243263394047485556主存儲器地址A處的64-bit數(shù)據(jù)地址A4096行舉例：128MB的DRAM存儲器:行、列地址為(i,j)的8個單元由8片DRAM芯片構成每片16Mx8bits行地址、列地址各12位每行共4096列(8位/列)選中某一行并讀出之后再由列地址選擇其中的一列(8個二進位)送出主存地址和片內(nèi)地址有何關系？主存地址27位，片內(nèi)地址24位，與高24位主存地址相同。主存低3位地址的作用是什么？確定8個字節(jié)中的哪個，即用來選片。不連續(xù)，交叉編址，可同時讀寫所有芯片。芯片內(nèi)地址是否連續(xù)？從該存儲器結構可理解為什么規(guī)定數(shù)據(jù)對齊存放。例如，一個32位int型數(shù)據(jù)若存放在第8、9、10、11這4個單元，則需要訪問幾次內(nèi)存？若存放在6、7、8、9這4個單元，則需要訪問幾次內(nèi)存？分別訪問1次和2次DRAM芯片的規(guī)格若一個2n×b位DRAM芯片的存儲陣列是r行×c列，則該芯片容量為2n×b位且2n=r×c。如：16K×8位DRAM，則r=c=128。芯片內(nèi)的地址位數(shù)為n，其中行地址位數(shù)為log2r，列地址位數(shù)為log2c。如：16K×8位DRAM，則n=14，行、列地址各占7位。n位地址中高位部分為行地址，低位部分為列地址為提高DRAM芯片的性價比，通常設置的r和c滿足r≤c且|r-c|最小。例如，對于8K×8位DRAM芯片，其存儲陣列設置為26行×27列，因此行地址和列地址的位數(shù)分別為6位和7位，13位芯片內(nèi)地址A12A11…A1A0中，行地址為A12A11…A7，列地址為A6…A1A0。因按行刷新，為盡量減少刷新次數(shù)，故行數(shù)越少越好，但是，為了減少地址引腳，應盡量使行、列地址位數(shù)一致主存模塊的連接和讀寫操作DRAM芯片內(nèi)部結構示意圖圖中芯片容量為16×8位，存儲陣列為4行×4列，地址引腳采用復用方式，因而僅需2根地址引腳，每個超元（supercell）有8位，需8根數(shù)據(jù)引腳，有一個內(nèi)部的行緩沖（rowbuffer），通常用SRAM元件實現(xiàn)。主存模塊的連接和讀寫操作DRAM芯片讀寫原理示意圖

首先，存儲控制器將行地址“2”送行譯碼器，選中第“2”行，此時，整個一行數(shù)據(jù)被送行緩沖。然后，存儲控制器將列地址“1”送列譯碼器，選中第“1”列，此時，將行緩沖第“1”列的8位數(shù)據(jù)supercell(2,1)讀到數(shù)據(jù)線，并繼續(xù)送往CPU。

指令“movl8(%ebp),%eax”操作過程CPU先把地址A和“主存讀”命令送到總線主存經(jīng)過一個取數(shù)時間，把數(shù)據(jù)x送到總線CPU等待一個確定的時間后，從總線取x到EAX由8(%ebp)得到地址A的過程較復雜，涉及MMU、TLB、頁表等重要概念！指令“movl%eax,8(%ebp)”操作過程CPU先把地址A和“主存寫”命令送總線CPU把數(shù)據(jù)y送總線（若不復用數(shù)據(jù)和地址信號線，可同時送地址和數(shù)據(jù)）等待一個寫入時間后，主存將y存入A中由8(%ebp)得到地址A的過程較復雜，涉及MMU、TLB、頁表等重要概念！層次結構存儲系統(tǒng)分以下六個部分介紹第一講：存儲器概述第二講：主存與CPU的連接及其讀寫操作主存模塊的連接和讀寫操作“裝入”指令和“存儲”指令操作過程第三講：磁盤存儲器

第四講：高速緩沖存儲器(cache)程序訪問的局部性、cache的基本工作原理cache行和主存塊之間的映射方式cache和程序性能第五講：虛擬存儲器虛擬地址空間、虛擬存儲器的實現(xiàn)第六講：IA-32/Linux中的地址轉換邏輯地址到線性地址的轉換線性地址到物理地址的轉換PC機中的外存儲器硬盤存儲器軟盤驅(qū)動器CD-ROM驅(qū)動器PC中的外存儲器磁盤存儲器的信息存儲原理磁頭：磁-電和電-磁轉換，用于讀/寫信息“0”“1”盤片旋轉方向磁盤片線圈不同的磁化狀態(tài)被記錄在磁盤表面寫1：線圈通以正向電流，使呈N-S狀態(tài)寫0：線圈通以反向電流，使呈S-N狀態(tài)讀時：磁頭固定不動，載體運動。因為載體上小的磁化單元外部的磁力線通過磁頭鐵芯形成閉合回路，在鐵芯線圈兩端得到感應電壓。根據(jù)感應電壓的不同的極性，可確定讀出為0或1。磁表面信息讀出過程扇區(qū)磁道磁盤的磁道和扇區(qū)磁盤表面被分為許多同心圓，每個同心圓稱為一個磁道。每個磁道都有一個編號，最外面的是0磁道

每個磁道被劃分為若干段（段又叫扇區(qū)），每個扇區(qū)的存儲容量為512字節(jié)。每個扇區(qū)都有一個編號近三十年來，扇區(qū)大小一直是512字節(jié)。但最近幾年正遷移到更大、更高效的4096字節(jié)扇區(qū)，通常稱為4K扇區(qū)。在此例中，每個磁道包含30個固定長度的扇段，每個扇段有600個字節(jié)(17+7+41+515+20=600)。磁盤磁道的格式磁盤格式化操作指在盤面上劃分磁道和扇區(qū)，并在扇區(qū)中填寫ID域信息的過程一個磁道的開始一個扇段的開始磁盤驅(qū)動器移動臂控制電路硬盤片磁頭接口插座柱面磁道主軸磁道號就是柱面號、磁頭號就是盤面號每片有兩個面，每面一個磁頭平均存取時間磁盤信息以扇區(qū)為單位進行讀寫，平均存取時間為：

T=平均尋道時間+平均旋轉等待時間+數(shù)據(jù)傳輸時間（忽略不計）平均尋道時間——磁頭尋找到指定磁道所需平均時間(約5ms)平均旋轉等待時間——指定扇區(qū)旋轉到磁頭下方所需平均時間(約4～6ms)(轉速：4200/5400/7200/10000rpm)數(shù)據(jù)傳輸時間——(大約0.01ms/扇區(qū))磁頭磁道旋轉軸碟片硬盤的操作流程如下：

所有磁頭同步尋道（由柱面號控制）→選擇磁頭（由磁頭號控制）→被選中磁頭等待扇區(qū)到達磁頭下方（由扇區(qū)號控制）→讀寫該扇區(qū)中數(shù)據(jù)磁盤響應時間計算舉例假定每個扇區(qū)512字節(jié)，磁盤轉速為5400RPM，聲稱尋道時間（最大尋道時間的一半）為12ms,數(shù)據(jù)傳輸率為4MB/s,磁盤控制器開銷為1ms,不考慮排隊時間，則磁盤響應時間為多少？磁盤轉速非常重要！

DiskResponseTime=QueuingDelay

+ControllerTime+Seektime+RotationalLatency+Transfertime

=0+1ms+12ms+0.5/5400RPM+0.5KB/4MB/s=0

+1ms+12ms+0.5/90RPS+0.125/1024s=1ms+12ms+5.5ms+0.1ms=18.6ms如果實際的尋道時間只有1/3的話，則總時間變?yōu)?0.6ms，這樣旋轉等待時間就占了近50%！12/3+5.5+0.1+1=10.6ms為什么實際的尋道時間可能只有1/3？訪問局部性使得每次磁盤訪問大多在局部幾個磁道，實際尋道時間變少！能否算出每道有多少扇區(qū)？4MBx60/512Bx5400≈87個扇區(qū)硬盤存儲器的組成硬盤存儲器的基本組成磁記錄介質(zhì)：用來保存信息磁盤驅(qū)動器：包括讀寫電路、讀\寫轉換開關、磁頭與磁頭定位伺服系統(tǒng)等磁盤控制器：包括控制邏輯、時序電路、“并→串”轉換和“串→并”轉換電路等。（用于連接主機與盤驅(qū)動器）磁盤驅(qū)動器磁盤控制器硬盤存儲器的簡化邏輯結構還包括數(shù)據(jù)緩存器、控制狀態(tài)寄存器等。硬盤驅(qū)動器的邏輯結構與磁盤控制器之間的接口如何定位磁盤上的數(shù)據(jù)（磁盤地址格式）？柱面(磁道)號、磁頭（盤面）號、扇區(qū)號操作過程？尋道、旋轉、讀/寫磁盤存儲器的連接磁盤控制器連接在I/O總線上，I/O總線與其他總線（系統(tǒng)總線、存儲器總線）之間用橋接器連接磁盤的最小讀寫單位是扇區(qū)，因此，磁盤按成批數(shù)據(jù)交換方式進行讀寫，采用直接存儲器存取（DMA，DirectMemoryAccess）方式進行數(shù)據(jù)輸入輸出，需用專門的DMA接口來控制外設與主存間直接數(shù)據(jù)交換，數(shù)據(jù)不通過CPU。通常把專門用來控制總線進行DMA傳送的接口硬件稱為DMA控制器讀一個磁盤扇區(qū)–第一步MainmemoryALURegisterfileCPUchipDiskcontrollerGraphicsadapterUSBcontrollermousekeyboardMonitorDiskI/ObusBusinterfaceCPU對磁盤控制器初始化：讀命令磁盤邏輯塊號主存起始地址然后啟動磁盤驅(qū)動器工作讀一個磁盤扇區(qū)–第二步MainmemoryALURegisterfileCPUchipDiskcontrollerGraphicsadapterUSBcontrollerMouseKeyboardMonitorDiskI/ObusBusinterface磁盤控制器讀相應的扇區(qū)，并按DMA方式把數(shù)據(jù)送主存讀一個磁盤扇區(qū)–第三步MainmemoryALURegisterfileCPUchipDiskcontrollerGraphicsadapterUSBcontrollerMouseKeyboardMonitorDiskI/ObusBusinterface當DMA傳送結束，磁盤控制器向CPU發(fā)出“DMA結束中斷請求”，要求CPU進行相應的后處理。固態(tài)硬盤（SSD）固態(tài)硬盤（SolidStateDisk，簡稱SSD）也被稱為電子硬盤。它并不是一種磁表面存儲器，而是一種使用NAND閃存組成的外部存儲系統(tǒng)，與U盤并沒有本質(zhì)差別，只是容量更大，存取性能更好。它用閃存顆粒代替了磁盤作為存儲介質(zhì)，利用閃存的特點，以區(qū)塊寫入和抹除的方式進行數(shù)據(jù)的讀取和寫入。寫操作比讀操作慢得多。電信號的控制使得固態(tài)硬盤的內(nèi)部傳輸速率遠遠高于常規(guī)硬盤。其接口規(guī)范和定義、功能及使用方法與傳統(tǒng)硬盤完全相同，在產(chǎn)品外形和尺寸上也與普通硬盤一致。目前接口標準上使用USB、SATA和IDE，因此SSD是通過標準磁盤接口與I/O總線互連的。在SSD中有一個閃存翻譯層，它將來自CPU的邏輯磁盤塊讀寫請求翻譯成對底層SSD物理設備的讀寫控制信號。因此，這個閃存翻譯層相當于磁盤控制器。閃存的擦寫次數(shù)有限，所以頻繁擦寫會降低其寫入使用壽命。層次結構存儲系統(tǒng)分以下六個部分介紹第一講：存儲器概述第二講：主存與CPU的連接及其讀寫操作主存模塊的連接和讀寫操作“裝入”指令和“存儲”指令操作過程第三講：磁盤存儲器第四講：高速緩沖存儲器(cache)

程序訪問的局部性、cache的基本工作原理cache行和主存塊之間的映射方式cache和程序性能第五講：虛擬存儲器虛擬地址空間、虛擬存儲器的實現(xiàn)第六講：IA-32/Linux中的地址轉換邏輯地址到線性地址的轉換線性地址到物理地址的轉換希望的理想存儲器到目前為止，已經(jīng)了解到有以下幾種存儲器：寄存器，SRAM，DRAM，硬盤單獨用某一種存儲器，都不能滿足我們的需要！采用分層存儲結構來構建計算機的存儲體系！1ns2ns10ns10ms<1KB1MB1GB1000GB100GB1ns問題：你認為哪一種最適合做計算機的存儲器呢？存儲器的層次結構cache主存(RAM和ROM)外存儲器（硬盤、光盤）后備存儲器（磁帶庫、光盤庫）內(nèi)部存儲器外部存儲器寄存器典型容量<1KB1MB256MB~1GB40GB~200GB10TB~100TB典型存取時間1ns(0.5~1cycles)2ns(1~3cycles)10ns(10~100cycles)10ms(107~108cycles)10s(脫機)列出的時間和容量會隨時間變化，但數(shù)量級相對關系不變。層次化存儲器結構（MemoryHierarchy）時間局部性（TemporalLocality）含義：剛被訪問過的單元很可能不久又被訪問做法：讓最近被訪問過的信息保留在靠近CPU的存儲器中空間局部性（SpatialLocality）含義：剛被訪問過的單元的鄰近單元很可能不久被訪問做法：將剛被訪問過的單元的鄰近單元調(diào)到靠近CPU的存儲器中Lower

LevelMemoryUpperLevelMemoryToCPUFromCPUBlockXBlockY數(shù)據(jù)總是在相鄰兩層之間復制傳送UpperLevel:上層更靠CPULowerLevel:下層更遠離CPUBlock:最小傳送單位是定長塊，互為副本問題：為什么這種層次化結構是有效的？相當于工廠中設置了多級倉庫！程序訪問局部化特點！例如，寫論文時圖書館借參考書：欲借書附近的書也是欲借書！加快訪存速度措施之三：引入Cache大量典型程序的運行情況分析結果表明在較短時間間隔內(nèi)，程序產(chǎn)生的地址往往集中在一個很小范圍內(nèi)這種現(xiàn)象稱為程序訪問的局部性：空間局部性、時間局部性程序具有訪問局部性特征的原因指令：指令按序存放，地址連續(xù)，循環(huán)程序段或子程序段重復執(zhí)行數(shù)據(jù)：連續(xù)存放，數(shù)組元素重復、按序訪問為什么引入Cache會加快訪存速度？在CPU和主存之間設置一個快速小容量的存儲器，其中總是存放最活躍（被頻繁訪問）的程序和數(shù)據(jù)，由于程序訪問的局部性特征，大多數(shù)情況下，CPU能直接從這個高速緩存中取得指令和數(shù)據(jù)，而不必訪問主存。這個高速緩存就是位于主存和CPU之間的Cache！程序的局部性原理舉例1sum=0;for(i=0;i<n;i++) sum+=a[i];*v=sum;每條指令4個字節(jié)；每個數(shù)組元素4字節(jié)指令和數(shù)組元素在內(nèi)存中均連續(xù)存放sum,ap,i,t均為通用寄存器；A，V為內(nèi)存地址I0: sum<--0I1: ap<--AA是數(shù)組a的起始地址I2: i<--0I3: if(i>=n)gotodoneI4: loop: t<--(ap)數(shù)組元素a[i]的值I5: sum<--sum+t

累計在sum中I6: ap<--ap+4

計算下個數(shù)組元素地址I7: i<--i+1

I8: if(i<n)gotoloopI9: done: V<--sum

累計結果保存至地址vI1I2I3I4I5I60x1000x1040x1080x10C0x1100x114a[0]a[1]a[2]a[3]a[4]a[5]0x4000x4040x4080x40C0x4100x414?

?

?0x7A4?

?

?主存的布局:I00x0FC指令數(shù)據(jù)AV高級語言源程序?qū)膮R編語言程序程序的局部性原理舉例1sum=0;for(i=0;i<n;i++) sum+=a[i];*v=sum;問題：指令和數(shù)據(jù)的時間局部性和空間局部性各自體現(xiàn)在哪里？指令：0x0FC（I0）…→0x108（I3）→0x10C（I4）…→0x11C（I8）→0x120（I9）數(shù)據(jù)：只有數(shù)組在主存中：0x400→0x404→0x408→0x40C→……→0x7A4I1I2I3I4I5I60x1000x1040x1080x10C0x1100x114a[0]a[1]a[2]a[3]a[4]a[5]0x4000x4040x4080x40C0x4100x414?

?

?0x7A4?

?

?主存的布局:I00x0FC指令數(shù)據(jù)AV若n足夠大，則在一段時間內(nèi)一直在局部區(qū)域內(nèi)執(zhí)行指令，故循環(huán)內(nèi)指令的時間局部性好；按順序執(zhí)行，故程序空間局部性好！數(shù)組元素按順序存放，按順序訪問，故空間局部性好；每個數(shù)組元素都只被訪問1次，故沒有時間局部性。循環(huán)n次程序的局部性原理舉例2

以下哪個對數(shù)組a引用的空間局部性更好？時間局部性呢？變量sum的空間局部性和時間局部性如何？對于指令來說，for循環(huán)體的空間局部性和時間局部性如何？數(shù)組在存儲器中按行優(yōu)先順序存放程序段B:intsumarraycols(inta[M][N]){inti,j,sum=0;for(j=0;j<N,j++) for(i=0;i<M,i++)sum+=a[i][j];returnsum;}程序段A:intsumarrayrows(inta[M][N]){inti,j,sum=0;for(i=0;i<M,i++) for(j=0;j<N,j++)sum+=a[i][j];returnsum;}M=N=2048時主存的布局:0x1000x17C0x1800x1840x4000x4040xc000xc040x0FC指令數(shù)據(jù)asumI34I35a[0][0]a[0][1]?

?

?a[0][2047]a[1][0]a[1][1]?

?

??

?

?I1I2I33?

?

?for循環(huán)體程序的局部性原理舉例2程序段A的時間局部性和空間局部性分析（1）數(shù)組a：訪問順序為a[0][0],a[0][1],……,a[0][2047];a[1][0],a[1][1],……,a[1][2047];

……，與存放順序一致，故空間局部性好！因為每個a[i][j]只被訪問一次，故時間局部性差！（2）變量sum：單個變量不考慮空間局部性；每次循環(huán)都要訪問sum，所以其時間局部性較好！（3）for循環(huán)體：循環(huán)體內(nèi)指令按序連續(xù)存放，所以空間局部性好！循環(huán)體被連續(xù)重復執(zhí)行2048x2048次，所以時間局部性好！0x1000x17C0x1800x1840x4000x4040xc000xc040x0FC指令數(shù)據(jù)asumI34I35a[0][0]a[0][1]?

?

?a[0][2047]a[1][0]a[1][1]?

?

??

?

?I1I2I33?

?

?for循環(huán)體實際上優(yōu)化的編譯器使循環(huán)中的sum分配在寄存器中，最后才寫回存儲器！程序的局部性原理舉例2程序段B的時間局部性和空間局部性分析（1）數(shù)組a：訪問順序為a[0][0],a[1][0],……,a[2047][0];a[0][1],a[1][1],……,a[2047][1];……，與存放順序不一致，每次跳過2048個單元，若交換單位小于2KB，則沒有空間局部性！（時間局部性差，同程序A）（2）變量sum：（同程序A）（3）for循環(huán)體：（同程序A）0x1000x17C0x1800x1840x4000x4040xc000xc040x0FC指令數(shù)據(jù)asumI34I35a[0][0]a[0][1]?

?

?a[0][2047]a[1][0]a[1][1]?

?

??

?

?I1I2I33?

?

?for循環(huán)體實際運行結果(2GHzIntelPentium4):程序A：59,393,288時鐘周期程序B：1,277,877,876時鐘周期程序A比程序B快21.5倍!!Cache(高速緩存)是什么樣的？Cache是一種小容量高速緩沖存儲器，它由SRAM組成。Cache直接制作在CPU芯片內(nèi)，速度幾乎與CPU一樣快。程序運行時，CPU使用的一部分數(shù)據(jù)/指令會預先成批拷貝在Cache中，Cache的內(nèi)容是主存儲器中部分內(nèi)容的映象。當CPU需要從內(nèi)存讀(寫)數(shù)據(jù)或指令時，先檢查Cache，若有，就直接從Cache中讀取，而不用訪問主存儲器。012345678910111213141589143444101010主存中的信息按“塊”送到Cache中Cache存儲器主存儲器數(shù)據(jù)訪問過程：塊（Block）Cache的操作過程若被訪問信息不在cache中，稱為缺失或失靶(miss)若被訪問信息在cache中，稱為命中(hit)問題：什么情況下，CPU產(chǎn)生訪存要求？執(zhí)行指令時！Cache（高速緩存）的實現(xiàn)問題：要實現(xiàn)Cache機制需要解決哪些問題？如何分塊？主存塊和Cache之間如何映射?Cache已滿時，怎么辦？寫數(shù)據(jù)時怎樣保證Cache和MM的一致性？如何根據(jù)主存地址訪問到cache中的數(shù)據(jù)？……問題：Cache對程序員(編譯器)是否透明？為什么？是透明的，程序員(編譯器)在編寫/生成高級或低級語言程序時無需了解Cache是否存在或如何設置，感覺不到cache的存在。但是，對Cache深入了解有助于編寫出高效的程序！主存被分成若干大小相同的塊，稱為主存塊(Block)，Cache也被分成相同大小的塊，稱為Cache行（line）或槽（Slot）。Cache映射(CacheMapping)什么是Cache的映射功能？把訪問的局部主存區(qū)域取到Cache中時，該放到Cache的何處？Cache槽比主存塊少，多個主存塊映射到一個Cache槽中如何進行映射？把主存空間劃分成大小相等的主存塊（Block）Cache中存放一個主存塊的對應單位稱為槽（Slot）或行（line）有書中也稱之為塊（Block），有書稱之為頁（page）（不妥！）將主存塊和Cache行按照以下三種方式進行映射直接(Direct)：每個主存塊映射到Cache的固定行全相聯(lián)(FullAssociate)：每個主存塊映射到Cache的任一行組相聯(lián)(SetAssociate)：每個主存塊映射到Cache固定組中任一行

TheSimplestCache:DirectMappedCacheDirectMappedCache（直接映射Cache舉例)把主存的每一塊映射到一個固定的Cache行（槽）也稱模映射(ModuleMapping)映射關系為：

Cache行號=主存塊號modCache行數(shù)舉例：4=100mod16（假定Cache共有16行）(說明：主存第100塊應映射到Cache的第4行中。)特點：容易實現(xiàn)，命中時間短無需考慮淘汰（替換）問題但不夠靈活，Cache存儲空間得不到充分利用，命中率低

例如，需將主存第0塊與第16塊同時復制到Cache中時，由于它們都只能復制到Cache第0行，即使Cache其它行空閑，也有一個主存塊不能寫入Cache。這樣就會產(chǎn)生頻繁的Cache裝入。SKIP塊（行）都從0開始編號直接映射Cache組織示意圖假定數(shù)據(jù)在主存和Cache間的傳送單位為512字。Cache大小：213字=8K字=16行x512字/行主存大小：220字=1024K字=2048塊x512字/塊Cache標記(tag)指出對應行取自哪個主存塊群指出對應地址位于哪個塊群例：如何對0220CH單元進行訪問？0220CH00000010001000001100B是第1塊群中的0001塊（即第17塊）中第12個單元！0000001Cache索引有效位（ValidBit）

V為有效位，為1表示信息有效，為0表示信息無效開機或復位時，使所有行的有效位V=0某行被替換后使其V=1某行裝入新塊時使其V=1

通過使V=0來沖刷Cache（例如：進程切換時，DMA傳送時）通常為操作系統(tǒng)設置“cache沖刷”指令，因此，cache對操作系統(tǒng)程序員不是透明的！為何要用有效位來區(qū)分是否有效？64KBDirectMappedCachewith16BBlocks

主存和Cache之間直接映射，塊大小為16B。Cache的數(shù)據(jù)區(qū)容量為64KB，主存地址為32位，按字節(jié)編址。要求：說明主存地址如何劃分和訪存過程。

1612ByteoffsetVtag163212832323223231

DataWord20ByteBlockoffsetMemoryAddressTagIndexMUX4Klines=Mux16data④①②Hit③⑤

問題：Cache有多少行？容量多大？容量4Kx(1+16)+64Kx8=580Kbits=72.5KB,數(shù)據(jù)占64KB/72.5KB=88.3%

64KB÷16B=4K行如何計算Cache的容量？Consideracachewith64Linesandablocksizeof16bytes.Whatlinenumberdoesbyteaddress1200mapto?地址1200對應存放在第11行。因為：[1200/16=75]module64=11實現(xiàn)以下cache需要多少位容量？Cache：直接映射、16K行數(shù)據(jù)、塊大小為1個字(4B)、32位主存地址

答：Cache的存儲布局如下：所以，Cache的大小為：214×(32+(32-14-2)+1)=214×49=784Kbits32–14–2

322141若塊大小為4個字呢？214×(4×32+(32-14-2-2)+1)=214×143=2288KbitsCache共有16Kx4B=64KB數(shù)據(jù)若塊大小為2m個字呢？214×(2m×32+(32-14-2-m)+1)

BACK1200=1024+128+32+16=0…01

001011

0000B全相聯(lián)映射Cache組織示意圖Cache標記（tag）指出對應行取自哪個主存塊主存tag指出對應地址位于哪個主存塊如何對01E0CH單元進行訪問？00000001111000001100B是第15塊中的第12個單元！每個主存塊可裝到Cache任一行中。假定數(shù)據(jù)在主存和Cache間的傳送單位為512字。Cache大小：213字=8K字=16行x512字/行主存大小：220字=1024K字=2048塊x512字/塊00000001111按內(nèi)容訪問，是相聯(lián)存取方式！如何實現(xiàn)按內(nèi)容訪問？直接比較！為何地址中沒有cache索引字段？因為可映射到任意一個cache行中！舉例：FullyAssociativeFullyAssociativeCache無需Cache索引，為什么？因為同時比較所有Cache項的標志Bydefinition:ConflictMiss=0(沒有沖突缺失，因為只要有空閑Cache塊，都不會發(fā)生沖突)Example:32bitsmemoryaddress,

32Bblocks.

比較器位數(shù)多長？

weneedN27-bitcomparators0431:

CacheDataB

0:CacheTag(27bitslong)V:B

1B

31:B

32B33B63:

CacheTagByte

SelectEx:0x01=====:問題：需要多少個比較器？每行一個比較器！組相聯(lián)映射（SetAssociative）組相聯(lián)映射結合直接映射和全相聯(lián)映射的特點將Cache所有行分組，把主存塊映射到Cache固定組的任一行中。也即：組間模映射、組內(nèi)全映射。映射關系為：

Cache組號=主存塊號modCache組數(shù)舉例：假定Cache劃分為：8K字=8組x2行/組x512字/行4=100mod8(主存第100塊應映射到Cache的第4組的任意行中。)

特點：結合直接映射和全相聯(lián)映射的優(yōu)點。當Cache組數(shù)為1時，變?yōu)橄嗦?lián)映射；當每組只有一個槽時，變?yōu)橹苯佑成洹Ｃ拷M2或4行（稱為2-路或4-路組相聯(lián)）較常用。通常每組4行以上很少用。在較大容量的L2Cahce和L3Cahce中使用4-路以上。指出對應行取自哪個主存組群指出對應地址位于哪個主存組群中將主存地址標記和對應Cache組中每個Cache標記進行比較！例：如何對0120CH單元進行訪問？00000001001000001100B是第1組群中的001塊（即第9塊）中第12個單元。

所以，映射到第一組中。假定數(shù)據(jù)在主存和Cache間的傳送單位為512字。Cache大小：213字=8K字=16行x512字/行主存大小：220字=1024K字=2048塊x512字/塊Cache索引例1：ATwo-waySetAssociativeCacheN-waysetassociativeN個直接映射的行并行操作Example:Two-waysetassociativecacheCacheIndex選擇其中的一個Cache行集合（共2行）對這個集合中的兩個Cache行的Tag并行進行比較根據(jù)比較結果確定信息在哪個行，或不在Cache中CacheIndexCache

DataBlock0CacheTagValid:::CacheDataBlock0CacheTagValid:::Mux01

=

=ORHit④①AdrTag②②③③Cache

Block⑤⑤命中率、缺失率、缺失損失Hit:要訪問的信息在Cache中HitRate(命中率)：在Cache中的概率HitTime(命中時間)

：在Cache中的訪問時間，包括：Timetodeterminehit/miss+Cacheaccesstime(即：判斷時間+Cache訪問)Miss:要找的信息不在Cache中MissRate(缺失率)=1-(HitRate)MissPenalty(缺失損失)：訪問一個主存塊所花時間HitTime<<MissPenalty（Why?）Averageaccesstime(平均訪問時間)Cache對程序員來說是透明的，以方便編程！要提高平均訪問速度，必須提高命中率！命中率到底應該有多大？看看命中率對平均訪問時間的影響設H是命中率，則平均訪問時間T

=HTC+(1-H)(TC+TM)=TC+(1-H)TM例1.若H=0.85,Tc=1ns,TM=20ns，則T為多少？答：T=4ns

例2.若命中率H提高到0.95，則結果又如何？ 答：T=2ns例3.若命中率為0.99呢？答:T=1.2ns訪存速度與命中率的關系非常大！高速緩存的缺失率和關聯(lián)度三種映射方式直接映射：唯一映射（只有一個可能的位置）全相聯(lián)映射：任意映射（每個位置都可能）N-路組相聯(lián)映射：N-路映射（有N個可能的位置）什么叫關聯(lián)度？一個主存塊映射到Cache中時，可能存放的位置個數(shù)直接映射關聯(lián)度？全相聯(lián)映射關聯(lián)度？N-路組相聯(lián)映射關聯(lián)度？關聯(lián)度和missrate有什么關系呢？和命中時間的關系呢？直觀上，你的結論是什么？（Cache大小和塊大小一定時）缺失率：直接映射最高，全相聯(lián)映射最低命中時間：直接映射最小，全相聯(lián)映射最大用例子來說明關聯(lián)度最低，為1關聯(lián)度最高，為Cache行數(shù)關聯(lián)度居中，為N如何只取Data中某字節(jié)？關聯(lián)度不同，總的標記位數(shù)不同，也即額外空間開銷不同！根據(jù)地址中最低兩位來取！標記位大小與關聯(lián)度按字節(jié)編址，塊大小為4B，故塊內(nèi)地址占3位標記位大小與關聯(lián)度問題：若主存地址32位，塊大小為16字節(jié)，Cache總大小為4K行，問：標記位的總位數(shù)是多少？直接映射方式下：相當于每組1行，共4K組，標志占32-4-12=16位總位數(shù)占4Kx16=64K位關聯(lián)度增加到2倍(2-way)：每組2行，共2K組，標志占32-4-11=17位總位數(shù)占4Kx17=68K位關聯(lián)度增加到4倍(4-way)：每組4行，共1K組，標志占32-4-10=18位總位數(shù)占4Kx18=72K位全相聯(lián)時：整個為1組，每組4K行，標志占32-4=28位總位數(shù)占4Kx28=112K位關聯(lián)度越高，總的標記位數(shù)越多，額外空間開銷越大！替換(Replacement)算法問題舉例：組相聯(lián)映射時，假定第0組的兩行分別被主存第0和8塊占滿，此時若需調(diào)入主存第16塊，根據(jù)映射關系，它只能放到Cache第0組，因此，第0組中必須調(diào)出一塊，那么調(diào)出哪一塊呢？這就是淘汰策略問題，也稱替換算法。常用替換算法有：先進先出FIFO（first-in-first-out）最近最少用LRU（least-recentlyused）最不經(jīng)常用LFU（least-frequentlyused）隨機替換算法（Random）等等這里的替換策略和后面的虛擬存儲器所用的替換策略類似，將是以后操作系統(tǒng)課程的重要內(nèi)容，本課程只做簡單介紹。有興趣的同學可以自學。SKIP假定第0組的兩行分別被主存第0和8塊占滿，此時若需調(diào)入主存第16塊該怎么辦？第0組中必須調(diào)出一塊，那么，調(diào)出哪一塊呢？BACK替換算法-先進先出（FIFO）總是把最先進入的那一塊淘汰掉。例：假定主存中的5塊{1,2,3,4,5}同時映射到Cache同一組中，對于同一地址流，考察3行/組、4行/組的情況。由此可見，F(xiàn)IFO不是一種棧算法，即命中率并不隨組的增大而提高。1*1*4231*442*13*4*51*1*2355*2*341234125123452312251*255*34

√√√

3行/組1*1*4231*44243*1*512*3*15*421*2232335125452*

√√

1*21*4*3334行/組注：通常一組中含有2k行，這里3行/組主要為了簡化問題而假設總是把最先從圖書館搬來的書還回去！替換算法-最近最少用(LRU)總是把最近最少用的那一塊淘汰掉。例：假定主存中的5塊{1,2,3,4,5}同時映射到Cache同一組中，對于同一地址流，考察3行/組、4行/組、5行/組的情況。31221131433325224234132221415152543

√√

√√√√√√√√√√√44145121234125123453134513行/組4行/組5行/組總是把最長時間不看的書還回去！替換算法-最近最少用LRU是一種棧算法，它的命中率隨組的增大而提高。當分塊局部化范圍(即：某段時間集中訪問的存儲區(qū))超過了Cache存儲容量時，命中率變得很低。極端情況下，假設地址流是1,2,3,4,12,3,4,1,……，而Cache每組只有3行，那么，不管是FIFO，還是LRU算法，其命中率都為0。這種現(xiàn)象稱為顛簸(Thrashing/PingPong)。LRU具體實現(xiàn)時，并不是通過移動塊來實現(xiàn)的，而是通過給每個cache行設定一個計數(shù)器，根據(jù)計數(shù)值來記錄這些主存塊的使用情況。這個計數(shù)值稱為LRU位。

具體實現(xiàn)替換算法-最近最少用計數(shù)器變化規(guī)則：每組4行時，計數(shù)器有2位。計數(shù)值越小則說明越被常用。命中時，被訪問行的計數(shù)器置0，比其低的計數(shù)器加1，其余不變。未命中且該組未滿時，新行計數(shù)器置為0，其余全加1。未命中且該組已滿時，計數(shù)值為3的那一行中的主存塊被淘汰，新行計數(shù)器置為0，其余加1。123412512345543203211243320112532130125410231254021312542103123410321234032112343210123210121010即：計數(shù)值為0的行中的主存塊最常被訪問，計數(shù)值為3的行中的主存塊最不經(jīng)常被訪問，先被淘汰！通過計數(shù)值來確定cache行中主存塊的使用情況TheNeedtoReplace!(何時需要替換？)DirectMappedCache:映射唯一，毫無選擇，無需考慮替換N-waySetAssociativeCache:每個主存數(shù)據(jù)有N個Cache行可選擇，需考慮替換FullyAssociativeCache:每個主存數(shù)據(jù)可存放到Cache任意行中，需考慮替換結論：若CachemissinaN-waySetAssociativeorFullyAssociativeCache，則可能需要替換。其過程為：從主存取出一個新塊選擇一個有映射關系的空Cache行若對應Cache行被占滿時又需調(diào)入新主存塊，則必須考慮從Cache行中替換出一個主存塊舉例假定計算機系統(tǒng)主存空間大小為32Kx16位，且有一個4K字的4路組相聯(lián)Cache，主存和Cache之間的數(shù)據(jù)交換塊的大小為64字。假定Cache開始為空，處理器順序地從存儲單元0、1、…、4351中取數(shù)，一共重復10次。設Cache比主存快10倍。采用LRU算法。試分析Cache的結構和主存地址的劃分。說明采用Cache后速度提高了多少？采用MRU算法后呢？答：假定主存按字編址。每字16位。主存：32K字=512塊x64字/塊

Cache：4K字=16組x4行/組x64字/行主存地址劃分為：字號標志位組號6454352/64=68，所以訪問過程實際上是對前68塊連續(xù)訪問10次。舉例第0組第1組第2組第3組第4組…………第15組第0行第1行第2行第3行0/64/481/65/492/66/503/67/514…………1516/0/6417/1/6518/2/6619/3/6720…………3132/1633/1734/1835/1936…………4748/3249/3350/3451/3552…………63LRU算法：第一次循環(huán),每一塊只有第一字未命中,其余都命中;以后9次循環(huán),有20塊的第一字未命中,其余都命中.所以,命中率p為(43520-68-9x20)/43520=99.43%速度提高：tm/ta=tm/(tc+(1-p)tm)=10/(1+10x(1-p))=9.5倍舉例0/16/32/481/17/33/492/18/34/503/19/35/524……15組16/32/48/6417/33/49/6518/34/50/6619/35/51/6720……3132/48/64/033/49/65/134/50/66/235/51/67/336……4748/64/0/1649/65/1/1750/66/2/1851/67/3/1952……63MRU算法：第一次68字未命中；第2,3,4,6,7,8,10次各有4字未命中；第5,9次各有8字未命中；其余都命中.所以,命