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

1、計(jì)算機(jī)原理及系統(tǒng)結(jié)構(gòu) 第三十四講主講教師：趙主講教師：趙宏偉宏偉 學(xué)時：學(xué)時：64第第8 8章章高速緩沖存儲器和虛擬存儲器高速緩沖存儲器和虛擬存儲器3本章主要內(nèi)容本章主要內(nèi)容高速緩沖存儲器（高速緩沖存儲器（Cache）n高速緩存的基本運(yùn)行原理n高速緩存的3種映像方式n高速緩存使用中的幾個問題虛擬存儲器虛擬存儲器n虛擬存儲器概述n段式存儲管理n頁式存儲管理4微電子技術(shù)發(fā)展趨勢微電子技術(shù)發(fā)展趨勢CPU與與DRAM性能比較性能比較處理器性能每年處理器性能每年增長增長60%動態(tài)存儲器性能每年增長9%1101001000198019811983198419851986198719881989199019

2、91199219931994199519961997199819992000DRAMCPU1982CPU與主存儲器的性能差與主存儲器的性能差異，每年增長異，每年增長50%性能性能摩爾定律年份年份P214P2145程序的局部性原理程序的局部性原理程序在一定時間段內(nèi)通常只訪問較小的地址空間程序在一定時間段內(nèi)通常只訪問較小的地址空間兩種局部性：兩種局部性：時間局部性時間局部性和和空間局部性空間局部性n時間局部性：最近被訪問的信息很可能還要被訪問。w將最近被訪問的信息項(xiàng)裝入到Cache中。n空間局部性：最近被訪問的信息臨近的信息也可能被訪問。w將最近被訪問的信息項(xiàng)臨近的信息一起裝入到Cache中。地址

3、空間訪問概率6高速緩沖存儲器（高速緩沖存儲器（Cache）用途：用途：設(shè)置在設(shè)置在 CPU 和和 主存儲器之間，完成高速主存儲器之間，完成高速與與 CPU 交換信息，盡量避免交換信息，盡量避免 CPU不必要地多次不必要地多次直接訪問慢速的主存儲器，從而提高計(jì)算機(jī)系統(tǒng)直接訪問慢速的主存儲器，從而提高計(jì)算機(jī)系統(tǒng)的運(yùn)行效率。的運(yùn)行效率。實(shí)現(xiàn)：實(shí)現(xiàn)：這是一個存儲容量很小，但讀寫速度更快這是一個存儲容量很小，但讀寫速度更快的，以的，以 關(guān)聯(lián)存儲器方式關(guān)聯(lián)存儲器方式 運(yùn)行、用靜態(tài)存儲器芯運(yùn)行、用靜態(tài)存儲器芯片實(shí)現(xiàn)的存儲器系統(tǒng)。片實(shí)現(xiàn)的存儲器系統(tǒng)。要求：要求：有足夠高的命中率，既當(dāng)有足夠高的命中率，既當(dāng) C

4、PU需用主存中需用主存中的數(shù)據(jù)時，多數(shù)情況可以直接從的數(shù)據(jù)時，多數(shù)情況可以直接從CACHE中得到，中得到，稱二者之比為命中率。稱二者之比為命中率。計(jì)算機(jī)原理及系統(tǒng)結(jié)構(gòu) 第三十五講主講教師：趙主講教師：趙宏偉宏偉 學(xué)時：學(xué)時：648CACHE的基本運(yùn)行原理的基本運(yùn)行原理Cache存儲單元的組成部分存儲單元的組成部分n數(shù)據(jù)字段數(shù)據(jù)字段：保存從主存單元復(fù)制過來的數(shù)據(jù)n標(biāo)志字段標(biāo)志字段：保存相應(yīng)主存單元的地址信息n有效位字段有效位字段：標(biāo)識數(shù)據(jù)字段和標(biāo)志字段的是否有效提高提高Cache性能，降低成本性能，降低成本nCache單元的大小：cache line size（幾個主存字，減少標(biāo)志位位數(shù)，較少C

