計算機系統(tǒng)結(jié)構(gòu)第四章

1、第四章 存儲體系概 述本章著重講述存貯體系的基本概念并行主存系統(tǒng)的組成虛擬存貯器的原理Cache存貯器的原理虛實地址的映象和變換替換算法影響性能的因素分析及軟硬件功能分配中的某些問題本章的基本要求并行主存系統(tǒng)的基本要求：領(lǐng)會發(fā)展存貯體系的必要性及存貯體系的兩個分支。了解并行主存系統(tǒng)的各種組織形式。掌握并行主存系統(tǒng)的極限頻寬和實際頻寬的關(guān)系與計算。領(lǐng)會并行主存局限性以及發(fā)展存貯體系的必要性。了解有關(guān)存貯體系的性能參數(shù)及相關(guān)結(jié)論。4本章的基本要求虛擬存儲器的基本要求：理解虛擬存貯器的工作原理；掌握頁式虛擬存貯器的虛、實地址字段對應(yīng)關(guān)系和地址映象規(guī)則。熟練掌握在頁式虛擬存貯器中，頁面裝入和替換的過程

2、，并能計算出頁面命中率。理解堆棧型替換算法的定義。領(lǐng)會在虛擬存貯器中對頁面失效的處理及內(nèi)部地址映象表中的快慢表機構(gòu)。 5本章的基本要求高速緩存存儲器的基本要求：了解Cache存貯器的組成、工作原理。掌握Cache存貯器中的組相聯(lián)地址映象規(guī)則，相應(yīng)的映象表機構(gòu)和虛、實地址變換過程。給出主存的塊地址流后，采用組相聯(lián)或直接映象、LRU或FIFO替換算法時，能 熟練畫出各主存塊裝入Cache和其被替換的過程示意圖，并計算出Cache塊的命中率。6一、存貯體系的概念與并行主存系統(tǒng)1 存貯系統(tǒng)的基本要求 對存貯系統(tǒng)的基本要求是：大容量、高速度、低價格。 存儲器容量SM=WLm 存儲器速度可以用存儲周期TM

3、和頻寬Bm來描述。 TM是存貯器連續(xù)訪問時所需要的間隔時間； Bm是指存貯器連續(xù)訪問時能提供的數(shù)據(jù)傳送速率： Bm=Wm/ TM7一、存貯體系的概念與并行主存系統(tǒng)2 發(fā)展存儲體系的必要性 存在的問題： 1） 容量增大，速度會下降，價格會升高； 2）速度升高，價格也會升高。 解決問題的思路： 1）改進工藝、提高技術(shù)、降低成本； 2）配置多種性能價格不同的存貯器組成系統(tǒng)，使所有信息以各種方式分布于不同的存儲器上。8一、存貯體系的概念與并行主存系統(tǒng)單體單字單體多字多體單字9一、存貯體系的概念與并行主存系統(tǒng)單體單字單體多字多體單字10一、存貯體系的概念與并行主存系統(tǒng)單體單字單體多字多體單字BM=W/T

4、M11一、存貯體系的概念與并行主存系統(tǒng)單體單字單體多字多體單字BM=W/TM12一、存貯體系的概念與并行主存系統(tǒng)單體單字單體多字多體單字BM=W/TMBM=4W/TM一、存貯體系的概念與并行主存系統(tǒng)單體單字單體多字多體單字BM=W/TMBM=4W/TM一、存貯體系的概念與并行主存系統(tǒng)單體單字單體多字多體單字BM=W/TMBM=4W/TMBM=4W/TM一、存貯體系的概念與并行主存系統(tǒng)單體多字存儲器主要缺點：（訪問沖突大）1）取指沖突；2）讀操作數(shù)沖突；3）寫數(shù)據(jù)沖突；4）讀寫沖突；單體多字一、存貯體系的概念與并行主存系統(tǒng)單體多字存儲器與多體單字存儲器的區(qū)別：1）前者并行讀出的數(shù)據(jù)其地址必須是連

5、續(xù)的且在同一單元內(nèi)；2）后者并行讀出的數(shù)據(jù)可以分屬不同的分體，地址無需連續(xù)，因為每個存儲體均有自己的地址譯碼、讀寫驅(qū)動等外圍電路。一、存貯體系的概念與并行主存系統(tǒng)一、存貯體系的概念與并行主存系統(tǒng)4 并行主存系統(tǒng)的局限性主要缺點：分體沖突；5 存儲體系的形成與分支 所謂存貯體系指的是構(gòu)成存貯系統(tǒng)的n種不同的存貯器(M1Mn)之間，配上輔助軟硬件或輔助硬件，使之從應(yīng)用程序員來看，他們在邏輯上是一個整體。讓存貯層次的等效訪問速度接近于最高層M1的，容量是最低層 Mn 的，每位價格是接近于 Mn 的。典型的兩級存貯體系是虛擬存貯器和Cache存貯器。一、存貯體系的概念與并行主存系統(tǒng) 虛擬存貯器是從主存

