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

計算機系統(tǒng)機構(gòu)第四第一頁，共九十五頁，編輯于2023年，星期五……Cache塊位置012ncb-1主存塊012nmb-1…2ncb-1塊2ncb+02ncb+1…2·2ncb-1塊2·2ncb+0…3·2ncb-1……0區(qū)1區(qū)2區(qū)2nmb－ncb-1區(qū)圖4.35直接映象規(guī)則第二頁，共九十五頁，編輯于2023年，星期五

2)變換過程主存塊號塊內(nèi)地址主存地址

nmnmbnmr

ncbncrCache地址

nc…2ncb項

相聯(lián)比較不等塊失效區(qū)號…012ncb-1??相等訪Cache

區(qū)號(按地址訪問存貯器)由2ncb

中選

1圖4.36直接映象的地址變換過程第三頁，共九十五頁，編輯于2023年，星期五

3)優(yōu)缺點優(yōu)點：

a)所需硬件簡單，只需要容量較小的按地址訪問的區(qū)號標(biāo)志表存貯器和少量外比較電路，因此成本低。

b)訪問Cache與訪問區(qū)號表、比較區(qū)號是否相符的操作是同時進行的。當(dāng)Cache命中時就意味著省去了地址變換所花費的時間。第四頁，共九十五頁，編輯于2023年，星期五

缺點：直接映象法最致命的缺點就是Cache的塊沖突率很高。只要有兩個或兩個以上經(jīng)常使用的塊恰好被映象到Cache的同一個塊位置時，就會使得Cache的命中率急劇下降。而且，即使此時Cache中有大量的空閑塊存在，仍然會發(fā)生塊失效和塊沖突，無法使用Cache中的空閑塊，所以，Cache的利用率很低。正是因為這個原因才使得目前采用直接映象的Cache存貯器很少了。第五頁，共九十五頁，編輯于2023年，星期五3.組相聯(lián)映象及其變換1)思想：簡要說明如下圖4.37所示，將Cache空間和主存空間都分組，每組S塊(S＝2s)。Cache一共2ncb個塊，分成Q組(Q=2q)，整個Cache是一區(qū)。主存分成與Cache一樣大小的2nd個區(qū)，其地址按區(qū)號、組號、組內(nèi)塊號、塊內(nèi)地址分成對應(yīng)的4個字段。主存地址的組號、組內(nèi)塊號分別用q、s'字段表示，它們的寬度和位置與Cache地址的q、s是一致的。第六頁，共九十五頁，編輯于2023年，星期五2)規(guī)則：組相聯(lián)映象指的是各組之間直接映象，但組內(nèi)各塊間則是全相聯(lián)映象。如圖4.37所示。第七頁，共九十五頁，編輯于2023年，星期五組號

q組內(nèi)塊號

s塊內(nèi)地址

ncr組號

q組內(nèi)塊號

s'塊內(nèi)地址

nmr區(qū)號

nd1位1位2位2位1位ncbnmbncnm塊位置0塊01122334455667789101112131415012301230123012301230123第0組第0組第1組第1組第0組第1組第0區(qū)(Cache容量)第1區(qū)(Cache容量)Cache主存組內(nèi)全相聯(lián)組間直接相聯(lián)圖4.37組相聯(lián)映象規(guī)則

第八頁，共九十五頁，編輯于2023年，星期五

3)討論當(dāng)組相聯(lián)映象的S值大到等于Cache的塊數(shù)(即s=ncb)時就變成了全相聯(lián)映象，而當(dāng)S值小到只有1塊(即無s字段)時就變成了直接映象。因此全相聯(lián)映象和直接映象只是組相聯(lián)映象的兩個極端。在Cache空間大小及塊的大小都已經(jīng)確定的情況下，Cache的總塊數(shù)就定了，但結(jié)構(gòu)設(shè)計者仍可以對S和Q值進行選擇。Q和S的選取主要依據(jù)對塊沖突概率、塊失效率、映象表復(fù)雜性和成本、查表速度等的折衷權(quán)衡。組內(nèi)塊數(shù)S愈多，塊沖突概率和塊失效率愈低，映象表愈復(fù)雜、成本愈高，查表速度愈慢。所以通常采用在典型工作負(fù)荷下進行模擬而定。第九頁，共九十五頁，編輯于2023年，星期五

4)地址變換組號

q組內(nèi)塊號

s'塊內(nèi)地址

nmr區(qū)號

nd組號

q組內(nèi)塊號

s塊內(nèi)地址

ncrnmnc直接直接相聯(lián)比較不等塊失效相等?相聯(lián)比較nds's?nd

＋s'表的總?cè)萘繛?ncb

＝2q·2s行2q組中選

12s行第十頁，共九十五頁，編輯于2023年，星期五4.段相聯(lián)映象在全相聯(lián)、直接相聯(lián)、組相聯(lián)映象的基礎(chǔ)上還可以有各種變形，段相聯(lián)就是一例。段相聯(lián)實質(zhì)上是組相聯(lián)的特例。他是采用組間全相聯(lián)、組內(nèi)直接映象。為了與組相聯(lián)加以區(qū)別，將這種映象方式稱為段相聯(lián)。就是說，段相聯(lián)映象是把主存和Cache分成具有相同的Z塊的若干段，段與段之間采用全相聯(lián)映象，而段內(nèi)各塊之間采用直接映象。如圖4.42所示：第十一頁，共九十五頁，編輯于2023年，星期五塊0塊1塊2Z－1Cache主存…塊0塊1塊2Z－1…≈≈塊0塊1塊2Z－1…塊0塊1塊2Z－1…≈≈塊0塊1塊2Z－1…段0段0(Z個段)段1段2nmb/Z－1段2ncb/Z－1圖4.42

具有每段Z個塊的斷相聯(lián)映象段間全相聯(lián)段內(nèi)直接第十二頁，共九十五頁，編輯于2023年，星期五4.3.3替換算法的實現(xiàn)

當(dāng)訪存發(fā)生Cache塊失效，需要把主存塊按所采用的映象規(guī)則裝入Cache時，如果又出現(xiàn)Cache塊沖突，就必須按某種策略選擇將Cache中的哪一塊替換出去。Cache——主存存貯層次的替換算法與虛擬存貯器的沒有什么不同，不外乎也是FIFO法或LRU法，其中LRU法最為常用。第十三頁，共九十五頁，編輯于2023年，星期五1.堆棧法

