高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)

1、高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院李金寶2006年2月-2010年4月計(jì)算機(jī)科學(xué)技術(shù)學(xué)院研究生課程高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第一章 并行計(jì)算機(jī)模型第二章 程序劃分與調(diào)度第三章 系統(tǒng)互連與通信第四章 可擴(kuò)展性能原理第五章 并行存儲(chǔ)器系統(tǒng)第六章 高速緩存與共享存儲(chǔ)器第七章 指令級(jí)并行處理第八章 標(biāo)量處理機(jī)與向量處理機(jī)第九章 并行模型、語(yǔ)言與編譯器第十章 并行程序設(shè)計(jì)與開(kāi)發(fā)第五章 并行存儲(chǔ)器系統(tǒng)5.1 存儲(chǔ)器系統(tǒng)的層次結(jié)構(gòu)5.2 包含性、一致性和局部性5.3 存儲(chǔ)器容量的規(guī)劃5.4 虛擬存儲(chǔ)器技術(shù)5.5 交叉訪(fǎng)問(wèn)的存儲(chǔ)器 現(xiàn)代計(jì)算機(jī)系統(tǒng)都以存儲(chǔ)器為現(xiàn)代計(jì)算機(jī)系統(tǒng)都以存儲(chǔ)器為中心，在計(jì)算機(jī)運(yùn)行過(guò)程

2、中，中心，在計(jì)算機(jī)運(yùn)行過(guò)程中，存儲(chǔ)器是各種信息存儲(chǔ)和交存儲(chǔ)器是各種信息存儲(chǔ)和交換的中心。換的中心。5.1 存儲(chǔ)器系統(tǒng)的層次結(jié)構(gòu)CPU內(nèi)的寄存器高速緩存主存儲(chǔ)器磁盤(pán)存儲(chǔ)器磁帶機(jī)層0：M0層1：M1層2：M2層3：M3層4：M4容量和存取時(shí)間增加每位成本增加存儲(chǔ)器系統(tǒng)的層次結(jié)構(gòu)圖五個(gè)參數(shù)：存取時(shí)間ti：從CPU到第i層存儲(chǔ)器的往返時(shí)間存儲(chǔ)器容量Si：第i層的字節(jié)或字的數(shù)量每字節(jié)成本Ci：第i層存儲(chǔ)器的成本為CiSi傳輸帶寬bi：相鄰層之間傳送信息的速率傳輸單位Xi：i和i+1層之間數(shù)據(jù)傳送的粒度 對(duì)存儲(chǔ)器系統(tǒng)中各層次存儲(chǔ)器的特性，1993年的統(tǒng)計(jì)數(shù)據(jù)如下表：存儲(chǔ)器層次特性第0層CPU寄存器第1層高

3、速緩存第2層主存儲(chǔ)器第3層磁盤(pán)存儲(chǔ)器第4層磁帶存儲(chǔ)器設(shè)備工藝存取時(shí)間容量(字節(jié))成本(美分/KB)帶寬(MB/S)傳送單位分配管理ECLSRAMDRAM磁盤(pán)機(jī)磁帶機(jī)10ns25-40ns60-100ns10-20ms2-20min512B128KB512MB60-228GB512G-2TB18000725.60.230.01400-800250-40080-1333-50.18-0.23字:4-8B塊:32B頁(yè):0.5-1KB文件:5-512KB后援存儲(chǔ)器編譯器分配 硬件控制 操作系統(tǒng)操作系統(tǒng)/用戶(hù)操作系統(tǒng)/用戶(hù)第五章 并行存儲(chǔ)器系統(tǒng)5.1 存儲(chǔ)器系統(tǒng)的層次結(jié)構(gòu)5.2 包含性、一致性和局部性5

4、.2.1 包含性5.2.2 一致性5.2.3 局部性5.3 存儲(chǔ)器容量的規(guī)劃5.4 虛擬存儲(chǔ)器技術(shù)5.5 交叉訪(fǎng)問(wèn)的存儲(chǔ)器5.2 包含性、一致性和局部性5.2.1 包含性（inclusion）1. 包含性的定義 初始時(shí)，所有信息項(xiàng)都存放在最外層Mn，在處理過(guò)程中，它的子集被復(fù)制到Mn-1，同樣， Mn-1的子集被復(fù)制到Mn-2， 如果在Mi中找到一個(gè)信息字，那么同一個(gè)字的Copy在所有的高層Mi+1，Mi+2，Mn中都一定可以找到，即存在如下規(guī)律：M0 M1 M2 Mn2. 相鄰層之間的數(shù)據(jù)傳送單位CPU高速緩存：字高速緩存主存儲(chǔ)器：塊（每塊32個(gè)字節(jié)（8個(gè)字）主存磁盤(pán)：頁(yè)面（比如每頁(yè)4K字節(jié)

5、，包含128塊）磁盤(pán)磁帶：段包含性可以用下面的圖來(lái)說(shuō)明：CPU寄存器baM1:高速緩存a,b為高速緩存塊，32個(gè)字節(jié)頁(yè)面AaM2:主存儲(chǔ)器頁(yè)面Bb頁(yè)面AaM3:磁盤(pán)存儲(chǔ)器頁(yè)面Bb段F段G頁(yè)面AaM4:磁帶機(jī)后援存儲(chǔ)器頁(yè)面Bb段F段G字單位塊單位頁(yè)單位段單位5.2.2 一致性（coherence）1.一致性定義同一個(gè)信息項(xiàng)與后繼存儲(chǔ)器層次的副本是一致的。如果在高速緩存中的一個(gè)字被修改過(guò)，那么在所有更高層上該字的副本也必須立即或最后加以修改 。2.維護(hù)一致性的兩種策略（1）寫(xiě)直達(dá)（write-through,WT），即如果在Mi（i=1，2，n-1）中修改了一個(gè)字，則在Mi+1中需要立即修改。 （

