計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第4章(存儲(chǔ)系統(tǒng))

第3章存儲(chǔ)系統(tǒng)/MemorySystem

主存讀緩存器指令讀緩存器寫緩存器

I/O

部件

I/O

部件CPU以存儲(chǔ)器為中心的計(jì)算機(jī)結(jié)構(gòu)現(xiàn)代計(jì)算機(jī)系統(tǒng)都以存儲(chǔ)器為中心.在計(jì)算機(jī)運(yùn)行過程中，存儲(chǔ)器是各種信息存儲(chǔ)和交換的中心.存儲(chǔ)系統(tǒng)/MemorySystem【學(xué)習(xí)目標(biāo)】1.領(lǐng)會(huì)存儲(chǔ)系統(tǒng)的含義及其性能指標(biāo).2.

理解并行存儲(chǔ)器的工作原理。3.掌握虛擬存儲(chǔ)系統(tǒng)的工作原理和虛擬存儲(chǔ)系統(tǒng)的頁面替換算法。4.掌握Cache存儲(chǔ)系統(tǒng)的地址映象及變換方法以及Cache存儲(chǔ)系統(tǒng)的塊替換算法。第4章存儲(chǔ)系統(tǒng)/MemorySystem【學(xué)習(xí)內(nèi)容】4.1存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)與性能指標(biāo)4.2并行存儲(chǔ)器4.3虛擬存儲(chǔ)器4.4高速緩沖存儲(chǔ)器（Cache)4.5三級(jí)存儲(chǔ)系統(tǒng)4.1存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)與性能指標(biāo)4.1.1存儲(chǔ)器的層次結(jié)構(gòu)4.1.2存儲(chǔ)系統(tǒng)的性能指標(biāo)存儲(chǔ)器的層次結(jié)構(gòu)計(jì)算機(jī)中的存儲(chǔ)器類型:主存儲(chǔ)器、Cache、通用寄存器、各種緩沖存儲(chǔ)器構(gòu)成材料:ECL,TTL,MOS，磁表面存儲(chǔ)器，光存儲(chǔ)器,SRAM,DRAM訪問方式：直接譯碼、隨機(jī)訪問、相聯(lián)訪問、塊交換、文件組、手工加載等存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的主要性能指標(biāo)速度:用存儲(chǔ)器的訪問周期、讀出時(shí)間、頻帶寬度等表示容量:用字節(jié)B、千字節(jié)KB、兆字節(jié)MB和千兆字節(jié)GB等表示價(jià)格:用單位容量的價(jià)錢表示，例如$C/bit

兩個(gè)或兩個(gè)以上速度、容量和價(jià)格各不相同的存儲(chǔ)器,用硬件、軟件、或軟件與硬件相結(jié)合的方法連接起來成為一個(gè)系統(tǒng)。這個(gè)系統(tǒng)對應(yīng)用程序員透明，并且，從應(yīng)用程序員看，它是一個(gè)存儲(chǔ)器，這個(gè)存儲(chǔ)器的速度接近速度最快的那個(gè)存儲(chǔ)器，存儲(chǔ)容量與容量最大的那個(gè)存儲(chǔ)器相等，單位容量的價(jià)格接近最便宜的那個(gè)存儲(chǔ)器。

具有這種層次的存儲(chǔ)系統(tǒng)能獲得比較高的性能價(jià)格比的重要依據(jù)是:程序?qū)Τ绦蚩臻g的訪問具有程序訪問局部性的特點(diǎn).

存儲(chǔ)系統(tǒng)的定義存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)1.程序訪問局部性2.存儲(chǔ)系統(tǒng)的多級(jí)層次結(jié)構(gòu)3.存儲(chǔ)系統(tǒng)的透明性要求4.三級(jí)存儲(chǔ)系統(tǒng)1.程序訪問局部性程序訪問局部性包括:時(shí)間局部性和空間局部性.時(shí)間局部性:程序在最近的未來要用到的信息很可能是在正在使用的信息.如循環(huán)程序的多次重復(fù)使用.空間局部性:程序在最近的未來用用到的信息很可能同現(xiàn)在使用的信息在存儲(chǔ)空間位置上是相鄰近的.程序訪問局部性指出了最近的未來要使用的指令和數(shù)據(jù)很可能就是正在使用的指令和數(shù)據(jù),或者是與正在使用的指令和數(shù)據(jù)在存儲(chǔ)空間位置上相鄰的指令和數(shù)據(jù).因此,可以把存儲(chǔ)空間位置相鄰的信息作為一“塊”或一“頁”放到容量最小但速度最快的一級(jí)存儲(chǔ)器中,從而可以使訪問速度接近速度最快的那一級(jí)的存儲(chǔ)器的速度.例如:2.存儲(chǔ)系統(tǒng)的多級(jí)層次結(jié)構(gòu)由n個(gè)速度、容量、價(jià)格各不相同的存儲(chǔ)器組成的存儲(chǔ)系統(tǒng).其中,M1級(jí)最靠近CPU,它的速度最快,或者說M1的訪問周期T1最小,正是通過高速的M1使存儲(chǔ)系統(tǒng)的訪問速度能與CPU的速度匹配.但是,高速的M1的單位容量的平均價(jià)格同速度較低的存儲(chǔ)器相比要貴得多,容量S1也因?yàn)閮r(jià)格的限制不能T太大.多層次結(jié)構(gòu)的存儲(chǔ)系統(tǒng)的性能價(jià)格比有優(yōu)于任何的單級(jí)存儲(chǔ)器.3.存儲(chǔ)系統(tǒng)的透明性要求

存儲(chǔ)系統(tǒng)應(yīng)滿足以下透明性要求:

(1)在程序執(zhí)行期間,CPU產(chǎn)生一個(gè)連續(xù)的邏輯地址流,邏輯地址需要變換為某個(gè)Mi的物理地址,才能實(shí)現(xiàn)對Mi的訪問,這鐘地址變換對程序員應(yīng)該是透明的.

(2)在兩個(gè)相臨的存儲(chǔ)器Mi

和Mi+1之間調(diào)入和調(diào)出塊或頁的操作對程序員也應(yīng)該是透明的.存儲(chǔ)系統(tǒng)的透明性是由對存儲(chǔ)系統(tǒng)進(jìn)行管理的硬件和軟件來實(shí)現(xiàn)的.4.三級(jí)存儲(chǔ)系統(tǒng)

多數(shù)計(jì)算機(jī)是由高速緩沖存儲(chǔ)器(Cache)、主存儲(chǔ)器和磁盤存儲(chǔ)器(輔存)構(gòu)成一個(gè)三級(jí)存儲(chǔ)系統(tǒng).實(shí)現(xiàn)方式:組織成2個(gè)獨(dú)立的二級(jí)存儲(chǔ)系統(tǒng).

(1)由Cache和主存組成的“Cache-主存”存儲(chǔ)系統(tǒng),或稱為Cache存儲(chǔ)器.