1)思想我們在4.2.2中講過，LRU法是堆棧型替換算法，也講了對于LRU算法，堆棧St中由棧頂?shù)綏５椎母黜棧ㄐ校┖惴从吵龅絫時刻，實存中各頁被訪問過的近遠(yuǎn)次序，以及每訪問一頁，堆棧St中各項的變換過程。結(jié)果是此堆棧的棧頂恒存放近期最近訪問過的頁的頁號，而棧底恒存放近期最久沒有方問過的頁的頁號，即準(zhǔn)備被替換掉的頁的頁號。那么，我們在Cache——主存存貯層次中就可以按此思想實際組成一個硬件堆棧。

第十四頁，共九十五頁，編輯于2023年，星期五

2)過程（塊號）（塊號）（塊號）（塊號）（塊號）2ncb個寄存器需重新排列的塊號都下推一行被訪問的塊號（經(jīng)相聯(lián)比較找到）?寄存器堆棧壓入ncb位近期最近訪問過的塊近期最久沒有訪問過的塊圖4.43全相聯(lián)映象LRU法經(jīng)堆棧實現(xiàn)（需要有相聯(lián)比較功能）第十五頁，共九十五頁，編輯于2023年，星期五

3)缺點：這種硬件堆棧既要求具有相聯(lián)比較的功能，又要求能全下移、部分下移和從中間取出一項的功能，成本較高，因此只適用于組相聯(lián)且組內(nèi)塊數(shù)較少的LRU替換場合。

4)變形上述這種堆棧，各塊被訪問的先后次序由該項在堆棧中距離棧底是近還是遠(yuǎn)來反映。為了避免堆棧中各行存放的內(nèi)容經(jīng)常同時進行下移，以便節(jié)省成本，我們采用另一種變形，即將存放塊號的寄存器的幾何位置與Cache中的塊號對應(yīng)，而用寄存器存第十六頁，共九十五頁，編輯于2023年，星期五放值的大小來表示已被訪問過的遠(yuǎn)近次序。以組相聯(lián)為例，每一組均使用如圖4.44那樣的一個寄存器組，由2s個寄存器組成，每個寄存器為s位寬，可以存放表示從0到2s－1的次序值。如果讓越是最近訪問的，其次序值愈小，則只需通過相聯(lián)比較求最大值（不是相聯(lián)比較相符），找到該最大值所在的寄存器號，這就是對應(yīng)Cache中應(yīng)該被替換掉的塊的塊號。第十七頁，共九十五頁，編輯于2023年，星期五第0塊的訪問次序第1塊的訪問次序第2塊的訪問次序第2s-1塊的訪問次序塊0塊1塊2塊2s-1

2s個寄存器

S位（其中一組）Cache存貯器（其中一組）圖4.44組相聯(lián)LRU法經(jīng)寄存器實現(xiàn)（每組一個，需要有相聯(lián)比較功能）第十八頁，共九十五頁，編輯于2023年，星期五2.比較對法

1)思路比較法的基本思路是讓各個塊成對組合，用一個觸發(fā)器的狀態(tài)來表示該比較對內(nèi)兩塊訪問的遠(yuǎn)近次序，再經(jīng)門電路就可以找到LRU塊。比如說有ABC三塊，互相之間可以組合成ABBAACCABCCB6對，其中AB和BA、AC和CA、BC和CB是重復(fù)的，所以TAB為“1”，表示A比B更近被訪問過；TAB為“0”，則表示B比A更近被訪問過。TAC

、TBC也類似定義。這樣，當(dāng)訪問過的次序為ABC，即最近第十九頁，共九十五頁，編輯于2023年，星期五訪問過的為A，最久未被訪問過的為C，則這三個觸發(fā)器狀態(tài)分別為TAB＝1，TAC＝1，TBC＝1。如果訪問過的次序為BAC，C為最久未被訪問過的塊，則此時必有TAB＝0，TAC＝1，TBC＝1。因此最久未被訪問過的塊C作為被替換掉的塊的話，用布爾代數(shù)式必有：

CLRU＝TAB?TAC?TBC+TAB?TAC?TBC＝TAC?TBC同理可得：

BLRU＝TAB?TBC；

ALRU＝TAB?TAC因此，完全可以用門、觸發(fā)器等硬件組合實現(xiàn)，如圖4.45所示：第二十頁，共九十五頁，編輯于2023年，星期五&&&010101TABTACTBC

ALRU

BLRU

CLRU???訪問B訪問C訪問A圖4.15用比較對法實現(xiàn)LRU算法第二十一頁，共九十五頁，編輯于2023年，星期五

2)分析我們來看比較對法所用的硬件量。由于每塊均可能作為LRU塊，其信號需要用一個與門產(chǎn)生，例如ALRU與門要有從TABTAC來的輸入，BLRU門要有從TAB

，TBC來的輸入，而與每塊有關(guān)的對數(shù)個數(shù)為塊數(shù)減去1，所以與門的扇入數(shù)是塊數(shù)減去1。若p為塊數(shù)，量量組合，比較對觸發(fā)器的個數(shù)應(yīng)為Cp2，即為p(p-1)/2。表4.2給出了比較對法塊數(shù)p的取值與門數(shù)、門的輸入端數(shù)及比較對觸發(fā)器數(shù)的關(guān)系。第二十二頁，共九十五頁，編輯于2023年，星期五3)總結(jié)替換算法實現(xiàn)的設(shè)計要圍繞下面兩點來考慮：

a)如何對每次訪問進行記錄（使用位法、堆棧法和比較對法所用的記錄方法都不同）；

