1

存儲系統(tǒng)27.1存儲系統(tǒng)的層次結(jié)構(gòu)CPUCACHE主存（內(nèi)存）輔存（外存）根據(jù)各種存儲器的存儲容量、存取速度和價格比的不同，將它們按照一定的體系結(jié)構(gòu)組織起來，使所放的程序和數(shù)據(jù)按照一定的層次分布在各種存儲器中。31、主存和高速緩存之間的關(guān)系Cache引入:為解決CPU和主存之間的速度差距,提高整機的運算速度,在CPU和主存之間插入的由高速電子器件組成的容量不大,但速度很快的存儲器。Cache特點存取速度最快，容量小，價格貴，存儲控制和管理由硬件實現(xiàn)。Cache工作原理——程序訪問的局部性在較短時間內(nèi)由程序產(chǎn)生的地址往往集中在存儲器邏輯地址空間的很小范圍內(nèi)。這種對局部的存儲器地址頻繁訪問，而對此范圍以外的地址范圍甚少的現(xiàn)象就稱為程序訪問的局部性。CPU與Cache之間的數(shù)據(jù)交換是以字為單位，而Cache與主存之間的數(shù)據(jù)交換是以塊(頁）為單位，一個塊（頁）是由若干字組成，是定長度的。演示4Cache功能演示52、主存與輔存之間的關(guān)系主存:(半導(dǎo)體存儲器組成)優(yōu):速度快缺:容量居中,單位成本較高,價格居中。輔存:(光盤,磁盤)優(yōu):容量大,信息長久保存,單位成本低.缺:存取速度慢CPU將要運行的程序和數(shù)據(jù)存放在主存中，而暫時不用的程序和數(shù)據(jù)存放在輔存中。輔存只與主存進行數(shù)據(jù)交換，不能直接運行,需靠輔助的軟、硬件來實現(xiàn)之。演示67.2高速緩沖存儲器Cache組成:由高速小容量的SRAM和高速緩存控制器組成。功能:將CPU當(dāng)前快要用到的部分數(shù)據(jù)塊由主存復(fù)制到容量小、速度快的Cache中,再由Cache向CPU直接提供它所需要的數(shù)據(jù)。它內(nèi)部存放的是部分主存內(nèi)容的副本。Cache存儲器介于CPU和主存之間，它的工作速度數(shù)倍于主存，全部功能由硬件實現(xiàn)。由于轉(zhuǎn)換速度快，軟件人員絲毫未感到Cache的存在，這種特性稱為Cache的透明性。Cache內(nèi)部是用同主存內(nèi)部同樣大小的塊組成，故由于Cache存儲容量小，所以塊的數(shù)目少在Cache中，每一塊外加有一個標記，指明它是主存的哪一塊的副本，所以該標記的內(nèi)容相當(dāng)于主存中塊的編號，塊內(nèi)字節(jié)數(shù)與主存相同。77.2.1

Cache的組成和工作原理標志塊號塊內(nèi)地址主存地址主存塊號塊內(nèi)地址Cache標記Cache地址 比較器替換算法Cache數(shù)據(jù)去CPU來自CPU不命中命中Cache滿訪數(shù)據(jù)修改標記訪標記NO8數(shù)據(jù)總線Cache替換機構(gòu)可裝進？命中？主存Cache

地址映象變換機構(gòu)主存訪問主存替換CacheCache存儲體塊號塊內(nèi)地址直接通路訪問主存裝入CacheNNYY塊號塊內(nèi)地址CPU主存地址地址總線Cache地址Cache的基本結(jié)構(gòu)Cache替換機構(gòu)由CPU完成Cache存儲體主存Cache

地址映象變換機構(gòu)9Cache的工作原理主存和緩存的編址主存和緩存按塊存儲塊的大小相同B

為塊長~~~~……主存塊號主存儲器012m－1字塊0字塊1字塊M－1主存塊號塊內(nèi)地址m位b位n位M塊B個字緩存塊號塊內(nèi)地址c位b位C塊B個字~~~~……字塊0字塊1字塊C－1012c－1標記Cache緩存塊號10Cache工作原理演示11

7.2.2Cache的組織和管理1.地址映像為了把信息放到Cache存儲器中，必須應(yīng)用某種方法把主存地址定位到Cache中，稱作地址映像。在信息按照這種映像關(guān)系（采用硬件方法實現(xiàn)）裝入Cache后，執(zhí)行程序時應(yīng)將主存地址變換成Cache地址,這個變換過程叫做地址變換。地址的映像和變換是密切相關(guān)的。例如主存容量1MB,Cache容量8KB，其地址結(jié)構(gòu)如圖：主存地址Cache地址

Cache塊號下面介紹幾種基本地址映像方式，它們是全相聯(lián)映像、直接映像和組相聯(lián)映像等。A19主存塊號A10A9塊內(nèi)地址A0A12A11A10

A9塊內(nèi)地址A012

（1）全相聯(lián)映像

全相聯(lián)映像方式是最靈活，但成本最高的一種方式。實際中較少使用。它允許主存中的每一個字塊映像到Cache存儲器的任何一個字塊位置上,也允許從確實已被占滿的Cache存儲器中替換出任何一個舊字塊。它的標記位數(shù)要多，為主存總位數(shù)減去塊內(nèi)的位數(shù)，這樣會使Cache標記容量加大。主要問題是在訪問Cache時，需要和Cache的全部標記進行比較，這樣才能判斷出所訪主存地址的內(nèi)容是否已在Cache中。由于Cache速度要求高，所以全部‘比較’操作都要用硬件實現(xiàn)，通常由“按內(nèi)容尋址的”相聯(lián)存儲器完成（見7.4章節(jié)）。在具體操作時需要設(shè)立一個塊號對照表，凡已裝入Cache中的主存塊號其標識位都要置1，以便快速使用。13圖7.4全相聯(lián)映像主存字塊總位數(shù)減去b

字塊0

字塊1

字塊i

字塊2m-1

…

…

字塊0

字塊1

字塊2c-1

…

標記

標記

標記

主存字

字塊內(nèi)

地址

塊標記

主存儲器

m=

b位

m=

主存地址

cache存儲器

14全相聯(lián)映象主存中的任一塊可以映象到緩存中的任一塊字塊2m－1字塊2c－1字塊1

字塊0……字塊2c－1字塊1字塊0…標記標記標記主存字塊標記

字塊內(nèi)地址主存地址m=t+c

位b位m

=

t+cCache存儲器主存儲器

字塊015全相聯(lián)映象演示16例如某機主存為1MB(20位),要求每頁512B(9位)，要劃分2048頁(占11位);Cache為8KB(13位),每頁512B(9位)，要劃分16頁(占4)11位Cache主存主存地址11位9位主存頁號由于每個Cache頁可以映射2048個主存頁中的任一頁，因此每頁的Cache標記也需要11位，已表明它現(xiàn)在所映象的主存頁號。

標記0頁標記1頁

.

...

..標記15頁0頁1頁…15頁…2047頁主存頁標號

頁內(nèi)地址注：這里的頁相當(dāng)于以上所介紹的字塊。17

(2)直接映像在直接映像方式中，主存和Cache中字塊的對應(yīng)關(guān)系,如圖7.3所示。直接映像函數(shù)可定義為：

j=imod2c

其中j是Cache的字塊號，i是主存的字塊號，主存中有2m個塊,字塊大小為2b字，Cache中有同樣大小的2c個塊。C是Cache高位地址位數(shù),b是Cache低位地址位數(shù)。其做法是先將主存分成與Cache同樣大小的若干個區(qū)（組），每個區(qū)中的某個塊只能固定調(diào)入Cache中的對應(yīng)塊，如第0塊，第2c塊，第2c+1塊，…，只能映像到cache的第0塊，而主存的第1塊，第2c＋1塊第2c+1十1塊，…,只能映像到Cache的第1塊等等。在這種映像方式中，其對應(yīng)關(guān)系是固定的并有一定限制的。18圖7.3

字塊0

字塊1

字塊2c-1

字塊2c

字塊2c+1

字塊2c+1-1

字塊2c+1

字塊2m-1

…

…

字塊0

字塊1

字塊2c-1

…

標記

標記

標記

主存字

cache字塊內(nèi)

塊標記

字塊地址

地址

主存儲器

t位

c位

b位

m位

t位

0

1

2c-1

比較器(t位)

=

≠

主存

地址

有效位=1？

命中

不命中

cache存儲器

*

*假設(shè)cache字塊地址字段內(nèi)容為00…01

19

字塊2m－1

字塊2c+1

字塊2c+1－1

字塊2c

+1

字塊2c

字塊2c－1

字塊1字塊0………主存儲體字塊1

標記字塊0

標記字塊2c－1標記Cache存儲體t位01C－1…字塊字塊地址主存字塊標記t

位c

位b

位主存地址比較器（t位）=≠不命中有效位=1？*m位Cache內(nèi)地址否是命中直接映象每個緩存塊

i

可以和若干個主存塊對應(yīng)每個主存塊

j

只能和一個緩存塊對應(yīng)i=j

mod

C

字塊2c+1

字塊2c

字塊0

字塊020直接映象演示21

例如某機主存為1MB,每頁512B，這樣劃分2048頁，共分0~127組，每組16頁;Cache為8KB,每頁512B，劃分16頁。

7位Cache主存主存地址7位4位9位0組

1組主存頁號

Cache地址標記為組號在訪存時，只需比較兩者標記，如相同則命中127組標記0頁標記1頁

.

.

.

...標記15頁0頁1頁

…15頁16頁17頁

…31頁

…2032頁2033頁

…2047頁主存標記Cache頁號頁內(nèi)地址頁相當(dāng)于字塊22

優(yōu)點是實現(xiàn)簡單，只需利用主存地址,按某些字段直接判斷，即可確定所需字塊是否已在Cache存儲器中。缺點是不夠靈活，即主存的2t個字塊只能對應(yīng)唯一的Cache存儲器字塊。因此,即使Cache存儲器別的許多地址空著也不能占用。這使得Cache存儲空間得不到充分利用，并降低了命中率。23

（3）組相聯(lián)映像組相聯(lián)映像方式是直接映像和全相聯(lián)映像方式的一種折衷方案。組相聯(lián)映像Cache組織如圖7.5所示。即在高速緩沖區(qū)內(nèi)將其容量先分成以組為單位，然后每組內(nèi)在包含若干頁。組相聯(lián)映像方式的性能與復(fù)雜性介于直接映像與全相聯(lián)映像兩種方式之間。設(shè)r為Cache中每組中包含2r個字塊數(shù)，這樣當(dāng)r=0時，它就成為直接映像方式,當(dāng)r=c時，就是全相聯(lián)映像方式。也就是各組是直接映像方式，組內(nèi)的頁執(zhí)行的是全相連映像方式。

Cache的命中率除了與地址映像的方式有關(guān)外，還與Cache的容量有關(guān)。Cache容量大,則命中率就高，但達到一定容量后，命中率的提高就不明顯了。到80486才引進一個8KB的片上Cache，一個用作指令緩存，另一個用作數(shù)據(jù)緩存。它們的塊大小都為32KB，采用兩路組相連的組織方式。24

圖7.5組相聯(lián)映像每組兩個子塊

字塊0

字塊1

字塊2c-r-1

字塊2c-r

字塊2c-r+1

字塊2c-r+1-1

字塊2c-r+1

字塊2m-1

…

…

主存儲器

…

標記

字塊0標記

字塊1

標記

字塊0標記

字塊1

標記

字塊0標記

字塊1

…

…

…

…

cache(r=1)

組

0

1

2c-r-1

主存字塊標記

組地址

塊內(nèi)地址

t+r位

c’=c-rb位

主存地址

25字塊2m－1字塊2c-r+1

字塊2c-r+

1字塊2c-r字塊2c-r

－

字塊1字塊0………字塊3標記字塊1標記字塊2c－1標記字塊2標記字塊0標記字塊2c－2標記…………字塊內(nèi)地址組地址主存字塊標記s=t+r

位q=

c－r

位b

位組012c-r－1主存地址Cache主存儲器m

位共Q

組，每組內(nèi)兩塊（r=1)1某一主存塊