6、容量滿足不了要求提出來的。在主存和輔存之間，增加輔助的軟硬件，讓它們構(gòu)成一個整體。從CPU看，速度接近于主存的，容量是輔存的，每位價格接近于輔存的。主存輔存一、存貯體系的概念與并行主存系統(tǒng)Cache存貯器是從主存速度滿足不了要求提出來的。在物理Cache和主存之間，加設(shè)輔助硬件，讓它們構(gòu)成一個整體。從CPU看，速度接近于物理Cache的，容量是主存的，每位價格接近于主存的。Cache主存一、存貯體系的概念與并行主存系統(tǒng)6 存儲體系的性能參數(shù)C=（C1SM1+C2SM2）/（SM1+SM2）T=HT1+（1-H）T2 在設(shè)計存貯體系時，需要在選擇高命中率的算法、層次化相鄰兩級存貯器之間的容量差和

7、速度差，以及所增設(shè)的輔助軟硬件價格等多個因素之間進行綜合權(quán)衡。C1、SM1、T1C2、SM2、T2C、SM、TM1M2一、存貯體系的概念與并行主存系統(tǒng) 7 存貯體系依據(jù)于程序的局部性 程序的局部性表現(xiàn)在 時間和空間兩個方面。時間上的局部性是因為程序存在著循環(huán)?？臻g上的局部性是因為程序中大部分指令是順序存貯和順序被取出來執(zhí)行的，數(shù)據(jù)一般也是以向量、數(shù)組、樹、表等形式簇聚地存貯在一起的。最近的未來要用的指令和數(shù)據(jù)大多局限于正在用的指令和數(shù)據(jù)，或是與這些指令和數(shù)據(jù)位置上鄰近的單元。這樣，就可以把目前常用或?qū)⒁玫降男畔㈩A先放在容量較小的第一級存貯器M1中，從而使CPU的訪問速度可接近于M1的。一、存

8、貯體系的概念與并行主存系統(tǒng)8 存貯體系的透明性 虛擬存貯器和Cache存貯器對應(yīng)用程序員都是透明的，不需要對應(yīng)用程序做任何修改就可以在系統(tǒng)上運行。由于CPU與主存的速度差只有一個數(shù)量級，主存與輔存之間的速度差卻有3至4個數(shù)量級，所以，Cache存貯器只能全部采用硬件來實現(xiàn)。這樣，Cache存貯器對系統(tǒng)程序員也是透明的，操作系統(tǒng)不參予對Cache存貯器的管理。而在虛擬存貯器中，為了降低系統(tǒng)的成本，讓不少功能依靠操作系統(tǒng)中的虛擬存貯管理軟件來實現(xiàn)。因此，虛擬存貯器對系統(tǒng)程序員則是不透明的。二、虛擬存貯器段式存貯管理 根據(jù)所用的存貯映象算法不同，虛擬存貯器可以有段式、頁式和段頁式三種不同的存貯管理方

9、式。1 段式存貯管理方式： 在系統(tǒng)工作時，根據(jù)所給的某道程序虛地址，由該道程序的程序號經(jīng)硬件自動到段表基址寄存器組中取出相應(yīng)該程序的段表起始地址。將段表起始地址與程序地址中給出的段號相加后，到該程序段表中讀出相應(yīng)行中的裝入位。若裝入位為“0”，就發(fā)生段失效故障。此時，程序自動換道，由I/O處理機去調(diào)段，而CPU轉(zhuǎn)去執(zhí)行另一道程序。若裝入位為“1”，就讀出段映象表中該行的地址字段的值。將此地址字段的值與程序虛地址的段內(nèi)位移相加，就形成訪存的物理地址。按此物理地址就可以訪問所需要的物理存貯單元。利用段表中的段長字段可以判斷出該段的地址是否越界。利用段表中的訪問方式字段可以判斷出這次訪問是否會發(fā)生訪