(2)由主存和磁盤存儲(chǔ)器組成的“主存-輔存”存儲(chǔ)系統(tǒng),因采用虛擬存儲(chǔ)技術(shù),也稱為虛擬存儲(chǔ)器.Cache主存輔存三級(jí)存儲(chǔ)系統(tǒng)虛擬存儲(chǔ)器(VirtualMemory)是針對主存容量不能滿足要求而提出來的,在主存和輔存之間增加輔助的軟件和硬件,使主存和輔存構(gòu)成一個(gè)整體.等效的訪問速度接近于主存訪問速度,容量是輔存的容量,每位價(jià)格接近于輔存.Cache存儲(chǔ)器是針對主存速度不能滿足而提出來的,在物理Cache和主存之間增加輔助硬件,使Cache和主存構(gòu)成一個(gè)整體,Cache存儲(chǔ)器的等效訪問速度接近物理Cache訪問速度,容量卻是主存的容量,每位價(jià)格接近主存的價(jià)格.虛擬存儲(chǔ)器和Cache存儲(chǔ)器對應(yīng)用程序員都是透明的.由于CPU與主存的速度只差1個(gè)數(shù)量級(jí),主存與輔存的速度卻差3～4個(gè)數(shù)量級(jí),因此,Cache只能全部采用硬件來實(shí)現(xiàn).Cache存儲(chǔ)器對系統(tǒng)程序員也是透明的,操作系統(tǒng)不會(huì)參與對Cache存儲(chǔ)器的管理.

在虛擬存儲(chǔ)器中,為了降低成本,有部分功能由操作系統(tǒng)的存儲(chǔ)管理軟件來實(shí)現(xiàn),因此,虛擬存儲(chǔ)器對系統(tǒng)程序員是不透明的.

目前,很多CPU的芯片內(nèi)集成有Cache,因此把Cache又分為相臨的二級(jí),片內(nèi)Cache稱為一級(jí)Cache,片外Cache稱為二級(jí)Cache.三級(jí)存儲(chǔ)系統(tǒng)4.1.2存儲(chǔ)系統(tǒng)的性能指標(biāo)兩個(gè)存儲(chǔ)器組成的存儲(chǔ)系統(tǒng).T1＜T2,S1

＜S2,C1＞C2存儲(chǔ)系統(tǒng)的性能指標(biāo)

1.存儲(chǔ)系統(tǒng)的容量S存儲(chǔ)系統(tǒng)對計(jì)算機(jī)的使用者提供盡可能大地址空間,且能夠隨機(jī)訪問.對于Cache存儲(chǔ)器,其容量等于主存的容量,既M=M2.對于虛擬存儲(chǔ)器,其容量既不是主存的地址空間,也不是輔存的地址空間,而是比實(shí)際物理地址空間大得多的虛擬地址空間,并且用像主存一樣的隨機(jī)訪問方式.2.存儲(chǔ)系統(tǒng)的帶寬存儲(chǔ)器被連續(xù)訪問時(shí)能提供的數(shù)據(jù)傳輸率稱為存儲(chǔ)器的最大帶寬(一般用每秒鐘所傳送的信息位數(shù)來衡量)。由于存儲(chǔ)器不一定始終滿負(fù)荷工作,因此,存儲(chǔ)器的實(shí)際帶寬一般低于最大帶寬.存儲(chǔ)系統(tǒng)的性能指標(biāo)當(dāng)S2》S1時(shí)，C≈C2但S2與S1不能相差太大,否則,難實(shí)現(xiàn)調(diào)度使性能高3.單位容量的平均價(jià)格C計(jì)算公式:4.命中率HCPU產(chǎn)生的邏輯地址在M1存儲(chǔ)器中訪問到的概率其中：N1是對M1存儲(chǔ)器的訪問次數(shù)

N2是對M2存儲(chǔ)器的訪問次數(shù)H越接近1越好!

訪問效率主要與命中率和兩級(jí)存儲(chǔ)器的速度之比有關(guān)5.存儲(chǔ)系統(tǒng)的訪問周期T表示方法：訪問周期、存取周期、存儲(chǔ)周期、存取時(shí)間等系統(tǒng)的訪問周期T＝H×T1＋(1－H)×T2T1

和T2

分別是存儲(chǔ)器M1

和M2的訪問周期

當(dāng)命中率H→1時(shí)，T→T16.存儲(chǔ)系統(tǒng)的訪問效率存儲(chǔ)系統(tǒng)的性能指標(biāo)主要與命中率和構(gòu)成系統(tǒng)的兩級(jí)存儲(chǔ)器的訪問周期比有關(guān).可以看出:存儲(chǔ)系統(tǒng)的訪問效率主要與命中率和構(gòu)成存儲(chǔ)系統(tǒng)的兩級(jí)存儲(chǔ)器的速度之比有關(guān).

結(jié)論:提高存儲(chǔ)系統(tǒng)速度的兩條途徑：

一是提高命中率H

二是兩個(gè)存儲(chǔ)器的速度不要相差太大其中：第二條有時(shí)做不到(如虛擬存儲(chǔ)器)因此,主要依靠提高命中率

存儲(chǔ)系統(tǒng)的性能指標(biāo)例1：假設(shè)T2＝５T１，在命中率H為0.9和0.99兩種情況下，分別計(jì)算存儲(chǔ)系統(tǒng)的訪問效率。解：當(dāng)H＝0.9時(shí)，e1＝1／(0.9＋5×(1－0.9))＝0.72

當(dāng)H＝0.99時(shí)，e2＝1／(0.99＋5×(1－0.99))＝0.96

存儲(chǔ)系統(tǒng)的性能指標(biāo)例2：在虛擬存儲(chǔ)系統(tǒng)中，兩級(jí)存儲(chǔ)器的速度相差特別懸殊T2＝105T１。如果要使訪問效率e＝0.9，問需要有多高的命中率？解：0.9H＋90000(1－H)＝189999.1H＝89999

計(jì)算得H＝0.999998888877777…≈0.999999存儲(chǔ)系統(tǒng)的性能指標(biāo)例3：在一個(gè)Cache存儲(chǔ)系統(tǒng)中，當(dāng)Cache的塊大小為一個(gè)字時(shí)，命中率為H＝0.8；假設(shè)數(shù)據(jù)的重復(fù)利用率為5，計(jì)算Cache的塊大小為4個(gè)字時(shí)，Cache存儲(chǔ)系統(tǒng)的命中率是多少？假設(shè)T2＝５T1，分別計(jì)算訪問效率。解：n＝4×5＝20，采用預(yù)取技術(shù)之后，命中率提高到：Cache的塊大小為一個(gè)字時(shí)，H＝0.8，訪問效率為：

e1＝1／(0.8＋5(1－0.8))＝0.55…Cache的塊大小為4個(gè)字時(shí)，H＝0.99，訪問效率為：

e2＝1／(0.99＋5(1－0.99))＝0.96存儲(chǔ)系統(tǒng)的性能指標(biāo)例4：在一個(gè)虛擬存儲(chǔ)系統(tǒng)中，T2＝105T１，原來的命中率只有0.8，現(xiàn)采用預(yù)取技術(shù)，訪問磁盤存儲(chǔ)器的數(shù)據(jù)塊大小為4K字，如果要求訪問效率不低于0.9，計(jì)算數(shù)據(jù)在主存儲(chǔ)器中的重復(fù)利用率至少為多少？解：假設(shè)數(shù)據(jù)在主存儲(chǔ)器中的重復(fù)利用率為m，根據(jù)前面的給出關(guān)系：解這個(gè)方程組，得到m＝44，即數(shù)據(jù)在主存儲(chǔ)器中的重復(fù)利用率至少為44次。存儲(chǔ)系統(tǒng)的性能指標(biāo)4.2并行存儲(chǔ)器存儲(chǔ)器的存取速度直接影響著計(jì)算機(jī)系統(tǒng)的性能.為此:要解決存儲(chǔ)器的頻帶平衡問題.計(jì)算機(jī)系統(tǒng)中各級(jí)存儲(chǔ)器的頻帶應(yīng)該達(dá)到平衡例如：有一臺(tái)速度為500MIPS的計(jì)算機(jī)系統(tǒng)，主存儲(chǔ)器的各種訪問源的頻帶寬度如下：

