組成原理課程第四章

組成原理課程第四章第1頁，共93頁，2023年，2月20日，星期二重要通知組成原理實(shí)驗(yàn)課的時(shí)間調(diào)整為10，12，16周周六晚上第2頁，共93頁，2023年，2月20日，星期二本章知識(shí)點(diǎn)：4.1存儲(chǔ)器概述

1)存儲(chǔ)器主要技術(shù)指標(biāo)

2)主存中的數(shù)據(jù)存放:大、小端存放

3)主存的基本結(jié)構(gòu)和工作過程

4)存儲(chǔ)系統(tǒng)層次結(jié)構(gòu)4.2半導(dǎo)體存儲(chǔ)器

1)SRAM的工作原理

2)DRAM的工作原理4.3主存的組織及與CPU的連接

1)位擴(kuò)展

2)字?jǐn)U展4.4并行存儲(chǔ)系統(tǒng)

1)雙端口存儲(chǔ)器

2)單體多字存儲(chǔ)器

3)多體交叉存儲(chǔ)器4.5高速緩沖存儲(chǔ)器

1)程序訪問的局部性原理

2)Cache的組織及訪問Cache流程

3)三種常見的Cache地址映射及地址變換方法

4)Cache的替換算法

5)Cache的寫策略

6)應(yīng)用舉例4.6虛擬存儲(chǔ)器

1)虛擬存儲(chǔ)器的基本概念及種類

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

3)TLB(快表)第3頁，共93頁，2023年，2月20日，星期二1.主存的常用技術(shù)指標(biāo)1)存儲(chǔ)容量指標(biāo)：存儲(chǔ)器所能存儲(chǔ)的二進(jìn)制信息的位數(shù).2)速度指標(biāo)：

(1)存取時(shí)間(存儲(chǔ)器訪問時(shí)間)

啟動(dòng)存取操作到操作完成所經(jīng)歷的時(shí)間

(2)存儲(chǔ)周期(讀寫周期)：對(duì)存儲(chǔ)器進(jìn)行連續(xù)兩次存取操作所需的最短時(shí)間間隔。存儲(chǔ)器在一次存取操作后需要一定的恢復(fù)時(shí)間,故該時(shí)間一般大于存取時(shí)間.(3)存儲(chǔ)器帶寬：單位時(shí)間內(nèi)存儲(chǔ)器所存取的信息位，也稱存儲(chǔ)器的數(shù)據(jù)傳輸率.即存儲(chǔ)器總線寬度/存儲(chǔ)周期,單位為位/秒4.1.存儲(chǔ)器概述第4頁，共93頁，2023年，2月20日，星期二1)信息存儲(chǔ)及存儲(chǔ)器編址(1)存儲(chǔ)字長與數(shù)據(jù)字長的概念存儲(chǔ)字長：主存的一個(gè)存儲(chǔ)單元所包含的二進(jìn)制位數(shù)數(shù)據(jù)字長(字長)：計(jì)算機(jī)一次能處理的二進(jìn)制數(shù)的位數(shù)．(2)目前大多數(shù)計(jì)算機(jī)的主存采用按字節(jié)編址,而計(jì)算機(jī)的字長又包含多個(gè)字節(jié),如16位字長、32位字長和64位字長，所包含的字節(jié)數(shù)分別為2、4、8。2.主存中的數(shù)據(jù)存放第5頁，共93頁，2023年，2月20日，星期二2)大端(big-endian)和小端(little-endian)數(shù)據(jù)存放方式big-endian:最高字節(jié)地址(最左邊)作為字地址

(正常存放方式)MSBLSB0123字節(jié)地址4567字地址04little-endian:最低字節(jié)地址(最右邊)作為字地址MSBLSB0123字節(jié)地址4567字地址0468000采用大端,Intel采用小端，ARM兩者都支持第6頁，共93頁，2023年，2月20日，星期二數(shù)據(jù)存放方式應(yīng)用舉例設(shè)某程序執(zhí)行前r0=0x11223344執(zhí)行下列指令：

r1=0x100STRr0,[r1]LDRBr2,[r1]執(zhí)行后：小端模式下：r2=0x44大端模式下：r2=0x11第7頁，共93頁，2023年，2月20日，星期二3)字節(jié)編址的存儲(chǔ)器按邊界對(duì)齊數(shù)據(jù)存放方法若數(shù)據(jù)字長32位，存儲(chǔ)字長64位。則半字長16位，雙字長64位邊界對(duì)齊的數(shù)據(jù)存放如下圖所示。雙字?jǐn)?shù)據(jù)的起始地址的最末三位為000（8字節(jié)的整數(shù)倍）,表示訪問一個(gè)64位字長的字,如果要訪問其中的某字節(jié)或半字則用低三位中的部分位來選擇.單字?jǐn)?shù)據(jù)的起始地址的最末二位為00（4字節(jié)的整數(shù)倍）半字?jǐn)?shù)據(jù)的起始地址的最末一位為0（２字節(jié)的整數(shù)倍）字節(jié)半字雙字單字半字半字字節(jié)64位第8頁，共93頁，2023年，2月20日，星期二3.主存結(jié)構(gòu)及其工作過程CPU與存儲(chǔ)器交換信息時(shí)，先給出地址,該地址經(jīng)地址譯碼驅(qū)動(dòng)器后選中存儲(chǔ)體中對(duì)應(yīng)的存儲(chǔ)單元，然后由控制線路控制讀出或?qū)懭?。讀出時(shí)，將選中的存儲(chǔ)單元所存的數(shù)據(jù)送入數(shù)據(jù)寄存器，原存儲(chǔ)單元中的內(nèi)容不變。CPU從數(shù)據(jù)寄存器取走該數(shù)據(jù)進(jìn)行指令所要求的處理。寫入時(shí)，將CPU送來并已存放于數(shù)據(jù)寄存器中的數(shù)據(jù)寫入選中的存儲(chǔ)單元，原數(shù)據(jù)將被新數(shù)據(jù)所取代。第9頁，共93頁，2023年，2月20日，星期二4、存儲(chǔ)系統(tǒng)層次結(jié)構(gòu)1)分級(jí)結(jié)構(gòu)的提出對(duì)存儲(chǔ)系統(tǒng)追求的目標(biāo):大容量、快速度、低價(jià)格2)分級(jí)結(jié)構(gòu)CPUCACHE主存輔助存儲(chǔ)器最后的效果(左向右看)：Cache的速度，輔存的容量和價(jià)格第10頁，共93頁，2023年，2月20日，星期二3)存儲(chǔ)分級(jí)的理論基礎(chǔ)！程序的局部性原理

