計算機系統(tǒng)組成與結(jié)構PPT第9章ppt課件

1、第9章 存儲器結(jié)構,9.1 存儲器的層次結(jié)構 9.2 Cache存儲器 *9.3 虛擬存儲器 *9.4 基本Cache和虛擬存儲器的擴展 *9.5 實例：Pentium/Windows個人計算機 上的內(nèi)存管理,計算機組成與結(jié)構,1,湖南大學計算機與通信學院,9.1 存儲器的層次結(jié)構,圖9.1 一般的存儲器層次,物理內(nèi)存：由動態(tài)RAM組成。 Cache存儲器：由靜態(tài)RAM構成，比DRAM快得多，但也 昂貴的多。Cache是物理內(nèi)存的部分副本。 虛擬存儲器：空間比物理內(nèi)存大得多邏輯空間。虛擬管理器 通過在物理內(nèi)存和一個存儲介質(zhì)之間調(diào)度來達 到訪問的目的。,計算機組成與結(jié)構,2,湖南大學計算機與通信

2、學院,哈佛結(jié)構： 計算機存儲系統(tǒng)的Cache層次中，每一級Cache包含兩個單獨的Cache存儲器，其中 一個是指令Cache，一個是數(shù)據(jù)Cache。,9.2 Cache存儲器,大部分計算機在CPU和物理內(nèi)存之間包含一個較小容量的Cache存儲器，而不是使用Cache存儲器構建計算機的整個存儲系統(tǒng)。目標是在合理的價格下減少處理器的內(nèi)存訪問時間。,計算機組成與結(jié)構,3,湖南大學計算機與通信學院,9.2.1 相聯(lián)存儲器,一般存儲器：接收一個地址，訪問該地址中的 數(shù)據(jù)。 相聯(lián)存儲器：并行搜索所有單元，標記那些與 特定數(shù)據(jù) 匹配的單元，然后連續(xù) 讀出匹配的數(shù)據(jù)值。,計算機組成與結(jié)構,4,湖南大學計算機

3、與通信學院,考慮一個由8個字單元組成的簡單的相聯(lián)存儲器，每個單元有16 位，如圖9.2所示。 除數(shù)據(jù)位外，每單元都有一個額外的標記位V。（數(shù)據(jù)有效位，為1說明這個單元數(shù)據(jù)有效，為0說明數(shù)據(jù)無效 ）,圖9.2 相聯(lián)存儲器的內(nèi)部組織結(jié)構,計算機組成與結(jié)構,5,湖南大學計算機與通信學院,為了從相聯(lián)存儲器中讀出一個值，CPU必 須給出兩個值，即要被匹配的數(shù)據(jù)值、以 及哪些位需要檢查。第一個值是參數(shù)或數(shù) 據(jù)，第二個值是屏蔽位或關鍵位 如果滿足如下的公式，則匹配就會發(fā)生,計算機組成與結(jié)構,6,湖南大學計算機與通信學院,屏蔽寄存器中值為1的每一位，單元中的值與數(shù)據(jù)寄存器中的值都相同 單元的有效位被設置為1；

4、 例如(參考圖9.2)： 屏蔽寄存器K 1111 0000 0000 0000 數(shù)據(jù)寄存器D 1010 XXXX XXXX XXXX 數(shù) 據(jù) 位M 1010 1101 0000 0111 執(zhí)行 0000 XXXX XXXX XXXX 執(zhí)行 1111 XXXX XXXX XXXX 執(zhí)行 1111 1111 1111 1111,計算機組成與結(jié)構,7,湖南大學計算機與通信學院,將數(shù)據(jù)寫回相聯(lián)存儲器,CPU把數(shù)據(jù)送到數(shù)據(jù)寄存器并發(fā)出寫信號。相聯(lián)存儲器檢查所有單元的有效位，并找到有效位為0的一個單元，如果找到，把數(shù)據(jù)存到這個單元，同時將有效位設為1。如果沒有找到，必須采用替換算法清除一個單元來保存數(shù)據(jù)。

