第4章-存儲體系課件

第4章存儲體系4.1存儲體系概念與并行主存系統(tǒng)4.2虛擬存儲器4.3高速緩沖存儲器Cache?本章重點：

段頁式和頁式虛擬存儲器的原理；頁式虛擬存儲器的地址映像；LRU/FIFO/OPT替換算法進行頁面替換的過程模擬；LRU算法對頁地址流的堆棧處理模擬及性能分析；Cache存儲器的直接和組相聯(lián)地址映像；LRU替換算法的硬件實現(xiàn)及替換過程模擬；Cache存儲器的性能分析等。?本章難點：

段頁式和頁式中虛實地址的計算；各種頁面替換算法的模擬和頁面命中率的計算；Cache組相聯(lián)映像和塊替換算法的模擬。4.1存儲體系概念與并行主存系統(tǒng)

4.1.1發(fā)展存儲體系的必要性

1.存儲器的性能要求

1)大容量

2)高速度

3)低價格

2.容量

SM=W·l·m

W：存儲體的字長，單位為bit或Byte。

l：每個存儲體的字數(shù)。

m：并行工作的存儲體的個數(shù)。

3.速度

從下面三個方面來描述：

1)訪問時間TA

TA是存儲器接到訪存到信息被讀到數(shù)據(jù)總線上所需的時間。是確定CPU與存儲器時間關(guān)系的重要指標。

2)存儲周期TMTM是連續(xù)啟動一個存儲體所需要的時間間隔。一般來說總比TA大。3)存儲器頻寬是指存儲器可以提供的數(shù)據(jù)傳送率，一般用每秒鐘所傳送的信息位數(shù)來衡量。a)最大頻寬BM(極限頻寬)是存儲器連續(xù)訪問時能提供的頻寬。單體：BM=W/TMm體并行工作：BM=mW/TM

b)實際頻寬實際頻寬小于最大頻寬BM。

4.價格

可以用總價格C或每位價格c來表示。具有SM位的存儲器每位價格c=C/SM。其中包括了存儲器本身的價格和為該存儲器操作所必須的外圍電路的價格。5.結(jié)論

由于存儲器的價格、速度和容量的要求是矛盾的，為了同時滿足三方面的要求，在一個完整的存儲體系中，必須采用不同工藝的存儲器，使得信息以各種方式分布于不同的存儲體。

比如：

主存

當前活躍的信息，快，少

輔存

暫時不用的信息，慢，多

虛存

swap

從速度來說，主存遠遠跟不上CPU的要求，為

了彌補這一差距，特引入并行和重疊技術(shù)，構(gòu)

成并行主存系統(tǒng)，但這種并行主存的方法提高

頻寬是有限的，因此還需從系統(tǒng)結(jié)構(gòu)入手，發(fā)展存儲體系。4.1.2并行主存系統(tǒng)頻寬的分析1.類型

1)單體單字存儲器字長W與CPU字長W相同,一次訪問一個存儲器字,主存最大頻寬BM=W/TMW位讀出寄存器地址寄存器單體單字存儲器l2)單體多字存儲器字長等于m個CPU字,BM=mW/TM

W位W位W位W位地址寄存器單體多字(m=4)存儲器W位單字長寄存器

3)多體單字交叉總線控制地址寄存器0地址寄存器1地址寄存器2地址寄存器3M0M1M2M3主控(主存控制部件)CPUIOP……………………多體(m=4)交叉存儲器a)存儲器字長等于m個CPU字，BM=mW/TM。實際頻寬大于單體多字。?單體多字：并行讀出的m個字要地址順序的存在于同一主存單元。?多體單字：m個CPU字地址不必順序存放，只要不發(fā)生沖突。b)編址模式Mj體的編制模式為：m·i+j；其中I=0，1，···，l-1，表示第i個字；j=0，1，···，m-1，表示第j個分體；

m—模單體多字：一個主存包含的CPU字數(shù)多體單字：分體體數(shù)模體地址編址序列二進制地址碼末二位狀態(tài)M0M1M2M30,4,8,12,·

·

·,4i+0,···1,5,9,13,·

·

·,4i+1,···2,6,10,14,·

·

·,4i+2,···3,7,11,15,·

·

·,4i+3,···00011011地址的模4低位交叉編址4)多體多字交叉多個存儲體，每個存儲體有CPU字。

上述能并行讀出多個CPU字的單體多字和多體單字或多體多字的交叉存儲主存系統(tǒng)統(tǒng)稱為并行主存系統(tǒng)。2.分析

提高m值，可以提高主存系統(tǒng)的最大頻率，但并不能線性提高實際頻率。

原因：1)模m越高，存儲器數(shù)據(jù)總線越長，導致傳輸延遲增加；2)系統(tǒng)效率問題，對于順序取指，效率可以提高m倍，但遇到轉(zhuǎn)移指令，效率就會下降。3.模型分析

對于m個獨立分體的主存系統(tǒng)，處理機發(fā)出一串地址為A1,A2,…

Aq的訪存申請隊，在每個主存周期到來前，申請隊被掃描，截取從隊頭起的A1,A2,…

Ak的申請序列。申請序列是個在要求訪存申請的k個地址中，沒有兩個或兩個以上的地址處于同一分體中的最長序列。顯然k表示可以同時訪問的分體個數(shù)的隨機變量，不大于m，系統(tǒng)效率取決于k的均值B，其值越大，可訪問的分體個數(shù)越多，系統(tǒng)效率越高。

1)數(shù)學模型

設(shè)p(k)表示申請序列長度為k的概率密度函數(shù)，其中k=1,2,…m。則k的均值B為B=∑k?p(k)B實際就是每個主存周期所訪問的平均字數(shù)。而p(k)與程序的狀態(tài)密切相關(guān)，特別是指令轉(zhuǎn)移概率p，它定義為給定下條指令地址為非順序地址的概率。因此p(k)=(1-p)k-1?p，1≤k<m—幾何概率p(m)=(1-p)m-1k=1m

所以，B=∑k?p(k)=1?p+2?(1-p)?p++m?(1-p)m-1

=(1-(1-p)m)/p2)討論：a)若每條指令都是轉(zhuǎn)移指令且轉(zhuǎn)移成功，即p=1,則B=1，就是并行多體交叉存取的實際頻寬降到和單體單字一樣；b)若所有指令都不轉(zhuǎn)移，即p=0，則B=m，此時多體交叉存儲的效率最高。k=1m…

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

