《存儲(chǔ)技術(shù)基礎(chǔ)》課件第5章

第五章計(jì)算機(jī)系統(tǒng)中的存儲(chǔ)管理5.1局部性原理

5.2存儲(chǔ)器層次結(jié)構(gòu)

5.3高速緩沖存儲(chǔ)器

5.4虛擬存儲(chǔ)器

5.5Pentium處理器

小結(jié)

5.1局?部?性?原?理

局部性原理是指在指定時(shí)間內(nèi)，程序趨于在有限的內(nèi)存區(qū)域內(nèi)重復(fù)訪問。我們通常將局部性分為空間局部性和時(shí)間局部性。存儲(chǔ)器層次結(jié)構(gòu)建立在局部性原理的基礎(chǔ)上，局部性原理對(duì)硬件和軟件系統(tǒng)的設(shè)計(jì)有著極大的影響。

空間局部性(SpatialLocality)是指訪問內(nèi)存地址X后很可能會(huì)緊接著訪問內(nèi)存地址X?±?i，其中i是一個(gè)很小的值，X?±?i和X物理鄰近，即已訪問過的內(nèi)存地址附近的位置很可能被連續(xù)訪問。時(shí)間局部性(TemporalLocality)是指在T時(shí)刻訪問過內(nèi)存地址X，在T?±?j時(shí)刻很可能再次訪問內(nèi)存地址X，其中j是一個(gè)很小的值，T?±?j和T時(shí)間鄰近。即已訪問過的內(nèi)存地址在較短的時(shí)間內(nèi)還可能被多次訪問。

考慮圖5.1所示的代碼段，在for循環(huán)體內(nèi)數(shù)組v的元素按照其存儲(chǔ)順序被逐一訪問，因此數(shù)組v有很好的空間局部性，但每個(gè)元素只被訪問了一次，故其時(shí)間局部性很差。整型變量j和N在循環(huán)體內(nèi)被多次訪問，故其時(shí)間局部性很好。for語句代碼被執(zhí)行了N次，故其有較好的時(shí)間和空間局部性。圖5.1for循環(huán)語句的局部性

5.2存儲(chǔ)器層次結(jié)構(gòu)

存儲(chǔ)器層次結(jié)構(gòu)(MemoryHierarchy)建立在局部性原理的基礎(chǔ)上，由具有不同容量、成本和訪問時(shí)間的存儲(chǔ)器構(gòu)成。各種存儲(chǔ)器在性能和價(jià)格上有很大的差別，為了能達(dá)到最佳的性價(jià)比，計(jì)算機(jī)系統(tǒng)都采用將各種不同的存儲(chǔ)器組合起來，形成一個(gè)存儲(chǔ)器層次結(jié)構(gòu)。在存儲(chǔ)器層次結(jié)構(gòu)中，CPU寄存器中存放著最常用的數(shù)據(jù)；Cache作為主存的緩沖區(qū)，存放著主存中的常用數(shù)據(jù)；主存又作為大容量本地磁盤的緩沖區(qū)，存放著本地磁盤上的數(shù)據(jù)；本地磁盤可作為網(wǎng)絡(luò)上遠(yuǎn)程磁盤的緩存。這種金字塔型的層次結(jié)構(gòu)的目的是使存儲(chǔ)系統(tǒng)速度盡量的快，而成本又盡量的低。在圖5.2所示的金字塔型存儲(chǔ)器體系中，最高層M0是距離處理器最近的內(nèi)部寄存器，內(nèi)部寄存器的數(shù)量相對(duì)較少，處理器可以在一個(gè)時(shí)鐘周期內(nèi)快速訪問它們；M1層是高速緩沖存儲(chǔ)器，一般由靜態(tài)存儲(chǔ)器(SRAM)構(gòu)成，處理器可在幾個(gè)時(shí)鐘周期內(nèi)訪問到它們；M2層是由動(dòng)態(tài)存儲(chǔ)器(DRAM)構(gòu)成的主存，處理器可在幾十到幾百個(gè)時(shí)鐘周期內(nèi)訪問到它們；M3層是本地磁盤，同M0、M1、M2層相比，M3層具有速度慢、容量大、價(jià)格低的特點(diǎn)；M4層是可通過網(wǎng)絡(luò)訪問的遠(yuǎn)程服務(wù)器上的磁盤系統(tǒng)。圖5.2存儲(chǔ)器層次結(jié)構(gòu)

5.3高速緩沖存儲(chǔ)器