b)如何根據(jù)所記錄的信息來判定近期內(nèi)哪一塊最久沒有被訪問過。由此可見，實現(xiàn)方法和所用的映象方法密切相關(guān)。例如，對于主存——輔存存貯層次的全相聯(lián)映象宜于采用使用位法或類似的方法，而不宜采用堆棧法和比較對法；但對于Cache——主存存貯層次的組相聯(lián)映象，因為組內(nèi)塊數(shù)較少，就宜于采用比較第二十三頁，共九十五頁，編輯于2023年，星期五對法或堆棧法。替換算法的設(shè)計和實現(xiàn)也和器件的發(fā)展密切相關(guān)，隨著器件技術(shù)的發(fā)展，尤其是高速相聯(lián)存貯器片子的改進，已經(jīng)而且必然會不斷研制出新的更好的實現(xiàn)方法。第二十四頁，共九十五頁，編輯于2023年，星期五4.3.4Cache的透明性及性能分析

1.Cache的透明性分析

1)兩種問題的出現(xiàn)雖然Cache是主存的一部分副本，主存中某單元的內(nèi)容卻可能在一段時間里會與Cache中對應(yīng)單元的內(nèi)容不一致。例如，CPU往Cache寫入，修改了Cache中某單元的內(nèi)容，而在主存中對應(yīng)于此單元的內(nèi)容卻可能仍是原來的，沒有改變。這時，如果CPU或I/O處理機及其他處理機要經(jīng)主存交換信息，那么主存內(nèi)容跟不上Cache對應(yīng)內(nèi)容變化的這種不一致就會造成錯誤。第二十五頁，共九十五頁，編輯于2023年，星期五同樣，I/O處理機或其他處理機已把新的內(nèi)容送入主存某個區(qū)域，而Cache中對應(yīng)于此區(qū)域的副本內(nèi)容卻仍可能是原來的。這時，如果CPU要從Cache中讀取信息，也會因為這種Cache內(nèi)容跟不上主存對應(yīng)內(nèi)容變化的不一致而造成錯誤。因此，必須采取措施解決好由于讀寫過程中產(chǎn)生的Cache和主存對應(yīng)內(nèi)容不一致的問題。第二十六頁，共九十五頁，編輯于2023年，星期五

2)寫回法寫回法是在CPU執(zhí)行寫操作時，只是把信息寫入Cache，僅當(dāng)需要被替換時，才將已經(jīng)被寫入過的Cache塊先送回主存，然后再調(diào)入新塊。這種方法也稱為抵觸修改法，類似于虛擬存貯器中進行頁面替換時的情況。因此，Cache——主存存貯層次的地址映象表中需對Cache中的每個塊設(shè)置一個“修改位”，作為該塊裝入Cache后是否被修改過的標(biāo)志。這樣在塊替換時，根據(jù)該塊的修改位是否位1，就可以決定替換時是否先將該塊存回主存原來的位置。第二十七頁，共九十五頁，編輯于2023年，星期五

3)寫直達法寫直達法也稱為存直達法，它利用Cache——主存存貯層次在處理機和主存之間的直接通路，每當(dāng)處理機寫入Cache的同時，也通過此通路直接寫入主存。這樣，在塊替換時，就不必先寫回主存，而可以立即調(diào)入新頁。顯然，寫回法是把開銷花在每次需要替換的時候，而寫直達法則把開銷花在每次寫入Cache時都附加一個比寫Cache長的多的寫主存時間。第二十八頁，共九十五頁，編輯于2023年，星期五

4)寫不命中處理當(dāng)出現(xiàn)寫不命中時，無論是寫回法還是寫直達法都有一個在寫時是否取的問題。一種是不按寫分配法，即當(dāng)Cache寫不命中時只寫入主存，該寫地址單元所在塊不從主存調(diào)進Cache。另一種是按寫分配法，即當(dāng)Cache不命中時除寫入主存外，還把該寫地址單元所在的塊由主存調(diào)入Cache。這兩種策略對不同的主存修改算法，其效果不同，但命中率差別不大。目前寫回法一般采用按寫分配法，而寫直達法則一般采用不按寫分配法。第二十九頁，共九十五頁，編輯于2023年，星期五寫回法和寫直達法都需要有少量緩沖器。寫回法中緩沖器用于暫存將要寫回的塊，使之不必等待被替換塊寫回主存后才開始進行Cache取。寫直達法中緩沖器則用于緩沖由寫Cache所要求的寫回主存的內(nèi)容，使CPU不必等待這些寫主存完成就能往下運行。緩沖器由要存的數(shù)據(jù)和要存入的目標(biāo)地址組成。在寫直達系統(tǒng)中容量為4的緩沖器就可以顯著改進其性能，IBM3033就是這樣用的。要注意的這些緩沖器對Cache和主存是透明的。在設(shè)計時，要處理好可能由它們所引起的錯誤(如另一個處理機要訪問的主存單元的內(nèi)容正好仍在緩沖器中)。第三十頁，共九十五頁，編輯于2023年，星期五

5)兩種方法對比

a)寫回法有利于省去許多將中間結(jié)果寫入主存的無謂開銷。但是增加了Cache的復(fù)雜性。

b)可靠性上寫回法不如寫直達法好。

c)具體采用哪種方法還與系統(tǒng)使用場合有關(guān)。

d)如果讓多CPU共享主存交換信息改成共享Cache交換信息，信息的一致性就能得到保證。

e)對于共享主存的多CPU系統(tǒng)，絕大多數(shù)還是采用各個CPU都有自己的Cache的方式與共享主存連接。這樣的系統(tǒng)由于Cache的透明性，僅靠寫直達法并不能保證同一主存單元在各個Cache中的對應(yīng)內(nèi)容都一致。如下圖：第三十一頁，共九十五頁，編輯于2023年，星期五要采取措施保證讓有此單元的各個Cache的內(nèi)容都一致才行。CPUACacheaCPUBCacheb主存?????圖4.46每個處理機都有Cache的共享多處理機系統(tǒng)第三十二頁，共九十五頁，編輯于2023年，星期五解決辦法：

?采用播寫法：即任何處理機要寫入Cache時，不僅要寫入自己Cache的目標(biāo)塊和主存中，還把信息或者播寫到所有Cache有此單元的地方，或者讓所有Cache有此單元的塊作廢以便下次訪問時按缺塊處理，從主存中重新調(diào)入。

?控制某些共享信息（如信號燈或作業(yè)隊等）不等進入Cache。