j

按模Q

映射到緩存的第i

組中的任一塊i=j

mod

Q直接映象全相聯(lián)映象組相聯(lián)映象字塊0字塊1字塊0字塊2c-r字塊2c-r+126組相聯(lián)映象演示27

例如某機主存為1MB（2048頁），共分0~255組，每組8頁，每頁512B;Cache為8KB,（16頁），共為8組，每組2頁，每頁512B

8位Cache主存主存頁標記0組7位3位1位9位1組0組

Cache地址

1組7組255組訪存時根據(jù)主存地址的中間4位，找到Cache頁，將其標記與主存頁標記進行比較，判斷是否是主存中的副本，即訪問是否命中。

標記標記0頁1頁標記標記2頁3頁……標記標記14頁15頁0頁1頁……7頁8頁9頁……15頁……2047頁主存組號Cache組號組內(nèi)頁號頁內(nèi)地址282.Cache的寫入操作寫貫穿（全寫法）（Writethrough):

同時寫入Cache和主存。保證主存和Cache內(nèi)容相同,方法簡單可靠。對Cache的更新同時要寫主存,速度會受影響。寫回法(Copyback)：先將更新內(nèi)容寫入Cache，并做標記，在特定時間將Cache內(nèi)容寫入主存。省去不必要的立即回寫操作；回寫式系統(tǒng)機構(gòu)比較復(fù)雜。寫一次法：寫命中與未命中的處理方法與寫回法基本相同，只是第一次寫命中是要同時寫入主存。Pentium機的L2級Cache采用的是寫回法，L1級數(shù)據(jù)Cache采用的是寫一次法。29

