課件intellect系統(tǒng)結(jié)構(gòu)第3章

現(xiàn)代計(jì)算機(jī)系統(tǒng)以存儲(chǔ)器為中心對(duì)存儲(chǔ)器的要求：

1、存儲(chǔ)器的容量要跟上用戶(hù)程序的需求。容量要大

2、速度要快，要跟上CPU的速度。

3、合適的性?xún)r(jià)比現(xiàn)實(shí)：存儲(chǔ)器的容量和速度都在不斷的提高，但總不能滿(mǎn)足用戶(hù)的需求。有戶(hù)的軟件體積越來(lái)越大，CPU的速度也越來(lái)越快。

第3章存儲(chǔ)系統(tǒng)01六月2023計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第三章存儲(chǔ)系統(tǒng)2存儲(chǔ)器取指令取數(shù)據(jù)寫(xiě)數(shù)據(jù)I/O設(shè)備01六月2023計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第三章存儲(chǔ)系統(tǒng)3本章內(nèi)容3.1存儲(chǔ)系統(tǒng)原理

3.2虛擬存儲(chǔ)系統(tǒng)

3.3高速緩沖存儲(chǔ)器系統(tǒng)(Cache)3.4三級(jí)存儲(chǔ)系統(tǒng)3.1存儲(chǔ)系統(tǒng)原理 3.1.1存儲(chǔ)系統(tǒng)的定義

3.1.2存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)

3.1.3存儲(chǔ)系統(tǒng)的頻帶平衡

3.1.4并行訪問(wèn)存儲(chǔ)器

3.1.5交叉訪問(wèn)存儲(chǔ)器

3.1.6無(wú)沖突訪問(wèn)存儲(chǔ)器3.1.1存儲(chǔ)系統(tǒng)的定義

在一臺(tái)計(jì)算機(jī)中，通常有多種存儲(chǔ)器。他們的種類(lèi)、材料、價(jià)格、性能各不相同種類(lèi)：主存儲(chǔ)器、Cache、通用寄存器、緩沖存儲(chǔ)器、磁盤(pán)存儲(chǔ)器、磁帶存儲(chǔ)器、光盤(pán)存儲(chǔ)器等材料工藝：ECL、TTL、MOS、磁表面、激光，

SRAM，DRAM、DDRAM訪問(wèn)方式：隨機(jī)訪問(wèn)、直接譯碼、先進(jìn)先出、相聯(lián)訪問(wèn)、塊傳送、文件組

存儲(chǔ)器的主要性能：速度、容量、價(jià)格

速度用存儲(chǔ)器的訪問(wèn)周期、讀出時(shí)間、頻帶寬度等表示。

容量用字節(jié)B、千字節(jié)KB、兆字節(jié)MB和千兆字節(jié)GB等單位表示。

價(jià)格用單位容量的價(jià)格表示，例如：$C/bit。

組成存儲(chǔ)系統(tǒng)的關(guān)鍵：把速度、容量和價(jià)格不同的多個(gè)物理存儲(chǔ)器組織成一個(gè)存儲(chǔ)器，這個(gè)存儲(chǔ)器的速度最快，存儲(chǔ)容量最大，單位容量的價(jià)格最便宜。1.存儲(chǔ)系統(tǒng)的定義兩個(gè)或兩個(gè)以上速度、容量和價(jià)格各不相同的存儲(chǔ)器用硬件、軟件、或軟件與硬件相結(jié)合的方法連接起來(lái)成為一個(gè)存儲(chǔ)系統(tǒng)。這個(gè)存儲(chǔ)系統(tǒng)對(duì)應(yīng)用程序員是透明的，并且，從應(yīng)用程序員看，它是一個(gè)存儲(chǔ)器，這個(gè)存儲(chǔ)器的速度接近速度最快的那個(gè)存儲(chǔ)器，存儲(chǔ)容量與容量最大的那個(gè)存儲(chǔ)器相等，單位容量的價(jià)格接近最便宜的那個(gè)存儲(chǔ)器。虛擬存儲(chǔ)器系統(tǒng)：對(duì)應(yīng)用程序員透明Cache存儲(chǔ)系統(tǒng)：對(duì)系統(tǒng)程序員以上均透明由多個(gè)存儲(chǔ)器構(gòu)成的存儲(chǔ)系統(tǒng)