5、ache總?cè)萘浚﹏Cache與主存交換數(shù)據(jù)的單位： cache line size（充分利用空間局部性）nCache單元與主存單元的對應(yīng)關(guān)系，例如：w完全隨意對應(yīng)、一對多硬性對應(yīng)和多對多有限隨意對應(yīng)nCache的容量、分層組織、接入方式等方面P215P2159CACHE的基本運(yùn)行原理的基本運(yùn)行原理MEMORY CACHE CONTROL數(shù)據(jù)總線數(shù)據(jù)總線譯碼選一單元譯碼選一單元比較選一行比較選一行讀過程為例讀過程為例地址總線地址總線ADDR DATA CACHE CPU 10CACHE的的3種映像方式種映像方式地址映像地址映像：把一主存單元的數(shù)據(jù)復(fù)制到：把一主存單元的數(shù)據(jù)復(fù)制到CACHE中中時，

6、還要把該主存單元的地址，經(jīng)過某種函數(shù)關(guān)時，還要把該主存單元的地址，經(jīng)過某種函數(shù)關(guān)系處理后寫進(jìn)系處理后寫進(jìn)CACHE的標(biāo)志字段，這一過程被稱的標(biāo)志字段，這一過程被稱為為CACHE的地址映像。的地址映像。地址變換地址變換：在程序執(zhí)行時，還要把主存地址變換：在程序執(zhí)行時，還要把主存地址變換為訪問為訪問CACHE的地址，這一過程被叫做的地址，這一過程被叫做CACHE的地址變換。的地址變換。 CACHE存儲器通常使用存儲器通常使用3種映像方式，它們是全種映像方式，它們是全相聯(lián)映像方式、直接映像方式、多路組相聯(lián)映像相聯(lián)映像方式、直接映像方式、多路組相聯(lián)映像方式，方式，3種映像方式有各自的優(yōu)缺點(diǎn)。種映像方式

7、有各自的優(yōu)缺點(diǎn)。11全相聯(lián)映像方式全相聯(lián)映像方式全相聯(lián)映像方式：是指主存的一個字塊可以映像全相聯(lián)映像方式：是指主存的一個字塊可以映像到整個到整個CACHE的任何一個字塊中。的任何一個字塊中。全相聯(lián)映像方式特點(diǎn)：全相聯(lián)映像方式特點(diǎn)：n主存的字塊可以和Cache的任何字塊對應(yīng)，利用率高，方式靈活。n標(biāo)志位較長，比較電路的成本太高。如果主存空間有2m塊，則標(biāo)志位要有m位。同時，如果Cache有n塊，則需要有n個比較電路。使用成本太高12全相聯(lián)映像方式全相聯(lián)映像方式C P U數(shù)據(jù)數(shù)據(jù)主存字塊標(biāo)記主存字塊標(biāo)記有效位有效位主存儲器主存儲器CACHE比較比較譯碼譯碼標(biāo)志標(biāo)志數(shù)據(jù)數(shù)據(jù)主存字塊標(biāo)記塊內(nèi)地址主存地

8、址13全相聯(lián)硬件實(shí)現(xiàn)舉例全相聯(lián)硬件實(shí)現(xiàn)舉例計(jì)算機(jī)原理及系統(tǒng)結(jié)構(gòu) 第三十六講主講教師：趙主講教師：趙宏偉宏偉 學(xué)時：學(xué)時：6415直接映像方式直接映像方式直接映像方式：是指主存的一個字塊只能映像到直接映像方式：是指主存的一個字塊只能映像到CACHE的一個準(zhǔn)確確定的字塊中。的一個準(zhǔn)確確定的字塊中。直接映像方式特點(diǎn)：直接映像方式特點(diǎn)：n主存的字塊只可以和固定的Cache字塊對應(yīng)，方式直接，利用率低。n標(biāo)志位較短，比較電路的成本低。如果主存空間有2m塊，Cache中字塊有2c塊，則標(biāo)志位只要有m-c位。且僅需要比較一次。利用率低，命中率低，效率較低16直接映像方式直接映像方式C P U數(shù)據(jù)數(shù)據(jù)有效位有