3.替換算法

當(dāng)新的主存字塊需要調(diào)入Cache存儲器，而它的可用位置又已被占滿時，就產(chǎn)生替換算法問題。先介紹兩種替換算法先進先出（FIFO）算法和近期最少使用（LRU）算法。

FIFO算法：在地址變換表中設(shè)置一個歷史位，當(dāng)替換時，總是把一組中最先調(diào)入Cache存儲器的字塊替換出去，它不需要隨時記錄各個字塊的使用情況，所以實現(xiàn)容易且開銷小。LRU算法是把一組中近期最少使用的字塊替換出去。這種替換算法需隨時記錄ache存儲器中各個字塊的使用情況，即頁表為在物理存儲取中的每一頁保留了一個時間或年齡域，以便確定哪個字塊是近期最少使用的字塊。LRU替換算法的平均命中率比FIFO要高，并且當(dāng)分組容量加大時，能提高LRU替換算法的命中率，能較好地反映出程序的局部性的特點。

30

LRU是最常使用的一種算法。其設(shè)計思想是把組中各塊的使用情況記錄在一張表上（如圖7.6所示）。并把最近使用過的塊放在表的最上面。這種算法用硬件實現(xiàn)比較麻煩，經(jīng)常采用修改型LRU算法，如圖7.6所示。

