《計算機系統(tǒng)結(jié)構(gòu)》 課件 第四章 存儲系統(tǒng)

第四章存儲系統(tǒng)主講教師：單博煒存儲器是用于存放程序和數(shù)據(jù)的計算機核心部件之一，其性能直接關(guān)系到整個計算機系統(tǒng)性能的高低。存儲系統(tǒng)是指存儲器硬件以及管理存儲器的軟、硬件，對存儲系統(tǒng)的基本要求是大容量、高速度和低成本。如何以合理的價格設(shè)計容量和速度滿足計算機系統(tǒng)要求的存儲器系統(tǒng)，始終是計算機體系結(jié)構(gòu)設(shè)計中的關(guān)鍵問題之一。本章將著重介紹存儲系統(tǒng)的基本原理及并行存儲器、虛擬存儲器、高速緩沖存儲器(Cache)的有關(guān)技術(shù)存儲系統(tǒng)及性能存儲器的三個主要指標是：容量、速度和價格。存儲器容量SM=W·l·m。其中，W為單個存儲體的字長，l為單個存儲體的字數(shù)，m為并行工作的存儲體的個數(shù)。也就是說，存儲器的容量正比于單個存儲體的字長、單個存儲體的字數(shù)和并行工作的存儲體的個數(shù)。存儲器的速度可以用訪問時間TA、存儲周期TB，或頻寬Bm來描述。Bm是存儲器被連續(xù)訪問時，可以提供的數(shù)據(jù)傳送速率，通常用傳送信息的位數(shù)（或字節(jié)數(shù)）每秒來衡量。單體的Bm=W/TM，m個存儲體并行工作時可達到的最大頻寬Bm=W·m/TM。以上指的都是理想情況為了下存儲器所能達到的最大頻寬，由于存儲器不一定總能連續(xù)滿負荷的工作，所以，實際頻寬往往要低于最大頻寬。存儲器的價格可以用總價格C或每位價格c來表示。具有SM位的存儲器每位價格c=C/SM。存儲器價格包含了存儲單元本身及為該存儲器操作所必需的外圍電路的價格。人們對存儲器的要求是“容量大、速度快、價格低”，然而這三個要求是相互矛盾的。通過研究不同的存儲器實現(xiàn)技術(shù)可以發(fā)現(xiàn)，存儲器的速度越快，價格就越高；存儲器的容量越大，速度就越慢，價格也越高。解決上述矛盾在組成上引入并行和重疊技術(shù)，構(gòu)成并行主存系統(tǒng)。在保持每位價格基本不變的情

況下，能使主存的頻寬得到較大的提高。改進存儲器的系統(tǒng)結(jié)構(gòu)，發(fā)展多層次存儲體系（或稱存儲系統(tǒng)）。所謂存儲體系，是指計算機系統(tǒng)的存儲器部分由多種不同的存儲器構(gòu)成，由操作系統(tǒng)和硬件技術(shù)來完成程序的定位，使之成為一個完整的整體。由于它由多級存儲器構(gòu)成，故又稱之為存儲層次。其中，M1，M2，…，Mn為用不同技術(shù)實現(xiàn)的存儲器．它們之間以塊或頁面為單位傳送數(shù)據(jù)。最靠近CPU的M1速度最快，容量最小，每位價格最高．而離CPU最遠的Mn則相反，速度最慢，容量最大，每位價格最低。若設(shè)ci、TAi、SMi分別表示Mi的每位價格、訪問時間和存儲容量，則多級存儲層次中任意相鄰兩級之間存在以下關(guān)系：ci>ci+1TAi<TA(i+1)SMi<SM(i+1)層次存儲系統(tǒng)設(shè)計追求的目標是：從CPU來看，該存儲體系是一個整體，且具有接近于M1的速度和Mn的容量和價格。程序訪問的局部性原理絕大多數(shù)程序訪問的指令和數(shù)據(jù)是相對簇聚的，它包括時間上的局部性和空間上的局部性。時間局部性是指在近期將要用到的信息很可能是現(xiàn)在正在使用的信息，這主要是程序循環(huán)造成的，即循環(huán)中的語句要被重復(fù)執(zhí)行?？臻g局部性是指在近期將要用到的信息很可能與現(xiàn)在正在使用的信息在程序空間上是相鄰或相近的，這主要是由于指令通常是按執(zhí)行順序存儲，以及數(shù)據(jù)經(jīng)常以向量、陣列、樹、表格等形式簇聚的存儲所致。存儲系統(tǒng)的性能參數(shù)我們以圖4.2所示兩級存儲層次結(jié)構(gòu)為例分析存儲系統(tǒng)的性能。存儲層次由M1和M2兩個存儲器構(gòu)成，假設(shè)M1的容量、訪問時間和每位價格分別為SM1、TA1和c1，M2的對應(yīng)參數(shù)為SM2、TA2和c2，。每位平均價格c當SM1<<SM2時，有c≈c2

2.命中率H命中率為CPU產(chǎn)生的邏輯地址流在M1中訪問到指定信息的概率。命中率一般用模擬的方法來確定，也就是通過模擬執(zhí)行一組有代表性的程序，分別記錄下訪問M1和M2的次數(shù)R1和R2，則命中率為命中率H與程序的訪存地址流、M1和M2之間所采用的地址映像關(guān)系、替換算法及M1的容量都有很大的關(guān)系。顯然，H越接近于1越好。3.等效訪問時間TATA=HTAl+(l–H)TA2當命中率H接近于1時，等效訪問時間TA就接近于速度比較快的M1存儲器的訪問時間TA1。因此，命中率H越大，整個存儲系統(tǒng)的工作速度就越高，越接近于M1的工作速度。4.存儲層次訪問效率e兩級存儲層次的訪問效率為

為兩級存儲器的訪問時間比。5.復(fù)雜存儲系統(tǒng)的性能參數(shù)(l)多級存儲體系的性能若存儲體系由行級存儲器構(gòu)成，如圖4.1所示。設(shè)Mi的訪問時間、訪問次數(shù)和命中率分別表示為TAi、Ri和Hi，則有等效訪問時間TA為TA=H1TAl+(l–H)H2TA2+(l–H1

)(l–H2)H3TA3+… +(l–H1

)(l–H2)…(l–Hn-1)TAn(2)兩級分類存儲體系的性能將Cache存儲器分為指令Cache(I-Cache)和數(shù)據(jù)Cache(D-Cache)，如圖4.3所示設(shè)指令Cache和數(shù)據(jù)Cache的訪問時間均為Tc，主存的訪問時間為Tm，指令Cache的命中率為H1，數(shù)據(jù)Cache的命中率為HD，CPU訪存取指的比例為f1，則存儲體系的等效訪問時間為TA=f1(H1Tc+(l–H1

)Tm)+(l–f1

)(HDTc+(1-HD)Tm)[例4.1]某機是由高速緩存與主存組成的兩級存儲系統(tǒng)，高速緩存訪問時間Tc=50ns，主存訪問時間Tc=400ns，訪問Cache的命中率為0.96。問：(l)系統(tǒng)的等效訪問時間TA為多少？(2)如果將高速緩存分為指令Cache與數(shù)據(jù)Cache，使等效訪問時間減小了10%。在所有的訪存操作中有20%是訪問指令Cache，而訪問指令Cache的命中率仍為0.96(假設(shè)不考慮寫操作一致性的問題)，問數(shù)據(jù)Cache的訪問命中率應(yīng)是多少？解：(l)系統(tǒng)的等效訪問時間為

TA=HTc+(l–H)Tm=0.96×50+(1-0.96)×400=64ns(2)設(shè)改進后的數(shù)據(jù)Cache的命中率為HD，CPU訪存取指的比例為f1，則TA=f1(H1Tc+(l–H1

)Tm)+(l–f1

)(HDTc+(1-HD)Tm)64×(1-10%)=0.2(0.96×50+(1-0.96)×400)+(1-0.2)(HD×50+(1-HD)×400) 280HD=275.2