9、效位主存儲器主存儲器CACHE比較比較譯碼譯碼譯碼譯碼cache字塊地址主存字塊標(biāo)記標(biāo)志標(biāo)志數(shù)據(jù)數(shù)據(jù)主存字塊標(biāo)記塊內(nèi)地址主存地址cache字塊地址17直接映像硬件實(shí)現(xiàn)舉例直接映像硬件實(shí)現(xiàn)舉例Address (showing bit positions)2010ByteoffsetValid TagDataIndex012102110221023TagIndexHitData203231 30 13 12 11 2 1 018多路組相聯(lián)映像方式多路組相聯(lián)映像方式多路組相聯(lián)映像方式：是對全相聯(lián)映像和直接映想象的多路組相聯(lián)映像方式：是對全相聯(lián)映像和直接映想象的一種折衷的處理方案。既不在主存和一種折衷

10、的處理方案。既不在主存和CACHE之間實(shí)現(xiàn)字之間實(shí)現(xiàn)字塊的完全隨意對應(yīng)，也不在主存和塊的完全隨意對應(yīng)，也不在主存和CACHE之間實(shí)現(xiàn)字塊之間實(shí)現(xiàn)字塊的多對一的硬性對應(yīng)，而是實(shí)現(xiàn)一種有限度的隨意對應(yīng)。的多對一的硬性對應(yīng)，而是實(shí)現(xiàn)一種有限度的隨意對應(yīng)。 多路組相聯(lián)映像方式特點(diǎn)：多路組相聯(lián)映像方式特點(diǎn)：n折衷方案。組間為全相連，組內(nèi)為直接映像。n集中了兩個方式的優(yōu)點(diǎn)。成本也不太高。最常用的CACHE映像方式19組地址兩路組相聯(lián)映像方式兩路組相聯(lián)映像方式C P U數(shù)據(jù)數(shù)據(jù)有效位有效位主存儲器主存儲器CACHE譯碼譯碼比較比較比較比較譯碼譯碼譯碼譯碼標(biāo)志標(biāo)志數(shù)據(jù)數(shù)據(jù)主存地址主存字塊標(biāo)記塊內(nèi)地址組地址主存

11、字塊標(biāo)記20多路組相聯(lián)硬件實(shí)現(xiàn)舉例多路組相聯(lián)硬件實(shí)現(xiàn)舉例Address228VTagIndex012253254255DataVTagDataVTagDataVTagData32224-to-1 multiplexorHitData123891011123031021三種映像方式比較三種映像方式比較全相聯(lián)映射全相聯(lián)映射n主存中的一塊可以映射到Cache中任何一個位置直接映像直接映像n主存中的一塊只能映射到Cache中唯一的一個位置n定位時，不需要判斷，只需替換多路組相聯(lián)映射多路組相聯(lián)映射n主存中的一塊可以選擇映射到Cache中多個位置全相聯(lián)映射和多路組相聯(lián)映射的失效處理全相聯(lián)映射和多路組相聯(lián)映

12、射的失效處理n從主存中取出新塊n為了騰出Cache空間，需要替換出一個Cache塊n不唯一，則需要判斷應(yīng)替出哪塊22CACHE使用中的幾個問題使用中的幾個問題CACHE的重要技術(shù)指標(biāo)：的重要技術(shù)指標(biāo)：命中率命中率影響影響 CACHE 命中率的因素命中率的因素nCACHE 的容量，大一些好的容量，大一些好nCACHE 與主存儲器每次交換信息的單位量與主存儲器每次交換信息的單位量(Cache Line Size)適中適中nCACHE 不同的組織方式，多路組相聯(lián)更好不同的組織方式，多路組相聯(lián)更好nCACHE 的多級組織可提高命中率的多級組織可提高命中率nCACHE 裝滿后的替換算法裝滿后的替換算法2

