§2虛擬存儲器1961年英國曼徹斯特大學(xué)Kilbrn等人提出70年代廣泛地應(yīng)用于大中型計算機(jī)系統(tǒng)中目前許多微型機(jī)也開始使用虛擬存儲器是進(jìn)一步完善主存-輔存存儲層次，解決主存容量提出的。目錄不同的虛擬存儲管理方式

頁式虛擬存儲器構(gòu)成

頁式虛擬存儲器實(shí)現(xiàn)中的問題虛擬地址空間實(shí)際地址空間映射壓縮不同的虛擬存儲管理方式

通過增設(shè)地址映像表機(jī)構(gòu)來實(shí)現(xiàn)程序在主存中的定位。這種定位技術(shù)是將程序分割成若干較小的段或頁，用相應(yīng)的映像表機(jī)構(gòu)來指明程序的某段或某頁是否已裝入內(nèi)存。段式管理

頁式管理段頁式管理段式管理

段為程序的邏輯單位段表，本身也是段，常駐內(nèi)存，也可以在輔存，需要時調(diào)入主存。段表結(jié)構(gòu)：

段名、地址、裝入位、段長、訪問方式。段表基址寄存器：指明段表的啟始地址。能使大程序分模塊編制，并行編程，縮短時間便于幾道程序共用已在內(nèi)存內(nèi)的程序和數(shù)據(jù)；各段是按其邏輯特點(diǎn)組合的，容易以段為單位實(shí)現(xiàn)存儲保護(hù)。人工建立。

3kA41.5k0段1段2段3段4段5段6段1k2k3k1k2k2k4ka701A2段4段0段1k1k++605041k2k13025k3k110001k1段名地址裝入位段長訪問方式a已裝入段表長度段表基地址段表基址寄存器實(shí)主存空間A道程序的程序空間A道程序的段表2.5k主程序

(0段)1k1段2段3段0500020002000段號段長起址01k8k150016k22009k320030k08k9k16k30k程序

空間主存儲器地址映象方法：每個程序段都從0地址開始編址，長度可長可短，可以在程序執(zhí)行過程中動態(tài)改變程序段的長度。地址變換方法：由用戶號找到基址寄存器從基址寄存器中讀出段表的起始地址把起始地址與多用戶虛地址中段號相加得到段表地址把段表中給出的起始地址與段內(nèi)偏移D相加就能得到主存實(shí)地址0段表

長度段表

基址6As段名起始地址裝入

位段長訪問

方式用戶號U段號S段內(nèi)偏移D多用戶

虛地址主存實(shí)地址432101n-1As段表基址寄存器一個用戶（一道作業(yè)）的段表段式管理優(yōu)缺點(diǎn)優(yōu)點(diǎn)程序的模塊化性能好便于程序和數(shù)據(jù)的共享程序的動態(tài)鏈接和調(diào)度比較容易便于實(shí)現(xiàn)信息保護(hù)缺點(diǎn)地址變換所花費(fèi)的時間比較長，做兩次加法運(yùn)算主存儲器的利用率往往比較低對輔存（磁盤存儲器）的管理比較困難段分配算法首先分配：順序掃描可用區(qū)域表，當(dāng)找到第一個不小于調(diào)

入段長度的可用區(qū)時，立即分配。最佳分配：先掃描全部可用區(qū)域表，然后尋找一個可用區(qū)進(jìn)行分配，使之分配后段間可用區(qū)零頭最小。舉例0.5k03k7k8k10kCBADEF1k2.5k2k03k7k8k10kCBA

主存

程序

主存03k7k8k10kCBA