HD≈0.983存儲系統(tǒng)的相關(guān)問題在多層次存儲體系中的相鄰層次之間不可避免地存在信息調(diào)度的操作，對于每一個層次都將涉及到以下四個問題。把低層存儲器的一個信息塊調(diào)入靠近CPU的高一層存儲器時，可以放到哪些位置

上？（映像規(guī)則）如果所訪問的信息在高一層存儲器中時，如何找到該信息？（查找算法）在某層存儲空間已滿而對該存儲器訪問失效時，調(diào)入塊應(yīng)替換哪一塊？（替換算法）對存儲器進行寫訪問時，應(yīng)進行哪些操作？（寫策略）搞清楚這些問題，對于理解一個具體存儲層次的工作原理以及設(shè)計時的考慮是十分重要的。并行主存系統(tǒng)主存系統(tǒng)的頻寬分析單體多字存儲器交叉訪問存儲器提高存儲器頻寬的方法根據(jù)主存中存儲體的個數(shù)以及CPU訪問主存一次所能讀出的信息的位數(shù)1．單體單字存儲器這種存儲器只有一個存儲體，其存儲器字長為W位，一次可以訪問一個存儲器字。所以主存最大頻寬Bm=W/TM,一個存儲器字W和CPU字長w相等，即W=w，我們稱這種主存為單體單字存儲器。圖4.4所示為單體單字存儲器。2．單體多字存儲器這種存儲器只有一個存儲體，其存儲器字長為W位，一次可以訪問一個存儲器字。但一個存儲器字包含n個CPU字，即W=nw，主存在一個存儲周期內(nèi)可以讀出n個CPU字，所以主存最大頻寬Bm=W/TM=nw/TM。我們稱這種主存為單體多字存儲器。圖4.5所示為n=4的單體多字存儲器。3.多體單字交叉存取的存儲器存儲器有m個存儲體，每個存儲體都是一個CPU字的寬度，即W=w。對存儲單元采用按模m交叉編址，故稱它為多體單字交叉存取的存儲器。主存在一個存儲周期內(nèi)可以按同時啟動或分時啟動方式讀出m個CPU字，所以主存最大頻寬Bm=W/TM=nw/TM。根據(jù)應(yīng)用特點，這種交叉編址有低位交叉和高位交叉兩種，后面將進一步介紹。圖4.6所示為低位交叉編址m=4的多體交叉存儲器。4.多體多字交叉存儲器它將多分體并行存取與單體多字相結(jié)合，存儲器有m個存儲體，每個存儲體都是n個CPU字的寬度，即W=nw。主存在一個存儲周期內(nèi)可以從每個存儲體中讀出n個CPU字，主存的最大頻寬Bm=mW/TM=mnw/TM。。我們稱這種主存為多體多字交叉存儲器。我們將能并行讀出多個CPU字的單體多字、多體單字交叉、多體多字交叉存取的主存系統(tǒng)稱為并行主存系統(tǒng)。4.2.2單體多字存儲器單體多字并行存儲器利用將存儲器的存儲字字長增加n倍，存放n個指令字或數(shù)據(jù)字，從而實現(xiàn)在一個存儲周期內(nèi)能訪問到n個指令字或數(shù)據(jù)字，以此增加存儲器的頻寬。單體多字并行存儲器的優(yōu)點是實現(xiàn)簡單，缺點是訪問沖突概率大。訪問沖突主要來自以下幾個方面。取指令沖突

單體多字并行存儲器一次取n個指令字，能很好地支持程序的順序執(zhí)行。但是，若一個存儲字中有一個轉(zhuǎn)移指令字，那么存儲字中轉(zhuǎn)移指令后面被同時預(yù)取的幾個指令字只能作廢。2.讀操作數(shù)沖突

單體多字并行存儲器一次取n個數(shù)據(jù)字不一定都是要執(zhí)行的指令所需要的操作數(shù)，而當前執(zhí)行指令需要的全部操作數(shù)也可能不包含在一個存儲字中而不能被一次取出。因為數(shù)據(jù)存放的隨機性比程序指令存放的隨機性大，所以讀操作數(shù)沖突的概率較大。3.寫數(shù)據(jù)沖突

單體多字并行存儲器必須是湊齊了以個數(shù)據(jù)字之后才能作為一個存儲字一次寫入存儲

器。只寫一個數(shù)據(jù)宇時，需要先把屬于一個存儲字的玎個數(shù)讀到數(shù)據(jù)寄存器中，改寫其中一

個字，然后再把整個存儲字寫回存儲器。4.讀寫沖突

當要讀出的數(shù)據(jù)字和要寫入存儲器的數(shù)據(jù)字同處于一個存儲字中時，讀和寫的操作就無法再同一個存儲周期中完成。4.2.3交叉訪問存儲器一個存儲器通常對存儲單元是順序編址的。如果主存采用多體單字方式組成，對存儲器m個存儲體的存儲單元采用m體交叉編址，組成交叉訪問存儲器。交叉訪問存儲器通常有兩種交叉編址方式：一是地址碼的高位交叉編址，二是地址碼的低位交叉編址。高位交叉編址存儲器的編址方式能很方便地擴展常規(guī)主存的容量。但只有低位交叉編址存儲器才能提高存儲器的實際頻寬，有效地解決并行訪問沖突問題，才能作為并行存儲器的一種工作方式高位交叉訪問存儲器高位交叉訪問存儲器的結(jié)構(gòu)如圖4.7所示。如果主存空間為N=2n字，那么訪問該存儲器的地址為n位。若存儲器由2m個存儲體構(gòu)成（稱為模m多體交叉存儲器），則用地址碼的高m位來選擇不同的存儲體，低n-m位為存儲體的體內(nèi)地址。當處理機發(fā)出的訪存地址高m位不相同時，便可對存儲器內(nèi)不同的存儲體進行并行存?。ㄟ@里的并行性指的是并發(fā)性）。當處理機發(fā)出的訪存地址高m位相同，即訪問同一存儲體時．就不能并行操作了，我們稱之為存儲器的分體沖突。在最好的情況下，即一個模m的多體交叉訪問存儲器在不發(fā)生分體沖突時的頻寬是單體存儲器頻寬的m倍。低位交叉訪問存儲器低位交叉訪問存儲器的結(jié)構(gòu)如圖4.8所示。如果主存空間為N=2n字．那么訪問該存儲器的地址為n位，若存儲器由2m個存儲體構(gòu)成，則用地址碼的低m位來選擇不同的存儲體，高n-m位為體內(nèi)地址。當處理機發(fā)出的訪存地址低m位不相同時，便可對存儲器內(nèi)不同的存儲體進行并行存?。ㄟ@里的并行性指的是并發(fā)性）。當處理機發(fā)出的訪存地址低m位相同，即訪問同一存儲體時，則因發(fā)生存儲器分體沖突而不能并行操作。4.2.4提高存儲器頻寬的方法由前述交叉訪問的并行主存系統(tǒng)可達到的最大頻寬為Bm=mW/TM，由此可見提高模m的值，應(yīng)能提高主存系統(tǒng)的頻寬Bm，但Bm并不是隨m值增大而線性提高。工程實現(xiàn)上由于模m越高，存儲器數(shù)據(jù)總線越長，總線上并聯(lián)的存儲芯片越多，負載越重，有時還不得不增加門的級數(shù)，這些都會使傳輸延遲增加；系統(tǒng)效率問題。對模m交叉，如果都是順序地取指令，效率可提高m倍．但實際中指令并不總是順序執(zhí)行的，一旦出現(xiàn)轉(zhuǎn)移，效率就會下降．轉(zhuǎn)移頻度越高．效率下降越明顯。數(shù)據(jù)的順序性比指令差，實際的頻寬可能更低一些；分析程序轉(zhuǎn)移對其頻寬的影響當轉(zhuǎn)移概率λ>0.3時，m=4、8、16的B差別不大，即在這種情況下，模m取值再大，對系統(tǒng)效率也并沒有帶來多大的好處；而在λ<0.1時，m值的大小對B的改進則會有顯著的影響。為了降低轉(zhuǎn)移概率λ，就要求在程序中盡量少使用轉(zhuǎn)移指令。