5、,常見的替換算法 FIFO LRU RANDOM,計算機組成與結(jié)構,8,湖南大學計算機與通信學院,Cache地址,字塊0,字塊1,字塊C-1,0,1,主存地址,M塊,B個字節(jié),主存和Cache的基本結(jié)構,標簽,標簽,標簽,C塊,B個字節(jié),計算機組成與結(jié)構,9,湖南大學計算機與通信學院,下面以主存=16塊，Cache=8塊，塊大小=16個存儲字節(jié)為例說明幾種常用映像方式：,Cache標簽需記下主存塊號 （主存地址高4位）,計算機組成與結(jié)構,10,湖南大學計算機與通信學院,(2)直接相聯(lián)：主存中的一塊只能映像到Cache中某一特定塊,Cache標簽只需記下主存區(qū)號 （主存地址高1位）,區(qū)號a,區(qū)內(nèi)

6、 塊號b,塊內(nèi)地址w,3位,4位,1位,計算機組成與結(jié)構,11,湖南大學計算機與通信學院,(3)N路組相聯(lián)：全相聯(lián)和直接相聯(lián)的結(jié)合。,b0,b1,b2,b3,b4,b5,b6,b7,B0,B1,B2,B3,B4,B5,B6,B7,B8,B9,B30,B31,組0,組1,組2,組3,組0,組1,組2,組3,組0,組3,區(qū)0,區(qū)1,區(qū)3,設組大小=2塊,Cache,主存地址,塊號B,塊內(nèi)地址W,4位,Cache地址,組內(nèi) 塊號b,塊內(nèi)地址w,1位,4位,4位,組號g,2位,Cache標簽需記下主存段號 （主存地址高2位）,段號s,段內(nèi) 塊號b,塊內(nèi)地址w,2位,4位,2位,計算機組成與結(jié)構,12,

7、湖南大學計算機與通信學院,9.2.2 相聯(lián)映象的Cache存儲器,64K的8位內(nèi)存,圖 9.3 相對簡單CPU的相聯(lián)Cache,計算機組成與結(jié)構,13,湖南大學計算機與通信學院,作用于數(shù)據(jù)行或數(shù)據(jù)塊的相聯(lián)存儲器 存儲器在每個單元存儲4個字節(jié)的數(shù)據(jù)。（如圖9.4） 同一個單元的4個數(shù)據(jù)具有相同的高位地址，即高14位相同。 比圖9.3中的相聯(lián)存儲器采用了更多的位數(shù) （46位 vs 24位）,但更少的存儲單元。,計算機組成與結(jié)構,14,湖南大學計算機與通信學院,圖 9.4 相對簡單CPU中，行大小 為4字節(jié)的相聯(lián)Cache,計算機組成與結(jié)構,15,湖南大學計算機與通信學院,優(yōu)點： 利用了訪問的局部性

8、原理：當內(nèi)存單元X中的指令被訪問時，下一條被執(zhí)行的指令非常有可能就在內(nèi)存單元X+1中。 例如： 當訪問地址0單元的時候，整個塊（0，1，2，3）的值都被從物理內(nèi)存讀入CPU。 當CPU下次要執(zhí)行在內(nèi)存單元1、2、3中的指令時，他們已在cache中即能被訪問而不必從較慢的物理內(nèi)存中讀取。,計算機組成與結(jié)構,16,湖南大學計算機與通信學院,不僅指令具有訪問的局部性，數(shù)據(jù)同樣也具有 訪問的局部性 如編譯器通常將一列數(shù)組元素安排到相鄰的內(nèi) 存單元中，以方便處理器順序訪問數(shù)據(jù)值。,計算機組成與結(jié)構,17,湖南大學計算機與通信學院,9.2.3 直接映象的Cache存儲器,一種利用標準的SRAM、廉價的Ca

9、che映射方案,xxxx xx11 1111 1111,11 1111 1111,計算機組成與結(jié)構,18,湖南大學計算機與通信學院,索引原始地址的低十位，用來選擇Cache 的一個特定單元 標簽原始地址中不是索引的那些高位。 直接映象的Cache存儲器一個單元包括（圖9.5)： 標簽 數(shù)據(jù) 有效值,計算機組成與結(jié)構,19,湖南大學計算機與通信學院,圖9.5 相對簡單CPU的直接映象Cache,計算機組成與結(jié)構,20,湖南大學計算機與通信學院,采用數(shù)據(jù)行的直接映像Cache存儲器,圖9.6 相對簡單的CPU中，行大小為4字節(jié)的直接映像Cache,計算機組成與結(jié)構,21,湖南大學計算機與通信學院,