另外還有一種隨機替換法（RAND），這種算法不考慮使用情況，在組內(nèi)隨機選擇一塊來替換，其性能要差些。31

原始狀態(tài)

替換7訪問5訪問1替換6

0

7

5

1

6

1

0

7

5

1

2

1

075

3210

7

4322

0

5433

2

6544

3

7666

4

圖

7.6LRU算法替換登記表

327.2.3Cache的命中率設(shè)NC表示Cache完成存取的總次數(shù)，Nm表示主存完成存取的總次數(shù)，h定義為命中率，則有

h=NC/(NC+Nm)

若tc

表示命中時的Cache存儲周期，tm表示未命中時的主存的存儲周期，1－h(huán)表示未命中率，則Cache、主存系統(tǒng)的平均訪問時間ta為：

ta=htc+(1-h)(tm+tc)≈htc+(1-h)tm即沒有命中時，到主存中去取，然后放入到Cache中再執(zhí)行。設(shè)r=tm/tc表示主存慢于Cache的倍率，e表示訪問效率則有e=tc/ta=tc/[htc+(1-h)tm]=1/[h+(1-h)r=1/[r+(1-r)h]為提高訪問效率，h接近1好。

33

例題：CPU執(zhí)行一段程序時，Cache完成存取的次數(shù)為1900次，主存完成存取的次數(shù)為100次，已知Cache存取周期tc為50ns,主存存取周期tm為250ns,求Cache/主存系統(tǒng)的效率e和平均訪問時間ta

。

解：命中率h的計算h=NC/(NC+Nm)=1900/(1900+100)=0.95平均訪問時間ta的計算ta≈htc+(1－h(huán))tm=0.95×50ns+0.05×250ns=47.5ns+12.5ns=60ns效率的計算e=tc/ta=50ns/60ns=83.3%34

7.2.4多層次Cache存儲器1.指令Cache和數(shù)據(jù)Cache開始實現(xiàn)Cache時，是將指令和數(shù)據(jù)存放在同一Cache中的。后來隨著計算機技術(shù)的發(fā)展和處理速度的加快,存取數(shù)據(jù)的操作經(jīng)常會與取指令的操作發(fā)生沖突，從而延遲了指令的讀取。發(fā)展的趨勢是將指令Cache和數(shù)據(jù)Cache分開而成為兩個相互獨立的Cache。

2.多層次Cache結(jié)構(gòu)當(dāng)芯片集成度提高后，可以將更多的電路集成在一個微處理器芯片中,于是近年來新設(shè)計的快速微處理芯片都將Cache集成在片內(nèi)，片內(nèi)cache的讀取速度要比片外Cache快得多。Pentium微處理器的片內(nèi)包含有8KB數(shù)據(jù)Cache和8KB指令Cache。Cache行的長度為32b，采取兩路組相聯(lián)組織。35

片內(nèi)Cache的容量受芯片集成度的限制，一般在幾十KB以內(nèi)。因此命中率比大容量Cache低，于是推出了二級Cache方案。其中第一級Cache（L1）在處理器芯片內(nèi)部；第二級Cache（L2）在片外，其容量可從幾十KB到幾百KB，采用SRAM存儲器，兩級Cache之間一般有專用總線相連。Pentium微處理器支持片外的第二級Cache。其容量為256KB或512KB。也是采用兩路組相連方案。36奔騰2級cache工作環(huán)境演示377.3虛擬存儲器虛擬存儲器只是一個容量非常大的存儲器的邏輯模型，不是任何實際的物理存儲器。它是借助磁盤等輔助存儲器來擴大主存容量，使之為更大或更多的程序所使用。在虛擬存儲器中不僅有主存和輔存兩級存儲器，還必須有輔助軟、硬件來對它們之間的數(shù)據(jù)實現(xiàn)控制。有了虛擬存儲器，用戶無需考慮所編程序在主存中是否放得下或放在什么位置等問題。特點:1）允許用戶訪問比實際存儲空間大得多的地址空間，虛存空間取決于機器所能提供的虛存地址碼的長度。將當(dāng)前和常用到的內(nèi)容放在主存中，其他還未用到的放在外存中。2）每次訪存都要自動的進行虛實地址的轉(zhuǎn)換38

虛擬存儲系統(tǒng)所采取的映像方式同樣有全相聯(lián)映像、組相聯(lián)映像和直接映像等。替換算法也多采用LRU算法。虛擬主存的實現(xiàn)方法有分頁、分段和段頁式。在分頁式虛擬主存中，地址空間被分成大小相對的虛擬頁。其中的某些頁被映像到物理頁面，其他的頁面則不映像到物理頁面。對映像頁面的訪問將由MMU轉(zhuǎn)換到正確的物理地址。引用一個沒有映像的頁面將產(chǎn)生一個缺頁。主存一輔存層次的信息傳送可采用幾種不同的管理方案，如段、頁或段頁式。7.3.1段式管理方案

段式管理方案是將程序按其邏輯結(jié)構(gòu)分成許多大小不同的、相對獨立的程序段。在采用段式管理的系統(tǒng)中，為了進行地址變換需要為各用戶建立一個段表。段表內(nèi)包括段號、段起點、段長、裝入位和訪問權(quán)等內(nèi)容。任何一個段可從0地址開始編址。訪問權(quán)是指該段所允許的訪問形式，便于以段為單位實現(xiàn)存儲保護。如程序段只允許執(zhí)行不許寫，數(shù)據(jù)段只許讀寫不能執(zhí)行，常數(shù)段只許讀不許寫等。39段式管理方案段號起始位置有效位段長訪問方式以程序的邏輯結(jié)構(gòu)所形成的段作為主存分配單位的存儲器管理方式.段大小可以不相等.每個程序有一個段表(E表示執(zhí)行）段1（1KB）段2（2KB）段3（3KB）段4（1KB）段5（3KB）地址主存空間段1段5段301K4K6063段表邏輯程序空間1011KB2360K13KB451K13KBER,WE,R40段式存儲器地址變換演示41

段式管理系統(tǒng)的優(yōu)點是段的分界與程序的自然分界相對應(yīng)。段的邏輯獨立性，使它易于編譯、管理、修改和保護,也便于多道程序共享。其缺點是容易在段間留下許多空余的零碎存儲空間造成浪費。另外段的起點和終點不定。7.3.2頁式管理方案信息傳送單位是定長的頁（如4KB)，所以虛存和主存的存儲空間都被劃分為等長的固定頁。而把前者稱為虛頁或邏輯頁，而把后者稱為實頁或物理頁。它比段式管理系統(tǒng)的空間浪費要小得多。由于頁不是邏輯上獨立的實體，所以處理保護和共享都沒有段式管理方式容易實現(xiàn)。圖7.13表示某個程序有5頁（邏輯頁號0～4）各頁分別裝入主存不連續(xù)的頁面位置，用頁表記錄邏輯頁號及其所對應(yīng)的實主存頁號，頁表是由操作系統(tǒng)建立的。圖7.13中邏輯頁號0、1、3已分配實主存空間，所以裝入位為1。42頁式管理方案程序空間實存空間邏輯頁號物理頁號01234012345602111123414頁表邏輯頁號物理頁號有效位將虛擬空間和主存空間劃分成大小固定的頁,以頁為分配單位的存儲管理方式.頁的大小隨機器而異，如4KB。每道程序擁有一個頁表頁表自動生成,對程序員透明.演示43

虛擬地址到主存實地址的變換是由頁表來實現(xiàn)的。在頁表中，對應(yīng)每一個虛存頁號有一個表目，表目內(nèi)容至少要包含該虛頁所在的主存頁面地址（頁面號），用它作為實（主）存地址的高字段；與虛擬地址的字地址字段相拼接就產(chǎn)生完整的實主存地址，據(jù)此訪問主存、頁式管理的地址變換如圖7.14所示。通常，在頁表的表項中還包括裝入位(有效位)修改位、替換控制位及其他保護項等組成的控制字。如裝入位為“1’，表示該虛頁已從輔存調(diào)入主存。如裝入位為0，則表示對應(yīng)的虛頁尚未調(diào)入主存，如訪問該頁就要產(chǎn)生頁面失效中斷。啟動輸入輸出子系統(tǒng)，根據(jù)外頁表項目中查得的輔存地址，由磁盤等輔存中讀出新的頁到主存中來。

44

修改位指出主存頁面中的內(nèi)容是否被修改過，替換時是否要寫回輔存；替換控制位指出需替換的頁等。值得注意的問題是在頁式管理中，假設(shè)頁表是保存在主存儲器中，那么在訪問存儲器時首先要查頁表，即使頁面命中，也得先訪問一次主存去查頁表，再訪問主存才能取得數(shù)據(jù)，這就相當(dāng)于主存速度降低了一倍。如果頁面失效，要進行頁面替換，頁面修改，訪問主存次數(shù)就更多了。如果采用把頁表的最活動部分存放在快速存儲器中組成快表，這是減少時間開銷的一種方法。另外在一些影響工作速度的關(guān)鍵部分（如快表）再引入了硬件支持，以縮短訪存時間。這樣，一種經(jīng)快表與慢表實現(xiàn)內(nèi)部地址變換的方式如圖7.15所示。45

圖7.14頁式虛存結(jié)構(gòu)

頁表基地址

頁地址

字地址

控制字

主存頁面號

…

…

…

…

頁地址

字地址

頁面基址寄存器

虛地址

實存地址

頁表

（在主存中）

46

快表由硬件組成，通常稱為轉(zhuǎn)換旁路緩沖器（translationlookasidebuffer，簡稱TLB）。它比實際的頁表小得多，一般在16行～64行之間，快表只是慢表（指主存中的頁表）的小小的副本。查表時，由虛頁號同時去查快表和慢表，當(dāng)在快表中有此虛頁號時，就能很快地找到對應(yīng)的實頁號送入實主存地址寄存器，并使慢表的查找作廢。從而能做到雖采用虛擬存儲器，但訪主存速度幾乎沒有下降。如果在快表中查不到時，那就要費一個訪主存時間查慢表，從慢表中查到實頁號送入實主存地址寄存器并將此虛頁號和對應(yīng)的實頁號同時送入快表。替換快表中某一行內(nèi)容這也要用到替換算法。具體的替換算法如先進先出、近期最少使用和隨機算法等。47

圖7.15使用快表和慢表實現(xiàn)虛實地址變換

虛頁號

字地址

虛地址

實頁號

字地址

實存地址

慢表（在主存中）

（快表中查到）

（按內(nèi)容訪問）

相聯(lián)比較

（快表中查不到）

實頁號

…

控制位

（按地址訪問）

表）（硬件構(gòu)成）…

…

虛頁號

實頁號

快表（TLB16~64行

演示48段頁式管理方案將段式和頁式管理方式結(jié)合起來。段頁式將實際存儲器機械等分成固定大小的頁,程序則按模塊分段,每段又分成與主存頁面大小相同的頁。段頁式管理兼有段式和頁式的優(yōu)點。缺點是在地址映像過程中需要多次查表。49

在這種系統(tǒng)中，虛擬地址轉(zhuǎn)換成物理地址是通過一個段表和一組頁表來進行定位的。段表中的每個表目對應(yīng)一個段，每個表目有一個指向該段的頁表的起始地址（頁號）及該段的控制保護信息。由頁表指明該段各頁在主存中的位置以及是否已裝入、已修改等標志。如果有多個用戶在機器上運行稱為多道程序，多道程序的每一道（每個用戶）需要一個基號（用戶標志號），可由它指明該道程序的段表起點（存放在基址寄存器中）。這樣虛擬地址應(yīng)包括基號D、段號S、頁號P、頁內(nèi)地址d。格式如下：段頁式虛擬存儲系統(tǒng)由虛擬地址向?qū)嵵鞔娴刂返淖儞Q至少需查兩次表（段表與頁表）。基號D段號S頁號P頁內(nèi)地址d50段頁式存儲器地址變換演示51