10、問方式保護。 二、虛擬存貯器段式存貯管理 將程序按邏輯意義分成段，各段順序編號；各段程序都以該段的起點為0相對編址。 設(shè)置段表，程序分幾段，段表有幾行，行與段順序?qū)?yīng)；地址字段記錄、裝入位、段長。 如果系統(tǒng)有N道程序，就有N個段映象表。用N個段表基址寄存器分別記錄各道程序的段表在主存中的起始地址。二、虛擬存貯器段式存貯管理段表二、虛擬存貯器段式存貯管理 段式存貯管理方式為了對實主存的空間進行分配和回收，段式存貯器需要為操作系統(tǒng)配備一個實主存空間管理表，進行存貯管理。它包括占用區(qū)域表和可用區(qū)域表兩部分。在分配主存空間時，可采用下述兩種方法：二、虛擬存貯器段式存貯管理首先分配法：掃描可用區(qū)域表，找

11、到可用區(qū)域立即分配；二、虛擬存貯器段式存貯管理最佳分配法：掃描全部可用區(qū)域表，分配找到可用區(qū)域，使的分配后段間可用區(qū)零頭最?。欢?、虛擬存貯器段式存貯管理段式存貯管理的優(yōu)點是：支持了程序的模塊化設(shè)計和并行編程的要求，縮短了程序的編制時間；各個程序段的修改相互不會有影響；便于多道程序共享主存中某些段，不必將它們在物理主存中重復存放；段式存貯管理最主要的問題是：段映象表機構(gòu)太龐大，其地址字段和段長字段都太長；查表進行地址變換的速度太慢；對主存各區(qū)域的存貯管理十分麻煩；存貯器內(nèi)部的段間零頭浪費大，有時難以利用。結(jié)論：單純的段式存貯管理在實際的系統(tǒng)中無法采用。 將程序和內(nèi)存分稱大小相等的頁，分別按頁順序

12、編號；虛頁號和實頁號。讓程序的起點必須處在主存中某一個頁面位置的起點上。 設(shè)置頁表，程序分幾頁，頁表有幾行，行與頁順序?qū)?yīng)；虛頁號、實頁號、裝入位。 如果系統(tǒng)有N道程序，就有N個頁映象表。用N個頁表基址寄存器分別記錄各道程序的頁表在主存中的起始地址。二、虛擬存貯器頁式存貯管理二、虛擬存貯器頁式存貯管理頁表二、虛擬存貯器頁式存貯管理頁式存貯管理的優(yōu)點：所用映象表的硬件量少；地址變換的速度快；主存空間的分配和管理簡便得多。頁式存貯管理最主要的不足是：缺乏段式存貯管理的優(yōu)點。結(jié)論：頁式存貯管理在實際中使用較多。將段式存貯管理和頁式存貯管理加以結(jié)合，取長補短，引出了段頁式的存貯管理。二、虛擬存貯器段頁

13、式存貯管理3段頁式存貯管理方式：分主存為大小相等的頁，并順序編號；將程序按邏輯意義先分成段，并順序編號；各段再分成與實頁相同大小的頁，各段的頁單獨順序編號；每道程序通過一個段表和相應(yīng)的一組頁表來進行程序在主存空間中的定位；段表和頁表一般在主存中，段表的起始地址在段表基址寄存器中，頁表的起始地址在段表中；段（頁）表中的每一行對應(yīng)一個段頁）；二、虛擬存貯器地址映象與變換全相聯(lián)映象：讓每道程序的任何一個虛頁均可以映象裝入到主存中任何一個實頁位置上。地址映象：建立虛頁和實頁的對應(yīng)關(guān)系；地址變換：根據(jù)多用戶虛地址計算實地址。實地址=實頁號*每頁字數(shù)+頁內(nèi)偏移虛頁號=Int（虛地址/每頁字數(shù)）頁內(nèi)偏移=M

14、od（虛地址，每頁字數(shù)）二、虛擬存貯器地址映象與變換頁面失效：CPU按虛地址訪存時未找到所需的程序頁，稱為頁面失效。頁面爭用：兩個以上的虛頁要想進入主存中同一個實頁位置時，就會產(chǎn)生實頁沖突，或稱發(fā)生了頁面爭用。地址映象方式的選擇應(yīng)盡量能降低實頁沖突發(fā)生的概率。因此，虛擬存貯器都采用全相聯(lián)的映象規(guī)則，實頁沖突發(fā)生的概率必將是最低的。二、虛擬存貯器頁面替換算法4 頁面替換算法當頁面失效后，從輔存中將一個虛頁調(diào)入主存時又發(fā)生了實頁沖突，這就要啟用替換算法，選出主存中的一個頁，將其替換出去。替換算法的選擇應(yīng)當盡可能使主存的命中率高些，算法的實現(xiàn)要方便，所需的軟硬件要少，成本要低。二、虛擬存貯器頁面替換