6、2）寫(xiě)回（write-back,WB），即在Mi+1 中的修改延遲到Mi中正在修改的字被替換時(shí)才進(jìn)行。5.2.3 局部性（locality） Hennessy和Patterson（1990年）提出了一條90-10規(guī)則： 典型程序在10%的代碼上可能要耗費(fèi)其執(zhí)行時(shí)間的90% 例如嵌套循環(huán)操作的最內(nèi)層循環(huán) 時(shí)間局部性（temporal locality）：最近的訪(fǎng)問(wèn)項(xiàng)（指令或數(shù)據(jù)）很可能在不久的將來(lái)再次被訪(fǎng)問(wèn)。即對(duì)最近使用區(qū)域的集中訪(fǎng)問(wèn)。空間局部性（spatial locality）：一個(gè)進(jìn)程訪(fǎng)問(wèn)的各項(xiàng)的地址彼此很近，例如，表操作或數(shù)組操作含對(duì)地址空間中某一區(qū)域的集中訪(fǎng)問(wèn)。順序局部性（sequen

7、tial locality）：在典型程序中，除轉(zhuǎn)移指令產(chǎn)生不按次序的轉(zhuǎn)移外，指令都是順序執(zhí)行的。 局部性原理指導(dǎo)我們?nèi)ピO(shè)計(jì)高速緩存、主存儲(chǔ)器以及虛擬存儲(chǔ)器組織。第五章 并行存儲(chǔ)器系統(tǒng)5.1 存儲(chǔ)器系統(tǒng)的層次結(jié)構(gòu)5.2 包含性、一致性和局部性5.3 存儲(chǔ)器容量的規(guī)劃5.3.1 命中率5.3.2 有效存取時(shí)間5.4 虛擬存儲(chǔ)器技術(shù)5.5 交叉訪(fǎng)問(wèn)的存儲(chǔ)器5.3 存儲(chǔ)器容量的規(guī)劃存儲(chǔ)器層次結(jié)構(gòu)的性能是由層次結(jié)構(gòu)的有效存取時(shí)間Teff決定的，它依賴(lài)于相繼層次的命中率和訪(fǎng)問(wèn)頻率。 在Mi中找到一個(gè)信息項(xiàng)時(shí)，稱(chēng)之為命中，反之稱(chēng)為缺失。 假定在層次結(jié)構(gòu)中的存儲(chǔ)器層次為Mi和Mi-1，其中i=1，2，n。則在

8、Mi層的命中率hi是信息項(xiàng)可在Mi中找到的概率。 它是表示兩個(gè)相鄰層Mi-1和Mi特性的函數(shù)。 在Mi中的缺失率定義為1-hi。5.3.1 命中率 相繼層的命中率是存儲(chǔ)器容量、管理策略和程序行為的函數(shù)，它是獨(dú)立的隨機(jī)變量，其值在0到1之間。 假設(shè)h0=0和hn=1，即CPU總是先訪(fǎng)問(wèn)M1，并且訪(fǎng)問(wèn)到最外層Mn時(shí)總是命中。則對(duì)Mi的訪(fǎng)問(wèn)頻率為：iiihhhhf)1()1)(1(121即在較低層次有i-1次缺失而在Mi有一次命中時(shí)訪(fǎng)問(wèn)Mi成功的概率。111,1hffniinfff21通常情況下，有：對(duì)存儲(chǔ)器內(nèi)層的訪(fǎng)問(wèn)比對(duì)外層的訪(fǎng)問(wèn)要多。訪(fǎng)問(wèn)內(nèi)存比訪(fǎng)問(wèn)外存要多。5.3.2 有效存取時(shí)間每當(dāng)發(fā)生缺失時(shí)

9、，就要付出代價(jià)去訪(fǎng)問(wèn)較高層次的存儲(chǔ)器。這種缺失在Cache中稱(chēng)為塊缺失。在主存儲(chǔ)器中稱(chēng)為缺頁(yè)錯(cuò)（page fault），因?yàn)閴K和頁(yè)面是這些層次之間傳送信息的單位。缺頁(yè)錯(cuò)付出的時(shí)間代價(jià)要比塊缺失付出的更大：nnnniiieffthhhhthhthtfT)1()1)(1()1(1211221115.3.3 層次結(jié)構(gòu)的優(yōu)化 優(yōu)化目標(biāo) 使Teff接近于M1的t1， 總成本接近于Mn的Cn。 優(yōu)化過(guò)程可以表達(dá)為：對(duì)一個(gè)線(xiàn)性規(guī)劃求最小值問(wèn)題:減到最小值。要將有效存取時(shí)間總價(jià)格的上限）時(shí)，對(duì)于niiieffniiitotaliitfTCSCCnitS101(, 2 , 1, 0, 0例1：存儲(chǔ)器層次結(jié)構(gòu)設(shè)計(jì)

10、存儲(chǔ)器層次存取時(shí)間容量?jī)r(jià)格/K字節(jié)高速緩存主存儲(chǔ)器磁盤(pán)陣列t1 = 25nst2 = 未知t3 = 4mss1=512K字節(jié)s2=32M字節(jié)s3 = 未知c1=1.25美元c2=0.2美元c3=0.0002美元要求：有效存取時(shí)間Teff=10.04s, 高速緩存命中率為h1=0.98， 主存儲(chǔ)器命中率h2=0.9， 總成本上限為15000美元。解：nstthhhthhthTGByteSSCSCSCCeff90304.10)1)(1 ()1 (8 .391500023321221113332211代入可得代入有：如果在同樣的預(yù)算限制條件下，要把主存儲(chǔ)器容量提高64M字節(jié)，那么只好以減少磁盤(pán)容量為

11、代價(jià)，但是這一變化并不影響高速緩存的命中率。如果使用合適的頁(yè)面替換算法，可能會(huì)增加主存儲(chǔ)器的命中率，但Teff有所降低。練習(xí)：P168 習(xí)題4.11層次化存儲(chǔ)器系統(tǒng)必須解決的問(wèn)題：（1）數(shù)據(jù)塊在較高層存儲(chǔ)器中存放在哪個(gè)位置？即塊和頁(yè)的定位問(wèn)題。如果一個(gè)塊存放在某一上層存儲(chǔ)器中，怎樣確定并找到該塊，即塊的尋址問(wèn)題。（2）不命中的將從下層存儲(chǔ)器中訪(fǎng)問(wèn)，并將該塊調(diào)入上層存儲(chǔ)器中，但是如果上層存儲(chǔ)器中已無(wú)空閑空間，則勢(shì)必將上層存儲(chǔ)器中的某一塊調(diào)出，但應(yīng)調(diào)出那一塊，即替換問(wèn)題。（3）在寫(xiě)訪(fǎng)問(wèn)時(shí)，寫(xiě)入上層存儲(chǔ)器中的數(shù)據(jù)必須在適當(dāng)?shù)臅r(shí)候?qū)懭胂聦哟鎯?chǔ)器，何時(shí)寫(xiě)？第五章 并行存儲(chǔ)器系統(tǒng)5.1 存儲(chǔ)器系統(tǒng)的層次結(jié)