,又包括時(shí)間局部性和空間局部性

?時(shí)間局部性現(xiàn)在被訪問的指令在不久的將來還將再次被訪問。

12345時(shí)間局部性的程序結(jié)構(gòu)體現(xiàn)：循環(huán)

?空間局部性現(xiàn)在訪問指令2，下一次訪問的指令在2的附近?？臻g局部性的程序結(jié)構(gòu)體現(xiàn)：

順序第11頁，共93頁，2023年，2月20日，星期二

1、SRAM(StaticRandomAccessMemory)工作原理1)基本存儲(chǔ)單元

存放一位二進(jìn)制信息的電路2)SRAM存儲(chǔ)單元結(jié)構(gòu)及其工作原理?工作管：T1、T2?負(fù)載管：T3、T4?門控管：T5、T6、

T7、T8Source:源極Drain：漏極Gate：柵極襯底一般與S極相連，與G極之間絕緣，大多數(shù)情況下S和D可互換4.2半導(dǎo)體存儲(chǔ)器第12頁，共93頁，2023年，2月20日，星期二?寫過程行選通T5、T6通A與D連通列選通T7、T8通

B與D

連通寫1的過程D=1A=1T2通B=0T1截止D=0B=0T1截止A=1T2通此時(shí),T1、T2形成了穩(wěn)態(tài)，A=1、B=0寫0的過程D=0A=0T2截止B=1T1通D=1B=1T1通A=0T2截止此時(shí)，T1、T2形成了穩(wěn)態(tài)，B=1、A=0即：六管靜態(tài)存儲(chǔ)單元是以T1和T2構(gòu)成的穩(wěn)定互鎖態(tài)保存信息第13頁，共93頁，2023年，2月20日，星期二?讀過程行選通T5、T6通A與D連通列選通T7、T8通

B與

D

連通讀1的過程若原來保存的是1，則此時(shí)，D=1、D=0，D和D外接一個(gè)讀出放大器，放大器中的電流從D流向D

，表示讀出為1讀0的過程若原來保存的是0，則此時(shí)，D=0、D=1，D和D外接一個(gè)讀出放大器，放大器中的電流從D

流向D，表示讀出為0讀出的內(nèi)容是通過外接在D和D之間電流放大器中的電流的方向來判斷第14頁，共93頁，2023年，2月20日，星期二2、動(dòng)態(tài)存儲(chǔ)器-DRAM1)構(gòu)成工作管：T1、T2門控管：T5、T6、T7、T82)信息的保存：分布電容C1、C2上的電荷3)寫操作：基本步驟同六管靜態(tài)單元A=1對(duì)C2充電，T2導(dǎo)通B=0對(duì)C1放電，T1截止

寫1A=0對(duì)C2放電，T1導(dǎo)通B=B對(duì)C1充電，T2截止

寫0第15頁，共93頁，2023年，2月20日，星期二4)讀操作通過T9T10給D線和D線上的分布電容CD、CD預(yù)充電.?讀出信息：

X有效T5、T6通

Y有效T7、T8通若原來寫入為1則CD

上的電荷經(jīng)T2泄漏

D=0而CD只向C2微充電D=1有D到D的電流，即讀出的為“1”若原來寫入為0則CD上的電荷經(jīng)T1泄漏

D=0而CD只向C1微充電D=1有D到D的電流，即讀出的為“0”第16頁，共93頁，2023年，2月20日，星期二5)還需要什么狀態(tài)？

5)刷新操作

?刷新原理：對(duì)C1、C2充電只給字線T5、T6導(dǎo)通CD對(duì)C2充電或CD對(duì)C1充電。即刷新是按行進(jìn)行，因此，必須知道動(dòng)態(tài)存儲(chǔ)器的內(nèi)部行列結(jié)構(gòu)。一次刷新是一次不完全的讀操作。刷新地址由刷新計(jì)數(shù)器給出。?需要刷新的原因：保存信息的電容C1、C2上的電荷維持的時(shí)間有限(一般2ms)。第17頁，共93頁，2023年，2月20日，星期二6)三種刷新方式（設(shè)刷新周期為2ms，存儲(chǔ)矩陣采用128×128結(jié)構(gòu)，存儲(chǔ)體的讀/寫周期為0.5s

）?集中式刷新：

將2ms的讀寫周期分成2000/0.5=4000個(gè)讀寫時(shí)間段。前面4000-128=3872個(gè)讀寫時(shí)間段用于讀/寫，后面128個(gè)讀寫時(shí)間段用于刷新，在此階段，不允許進(jìn)行讀寫操作，故稱為死時(shí)間.…

3872個(gè)讀寫周期

