現(xiàn)代計(jì)算機(jī)系統(tǒng)以存儲(chǔ)器為中心3.1存儲(chǔ)系統(tǒng)原理3.2虛擬存儲(chǔ)器3.3高速緩沖存儲(chǔ)器(Cache)3.4三級(jí)存儲(chǔ)系統(tǒng)第3章存儲(chǔ)系統(tǒng)10/18/20221計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第三章存儲(chǔ)系統(tǒng)3.1存存儲(chǔ)系系統(tǒng)原理理3.1..1存存儲(chǔ)系統(tǒng)統(tǒng)的定義義3.1..2存存儲(chǔ)系統(tǒng)統(tǒng)的層次次結(jié)構(gòu)3.1..3存存儲(chǔ)系統(tǒng)統(tǒng)的頻帶帶平衡3.1..4并并行訪問(wèn)問(wèn)存儲(chǔ)器器3.1..5交交叉訪問(wèn)問(wèn)存儲(chǔ)器器3.1..6無(wú)無(wú)沖突訪訪問(wèn)存儲(chǔ)儲(chǔ)器2/28/20202計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.1..1存存儲(chǔ)系統(tǒng)統(tǒng)的定義義在一臺(tái)計(jì)計(jì)算機(jī)中中，通常常有多種種存儲(chǔ)器器種類(lèi)：主存儲(chǔ)器器、Cache、通用用寄存器器、緩沖沖存儲(chǔ)器器、磁盤(pán)盤(pán)存儲(chǔ)器器、磁帶帶存儲(chǔ)器器、光盤(pán)盤(pán)存儲(chǔ)器器等材料工藝藝：ECL、、TTL、MOS、磁磁表面、、激光，，SRAM，DRAM訪問(wèn)方式式：隨機(jī)訪問(wèn)問(wèn)、直接接譯碼、、先進(jìn)先先出、相相聯(lián)訪訪問(wèn)、塊塊傳送送、文件件組2/28/20203計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)存儲(chǔ)器的的主要性性能：速度、容容量、價(jià)價(jià)格速度用存儲(chǔ)器器的訪問(wèn)問(wèn)周期、、讀出時(shí)時(shí)間、頻頻帶寬度度等表示示。容量用字節(jié)B、千字字節(jié)KB、兆字字節(jié)MB和千兆兆字節(jié)GB等單單位表示示。價(jià)格用單位容容量的價(jià)價(jià)格表示示，例如如：$C/bit。組成存儲(chǔ)儲(chǔ)系統(tǒng)的的關(guān)鍵：：把速度、、容量和和價(jià)格不不同的多多個(gè)物理理存儲(chǔ)器器組織成成一個(gè)存存儲(chǔ)器，，這個(gè)存存儲(chǔ)器的的速度最最快，存存儲(chǔ)容量量最大，，單位容容量的價(jià)價(jià)格最便便宜。2/28/20204計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)1.存存儲(chǔ)系統(tǒng)統(tǒng)的定義義兩個(gè)或兩兩個(gè)以上上速度、、容量和和價(jià)格各各不相同同的存儲(chǔ)儲(chǔ)器用硬硬件、軟軟件、或或軟件與與硬件相相結(jié)合的的方法連連接起來(lái)來(lái)成為一一個(gè)存儲(chǔ)儲(chǔ)系統(tǒng)。。這個(gè)存存儲(chǔ)系統(tǒng)統(tǒng)對(duì)應(yīng)用用程序員員是透明明的，并并且，從從應(yīng)用程程序員看看，它是是一個(gè)存存儲(chǔ)器，，這個(gè)存存儲(chǔ)器的的速度接接近速度度最快的的那個(gè)存存儲(chǔ)器，，存儲(chǔ)容容量與容容量最大大的那個(gè)個(gè)存儲(chǔ)器器相等，，單位容容量的價(jià)價(jià)格接近近最便宜宜的那個(gè)個(gè)存儲(chǔ)器器。虛擬存儲(chǔ)儲(chǔ)器系統(tǒng)統(tǒng)：對(duì)應(yīng)應(yīng)用程序序員透明明Cache存儲(chǔ)儲(chǔ)系統(tǒng)：：對(duì)系統(tǒng)統(tǒng)程序員員以上均均透明2/28/20205計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)由多個(gè)存存儲(chǔ)器構(gòu)構(gòu)成的存存儲(chǔ)系統(tǒng)統(tǒng)2/28/20206計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)在一般計(jì)計(jì)算機(jī)系系統(tǒng)中，，有兩種種存儲(chǔ)系系統(tǒng)：Cache存儲(chǔ)儲(chǔ)系統(tǒng)：：由Cache和主存存儲(chǔ)器構(gòu)構(gòu)成主要目的的：提高高存儲(chǔ)器器速度2/28/20207計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)虛擬存儲(chǔ)儲(chǔ)系統(tǒng)：：由主存存儲(chǔ)器和和硬盤(pán)構(gòu)構(gòu)成主要目的的：擴(kuò)大大存儲(chǔ)器器容量2/28/20208計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2.存儲(chǔ)儲(chǔ)系統(tǒng)的的容量要求：提供盡可可能大的的地址空空間能夠隨機(jī)機(jī)訪問(wèn)方法有兩兩種：只對(duì)系統(tǒng)統(tǒng)中存儲(chǔ)儲(chǔ)容量最最大的那那個(gè)存儲(chǔ)儲(chǔ)器進(jìn)行行編址，，其他存存儲(chǔ)器只只在內(nèi)部部編址或或不編址址Cache存儲(chǔ)儲(chǔ)系統(tǒng)另外設(shè)計(jì)計(jì)一個(gè)容容量很大大的邏輯輯地址空空間，把把相關(guān)存存儲(chǔ)器都都映射這這個(gè)地址址空間中中虛擬存儲(chǔ)儲(chǔ)系統(tǒng)2/28/20209計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.存儲(chǔ)儲(chǔ)系統(tǒng)的的價(jià)格計(jì)算公式式：當(dāng)S2》》S1時(shí)時(shí)，C≈≈C2S2與S1不能能相差太太大2/28/202010計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)4.存存儲(chǔ)系統(tǒng)統(tǒng)的速度度表示方法法：訪問(wèn)周期期、存取取周期、、存儲(chǔ)周周期、存存取時(shí)間間等命中率定定義：在M1存存儲(chǔ)器中中訪問(wèn)到到的概率率