?目錄表法：即在CPU讀/寫Cache不命中時，先查主存中的目錄表以判定目錄塊是否在別的Cache內(nèi)，以及是否正在被修改等，然后再決定如何讀寫此塊。第三十三頁，共九十五頁，編輯于2023年，星期五

6)第二種問題

Cache內(nèi)容跟不上已變化了的主存內(nèi)容的問題，有兩種解決辦法：

a)當(dāng)I/O處理機未經(jīng)Cache往主存寫入新內(nèi)容的同時，由OS經(jīng)某個專用指令清除整個Cache。這種辦法的缺點是象我們在講述用專用指令清除快表一樣，會使Cache對OS和系統(tǒng)程序員成為不透明的，因此并不好。

b)當(dāng)I/O處理機往主存某個區(qū)域?qū)懭胄聝?nèi)容時，由專用硬件自動地將Cache內(nèi)對應(yīng)此區(qū)域地副本作廢，而不必由OS進行任何干預(yù)，從而保持Cache的透明性。第三十四頁，共九十五頁，編輯于2023年，星期五2.Cache的取算法

1)預(yù)取法為了便于硬件實現(xiàn)，通常只預(yù)取直接順序的下一塊，即在訪問到主存的第i塊(不論是否已取進Cache)時，只有第i＋1塊才是可能的預(yù)取塊。至于何時將該塊取進，可以有恒預(yù)取和不命中時預(yù)取兩種不同的方法。恒預(yù)取指的是只要訪問到主存的第i塊的某個字，不論Cache是否命中，恒發(fā)預(yù)取指令。不命中時預(yù)取僅當(dāng)訪問第i塊不命中時，才發(fā)預(yù)取指令。第三十五頁，共九十五頁，編輯于2023年，星期五

2)影響命中率的其它因素

a)塊的大?。喝裘繅K的字節(jié)數(shù)過少，預(yù)取的效果不明顯。從預(yù)取的需要出發(fā)，希望塊盡可能大。但若每塊的字節(jié)數(shù)過多，一方面可能會預(yù)取進不需要的信息，另一方面由于Cache容量有限，又可能把正在使用或近期使用到的信息給替換出去，反而降低了命中率。從模擬結(jié)果來看，每塊的字節(jié)數(shù)如果超過了256，就會出現(xiàn)這種情況。第三十六頁，共九十五頁，編輯于2023年，星期五

b)預(yù)取開銷：要預(yù)取就要有訪主存開銷和將它取進Cache的訪Cache開銷，還要加上把被替換的塊寫回主存的開銷，這些開銷會增加主存和Cache的負(fù)擔(dān)，干擾和延緩程序的執(zhí)行。由上可知，采用預(yù)取法的效果不能只從命中率的提高來衡量，還需要從所花費的開銷多少來考慮。而這種開銷的多少可以通過對按需取進法的不命中開銷與預(yù)取法的不命中開銷和預(yù)取開銷(包括訪存開銷及對Cache的干擾影響)二者之和的比較來得到。

第三十七頁，共九十五頁，編輯于2023年，星期五

3)計算分析設(shè)Dc為Cache不命中時，由主存調(diào)一塊進Cache的開銷，則：

a)按需取進法的不命中開銷為：

Dc×不命中率(按需取進法)b)預(yù)取法不命中的開銷為：

Dc×不命中率(預(yù)取法)

而預(yù)取法還應(yīng)有預(yù)取開銷，為此，我們設(shè)：

?預(yù)取率：預(yù)取總塊數(shù)/訪存總塊數(shù)

?Pa

：預(yù)取訪主存和訪Cache的開銷第三十八頁，共九十五頁，編輯于2023年，星期五

c)預(yù)取法取進預(yù)取塊的開銷為：

Pa×預(yù)取率

?訪問率：訪Cache的總次數(shù)/程序訪Cache的總次數(shù)，即(程序訪Cache次數(shù)＋預(yù)取訪Cache次數(shù))/程序訪Cache次數(shù)。

?Ac：由于預(yù)取訪Cache占用了Cache，延遲、干擾了程序?qū)ache的訪問的預(yù)取干擾開銷。

d)預(yù)取法對程序訪Cache的映象為：

Ac×(訪問率－1)e)結(jié)論由上計算可知，只有下式成立，即：第三十九頁，共九十五頁，編輯于2023年，星期五

Dc×不命中率(按需取進)

>Dc×不命中率(預(yù)取)＋Pa×預(yù)取率＋Ac×(訪問率－1)時，預(yù)取法才是可取的。這里，采用緩沖器技術(shù)是減少預(yù)取干擾的好辦法。Cache和主存都設(shè)置預(yù)取專用緩沖器，使預(yù)取訪主存與訪Cache都盡可能在主存、Cache空閑時進行。第四十頁，共九十五頁，編輯于2023年，星期五3.任務(wù)切換對失效率的影響

1)兩種失效率

a)冷啟動(Cold－start)失效率：從Cache為空(指新進程所需的內(nèi)容都未裝入Cache內(nèi))開始到Cache全部被裝滿這一期間的失效率。

b)熱啟動(Warm－start)失效率：從Cache為現(xiàn)行進程裝滿之后測出的失效率。

第四十一頁，共九十五頁，編輯于2023年，星期五

2)影響失效率的因素

a)與任務(wù)的切換頻度(平均時間間隔Qsw)有關(guān)

Qsw對失效率的影響和工作負(fù)荷有很大關(guān)系。比如，如果進程切換發(fā)生在用戶程序因為系統(tǒng)需要運行管理程序來處理某個I/O中斷或時鐘中斷請求時，則Qsw值愈小，表明由管理程序切換回原先的用戶程序愈快，Cache中保留的原先程序的指令和數(shù)據(jù)就愈多，即失效率愈低。但是如果進程切換是在幾個用戶程序之間進行，且每個進程都要更換掉Cache中的大部分內(nèi)容時，Qsw值愈小就會使失效率愈高。

第四十二頁，共九十五頁，編輯于2023年，星期五

b)與Cache的容量有關(guān)

Qsw值一定時，若容量過小，存不下該程序的工作區(qū)，那么就會有很高的熱啟動失效率。因此，增大Cache的容量可使這個矛盾迅速緩解，而使失效率急劇下降；但在容量增大到基本上保護得了足夠大的工作區(qū)之后，容量大小對失效率的下降就趨于平緩，也就是說增大容量對降低失效率已影響不大。第四十三頁，共九十五頁，編輯于2023年，星期五