CPU取指令：500MW/sCPU取操作數(shù)和保存運(yùn)算結(jié)果：1000MW/s

各種輸入輸出設(shè)備訪問存儲(chǔ)器：50MW/s三項(xiàng)相加，要求存儲(chǔ)器的頻帶寬度不低于1550MW/s。訪問周期不大于0.64ns。

實(shí)際上目前作為主存儲(chǔ)器的工作周期為100ns左右，兩者相差150多倍.并行存儲(chǔ)器

解決存儲(chǔ)器頻帶平衡方法有多種,其中,設(shè)置多個(gè)獨(dú)立的存儲(chǔ)器,并行工作,在一個(gè)存儲(chǔ)周期內(nèi)可以訪問多個(gè)數(shù)據(jù),是提高存儲(chǔ)器速度最直接的方法4.2.1單體多字并行存儲(chǔ)器4.2.2低位交叉編址多體并行存儲(chǔ)器4.2.1單體多字并行存儲(chǔ)器邏輯實(shí)現(xiàn)：把地址碼分成兩個(gè)部分.一部分仍作為存儲(chǔ)器的地址,訪問存儲(chǔ)器.另一部分去控制一個(gè)多路選擇器,負(fù)責(zé)從讀出的n個(gè)數(shù)據(jù)中選擇一個(gè)數(shù)據(jù)輸出.

方法：把m個(gè)字w位的存儲(chǔ)器改變成為m/n字n×w位的存儲(chǔ)器(把字長增加n倍,以存放n個(gè)指令字或數(shù)據(jù)字)主要優(yōu)點(diǎn):實(shí)現(xiàn)簡單、容易主要缺點(diǎn)：訪問沖突大,主要沖突來自:

(1)

取指令沖突（條件轉(zhuǎn)移時(shí)）.(2)讀操作數(shù)沖突（需要的多個(gè)操作數(shù)不一定都存放在同一個(gè)存儲(chǔ)字中）.(3)寫數(shù)據(jù)沖突（必須湊齊n個(gè)數(shù)才一起寫入存儲(chǔ)器）.(4)讀寫沖突（要讀出的一個(gè)字和要寫入的一個(gè)字處在同一個(gè)存儲(chǔ)字內(nèi)時(shí)，無法在一個(gè)存儲(chǔ)周期內(nèi)完成）。單體多字并行存儲(chǔ)器交叉訪問存儲(chǔ)器通常有兩種工作方式,一種是地址碼高位交叉,另一種是地址碼低位交叉.高位交叉訪問存儲(chǔ)器主要目的：擴(kuò)大存儲(chǔ)器容量

低位交叉訪問存儲(chǔ)器。主要目的：提高存儲(chǔ)器訪問速度,同時(shí)也增加了存儲(chǔ)器的容量.4.2.2低位交叉編址多體并行存儲(chǔ)器實(shí)現(xiàn)方法：用地址碼的低位部分區(qū)分存儲(chǔ)體號(hào),高位是各存儲(chǔ)體的體內(nèi)地址.低位交叉編址多體并行存儲(chǔ)器存儲(chǔ)器地址A的計(jì)算公式為：A＝m×i＋k如果已經(jīng)知道存儲(chǔ)器的地址為A,則它的:存儲(chǔ)器的體內(nèi)地址：Ai＝存儲(chǔ)器的體號(hào)Ak＝Amodm交叉編址方式低位交叉編址多體并行存儲(chǔ)器地址碼低位：存儲(chǔ)體的個(gè)數(shù)為m,低位位數(shù)=log2m地址碼高位：每個(gè)存儲(chǔ)體的容量n,高位位數(shù)=log2n用i表示存儲(chǔ)體的體內(nèi)地址,用k表示存儲(chǔ)體的體號(hào)存儲(chǔ)體地址的編碼方法

為了達(dá)到提高速度的目的,m個(gè)存儲(chǔ)體必須分時(shí)啟動(dòng).m個(gè)存儲(chǔ)體分時(shí)啟動(dòng)每存儲(chǔ)體的啟動(dòng)間隔為：t＝實(shí)際上是一種采用流水線方式工作的并行存儲(chǔ)器,理論上，存儲(chǔ)器的速度可望提高m倍.

由于每個(gè)存儲(chǔ)單元都有自己的地址,低位交叉編址多體并行存儲(chǔ)器的實(shí)際帶寬也高于相同容量的單體多字存儲(chǔ)器的實(shí)際帶寬.

4.3虛擬存儲(chǔ)器1961年英國曼徹斯特大學(xué)的Kilbrn等人提出的。到了70年代被廣泛地應(yīng)用于大中型計(jì)算機(jī)系統(tǒng)中。目前，許多微型機(jī)也開始使用虛擬存儲(chǔ)器。

4.3.1虛擬存儲(chǔ)器的地址變換4.3.2頁面替換算法及其命中率*4.3.3堆棧型替換算法及其堆棧處理過程4.3.1虛擬存儲(chǔ)器的地址變換幾個(gè)概念:三種地址空間：虛擬地址空間(用來編寫程序的地址空間)，主存儲(chǔ)器地址空間(實(shí)存地址空間)，輔存地址空間(磁盤存儲(chǔ)器的地址空間)。三種地址：虛擬地址(程序經(jīng)編譯生成的訪存地址)、主存地址、磁盤地址地址映象：程序代碼運(yùn)行時(shí),必須先把虛擬地址轉(zhuǎn)換成主存實(shí)地址,才能訪問主存.虛地址與實(shí)地址之間對應(yīng)關(guān)系的規(guī)則(AddressMapping).地址變換：在程序運(yùn)行過程中，虛擬存儲(chǔ)系統(tǒng)按照某種地映象把虛擬地址變換成主存實(shí)地址,稱為地址變換(AddressTranslation)因地址映象和變換方法不同，有三種虛擬存儲(chǔ)器：段式虛擬存儲(chǔ)器、頁式虛擬存儲(chǔ)器、段頁式虛擬存儲(chǔ)器。1.段式虛擬存儲(chǔ)器的地址變換(1)地址映象方法：每個(gè)程序段都從0地址開始編址，長度可長可短，可以在程序執(zhí)行過程中動(dòng)態(tài)改變程序段的長度。段式虛擬存儲(chǔ)器的地址映象段號(hào)段長起始地址01k8k150016k22009k320030k虛擬存儲(chǔ)器的地址變換

主程序0段1段2段3段程序空間01k050002000200主存空間8k9k16k30k段表(段號(hào)可以省掉)(2)段式虛擬存儲(chǔ)器地址變換