7.3.4虛擬存儲器工作的全過程對虛擬存儲器來說，程序員按虛存儲空間編制程序，在直接尋址方式下由機器指令的地址碼給出地址。這個地址碼就是虛地址，可由虛頁號及頁內(nèi)地址組成，如下所示：這個虛地址實際上不是輔存的實地址，而是輔存的邏輯地址。以磁盤為例按字編址的實地址Nd如下:

NvdNd:在虛擬存儲器中還應(yīng)有虛擬地址到輔存實地址的變換。輔存一般按信息塊編址而不是按字編址，若使一個塊的大小等于一個虛頁面的大小，這樣就只需把虛頁號變換到Nvd

即可完成虛地址到輔存實地址的變換。為此可采用頁表的方式，把由虛頁號Nv變換成輔存實頁號Nvd的表稱為外頁表，而把由Nv變換到主存頁號的表稱為內(nèi)頁表。見書圖7.18所示虛頁號Nv頁內(nèi)地址Nr磁盤機號磁頭號柱面號塊號塊內(nèi)地址52

虛擬存儲器的工作過程（以頁式管理方式為例,見圖7.18）在虛擬存儲器中，CPU首先查內(nèi)頁表判定實存是否命中。若命中，則從內(nèi)頁表中得到實存頁號與頁內(nèi)地址拼接起來構(gòu)成訪問實存的實地址，然后可以使用該實地址可直接去訪問實存（圖中1，2，3）；若不命中則需完成三項任務(wù)：1.向CPU發(fā)出缺頁中斷（圖中4）,執(zhí)行中斷程序到輔存中調(diào)頁。2.通過外部地址轉(zhuǎn)換（5），即查外頁表得到該頁的輔存實地址Nvd；到輔存中去選頁（6），將該頁內(nèi)容通過I/O處理機或通道調(diào)入主存中（7）。并在實存中調(diào)整相應(yīng)頁表（9）。并填寫好外頁表；3.最后查實存頁面分配表，若主存中還有空閑頁面，則從輔存取出的頁面直接寫入實存的空閑頁中，并填寫好內(nèi)頁表（10）。若主存空間以滿，則需根據(jù)所采用的替換算法確定當(dāng)前的被替換頁面（11，12），并填寫好內(nèi)頁表。把確定了的實頁號送入通道（13），進行替換。在進行頁面替換時，如果被替換的頁調(diào)入主存后一直未修改過，則不送回輔存。如果已修改過，則須先將他送回輔存原來的位置（14），而后再把調(diào)入也裝入主存（7），如果所需的頁未裝入輔存，還需在進行中斷，進行出錯處理或其他處理（8）。然后才能用原虛地址去訪問主存。這時肯定是實命中，經(jīng)地址變換后，可直接去訪問主存，完成一次訪問虛擬存儲器的全過程。53虛擬存儲器工作工程演示54