3)解決辦法

a)增大Cache容量

b)修改調(diào)度算法，使任務(wù)切換回來前，有用的信息仍能保留在Cache中而不被破壞。

c)設(shè)置多個Cache，例如設(shè)置兩個，一個專用于管理程序，一個專用于用戶程序。這樣，在管態(tài)和目態(tài)之間切換時，不會破壞各Cache中的內(nèi)容。

d)對于某些操作，例如長的向量運算、長的字符行運算等，可以不經(jīng)過Cache直接進行，以避免這些操作由于使用Cache而從Cache中替換出大量更有希望將重新使用的數(shù)據(jù)。第四十四頁，共九十五頁，編輯于2023年，星期五4.影響Cache存貯器性能的因素

1)不命中率與Cache的容量、組的大小和塊的大小的一般關(guān)系不命中率1－HcCache容量組的大小一定塊的大小減小(a)不命中率1－HcCache容量塊的大小一定組的大小減小(b)圖4.47塊的大小、組的大小與Cache容量對Cache命中率的影響第四十五頁，共九十五頁，編輯于2023年，星期五

2)Cache——主存存貯層次的等效速度與命中率的關(guān)系設(shè)：tc為Cache的訪問時間；

tm為主存周期；

Hc為訪Cache的命中率；則Cache存貯器的等效存貯周期為：

ta＝Hctc＋(1－Hc)tm

與主存——輔存存貯層次不同的是一旦Cache不命中，由于主存與CPU之間有直接通路，CPU對第二級的訪問時間就是tm

，而不是調(diào)塊時間再加一個訪Cache的時間了。這樣，采用Cache比之于處理機直第四十六頁，共九十五頁，編輯于2023年，星期五接訪問主存，其速度提高的倍數(shù)為：ρ＝tm/ta＝tm/(Hctc＋(1－Hc)tm)＝1/(1－(1－tc/tm)Hc)因為Hc總是小于1，可以令Hc＝α/(α+1)，代入上式得：

ρ＝(α+1)顯然，不管Cache本身的速度有多高，只要Cache的命中率有限，那么采用Cache——主存存貯層次后，速度能提高的最大值是有限的，不會超過α+1倍。tm

tm+αtc第四十七頁，共九十五頁，編輯于2023年，星期五

3)Cache的容量對機器速度的影響對流水機器，機器速度與主存速度、CPU拍寬、Cache容量的可能關(guān)系如圖4.49所示，機器的單位是MIPS(每秒執(zhí)行百萬條指令)，主存采用多體交叉存取。

a)由圖可見，主存速度和CPU周期一定時，由不用Cache到Cache容量從4KB增大到64KB，機器速度有了顯著提高，尤其是在主存速度較低時。

b)還可以看出，Cache容量的增大，可以顯著降低對主存速度的要求。第四十八頁，共九十五頁，編輯于2023年，星期五

4)總結(jié)總之，Cache本身的速度與容量都會影響Cache存貯器的等效訪問速度。如果對Cache存貯器的等效訪問速度不滿意，需要改進的話就要作具體分析，看看現(xiàn)在Cache的等效訪問速度是否已接近于第一級Cache本身的訪問速度。如果尚差的較遠(yuǎn)，說明Cache的命中率低，這個時時就不是去采用更高速度的Cache片子來替換現(xiàn)有的Cache片子，而應(yīng)當(dāng)從提高Cache的命中率入手，包括調(diào)整組的大小、替換算法以及增大Cache容量等方面著手，否則該速度是無法提高的。相反的，如果實際的等效訪問速第四十九頁，共九十五頁，編輯于2023年，星期五度已經(jīng)非常接近于Cache本身的訪問速度還不能滿足速度要求時，就只有更換更高速的Cache片子。否則，任何其它途徑也是不會有什么效果的。因此我們不能盲目設(shè)計和改進，否則花了很大代價，卻反而降低了系統(tǒng)的性能價格比。第五十頁，共九十五頁，編輯于2023年，星期五4.3.5“Cache—主存—輔存”存貯層次

1.三級存貯層次的地址變換：

CPU提供訪存的虛地址可能需要變換成Cache地址、主存地址或輔存地址。

1)對應(yīng)于虛地址的單元已在Cache中這時就需要把虛地址直接變換成Cache地址來訪問Cache，而不是先把虛地址變換成主存實地址，再由主存實地址變換成Cache地址，這樣可以縮短地址變換的時間。第五十一頁，共九十五頁，編輯于2023年，星期五

2)對應(yīng)單元已在主存但尚未調(diào)入Cache

這時則需要把虛地址經(jīng)快表和慢表變換成主存實地址去訪主存，對讀訪問以及采用按寫訪問還必須進行虛地址到Cache地址的映象或變換，以便把包含對應(yīng)此單元所在的一塊調(diào)入或替換進Cache。

3)對應(yīng)單元還不在主存這時就需要把虛地址變換成輔存實地址去輔存調(diào)頁，同時還要將虛地址映象變換成主存實地址將頁調(diào)入主存，以及把虛地址映象變換成Cache地址，將其中的一塊裝入Cache。第五十二頁，共九十五頁，編輯于2023年，星期五

2.訪問Cache過程

在這三級存貯層次中通?？偸亲岉摰拇笮∏『脮r塊的2的冪倍，每一塊的大小又是字的2的冪倍。而且每次用虛頁號查快表和慢表以取得主存實地址和用虛地址對應(yīng)Cache塊號位置的虛塊號經(jīng)組相聯(lián)去訪Cache(Cache中每個單元存放有主存實地址和對應(yīng)的數(shù)據(jù))同時進行。若能在快表中找到，就用由快表來的主存實地址與由Cache中讀出的主存實地址相比較。當(dāng)兩者相符，存在Cache中該單元的數(shù)據(jù)就是要訪問的虛、實地址的內(nèi)容。寫Cache的過程與此類似。第五十三頁，共九十五頁，編輯于2023年，星期五4.4