…128個(gè)刷新周期采用集中刷新的存儲(chǔ)器平均讀寫周期T=2ms/(4000–128)=0.5165s第18頁，共93頁，2023年，2月20日，星期二?分散刷新將每一個(gè)存儲(chǔ)周期分成兩部分，前一部分為讀/寫時(shí)間段，后一部分為刷新時(shí)間段，對(duì)于本例的實(shí)際則是存儲(chǔ)器的讀寫周期變成了1s，其中前0.5s為讀/寫時(shí)間，0.5s為刷新時(shí)間?！?/p>

2000個(gè)讀寫周期

T=1s第19頁，共93頁，2023年，2月20日，星期二?異步刷新是集中刷新和分散刷新的結(jié)合，將2ms分成128個(gè)時(shí)間段，每段的時(shí)間為2000/128=15.5s，再將每段時(shí)間分成兩部分，其中前面的15s用于讀寫，最后的0.5s用于刷新?！?5.5s……15.5sT=2ms/(4000–128)=0.5165s第20頁，共93頁，2023年，2月20日，星期二?三種刷新方式的比較集中刷新：用于高速存儲(chǔ)器中，但存在死時(shí)間分散刷新：雖然不存在死時(shí)間，但大大降低了存儲(chǔ)體的速度異步刷新：既不存在死時(shí)間，也保持了存儲(chǔ)體的高速特性7)關(guān)于動(dòng)態(tài)存儲(chǔ)器刷新的幾點(diǎn)說明：?不同材料及生產(chǎn)工藝的動(dòng)態(tài)存儲(chǔ)器的刷新周期不同(2ms、4ms、8ms等)。?刷新按行進(jìn)行,要知道存儲(chǔ)體的行、列結(jié)構(gòu)，即行譯碼器輸出的線數(shù)，當(dāng)存儲(chǔ)器是由若干單體構(gòu)成時(shí)，以單體的容量為計(jì)算的依據(jù)，同時(shí)考慮雙譯碼的原則。如由256K的存儲(chǔ)體構(gòu)成2M的存儲(chǔ)器。行為29，若由512K的單體構(gòu)成，則行可以是29或210，但要說明。?刷新地址是由專門的器件

刷新地址計(jì)數(shù)器給出。第21頁，共93頁，2023年，2月20日，星期二1、SRAM存儲(chǔ)器與CPU的連接及擴(kuò)展1)需要連接的線連接的地址線的數(shù)量與CPU要訪問的主存容量有關(guān)；連接的數(shù)據(jù)線的數(shù)量與計(jì)算機(jī)字長有關(guān)；對(duì)于RAM而言，控制線包括片選信號(hào)和讀/寫控制，而對(duì)于ROM而言則只有片選信號(hào)線。DRAM沒有片選控制線，容量擴(kuò)展時(shí)，利用RAS和CAS控制芯片的選擇。從上述連接線可檢查存儲(chǔ)擴(kuò)展是否正確2)存儲(chǔ)器擴(kuò)展的種類

位擴(kuò)展

：當(dāng)數(shù)據(jù)位不足時(shí)字?jǐn)U展：當(dāng)容量不足時(shí)字位同時(shí)擴(kuò)展：當(dāng)數(shù)據(jù)位和存儲(chǔ)體的容量均不足時(shí)使用4.3主存的組織及與CPU的連接

第22頁，共93頁，2023年，2月20日，星期二2.位擴(kuò)展當(dāng)儲(chǔ)芯片的數(shù)據(jù)位小于CPU對(duì)數(shù)據(jù)位的要求時(shí)，采用位擴(kuò)展將所有存儲(chǔ)芯片的地址線、讀寫控制線并聯(lián)同時(shí)分別與CPU的地址線和讀寫控制線連接；存儲(chǔ)芯片的數(shù)據(jù)線依次與CPU的數(shù)據(jù)線相連；所有芯片的片選控制線并聯(lián)接低電平。僅進(jìn)行位擴(kuò)展時(shí)，所需存儲(chǔ)芯片的數(shù)量為：L=存儲(chǔ)器的數(shù)據(jù)位/存儲(chǔ)芯片的數(shù)據(jù)位=8/2=4第23頁，共93頁，2023年，2月20日，星期二2.字?jǐn)U展容量不夠時(shí)字?jǐn)U展所需芯片數(shù)量:L=主存容量/存儲(chǔ)體容量

=2(CPU地址線數(shù)-存儲(chǔ)體地址線數(shù))

本例中L=64/16=4片選產(chǎn)生辦法:

線選法\全譯碼法\部分譯碼法將CPU多余地址送片選譯碼輸入端．CPU每次只能選中一個(gè)存儲(chǔ)芯片中的某個(gè)單元.第24頁，共93頁，2023年，2月20日，星期二不同存儲(chǔ)體的全局地址范圍體號(hào)

地址范圍16進(jìn)制值A(chǔ)15A14A13-

A000000，0000，0000，00000000H~03FFFH0011，1111，1111，111110100，0000，0000，000004000H~07FFFH0111，1111，1111，111121000，0000，0000，00008000H~0BFFFH1011，1111，1111，111131100，0000，0000，00000CFFFH~0FFFFH1111，1111，1111，1111第25頁，共93頁，2023年，2月20日，星期二例1某計(jì)算機(jī)的主存地址空間中，從地址0000H

-3FFFH