1.容量需求

1)程序覆蓋技術(shù)

方法：將大程序分塊，確定在輔存中的位置并放入輔存，然后根據(jù)要求把當前用到的程序和數(shù)據(jù)調(diào)入主存中指定位置以覆蓋或替換那些已在主存但現(xiàn)在不用的段。這只構(gòu)成一個存儲系統(tǒng)而非存儲體系。主輔存間的調(diào)入調(diào)出完全由程序員安排，增大編程難度和負擔，拉長程序運行時間，也難以使用更好的算法。主存輔存程序員2)增設(shè)輔助軟硬件

隨著I/O處理機的出現(xiàn)及多道程序的發(fā)展，一道程序的運行可以與另一道程序的調(diào)入調(diào)出同時進行。因此主輔存間的地址定位可以改由輔助軟硬件來完成，如圖。這樣就構(gòu)成了存儲體系，或存儲層次。主存輔存輔助軟硬設(shè)備從整體來看，速度是主存的容量是輔存的主存—輔存存儲層次

如果存儲層次能以接近于輔存的每位價格構(gòu)成等于輔存容量的快速主存，存儲系統(tǒng)的性價比就會大大提高。進一步完善發(fā)展就形成虛擬存儲系統(tǒng)。這樣程序員就可以用機器指令的地址碼對整個程序統(tǒng)一編址，這一空間遠大于實際主存空間。這種指令地址碼稱為虛地址、邏輯地址、程序地址等，其對應(yīng)的存儲容量稱為虛存容量或程序空間；而實際主存的地址稱為物理地址、實(存)地址，其對應(yīng)的存儲容量稱為主存容量、實存容量或?qū)?主)存空間。

由于程序空間遠大于主存空間，特別多道程序，每個用戶只用到主存空間的一部分，不能將程序全部裝入主存，只能把程序空間分成較小的塊或頁，由系統(tǒng)負責把所需塊或頁按需調(diào)入主存。當用虛地址訪問主存時，首先檢查其對應(yīng)的內(nèi)容是否已在主存。若在，就由硬件自動把虛地址變換成實地址去訪存；否則需經(jīng)輔助軟硬件將包含所要訪問的單元在內(nèi)的那一塊程序由虛存調(diào)入主存，然后進行訪問。這樣，不論是虛實地址的變換還是程序的調(diào)入都不必程序員安排，而是透明的。也正符合存儲層次的要求。2.速度需求

由于主存和CPU的速度差距已達一個數(shù)量級，為了解決這一問題，提出了多種辦法：

1)在CPU中設(shè)置通用寄存器(GR)，讓運算直接在CPU的GR中進行，減少與主存的交往。但主存與GR間的傳送要由程序設(shè)計者安排，且GR的數(shù)目不能過多。2)采用存儲器的多體交叉并行存取來提高主存的速度。但這種方法對速度的改善有限，且有可能使性價比下降。3)Cache—主存存儲層次通過在CPU與主存間加一級速度高、容量小、每個價格較高的高速緩沖存儲器(Cache)，借助于硬件是Cache和主存構(gòu)成一個整體。信息在Cache與主存間的傳送全部由硬件完成，所以Cache對應(yīng)用程序員和系統(tǒng)程序員都是透明的。高速緩沖Cache主存M輔助硬件CPU從CPU來看，速度是Cache的容量是主存的4)多級存儲層次從M1到Mn，速度變慢，容量增大，價格降低。CPUM1M2M3Mn從CPU來看，速度是M1的，容量是Mn的，價格是Mn的

程序局部性概念：a)時間局部性：在最近的未來要用到的信息很可能是現(xiàn)在正在使用的信息，這是由程序循環(huán)造成的，即循環(huán)中的語句要被重復執(zhí)行。b)空間局部性：在最近的未來要用到的信息很可能與現(xiàn)在正在使用的信息在程序空間上相鄰或相近，這是由于指令通常是順序執(zhí)行的。利用程序局部性，可以預(yù)知下一步要訪問的程序塊而在M1中做好準備。時間局部性：存放近期使用過的塊或頁?？臻g局部性：從M2級把訪問字所在頁或塊一同取到M1中。4.1.4存儲體系的性能參數(shù)

以如圖所示的二級體系(M1,M2)為例來分析

1.存儲體系的每位平均價格cc1?

SM1+c2?

SM2

SM1+SM2

1)M2容量大且便宜，所以，SM1<<SM2，使c接近于c2。

2)應(yīng)使輔助軟硬件的價格占很小比例。

M1M2c1,

SM1,

TA1c2,

SM2,

TA2c

,

SM,

TAc=

2.命中率H

CPU產(chǎn)生的邏輯地址能M1在中訪問到(命中)的概率。

R1表示能在M1中訪問到的次數(shù)；R2表示當時在M2中還未調(diào)到M1的次數(shù)。失效率(不命中率)：1-HR1R1+R2H=

3.等效訪問時間

TA=HTA1+(1-H)TA2

TATA1越好，即訪問效率e=TA1/TA1越好。相鄰兩級的訪問時間比r=TA2/TA1，則：e=TA1/TA=

TA1/(HTA1+(1-H)TA2)=1/(H+(1-H)r)由上式知，要是e趨近1，r越大要求H越高。H提高不易，采用其它方法：a)減小相鄰兩級的訪問速度差距b)減小相鄰兩級存儲器的容量差4.2虛擬存儲器

虛擬存儲器是主存—輔存存儲層次的發(fā)展和完善，主要為了克服高速主存容量滿足不了要求而提出的。在虛擬存儲器中，應(yīng)用程序員直接用機器指令的地址碼對程序統(tǒng)一編址，這一地址碼寬度對應(yīng)的程序空間比實際主存空間大的多，就好像對應(yīng)用程序員來說有一個比實際主存大得多的，可以放得下整個程序得虛(主)存空間。程序不必作任何修改就可以以接近于實際主存的速度在虛擬存儲器上運行。4.2.1不同的虛擬存儲管理方式

程序定位：