10、直接映像的Cache存儲器 優(yōu)點： 價格低 容量大 缺點： 靈活性差 如前所述，物理內(nèi)存中任何形式為xxxx xx11 1111 1111的地址都只能映射到Cache中地址為11 1111 1111的單元中。,計算機組成與結(jié)構,22,湖南大學計算機與通信學院,JUMP 1000H,JUMP 0000H,JUMP 0000H,JUMP 1000H,考慮下面的代碼： 0000 0000 0000 0000（0000H）:JUMP 1000H 0001 0000 0000 0000（1000H）:JUMP 0000H,直接映象Cache,地址00 0000 0000,JUMP 0000H,JUMP

11、1000H,計算機組成與結(jié)構,23,湖南大學計算機與通信學院,9.2.4 組相聯(lián)映像的cache存儲器,特點 靈活性增強 減少由直接映像帶來的覆蓋數(shù)據(jù)的問題 采用比較便宜的SRAM,N路組相聯(lián)：每個單元能夠包含N個字節(jié)或字 直接映像的cache可以看作是一個一路 組相聯(lián)映像cache存儲器,計算機組成與結(jié)構,24,湖南大學計算機與通信學院,考察大小為1k的2路組相聯(lián)cache（如圖9.7）,該cache有1k個數(shù)據(jù)入口，每個單元2個數(shù)據(jù)值，因此有512個單元 用9個地址位選擇cache單元，剩下的7位說明標簽值 計數(shù)值用來紀錄數(shù)據(jù)什么時候被訪問過了,圖9.7 相對簡單CPU的2路組相聯(lián)cach

12、e,計算機組成與結(jié)構,25,湖南大學計算機與通信學院,JUMP 1000H,JUMP 0000H,JUMP 0000H,JUMP 1000H,重新考慮下面的代碼： 0000 0000 0000 0000（0000H）:JUMP 1000H 0001 0000 0000 0000（1000H）:JUMP 0000H,組相聯(lián)映象cache,同一組,計算機組成與結(jié)構,26,湖南大學計算機與通信學院,一種采用數(shù)據(jù)行的組相聯(lián)cache,圖9.8 相對簡單CPU中 具有4字節(jié)數(shù)據(jù)行的2 路組相聯(lián)cache,計算機組成與結(jié)構,27,湖南大學計算機與通信學院,第9章 習題5：,一個使用相對簡單CPU的計算機系

13、統(tǒng)，要包含一個1K大小、行大小為2字節(jié)的相聯(lián)Cache： a) Cache中的每一單元有多少位？ b) 相聯(lián)存儲器需要什么mask值？,解： a) Cache每一單元共32位，構成如下：,b) Mask Resister7FFF0000H,計算機組成與結(jié)構,28,湖南大學計算機與通信學院,第9章 習題6：,對于第5題所示的計算機系統(tǒng)，給出執(zhí)行每一如下指令后的Cache中的內(nèi)容（所有值均以16進制給出）： 0:LDAC4234 3:CLAC 4:JMPZ000A 7:JUMP0000 A:INAC B:MVAC C:ADD D:STAC0927 10:JUMP0000 4234:55 4235:

14、29,4次訪存,AC=55H,命中1次,1次訪存,命中,AC=0,3次訪存,命中1次,跳過未執(zhí)行,1次訪存,1次訪存,命中,發(fā)生跳轉(zhuǎn),AC=1,R=1,1次訪存,4次訪存,命中2次,AC=2,0927=2,3次訪存,命中1次,發(fā)生跳轉(zhuǎn),第一輪命中率7/18，從第二輪開始100,計算機組成與結(jié)構,29,湖南大學計算機與通信學院,P301習題6：,Cache hit,計算機組成與結(jié)構,30,湖南大學計算機與通信學院,9.2.5 在cache中替換數(shù)據(jù),問題的引出： 計算機開始執(zhí)行一個程序。它從內(nèi)存中取指令和數(shù)據(jù)，同時將這些值載入cache。當cache為空或很少被占用時，會工作得很好。但是，最終計