在CPU-Cache-主存三層存儲(chǔ)器層次結(jié)構(gòu)中，高速緩沖存儲(chǔ)器(Cache)和主存被劃分為連續(xù)的數(shù)據(jù)塊(block)，并以塊的大小為單位在相鄰層之間傳輸。當(dāng)程序要訪問主存中某個(gè)數(shù)據(jù)D時(shí)，CPU首先在Cache的相應(yīng)塊X中查找D，如果D在X中，那么我們說緩沖命中(CacheHit)，程序直接從Cache的X塊中讀取D數(shù)據(jù)，如圖5.3所示；如果D不在X中，我們就說緩沖不命中(CacheMiss)，此時(shí)Cache將主存中包含D數(shù)據(jù)的塊讀入，如圖5.4所示。圖5.3緩沖命中圖5.4緩沖不命中通過上述分析，我們得知，在Cache-主存這種映射機(jī)制中有四個(gè)關(guān)鍵問題需要解決：

(1)主存中的塊如何映射到Cache中？(地址映像)

(2)若請(qǐng)求數(shù)據(jù)在Cache中，CPU如何尋找到Cache中的請(qǐng)求數(shù)據(jù)？(地址變換)

(3)當(dāng)請(qǐng)求數(shù)據(jù)不在Cache中且Cache已滿，此時(shí)需將主存中相應(yīng)塊調(diào)入Cache，如何替換出Cache中的塊？(替換算法)

(4)當(dāng)替換Cache塊時(shí)，如何保持Cache中的塊與主存中的對(duì)應(yīng)塊一致？(寫策略)5.3.1直接映像

直接映像(Direct-MappedCache)是把主存按Cache的大小分為相等的區(qū)，每區(qū)又分為大小相等的塊，主存中不同區(qū)的各塊一一對(duì)應(yīng)Cache的塊，如圖5.5所示。圖5.5直接映像的地址映像因直接映像中Cache塊號(hào)與主存各區(qū)內(nèi)的塊號(hào)一一對(duì)應(yīng)，為了區(qū)分Cache的塊來自主存中的哪個(gè)區(qū)，需要設(shè)置一個(gè)按地址訪問的區(qū)號(hào)表存儲(chǔ)器硬件來記錄放入Cache中塊的區(qū)號(hào)，即當(dāng)主存中的某塊映像到Cache中的對(duì)應(yīng)塊時(shí)，在對(duì)應(yīng)的區(qū)號(hào)表存儲(chǔ)器項(xiàng)中應(yīng)記錄其區(qū)號(hào)，以供地址變換使用。

直接映像的地址變換過程比較簡單。如圖5.6所示，將主存地址劃分為區(qū)號(hào)、塊號(hào)、塊內(nèi)地址三部分，將Cache地址劃分為塊號(hào)和塊內(nèi)地址兩部分。用主存地址中的塊號(hào)部分尋址區(qū)號(hào)表存儲(chǔ)器，讀取區(qū)號(hào)表存儲(chǔ)器對(duì)應(yīng)項(xiàng)所存的區(qū)號(hào)，使其與主存地址的區(qū)號(hào)部分比較。若相等，則Cache命中，直接用主存地址中塊號(hào)和塊內(nèi)地址構(gòu)成Cache地址；若不相等，則Cache不命中，進(jìn)入缺塊處理程序。圖5.6直接映像的地址變換通過對(duì)主存地址進(jìn)行劃分，我們知道請(qǐng)求數(shù)據(jù)是主存第2區(qū)第1塊內(nèi)的第2個(gè)字節(jié)，如圖5.7(a)所示。地址映像時(shí)，將第1塊調(diào)入Cache的第1塊中，在區(qū)號(hào)表第1項(xiàng)中記錄區(qū)號(hào)2，如圖5.7(b)所示。注意，區(qū)號(hào)表和Cache是對(duì)應(yīng)的。圖5.7直接映像的地址映像示例地址變換時(shí)，通過主存地址的塊號(hào)1找到區(qū)號(hào)表的第1項(xiàng)，將其內(nèi)容(10)2取出與主存地址的區(qū)號(hào)比較，若相等則命中，主存地址的塊號(hào)和塊內(nèi)組合(1000000001)2地址即是Cache地址，如圖5.8所示。圖5.8直接映像的地址變換示例直接映像的地址變換比較簡單，可以直接從主存地址中提取Cache地址，并且其區(qū)號(hào)表只需使用普通的按地址訪問存儲(chǔ)器即可。其缺點(diǎn)是地址映像決定了其主存中不同區(qū)的相同塊號(hào)會(huì)被映像到同一個(gè)Cache塊中，從而導(dǎo)致Cache的塊沖突率比較高，即使Cache中其他塊為空時(shí)也無法利用，降低了Cache的命中率和利用率。