12、構(gòu)5.2 包含性、一致性和局部性5.3 存儲(chǔ)器容量的規(guī)劃5.4 虛擬存儲(chǔ)器技術(shù)5.4.1 虛擬存儲(chǔ)器原理 5.4.2 共享存儲(chǔ)和分布存儲(chǔ)5.4.3 DSM與SVM5.4.4 虛擬存儲(chǔ)器的主要技術(shù)5.5 交叉訪(fǎng)問(wèn)的存儲(chǔ)器5.4 虛擬存儲(chǔ)器技術(shù) 19611961年英國(guó)曼徹斯特大學(xué)年英國(guó)曼徹斯特大學(xué)KilbrnKilbrn等人提出等人提出了了7070年代被廣泛地應(yīng)用于大中型計(jì)算機(jī)系年代被廣泛地應(yīng)用于大中型計(jì)算機(jī)系統(tǒng)中、目前許多微型機(jī)也廣泛使用的統(tǒng)中、目前許多微型機(jī)也廣泛使用的虛擬虛擬存儲(chǔ)器。存儲(chǔ)器。 虛擬存儲(chǔ)器提供了幾乎沒(méi)有限制的存儲(chǔ)器工作空間。 虛擬地址在編譯時(shí)產(chǎn)生。 虛擬地址到物理地址的轉(zhuǎn)換在運(yùn)

13、行時(shí)進(jìn)行，需要使用轉(zhuǎn)換表和映象系統(tǒng)。 替換策略。5.4.1 5.4.1 虛擬存儲(chǔ)器工作原理虛擬存儲(chǔ)器工作原理 把主存儲(chǔ)器、磁盤(pán)存儲(chǔ)器和虛擬存儲(chǔ)器都劃分成固定大小的頁(yè)，主存儲(chǔ)器的頁(yè)稱(chēng)為實(shí)頁(yè)，虛擬存儲(chǔ)器中的頁(yè)稱(chēng)為虛頁(yè)。 一個(gè)主存地址A由兩部分組成，實(shí)頁(yè)號(hào)p和頁(yè)內(nèi)偏移d 一個(gè)虛地址Av由三部分組成，用戶(hù)號(hào)U、虛頁(yè)號(hào)P和頁(yè)內(nèi)偏移D。用戶(hù)號(hào)U虛頁(yè)號(hào)P頁(yè)內(nèi)偏移D多用戶(hù)虛擬地址Av的組成實(shí)頁(yè)號(hào)p頁(yè)內(nèi)偏移d主存地址A的組成 內(nèi)部地址變換：內(nèi)部地址變換： 多用戶(hù)虛擬地址多用戶(hù)虛擬地址AvAv變換成主存實(shí)地址變換成主存實(shí)地址A A 多用戶(hù)虛擬地址中的頁(yè)內(nèi)偏移多用戶(hù)虛擬地址中的頁(yè)內(nèi)偏移D D直接作為直接作為主存實(shí)地

