第4章儲(chǔ)存體系2

2.直接映象及其變換

1)規(guī)則：主存中每一塊只能映像到Cache中唯一一個(gè)特定位置。

如圖所示，主存的第i塊只能映像到第imod2ncb塊位置上。如圖4.35所示：……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ī)則

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

nmnmbnmrncbncrCache地址nc…2ncb項(xiàng)

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

區(qū)號(hào)(按地址訪問存貯器)由2ncb中選1圖4.36直接映象的地址變換過程快速度的直接相聯(lián)地址變換

3)優(yōu)缺點(diǎn)優(yōu)點(diǎn)：a)所需硬件簡單，只需要容量較小的按地址訪問的區(qū)號(hào)標(biāo)志表存貯器和少量外比較電路，因此成本低。b)訪問Cache與訪問區(qū)號(hào)表、比較區(qū)號(hào)是否相符的操作是同時(shí)進(jìn)行的。當(dāng)Cache命中時(shí)就意味著省去了地址變換所花費(fèi)的時(shí)間。

缺點(diǎn)：直接映象法最致命的缺點(diǎn)就是Cache的塊沖突率很高。只要有兩個(gè)或兩個(gè)以上經(jīng)常使用的塊恰好被映象到Cache的同一個(gè)塊位置時(shí)，就會(huì)使得Cache的命中率急劇下降。而且，即使此時(shí)Cache中有大量的空閑塊存在，仍然會(huì)發(fā)生塊失效和塊沖突，無法使用Cache中的空閑塊，所以，Cache的利用率很低。正是因?yàn)檫@個(gè)原因才使得目前采用直接映象的Cache存貯器很少了。3.組相聯(lián)映象及其變換組相聯(lián)方式是目前在Cache中用得比較多的一種地址映象和變換方式。它是介于全相聯(lián)和直接相聯(lián)之間的一種折中方案。

思想：簡要說明如下圖4.37所示，將Cache空間和主存空間都分組，每組S塊(S＝2s)。Cache一共2ncb個(gè)塊，分成Q組(Q=2q)，整個(gè)Cache是一區(qū)。主存分成與Cache一樣大小的2nd個(gè)區(qū)，其地址按區(qū)號(hào)、組號(hào)、組內(nèi)塊號(hào)、塊內(nèi)地址分成對(duì)應(yīng)的4個(gè)字段。主存地址的組號(hào)、組內(nèi)塊號(hào)分別用q、s'字段表示，它們的寬度和位置與Cache地址的q、s是一致的。規(guī)則：組相聯(lián)映象指的是各組之間直接映象，但組內(nèi)各塊間則是全相聯(lián)映象。如圖4.37所示。為了實(shí)現(xiàn)主存塊號(hào)到Cache塊號(hào)的變換，需要一個(gè)由高速小容量存儲(chǔ)器做成的塊表存儲(chǔ)器。塊表存儲(chǔ)器采用按地址訪問和按相聯(lián)訪問兩種方式工作。在組內(nèi)采用相聯(lián)方式訪問，在組之間采用按地址方式訪問。塊表的容量與Cache的塊容量相等，字長為主存地址中的區(qū)號(hào)E、組內(nèi)塊號(hào)B與Cache地址中的組內(nèi)塊號(hào)b的長度之和。為了提高Cache的訪問速度，可以把Cache的地址變換與訪問Cache并行進(jìn)行，并采用流水線方式工作。

組號(hào)q組內(nèi)塊號(hào)s塊內(nèi)地址ncr組號(hào)q組內(nèi)塊號(hào)s'塊內(nèi)地址nmr區(qū)號(hào)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ī)則

3)討論當(dāng)組相聯(lián)映象的S值大到等于Cache的塊數(shù)(即s=ncb)時(shí)就變成了全相聯(lián)映象，而當(dāng)S值小到只有1塊(即無s字段)時(shí)就變成了直接映象。因此全相聯(lián)映象和直接映象只是組相聯(lián)映象的兩個(gè)極端。在Cache空間大小及塊的大小都已經(jīng)確定的情況下，Cache的總塊數(shù)就定了，但結(jié)構(gòu)設(shè)計(jì)者仍可以對(duì)S和Q值進(jìn)行選擇。Q和S的選取主要依據(jù)對(duì)塊沖突概率、塊失效率、映象表復(fù)雜性和成本、查表速度等的折衷權(quán)衡。組內(nèi)塊數(shù)S愈多，塊沖突概率和塊失效率愈低，映象表愈復(fù)雜、成本愈高，查表速度愈慢。所以通常采用在典型工作負(fù)荷下進(jìn)行模擬而定。4)地址變換組號(hào)q組內(nèi)塊號(hào)s'塊內(nèi)地址nmr區(qū)號(hào)nd組號(hào)q組內(nèi)塊號(hào)s塊內(nèi)地址ncrnmnc直接直接相聯(lián)比較不等塊失效相等?相聯(lián)比較nds's?nd＋s'表的總?cè)萘繛?ncb＝2q·2s行2q組中選12s行組相聯(lián)映象方式與直接映象方式相比，最明顯的優(yōu)點(diǎn)是塊的沖突概率大大降低。組相聯(lián)映象方式與全相聯(lián)映象方式相比，實(shí)現(xiàn)起來要容易得多，但Cache的命中率與全相聯(lián)映象方式很接近。因此，組相聯(lián)映象方式在許多機(jī)器中得到廣泛的應(yīng)用。在Cache的容量和每塊的大小確定之后，可以通過選擇每組的塊容量和Cache的組容量，即分配Cache地址中組號(hào)q和組內(nèi)塊號(hào)s兩個(gè)字段的長度，來優(yōu)化Cache的性能。主要包括塊沖突概率，塊的失效率，查表的速度，實(shí)現(xiàn)的復(fù)雜性和成本等。一般來說，每組的塊容量s越大，塊的沖突概率和Cache的失效率就越低，但由于映象關(guān)系復(fù)雜，查表的速度就越慢，實(shí)現(xiàn)的成本也越越高。