15、算法1）隨機(RAND)替換算法是用軟件或硬件的隨機數(shù)生成器產(chǎn)生出一個待替換頁的頁號。 此替換算法雖然簡單，容易實現(xiàn)，但由于未反映出程序的局部性特點，命中率很低，所以無法實用。2）先進先出(FIFO)替換算法是選擇其中最早裝入主存的虛頁，將其替換出去。 這種算法實現(xiàn)起來不復雜，但不能很好地反映出程序的局部性，因此主存的命中率不一定很高。由于實現(xiàn)成本低，目前仍有不少系統(tǒng)在用。二、虛擬存貯器頁面替換算法3）近期最少使用(LRU)替換算法是選擇近期使用得最少的頁，將其替換出去。 這種算法能比較確切地反映出程序的局部性特點。也稱為近期最久未用過的替換算法。4）優(yōu)化(OPT)替換算法是選擇未來的近期里不

16、用或很久才用的頁面，將其替換出去。 這種算法雖然不實用，但它可作為評價所用替換算法好壞的一個標準，哪種替換算法的主存命中率能接近于OPT法的，它就是好的替換算法。二、虛擬存貯器頁面替換算法例1有一個虛擬存貯器，主存有03四頁位置，程序有07八個虛頁，采用全相聯(lián)映象和LRU替換算法。給出如下程序頁地址流：2,3,5,2,4,0,1,2,4,6。 (1) 分配給程序3個實頁，請畫出上述頁地址流工作過程中，主存各頁位置上所裝程序各頁頁號的變化過程圖，標出命中時刻。 (2) 分配給程序4個實頁，請畫出上述頁地址流工作過程中，主存各頁位置上所裝程序各頁頁號的變化過程圖，求此時命中率。二、虛擬存貯器頁面替

17、換算法5）堆棧型替換算法對任一程序的頁地址流作兩次主存頁面分配，分別分配給m個和n個頁面，并且有mn，如果在任何時刻t，主存中的虛頁集合Bt都滿足關(guān)系： Bt（m） Bt（ n）則這類替換算法稱為堆棧型替換算法。通俗地講，凡屬堆棧型替換算法，當增加分配給程序的實頁數(shù)目時，其命中率一般會提高，至少不會下降。二、虛擬存貯器頁面替換算法例3 頁式虛擬存貯器共有9頁空間準備分配給A、B兩道程序。已知B道程序若給其分配4頁時，命中率為8/15；而若分配5頁時，命中率可達10/15?，F(xiàn)給出A道程序的頁地址流為2，3，2，1，5，2，4，5，3，2，5，2，1，4，5。 (1)畫出用堆棧對A道程序頁地址流的

18、模擬處理過程圖，統(tǒng)計給其分配4頁和5頁時的命中率。 (2)根據(jù)已知條件和上述統(tǒng)計結(jié)果，給A、B兩道程序各分配多少實頁，可使系統(tǒng)總的命中率最高？系統(tǒng)總的命中率是多少？二、虛擬存貯器影響H的主要因素6 影響H的主要因素（1）頁面替換算法（2）頁地址流（3）所分配到的實頁數(shù)（4）頁面的大?。?）主存容量等多種因素有關(guān)。二、虛擬存貯器提高虛擬存儲器等效訪問速度的措施理論依據(jù)：程序的局部性特點。硬件支持：小容量快速存儲器。那些地方還可繼續(xù)改進？ 24 12 12 二、虛擬存貯器提高虛擬存儲器等效訪問速度的措施理論依據(jù)：一段時間內(nèi)快表對應(yīng)一個用戶或任務(wù)。1 有什么缺陷？2 如何改進？ 24 12 12 二

19、、虛擬存貯器提高虛擬存儲器等效訪問速度的措施第三步：改進快表1 有什么缺陷？ 如何改進？2那些地方還可繼續(xù)改進？二、虛擬存貯器提高虛擬存儲器等效訪問速度的措施三、高速緩沖存貯器 Cache存貯器和虛擬存貯器在工作原理上并沒有本質(zhì)上的區(qū)別，只是因為Cache存貯器的訪問速度要求很高，所以在虛實地址字段的對應(yīng)關(guān)系、信息塊大小的劃分、虛實地址映象規(guī)則、映象表機構(gòu)、地址的變換和替換算法的實現(xiàn)、透明性及性能分析上有著較大的差異。三、高速緩沖存貯器1 Cache的工作原理分和主存為大小相等的塊，為了加速調(diào)塊，一般讓Cache塊的大小取成主存在一個主存周期里能訪問到的字節(jié)數(shù)。因此，主存貯器都采用模m多分體多