在一般計(jì)算機(jī)系統(tǒng)中，有兩種存儲(chǔ)系統(tǒng)：Cache存儲(chǔ)系統(tǒng)：由Cache和主存儲(chǔ)器構(gòu)成主要目的：提高存儲(chǔ)器速度虛擬存儲(chǔ)系統(tǒng)：由主存儲(chǔ)器和硬盤(pán)構(gòu)成主要目的：擴(kuò)大存儲(chǔ)器容量2.存儲(chǔ)系統(tǒng)的容量要求：提供盡可能大的地址空間能夠隨機(jī)訪問(wèn)方法有兩種：只對(duì)系統(tǒng)中存儲(chǔ)容量最大的那個(gè)存儲(chǔ)器進(jìn)行編址，其他存儲(chǔ)器只在內(nèi)部編址或不編址

Cache存儲(chǔ)系統(tǒng)另外設(shè)計(jì)一個(gè)容量很大的邏輯地址空間，把相關(guān)存儲(chǔ)器都映射這個(gè)地址空間中

虛擬存儲(chǔ)系統(tǒng)3.存儲(chǔ)系統(tǒng)的價(jià)格計(jì)算公式：當(dāng)S2》S1時(shí)，C≈C2S2與S1不能相差太大4.存儲(chǔ)系統(tǒng)的速度表示方法：訪問(wèn)周期、存取周期、存儲(chǔ)周期、存取時(shí)間等命中率定義：在M1存儲(chǔ)器中訪問(wèn)到的概率

其中：N1是對(duì)M1存儲(chǔ)器的訪問(wèn)次數(shù)

N2是對(duì)M2存儲(chǔ)器的訪問(wèn)次數(shù)訪問(wèn)周期與命中率的關(guān)系：

T＝HT1＋(1－H)T2

當(dāng)命中率H→1時(shí)，T→T1存儲(chǔ)系統(tǒng)的訪問(wèn)效率：訪問(wèn)效率主要與命中率和兩級(jí)存儲(chǔ)器的速度之比有關(guān)例3.1：假設(shè)T2＝５T１，在命中率H為0.9和0.99兩種情況下，分別計(jì)算存儲(chǔ)系統(tǒng)的訪問(wèn)效率。解：當(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)速度的兩條途徑：一是提高命中率H，二是兩個(gè)存儲(chǔ)器的速度不要相差太大其中：第二條有時(shí)做不到(如虛擬存儲(chǔ)器)，這時(shí)，只能依靠提高命中率例3.2：在虛擬存儲(chǔ)系統(tǒng)中，兩個(gè)存儲(chǔ)器的速度相差特別懸殊，例如：T2＝105T１。如果要使訪問(wèn)效率到達(dá)e＝0.9，問(wèn)需要有多高的命中率？解：0.9H＋90000(1-H)＝189999.1H＝89999計(jì)算得：

H＝0.999998888877777…≈0.9999995.采用預(yù)取技術(shù)提高命中率方法：不命中時(shí)，把M2存儲(chǔ)器中相鄰多個(gè)單元組成的一個(gè)數(shù)據(jù)塊取出來(lái)送入M1存儲(chǔ)器中。

計(jì)算公式：其中：H’是采用預(yù)取技術(shù)之后的命中率

H是原來(lái)的命中率

n為數(shù)據(jù)塊大小與數(shù)據(jù)重復(fù)使用次數(shù)的乘積例3.3：在一個(gè)Cache存儲(chǔ)系統(tǒng)中，當(dāng)Cache的塊大小為一個(gè)字時(shí)，命中率H＝0.8；假設(shè)數(shù)據(jù)的重復(fù)利用率為5，T2＝5T1。計(jì)算塊大小為４個(gè)字時(shí)，Cache存儲(chǔ)系統(tǒng)的命中率？并分別計(jì)算訪問(wèn)效率。解：n＝4×5＝20，采用預(yù)取技術(shù)之后，命中率提高到：例3.4：在一個(gè)虛擬存儲(chǔ)系統(tǒng)中，T2＝105T１，原來(lái)的命中率只有0.8，如果訪問(wèn)磁盤(pán)存儲(chǔ)器的數(shù)據(jù)塊大小為4K字，并要求訪問(wèn)效率不低于0.9，計(jì)算數(shù)據(jù)在主存儲(chǔ)器中的重復(fù)利用率至少為多少？解：假設(shè)數(shù)據(jù)在主存儲(chǔ)器中的重復(fù)利用率為m，根據(jù)前面給出的關(guān)系，有如下方程組：解方程組：由方程(1)得到：0.9HH=13.1.2存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)多個(gè)層次的存儲(chǔ)器：第1層：RegisterFiles(寄存器堆)