表3.5采用組相聯(lián)映象方式的典型機(jī)器的Cache分組情況機(jī)器型號(hào)Cache的塊容量Cb每組的塊容量GbCache組容量CgDECVAX-11/78010242512Amdahl470/V65122256Inteli860D-Cache2562128Honeywell66/605124128Amdahl470/V720484512IBM370/16810248128IBM303310241664Motolola88110I-Cache2562128當(dāng)每個(gè)組的塊容量增大時(shí)，需要進(jìn)行相聯(lián)訪問的存儲(chǔ)器的容量將增加，造成查表的速度降低，實(shí)現(xiàn)成本增加。但是，當(dāng)每個(gè)組的塊數(shù)太少時(shí)，塊的沖突概率和Cache的失效率就會(huì)增大。例如，當(dāng)每組的塊容量為2時(shí)，主存的各個(gè)分區(qū)中相對(duì)塊號(hào)相同那些塊只能映象到Cache的兩個(gè)特定塊中，當(dāng)這些塊中有兩個(gè)以上是當(dāng)前的常用塊時(shí)，就會(huì)出現(xiàn)所謂的顛簸現(xiàn)象。4.段相聯(lián)映象在全相聯(lián)、直接相聯(lián)、組相聯(lián)映象的基礎(chǔ)上還可以有各種變形，段相聯(lián)就是一例。段相聯(lián)實(shí)質(zhì)上是組相聯(lián)的特例。他是采用組間全相聯(lián)、組內(nèi)直接映象。為了與組相聯(lián)加以區(qū)別，將這種映象方式稱為段相聯(lián)。就是說，段相聯(lián)映象是把主存和Cache分成具有相同的Z塊的若干段，段與段之間采用全相聯(lián)映象，而段內(nèi)各塊之間采用直接映象。如圖4.42所示：塊0塊1塊2Z－1Cache主存…塊0塊1塊2Z－1…≈≈塊0塊1塊2Z－1…塊0塊1塊2Z－1…≈≈塊0塊1塊2Z－1…段0段0(Z個(gè)段)段1段2nmb/Z－1段2ncb/Z－1圖4.42具有每段Z個(gè)塊的斷相聯(lián)映象段間全相聯(lián)段內(nèi)直接4.3.3替換算法的實(shí)現(xiàn)

當(dāng)訪存發(fā)生Cache塊失效，需要把主存塊按所采用的映象規(guī)則裝入Cache時(shí)，如果又出現(xiàn)Cache塊沖突，就必須按某種策略選擇將Cache中的哪一塊替換出去。直接映象及變換方式實(shí)際上不需要替換算法，這是因?yàn)橹鞔嬷械囊粔K只能裝入到Cache的唯一一個(gè)塊中。如果Cache的這一塊是空的，則可以裝入，如果Cache的這一塊已經(jīng)被占用，唯一的辦法就是把它替換出去。

在全相聯(lián)映象及變換方式中，由于主存中的一塊可以裝入的Cache中任意一塊的位置上，因此，它的替換是否也就最復(fù)雜。

在組相聯(lián)及位選擇組相聯(lián)映象及地址變換方式中，需要從Cache同一組內(nèi)的幾個(gè)塊中選擇一塊替換出去。Cache——主存存貯層次的替換算法與虛擬存貯器的類似，不外乎也是FIFO法或LRU法，其中LRU法最為常用。由于虛擬存儲(chǔ)器中的頁面替換算法主要是用軟件實(shí)現(xiàn)的，而且虛擬存儲(chǔ)器都采用全相聯(lián)映象方式。而在Cache中，由于Cache的訪問速度很高，替換算法必須全部用硬件實(shí)現(xiàn)，而且Cache中一般不采用全相聯(lián)映象方式。因此，Cache中的塊替換算法與虛擬存儲(chǔ)器中的頁面替換算法雖然有一些相同的地方，但不相同的地方是主要。

隨機(jī)法Cache替換算法中最簡單的是隨機(jī)法。

在PDP-11/70的Cache采用組相聯(lián)映象方式，每組只有兩塊。當(dāng)發(fā)生塊沖突時(shí)，使用一個(gè)2態(tài)的隨機(jī)數(shù)發(fā)生器，從組內(nèi)的兩塊中任意選擇一塊替換出去。

隨機(jī)法的優(yōu)點(diǎn)是實(shí)現(xiàn)起來非常容易，因此，在有些小型微型計(jì)算機(jī)中被采用。它的缺點(diǎn)是既沒有利用程序的局部性特點(diǎn)，也沒有利用歷史上的塊地址流分布情況，因此，它的效果往往不好。

輪換法及其實(shí)現(xiàn)輪換法通常用于組相聯(lián)映象及地址變換方式中，常見的有兩種實(shí)現(xiàn)方法。

1、每塊一個(gè)計(jì)數(shù)器

2、每組一個(gè)計(jì)數(shù)器

每塊一個(gè)計(jì)數(shù)器

在上面介紹組相聯(lián)及位選擇組相聯(lián)地址變換方式中，塊表內(nèi)用來表示每一塊映象關(guān)系的一個(gè)存儲(chǔ)字由三字段組成，包括主存地址的區(qū)號(hào)E和塊號(hào)B（在位選擇組相聯(lián)映象方式中只有主存地址的區(qū)號(hào)E，沒有塊號(hào)B）、Cache的塊號(hào)b及一個(gè)有效位e。為了實(shí)現(xiàn)輪換法，還要再增加設(shè)置一個(gè)替換計(jì)數(shù)器字段。計(jì)數(shù)器字段的長度與Cache地址中的組內(nèi)塊號(hào)字段的長度相同。替換方法及計(jì)數(shù)器的管理規(guī)則是：被裝入或被替換的塊，它所屬的計(jì)數(shù)器清為“0”，同組的其它塊所屬的計(jì)數(shù)器都加“1”。需要替換時(shí)，在同組中選擇計(jì)數(shù)器的值最大的塊作為被替換的塊。

Solar-16/65機(jī)的Cache采用位選擇組相聯(lián)映象方式。Cache每組的塊容量為4，因此，每塊用一個(gè)2位的計(jì)數(shù)器。剛開始時(shí)，同組的4個(gè)計(jì)數(shù)器均為00。序列初始值裝入塊00裝入塊01裝入塊10裝入塊11替換塊00塊00000001101100塊01000100011011塊10000110000110塊11000110110001一種輪換法的裝入及替換過程2、每組一個(gè)計(jì)數(shù)器

分析上面的方法，實(shí)際上同組內(nèi)的所有塊是按順序輪流替換的。為此，只要為每個(gè)組設(shè)置一個(gè)計(jì)數(shù)器即可。

替換規(guī)則和計(jì)數(shù)器的管理方法很簡單。本組有替換時(shí)，計(jì)數(shù)器加"1"，計(jì)數(shù)器的值就是要被替換出去的塊號(hào)。