由于CPU只能執(zhí)行已裝入主存的程序塊，為了提高主存空間的利用率，應(yīng)及時釋放主存中現(xiàn)已不用的空間以裝入別的程序塊。隨著程序的運行，程序的各個部分就會在主存和輔存間來回調(diào)進調(diào)出。當輔存中的程序調(diào)入主存時，必須進行程序在主存中的定位。這種定位應(yīng)該由系統(tǒng)提供的定位機構(gòu)來自動完成，從而對應(yīng)用程序員透明。

虛擬存儲器程序定位的實現(xiàn)：

虛擬存儲器通過地址映像表來實現(xiàn)程序在主存中的定位。其思想是把程序分割成若干較小的段或頁，用相應(yīng)的映像表機構(gòu)來指明該程序的某段或頁是否已裝入主存。若已裝入，則同時指明其在主存中所處的開始位置；否則去輔存中調(diào)段或頁，并建立起程序空間和主存空間的地址映像關(guān)系。這樣，程序執(zhí)行時通過查映像表將程序虛地址變換成實際主存地址再訪主存。1.段式管理1)思想根據(jù)程序的模塊性，把一個復雜的大程序分解成多個邏輯上相對獨立的模塊。模塊可以是主程序、子程序或過程，也可以是表格、數(shù)組、樹、向量等某類數(shù)據(jù)元素的集合。其大小可以不同，甚至事先無法確定。每個模塊都是一個單獨的程序段，都以該段的起點為0相對編址。調(diào)入主存時，系統(tǒng)按照基址(該段程序在主存中的起始地址)和每個單元在段內(nèi)的相對位移組合來形成各單元在主存的實際地址。這種按段分配的存儲管理方式稱為段式管理。

0段1段2段3段4段5段6段A道程序的程序空間段表長度段表基地址段表基址寄存器(主存中最多有N道道程序)012345605k1k00001111k3k2k訪問方式段長裝入位地址段名(號)a01AN-101k-10000002k-12k-12k-11k-14k-13k-1a7…………實主存空間1k2k3k0段4段2段1k0k5k2.5k段內(nèi)位移段號基號(程序號)多用戶虛地址A41.5k???+???+已裝入段式管理的定位映像機構(gòu)及其地址的變換過程A道程序的段表2)段表為了進行段式管理，每道程序都有一個段表(映像表)，用以存放該程序各程序段裝入主存的狀況信息。段名(號):實際由于段號與行對應(yīng)，省略掉。裝入位:表征是(1)否(0)已調(diào)入主存。地址:調(diào)入主存時，在主存的起始(絕對)地址。段長:段的大小，限制偏移越界。訪問方式:只讀、可寫、只執(zhí)行，提供訪問保護。

3)段表基址寄存器段表長度:該道程序的段數(shù)(段表行數(shù))。段表基地址:程序的段表在主存中的起始地址。

4)虛擬地址基號(程序號):段表在段表基址寄存器的位置。段號:段在段表中的位置。段內(nèi)位移:所訪問單元在段內(nèi)的偏移。5)地址變換如上圖所示。

6)優(yōu)點a)能使大程序分模塊編制，便于多程序員并行編程，縮短編制時間。且各段的修改增添方便。b)便于多道程序共用已在主存的程序和數(shù)據(jù)。c)有利于以段為單位實現(xiàn)存儲保護，這對發(fā)現(xiàn)程序設(shè)計錯誤和非法使用是有用的。

7)實主存管理表為了高效的為調(diào)入段分配主存區(qū)域，OS為整個主存建立一個實主存管理表，來標明主存的使用情況。

a)占用區(qū)域表用來指明主存中的哪些區(qū)域被哪道程序的哪個段占用以及該段程序在主存的起點和長度。

b)可用區(qū)域表用來指明未被占用的區(qū)域的基地址和大小。

8)可用區(qū)域分配算法由于各段的長度不等，必須采用不同的算法對主存可用區(qū)域進行分配。

a)首先分配算法

順序掃描可用區(qū)域表，當找到第一個不小于要調(diào)入段長度的可用區(qū)域時就立即進行分配。優(yōu)點是分配速度快，由于首先分配主存低區(qū)，造成可用區(qū)零頭數(shù)少，而且容易在主存高區(qū)保留較大空間以備容納大程序段。

補充知識：

b)最佳分配算法先全部掃描可用區(qū)域表，然后尋找一個可用區(qū)域進行分配，使之分配后段間可用區(qū)零頭最小。這一算法雖然考慮了盡量減小每一個段間可用區(qū)的零頭，但是會使段間可用區(qū)零頭數(shù)較多。

如下例：補充知識：

ABCAABBCCDEFDEFDE0000.5k0.5k0.5k3k3k3k7k7k7k8k8k8k10k10k10k4k1k2.5k2k6.5k5.5k9k主存程序主存主存(a)需依次調(diào)入D、E、F段(b)首先分配法D、E、F全被裝入(c)最佳分配法F段無法裝入段式存儲分配算法補充知識：2.頁式管理

1)段式管理的缺點

a)各程序段裝入主存的起點是任意的，段表中的地址字段必須能夠表示出主存中的任意一個絕對地址。b)各段長度受程序本身影響也是任意的，所以地址字段和段長字段都很長。c)容易產(chǎn)生較大的段間零頭浪費。如下所示:

0011223456704k-132k-14k4k4k主存頁號虛存頁號主存空間D道程序程序空間程序標志號D基號虛頁號頁內(nèi)位移??實頁號頁內(nèi)位移bnvnrnpNv’Nr專用位訪問方式裝入位主存起點012111267虛存頁號(實頁號)(可省略)D道程序頁表b采用頁式存儲后D道程序可裝入2)頁式管理思想把主存空間和程序空間都機械的等分成固定大小的頁(頁面大小因機器而已，一般在512到幾kB)然后按頁順序編號。

3)主存單元地址np

實頁號nv:主存中實際劃分的頁。頁內(nèi)位移nr:單元在主存頁內(nèi)的偏移量。4)虛地址虛頁號Nv’：程序空間中劃分的頁。頁內(nèi)位移

Nr：等于nr，頁大小相同。