直接映像在劃分主存地址時(shí)，用內(nèi)存地址的中間位來做塊索引并非偶然。如果用高位來做塊索引，那么連續(xù)存儲(chǔ)器塊會(huì)映像到同一個(gè)Cache塊中，如圖5.9所示。由局部性原理可知，這樣不利于提高Cache的命中率。圖5.9內(nèi)存地址中間位做塊索引5.3.2全相聯(lián)映像

全相聯(lián)映像(FullAssociativeCache)是指將主存和Cache劃分成大小相等的塊，主存中的任意一塊都可以映像到Cache中的任意一塊，如圖5.10所示。

全相聯(lián)映像使用相聯(lián)存儲(chǔ)器來記錄主存塊和Cache塊的對(duì)應(yīng)關(guān)系，當(dāng)主存中某塊調(diào)入Cache時(shí)，在相聯(lián)存儲(chǔ)器Cache對(duì)應(yīng)項(xiàng)中記錄主存塊號(hào)。

全相聯(lián)映像地址變換過程如圖5.11所示。主存地址和Cache地址均被分為塊號(hào)和塊內(nèi)地址兩部分。用主存塊號(hào)在塊號(hào)表中相聯(lián)比較，若相等，則Cache命中，將相聯(lián)存儲(chǔ)器對(duì)應(yīng)的Cache塊號(hào)與主存的塊內(nèi)地址部分組合起來，形成Cache地址；若均不等，則Cache不命中，進(jìn)入缺塊處理程序。圖5.10全相聯(lián)映像的地址映像圖5.11全相聯(lián)映像的地址變換通過對(duì)主存地址進(jìn)行劃分，我們知道請(qǐng)求數(shù)據(jù)是主存第5塊、塊內(nèi)第2個(gè)字節(jié)，如圖5.12(a)所示。全相聯(lián)地址映像時(shí)，主存中的任意一塊都可以映像到Cache中的任意一塊。我們假設(shè)主存中的第5塊映像到Cache的第2塊中，即將主存第5塊調(diào)入Cache第2塊中，并在塊號(hào)表第2項(xiàng)中記錄主存塊號(hào)5，如圖5.12(b)所示。圖5.12全相聯(lián)映像的地址映像示例地址變換如圖5.13所示，首先將主存地址塊號(hào)5與塊號(hào)表相聯(lián)比較，匹配塊號(hào)表第2項(xiàng)，然后將塊號(hào)表序號(hào)2與主存塊內(nèi)地址(000000001)2組合，構(gòu)成Cache地址(10000000001)2。

全相聯(lián)映像中，主存中的塊可以裝入Cache中任意一塊，只要Cache有空閑塊，就不會(huì)發(fā)生塊沖突，故全相聯(lián)映像是三種映像中Cache利用率最高的。但其地址變換機(jī)制相對(duì)比較復(fù)雜，無法從主存地址直接提取Cache地址，并且需要使用相聯(lián)存儲(chǔ)器來提高查表速度。圖5.13全相聯(lián)映像的地址變換示例5.3.3組相聯(lián)映像

組相聯(lián)映像(SetAssociativeCache)是將主存按Cache的大小分成相等的區(qū)，區(qū)內(nèi)分為大小相等的組，組內(nèi)又分成大小相等的塊，按照組間直接相聯(lián)、組內(nèi)全相聯(lián)的方式進(jìn)行映像，這種方式實(shí)質(zhì)上是前兩種映像方式的折中，如圖5.14所示。圖5.14組相聯(lián)映像的地址映像組相聯(lián)映像采用一種按地址訪問與按內(nèi)容訪問混合的存儲(chǔ)器來存放主存塊與Cache塊的對(duì)應(yīng)關(guān)系表，為了講述方便，我們稱這個(gè)表為區(qū)號(hào)塊號(hào)表。地址映像時(shí)需要將調(diào)入Cache的主存塊的區(qū)號(hào)和塊號(hào)同時(shí)記錄在區(qū)號(hào)塊號(hào)表中，由于組間采用直接相聯(lián)映像，故組號(hào)無需記錄。