15、算機會要將數(shù)據(jù)移入到已占用的cache單元。此時，將哪個數(shù)據(jù)移出cache，以及此數(shù)據(jù)如何再保存到物理內(nèi)存，這一問題就變得至關重要。,計算機組成與結(jié)構,31,湖南大學計算機與通信學院,替換策略：,FIFO 先進先出原則 LRU 最久未使用原則 LFU 最少使用原則 隨機策略,計算機組成與結(jié)構,32,湖南大學計算機與通信學院,1.FIFO 先進先出策略：一般與全相聯(lián)映像配套使用,按順序填充相聯(lián)存儲器，當cache 占滿時返回最頂單元，用新數(shù)據(jù) 替換原有數(shù)據(jù) 只要一個寄存器就能實現(xiàn) 該寄存器保存下一個要被替換的 單元的指針 性能可能不好、容易實現(xiàn),計算機組成與結(jié)構,33,湖南大學計算機與通信學院,

16、2. LRU 最久未使用策略,跟蹤單元的訪問順序，用新的數(shù) 據(jù)替換近期最久未使用的數(shù)據(jù) 每個cache單元需要一個計數(shù)器 最近訪問的數(shù)據(jù)，將相應的計數(shù) 器置為0；其余的計數(shù)器依次加1 性能好但實現(xiàn)難，一般用于組相聯(lián)Cache中。,計算機組成與結(jié)構,34,湖南大學計算機與通信學院,例：在一個4路組相聯(lián)cache單元中應用LRU策略,T,D,C,V,T,D,C,V,T,D,C,V,T,D,C,V,C,c,2,1,B,b,1,1,A,a,0,1,-,-,-,0,1.Cache單元的當前狀態(tài),2.CPU訪問D,T,D,C,V,T,D,C,V,T,D,C,V,T,D,C,V,C,c,1,B,b,1,A,

17、a,1,3,2,1,1,2,1,0,0,計算機組成與結(jié)構,35,湖南大學計算機與通信學院,3.CPU訪問E,T,D,C,V,T,D,C,V,T,D,C,V,T,D,C,V,0,1,B,b,3,1,A,a,2,1,d,1,1,4.CPU訪問A,T,D,C,V,T,D,C,V,T,D,C,V,T,D,C,V,1,1,B,b,1,0,1,D,d,2,1,命中,3,2,1,1,D,d,0,0,2,1,E,e,3,計算機組成與結(jié)構,36,湖南大學計算機與通信學院,3.RANDOM 隨機策略,隨機的選擇一個單元給新的數(shù)據(jù)使用 性能可能不好，與FIFO策略差不多,計算機組成與結(jié)構,37,湖南大學計算機與通信

18、學院,9.2.6 寫數(shù)據(jù)到cache,寫直達法 每次信息從CPU寫入cache單元 中時，也要寫回相應的物理內(nèi)存 單元中 回寫法 寫入cache中的值并不總是被寫 回物理內(nèi)存。僅在數(shù)據(jù)被移出 cache時寫回物理內(nèi)存一次,寫命中時：,計算機組成與結(jié)構,38,湖南大學計算機與通信學院,處理寫失效問題,按寫分配法 把單元裝入cache，然后使用寫 直達法或?qū)懟胤ò褦?shù)據(jù)寫到cache 不按寫分配法 直接更新物理內(nèi)存中的值，而 不把值裝載至cache,計算機組成與結(jié)構,39,湖南大學計算機與通信學院,9.2.7 cache的性能,評判性能的標準 Cache命中 要訪問的數(shù)據(jù)已在cache中 Cache

19、失效 要訪問的數(shù)據(jù)不在cache中,計算機組成與結(jié)構,40,湖南大學計算機與通信學院,命中率h：指由cache（而不是物理內(nèi)存） 提供服務的訪存百分比,平均訪問時間Tm：是cache訪問時間Tc和內(nèi) 存訪問時間Tp的加權平均，權值是h,Tm=h Tc+(1-h) Tp,計算機組成與結(jié)構,41,湖南大學計算機與通信學院,Tc=10ns Tp=60ns 結(jié)論：增加命中率 能夠減少平均訪問 時間,計算機組成與結(jié)構,42,湖南大學計算機與通信學院,首先考慮相聯(lián)cache。它初始化為空，使用FIFO的替換策略。表9.2展示了每一個值被訪問時cache的內(nèi)容。在18次訪問中，有7次命中，命中率為h=0.3