第2層：Buffers(Lookahead)(先行緩沖站)

第3層：Cache(高速緩沖存儲(chǔ)器)

第4層：MainMemory(主存儲(chǔ)器)

第5層：OnlineStorage(聯(lián)機(jī)存儲(chǔ)器)

第6層：Off-lineStorage(脫機(jī)存儲(chǔ)器)用i表示層數(shù)，則有：工作周期Ti＜Ti+1，存儲(chǔ)容量：Si＜Si+1，單位價(jià)格：Ci＞Ci+1各級(jí)存儲(chǔ)器的主要主要性能特性

CPU與主存儲(chǔ)器的速度差距越來(lái)越大目前相差兩個(gè)數(shù)量級(jí)

今后CPU與主存儲(chǔ)器的速度差距會(huì)更大3.1.3存儲(chǔ)系統(tǒng)的頻帶平衡例3.5：Pentium4的指令執(zhí)行速度為8GIPS，CPU取指令8GW/s，訪問(wèn)數(shù)據(jù)16GW/s，各種輸入輸出設(shè)備訪問(wèn)存儲(chǔ)器1GW/s，三項(xiàng)相加，要求存儲(chǔ)器的頻帶寬度不低于25GW/s。如果采用PC133內(nèi)存，主存與CPU速度差188倍如果采用PC266內(nèi)存，主存與CPU速度差94倍解決存儲(chǔ)器頻帶平衡方法

(1)并行工作（并行和交叉）（本節(jié)下面介紹）

(2)設(shè)置各種緩沖存儲(chǔ)器（第五章介紹）

(3)采用存儲(chǔ)系統(tǒng)（本章第二、第三節(jié)介紹）3.1.4并行訪問(wèn)存儲(chǔ)器方法：把m字w位的存儲(chǔ)器改變成為m/n字n×w位的存儲(chǔ)器邏輯實(shí)現(xiàn)：把地址碼分成兩個(gè)部分，一部分作為存儲(chǔ)器的地址另一部分負(fù)責(zé)選擇數(shù)據(jù)主要缺點(diǎn)：訪問(wèn)沖突大

(1)取指令沖突(當(dāng)遇到轉(zhuǎn)移指令時(shí)）

(2)讀操作數(shù)沖突（需要的幾個(gè)操作數(shù)不一定在一個(gè)字內(nèi)）

(3)寫(xiě)數(shù)據(jù)沖突（必須湊夠n個(gè)數(shù)才能一起寫(xiě)入）

(4)讀寫(xiě)沖突（寫(xiě)數(shù)據(jù)和讀數(shù)據(jù)在同一個(gè)字內(nèi)時(shí))

并行訪問(wèn)存儲(chǔ)器結(jié)構(gòu)框圖00000000

XXX

XX

X

XXX8X84X162X321.高位交叉訪問(wèn)存儲(chǔ)器主要目的：擴(kuò)大存儲(chǔ)器容量實(shí)現(xiàn)方法：用地址碼的高位部分區(qū)分存儲(chǔ)體號(hào)參數(shù)計(jì)算方法:

m：每個(gè)存儲(chǔ)體的容量，

n：總共的存儲(chǔ)體個(gè)數(shù)，

j：存儲(chǔ)體的體內(nèi)地址，j＝0，1，2，...，m-1k：存儲(chǔ)體的體號(hào)，k＝0，1，2，...，n-1

存儲(chǔ)器的地址：A＝m×k＋j

存儲(chǔ)器的體內(nèi)地址：Aj＝Amodm。存儲(chǔ)器的體號(hào)：Ak＝3.1.5交叉訪問(wèn)存儲(chǔ)器

高位交叉訪問(wèn)存儲(chǔ)器結(jié)構(gòu)框圖01六月2023計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第三章存儲(chǔ)系統(tǒng)307654321015141312111098232221201918171631302928272625240#1#2#3#