輪換法的優(yōu)點(diǎn)是實(shí)現(xiàn)比較簡單。與隨機(jī)法相比，它能夠利用歷史上的塊地址流情況，把最先裝入的塊作為被替換的塊。但是，與隨機(jī)法相同，它也沒有能夠利用程序的局部性特點(diǎn)。因?yàn)樽钕妊b入cache的塊，很可能也是經(jīng)常要使用的塊。因此，它的效果雖然比隨機(jī)法好，但仍然不理想。

堆棧法1)思想我們?cè)?.2.2中講過，LRU法是堆棧型替換算法，也講了對(duì)于LRU算法，堆棧St中由棧頂?shù)綏５椎母黜?xiàng)（行）恒反映出到t時(shí)刻，實(shí)存中各頁被訪問過的近遠(yuǎn)次序，以及每訪問一頁，堆棧St中各項(xiàng)的變換過程。結(jié)果是此堆棧的棧頂恒存放近期最近訪問過的頁的頁號(hào)，而棧底恒存放近期最久沒有方問過的頁的頁號(hào)，即準(zhǔn)備被替換掉的頁的頁號(hào)。那么，我們?cè)贑ache——主存存貯層次中就可以按此思想實(shí)際組成一個(gè)硬件堆棧。

2)過程（塊號(hào)）（塊號(hào)）（塊號(hào)）（塊號(hào)）（塊號(hào)）2ncb個(gè)寄存器需重新排列的塊號(hào)都下推一行被訪問的塊號(hào)（經(jīng)相聯(lián)比較找到）?寄存器堆棧壓入ncb位近期最近訪問過的塊近期最久沒有訪問過的塊圖4.43全相聯(lián)映象LRU法經(jīng)堆棧實(shí)現(xiàn)（需要有相聯(lián)比較功能）3)缺點(diǎn)：這種硬件堆棧既要求具有相聯(lián)比較的功能，又要求能全下移、部分下移和從中間取出一項(xiàng)的功能，成本較高，因此只適用于組相聯(lián)且組內(nèi)塊數(shù)較少的LRU替換場合。4)變形為了避免堆棧中各行存放的內(nèi)容經(jīng)常同時(shí)進(jìn)行下移，以便節(jié)省成本，我們采用另一種變形，即將存放塊號(hào)的寄存器的幾何位置與Cache中的塊號(hào)對(duì)應(yīng)，而用寄存器存放值的大小來表示已被訪問過的遠(yuǎn)近次序。以組相聯(lián)為例，每一組均使用如圖4.44那樣的一個(gè)寄存器組，由2s個(gè)寄存器組成，每個(gè)寄存器為s位寬，可以存放表示從0到2s－1的次序值。如果讓越是最近訪問的，其次序值愈小，則只需通過相聯(lián)比較求最大值（不是相聯(lián)比較相符），找到該最大值所在的寄存器號(hào)，這就是對(duì)應(yīng)Cache中應(yīng)該被替換掉的塊的塊號(hào)。第0塊的訪問次序第1塊的訪問次序第2塊的訪問次序第2s-1塊的訪問次序塊0塊1塊2塊2s-12s個(gè)寄存器

S位（其中一組）Cache存貯器（其中一組）組相聯(lián)LRU法經(jīng)寄存器實(shí)現(xiàn)（每組一個(gè)，需要有相聯(lián)比較功能）2.比較對(duì)法

1)思路比較法的基本思路是讓各個(gè)塊成對(duì)組合，用一個(gè)觸發(fā)器的狀態(tài)來表示該比較對(duì)內(nèi)兩塊訪問的遠(yuǎn)近次序，再經(jīng)門電路就可以找到LRU塊。比如說有ABC三塊，互相之間可以組合成AB、BA、AC、CA、BC、CB6對(duì)，其中AB和BA、AC和CA、BC和CB是重復(fù)的，所以TAB為“1”，表示A比B更近被訪問過；TAB為“0”，則表示B比A更近被訪問過。TAC、TBC也類似定義。這樣，當(dāng)訪問過的次序?yàn)锳-B-C，即最近訪問過的為A，最久未被訪問過的為C，則這三個(gè)觸發(fā)器狀態(tài)分別為TAB＝1，TAC＝1，TBC＝1。如果訪問過的次序?yàn)锽-A-C，C為最久未被訪問過的塊，則此時(shí)必有TAB＝0，TAC＝1，TBC＝1。因此最久未被訪問過的塊C作為被替換掉的塊的話，用布爾代數(shù)式必有：

CLRU＝TAB?TAC?TBC+TAB?TAC?TBC＝TAC?TBC同理可得：BLRU＝TAB?TBC；ALRU＝TAB?TAC因此，完全可以用門、觸發(fā)器等硬件組合實(shí)現(xiàn)，如圖4.45所示：&&&010101TABTACTBC

ALRU

BLRU

CLRU???訪問B訪問C訪問A圖4.15用比較對(duì)法實(shí)現(xiàn)LRU算法

2)分析我們來看比較對(duì)法所用的硬件量。由于每塊均可能作為LRU塊，其信號(hào)需要用一個(gè)與門產(chǎn)生，例如ALRU與門要有從TAB、TAC來的輸入，BLRU門要有從TAB、TBC來的輸入，而與每塊有關(guān)的對(duì)數(shù)個(gè)數(shù)為塊數(shù)減去1，所以與門的扇入數(shù)是塊數(shù)減去1。若p為塊數(shù)，兩兩組合，比較對(duì)觸發(fā)器的個(gè)數(shù)應(yīng)為Cp2，即為p(p-1)/2。表4.2給出了比較對(duì)法塊數(shù)p的取值與門數(shù)、門的輸入端數(shù)及比較對(duì)觸發(fā)器數(shù)的關(guān)系。每組塊容量與所需觸發(fā)器、與門及與門輸入端個(gè)數(shù)的關(guān)系每組塊容量34681664256觸發(fā)器個(gè)數(shù)361528120201632640與門個(gè)數(shù)34681664256與門輸入端個(gè)數(shù)235715632553)總結(jié)替換算法實(shí)現(xiàn)的設(shè)計(jì)要圍繞下面兩點(diǎn)來考慮：a)如何對(duì)每次訪問進(jìn)行記錄（使用位法、堆棧法和比較對(duì)法所用的記錄方法都不同）；b)如何根據(jù)所記錄的信息來判定近期內(nèi)哪一塊最久沒有被訪問過。由此可見，實(shí)現(xiàn)方法和所用的映象方法密切相關(guān)。例如，對(duì)于主存——輔存存貯層次的全相聯(lián)映象宜于采用使用位法或類似的方法，而不宜采用堆棧法和比較對(duì)法；但對(duì)于Cache——主存存貯層次的組相聯(lián)映象，因?yàn)榻M內(nèi)塊數(shù)較少，就宜于采用比較對(duì)法或堆棧法。替換算法的設(shè)計(jì)和實(shí)現(xiàn)也和器件的發(fā)展密切相關(guān)，隨著器件技術(shù)的發(fā)展，尤其是高速相聯(lián)存貯器片子的改進(jìn)，已經(jīng)而且必然會(huì)不斷研制出新的更好的實(shí)現(xiàn)方法。4.3.4Cache的透明性及性能分析1.Cache的透明性分析

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

