第3章存儲器層次結(jié)構(gòu)-5

計算機組成原理

—多層次的存儲器(5)2016-3-30第3章多層次的存儲器3.1存儲器概述3.1.1存儲器的分類3.1.2存儲器的分級3.1.3主存儲器的技術(shù)指標(biāo)3.2SRAM存儲器3.2.1基本的靜態(tài)存儲元陣列3.2.2基本的SRAM邏輯結(jié)構(gòu)3.2.3讀/寫周期波形圖3.3DRAM存儲器3.3.1DRAM存儲位元的記憶原理3.3.2DRAM芯片的邏輯結(jié)構(gòu)3.3.3讀/寫周期、刷新周期3.3.4存儲器容量的擴充3.4只讀存儲器和閃速存儲器3.4.1只讀存儲器ROM3.4.2FLASH存儲器3.5并行存儲器3.5.1雙端口存儲器3.5.2多模塊交叉存儲器3.6cache存儲器3.6.1cache基本原理3.6.2主存與cache的地址映射3.6.3替換策略3.6.4cache的寫操作策3.7虛擬存儲器*3.8奔騰系列的虛存組織計算機組成原理2上節(jié)回顧為解決主存和CPU之間的速度不匹配問題，依據(jù)程序訪問的局部性原理，在主存和CPU之間引入Cache。Cache的功能全部通過硬件進行實現(xiàn)，在具體設(shè)計時，要考慮Cache容量、數(shù)據(jù)塊的大小、地址映射方式、替換算法、寫策略等問題。Cache的地址映射有直接映射、全相聯(lián)映射、組相聯(lián)映射三種方式。Cache的替換算法有FIFO法、LRU法、RAND法等。寫策略有寫回法、全寫法（寫直達法）等。計算機組成原理33.6.2主存與cache的地址映射選擇哪種映射方式，要考慮：硬件是否容易實現(xiàn)(目標(biāo)：容易)；地址變換的速度是否快(目標(biāo)：快)；主存空間的利用率是否高(目標(biāo)：高)；主存裝入一塊時，發(fā)生沖突的概率(目標(biāo)：小)；計算機組成原理43.6.2主存與cache的地址映射1、全相聯(lián)映射方式轉(zhuǎn)換公式：

主存地址長度=(s+w)位； 主存尋址單元數(shù)=2(s+w)個字或字節(jié)； 主存的塊數(shù)=2s； 塊大?。叫写笮?2w個字或字節(jié)； 標(biāo)記tag長度=s位； cache的行數(shù)k=不由地址格式確定；特點：優(yōu)點：靈活，沖突概率小，Cache的命中率和利用率高；缺點：⑴比較器難實現(xiàn)，需要一個訪問速度很快代價高的相聯(lián)存儲器；⑵尋找塊時，比較器比較的次數(shù)多；應(yīng)用場合：小容量的Cache計算機組成原理53.6.2主存與cache的地址映射2、直接映射方式轉(zhuǎn)換公式：

主存的塊數(shù)=2s；

主存地址長度=(s+w)位； 尋址單元數(shù)=2s+w個字或字節(jié)； 塊大小=行大小=2w個字或字節(jié)； cache的行數(shù)=m=2r； 標(biāo)記大小=(s-r)位；優(yōu)點：(1)硬件實現(xiàn)簡單，成本低；(2)Cache地址為主存地址的低（r+w）位，不需變換。缺點：不靈活，存在Cache有空行不能存數(shù)據(jù)塊問題，替換頻繁，沖突概率高（抖動）。應(yīng)用場合：適合大容量Cache，更多行數(shù)可減少沖突機會。計算機組成原理63.6.2主存與cache的地址映射3、組間直接相聯(lián)、組內(nèi)全相聯(lián)的組相聯(lián)映射方式轉(zhuǎn)換公式： 主存地址長度=(s+w)位； 尋址單元數(shù)=2s+w個字或字節(jié)； 塊大小=行大小=2w個字或字節(jié)； 主存的塊數(shù)=2s；