地址變換方法：由用戶號(hào)找到基址寄存器從基址寄存器中讀出段表的起始地址把起始地址與多用戶虛地址中段號(hào)相加得到段表地址把段表中給出的起始地址與段內(nèi)偏移D相加就能得到主存實(shí)地址段式虛擬存儲(chǔ)器的地址變換多用戶虛地址由三部分組成:U,S,D在CPU中有一個(gè)段表基址寄存器堆,每道程序使用其中的一個(gè)基址寄存器,通過虛地址中的用戶號(hào)可直接找到與這道程序相對應(yīng)的基址寄存器.用戶號(hào)U段號(hào)S段內(nèi)偏移D6As段表長度段表基地址段式虛擬存儲(chǔ)器地址變換方法：多用戶虛地址01234段名起始地址裝入位段長訪問方式主存實(shí)地址0N-1+As+段表基址寄存器一個(gè)用戶(一道作業(yè))的段表(3)段式虛擬存儲(chǔ)器的主要優(yōu)點(diǎn)：程序的模塊化性能好。便于程序和數(shù)據(jù)的共享。在主程序裝入共享程序段.其他要調(diào)用這個(gè)程序段的程序,在其段表中都使用這個(gè)被共享的程序段的起始地址和段長.程序的動(dòng)態(tài)鏈接和調(diào)度比較容易。便于實(shí)現(xiàn)信息保護(hù)。(4)段式虛擬存儲(chǔ)器的主要缺點(diǎn)：地址變換所花費(fèi)的時(shí)間比較長，做兩次加法運(yùn)算。主存儲(chǔ)器的利用率往往比較低。對輔存（磁盤存儲(chǔ)器）的管理比較困難。

段式虛擬存儲(chǔ)器地址的映象

地址的映象與變換0頁1頁2頁3頁用戶程序主存儲(chǔ)器2.頁式虛擬存儲(chǔ)器的地址變換(1)頁式虛擬存儲(chǔ)器的地址映象把主存儲(chǔ)器、磁盤存儲(chǔ)器和虛擬存儲(chǔ)器都劃分成固定大小的塊—頁(page)，每頁的大小相同。主存儲(chǔ)器的頁稱為實(shí)頁，虛擬存儲(chǔ)器中的頁稱為虛頁。由用戶號(hào)U直接找到相對應(yīng)的基址寄存器從基址寄存器中讀出頁表起始地址把頁表起始地址與多用戶虛地址中虛頁號(hào)相加得到頁表地址，從頁表中讀出主存頁號(hào)p與虛地址中的頁內(nèi)偏移D拼接得到主存實(shí)地址

2.頁式虛擬存儲(chǔ)器的地址變換(1)頁式虛擬存儲(chǔ)器的地址變換用戶號(hào)U虛頁號(hào)P頁內(nèi)偏移DPa1P裝入位修改位主存頁號(hào)各種標(biāo)志實(shí)頁號(hào)p頁內(nèi)偏移d頁表基址寄存器頁表多用戶虛地址Av主存實(shí)地址APa+2.頁式虛擬存儲(chǔ)器的地址變換(2)頁式虛擬存儲(chǔ)器的地址變換(3)頁式虛擬存儲(chǔ)器的主要優(yōu)點(diǎn)：主存儲(chǔ)器的利用率比較高。頁表相對比較簡單，節(jié)省了頁表的存儲(chǔ)容量。地址映象和變換的速度比較快。對輔存（磁盤存儲(chǔ)器）的管理比較容易。(4)頁式虛擬存儲(chǔ)器的主要缺點(diǎn)：程序的模塊化性能不好。頁表很長，需要占用很大的存儲(chǔ)空間。例如：虛擬存儲(chǔ)空間4GB，頁大小1KB，則頁表的容量為4M字，16MB。3.頁式虛擬存儲(chǔ)器內(nèi)部地址變換：多用戶虛擬地址Av變換成主存實(shí)頁號(hào)p多用戶虛擬地址中的頁內(nèi)偏移D直接作為主存實(shí)地址中的頁內(nèi)偏移d，主存實(shí)頁號(hào)p與它的頁內(nèi)偏移d直接拼接起來就得到主存實(shí)地址A。進(jìn)行外部地址變換：首先查外頁表得到磁盤存儲(chǔ)器的實(shí)地址.然后再查內(nèi)頁表，看主存儲(chǔ)器中是否有空頁。若空,把磁盤存儲(chǔ)器的實(shí)地址和主存儲(chǔ)器的實(shí)頁號(hào)送入輸入輸出處理機(jī)，要訪問數(shù)據(jù)所在的一整頁都從磁盤存儲(chǔ)器調(diào)入到主存儲(chǔ)器。若不空,進(jìn)行頁面替換,把主存中暫時(shí)不用的一頁寫回到磁盤存儲(chǔ)器中原來的位置上.外部地址變換不命中,啟動(dòng)海量存儲(chǔ)器,把所需數(shù)據(jù)相關(guān)的文件調(diào)磁盤存儲(chǔ)器.頁式虛擬存儲(chǔ)器虛擬存儲(chǔ)器工作原理先內(nèi)后外再海量,內(nèi)部變換最優(yōu)先,AV換成實(shí)頁號(hào)(p),工作全由操、硬完,得到實(shí)頁(號(hào)p)尚未了,還需得到頁內(nèi)偏(d),最后將p拼接d,用A訪存不麻煩;內(nèi)部變換不成功,軟件進(jìn)行外變換,首先查查外頁表,相應(yīng)實(shí)址在磁盤,然后再查內(nèi)頁表,檢查主存頁有閑?若是主存有空頁,整頁調(diào)進(jìn)主存間;如果變換不成功,操作系統(tǒng)啟光盤,信息調(diào)入磁盤器,組織方式是文件.3.段頁式虛擬存儲(chǔ)器

基本思想是用戶用來編寫程序的虛擬存儲(chǔ)空間采用分段的方法管理,主存物理空間采用分頁的方法進(jìn)行管理.用戶按照程序段來編寫程序，每個(gè)程序段分成幾個(gè)固定大小的頁。(1)地址映象方法：每個(gè)程序段在段表中占一行。在段表中給出該程序段的頁表長度和頁表的起始地址.頁表中給出這個(gè)程序段的每一頁在主存儲(chǔ)器中的實(shí)頁號(hào)。虛擬存儲(chǔ)器的地址變換

段頁式虛擬存儲(chǔ)器

０段（12K）０段０頁０段１頁０段２頁２段（5K）地址映象方法頁表長度頁表地址３３２１段０頁１段１頁１段２頁１段（10K）２段０頁２段１頁０段頁表１段頁表２段頁表每頁４ＫＢ段表用戶程序主存儲(chǔ)器(2)地址變換方法：先查段表，得到該程序段的頁表起始地址和頁表長度．再查頁表找到要訪問的主存實(shí)頁號(hào)．最后把實(shí)頁號(hào)p與頁內(nèi)偏移d拼接得到主存的實(shí)地址。

段頁式虛擬存儲(chǔ)器

10/1Ap裝入位修改位標(biāo)志頁表長頁表地址As1p0/1裝入位實(shí)頁號(hào)修改位標(biāo)志段頁式虛擬存儲(chǔ)器

地址變換方法：用戶號(hào)U段號(hào)S虛頁號(hào)P頁內(nèi)偏移D實(shí)頁號(hào)p頁內(nèi)偏移d多用戶虛地址Av主存地址A段表地址寄存器多用戶段表多用戶頁表ApAs++造成虛擬存儲(chǔ)器速度降低的主要原因：要訪問主存儲(chǔ)器必須先查段表或頁表，如果頁表和段表在主存儲(chǔ)器內(nèi),包括訪問主存儲(chǔ)器本身這一次在內(nèi),主存儲(chǔ)器的訪問速度下降.當(dāng)頁表和段表的容量超過了一個(gè)頁面的大小時(shí),可能被映象到不連續(xù)的頁面位置上,這樣按照地址查找不能成立.可能需要多級(jí)頁表。4.加快地址變換的方法