寫回法是在CPU執(zhí)行寫操作時(shí)，只是把信息寫入Cache，僅當(dāng)需要被替換時(shí)，才將已經(jīng)被寫入過的Cache塊先送回主存，然后再調(diào)入新塊。這種方法也稱為抵觸修改法，類似于虛擬存貯器中進(jìn)行頁面替換時(shí)的情況。因此，Cache——主存存貯層次的地址映象表中需對(duì)Cache中的每個(gè)塊設(shè)置一個(gè)“修改位”，作為該塊裝入Cache后是否被修改過的標(biāo)志。這樣在塊替換時(shí)，根據(jù)該塊的修改位是否位1，就可以決定替換時(shí)是否先將該塊存回主存原來的位置。3)寫直達(dá)法寫直達(dá)法也稱為存直達(dá)法，它利用Cache——主存存貯層次在處理機(jī)和主存之間的直接通路，每當(dāng)處理機(jī)寫入Cache的同時(shí)，也通過此通路直接寫入主存。這樣，在塊替換時(shí)，就不必先寫回主存，而可以立即調(diào)入新頁。顯然，寫回法是把開銷花在每次需要替換的時(shí)候，而寫直達(dá)法則把開銷花在每次寫入Cache時(shí)都附加一個(gè)比寫Cache長的多的寫主存時(shí)間。

4)寫不命中處理當(dāng)出現(xiàn)寫不命中時(shí)，無論是寫回法還是寫直達(dá)法都有一個(gè)在寫時(shí)是否取的問題。一種是不按寫分配法，即當(dāng)Cache寫不命中時(shí)只寫入主存，該寫地址單元所在塊不從主存調(diào)進(jìn)Cache。另一種是按寫分配法，即當(dāng)Cache不命中時(shí)除寫入主存外，還把該寫地址單元所在的塊由主存調(diào)入Cache。這兩種策略對(duì)不同的主存修改算法，其效果不同，但命中率差別不大。目前寫回法一般采用按寫分配法，而寫直達(dá)法則一般采用不按寫分配法。

寫回法和寫直達(dá)法都需要有少量緩沖器。寫回法中緩沖器用于暫存將要寫回的塊，使之不必等待被替換塊寫回主存后才開始進(jìn)行Cache取。寫直達(dá)法中緩沖器則用于緩沖由寫Cache所要求的寫回主存的內(nèi)容，使CPU不必等待這些寫主存完成就能往下運(yùn)行。緩沖器由要存的數(shù)據(jù)和要存入的目標(biāo)地址組成。在寫直達(dá)系統(tǒng)中容量為4的緩沖器就可以顯著改進(jìn)其性能，IBM3033就是這樣用的。要注意的這些緩沖器對(duì)Cache和主存是透明的。在設(shè)計(jì)時(shí)，要處理好可能由它們所引起的錯(cuò)誤(如另一個(gè)處理機(jī)要訪問的主存單元的內(nèi)容正好仍在緩沖器中)。

5)兩種方法對(duì)比寫回法有利于省去許多將中間結(jié)果寫入主存的無謂開銷。但是增加了Cache的復(fù)雜性?？煽啃陨蠈懟胤ú蝗鐚懼边_(dá)法好。具體采用哪種方法還與系統(tǒng)使用場合有關(guān)。如果讓多CPU共享主存交換信息改成共享Cache交換信息，信息的一致性就能得到保證。對(duì)于共享主存的多CPU系統(tǒng)，絕大多數(shù)還是采用各個(gè)CPU都有自己的Cache的方式與共享主存連接。這樣的系統(tǒng)由于Cache的透明性，僅靠寫直達(dá)法并不能保證同一主存單元在各個(gè)Cache中的對(duì)應(yīng)內(nèi)容都一致。如下圖：要采取措施保證讓有此單元的各個(gè)Cache的內(nèi)容都一致才行。CPUACacheaCPUBCacheb主存?????每個(gè)處理機(jī)都有Cache的共享多處理機(jī)系統(tǒng)解決辦法：?采用播寫法：即任何處理機(jī)要寫入Cache時(shí)，不僅要寫入自己Cache的目標(biāo)塊和主存中，還把信息或者播寫到所有Cache有此單元的地方，或者讓所有Cache有此單元的塊作廢以便下次訪問時(shí)按缺塊處理，從主存中重新調(diào)入。?控制某些共享信息（如信號(hào)燈或作業(yè)隊(duì)等）不等進(jìn)入Cache。?目錄表法：即在CPU讀/寫Cache不命中時(shí)，先查主存中的目錄表以判定目錄塊是否在別的Cache內(nèi)，以及是否正在被修改等，然后再?zèng)Q定如何讀寫此塊。

6)第二種問題

Cache內(nèi)容跟不上已變化了的主存內(nèi)容的問題，有兩種解決辦法：當(dāng)I/O處理機(jī)未經(jīng)Cache往主存寫入新內(nèi)容的同時(shí)，由OS經(jīng)某個(gè)專用指令清除整個(gè)Cache。這種辦法的缺點(diǎn)是象我們?cè)谥v述用專用指令清除快表一樣，會(huì)使Cache對(duì)OS和系統(tǒng)程序員成為不透明的，因此并不好。當(dāng)I/O處理機(jī)往主存某個(gè)區(qū)域?qū)懭胄聝?nèi)容時(shí)，由專用硬件自動(dòng)地將Cache內(nèi)對(duì)應(yīng)此區(qū)域地副本作廢，而不必由OS進(jìn)行任何干預(yù)，從而保持Cache的透明性。2.Cache的取算法

1)預(yù)取法