Cache每組的行數(shù)=k； cache組數(shù)v=2d； cache標(biāo)記大小=(s-d)位；計算機組成原理73.6.2主存與cache的地址映射1、全相聯(lián)映射方式（隨意坐）主存地址長度=(s+w)位； 主存尋址單元數(shù)=2(s+w)個字或字節(jié)； 主存的塊數(shù)=2s； 塊大小＝行大小=2w個字或字節(jié)； 標(biāo)記長度=s位；

2、直接映射方式（按號入座）主存地址長度=(s+w)位； 主存尋址單元數(shù)=2(s+w)個字或字節(jié)； 主存的塊數(shù)=2s； 塊大?。叫写笮?2w個字或字節(jié)； cache的行數(shù)=m=2r；

標(biāo)記長度=(s-r)位；3、組相聯(lián)映射方式（按排入座，排內(nèi)隨意做）

主存地址長度=(s+w)位； 主存尋址單元數(shù)=2s+w個字或字節(jié)； 塊大小=行大小=2w個字或字節(jié)； 主存的塊數(shù)=2s；

cache每組的行數(shù)=k； cache組數(shù)v=2d； cache標(biāo)記大小=(s-d)位；計算機組成原理83.6.2主存與cache的地址映射全相聯(lián)映射實例分析（注意：行=塊,字長32位）[例1]：假設(shè)主存塊大小為16B，主存有4096B(則有：4096B÷16B=256塊，即256行)，cache有128B

(則有：128B÷16B=8行)，按字節(jié)編址(16=24，所以塊內(nèi)地址碼4位)，若采用全相聯(lián)映射；cache的當(dāng)前存儲情況如下所示，若訪存指令的地址碼依次為101010011010和100101101001，分別簡述其訪存過程；計算機組成原理93.6.2主存與cache的地址映射[解]：⑴訪問內(nèi)存單元101010011010時：取地址碼的高8位10101001依次與cache中8行的標(biāo)記比較，當(dāng)比較到第011行的標(biāo)記時發(fā)現(xiàn)相同(即命中cache)，則訪問該行的第1010號單元，即內(nèi)存地址101010011010映射到cache地址0111010；計算機組成原理103.6.2主存與cache的地址映射[解]：⑵訪問內(nèi)存單元100101101001時：取地址碼的高8位10010110依次與cache中8行的標(biāo)記比較，發(fā)現(xiàn)沒有相同的(即不命中cache)，則訪問內(nèi)存的100101101001號單元;同時把內(nèi)存的第10010110塊（即100101100000至100101101111單元）的內(nèi)容調(diào)入cache，根據(jù)一定的替換策略替換cache的某一行，假設(shè)是第101行，并用10010110覆蓋第101行的標(biāo)記；計算機組成原理113.6.2主存與cache的地址映射直接相聯(lián)映射實例分析（注意：行=塊）[例2]：假設(shè)內(nèi)存塊大小為16B，主存有4096B(則有:4096B÷16B=256塊，即256行)，cache有128B

(則有:128B÷16B=8行)，按字節(jié)編址(16=24，所以塊內(nèi)地址碼4位)，若采用直接相聯(lián)映射；cache的當(dāng)前存儲情況如下所示，若訪存指令的地址碼依次為101010011010和100101101001，分別簡述其訪存過程；計算機組成原理123.6.2主存與cache的地址映射[解]：

⑴訪問內(nèi)存單元101010011010時：取地址碼的高5位組號10101與cache中第001行的標(biāo)記比較，發(fā)現(xiàn)相同(即命中cache)，則訪問該行的第1010號單元,即內(nèi)存地址101010011010映射到cache地址0011010；計算機組成原理133.6.2主存與cache的地址映射[解]：⑵訪問內(nèi)存單元100101101001時：取地址碼的高5位組號10010與cache中第110行的標(biāo)記比較，發(fā)現(xiàn)不相同(即不命中cache)，則訪問內(nèi)存的100101101001號單元；同時把內(nèi)存的第10010110塊（即100101100000至100101101111單元）的內(nèi)容調(diào)入cache，替換cache的第110行內(nèi)容，并用組號10010覆蓋第110行的標(biāo)記00111；計算機組成原理143.6.2主存與cache的地址映射組相聯(lián)映射實例分析（注意：行=塊）[例3]：假設(shè)內(nèi)存塊大小為16B，主存有65536B(即65536B÷16B=4096塊)，cache有256B(即256B÷16B=16行)；若cache分4組(因為16÷4=4,所以每組4行)。若采用組間直接相聯(lián)、組內(nèi)全相聯(lián)的組相聯(lián)映射方式；cache的當(dāng)前存儲情況如下所示，若兩次訪存的地址碼依次為1010110110011010和1001001100111001，試簡述其操作過程；計算機組成原理153.6.2主存與cache的地址映射