為ROM存儲(chǔ)區(qū)域，從4000H-5FFFH為保留地址區(qū)域，暫時(shí)不用，從6000H-FFFFH為RAM地址區(qū)域。RAM的控制信號(hào)為CS#和WE#，CPU的地址線為A15-A0，數(shù)據(jù)線為D7-D0，控制信號(hào)有R/W#和訪存請(qǐng)求MREQ#.如果ROM存儲(chǔ)器芯片采用8K×8的芯片，RAM存儲(chǔ)器芯片采用4K×8的芯片，試畫出存儲(chǔ)器與CPU的連接圖。解:地址空間分布分析：0000H

-3FFFH

(16K):ROM

011111111111111–000000000000000=111111111111114000H-5FFFH(8K):

保留區(qū)6000H-FFFFH(40K):RAM區(qū)（FFFFH-6000H=1001，1111，1111，1111=215+8K）?需要ROM的芯片數(shù)量為：16K×88K×8=2?需要RAM的芯片數(shù)量為：40K×84K×8=10第26頁，共93頁，2023年，2月20日，星期二?如何選擇譯碼輸入?以大容量的為目標(biāo)(8k單體),此時(shí)送入譯碼器的輸入地址線的數(shù)量為：

16–13=3根共產(chǎn)生8個(gè)譯碼輸出線，每根譯碼輸出線選擇的內(nèi)存空間范圍是：

64K/8=8K第27頁，共93頁，2023年，2月20日，星期二

每個(gè)片選譯碼線選擇8K的存儲(chǔ)空間第28頁，共93頁，2023年，2月20日，星期二

每個(gè)片選譯碼線選擇8K的存儲(chǔ)空間第29頁，共93頁，2023年，2月20日，星期二如以小容量的為目標(biāo)(4K的單體)

此時(shí)送入譯碼器的輸入地址線的數(shù)量為：

16–12=4根共產(chǎn)生16個(gè)譯碼輸出線，每根譯碼輸出線選擇的內(nèi)存空間范圍是：

64K/16=4K

顯然，為了留出8K的保留區(qū)，必須預(yù)留出2根片選信號(hào)第30頁，共93頁，2023年，2月20日，星期二以小容量的為目標(biāo),每個(gè)片選譯碼輸出選擇4K的存儲(chǔ)范圍第31頁，共93頁，2023年，2月20日，星期二4.4并行存儲(chǔ)器1、問題的提出

(1)CPU和主存速度上存在差異

(2)一個(gè)CPU周期內(nèi)需要多個(gè)存儲(chǔ)字60%/yr.DRAM7%/yr.110100100019801981198319841985198619871988198919901991199219931994199519961997199819992000DRAMCPU1982Processor-MemoryPerformanceGap:

(grows50%/year)Performance“Moore’sLaw”第32頁，共93頁，2023年，2月20日，星期二2、雙端口存儲(chǔ)器構(gòu)造及工作原理：

?具有相互獨(dú)立的兩組讀/寫控制電路,正常情況下各自獨(dú)立進(jìn)行讀/寫

?左右讀/寫不同單元時(shí)不發(fā)生沖突

?左右同時(shí)存取同一個(gè)單元時(shí),發(fā)生讀寫沖突.此時(shí),由判斷邏輯來延時(shí)一個(gè)讀寫控制器的工作并設(shè)該端口.BUSY=0.第33頁，共93頁，2023年，2月20日，星期二3、多體交叉存儲(chǔ)器(低位)1)多體交叉存儲(chǔ)器的結(jié)構(gòu)?由2n個(gè)容量相同存儲(chǔ)器的組成,各有自己的讀\寫線路、地址寄存器、數(shù)據(jù)寄存器；?各模塊的讀寫過程將重疊進(jìn)行，對(duì)于每個(gè)模塊而言，讀寫時(shí)間不變，但對(duì)CPU而言，在一個(gè)存儲(chǔ)周期內(nèi)連續(xù)訪問四個(gè)模塊；?用CPU的高位連接存儲(chǔ)芯片的地址；?是一種并行存儲(chǔ)器結(jié)構(gòu)?對(duì)于m體低位交叉存儲(chǔ)器而言，連續(xù)讀m個(gè)字的時(shí)間:t1=T+(m1)不采用多體交叉時(shí)讀m個(gè)字的時(shí)間:t1=Tm

第34頁，共93頁，2023年，2月20日，星期二2)低位多體交叉方式下的數(shù)據(jù)特征?相鄰地址分布在不同存儲(chǔ)體中?同一存儲(chǔ)體中的地址不相鄰?四片的地址通項(xiàng)公式分別為:4i+0、4i+1、4i+2、4i+3?能在一個(gè)存儲(chǔ)周期內(nèi)存取多個(gè)字第35頁，共93頁，2023年，2月20日，星期二例2設(shè)計(jì)算機(jī)字長64位,存儲(chǔ)器容量為128MW,采用模8的存儲(chǔ)器交叉方式組織(低位).存儲(chǔ)周期T=200ns,數(shù)據(jù)總線寬度為64位,總線傳輸周期=50ns,計(jì)算存儲(chǔ)器最高帶寬。

解:交叉方式下，連續(xù)讀8個(gè)字所需要的時(shí)間t=T+7=550ns則，交叉方式下存儲(chǔ)器帶寬

=64*8/t=64*8/550ns=9.31108bps第36頁，共93頁，2023年，2月20日，星期二4.5高速緩沖存儲(chǔ)器1.程序訪問的局部性原理時(shí)間局部性:

針對(duì)同一個(gè)數(shù)據(jù)的多次訪問空間局部性:

針對(duì)一個(gè)數(shù)據(jù)塊中的不同數(shù)據(jù)例3.以下程序A和B中，哪一個(gè)對(duì)數(shù)組A[2048][2048]訪問的空間局部性更好？時(shí)間局部性呢？變量sum的空間局部性和時(shí)間局部性如何？對(duì)于指令來說，for循環(huán)體的空間局部性和時(shí)間局部性如何？第37頁，共93頁，2023年，2月20日，星期二(1)數(shù)組A：訪問順序?yàn)锳[0][0],A[0][1],……,A[0][2047];與存放順序一致，故空間局部性好！但每個(gè)A[i][j]只被訪問一次，故時(shí)間局部性差！(2)變量sum：單個(gè)變量不考慮空間局部性；每次循環(huán)都要訪問sum，所以其時(shí)間局部性較好！(3)for循環(huán)體：循環(huán)體內(nèi)指令按序連續(xù)存放，所以空間局部性好！循環(huán)體被連續(xù)重復(fù)執(zhí)行2048x2048次，所以時(shí)間局部性好！第38頁，共93頁，2023年，2月20日，星期二程序段B的時(shí)間局部性和空間局部性分析(1)變量sum：（同程序A）(2)for循環(huán)體：（同程序A）(3)數(shù)組A：訪問順序?yàn)锳[0][0]-A[2047][0];與存放順序不一致，每次跳過2048個(gè)單元，若主存與Cache之間交換信息的塊小于2KB，則沒有空間局部性?。總€(gè)數(shù)組變量只被訪問一次，沒有時(shí)間局部性，同程序A）第39頁，共93頁，2023年，2月20日，星期二2.Cache的組織及訪問Cache流程?CPU與Cache之間交換信息的基本單位是字,而Cache與主存之間信息交換的單位是塊。?Cache的一個(gè)塊包含若干個(gè)字。?CPU訪問主存時(shí)，先根據(jù)該主存地址到Cache中查找，如果查找成功(命中)，則直接從Cache中讀取，反之(不命中)CPU訪問主存，同時(shí)將該字所在的塊送入Cache，并在CAM中登記相關(guān)信息?相聯(lián)存儲(chǔ)器是一種根據(jù)內(nèi)容訪問的存儲(chǔ)器?當(dāng)不命中時(shí),存在頁面調(diào)度的問題,常用的算法有LRU第40頁，共93頁，2023年，2月20日，星期二應(yīng)用于Cache中的主存地址格式

?塊內(nèi)偏移地址（塊內(nèi)地址）表示CPU所要訪問的單元在某塊內(nèi)的偏移值。?索引(Index)索引是比主存塊地址粒度更細(xì)的地址，作為Cache存儲(chǔ)體的地址指示器，指出CPU訪問Cache存儲(chǔ)體的范圍。?標(biāo)記(Tgg)標(biāo)記也是比主存塊地址粒度更細(xì)的地址，作為判斷CPU要訪問的內(nèi)容是否在Cache中的依據(jù)。不同主存與Cache地址映射方法，對(duì)主存地址的不同劃分，這是掌握Cache工作原理的關(guān)鍵。?主存塊地址是CPU訪問主存單元地址按塊大小劃分后得到地址，用于標(biāo)識(shí)CPU所訪問的主存單元所在的主存塊號(hào)。第41頁，共93頁，2023年，2月20日，星期二Cache的訪問流程1)Cache命中的流程(1)從CPU送出的主存地址中畫分出記(Tag)、索引(Index)、塊內(nèi)地址；(2)按Index的值從Cache標(biāo)記存儲(chǔ)體特定單元讀出Tag,并與(1)中的Tag比較；(3)若比較結(jié)果相同(稱為命中),則形成Cache地址；(4)根據(jù)形成的Cache地址訪問Cache數(shù)據(jù)存儲(chǔ)體,Index部分?jǐn)?shù)據(jù)存儲(chǔ)體的范圍；(5)從Cache中讀出信息送CPU。第42頁，共93頁，2023年，2月20日，星期二3.三種常見的Cache地址映射及地址變換方法(1)主存與Cache之間的映射方式?地址映射：將主存地址變換成Cache地址的方法?地址映射的作用：

CPU訪問主存時(shí)，主存地址變換成Cache地址，從而查找Cache。?地址映射的實(shí)現(xiàn)：硬件實(shí)現(xiàn)，對(duì)軟件人員(包括程序員和系統(tǒng)程序員)透明?三種地址映射方法：全相聯(lián)、直接相聯(lián)、組相聯(lián)第43頁，共93頁，2023年，2月20日，星期二2)全相聯(lián)映射方式?主存分塊，Cache分行，包含相同數(shù)量的字?圖中主存分成256塊，Cache被分成8行。?算法：主存的一塊可映射到Cache的任意行?映射時(shí)，主存的一個(gè)塊被拷貝到Cache數(shù)據(jù)存儲(chǔ)體的某一行,其中,主存塊地址被填寫到Cache的標(biāo)記部分(相聯(lián)存儲(chǔ)器)。?舉例：設(shè)每塊4個(gè)字，則主存的大小為1024個(gè)字，其中第61個(gè)字的主存地址為：

0000111101（塊號(hào)塊內(nèi)地址）則將00001111填入Cache某行的標(biāo)記，該塊的4個(gè)字填入該行的Cache存儲(chǔ)體內(nèi)存第44頁，共93頁，2023年，2月20日，星期二?檢索過程?舉例：

CPU要讀內(nèi)存地址為：0000111110則將前8位00001111送入比較器，同時(shí)Cache所有行的標(biāo)記字段也同時(shí)送入該比較器，若某行命中，則選通內(nèi)存地址的剩余部分，并由它選擇Cache中相應(yīng)字，本例中選擇該塊內(nèi)的第2個(gè)字。若CPU訪問內(nèi)存地址為：

0000111001