為了便于硬件實(shí)現(xiàn)，通常只預(yù)取直接順序的下一塊，即在訪問到主存的第i塊(不論是否已取進(jìn)Cache)時(shí)，只有第i＋1塊才是可能的預(yù)取塊。至于何時(shí)將該塊取進(jìn)，可以有恒預(yù)取和不命中時(shí)預(yù)取兩種不同的方法。恒預(yù)取指的是只要訪問到主存的第i塊的某個(gè)字，不論Cache是否命中，恒發(fā)預(yù)取指令。不命中時(shí)預(yù)取僅當(dāng)訪問第i塊不命中時(shí)，才發(fā)預(yù)取指令。2)影響命中率的其它因素a)塊的大小：

若每塊的字節(jié)數(shù)過少，預(yù)取的效果不明顯。從預(yù)取的需要出發(fā)，希望塊盡可能大。但若每塊的字節(jié)數(shù)過多，一方面可能會(huì)預(yù)取進(jìn)不需要的信息，另一方面由于Cache容量有限，又可能把正在使用或近期使用到的信息給替換出去，反而降低了命中率。從模擬結(jié)果來看，每塊的字節(jié)數(shù)如果超過了256，就會(huì)出現(xiàn)這種情況。b)預(yù)取開銷：要預(yù)取就要有訪主存開銷和將它取進(jìn)Cache的訪Cache開銷，還要加上把被替換的塊寫回主存的開銷，這些開銷會(huì)增加主存和Cache的負(fù)擔(dān)，干擾和延緩程序的執(zhí)行。由上可知，采用預(yù)取法的效果不能只從命中率的提高來衡量，還需要從所花費(fèi)的開銷多少來考慮。而這種開銷的多少可以通過對(duì)按需取進(jìn)法的不命中開銷與預(yù)取法的不命中開銷和預(yù)取開銷(包括訪存開銷及對(duì)Cache的干擾影響)二者之和的比較來得到。

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

a)按需取進(jìn)法的不命中開銷為：Dc×不命中率(按需取進(jìn)法)b)預(yù)取法不命中的開銷為：Dc×不命中率(預(yù)取法)而預(yù)取法還應(yīng)有預(yù)取開銷，為此，我們?cè)O(shè)：?預(yù)取率：預(yù)取總塊數(shù)/訪存總塊數(shù)?Pa：預(yù)取訪主存和訪Cache的開銷

c)預(yù)取法取進(jìn)預(yù)取塊的開銷為：Pa×預(yù)取率?訪問率：訪Cache的總次數(shù)/程序訪Cache的總次數(shù)，即(程序訪Cache次數(shù)＋預(yù)取訪Cache次數(shù))/程序訪Cache次數(shù)。?Ac：由于預(yù)取訪Cache占用了Cache，延遲、干擾了程序?qū)ache的訪問的預(yù)取干擾開銷。d)預(yù)取法對(duì)程序訪Cache的映象為：Ac×(訪問率－1)e)結(jié)論由上計(jì)算可知，只有下式成立，即：

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

>Dc×不命中率(預(yù)取)＋Pa×預(yù)取率＋Ac×(訪問率－1)時(shí)，預(yù)取法才是可取的。這里，采用緩沖器技術(shù)是減少預(yù)取干擾的好辦法。Cache和主存都設(shè)置預(yù)取專用緩沖器，使預(yù)取訪主存與訪Cache都盡可能在主存、Cache空閑時(shí)進(jìn)行。3.任務(wù)切換對(duì)失效率的影響

1)兩種失效率a)冷啟動(dòng)(Cold－start)失效率：從Cache為空(指新進(jìn)程所需的內(nèi)容都未裝入Cache內(nèi))開始到Cache全部被裝滿這一期間的失效率。b)熱啟動(dòng)(Warm－start)失效率：從Cache為現(xiàn)行進(jìn)程裝滿之后測(cè)出的失效率。

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

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

Qsw值一定時(shí)，若容量過小，存不下該程序的工作區(qū)，那么就會(huì)有很高的熱啟動(dòng)失效率。因此，增大Cache的容量可使這個(gè)矛盾迅速緩解，而使失效率急劇下降；但在容量增大到基本上保護(hù)得了足夠大的工作區(qū)之后，容量大小對(duì)失效率的下降就趨于平緩，也就是說增大容量對(duì)降低失效率已影響不大。3)解決辦法a)增大Cache容量b)修改調(diào)度算法，使任務(wù)切換回來前，有用的信息仍能保留在Cache中而不被破壞。c)設(shè)置多個(gè)Cache，例如設(shè)置兩個(gè)，一個(gè)專用于管理程序，一個(gè)專用于用戶程序。這樣，在管態(tài)和目態(tài)之間切換時(shí)，不會(huì)破壞各Cache中的內(nèi)容。d)對(duì)于某些操作，例如長的向量運(yùn)算、長的字符行運(yùn)算等，可以不經(jīng)過Cache直接進(jìn)行，以避免這些操作由于使用Cache而從Cache中替換出大量更有希望將重新使用的數(shù)據(jù)。4.影響Cache存貯器性能的因素

1)不命中率與Cache的容量、組的大小和塊的大小的一般關(guān)系不命中率1－HcCache容量組的大小一定塊的大小減小(a)不命中率1－HcCache容量塊的大小一定組的大小減小(b)塊的大小、組的大小與Cache容量對(duì)Cache命中率的影響2)Cache——主存存貯層次的等效速度與命中率的關(guān)系設(shè)：tc為Cache的訪問時(shí)間；tm為主存周期；Hc為訪Cache的命中率；則Cache存貯器的等效存貯周期為：ta＝Hctc＋(1－Hc)tm

與主存—輔存存貯層次不同的是一旦Cache不命中，由于主存與CPU之間有直接通路，CPU對(duì)第二級(jí)的訪問時(shí)間就是tm，而不是調(diào)塊時(shí)間再加一個(gè)訪Cache的時(shí)間了。這樣，采用Cache比之于處理機(jī)直接訪問主存，其速度提高的倍數(shù)為：

ρ＝tm/ta＝tm/(Hctc＋(1－Hc)tm)＝1/(1－(1－tc/tm)Hc)因?yàn)镠c總是小于1，可以令Hc＝α/(α+1)，代入上式得：

ρ＝(α+1)從這個(gè)關(guān)系式看到，Cache系統(tǒng)的加速比ρ是命中率H和主存周期Tm與Cache周期TC比值的函數(shù)。在Cache系統(tǒng)中，主存儲(chǔ)器的訪問周期Tm和Cache的訪問周期TC由于受所用器件的限制通常是一定。因此，要提高Cache系統(tǒng)的加速比ρ最好的途徑是提高命中率H。

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

tm+αtc

3)Cache的容量對(duì)機(jī)器速度的影響