[解]：⑴訪問內(nèi)存單元1010110110011010時：取地址碼的高10位組號1010110110與cache中第01組的4行標(biāo)記依次比較，發(fā)現(xiàn)與第01組的第10行相同(即命中cache)，則訪問該行的第1010號單元，即內(nèi)存地址1010110110011010映射到cache地址01101010；

計算機組成原理163.6.2主存與cache的地址映射

[解]：⑵訪問內(nèi)存單元1001001100111001時：取地址碼的高10位組號1001001100與cache中第11組的4行標(biāo)記依次比較,發(fā)現(xiàn)都不相同(即不命中cache),則訪問內(nèi)存的1001001100111001號單元；同時把內(nèi)存的第100100110011塊(即1001001100110000至1001001100111111單元)的內(nèi)容調(diào)入cache，根據(jù)某種策略替換cache的第11組的某一行(假設(shè)是第00行),并用組號1001001100覆蓋第11組的第00行標(biāo)記1010001101；計算機組成原理173.6.2主存與cache的地址映射行號計算機組成原理183.6.2主存與cache的地址映射典型例題計算機組成原理192014-4-293.6.2主存與cache的地址映射[例9]有一個處理器，主存容量1MB，塊大小16B，Cache容量64KB。若Cache采用全相聯(lián)映射，對內(nèi)存地址(F0010)H給出相應(yīng)的標(biāo)記和字號。注意：教材上該題目疏漏多，注意糾正。計算機組成原理203.6.2主存與cache的地址映射解：塊大小=行大小=24字節(jié)w=4主存尋址單元數(shù)=2s+w=1M=220s+w=20位，s=16位主存的塊數(shù)2s=216

，標(biāo)記大小s=16位內(nèi)存格式內(nèi)存地址（F0010）16=（11110000000000010000）2對應(yīng)的標(biāo)記=1111000000000001字號=0000標(biāo)記s字號w16位4位計算機組成原理213.6.3cache的替換策略1、LFU(最不經(jīng)常使用)：最近一段時間內(nèi)訪問次數(shù)最少的行換出：每行設(shè)置計數(shù)器，初值為0；被訪問的行計數(shù)器每次增1；替換計數(shù)器值最小的行；不能反映近期cache的訪問情況；2、LRU(近期最少使用)：近期長久未被訪問的行換出：每行設(shè)置計數(shù)器，初值為0；訪問某行時，其行計數(shù)器清零，而其它行的計數(shù)器增1；替換計數(shù)器值最大的行；反映近期cache的訪問情況，體現(xiàn)程序局部性原理；符合cache的工作原理；計算機組成原理223.6.3cache的替換策略3、FIFO(先進先出)：命不中采用先進先出策略，命中單元重新位于隊首優(yōu)點：容易實現(xiàn)缺點：沒有依據(jù)程序訪問的局部性原理，可能會把經(jīng)常使用的程序塊（循環(huán)程序）替換掉。4、隨機替換：從特定的行位置中隨機地選取一行換出即可優(yōu)點：硬件上容易實現(xiàn)，且速度也比前兩種策略快。缺點：沒有體現(xiàn)程序局部性原理，隨意換出的數(shù)據(jù)很可能馬上又要使用，從而降低命中率和cache工作效率。但這個不足隨著cache容量增大而減小。計算機組成原理233.6.4cache的寫操作策略(1)寫回法：寫cache命中時，只修改cache內(nèi)容，不立即寫入主存，當(dāng)此行被換出時才寫回主存。每行設(shè)修改位（臟位），修改cache時，該位置1。當(dāng)該行需換出時，對其修改位進行判斷，決定寫回主存或簡單舍掉優(yōu)點：減少訪問主存次數(shù)；缺點：主存與cache存在不一致性隱患；(2)全寫法（寫直達法）：寫cache命中時，Cache與內(nèi)存同時寫入；優(yōu)點：cache不必設(shè)修改位，不存在不一致性問題；缺點：訪存次數(shù)多，降低cache功效；(3)寫一次法：前兩種方法的結(jié)合；與寫回法基本一致，不同的是第一次寫Cache命中時采用全寫法；計算機組成原理24小結(jié)計算機組成原理25某一主存塊只能固定