主存DEF4k6.5kED5.5k9k(a)需依次調(diào)入D、E、F段(b)首先分配法D、E、F段全被調(diào)入（c)最佳分配法F段無法調(diào)入頁式管理頁式虛擬存儲器把虛擬地址空間劃分成一個個固定大小的塊,每塊稱為一頁,把主存儲器的地址空間也按虛擬地址空間同樣的大小劃分為頁。頁是一種邏輯上的劃分，它可以由系統(tǒng)軟件任意指定。虛擬地址空間中的頁稱為虛頁，主存地址空間中的頁稱為實(shí)頁。每個用戶使用一個基址寄存器（在CPU內(nèi)），通過用戶號U可以直接找到與這個用戶程序相對應(yīng)的基址寄存器，從這個基址寄存器中讀出頁表起始地址。訪問這個頁表地址，把得到的主存頁號p與虛地址中的頁內(nèi)偏移直接拼接起來得到主存實(shí)地址。頁式管理

把主存空間和程序空間機(jī)械地等分成固定大小的頁，按順序編號；頁表。如下圖。

特點(diǎn)：頁表項簡單，查找速度快；頁面大小固定不利于系統(tǒng)的效率，有些系統(tǒng)可調(diào)整其大小。例：MC88200應(yīng)用程序

4kb系統(tǒng)程序512kb頁式管理在存儲空間較大時，由于頁表過大，效率降低。存儲空間的保護(hù)困難。

0124k4k4kD道程序程序空間虛存頁號ABC04k-132k-1D程序標(biāo)志號bNvNrnrnv271161021D道程序頁表虛存頁號主存起點(diǎn)裝如位訪問方式專用位基號虛頁號頁內(nèi)偏移實(shí)頁號頁內(nèi)偏移0124k4k4kD道程序程序空間虛存頁號ABC04k-132k-1271161021D道程序頁表虛存頁號主存起點(diǎn)裝如位訪問方式專用位XNvNr多用戶虛地址用戶標(biāo)志u用戶虛頁號頁內(nèi)位移多用戶虛頁號某道程序的地址由u轉(zhuǎn)換成基號bx頁表基址寄存器nvnr實(shí)頁號裝入位nv1已裝入主存主存地址寄存器舉例虛地址空間32位，頁面大小為1kb（10位）

頁表地址段將達(dá)22位，

32-10=22

頁表的長度為4兆行(222=4096k=4M)如主存容量為8MB則頁表字段為13位，每行為2+1字節(jié)

則頁表容量為

4MB*3=12MB＞主存容量

0頁1頁2頁3頁頁號主存頁號0123用戶程序主存儲器頁表頁式虛擬存儲器的地址映象Pa裝入修改主存頁號標(biāo)志用戶號U虛頁號P頁內(nèi)偏移D頁內(nèi)偏移d2pPa頁表基址頁表實(shí)頁號p頁式管理的優(yōu)缺點(diǎn)優(yōu)點(diǎn)主存儲器的利用率比較高頁表相對比較簡單地址變換的速度比較快對磁盤的管理比較容易缺點(diǎn)程序的模塊化性能不好頁表很長，需要占用很大的存儲空間。段頁式管理

頁式：對應(yīng)用程序員完全透明，由系統(tǒng)劃分.硬件較少，地址變換速度快，調(diào)入操作簡單，靜態(tài)連接程序；段式：段獨(dú)立，有利于程序員靈活實(shí)現(xiàn)段的連接、段的擴(kuò)大/縮小和修改，而不影響其他段，易于針對其特定類型實(shí)現(xiàn)保護(hù)，把共享的程序或數(shù)據(jù)單獨(dú)構(gòu)成一個段，從而易于實(shí)現(xiàn)多個用戶、進(jìn)程對共用段的管理，動態(tài)連接程序；特點(diǎn)：訪存兩次。段頁式：把實(shí)存機(jī)械地等分成固定大小的頁，程序按模塊分段，每個段又分成與主存頁面大小相同的頁。

地址變換方法：先查段表，得到該程序段的頁表起始地址和頁表長度再查頁表找到要訪問的主存實(shí)頁號最后把實(shí)頁號p與頁內(nèi)偏移d拼接得到主存的實(shí)地址。裝入修改實(shí)頁號標(biāo)志用戶號U段號S頁內(nèi)偏移頁內(nèi)偏移0/11pA實(shí)頁號p虛頁號PAs裝入1修改0/1頁表地址ApAs頁式虛擬存儲器構(gòu)成