14、址中的頁(yè)內(nèi)偏移主存實(shí)地址中的頁(yè)內(nèi)偏移d d 主存實(shí)頁(yè)號(hào)主存實(shí)頁(yè)號(hào)p p與它的頁(yè)內(nèi)偏移與它的頁(yè)內(nèi)偏移d d直接拼接直接拼接起來(lái)就得到主存實(shí)地址起來(lái)就得到主存實(shí)地址A A 外部地址變換：外部地址變換： 首先查外頁(yè)表得到磁盤(pán)存儲(chǔ)器實(shí)地址首先查外頁(yè)表得到磁盤(pán)存儲(chǔ)器實(shí)地址 把磁盤(pán)存儲(chǔ)器實(shí)地址和主存儲(chǔ)器實(shí)頁(yè)號(hào)送把磁盤(pán)存儲(chǔ)器實(shí)地址和主存儲(chǔ)器實(shí)頁(yè)號(hào)送入輸入入輸入/輸出處理機(jī)輸出處理機(jī) 把要訪(fǎng)問(wèn)數(shù)據(jù)所在的一整頁(yè)都從磁盤(pán)存儲(chǔ)把要訪(fǎng)問(wèn)數(shù)據(jù)所在的一整頁(yè)都從磁盤(pán)存儲(chǔ)器調(diào)入到主存儲(chǔ)器器調(diào)入到主存儲(chǔ)器地址的映象與變換地址的映象與變換 三種地址空間：三種地址空間：虛擬地址空間，主存儲(chǔ)虛擬地址空間，主存儲(chǔ)器地址空間，輔存地址空

15、間器地址空間，輔存地址空間 地址映象：地址映象：把虛擬地址空間映象到主存地址空間把虛擬地址空間映象到主存地址空間 地址變換：地址變換：在程序運(yùn)行時(shí)，把虛地址變?cè)诔绦蜻\(yùn)行時(shí)，把虛地址變換成主存實(shí)地址換成主存實(shí)地址 因地址映象和變換方法不同，有因地址映象和變換方法不同，有三種虛三種虛擬存儲(chǔ)器擬存儲(chǔ)器：頁(yè)式虛擬存儲(chǔ)器、段式虛擬頁(yè)式虛擬存儲(chǔ)器、段式虛擬存儲(chǔ)器、段頁(yè)式虛擬存儲(chǔ)器存儲(chǔ)器、段頁(yè)式虛擬存儲(chǔ)器1 1、段式虛擬存儲(chǔ)器、段式虛擬存儲(chǔ)器 地址映象方法：地址映象方法：每個(gè)程序段都從每個(gè)程序段都從0 0地址地址開(kāi)始編址，長(zhǎng)度可長(zhǎng)可短，可以在程序開(kāi)始編址，長(zhǎng)度可長(zhǎng)可短，可以在程序執(zhí)行過(guò)程中動(dòng)態(tài)改變程序段的長(zhǎng)

16、度。執(zhí)行過(guò)程中動(dòng)態(tài)改變程序段的長(zhǎng)度。0段1k1段2段3段0500020002000段號(hào) 段長(zhǎng) 起址01k8k1500 16k22009k3200 30k08k9k16k30k程序空間主存儲(chǔ)器主程序主程序 地址變換方法：地址變換方法：由用戶(hù)號(hào)找到基址寄存器由用戶(hù)號(hào)找到基址寄存器從基址寄存器中讀出段表的起始地址從基址寄存器中讀出段表的起始地址把起始地址與多用戶(hù)虛地址中段號(hào)相加得把起始地址與多用戶(hù)虛地址中段號(hào)相加得到段表地址到段表地址把段表中給出的起始地址與段內(nèi)偏移把段表中給出的起始地址與段內(nèi)偏移D D相相加就能得到主存實(shí)地址加就能得到主存實(shí)地址0段表長(zhǎng)度段表基址6As段名起始地址裝入位段長(zhǎng)訪(fǎng)問(wèn)方式

17、用戶(hù)號(hào)U 段號(hào)S段內(nèi)偏移D多用戶(hù)虛地址主存實(shí)地址432101n-1As段表基址寄存器一個(gè)用戶(hù)（一道作業(yè)）的段表段式虛擬存儲(chǔ)器的主要優(yōu)點(diǎn)：段式虛擬存儲(chǔ)器的主要優(yōu)點(diǎn)：(1) (1) 程序的模塊化性能好程序的模塊化性能好(2) (2) 便于程序和數(shù)據(jù)的共享便于程序和數(shù)據(jù)的共享(3) (3) 程序的動(dòng)態(tài)鏈接和調(diào)度比較容易程序的動(dòng)態(tài)鏈接和調(diào)度比較容易(4) (4) 便于實(shí)現(xiàn)信息保護(hù)便于實(shí)現(xiàn)信息保護(hù)段式虛擬存儲(chǔ)器的主要缺點(diǎn)：段式虛擬存儲(chǔ)器的主要缺點(diǎn)：(1) (1) 地址變換所花費(fèi)的時(shí)間比較長(zhǎng)，需地址變換所花費(fèi)的時(shí)間比較長(zhǎng)，需 要做兩次加法運(yùn)算要做兩次加法運(yùn)算(2) (2) 主存儲(chǔ)器的利用率往往比較低主存儲(chǔ)

18、器的利用率往往比較低(3) (3) 對(duì)輔存（磁盤(pán)存儲(chǔ)器）的管理比較對(duì)輔存（磁盤(pán)存儲(chǔ)器）的管理比較 困難困難2 2、頁(yè)式虛擬存儲(chǔ)器、頁(yè)式虛擬存儲(chǔ)器 頁(yè)式虛擬存儲(chǔ)器頁(yè)式虛擬存儲(chǔ)器把虛擬地址空間劃分成一個(gè)個(gè)把虛擬地址空間劃分成一個(gè)個(gè)固定大小的塊固定大小的塊, ,每塊稱(chēng)為每塊稱(chēng)為一頁(yè)一頁(yè), ,把主存儲(chǔ)器的地把主存儲(chǔ)器的地址空間也按虛擬地址空間同樣的大小劃分為頁(yè)。址空間也按虛擬地址空間同樣的大小劃分為頁(yè)。 頁(yè)是一種邏輯上的劃分，它可以由系統(tǒng)軟件任意指頁(yè)是一種邏輯上的劃分，它可以由系統(tǒng)軟件任意指定。定。 虛擬地址空間中的頁(yè)稱(chēng)為虛頁(yè)，主存地址空間中虛擬地址空間中的頁(yè)稱(chēng)為虛頁(yè)，主存地址空間中的頁(yè)稱(chēng)為實(shí)頁(yè)。的頁(yè)