為此采取幾種加快內(nèi)部地址變換的方法:

(1)目錄表(2)快慢表虛擬存儲(chǔ)器的地址變換

基本思想：用目錄表代替頁表,目錄表的行數(shù)是實(shí)頁數(shù),使用容量較小的相聯(lián)存儲(chǔ)器.

方法：把多用戶虛地址中的虛頁號(hào)(U與P拼接起來)作為關(guān)鍵字段對目錄表中所有存儲(chǔ)字的多用戶虛頁號(hào)字段進(jìn)行并行查找.如相等,把實(shí)頁號(hào)p與多用戶虛地址中的頁內(nèi)偏移D直接拼接起來,即是要訪問的主存實(shí)地址.如果沒有相等的,則表示要訪問的虛頁還沒有裝入主存,此時(shí)發(fā)出頁面失敗請求,從磁盤存儲(chǔ)器中把要訪問的那個(gè)頁調(diào)入主存.加快內(nèi)部地址變換的方法(1)目錄表用戶號(hào)U虛頁號(hào)P頁內(nèi)偏移D實(shí)頁號(hào)p頁內(nèi)偏移d目錄表地址變換方法U,Pp0/1多用戶虛頁號(hào)(U,P拼接)實(shí)頁號(hào)修改位其他標(biāo)志主存實(shí)地址多用戶虛地址相聯(lián)訪問目錄表(按內(nèi)容訪問的相聯(lián)存儲(chǔ)器)根據(jù)程序在執(zhí)行過程中的局部性特性,在一段時(shí)間內(nèi),地址變換對頁表的訪問會(huì)局限在少數(shù)存儲(chǔ)字內(nèi),因此,可大大縮小目錄表的存儲(chǔ)容量,例如,容量為8～16個(gè)存儲(chǔ)字,訪問速度與CPU中的通用寄存器相當(dāng),這個(gè)小容量的頁表成為快表TLB(Translation

LookasideBuffer).快表的容量小(幾～幾十個(gè)字)，高速硬件實(shí)現(xiàn)，采用相聯(lián)方式訪問.

與快表相對應(yīng)的存放在主存儲(chǔ)器中的頁表成為慢表,慢表是一個(gè)全表,快表是慢表的一個(gè)副本,而且只存放了慢表中很少一部分.快表與慢表也構(gòu)成了一個(gè)兩級(jí)存儲(chǔ)系統(tǒng)。加快內(nèi)部地址變換的方法(2)快慢表加快內(nèi)部地址變換的方法快慢表地址變換過程用多用戶虛頁號(hào)同時(shí)查快表和慢表.在快表中查到,終止查慢表,讀出實(shí)業(yè)頁號(hào)p送主存的地址寄存器.在快表中沒有查到,不終止慢表的查表過程.若在慢表中查到,把慢表中的實(shí)業(yè)頁號(hào)p送主存的地址寄存器.同時(shí)把實(shí)頁號(hào)連同用戶虛地址送人快表中.若慢表中也未查到,則發(fā)出頁面失敗請求.1

p裝入位實(shí)頁號(hào)U,Pp多用戶虛頁號(hào)(U,P拼接)實(shí)頁號(hào)用戶號(hào)U虛頁號(hào)P頁內(nèi)偏依D快慢表地址變換過程實(shí)頁號(hào)p頁內(nèi)偏移d多用戶虛地址慢表(按地址訪問)快表(按內(nèi)容相聯(lián)訪問)主存實(shí)地址慢表快表例:IMB370/168計(jì)算機(jī)的虛擬存儲(chǔ)器快表結(jié)構(gòu)及地址變換過程。采用頁式虛擬存儲(chǔ)器,虛擬地址長48位，頁面大小為4KB，每個(gè)用戶最多占用4K個(gè)頁面，最多允許2∧24個(gè)用戶，實(shí)際上同時(shí)上機(jī)的用戶數(shù)一般不超過6個(gè)?？毂戆吹刂吩L問,快表的地址由多用戶虛頁號(hào)經(jīng)硬件散列部件壓縮后生成.快表地址共6位,故快表容量為64個(gè)存儲(chǔ)字.

采用了兩項(xiàng)新的措施：

一是在快表的每一個(gè)存儲(chǔ)字中多用戶虛頁號(hào)與主存實(shí)頁號(hào),并采用兩個(gè)相等比較器。二是用相聯(lián)寄存器組把24位用戶號(hào)U壓縮成3位的ID.把這個(gè)ID與虛頁號(hào)直接拼接起來作為散列變換部件的輸入.虛擬存儲(chǔ)器舉例U1010U2011U3100U4101U5110U6111ID與P拼接pID與P拼接p多用戶虛頁號(hào)實(shí)地址多用戶虛頁號(hào)實(shí)地址用戶號(hào)U虛頁號(hào)P頁內(nèi)偏移DIMB370/168計(jì)算機(jī)的虛擬存儲(chǔ)器快表結(jié)構(gòu)及地址變換過程實(shí)頁號(hào)p頁內(nèi)偏移d多用戶虛地址24位12位12位相聯(lián)比較散列變換相聯(lián)寄存器組ID快表(按地址訪問,有兩組)相等比較相等比較拼接相等不等或相等不等12位主存實(shí)地址15位6位例4.14.3.2頁面替換算法及其命中率頁面替換發(fā)生時(shí)間：當(dāng)發(fā)生頁面失效時(shí)，要從磁盤中調(diào)入一頁到主存。如果主存所有頁面都已經(jīng)被占用，必須從主存儲(chǔ)器中淘汰掉一個(gè)不常使用的頁面，以便騰出主存空間來存放新調(diào)入的頁面。評(píng)價(jià)頁面替換算法好壞的標(biāo)準(zhǔn)：一是命中率要高;二是算法要容易實(shí)現(xiàn)。頁面替換算法的使用場合：(1)虛擬存儲(chǔ)器中，主存頁面的替換，一般用軟件實(shí)現(xiàn)。(2)Cache中的塊替換，一般用硬件實(shí)現(xiàn)。(3)虛擬存儲(chǔ)器的快慢表中，快表存儲(chǔ)字的替換，用硬件實(shí)現(xiàn)。(4)虛擬存儲(chǔ)器中，用戶基地址寄存器的替換，用硬件實(shí)現(xiàn)。(5)在有些虛擬存儲(chǔ)器中，目錄表的替換。頁面替換算法及其命中率1.幾種頁面替換算法常用的頁面替換算法：(1)隨機(jī)算法（RANDRandomalgorithm）：算法簡單，容易實(shí)現(xiàn)。沒有利用歷史信息，沒有反映程序的局部性，命中率低。(2)先進(jìn)先出算法（FIFOFirst-InFirst-Outalgorithm）：選擇最早裝入主存的虛頁作為被替換頁.在頁表和目錄表中對每個(gè)頁增設(shè)一個(gè)“年齡記數(shù)器”字段,剛調(diào)入的虛頁的計(jì)數(shù)器的記數(shù)值為0,每調(diào)入一個(gè)虛頁時(shí),其他裝入頁的記數(shù)值都加1,需要替換時(shí),只需要找出記數(shù)值最大的裝入頁就是最進(jìn)入的虛頁.比較容易實(shí)現(xiàn)，利用了歷史信息，沒有反映程序的局部性。最先調(diào)入主存的頁面，很可能也是經(jīng)常要使用的頁面。頁面替換算法及其命中率(3)近期最少使用算法（LRULeastRecentlyUsedalgorithm