組相聯(lián)映像的地址變換過程如圖5.15所示，先依據(jù)主存地址的組號(hào)按地址查找，并鎖定區(qū)號(hào)塊號(hào)表對(duì)應(yīng)組，之后將鎖定組中的各項(xiàng)與主存地址區(qū)號(hào)塊號(hào)部分進(jìn)行相聯(lián)比較。若相等，則Cache命中；反之，Cache不命中，進(jìn)入缺塊處理程序。圖5.15組相聯(lián)映像的地址變換通過對(duì)主存地址進(jìn)行劃分，我們知道請(qǐng)求數(shù)據(jù)位于主存第1區(qū)、第0組、第1塊內(nèi)第2個(gè)字節(jié)，如圖5.16(a)所示。圖5.16組相聯(lián)映像的地址映像示例在地址映像時(shí)，依據(jù)組內(nèi)全相聯(lián)、組間直接相聯(lián)的規(guī)則，主存第1區(qū)、第0組、第1塊可以映像到Cache第0組、第0塊或第0組、第1塊，我們假設(shè)將其映像到第0組、第0塊，并在區(qū)號(hào)塊號(hào)表第1項(xiàng)中記錄對(duì)應(yīng)塊的主存區(qū)號(hào)1和塊號(hào)1，如圖5.16(b)所示。

地址變換如圖5.17所示，首先通過主存組號(hào)0按地址鎖定區(qū)號(hào)塊號(hào)表第0組，然后用主存地址區(qū)號(hào)塊號(hào)部分相聯(lián)比較區(qū)號(hào)塊號(hào)表鎖定組中各項(xiàng)，發(fā)現(xiàn)與第0組第0塊匹配，最后將匹配項(xiàng)的塊號(hào)同主存地址中組號(hào)和塊內(nèi)地址組合，構(gòu)成Cache地址(10000000001)2。圖5.17組相聯(lián)映像的地址變換示例5.3.4替換算法

當(dāng)Cache已滿并且不命中時(shí)，需要將主存塊調(diào)入Cache中，替換算法決定了應(yīng)當(dāng)替換掉Cache中的哪一塊。替換算法應(yīng)盡量找出Cache中最不可能再次被訪問的塊將其替換出去，從而提高命中率和訪問延遲。常用的替換算法有以下幾種。

1.最優(yōu)置換算法OPT(OptimalReplacement)

OPT算法是一種理論上的算法，其基本思想是根據(jù)將來使用塊的時(shí)間作為替換依據(jù)，替換掉Cache中最遠(yuǎn)的將來才會(huì)被訪問的塊。這種算法可以保證最少的缺塊率，但無法完全用程序?qū)崿F(xiàn)，故其一般用來衡量其他算法的優(yōu)劣。

2.先進(jìn)先出算法FIFO(First-In,First-Out)

FIFO算法根據(jù)塊在Cache中的時(shí)間長短作為替換依據(jù)。FIFO算法認(rèn)為是最早調(diào)入Cache中的塊，其以后不再被使用的可能性比剛調(diào)入的可能性大，故總是選擇在Cache中停留時(shí)間最長的塊替換。在算法實(shí)現(xiàn)上，將進(jìn)入Cache的塊按照時(shí)間先后順序排隊(duì)，隊(duì)首是最早進(jìn)入Cache的塊，隊(duì)尾是最晚進(jìn)入Cache的塊，需要替換時(shí)，隊(duì)首的塊首先被替換掉。先進(jìn)先出算法是一種簡單并易于實(shí)現(xiàn)的替換算法，其缺點(diǎn)是較早調(diào)入的塊有可能是經(jīng)常被訪問的塊，這些塊在FIFO算法下會(huì)被反復(fù)調(diào)入調(diào)出，會(huì)導(dǎo)致Cache的命中率較低，故在實(shí)際的系統(tǒng)中很少直接使用FIFO算法。FIFO還有一種異?，F(xiàn)象(Belady’sAnomaly)，即在增加Cache塊的情況下，有可能反而使缺塊率增加，例如：對(duì)主存中塊請(qǐng)求順序?yàn)?，2，1，0，3，2，4，3，2，1，0，4，當(dāng)Cache大小為3時(shí)，缺塊率為9；當(dāng)Cache大小增加為4時(shí)，缺塊率反而變成了10，如表5.1和表5.2所示。表5.1FIFO算法(Cache塊為3，×表示缺塊)表5.2FIFO算法(Cache塊為4，×表示缺塊)

3.第二次機(jī)會(huì)算法(Second-Chance)

第二次機(jī)會(huì)算法是經(jīng)改進(jìn)的FIFO算法。它通過對(duì)塊設(shè)置訪問位來避免把經(jīng)常使用的塊置換出去。與FIFO相似，第二次機(jī)會(huì)算法將進(jìn)入Cache的塊按照時(shí)間先后順序排隊(duì)，在替換隊(duì)列首部的時(shí)候同時(shí)檢查其訪問位，如果是0，就置換塊，如果是1，則保留它，給其第二次機(jī)會(huì)。