(8)(4)Nvd外部地址變換用戶名頁號頁內(nèi)地址6內(nèi)部地址變換頁面號頁內(nèi)地址實存頁面表替換算法I/O處理機（通道）主存（頁式）輔存輔存實地址多用戶虛地址Ns實存地址np(6)(5)(1)(2)(2)(9)(10)(11)(6)(3)(14)(7)(13)(12)(7)(14)55

可以看出，虛擬存儲系統(tǒng)中存在三個存儲空間：1.主存空間，它取決于系統(tǒng)中實際使用的主存容量；2.虛存空間，它取決于虛地址的長度；3.輔存空間，它取決于系統(tǒng)中實際使用的輔助存儲器的總?cè)萘俊?56

7.3.5Pentium處理機的虛擬存儲器

Pentium存儲器地址轉(zhuǎn)換過程（從虛地址到物理地址）如圖7.1.9所示。Pentium的虛擬地址被稱為邏輯地址，其長度為48位，由16位段地址和32位位移地址構(gòu)成。段地址中有2位用于存儲保護，真正屬于段地址的是14位，所以有效的邏輯地址為46位（14位十32位），虛擬空間為246，訪存地址長度為64T。57

段

位移位移頁

目錄邏輯地址（48位）線性地址（32位）段表物理