映射到某一

緩存塊直接全相聯(lián)組相聯(lián)某一主存塊能映射到任一緩存塊某一

主存塊只能

映射到某一

緩存組

中的任一塊不靈活成本高練習(xí)1.

在主存與Cache間建立地址映射，有幾種不同的地址映射方式，沒有的是

。A全相聯(lián)映射方式 B直接映射方式C組相聯(lián)映射方式 D隨機映射方式2.某計算機的Cache共有16塊，采用2路組相聯(lián)映射方式（即每組2塊）。每個主存塊大小32字節(jié)，按字節(jié)編址。主存129號單元所在主存塊應(yīng)裝入到的Cache組號是

。A.0B.2C.4D.6【例】假設(shè)主存容量為512KB，cache容量為4KB，每個字塊為16個字，每個字為32位。（1）cache地址有多少位？可容納多少塊？（2）主存地址有多少位？可容納多少塊？（3）在直接映射方式下，主存的第幾塊映射到cache中的第5塊（設(shè)起始字塊為第1塊）（4）畫出直接映射方式下的主存地址字段中各段的位數(shù)。【例】假設(shè)主存容量為512KB，cache容量為4KB，每個字塊為16個字，每個字為32位。（1）cache地址有多少位？可容納多少塊？【解】（1）cache容量為4KB=212B，即cache地址為12位，c+b=12。每個字32位=4B，每個字塊為16個字，則每字塊16×4B=26B，則每個字塊的塊內(nèi)地址為6位，即b=6。c=12-b=6，C=26=64塊?！纠考僭O(shè)主存容量為512KB，cache容量為4KB，每個字塊為16個字，每個字為32位。（2）主存地址有多少位？可容納多少塊？【解】（2）主存容量512KB=219B，即主存地址為19位。m=19-b=13。M=213=8192塊。【例】假設(shè)主存容量為512KB，cache容量為4KB，每個字塊為16個字，每個字為32位。（3）在直接映射方式下，主存的第幾塊映射到cache中的第5塊（設(shè)起始字塊為第1塊）【解】（3）i=jmodCi是cache的字塊號，j是主存的字塊號，C為Cache的字塊數(shù)量為26=64塊，主存的字塊數(shù)量為213=8192塊。i=5，主存的字塊數(shù)分別是5，64+5，…，(27-1)26+5，共128個塊?！纠考僭O(shè)主存容量為512KB，cache容量為4KB，每個字塊為16個字，每個字為32位。（4）畫出直接映射方式下的主存地址字段中各段的位數(shù)?！窘狻縨=13，c=6，b=6，即得到t=7位。主存地址為：103.7虛擬存儲器3.7.1虛擬存儲器的基本概念3.7.2頁式虛擬存儲器3.7.3段式虛擬存儲器和段頁式虛擬存儲器3.7.4虛存的替換算法計算機組成原理353.7.1虛擬存儲器的基本概念1、虛擬存儲器：一個容量非常大的存儲器邏輯模型，非實際的物理存儲器，由主存和聯(lián)機工作的輔存共同組成，在硬件和系統(tǒng)軟件的共同管理下工作，對應(yīng)用程序員透明。2、目的：解決存儲容量和存取速度矛盾問題，它具有主存的速度和輔存的容量。3、實地址和虛地址(1)虛地址(邏輯地址)：用戶編程時程序(或數(shù)據(jù))使用的地址，對應(yīng)存儲空間稱虛存空間(邏輯地址空間)(2)實地址(物理地址)：程序或數(shù)據(jù)調(diào)入主存的主存地址，對應(yīng)的存儲空間稱主存空間(物理存儲空間)計算機組成原理363.7.1虛擬存儲器的基本概念4、虛存的訪問過程編程時：按虛地址編程并存在輔存；程序運行時，由地址變換機構(gòu)依當(dāng)時分配給該程序的實地址空間把程序(或程序一部分)調(diào)入實存。每次訪存時，先判斷該虛地址對應(yīng)程序是否在實存：若在，則進行地址轉(zhuǎn)換并訪問實存；若不在，則按某算法將輔存中的程序(或程序一部分)調(diào)入實存，再按同樣方法訪問實存；注意：⑴每程序的虛空間大小依賴于輔存大小和程序本身實際需要，與主存大小無關(guān)：可遠大于、遠小于主存空間；⑵若主存命中率很高，則虛存訪問時間就接近主存訪問時間，此虛存機制就能實現(xiàn)“每個程序可擁有一個虛擬存儲器，該虛擬存儲器具輔存容量和接近主存的訪問速度”；⑶“內(nèi)存=cache+主存”；而“虛存=主存+輔存+存儲管理部件(軟件和硬件)”。虛存對應(yīng)用程序員透明，但對設(shè)計存儲管理軟件的系統(tǒng)程序員不透明。計算機組成原理373.7.1虛擬存儲器的基本概念5、虛存機制要解決的關(guān)鍵問題：⑴調(diào)度問題：決定哪些程序和數(shù)據(jù)調(diào)入主存；⑵地址映射問題：主存命中而訪問主存時如何把虛地址變?yōu)橹鞔娴刂?，即“?nèi)地址變換”；主存不命中而訪問輔存時如何把虛地址變?yōu)檩o存地址，即“外地址變換”；此外還要解決主存分配、存儲保護、程序重定位等問題；⑶替換問題：決定哪些信息調(diào)出主存而騰出空間讓位于新調(diào)入的信息；⑷更新問題：確保主存和輔存的一致性；計算機組成原理383.7.2頁式虛擬存儲器1、頁式虛存地址映射