對(duì)流水機(jī)器，機(jī)器速度與主存速度、CPU拍寬、Cache容量的可能關(guān)系如圖4.49所示，機(jī)器的單位是MIPS(每秒執(zhí)行百萬條指令)，主存采用多體交叉存取。由圖可見，主存速度和CPU周期一定時(shí)，由不用Cache到Cache容量從4KB增大到64KB，機(jī)器速度有了顯著提高，尤其是在主存速度較低時(shí)。還可以看出，Cache容量的增大，可以顯著降低對(duì)主存速度的要求。

4)總結(jié)

總之，Cache本身的速度與容量都會(huì)影響Cache存貯器的等效訪問速度。如果對(duì)Cache存貯器的等效訪問速度不滿意，需要改進(jìn)的話就要作具體分析：Cache的等效訪問速度與第一級(jí)Cache本身的訪問速度尚差的較遠(yuǎn)-----Cache的命中率低-----提高Cache的命中率入手（調(diào)整組的大小、替換算法以及增大Cache容量）如果實(shí)際的等效訪問速度已經(jīng)非常接近于Cache本身的訪問速度------只有更換更高速的Cache片子。否則，任何其它途徑也是不會(huì)有什么效果的。4.3.5“Cache—主存—輔存”存貯層次三級(jí)存貯層次的地址變換：

CPU提供訪存的虛地址可能需要變換成Cache地址、主存地址或輔存地址。對(duì)應(yīng)于虛地址的單元已在Cache中

這時(shí)就需要把虛地址直接變換成Cache地址來訪問Cache，而不是先把虛地址變換成主存實(shí)地址，再由主存實(shí)地址變換成Cache地址，這樣可以縮短地址變換的時(shí)間。

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

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

這時(shí)就需要把虛地址變換成輔存實(shí)地址去輔存調(diào)頁，同時(shí)還要將虛地址映象變換成主存實(shí)地址將頁調(diào)入主存，以及把虛地址映象變換成Cache地址，將其中的一塊裝入Cache。

2.訪問Cache過程在這三級(jí)存貯層次中通?？偸亲岉摰拇笮∏『脮r(shí)塊的2的冪倍，每一塊的大小又是字的2的冪倍。而且每次用虛頁號(hào)查快表和慢表以取得主存實(shí)地址和用虛地址對(duì)應(yīng)Cache塊號(hào)位置的虛塊號(hào)經(jīng)組相聯(lián)去訪Cache(Cache中每個(gè)單元存放有主存實(shí)地址和對(duì)應(yīng)的數(shù)據(jù))同時(shí)進(jìn)行。若能在快表中找到，就用由快表來的主存實(shí)地址與由Cache中讀出的主存實(shí)地址相比較。當(dāng)兩者相符，存在Cache中該單元的數(shù)據(jù)就是要訪問的虛、實(shí)地址的內(nèi)容。寫Cache的過程與此類似。根據(jù)目前的硬件實(shí)現(xiàn)技術(shù)，除了上面介紹的采用Cache、主存和輔存（磁盤存儲(chǔ)器中的一部分）三個(gè)存儲(chǔ)器構(gòu)成兩個(gè)兩級(jí)存儲(chǔ)系統(tǒng)和一個(gè)三級(jí)存儲(chǔ)系統(tǒng)的方法之外，還有一種新的實(shí)現(xiàn)方法。就是不用主存儲(chǔ)器，只用Cache和輔存兩個(gè)存儲(chǔ)器構(gòu)成“Cache—輔存”存儲(chǔ)系統(tǒng)。這種存儲(chǔ)系統(tǒng)簡稱為全Cache（all-Cache）存儲(chǔ)系統(tǒng)。

全Cache存儲(chǔ)系統(tǒng)的等效訪問周期與Cache很接近，等效存儲(chǔ)容量就是虛擬地址空間的容量。

目前，全Cache存儲(chǔ)系統(tǒng)還處于實(shí)驗(yàn)階段，并沒有商用化。4.4

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

1)主存系統(tǒng)的保護(hù)

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

2)虛擬存貯系統(tǒng)由于界限寄存器方式只適用于每個(gè)用戶程序占用主存一個(gè)或幾個(gè)(當(dāng)有多對(duì)上、下界寄存器時(shí))連續(xù)的區(qū)域；而對(duì)于虛擬存貯系統(tǒng)，由于一個(gè)用戶的各頁能離散地分布于主存內(nèi)，從而無法使用這種保護(hù)方式。對(duì)虛擬存貯系統(tǒng)的主存區(qū)域保護(hù)就需要采用頁表保護(hù)和鍵式保護(hù)等方式。a)頁表保護(hù)每個(gè)程序都有自己的頁表，其行數(shù)等于該程序的虛頁數(shù)。例如它有4頁，則只能有0、1、2、3這4個(gè)虛頁號(hào)。設(shè)由OS建立的程序也表，這4個(gè)虛頁號(hào)分別對(duì)應(yīng)于實(shí)頁號(hào)4、8、10、14，則不論虛地址如何出錯(cuò)，總只能影響主存中分配給該程序的第4、8、10、14號(hào)實(shí)頁。假設(shè)虛頁號(hào)錯(cuò)成5，肯定不可能在該程序的頁表中找到，也就訪問不了主存，當(dāng)然就不會(huì)映象主存中其它程序的區(qū)域。這正是虛擬存貯系統(tǒng)本身固有的保護(hù)機(jī)能，也是它的一大優(yōu)點(diǎn)。為了便于實(shí)現(xiàn)這種保護(hù)，還可以在段表中的每行內(nèi)，不僅設(shè)置頁表起點(diǎn)，還設(shè)置段長(頁數(shù))項(xiàng)。若出現(xiàn)該段內(nèi)的虛頁號(hào)大于段長，則可以發(fā)越界中斷。這種頁表保護(hù)是在沒有形成主存實(shí)地址前進(jìn)行的保護(hù)，使之無法形成能侵犯別的程序區(qū)域的主存地址。然而，若地址形成環(huán)節(jié)由于軟、硬件方面的故障而形成了不屬于本程序區(qū)域的錯(cuò)誤主存地址時(shí)，則上述這種保護(hù)就無能為力了。因此，還應(yīng)采取進(jìn)一步的保護(hù)措施，鍵方式就是其中成功的一種。