xxxxx例3.6：用4M字×4位的存儲(chǔ)芯片組成16M×32位的主存儲(chǔ)器。共用存儲(chǔ)芯片：用最高2位地址經(jīng)譯碼后產(chǎn)生的信號(hào)，控制各組存儲(chǔ)芯片CS。每組中的32根數(shù)據(jù)線分別對(duì)應(yīng)直接相連，稱(chēng)為“線或”方式。2.低位交叉訪問(wèn)存儲(chǔ)器主要目的：提高存儲(chǔ)器訪問(wèn)速度實(shí)現(xiàn)方法：用地址碼的低位部分區(qū)分存儲(chǔ)體號(hào)參數(shù)計(jì)算:

m：每個(gè)存儲(chǔ)體的容量，

n：總共的存儲(chǔ)體個(gè)數(shù)，

j：存儲(chǔ)體的體內(nèi)地址，j＝0，1，2，...，m-1k：存儲(chǔ)體的體號(hào)，k＝0，1，2，...，n-1

存儲(chǔ)器地址A的計(jì)算公式為：A＝n×j＋k

存儲(chǔ)器的體內(nèi)地址：Aj＝存儲(chǔ)器的體號(hào)：Ak＝Amodn

低位交叉訪問(wèn)存儲(chǔ)器結(jié)構(gòu)框圖

地址是編碼方法：由8個(gè)存儲(chǔ)體構(gòu)成的低位交叉編址方式主存儲(chǔ)器數(shù)據(jù)寄存器0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263體內(nèi)地址(3位)模塊地址(3位)主存儲(chǔ)器地址寄存器（6位）體內(nèi)地址2體數(shù)8體號(hào)3

n個(gè)存儲(chǔ)體分時(shí)啟動(dòng)一種采用流水線方式工作的并行存儲(chǔ)器每存儲(chǔ)體的啟動(dòng)間隔為：t＝其中：

Tm為每個(gè)存儲(chǔ)體的訪問(wèn)周期,

n為存儲(chǔ)體個(gè)數(shù)。01六月2023計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第三章存儲(chǔ)系統(tǒng)36問(wèn)題：由n個(gè)存儲(chǔ)體構(gòu)成的低位交叉的存儲(chǔ)器速度是否一定提高n倍？試舉例說(shuō)明。1、遇到轉(zhuǎn)移指令時(shí)2、使用數(shù)據(jù)的隨機(jī)性3.2.1虛擬存儲(chǔ)器工作原理3.2.2地址的映象和變換方法3.2.3加快內(nèi)部地址變換的方法3.2.4頁(yè)面替換算法及其實(shí)現(xiàn)3.2.5提高主存命中率的方法3.2虛擬存儲(chǔ)器3.2.1虛擬存儲(chǔ)器工作原理也稱(chēng)為虛擬存儲(chǔ)系統(tǒng)、虛擬存儲(chǔ)體系等其概念由英國(guó)曼徹斯特大學(xué)的Kilbrn等人于1961年提出到70年代廣泛應(yīng)用于大中型計(jì)算機(jī)系統(tǒng)目前，許多微型機(jī)也使用虛擬存儲(chǔ)器把主存儲(chǔ)器、磁盤(pán)存儲(chǔ)器和虛擬存儲(chǔ)器都劃分成固定大小的頁(yè)主存儲(chǔ)器的頁(yè)稱(chēng)為實(shí)頁(yè)虛擬存儲(chǔ)器中的頁(yè)稱(chēng)為虛頁(yè)內(nèi)部地址變換：多用戶(hù)虛擬地址Av變換成主存實(shí)地址A

多用戶(hù)虛擬地址中的頁(yè)內(nèi)偏移D直接作為主存實(shí)地址中的頁(yè)內(nèi)偏移d，主存實(shí)頁(yè)號(hào)p與它的頁(yè)內(nèi)偏移d直接拼接起來(lái)就得到主存實(shí)地址A。3.2.2地址的映象與變換三種地址空間：虛擬地址空間主存儲(chǔ)器地址空間輔存地址空間地址映象：把虛擬地址空間映象到主存地址空間地址變換：在程序運(yùn)行時(shí)，把虛地址變換成主存實(shí)地址三種虛擬存儲(chǔ)器：頁(yè)式虛擬存儲(chǔ)器段式虛擬存儲(chǔ)器段頁(yè)式虛擬存儲(chǔ)器1.段式虛擬存儲(chǔ)器地址映象方法：每個(gè)程序段都從0地址開(kāi)始編址，長(zhǎng)度可長(zhǎng)可短，可以在程序執(zhí)行過(guò)程中動(dòng)態(tài)改變程序段的長(zhǎng)度。地址變換方法：由用戶(hù)號(hào)找到基址寄存器，讀出段表起始地址，與虛地址中段號(hào)相加得到段表地址，把段表中的起始地址與段內(nèi)偏移D相加就能得到主存實(shí)地址。

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