4.最近最少使用算法LRU(Leastrecentlyused)

LRU算法將最近的過去作為不久將來的近似，用塊在Cache中未被使用的時(shí)間作為替換依據(jù)，選擇替換最近一段時(shí)間Cache里最久沒有被使用過的塊。LRU算法是一種經(jīng)常被采用的塊替換算法，Pentium處理器的Cache替換策略就采用了LRU算法，PentiumMMX和Intel486采用了一種改進(jìn)的LRU算法—PseudoLRU(也稱做Tree-LRU)。5.3.5寫策略

Cache的寫操作要比讀操作復(fù)雜。假設(shè)CPU對(duì)Cache中某塊Xc進(jìn)行了寫操作，那么此時(shí)Cache中的Xc塊和主存中對(duì)應(yīng)塊Xm會(huì)出現(xiàn)數(shù)據(jù)不一致，為了保持Cache中的Xc塊和主存中對(duì)應(yīng)塊Xm一致，一般情況下，可通過以下兩種策略來更新主存中的Xm塊。

1.直寫法(Write-Through)

直寫法是指在寫Cahce中Xc塊的同時(shí)寫主存Xm塊，即在寫Cache時(shí)同步寫主存。這種方法比較簡單，但每次寫操作都會(huì)引起寫主存，寫主存次數(shù)較多，則效率較低。

2.寫回法(Write-Back)

寫回法是指在寫Cache中Xc塊時(shí)，并不立即寫主存，只有當(dāng)替換算法要替換掉Xc塊時(shí)，才將Xc塊一次性寫入主存Xm塊。這種策略通過盡量推遲對(duì)主存的寫操作，減少寫主存的次數(shù)。寫回法的Cache各塊需要一個(gè)額外的臟數(shù)據(jù)位(DirtyBit)來標(biāo)記Cache塊是否被修改過。

5.4虛?擬?存?儲(chǔ)?器

虛擬存儲(chǔ)器(VirtualMemory)是計(jì)算機(jī)系統(tǒng)中一個(gè)十分重要的概念。虛擬存儲(chǔ)器通常是指將主存作為輔存的緩沖區(qū)，通過硬件和操作系統(tǒng)等機(jī)制，實(shí)現(xiàn)兩者數(shù)據(jù)交互。虛擬存儲(chǔ)器機(jī)制一方面通過硬件和操作系統(tǒng)的配合，為每個(gè)進(jìn)程提供了一個(gè)一致的邏輯地址空間，簡化了存儲(chǔ)器的管理；另一方面，由于主存中只保留了各進(jìn)程的活動(dòng)區(qū)域，不活動(dòng)部分保存在輔存中，使得程序的并行性和主存的利用率大大提高。虛擬存儲(chǔ)器是在20世紀(jì)60年代早期提出的，虛擬存儲(chǔ)器的提出解決了主存過小的題，更重要的是，它使程序員從原本繁瑣的編程模式中解放出來。高速緩存是在20世紀(jì)60年代末才被提出的，其目的是解決CPU和主存速度差距的問題。我們不難發(fā)現(xiàn)虛擬存儲(chǔ)器和高速緩存有許多相似之處，在學(xué)習(xí)時(shí)一些概念可以類比理解，但其所使用的術(shù)語卻并不相同，例如高速緩存中我們稱數(shù)據(jù)為“塊”，而在虛擬存儲(chǔ)器中卻稱為“頁”，這是由時(shí)代所造成的。5.4.1分頁模型

我們可以將主存看做是一個(gè)由相等字節(jié)大小單元組成的數(shù)組，數(shù)組中的各項(xiàng)通過地址來索引，地址是唯一且連續(xù)的。如圖5.18所示，假設(shè)一個(gè)大小為256MB的主存，其第一個(gè)字節(jié)地址為0，接下來的字節(jié)地址為1，以此類推，最后一個(gè)字節(jié)地址為228－1。這里的“地址”是物理地址，早期的PC機(jī)大都使用物理尋址，這種尋址模式無需地址變換，程序直接訪問物理內(nèi)存，程序的靈活性和可移植性比較差。

圖5.18物理尋址圖5.19虛擬尋址虛擬存儲(chǔ)器被分為大小固定的虛頁(VirtualPage)，主存被分為同等大小的頁框(PageFrame)，虛擬存儲(chǔ)器機(jī)制是將虛頁映像到頁框或輔存，一般采用全相連映像，并用頁表(PageTable)來描述兩者的對(duì)應(yīng)關(guān)系。