19、稱(chēng)為實(shí)頁(yè)。 每個(gè)用戶(hù)使用一個(gè)每個(gè)用戶(hù)使用一個(gè)基址寄存器基址寄存器（在（在CPUCPU內(nèi)），通內(nèi)），通過(guò)用戶(hù)號(hào)過(guò)用戶(hù)號(hào)U U可以直接找到與這個(gè)用戶(hù)程序相對(duì)應(yīng)可以直接找到與這個(gè)用戶(hù)程序相對(duì)應(yīng)的的基址寄存器基址寄存器，從這個(gè)基址寄存器中讀出頁(yè)表，從這個(gè)基址寄存器中讀出頁(yè)表起始地址。訪(fǎng)問(wèn)這個(gè)頁(yè)表地址，把得到的主存起始地址。訪(fǎng)問(wèn)這個(gè)頁(yè)表地址，把得到的主存頁(yè)號(hào)頁(yè)號(hào)p p與虛地址中的頁(yè)內(nèi)偏移直接拼接起來(lái)得到與虛地址中的頁(yè)內(nèi)偏移直接拼接起來(lái)得到主存實(shí)地址。主存實(shí)地址。 如圖所示：如圖所示：0頁(yè)1頁(yè)2頁(yè)3頁(yè)頁(yè)號(hào) 主存頁(yè)號(hào)0123用戶(hù)程序主存儲(chǔ)器頁(yè)表頁(yè)式虛擬存儲(chǔ)器的地址映象Pa裝入 修改 主存頁(yè)號(hào) 標(biāo)志用戶(hù)號(hào)U虛

20、頁(yè)號(hào)P頁(yè)內(nèi)偏移D頁(yè)內(nèi)偏移d2pPa頁(yè)表基址頁(yè)表實(shí)頁(yè)號(hào)p 主要優(yōu)點(diǎn)：主要優(yōu)點(diǎn)：(1) (1) 主存儲(chǔ)器的利用率比較高主存儲(chǔ)器的利用率比較高(2) (2) 頁(yè)表相對(duì)比較簡(jiǎn)單頁(yè)表相對(duì)比較簡(jiǎn)單(3) (3) 地址變換的速度比較快地址變換的速度比較快(4) (4) 對(duì)磁盤(pán)的管理比較容易對(duì)磁盤(pán)的管理比較容易 主要缺點(diǎn)：主要缺點(diǎn)：(1) (1) 程序的模塊化性能不好程序的模塊化性能不好(2) (2) 頁(yè)表很長(zhǎng)，需要占用很大的存頁(yè)表很長(zhǎng)，需要占用很大的存儲(chǔ)空間。例如：虛擬存儲(chǔ)空間儲(chǔ)空間。例如：虛擬存儲(chǔ)空間4GB4GB，頁(yè)大小頁(yè)大小1KB1KB，則頁(yè)表的容量為，則頁(yè)表的容量為4M4M字，字，16MB16MB3

21、3、段頁(yè)式虛擬存儲(chǔ)器、段頁(yè)式虛擬存儲(chǔ)器 用戶(hù)按照程序段來(lái)編寫(xiě)程序，每個(gè)程序用戶(hù)按照程序段來(lái)編寫(xiě)程序，每個(gè)程序段分成幾個(gè)固定大小的頁(yè)。段分成幾個(gè)固定大小的頁(yè)。 地址變換方法：地址變換方法：(1) (1) 先查段表，得到該程序段的頁(yè)表起先查段表，得到該程序段的頁(yè)表起 始地址和頁(yè)表長(zhǎng)度始地址和頁(yè)表長(zhǎng)度(2) (2) 再查頁(yè)表找到要訪(fǎng)問(wèn)的主存實(shí)頁(yè)號(hào)再查頁(yè)表找到要訪(fǎng)問(wèn)的主存實(shí)頁(yè)號(hào)(3) (3) 最后把實(shí)頁(yè)號(hào)最后把實(shí)頁(yè)號(hào)p p與頁(yè)內(nèi)偏移與頁(yè)內(nèi)偏移d d拼接得拼接得 到主存的實(shí)地址到主存的實(shí)地址裝入修改實(shí)頁(yè)號(hào)標(biāo)志用戶(hù)號(hào)U 段號(hào)S頁(yè)內(nèi)偏移頁(yè)內(nèi)偏移0/11pA實(shí)頁(yè)號(hào)p虛頁(yè)號(hào)PAs裝入1修改0/1頁(yè)表地址ApAs

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