其中：N1是對(duì)對(duì)M1存存儲(chǔ)器的的訪問(wèn)次次數(shù)N2是對(duì)對(duì)M2存存儲(chǔ)器的的訪問(wèn)次次數(shù)訪問(wèn)周期期與命中中率的關(guān)關(guān)系：T＝HT1＋((1－H)T2當(dāng)命中率率H→1時(shí)，T→T12/28/202011計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)統(tǒng)的訪問(wèn)問(wèn)效率：：訪問(wèn)效率率主要與與命中率率和兩級(jí)級(jí)存儲(chǔ)器器的速度度之比有有關(guān)例3.1：假設(shè)T2＝５T１，在命中中率H為為0.9和0..99兩兩種情況況下，分分別計(jì)算算存儲(chǔ)系系統(tǒng)的訪訪問(wèn)效率率。解：當(dāng)H＝0.9時(shí)時(shí)，e1＝1／((0.9＋5((1－0.9)))＝0.72當(dāng)H＝0.99時(shí)，e2＝1／((0.99＋5(1－－0.99)))＝0..962/28/202012計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)提高存儲(chǔ)儲(chǔ)系統(tǒng)速速度的兩兩條途徑徑：一是提高高命中率率H，二是兩個(gè)個(gè)存儲(chǔ)器器的速度度不要相相差太大大其中：第第二條有有時(shí)做不不到(如如虛擬存存儲(chǔ)器))，這時(shí)時(shí)，只能能依靠提高高命中率率例3.2：在虛擬存存儲(chǔ)系統(tǒng)統(tǒng)中，兩兩個(gè)存儲(chǔ)儲(chǔ)器的速速度相差差特別懸懸殊，例例如：T2＝105T１。如果要要使訪問(wèn)問(wèn)效率到到達(dá)e＝＝0.9，問(wèn)需需要有多多高的命命中率？？2/28/202013計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)解：0.9H＋90000(1--H)＝＝189999.1H＝＝89999計(jì)算得：：H＝0..999998888877777…≈0.9999995.采采用預(yù)取取技術(shù)提提高命中中率方法：不命中時(shí)時(shí)，把M2存儲(chǔ)儲(chǔ)器中相相鄰多個(gè)個(gè)單元組組成的一一個(gè)數(shù)據(jù)據(jù)塊取出出來(lái)送入入M1存存儲(chǔ)器中中。2/28/202014計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)計(jì)算公式式：其中：H’是采采用預(yù)取取技術(shù)之之后的命命中率H是原來(lái)來(lái)的命中中率n為數(shù)據(jù)據(jù)塊大小小與數(shù)據(jù)據(jù)重復(fù)使使用次數(shù)數(shù)的乘積積例3.3：在一個(gè)Cache存儲(chǔ)儲(chǔ)系統(tǒng)中中，當(dāng)Cache的塊塊大小為為一個(gè)字字時(shí)，命命中率H＝0..8；假假設(shè)數(shù)據(jù)據(jù)的重復(fù)復(fù)利用率率為5，，T2＝＝5T1。計(jì)算塊塊大小為為４個(gè)字字時(shí)，Cache存儲(chǔ)儲(chǔ)系統(tǒng)的的命中率率？并分分別計(jì)算算訪問(wèn)效效率。2/28/202015計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)解：n＝4××5＝20，采用預(yù)取取技術(shù)之之后，命命中率提提高到：：2/28/202016計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)例3.4：在一個(gè)虛虛擬存儲(chǔ)儲(chǔ)系統(tǒng)中中，T2＝105T１，原原來(lái)的命命中率只只有0..8，如如果訪問(wèn)問(wèn)磁盤(pán)存存儲(chǔ)器的的數(shù)據(jù)塊塊大小為為4K字字，并要要求訪問(wèn)問(wèn)效率不不低于0.9，，計(jì)算數(shù)數(shù)據(jù)在主主存儲(chǔ)器器中的重重復(fù)利用用率至少少為多少少？解：假設(shè)數(shù)據(jù)據(jù)在主存存儲(chǔ)器中中的重復(fù)復(fù)利用率率為m，根據(jù)前前面給出出的關(guān)系系，有如如下方程程組：2/28/202017計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)解方程組組：由方程((1)得得到：0.9H+90000-90000H=12/28/202018計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)證明方法法一：采用預(yù)取取技術(shù)之之后，不命中率率(1--H)降降低ｎ倍倍：2/28/202019計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)證明方法法二：在原有命命中率的的計(jì)算公公式中，，把訪問(wèn)問(wèn)次數(shù)擴(kuò)擴(kuò)大到n倍。由由于采用用了預(yù)取取技術(shù)，，命中次次數(shù)為：：nN1＋(n--1)N2,不命中中次數(shù)仍仍為N2，因此新新的命中中率為：：2/28/202020計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.1..2存存儲(chǔ)系統(tǒng)統(tǒng)的層次次結(jié)構(gòu)多個(gè)層次次的存儲(chǔ)儲(chǔ)器：第1層：：RegisterFiles((寄存器堆堆)第2層：：Buffers((Lookahead)(先先行緩沖沖站)第3層：：Cache(高速速緩沖存存儲(chǔ)器))第4層：：MainMemory(主存存儲(chǔ)器))第5層：：OnlineStorage(聯(lián)機(jī)機(jī)存儲(chǔ)器器)第6層：：Off-lineStorage((脫機(jī)存存儲(chǔ)器))用i表示層數(shù)數(shù)，則有：工作周期期Ti＜Ti+1，存儲(chǔ)容量量：Si＜Si+1，單位價(jià)格格：Ci＞Ci+12/28/202021計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)各級(jí)存儲(chǔ)儲(chǔ)器的主主要主要要性能特特性CPU與與主存儲(chǔ)儲(chǔ)器的速速度差距距越來(lái)越越大目前相差差兩個(gè)數(shù)量量級(jí)今后CPU與主主存儲(chǔ)器器的速度度差距會(huì)會(huì)更大2/28/202023計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.1..3存存儲(chǔ)系統(tǒng)統(tǒng)的頻帶帶平衡例3.5：Pentium4的指指令執(zhí)行行速度為為8GIPS，，CPU取指令令8GW/s，，訪問(wèn)數(shù)數(shù)據(jù)16GW//s，各各種輸入入輸出設(shè)設(shè)備訪問(wèn)問(wèn)存儲(chǔ)器器1GW/s，，三項(xiàng)相相加，要要求存儲(chǔ)儲(chǔ)器的頻頻帶寬度度不低于于25GW/s。如果采用用PC133內(nèi)內(nèi)存，主主存與CPU速速度差188倍倍如果采用用PC266內(nèi)內(nèi)存，主主存與CPU速速度差94倍解決存儲(chǔ)儲(chǔ)器頻帶帶平衡方方法(1)多多個(gè)存儲(chǔ)儲(chǔ)器并行行工作（（本節(jié)下下面介紹紹）(2)設(shè)設(shè)置各種種緩沖存存儲(chǔ)器（（第五章章介紹））(3)采采用存儲(chǔ)儲(chǔ)系統(tǒng)（（本章第第二、第第三節(jié)介介紹）2/28/202024計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.1..4并并行訪問(wèn)問(wèn)存儲(chǔ)器器方法：把m字w位的存存儲(chǔ)器改改變成為為m/n字n××w位的的存儲(chǔ)器器邏輯實(shí)現(xiàn)現(xiàn)：把地址碼碼分成兩兩個(gè)部分分，一部部分作為為存儲(chǔ)器器的地址址另一部部分負(fù)責(zé)責(zé)選擇數(shù)數(shù)據(jù)主要缺點(diǎn)點(diǎn)：訪問(wèn)問(wèn)沖突大大(1)取取指令沖沖突(2)讀讀操作數(shù)數(shù)沖突(3)寫(xiě)寫(xiě)數(shù)據(jù)沖沖突(4)讀讀寫(xiě)沖突突2/28/202025計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)并行訪問(wèn)問(wèn)存儲(chǔ)器器結(jié)構(gòu)框框圖2/28/202026計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)1.高高位交叉叉訪問(wèn)存存儲(chǔ)器主要目的的：擴(kuò)大存儲(chǔ)儲(chǔ)器容量量實(shí)現(xiàn)方法法：用地址碼碼的高位位部分區(qū)區(qū)分存儲(chǔ)儲(chǔ)體號(hào)參數(shù)計(jì)算算方法::m：每個(gè)個(gè)存儲(chǔ)體體的容量量，n：總共共的存儲(chǔ)儲(chǔ)體個(gè)數(shù)數(shù)，j：存儲(chǔ)儲(chǔ)體的體體內(nèi)地址址，j＝＝0，1，2，，....，m--1k：存儲(chǔ)儲(chǔ)體的體體號(hào)，k＝0，，1，2，....，n-1存儲(chǔ)器的的地址：：A＝m×k＋＋j存儲(chǔ)器的的體內(nèi)地地址：Aj＝Amodm。存儲(chǔ)器的的體號(hào)：：Ak＝3.1..5交交叉訪問(wèn)問(wèn)存儲(chǔ)器器2/28/202027計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)高位交叉叉訪問(wèn)存存儲(chǔ)器結(jié)結(jié)構(gòu)框圖圖2/28/202028計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)例3.6：用4M字××4位的的存儲(chǔ)芯芯片組成成16M×32位的主主存儲(chǔ)器器。共用用存儲(chǔ)芯芯片：用最高2位地址址經(jīng)譯碼碼后產(chǎn)生生的信號(hào)號(hào)，控制制各組存存儲(chǔ)芯片片CS。。每組中的的32根根數(shù)據(jù)線線分別對(duì)對(duì)應(yīng)直接接相連，，稱(chēng)為““線或””方式。。2/28/202029計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2/28/202030計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2.低低位交叉叉訪問(wèn)存存儲(chǔ)器主要目的的：提高存儲(chǔ)儲(chǔ)器訪問(wèn)問(wèn)速度實(shí)現(xiàn)方法法：用地址碼碼的低位位部分區(qū)區(qū)分存儲(chǔ)儲(chǔ)體號(hào)參數(shù)計(jì)算算:m：每個(gè)個(gè)存儲(chǔ)體體的容量量，n：總共共的存儲(chǔ)儲(chǔ)體個(gè)數(shù)數(shù)，j：存儲(chǔ)儲(chǔ)體的體體內(nèi)地址址，j＝＝0，1，2，，....，m--1k：存儲(chǔ)儲(chǔ)體的體體號(hào)，k＝0，，1，2，....，n-1存儲(chǔ)器地地址A的的計(jì)算公公式為：：A＝n×j＋＋k存儲(chǔ)器的的體內(nèi)地地址：Aj＝存儲(chǔ)器的的體號(hào)：：Ak＝Amodn2/28/202031計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)低位交叉叉訪問(wèn)存存儲(chǔ)器結(jié)結(jié)構(gòu)框圖圖2/28/202032計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)地址是編編碼方法法：由8個(gè)存存儲(chǔ)體構(gòu)構(gòu)成的低低位交叉叉編址方方式2/28/202033計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)n個(gè)存儲(chǔ)儲(chǔ)體分時(shí)時(shí)啟動(dòng)一種采用用流水線線方式工工作的并并行存儲(chǔ)儲(chǔ)器每存儲(chǔ)體體的啟動(dòng)動(dòng)間隔為為：t＝＝其中：Tm為每個(gè)存存儲(chǔ)體的的訪問(wèn)周周期,n為存儲(chǔ)儲(chǔ)體個(gè)數(shù)數(shù)。2/28/202034計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)訪問(wèn)沖突突共有n個(gè)個(gè)存儲(chǔ)體體，每個(gè)個(gè)存儲(chǔ)周周期只能能取到k個(gè)有效效字,其其余n--k個(gè)存存儲(chǔ)體有有沖突。。假設(shè)p((k)是是k的概概率密度度函數(shù)，，即p((1)是是k＝1的概率率，p((2)是是k＝2的概率率，…,,p(n)是k＝n的的概率。。k的平平均值為為：N是每個(gè)個(gè)存儲(chǔ)周周期能夠夠訪問(wèn)到到的平均均有效字字的個(gè)數(shù)數(shù)。通常把N稱(chēng)為并并行存儲(chǔ)儲(chǔ)器的加加速比。。2/28/202035計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)定義轉(zhuǎn)移移概率為為g，即即讀出的的是轉(zhuǎn)移移指令，，且轉(zhuǎn)移移成功的的概率。。這時(shí)有有：p(1))＝gp(2))＝(1-p((1)))g＝((1-g)gp(3))＝(1-p((1)--p(2))g＝(1-g))2g……p(k))＝(1-g))k-1g(k＝1,,2,……,n－－1)……p(n))＝(1-g))n-12/28/202036計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)Ｎ＝g＋(1-g))g＋((1-g)2g＋…＋＋(1--g)n-2g＋(1--g)g＋(1-g))2g＋…＋＋(1--g)n-2g＋(1--g)2g＋…＋＋(1--g)n-2g…＋(1--g)n-2g＋n(1-g))n-1以上共n行，前前n-2行分別別為等比比級(jí)數(shù)把n-1行拆分分成2項(xiàng)項(xiàng)則：Ｎ＝＝1g＋＋2(1-g))g＋3(1--g)2g＋…＋(n--1)((1-g)n-2g＋n((1-g)n-11-(1-g)n-12/28/202037計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)Ｎ＝1-(1-g))n-1＋(1-g)-((1-g)n-1＋(1-g)2-(1--g)n-1…＋(1-g)n-2-(1--g)n-1＋n(1-g))n-1(1-g)n-2gＮ＝1＋＋(1--g)＋＋(1--g)2＋…(1-g))n-2＋(1--g)n-12/28/202038計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2/28/202039計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2/28/202040計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)例3.7：Star-100巨型型機(jī)存儲(chǔ)儲(chǔ)系統(tǒng)采采用并行行和交叉叉相結(jié)合合的方式式工作，，有32個(gè)存儲(chǔ)儲(chǔ)體低位位交叉，，每次并并行讀寫(xiě)寫(xiě)512位，存存儲(chǔ)周期期為1280ns，處處理機(jī)字字長(zhǎng)32位，計(jì)計(jì)算它的的頻帶寬寬度Bm和峰值值速度T。解：因?yàn)椋簄＝32，w＝＝512，Tm＝1280ns，Bm＝nw//tm＝＝32512b/1280ns＝12..8Gb/s＝＝1.6GB//s＝400MW/sT＝2..5ns與Tm相相比，峰峰值速度度提高512倍倍實(shí)際速度度的提高高要遠(yuǎn)遠(yuǎn)遠(yuǎn)小于這這個(gè)數(shù)字字2/28/202041計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.1..6無(wú)無(wú)沖突訪訪問(wèn)存儲(chǔ)儲(chǔ)器1.一一維數(shù)組組(向量量)的無(wú)無(wú)沖突訪訪問(wèn)存儲(chǔ)儲(chǔ)器按連續(xù)地地址訪問(wèn)問(wèn)，沒(méi)有有沖突，，位移量為為2的變變址訪問(wèn)問(wèn)，速度度降低一一倍，……2/28/202042計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)具體方法法：存儲(chǔ)體的的個(gè)數(shù)取取質(zhì)數(shù)，，且n≥≥向量長(zhǎng)長(zhǎng)度。原因：變址位移移量必然然與存儲(chǔ)儲(chǔ)體個(gè)數(shù)數(shù)互質(zhì)例如：Burroughs公公司巨型型科學(xué)計(jì)計(jì)算機(jī)BSP存儲(chǔ)體個(gè)個(gè)數(shù)為17向量長(zhǎng)度度≤16我國(guó)研制制的銀河河巨型向向量機(jī)存儲(chǔ)體的的個(gè)數(shù)為為37向量長(zhǎng)度度≤322/28/202043計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2.二二維數(shù)組組的無(wú)沖沖突訪問(wèn)問(wèn)存儲(chǔ)器器要求：一個(gè)n×n的二維數(shù)數(shù)組，按按行、列列、對(duì)角角線和反反對(duì)角線線訪問(wèn)，，并且在在不同的的變址位位移量情情況下，，都能實(shí)實(shí)現(xiàn)無(wú)沖沖突訪問(wèn)問(wèn)。順序存儲(chǔ)儲(chǔ)：按行、對(duì)對(duì)角線訪訪問(wèn)沒(méi)有有沖突，，但按列列訪問(wèn)每每次沖突突2/28/202044計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)錯(cuò)位存儲(chǔ)儲(chǔ)：按行、按按列訪問(wèn)問(wèn)無(wú)沖突突，但按對(duì)角角線訪問(wèn)問(wèn)有沖突突2/28/202045計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)n×n二二維數(shù)組組無(wú)沖突突訪問(wèn)存存儲(chǔ)方案案(P··Budnik和和D··J··Kuck提提出))：并行存儲(chǔ)儲(chǔ)體的個(gè)個(gè)數(shù)m≥n，并且取取質(zhì)數(shù)，，同時(shí)還還要在行行、列方方向上錯(cuò)錯(cuò)開(kāi)一定定的距離離存儲(chǔ)數(shù)數(shù)組元素素。設(shè)同一列列相鄰元元素在并并行存儲(chǔ)儲(chǔ)器中錯(cuò)錯(cuò)開(kāi)d1個(gè)存儲(chǔ)儲(chǔ)體存放放，同一一行相鄰鄰元素在在并行存存儲(chǔ)器中中錯(cuò)開(kāi)d2個(gè)存存儲(chǔ)體存存放。當(dāng)當(dāng)m＝22p＋1（p為任意意自然數(shù)數(shù)）時(shí)，，能夠同同時(shí)實(shí)現(xiàn)現(xiàn)按行、、按列、、按對(duì)角角線和按按反對(duì)角角線無(wú)沖沖突訪問(wèn)問(wèn)的充要要條件是是：d1＝2P，d2＝＝1。2/28/202046計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)例如：4×4的的二維數(shù)數(shù)組，取取并行存存儲(chǔ)體的的個(gè)數(shù)m＝5，由由關(guān)系式式m＝22P＋1，解解得到p＝1，，計(jì)算得得到：d1＝21＝2d2＝12/28/202047計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)n×n數(shù)組中的的任意一一個(gè)元素素aij在無(wú)沖突突并行存存儲(chǔ)器中中的體號(hào)號(hào)地址和和體內(nèi)地地址的計(jì)計(jì)算公式式：體號(hào)地址址：(2Pi＋j＋＋k)MODm體內(nèi)地址址：i其中：0≤i≤≤n－1，0≤j≤n－1，k是數(shù)組組的第一一個(gè)元素素a00所在體號(hào)號(hào)地址，，m是并行存存儲(chǔ)體的的個(gè)數(shù)，，要求m≥n且為質(zhì)數(shù)數(shù)，p是滿(mǎn)足足m＝22P＋1關(guān)系系的任意意自然數(shù)數(shù)。主要缺點(diǎn)點(diǎn)：浪費(fèi)存儲(chǔ)儲(chǔ)單元對(duì)于n×n數(shù)組,有有(m-n)×m個(gè)存儲(chǔ)單單元浪費(fèi)費(fèi)主要優(yōu)點(diǎn)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單單列元素順順序存儲(chǔ)儲(chǔ)，行元元素按地地址取模模順序存存儲(chǔ)483.二二維數(shù)組組的無(wú)沖沖突訪問(wèn)問(wèn)存儲(chǔ)器器(之二二)規(guī)則：對(duì)于任意意一個(gè)n×n的數(shù)組，如如果能夠夠找到滿(mǎn)滿(mǎn)足n＝22P關(guān)系的任任意自然然數(shù)p，，則這個(gè)個(gè)二維數(shù)數(shù)組就能能夠使用用n個(gè)并行存存儲(chǔ)體實(shí)現(xiàn)按行行、列、、對(duì)角線線和反對(duì)對(duì)角線的的無(wú)沖突突訪問(wèn)。。4×4數(shù)數(shù)組用4個(gè)存儲(chǔ)儲(chǔ)體的無(wú)無(wú)訪問(wèn)沖沖突存儲(chǔ)儲(chǔ)方案2/28/202049計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)實(shí)現(xiàn)方法法：假設(shè)aij是4×4數(shù)數(shù)組中的的任意一一個(gè)元素素，下標(biāo)i和和j都可可以用兩兩位二進(jìn)進(jìn)制表示示。假設(shè)設(shè)i和j的高位位和低位位分別為為iH、iL、jH和jL，則aij在無(wú)沖突突并行存存儲(chǔ)器中中的體號(hào)號(hào)地址和和體內(nèi)地地址如下下：體號(hào)地址址：2((iLjH)＋(iHiLjL)體內(nèi)地址址：j其中：0≤i≤≤3，0≤j≤≤3主要優(yōu)點(diǎn)點(diǎn)：沒(méi)有浪費(fèi)費(fèi)的存儲(chǔ)儲(chǔ)單元，主要缺點(diǎn)點(diǎn)：在執(zhí)行并并行讀和和寫(xiě)操作作時(shí)需要要借助比比較復(fù)雜雜的對(duì)準(zhǔn)準(zhǔn)網(wǎng)絡(luò)。2/28/202050計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.2..1虛虛擬存儲(chǔ)儲(chǔ)器工作作原理3.2..2地地址的映映象和變變換方法法3.2..3加加快內(nèi)部部地址變變換的方方法3.2..4頁(yè)頁(yè)面替換換算法及及其實(shí)現(xiàn)現(xiàn)3.2..5提提高主存存命中率率的方法法3.2虛虛擬存存儲(chǔ)器2/28/202051計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.2..1虛虛擬存儲(chǔ)儲(chǔ)器工作作原理也稱(chēng)為虛虛擬存儲(chǔ)儲(chǔ)系統(tǒng)、、虛擬存存儲(chǔ)體系系等其概念由由英國(guó)曼曼徹斯特特大學(xué)的的Kilbrn等人于于1961年提提出到70年年代廣泛泛應(yīng)用于于大中型型計(jì)算機(jī)機(jī)系統(tǒng)目前，許許多微型型機(jī)也使使用虛擬擬存儲(chǔ)器器把主存儲(chǔ)儲(chǔ)器、磁磁盤(pán)存儲(chǔ)儲(chǔ)器和虛虛擬存儲(chǔ)儲(chǔ)器都劃劃分成固固定大小小的頁(yè)主存儲(chǔ)器器的頁(yè)稱(chēng)稱(chēng)為實(shí)頁(yè)頁(yè)虛擬存儲(chǔ)儲(chǔ)器中的的頁(yè)稱(chēng)為為虛頁(yè)2/28/202052計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)內(nèi)部地址址變換：：多用戶(hù)虛虛擬地址址Av變換成主主存實(shí)地地址A多用戶(hù)虛虛擬地址址中的頁(yè)頁(yè)內(nèi)偏移移D直接接作為主主存實(shí)地地址中的的頁(yè)內(nèi)偏偏移d，，主存實(shí)頁(yè)頁(yè)號(hào)p與與它的頁(yè)頁(yè)內(nèi)偏移移d直接接拼接起起來(lái)就得得到主存存實(shí)地址址A。2/28/202053計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.2..2地地址的映映象與變變換三種地址址空間：：虛擬地址址空間主存儲(chǔ)器器地址空空間輔存地址址空間地址映象象：把虛擬地地址空間間映象到到主存地地址空間間地址變換換：在程序運(yùn)運(yùn)行時(shí)，，把虛地地址變換換成主存存實(shí)地址址三種虛擬擬存儲(chǔ)器器：頁(yè)式虛擬擬存儲(chǔ)器器段式虛擬擬存儲(chǔ)器器段頁(yè)式虛虛擬存儲(chǔ)儲(chǔ)器2/28/202055計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)1.段段式虛擬擬存儲(chǔ)器器地址映象象方法：：每個(gè)程序序段都從從0地址址開(kāi)始編編址，長(zhǎng)長(zhǎng)度可長(zhǎng)長(zhǎng)可短，，可以在在程序執(zhí)執(zhí)行過(guò)程程中動(dòng)態(tài)態(tài)改變程程序段的的長(zhǎng)度。。地址變換換方法：：由用戶(hù)號(hào)號(hào)找到基基址寄存存器，讀讀出段表表起始地地址，與與虛地址址中段號(hào)號(hào)相加得得到段表表地址，，把段表表中的起起始地址址與段內(nèi)內(nèi)偏移D相加就就能得到到主存實(shí)實(shí)地址。。主要優(yōu)點(diǎn)點(diǎn)：(1)程程序的模模塊化性性能好。。(2)便便于程序序和數(shù)據(jù)據(jù)的共享享。(3)程程序的動(dòng)動(dòng)態(tài)鏈接接和調(diào)度度比較容容易。(4)便便于實(shí)現(xiàn)現(xiàn)信息保保護(hù)。主要缺點(diǎn)點(diǎn)：(1)地地址變換換所花費(fèi)費(fèi)的時(shí)間間長(zhǎng)，兩兩次加法法(2)主主存儲(chǔ)器器的利用用率往往往比較低低。(3)對(duì)對(duì)輔存（（磁盤(pán)存存儲(chǔ)器））的管理理比較困困難。2/28/202058計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2.頁(yè)頁(yè)式虛擬擬存儲(chǔ)器器地址映象象方法：：地址變換換方法：：2/28/202060計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)主要優(yōu)點(diǎn)點(diǎn)：(1)主主存儲(chǔ)器器的利用用率比較較高(2)頁(yè)頁(yè)表相對(duì)對(duì)比較簡(jiǎn)簡(jiǎn)單(3)地地址變換換的速度度比較快快(4)對(duì)對(duì)磁盤(pán)的的管理比比較容易易主要缺點(diǎn)點(diǎn)：(1)程程序的模模塊化性性能不好好(2)頁(yè)頁(yè)表很長(zhǎng)長(zhǎng)，需要要占用很很大的存存儲(chǔ)空間間例如：虛擬存儲(chǔ)儲(chǔ)空間4GB，，頁(yè)大小小1KB，則頁(yè)頁(yè)表的容容量為4M字，，16MB。2/28/202061計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.段段頁(yè)式虛虛擬存儲(chǔ)儲(chǔ)器用戶(hù)按段段寫(xiě)程序序,每每段分成成幾個(gè)固固定大小小的頁(yè)地址映象象方法：：每個(gè)程序序段在段段表中占占一行，，在段表中中給出頁(yè)頁(yè)表長(zhǎng)度度和頁(yè)表表的起始始地址，，頁(yè)表中給給出每一一頁(yè)在主主存儲(chǔ)器器中的實(shí)實(shí)頁(yè)號(hào)。。地址變換換方法：：先查段表表，得到到頁(yè)表起起始地址址和頁(yè)表表長(zhǎng)度，，再查頁(yè)表表找到要要訪問(wèn)的的主存實(shí)實(shí)頁(yè)號(hào)，，把實(shí)頁(yè)號(hào)號(hào)p與頁(yè)頁(yè)內(nèi)偏移移d拼接接得到主主存實(shí)地地址。4.外外部地址址變換每個(gè)程序序有一張張外頁(yè)表表，每一一頁(yè)或每每個(gè)程序序段，在在外頁(yè)表表中都有有對(duì)應(yīng)的的一個(gè)存存儲(chǔ)字。。3.2..3加加快內(nèi)部部地址變變換的方方法造成虛擬擬存儲(chǔ)器器速度降降低的主主要原因因：(1)要要訪問(wèn)問(wèn)主存儲(chǔ)儲(chǔ)器必須須先查段段表或頁(yè)頁(yè)表，(2)可可能需需要多級(jí)級(jí)頁(yè)表。。頁(yè)表級(jí)數(shù)數(shù)的計(jì)算算公式：：其中：Nv為為虛擬存存儲(chǔ)空間間大小，，Np為頁(yè)頁(yè)面的大大小，Nd為一一個(gè)頁(yè)表表存儲(chǔ)字字的大小小2/28/202065計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)例如：虛擬存儲(chǔ)儲(chǔ)空間大大小Nv＝4GB，頁(yè)頁(yè)的大小小Np＝＝1KB，每個(gè)個(gè)頁(yè)表存存儲(chǔ)字占占用4個(gè)個(gè)字節(jié)。。計(jì)算得得到頁(yè)表表的級(jí)數(shù)數(shù)：通常僅把把1級(jí)頁(yè)頁(yè)表和2、3級(jí)級(jí)頁(yè)表中中的一小小部分駐駐留在主主存中2/28/202066計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)1.目錄錄表基本思想想：用一個(gè)小小容量高高速存儲(chǔ)儲(chǔ)器存放放頁(yè)表地址變換換過(guò)程：：把多用戶(hù)戶(hù)虛地址址中U與與P拼接接，相聯(lián)聯(lián)訪問(wèn)目目錄表。。讀出主主存實(shí)頁(yè)頁(yè)號(hào)p，，把p與與多用戶(hù)戶(hù)虛地址址中的D拼接得得到主存存實(shí)地址址。如果果相聯(lián)訪訪問(wèn)失敗敗，發(fā)出出頁(yè)面失失效請(qǐng)求求。主要優(yōu)點(diǎn)點(diǎn)：與頁(yè)表放放在主存存中相比比，查表表速度快快。主要缺點(diǎn)點(diǎn)：可擴(kuò)展性性比較差差,主存儲(chǔ)器器容量大大時(shí)，目目錄表造造價(jià)高，，速度低低。2/28/202068計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2.快快慢表快表：TLB((TranslationLookasideBuffer)：小容量((幾～幾幾十個(gè)字字)，高速硬件件實(shí)現(xiàn)，，采用相聯(lián)聯(lián)方式訪訪問(wèn)。慢表：當(dāng)快表中中查不到到時(shí)，從從主存的的慢表中中查找；；慢表按地地址訪問(wèn)問(wèn)；用軟軟件實(shí)現(xiàn)現(xiàn)?？毂砼c慢慢表也構(gòu)構(gòu)成一個(gè)個(gè)兩級(jí)存存儲(chǔ)系統(tǒng)統(tǒng)。主要存在在問(wèn)題：：相聯(lián)訪問(wèn)問(wèn)實(shí)現(xiàn)困困難，速速度低2/28/202070計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.散散列函數(shù)數(shù)目的：把相聯(lián)訪訪問(wèn)變成成按地址址訪問(wèn)散列(Hashing)函數(shù)數(shù)：Ah＝H(Pv)采用散列列變換實(shí)實(shí)現(xiàn)快表表按地址址訪問(wèn)避免散列列沖突：：采用相等等比較器器地址變換換：相等比較較與訪問(wèn)問(wèn)存儲(chǔ)器器同時(shí)進(jìn)進(jìn)行4.虛擬擬存儲(chǔ)器器舉例例3.8：IMB370//168計(jì)算機(jī)機(jī)的虛擬擬存儲(chǔ)器器中的快快表結(jié)構(gòu)構(gòu)及地址址變換過(guò)過(guò)程。虛擬地址址長(zhǎng)36位，頁(yè)頁(yè)面大小小為4KB，每每個(gè)用戶(hù)戶(hù)最多占占用4K個(gè)頁(yè)頁(yè)面，最最多允許許16G個(gè)用戶(hù)戶(hù)，但同同時(shí)上機(jī)機(jī)的用戶(hù)戶(hù)數(shù)一般般不超過(guò)過(guò)6個(gè)。。采用了兩兩項(xiàng)新的的措施：：(1)采采用兩個(gè)個(gè)相等比比較器，，以減少少散列沖沖突。(2)用用一個(gè)相相聯(lián)寄存存器組，，把24位用的的多戶(hù)號(hào)號(hào)U壓縮縮成3位位，以縮縮短快表表的長(zhǎng)度度。2/28/202073計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.2..4頁(yè)頁(yè)面替換換算法及及其實(shí)現(xiàn)現(xiàn)1.頁(yè)頁(yè)面替換換發(fā)生時(shí)時(shí)間：當(dāng)發(fā)生頁(yè)頁(yè)面失效效時(shí)，要要從磁盤(pán)盤(pán)中調(diào)入入一頁(yè)到到主存。。如果主主存儲(chǔ)器器的所有有頁(yè)面都都已經(jīng)被被占用，，必須從從主存儲(chǔ)儲(chǔ)器中淘淘汰掉一一個(gè)不常常使用的的頁(yè)面，，以便騰騰出主存存空間來(lái)來(lái)存放新新調(diào)入的的頁(yè)面。。2.評(píng)評(píng)價(jià)頁(yè)面面替換算算法好壞壞的標(biāo)準(zhǔn)準(zhǔn)：一是命中中率要高高，二是算法法要容易易實(shí)現(xiàn)。。2/28/202075計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.頁(yè)頁(yè)面替換換算法的的使用場(chǎng)場(chǎng)合：(1)虛虛擬存儲(chǔ)儲(chǔ)器中，，主存頁(yè)頁(yè)面的替替換，一一般用軟軟件實(shí)現(xiàn)現(xiàn)。(2)Cache中的的塊替換換，一般般用硬件件實(shí)現(xiàn)。。(3)虛虛擬存儲(chǔ)儲(chǔ)器的快快慢表中中，快表表存儲(chǔ)字字的替換換，用硬硬件實(shí)現(xiàn)現(xiàn)。(4)虛虛擬存儲(chǔ)儲(chǔ)器中，，用戶(hù)基基地址寄寄存器的的替換，，用硬件件實(shí)現(xiàn)。。(5)在在有些虛虛擬存儲(chǔ)儲(chǔ)器中，，目錄表表的替換換。2/28/202076計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)4.主主要頁(yè)面面替換算算法(1)隨機(jī)算法法（RANDrandomalgorithm）算法簡(jiǎn)單單，容易易實(shí)現(xiàn)。。沒(méi)有利用用歷史信信息，沒(méi)沒(méi)有反映映程序的的局部性性命中率低低。(2)先進(jìn)先出出算法(FIFOfirst-infirst-outalgorithm)容易實(shí)現(xiàn)現(xiàn)，利用用了歷史史信息，，沒(méi)有反映映局部性性。最先調(diào)入入的頁(yè)面面，很可可能也是是要使用用的頁(yè)面面2/28/202077計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)(3)近近期最少少使用算算法(LFUleastfrequentlyusedalgorithm))：既充充分利用用了歷史史信息，，又反映映了程序序的局部部性實(shí)現(xiàn)現(xiàn)起來(lái)非非常困難難。(4)最最久沒(méi)有有使用算算法(LRUleastrecentlyusedalgorithm))：把LFU算法中中的“多多”與““少”簡(jiǎn)簡(jiǎn)化成““有”與與“無(wú)””，實(shí)現(xiàn)現(xiàn)比較容容易(5)最最優(yōu)替換換算法（OPToptimalreplacementalgorithm）：是是一種理理想算法法，僅用用作評(píng)價(jià)價(jià)其它頁(yè)頁(yè)面替換換算法好好壞的標(biāo)標(biāo)準(zhǔn)。在虛擬存存儲(chǔ)器中中，實(shí)際際上可能能采用的的只有FIFO和LRU兩種種算法。。2/28/202078計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)例3.9：一個(gè)程序序共有5個(gè)頁(yè)面面組成，，在程序序執(zhí)行過(guò)過(guò)程中，，頁(yè)面地地址流如如下：P1，P2，P1，P5，P4，P1，P3，P4，P2，P4假設(shè)分配配給這個(gè)個(gè)程序的的主存只只有3個(gè)個(gè)頁(yè)面。。(1)給給出用FIFO、LRU和OPT三三種頁(yè)面面替換算算法對(duì)這這3個(gè)主主存頁(yè)面面的調(diào)度度情況表表，并統(tǒng)統(tǒng)計(jì)頁(yè)面面命中次次數(shù)。(2)計(jì)計(jì)算這LRU頁(yè)頁(yè)面替換換算法的的頁(yè)面命命中率。。(3)假假設(shè)每個(gè)個(gè)數(shù)據(jù)平平均被訪訪問(wèn)30次，為為了使LRU算算法的失失效率小小于10-5，計(jì)算頁(yè)頁(yè)面大小小至少應(yīng)應(yīng)該為多多少？2/28/202079計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)解：(1)FIFO、LRU和OPT的的頁(yè)面命命中次數(shù)數(shù)分別為為2次、、4次和和5次(2)LRU頁(yè)頁(yè)面替換換算法的的頁(yè)面命命中率為為：Hp＝4/10＝0.4(3)解得P>2000字頁(yè)面大小小應(yīng)該為為2K字字。2/28/202080計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2/28/202081計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)例3.10：一個(gè)循環(huán)環(huán)程序，，依次使使用P1，P2，P3，P4頁(yè)面面，分配配給它的的主存頁(yè)頁(yè)面數(shù)只只有2個(gè)個(gè)。在FIFO和LRU算法法中，發(fā)發(fā)生“顛簸”現(xiàn)象。。5.堆堆棧型替替換算法法定義：對(duì)任意一一個(gè)程序序的頁(yè)地地址流作作兩次主主存頁(yè)面面數(shù)分配配，分別別分配m個(gè)個(gè)主存頁(yè)頁(yè)面和n個(gè)個(gè)主存頁(yè)頁(yè)面，并并且有m≤n。如果果在任何何時(shí)刻t，主主存頁(yè)面面數(shù)集合合Bt都滿(mǎn)滿(mǎn)足關(guān)系系：Bt（m）Bt（n），則這類(lèi)算算法稱(chēng)為為堆棧型型替換算算法。堆棧型算算法的基基本特點(diǎn)點(diǎn)是：隨著分配配給程序序的主存存頁(yè)面數(shù)數(shù)增加，，主存的的命中率率也提高高，至少少不下降降。2/28/202083計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2/28/202084計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.2..5提提高主存存命中率率的方法法影響主存存命中率率的主要要因素：：(1)程程序在執(zhí)執(zhí)行過(guò)程程中的頁(yè)頁(yè)地址流流分布情情況。(2)所所采用的的頁(yè)面替替換算法法。(3)頁(yè)頁(yè)面大小小。(4)主主存儲(chǔ)器器的容量量(5)所所采用的的頁(yè)面調(diào)調(diào)度算法法以下，對(duì)對(duì)后三個(gè)個(gè)因素進(jìn)進(jìn)行分析析。1.頁(yè)面面大小與與命中率率的關(guān)系系頁(yè)面大小小為某個(gè)個(gè)值時(shí)，，命中率率達(dá)到最最大。2/28/202085計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)頁(yè)面大小小與命中中率關(guān)系系的解釋釋?zhuān)杭僭O(shè)At和At+1是相鄰兩兩次訪問(wèn)問(wèn)主存的的邏輯地地址，d＝｜At－At+1｜。如果ｄ＜＜Sp，，隨著Sp增大大，At和At+1在同一頁(yè)頁(yè)面的可可能性增增加，即即Ｈ隨著著Sp的的增大而而提高。。如果ｄ＞＞Sp，，At和At+1一定不在在同一個(gè)個(gè)頁(yè)面內(nèi)內(nèi)。隨著著Sp增增大，主主存頁(yè)面面數(shù)減少少，頁(yè)面面替換更更加頻繁繁。Ｈ隨隨著Sp的增大大而降低低。2/28/202086計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)當(dāng)Sp比比較小的的時(shí)候，，前一種種情況是是主要的的，Ｈ隨隨著Sp的增大大而提高高。當(dāng)Sp達(dá)到到某一個(gè)個(gè)最大值值之后，，后一種種情況成成為主要要的，ＨＨ隨著Sp的增增大而降降低。當(dāng)頁(yè)面增增大時(shí)，，造成的浪費(fèi)費(fèi)也要增增加當(dāng)頁(yè)面減減小時(shí)，，頁(yè)表和頁(yè)面面表在主主存儲(chǔ)器中所所占的比比例將增加2/28/202087計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2.主主存容量量與命中中率的關(guān)關(guān)系主存命中中率H隨隨著分配配給該程程序的主主存容量量S的增增加而單單調(diào)上升升。在S比較較小的時(shí)時(shí)候，H提高得得非?？炜臁ｋS著著S的逐逐漸增加加，H提提高的速速度逐漸漸降低。。當(dāng)S增增加到某某一個(gè)值值之后，，H幾乎乎不再提提高。2/28/202088計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.頁(yè)頁(yè)面調(diào)度度方式與與命中率率的關(guān)系系請(qǐng)求式：：當(dāng)使用到到的時(shí)候候，再調(diào)調(diào)入主存存預(yù)取式：：在程序重重新開(kāi)始始運(yùn)行之之前，把把上次停止運(yùn)行行前一段段時(shí)間內(nèi)內(nèi)用到的的頁(yè)面先先調(diào)入到到主存儲(chǔ)器器，然后后才開(kāi)始始運(yùn)行程程序。預(yù)取式的的主要優(yōu)優(yōu)點(diǎn)：可以避免免在程序序開(kāi)始運(yùn)運(yùn)行時(shí)，，頻繁發(fā)發(fā)生頁(yè)面面失效的情情況。預(yù)取式的的主要缺缺點(diǎn)：如果調(diào)入入的頁(yè)面面用不上上，浪費(fèi)費(fèi)了調(diào)入入的時(shí)間間，占用了主主存的資資源。2/28/202089計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.3高高速緩緩沖存儲(chǔ)儲(chǔ)器3.3..1基基本工工作原理理3.3..2地地址映映象與變變換方法法3.3..3Cache替替換算法法及其實(shí)實(shí)現(xiàn)3.3..4Cache存存儲(chǔ)系統(tǒng)統(tǒng)的加速速比3.3..5Cache的的一致性性問(wèn)題3.3..6Cache的的預(yù)取算算法2/28/202090計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2/28/202091計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.3..1基基本工工作原理理3.3..2地地址映象象與變換換方法地址映象象：把主存中中的程序序按照某某種規(guī)則則裝入到到Cache中中，并建建立主存存地址與與Cache地地址之間間的對(duì)應(yīng)應(yīng)關(guān)系。。地址變換換：當(dāng)程序已已經(jīng)裝入入到Cache之后，，在程序序運(yùn)行過(guò)過(guò)程中，，把主存存地址變變換成Cache地址址。在選取地地址映象象方法要要考慮的的主要因因素：地址變換換的硬件件實(shí)現(xiàn)容容易、速速度要快快，主存空間間利用率率要高，，發(fā)生塊沖沖突的概概率要小小。2/28/202093計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)1.全全相聯(lián)映映象及其其變換映象規(guī)則則：主存的任任意一一塊可以以映象到到Cache中的任意意一塊。。（映象關(guān)系系有Cb×Mb種）地址變換換規(guī)則用硬件實(shí)實(shí)現(xiàn)非常常復(fù)雜2/28/202095計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2.直直接映象象及其變變換映象規(guī)則則：主存儲(chǔ)器器中一塊塊只能映映象到Cache的一一個(gè)特定定的塊中中。Cache地址址的計(jì)算算公式：：b＝BmodCb其中：b為Cache塊號(hào)，，B是主存存塊號(hào)，，Cb是Cache塊塊數(shù)。實(shí)際上，，Cache地址址與主存存儲(chǔ)器地地址的低低位部分分完全相相同。2/28/202096計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)直接映象象方式的的地址映映象規(guī)則則直接映象象方式的的地址變變換過(guò)程程：用主存地地址中的的塊號(hào)B去訪問(wèn)問(wèn)區(qū)號(hào)存存儲(chǔ)器，，把讀出出來(lái)的區(qū)區(qū)號(hào)與主主存地址址中的區(qū)區(qū)號(hào)E進(jìn)進(jìn)行比較較：比較結(jié)果果相等，，有效位位為1，，則Cache命中，，否則該該塊已經(jīng)經(jīng)作廢。。比較結(jié)果果不相等等，有效效位為1，Cache中的該該塊是有有用的，，否則該該塊是空空的。2/28/202098計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)直接映象象方式的的地址變變換規(guī)則則2/28/202099計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)提高Cache速度的的一種方方法：把區(qū)號(hào)存存儲(chǔ)器與與Cache合合并成一一個(gè)存儲(chǔ)儲(chǔ)器2.直直接映象象及其變變換的優(yōu)優(yōu)缺點(diǎn)主要優(yōu)點(diǎn)點(diǎn)：硬件實(shí)現(xiàn)現(xiàn)很簡(jiǎn)單單，不需需要相聯(lián)聯(lián)訪問(wèn)存存儲(chǔ)器訪問(wèn)速度度也比較較快，實(shí)實(shí)際上不不需要進(jìn)進(jìn)行地址址變換主要缺點(diǎn)點(diǎn)：塊的沖突突率比較較高。2/28/2020101計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.組組相聯(lián)映映象及其其變換映象規(guī)則則：主存和Cache按同同樣大小小劃分成成塊和組組。主存和Cache的組組之間采采用直接接映象方方式。在兩個(gè)對(duì)對(duì)應(yīng)的組組內(nèi)部采采用全相相聯(lián)映象象方式。。組相聯(lián)映映象方式式的優(yōu)點(diǎn)點(diǎn)：塊的沖突突概率比比較低，，塊的利用用率大幅幅度提高高，塊失效率率明顯降降低。組相聯(lián)映映象方式式的缺點(diǎn)點(diǎn)：實(shí)現(xiàn)難度度和造價(jià)價(jià)要比直直接映象象方式高高。2/28/2020102計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)組相聯(lián)映映象的地地址變換換過(guò)程：：用主存地地址中的的組號(hào)G按地址址訪問(wèn)塊塊表存儲(chǔ)儲(chǔ)器。把讀出來(lái)來(lái)的一組組區(qū)號(hào)和和塊號(hào)與與主存地地址中的的區(qū)號(hào)和和塊號(hào)進(jìn)進(jìn)行相聯(lián)比較較。如果有相相等的，，表示Cache命中中；如果全部部不相等等，表示示Cache沒(méi)沒(méi)有命中中。2/28/2020104計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)組相聯(lián)映映象的地地址變換換提高Cache訪問(wèn)速速度的一一種方法法：用多個(gè)相相等比較較器來(lái)代代替相聯(lián)聯(lián)訪問(wèn)2/28/2020107計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)4.位位選擇組組相聯(lián)映映象及其其變換地址映象象規(guī)則：：主存和Cache都按按同樣大大小分塊塊，Cache在分分塊的基基礎(chǔ)上再再分組，，主存按照照Cache的的組容量量分區(qū)。。主存的塊塊與Cache的組之之間采用用直接映映象方式式，主存中的的塊與Cache中組組內(nèi)部的的各個(gè)塊塊之間采采用全相相聯(lián)映象象方式。。與組相聯(lián)聯(lián)映象方方式比較較：映象關(guān)系系明顯簡(jiǎn)簡(jiǎn)單，實(shí)實(shí)現(xiàn)起來(lái)來(lái)容易。。在塊表中中存放和和參與相相聯(lián)比較較的只有有區(qū)號(hào)E2/28/2020108計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)位選擇組組相聯(lián)的的地址映映象規(guī)則則位選擇組組相聯(lián)的的地址變變換規(guī)則則5.段段相聯(lián)映映象及其其變換映象規(guī)則則：主存和Cache都按按同樣大大小分塊塊和段段之間采采用全相相聯(lián)映象象方式段內(nèi)部的的塊之間間采用直直接映象象方式地址變換換過(guò)程：：用主存地地址中的的段號(hào)與與段表中中的主存存段號(hào)進(jìn)進(jìn)行相聯(lián)聯(lián)比較如果有相相等的，，用主存存地址的的段內(nèi)塊塊號(hào)按地地址訪問(wèn)問(wèn)Cache的的段號(hào)部部分。把讀出的的段號(hào)s與主存存地址的的段內(nèi)塊塊號(hào)b及及塊內(nèi)地地址w拼拼接起來(lái)來(lái)得到Cache地址址；2/28/2020111計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)段相聯(lián)映映象地址址映象規(guī)規(guī)則段相聯(lián)映映象地址址變換過(guò)過(guò)程段相聯(lián)映映象方式式的優(yōu)缺缺點(diǎn)主要優(yōu)點(diǎn)點(diǎn)：段表比較較簡(jiǎn)單，，實(shí)現(xiàn)的的成本低低。例如：一個(gè)容量量為256KB的Cache，分成成8個(gè)段段，每段段2048塊，，每塊16B。。在段表存存儲(chǔ)器中中只需要要存8個(gè)個(gè)主存地地址的段段號(hào),而在塊表表中要存存儲(chǔ)8××2048＝16384個(gè)區(qū)區(qū)號(hào)，兩者相差差2000多倍倍。主要缺點(diǎn)點(diǎn)：當(dāng)發(fā)生段段失效時(shí)時(shí)，要把把本段內(nèi)內(nèi)已經(jīng)建建立起來(lái)來(lái)的所有有映象關(guān)關(guān)系全部部撤消。。2/28/2020114計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.3..3Cache替換換算法及及其實(shí)現(xiàn)現(xiàn)使用的場(chǎng)場(chǎng)合：直接映象象方式實(shí)實(shí)際上不不需要替替換算法法全相聯(lián)映映象方式式的替換換算法最最復(fù)雜主要用于于組相聯(lián)、段相聯(lián)聯(lián)等映象象方式中中要解決的的問(wèn)題：：記錄每次次訪問(wèn)Cache的塊塊號(hào)在訪問(wèn)過(guò)過(guò)程中，，對(duì)記錄錄的塊號(hào)號(hào)進(jìn)行管管理根據(jù)記錄錄和管理理結(jié)果，，找出替替換的塊塊號(hào)主要特點(diǎn)點(diǎn)：全部用硬硬件實(shí)現(xiàn)現(xiàn)2/28/2020115計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)1.輪輪換法及及其實(shí)現(xiàn)現(xiàn)用于組相相聯(lián)映象象方式中中，有兩兩種實(shí)現(xiàn)現(xiàn)方法。。方法一：：每塊一一個(gè)計(jì)數(shù)數(shù)器在塊表內(nèi)內(nèi)增加一一個(gè)替換換計(jì)數(shù)器器字段，，計(jì)數(shù)器的的長(zhǎng)度與與Cache地地址中的的組內(nèi)塊塊號(hào)字段段的長(zhǎng)度度相同。。替換方法法及計(jì)數(shù)數(shù)器的管管理規(guī)則則：新裝入或或替換的的塊，它它的計(jì)數(shù)數(shù)器清0，同組組其它塊塊的計(jì)數(shù)數(shù)器都加加“1””。在同組中中選擇計(jì)計(jì)數(shù)器的的值最大大的塊作作為被替替換的塊塊。2/28/2020116計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)例3.11：Solar-16/65小型型機(jī)的Cache采用用位選擇擇組相聯(lián)聯(lián)映象方方式。Cache每組組的塊數(shù)數(shù)為4，，因此，，每塊用用一個(gè)2位的計(jì)計(jì)數(shù)器。。2/28/2020117計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)方法二：：每組一一個(gè)計(jì)數(shù)數(shù)器替換規(guī)則則和計(jì)數(shù)數(shù)器的管管理：本組有替替換時(shí)，，計(jì)數(shù)器器加“1”，計(jì)數(shù)器的的值就是是要被替替換出去去的塊號(hào)號(hào)。例3.12：NOVA3機(jī)的的Cache采采用組相相聯(lián)映象象方式，，Cache每每組的塊塊數(shù)為8，每組組設(shè)置一一個(gè)3位位計(jì)數(shù)器器。在需需要替換換時(shí)，計(jì)計(jì)數(shù)器的的值加““1”，，用計(jì)數(shù)數(shù)器的值值直接作作為被替替換塊的的塊號(hào)。。輪換法的的優(yōu)點(diǎn)：：實(shí)現(xiàn)比較較簡(jiǎn)單，，能夠利利用歷史史上的塊塊地址流流情況輪換法的的缺點(diǎn)：：沒(méi)有利用用程序的的局部性性特點(diǎn)2/28/2020118計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2.LRU算算法及其其實(shí)現(xiàn)為每一塊塊設(shè)置一一個(gè)計(jì)數(shù)數(shù)器計(jì)數(shù)器的的長(zhǎng)度與與塊號(hào)字字段的長(zhǎng)長(zhǎng)度相同同計(jì)數(shù)器的的使用及及管理規(guī)規(guī)則：新裝入或或替換的的塊，計(jì)計(jì)數(shù)器清清0，同同組中其其它塊的的計(jì)數(shù)器器加1。。命中塊的的計(jì)數(shù)器器清0，，同組的的其它計(jì)計(jì)數(shù)器中中，凡計(jì)計(jì)數(shù)器的的值小于于命中塊塊計(jì)數(shù)器器原來(lái)值值的加1，其余余計(jì)數(shù)器器不變。。需要替換換時(shí)，在在同組的的所有計(jì)計(jì)數(shù)器中中選擇計(jì)計(jì)數(shù)值最最大的計(jì)計(jì)數(shù)器，，它所對(duì)對(duì)應(yīng)的塊塊被替換換。2/28/2020119計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)LRU算算法的優(yōu)優(yōu)缺點(diǎn)主要優(yōu)點(diǎn)點(diǎn)：(1)命命中率比比較高，，(2)能能夠比較較正確地地利用程程序的局局部性特特點(diǎn)，(3)充充分地利利用歷史史上塊地地址流的的分布情情況，(4)是是一種堆堆棧型算算法，隨隨著組內(nèi)內(nèi)塊數(shù)增增加，命命中率單單調(diào)上升升。主要缺點(diǎn)點(diǎn)：控制邏輯輯復(fù)雜，，因?yàn)樵黾蛹恿伺袛鄶嗪吞幚砝硎欠衩械那榍闆r。2/28/2020120計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)例3.13：IBM370/165機(jī)的的Cache采采用組相相聯(lián)映象象方式。。每組有有4塊，，為了實(shí)實(shí)現(xiàn)LRU替換換算法，，在塊表表中為每每一塊設(shè)設(shè)置一個(gè)個(gè)2位位的計(jì)計(jì)數(shù)器。。在訪問(wèn)問(wèn)Cache的的過(guò)程中中，塊的的裝入、、替換及及命中時(shí)時(shí)，計(jì)數(shù)數(shù)器的工工作情況況如表：2/28/2020121計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.比比較對(duì)法法以三個(gè)塊塊為例，，分別稱(chēng)稱(chēng)為塊A、塊B、塊C表示方法法：用TAB＝1表示示B塊塊比A塊更更久沒(méi)有有被訪問(wèn)問(wèn)過(guò)。如如果表示示塊C最久久沒(méi)有被被訪問(wèn)過(guò)過(guò)：