13、3cache的容量與命中率的關(guān)系的容量與命中率的關(guān)系 Cache Size in KBHit Rate24cache line size與缺失率的關(guān)系與缺失率的關(guān)系 P220P220計(jì)算機(jī)原理及系統(tǒng)結(jié)構(gòu) 第三十七講主講教師：趙主講教師：趙宏偉宏偉 學(xué)時：學(xué)時：6426多級的多級的cache結(jié)構(gòu)與命中率的關(guān)系結(jié)構(gòu)與命中率的關(guān)系 為增加計(jì)算機(jī)系統(tǒng)中的為增加計(jì)算機(jī)系統(tǒng)中的cache容量，通?？梢栽谝延械娜萘?，通常可以在已有的cache存儲器系統(tǒng)之外，再增加一個容量更大的存儲器系統(tǒng)之外，再增加一個容量更大的cache。此時原有此時原有cache為第一級為第一級cache（例如奔騰機(jī)微處理機(jī)芯（例如奔騰

14、機(jī)微處理機(jī)芯片內(nèi)的片內(nèi)的cache），新增加的），新增加的cache則成為第二級的則成為第二級的cache。第二級第二級cache的容量比第一級的容量比第一級cache的容量要大得多，在的容量要大得多，在第一級第一級cache中保存的信息也一定保存在第二級中保存的信息也一定保存在第二級cache中，中，但保存有比第一級但保存有比第一級cache中更多的信息。當(dāng)中更多的信息。當(dāng)CPU訪問第一訪問第一級級cache出現(xiàn)缺失情況時，就去訪問第二級出現(xiàn)缺失情況時，就去訪問第二級cache。若第一級、第二級若第一級、第二級cache的命中率為的命中率為90%，則它們合起，則它們合起來后的命中率為來后的命

15、中率為-（-90）（-90）=99，而不會是而不會是81。27Cache替換算法替換算法隨機(jī)替換（隨機(jī)替換（RAND）n隨機(jī)找一個Cache塊進(jìn)行替換，比較盲目。先進(jìn)先出算法（先進(jìn)先出算法（FIFO）n將最早調(diào)入Cache的字塊替換出去，采用循環(huán)電路容易實(shí)現(xiàn)，開銷小。最近最少使用算法（最近最少使用算法（LRU）n需要計(jì)算字塊的使用次數(shù)，開銷大，但平均命中率比FIFO要高。28改寫主存儲器的策略改寫主存儲器的策略若若 CPU 改寫了改寫了 Cache 一單元內(nèi)容（寫命中）后且尚未一單元內(nèi)容（寫命中）后且尚未改變主存相應(yīng)單元內(nèi)容，則出現(xiàn)數(shù)據(jù)不一致性。有兩種改變主存相應(yīng)單元內(nèi)容，則出現(xiàn)數(shù)據(jù)不一致性。

16、有兩種解決辦法：解決辦法：n直接改寫主存單元內(nèi)容（直接改寫主存單元內(nèi)容（Write Through）： 簡便易行，數(shù)據(jù)一致性容易保證，但可能帶來系統(tǒng)運(yùn)行效率不高的問題，Cache對寫操作沒有提高性能。n拖后改寫主存單元內(nèi)容（拖后改寫主存單元內(nèi)容（Write Back）：一直拖到有另外的設(shè)備要讀該內(nèi)容過時的主存單元時，則首先停止這一讀操作，接下來改寫主存內(nèi)容，之后再起動已停下來的讀操作。矛盾是如何檢查是否是讀無效內(nèi)存單元的操作，這是通過監(jiān)視地址總線完成的，記下無效單元地址用于比較?？刂茝?fù)雜些，但可以提供更高的系統(tǒng)運(yùn)行效率。如果如果CPU寫內(nèi)存的數(shù)據(jù)不在寫內(nèi)存的數(shù)據(jù)不在Cache中（寫缺失）那么怎