b)鍵方式是由OS按當(dāng)時(shí)主存的使用分配狀況給主存的每頁配一個(gè)鍵，稱為存貯鍵，它相當(dāng)于一把“鎖”。所有頁的存貯鍵存在于相應(yīng)的快速寄存器內(nèi)，每個(gè)用戶(任務(wù))的各實(shí)頁的頁存貯鍵都相同。為了打開這把鎖，需要有把“鑰匙”，稱為訪問鍵。每個(gè)用戶的訪問鍵由OS給定，存在處理機(jī)的程序狀態(tài)字(PSW)或控制寄存器中。程序每次訪存前，要核對(duì)主存地址所在頁的存貯鍵是否與該道程序的訪問鍵相符，只有相符才準(zhǔn)訪問。這樣，就是錯(cuò)誤地形成了侵犯別的程序的主存地址，也因?yàn)檫@種鍵保護(hù)而仍然不允許訪問。c)環(huán)狀保護(hù)環(huán)狀保護(hù)把系統(tǒng)程序和用戶程序按其重要性及對(duì)整個(gè)系統(tǒng)能否正常工作的影響程度分層，如圖4.50所示。設(shè)0、1、2三層是系統(tǒng)程序的，之外的各層是同一用戶程序的分層。環(huán)號(hào)大小表示保護(hù)的級(jí)別，環(huán)號(hào)愈大，等級(jí)愈低。在現(xiàn)行程序運(yùn)行前，先由OS定好程序各頁的環(huán)號(hào)，并置入也表。而后把該道程序的開始環(huán)號(hào)送入處理機(jī)內(nèi)的現(xiàn)行環(huán)號(hào)寄存器，并且把OS規(guī)定給該程序的上限環(huán)號(hào)(規(guī)定該程序所能進(jìn)入的最內(nèi)層環(huán)號(hào))也置入相應(yīng)的寄存器。若是Pi在某一時(shí)候?qū)儆趇層各頁的集合，則當(dāng)進(jìn)程執(zhí)行P∈Pi頁內(nèi)的程序時(shí)，允許訪問F∈Pj頁，這里對(duì)應(yīng)的是j≥i。但是如果是j<i時(shí)，則需由OS環(huán)控制例行程序判定這個(gè)內(nèi)向訪問是否允許和是否正確之后才能訪問，否則就是出錯(cuò)，進(jìn)入保護(hù)處理。但j值肯定不能小于給定的上限環(huán)號(hào)。只要j≠i，就進(jìn)入中斷，若允許訪問，則需經(jīng)特權(quán)指令把現(xiàn)行環(huán)號(hào)寄存器的值由i改為j。這種環(huán)式保護(hù)既能保證由于用戶程序的出錯(cuò)不至于侵犯系統(tǒng)程序，也能保證由于同一用戶程序內(nèi)的低級(jí)(環(huán)號(hào)大)的部分的出錯(cuò)而不致破壞其高級(jí)(環(huán)號(hào)小)的部分。這種環(huán)式保護(hù)對(duì)系統(tǒng)程序的研究和調(diào)試運(yùn)行特別有利，因?yàn)榭梢宰龅侥苄薷南到y(tǒng)程序的某些部分而不必?fù)?dān)心會(huì)影響到系統(tǒng)程序已設(shè)計(jì)好并調(diào)好的核心部分。至于如何控制j≠i的跨層訪問，有的機(jī)器規(guī)定只能由規(guī)定的轉(zhuǎn)移指令執(zhí)行，且對(duì)和j>i和j<i分別只能用不同的轉(zhuǎn)移指令。2.訪問方式的保護(hù)

上述種種區(qū)域保護(hù)，如判越界、判建相符、判環(huán)號(hào)相符、判不超出段長等等，都是經(jīng)硬件實(shí)現(xiàn)的，因此速度可以是很快的。這些區(qū)域保護(hù)是對(duì)允許訪問的區(qū)域可以進(jìn)行任何形式的訪問，而對(duì)允許區(qū)域之外，則任何形式的訪問都不允許。但在實(shí)際中，只是這種限制往往適應(yīng)不了各種應(yīng)用的要求，因此還得加上訪問方式的保護(hù)(限制)。對(duì)主存信息的使用可以有讀R、寫W和執(zhí)行E三種方式。相應(yīng)的就有R、W、E訪問方式保護(hù)，這3者的邏輯組合可以反映出各種應(yīng)用要求，如：

R∪W∪E——不允許進(jìn)行任何訪問；R∪W∪E——可以進(jìn)行任何訪問；R∩W∪E——只能進(jìn)行讀訪問；R∪W∩E——只能按數(shù)據(jù)進(jìn)行讀寫；R∪W∩E——只能執(zhí)行，不能作為數(shù)據(jù)使用；R∪E∩W——只能進(jìn)行寫訪問；R∪E∩W——不準(zhǔn)寫訪問。對(duì)前面講過的各種區(qū)域保護(hù)，都可以加上相應(yīng)的訪問方式位以實(shí)現(xiàn)這種訪問限制。至于環(huán)式保護(hù)和也表保護(hù)，可以把R、W、E等訪問方式位設(shè)在各個(gè)程序的段、頁表的各行內(nèi)，使得同一環(huán)內(nèi)或同一段內(nèi)的各頁可以有上述種種不同的訪問保護(hù)，以增強(qiáng)靈活性。在某些應(yīng)用中，我么既要求能實(shí)現(xiàn)多個(gè)用戶可讀、寫訪問共享的數(shù)據(jù)，但又要保證只當(dāng)一個(gè)用戶訪問完該數(shù)據(jù)后，別的用戶才可以訪問，以防止在一個(gè)用戶還未把某個(gè)共享文件寫好之前，別的用戶卻能把它讀了去?？梢圆捎谩皽y(cè)試與置定”和“比較與交換”指令實(shí)現(xiàn)這點(diǎn)。所以這也是一種保護(hù)方法。第4章小節(jié)4.1存貯體系的形成與性能

1.存貯器的性能要求

1)大容量

2)低價(jià)格3)高速度訪問時(shí)間TA

存貯周期TM存貯器頻寬

4)結(jié)論

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

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

1)容量需求主存——輔存存貯層次程序局部性

2)速度需求Cache——主存存貯層次程序局部性3)多級(jí)存貯層次4.存貯體系的性能參數(shù)1)存貯體系的每位平均價(jià)格c

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

TA=HTA1+(1-H)TA24.2虛擬存貯器1.管理方式

1)段式管理