地址頁表主存

圖7.19Pentium存儲器地址轉(zhuǎn)換過程58

Pentium采用段頁式地址轉(zhuǎn)換機制，通過段地址查閱段表，將表中地址與位移地址相加后得到32位線性地址，然后通過頁面轉(zhuǎn)換得物理地址。頁面轉(zhuǎn)換是通過頁目錄和頁表實現(xiàn)的（相當(dāng)于2級頁表）線性地址由頁目錄（10位）、頁號（10位）和位移地址（12位）組成，頁面大小為4KB。Pentium還允許將頁面大小設(shè)置為4MB,此時頁面轉(zhuǎn)換只要查一次頁表即可。

Pentium存儲器結(jié)構(gòu)有很大靈活性，根據(jù)其段表和頁表是否設(shè)置可以有4種組合情況。（1）無段表和無頁表的存儲器、非虛擬存儲器其邏輯地址即為物理地址可減少復(fù)雜性，在高性能的控制機中經(jīng)常被采用。（2）無段表和有頁表的存儲器。頁式虛擬存儲器，此時存儲器的管理和保護是通過頁面轉(zhuǎn)換實現(xiàn)的。（3）有段表和無頁表的存儲器。段式虛擬存儲器。（4）有段表和有頁表的存儲器。段頁式虛擬存儲器59Pentium處理機地址變換演示60

7.3.6存儲管理部件（MMU）

現(xiàn)代計算機一般都有輔助存儲器，但具有輔存的存儲系統(tǒng)不一定是虛擬存儲系統(tǒng)。虛擬存儲系統(tǒng)有兩大特點：（1）允許用戶用比主存空間大得多的空間來訪問主存。（2）每次訪