17、中（寫缺失）那么怎么處理呢？么處理呢？n按寫分配法 vs. 不按寫分配法P222P22229CACHE 接入系統(tǒng)的體系結(jié)構(gòu)接入系統(tǒng)的體系結(jié)構(gòu)側(cè)接法：像入出設(shè)備似的連接到總線上，優(yōu)點(diǎn)是結(jié)構(gòu)側(cè)接法：像入出設(shè)備似的連接到總線上，優(yōu)點(diǎn)是結(jié)構(gòu)簡單，成本低，缺點(diǎn)是不利于降低總線占用率。簡單，成本低，缺點(diǎn)是不利于降低總線占用率。CPUMEMORYCACHEBus Master 1Bus Master 2總線總線30CACHE 接入系統(tǒng)的體系結(jié)構(gòu)接入系統(tǒng)的體系結(jié)構(gòu)隔斷法：把原來的總線打斷為兩段，使隔斷法：把原來的總線打斷為兩段，使 CACHE 處在處在兩段之間。優(yōu)點(diǎn)是有利于提高總線利用率，支持總線兩段之間。優(yōu)

18、點(diǎn)是有利于提高總線利用率，支持總線并發(fā)操作；缺點(diǎn)是結(jié)構(gòu)復(fù)雜，成本較高。并發(fā)操作；缺點(diǎn)是結(jié)構(gòu)復(fù)雜，成本較高。CPUMEMORYBus Master 1Bus Master 2總線總線CACHE31本章主要內(nèi)容本章主要內(nèi)容高速緩沖存儲器（高速緩沖存儲器（Cache）n高速緩存的基本運(yùn)行原理n高速緩存的3種映像方式n高速緩存使用中的幾個問題虛擬存儲器虛擬存儲器n虛擬存儲器概述n段式存儲管理n頁式存儲管理32虛擬存儲器概述虛擬存儲器概述虛擬存儲器是指用磁盤的存儲空間來彌補(bǔ)主存空間的不足，虛擬存儲器是指用磁盤的存儲空間來彌補(bǔ)主存空間的不足，使得程序人員能夠使用比主存實(shí)際空間更大的存儲空間來使得程序人員能

19、夠使用比主存實(shí)際空間更大的存儲空間來編寫和運(yùn)行程序。編寫和運(yùn)行程序。根據(jù)根據(jù)“程序運(yùn)行的局部性原理程序運(yùn)行的局部性原理”，只把一小段時間內(nèi)用到，只把一小段時間內(nèi)用到的程序和數(shù)據(jù)裝入主存；其他程序和數(shù)據(jù)在操作系統(tǒng)的支的程序和數(shù)據(jù)裝入主存；其他程序和數(shù)據(jù)在操作系統(tǒng)的支持下，在磁盤和主存之間按程序運(yùn)行的需要自動成批量地持下，在磁盤和主存之間按程序運(yùn)行的需要自動成批量地完成交換。完成交換。虛擬存儲器經(jīng)常使用兩種基本管理技術(shù)，核心問題都在于虛擬存儲器經(jīng)常使用兩種基本管理技術(shù)，核心問題都在于處理數(shù)據(jù)的存放與調(diào)度。處理數(shù)據(jù)的存放與調(diào)度。n段式存儲管理段式存儲管理n頁式存儲管理頁式存儲管理P224P22433

20、段式存儲管理段式存儲管理段段是程序模塊化設(shè)計(jì)的結(jié)果，即把程序中邏輯上是程序模塊化設(shè)計(jì)的結(jié)果，即把程序中邏輯上相對獨(dú)立的部分設(shè)計(jì)為不同的段，再經(jīng)過連接程相對獨(dú)立的部分設(shè)計(jì)為不同的段，再經(jīng)過連接程序連接成更大的程序。此時用段作為信息調(diào)入主序連接成更大的程序。此時用段作為信息調(diào)入主存的單位是合適的，以段為單位分配與管理主存存的單位是合適的，以段為單位分配與管理主存儲器被稱為段式存儲管理。儲器被稱為段式存儲管理。段式存儲管理的核心問題在于設(shè)立和管理段式存儲管理的核心問題在于設(shè)立和管理段表段表；段表也是主存中的可再定位的一段信息，用于變段表也是主存中的可再定位的一段信息，用于變換程序中的換程序中的虛地址