頁內(nèi)位移用戶虛頁號用戶標志u多用戶虛頁號Nv某道程序的地址NiNv’NrX多用戶虛地址Ns???由u轉(zhuǎn)換成基號b頁表基址寄存器0bN-1X?……查到查不到+指向道程序頁表X頁內(nèi)位移實頁號nrnvnp實頁號裝入位nv1X??主存地址寄存器已裝入主存X道程序的內(nèi)頁表Y道程序的內(nèi)頁表頁式管理的定位映像機構(gòu)及其地址的變換過程5)頁表保存虛頁裝入實頁時的頁面對應(yīng)關(guān)系。

虛頁號:與頁表行號相同，可以省略。

實頁號:主存起點。

裝入位:標志該頁是否裝入主存。

訪問方式:用于存儲保護。

專用位:區(qū)分該頁是獨占或共享。

?用戶標志u:指明程序所使用的頁表基址寄存器。?頁表寄存器:存放頁表在主存中的地址。6)地址變換

如上圖。3.段頁式管理

頁式對應(yīng)用程序員完全透明，所需映像表硬件少，地址變換速度快，調(diào)入操作簡單等都優(yōu)于段式。頁式雖然不能完全消除主存可用區(qū)的零頭浪費，因為程序大小不可能恰好是頁面大小的整數(shù)倍，產(chǎn)生的零頭無法利用，但頁內(nèi)零頭比段式的小的多，所以在空間利用率上頁式優(yōu)于段式的。因此很少使用純粹的段式管理存儲器。

然而，段式本身也具有頁式所沒有的優(yōu)點，如：段式中每個段獨立，有利于程序員靈活實現(xiàn)段的鏈接、段的擴大/縮小和修改，而不影響其它段；每段只包含一種類型的對象，若過程或是數(shù)組、堆棧、標量等的集合，易于針對其特定類型實現(xiàn)保護；把共享的程序或數(shù)據(jù)單獨構(gòu)成一個段，易于實現(xiàn)多用戶、進程對共用段的管理等。因此，為了取長補短，提出了把段式和頁式相結(jié)合的段頁式存儲和管理。1)思想把內(nèi)存機械的等分成固定大小的頁，把程序按模塊分段，每個段分成與主存頁面大小相同的頁，每道程序通過一個斷表和相應(yīng)于每段的一組頁表來進行定位。2)段表裝入位:標識該段的頁表是否已裝入主存。地址字段:指明已裝入頁表在主存中的起始地址。訪問方式:指明該段的控制保護信息。段長:指明該段頁表的行數(shù)。3)頁表裝入位:指明此段該頁是否已裝入主存。地址字段:裝入頁在主存中的頁號。

段頁式與純段式的主要區(qū)別是：段的起點不再是因程序段的大小而任意的，必須是位于主存中頁面的起點。對于多道程序來說，每道程序都需要有一個用戶標志號u(轉(zhuǎn)換成基號b)來指明該道程序的段表起點存放在哪個基址寄存器中。

頁內(nèi)位移d頁號p段號s用戶標志u程序標志用戶虛頁號Nv’某道程序的地址Ni

多用戶虛地址NS由u轉(zhuǎn)換成基號b????段表基址寄存器段表長度段表起點c0bN-1?查不到查到+裝入位頁表起點訪問方式段長1d1??某用戶段表主存(多用戶段表)c實頁號裝入位主存(多用戶頁表)1nv??d1+頁內(nèi)位移nrnv實頁號已裝入

主存地址np某用戶s段的頁表段頁式管理的定位映像機構(gòu)及其地址變換過程4)多級頁表在虛擬存儲器中每訪問一次主存都要進行一次程序地址向?qū)嵵鞔娴刂返霓D(zhuǎn)換，段頁式的主要問題就是這個地址變換至少要兩次查表，即查段表和頁表。為了提高虛擬存儲器的速度，必須采取措施加快這種地址轉(zhuǎn)換查表速度。這一問題頁式管理同樣存在，因為前面所講的查頁表是基于整個頁表連續(xù)存儲的，而當頁表的大小超過一個頁面大小時，頁表就會分存于主存中不連續(xù)的頁面上。這樣前述由頁表起點加頁號查得該頁在頁表中的行的查表方式就會出錯。例如：若程序虛地址為24位，其中頁內(nèi)地址Nr為10位，即則頁表就需要214行，而頁面大小只有210行。所以頁表本身可能要分存于16個頁面。為此要建立多級頁表，用頁表基址寄存器指明第一級頁表的基址，用第一級頁表中各行的地址字段指明第二級各個頁表的基址，依此類推。為了節(jié)省存放映像表的主存空間，通常只把第一級頁表駐留在主存內(nèi)，其它各級頁表則根據(jù)需要才調(diào)入，大部分放在輔存中。程序虛地址Nr(10位)Nv’(14位)4.2.2頁式虛擬存儲器的構(gòu)成

1.地址的映像和變換多用戶虛頁號Nv指令中訪存地址NiuNrNv’nrnv多用戶虛地址NS實存地址np實存空間2nv頁2nr2Nr=2nr………2Nv頁包括2u個用戶，每個用戶2Nv’頁虛存總空間虛實地址對應(yīng)關(guān)系及空間的壓縮

頁式虛擬存儲器是采用頁式管理的主存—輔存存儲層次。把主存空間和程序空間都等分成頁，讓程序起點處于頁的起點上。程序員用地址碼Ni來編程，所以Ni由用戶虛頁號Nv’和頁內(nèi)地址Nr組成。主存地址分實頁號nv和頁內(nèi)地址nr兩部分，且nr與Nr一樣。大多數(shù)虛擬存儲器中每個用戶的程序空間比實際主存空間大得多，即一般Nv’大于nv。這樣，虛擬存儲器系統(tǒng)總的多用戶虛地址NS就由用戶標志u、用戶的虛頁號Nv’及頁內(nèi)地址Nr

3部分構(gòu)成，則總的虛存空間為2u?2Nv’頁。

