第4章

存儲器層次結(jié)構(gòu)4.6高速緩沖存儲器4.6.1程序訪問的局部性4.6.2Cache的基本工作原理4.6.3Cache與主存的地址映像方式4.6.4Cache的替換算法與寫策略4.6.5Cache應(yīng)用舉例4.6.1程序訪問的局部性據(jù)統(tǒng)計CPU的速度平均每年改進(jìn)60%，而組成主存的動態(tài)RAM速度平均每年只改進(jìn)7%，結(jié)果是CPU和動態(tài)RAM之間的速度間隔平均每年增大50%。為了解決CPU和主存之間速度不匹配的問題，可以考慮在CPU和主存之間設(shè)置一個高速的容量相對較小的存儲器，稱為高速緩沖存儲器（Cache）。通過大量典型程序的分析，可以發(fā)現(xiàn)CPU從主存取指令或取數(shù)據(jù)，在一定時間內(nèi)，只是對主存局部地址區(qū)域的訪問。這是由于指令和數(shù)據(jù)在主存內(nèi)都是連續(xù)存放的，并且有些指令和數(shù)據(jù)往往會被多次調(diào)用（如子程序、循環(huán)程序和一些常數(shù)）。這種一定時間內(nèi)對局部范圍的存儲器地址頻繁訪問，而對此范圍以外的地址則訪問甚少的現(xiàn)象就稱為程序訪問的局部性。根據(jù)這一原理，很容易設(shè)想，只要將CPU近期要用到的程序和數(shù)據(jù)，提前從主存送到Cache，那么就可以做到CPU在一定的時間內(nèi)不必從主存儲器取指令和數(shù)據(jù)，而只需要訪問Cache，從而提高訪問速度。一般Cache采用高速的SRAM制作，其價格比主存貴，但因其容量遠(yuǎn)小于主存，因此能很好地解決速度和成本的矛盾。為了盡量提高Cache存儲器的速度，它的全部功能由硬件實現(xiàn)，并且對程序員是透明的。4.6.2Cache的基本工作原理1、Cache的基本結(jié)構(gòu)圖4-36表示Cache的基本結(jié)構(gòu)。它一般由兩部分組成，一部分存放由主存儲器來的數(shù)據(jù)，另一部分存放該數(shù)據(jù)在主存儲器時的存放地址（此部分稱為地址標(biāo)記存儲器，記為Tag）。圖4-36Cache的基本結(jié)構(gòu)設(shè)主存有2n個字節(jié)，每個字節(jié)的地址碼為n位，為了與Cache映射，將主存與緩存都分成若干大小相同的塊，每個塊內(nèi)又包含若干個字節(jié)。設(shè)塊內(nèi)有B個字節(jié)，則主存共分成M=2n/B塊，這就將主存的n位地址分成兩段：高m位表示主存的塊地址，低b（B=2b）位表示塊內(nèi)地址。設(shè)Cache地址碼為（c+b）位，則Cache的塊數(shù)為2c塊。由于Cache容量小，所以分得的塊的數(shù)目少的多，主存中只有一部分塊的內(nèi)容可存放在Cache中。在Cache中，每一塊外加有一個標(biāo)記，指明它是主存的哪一塊信息的副本，所以該標(biāo)記的內(nèi)容相當(dāng)于主存中塊的編號。當(dāng)CPU發(fā)出讀請求時，將主存地址m位（或m位中的一部分）與Cache某塊的標(biāo)記相比較，根據(jù)其比較的結(jié)果是否相等而區(qū)分出兩種情況：當(dāng)比較結(jié)果相等時，說明需要的數(shù)已在Cache塊中，那么直接訪問Cache就行了；當(dāng)比較結(jié)果不相等時，說明需要的數(shù)據(jù)尚未調(diào)入Cache中，那么就要把該數(shù)據(jù)所在的整個字塊從主存中調(diào)進(jìn)來。前一種情況稱為訪問Cache命中，后一種情況稱為訪問Cache不命中。2、Cache的設(shè)計要素在Cache系統(tǒng)的設(shè)計中，需要考慮的基本要素有：①、Cache的容量：在設(shè)計Cache時，從價格的角度考慮，我們希望Cache的容量足夠小，這樣它和主存的平均每位價格才會接近于單個主存儲器位的價格。從速度的角度考慮，我們希望Cache的容量足夠大，這樣才能在Cache里存放更多主存信息的副本，使得CPU對信息的平均存取時間接近于單個Cache的存取時間。②、塊的大?。褐鞔婧虲ache都劃分了同樣大小的塊，塊的大小也稱為塊長，Cache的容量和塊的大小是影響Cache的效率的重要因素。通常用“命中率”來測量Cache的效率。命中率指CPU所要訪問的信息在Cache中的比率，而將所要訪問的信息不在Cache中的比率稱為失效率。塊長在由小變大的過程中，由程序局部性的原理，在已被訪問字的附近的內(nèi)容近期也可能被訪問到，所以命中率首先會增大。然后塊長增大到一定值后，Cache的塊數(shù)會減少，此時命中率反而會下降。通常塊長的大小取一個主存周期所能調(diào)出的信息長度。例如，CRAY-1機器的主存是模16交叉，每個分體為單字寬，其指令Cache的塊長為16個字。③、Cache的映像：由于Cache的數(shù)據(jù)塊比主存的數(shù)據(jù)塊要少得多，因此需要一種算法把主存儲器的數(shù)據(jù)塊映射到Cache中。而且，還需要一種方法來確定主存儲器中的哪一塊占用著Cache塊，所以映射的功能決定了Cache的結(jié)構(gòu)。通常，Cache的映射采用三種技術(shù)：直接映像、全相聯(lián)映像和組相聯(lián)映像。④、替換算法：當(dāng)新的主存塊需要被調(diào)入Cache時，如果它的可用空間被占滿的話，Cache中原存儲的塊需要被替換掉。如果新裝入塊的可用空間不只一個，就需要一種替換算法決定先替換哪一個。替換算法也稱為替換策略，一般由硬件實現(xiàn)。⑤、寫策略。在將駐留在Cache中的塊替換之前，需要考慮這塊數(shù)據(jù)駐留Cache期間是否被修改過，同時在主存中對應(yīng)的塊有沒有被修改。如果駐留期間沒有被修改過，則可直接將這塊替換掉；如果被修改過，即這個Cache塊至少被執(zhí)行過一次寫操作，那么在這個塊被替換掉之前必須對主存內(nèi)相應(yīng)的塊作修改，常見的寫策略有通寫和回寫等方法。⑥、Cache數(shù)目。Cache剛剛出現(xiàn)時，通常系統(tǒng)只有一個Cache，近年來普遍采用多個Cache。這個增多有兩個方面，一個是增加Cache的級數(shù)，一個是將統(tǒng)一的Cache分成分立的Cache。（1）一級緩存和二級緩存當(dāng)芯片集成度提高后，可以將Cache直接和處理器制作在同一個芯片內(nèi)，這也叫片內(nèi)緩存。與通過外部總線連接的Cache相比，片內(nèi)Cache使得CPU訪問Cache時不必占用芯片之外的總線，并且片內(nèi)Cache與CPU之間的數(shù)據(jù)通路更短，大大提高了存取的速度。但由于片內(nèi)Cache嵌制在芯片內(nèi)，容量一般都不大，這樣也降低了系統(tǒng)的性能，此時可以在處理器芯片外仍設(shè)置Cache，叫做片外緩存。片外緩存可以有較大的容量，向片內(nèi)緩存和處理器高速提供數(shù)據(jù)。此時在處理器芯片內(nèi)部的Cache稱為第一級Cache（L1），把片外的Cache稱為第二級Cache（L2）。（2）統(tǒng)一和分立緩存計算機開始實現(xiàn)Cache時，是將指令和數(shù)據(jù)存放在一個Cache中的。后來隨著計算機技術(shù)的發(fā)展和處理速度的加快，存取數(shù)據(jù)的操作經(jīng)常會與取指令的操作發(fā)生沖突，從而延遲了指令的讀取。當(dāng)前的趨勢是將指令Cache和數(shù)據(jù)Cache分開而成為兩個相互獨立的Cache。在給定Cache總?cè)萘康那闆r下，統(tǒng)一Cache可以有較高的利用率。因為在執(zhí)行不同程序時，Cache中指令和數(shù)據(jù)所占的比例是不同的，單一Cache可以自動調(diào)整指令和數(shù)據(jù)的空間，而分立緩存則不具有這一優(yōu)點。但在超標(biāo)量或流水技術(shù)的計算機中，要求同時取數(shù)據(jù)和取指令，必須將指令Cache和數(shù)據(jù)Cache分開。4.6.3Cache與主存的地址映像方式