主存保護大多數(shù)計算機系統(tǒng)設(shè)計成讓其資源能被并行的多個用戶所共享，就主存來說，就同時存有多個用戶的程序和系統(tǒng)軟件。為使系統(tǒng)能正常工作，應(yīng)防止由于一個用戶程序出錯而破壞主存中其它用戶的程序或系統(tǒng)軟件，還要防止一個用戶程序不合法地訪問不是分配給它的主存區(qū)域，哪怕這種訪問不會引起系統(tǒng)破壞。因此，系統(tǒng)結(jié)構(gòu)需要為主存的使用提供存貯保護，它是多道程序和多處理機系統(tǒng)所必不可少的。第五十四頁，共九十五頁，編輯于2023年，星期五1.存貯區(qū)域的保護

1)主存系統(tǒng)的保護對于不是虛擬存貯器的主存系統(tǒng)可采用第二章講過的界限寄存器方式，由系統(tǒng)軟件經(jīng)特權(quán)指令置定上、下界寄存器，從而劃定每個用戶程序的區(qū)域，禁止它越界訪問。由于用戶程序不能改變上、下界的值，因此不論它如何出錯，也只能破壞該用戶自身的程序，侵犯不到別的用戶程序及系統(tǒng)軟件。

第五十五頁，共九十五頁，編輯于2023年，星期五

2)虛擬存貯系統(tǒng)由于界限寄存器方式只適用于每個用戶程序占用主存一個或幾個(當(dāng)有多對上、下界寄存器時)連續(xù)的區(qū)域；而對于虛擬存貯系統(tǒng)，由于一個用戶的各頁能離散地分布于主存內(nèi)，從而無法使用這種保護方式。對虛擬存貯系統(tǒng)的主存區(qū)域保護就需要采用頁表保護和鍵式保護等方式。

第五十六頁，共九十五頁，編輯于2023年，星期五

a)頁表保護每個程序都有自己的頁表，其行數(shù)等于該程序的虛頁數(shù)。例如它有4頁，則只能有0、1、2、3這4個虛頁號。設(shè)由OS建立的程序也表，這4個虛頁號分別對應(yīng)于實頁號4、8、10、14，則不論虛地址如何出錯，總只能影響主存中分配給該程序的第4、8、10、14號實頁。假設(shè)虛頁號錯成5，肯定不可能在該程序的頁表中找到，也就訪問不了主存，當(dāng)然就不會映象主存中其它程序的區(qū)域。這正是虛擬存貯系統(tǒng)本身固有的保護機能，也是它的一大優(yōu)點。為了便于實現(xiàn)這種保護，還可以在段表中的每行內(nèi)，不第五十七頁，共九十五頁，編輯于2023年，星期五僅設(shè)置頁表起點，還設(shè)置段長(頁數(shù))項。若出現(xiàn)該段內(nèi)的虛頁號大于段長，則可以發(fā)越界中斷。這種頁表保護是在沒有形成主存實地址前進行的保護，使之無法形成能侵犯別的程序區(qū)域的主存地址。然而，若地址形成環(huán)節(jié)由于軟、硬件方面的故障而形成了不屬于本程序區(qū)域的錯誤主存地址時，則上述這種保護就無能為力了。因此，還應(yīng)采取進一步的保護措施，鍵方式就是其中成功的一種。第五十八頁，共九十五頁，編輯于2023年，星期五

b)鍵方式是由OS按當(dāng)時主存的使用分配狀況給主存的每頁配一個鍵，稱為存貯鍵，它相當(dāng)于一把“鎖”。所有頁的存貯鍵存在于相應(yīng)的快速寄存器內(nèi)，每個用戶(任務(wù))的各實頁的頁存貯鍵都相同。為了打開這把鎖，需要有把“鑰匙”，稱為訪問鍵。每個用戶的訪問鍵由OS給定，存在處理機的程序狀態(tài)字(PSW)或控制寄存器中。程序每次訪存前，要核對主存地址所在頁的存貯鍵是否與該道程序的訪問鍵相符，只有相符才準(zhǔn)訪問。這樣，就是錯誤地形成了侵犯別的程序的主存地址，也因為這種鍵保護而仍然不允許訪問。第五十九頁，共九十五頁，編輯于2023年，星期五

c)環(huán)狀保護環(huán)狀保護把系統(tǒng)程序和用戶程序按其重要性及對整個系統(tǒng)能否正常工作的影響程度分層，如圖4.50所示。設(shè)0、1、2三層是系統(tǒng)程序的，之外的各層是同一用戶程序的分層。環(huán)號大小表示保護的級別，環(huán)號愈大，等級愈低。在現(xiàn)行程序運行前，先由OS定好程序各頁的環(huán)號，并置入也表。而后把該道程序的開始環(huán)號送入處理機內(nèi)的現(xiàn)行環(huán)號寄存器，并且把OS規(guī)定給該程序的上限環(huán)號(規(guī)定該程序所能進入的最內(nèi)層環(huán)號)也置入相應(yīng)的寄存器。第六十頁，共九十五頁，編輯于2023年，星期五若是Pi在某一時候?qū)儆趇層各頁的集合，則當(dāng)進程執(zhí)行P∈Pi頁內(nèi)的程序時，允許訪問F∈Pj頁，這里對應(yīng)的是j≥i。但是如果是j<i時，則需由OS環(huán)控制例行程序判定這個內(nèi)向訪問是否允許和是否正確之后才能訪問，否則就是出錯，進入保護處理。但j值肯定不能小于給定的上限環(huán)號。只要j≠i，就進入中斷，若允許訪問，則需經(jīng)特權(quán)指令把現(xiàn)行環(huán)號寄存器的值由i改為j。第六十一頁，共九十五頁，編輯于2023年，星期五這種環(huán)式保護既能保證由于用戶程序的出錯不至于侵犯系統(tǒng)程序，也能保證由于同一用戶程序內(nèi)的低級(環(huán)號大)的部分的出錯而不致破壞其高級(環(huán)號小)的部分。這種環(huán)式保護對系統(tǒng)程序的研究和調(diào)試運行特別有利，因為可以做到能修改系統(tǒng)程序的某些部分而不必?fù)?dān)心會影響到系統(tǒng)程序已設(shè)計好并調(diào)好的核心部分。至于如何控制j≠i的跨層訪問，有的機器規(guī)定只能由規(guī)定的轉(zhuǎn)移指令執(zhí)行，且對和j>i和j<i分別只能用不同的轉(zhuǎn)移指令。第六十二頁，共九十五頁，編輯于2023年，星期五2.訪問方式的保護