）：選擇過去近期訪問次數(shù)最少的虛頁作為被替換頁.這種算法能比較好地反映程序局部性,因?yàn)橐话憬谧钌偈褂玫捻撛谖磥硪欢螘r(shí)間內(nèi)也將最少被訪問.在目錄表或頁表中,對每個(gè)頁增設(shè)一個(gè)“使用次數(shù)計(jì)數(shù)器”字段,某個(gè)頁被訪問一次時(shí),該頁的計(jì)數(shù)器字段加1.計(jì)數(shù)值最小的頁被替換.

既充分利用了歷史信息，又反映了程序的局部性實(shí)現(xiàn)起來非常困難。

(4)最久沒有使用算法（LFULeastFrequentlyUsedalgorithm

）：選擇過去近期最久訪問的虛頁作為被替換的頁.這種算法也比較好地反映了程序的局部性,因?yàn)橐话憬谧罹檬褂玫捻撛谖磥硪欢螘r(shí)間也將最久被訪問.在頁表或目錄表中,對每個(gè)頁增設(shè)一個(gè)“使用計(jì)數(shù)器”字段,某頁被訪問時(shí),該頁的計(jì)數(shù)器字段請0,其他裝入頁的計(jì)數(shù)器的值都加1,計(jì)數(shù)器的值最大的頁是被替換的頁.它與LRU算法相比,為支持替換算法的實(shí)現(xiàn),增加的內(nèi)容要少，實(shí)現(xiàn)起來比較容易。幾種頁面替換算法幾種頁面替換算法

(5)最優(yōu)替換算法（OPTOPTimal

replacemantalgorithm）：

是一種理想化的算法。是選擇將來一段時(shí)間最久被訪問的的頁作為被替換的頁.為了算法的實(shí)現(xiàn),需讓程序先運(yùn)行一遍得到程序的全部虛頁號(hào)序列(虛頁地址流),才能在替換時(shí)確定未來一段時(shí)間內(nèi)哪一頁是最久被訪問的.這是一種最優(yōu)的替換算法,常用來作為評(píng)價(jià)其它頁面替換算法好壞的標(biāo)準(zhǔn)。例:一個(gè)程序共有5個(gè)頁面組成，分別為P1～P5。程序執(zhí)行過程中的頁地址流（即程序執(zhí)行中依次用到的頁面）如下：P1，P2，P1，P5，P4，P1，P3，P4，P2，P4

假設(shè)分配給這個(gè)程序的主存儲(chǔ)器共有3個(gè)頁面。給出FIFO、LFU和OPT三種頁面替換算法對這3頁主存的使用情況，包括調(diào)入、替換和命中等。頁面替換算法及其命中率2.頁面替換算法的命中率計(jì)算*例2：一個(gè)循環(huán)程序，依次使用P1，P2，P3，P4四個(gè)頁面，分配給這個(gè)程序的主存頁面數(shù)為3個(gè)。FIFO、LFU和OPT三種頁面替換算法對主存頁面的調(diào)度情況如下圖所示。在FIFO和LFU算法中，總是發(fā)生下次就要使用的頁面本次被替換出去的情況，這就是“顛簸”現(xiàn)象。2.頁面替換算法的命中率計(jì)算

頁面替換算法的主存命中率H與分配給程序的主存實(shí)頁數(shù)n有關(guān).如果替換算法具有下述性質(zhì):隨著分配給程序的主存實(shí)頁數(shù)n的增加,替換算法到主存命中率H也隨之增加,至少不下降.那么,這種替換算法就稱為堆棧型替換算法.1.堆棧型替換算法的含義：設(shè)A為長度為L的任意一個(gè)虛頁地址流,t為已處理過t-1個(gè)虛頁的時(shí)間點(diǎn),n為分配給該虛頁地址流的主存實(shí)頁數(shù),Bt(n)表示在t時(shí)間點(diǎn)、在n個(gè)實(shí)頁的虛頁集合,Lt表示到t時(shí)間點(diǎn)已處理過的虛頁地址流中虛頁號(hào)相異的頁號(hào).如果替換算法具有下列包容性質(zhì):n＜Lt時(shí)Bt(n)

Bt(n+1)

n≥Lt

時(shí)Bt(n)＝Bt(n+1)則這類算法稱為堆棧型替換算法。

4.3.3堆棧型替換算法及其堆棧處理過程堆棧型替換算法的含義：也可以定義為:對任意一個(gè)程序的頁地址流作兩次主存頁面數(shù)分配，分別分配m個(gè)主存頁面和n個(gè)主存頁面，并且有m≤n。如果在任何時(shí)刻t，主存頁面數(shù)集合Bt都滿足關(guān)系：Bt（m）

Bt（n)

堆棧型算法的基本特點(diǎn)是：隨著分配給程序的主存頁面數(shù)增加，主存的命中率也提高，至少不下降。堆棧型替換算法的含義根據(jù)堆棧型替換算法的含義,可以證明LRU、LFU和OPT算法都是堆棧型替換算法.對于LRU算法,由于在主存中保留的是最近使用過的虛頁,如果先給某個(gè)程序分配n個(gè)主存實(shí)頁,那么在t時(shí)刻,這n個(gè)主存實(shí)頁位置中都是最近使用過的虛頁.如果再給這個(gè)程序多分配一個(gè)主存實(shí)頁,那么在t時(shí)刻,這n+1個(gè)主存實(shí)頁的位置中也都是最近使用過的虛頁.因此,這n+1個(gè)主存實(shí)頁位置中的虛頁集合Bt(n+1)必然包含了其中n個(gè)主存實(shí)頁位置的虛頁集合Bt(n).所以,LRU算法是堆棧型替換算法.FIFO算法不是堆棧型算法(見下例)LFU算法、LRU算法和OPT算法都是堆棧型算法。FIFO算法不是堆棧型算法堆棧型替換算法及其堆棧處理過程2.堆棧對訪存虛頁地址流的處理過程用堆棧處理技術(shù)對訪存虛頁地址流進(jìn)行處理時(shí),主存在t時(shí)間點(diǎn)的狀態(tài)用堆棧St表示,

St是

Lt個(gè)不同虛頁號(hào)在堆棧中的

有序集,St(1)是St

的棧頂項(xiàng),St(2)是St

的次頂項(xiàng),依次類推.按照堆棧型替換算法具有的包容性,有n＜Lt

時(shí)Bt(n)=｛St(1),

St(2),St(n)｝

n≥Lt

時(shí),Bt(n)=｛St(1),St(2),St(Lt)｝

這樣,對程序分配n個(gè)實(shí)頁,且在這n個(gè)實(shí)頁位置上存放了哪些虛頁的虛頁號(hào)就在堆棧St的前n項(xiàng)中.因此,對虛頁地址流A在t時(shí)間點(diǎn)的At

虛頁是否命中,只需看St-1的前n項(xiàng)是否有At頁,若有,則命中.所以,經(jīng)過一次處理獲得St(1),St(2),St(Lt)之后,就知道對應(yīng)于不同n值時(shí)的主存命中率,從而為該道程序按所需要達(dá)到的訪問命中率來確定應(yīng)分配給它的主存實(shí)頁數(shù).堆棧對訪存虛頁地址流的處理過程