4.3虛擬存儲器虛擬存儲器的概念是1961年由英國曼徹斯特大學(xué)Kilburn等人提出的主要針對主存的容量與價格之間的矛盾，為解決主存容量不能滿足程序運行的需要而引入的。它由價格較貴、速度較快、容量較小的主存儲器M1和一個價格低廉、速度較慢、容量很大的輔助存儲器M2（通常是硬盤）組成。在系統(tǒng)軟件和輔助硬件的管理下，使應(yīng)用程序員擁有一個比主存容量大得多的虛擬存儲空間，而程序又可以按接近主存的工作速度在這個虛擬存儲器上運行。在虛擬存儲技術(shù)中，把程序經(jīng)編譯生成的訪存地址稱為虛擬地址或虛地址，程序代碼運行時，必須先把虛地址轉(zhuǎn)換成主存物理地址（或稱主存實地址），才能按實地址訪問主存。為實現(xiàn)將虛存單元在主存中定位，遵循某種規(guī)則（算法）建立虛擬地址與物理地址之間的對應(yīng)關(guān)系稱為地址映像。程序在運行時按照某種地址映像方式裝入主存，虛擬存儲系統(tǒng)杷虛擬地址轉(zhuǎn)換成主存物理地址的過程稱為地址變換。如果經(jīng)地址變換發(fā)現(xiàn)虛地址所對應(yīng)的數(shù)據(jù)不在主存中（未命中），則需要訪問磁盤存儲器。如果有新的數(shù)據(jù)塊要調(diào)入主存，但按地址映像關(guān)系對應(yīng)的主存區(qū)域已無空閑位置時，則要采用某些替換算法來確定新數(shù)據(jù)塊調(diào)入主存后替換已有數(shù)據(jù)塊的位置。地址映像與變換以及替換算法是虛擬存儲器的重要技術(shù)，虛擬存儲器的管理方式及地址變換段式虛擬存儲器、頁式虛擬存儲器段頁式虛擬存儲器段式虛擬存儲器根據(jù)結(jié)構(gòu)化程序設(shè)計思想，一個程序可由多個在邏輯上相對獨立的模塊組成。這些模塊可以是子程序、過程或函數(shù)，也可以是向量、數(shù)組、表等各種數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)集合。各模塊大小可以不同，每個模塊內(nèi)都從地址0開始編址并分別構(gòu)成單獨的程序段。段式管理就是將程序空間按模塊分段，主存空間按段分配的存儲管理方式。一個段占用的存儲容量成為段長，所以各段的段長可不同。采用段式管理的虛擬存儲器中，每個程序都用一個“段表”來存放該程序各段裝入主存的相關(guān)信息。每個段占用段表中的一行，存放該段的段長和該段在主存中的起始地址等內(nèi)容。段表組成結(jié)構(gòu)如圖4.10所示，段表中各段參數(shù)段號。段號是各段用戶或數(shù)據(jù)結(jié)構(gòu)格式名稱。也可以使用段的編號，這時由于段表行號與段序號存在的對應(yīng)關(guān)系，段表中可以不設(shè)該字段。起始地址。起始地址是該段在主存中的起始位置，即基址值。裝入位。裝入位用來表示該段是否已裝入主存。1表示裝入，0表示未裝入，裝入位隨該段是否調(diào)入主存而變化。段長。段長表示該段的大小，可用于判斷訪問地址是否越界。段式虛擬存儲器通過段表完成地址映像并結(jié)合段表基址寄存器實現(xiàn)地址變換，一個程序的各段裝入主存時，段與段之間并不一定是連續(xù)的，主存中只要有一個能容納某個段的空間，就可將該段裝入這個空間位置，并在段表中記載該段裝入主存的有關(guān)信息。段式虛擬存儲器的地址變換一個多用戶虛地址由用戶號U（或程序號）、段號S和段內(nèi)偏移D等三部分組成。若系統(tǒng)巾最多可同時有N道程序在主存中，可以在CPU中設(shè)置由N個段表基址寄存器組成的段表基址寄存器堆，每道程序由用戶號U指明使用其中哪個段表基址寄存器。段表基址寄存器中的段表基地址字段指向該道程序的段表在主存中的起始地址AS。段表長度字段指明該道程序所用段表的行數(shù)，即程序段的段數(shù)。將AS與虛地址中的段號S相加就得到這個程序段的段表地址，按這個段表地址訪問段表，就能得到該程序段有關(guān)的全部信息。段式虛擬存儲器的特點段式管理可使編程模塊化、結(jié)構(gòu)化，從而可以并行編程，縮短程序設(shè)計周期：段與模塊對應(yīng)并相互獨立，便于各段單獨修改和編譯。段式管理便于實現(xiàn)公用信息的存儲和使用。多任務(wù)公用的程序或數(shù)據(jù)段不用在主存中重復(fù)存儲，只需在每個任務(wù)的段表中使用公用段的名稱和同樣的基址值即可。段式管理便于實現(xiàn)以段為單位的存儲保護。例如，可設(shè)置常數(shù)段只讀不寫；可變數(shù)據(jù)段只能讀、寫，不能作為指令執(zhí)行；子程序段只能執(zhí)行，不能修改等，若違反就會產(chǎn)生軟件中斷。由于各段的段長不等，調(diào)入主存時每段要占用一個連續(xù)的主存空間，因此隨著各段的調(diào)入調(diào)出，主存中各段之間會存在很多空閑存儲區(qū)域。這些不足以容納一個段的空閑存儲區(qū)稱為段間零頭。段間零頭會使主存空間利用率降低，而消除段間零頭的操作又將增加系統(tǒng)運行的時間開銷。由于各段的民度依程序的邏輯可以是任意的，且程序段在主存中的起點也是隨意的，這就要求段表中主存的起始地址和段長這兩個字段的長度都要很長。這樣，既增加了段表本身的存儲開銷，又增加了虛實地址變換的時間開銷，使段式管理復(fù)雜費時。頁式虛擬存儲器將主存空間和程序空間分別機械地劃分成同樣大小的頁面，主存空間按物理地址順序?qū)摚▽嶍摚┚幪枺次锢眄撎柣驅(qū)嶍撎枺?，程序空間按虛擬地址對頁（虛頁）編號（即邏輯頁號或虛頁號），程序以頁為單位調(diào)進并裝入主存中不同的頁面位置。頁式管理就是將程序空間按頁劃分，主存空間按頁分配的存儲管理方式。地址空間的頁面劃分和頁的大小是由虛擬存儲器的頁式管理的軟硬件來實現(xiàn)的。在一般計算機系統(tǒng)中，頁的大小為lKB～16KB。采用頁式管理虛擬存儲器中，每個程序都用一個“頁表”來存放該程序各頁裝入主存的有關(guān)信息。每個虛頁占用頁表中的一行，存放該頁的虛頁號及該頁在主存中的實頁號等內(nèi)容。頁表組成結(jié)構(gòu)如圖4.12所示，虛頁號。是程序空間中各頁面編號。由于虛頁號是順序編寫的，故頁表內(nèi)該項可以不設(shè)。主存實頁號。該虛頁裝入主存后所在主存實頁的編號。裝入位。用來表示該虛頁是否已裝入主存。l表示裝入，0表示未裝入，裝入位隨該頁是否調(diào)入主存而變化。地址映像與變換頁式虛擬存儲器的地址變換如圖4.13所示。一個多用戶虛地址N，由用戶號U(或程序號)、頁號P和頁內(nèi)偏移D等三部分組成。由于虛頁和實頁的大小相同，因此，一個虛地址變換成主存實地址時，虛地址的頁內(nèi)偏移D同實地址的頁內(nèi)偏移d是相同的，需要變換的只是把虛地址中的虛頁號P變換成主存實地址的實頁號p。這樣可大大縮短進行變換的地址的長度，既節(jié)省了硬件和存儲開銷，又能加快地址變換的速度。在CPU內(nèi)部有一個頁表基址寄存器堆，每個用戶（程序）通過虛地址中的用戶號U指明使用其中哪一個頁表基址寄存器。頁表基址寄存器中存放該程序的頁表在主存中的基地址AP。虛地址中的虛頁號P就對應(yīng)頁表中記載該虛頁有關(guān)信息的行，只要把頁表基地址AP同虛頁號P相加就得到要訪問的頁表地址。按這個頁表地址訪問頁表，可得到相應(yīng)虛頁的有關(guān)信息。若裝入位顯示該虛頁已經(jīng)裝入主存，則將頁表中該虛頁對應(yīng)的主存實頁號p同虛地址中的頁內(nèi)偏移D直接拼接起來就得到主存實地址nP。頁式虛擬存儲器的特點存儲管理簡單。主存空間利用率較高。地址變換速度較快。程序的鏈接和調(diào)度不方便。程序和數(shù)據(jù)的保護不方便。頁表行的長度雖然比段表行長度要短，但頁表的行數(shù)很多，需要占用很大的存儲空間。段頁式虛擬存儲器它是段式管理和頁式管理相結(jié)合的一種存儲管理方式，具有段式管理方式和頁式管理方式二者的綜合優(yōu)點。段頁式管理的基本思想是將主存空間等分成頁，對程序空間按模塊分段，段內(nèi)再劃分成與實頁同樣大小的頁，程序以頁為單位進行調(diào)度。因此，段頁式管理就是將程序空間按模塊分段、段內(nèi)分頁、主存空間按頁分配的存儲管理方式。由于采用段內(nèi)分頁方式，段頁式與純段式的一個顯著區(qū)別在于段的起點不是任意的，而必須是實存中頁面的起點。在采用段頁式管理的虛擬存儲器中，每道程序（任務(wù)）通過一個段表和一組頁表（每段一個頁表）進行定位。段表中的每行對應(yīng)一個段，行內(nèi)記錄該段頁表的長度和頁表的起始地址，頁表長度就是該段的頁數(shù)。頁表則指明該段各頁是否裝入主存，并給出該段各頁在主存中的實頁號及是否被修改等信息。地址映像與變換段頁式虛擬存儲器通過一個段表和一組頁表完成地址映像并結(jié)合段表基址寄存器實現(xiàn)地址變換，其地址映像如圖4.14所示。段頁式虛擬存儲器的地址變址如圖4.15所示。一個多用戶虛地址N，由用戶號U、段號S、虛頁號P和頁內(nèi)偏移D等四部分組成。虛地址變換成主存實地址時要先根據(jù)段號查段表，得到該段的頁表起始地址和頁表長度，再根據(jù)虛頁號查頁表，得到該虛頁裝入主存頁面的實頁號p，將實頁號p與頁內(nèi)偏移D拼接即得到主存實地址段頁式虛擬存儲器的特點段頁式虛擬存儲器采用段式與頁式相結(jié)合的管理方式，使其同時獲得段式管理方式和頁式管理方式的優(yōu)點——既具有段式虛擬存儲器保證程序段和數(shù)據(jù)段的邏輯獨立性，使信息的共享和保護比較方便、程序可以在執(zhí)行時再動態(tài)鏈接等優(yōu)點，同時也具有頁式虛擬存儲器的主存空間利用率較高、固定大小的頁面調(diào)動有利于支持對磁盤存儲器的管理等優(yōu)點。段頁式虛擬存儲器的缺點是地址變換過程查表訪存次數(shù)多，使訪問速度降低。4.3.3替換算法處理機要用到的指令或數(shù)據(jù)不在主存中時會產(chǎn)生頁面失效，此時應(yīng)從輔存中將包含該指令或數(shù)據(jù)的虛頁調(diào)入主存。通常虛存空間遠大于主存空間，如果全部主存空間被虛頁占滿后再出現(xiàn)頁面失效，則將輔存的一頁調(diào)入主存時就會發(fā)生實頁沖突（發(fā)生兩個以上的虛頁想要進入主存中同一個頁面位置的現(xiàn)象被稱為發(fā)生了頁面爭用或賓頁沖突）。在頁面失效和頁面爭用同時發(fā)生時，需要讓主存釋放某個頁面才能接納由輔存中調(diào)進的新頁。選擇主存中哪一頁作為被替換頁面的規(guī)則稱為頁面替換算法。常見的替換算法有：隨機算法、先進先出算法、近期最少使用算法或近期最久未用過算法、優(yōu)化替換算法等1．隨機算法用軟件或硬件的隨機數(shù)產(chǎn)生器來形成主存中要被替換的虛頁號。這種算法簡單，易于實現(xiàn)，但沒有利用反映主存使用情況的“歷史”信息，不能體現(xiàn)程序的局部性，使主存命中率很低，所以很少使用。2．先進先出算法