23、換，一般用軟件實(shí)現(xiàn)一般用軟件實(shí)現(xiàn)(2) Cache(2) Cache塊替換一般用硬件實(shí)現(xiàn)塊替換一般用硬件實(shí)現(xiàn)(3) (3) 虛擬存儲(chǔ)器的快慢表中，快表存儲(chǔ)虛擬存儲(chǔ)器的快慢表中，快表存儲(chǔ)字的替換，用硬件實(shí)現(xiàn)字的替換，用硬件實(shí)現(xiàn)(4) (4) 虛擬存儲(chǔ)器中，用戶(hù)基地址寄存器虛擬存儲(chǔ)器中，用戶(hù)基地址寄存器的替換，用硬件實(shí)現(xiàn)的替換，用硬件實(shí)現(xiàn)(5) (5) 在有些虛擬存儲(chǔ)器中目錄表的替換在有些虛擬存儲(chǔ)器中目錄表的替換1 1、頁(yè)面替換算法、頁(yè)面替換算法隨機(jī)算法隨機(jī)算法算法簡(jiǎn)單，容易實(shí)現(xiàn)；沒(méi)有利用歷史信息，沒(méi)有反映程序的局部性，命中率低。(2) 先進(jìn)先出算法 (FIFO)比較容易實(shí)現(xiàn)，利用了歷史信息，沒(méi)有

24、反映程序的局部性。最先調(diào)入主存的頁(yè)面，很可能也是經(jīng)常要使用的頁(yè)面。(3) 近期最少使用算法 (LFU)既充分利用了歷史信息，又反映了程序的局部性(1) 實(shí)現(xiàn)起來(lái)非常困難。(4)最近最少使用算法 (LRU) 把LRU算法中的“多”與“少”簡(jiǎn)化成“有”與“無(wú)” 實(shí)現(xiàn)起來(lái)比較容易。(5)最優(yōu)替換算法 (OPT) 一種理想化的算法。 用來(lái)作為評(píng)價(jià)其它頁(yè)面替換算法好壞的標(biāo)準(zhǔn)。 在虛擬存儲(chǔ)器中，實(shí)際上有可能采用只有在虛擬存儲(chǔ)器中，實(shí)際上有可能采用只有FIFOFIFO和和LRULRU兩種算法。兩種算法。例2：一個(gè)程序共有5個(gè)頁(yè)面組成，程序執(zhí)行過(guò)程中的頁(yè)地址流如下： P1, P2, P1, P5, P5, P

25、1, P3, P4, P3, P4 假設(shè)分配給這個(gè)程序的主存儲(chǔ)器共有3個(gè)頁(yè)面。給出FIFO、LRU、OPT 三種頁(yè)面替換算法對(duì)這3頁(yè)主存的使用情況，包括調(diào)入、替換和命中等。例3：一個(gè)循環(huán)程序，依次使用P1，P2，P3，P4四個(gè)頁(yè)面，分配給這個(gè)程序的主存頁(yè)面數(shù)為3個(gè)。FIFO、LRU和OPT三種頁(yè)面替換算法對(duì)主存頁(yè)面的調(diào)度情況如下圖所示。在FIFO和LRU算法中，總是發(fā)生下次就要使用的頁(yè)面本次被替換出去的情況，這就是“顛簸”現(xiàn)象。練習(xí)P169 習(xí)題4.15提高主存命中率的方法影響主存命中率的主要因素：影響主存命中率的主要因素：(1) (1) 程序執(zhí)行過(guò)程中的頁(yè)地址流分布情況程序執(zhí)行過(guò)程中的頁(yè)地址

26、流分布情況(2) (2) 所采用的頁(yè)面替換算法所采用的頁(yè)面替換算法(3) (3) 頁(yè)面大小頁(yè)面大小(4) (4) 主存儲(chǔ)器的容量主存儲(chǔ)器的容量(5) (5) 所采用的頁(yè)面調(diào)度算法所采用的頁(yè)面調(diào)度算法 以下，對(duì)后三個(gè)因素進(jìn)行分析以下，對(duì)后三個(gè)因素進(jìn)行分析1、頁(yè)面大小與命中率的關(guān)系、頁(yè)面大小與命中率的關(guān)系 頁(yè)面大小為某個(gè)值時(shí)，命中率達(dá)到最大。頁(yè)面大小為某個(gè)值時(shí)，命中率達(dá)到最大。 頁(yè)面大小與命中率關(guān)系的解釋?zhuān)喉?yè)面大小與命中率關(guān)系的解釋?zhuān)杭僭O(shè)假設(shè)A At t和和A At+1t+1是相鄰兩次訪(fǎng)問(wèn)主存的邏輯是相鄰兩次訪(fǎng)問(wèn)主存的邏輯地址，地址，d dA At tA At+1t+1。如果如果S Sp p(S(

27、Sp p為頁(yè)面大小為頁(yè)面大小) )，隨著，隨著S Sp p的增的增大，大，A At t和和A At+1t+1在同一頁(yè)面的可能性增加，即在同一頁(yè)面的可能性增加，即（命中率）隨著（命中率）隨著S Sp p的增大而提高。的增大而提高。如果如果S Sp p，A At t和和A At+1t+1一定不在同一個(gè)頁(yè)一定不在同一個(gè)頁(yè)面內(nèi)。隨著面內(nèi)。隨著S Sp p的增大，主存頁(yè)面數(shù)減少，的增大，主存頁(yè)面數(shù)減少，頁(yè)面替換將更加頻繁。隨著頁(yè)面替換將更加頻繁。隨著S Sp p的增大而的增大而降低。降低。 當(dāng)Sp比較小的時(shí)候，前一種情況是主要的，隨著Sp的增大而提高 當(dāng)Sp達(dá)到某一個(gè)最大值之后，后一種情況成為主要的，隨