頁表存儲(chǔ)在主存中，由操作系統(tǒng)負(fù)責(zé)維護(hù)。頁表由頁表?xiàng)l目(PageTableEntry,PTE)構(gòu)成。在我們的模型中，每個(gè)頁表?xiàng)l目由一個(gè)有效位和一個(gè)N位地址字段構(gòu)成。N位地址字段用來索引主存中頁的物理地址，在虛擬地址轉(zhuǎn)換為物理地址時(shí)用來構(gòu)成物理地址的一部分。有效位用來指示虛頁分配情況可分為下面三種情況：

(1)虛頁已分配，緩存在主存中；

(2)虛頁已分配，未緩存在主存中；

(3)虛頁未分配。圖5.20(a)展示了一個(gè)具有8個(gè)虛頁和4個(gè)頁框的虛擬存儲(chǔ)器。其中：vp1、vp2、vp3、vp5四個(gè)虛頁依次被緩存在主存單元3、0、2、1中，屬于第(1)種情況。虛頁vp4和vp7已經(jīng)分配，但未被緩存在主存中，屬于第(2)種情況。虛頁vp0和vp6還未被分配，屬于第(3)種情況。

當(dāng)CPU要讀取的頁在主存中時(shí)，我們說頁命中，反之就是不命中，我們也常稱之為缺頁。假設(shè)CPU首先要讀取vp3頁內(nèi)的數(shù)據(jù)，通過頁表索引到主存中的vp3，且vp3頁命中。緊接著CPU要訪問vp4頁內(nèi)數(shù)據(jù)，頁表有效位為0，故vp4不在主存中，操作系統(tǒng)觸發(fā)缺頁異常。此時(shí)操作系統(tǒng)需將vp4頁調(diào)入主存中，但主存此時(shí)已滿，需要替換出其中一頁。在此我們假設(shè)替換出vp1，如果vp1已被修改，則需要將vp1寫回輔存中，接著操作系統(tǒng)將vp4從輔存中緩存到主存第3單元的位置，同時(shí)更新頁表?xiàng)l目1和4，更新后的頁表如圖5.20(b)所示。

從圖5.20(a)中我們還可看到，連續(xù)的頁表?xiàng)l目1、2、3分別對(duì)應(yīng)主存中不連續(xù)的頁框3、0、2。在虛擬存儲(chǔ)器機(jī)制中，連續(xù)的虛頁通過全相連方式可映射到任意的主存頁框，其好處是使得進(jìn)程在需要連續(xù)的地址空間時(shí)，操作系統(tǒng)沒有必要分配連續(xù)的實(shí)際物理主存空間。圖5.20頁表在實(shí)際情況中，操作系統(tǒng)的每個(gè)進(jìn)程都有一個(gè)獨(dú)立的頁表，虛擬存儲(chǔ)器機(jī)制使得多個(gè)虛頁可以映像到同一個(gè)物理頁框上，為進(jìn)程間的數(shù)據(jù)共享提供了便利。兩個(gè)虛頁映像到同一個(gè)頁框示例如圖5.21所示。圖中，進(jìn)程x虛頁映像用“實(shí)線”表示；進(jìn)程y虛頁映像用“虛線”表示。

最后，頁表?xiàng)l目的字段構(gòu)成遠(yuǎn)比上述模型中的一個(gè)有效位和一個(gè)n位地址字段復(fù)雜得多。因此在實(shí)際情況下，通過在頁表?xiàng)l目中設(shè)置更多的字段，來控制頁的讀寫權(quán)限和訪問權(quán)限等，對(duì)進(jìn)程數(shù)據(jù)起到保護(hù)作用。圖5.21兩個(gè)虛頁映像到同一個(gè)頁框示例5.4.2地址翻譯