現(xiàn)在把u和Nv’合并成多用戶虛頁號Nv，則2Nv遠遠大于2nv。主存中最多能放N道程序，即N個用戶，其它放在輔存。因此就出現(xiàn)了如何把大的多用戶虛存空間壓縮裝入到小的主存空間中的問題，而在程序運行時又要考慮如何把多用戶虛地址NS變換成主存地址np，再讓CPU去訪問主存中該單元。這就是地址的映像和變換。1)地址映像就是將每個虛存單元按某種規(guī)則(算法)裝入(定位于)實存，即建立多用戶虛地址NS與實存地址np的對應(yīng)關(guān)系。對于頁式就是將多用戶虛頁號Nv的頁可以裝入主存中的哪些頁面位置，建立Nv與nv的對應(yīng)關(guān)系。2)地址變換指的是程序按這種映像關(guān)系裝入實存后，在執(zhí)行時多用戶虛地址NS如何變換成對應(yīng)的實地址np。對頁式而言就是多用戶虛頁號Nv如何變換成實頁號nv。3)頁面爭用由于是把大的虛存空間壓縮到小的主存空間中去，主存中的一個頁面位置就必須能與多個虛頁相對應(yīng)，能對應(yīng)多少個虛頁與采用的映像方式有關(guān)。這就不可避免的發(fā)生有兩個以上的虛頁想要進入同一個主存頁面的現(xiàn)象，這種現(xiàn)象就是頁面爭用或?qū)嶍摏_突。一旦發(fā)生頁面爭用，只能裝入其中的一個虛頁，其它的虛頁只有等到該頁推出主存后方可裝入，這就會使執(zhí)行效率下降。

4)映像方式的選擇a)盡量減少頁面爭用概率；b)考慮減少輔助硬件，降低成本；c)有利于實現(xiàn)；d)地址變換的速度快。5)全相聯(lián)映像a)方法讓每道程序的任何虛頁可以映像裝入到主存的任何實頁位置。只有一個任務(wù)要求同時調(diào)入主存的頁數(shù)超出2nv(很少有)時

才會發(fā)生頁面爭用。因此全相聯(lián)的實頁沖突概率很低。

主存虛存頁面位置0122nv-1…頁0122Nv’-1……nvnrNrNv’npNi每道程序任何虛頁可映像到任何實頁位置全相聯(lián)映像

b)頁表利用率整個多用戶虛存空間有2u個用戶(程序)，但主存最多只對其中的N個用戶(N道程序)開放。由基號b標識的N道程序中的每一道都有一個最大行為2Nv’的頁表，而主存總共只有2nv個實頁位置，因此N道程序頁表的全部行N?2Nv’中，裝入位為1的最多只有2nv行。由于N?2Nv’>>2nv，使得頁表中絕大部分行中實頁號nv字段及其它字段都不再有用了，這就會大大降低頁表的空間利用率。c)解決辦法

?將頁表中裝入位為0的行用實頁號nv字段存放該程序此虛頁在輔存中的實地址，以便調(diào)頁時實現(xiàn)用戶虛頁號到輔存實地址的變換。

?相聯(lián)目錄表法:把頁表壓縮成只存放已裝入主存的那些虛頁(用基號b和Nv’標識)與實頁位置(nv)的對應(yīng)關(guān)系。這樣該表最多為2nv行，簡稱為目錄表法，采用按內(nèi)容訪問的相聯(lián)存儲器構(gòu)成。如下圖：基號用戶虛頁號頁內(nèi)位移某用戶虛地址基號＋用戶虛頁號實頁號其它信息目錄表(存在相聯(lián)存儲器中)相聯(lián)比較查找到目錄表法Nv’bNrnvnvnr(Nr)npb+Nv’2nv行

d)相聯(lián)存儲器在一個存儲周期內(nèi)能將給定的Nv同時與目錄表的全部2nv個單元對應(yīng)的虛頁號字段內(nèi)容比較進行相聯(lián)查找。如有相符的即相聯(lián)查找到時，表示此虛頁已裝入主存，該單元存放的實頁號nv就是此虛頁所存放的實頁位置，將其讀出拼接上Nr就可形成訪存實地址np；如無相符的即相聯(lián)查找不到，表示此虛頁未裝入主存，發(fā)生頁面失效，請求從輔存中調(diào)頁。由此可見，采用目錄表法不用設(shè)置裝入位了。

6)虛頁的調(diào)入當發(fā)生頁面失效時，要想把該道程序的虛頁調(diào)入主存，必須給出該頁在輔存中的實際地址。為了提高調(diào)頁效率，輔存一般是按信息塊編址的，且塊的大小等于頁面大小。以磁盤為例，輔存實(塊)地址格式Nvd為：

這樣就需要將多用戶虛頁號Nv變換成輔存實地址Nvd。磁盤號柱面號磁頭號塊號Nvd

?外頁表:存放用戶虛頁號Nv’與輔存實地址Nvd的映像關(guān)系，用于外部地址變換。

?內(nèi)頁表:存放用戶虛頁號Nv’與主存實頁號nv的映像關(guān)系，用于內(nèi)部地址變換。由于虛擬存儲器的頁面失效率很低，很少調(diào)用外頁表進行地址變換，因此外頁表存放在輔存中，當某道程序初始運行時，才把外頁表的內(nèi)容轉(zhuǎn)錄到已建立內(nèi)頁表的實頁號地址字段中，這也是前述當內(nèi)頁表裝入位為0時讓實頁號地址字段改放該虛頁在輔存中的實地址的原因。而且對外頁表速度要求低，可以用軟件實現(xiàn)。如下圖：磁盤號柱面號磁頭號塊號Nvd多用戶虛地址輔存地址NrNSuNv’Nvd1裝入位輔存實地址地址變換(軟件實現(xiàn))??已裝入外頁表虛地址到輔存實地址的變換2Nv’2.替換算法1)解決問題

當處理機要用到的指令或數(shù)據(jù)不在主存中時，就會產(chǎn)生頁面失效，應(yīng)去輔存中將包含該指令或數(shù)據(jù)的一頁調(diào)入主存。由于虛存空間比主存空間大得多，必然會出現(xiàn)主存頁面位置已全被占用后又發(fā)生頁面失效，這時再將輔存中的一頁調(diào)入主存時就發(fā)生頁面爭用。只用強制騰出主存中某頁后才能接納從輔存調(diào)來的新頁。具體選擇主存中哪一頁作為被替換的頁，就是替換算法要解決的問題。

2)原則

a)有高的主存命中率

b)算法便于實現(xiàn)

c)輔助軟、硬件成本盡量低

3)常用算法

a)隨機算法(Random,RAND)用軟的或硬的隨機數(shù)產(chǎn)生器來形成主存中要被替換頁的頁號。這種算法簡單，易于實現(xiàn)，但沒有利用主存使用情況的歷史信息，反映不了程序的局部性，使主存命中率低，很少采用。