28、著Sp的增大而降低 當(dāng)頁(yè)面大小增大時(shí)，造成的浪費(fèi)也要增加 當(dāng)頁(yè)面大小減小時(shí)，頁(yè)表和頁(yè)面表在主存儲(chǔ)器中所占的比例將增加。頁(yè)面大小 SP命中率 H1S2S2、主存容量與命中率的關(guān)系、主存容量與命中率的關(guān)系 主存命中率H隨著分配給該程序的主存容量S的增加而單調(diào)上升。 在S比較小的時(shí)候，H提高得非?？臁ｋS著S的逐漸增加，H提高的速度逐漸降低。當(dāng)S增加到某一個(gè)值之后，H幾乎不再提高。命中率 H主存容量S1.03、頁(yè)面調(diào)度方式與命中率的關(guān)系、頁(yè)面調(diào)度方式與命中率的關(guān)系 請(qǐng)求式：請(qǐng)求式：當(dāng)使用到的時(shí)候，再調(diào)入主存當(dāng)使用到的時(shí)候，再調(diào)入主存 預(yù)取式：預(yù)取式： 在程序重新開(kāi)始運(yùn)行之前，把上次程序在程序重新開(kāi)始運(yùn)

29、行之前，把上次程序停止運(yùn)行前一段時(shí)間內(nèi)用到的頁(yè)面先調(diào)停止運(yùn)行前一段時(shí)間內(nèi)用到的頁(yè)面先調(diào)入到主存儲(chǔ)器，然后再開(kāi)始運(yùn)行程序入到主存儲(chǔ)器，然后再開(kāi)始運(yùn)行程序 可以避免在程序開(kāi)始運(yùn)行時(shí)，頻繁發(fā)生可以避免在程序開(kāi)始運(yùn)行時(shí)，頻繁發(fā)生頁(yè)面失效的情況頁(yè)面失效的情況 如果調(diào)入的頁(yè)面用不上，則即浪費(fèi)了調(diào)如果調(diào)入的頁(yè)面用不上，則即浪費(fèi)了調(diào)入的時(shí)間，又占用了主存資源。入的時(shí)間，又占用了主存資源。5.4.2 共享存儲(chǔ)和分布存儲(chǔ)MIMD系統(tǒng)可以分為兩種：(1)tightly coupled shared-Memory multiprocessors(2)loosely coupled distributed-Memory

30、 multiprocessors它們可以用圖表示如下：P1P2PnICNSM1SMmshare-MemorymultiprocessorsPICNdistribued-MemorymultiprocessorsLMPLMPLM共享存儲(chǔ)和分布存儲(chǔ)的優(yōu)缺點(diǎn)：共享存儲(chǔ)器： 易于編程，是單機(jī)的自然延伸 程序員無(wú)數(shù)據(jù)劃分的負(fù)擔(dān) 多進(jìn)程并發(fā)的開(kāi)銷(xiāo)小，效率高，易于進(jìn)程遷移，任務(wù)動(dòng)態(tài)分配簡(jiǎn)單 由于每個(gè)處理器都通過(guò)總線(xiàn)訪(fǎng)問(wèn)存儲(chǔ)器，因而限制了處理器的個(gè)數(shù)，可擴(kuò)展性差。分布存儲(chǔ)器：系統(tǒng)結(jié)構(gòu)靈活，可擴(kuò)展性好 處理機(jī)數(shù)目可達(dá)成百上千，處理速度有巨大的發(fā)展?jié)摿?算法設(shè)計(jì)、編程以及任務(wù)動(dòng)態(tài)分配比較困難 很難在處理機(jī)之間傳遞

31、復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，難于進(jìn)程遷移 不能支持需要存儲(chǔ)空間的大規(guī)模數(shù)據(jù)處理要求。分布存儲(chǔ)的兩種編程方法：（1）message-passing，用send，receive原語(yǔ)實(shí)現(xiàn)通信，要求程序員在進(jìn)程的整個(gè)運(yùn)行期間對(duì)數(shù)據(jù)的移動(dòng)都很清楚；（2）remote procedure call，語(yǔ)言一級(jí)傳送控制與數(shù)據(jù)，可以看作是本地調(diào)用，但透明度有限。缺點(diǎn)： 這兩種方法都是用來(lái)解決不同地址空間的問(wèn)題，在節(jié)點(diǎn)間傳遞復(fù)雜數(shù)據(jù)結(jié)構(gòu)時(shí)都比較困難，需要打包，傳遞指針也不可能實(shí)現(xiàn)。 由于個(gè)處理機(jī)擁有不同的地址空間，使得進(jìn)程遷移時(shí)，該進(jìn)程所分配到的操作系統(tǒng)資源也得一起移動(dòng)（打開(kāi)的文件、文件存取控制塊等），這很費(fèi)時(shí)間。5.4.3

32、 DSM與SVM1.DSM和SVM的提出 如何把共享和分布的優(yōu)點(diǎn)結(jié)合起來(lái)，取長(zhǎng)補(bǔ)短？共享分布存儲(chǔ)器（Distributed Shared Memory，DSM）虛擬共享存儲(chǔ)器（Shared Virtual Memory，SVM）基于分布存儲(chǔ)器的多處理機(jī)上，實(shí)現(xiàn)物理上分布、但邏輯上共享的存儲(chǔ)器系統(tǒng)。虛擬共享存儲(chǔ)器的邏輯結(jié)構(gòu)：CPU1虛擬共享存儲(chǔ)器LM1CPU2LM2CPUnLMn地址映射部件地址映射部件地址映射部件MIMD機(jī)器存儲(chǔ)系統(tǒng)的發(fā)展方向：共享存儲(chǔ)器分布存儲(chǔ)器共享分布存儲(chǔ)器2.DSM系統(tǒng)的特點(diǎn) 在DSM系統(tǒng)中，每一臺(tái)處理機(jī)都可以訪(fǎng)問(wèn)全局存儲(chǔ)器的任一位置，用戶(hù)可以把它當(dāng)成全局共享存儲(chǔ)器系統(tǒng)。