每次訪問(wèn)問(wèn)之后要要改變觸觸發(fā)器的的狀態(tài)在訪問(wèn)塊塊A之后后：TAB＝1，TAC＝1在訪問(wèn)塊塊B之后后：TAB＝0，TBC＝1在訪問(wèn)塊塊C之后后：TAC＝0，TBC＝02/28/2020122計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)每組３個(gè)個(gè)塊的比比較對(duì)法法2/28/2020123計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)比較對(duì)法法硬件需需求量計(jì)計(jì)算：需要的觸觸發(fā)器個(gè)個(gè)數(shù)為：：與門(mén)個(gè)數(shù)數(shù)為Gb，每個(gè)門(mén)的的輸入端端個(gè)數(shù)為為Gb-1當(dāng)每組的的塊數(shù)比比較多時(shí)時(shí),采用分級(jí)級(jí)辦法實(shí)實(shí)現(xiàn)實(shí)質(zhì)上是是用降低低速度來(lái)來(lái)?yè)Q取節(jié)節(jié)省器件件。例3.14：IBM3033機(jī)的的Cache，，每組的的塊數(shù)為為16，，分3級(jí)級(jí)。從第第1級(jí)到到第3級(jí)級(jí)分別為為4、2、2。。共需要要觸發(fā)器器個(gè)數(shù)為為：6＋＋4＋8＝18。如果果不分級(jí)級(jí)則需要要觸發(fā)器器120個(gè)。2/28/2020124計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)比較對(duì)法法中每組組塊數(shù)與與所需硬硬件的關(guān)關(guān)系2/28/2020125計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)4.堆堆棧法堆棧法的的管理規(guī)規(guī)則：把本次訪訪問(wèn)的塊塊號(hào)與堆堆棧中保保存的所所有塊號(hào)號(hào)進(jìn)行相相聯(lián)比較較。如果有相相等的，，則Cache命中。。把本次次訪問(wèn)塊塊號(hào)從棧棧頂壓入入，堆棧棧內(nèi)各單單元中的的塊號(hào)依依次往下下移，直直至與本本次訪問(wèn)問(wèn)的塊號(hào)號(hào)相等的的那個(gè)單單元為止止，再往往下的單單元直止止棧底都都不變。。如果沒(méi)有有相等的的，則Cache塊失失效。本本次訪問(wèn)問(wèn)的塊號(hào)號(hào)從棧頂頂壓入，，堆棧內(nèi)內(nèi)各單元元的塊號(hào)號(hào)依次往往下移，，直至棧棧底，棧棧底單元元中的塊塊號(hào)被移移出堆棧棧，它就就是要被被替換的的塊號(hào)。。2/28/2020126計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)例如：每組為4塊，則則堆棧有有4個(gè)存存儲(chǔ)單元元，每個(gè)單元元2位。。2/28/2020127計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)每組4塊塊的堆棧棧法邏輯輯圖堆棧法的的主要優(yōu)優(yōu)點(diǎn)：塊失效率率比較低低，因?yàn)闉樗捎糜昧薒RU算法法。硬件實(shí)現(xiàn)現(xiàn)相對(duì)比比較簡(jiǎn)單單。堆棧法的的主要缺缺點(diǎn)：速度比較較低，因因?yàn)樗栊枰M(jìn)行行相聯(lián)比比較。堆棧法與與比較對(duì)對(duì)法所用用觸發(fā)器器的比例例：其中，Gb是Cache每每一組的的塊數(shù)。。當(dāng)Gb大于8時(shí)時(shí)，堆棧棧法所用用的器件件明顯少少于比較較對(duì)法。。2/28/2020129計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.3..4Cache存儲(chǔ)儲(chǔ)系統(tǒng)的的加速比比1.加加速比與與命中率率的關(guān)系系Cache存儲(chǔ)儲(chǔ)系統(tǒng)的的加速比比SP為：其中：Tm為主存儲(chǔ)儲(chǔ)器的訪訪問(wèn)周期期，Tc為Cache的的訪問(wèn)周周期，T為Cache存儲(chǔ)系系統(tǒng)的等等效訪問(wèn)問(wèn)周期，，H為命中中率。提高加速速比的最最好途徑徑是提高高命中率率2/28/2020130計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)加速比SP能夠接近近于期望望值是：加速比SP與命中率率H的關(guān)關(guān)系2/28/2020131計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)2.Cache命中中率與容容量的關(guān)關(guān)系Cache的命命中率隨隨它的容容量的增增加而提提高。關(guān)系曲線線可以近近似地表表示為：：2/28/2020132計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.Cache命中中率與塊塊大小的的關(guān)系在組相聯(lián)聯(lián)方式中中,塊塊大小對(duì)對(duì)命中率率非常敏敏感塊很小時(shí)時(shí)，命中中率很低低。隨著塊大大小增加加命中率率也增加加,有一個(gè)極極大值當(dāng)塊非常常大時(shí),,進(jìn)入入Cache中中的數(shù)據(jù)據(jù)可能無(wú)無(wú)用當(dāng)塊大小小等于Cache容量量時(shí),命命中率率將趨近近零4.Cache命中中率與組組數(shù)的關(guān)關(guān)系在組相聯(lián)聯(lián)方式中中,組組數(shù)對(duì)命命中率的的影響很很明顯隨著組數(shù)數(shù)的增加加，Cache的命中中率要降降低。當(dāng)組數(shù)不不太大時(shí)時(shí)(小于于512),命命中率率的降低低很少當(dāng)組數(shù)超超過(guò)一定定數(shù)量時(shí)時(shí),命命中率的的下降非非?？?/28/2020133計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)Cache命中中率與塊塊大小的的關(guān)系2/28/2020134計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)3.3..5Cache的一一致性造成Cache與主存存的不一一致的原原因：(1)由由于CPU寫(xiě)寫(xiě)Cache，，沒(méi)有立立即寫(xiě)主主存(2)由由于IO處理理機(jī)或IO設(shè)備備寫(xiě)主存存Cache的更更新算法法(1)寫(xiě)寫(xiě)直達(dá)法法，寫(xiě)通過(guò)法法，WT(Write--through)CPU的的數(shù)據(jù)寫(xiě)寫(xiě)入Cache時(shí)，同同時(shí)也寫(xiě)寫(xiě)入主存存(2)寫(xiě)寫(xiě)回法法，抵觸修改改法，WB(Write-Back)CPU的的數(shù)據(jù)只只寫(xiě)入Cache，不不寫(xiě)入主主存，僅僅當(dāng)替換換時(shí)，才才把修改改過(guò)的Cache塊寫(xiě)寫(xiě)回主存存寫(xiě)回法與寫(xiě)直達(dá)法法的優(yōu)缺點(diǎn)點(diǎn)比較：：(1)可可靠性，，寫(xiě)直達(dá)達(dá)法優(yōu)于于寫(xiě)回法法。寫(xiě)直達(dá)法法能夠始始終保證證Cache是是主存的的副本。。如果Cache發(fā)生錯(cuò)錯(cuò)誤，可可以從主主存得到到糾正。。2/28/2020136計(jì)算機(jī)系系統(tǒng)結(jié)構(gòu)構(gòu)第第三章存存儲(chǔ)儲(chǔ)系統(tǒng)(2)與與主存的的通信量量，寫(xiě)回回法少于于寫(xiě)直達(dá)達(dá)法。對(duì)于寫(xiě)回回法：大多數(shù)操操作只需需要寫(xiě)Cache，不不需要寫(xiě)寫(xiě)主存；；當(dāng)發(fā)生塊塊失效時(shí)時(shí)，可能能要寫(xiě)一一個(gè)塊到到主存；；即使是讀讀操作，，也可能能要寫(xiě)一一個(gè)塊到到主存。。對(duì)于寫(xiě)直直達(dá)法：：每次寫(xiě)操操作，必