為了把信息放到Cache存儲器中，必須應(yīng)用某種函數(shù)把主存地址映像到Cache，這稱為地址映像。在信息按照這種映像關(guān)系裝入Cache后，執(zhí)行程序時，應(yīng)將CPU給出的主存地址變換成Cache地址進(jìn)行訪問，這個變換過程叫做地址變換。地址的映像和變換是密切相關(guān)的。下面介紹幾種基本地址映像方式，它們是直接映像、全相聯(lián)映像和組相聯(lián)映像等。為了說明這幾種映像關(guān)系，假設(shè)主存儲器空間被分成Mm（0），Mm（1），……Mm（2m-1）共2m個塊，字塊大小為2b個字；Cache存儲空間被分成Mc（0），Mc（1），……Mc（2c-1）共2c個同樣大小的塊。1、直接映像在直接映像中，主存塊和Cache中字塊的對應(yīng)關(guān)系如圖4-37所示。直接映像函數(shù)可定義為：j=imod2c圖4-37直接映像Cache組織

直接映像的優(yōu)點是實現(xiàn)簡單，只需要利用主存地址按某些字段直接判斷，即可確定所需字塊是否已在Cache存儲器中。如圖4-37，主存地址末b位是字塊內(nèi)地址；中間c位是Cache字塊地址，又稱組地址；高（m-c）=t位就是主存字塊標(biāo)記，又稱區(qū)地址，是記錄在相應(yīng)Cache塊標(biāo)記中的內(nèi)容，當(dāng)有效位為“1”時，它表明該數(shù)據(jù)塊是主存哪一塊數(shù)據(jù)的副本。Cache在接收到CPU送來的主存地址和讀/寫命令后，只需根據(jù)中間c位字段找到Cache存儲器字塊，然后看其標(biāo)記是否與主存地址高t位符合，如果符合且有效位為“1”，則可根據(jù)b位塊內(nèi)地址，從Cache中取得所需指令或數(shù)據(jù)；如果不符合或有效位為“0”，就從主存讀入新的字塊來替換舊的字塊，并將CPU所需數(shù)據(jù)送往CPU，同時修改Cache標(biāo)記。假如原來有效位為“0”，還要將有效位改置成“1”。直接映像方式的缺點是不夠靈活，即主存的2t個字塊只能對應(yīng)惟一的一個Cache存儲器字塊，因此，即使Cache存儲器別的許多地址塊空著也不能占用。這使得Cache存儲空間得不到充分利用，并降低了命中率。2、全相聯(lián)映像全相聯(lián)映像方式是最靈活但成本最高的一種方式，如圖4-38所示。它允許主存中的每一個字塊映像到Cache存儲器的任何一個字塊位置上，也允許從確實已被占滿的Cache存儲器中替換出任何一個舊字塊。這是一個理想的方案。實際上由于它的成本太高而不能采用。圖4-38全相聯(lián)映像Cache組織

不只是它的標(biāo)記位數(shù)從t位增加到t+c位（與直接映像相比）使Cache標(biāo)記容量加大，主要問題是在訪問Cache時，需要和Cache的全部塊標(biāo)記進(jìn)行比較才能判斷出所訪問的主存地址的內(nèi)容是否已在Cache中。由于Cache速度要求很高，所以全部比較操作都要用硬件實現(xiàn)，通常由“按內(nèi)容尋址”的相聯(lián)存儲器完成。所需邏輯電路甚多，以致無法用于Cache中。3、組相聯(lián)映像組相聯(lián)映像方式是直接映像和全相聯(lián)映像方式的一種折中方案。組相聯(lián)映像Cache組織如圖4-39所示。它把Cache字塊分為2c`組，每組包含2r個字塊，于是有c=c`+r。此時組間為直接映像，而組內(nèi)的字塊為全相聯(lián)映像方式。圖4-39組相聯(lián)映像Cache組織