則不命中第45頁，共93頁，2023年，2月20日，星期二?全相聯(lián)映射的特點(diǎn)

(a)優(yōu)點(diǎn)：

Cache的利用率高，只要Cache中還有空行，就不需進(jìn)行頁面調(diào)度。(b)缺點(diǎn)：比較電路相對(duì)復(fù)雜?使用場合：適合小容量的Cache中使用第46頁，共93頁，2023年，2月20日，星期二3)直接映射?主存按Cache容量分區(qū)，區(qū)內(nèi)分塊；Cache分行，塊和行容量容量相同?對(duì)于如圖所示的情況,分區(qū)數(shù)為32?算法：i=jmod8(i是Cache行號(hào)，j是主存塊號(hào))是一種多對(duì)一的映射?映射時(shí)，數(shù)據(jù)所在主存區(qū)號(hào)被填寫到Cache某行的標(biāo)記部分，內(nèi)容存放到Cache相應(yīng)行的存儲(chǔ)體中。第47頁，共93頁，2023年，2月20日，星期二?舉例：設(shè)每塊4個(gè)字，則主存的大小為1024個(gè)字，其中第61個(gè)字的主存地址為：

0000111101(在1區(qū)、7塊中）則將00001填入Cache的第7行的標(biāo)記部分，該塊的4個(gè)字填入該行的數(shù)據(jù)存儲(chǔ)體第48頁，共93頁，2023年，2月20日，星期二?直接映射的檢索?舉例:CPU要讀內(nèi)存地址為：

0000111111則將前5位00001與Cache的第7行標(biāo)記的內(nèi)容送入比較器，若命中，選擇Cache第7行內(nèi)的第3個(gè)字。?若CPU讀內(nèi)存地址：

0001011101它是第93個(gè)字，B23塊。此次訪問將不會(huì)命中，將發(fā)生頁面調(diào)度。第49頁，共93頁，2023年，2月20日，星期二3）組相聯(lián)映射?主存分塊；Cache分行，兩者容量相同。Cache分組，每組中的行數(shù)相同，主存分組，每組中的塊的數(shù)量同Cache的組數(shù)量(每組中包含k行稱為k路組相聯(lián))?對(duì)于如圖所示的情況,主存分組數(shù)為64(=256/4),故標(biāo)記需要6位?算法：i=jmod4(i是Cache組號(hào)，j是主存塊號(hào))是一種多對(duì)一的映射，但是j塊映射到Cachei組中的哪一行則采用全相聯(lián)映射實(shí)現(xiàn)?映射時(shí)，主存塊所在的組號(hào)被填入Cache特定組、任意行的標(biāo)記中，數(shù)據(jù)存放到相應(yīng)行的Cache存儲(chǔ)體中。第50頁，共93頁，2023年，2月20日，星期二?舉例：設(shè)每塊4個(gè)字，則主存的大小為1024個(gè)字，其中第61個(gè)字的主存地址為：

0000111101(主存3組中第3塊、即B15塊中)則將000011填入Cache的第3組某行的標(biāo)記部分，該塊的4個(gè)字填入該行的Cache存儲(chǔ)體又如第93個(gè)字的主存地址為:0001011101

也將分配到Cache第3組某行第51頁，共93頁，2023年，2月20日，星期二?組相聯(lián)映射的檢索?舉例：CPU要讀內(nèi)存地址為：

0000111111則將前6位000011與Cache的第3組中所有行標(biāo)記的內(nèi)容送入比較器，若命中，選擇Cache第3組中命中行內(nèi)的第3個(gè)字。?若CPU要訪問的地址為：

0000111011則不命中第52頁，共93頁，2023年，2月20日，星期二4.替換算法(1)LFU算法

最不經(jīng)常使用算法(LeastFrequentlyUsed

)

該算法將一段時(shí)間內(nèi)使用次數(shù)最少的行調(diào)出。故每行設(shè)置一個(gè)計(jì)數(shù)器，新調(diào)入的行計(jì)數(shù)值為0，每被訪問一次，計(jì)數(shù)值加1，當(dāng)需要發(fā)生頁面調(diào)度時(shí)，比較各行計(jì)數(shù)器的值，將最小者調(diào)出。第53頁，共93頁，2023年，2月20日，星期二

112323452111

11201120301121301121311131401121315010

第54頁，共93頁，2023年，2月20日，星期二(2)LRU最近最少用算法(Leastrecentlyused)

該算法將一段時(shí)間內(nèi)最長時(shí)間沒有被使用的行調(diào)出。故每行設(shè)置一個(gè)計(jì)時(shí)器，新調(diào)入的和命中行計(jì)數(shù)值為0，同時(shí)其他各行的計(jì)數(shù)器值加1，當(dāng)需要發(fā)生頁面調(diào)度時(shí)，比較各行計(jì)數(shù)器的值，將最大者調(diào)出。第55頁，共93頁，2023年，2月20日，星期二

1123234510

1120122130132031142130152231405023324110

第56頁，共93頁，2023年，2月20日，星期二?如果出現(xiàn)了下列情況(LRU)11

2010

213012112010223113402332504110335142112052431221533012345123?上述現(xiàn)象稱為抖動(dòng)，出現(xiàn)的原因是用戶的程序足局性不好在這種情況下，Cache的作用得不到發(fā)揮。?要充分發(fā)揮計(jì)算機(jī)硬件的高速特性，要求用戶的程序滿足一定的要求！以便實(shí)現(xiàn)硬件與軟件的完美結(jié)合！第57頁，共93頁，2023年，2月20日，星期二(3)比較三種映射方法中的LRU?全相聯(lián)每次改變和被比較的是Cache所有行的計(jì)數(shù)值?直接相聯(lián)不用LRU,只要有沖突就直接替換原Cache行中的頁面，因?yàn)槭嵌鄬?duì)一的關(guān)系?組相聯(lián)頁面調(diào)入時(shí),只是相關(guān)組內(nèi)的計(jì)數(shù)器的計(jì)數(shù)值會(huì)發(fā)生變化,且比較時(shí)也是比較相關(guān)組內(nèi)所有Cache行的計(jì)數(shù)器的值.第58頁，共93頁，2023年，2月20日，星期二1)幾個(gè)相關(guān)的概念