虛擬存儲(chǔ)器的地址翻譯通過硬件和操作系統(tǒng)相互協(xié)作來完成。如圖5.22所示，處理器將虛擬地址交給處理器中的MMU單元，MMU負(fù)責(zé)虛擬地址到物理地址的轉(zhuǎn)換工作。在MMU查找主存中的頁表時(shí)，若頁命中，則通過頁表項(xiàng)構(gòu)造物理地址，CPU取得物理地址后訪問主存中的數(shù)據(jù)。若頁不命中，即頁表項(xiàng)有效位為零時(shí)，MMU觸發(fā)缺頁異常，操作系統(tǒng)進(jìn)入缺頁異常處理程序。缺頁異常處理程序決定將請(qǐng)求頁調(diào)入主存，在主存已滿時(shí)，缺頁異常處理程序還需確定主存中的哪個(gè)頁面需要首先換出，換出時(shí)要檢查這個(gè)頁面是否被更新過，如果更新過則需將頁面寫入輔存，然后再將請(qǐng)求頁調(diào)入主存，同時(shí)更新頁表項(xiàng)。圖5.22虛擬存儲(chǔ)器機(jī)制虛擬地址到物理地址的映射是全相連方式，一般將虛擬地址分為虛頁號(hào)和頁偏移兩部分，如圖5.23所示，①表示處理器中的控制寄存器CR3指向當(dāng)前頁表，②表示虛擬地址通過虛頁號(hào)索引頁表，找到對(duì)應(yīng)的頁表項(xiàng)，③表示當(dāng)頁表有效位為1時(shí)，將頁表?xiàng)l目中的物理頁號(hào)同虛擬地址中的頁偏移組合形成物理地址。當(dāng)有效位為0時(shí)，則進(jìn)行缺頁異常處理。圖5.23虛擬地址到物理地址的變換若要通過虛擬地址取得數(shù)據(jù)需經(jīng)過兩次主存訪問。第一次訪問主存中的頁表，取得頁表項(xiàng)，構(gòu)成物理地址；第二次通過物理地址訪問主存，取得請(qǐng)求數(shù)據(jù)。若要加快數(shù)據(jù)的讀取速度，就需要減少對(duì)主存的訪問次數(shù)，實(shí)際中的系統(tǒng)會(huì)使用一個(gè)較小的高速緩存——快表(TranslationLookasideBuffer,TLB)，來緩存部分頁表項(xiàng)，它將把主存的訪問次數(shù)由兩次減少到一次。

快表的結(jié)構(gòu)與頁表類似，依據(jù)程序的局部性原理，快表緩存著最近一段時(shí)間經(jīng)常用到的頁表項(xiàng)，我們可以認(rèn)為它是一個(gè)微型頁表?？毂碇许摫眄?xiàng)與頁表中頁表項(xiàng)的映射關(guān)系同Cache映像方式類似，可相互參考。下面我們以圖5.24來解釋整個(gè)讀操作的過程：

(1)處理器將虛擬地址交給處理器中的MMU單元，MMU查找快表中緩存的頁表項(xiàng)。

①若快表項(xiàng)命中，則通過頁表項(xiàng)物理地址字段構(gòu)造物理地址；

②若快表項(xiàng)未命中，則查找主存中的頁表，將相應(yīng)頁表項(xiàng)調(diào)入快表，通過頁表項(xiàng)物理地址字段構(gòu)造物理地址。

(2)當(dāng)物理地址構(gòu)造完成后，則通過物理地址查看請(qǐng)求數(shù)據(jù)是否在緩存中。

①若在緩存中，直接從緩存中取得請(qǐng)求數(shù)據(jù)；

②若不在緩存中，則需訪問主存，將所需數(shù)據(jù)調(diào)入緩存，然后取得請(qǐng)求數(shù)據(jù)。圖5.24加入快表和數(shù)據(jù)Cache后系統(tǒng)的虛擬存儲(chǔ)器機(jī)制5.4.3小系統(tǒng)舉例

我們先假設(shè)了一個(gè)小系統(tǒng)，通過對(duì)其進(jìn)行分析，來綜合理解虛擬存儲(chǔ)器機(jī)制。小系統(tǒng)的具體參數(shù)：虛擬地址為8位，物理地址為7位，頁大小為4字節(jié)，高速緩存大小共8字節(jié)(分為4塊、每塊2字節(jié))，快表分為4組(每組2個(gè)頁表項(xiàng))，主存按字節(jié)尋址，假設(shè)每次訪問1個(gè)字節(jié)。

虛擬地址和物理地址的格式劃分分別如圖5.25和圖5.26所示。頁大小為4字節(jié)，故虛擬地址低2位為頁偏移，高6位為虛頁號(hào)；物理地址低2位為頁偏移，高5位為物理頁號(hào)。圖5.25虛擬地址的劃分圖5.26物理地址的劃分快表分為4組，每組2個(gè)頁表項(xiàng)，以類似組相聯(lián)的方式映像頁表，用虛頁號(hào)的低2位作為其組號(hào)，用虛頁號(hào)剩余4位作為標(biāo)記，區(qū)分同一組里不同的項(xiàng)，如圖5.27所示。