FIFO，F(xiàn)irst-InFirst-out選擇最早裝入主存的虛頁作為被替換的頁。實現(xiàn)時，在操作系統(tǒng)為實現(xiàn)主存管理而建立的主存頁面表中，給每個實頁設(shè)置一個計數(shù)器字段。當一個虛頁調(diào)入主存時，讓該頁的計數(shù)器清零，其他已裝入主存的虛頁的計數(shù)值加1。替換時，找出計數(shù)值最大的裝入頁就是最先進入主存而現(xiàn)在將被替換掉的虛頁。3.近期最少使用算法

LRU，LeastRecentlyUsed選擇過去近期最少訪問的虛頁作為被替換的頁。這種算法能比較正確地反映程序的局部性，因為一般近期最少使用的頁在未來一段時間內(nèi)也將很少被訪問。此算法在實現(xiàn)時，需在頁表或目錄表中對每個實頁增設(shè)一個字長很長的“使用次數(shù)計數(shù)器”字段，某個頁被訪問一次，該頁的計數(shù)器字段加1，使用次數(shù)最少（即計數(shù)值最?。┑捻撌潜惶鎿Q頁。主存頁面表4.優(yōu)化替換算法

OPT，OptimalReplacementAlgorithm選擇將來一段時間內(nèi)最久不被訪問的頁作為被替換頁。它需要在時刻t找出主存中每個頁將要用到的時刻ti，然后選擇其中ti-t最大的那一頁作為被替換頁。顯然，只有讓程序運行過一遍，得到程序訪問的全部虛頁號序列（稱為虛頁地址流），才能找到為實現(xiàn)這種替換算法所需要的各頁使用信息，這是不現(xiàn)實的。因此，優(yōu)化替換算法是一種理想的算法，它的命中率是最高的。它的意義在于可以作為評價其他替換算法好壞的標準，看看哪種替換算法能使主存的命中率最接近于優(yōu)化替換算法。影響主存命中率的因素替換算法虛頁地址流頁面大小主存容量等因素。替換算法對命中率的影響設(shè)有一道程序，由1～5共五個虛頁，程序執(zhí)行時的訪存虛頁地址流為2，3，2，1，5，2，4，5，3，2，5，2分別采用FIFO、LRU、OPT三種替換算法對這三頁的使用情況和替換過程如圖4.17所示FIFO算法的命中率為3/12=0.25，OPT算法的命中率為6/12=0.5，LRU算法的命中率為5/12=0.417，非常接近于OPT算法的命中率。這反映了替換算法對命中率的影響，同時表明LRU算法要優(yōu)于FIFO算法，所以在實際中LRU算法得到更多應(yīng)用。頁地址流對命中率的影響假設(shè)有一個循環(huán)程序，共有四個虛頁，如果分配給該程序三個主存實頁，則用FIFO、LRU和OPT替換算法對這三個主存實頁的使用和替換過程如圖4.18所示。結(jié)果顯示OPT算法命中三次．而LRU和FIFO算法均沒有命中。因為它們使程序在按虛頁地址流訪問主存過程中，每次發(fā)生替換時的被替換頁就是下次要使用的頁，從而導(dǎo)致連續(xù)不斷的頁面失效，產(chǎn)生所謂的顛簸現(xiàn)象。這表明命中率與頁地址流的狀況有關(guān)。這種信息交換在嚴重時可使系統(tǒng)只忙于交換，而無法對問題進行處理，這種現(xiàn)象被稱為“顛簸”。程序的主存頁數(shù)對命中率的影響一般來說．分配給程序的主存頁數(shù)越多，虛頁裝入主存的機會越多，命中率也就可能越高，但實際能否真正提高命中率還與替換算法的類型有關(guān)。圖4.19所示反映的就是當分配給程序的主存頁數(shù)由三頁增加到四頁時，用FIFO算法反而使命中率由3/12降低到2/12．而LRU算法卻能保證隨著分配給程序的主存頁數(shù)的增加，使命中率得到提高或保持不變。堆棧型替換算法堆棧型替換算法的定義如下：設(shè)A是長度為L的任意一個虛頁地址流，t為已處理過t-1個虛頁的時間點，n為分配給該虛頁地址流的主存實頁數(shù)，Bt(n)表示在t時間點、在n個主存實頁中的虛頁集合，Lt表示到t時間點已處理過的虛頁地址流中虛頁號相異的頁數(shù)。如果替換算法具有下列包含性質(zhì)：