uNv’Nrnrnv直接多用戶虛地址Ns實(shí)存地址np實(shí)存空間虛存總空間2nv頁2Nv頁包括2u個用戶，每個用戶為2Nv頁。2Nr2nr2Nr=2nr地址映象和變換

地址映象：是將每個虛存單元按某種規(guī)則（算法）裝入（定位于）實(shí)存，即建立多用戶虛地址Ns與實(shí)存地址np之間的對應(yīng)關(guān)系。地址變換：是程序按照這種映象關(guān)系裝入實(shí)存后，在執(zhí)行時，多用戶虛地址Ns如何變換成對應(yīng)的實(shí)地址np。頁面爭用（實(shí)頁沖突）：發(fā)生兩個以上的虛頁想要進(jìn)入主存中同一個頁面位置的現(xiàn)象。

地址變換的原則減少實(shí)頁沖突硬件少、成本低實(shí)現(xiàn)方便、變換速度快。由于虛存空間遠(yuǎn)遠(yuǎn)大于實(shí)存空間，因此頁式虛擬存儲器常采用全相聯(lián)映像。全相聯(lián)映像

任何虛頁可以映象裝入到任何實(shí)頁位置。沖突概率最低。

頁面位置0頁面位置1頁0頁1頁2主存虛存每道程序任何虛頁可映像到任何實(shí)頁位置全相聯(lián)映像的頁表法頁表法

nv裝入位2u+Nv行全相聯(lián)映像的相聯(lián)目錄表法相聯(lián)目錄表法u+Nvnv

2nv行相聯(lián)比較頁表法與相聯(lián)目錄表法的比較

頁表法相聯(lián)目錄表法訪問方式地址內(nèi)容存儲容量存取速度慢快入口個數(shù)入口寬度替換算法頁面替換發(fā)生時間：

當(dāng)發(fā)生頁面失效時，要從磁盤中調(diào)入一頁到主存。如果主存所有頁面都已經(jīng)被占用，必須從主存儲器中淘汰掉一個不常使用的頁面，以便騰出主存空間來存放新調(diào)入的頁面。替換算法的確定主存的命中率

是否便于實(shí)現(xiàn)，軟、硬件成本

頁面替換算法的使用場合虛擬存儲器中，主存頁面的替換，一般用軟件實(shí)現(xiàn)Cache塊替換一般用硬件實(shí)現(xiàn)虛擬存儲器的快慢表中，快表存儲字的替換，用硬件實(shí)現(xiàn)虛擬存儲器中，用戶基地址寄存器的替換，用硬件實(shí)現(xiàn)在有些虛擬存儲器中目錄表的替換替換算法（續(xù)）隨機(jī)算法（Random，RAND）：用軟的或硬的隨機(jī)數(shù)產(chǎn)生器來形成主存重要被替換頁的頁號。簡單，易于實(shí)現(xiàn)沒有利用歷史信息命中率低，很少使用先進(jìn)先出算法（First-InFirst-Out，F(xiàn)IFO）：選擇最早裝入主存的頁作為被替換的頁。配置計數(shù)器字段雖然利用歷史信息，但不一定反映出程序的局部性替換算法（續(xù)）近期最少使用算法（LeastRecentlyUsed，LRU）：選擇近期最少訪問的頁作為被替換的頁。配有計數(shù)器字段。比較正確反映程序的局部性。優(yōu)化替換算法（OptimalReplacementAlgorithm，

OPT）:是在時刻t找出主存中每個頁將要用到時刻ti，然后選擇其中ti-t最大的那一頁作為替換頁。

理想化算法舉例1設(shè)有一道程序，有1至5共5頁，執(zhí)行時的地址流為：