頁表共64(26)個(gè)表項(xiàng)，存放在主存中，通過虛擬地址虛頁號(hào)部分來索引，如圖5.28所示。圖5.27快表和頁表的劃分圖5.28小系統(tǒng)頁表高速緩存采用全相聯(lián)映像，共4塊，每塊2字節(jié)。物理地址的低1位作為塊內(nèi)地址，高6位作為塊號(hào)，如圖5.29所示。

下面我們來分析比較兩種簡單的讀操作情況：

(1)快表命中，數(shù)據(jù)Cache命中；

(2)快表不命中，頁表命中，數(shù)據(jù)Cache命中。圖5.29高速緩存地址的劃分首先分析第一種情況。我們假設(shè)CPU要讀取0x15處的一個(gè)字節(jié)，如圖5.30所示。圖5.30小系統(tǒng)舉例①?MMU從虛擬地址中取得虛頁號(hào)000101，劃分為標(biāo)記0001和組號(hào)01，通過標(biāo)記和組號(hào)來查找匹配快表表項(xiàng)，與第1組第二表項(xiàng)匹配成功，即快表命中，將對(duì)應(yīng)的物理頁號(hào)00011返回給MMU。

②?MMU將取得的物理頁號(hào)00011同虛擬地址中頁偏移01組合起來，形成物理地址0001101。

③高速緩存從物理地址0001101中取得塊號(hào)000110，同塊號(hào)表相聯(lián)比較，發(fā)現(xiàn)塊號(hào)表第2項(xiàng)與之匹配，即高速緩存命中。組合塊號(hào)表第2項(xiàng)和物理地址的塊內(nèi)地址部分構(gòu)成Cache地址，最終取得目標(biāo)字節(jié)0xFF。接著分析第二種情況。即當(dāng)快表不命中時(shí)，我們假設(shè)CPU要讀取0x05處的一個(gè)字節(jié)，頁表如圖5.28所示，其過程如下：

①?MMU從虛擬地址中取得虛頁號(hào)000001，劃分為標(biāo)記0000和組號(hào)01，通過標(biāo)記和組號(hào)查找匹配快表表項(xiàng)，發(fā)現(xiàn)匹配不成功，即快表不命中。

②?MMU通過虛頁號(hào)000001索引內(nèi)存中的頁表，取得物理頁號(hào)00110，同虛擬地址中頁偏移01組合起來，形成物理地址0011001。

③高速緩存從物理地址0011001中取得塊號(hào)001100，同塊號(hào)表相聯(lián)比較，發(fā)現(xiàn)塊號(hào)表第3項(xiàng)與之匹配，即高速緩存命中。組合塊號(hào)表第3項(xiàng)和物理地址的塊內(nèi)地址部分構(gòu)成Cache地址，最終取得目標(biāo)字節(jié)0xEA。當(dāng)快表不命中，MMU查找頁表，對(duì)應(yīng)的頁表項(xiàng)有效位字段為零時(shí)，還需從輔存中調(diào)入頁面；若數(shù)據(jù)Cache不命中，則還需要進(jìn)行相關(guān)的調(diào)塊操作。

寫操作與讀操作類似。虛擬內(nèi)存讀取的整個(gè)流程如圖5.31所示，不再具體分情況討論，請(qǐng)讀者自己思考。圖5.31虛擬內(nèi)存讀取流程圖

5.5Pentium處理器

1.?L1Cache

PentiumL1Cache內(nèi)部可分為數(shù)據(jù)Cache和指令Cache兩部分，每部分的大小為8KB，分128組，每組2塊，2路組相連映像方式，塊大小為32字節(jié)。數(shù)據(jù)Cache采用了一種MESI協(xié)議，M表示當(dāng)前緩存塊中的數(shù)據(jù)修改過

；E表示當(dāng)前緩存塊中的數(shù)據(jù)未被修改過，和主存中一致；S表示當(dāng)前緩存塊中的數(shù)據(jù)與其他緩存共享；I表示所請(qǐng)求的塊不在當(dāng)前緩存塊中。數(shù)據(jù)Cache各塊需要額外的兩位來存儲(chǔ)MESI狀態(tài)。指令Cache只有S和I兩種狀態(tài)，故只需要1位二進(jìn)制來存儲(chǔ)。替換算法先采用了LRU算法。

PentiumMMX處理器的數(shù)據(jù)Cache和指令Cache擴(kuò)展到了16KB，并采用4路組相連映像方式。替換算法采用了PseudoLRU算法。

2.?L2Cache

L2Cache的大小從512KB到1MB不等，塊大小32字節(jié)，采用