Cache臟位或修改位(Dirtybit)表示Cache中的數(shù)據(jù)是否被修改過，當(dāng)Cache中某塊數(shù)據(jù)被CPU修改(寫)時(shí)將該位置1，一般用于Cache的寫回策略,即表示Cache中的數(shù)據(jù)被更新，而主存中的數(shù)據(jù)未被更新。

Cache有效位(Validbit)

用來表示是否有不經(jīng)過Cache的主存數(shù)據(jù)更新(如DMA操作),當(dāng)有這種主存數(shù)據(jù)更新時(shí),有效位修改成0,表示主存的數(shù)據(jù)被更新,而Cache中的數(shù)據(jù)無效.5.CACHE的一致性問題第59頁，共93頁，2023年，2月20日，星期二2)Cache的結(jié)構(gòu)TagDataValid(1)Dirty(1)第60頁，共93頁，2023年，2月20日，星期二?問題的提出：

正常情況下,Cache是主存的副本，但經(jīng)過一段時(shí)間后，可能會(huì)出現(xiàn)兩者內(nèi)容不一致的情況，導(dǎo)致這種不一致的情況有：CPU將Cache某單元的內(nèi)容修改成了X’，而主存相關(guān)單元的內(nèi)容還是X，當(dāng)外設(shè)讀取X對(duì)應(yīng)單元的數(shù)值時(shí)，就會(huì)發(fā)生不一致錯(cuò)誤。3)Cache的一致性主存cacheCPUX’XI/O(1)情況1第61頁，共93頁，2023年，2月20日，星期二?解決問題的方法(a)寫直達(dá)法(WT-Writethrough)：

CPU在執(zhí)行寫操作時(shí)，必須把數(shù)據(jù)同時(shí)寫入Cache和主存。(b)寫回法(WB-WriteBack):CPU寫Cache命中時(shí)，數(shù)據(jù)只寫向Cache，不寫主存，同時(shí)修改Cache中數(shù)據(jù)的臟位或修改位，供其它讀內(nèi)存的設(shè)備參考。主存cacheCPUX’XI/O第62頁，共93頁，2023年，2月20日，星期二主存cacheCPUXX‘I/O外設(shè)將主存某單元的內(nèi)容修改成了X’，而主存該單元的內(nèi)容在修改前被讀入到Cache，還是保存原來的X，當(dāng)ＣＰＵ再次讀取該值時(shí)，就會(huì)發(fā)生不一致錯(cuò)誤。(2)情況2?解決問題的方法當(dāng)外設(shè)修改主存單元內(nèi)容時(shí)，將Ｃache對(duì)應(yīng)位置的有效標(biāo)致位置無效即可．第63頁，共93頁，2023年，2月20日，星期二主存cacheCPU1XX’或X(3)情況3CPU2X’……..第64頁，共93頁，2023年，2月20日，星期二例3假定主存和Cache之間采用直接映射方式，塊大小為16B。Cache的數(shù)據(jù)區(qū)容量為64KB，主存地址為32位，按字節(jié)編址，數(shù)據(jù)字長32位。要求：說明主存地址如何劃分，訪存過程的硬件實(shí)現(xiàn),并計(jì)算Cache行數(shù)和容量？(1)計(jì)算機(jī)字長32位，每塊大小為16B，按字節(jié)編址。

則一塊包含4個(gè)字，故需要2位表示選擇一塊內(nèi)的哪個(gè)字，而一個(gè)字32位又包含4個(gè)字節(jié)，故用2位表示一個(gè)32位字中的哪個(gè)字節(jié)。

(也可直接理解成需要4位來表示選擇哪個(gè)字節(jié))

Cache分成的行數(shù)為：

64KB/16B=4096塊，則用于選擇Cache行的索引字段位數(shù)為12位則標(biāo)記字段的位數(shù)為（表示主存的不同分區(qū)）

32-12-（2+2)=16位硬件訪問過程如下圖所示第65頁，共93頁，2023年，2月20日，星期二第66頁，共93頁，2023年，2月20日，星期二(2)計(jì)算Cache的容量4096（1+16+128）=580Kbits第67頁，共93頁，2023年，2月20日，星期二4.6虛擬存儲(chǔ)器1.虛擬存儲(chǔ)器的基本概念1)問題的提出如果目標(biāo)程序比主存空間大，程序能運(yùn)行嗎?2)虛擬存儲(chǔ)器虛擬存儲(chǔ)器是一個(gè)大容量存儲(chǔ)器的邏輯模型，該模型描述的存儲(chǔ)器的大小取決于輔存空間。在存儲(chǔ)體系中處于主存輔存層次。3)虛擬存儲(chǔ)器的優(yōu)點(diǎn)

?提供更為有效的管理存儲(chǔ)設(shè)備的方法