對于不同的堆棧型替換算法,堆棧St各項(xiàng)的改變過程是不同的.例如LRU算法把剛訪問過的虛頁號(hào)壓入棧頂單元后,把棧頂單元中的虛頁號(hào)與其他堆棧單元中的虛頁號(hào)進(jìn)行比較,去掉與棧頂單元虛頁號(hào)相同的其他棧頂單元,從而保證堆棧單元中保留的虛頁號(hào)都是相異頁號(hào).使得在任何時(shí)刻,堆棧中的虛頁號(hào)集合是按過去訪問的時(shí)間順序排序的,剛訪問的虛頁的置于棧頂單元中,最久訪問的虛頁的虛頁號(hào)置于棧底單元中.例4.54.3高速緩沖存儲(chǔ)器（Cache）4.4.1Cache的地址映象與地址變換4.4.2Cache的替換算法及其實(shí)現(xiàn)4.4.3Cache的性能分析Cache與虛擬存儲(chǔ)器的主要區(qū)別

在Cache系統(tǒng)中,Cache和主存儲(chǔ)器都劃分成相同大小的(Block）。主存地址由塊號(hào)B和塊內(nèi)地址W兩部分組成。Cache的地址也由塊號(hào)b和塊內(nèi)地址w組成。地址映象是把存放在主存中的程序按照某種規(guī)則裝入到Cache中，并建立主存地址與Cache地址之間的對應(yīng)關(guān)系。

地址變換是當(dāng)程序已經(jīng)裝入到Cache之后，在實(shí)際運(yùn)行過程中，把主存地址變換成Cache地址。

4.4.1Cache的地址映象與地址變換高速緩沖存儲(chǔ)器地址映象與變換方法1.

全相聯(lián)映象及其變換映象規(guī)則：主存的任意一塊可以映象到Cache

中的任意一塊的位置上。如果Cache的塊數(shù)為Cb，主存的塊數(shù)為Mb，映象關(guān)系共有Cb×Mb種。全相聯(lián)映象及其變換地址變換規(guī)則用主存地址的塊號(hào)B與目錄表中的主存塊號(hào)字段進(jìn)行相聯(lián)比較如果相等,命中;不等,失效;用主存地址訪問主存,把讀出的一個(gè)字送往CPU,同時(shí)把包含這個(gè)字那一塊裝入Cache,并修改目錄表.全相聯(lián)映象及其變換的優(yōu)點(diǎn):沖突率低,Cache的利用率高;缺點(diǎn)是需要一個(gè)訪問速度快、容量為Cb

個(gè)字的相聯(lián)存儲(chǔ)器.相聯(lián)存儲(chǔ)器的存儲(chǔ)字字長=B的長度+b的長度+1=log2CB+log2Cb+1全相聯(lián)映象及其變換

例:在Cache存儲(chǔ)器中,Cache的容量是字節(jié),主存是由m個(gè)存儲(chǔ)體組成的低位交叉并行存儲(chǔ)器,主存容量是字節(jié),按存儲(chǔ)單元編址,每個(gè)存儲(chǔ)體的存儲(chǔ)單元是k字節(jié).采取全相聯(lián)映象,用相聯(lián)目錄表實(shí)現(xiàn)地址變換.(1)寫出主存地址和Cache地址的格式,并指出各字段的長度.(2)求出目錄表的行數(shù)、相聯(lián)比較的位數(shù)和目錄表的寬度.例4.62.直接映象及其變換映象規(guī)則：主存地址分為三部分:區(qū)號(hào)E,區(qū)內(nèi)塊號(hào)B,塊內(nèi)地址W主存各區(qū)的容量與Cache的容量相等.Cache地址分為塊號(hào)b和塊內(nèi)地址w.主存中各區(qū)內(nèi)的一塊只能裝到與Cache塊號(hào)相同的那個(gè)特定的位置上。

整個(gè)Cache地址與主存地址的低位部分完全相同。

地址映象與變換方法2.直接映象及其變換直接映象方式的地址變換過程：(由存放在Cache中的區(qū)表實(shí)現(xiàn),區(qū)表行數(shù)等于Cache的塊數(shù),一行二個(gè)字段:區(qū)號(hào)E,有效位)用主存地址中的塊號(hào)B去訪問區(qū)表存儲(chǔ)器;把讀出來的區(qū)號(hào)與主存地址中的區(qū)號(hào)E進(jìn)行比較：比較結(jié)果相等:有效位為1，則Cache命中;有效位為0,該塊同已被修改過的主存的副本塊的內(nèi)容不一致,已經(jīng)作廢,需重寫該塊,并把有效位置1;比較結(jié)果不相等:有效位為1，沒有命中,但Cache中的該塊是有用的，需把該塊調(diào)出寫入主存,再從主存調(diào)入所需要的新塊;有效位為0,沒有命中,且該Cache塊已作廢,可直接調(diào)入所需要的新塊。

2.直接映象及其變換直接映象方式的地址變換規(guī)則

提高Cache速度的一種方法：

把區(qū)號(hào)存儲(chǔ)器與Cache合并成一個(gè)存儲(chǔ)器2.直接映象及其變換的優(yōu)缺點(diǎn)

主要優(yōu)點(diǎn)：

硬件實(shí)現(xiàn)很簡單，不需要相聯(lián)訪問存儲(chǔ)器訪問速度也比較快，實(shí)際上不需要進(jìn)行地址變換主要缺點(diǎn)：塊的沖突率比較高地址映象與變換方法3.組相聯(lián)映象及其變換

是介于全相聯(lián)映象和直接映象之間的一種折中方式,是目前應(yīng)用的比較多的一種映象方式.

映象規(guī)則：主存按Cache的大小分區(qū),區(qū)內(nèi)和Cache按同樣大小劃分成塊和組。從主存的組到Cache的組之間采用直接映象方式。在兩個(gè)對應(yīng)的組內(nèi)部采用全相聯(lián)映象方式。組相聯(lián)映象的地址變換地址變換過程：通過塊表實(shí)現(xiàn).塊表行數(shù)是Cache的塊數(shù),每行包括E、B、b和有效位e.用主存地址中的組號(hào)G作首址,在塊表存儲(chǔ)器中連續(xù)訪問多行(一組內(nèi)各塊)。把讀出來的一組字中區(qū)號(hào)和塊號(hào)與主存地址中的區(qū)號(hào)和塊號(hào)進(jìn)行相聯(lián)比較：如果有一行相等，表示Cache命中；如果沒有相等的，表示Cache沒有命中。(1)用相聯(lián)訪問存儲(chǔ)器的組相聯(lián)地址變換有效位(塊表的行數(shù)是Cache的塊數(shù))(2)用多個(gè)相等比較器來代替相聯(lián)訪問的組相聯(lián)地址變換-—提高Cache的訪問速度的一種方法.塊表的行數(shù)是Cache的組數(shù),塊表的一行由多存儲(chǔ)字組成（組內(nèi)塊數(shù)Cb),一個(gè)存儲(chǔ)字由4個(gè)字段組成:主存區(qū)號(hào)E,主存組內(nèi)塊號(hào)B,Cache組內(nèi)塊號(hào)b和有效位.把CPU送來的主存地址中的組號(hào)G與塊表基址相加作為訪問塊表的物理地址,讀出該行中有效位是“有效”的所有存儲(chǔ)字;通過相等比較電路把主存地址中的區(qū)號(hào)E和塊號(hào)B同時(shí)與這些有效存儲(chǔ)字中的區(qū)號(hào)E字段和塊號(hào)B字段進(jìn)行比較:若其中有一個(gè)有效存儲(chǔ)字的區(qū)號(hào)E和塊號(hào)B分別與主存地址中的區(qū)號(hào)E和塊號(hào)B相等,則把該存儲(chǔ)字中的塊號(hào)b和主存地址中的組號(hào)G以及塊內(nèi)地址W組成Cache地址;若沒有一個(gè)存儲(chǔ)字相等,則發(fā)生塊失敗.組相聯(lián)映象及其變換