b)先進先出算法(FirstInFirstOut,FIFO)選擇最早裝入的頁作為被替換的頁。這種算法實現(xiàn)方便，雖然利用了主存使用情況的歷史信息，但是不一定能正確反映出程序的局部性，因為最先進入的頁很可能是現(xiàn)在經(jīng)常要用到的頁。

實頁號占用位程序號段頁號計數(shù)器(使用位)程序優(yōu)先位HS其它信息012nv-1……主存頁面表

c)近期最少使用算法(LeastRecentlyUsed,LRU)選擇近期最少訪問的頁作為被替換的頁。這種算法能比較正確的反映程序的局部性，因為當前最少使用的頁一般來說未來也將很少訪問，但完全按此算法實現(xiàn)比較困難，需要為每個實頁都配置一個字長很長的計數(shù)器字段才行。所以一般采用它的變形，即近期最久沒被訪問過的頁作為被替換的頁。這樣把“多”和“少”簡化成“有”和“無”之后，實現(xiàn)起來比較方便。

?主存頁面表OS為實現(xiàn)主存管理而設(shè)置的，是對主存而言的，整個主存只有一個。每一行用來記錄主存中各頁的使用狀況。而頁表是對程序空間而言的，每道程序都有一個，是用來存儲地址映像關(guān)系和實現(xiàn)地址變換的。實頁號:主存頁號是順序的，可以省略占用位:表示該主存頁面是否被占用程序號/段頁號:該主存頁被哪道程序的哪段哪頁占用使用位:表示該主存頁近期是否被使用過

開始時所有頁的使用位全為“0”，只要某個頁的任何單元被訪問過，硬件就自動將該頁使用位置“1”。由于采用全相聯(lián)映像，調(diào)入頁可進入對應(yīng)于主存頁面表中任何占用位為“0”的實頁位置，一旦裝入主存某實頁上，就置該實頁的占用位為“1”。只有當所有占用位都是1且又發(fā)生頁面失效時才有頁面替換問題，這時就要用到使用位，只需替換使用位為“0”的頁即可。?使用位全“1”處理一種辦法是由硬件強制全部使用位都為“0”。從概念上看，近期最少使用的“期”是從上次使用位全0到這次使用位全0的這段時間。由于這個期的長短是隨機的，所以稱為隨機期法。另一種辦法是它定期的置全部使用位為“0”。由“未用過計數(shù)器”HS(或稱為歷史位)，定期地每

隔Δt掃視使用位，對使用位為0的頁，則加1Hs，并讓使用位繼續(xù)為0；對使用位為1的頁，則置0Hs，同時置0使用位。掃描結(jié)束所有使用位為0，Hs大的就是最久未訪問過的，作為替換頁。

d)優(yōu)化替換算法(OPT)

?定義無論是“近期最少使用”還是“近期最久未用過”都屬于LRU，與FIFO類似，都是根據(jù)頁面使用的歷史情況來預(yù)估未來的頁面使用狀況，只是比FIFO更好反映局部性而已。然而，這種“近期”畢竟是過去了的近期，如果能根據(jù)未來實際使用情況，替換出近期不用的頁，主存命中率會更高，這就是優(yōu)化替換算法(OptimalReplacementAlgorithm,OPT)?方法在時刻t找出主存中每個頁面將要用到的時刻ti，然后選擇ti－t最大的那一頁作為被替換的頁。顯然，這只有讓程序運行一遍得到實際的頁地址流，才能找到為實現(xiàn)這種替換算法所需要的各頁使用信息，這是不現(xiàn)實的。所以，優(yōu)化替換算法只是一種理想化的算法，它可以被用作評價其它替換算法好壞的標準，看看哪種替換算法能使主存的命中率接近于優(yōu)化替換算法。

4)影響命命中率的因素

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

例：設(shè)有一道程序，有1至5共5頁，執(zhí)行時的頁地址流(即執(zhí)行時依次使用到的程序頁頁號)為：2，3，2，1，5，2，4，5，3，2，5，2若分配給該道程序的主存有3頁，如下圖表示分別用FIFO,LRU,OPT3種替換算法對這3頁的使用和替換過程。FIFO的命中率最低，而LRU的接近于OPT的。2*312323命中2調(diào)進調(diào)進調(diào)進53*1替換521*替換5*24替換5*24命中32*4替換32*4命中354*替換3*52替換FIFO命中3次2323命中2調(diào)進調(diào)進2323命中2調(diào)進調(diào)進LRU命中5次OPT命中6次頁地址流232152453252時間t12345678910111223*1調(diào)進2*51替換251*命中25*4替換2*54命中354*替換35*2替換3*52命中3*52命中231*調(diào)進23*5替換2*35命中4*35替換4*35命中4*35命中23*5替換235命中235命中3種替換算法對同一頁地址流的替換過程

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

例如一個循環(huán)程序，當所需頁數(shù)大于分配給它的主存頁數(shù)時，無論是FIFO還是LRU算法的命中率都明顯低于OPT的。如下圖所示，LRU和FIFO一次都沒有命中，因為它恰好總是將馬上要用到的頁面給替換出去了，從而連續(xù)不斷的出現(xiàn)頁面失效，產(chǎn)生所謂的顛簸現(xiàn)象。

1*2312142*3413*4*1231*2342*FIFO無命中121121LRU無命中OPT命中3次頁地址流12341234時間t1234567812*4134*123*1*24命中命中13*4命中

命中率與頁地址流有關(guān)124*1*2342*3413*4*1231*2342*

c)與主存容量(即分配給程序的主存頁數(shù))有關(guān)一般來說，分配給程序的主存頁數(shù)越多，虛頁裝入主存的機會就越多，命中率也可能就越高。但具體還與所采用的替換算法有很大關(guān)系。如下圖所示，當分配給程序的主存頁數(shù)n由3增加到4時，F(xiàn)IFO的命中率反而由3/12降到2/12;而LRU的命中率卻不會發(fā)生這種情況，隨著分配給該道程序的主存頁數(shù)的增加，命中率一般都會得到提高，至少不會降低。121*21413*4*1251*251*2命中51*2命中532*5*345*34命中n=3命中3次12121n=4命中2次頁地址流123412512345時間t1234567891011121*23命中342*3341*234命中1*23452*34513*45124*5*12341*23452*3FIFO法的實頁數(shù)增加，命中率反而有可能下降5)堆棧型替換算法a)定義