上述種種區(qū)域保護，如判越界、判建相符、判環(huán)號相符、判不超出段長等等，都是經(jīng)硬件實現(xiàn)的，因此速度可以是很快的。這些區(qū)域保護是對允許訪問的區(qū)域可以進行任何形式的訪問，而對允許區(qū)域之外，則任何形式的訪問都不允許。但在實際中，只是這種限制往往適應(yīng)不了各種應(yīng)用的要求，因此還得加上訪問方式的保護(限制)。第六十三頁，共九十五頁，編輯于2023年，星期五

1)對主存信息的使用可以有讀R、寫W和執(zhí)行E三種方式。相應(yīng)的就有R、W、E訪問方式保護，這3者的邏輯組合可以反映出各種應(yīng)用要求，如：

R∪W∪E——不允許進行任何訪問；

R∪W∪E——可以進行任何訪問；

R∩W∪E——只能進行讀訪問；

R∪W∩E——只能按數(shù)據(jù)進行讀寫；

R∪W∩E——只能執(zhí)行，不能作為數(shù)據(jù)使用；

R∪E∩W——只能進行寫訪問；

R∪E∩W——不準(zhǔn)寫訪問。第六十四頁，共九十五頁，編輯于2023年，星期五

2)對前面講過的各種區(qū)域保護，都可以加上相應(yīng)的訪問方式位以實現(xiàn)這種訪問限制。

3)至于環(huán)式保護和也表保護，可以把R、W、E等訪問方式位設(shè)在各個程序的段、頁表的各行內(nèi)，使得同一環(huán)內(nèi)或同一段內(nèi)的各頁可以有上述種種不同的訪問保護，以增強靈活性。

4)在某些應(yīng)用中，我么既要求能實現(xiàn)多個用戶可讀、寫訪問共享的數(shù)據(jù)，但又要保證只當(dāng)一個用戶訪問完該數(shù)據(jù)后，別的用戶才可以訪問，以防止在一個用戶還未把某個共享文件寫好之前，別的用戶卻能把它讀了去?？梢圆捎谩皽y試與置定”和“比較與交換”指令實現(xiàn)這點。所以這也是一種保護方法。第六十五頁，共九十五頁，編輯于2023年，星期五第4章小節(jié)4.1

存貯體系的形成與性能

1.存貯器的性能要求

1)大容量

2)低價格

3)高速度訪問時間TA

存貯周期TM

存貯器頻寬第六十六頁，共九十五頁，編輯于2023年，星期五

4)結(jié)論

由于存貯器的價格、速度和容量的要求是相互矛盾的，為了同時滿足三方面的要求，在一個完整的存貯體系中，必須采用不同工藝的存貯器，使得信息以各種方式分布于不同的存貯體。2.并行主存系統(tǒng)頻寬的分析

1)類型單體單字單體多字多體單字交叉多體多字交叉第六十七頁，共九十五頁，編輯于2023年，星期五

2)分析結(jié)論由于程序的轉(zhuǎn)移概率不會很低，數(shù)據(jù)分布的離散性較大，所以單純靠增大m來提高并行主存系統(tǒng)的頻寬是有限的，而且性價比還會隨m的增大而下降。如果采用并行主存系統(tǒng)仍不能滿足速度上的要求，就必須從系統(tǒng)結(jié)構(gòu)上改進，采用存貯體系。3.存貯體系的形成與分支

1)容量需求主存——輔存存貯層次程序局部性第六十八頁，共九十五頁，編輯于2023年，星期五

2)速度需求

Cache——主存存貯層次程序局部性

3)多級存貯層次4.存貯體系的性能參數(shù)

1)存貯體系的每位平均價格c

2)命中率H=R1/(R1+R2)3)等效訪問時間

TA=HTA1+(1-H)TA2第六十九頁，共九十五頁，編輯于2023年，星期五4.2虛擬存貯器

1.管理方式

1)段式管理

a)思想：根據(jù)程序的模塊性，把一個復(fù)雜的大程序分解成多個邏輯上相對獨立的模塊。

b)段表為了進行段式管理，每道程序都由一個斷表(映像表)，以存放該程序各程序段裝入主存的狀況信息。第七十頁，共九十五頁，編輯于2023年，星期五段名(號)：實際由于段號與行對應(yīng)，省略掉裝入位：表征是(1)否(0)已調(diào)入主存地址：調(diào)入主存時，在主存的起始(絕對)地址段長：段的大小，限制偏移越界訪問方式：只讀、可寫、只執(zhí)行，提供訪問保護

c)段表基址寄存器斷表長度:該道程序的斷數(shù)(斷表行數(shù))

斷表基地址:程序的斷表在主存中的起始地址第七十一頁，共九十五頁，編輯于2023年，星期五

d)虛擬地址基號(程序號):斷表在斷表基址寄存器的位置段號:段在斷表中的位置段內(nèi)位移:所訪問單元在段內(nèi)的偏移

e)實主存管理表占用區(qū)域表可用區(qū)域表

f)可用區(qū)域分配算法首先分配算法最佳分配算法第七十二頁，共九十五頁，編輯于2023年，星期五

2)頁式管理思想：把主存空間和程序空間都機械的等分成固定大小的頁(頁面大小因機器不同而異，一般在512到幾kB)然后按頁順序編號。

3)段頁式管理思想：把內(nèi)存機械的等分成固定大小的頁，把程序按模塊分段，每個段分成與主存頁面大小相同的頁，每道程序通過一個斷表和相應(yīng)于每段的一組頁表來進行定位。問題：二次查表，費時間第七十三頁，共九十五頁，編輯于2023年，星期五2.頁式虛擬存貯器的構(gòu)成

1)地址映像與變換

a)地址映像就是將虛存單元按某種規(guī)則裝入(定位于)實存，即建立多用戶虛地址NS與實存地址np的對應(yīng)關(guān)系。