主存字塊Mm（i）（0≤i≤2m-1）可以用下列映像函數(shù)映像到Cache字塊Mc（j）（0≤j≤2c-1）上。j=（imod2c`）×2r+k（0≤k≤2r-1）組相聯(lián)映像把地址分成3段，末b位為塊內(nèi)地址，中間c`位為Cache組地址，高t位（區(qū)地址）和r位（組內(nèi)塊地址）形成標(biāo)記字段。在實際Cache中用得最多的是直接映像（r=0）、兩路組相聯(lián)映像（r=1）和4路組相聯(lián)映像（r=2）。如r=2，計算得0≤k≤3，所以主存某一字塊可映像到Cache某組4個字塊的任一字塊中，這大大地增加了映像的靈活性，提高了命中率。根據(jù)主存地址的“Cache組地址”字段訪問Cache，并將主存字塊標(biāo)記（t位+r位）與Cache同一組的2r個字塊標(biāo)記同時進(jìn)行比較，并檢查有效位，以確定是否命中。當(dāng)r不大時，需要同時進(jìn)行比較的標(biāo)記數(shù)不大，這個方案還是比較現(xiàn)實的。組相聯(lián)映像方式的性能與復(fù)雜性介于直接映像與全相聯(lián)映像兩種方式之間。組相聯(lián)映像方式中，當(dāng)r=0時，它就成為直接映像方式；當(dāng)r=c時，就是全相聯(lián)映像方式。4.6.4Cache的替換算法與寫策略1、Cache中主存塊的替換算法在從主存讀出新的字塊調(diào)入cache存儲器時，如果遇到cache存儲器中相應(yīng)的位置已被其他字塊占有，那么就必須去掉一個舊的字塊，讓位于一個新的字塊。這種替換應(yīng)該遵循一定的規(guī)則，最好能使被替換的字塊是下一段時間內(nèi)估計最少使用的。這些規(guī)則稱為替換策略或替換算法，由替換部件加以實現(xiàn)。常用的替換算法有以下幾種：（1）隨機替換算法。這種替換的原則是需要替換Cache塊時，用隨機數(shù)發(fā)生器產(chǎn)生需替換掉的Cache塊號。由于這種算法沒有考慮到信息的歷史情況和使用情況，所以在性能上比根據(jù)使用情況的替換算法要差些，實際很少使用。（2）先進(jìn)先出（FIFO）算法。FIFO算法的原則是每次需要替換塊的時候，將最先裝入Cache中的塊替換掉。FIFO用循環(huán)或環(huán)形緩沖技術(shù)很容易實現(xiàn)，不需要隨時記錄各字塊的使用情況。但其缺點是可能將一些經(jīng)常被用到的程序作為最早裝入的塊替換掉。（3）近期最少使用（LRU）算法。這種算法是把近期最少使用的字塊替換出去，為了確定近期哪些塊是最少使用的，需要隨時記錄Cache中各個字塊的使用情況。這是實際中最常采用的一種算法，一般來說，最近使用的存儲內(nèi)容很有可能再被使用，所以LRU有較好的命中率。（4）最不經(jīng)常使用（LFU）算法。LFU算法的原則是替換掉Cache中引用次數(shù)最少的塊。為了確定使用次數(shù)最少的Cache塊，每個塊都使用一個相關(guān)的計數(shù)器，Cache塊每引用一次，計數(shù)器就記錄一次，每次需要將Cache塊替換掉的時候，就將計數(shù)器值最小的那塊替換掉。2、Cache寫策略Cache存儲器中保存的字塊是主存中相應(yīng)字塊的一個副本。如果程序執(zhí)行過程中要對該字塊的某個單元進(jìn)行寫操作，就會遇到如何保持cache與主存的一致性問題。通常有兩種寫入策略：一種是通寫策略（也叫寫直達(dá)，或?qū)懲ㄟ^），這種策略的原理是所有的寫操作都對主存儲器和Cache同時進(jìn)行，這樣就可以保證主存儲器總是有效的。其他的CPU-Cache模塊則監(jiān)視對主存儲器的訪問，保持和它自己的Cache的一致性。不過由于每次向Cache寫入時，都需要向主存寫入，所以會增加訪問次數(shù)，降低系統(tǒng)性能。另一種為回寫策略（或標(biāo)志交換方式），這種策略的原理是數(shù)據(jù)每次只是暫時寫入Cache，并用標(biāo)志將該Cache塊加以標(biāo)記，直到該塊從Cache中被替換掉時，才將該塊的內(nèi)容寫回主存，這樣可以減少對存儲器的寫入。這種寫策略的速度很快，但是主存中的字塊并未隨時修改，因此部分存儲器是無效的，I/O模塊的存取只通過Cache進(jìn)行。這會引起更復(fù)雜電路和潛在瓶頸問題。另外還有一種寫操作方法是：當(dāng)被修改的單元根本就不在cache存儲器時，寫操作直接對主存進(jìn)行，而不寫入cache存儲器。4.6.5Cache應(yīng)用舉例