當n<Lt時，Bt(n)Bt(n+1)

當n≥Lt時，Bt(n)=Bt(n+1)則此替換算法為堆棧型替換算法。對于LRU算法．在主存中保留的是n個最近使用的頁面．它們又總是被包含在n+1個最近使用的頁面之中，所以LRU算法是堆棧型算法。同理，可說明OPT算法也是堆棧型替換算法。而對于FIFO算法，從圖4.19中可看到B7(3)={1，2，5}，而B7(4)={2，3，4，5}，所以B7(3)B7(4)。FIFO算法不具有任何時刻都能滿足上述包含性質(zhì)的特征，所以它不是堆棧型替換算法。堆棧型替換算法的模擬處理技術(shù)用堆棧處理技術(shù)對地址流進行模擬處理時，主存在t時間點的狀況用堆棧St表示。St是Lt個不同虛頁面號在堆棧中的有序集，St(1)是St的棧頂項，St(2)是St的次棧頂項，以此類推。按照堆棧型算法具有的包含性質(zhì)，必有n<Lt時，Bt(n)={St(1)，St(2)，…，St(n)}n≥Lt時，Bt(n)={St(1)，St(2)，…，St(Lt)}這樣，給程序分配的n個實頁中所存放的虛頁號就由St的前n項決定。而頁地址流A在t時間點的At頁是否命中，只需看St-1的前n項中是否有At，若有則命中。因此，經(jīng)過一次模擬處理，獲得St(1)、St(2)、…、St(Lt)之后，就能同時知道對應(yīng)于不同n值時的主存命中率，從而對該道程序為達到所需命中率確定應(yīng)分配的主存頁數(shù)提供依據(jù)。對于不同的堆棧型替換算法，堆棧St各項的改變過程是不同的。例如，LRU算法是把剛訪問過的虛頁號置于棧頂，而把最久未被訪問的虛頁號置于棧底。確切地說，t時間點訪問的頁At，若AtSt-1，則把At壓入堆棧使之成為St(1)，而St-1各項都下推一個位置；若At∈St-1，則把它由St-1中取出，壓入棧頂成為St(1)，在At之下各項的位置不動，而在At之上的各項都下推一個位置。[例4.2]對圖4.17給出的訪存虛頁地址流，采用LRU算法進行堆棧模擬處理。分別求出分配給該程序主存實頁數(shù)為1、2、3、4和5頁時的主存命中率。使用LRU算法由圖4.20中的St可確定對應(yīng)這個虛頁地址流，當分配主存頁數(shù)n取不同值時的命中率H如下所示：堆棧型替換算法的發(fā)展基于堆棧型替換算法具有隨分配給該道程序的實頁數(shù)n的增加．命中率H會單調(diào)上升的基本特點，可對LRU算法加以改進和發(fā)展，提出使系統(tǒng)性能可以更優(yōu)的動態(tài)頁面調(diào)度算法，即根據(jù)各道程序運行中主存頁面失效率的高低，由操作系統(tǒng)動態(tài)調(diào)節(jié)分配給每道程序的實頁數(shù)。當主存頁面失效率超過某個限值時就自動增加分配給該道程序的主存頁數(shù)來提高其命中率；而當主存頁面失效率低于某個限值時就自動減少分配給該道程序的主存頁數(shù)，以便釋放出這部分主存頁面位置來給其他程序用，從而使整個系統(tǒng)整體的主存命中率和主存利用率得到提高。[例4.3]一個程序由五個虛頁組成，采用LRU替換算法，在程序執(zhí)行過程中依次訪問的頁地址流為4，5，3，2，5，1，3，2，3，5，1，3。(1)可能的最高頁命中率是多少？(2)至少分配給該程序多少個主存頁面才能獲得最高頁命中率？(3)如果在程序執(zhí)行過程中每訪問一個頁面，平均要對該頁面內(nèi)的存儲單元訪問1024次，求訪問存儲單元的命中率。解：(1)由于在頁地址流中互不相同的頁面共有五個，所以最多分配五個主存頁面就可獲得最高頁命中率，可能的最高頁命中率為(2)因為LRU替換算法為堆棧型替換算法，可采用堆棧處理技術(shù)對該頁地址流進行模擬處理，其處理過程如圖4.21所示。至少要分配給該程序四個主存頁面(3)訪問存儲單元的命中率為值得說明的是，盡管LRU屬于堆棧型替換算法，但分配的實頁數(shù)n并不是越多越好，當命中率H達到飽和后，實頁數(shù)的增加不僅不會提高命中率，反而會使主存的利用率下降。虛擬存儲器中的相關(guān)技術(shù)1．多級頁表技術(shù)2．加快地址變換的技術(shù)1．多級頁表技術(shù)在頁式虛擬存儲器和段頁式虛擬存儲器中，頁表的大小很可能超過一個頁面，此時頁表可能分存于主存中不連續(xù)的頁面位置上。這樣，描述基于整個頁表連續(xù)存儲情況下的由頁表起始地址加頁號得到該頁在頁表中對應(yīng)行的查表方式就會出錯。例如，虛地址為20位，頁內(nèi)地址為8位，即