虛存空間分成等大小邏輯頁，主存空間分成與邏輯頁等大小的物理頁；虛、實地址都分2字段：高字段頁號，低字段頁內(nèi)地址(偏移量)，虛、實頁內(nèi)地址長度一樣每個進程對應(yīng)一個頁表頁表每一項對應(yīng)一個邏輯頁每頁表項包含有效位和主存頁號頁表大小由進程大小確定頁表的基地址保存在頁表基址寄存器頁表本身一般放在主存中計算機組成原理393.7.2頁式虛擬存儲器2、內(nèi)頁表和外頁表內(nèi)頁表：實現(xiàn)虛地址到主存物理地址的變換外頁表：實現(xiàn)虛地址到輔存地址變換的表當(dāng)主存缺頁時，調(diào)頁操作首先通過外頁表確定輔存地址，外頁表的結(jié)構(gòu)與輔存的尋址機制有關(guān)；外頁表通常放在輔存中，主存缺頁時調(diào)入主存，由存儲管理部件向CPU發(fā)出“缺頁中斷”進行調(diào)頁操作。計算機組成原理403.7.2頁式虛擬存儲器3、頁式存儲器的優(yōu)缺點優(yōu)點：頁等長且頁長固定，構(gòu)造頁表容易，易于管理，不存在外碎片缺點：頁長與程序無關(guān)，易于產(chǎn)生內(nèi)碎片；同一程序可能部分在主存，部分在輔存，給換入換出、存儲保護、存儲共享等帶來麻煩。計算機組成原理413.7.3段式虛擬存儲器和段頁式虛擬存儲器1、段式虛擬存儲器根據(jù)程序的自然分界將程序占據(jù)的虛空間分成長度可動態(tài)變化的若干不同類型段(如程序段、操作數(shù)段、常數(shù)段等)；虛地址由“段號”和“段內(nèi)地址”組成；虛地址到實地址的轉(zhuǎn)換由段表實現(xiàn)。每個程序設(shè)置一個段表，段表每一項對應(yīng)一個段，每個段表項由“有效位(標(biāo)示該段是否調(diào)入主存)”、“段起址(標(biāo)示該段在主存的首地址)”和“段長(標(biāo)示該段的實際長度)”三部分組成；段表大小由程序大小確定，段表的基地址保存在段表基址寄存器中，段表本身一般放在主存中，也可以放在輔存中；計算機組成原理423.7.3段式虛擬存儲器和段頁式虛擬存儲器段式虛擬存儲器的優(yōu)點：段的邏輯獨立性使其易于編譯、管理、修改和保護，便于多道程序共享；段長可動態(tài)變化，允許自由調(diào)度，以便有效利用主存空間；段式虛擬存儲器的缺點：主存空間分配麻煩；易于產(chǎn)生外碎片：沒有內(nèi)碎片，外碎片多；形成實地址麻煩：段長不一定是2的整數(shù)倍，因而虛地址的低位部分未必是段內(nèi)偏移，形成實地址時必須把段起址和段內(nèi)偏移相加才行(頁式虛擬存儲器：主存頁號與邏輯頁內(nèi)地址拼接即可)；計算機組成原理432014-4-293.7.3段式虛擬存儲器和段頁式虛擬存儲器地址轉(zhuǎn)換：據(jù)虛地址段號和段表基地址找到對應(yīng)段表項，若段表項有效位為0，則產(chǎn)生調(diào)段中斷，從輔存調(diào)入該段；若段表項有效位為1，則取虛地址的段內(nèi)地址和段表項的段長比較，段內(nèi)地址大產(chǎn)生越界中斷，段內(nèi)地址小則將“段起址”+“虛地址的段內(nèi)地址”形成主存的物理地址。計算機組成原理443.7.3段式虛擬存儲器和段頁式虛擬存儲器2、段頁式虛擬存儲器：頁式與段式的集合實存分成等大的頁，程序按邏輯結(jié)構(gòu)分成若干段，每段再按實存頁大小分成若干頁，程序按頁調(diào)入調(diào)出(注意：實存中，同一程序的各段未必連續(xù)、各頁未必連續(xù))，程序按段編程、保護和共享；虛地址由“段號S、段內(nèi)頁號P、頁內(nèi)偏移D”組成，多任務(wù)操作系統(tǒng)還在虛地址前加一個標(biāo)示程序在系統(tǒng)中的序號的“基號N”；每道程序通過一個段表和多個頁表進行兩級再定位：段表每一項對應(yīng)一個段的頁表首地址，頁表的每一項對應(yīng)一個物理頁號；計算機組成原理453.7.3段式虛擬存儲器和段頁式虛擬存儲器段頁式虛擬存儲器地址變換實例：[例12]假設(shè)有三道程序，基號用A、B、C表示，對應(yīng)的基地址寄存器內(nèi)容(段表基地址)分別為SA、SB、SC，程序A有2個段，程序B有3個段，程序C有3個段，則其邏輯地址到物理地址的變換過程如下：計算機組成原理463.7.3段式虛擬存儲器和段頁式虛擬存儲器計算機組成原理473.7.3段式虛擬存儲器和段頁式虛擬存儲器計算機組成原理483.7.4快表轉(zhuǎn)換后援緩沖器(TLB)(塊表)頁表、邏輯頁都在主存中，CPU取得信息至少要訪問兩次物理存儲器為減少訪存次數(shù)，對頁表實現(xiàn)二級緩存，即把頁表中活躍部分放在高速存儲部件中，這種專用于存放頁表部分副本的小容量高速存儲部件稱之為“轉(zhuǎn)換后援緩沖器，通常由相連存儲器實現(xiàn)，其作用與工作過程類似于cache)”，主存中的完整頁表叫慢表；計算機組成原理492014-4-29