?主存空間的大小對(duì)程序員透明，用戶可以使用比主存空間大的程序地址空間第68頁，共93頁，2023年，2月20日，星期二4)虛擬地址與物理地址?虛擬地址：是程序的邏輯地址，由編譯程序生成，所對(duì)應(yīng)的虛擬地址空間的大小受到輔存容量的限制。?物理地址：主存的地址，其空間受CPU地址線數(shù)的限制?當(dāng)程序由輔存調(diào)入到主存時(shí)將發(fā)生虛擬地址到物理地址的轉(zhuǎn)換。第69頁，共93頁，2023年，2月20日，星期二ASystemwithVirtualMemoryAddressTranslation:HardwareconvertsvirtualaddressestophysicaladdressesviaOS-managedlookuptable(pagetable)Workstations,servers,modernPCs,etcCPU0:1:N-1:Memory0:1:P-1:PageTableVirtualAddressesPhysicalAddressesPartDisk第70頁，共93頁，2023年，2月20日，星期二ASystemwithPhysicalMemoryOnlyAddressesgeneratedbytheCPUcorresponddirectlytobytesinphysicalmemory.MostCraymachines,earlyPCs,nearlyallembeddedsystems,etc.CPU0:1:N-1:MemoryPhysicalAddresses第71頁，共93頁，2023年，2月20日，星期二PageFaults(like“CacheMisses”)頁表指示虛擬地址不在內(nèi)存中操作系統(tǒng)負(fù)責(zé)將數(shù)據(jù)從磁盤遷移到內(nèi)存中當(dāng)前進(jìn)程掛起操作系統(tǒng)負(fù)責(zé)所有的替換策略CPUMemoryPageTableVirtualAddressesPhysicalAddressesCPUMemoryPageTableVirtualAddressesPhysicalAddressesBeforefaultAfterfaultPartDiskPartDisk第72頁，共93頁，2023年，2月20日，星期二層次性結(jié)構(gòu)CPUCache主存輔助存儲(chǔ)器

MMUDMA傳送物理地址物理地址虛擬地址數(shù)據(jù)數(shù)據(jù)Cache以虛擬地址還是物理地址訪問？第73頁，共93頁，2023年，2月20日，星期二

5)虛擬存儲(chǔ)器和高速緩沖存儲(chǔ)器的比較?使用的目的不同:Cache是為了緩解快速的CPU與慢速的主存之間的速度差異。虛擬存儲(chǔ)器雖然也大大地減少了慢速輔存對(duì)CPU性能的影響，但其主要功能是解決主存容量不足的問題。?交換的信息單位不同：Cache--主存之間信息交換的基本單位是定長的塊；而主存輔存間交換信息的基本單位隨虛擬存儲(chǔ)器類型的不同而不同，如有段、頁、段頁CPU

cachecache主存輔存cache第74頁，共93頁，2023年，2月20日，星期二

Cache—主存在命中失效時(shí)，一方面信息從主存調(diào)入Cache，同時(shí)通過CPU和主存之間的專用通道調(diào)入CPU；而對(duì)于虛擬存儲(chǔ)器而言，由于CPU和輔存之間不存在專用通道，所以，只有當(dāng)信息調(diào)入主存后，CPU才能通過主存來讀信息。CPU

cachecache主存輔存cache?命中失效的處理方式不同：第75頁，共93頁，2023年，2月20日，星期二高速緩沖存儲(chǔ)器的地址映射和替換策略全由硬件實(shí)現(xiàn)，對(duì)程序員和系統(tǒng)程序員透明。虛擬存儲(chǔ)系統(tǒng)的地址映射和和替換由操作系統(tǒng)加部分硬件實(shí)現(xiàn)，其算法對(duì)程序員透明，但對(duì)系統(tǒng)程序員不透明。?透明程度不同CPU

cachecache主存輔存cache第76頁，共93頁，2023年，2月20日，星期二6)三種類型的虛擬存儲(chǔ)器段式：

按程序的自然段作為主存和輔存之間交換的信息單位。

使用段表來登記段的調(diào)入情況，段表是主存的一部分。

優(yōu)點(diǎn)：保護(hù)了用戶程序自身的相對(duì)獨(dú)立性。缺點(diǎn)：管理復(fù)雜，且容易造成主存的碎片第77頁，共93頁，2023年，2月20日，星期二頁式將程序分成固定長度的頁作為主存和輔存之間交換的信息單位。

使用頁表來登記頁的調(diào)入情況，頁表是主存的一部分。

優(yōu)點(diǎn)：管理方便，主存空間浪費(fèi)少缺點(diǎn)：破壞了原程序自身的相對(duì)獨(dú)立性。第78頁，共93頁，2023年，2月20日，星期二段頁式對(duì)程序段分成固定長度的頁，頁作為主存和輔存之間交換的信息單位。但共享和保護(hù)按段進(jìn)行。

使用段表和頁表來登記段和頁的調(diào)入情況。

優(yōu)點(diǎn)：管理方便，主存空間浪費(fèi)少，保持原程序自身的相對(duì)獨(dú)立性。第79頁，共93頁，2023年，2月20日，星期二頁式虛擬地址空間第0塊第0頁第1頁…第n-1頁………0頁1…N-1主存空間虛擬空間………磁盤部分磁盤第80頁，共93頁，2023年，2月20日，星期二2.頁式虛擬存儲(chǔ)器(1)基本概念頁表記錄虛擬空間和物理空間的映射關(guān)系第81頁，共93頁，2023年，2月20日，星期二(2)頁式虛擬存儲(chǔ)器邏輯地址劃分虛擬頁號(hào)頁偏移量虛擬地址與物理頁大小相關(guān)與頁表項(xiàng)數(shù)相關(guān)若主存頁大小為4K，虛存大小為4GB，則：頁內(nèi)偏移量為：12位虛擬頁號(hào)為：32-12=20位，對(duì)應(yīng)的頁表有1024*