(1)程序的模塊化性能好。

(2)便于程序和數(shù)據(jù)的共享。

(3)程序的動(dòng)態(tài)鏈接和調(diào)度比較容易。

(4)便于實(shí)現(xiàn)信息保護(hù)。

主要缺點(diǎn)：

(1)地址變換所花費(fèi)的時(shí)間長(zhǎng)，兩次加法

(2)主存儲(chǔ)器的利用率往往比較低。

(3)對(duì)輔存（磁盤(pán)存儲(chǔ)器）的管理比較困難。2.頁(yè)式虛擬存儲(chǔ)器地址映象方法：

地址變換方法：

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

(1)主存儲(chǔ)器的利用率比較高

(2)頁(yè)表相對(duì)比較簡(jiǎn)單

(3)地址變換的速度比較快

(4)對(duì)磁盤(pán)的管理比較容易主要缺點(diǎn)：

(1)程序的模塊化性能不好

(2)頁(yè)表很長(zhǎng)，需要占用很大的存儲(chǔ)空間例如：虛擬存儲(chǔ)空間4GB，頁(yè)大小1KB，則頁(yè)表的容量為4M字，16MB。3.段頁(yè)式虛擬存儲(chǔ)器

用戶(hù)按段寫(xiě)程序,每段分成幾個(gè)固定大小的頁(yè)

地址映象方法：每個(gè)程序段在段表中占一行，在段表中給出頁(yè)表長(zhǎng)度和頁(yè)表的起始地址，頁(yè)表中給出每一頁(yè)在主存儲(chǔ)器中的實(shí)頁(yè)號(hào)。

地址變換方法：先查段表，得到頁(yè)表起始地址和頁(yè)表長(zhǎng)度，再查頁(yè)表找到要訪問(wèn)的主存實(shí)頁(yè)號(hào)，把實(shí)頁(yè)號(hào)p與頁(yè)內(nèi)偏移d拼接得到主存實(shí)地址。4.外部地址變換每個(gè)程序有一張外頁(yè)表，每一頁(yè)或每個(gè)程序段，在外頁(yè)表中都有對(duì)應(yīng)的一個(gè)存儲(chǔ)字。3.2.3加快內(nèi)部地址變換的方法造成虛擬存儲(chǔ)器速度降低的主要原因：

(1)要訪問(wèn)主存儲(chǔ)器必須先查段表或頁(yè)表，

(2)可能需要多級(jí)頁(yè)表。

例如：頁(yè)面為1K，用戶(hù)程序的頁(yè)數(shù)為3K，如何存放？問(wèn)題：如何加快頁(yè)表的訪問(wèn)速度?1.目錄表基本思想：用一個(gè)小容量高速存儲(chǔ)器存放頁(yè)表01六月2023計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第三章存儲(chǔ)系統(tǒng)53目錄表：是一種經(jīng)過(guò)壓縮的頁(yè)表。頁(yè)表只為那些已裝入內(nèi)存的頁(yè)建立虛頁(yè)與實(shí)頁(yè)的對(duì)應(yīng)關(guān)系。所以頁(yè)表的體積縮小，可以用一個(gè)專(zhuān)用的高速存儲(chǔ)器。

地址變換過(guò)程：

把多用戶(hù)虛地址中U與P拼接，相聯(lián)訪問(wèn)目錄表。讀出主存實(shí)頁(yè)號(hào)p，把p與多用戶(hù)虛地址中的D拼接得到主存實(shí)地址。如果相聯(lián)訪問(wèn)失敗，發(fā)出頁(yè)面失效請(qǐng)求。主要優(yōu)點(diǎn)：與頁(yè)表放在主存中相比，查表速度快。主要缺點(diǎn)：