A：長度為L的任意一個頁面地址流t：已處理過t－1個頁面的時間點n：分配給該地址流的主存頁面數(shù)Bt(n)：在t時間點、在n頁的主存中的頁面集合Lt：到t時刻已遇到的地址流中相異頁的頁數(shù)若n<Lt時，Bt(n＋1)?Bt(n)n>=Lt時，Bt(n＋1)=Bt(n)成立，則此替換算法屬于堆棧型的替換算法。b)優(yōu)點

?命中率隨主存頁數(shù)的增加只可能提高，至少不會下降。

?只需采用堆棧處理技術(shù)對地址流模擬處理一次，即可同時獲得對此地址流在不同主存頁數(shù)時的命中率，大大節(jié)省存儲體系設(shè)計的工作量。

?對頁地址流A在t時刻的At頁是否命中，只需看St-1(主存在t-1時刻的堆棧)的前n項是否有At，若有則命中。

c)LRU算法屬于堆棧型算法，把剛訪問過的頁面至于棧頂，而把最久未被訪問過的頁面置于棧底。命中率隨著分配給該道程序的主存頁數(shù)n的增加而單調(diào)上升，至少不會下降，這是堆棧型算法具有的共同特點。

d)FIFO算法非堆棧型算法，命中率總趨勢是會隨著主存頁數(shù)n的增加而提高，但從某個局部來看，主存頁數(shù)n的增加有時反倒可能降低其命中率。

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

由于堆棧型替換算法具有隨分配給該道程序的實頁數(shù)n的增加，命中率H會單調(diào)上升的特點，所以可對LRU算法加以改進和發(fā)展：根據(jù)各道程序運行中的主存頁面失效率的高低，由OS來動態(tài)調(diào)節(jié)分配給每道程序的實頁數(shù)。當主存頁面失效率超過某個限值時就自動增加給該道程序的主存頁數(shù)來提高其命中率；而當主存頁面失效率低于某個限值時就自動減少分配給該道程序的主存頁數(shù)，以便釋放出這部分主存頁面位置給其它程序用，從而使整個系統(tǒng)總的主存命中率和主存利用率得到提高。3.虛擬存儲器工作的全過程

具體過程見下頁圖：Nvd輔存實地址

外部地址變換虛地址=>輔存實地址用戶標志u虛頁號Nv’Nr

6

多用戶虛地址NS

內(nèi)部地址變換虛頁號=>主存實頁號nvnrnp

5

2

1

2頁面02nv-1…2nr個字2nv個頁

3

3

2是否在主存？

“是”(訪主存)

“否”(主存頁面失效)

4

5主存(頁式)

2np個字是否在輔存？

8

6“否”(輔存頁面失效)“是”(訪輔存)主存頁面表

9

6頁面替換算法1112已滿未滿10I/O處理機13主存頁號頁面0頁面0112Nv’-1……(選頁)

714調(diào)入頁

714替換頁被替換頁退回若未被修改則不必退回輔存2NS個字4.2.3頁式虛擬存儲器實現(xiàn)中的問題

1.頁面失效處理1)原因頁面的劃分只是機械的對程序空間和主存空間進行等分，與程序的邏輯結(jié)構(gòu)毫無關(guān)系。這樣，對于按字節(jié)編址的存儲器就有可能出現(xiàn)一條指令橫跨在兩頁上存儲的情況。同理，也會出現(xiàn)一個操作數(shù)跨在兩頁上存儲。另外，采用間接尋址，特別是多重間接尋址時，在尋址的過程中，可能出現(xiàn)跨頁、甚至連續(xù)跨多個頁訪問的情況。每當當前一頁已在主存而跨頁存放的另一頁不在主存時，就會發(fā)生頁面失效。

2)解決方法

由于頁面失效可能出現(xiàn)于取指、取操作數(shù)、間接尋址等過程中，即會在一條指令的分析或執(zhí)行中發(fā)生。通常的中斷都是依靠在每條指令執(zhí)行的末尾去設(shè)置一個訪中斷微操作，來檢查系統(tǒng)中有無未屏蔽的中斷請求，以便對其進行響應(yīng)和處理。而頁面失效不能采用這種辦法，否則由于未能對頁面失效進行處理，就不可能調(diào)頁，也就無法執(zhí)行到訪中斷微操作，從而就不可能對頁面失效進行響應(yīng)和處理，機器的工作就被停頓下來。所以，頁面失效不能按一般的中斷對待，應(yīng)看作一種故障，一旦出現(xiàn)，處理機必須立即予以響應(yīng)和處理。

a)后援寄存器技術(shù)把發(fā)生頁面失效故障時指令的全部現(xiàn)場都保存下來。在處理完故障并把所需要的頁調(diào)入主存后，取出后援寄存器的內(nèi)容恢復故障點現(xiàn)場，然后從故障點處繼續(xù)執(zhí)行完該條指令。

b)預(yù)判技術(shù)執(zhí)行指令前先預(yù)判操作數(shù)的首尾字符是否都已在主存中。如果是，才執(zhí)行這條指令；否則就發(fā)生頁面失效，直到調(diào)入該頁后才開始執(zhí)行這條指令。

c)替換算法不允許出現(xiàn)指令或操作數(shù)跨頁存儲的那些頁被輪流從主存中替換出去的“顛簸”現(xiàn)象。因此，給某道程序分配的主存頁數(shù)應(yīng)該有個下限。d)頁面大小不能過大以便多道程序的道數(shù)、每道程序所分配到的主存頁數(shù)都能在一個適當?shù)姆秶鷥?nèi)。如果頁面過大，就會使主存中頁數(shù)過少，從而出現(xiàn)大量的頁面失效，嚴重降低虛擬存儲器的訪問速率和等效速度。2.提高虛擬存儲器等效訪問速度的措施根據(jù)虛擬存儲器等效訪問速度公式

TA=HTA1+(1-H)TA2