20、字交叉并行訪問的組織形式。受主存實際效率的影響，模數(shù)m不可能很高，使得Cache塊的大小一般只有十幾到幾十個字節(jié)，只是虛擬存貯器頁面大小的幾十分之一；三、高速緩沖存貯器2 地址的映象與變換 在Cache存貯器中，所謂地址的映象就是讓主存塊能裝入到物理Cache中的哪些塊位置的規(guī)則。映象規(guī)則好壞的評價標準：進行地址映象和變換所需增加的輔助硬件是否少；價格是否便宜；地址變換的速度是否高；實現(xiàn)是否方便；Cache的塊沖突概率是否比較低；物理Cache的空間利用率是否比較高。三、高速緩沖存貯器全相聯(lián)映象是在主存和Cache都機械等分成相同大小的塊后，讓主存中的任何一個塊均可以映象裝入到Cache中任何

21、一個塊位置上。三、高速緩沖存貯器全相聯(lián)映象優(yōu)點：Cache塊沖突概率最低Cache空間利用率最高全相聯(lián)映象缺點：目錄表容量太大，成本極高。結(jié)論：無法實用。Why?三、高速緩沖存貯器直接映象是在主存和Cache都機械等分成相同大小的塊后，再將主存空間按物理Cache大小等分成區(qū)，讓主存中每一個區(qū)中的各個塊均只能按位置一一對應(yīng)裝入Cache中相應(yīng)的塊位置上。也就是說，當物理Cache共有n個塊位置時，讓主存第i塊只能唯一映象裝入到物理Cache的第i mod n塊位置上。三、高速緩沖存貯器直接映象優(yōu)點：目錄表所需的硬件量很少，成本低，易于實現(xiàn)。采用直接映象時，查表找區(qū)號可以與訪物理Cache同時進

22、行。所以Cache的實際訪問速度很快。直接映象缺點：Cache塊沖突的概率很高，Cache的空間利用率很低。結(jié)論：現(xiàn)在已很少使用。Why?三、高速緩沖存貯器組相聯(lián)映象規(guī)則：分Cache和主存為大小相等的塊；Cache分為幾個大小相同的組，并順序編號；主存各區(qū)以同樣方式分組，使的主存每區(qū)組數(shù)等于Cache的組數(shù)，各區(qū)的分組單獨順序編號；主存和Cache各組內(nèi)的塊也單獨順序編號（以組為單位），一般從0開始；主存的組與Cache的組通過組號直接映象，組內(nèi)塊間全相聯(lián)映象；三、高速緩沖存貯器三、高速緩沖存貯器地址映象和變換通過目錄表來完成， Cache分幾組，目錄表有幾個；組內(nèi)有幾塊，目錄表有幾行，每行

23、有三個字段：區(qū)號（nd）、主存組內(nèi)塊號（S）、 Cache組內(nèi)塊號（S）；可否改進？三、高速緩沖存貯器一種改進方法：通常所有目錄表存于一個單體多字存儲器中，每存儲單元字數(shù)m= Cache每組內(nèi)塊數(shù)， Cache有幾組，存儲器有幾行（存儲單元），存儲器設(shè)有m個相等比較電路，按地址訪問，按內(nèi)容相聯(lián)比較。三、高速緩沖存貯器例4 Cache一主存存貯層次中，主存有07共8塊，Cache為4塊，采用組相聯(lián)映象。假設(shè)Cache已先后訪問并預取進了主存的第5、1、3、7塊，現(xiàn)訪存塊地址流又為1、2、4、1、3、7、0、1、2、5、4、6時， (1)畫出用LRU替換算法，Cache內(nèi)各塊的實際替換過程圖，并標

24、出命中時刻。其中Cache分為兩組。 (2)求出在此期間的Cache命中率。三、高速緩沖存貯器例5 Cache分S116塊，主存分S2256塊，讓主存第i塊映象裝入到Cache中的第j塊，jI mod Sl。 (1)這是什么映象規(guī)則? (2)畫出主存地址到Cache地址變換過程的示意圖，圖中應(yīng)標識出主存與Cache地址各字段位數(shù)及對應(yīng)關(guān)系；指出用于地址映象變換的輔助表存貯器的寬度和單元數(shù)；對變換過程作簡單的文字說明。三、高速緩沖存貯器 3 提高Cache命中率的取算法 Cache的取算法會影響到Cache的塊命中率。按需取進法是在Cache發(fā)生塊失效時才去調(diào)塊。預取法是在將要用到某塊之前，就已經(jīng)將該塊預先取進Cache中了。 預取算法具體又有恒預取法和不命中時預取法兩種。恒預取法是在訪問到主存第i塊的信息時，不管其是否在Cache中命中，恒將主存第 i +1塊預取進Cache。不命中