可擴(kuò)展性比較差,

主存儲(chǔ)器容量大時(shí)，目錄表造價(jià)高，速度低2.快慢表

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

慢表：慢表按地址訪問(wèn)；

快表與慢表也構(gòu)成一個(gè)兩級(jí)存儲(chǔ)系統(tǒng)。主要存在問(wèn)題：相聯(lián)訪問(wèn)實(shí)現(xiàn)困難，速度低3.散列函數(shù)

目的：把相聯(lián)訪問(wèn)變成按地址訪問(wèn)

散列(Hashing)函數(shù)：Ah＝H(Pv)Pv是虛頁(yè)號(hào)

Ah是快表的頁(yè)號(hào)特點(diǎn)：存在散列沖突。如何解決？散列函數(shù)方法的快表可以做得較大。01六月2023計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第三章存儲(chǔ)系統(tǒng)58

采用散列變換實(shí)現(xiàn)快表按地址訪問(wèn)避免散列沖突：采用相等比較器地址變換：相等比較與訪問(wèn)存儲(chǔ)器同時(shí)進(jìn)行3.2.4頁(yè)面替換算法及其實(shí)現(xiàn)

1.頁(yè)面替換發(fā)生時(shí)間：

當(dāng)發(fā)生頁(yè)面失效時(shí)，要從磁盤(pán)中調(diào)入一頁(yè)到主存。如果主存儲(chǔ)器的所有頁(yè)面都已經(jīng)被占用，必須從主存儲(chǔ)器中淘汰掉一個(gè)不常使用的頁(yè)面，以便騰出主存空間來(lái)存放新調(diào)入的頁(yè)面。2.評(píng)價(jià)頁(yè)面替換算法好壞的標(biāo)準(zhǔn)：

一是命中率要高，二是算法要容易實(shí)現(xiàn)。4.主要頁(yè)面替換算法(1)隨機(jī)算法（RANDrandomalgorithm）算法簡(jiǎn)單，容易實(shí)現(xiàn)。沒(méi)有利用歷史信息，沒(méi)有反映程序的局部性命中率低。(2)先進(jìn)先出算法

(FIFOfirst-infirst-outalgorithm)

容易實(shí)現(xiàn)，利用了歷史信息，沒(méi)有反映局部性。最先調(diào)入的頁(yè)面，很可能也是要使用的頁(yè)面(3)近期最少使用算法(LFUleastfrequentlyusedalgorithm)：既充分利用了歷史信息，又反映了程序的局部性實(shí)現(xiàn)起來(lái)非常困難。(4)最久沒(méi)有使用算法(LRUleastrecentlyusedalgorithm)：把LFU算法中的“多”與“少”簡(jiǎn)化成“有”與“無(wú)”，實(shí)現(xiàn)比較容易(5)最優(yōu)替換算法（OPToptimalreplacementalgorithm）：是一種理想算法，僅用作評(píng)價(jià)其它頁(yè)面替換算法好壞的標(biāo)準(zhǔn)。

在虛擬存儲(chǔ)器中，實(shí)際上可能采用的只有FIFO和LRU兩種算法。例3.9：一個(gè)程序共有5個(gè)頁(yè)面組成，在程序執(zhí)行過(guò)程中，頁(yè)面地址流如下：

P1，P2，P1，P5，P4，P1，P3，P4，P2，P4

假設(shè)分配給這個(gè)程序的主存只有3個(gè)頁(yè)面。(1)給出用FIFO、LRU和OPT三種頁(yè)面替換算法對(duì)這3個(gè)主存頁(yè)面的調(diào)度情況表，并統(tǒng)計(jì)頁(yè)面命中次數(shù)。(2)計(jì)算這LRU頁(yè)面替換算法的頁(yè)面命中率。解：(1)FIFO、LRU和OPT的頁(yè)面命中次數(shù)分別為2次、4次和5次(2)LRU頁(yè)面替換算法的頁(yè)面命中率為：

Hp＝4/10＝0.4例3.10：一個(gè)循環(huán)程序，依次使用P1，P2，P3，

P4頁(yè)面，分配給它的主存頁(yè)面數(shù)只有2個(gè)。在