則頁表就需要2P=212行，而頁面大小為2D=212個存儲單元，如果每個頁表行占用一個存儲單元，則有2P/2D=212/28=24=16，該頁表要分存于16個頁面。為此要建立多級頁表，用頁表基址寄存器指明第一級頁表的基址，用第一級頁表中各行的地址字段指明各第二級頁表的基址，……，以此類推。2．加快地址變換的技術(shù)由于多用戶虛存空間比主存空間大得多，而每一個虛頁都要占用頁表中的一行，所以頁表的存儲容量是由虛頁數(shù)決定的，一般只能將容量較大的頁表放在主存中。主存的工作速度較低，使地址變換費時較多。為了提高地址變換的速度，可采用如下技術(shù)。目錄表法快表一慢表技術(shù)內(nèi)頁表和外頁表(1)目錄表法把頁表壓縮成只保留已裝入主存（即裝入位為1）的那些虛頁與實員位置對應(yīng)關(guān)系的表項，我們稱它為相聯(lián)目錄表，簡稱目錄表，并采用相聯(lián)存儲器保存。目錄表的存儲容量取決于主存的實頁數(shù)，所以所需的存儲容量較小，而相聯(lián)存儲器的并行查找速度比主存的工作速度快得多，從而可以加快查表的速度。采用目錄表的虛擬存儲器的地址變換如圖4.22所示。(2)快表----慢表技術(shù)由于程序訪問的局部性特點，在一段時間內(nèi)，地址變換對頁表的訪問會只用到表中很少的幾行。因此，可以用高速硬件構(gòu)成比頁表小得多的部分“目錄表”，存放當前正在使用的虛、實地址映像關(guān)系。我們把這個部分目錄表稱為快表，將原位于主存中存放全部虛、實地址映像關(guān)系的頁表稱為慢表，快表只是慢表中很小的一部分副本。(3)內(nèi)頁表和外頁表多用戶虛地址Ns到輔存實（塊）地址Nvd之間的變換可采用類似前述頁表的方式，每道程序（用戶）在裝入輔存時由操作系統(tǒng)建立一個存放用戶虛頁號P與輔存實（塊）地址Nvd映像關(guān)系的表，稱為外頁表，用于實現(xiàn)外部地址變換，而將前述用于實現(xiàn)內(nèi)部地址變換的存放P與p映像關(guān)系的頁表稱為內(nèi)頁表。每個用戶的外頁表也是2P項（行），每行中用裝入位表示該信息塊是否已由海量存儲器（如磁帶）裝入磁盤。當裝入位為1時，輔存實地址字段內(nèi)容有效，是該信息塊（虛頁）在輔存（磁盤）中的實際位置。外頁表也可采用多級表技術(shù)。其地址變換過程如圖4.24所示。由于虛擬存儲器的頁面失效率一般低于1%，調(diào)周外頁表進行虛擬地址到輔存地址變換的機會很少，加上訪問輔存調(diào)頁需機械動作，速度很慢，所以外頁表通常存在輔存中，并采用軟件方法查外頁表實現(xiàn)地址變換過程。當某道程序初始運行時，從輔存調(diào)信息頁入主存并建立內(nèi)頁表，同時把未調(diào)入主存的其他虛頁在外頁表的內(nèi)容轉(zhuǎn)錄到內(nèi)頁表中。用內(nèi)頁表中裝入位為1的行的實頁號字段存放該程序的虛頁在主存中的實地址，實現(xiàn)虛地址到主存實地址的變換，而用內(nèi)頁表中裝入位為0的行的實頁號字段存放該程序的虛頁在輔存中的實地址，以方便調(diào)頁時實現(xiàn)用戶虛頁號到輔存實地址的變換。圖4.25表示出了各地址空間與內(nèi)、外頁表的關(guān)系。虛擬存儲器的工作過程(1)CPU執(zhí)行程序，從指令中獲得用戶虛地址P‘（用戶標志U+用戶虛頁號P），送內(nèi)部地址變換。(2)在內(nèi)部地址變換中，依據(jù)U+P查內(nèi)頁表，如果對應(yīng)該虛頁的頁表行中裝入位為1，則進入(3)；如果裝入位為0，則進入(4)。(3)內(nèi)頁表中虛頁對應(yīng)的裝入位為1．說明該虛頁已在主存中，則取出其頁表行中的主存頁號p與虛地址Ns中的D(等于d)拼接成主存實地址np，并在主存中完成讀/寫操作。(4)內(nèi)頁表中虛頁對應(yīng)的裝入位為0，說明該虛頁未在主存中，則產(chǎn)生頁面失效故障．然后轉(zhuǎn)入(5)，啟動外部地址變換，同時轉(zhuǎn)入(9)，啟動操作系統(tǒng)查主存頁面表。(5)在外部地址變換中，依據(jù)U+P查外頁表，判斷該頁是否在輔存：如果該虛頁的裝入位為1，則進入(6)；如果裝入位為0，則進入(8)。(6)外頁表中虛頁對應(yīng)的裝入位為1，說明該虛頁已在輔存中，通過外部地址變換形成輔存實地址Nvd，并將輔存實地址送輔存硬件。(7)在I/O處理機（通道）參與下，將該頁從輔存調(diào)入主存。該操作與CPU的運行并行進行。(8)外頁表中虛頁對應(yīng)的裝入位為0，說明該虛頁不在輔存中，此時產(chǎn)生輔存缺頁故障（異常），從海量存儲器（例如磁帶）將該頁調(diào)入輔存。(9)頁面失效時，啟動操作系統(tǒng)查主存頁面表，查找可用實頁，該操作與(5)、(6)并行。(10)若查主存頁面表得到主存未滿結(jié)果，則將內(nèi)部地址變換得到的實頁號送主存頁面表進行更新。(11)若查主存頁面表得到主存已滿結(jié)果，則執(zhí)行頁面替換算法。(12)確定被替換的主存頁面，獲得該頁的實頁號。(13)將實頁號（主存未滿時為內(nèi)部地址變換后得到的實頁號；主存已滿時為執(zhí)行替換算法后得到的被替換的實頁號）送I/O處理機，I/O處理機根據(jù)輔存實地址到輔存讀出一頁信息，然后根據(jù)主存實頁號（實地址）將該頁信息寫入主存。(14)在頁面替換時，如果被替換的頁調(diào)入主存后一直未經(jīng)修改則不需回送輔存；如果已經(jīng)修改（查主存頁面表可知），則需先將其送回輔存原來位置，而后再把調(diào)入頁裝入主存。