(2)用多個(gè)相等比較器來代替相聯(lián)訪問的組相聯(lián)地址變換組相聯(lián)映象及其變換一些典型機(jī)器的Cache分組情況組相聯(lián)映象及其變換組相聯(lián)映象方式的優(yōu)點(diǎn)：

塊的沖突概率比較低，塊的利用率大幅度提高，塊失效率明顯降低。組相聯(lián)映象方式的缺點(diǎn)：

實(shí)現(xiàn)難度和造價(jià)要比直接映象方式高。組相聯(lián)映象及其變換

例4.7采用組相聯(lián)映象的Cache存儲(chǔ)器,Cache的容量為1K字,要求Cache的每一塊在一個(gè)主存訪問周期能從主存取得.主存采用4個(gè)低位交叉編址的存儲(chǔ)體組成,主存容量為256K字.采用按地址訪問存儲(chǔ)器存放塊表來實(shí)現(xiàn)地址變換,并采用4個(gè)相等比較電路.請?jiān)O(shè)計(jì)地址變換的塊表,求出該表的行數(shù)和容量.說明地址變換過程及每個(gè)相等比較電路進(jìn)行相等比較的位數(shù).例4.8何時(shí)使用Cache替換算法：

發(fā)生塊失效，且可以裝入新調(diào)入塊的幾個(gè)Cache塊都已經(jīng)被裝滿時(shí),使用替換算法將Cache中某一塊替換出去。

對于:直接映象方式實(shí)際上不需要替換算法。全相聯(lián)映象方式的替換算法最復(fù)雜。在組相聯(lián)和位選擇相聯(lián)映象及地址變換中,需要從Cache同一組內(nèi)的幾個(gè)塊中選擇一塊替換出去.Cache替換算法及其實(shí)現(xiàn)Cache替換算法要解決的問題：1.記錄每次訪問Cache的塊號(hào)。2.管理好所記錄的Cache塊號(hào)，為找出被替換的塊號(hào)提供方便。3.根據(jù)記錄和管理的結(jié)果，找出被替換的塊號(hào)。Cache替換算法的主要特點(diǎn)：全部用硬件實(shí)現(xiàn)Cache替換算法及其實(shí)現(xiàn)幾種替換算法Cache替換算法及其實(shí)現(xiàn)1.隨機(jī)替換算法2.FIFO替換算法

通常用于組相聯(lián)映像及地址變換方式中,有以下兩種實(shí)現(xiàn)方法:(1)每塊一個(gè)計(jì)數(shù)器實(shí)現(xiàn)方法在塊表內(nèi)增加一個(gè)替換計(jì)數(shù)器字段,計(jì)數(shù)器的長度與Cache地址中的組內(nèi)塊號(hào)b字段的長度相同。新裝入或替換的塊，它的計(jì)數(shù)器清0，同組其它塊的計(jì)數(shù)器都加“1”。在同組中選擇計(jì)數(shù)器的值最大的塊作為被替換的塊。例1：Solar-16/65小型機(jī)的Cache采用位選擇組相聯(lián)映象方式。Cache每組的塊數(shù)為4，因此，每塊用一個(gè)2位的計(jì)數(shù)器。Cache替換算法及其實(shí)現(xiàn)2.FIFO替換算法(2)每組一個(gè)計(jì)數(shù)器的實(shí)現(xiàn)方法FIFO替換算法實(shí)際上是同組內(nèi)的塊按順序輪流替換,因此只要為每一組設(shè)置一個(gè)計(jì)數(shù)器即可.如果每組的塊數(shù)為Cb,設(shè)置一個(gè)模為Cb

的計(jì)數(shù)器,它最先指向該組最先進(jìn)來的塊,該塊被替換后記數(shù)值加1,指向下一個(gè)要替換的塊.最先裝入的塊,有可能是經(jīng)常要用的塊,因此,FIFO替換算法的效果雖然比隨機(jī)替換算法好,但仍不理想.例2：NOVA3機(jī)的Cache采用組相聯(lián)映象方式，Cache每組的塊數(shù)為8，每組設(shè)置一個(gè)3位計(jì)數(shù)器。在需要替換時(shí)，計(jì)數(shù)器的值加“1”，用計(jì)數(shù)器的值直接作為被替換塊的塊號(hào)。3.LFU算法及其實(shí)現(xiàn)(最久沒有使用算法,Leastfrequentlyusedalgorithm)(1)計(jì)數(shù)器法為每一塊設(shè)置一個(gè)計(jì)數(shù)器計(jì)數(shù)器的長度與Cache地址中的組內(nèi)塊號(hào)字段的長度相同.計(jì)數(shù)器的使用及管理規(guī)則：新裝入或替換的塊，計(jì)數(shù)器清“0”，同組中其它塊的計(jì)數(shù)器都加“1”。命中塊的計(jì)數(shù)器清0，同組的其它計(jì)數(shù)器中，凡計(jì)數(shù)器的值小于命中塊計(jì)數(shù)器原來值的加1，其余計(jì)數(shù)器不變。需要替換時(shí)，在同組的所有計(jì)數(shù)器中選擇計(jì)數(shù)值最大的計(jì)數(shù)器，它所對應(yīng)的塊被替換。例：IBM370/165機(jī)的Cache采用組相聯(lián)映象方式。每組有4塊，為了實(shí)現(xiàn)LFU替換算法，在塊表中為每一塊設(shè)置一個(gè)2位的計(jì)數(shù)器。在訪問Cache的過程中，塊的裝入、替換及命中時(shí)，計(jì)數(shù)器的工作情況如表.LFU算法及其實(shí)現(xiàn)LFU算法及其實(shí)現(xiàn)(2)比較對法基本思想用2個(gè)塊組成一個(gè)比較對,利用一個(gè)觸發(fā)器的狀態(tài)表示該比較對的兩塊被訪問的先后順序,經(jīng)門電路組合,可從多個(gè)塊中找出最久被訪問過的塊.實(shí)現(xiàn)方法以3個(gè)塊為例.設(shè)有3個(gè)塊A、B、C,可組合成3個(gè)比較對:AB、AC和BC.用一個(gè)觸發(fā)器的狀態(tài)表示一個(gè)比較對中兩塊被訪問的順序,例如,觸發(fā)器TAB=1,表示A比B更近被訪問過,TAB=0表示B比A更近被訪問過.3個(gè)塊最久被訪問過的條件分別是:LRU算法及其實(shí)現(xiàn)(2)比較對法實(shí)現(xiàn)方法01TAB01TAC01TBC&&&ALFUBLFUCLFU訪問B訪問C訪問ACache的性能分析Cache存儲(chǔ)系統(tǒng)的主要目標(biāo)：提高存儲(chǔ)系統(tǒng)的速度Cache存儲(chǔ)系統(tǒng)的加速比Cache存儲(chǔ)系統(tǒng)的一致性問題1.加速比與命中率的關(guān)系Cache存儲(chǔ)系統(tǒng)的加速比SP為：

其中：Tm為主存儲(chǔ)器的訪問周期，

Tc為Cache的訪問周