FIFO和LRU算法中，發(fā)生“顛簸”現(xiàn)象。3.2.5提高主存命中率的方法影響主存命中率的主要因素：(1)程序在執(zhí)行過(guò)程中的頁(yè)地址流分布情況。(2)所采用的頁(yè)面替換算法。(3)頁(yè)面大小。(4)主存儲(chǔ)器的容量(5)所采用的頁(yè)面調(diào)度算法3.3高速緩沖存儲(chǔ)器3.3.1基本工作原理3.3.2地址映象與變換方法3.3.3Cache替換算法及其實(shí)現(xiàn)3.3.4Cache存儲(chǔ)系統(tǒng)的加速比3.3.5Cache的一致性問(wèn)題3.3.6Cache的預(yù)取算法01六月2023計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第三章存儲(chǔ)系統(tǒng)703.3.1基本工作原理

01六月2023計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第三章存儲(chǔ)系統(tǒng)72問(wèn)題：

1、主存的內(nèi)容放在Cache的哪一部分？（地址映像）

2、查表（地址變換）的速度如何保證快？

3、如何替換？

4、Cache取多大，塊取多大，性?xún)r(jià)比好？3.3.2地址映象與變換方法

地址映象：把主存中的程序按照某種規(guī)則裝入到Cache中，并建立主存地址與Cache地址之間的對(duì)應(yīng)關(guān)系。地址變換：當(dāng)程序已經(jīng)裝入到Cache之后，在程序運(yùn)行過(guò)程中，把主存地址變換成Cache地址。在選取地址映象方法要考慮的主要因素：地址變換的硬件實(shí)現(xiàn)容易、速度要快，

Cache空間利用率要高，發(fā)生塊沖突的概率要小。1.全相聯(lián)映象及其變換映象規(guī)則：主存的任意一塊可以映象到Cache

中的任意一塊。（映象關(guān)系有Cb×Mb種）

地址變換規(guī)則用硬件實(shí)現(xiàn)非常復(fù)雜2.直接映象及其變換映象規(guī)則：

主存儲(chǔ)器中一塊只能映象到Cache的一個(gè)特定的塊中。

Cache地址的計(jì)算公式：

b＝BmodCb

其中：b為Cache塊號(hào)，

B是主存塊號(hào)，

Cb是Cache塊數(shù)。實(shí)際上，Cache地址與主存儲(chǔ)器地址的低位部分完全相同。

直接映象方式的地址映象規(guī)則

直接映象方式的地址變換過(guò)程：用主存地址中的塊號(hào)B去訪問(wèn)區(qū)號(hào)存儲(chǔ)器，把讀出來(lái)的區(qū)號(hào)與主存地址中的區(qū)號(hào)E進(jìn)行比較：比較結(jié)果相等，有效位為1，則Cache命中，否則該塊已經(jīng)作廢。比較結(jié)果不相等，有效位為1，Cache中的該塊是有用的，否則該塊是空的。

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

提高Cache速度的一種方法：

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

硬件實(shí)現(xiàn)很簡(jiǎn)單，不需要相聯(lián)訪問(wèn)存儲(chǔ)器訪問(wèn)速度也比較快，實(shí)際上不需要進(jìn)行地址變換

主要缺點(diǎn)：

塊的沖突率比較高。3.組相聯(lián)映象及其變換映象規(guī)則：

主存和Cache按同樣大小劃分成塊和組。主存和Cache的組之間采用直接映象方式。在兩個(gè)對(duì)應(yīng)的組內(nèi)部采用全相聯(lián)映象方式。組相聯(lián)映象方式的優(yōu)點(diǎn)：

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

實(shí)現(xiàn)難度和造價(jià)要比直接映象方式高。組相聯(lián)映象的地址變換過(guò)程：用主存地址中的組號(hào)G按地址訪問(wèn)塊表存儲(chǔ)器。把讀出來(lái)的一組區(qū)號(hào)和塊號(hào)與主存地址中的區(qū)號(hào)和塊號(hào)進(jìn)行相聯(lián)比較。如果有相等的，表示Cache命中；如果全部不相等，表示Cache沒(méi)有命中。

組相聯(lián)映象的地址變換

提高Cache訪問(wèn)速度的一種方法：用多個(gè)相等比較器來(lái)代替相聯(lián)訪問(wèn)3.3.3Cache替換算法及其實(shí)現(xiàn)使用的場(chǎng)合：