高速緩沖存儲器高速緩沖存儲器(Cache)用以彌補主存速度的不足。在處理機和主存之間設(shè)置一個高速、小容量的緩沖存儲器(Cache)，構(gòu)成存儲器體系結(jié)構(gòu)中的“Cache-主存”存儲層次，使之從CPU觀察，具有接近Cache的速度，又具有主存的容量。Cache技術(shù)在當代計算機系統(tǒng)中已被普遍使用，成為提高系統(tǒng)性能不可缺少的功能部件。Cache的容量不斷增大，Cache的管理實現(xiàn)全硬化，其部件已高度集成，這些已成為當代Cache的特征。Cache的基本結(jié)構(gòu)Cache和主存都分成相同大小的塊（行），每塊（行）由若干個字（節(jié)）組成，“塊”相似于“主存一輔存”層次中的“頁”。主存地址nm由塊號B和塊內(nèi)地址W兩部分組成。Cache地址ne由塊號b和塊內(nèi)地址w組成。當CPU送出一個主存地址訪存時，該主存地址將被主存-Cache地址映像變換機構(gòu)通過查表判定包含被訪問字的塊是否已在Cache中。如在即為Cache命中，則經(jīng)地址映像變換機構(gòu)將主存地址變換成Cache地址去訪Cache，此時Cache與處理機之間以單字寬進行信息傳送；如果不在Cache中則產(chǎn)生Cache塊失效，這時剛主存地址直接訪問主存，將被訪問字直接從單字寬通路送往處理機，同時把包含該字的一塊信息通過多字寬通路從主存調(diào)入Cache。如果Cache已裝不進信息，即發(fā)生塊沖突，則要采用某種替換算法將包含被訪問字的塊替換進Cache，新塊調(diào)入Cache時要更新地址映像表中的相關(guān)信息。Cache存儲器的特點(1)為使Cache能與CPU在速度上相匹配，一般采用高速SRAM芯片組成Cache(2)由于訪問Cache實際上包括查表進行地址變換和真正訪問Cache兩部分工作，故Cache存儲器在設(shè)計時可以讓前一地址的訪問Cache與后一地址的查表變換在時問上采用重疊流水方式，以提高CPU訪問Cache的速度。(3)Cache與主存之間以塊為單位進行數(shù)據(jù)交換。(4)在Cache到CPU和主存到CPU之間分別設(shè)置通路，一旦出現(xiàn)Cache塊失效，就使Cache調(diào)塊與CPU訪問主存同時進行，即通過直接通路實現(xiàn)CPU對主存的讀直達。同樣，也可實現(xiàn)CPU直接寫主存的寫直達。(5)由于主存被計算機系統(tǒng)的多個部件共享，難免發(fā)生訪存的沖突。應(yīng)該把Cache訪問主存的優(yōu)先級盡量提高，地址映像與地址變換在Cache-主存層次中，主存容量遠大于Cache的容量。地址的映像就是將主存塊按什么規(guī)則定位于Cache之中；而地址的變換就是當主存中的塊按照這種映像方式裝入Cache之后，每次訪Cache時如何將主存地址變換成對應(yīng)的Cache地址。地址映像和地址變換是緊密相關(guān)的，不同的地址映像方式在硬件實現(xiàn)相應(yīng)地址變換的難易程度、地址變換的速度、主存或Cache空間利用率、塊調(diào)入時發(fā)生塊沖突的概率等方面有所不同。常用的地址映像方式有全相聯(lián)映像、直接映像、組相聯(lián)映像和段相聯(lián)映像。1．全相聯(lián)映像及變換相聯(lián)映像方式是指主存中的任意一塊可以映像到Cache中任意的塊位置上。如果Cache的塊數(shù)為2b，主存的塊數(shù)為2B，則主存與Cache之間的映像關(guān)系有2b×2B種，如圖4.28所示。全相聯(lián)映像法的主要優(yōu)點是塊沖突概率最低，因為全相聯(lián)映像方式規(guī)定任何一個主存塊可以放在任何一個空閑的Cachc塊位置上，只有當Cache中全部裝滿后，才有可能出現(xiàn)塊沖突，所以Cache的空間利用率最高。但由于要構(gòu)成容量為2b項的相聯(lián)存儲器來存放目錄表，其代價相對較大，硬件實現(xiàn)復(fù)雜。2．直接映像及變換直接映像方式是指主存中的每一塊只能映像到Cache中的一個特定塊位置上，如圖4.30所示。設(shè)主存塊的塊號為B、Cache塊的塊號為b，若Cache的塊容量（塊數(shù)）為2b，則它們的映像關(guān)系可表示為 b=Bmod2b直接映像方式的優(yōu)點是所需硬件簡單，不需要相聯(lián)存儲器，所以成本很低，而且訪問Cache與訪問區(qū)號表、比較區(qū)號是否相符的操作是同時進行的。當Cache命中時，主存地址去掉區(qū)號E后的低位部分就是Cache地址，所以省去了地址變換所花費的時間。直接映像法最致命的缺點是Cache的塊沖突概率比較高。當兩個或兩個以上的塊映射到相同的Cache塊位置即發(fā)生沖突，這會使Cache的命中率急劇下降。而且，此時Cache中即使存在其他空閑塊也不能被使用，所以Cache的利用率很低。3．組相聯(lián)映像及變換組相聯(lián)映像方式把主存按Cache的容量分區(qū)，主存中的各區(qū)和Cache再按同樣大小劃分成數(shù)量相同的組，組內(nèi)按同樣的大小劃分成數(shù)量相同的塊，主存的組到Cache的組之間采用直接映像方式，但組內(nèi)各塊之間則采用全相聯(lián)映像方式，如圖4.33所示。既能減少塊沖突概率，提高Cache空間利用率，又能使地址映像機構(gòu)及地址變換的速度比起全相聯(lián)的要簡單和快速的映像方式。它是目前應(yīng)用較多的一種地址映像方式。組相聯(lián)映像的Cache塊沖突概率要比直接映像的低得多，只有當主存塊要進入的Cache財應(yīng)組中所有塊位置都被占用時，才出現(xiàn)塊沖突，此時即使Cache其他組中有空閑塊也不能被使用。而且，組的容量越大（組內(nèi)塊數(shù)越多），Cache塊沖突的概率就越低。另一方面，組相聯(lián)映像進行地址變換時參與相聯(lián)比較的只有2b行、E+B位，比全相聯(lián)映像地址變換時參與相聯(lián)比較的行數(shù)、位數(shù)要小得多，這都會使查表速度提高。因此，組相聯(lián)映像比全相聯(lián)映像在成本上要低得多，而性能上仍可接近于全相聯(lián)映像，所以獲得了廣泛應(yīng)用。段相聯(lián)映像及變換相聯(lián)實質(zhì)上是組相聯(lián)的特例，它采用組間全相聯(lián)、組內(nèi)直接映像。就是說，段相聯(lián)映像是把主存和Cache分成具有相同的Z塊的若干段，段與段之間采用全相聯(lián)映像，而段內(nèi)各塊之間則采用直接映像。如圖4.35所示，主存共2B塊，Cache共2b塊，主存各段中的第i塊可以映像裝入Cache任意段中的第i塊位置。采用段相聯(lián)映像的目的與采用組相聯(lián)映像一樣，主要是為減小相聯(lián)目錄表的容量、降低成本、提高地址變換的速度。當然，其Cache塊沖突概率將比全相聯(lián)的高。Cache的替換算法及實現(xiàn)當訪存發(fā)生Cache塊失效而需要把主存塊按所使用的映像規(guī)則裝入Cache時，如果又出現(xiàn)Cache塊位置沖突，就必須按某種替換策略選擇將Cache中的某一塊替換出去。對于直接映像方式實際上不需要替換算法，因為一個主存塊只能與一個Cache塊位置具有唯一的對應(yīng)關(guān)系，如果Cache的這個塊位置是空閑的，則該主存塊裝入；如果這個塊位置已經(jīng)被占用，只能把原占用塊替換出去。在全相聯(lián)映像方式中，由于一個主存塊可以裝入Cache中任意的塊位置上，使它的替換算法實現(xiàn)起來最復(fù)雜；在組相聯(lián)映像方式中，則需要從同一組內(nèi)的幾個Cache塊中選擇一塊替換出去。Cache-主存存儲層次的替換算法與虛擬存儲器的大致相同，一般采用FIFO算法或LRU算法，其中LRU算法最常用。但由于CPU調(diào)Cache塊的時間在微秒級，所以其替換算法必須全部用硬件實現(xiàn)。下面介紹兩種用硬件實現(xiàn)LRU替換算法的具體方法計數(shù)器法在塊表中為每個Cache塊設(shè)置一個計數(shù)器，計數(shù)器的長度與被選擇替換范圍內(nèi)的Cache塊號字段的長度相同。假設(shè)Cache共有16塊，對于全相聯(lián)映像，被選擇替換范圍為全部Cache塊，計數(shù)器應(yīng)與Cache塊號字段的位數(shù)相同為4位；若此Cache采用分成兩組、每組八塊的組相聯(lián)映像，則被選擇替換范圍為一組內(nèi)的Cache塊，故計數(shù)器應(yīng)為組內(nèi)塊號字段的長度3位。計數(shù)器的使用及管理規(guī)則是：塊被裝入或被替換時，其對應(yīng)的計數(shù)器清零，而被選擇范圍內(nèi)其他塊對應(yīng)的計數(shù)器都加1。塊命中時，其對應(yīng)的計數(shù)器清零。對被選擇范圍內(nèi)其他的計數(shù)器．凡是計數(shù)值小于命中塊所對應(yīng)計數(shù)器原值的加1，其他計數(shù)器不變。需要塊替換時，對被選擇范圍內(nèi)的所有計數(shù)器進行相聯(lián)比較，選擇計數(shù)值最大（一般為全1）的計數(shù)器對應(yīng)的塊作為被替換塊。[例4.4]某Cache系統(tǒng)．采用組相聯(lián)映像方式，每組四塊，用計數(shù)器法實現(xiàn)LRU替換算法。若映像到某Cache組的訪存塊地址流為1、3、2、8、9、8，請說明該組內(nèi)四個Cache塊計數(shù)器的工作情況。解：四個Cache塊的計數(shù)器工作情況如表4.1所示。由表可見，當四個Cache塊位置被占滿后Cache塊0的計數(shù)器值為11，是四個計數(shù)器值中最大的。當主存塊9要調(diào)入時，發(fā)生塊沖突，主存塊9替換Cache塊0位置上的主存塊1。計數(shù)器法需要硬件有相聯(lián)比較功能，所以其速度較低，也比較貴。比較對法比較對法的墓本思想是讓各塊兩兩構(gòu)成比較對，用一個觸發(fā)器的狀態(tài)表示該比較對的兩塊被訪問過的先后順序，經(jīng)門電路組合，可從多個塊中找出最久未被訪問過的塊。假設(shè)有A、B、C三個塊，互相之間不重復(fù)的組合有AB、AC和BC三對。分別用一個觸發(fā)器的狀態(tài)表示每個比較對內(nèi)兩塊被訪問過的順序，例如，觸發(fā)器TAB=1表示A比B更近被訪問過，TAB=0表示B比A更近被訪問過，TAC和TBC也類似定義?？傻玫阶罹梦幢辉L問過的塊作為被替換塊的布爾表達式分別為用觸發(fā)器、門電路等硬件組合實現(xiàn)比較對法的邏輯電路如圖4.36所示。在每次CPU訪問到Cache中的某塊是，通過改變與該塊有關(guān)的比較對觸發(fā)器的狀態(tài)來記錄各塊被訪問過的順序。對于塊數(shù)更多的情況，可采用同樣的思路實現(xiàn)。若塊數(shù)為p，觸發(fā)器的個數(shù)為