20、89。,計算機組成與結(jié)構,43,湖南大學計算機與通信學院,直接映射cache中的結(jié)構在表9.3中。不需要替換策略。18次訪問中只有3次命中，命中率僅為h=0.167。,計算機組成與結(jié)構,44,湖南大學計算機與通信學院,2路組相聯(lián)cache的結(jié)構在表9.4中。Cache使用LRU替換策略；計數(shù)值也顯示在表中。值得注意的是，因為cache是2路的，僅僅構成4個cache地址，當內(nèi)存低3位地址中的低2位(組號)相同時，映像到cache的同一組。18次訪問中同樣7次命中，命中率h=0.389。,計算機組成與結(jié)構,45,湖南大學計算機與通信學院,同上例相聯(lián)Cache，但數(shù)據(jù)行（塊）大小2,計算機組成與結(jié)

21、構,46,湖南大學計算機與通信學院,直接映像Cache，數(shù)據(jù)行（塊）大小2,A0B0C2A0D1B0E4F5A0C2D1B0G3C2H7I6A0B0,計算機組成與結(jié)構,47,湖南大學計算機與通信學院,課堂練習：,一臺基于相對簡單CPU的計算機，有一個16個字節(jié)、行大小為2字節(jié)的直接映像Cache。給出執(zhí)行下列代碼過程中及執(zhí)行完代碼后Cache的內(nèi)容。同時求這段程序在Cache系統(tǒng)中的命中率。 0:LDAC4234 3:STAC4235 6:MVAC 7:INAC 8:ADD 9:JPNZ0020 C:JUMP0010 F:NOP 10:CLAC 11:JUMP0020 20:LDAC4235

22、23:JUMP0029 26:JUMP0000 29:AND 4234:55,計算機組成與結(jié)構,48,湖南大學計算機與通信學院,塊0 塊1 塊2 塊3 塊4 塊5 塊6 塊7,000,LDAC,34,1,000,42,STAC,1,423,55,1,0:LDAC4234 3:STAC4235 6:MVAC 7:INAC 8:ADD 9:JPNZ0020 C:JUMP0010 F:NOP 10:CLAC 11:JUMP0020 20:LDAC4235 23:JUMP0029 26:JUMP0000 29:AND 4234:55,1/4命中，AC=55H,000,35,42,命中,1,命中,替換,

23、423,55,2/4命中，4235H=55H,000,MVAC,INAC,1,0/1命中，R=55H,1/1命中，AC=56H,命中,000,ADD,JPNZ,1,命中,0/1命中，AC=ABH,34,命中,STAC,替換,42,55,INAC,JPNZ,000,20,00,00,命中,2/3命中,LDAC,35,替換,002,42,JUMP,002,35,命中,替換,55,命中,2/4命中，AC=55H,JUMP,命中,29,00,替換,002,00,命中,2/3命中,跳過不執(zhí)行,00,002,AND,替換,0/1命中，AC=55H,命中率=5/1145.45%,計算機組成與結(jié)構,49,湖南

24、大學計算機與通信學院,9.3 虛擬存儲器,存儲管理單元 在物理內(nèi)存和較慢的存儲設備間移動數(shù)據(jù) 虛擬存儲器的主要實現(xiàn)方法：分頁和分段,交換磁盤 交換文件,計算機組成與結(jié)構,50,湖南大學計算機與通信學院,9.3.1 分頁,頁面：在分頁技術中，整個邏輯地址空間被劃分為連續(xù)的塊叫做頁面,頁面的特點： 每個頁尺寸相同 頁面不可重疊，每個邏輯地址確切地 屬于某個頁面,計算機組成與結(jié)構,51,湖南大學計算機與通信學院,一個頁面或者包含程序指令或者包含數(shù)據(jù)，不能同時包含兩者。 4. 可能導致內(nèi)部碎片問題 內(nèi)部碎片：假設MMU實現(xiàn)的頁式存儲器中每個頁面大小為4K，一個4K+1大小的程序需要MMU分配兩個存儲器