直接映象方式實(shí)際上不需要替換算法全相聯(lián)映象方式的替換算法最復(fù)雜主要用于組相聯(lián)、段相聯(lián)等映象方式中要解決的問(wèn)題：記錄每次訪問(wèn)Cache的塊號(hào)在訪問(wèn)過(guò)程中，對(duì)記錄的塊號(hào)進(jìn)行管理根據(jù)記錄和管理結(jié)果，找出替換的塊號(hào)主要特點(diǎn)：全部用硬件實(shí)現(xiàn)（與虛擬存儲(chǔ)器合并講解）3.3.4Cache存儲(chǔ)系統(tǒng)的加速比1.加速比與命中率的關(guān)系Cache存儲(chǔ)系統(tǒng)的加速比SP為：其中：Tm為主存儲(chǔ)器的訪問(wèn)周期，

Tc為Cache的訪問(wèn)周期，

T為Cache存儲(chǔ)系統(tǒng)的等效訪問(wèn)周期，

H為命中率。提高加速比的最好途徑是提高命中率

加速比SP能夠接近于期望值是：

加速比SP與命中率H的關(guān)系2.Cache命中率與容量的關(guān)系

Cache的命中率隨它的容量的增加而提高。關(guān)系曲線可以近似地表示為：3.Cache命中率與塊大小的關(guān)系在組相聯(lián)方式中,塊大小對(duì)命中率非常敏感塊很小時(shí)，命中率很低。隨著塊大小增加命中率也增加,有一個(gè)極大值當(dāng)塊非常大時(shí),進(jìn)入Cache中的數(shù)據(jù)可能無(wú)用當(dāng)塊大小等于Cache容量時(shí),命中率將趨近零4.Cache命中率與組數(shù)的關(guān)系

在組相聯(lián)方式中,組數(shù)對(duì)命中率的影響很明顯隨著組數(shù)的增加，Cache的命中率要降低。當(dāng)組數(shù)不太大時(shí)(小于512),命中率的降低很少當(dāng)組數(shù)超過(guò)一定數(shù)量時(shí),命中率的下降非?？霤ache命中率與塊大小的關(guān)系3.3.5Cache的一致性造成Cache與主存的不一致的原因：

(1)由于CPU寫(xiě)Cache，沒(méi)有立即寫(xiě)主存

(2)由于IO處理機(jī)或IO設(shè)備寫(xiě)主存Cache的更新算法

(1)寫(xiě)直達(dá)法，寫(xiě)通過(guò)法，WT(Write-through)CPU的數(shù)據(jù)寫(xiě)入Cache時(shí)，同時(shí)也寫(xiě)入主存

(2)寫(xiě)回法，抵觸修改法，WB(Write-Back)CPU的數(shù)據(jù)只寫(xiě)入Cache，不寫(xiě)入主存，僅當(dāng)替換時(shí)，才把修改過(guò)的Cache塊寫(xiě)回主存寫(xiě)回法與寫(xiě)直達(dá)法的優(yōu)缺點(diǎn)比較：

(1)可靠性，寫(xiě)直達(dá)法優(yōu)于寫(xiě)回法。寫(xiě)直達(dá)法能夠始終保證Cache是主存的副本。如果Cache發(fā)生錯(cuò)誤，可以從主存得到糾正。(2)與主存的通信量，寫(xiě)回法少于寫(xiě)直達(dá)法。對(duì)于寫(xiě)回法：大多數(shù)操作只需要寫(xiě)Cache，不需要寫(xiě)主存；當(dāng)發(fā)生塊失效時(shí)，可能要寫(xiě)一個(gè)塊到主存；

對(duì)于寫(xiě)直達(dá)法：每次寫(xiě)操作，必須寫(xiě)、且只寫(xiě)一個(gè)字到主存。實(shí)際上：寫(xiě)直達(dá)法的寫(xiě)次數(shù)很多、每次只寫(xiě)一個(gè)字；寫(xiě)回法是的寫(xiě)次數(shù)很少、每次要寫(xiě)一個(gè)塊。例3.15：寫(xiě)操作占總訪存次數(shù)的20％,Cache的命中率為99％，每塊為4個(gè)字。當(dāng)Cache發(fā)生塊替換時(shí)，有30％塊需要寫(xiě)回到主存，其余的塊因?yàn)闆](méi)有被修改過(guò)而不必寫(xiě)