，即觸發(fā)器個數(shù)隨塊數(shù)的平方遞增，所以比較對法只適用于組內(nèi)塊數(shù)較少的組相聯(lián)映像的Cache存儲器?？傮w來講，實現(xiàn)替換算法的設(shè)計應(yīng)考慮以下兩點：如何對每次訪問進行記錄，即記錄Cache塊被訪問的先后次序。如何根據(jù)所記錄的信息來判斷哪一塊是最近最少使用的塊．使之成為發(fā)生Cache塊沖突時最先被替換的塊。Cache的性能分析1．Cache的透明性2．Cache的取算法3.Cache的性能分析向量處理的基本概念問題：Y=a×X+Y其中，a為標量；X和Y是向量例4.1用標量處理機來計算LD F0,a ;ADD R4,Rx,#512 ;LD F2,M(Rx) ;MUL F2,F0,F2 ;LD F4,M(Ry) ;LOOP: ADD F4,F2,F4 ; SD M(Ry),F4 ; ADD Rx,Rx,#8 ; ADD Ry,Ry,#8 ; SUB R20,R4,Rx ; BNZ R20,LOOP ;Cache的透明性由于Cache存儲器的地址變換、替換算法和調(diào)度算法等均由硬件實現(xiàn)，故“Cache-主存”層次對系統(tǒng)程序員和用戶都是透明的，且Cache對CPU和主存之間的信息交換也是透明的。對于Cachc的透明性可能引發(fā)的問題及其影響需慎重對待，并予以妥善解決。一致性問題與寫策略一般情況下，Cache中存放的內(nèi)容應(yīng)該是主存的部分副本。然而，由于以下兩個原因，主存某單元中的內(nèi)容與Cache對應(yīng)單元中的內(nèi)容可能在一段時間內(nèi)不一致：CPU修改Cache內(nèi)容時，主存對應(yīng)部分內(nèi)容還沒有變化；I/O處理機(IOP)已將新的內(nèi)容輸入主存某區(qū)域，而Cache對應(yīng)部分的內(nèi)容卻可能還是原來的。這些通信過程所引起的Cache內(nèi)容與主存內(nèi)容的不一致，在Cache對CPU和主存均是透明的前提下，可能引發(fā)錯誤。當CPU執(zhí)行寫入操作時，若只寫入Cache，則主存中對應(yīng)部分仍是原來的，會對Cache的塊替換產(chǎn)生影響。而且，當CPU、IOP和其他處理機經(jīng)主存交換信息時會造成錯誤。為了解決這個問題，提出了主存修改算法．即寫策略。一般可用兩種修改主存的寫策略：寫回法和寫直達法。寫回法是指在CPU執(zhí)行寫操作命中Cache時，信息只寫入Cache，僅當需要被替換時，才將已被改寫過的Cache塊先送回主存，然后再調(diào)入新塊。寫回法包括簡單寫回法和采用標志位寫回法：簡單寫回法是不管塊是否被改寫，都進行寫回操作；而采用標志位寫回法只在塊被改寫過時，才進行寫回操作。寫直達法是利用Cache-主存存儲層次在CPU和主存之間的直接通路，每當CPU將信息寫入Cache的同時，也通過此通路直接寫入主存。這樣，在塊替換時就無須寫回操作，可立即調(diào)入新塊。寫回法和寫直達法是兩種常用的寫策略，它們具有以下特點。寫回法把開銷花費在替換時，而寫直達法則是把開銷花費在每次寫Cache時都要附加一個比寫Cache時間長得多的寫主存時間。寫回法和寫直達法都需要有少量緩沖器。寫回法中緩沖器用于暫存要寫回的塊，使之不必等待被替換塊寫回主存后才開始進行Cache取；寫直達法中則用于緩沖由寫Cache導(dǎo)致的要寫回主存昀內(nèi)容，使CPU不必等待這些寫主存完成就可往下運行。寫回法使主存的通信量比寫直達法的要小得多（如采用寫回法有利于省去許多將中間結(jié)果寫入主存的無謂開銷），但它增加了Cache的復(fù)雜性（如需要設(shè)置修改位以確定是否需要寫回以及控制先寫回后才調(diào)入的執(zhí)行順序），并且寫回法在塊替換前，會存在主存內(nèi)容與Cache內(nèi)容不一致的問題。寫直達法的可靠性比寫回法的可靠性要高。寫直達法需花費大量緩沖器和其他輔助邏輯來減少CPU為等待寫主存所耗費的時

間，相對而言寫回法的實現(xiàn)成本則要低得多。在出現(xiàn)寫不命中時，這兩種方法都面臨著一個在寫時是否取的問題。這有兩種解決方法：一種是不按寫分配法，即當Cache寫不命中時只寫入主存，該單元所在塊不從主存調(diào)入Cache;另一種是按寫分配法，即當Cache寫不命中時除寫入主存外，還把該單元所在塊由主存調(diào)入Cache。這兩種策略對不同的寫策略其效果不同，但差別不大。寫回法一般采用“按寫分配”，寫直達法一般采用“不按寫分配”。采用寫回法和寫直達法還與使用場合有關(guān)：一般單處理機Cache多數(shù)采用寫回法以節(jié)省成本；而共享主存的多處理機系統(tǒng)為保證各處理機經(jīng)主存交換信息時不出錯（為提高可靠性），多數(shù)采用寫直達法。至于Cache的內(nèi)容跟不上已變化了的主存內(nèi)容的問題，一種解決方法是當IOP向主存寫入（輸入）新內(nèi)容時，由操作系統(tǒng)用某個專用指令清除整個Cache。這種方法的缺點是使Cache對操作系統(tǒng)和系統(tǒng)程序員非透明。另一種方法是當IOP向主存寫入新內(nèi)容時，由專用硬件自動地將Cache肉對應(yīng)區(qū)域的副本作廢，而不必由操作系統(tǒng)干預(yù)，從而保持了Cache的透明性。另外，采用CPU、IOP共享一個Cache也是一種辦法。多處理機系統(tǒng)的Cache結(jié)構(gòu)及一致性多處理機系統(tǒng)的一般形式，是由多個CPU和多個I/O處理機組成共享主存的系統(tǒng)。對于共享主存的多處理機系統(tǒng)，絕大多數(shù)還是采用各個CPU具有自己私有Cache的方式與共享主存連接。在這樣的系統(tǒng)中，由于Cache的透明性，僅靠采用寫直達法并不能保證同一主存單元在各個Cache中的對應(yīng)內(nèi)容都一致。例如，在圖4.37所示的系統(tǒng)中，處理機A和處理機B通過各自的Cachea和Cacheb共享主存。在處理機A寫入Cachea的同