25、頁面，盡管它的第二個頁面只用了4K單元的一個單元，這就是所謂的內(nèi)存碎片。,計算機組成與結(jié)構,52,湖南大學計算機與通信學院,圖9.10 相對簡單CPU一種可能的內(nèi)存配置,它具有64k的邏輯地址空間 16k的物理內(nèi)存，頁面大小4k,計算機組成與結(jié)構,53,湖南大學計算機與通信學院,分頁系統(tǒng)必須解決的問題： 何時將某頁移入內(nèi)存？ CPU如何在物理內(nèi)存找到數(shù)據(jù)，尤其邏輯地址和物理地址不一致的情況下？ 當所有頁框都裝有頁面，而CPU需要訪問的數(shù)據(jù)不在這些頁面怎么辦？,計算機組成與結(jié)構,54,湖南大學計算機與通信學院,存儲管理單元處理上述所有問題,完成邏輯地址到物理地址的轉(zhuǎn)換 產(chǎn)生缺頁故障，將數(shù)據(jù)從頁面

26、裝入到物理內(nèi)存 產(chǎn)生請求頁，把新的請求頁移入到物理內(nèi)存,計算機組成與結(jié)構,55,湖南大學計算機與通信學院,圖9.11 存儲器層次結(jié)構中的MMU配置,計算機組成與結(jié)構,56,湖南大學計算機與通信學院,頁表的概念,MMU用頁表來跟蹤哪一頁存儲在哪個幀中,頁表的組成（如圖9.12）： 幀指示域(frame) 有效位(valid) 計數(shù)值（count,有些頁表不需要） 臟位(dirty),計算機組成與結(jié)構,57,湖南大學計算機與通信學院,圖9.12 （a）為頁表，（b）為對應的物理內(nèi)存,相對簡單CPU的頁表，有16K的物理內(nèi)存，頁面大小為4K。 頁表包含了16個單元，每一單元對應邏輯地址空間的一個頁面

27、，它包含一個2bit的域，表明了該邏輯頁存儲在哪一個頁框中 每一單元還包含一個有效位,0頁，對應于邏輯地 址0000H1FFFH， 存儲在1號頁框中，物理地址為1000H1FFFH,計算機組成與結(jié)構,58,湖南大學計算機與通信學院,9.3.1 分段,分段：在分段技術中，程序被劃分為幾段，每段為一個自包含的單元,分段的特點： 每個段大小可以變化 分段存在外部碎片問題,計算機組成與結(jié)構,59,湖南大學計算機與通信學院,外部碎片：內(nèi)存駐留有3個段，另有8K自由空間。而這8K空間被劃分開了，于是不移動或撤除某個當前載入段的話，大小超過3K的段已無法裝入內(nèi)存（如圖9.16）,圖9.16由于分段引起的物理

28、內(nèi)存外部碎片,計算機組成與結(jié)構,60,湖南大學計算機與通信學院,分段機制中邏輯地址到物理地址的轉(zhuǎn)換,圖9.15 分段機制中邏輯地址到物理地址的轉(zhuǎn)換,邏輯地址被剖分為段號和偏移量,計算機組成與結(jié)構,61,湖南大學計算機與通信學院,段號輸入到段表中，如果段已被裝入內(nèi)存，輸出段的起始地址和段大小 如果段不在物理內(nèi)存中，就產(chǎn)生一個缺段，MMU裝入新段到內(nèi)存中 偏移量與段大小進行比較，如果前者大于后者，或者相等，說明所訪問單元不在段內(nèi)，就產(chǎn)生一個錯誤 如果偏移量有效，則與段地址的起始值相加，形成一個正確的物理內(nèi)存地址,計算機組成與結(jié)構,62,湖南大學計算機與通信學院,分段機制中的一個嚴重缺陷 在分頁機制中，頁號送到頁表（和TLB） 以產(chǎn)生頁框號。該值和偏移量拼接構成物理地 址。而在分段機制中，通過