希望H提高，TA1，TA2縮短關(guān)于高的主存命中率問題，其影響因素很多，如地址流、頁面調(diào)度策略、替換算法、頁面大小及分配給程序的頁數(shù)(主存容量)等。這里主要討論怎樣縮短訪主存的時間。從虛擬存儲器工作的全過程可以看到，每次訪問主存時，都必須進行內(nèi)部地址變換(因為頁表都存在主存中，每次查頁表就要增加一次訪存。若采用段頁式虛擬存儲器，查表要增加兩次訪存)，其概率是100%。從縮短訪主存的時間來看，關(guān)鍵就是怎樣加快多用戶虛地址NS到主存實地址np的變換。只有內(nèi)部地址變換的速度高到使整個訪主存速度非常接近于不采用虛擬存儲器時的訪主存速度時，虛擬存儲器才能真正實用。如何從邏輯結(jié)構(gòu)上提高內(nèi)部地址變換的速度，正是系統(tǒng)結(jié)構(gòu)設(shè)計的任務(wù)。1)快表由于程序的局部性特點，對頁表內(nèi)各行的使用不是隨機的，在一段時間內(nèi)實際只用到表中很少的幾行。這樣就可以用快速硬件構(gòu)成比全表小的多，如8—16行的部分“目錄表”，存放當前正用的虛實地址映像關(guān)系，那么其相聯(lián)查找的速度就會很快。這部分目錄表就被稱為快表。

?慢表：存放全部虛、實地址映像關(guān)系的表。實質(zhì)上，快表只是慢表中很小的一部分副本。

2)地址變換

查表時，由虛頁號u＋Nv’(即Nv)同時去查快表和慢表。當在快表中有此虛頁號時，就能很快找到對應(yīng)的實頁號nv，將其送入主存實地址寄存器，并立即使慢表的查找作廢，這時訪存的速度沒有什么降低。如在快表中查不到時，則經(jīng)過一個訪主存周期后，從慢表中查到的實頁號nv就會送入主存實地址寄存器。同時將此虛頁號和對應(yīng)的實頁號送入快表。這里也要用到替換算法去替換快表中應(yīng)該移掉的內(nèi)容。如下圖：虛地址NvNrNv’uNSnvnr主存實地址npnv裝入位nvuNv’快表(硬件構(gòu)成)8—16行

相聯(lián)比較(按內(nèi)容訪問)快表中查不到

慢表(主存中)若查出對應(yīng)的裝入位為0發(fā)生頁面失效?

由2Nv中選1(按地址訪問)經(jīng)快表與慢表實現(xiàn)內(nèi)部地址變換從上圖可以看到，如果快表的命中率不高，系統(tǒng)的效率就會大大下降。若快表采用堆棧型替換算法，則快表容量越大其命中率就越高。但容量大，其相聯(lián)查找的速度就很慢，所以快表的命中率和查表速度是有矛盾的。一般快表取8—16行，每頁容量為1—4K字，則快表容量可以反映主存中的8—64K單元。這樣的快表命中率不會很低。這樣，快表與慢表實際上就構(gòu)成了快表—慢表存儲層次。概念上等同于主存—輔存存儲層次?？毂怼泶鎯哟蔚奶鎿Q算法一般也采用LRU法。3)減少快表相聯(lián)比較的位數(shù)在同樣的容量下，相聯(lián)比較的位數(shù)越少，相聯(lián)查找所花費的時間和設(shè)備量就越少。由于快表內(nèi)容在一段時間內(nèi)總是對應(yīng)于同一個任務(wù)或同一個用戶，它們的u值是不變的。因此可以將參與相聯(lián)比較的位數(shù)中的u字段去掉，從而由Nv(u+Nv’)位縮短到Nv’位。需增設(shè)用戶位來區(qū)分不同的任務(wù)，用戶位為0的行，其映像關(guān)系無效。任務(wù)切換時，通過硬件將所有用戶位全部置0，即都被作廢。虛地址NvNrNv’uNSnvnr主存實地址npnv裝入位nvNv’快表(硬件構(gòu)成)8—16行

相聯(lián)比較(按內(nèi)容訪問)快表中查不到

慢表(主存中)若查出對應(yīng)的裝入位為0發(fā)生頁面失效?

由2Nv中選1(按地址訪問)減少快表的相聯(lián)比較位數(shù)用戶位

4)散列快表a)思想快表容量越大，命中率越高，相聯(lián)比較越費時，使快表會快不起來。為此可以改用高速的按地址訪問存儲器來構(gòu)成容量更大的快表，并用散列(Hashing)法來實現(xiàn)按內(nèi)容查找。其思想是讓內(nèi)容Nv與存放該內(nèi)容的地址A之間建立某種散列函數(shù)關(guān)系，即讓快表的地址A=H(Nv)。當需將虛、實地址Nv與nv的映像關(guān)系存入快表存儲器中時，只需將Nv對應(yīng)的nv等內(nèi)容存入快表寄存器的A=H(Nv)單元即可。虛地址NvNrNv’uNSnvnr主存實地址np比較相等nvNv散列變換(硬化實現(xiàn))相等不等查慢表快表(按地址訪問)經(jīng)散列實現(xiàn)快表A?b)查找過程

查找時，按現(xiàn)給出的Nv經(jīng)同樣的散列函數(shù)變換成A后，按地址A訪問快表寄存器，就可以找到存放該Nv所對應(yīng)的nv及其余內(nèi)容。只有硬化實現(xiàn)散列函數(shù)變換才能保證必要的速度。如下圖，為解決多個不同的Nv可能散列到同一個A的散列沖突，在快表中再增加Nv項，在快表的A單元中除了存入當時的nv，也存入當時的Nv。這樣在地址變換時用現(xiàn)行Nv經(jīng)散列函數(shù)求得A，查到nv并訪存同時將同行中原保存的Nv讀出與現(xiàn)行Nv比較。若相等就繼續(xù)進行由nv形成的主存實地址訪存；否則就標明出現(xiàn)了沖突，即A地址單元中的nv不是現(xiàn)行Nv對應(yīng)的實頁號。就讓剛才由nv形成的主存實地址進行的訪存作廢。經(jīng)過一個主存周期，用從慢表中讀到的nv再去訪存。虛地址NvNrNv’uNSnvnr主存實地址np比較相等nvNv散列變換(硬化實現(xiàn))相等不等查慢表快表(按地址訪問)?A

c)改進散列沖突的辦法

?在快表的