33、 優(yōu)點(diǎn)：編程容易系統(tǒng)結(jié)構(gòu)靈活可擴(kuò)展性好系統(tǒng)價(jià)格低有較好的軟件移植性 DSM系統(tǒng)編制的程序比用消息傳遞方式編制的程序效率高：（1）在DSM系統(tǒng)中，數(shù)據(jù)都是以塊的方式進(jìn)行傳送，如果一個(gè)程序具有較高的局部性，則當(dāng)把一個(gè)數(shù)據(jù)塊傳送到一個(gè)節(jié)點(diǎn)后，該節(jié)點(diǎn)對(duì)它的訪(fǎng)問(wèn)就成為本地訪(fǎng)問(wèn)，而消息傳遞方式的每次訪(fǎng)問(wèn)都需要通訊。（2）許多并行應(yīng)用程序都是分階段執(zhí)行的，每次執(zhí)行前，都有一個(gè)數(shù)據(jù)交換階段，其時(shí)間受通訊限制。在DSM系統(tǒng)中，數(shù)據(jù)只有用到的時(shí)候才傳送，取消了數(shù)據(jù)交換階段，把通訊時(shí)間加以分散，提高了并行性。（3）DSM提供的虛存空間比單個(gè)節(jié)點(diǎn)的存儲(chǔ)空間大得多，減少了換頁(yè)操作。3.實(shí)現(xiàn)DSM的途徑主要有三種：（1）

34、硬件實(shí)現(xiàn)：將傳統(tǒng)的cache技術(shù)擴(kuò)展應(yīng)用到松耦合分布式存儲(chǔ)多處理機(jī)。要增加專(zhuān)用部件以取得高效的實(shí)現(xiàn)。（2）操作系統(tǒng)和庫(kù)實(shí)現(xiàn)：利用虛擬存儲(chǔ)管理機(jī)制取得共享（sharing）和一致（coherence）（3）編譯實(shí)現(xiàn)：自動(dòng)將共享訪(fǎng)問(wèn)轉(zhuǎn)換成同步和一致原語(yǔ)。用戶(hù)需要顯式控制全局?jǐn)?shù)據(jù)，當(dāng)傳遞大量數(shù)據(jù)時(shí)或試圖進(jìn)行進(jìn)程遷移時(shí)極其復(fù)雜。4.主要技術(shù)結(jié)構(gòu)（structure）：指共享數(shù)據(jù)在存儲(chǔ)器中的框架（如對(duì)象和語(yǔ)言的類(lèi)型）粒度（granularity）：指基本共享單位長(zhǎng)度（如字節(jié)、字、頁(yè)或復(fù)雜數(shù)據(jù)結(jié)構(gòu)）。數(shù)據(jù)訪(fǎng)問(wèn)與一致性（access and cosistency）一致性語(yǔ)義（coherence semant

35、ics）可擴(kuò)展性（scalability）異構(gòu)性（heterogeneity）第五章 并行存儲(chǔ)器系統(tǒng)5.1 存儲(chǔ)器系統(tǒng)的層次結(jié)構(gòu)5.2 包含性、一致性和局部性5.3 存儲(chǔ)器容量的規(guī)劃5.4 虛擬存儲(chǔ)器技術(shù)5.5 交叉訪(fǎng)問(wèn)的存儲(chǔ)器5.5.1 兩種組織方式5.5.2 兩種方式的比較5.3.3 帶寬和容錯(cuò)5.5 交叉訪(fǎng)問(wèn)的存儲(chǔ)器利用存儲(chǔ)器交叉存取技術(shù)可以對(duì)存儲(chǔ)器相鄰單元進(jìn)行流水線(xiàn)訪(fǎng)問(wèn)，因而能獲得更寬的帶寬。主存儲(chǔ)器由多個(gè)模塊構(gòu)成。假設(shè)主存儲(chǔ)器包含m=2a個(gè)存儲(chǔ)器模塊，每個(gè)模塊包含w=2b個(gè)存儲(chǔ)單元（字），則總存儲(chǔ)容量為個(gè)字bawm25.5.1 兩種組織方式交叉訪(fǎng)問(wèn)的存儲(chǔ)器可以分為兩種：(1)低位交叉方式(2)高位交叉方式1.低位交叉方式 低位交叉存取將鄰接的存儲(chǔ)單元沿橫向放在m個(gè)模塊中，存儲(chǔ)器地址的低a位用來(lái)指明存儲(chǔ)器模塊，高b位是每個(gè)模塊內(nèi)的字地址。 同一個(gè)字的地址同時(shí)送給所有的存儲(chǔ)模塊，模塊地址譯碼用來(lái)區(qū)分模塊地址。低位m路交叉存取如下圖：MAB0mm(w-1)MDBM0MAB1m+1m(w-1)+1MDBM1MABm-12m-1mw-1MDBMm-1WAB字模塊地址ab數(shù)據(jù)總線(xiàn)存儲(chǔ)器數(shù)據(jù)緩沖器模塊地址緩沖器字地址緩沖器2.高