Cache結(jié)構(gòu)的演變可以從Intel微處理器的發(fā)展演變中看出規(guī)律。在Intel的80386中還沒有使用Cache，在80486中開始包含一個容量僅為8KB的片內(nèi)Cache，這個片內(nèi)Cache采用的是16字節(jié)每塊的4路組相聯(lián)的結(jié)構(gòu)。而到了Pentium的時候，它則使用了兩個片內(nèi)的Cache，每個Cache容量為8KB，采用的是32字節(jié)每塊的兩路組相聯(lián)結(jié)構(gòu)，其中一個用于存儲數(shù)據(jù)，一個用于存儲指令，Pentium處理器框圖如圖4-40所示。圖4-40Pentium處理器框圖從圖中可以看到，Pentium的核心執(zhí)行單元為兩個可以并行執(zhí)行的整型算術(shù)邏輯單元和它自己的寄存器，還有加、乘、除運算部件的浮點單元，而突出的結(jié)構(gòu)為兩個Cache的布局結(jié)構(gòu)。其中數(shù)據(jù)Cache用于提供數(shù)據(jù)給整數(shù)和浮點數(shù)操作，它有兩個32位的端口，分別與兩個整型ALU相連，也可以合在一起與64位浮點單元相連。因此，數(shù)據(jù)Cache可以直接支持整型ALU和浮點操作。而另一個指令Cache為只讀存儲器，從它讀出代碼，然后直接送到預(yù)取指令緩沖區(qū)。Pentium的數(shù)據(jù)Cache由128個組組成，每個組組內(nèi)有兩個塊，在邏輯上可以形成兩個4K字節(jié)的“路”，在Cache中與每塊相關(guān)的是標(biāo)記和兩個狀態(tài)位，這在邏輯上也可以組織成兩個目錄。所以在Cache中每個塊都有一個目錄項。主存地址的32位中，高20位為標(biāo)記，中間7位為組號，最低5位為塊內(nèi)地址。Cache控制器采用的替換算法是近期最少使用（LRU）算法，所以每組設(shè)置有一個LRU狀態(tài)位相關(guān)每組中的兩個塊，表示塊的使用情況。數(shù)據(jù)Cache采用的寫策略為回寫策略，只有當(dāng)Cache中數(shù)據(jù)被修改過的塊要被替換掉時，才將相應(yīng)的信息寫回主存儲器。同時，Pentium處理器能夠動態(tài)配置以支持Cache的寫通過策略。在Cache數(shù)目方面，Pentium處理器支持外部的2級Cache，容量為256K字節(jié)或512字節(jié)，而Cache中每塊的大小可為32、64或128字節(jié)，外部Cache的結(jié)構(gòu)為二路組相聯(lián)結(jié)構(gòu)。在保持?jǐn)?shù)據(jù)Cache一致性方面，數(shù)據(jù)Cache支持MESI協(xié)議。4.7虛擬存儲器4.7.1虛擬存儲器的基本概念4.7.2段式虛擬存儲器4.7.3頁式虛擬存儲器4.7.4段頁式虛擬存儲器4.7.5快表TLB4.7.1虛擬存儲器的基本概念虛擬存儲器只是一個容量非常大的存儲器的邏輯模型，不是任何實際的物理存儲器，它由主存儲器和聯(lián)機工作的輔助存儲器（通常為磁盤存儲器）共同組成，這兩個存儲器在硬件和系統(tǒng)軟件的共同管理下工作，對于應(yīng)用程序員，可以把它們看作是一個單一的存儲器來使用。虛擬存儲器不僅是解決存儲容量和存取速度矛盾的一種方法，而且也是管理存儲設(shè)備的有效方法。它將主存或輔存的地址空間統(tǒng)一編址，形成一個龐大的存儲空間。在這個大空間里，用戶可以自由編程，完全不必考慮程序在主存里是否裝得下以及這些程序在主存中的實際存放位置。用戶編程的地址稱為虛地址或邏輯地址，實際的主存單元地址稱為實地址或物理地址。顯然，虛地址要比實地址大得多。在實際的物理存儲層次上，所編程序和數(shù)據(jù)在操作系統(tǒng)管理下，先送入磁盤，然后操作系統(tǒng)將當(dāng)前運行所需要的部分調(diào)入主存，供CPU使用，其余暫不運行部分留在磁盤中。程序運行時，CPU以虛地址來訪問主存，由輔助軟硬件找出虛地址和實地址之間的對應(yīng)關(guān)系，并判斷這個虛地址指示的存儲單元內(nèi)容是否已裝入主存。如果已在主存中，則通過地址變換得到主存實地址，CPU可直接訪問主存的實際單元；如果不在主存中，則把包含這個字的一頁或一個程序段調(diào)入主存后再由CPU訪問。如果主存已滿，則由替換算法從主存中將暫不運行的一塊調(diào)回輔存，再從輔存調(diào)入新的一塊到主存。從原理的角度看，虛擬存儲器和Cache—主存有不少相同之處。事實上，前面提到的各種地址變換及映像方法和替換策略都是先應(yīng)用于虛擬存儲器中，后來才發(fā)展到Cache—主存層次中去的。不過Cache—主存的控制完全由硬件實現(xiàn)，所以對各類程序員是透明的，而虛擬存儲器的控制是軟硬件相結(jié)合的，對于設(shè)計存儲管理軟件的系統(tǒng)程序員來說是不透明的，對于應(yīng)用程序員來說是透明的。主存—輔存層次的信息傳送單位可采用幾種不同的方案：段、頁或段頁式。段是利用程序的模塊化性質(zhì)，按照程序的邏輯結(jié)構(gòu)劃分成的多個相對獨立的部分，例如：過程、子程序、數(shù)據(jù)表、陣列等。段作為獨立的邏輯單位可以被其他程序段調(diào)用，這就形成段間連接，產(chǎn)生規(guī)模較大的程序。因此，把段作為基本信息單位在主存—輔存之間傳送和定位是比較合理的。一般用段表來指明各段在主存中的位置。每段都有它的名稱（用戶名、數(shù)據(jù)結(jié)構(gòu)名或段號）、段起點、段長等。段表本身也是主存儲器的一個可再定位段。把主存按段分配的存儲管理方式稱為段式管理。段式管理系統(tǒng)的優(yōu)點是段的分界與程序的自然分界相對應(yīng)；段的邏輯獨立性使它易于編譯、管理、修改和保護(hù)，也便于多道程序共享。某些類型的段（堆棧、隊列）具有動態(tài)可變長度，允許自由調(diào)度以便于有效利用主存空間。但是，正因為段的長度各不相同，段的起點和終點不定，給主存空間分配帶來麻煩，而且容易在段間留下許多空余的零碎存儲空間不好利用，造成浪費。頁式管理系統(tǒng)的基本信息傳送單位是定長的頁。主存的物理空間被劃分為等長的固定區(qū)域，稱為頁面。頁面的起點和終點地址是固定的，新頁調(diào)入主存時只要有空白頁面就可，可能造成浪費的是程序最后一頁的零頭，是不能利用的頁內(nèi)空間，它比段式管理系統(tǒng)的空間浪費要小得多。頁式管理系統(tǒng)的缺點正好和段式管理系統(tǒng)相反，由于頁不是邏輯上獨立的實體，所以處理、保護(hù)和共享都不及段式方便。段式存儲管理和頁式存儲管理各有其優(yōu)缺點，因此可以采用分段和分頁相結(jié)合的段頁式管理系統(tǒng)。程序按模塊分段，段內(nèi)再分頁，進(jìn)入主存仍以頁為基本信息傳送單位，用段表和頁表（每段一個頁表）進(jìn)行兩級定位管理。4.7.2段式虛擬存儲器在段式虛擬存儲系統(tǒng)中，段是按照程序的邏輯結(jié)構(gòu)劃分的，各個段的長度因程序而異。虛擬地址由段號和段內(nèi)地址組成，如圖4-41所示。圖4-41段式虛擬存儲器管理為了把虛擬地址變換成實主存地址，需要一個段表，段表實際上是程序的邏輯結(jié)構(gòu)段與其在主存中的實際存放位置之間的關(guān)系對應(yīng)表。段表中裝入位為“1”表示該段已調(diào)入主存，為“0”則表示該段不在主存中；段的長度可大可小，所以段表中需要有長度指示。在訪問某段時，如果段內(nèi)地址值超過段的長度，則發(fā)生地址越界中斷。段式虛擬存儲器的地址變換過程如下：CPU根據(jù)虛地址訪存時，首先將段號與段表的起始基地址相拼接，形成訪問段表對應(yīng)行的地址，然后根據(jù)段表內(nèi)裝入位判斷該段是否已調(diào)入主存。若已調(diào)入主存，從段表讀出該段在主存中的起始地址，與段內(nèi)地址（偏移量）相加，得到對應(yīng)的主存實地址。4.7.3頁式虛擬存儲器在頁式虛擬存儲系統(tǒng)中，把虛擬空間分成頁，稱為邏輯頁；主存空間也分成同樣大小的頁，稱為物理頁。各類計算機頁面大小不等，一般為512B到幾KB，由于頁的大小都取2的整數(shù)冪個字，所以，頁的起點都落在低位字段為0的地址上。程序虛地址分為兩個字段：高位字段為虛頁號，低位字段為頁內(nèi)地址。虛地址到實地址之間的變換是由頁表來實現(xiàn)的。頁表是一張存放在主存中的虛頁號和實頁號的對照表，記錄著程序的虛頁調(diào)入主存時被安排在主存中的位置。若計算機采用多道程序工作方式，則可為每個用戶作業(yè)建立一個頁表，硬件中設(shè)置一個頁表基址寄存器，存放當(dāng)前所運行程序的頁表的起始地址。在頁表中，對應(yīng)每一個虛存頁號有一個表目，表目內(nèi)容至少要包含該虛頁所在的主存頁面地址（頁面號），用它作為實（主）存地址的高字段；與虛擬地址的頁內(nèi)字地址字段相拼接，就產(chǎn)生完整的實主存地址，然后按此地址訪問主存。頁式管理的地址變換如圖4-42所示。圖4-42頁式虛擬存儲器結(jié)構(gòu)通常，在頁表的表項中還包括由裝入位（有效位）、修改位、替換控制位及其他保護(hù)位等組成的一個控制字。如裝入位為“1”，表示該虛頁已從輔存調(diào)入主存；如裝入位為“0”，則表示對應(yīng)的虛頁尚未調(diào)入主存。如訪問該頁就要產(chǎn)生頁面失效中斷，啟動輸入輸出子系統(tǒng)，根據(jù)外頁表項目中查得的輔存地址，由磁盤等輔存中讀出新的頁到主存中來。修改位指出主存頁面中的內(nèi)容是否被修改過，替換時是否要寫回輔存。替換控制位指出需替換的頁等。4.7.4段頁式虛擬存儲器在段頁式虛擬存儲器中，把程序按邏輯結(jié)構(gòu)分段后，再把每段分成固定大小的頁。程序?qū)χ鞔娴恼{(diào)入調(diào)出是按頁面進(jìn)行的，但它又可以按段實現(xiàn)共享和保護(hù)。因此，它可以兼取頁式和段式系統(tǒng)的優(yōu)點。其地址變換過程如圖4-43所示。圖4-43段頁式虛擬存儲器結(jié)構(gòu)CPU訪問時，虛地址包含段號、段內(nèi)頁號、頁內(nèi)地址3部分。首先將段表起始地址與段號合成，得到段表項地址；然后從段表中取出該段的頁表起始地址，與段內(nèi)頁號合成，得到頁表項地址；最后從頁表中取出實頁號，與頁內(nèi)地址拼接形成主存實地址?？梢钥闯觯雾撌教摂M存儲系統(tǒng)由虛擬地址向?qū)嵵鞔娴刂返淖儞Q過程中至少要查兩次表（段表和頁表），為了加快地址變換過程的速度，一般會在其中設(shè)置快表。另外，對段進(jìn)行劃分時，段的長度必須是頁長的整數(shù)倍，段的起點必須是某一頁的起點。4.7.5快表TLB假設(shè)頁表是保存在主存儲器中，那么在訪問存儲器時，首先要查頁表，即使頁面命中，也得先訪問一次主存去查頁表，再按查得的實主存地址訪問才能取得數(shù)據(jù)，這就相當(dāng)于主存速度降低了一倍。如果頁面失效，要進(jìn)行頁面替換、頁面修改，訪問主存次數(shù)就更多了。要想提高虛存系統(tǒng)訪問的速度，必須加快查表的速度。由于程序在執(zhí)行過程中具有局部性的特點，因此，對頁表的訪問并不完全是隨機的。在一段時間內(nèi)，對頁表的訪問只是局限在少數(shù)幾個頁表項內(nèi)。為了將訪問頁表的時間降低到最低，許多計算機將頁表分為快表和慢表兩種。將當(dāng)前最常用的頁表信息存放在一個小容量的高速存儲器中，稱為“快表”，也叫轉(zhuǎn)換旁路緩沖器（translationlookasidebuffer，簡稱TLB）；把主存中的頁表稱為慢表。一種經(jīng)快表與慢表實現(xiàn)內(nèi)部地址變換的方式如圖4-44所示。圖4-44使用快表和慢表實現(xiàn)地址變換查表時，由虛頁號同時去查快表和慢表，當(dāng)在快表中有此虛頁號時，就能很快地找到對應(yīng)的實頁號送入實主存地址寄存器。并使慢表的查找作廢。如果在快表中查不到，那就要費一個訪主存時間查找慢表，從中查到實頁號送入實主存地址寄存器，并將此虛頁號和對應(yīng)的實頁號送入快表，替換快表中某一行內(nèi)容。快表比頁表小得多，一般在16行~64行之間，只是慢表的小小的副本。用按內(nèi)容查找的相聯(lián)存儲器并行查找，是可供選擇的一種技術(shù)途徑（相聯(lián)存儲器內(nèi)容參見附錄3）。4.8輔助存儲器介紹4.8.1輔存概述4.8.2磁記錄原理與記錄方式4.8.3硬磁盤存儲器與磁盤陣列4.8.4磁帶存儲器4.8.5光盤存儲器4.8.1輔存概述輔助存儲器作為主存的后援設(shè)備，又稱為外部存儲器，簡稱外存或輔存。它具有容量大、速度慢、價格低、可脫機保存信息等特點。當(dāng)前市場上流行的輔助存儲器主要有磁表面存儲器和光存儲器兩大類。磁表面存儲器是將磁性材料沉積在盤片（或帶）的基體上形成記錄介質(zhì)，并以繞有線圈的磁頭與記錄介質(zhì)的相對運動來寫入或讀出信息。根據(jù)基體的性質(zhì)，可以分為軟性基體和硬性基體。在硬磁盤中使用的是硬性基體，一般為硬質(zhì)鋁合金；而磁帶和軟磁盤中使用的是軟性基體，一般為聚脂薄膜材料。用于計算機系統(tǒng)的光存儲器主要是光盤（opticaldisk），光盤是利用激光束在具有感光特性的介質(zhì)表面存儲和讀取信息的。輔助存儲器的主要技術(shù)指標(biāo)是存儲密度、存儲容量、尋址時間等，下面結(jié)合磁表面存儲器來進(jìn)行介紹。①、存儲密度存儲密度是指單位長度或單位面積磁層表面所存儲的二進(jìn)制信息量。磁盤存儲器可用道密度和位密度來表示，也可以用兩者的乘積——面密度表示。磁道指的是存儲在介質(zhì)表面上的信息的磁化軌跡。對于磁盤存儲器，磁道是磁盤表面上的許多同心圓。磁道具有一定的寬度，它取決于磁頭的工作間隙長度及磁頭定位精度等因素。為了避免干擾，磁道與磁道之間需保持一定距離，相鄰兩條磁道中心線之間的距離叫道距。沿磁盤半徑方向單位長度的磁道數(shù)稱為道密度，單位長度磁道所能記錄二進(jìn)制信息的位數(shù)叫位密度。對于磁帶，其磁道是沿著磁帶長度方向的直線，存儲密度主要用位密度來衡量。②、存儲容量存儲容量指磁表面存儲器所能存儲的二進(jìn)制信息總量，一般用字節(jié)作為單位。以磁盤存儲器為例，存儲容量可按下式計算：C=N×K×S其中C為存儲容量，N為存放信息的盤面數(shù)，K為每個盤面的磁道數(shù)，S為每條磁道上記錄的二進(jìn)制代碼數(shù)。磁盤存儲器有格式化容量和非格式化容量兩個指標(biāo)。非格式化容量是磁記錄表面可以利用的磁化單元總數(shù)。格式化容量是按照某種特定的記錄格式所能存儲信息的總量，也就是用戶真正可以使用的容量，它一般為非格式化容量的60%~70%。③、尋址時間磁盤存儲器的尋址時間包括兩部分：一是磁頭尋找目標(biāo)磁道所需的找道時間Ts；二是找到磁道以后，磁頭等待所需要讀寫的區(qū)段旋轉(zhuǎn)到它的下方所需要的等待時間Tw。由于尋找相鄰磁道和從最外面磁道找到最里面磁道所需的時間不同，磁頭等待不同區(qū)段所花的時間也不同，因此，取它們的平均值，稱作平均尋址時間Ta，它由平均找道時間Tsa和平均等待時間Twa組成：Ta=Tsa+Twa=（（Tsmax+Tsmin）/2）+（（Twmax+Twmin）/2）④、數(shù)據(jù)傳輸率磁表面存儲器在單位時間內(nèi)與主機之間傳送數(shù)據(jù)的位數(shù)或字節(jié)數(shù)，叫數(shù)據(jù)傳輸率Dr。它與記錄密度D和記錄介質(zhì)的運動速度V有關(guān)：Dr=D×V。⑤、誤碼率誤碼率是衡量磁表面存儲器出錯概率的參數(shù)，它等于從輔存讀出時，出錯信息位數(shù)和讀出的總信息位數(shù)之比。為了減少出錯率，磁表面存儲器通常采用循環(huán)冗余碼來發(fā)現(xiàn)并糾正錯誤。4.8.2磁記錄原理與記錄方式1、磁記錄原理磁表面存儲器通過磁頭和記錄介質(zhì)的相對運動完成讀寫操作。寫入過程如圖4-45（a）所示。讀出過程如圖4-45（b）所示。圖4-45磁表面存儲器讀寫原理2、磁表面存儲器的記錄方式磁記錄方式是一種編碼方式，它是按某種規(guī)律，將一串二進(jìn)制數(shù)字信息變換成磁表面相應(yīng)的磁化狀態(tài)。磁記錄方式對記錄密度和可靠性都有很大影響，常用的記錄方式有6種，如圖4-46所示。圖4-46磁記錄方式波形圖①、歸零制（RZ）②、不歸零制（NRZ）③、見“1”就翻的不歸零制（NRZ1）④調(diào)相制（PM）⑤調(diào)頻制（FM）⑥改進(jìn)調(diào)頻制（MFM）4.8.3硬磁盤存儲器與磁盤陣列磁盤存儲器是計算機系統(tǒng)中最主要的外存設(shè)備，和其他外存相比，它具有速度快、容量大，易于脫機保存等優(yōu)點。自從1956年美國IBM公司研制出第一個商品化的磁盤以來，它在結(jié)構(gòu)、性能等方面都有了很大的發(fā)展。1、硬磁盤存儲器的分類硬磁盤存儲器種類很多，結(jié)構(gòu)各異，性能差別很大。按磁頭的工作方式可分成移動頭磁盤存儲器和固定頭磁盤存儲器，如圖4-47所示；按磁盤的可換與否可分成可換盤存儲器和固定盤存儲器。圖4-47移動頭和固定頭磁盤移動頭磁盤存儲器存取數(shù)據(jù)時磁頭在磁盤盤面上徑向移動，磁頭與盤面不接觸，且隨氣流浮動，稱為浮動磁頭。這種存儲器可以有一個盤片或多個盤片組成，裝在主軸上。盤片的每面都有一個磁頭。固定頭磁盤存儲器的磁頭位置固定，磁盤的每一個磁道都對應(yīng)一個磁頭，盤片也不可更換。其特點是存取速度快，省去了磁頭沿盤片徑向運動找磁道的時間，磁頭處于工作狀態(tài)即可開始讀寫。可換盤存儲器是指磁盤不用時可以從驅(qū)動器中取出脫機保存。這種磁盤可以在兼容的磁盤存儲器間交換數(shù)據(jù)，便于擴大存儲容量。固定盤存儲器是指磁盤不能從驅(qū)動器中取出，更換時要把整個“頭盤組合體”一起更換。這種結(jié)構(gòu)的磁盤存儲器稱為溫徹斯特磁盤（Winchesterdisk）。溫徹斯特磁盤簡稱溫盤，是一種可移動磁頭固定盤片的磁盤存儲器，它的主要特點是一種密封組合式的硬磁盤，將磁頭、盤片、電機等驅(qū)動部件甚至讀寫電路等制成一個不可隨意拆卸的整體。它的防塵性能好，可靠性高，對使用環(huán)境要求不高。2、硬磁盤存儲器的結(jié)構(gòu)硬磁盤存儲器是由磁盤驅(qū)動器、磁盤控制器和盤片組成。磁盤驅(qū)動器為主機外一個獨立的設(shè)備，也稱為磁盤機，它主要包括主軸、定位驅(qū)動及數(shù)據(jù)控制等。主軸的作用是安裝盤片，并驅(qū)動它們以額定轉(zhuǎn)速穩(wěn)定旋轉(zhuǎn)。它的主要部件是主軸電機和有關(guān)控制電路。定位驅(qū)動系統(tǒng)是一個帶由速度和位置反饋的閉環(huán)調(diào)節(jié)自控系統(tǒng)。由位置檢測電路測得磁頭的即時位置，并與磁盤控制器送來的目標(biāo)磁道位置進(jìn)行比較，找出位差；再根據(jù)磁頭即時平移的速度求得磁頭正確運動的方向和速度，經(jīng)放大送回給線性電機，以驅(qū)動磁頭找到目標(biāo)磁道。數(shù)據(jù)控制部分主要完成數(shù)據(jù)轉(zhuǎn)換及讀寫控制操作。磁盤控制器是主機和磁盤驅(qū)動器之間的接口，它的作用是實現(xiàn)主機和驅(qū)動器之間的數(shù)據(jù)格式的轉(zhuǎn)換和數(shù)據(jù)的傳送，同時控制驅(qū)動器的讀寫操作。其內(nèi)部又包含兩個接口，一個是對主機的接口，稱為系統(tǒng)級接口，它通過系統(tǒng)總線與主機交換信息；另一個是對硬盤的接口，稱為設(shè)備級接口，又稱為設(shè)備控制器，它接收主機的命令以控制設(shè)備的各種操作。盤片是存儲信息的載體。硬磁盤一般以鋁合金材料作基片，在它的表面涂敷一層磁介質(zhì)作為記錄媒體。盤片上的磁道分布如圖4-48所示，每個磁道的周長不等，而存儲的信息量卻相同。因此，內(nèi)圈磁道比外圈磁道的位密度大。盤片分為單面盤和雙面盤兩種，單面盤僅有一面能記錄信息，雙面盤兩面都能記錄信息。為了增大存儲容量，硬盤一般由多個盤片組成盤片組。圖4-48磁盤上的磁道分布3、硬磁盤的磁道記錄格式盤面的信息串行排列在磁道上，以字節(jié)為單位，若干相關(guān)的字節(jié)組成記錄塊，一系列的記錄塊又構(gòu)成一個“記錄”，一批相關(guān)的“記錄”組成了文件。為了便于尋址，數(shù)據(jù)塊在盤面上的分布遵循一定規(guī)律，稱為磁道記錄格式。①、定長記錄格式一個具有n個盤片的磁盤組，可將其n個面上同一半徑的磁道看成一個圓柱面，這些磁道存儲的信息叫做柱面信息。在移動磁頭組合盤中，磁頭定位機構(gòu)一次定位的磁道集合正好是一個柱面。信息的交換通常在圓柱面上進(jìn)行，柱面?zhèn)€數(shù)正好等于磁道數(shù)，故柱面號就是磁道號，而磁頭號則是盤面號。盤面又分成若干扇區(qū)，每條磁道就被分割成若干個扇段。扇段是磁盤尋址的最小單位。在定長記錄格式中，當(dāng)臺號決定后，磁盤尋址首先確定柱面，再選定磁頭，最后找到扇段。因此尋址用的磁盤地址應(yīng)由臺號/柱面磁道號/盤面號/扇段號等組成。定長格式的一個例子如圖4-49。盤片共分12個扇區(qū)，每個扇段內(nèi)只記錄一個數(shù)據(jù)塊，每個扇段開始由扇區(qū)標(biāo)志處讀出一個扇標(biāo)脈沖，標(biāo)志一個扇段的開始，0扇區(qū)標(biāo)志處再增加一個磁道標(biāo)志，指明是起始扇區(qū)。圖4-49定長磁道記錄格式每個扇段的頭部是空白段，起到隧道清除作用。序標(biāo)段以某種約定代碼作為數(shù)據(jù)塊的引導(dǎo)。數(shù)據(jù)段可寫入512字節(jié)，若不滿512字節(jié)，該扇段余下部分為空白；若超過512字節(jié)，則可占用幾個扇段。檢驗字段寫一個校驗字，常用循環(huán)冗余碼檢驗，尾空白段為全0或空白區(qū)，以示數(shù)據(jù)結(jié)束。②、不定長記錄格式在實際應(yīng)用中，信息常以文件形式存入磁盤。若文件長度不是定長記錄塊的整數(shù)倍時，往往造成記錄塊的浪費。不定長記錄格式可以根據(jù)需要來決定記錄塊的長度，可充分利用記錄區(qū)。不定長格式的一個例子如圖4-50。圖4-50不定長磁道記錄格式4、磁盤陣列存儲器廉價冗余磁盤陣列（RedundentArrayOfInexpensiveDisk，簡稱RAID）是用多臺磁盤存儲器組成的大容量外存儲子系統(tǒng)。其基礎(chǔ)是數(shù)據(jù)分塊技術(shù)，即在多個磁盤上交錯存放數(shù)據(jù)，使之可以并行存取。在陣列控制器的組織管理下，能實現(xiàn)數(shù)據(jù)的并行、交叉存儲或單獨存儲操作。由于陣列中的一部分磁盤存有冗余信息，一旦系統(tǒng)中某一磁盤失效，可以利用冗余信息重建用戶數(shù)據(jù)。術(shù)語RAID最早出現(xiàn)在一篇由加州大學(xué)伯克利分校的研究小組撰寫的論文中，此論文概括了各種RAID的配置和應(yīng)用，并介紹了現(xiàn)在仍在使用的RAID級定義。根據(jù)RAID所采用的方法不同，可以將其分為0~5六個級別（后來又有一些混合方案被開發(fā)出來）。這些級別不是簡單地表示層次關(guān)系，它們是基于3個共同特性的不同設(shè)計結(jié)構(gòu)。這3個特性為：（1）RAID由一組磁盤驅(qū)動器組成，在操作系統(tǒng)中被看作一個邏輯驅(qū)動器。（2）數(shù)據(jù)分布在一組物理磁盤上。（3）冗余磁盤的容量用來存儲奇偶校驗信息，這樣可以在磁盤損壞的情況下恢復(fù)信息。RAID0：（無冗余無校驗的數(shù)據(jù)分塊）RAID1：（鏡像磁盤陣列）RAID3：（采用奇偶校驗碼的磁盤陣列RAID5：（無專用校驗盤的奇偶校驗磁盤陣列）4.8.4磁帶存儲器磁帶存儲器也屬于磁表面存儲器，其記錄原理和記錄方式與磁盤存儲器是相同的。但從存取方式來看，磁帶存儲器必須按順序進(jìn)行存取，即磁帶上的文件都是按磁帶頭尾順序存放的，因此磁帶存取時間比磁盤長。磁帶存儲器是由磁帶和磁帶機兩部分組成。磁帶機的主要特點有以下三點：①、高容量，低密度。②、高可靠性。③、互換性好。磁帶機由記錄媒體、磁頭組件、走帶機構(gòu)和控制電路4個基本部分組成。磁帶是磁帶機的記錄媒體。磁頭組件是磁頭及磁頭裝載體的總稱，它由記錄磁頭、讀出磁頭、抹除磁頭、磁頭載體等組成。走帶機構(gòu)用以實現(xiàn)磁帶的移動和啟停，并在工作過程中保證磁帶以恒定的速度穩(wěn)定地通過磁頭?？刂齐娐分饕凶x、寫電路，帶盤及驅(qū)帶輪電機伺服控制電路，邏輯控制電路等。由于磁帶的寬度、道數(shù)、記錄方式、附加信息不同，就構(gòu)成了不同的記錄格式。這里主要介紹最常用的國際通用的1／2英寸9道啟停式標(biāo)準(zhǔn)磁帶的記錄格式。1／2英寸標(biāo)準(zhǔn)磁帶的記錄格式如圖4-51所示。圖4-51?英寸磁帶標(biāo)準(zhǔn)格式4.8.5光盤存儲器光盤存儲器由光盤驅(qū)動器和光盤片組成。光盤的記錄介質(zhì)采用磁光材料，驅(qū)動器讀寫頭是用半導(dǎo)體激光器和光路系統(tǒng)組成的光頭。利用激光在光記錄介質(zhì)上寫入信息，然后再利用激光讀出信息的技術(shù)稱為光存儲技術(shù)。光存儲技術(shù)工作原理是改變一個存儲單元的性質(zhì)，使其性質(zhì)的變化反映出被存儲的數(shù)據(jù)，識別這種性質(zhì)的變化，就可以讀出存儲數(shù)據(jù)。光存儲單元的性質(zhì)反映在光反射率或反射光極化方向上，若存儲單元的性質(zhì)改變，對應(yīng)二進(jìn)制信息“1”，若存儲單元的性質(zhì)不變，則對應(yīng)二進(jìn)制信息“0”。

光電檢測器能夠通過檢測出光強和光極性的變化來識別信息。與其他存儲器相比，光盤存儲器具有記錄密度高、存儲容量大、信息保存壽命長、工作穩(wěn)定可靠、環(huán)境要求低等特點。因此，它得到廣泛的應(yīng)用