2，3，2，1，5，2，4，5，3，2，5，2分別采用FIFO、LRU、OPT算法。說明命中率與地址流有關(guān)例如：一個循環(huán)程序，F(xiàn)IFO、LRU的命中率明顯低于OPT。（下一張）顛簸現(xiàn)象：連續(xù)不斷出現(xiàn)頁面失效。命中率與分配給程序的主存頁數(shù)有關(guān)。主存頁數(shù)增加，LRU命中率提高，至少不會下降，而FIFO不一定。(P115,圖4.17)舉例一個循環(huán)程序，依次使用P1，P2，P3，P4四個頁面，分配給這個程序的主存頁面數(shù)為3個。FIFO、LRU和OPT三種頁面替換算法對主存頁面的調(diào)度情況如下圖所示。在FIFO和LRU算法中，總是發(fā)生下次就要使用的頁面本次被替換出去的情況，這就是“顛簸”現(xiàn)象。舉例2一個程序共有5個頁面組成，程序執(zhí)行過程中的頁地址流如下：

P1,P2,P1,P5,P5,P1,P3,P4,P3,P4

假設(shè)分配給這個程序的主存儲器共有3個頁面。給出FIFO、LRU、OPT三種頁面替換算法對這3頁主存的使用情況，包括調(diào)入、替換和命中等。堆棧型替換算法的定義對任意一個程序的頁地址流作兩次主存頁面數(shù)分配，分別分配m個主存頁面和n個主存頁面，并且有m≤n。如果在任何時刻t，主存頁面數(shù)集合Bt都滿足關(guān)系：Bt(m)íBt(n)，則這類算法稱為堆棧型替換算法。

堆棧型算法的基本特點(diǎn)隨著分配給程序的主存頁面數(shù)增加，主存的命中率也提高，至少不下降。LRU、OPT都是堆棧型算法FIFO是非堆棧型算法提出使系統(tǒng)性能可以更優(yōu)的動態(tài)算法。由操作系統(tǒng)來動態(tài)調(diào)節(jié)分配給每道程序的實(shí)頁數(shù)。虛擬存儲器工作的全過程

書中P117-118頁式虛擬存儲器實(shí)現(xiàn)中的問題

頁面失效的處理頁面失效會在一條指令的分析或執(zhí)行過程中發(fā)出。頁面失效時一種故障，不是一般的中斷；注意保護(hù)現(xiàn)場,采用后援寄存器技術(shù)、預(yù)判技術(shù)；選擇合適的替換算法；頁式虛擬存儲器實(shí)現(xiàn)中的問題提高虛擬存儲器等效訪問速度的措施要求：提高命中率，加快訪存時間；命中率受很多因素影響，如：地址流、頁面調(diào)度策略、替換算法、頁面大小、主存容量等。訪存時間，解決Ns-np的轉(zhuǎn)換。快表：相聯(lián)目錄表，慢表：頁表快表-慢表存儲層次的替換算法一般采用LRU法。實(shí)頁號用戶號U頁內(nèi)偏移Dp虛頁號P多用戶

虛地址快表（按內(nèi)容相聯(lián)訪問）頁內(nèi)偏移d實(shí)頁號p多用戶虛頁號U,P主存實(shí)地址實(shí)頁號p裝入1慢表散列函數(shù)目的：把相聯(lián)訪問變成按地址訪問，從而加大快表容量散列（Hashing）函數(shù)：Ah＝H(Pv),20位左右5~8位采用散列變換實(shí)現(xiàn)快表按地址訪問

避免散列沖突：采用相等比較器

地址變換過程：相等比較與訪問存儲器同時進(jìn)行實(shí)頁號用戶號U頁內(nèi)偏移Dp虛頁號P多用戶

虛地址按地址訪問的快表頁內(nèi)偏移d實(shí)頁號p多用戶虛頁號Pv主存實(shí)地址散列變

換（硬

件實(shí)現(xiàn)）相等比較多用戶虛頁號查慢表快表地址Ah快表