21、（邏輯地址）虛地址（邏輯地址）為主存單元的為主存單元的實(shí)實(shí)地址（物理地址）地址（物理地址）。P224P22434段式存儲管理段式存儲管理 主存地址空間 程序地址空間 1000 3000 0 段 1 段 2 段 計(jì)算機(jī)原理及系統(tǒng)結(jié)構(gòu) 第三十八講主講教師：趙主講教師：趙宏偉宏偉 學(xué)時：學(xué)時：6436段表內(nèi)容及其管理段表內(nèi)容及其管理段號段號 段內(nèi)地址段內(nèi)地址+邏輯地址邏輯地址段始地址段始地址 段長段長 裝入位裝入位段段表表主存實(shí)際地址主存實(shí)際地址段表基地址段表基地址37段式存儲管理段式存儲管理提高性能的方法提高性能的方法n使用段地址寄存器，保存一段的起始地址，以后使用這一段的數(shù)據(jù)不必再查段表，直接計(jì)

22、算主存地址段式存儲管理的特點(diǎn)段式存儲管理的特點(diǎn)n優(yōu)點(diǎn)：段的分界與程序的自然分界對應(yīng) 段邏輯上的獨(dú)立性有利于內(nèi)存保護(hù) 便于實(shí)現(xiàn)對段的信息共享n缺點(diǎn) 段長不確定，主存分配和管理不便 容易在段間形成難以利用的碎片38頁式存儲管理頁式存儲管理頁頁式存儲管理是把虛擬空間和主存空間都分成大式存儲管理是把虛擬空間和主存空間都分成大小相同的頁（為小相同的頁（為2的整數(shù)冪個字），并以頁為單的整數(shù)冪個字），并以頁為單位進(jìn)行虛存與主存間的信息交換。此時虛存邏輯位進(jìn)行虛存與主存間的信息交換。此時虛存邏輯地址和主存物理地址分別被分為地址和主存物理地址分別被分為“虛存頁號虛存頁號頁頁內(nèi)地址內(nèi)地址”和和“主存頁號主存頁號頁

23、內(nèi)地址頁內(nèi)地址”，虛、實(shí)二虛、實(shí)二頁號頁號會不同，但使用相同的頁內(nèi)地址。會不同，但使用相同的頁內(nèi)地址。與段式存儲管理不一樣，頁不是程序本身的結(jié)構(gòu)與段式存儲管理不一樣，頁不是程序本身的結(jié)構(gòu)特性，而是從管理的角度人為劃分的結(jié)果。設(shè)置特性，而是從管理的角度人為劃分的結(jié)果。設(shè)置和管理好和管理好頁表頁表是頁式存儲管理的關(guān)鍵技術(shù)。是頁式存儲管理的關(guān)鍵技術(shù)。P226P22639頁式存儲管理頁式存儲管理 主存地址空間 程序地址空間 A段 B段 40頁表內(nèi)容和頁式管理頁表內(nèi)容和頁式管理+（在內(nèi)存中）控制位（在內(nèi)存中）控制位 有效位有效位頁表頁表虛地址虛地址 (程序中給出程序中給出)實(shí)地址實(shí)地址 (讀寫內(nèi)存用讀寫內(nèi)存用)按地址讀按地址讀實(shí)頁號實(shí)頁號虛頁號虛頁號 頁內(nèi)地址頁內(nèi)地址實(shí)頁號實(shí)頁號 頁內(nèi)地址頁內(nèi)地址頁表基地址頁表基地址控制位：包括修改位、替換位有效位：表示該頁是否已裝入主存41頁式存儲管理頁式存儲管理頁式存儲管理的特點(diǎn)頁式存儲管理的特點(diǎn)n優(yōu)點(diǎn)：只要有空白頁新頁就可以調(diào)入內(nèi)存 只有程序的最