a)思想：根據(jù)程序的模塊性，把一個(gè)復(fù)雜的大程序分解成多個(gè)邏輯上相對(duì)獨(dú)立的模塊。b)段表為了進(jìn)行段式管理，每道程序都由一個(gè)斷表(映像表)，以存放該程序各程序段裝入主存的狀況信息。段名(號(hào))：實(shí)際由于段號(hào)與行對(duì)應(yīng)，省略掉裝入位：表征是(1)否(0)已調(diào)入主存地址：調(diào)入主存時(shí)，在主存的起始(絕對(duì))地址段長：段的大小，限制偏移越界訪問方式：只讀、可寫、只執(zhí)行，提供訪問保護(hù)c)段表基址寄存器斷表長度:該道程序的斷數(shù)(斷表行數(shù))斷表基地址:程序的斷表在主存中的起始地址d)虛擬地址基號(hào)(程序號(hào)):斷表在斷表基址寄存器的位置段號(hào):段在斷表中的位置段內(nèi)位移:所訪問單元在段內(nèi)的偏移e)實(shí)主存管理表占用區(qū)域表可用區(qū)域表f)可用區(qū)域分配算法首先分配算法最佳分配算法2)頁式管理思想：把主存空間和程序空間都機(jī)械的等分成固定大小的頁(頁面大小因機(jī)器不同而異，一般在512到幾kB)然后按頁順序編號(hào)。3)段頁式管理思想：把內(nèi)存機(jī)械的等分成固定大小的頁，把程序按模塊分段，每個(gè)段分成與主存頁面大小相同的頁，每道程序通過一個(gè)斷表和相應(yīng)于每段的一組頁表來進(jìn)行定位。問題：二次查表，費(fèi)時(shí)間2.頁式虛擬存貯器的構(gòu)成1)地址映像與變換a)地址映像就是將虛存單元按某種規(guī)則裝入(定位于)實(shí)存，即建立多用戶虛地址NS與實(shí)存地址np的對(duì)應(yīng)關(guān)系。b)地址變換指的是程序按這種映像關(guān)系裝入實(shí)存后，在執(zhí)行時(shí)多用戶虛地址NS如何變換成對(duì)應(yīng)的實(shí)地址np。c)全相聯(lián)映像讓每道程序的任何虛頁可以映像裝入到主存的任何實(shí)頁位置2)替換算法a)目的當(dāng)輔存中的頁面調(diào)入主存發(fā)生頁面爭用時(shí)，只有強(qiáng)制騰出主存中某頁后才能接納從輔存調(diào)來的新頁面。替換算法就是解決具體從主存中選擇哪一頁作為被替換的頁。b)原則有高的主存命中率算法便于實(shí)現(xiàn)輔助軟、硬件成本盡量低

c)常用算法隨機(jī)算法(Random,RAND)先進(jìn)先出算法(FirstInFirstOut,FIFO)近期最少使用算法(LeastRecentlyUsed,LRU)優(yōu)化替換算法(OPT)——衡量標(biāo)準(zhǔn)d)堆棧型替換算法保證命中率隨主存頁數(shù)的增加只可能提高，至少不會(huì)下降。

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

根據(jù)各道程序運(yùn)行中的主存頁面失效率的高低,由OS來動(dòng)態(tài)調(diào)節(jié)分配給每道程序的實(shí)頁數(shù)。3)影響命命中率的因素

a)與替換算法有關(guān)b)命中率與頁地址流有關(guān)c)與主存容量(即分配給程序的主存頁數(shù))有關(guān)4)虛擬存貯器工作的全過程P144圖4.25頁式虛擬存貯器工作原理3.頁式虛擬存貯器實(shí)現(xiàn)中的問題1)頁面失效處理后援寄存器技術(shù)預(yù)判技術(shù)解決方法替換算法頁面大小不能過大2)提高虛擬存貯器等效訪問速度的措施快表——慢表散列快表——硬件實(shí)現(xiàn)散列函數(shù)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)4.3高速緩沖存貯器(Cache)1.基本結(jié)構(gòu)特點(diǎn)：9個(gè)方面(與虛擬存貯器對(duì)比)2.地址的映像與變換

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

a)規(guī)則：主存中的任意一塊均可映像裝入到Cache內(nèi)的任意一塊的位置。b)地址變換過程c)優(yōu)缺點(diǎn)塊沖突率低；代價(jià)大，查表速度難以提高。2)直接映像及其變換

規(guī)則：主存中每一塊只能映像到Cache中唯一一個(gè)特定位置：主存的第i塊只能映像到第imod2ncb塊位置上。相當(dāng)于把主存空間按Cache空間分區(qū)，每區(qū)內(nèi)各塊只能按位置一一對(duì)應(yīng)到Cache相應(yīng)位置上。3)組相聯(lián)映象及其變換規(guī)則：把主存按Cache大小分區(qū)，整個(gè)Cache是一區(qū)，每個(gè)區(qū)再分成相等的組，組內(nèi)分塊。組間直接映象，組內(nèi)各塊全相聯(lián)映象。

4)段相聯(lián)映象規(guī)則：把主存和Cache分成具有相同的Z塊的若干段，段與段之間采用全相聯(lián)映象，而段內(nèi)各塊之間采用直接映象，實(shí)質(zhì)上就是組相聯(lián)映象的特例。3.替換算法的實(shí)現(xiàn)1)堆棧法思想：棧頂恒存放近期最久訪問過的頁的頁號(hào)，而棧底恒存放近期最久沒有訪問過的頁的頁號(hào)，即準(zhǔn)備被替換掉的頁的頁號(hào)。按此思想組成一個(gè)硬件堆棧。2)比較對(duì)法思路：讓各個(gè)塊成對(duì)組合，用一個(gè)觸發(fā)器的狀態(tài)來表示該比較對(duì)內(nèi)兩塊訪問的遠(yuǎn)近次序，再經(jīng)門電路就可以找到LRU塊。4.Cache的透明性及性能分析1)Cache的透明性分析a)寫回法在CPU執(zhí)行寫操作時(shí)，只是把信息寫入Cache，僅當(dāng)需要被替換時(shí)，才將已經(jīng)被寫入過的Cache塊先送回主存，然后再調(diào)入新塊。b)寫直達(dá)法也稱為存直達(dá)法，它利用Cache——主存存貯層次在處理機(jī)和主存之間的直接通路，每當(dāng)處理機(jī)寫入Cache的同時(shí)，也通過此通路直接寫入主存。

2)Cache的取算法a)預(yù)取法b)塊的大小c)預(yù)取開銷3)任務(wù)切換對(duì)失效率的影響a)與任務(wù)的切換頻度(平均時(shí)間間隔Qsw)有關(guān)