b)地址變換指的是程序按這種映像關(guān)系裝入實存后，在執(zhí)行時多用戶虛地址NS如何變換成對應(yīng)的實地址np。

c)全相聯(lián)映像讓每道程序的任何虛頁可以映像裝入到主存的任何實頁位置第七十四頁，共九十五頁，編輯于2023年，星期五

2)替換算法

a)目的當(dāng)輔存中的頁面調(diào)入主存發(fā)生頁面爭用時，只有強制騰出主存中某頁后才能接納從輔存調(diào)來的新頁面。替換算法就是解決具體從主存中選擇哪一頁作為被替換的頁。

b)原則有高的主存命中率算法便于實現(xiàn)輔助軟、硬件成本盡量低第七十五頁，共九十五頁，編輯于2023年，星期五

c)常用算法隨機算法(Random,RAND)

先進先出算法(FirstInFirstOut,FIFO)

近期最少使用算法(LeastRecentlyUsed,LRU)

優(yōu)化替換算法(OPT)——衡量標(biāo)準(zhǔn)

d)堆棧型替換算法保證命中率隨主存頁數(shù)的增加只可能提高，至少不會下降。

e)頁面失效頻率法(PFF)

根據(jù)各道程序運行中的主存頁面失效率的高低,由OS來動態(tài)調(diào)節(jié)分配給每道程序的實頁數(shù)。第七十六頁，共九十五頁，編輯于2023年，星期五

3)影響命命中率的因素

a)與替換算法有關(guān)

b)命中率與頁地址流有關(guān)

c)與主存容量(即分配給程序的主存頁數(shù))有關(guān)

4)虛擬存貯器工作的全過程

P144圖4.25頁式虛擬存貯器工作原理第七十七頁，共九十五頁，編輯于2023年，星期五3.頁式虛擬存貯器實現(xiàn)中的問題

1)頁面失效處理后援寄存器技術(shù)預(yù)判技術(shù)解決方法替換算法頁面大小不能過大

2)提高虛擬存貯器等效訪問速度的措施快表——慢表散列快表——硬件實現(xiàn)散列函數(shù)第七十八頁，共九十五頁，編輯于2023年，星期五

3)影響主存命中率和CPU效率的某些因素

a)與Sp有關(guān)

P150圖4.30頁面大小Sp

、容量S1與命中率H的關(guān)系曲線圖

b)命中率與主存容量S1有關(guān)

P151圖4.31命中率H與容量S1的關(guān)系圖

c)與所采用的頁面調(diào)度策略有關(guān)第七十九頁，共九十五頁，編輯于2023年，星期五4.3高速緩沖存貯器(Cache)1.基本結(jié)構(gòu)特點：9個方面(與虛擬存貯器對比)2.地址的映像與變換

1)全相聯(lián)映像和變換

a)規(guī)則：主存中的任意一塊均可映像裝入到Cache內(nèi)的任意一塊的位置。

b)地址變換過程

c)優(yōu)缺點塊沖突率低；代價大，查表速度難以提高。第八十頁，共九十五頁，編輯于2023年，星期五

2)直接映像及其變換

規(guī)則：主存中每一塊只能映像到Cache中唯一一個特定位置：主存的第i塊只能映像到第imod2ncb塊位置上。相當(dāng)于把主存空間按Cache空間分區(qū)，每區(qū)內(nèi)各塊只能按位置一一對應(yīng)到Cache相應(yīng)位置上。

3)組相聯(lián)映象及其變換規(guī)則：把主存按Cache大小分區(qū)，整個Cache是一區(qū)，每個區(qū)再分成相等的組，組內(nèi)分塊。組間直接映象，組內(nèi)各塊全相聯(lián)映象。第八十一頁，共九十五頁，編輯于2023年，星期五

4)段相聯(lián)映象規(guī)則：把主存和Cache分成具有相同的Z塊的若干段，段與段之間采用全相聯(lián)映象，而段內(nèi)各塊之間采用直接映象，實質(zhì)上就是組相聯(lián)映象的特例。3.替換算法的實現(xiàn)

1)堆棧法思想：棧頂恒存放近期最久訪問過的頁的頁號，而棧底恒存放近期最久沒有訪問過的頁的頁號，即準(zhǔn)備被替換掉的頁的頁號。按此思想組成一個硬件堆棧。第八十二頁，共九十五頁，編輯于2023年，星期五

2)比較對法思路：讓各個塊成對組合，用一個觸發(fā)器的狀態(tài)來表示該比較對內(nèi)兩塊訪問的遠(yuǎn)近次序，再經(jīng)門電路就可以找到LRU塊。4.Cache的透明性及性能分析

1)Cache的透明性分析

a)寫回法在CPU執(zhí)行寫操作時，只是把信息寫入Cache，僅當(dāng)需要被替換時，才將已經(jīng)被寫入過的Cache塊先送回主存，然后再調(diào)入新塊。第八十三頁，共九十五頁，編輯于2023年，星期五

b)寫直達法也稱為存直達法，它利用Cache——主存存貯層次在處理機和主存之間的直接通路，每當(dāng)處理機寫入Cache的同時，也通過此通路直接寫入主存。

2)Cache的取算法

a)預(yù)取法

b)塊的大小

c)預(yù)取開銷

3)任務(wù)切換對失效率的影響

a)與任務(wù)的切換頻度(平均時間間隔Qsw)有關(guān)

b)與Cache的容量有關(guān)第八十四頁，共九十五頁，編輯于2023年，星期五

4)影響Cache存貯器性能的因素

a)不命中率與Cache的容量、組的大小和塊的大小的一般關(guān)系看P168圖4.47塊的大小、組的大小與Cache容量對Cache命中率的影響。

b)Cache——主存存貯層次的等效速度與命中率的關(guān)系5.Cache——主存——輔存存貯層次

1)對應(yīng)于虛地址的單元已在Cache中

2)對應(yīng)單元已在主存但尚未調(diào)入Cache3)對應(yīng)單元還不在主存第八十五頁，共九十五頁，編輯于2023年，星期五4.4主存保護

1.存貯區(qū)域的保護

1)頁表保護

2)鍵方式

3)環(huán)式保護

2.訪問方式的保護