分頁存儲(chǔ)管理課件

4．3分頁管理

4.3.1

分頁管理的基本原理

分頁存儲(chǔ)管理是解決存儲(chǔ)零頭的一種方法。動(dòng)態(tài)重定位是解決存儲(chǔ)器零頭問題的一種途徑，但要移動(dòng)大量信息花去不少處理機(jī)時(shí)間,代價(jià)比較高,這是因?yàn)檫@種分配要求把作業(yè)必須安置在一連續(xù)存儲(chǔ)區(qū)內(nèi)的緣故,而分頁存儲(chǔ)管理正是要避開這種連續(xù)性要求。4．3分頁管理分頁存儲(chǔ)管理，在該方式中，用戶程序的地址被劃分成劃分若干個(gè)固定大小的區(qū)域，稱為頁（或頁面）。頁面的典型大小為1k；相應(yīng)地將內(nèi)存空間分成若干個(gè)物理塊(或頁框)，頁和塊的大小相同，這樣可將用戶程序的任一頁放到內(nèi)存的任一塊中，實(shí)現(xiàn)離散分配。這時(shí)內(nèi)存中的碎片大小不會(huì)超過一頁。關(guān)鍵問題是實(shí)現(xiàn)邏輯地址到物理地址的二維動(dòng)態(tài)映射，這是通過頁表實(shí)現(xiàn)的。引入聯(lián)想存貯器（超高速緩存）構(gòu)成的快表可加快映射的速度。內(nèi)存空間的保護(hù)是通過地址映射過程中檢查頁號(hào)越界來實(shí)現(xiàn)的。分頁存儲(chǔ)管理，在該方式中，用戶程序的地址被劃分成劃分若干個(gè)固（1）基本分頁存儲(chǔ)管理原理1．分頁 分頁存儲(chǔ)管理是將一個(gè)進(jìn)程的地址空間劃分成若干個(gè)大小相等的區(qū)域，稱為頁。相應(yīng)地，將內(nèi)存空間劃分成與頁相同大小的若干個(gè)物理塊，稱為塊或頁框。在為進(jìn)程分配內(nèi)存時(shí)，將進(jìn)程中若干頁分別裝入多個(gè)不相鄰接的塊中。2.地址結(jié)構(gòu) 分頁系統(tǒng)的地址結(jié)構(gòu)如下圖所示，它由兩部分組成：前一部分為頁號(hào)P；后一部分為位移量W，即頁內(nèi)地址。圖中的地址長(zhǎng)度為32位，其中0～11位為頁內(nèi)地址（每頁的大小為4K），12～31位為頁號(hào)，所以允許地址空間的大小最多為1M個(gè)頁。

3112110

頁號(hào)P位移量W（1）基本分頁存儲(chǔ)管理原理頁號(hào)P頁號(hào)頁內(nèi)地址

51025＝32（頁）210＝1024（每頁1024字節(jié)）在分配存儲(chǔ)空間時(shí),是以頁面為單位來分配.例如,一個(gè)作業(yè)的地址空間有M頁,那么只需要分配給他M個(gè)頁面的存儲(chǔ)空間,每一頁分別裝入一個(gè)存儲(chǔ)頁面即可.并不需要這些頁面是連續(xù)的.以上這些問題需要一個(gè)地址映射.頁號(hào)頁內(nèi)地址51025＝32（若給定一個(gè)邏輯地址空間中的地址為A，頁面大小為L(zhǎng)，則頁號(hào)P和頁內(nèi)地址w可按下式求得：P=INT[A/L]W=[A]MODL其中，INT是整除函數(shù)，MOD是取余函數(shù)。例：系統(tǒng)頁面大小為１KB，設(shè)A＝2170B，則P=2,W=122若給定一個(gè)邏輯地址空間中的地址為A，頁面大小為L(zhǎng)，則頁號(hào)P和3.頁表在將進(jìn)程的每一頁離散地分配到內(nèi)存的多個(gè)物理塊中后，系統(tǒng)應(yīng)能保證能在內(nèi)存中找到每個(gè)頁面所對(duì)應(yīng)的物理塊。為此，系統(tǒng)為每個(gè)進(jìn)程建立了一張頁面映射表，簡(jiǎn)稱頁表（如下圖所示）。每個(gè)頁在頁表中占一個(gè)表項(xiàng)，記錄該頁在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)。進(jìn)程在執(zhí)行時(shí)，通過查找頁表，就可以找到每頁所對(duì)應(yīng)的物理塊號(hào)?？梢?，頁表的作用是實(shí)現(xiàn)從頁號(hào)到物理塊號(hào)的地址映射。3.頁表

頁表：由頁號(hào)和頁面號(hào)組成，指出邏輯地址中頁號(hào)與主存中塊號(hào)（頁面號(hào)）的對(duì)應(yīng)關(guān)系頁號(hào)作業(yè)地址空間的頁序號(hào)頁面號(hào)內(nèi)存空間的頁面序號(hào)

頁號(hào)頁面號(hào)頁表頁表：由頁號(hào)和頁面號(hào)組成，頁號(hào)頁面號(hào)頁表存儲(chǔ)頁面表一個(gè)系統(tǒng)只有一張存儲(chǔ)頁面表.它指出內(nèi)存各頁面是否被分配,以及來分配頁面的總數(shù).………

19183210

若內(nèi)存被分配為1024個(gè)頁面,內(nèi)存單元長(zhǎng)20比特.1024/20=52個(gè)單元.描述了1024個(gè)頁面是否分配.存儲(chǔ)頁面表………19184.3.2地址變換(映射)機(jī)構(gòu)1.基本的地址變換機(jī)構(gòu)

地址變換機(jī)構(gòu)的基本任務(wù)是利用頁表把用戶程序中的邏輯地址變換成內(nèi)存中的物理地址，實(shí)際上就要將用戶程序中的頁號(hào)變換成內(nèi)存中的物理塊號(hào)。為了實(shí)現(xiàn)地址變換功能，在系統(tǒng)中設(shè)置頁表寄存器，用來存放頁表的始址和頁表的長(zhǎng)度。在進(jìn)程未執(zhí)行時(shí)，每個(gè)進(jìn)程對(duì)應(yīng)的頁表的始址和長(zhǎng)度存放在進(jìn)程的PCB中，當(dāng)該進(jìn)程被調(diào)度時(shí)，就將它們裝入頁表寄存器。在進(jìn)行地址變換時(shí)，系統(tǒng)將頁號(hào)與頁表長(zhǎng)度進(jìn)行比較，如果頁號(hào)大于頁表寄存器中的頁表長(zhǎng)度，則訪問越界，產(chǎn)生越界中斷。如未出現(xiàn)越界，則根據(jù)頁表寄存器中的頁表始址和頁號(hào)計(jì)算出該頁在頁表項(xiàng)中的位置，得到該頁的物理塊號(hào)，將此物理塊號(hào)裝入物理地址寄存器中。與此同時(shí)，將有效地址（邏輯地址）寄存器中頁內(nèi)地址直接裝入物理地址寄存器的塊內(nèi)地址字段中，這樣便完成了從邏輯地址到物理地址的變換。4.3.2地址變換(映射)機(jī)構(gòu)1.基本的地址變換機(jī)構(gòu)物理地址(絕對(duì)地址)

相對(duì)地址(有效邏輯地址)頁面號(hào)頁內(nèi)地址頁號(hào)頁內(nèi)地址頁表長(zhǎng)度頁表始址控制寄存器物理地址(絕對(duì)地址)相對(duì)地址(有效邏輯地址)頁面號(hào)頁內(nèi)地址頁表長(zhǎng)度頁表始址31k2452相對(duì)地址頁號(hào)頁面號(hào)0213288452OS物理地址86441024*8+452=8644頁表長(zhǎng)度頁表始址31k2452第0頁第1頁第2頁第3頁第4頁第5頁第6頁

05k6k7k8k9k10k11k12k13k14k15k16k17k31k57915131016...0k1k2k3k4k5k6k0k1k2k3k4k5k6k作業(yè)1的地址空間作業(yè)1的地址空間頁表圖頁式管理的示意圖主存空間頁表第0頁0.0k0k作業(yè)1的地例：作業(yè)地址空間共有7個(gè)頁，每頁的相對(duì)地址為0~1023，1024~2047，2048~3071，…，6144~6150。其對(duì)應(yīng)的主存塊在頁表中已列出。分別為5，7，9，15，13，10，16共7塊。假定頁表在主存始址為500。若該程序從第0頁開始運(yùn)行，且現(xiàn)程序計(jì)數(shù)器內(nèi)容為：例：作業(yè)地址空間共有7個(gè)頁，每頁的相對(duì)地址為0~1023，114.……..109…0硬件動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)工作如下：1.把該作業(yè)的頁表始址（500）和頁表長(zhǎng)度（7）放入控制寄存器中。2.將程序計(jì)數(shù)器內(nèi)容的頁號(hào)部分（0）與控制寄存器中的頁表長(zhǎng)度（7）相比較，若頁號(hào)<頁表長(zhǎng)度時(shí)轉(zhuǎn)3，否則產(chǎn)生地址越界，終止程序運(yùn)行。010014.……..109…03.將程序計(jì)數(shù)器中的頁號(hào)與控制寄存器中的頁表始址相加，得到該訪問操作所在頁號(hào)在頁表中的入口地址：500+0=5004.用該地址去訪頁表，獲得該頁所對(duì)應(yīng)的主存塊5。5.把主存塊號(hào)5與程序計(jì)數(shù)器中的頁內(nèi)位移相拼接，從而得到該操作所在主存的物理地址：5×1024+100=52206.根據(jù)這個(gè)地址5220，完成指定操作。3.將程序計(jì)數(shù)器中的頁號(hào)與控制寄存器中的頁表始址相加，得到該控制寄存器程序計(jì)數(shù)器50070(頁號(hào)）

100（頁內(nèi)地址）>+57915131016頁表內(nèi)存地址寄存器5(內(nèi)存塊號(hào)）

100（頁內(nèi)地址）12345圖頁式地址變換過程控制寄存器程序計(jì)數(shù)器50070(頁號(hào)）

頁表寄存器

邏輯地址2500

頁號(hào)塊號(hào)

012

每頁1KB(1024)

頁號(hào)2頁內(nèi)地址452頁表始址頁表長(zhǎng)度

2 4 5寫出下圖中邏輯地址2500所對(duì)應(yīng)的物理地址

越界中斷

頁表寄存器

邏輯地址2500

頁號(hào)塊號(hào)

012

每頁1KB(1024)

物理地址55725*1024+452塊號(hào)5塊內(nèi)地址452

頁號(hào)2頁內(nèi)地址452頁表始址頁表長(zhǎng)度﹥

2 4 5邏輯地址2500所對(duì)應(yīng)的物理地址

快表和聯(lián)想存貯器

從上述地址轉(zhuǎn)換過程可以看出，執(zhí)行一次訪內(nèi)操作至少要訪問主存兩次。一次訪頁表，以確定所取數(shù)據(jù)或指令的物理地址；另一次是根據(jù)地址取數(shù)據(jù)或指令。這樣就把程序的執(zhí)行速度降低一倍。為了提高存取速度，通常設(shè)置一個(gè)專用的高速緩沖寄存器組，用來存放頁表的一部分。我們把存放在高速緩沖寄存器中的頁表叫快表，這個(gè)高速緩沖寄存器又叫聯(lián)想存貯器?？毂砗吐?lián)想存貯器聯(lián)想存貯器的存取速度比主存高，但造價(jià)也高。因此只能采用少量，整個(gè)系統(tǒng)通常只要用8~16個(gè)寄存器即可使程序執(zhí)行速度大大提高?？毂淼母袷揭娤聢D。

頁號(hào)塊號(hào)訪問位狀態(tài)位聯(lián)想存貯器的存取速度比主存高，但造價(jià)也高。因此只能采用少量，其中，“頁號(hào)”是程序訪問過的地址空間的頁號(hào)，“塊號(hào)”是該頁所對(duì)應(yīng)的主存塊號(hào)；訪問位指示該頁最近是否被訪問過?！?”表示沒有被訪問，“1”表示訪問過；“狀態(tài)”位指示該寄存器是否被占用。通?！?”表示空閑，“1”表示占用。為了保證快表中的內(nèi)容為現(xiàn)正運(yùn)行程序的頁表內(nèi)容，在每個(gè)程序被選中時(shí)，由恢復(fù)現(xiàn)場(chǎng)程序把快表的所有狀態(tài)位清“0”，或恢復(fù)已保存的快表內(nèi)容。其中，“頁號(hào)”是程序訪問過的地址空間的頁號(hào)，“塊號(hào)”是該頁所當(dāng)進(jìn)程訪問一頁時(shí)，系統(tǒng)將頁號(hào)與快表中的所有項(xiàng)進(jìn)行并行比較。若訪問的頁在快表中，即可立即進(jìn)行地址轉(zhuǎn)換。當(dāng)被訪問的頁不在快表中時(shí)，就要將由慢表找到的內(nèi)存塊號(hào)與虛頁號(hào)填入快表中，若快表已滿，則置換其中訪問位為0的一項(xiàng)。另外，在設(shè)置快表的情況下，硬件地址轉(zhuǎn)換機(jī)構(gòu)在進(jìn)行地址變換時(shí)，同時(shí)開始兩個(gè)變換過程。當(dāng)進(jìn)程訪問一頁時(shí)，系統(tǒng)將頁號(hào)與快表中的所有項(xiàng)進(jìn)行并行比較。若一個(gè)是利用主存頁表進(jìn)行的正常變換過程，另一個(gè)是利用快表進(jìn)行的快速變換過程。一旦快表中有與查找的頁號(hào)相符合時(shí)，則立即停止正常的訪主存頁表過程。并將快表中的塊號(hào)與CPU給出的頁內(nèi)位移相拼接，得到訪問主存的絕對(duì)地址。從而結(jié)束了快表的查找工作。一個(gè)是利用主存頁表進(jìn)行的正常變換過程，另一個(gè)是利用快表進(jìn)行的當(dāng)利用快表進(jìn)行變換時(shí)，若沒有找到要查詢的頁時(shí)，則繼續(xù)正常的轉(zhuǎn)換過程，直到形成訪問主存的絕對(duì)地址。而且還要把從主存頁表中取出的塊號(hào)和CPU給出的頁號(hào)一起寫入快表中狀態(tài)位為0的一行中。若沒有這樣行存在，則寫入訪問位為0的某一行中，并同時(shí)置狀態(tài)位和訪問位為1。需要說明的是，快表的地址轉(zhuǎn)換是非?？斓模?yàn)樗菍㈨撎?hào)與快表中的各行同時(shí)比較，從而大大減少了地址變換時(shí)間，基本上克服了兩次訪問主存的缺點(diǎn)。當(dāng)利用快表進(jìn)行變換時(shí)，若沒有找到要查詢的頁時(shí)，則繼續(xù)正常的轉(zhuǎn)由于成本的原因，快表不可能做得很大，通常只能存放16~512個(gè)頁表項(xiàng)。例如，在Intel80486中有32個(gè)。這對(duì)中、小型作業(yè)來說，已可能把全部頁表項(xiàng)放入快表中；但對(duì)于大型作業(yè)來說，則只能將一部分頁表放入快表中。由于對(duì)程序和數(shù)據(jù)的訪問往往帶有局限性，所以快表的命中率可以達(dá)到80%～90%。例如，假設(shè)檢索聯(lián)想存儲(chǔ)器的時(shí)間為20ns，訪問內(nèi)存的時(shí)間為100ns，訪問聯(lián)想存儲(chǔ)器的的命中率為85%，則CPU存取一個(gè)數(shù)據(jù)的平均時(shí)間T=0.85*120+0.15*220=135ns，所以訪問時(shí)間只增加35%。如果不引入聯(lián)想存儲(chǔ)器，其訪問將延長(zhǎng)一倍（達(dá)200ns）。由于成本的原因，快表不可能做得很大，通常只能存放16~512具有快表的地址變換機(jī)構(gòu)

越界中斷

頁表寄存器

邏輯地址

頁號(hào)塊號(hào)

頁號(hào)塊號(hào)020141252

快表頁表物理地址

頁號(hào)頁內(nèi)地址頁表始址頁表長(zhǎng)度﹥

245塊號(hào)塊內(nèi)地址

輸入寄存器具有快表的地址變換機(jī)構(gòu)4.3.3兩級(jí)頁表機(jī)制80386的邏輯地址有232B，如頁面大小為4KB（212B），則頁表項(xiàng)達(dá)1M個(gè)，每個(gè)頁表項(xiàng)占用4B，故每個(gè)進(jìn)程的頁表占用4MB內(nèi)存空間，還要求是連續(xù)的，顯然這是不現(xiàn)實(shí)的。在80386中，為了減少頁表所占用的連續(xù)的內(nèi)存空間，采用了兩級(jí)頁表機(jī)制：基本方法是將頁表進(jìn)行分頁，每個(gè)頁面的大小與內(nèi)存物理塊的大小相同，并為它們進(jìn)行編號(hào)，可以離散地將各個(gè)頁面分別存放在不同的物理塊中，為此再建立一張頁表，稱為外層頁表（頁表目錄），即第一級(jí)頁表，其中的每個(gè)表目是存放某個(gè)頁表的物理地址。第二級(jí)才是頁表，其中的每個(gè)表目所存放的才是頁的物理塊號(hào)。4.3.3兩級(jí)頁表機(jī)制80386的邏輯地址有232B，如兩級(jí)頁表系統(tǒng)將32位邏輯地址空間的地址分成三段：其中，頁表目錄號(hào)（外層頁號(hào)p1）和頁號(hào)（外層頁內(nèi)地址p2）兩項(xiàng)各占10位，偏移量（頁內(nèi)地址d）占12位。每頁的大小為4KB。由于物理塊號(hào)和頁表的物理地址都占4個(gè)字節(jié)，使每頁中包含1024個(gè)頁表項(xiàng)，所以頁表目錄和頁表的大小也都是4KB，即一頁。在80386中設(shè)置了一個(gè)外層頁表寄存器（CR3），用于存放頁表目錄的基址。兩級(jí)頁表的邏輯地址結(jié)構(gòu)和兩級(jí)頁表的地址變換機(jī)構(gòu)圖如下：31222112110

外層頁表頁表物理地址

外層頁號(hào)p1外層頁內(nèi)地址p2頁內(nèi)地址d外層頁表寄存器++

bd兩級(jí)頁表系統(tǒng)將32位邏輯地址空間的地址分成三段：其中，頁表目?jī)杉?jí)頁表機(jī)制圖

第0頁頁表（物理塊號(hào)10）內(nèi)存010┇110232第1頁頁表（物理塊號(hào)25）01┇1023第N頁頁表（物理塊號(hào)120）01

外層頁表┇102310251201214323515115201……121314……32333435……151152……兩級(jí)頁表機(jī)制圖第0頁頁表（物理塊號(hào)4.5虛擬存儲(chǔ)器4.6請(qǐng)求分頁存儲(chǔ)管理（動(dòng)態(tài)頁式）4.5虛擬存儲(chǔ)器4.5虛擬存儲(chǔ)器的基本概念（1）虛擬存儲(chǔ)器的引入常規(guī)存儲(chǔ)管理方式的特征是：一次性、駐留性。

1．局部性原理早在1968年P(guān)．Denning就指出過，程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，即在一段時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它所訪問的存儲(chǔ)空間也局限于某個(gè)區(qū)域內(nèi)。那么程序?yàn)槭裁磿?huì)出現(xiàn)局部性規(guī)律呢？原因可以歸結(jié)為以下幾點(diǎn)：程序在執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，大多數(shù)仍是順序執(zhí)行的。子程序調(diào)用將會(huì)使程序的執(zhí)行由一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域。但在大多數(shù)情況下，過程調(diào)用的深度都不超過5。程序中存在許多循環(huán)結(jié)構(gòu)，循環(huán)體中的指令被多次執(zhí)行。程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，如對(duì)連續(xù)的存儲(chǔ)空間——數(shù)組的訪問，往往局限于很小的范圍內(nèi)。4.5虛擬存儲(chǔ)器的基本概念（1）虛擬存儲(chǔ)器的引入所以局限性表現(xiàn)為：

時(shí)間局限性：如果程序中的某條指令一旦執(zhí)行，則不久的將來該指令可能再次被執(zhí)行；如果某個(gè)存儲(chǔ)單元被訪問，則不久以后該存儲(chǔ)單元可能再次被訪問。產(chǎn)生時(shí)間局限性的典型原因是在程序中存在著大量的循環(huán)操作?？臻g局限性：一旦程序訪問了某個(gè)存儲(chǔ)單元，則在不久的將來，其附近的存儲(chǔ)單元也最有可能被訪問。即程序在一段時(shí)間內(nèi)所訪問的地址，可能集中在一定的范圍內(nèi)，其典型原因是程序是順序執(zhí)行的。2.虛擬存儲(chǔ)器的定義根據(jù)局部性原理，一個(gè)作業(yè)在運(yùn)行之前，沒有必要把全部作業(yè)裝入內(nèi)存，而僅將那些當(dāng)前要運(yùn)行的那部分頁面或段，先裝入內(nèi)存便可啟動(dòng)運(yùn)行，其余部分暫時(shí)留在磁盤上。所以局限性表現(xiàn)為：程序在運(yùn)行時(shí)如果它所要訪問的頁（段）已調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去；但如果程序所要訪問的頁（段）尚未調(diào)入內(nèi)存（稱為缺頁或缺段），此時(shí)程序應(yīng)利用OS所提供的請(qǐng)求調(diào)頁（段）功能，將它們調(diào)入內(nèi)存，以使進(jìn)程能繼續(xù)執(zhí)行下去。如果此時(shí)內(nèi)存已滿，無法再裝入新的頁（段），則還須再利用頁（段）的置換功能，將內(nèi)存中暫時(shí)不用的頁（段）調(diào)出至磁盤上，騰出足夠的內(nèi)存空間后，再將所要訪問的頁（段）調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。這樣，便可使一個(gè)大的用戶程序在較小的內(nèi)存空間中運(yùn)行；也可使內(nèi)存中同時(shí)裝入更多的進(jìn)程并發(fā)執(zhí)行。從用戶角度看，該系統(tǒng)所具有的內(nèi)存容量，將比實(shí)際內(nèi)存容量大得多，人們把這樣的存儲(chǔ)器稱為虛擬存儲(chǔ)器。程序在運(yùn)行時(shí)如果它所要訪問的頁（段）已調(diào)入內(nèi)存，便可繼續(xù)虛擬存儲(chǔ)器是具有請(qǐng)求調(diào)入功能和置換功能，能僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行作業(yè)的存儲(chǔ)器系統(tǒng)，它能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種虛擬的存儲(chǔ)器系統(tǒng)。其邏輯容量由內(nèi)存和外存容量之和所決定，其運(yùn)行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存。可見，虛擬存儲(chǔ)技術(shù)是一種性能非常優(yōu)越的存儲(chǔ)器管理技術(shù)，故被廣泛地應(yīng)用于大、中、小型機(jī)器和微型機(jī)中。虛擬存儲(chǔ)器是具有請(qǐng)求調(diào)入功能和置換功能，能僅把作業(yè)的一部分裝（2）虛擬存儲(chǔ)器實(shí)現(xiàn)方式1.請(qǐng)求分頁系統(tǒng)：它是在分頁系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁功能和頁面置換功能所形成的頁式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入若干頁（而非全部程序）的用戶程序和數(shù)據(jù)，就可以啟動(dòng)運(yùn)行，以后再通過調(diào)頁功能和頁面置換功能，陸續(xù)把將要運(yùn)行的頁面調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的頁面置換到外存上，置換時(shí)以頁面為單位。2.請(qǐng)求分段系統(tǒng)：它是在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段和分段置換功能所形成的段式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入若干段（而非全部段）的用戶程序和數(shù)據(jù)，就可以啟動(dòng)運(yùn)行，以后再通過調(diào)段功能和置換功能將不運(yùn)行的段調(diào)出，同時(shí)調(diào)入將要運(yùn)行的段，置換以段為單位。3.請(qǐng)求段頁式系統(tǒng)：它是在段頁式系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁和頁面置換功能所形成的段頁式虛擬存儲(chǔ)系統(tǒng)。（2）虛擬存儲(chǔ)器實(shí)現(xiàn)方式1.請(qǐng)求分頁系統(tǒng)：（3）虛擬存儲(chǔ)器的特征離散性：指在內(nèi)存分配時(shí)采用離散的分配方式，它是虛擬存儲(chǔ)器的最基本的特征。多次性：指一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行，即在作業(yè)運(yùn)行時(shí)沒有必要將其全部裝入，只須將當(dāng)前要運(yùn)行的那部分程序和數(shù)據(jù)裝入內(nèi)存即可。多次性是虛擬存儲(chǔ)器最重要的特征。對(duì)換性：指允許在作業(yè)的運(yùn)行過程中在內(nèi)存和外存的對(duì)換區(qū)之間換進(jìn)、換出。虛擬性：指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。（3）虛擬存儲(chǔ)器的特征4.6請(qǐng)求分頁存儲(chǔ)管理方式（動(dòng)態(tài)頁式）動(dòng)態(tài)頁式管理是在分頁存儲(chǔ)管理基礎(chǔ)上發(fā)展起來的，指導(dǎo)思想：在作業(yè)運(yùn)行之前，不必把作業(yè)的整個(gè)地址空間全部裝入主存，而只要求當(dāng)前需要的一部分裝入主存即可。這樣，對(duì)作業(yè)地址空間，當(dāng)其作業(yè)的大小超過主存可用空間時(shí)，用戶無需考慮覆蓋結(jié)構(gòu)，用頁式存儲(chǔ)管理實(shí)現(xiàn)虛擬存儲(chǔ)器管理。這個(gè)方案可以為每個(gè)用戶提供一個(gè)虛擬存儲(chǔ)器，其虛擬空間比主存的空間大。這對(duì)編制大型程序來說，帶來了很多方便。4.6請(qǐng)求分頁存儲(chǔ)管理方式（動(dòng)態(tài)頁式）

動(dòng)態(tài)頁式管理分為請(qǐng)求頁式管理和預(yù)調(diào)入式管理。由于請(qǐng)求也是只讓進(jìn)程或作業(yè)的部分程序和數(shù)據(jù)駐留在內(nèi)存中，因此，在執(zhí)行過程中，不可避免地會(huì)在內(nèi)存中虛頁以及怎樣處理這種情況，是請(qǐng)求頁式管理必須解決的基本問題。取頁--將哪部分裝入內(nèi)存置頁--將調(diào)入的頁放在什么地方淘汰--內(nèi)存不足時(shí)，將哪些頁換出內(nèi)存。動(dòng)態(tài)頁式管理分為請(qǐng)求頁式管理和預(yù)調(diào)入式管理。請(qǐng)求頁式管理中的置換算法（頁式淘汰算法）

為了衡量一個(gè)調(diào)度算法的優(yōu)劣，先介紹幾個(gè)概念。為了簡(jiǎn)單起見，假定一個(gè)作業(yè)分配的主存塊數(shù)固定不變，且采用局部淘汰(淘汰一頁時(shí)，只考慮本作業(yè)內(nèi)部實(shí)施淘汰)。假定作業(yè)Ji共有m頁，系統(tǒng)分配給它的主存塊為n塊，這里m>n。開始時(shí)，主存沒有裝入任何一頁的信息。如果作業(yè)Ji在運(yùn)行中成功訪問的次數(shù)為S，不成功的訪問次數(shù)為F(產(chǎn)生缺頁中斷的次數(shù))，則作業(yè)執(zhí)行過程中總的訪問次數(shù)為A.這里，A=S（成功訪問的次數(shù)）+F（不成功的訪問次數(shù)）作業(yè)Ji執(zhí)行過程中的缺頁率f=F/A。

請(qǐng)求頁式管理中的置換算法（1）請(qǐng)求分頁中的硬件支持

它是在純分頁系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁功能、頁面置換功能所形成的頁式虛擬存儲(chǔ)系統(tǒng)，它是目前常用的一種虛擬存儲(chǔ)器的方式。1．請(qǐng)求分頁的頁表機(jī)制它是在純分頁的頁表機(jī)制上形成的，由于只將應(yīng)用程序的一部分調(diào)入內(nèi)存，還有一部分仍在磁盤上，故需在頁表中再增加若干項(xiàng)，供程序(數(shù)據(jù))在換進(jìn)、換出時(shí)參考。在請(qǐng)求分頁系統(tǒng)中的每個(gè)頁表項(xiàng)如圖所示。

頁號(hào)物理塊號(hào)狀態(tài)位P訪問字段A修改位M外存地址（1）請(qǐng)求分頁中的硬件支持頁號(hào)物理塊號(hào)狀態(tài)位P其中各字段說明如下：狀態(tài)位（存在位P）：用于指示該頁是否已調(diào)入內(nèi)存，供程序訪問時(shí)參考。訪問字段A：用于記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù)，或最近已有多長(zhǎng)時(shí)間未被訪問，提供給置換算法選擇換出頁面時(shí)參考。修改位M：表示該頁在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時(shí)就不需將該頁寫回到外存上，以減少系統(tǒng)的開銷和啟動(dòng)磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。外存地址：用于指出該頁在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁時(shí)使用。其中各字段說明如下：

2．缺頁中斷機(jī)構(gòu) 在請(qǐng)求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時(shí)，便要產(chǎn)生一缺頁中斷，請(qǐng)求OS將所缺頁調(diào)入內(nèi)存。與一般中斷的主要區(qū)別在于：缺頁中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)，而一般中斷在一條指令執(zhí)行完后檢查和處理中斷信號(hào)。缺頁中斷返回到該指令的開始重新執(zhí)行該指令，而一般中斷返回到該指令的下一條指令執(zhí)行。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。3．地址變換機(jī)構(gòu) 請(qǐng)求分頁系統(tǒng)中的地址變換機(jī)構(gòu)，是在分頁系統(tǒng)的地址變換機(jī)構(gòu)的基礎(chǔ)上，再為實(shí)現(xiàn)虛擬存儲(chǔ)器而增加了某些功能所形成的，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)存中換出一頁的功能等等，下圖給出了請(qǐng)求分頁系統(tǒng)的地址變換過程。2．缺頁中斷機(jī)構(gòu)

缺頁中斷處理是否否 是是否產(chǎn)生缺頁中否是斷請(qǐng)求調(diào)頁是開始（程序請(qǐng)求訪問一頁)越界中斷CPU檢索快表頁表項(xiàng)是否在快表中？訪問頁表頁是否在內(nèi)存中？修改快表修改訪問位和修改位形成物理地址

地址變換結(jié)束保留CPU現(xiàn)場(chǎng)

從外存中找到缺頁

頁號(hào)>頁表長(zhǎng)度？

內(nèi)存滿否？選擇一頁換出

該頁是否被修改？

將該頁寫回外存

將一頁從外存換入內(nèi)存

修改頁表

CPU從外存讀缺頁

啟動(dòng)I/O硬件

（2）頁面分配1.最少物理塊數(shù)在為進(jìn)程分配物理塊時(shí)，首先應(yīng)該考慮的問題是：能保證進(jìn)程能正常運(yùn)行所需的最少物理塊數(shù)（稱為最小物理塊數(shù)）。若系統(tǒng)為某進(jìn)程所分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無法運(yùn)行，這取決于指令的格式、功能和尋址方式。2.頁面的分配和置換策略在請(qǐng)求分頁系統(tǒng)中，可采取兩種分配策略——固定和可變分配策略。在進(jìn)行置換時(shí)，也可采取兩種策略——全局置換和局部置換。于是可組合成以下三種策略：固定分配局部置換策略：它基于進(jìn)程的類型（交互型或批處理型等），或根據(jù)程序員、系統(tǒng)管理員的建議，為每個(gè)進(jìn)程分配一固定頁數(shù)的內(nèi)存空間，在整個(gè)運(yùn)行期間都不再改變。如果進(jìn)程在運(yùn)行中發(fā)現(xiàn)缺頁，則只能從該進(jìn)程在內(nèi)存的固定頁面中選出一頁換出，然后再調(diào)入另一頁，保證分配給該進(jìn)程的內(nèi)存空間不變。（2）頁面分配1.最少物理塊數(shù)可變分配全局置換策略：系統(tǒng)為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，而OS本身也保持一個(gè)空閑物理塊隊(duì)列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁時(shí)，由系統(tǒng)從空閑物理塊隊(duì)列中，取出一物理塊分配給該進(jìn)程，并將欲調(diào)入的缺頁裝入其中。當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí)，OS才能從內(nèi)存中選擇一頁調(diào)出，該頁可能是系統(tǒng)中任一進(jìn)程的頁?？勺兎峙渚植恐脫Q：根據(jù)進(jìn)程的類型或程序員的要求，為每個(gè)進(jìn)程分配一定數(shù)目的內(nèi)存空間；但當(dāng)某進(jìn)程發(fā)生缺頁時(shí)，只允許從該進(jìn)程在內(nèi)存的頁面中選出一頁換出，而不影響其它進(jìn)程的運(yùn)行?？勺兎峙淙种脫Q策略：系統(tǒng)為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，而3．頁面分配算法在采用固定分配策略時(shí)，可采用以下幾種物理塊分配方法：平均分配算法：將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。按比例分配算法：這是根據(jù)進(jìn)程的大小按比例分配物理塊?？紤]優(yōu)先權(quán)的分配算法：該方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。3．頁面分配算法(3)頁面調(diào)入策略

為能使進(jìn)程運(yùn)行，必須事先將一部分要執(zhí)行的程序和數(shù)據(jù)調(diào)入內(nèi)存。1.調(diào)入頁面的時(shí)機(jī)為了將進(jìn)程運(yùn)行時(shí)所缺的頁面調(diào)入內(nèi)存，可采取策略有：預(yù)調(diào)頁策略是一種主動(dòng)的缺頁調(diào)入策略，即將那些預(yù)計(jì)在不久的將來會(huì)被訪問的程序或數(shù)據(jù)所在的頁面，預(yù)先調(diào)入內(nèi)存。由于預(yù)測(cè)的準(zhǔn)確率不高（50%），所以這種策略主要用于進(jìn)程的首次調(diào)入。有的系統(tǒng)將預(yù)調(diào)頁策略用于請(qǐng)求調(diào)頁，例如在VAX/VMS操作系統(tǒng)中，采用了一種稱為群頁式的調(diào)頁策略，當(dāng)系統(tǒng)將進(jìn)程所請(qǐng)求的頁面調(diào)入內(nèi)存時(shí)，也同時(shí)將其相鄰的幾個(gè)頁面調(diào)入內(nèi)存。請(qǐng)求調(diào)頁策略是指當(dāng)進(jìn)程在運(yùn)行中發(fā)生缺頁時(shí)，就立即提出請(qǐng)求，由系統(tǒng)將缺頁調(diào)入內(nèi)存。目前的虛擬存儲(chǔ)器中，大多采用此策略。但這種策略在調(diào)頁時(shí)須花費(fèi)較大的系統(tǒng)開銷，如需頻繁啟動(dòng)磁盤I/O。(3)頁面調(diào)入策略為能使進(jìn)程運(yùn)行，必須事先將一部分要執(zhí)行2.從何處調(diào)入頁面在虛擬存儲(chǔ)系統(tǒng)中，外存（硬盤）常常被分成兩部分；文件區(qū)（用于存放文件）和對(duì)換區(qū)（用于存放對(duì)換頁面）。通常，對(duì)換區(qū)的磁盤I/O速度比文件區(qū)要高。每當(dāng)進(jìn)程發(fā)出缺頁請(qǐng)求時(shí)，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存呢？在UNIX系統(tǒng)中，對(duì)于從未運(yùn)行過的頁面，都應(yīng)從硬盤文件區(qū)調(diào)入；對(duì)于曾經(jīng)運(yùn)行過而又被換出的頁面，可以從對(duì)換區(qū)調(diào)入；對(duì)于共享頁面，該頁面可能已由其它進(jìn)程調(diào)入內(nèi)存，此時(shí)就無須再?gòu)膶?duì)換區(qū)調(diào)入。2.從何處調(diào)入頁面（三）頁面置換算法

（PageReplacementAlgorithms）在進(jìn)程運(yùn)行過程中，如果發(fā)生缺頁，此時(shí)內(nèi)存中又無空閑塊時(shí)，為了保證進(jìn)程能正常運(yùn)行，就必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送磁盤的對(duì)換區(qū)。但將哪個(gè)頁面調(diào)出，則須根據(jù)一定的頁面置換算法來確定。置換算法的好壞將直接影響系統(tǒng)的性能，不適當(dāng)?shù)乃惴赡軙?huì)導(dǎo)致進(jìn)程發(fā)生“抖動(dòng)”（Thrashing)。即剛被換出的頁很快又被訪問，需重新調(diào)入，導(dǎo)致系統(tǒng)頻繁地更換頁面，以致一個(gè)進(jìn)程在運(yùn)行中把大部分時(shí)間花費(fèi)在完成頁面置換的工作上，我們稱該進(jìn)程發(fā)生了“抖動(dòng)”（顛簸）。從理論上講，應(yīng)將那些以后不再被訪問的頁面換出，或把那些在較長(zhǎng)時(shí)間內(nèi)不會(huì)再被訪問的頁面換出。

（三）頁面置換算法

（PageReplacementAl（1）最佳（Optimal）置換算法 它是一種理想化的算法，性能最好，但在實(shí)際上難于實(shí)現(xiàn)。即選擇那些永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問的頁面置換出去。但是要確定哪一個(gè)頁面是未來最長(zhǎng)時(shí)間內(nèi)不再被訪問的，目前來說是很難估計(jì)的，所以該算法通常用來評(píng)價(jià)其它算法。例：假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁面號(hào)引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。如下圖所示，進(jìn)程運(yùn)行時(shí)先將7，0，1三個(gè)頁面裝入內(nèi)存。當(dāng)進(jìn)程訪問頁面2時(shí)，產(chǎn)生缺頁中斷，此時(shí)OS根據(jù)最佳置換算法，頁面7將在第18次才被訪問，是三頁中將最久不被訪問的頁面，所以被淘汰。接著訪問頁面0時(shí)，發(fā)現(xiàn)已在內(nèi)存中，而不會(huì)產(chǎn)生缺頁中斷，以此類推。從圖可以看出，采用最佳置換算法，只發(fā)生了6次頁面置換。4.7頁面置換算法（1）最佳（Optimal）置換算法4.7頁面置換算法最佳（Optimal）置換算法發(fā)生了6次面置換，9次缺頁中斷。最佳（Optimal）置換算法發(fā)生了6次面置換，9次缺頁中斷4.7頁面置換算法

2.先進(jìn)先出（FIFO）算法FIFO：總是淘汰最先進(jìn)入主存儲(chǔ)器的那一頁。FIFO算法容易實(shí)現(xiàn)，但是它所依據(jù)的理由不是普遍成立的。哪些在內(nèi)存中駐留很久的頁，往往是被經(jīng)常訪問的頁，結(jié)果這些常用的頁都被淘汰調(diào)出，而可能又需要立即調(diào)回內(nèi)存。采用FIFO算法還會(huì)產(chǎn)生一種奇怪現(xiàn)象，直觀上，分配給的作業(yè)的實(shí)頁越多，進(jìn)程執(zhí)行時(shí)發(fā)生的缺頁中斷率就越小，但對(duì)FIFO算法這個(gè)結(jié)論并不是絕對(duì)的。在某些情況下，當(dāng)分配的頁面多反而導(dǎo)致更多的缺頁中斷，這種現(xiàn)象稱為FIFO異?，F(xiàn)象或稱Belady現(xiàn)象。

4.7頁面置換算法所謂異?，F(xiàn)象，即在未給進(jìn)程或作業(yè)分配足它所要求的頁面數(shù)時(shí)，有時(shí)會(huì)出現(xiàn)分配的頁面數(shù)增多，缺頁次數(shù)反而增加的奇怪現(xiàn)象。所謂異?，F(xiàn)象，即在未給進(jìn)程或作業(yè)分配足它所要求的頁面數(shù)時(shí)，有(2)先進(jìn)先出（FIFO）置換算法

(2)先進(jìn)先出（FIFO）置換算法

練習(xí)：物理塊從3塊增加到4塊

練習(xí)：物理塊從3塊增加到4塊Belady現(xiàn)象示例Belady現(xiàn)象示例Belady現(xiàn)象示例Belady現(xiàn)象示例（3）最近最久未使用置換算法

LRU（LeastRecentlyUsed）該算法是選擇最近最久未使用的頁面予以淘汰，系統(tǒng)在每個(gè)頁面設(shè)置一個(gè)訪問字段，用以記錄這個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間T，當(dāng)要淘汰一個(gè)頁面時(shí)，選擇T最大的頁面。但在實(shí)現(xiàn)時(shí)需要硬件的支持（寄存器或棧）。利用LRU算法對(duì)上例進(jìn)行頁面置換的結(jié)果如下：

（3）最近最久未使用置換算法

LRU（Least

當(dāng)需要淘汰某一頁時(shí)，算法選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒有使用過的頁先淘汰。其理由是，如果某頁被訪問了，則它可能馬上還要被訪問，反之如果該頁很長(zhǎng)時(shí)間未被訪問，則它在最近一段時(shí)間內(nèi)也不會(huì)被訪問。要實(shí)現(xiàn)LFU算法，需要付出很大的系統(tǒng)開銷。在實(shí)際系統(tǒng)中，經(jīng)常采用LRU的近似算法LFU和NUR。

實(shí)現(xiàn)：可利用一個(gè)特殊的棧來保存當(dāng)前使用的各個(gè)頁面的頁面號(hào)。每當(dāng)進(jìn)程訪問某頁面時(shí)，便將該頁面的頁面號(hào)從棧中移出，再將它壓入棧頂。因此，棧頂始終是最新被訪問的頁面的編號(hào)，而棧底則是最近最久未使用頁面的頁面號(hào)。

2.最近最久未使用頁面置換算法（LRU）當(dāng)需要淘汰某一頁時(shí)，算法選擇離當(dāng)前時(shí)間最近的一段時(shí)間A.近似算法(LFU)：當(dāng)需要淘汰時(shí)，應(yīng)淘汰被訪問次數(shù)最少的頁。一種簡(jiǎn)單的方法式為每一頁設(shè)置一個(gè)計(jì)數(shù)器，每當(dāng)訪問一頁時(shí)，就把該頁對(duì)應(yīng)的計(jì)數(shù)器加1，隔一個(gè)周期T，把左右計(jì)數(shù)器清0，當(dāng)發(fā)生缺頁中斷時(shí)，選擇技術(shù)值最小的頁，把它淘汰，同時(shí)把所有計(jì)數(shù)器清0。A.近似算法(LFU)：當(dāng)需要淘汰時(shí)，應(yīng)淘汰被訪問次數(shù)最少的B.最近沒有使用頁面淘汰算法NUR,NRU,CLOCK：當(dāng)需要淘汰某一頁時(shí)，從那些最近一個(gè)時(shí)期內(nèi)來被訪問的頁中任選一頁淘汰。雖然LRU算法是一種比較好的置換算法，但由于它要求有較多的硬件支持，使實(shí)現(xiàn)起來成本較高，在實(shí)際應(yīng)用中，這是一種用得較多的算法。實(shí)現(xiàn)方法：在頁內(nèi)增設(shè)一個(gè)訪問位，當(dāng)這一頁被訪問時(shí)，硬件把它置成“1”，而沒有被訪問過的頁，訪問位為“0”。因此產(chǎn)生缺頁中斷時(shí)，可從那些訪問位為0的頁中選一頁進(jìn)行淘汰。B.最近沒有使用頁面淘汰算法NUR,NRU,CLOCK：當(dāng)需(4)Clock置換算法

（最近未用算法NUR（NotUsedRecently））將最近一段時(shí)間未引用過的頁面換出(4)Clock置換算法

（最近未用算法NUR（NotUClock置換算法Clock置換算法C.改進(jìn)型的CLOCK算法：在將一個(gè)頁面換出時(shí)，如果該頁已被修改過，便須將它重新寫到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。換言之，對(duì)于修改過的頁面在換出時(shí)所付出的開銷將比未修改過的頁面開銷大。因而，新算法中還須考慮置換代價(jià)問題。由訪問位A和修改位M可組成：1類（A=0,M=0）,表示該頁最近既未被訪問、又未被修改，是最佳淘汰頁。2類（A=0,M=1）,表示該頁最近未被訪問、但已被修改，并不是很好的淘汰頁。3類（A=1,M=0）,該頁最近已被訪問、又未被修改，有可能再被訪問。4類（A=1,M=1）,該頁最近已被訪問且被修改，有可能再被訪問。C.改進(jìn)型的CLOCK算法：在將一個(gè)頁面換出時(shí)，如果該頁已被改進(jìn)型CLOCK算法的執(zhí)行過程：1從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊(duì)列，尋找1類頁面，將所遇到的第一個(gè)頁面作為所選中的淘汰頁，在第一次掃描期間不改變?cè)L問位A；2如果第一步失敗，即查找一周后未遇到的1類頁面，則開始第2類頁面，將所遇到的第一個(gè)頁面作為所選中的淘汰頁。第二輪掃描期間，將所有經(jīng)過的頁面的訪問位置0；3如果第二步也失敗，則將指針返回到開始的位置（此時(shí)所有頁面的訪問位為0），然后重復(fù)第一步，仍不行再重復(fù)第二步，一定能找到要淘汰的頁。改進(jìn)型CLOCK算法的執(zhí)行過程：④隨機(jī)淘汰(RG)算法，在系統(tǒng)設(shè)計(jì)人員認(rèn)為無法確定哪些頁被訪問的概率較低時(shí)，隨機(jī)地選擇某個(gè)用戶頁面并將其淘汰的算法。*⑤輪轉(zhuǎn)法，循回?fù)Q出內(nèi)存可用區(qū)內(nèi)一個(gè)可以被換出的頁面，無論該頁是剛換進(jìn)或已換進(jìn)內(nèi)存很長(zhǎng)時(shí)間的算法。n抖動(dòng)（或稱顛簸）：如果分配給進(jìn)程的存儲(chǔ)塊數(shù)小于進(jìn)程所需要的最小值，進(jìn)程的運(yùn)行將很頻繁地產(chǎn)生缺頁中斷的現(xiàn)象。④隨機(jī)淘汰(RG)算法，在系統(tǒng)設(shè)計(jì)人員認(rèn)為無法確定哪些頁被訪(5)性能分析1.缺頁率對(duì)有效訪問時(shí)間的影響在請(qǐng)求分頁系統(tǒng)中，假設(shè)存儲(chǔ)器的訪問時(shí)間ma為100ns（一般為10ns～幾百ns），缺頁率為p，缺頁中斷時(shí)間為25ms，則有效訪問時(shí)間就可以表示為：有效訪問時(shí)間=（1一p）×ma十p×缺頁中斷時(shí)間=（1一p）×0.1十p×25000=0.1十24999.9p 由上式可以看出，有效訪問時(shí)間與缺頁率成正比。如果缺頁率為0.1%，則有效訪問時(shí)間約為25μs，與直接訪問存儲(chǔ)器的有效訪問時(shí)間（0.1μs）相比的時(shí)間，程序執(zhí)行的性能將受到嚴(yán)重的影響。如果希望在缺頁時(shí)，僅使有效訪問時(shí)間延長(zhǎng)不超過10%，則可計(jì)算出缺頁率p=0.0000004，由此得出，要求在2500000次的訪問中才發(fā)生一頁缺頁，即請(qǐng)求分頁方式應(yīng)保持非常低的缺頁率；否則，將使程序執(zhí)行速度受到嚴(yán)重影響。此外，提高磁盤I/O的速度，對(duì)改善請(qǐng)求分頁系統(tǒng)的性能至關(guān)重要。為此，應(yīng)選用高速磁盤和高速磁盤接口。(5)性能分析1.缺頁率對(duì)有效訪問時(shí)間的影響2.工作集程序在運(yùn)行中所產(chǎn)生的缺頁情況，會(huì)影響程序的運(yùn)行速度及系統(tǒng)性能，而缺頁率的高低又將是與每個(gè)進(jìn)程所占用的物理塊數(shù)目有關(guān)。這里我們簡(jiǎn)單地分析一下應(yīng)為每個(gè)進(jìn)程分配多少個(gè)物理塊，才能把缺頁率保持在一個(gè)合理的水平上。缺頁率與進(jìn)程所分得的物理塊數(shù)目有密切關(guān)系。下圖說明了的缺頁率與進(jìn)程分得的物理塊數(shù)目N之間的關(guān)系曲線。從圖中可以看出，缺頁率隨著所分得的物理塊數(shù)目的減少而遞增，并在所分到的物理塊數(shù)目較少處，出現(xiàn)一個(gè)拐點(diǎn)。在拐點(diǎn)上限以左時(shí)，隨著分到的物理塊數(shù)目的增加，缺頁率明顯地減少；而過了拐點(diǎn)，在下限以右時(shí)，隨著分到的物理塊數(shù)目的增加，卻對(duì)缺頁率的改善并不明顯。所以，為進(jìn)程分配的物理塊數(shù)，應(yīng)取在該曲線的拐點(diǎn)左右。2.工作集缺頁率拐點(diǎn)

所分得的物理塊數(shù)工作集的理論是在1968年由Denning提出來的。他認(rèn)為，程序在運(yùn)行時(shí)對(duì)頁面的訪問是不均勻的，即往往在某段時(shí)間內(nèi)的訪問僅局限于較少的若干個(gè)頁面，如果能夠預(yù)知程序在某段時(shí)間間隔內(nèi)要訪問哪些頁面，并能將它們提前調(diào)入內(nèi)存，將會(huì)大大地降低缺頁率，從而減少置換工作，提高CPU的利用率。缺頁率

所謂工作集是指，在某段時(shí)間間隔（Δ）里，進(jìn)程實(shí)際要訪問的頁面的集合。Denning認(rèn)為，雖然程序只需有少量的幾頁在內(nèi)存就可以運(yùn)行，但為了使程序能夠有效地運(yùn)行，較少地產(chǎn)生缺頁、就必須使程序的工作集全部在內(nèi)存中。把某進(jìn)程在時(shí)間t的工作集記為w（t，Δ），把變量Δ稱為工作集“窗口尺寸”（WindowsSize）。正確選擇工作集窗口（Δ）的大小，對(duì)存儲(chǔ)器的有效利用和系統(tǒng)吞吐量的提高，都將產(chǎn)生重要的影響。在WindowsNT中，虛擬存儲(chǔ)管理程序（VirtualMemoryManager)為每一個(gè)進(jìn)程分配固定數(shù)量的頁面，并且這個(gè)數(shù)目可以進(jìn)行動(dòng)態(tài)的調(diào)整。那么這個(gè)數(shù)量如何確定？又如何進(jìn)行動(dòng)態(tài)的調(diào)整呢？這個(gè)數(shù)目就是由每個(gè)進(jìn)程的工作集來確定，并且根據(jù)主存的負(fù)荷和進(jìn)程的缺頁情況動(dòng)態(tài)地調(diào)整其工作集。所謂工作集是指，在某段時(shí)間間隔（Δ）里，進(jìn)程實(shí)際要訪問

其具體的作法是：一個(gè)進(jìn)程在創(chuàng)建時(shí)就指定了一個(gè)最小工作集，該工作集的大小是保證進(jìn)程運(yùn)行在主存中應(yīng)有的最小頁面數(shù)。但在主存負(fù)荷不太大（頁面不太滿）時(shí)，虛存管理程序還允許進(jìn)程擁有盡可能多的頁面作為其最大工作集。當(dāng)主存負(fù)荷發(fā)生變化時(shí)，如空閑頁架（塊）不多了，虛存管理程序就使用“自動(dòng)調(diào)整工作集”的技術(shù)來增加主存中可用的自由頁架。方法是檢查主存中的每個(gè)進(jìn)程，將它當(dāng)前工作集大小與其最小工作集進(jìn)行比較。如果大于最小值，則從它們的工作集中移去一些頁面作為主存自由頁面，可為其它進(jìn)程所使用。若主存自由頁面仍然太小，則不斷進(jìn)行檢查，直到每個(gè)進(jìn)程的工作集都達(dá)到最小值為止。當(dāng)每個(gè)工作集都已達(dá)到最小值時(shí)，虛存管理程序跟蹤進(jìn)程的缺頁數(shù)量，根據(jù)內(nèi)存中自由頁面數(shù)量可以適當(dāng)增加其工作集的大小。其具體的作法是：一個(gè)進(jìn)程在創(chuàng)建時(shí)就指定了一個(gè)最小工作集，

存儲(chǔ)保護(hù)一種是地址越界保護(hù)，另一種是通過頁表控制對(duì)內(nèi)存信息的操作方式提供保護(hù)。地址越界保護(hù)可由地址變換機(jī)構(gòu)中的控制寄存器的值——頁表長(zhǎng)度和所要訪問的虛地址相比較完成。

存取控制保護(hù)的實(shí)現(xiàn)則是在頁表增加相應(yīng)的保護(hù)位即可。

存儲(chǔ)保護(hù)

4．3分頁管理

4.3.1

分頁管理的基本原理

分頁存儲(chǔ)管理是解決存儲(chǔ)零頭的一種方法。動(dòng)態(tài)重定位是解決存儲(chǔ)器零頭問題的一種途徑，但要移動(dòng)大量信息花去不少處理機(jī)時(shí)間,代價(jià)比較高,這是因?yàn)檫@種分配要求把作業(yè)必須安置在一連續(xù)存儲(chǔ)區(qū)內(nèi)的緣故,而分頁存儲(chǔ)管理正是要避開這種連續(xù)性要求。4．3分頁管理分頁存儲(chǔ)管理，在該方式中，用戶程序的地址被劃分成劃分若干個(gè)固定大小的區(qū)域，稱為頁（或頁面）。頁面的典型大小為1k；相應(yīng)地將內(nèi)存空間分成若干個(gè)物理塊(或頁框)，頁和塊的大小相同，這樣可將用戶程序的任一頁放到內(nèi)存的任一塊中，實(shí)現(xiàn)離散分配。這時(shí)內(nèi)存中的碎片大小不會(huì)超過一頁。關(guān)鍵問題是實(shí)現(xiàn)邏輯地址到物理地址的二維動(dòng)態(tài)映射，這是通過頁表實(shí)現(xiàn)的。引入聯(lián)想存貯器（超高速緩存）構(gòu)成的快表可加快映射的速度。內(nèi)存空間的保護(hù)是通過地址映射過程中檢查頁號(hào)越界來實(shí)現(xiàn)的。分頁存儲(chǔ)管理，在該方式中，用戶程序的地址被劃分成劃分若干個(gè)固（1）基本分頁存儲(chǔ)管理原理1．分頁 分頁存儲(chǔ)管理是將一個(gè)進(jìn)程的地址空間劃分成若干個(gè)大小相等的區(qū)域，稱為頁。相應(yīng)地，將內(nèi)存空間劃分成與頁相同大小的若干個(gè)物理塊，稱為塊或頁框。在為進(jìn)程分配內(nèi)存時(shí)，將進(jìn)程中若干頁分別裝入多個(gè)不相鄰接的塊中。2.地址結(jié)構(gòu) 分頁系統(tǒng)的地址結(jié)構(gòu)如下圖所示，它由兩部分組成：前一部分為頁號(hào)P；后一部分為位移量W，即頁內(nèi)地址。圖中的地址長(zhǎng)度為32位，其中0～11位為頁內(nèi)地址（每頁的大小為4K），12～31位為頁號(hào)，所以允許地址空間的大小最多為1M個(gè)頁。

3112110

頁號(hào)P位移量W（1）基本分頁存儲(chǔ)管理原理頁號(hào)P頁號(hào)頁內(nèi)地址

51025＝32（頁）210＝1024（每頁1024字節(jié)）在分配存儲(chǔ)空間時(shí),是以頁面為單位來分配.例如,一個(gè)作業(yè)的地址空間有M頁,那么只需要分配給他M個(gè)頁面的存儲(chǔ)空間,每一頁分別裝入一個(gè)存儲(chǔ)頁面即可.并不需要這些頁面是連續(xù)的.以上這些問題需要一個(gè)地址映射.頁號(hào)頁內(nèi)地址51025＝32（若給定一個(gè)邏輯地址空間中的地址為A，頁面大小為L(zhǎng)，則頁號(hào)P和頁內(nèi)地址w可按下式求得：P=INT[A/L]W=[A]MODL其中，INT是整除函數(shù)，MOD是取余函數(shù)。例：系統(tǒng)頁面大小為１KB，設(shè)A＝2170B，則P=2,W=122若給定一個(gè)邏輯地址空間中的地址為A，頁面大小為L(zhǎng)，則頁號(hào)P和3.頁表在將進(jìn)程的每一頁離散地分配到內(nèi)存的多個(gè)物理塊中后，系統(tǒng)應(yīng)能保證能在內(nèi)存中找到每個(gè)頁面所對(duì)應(yīng)的物理塊。為此，系統(tǒng)為每個(gè)進(jìn)程建立了一張頁面映射表，簡(jiǎn)稱頁表（如下圖所示）。每個(gè)頁在頁表中占一個(gè)表項(xiàng)，記錄該頁在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)。進(jìn)程在執(zhí)行時(shí)，通過查找頁表，就可以找到每頁所對(duì)應(yīng)的物理塊號(hào)?？梢姡摫淼淖饔檬菍?shí)現(xiàn)從頁號(hào)到物理塊號(hào)的地址映射。3.頁表

頁表：由頁號(hào)和頁面號(hào)組成，指出邏輯地址中頁號(hào)與主存中塊號(hào)（頁面號(hào)）的對(duì)應(yīng)關(guān)系頁號(hào)作業(yè)地址空間的頁序號(hào)頁面號(hào)內(nèi)存空間的頁面序號(hào)

頁號(hào)頁面號(hào)頁表頁表：由頁號(hào)和頁面號(hào)組成，頁號(hào)頁面號(hào)頁表存儲(chǔ)頁面表一個(gè)系統(tǒng)只有一張存儲(chǔ)頁面表.它指出內(nèi)存各頁面是否被分配,以及來分配頁面的總數(shù).………

19183210

若內(nèi)存被分配為1024個(gè)頁面,內(nèi)存單元長(zhǎng)20比特.1024/20=52個(gè)單元.描述了1024個(gè)頁面是否分配.存儲(chǔ)頁面表………19184.3.2地址變換(映射)機(jī)構(gòu)1.基本的地址變換機(jī)構(gòu)

地址變換機(jī)構(gòu)的基本任務(wù)是利用頁表把用戶程序中的邏輯地址變換成內(nèi)存中的物理地址，實(shí)際上就要將用戶程序中的頁號(hào)變換成內(nèi)存中的物理塊號(hào)。為了實(shí)現(xiàn)地址變換功能，在系統(tǒng)中設(shè)置頁表寄存器，用來存放頁表的始址和頁表的長(zhǎng)度。在進(jìn)程未執(zhí)行時(shí)，每個(gè)進(jìn)程對(duì)應(yīng)的頁表的始址和長(zhǎng)度存放在進(jìn)程的PCB中，當(dāng)該進(jìn)程被調(diào)度時(shí)，就將它們裝入頁表寄存器。在進(jìn)行地址變換時(shí)，系統(tǒng)將頁號(hào)與頁表長(zhǎng)度進(jìn)行比較，如果頁號(hào)大于頁表寄存器中的頁表長(zhǎng)度，則訪問越界，產(chǎn)生越界中斷。如未出現(xiàn)越界，則根據(jù)頁表寄存器中的頁表始址和頁號(hào)計(jì)算出該頁在頁表項(xiàng)中的位置，得到該頁的物理塊號(hào)，將此物理塊號(hào)裝入物理地址寄存器中。與此同時(shí)，將有效地址（邏輯地址）寄存器中頁內(nèi)地址直接裝入物理地址寄存器的塊內(nèi)地址字段中，這樣便完成了從邏輯地址到物理地址的變換。4.3.2地址變換(映射)機(jī)構(gòu)1.基本的地址變換機(jī)構(gòu)物理地址(絕對(duì)地址)

相對(duì)地址(有效邏輯地址)頁面號(hào)頁內(nèi)地址頁號(hào)頁內(nèi)地址頁表長(zhǎng)度頁表始址控制寄存器物理地址(絕對(duì)地址)相對(duì)地址(有效邏輯地址)頁面號(hào)頁內(nèi)地址頁表長(zhǎng)度頁表始址31k2452相對(duì)地址頁號(hào)頁面號(hào)0213288452OS物理地址86441024*8+452=8644頁表長(zhǎng)度頁表始址31k2452第0頁第1頁第2頁第3頁第4頁第5頁第6頁

05k6k7k8k9k10k11k12k13k14k15k16k17k31k57915131016...0k1k2k3k4k5k6k0k1k2k3k4k5k6k作業(yè)1的地址空間作業(yè)1的地址空間頁表圖頁式管理的示意圖主存空間頁表第0頁0.0k0k作業(yè)1的地例：作業(yè)地址空間共有7個(gè)頁，每頁的相對(duì)地址為0~1023，1024~2047，2048~3071，…，6144~6150。其對(duì)應(yīng)的主存塊在頁表中已列出。分別為5，7，9，15，13，10，16共7塊。假定頁表在主存始址為500。若該程序從第0頁開始運(yùn)行，且現(xiàn)程序計(jì)數(shù)器內(nèi)容為：例：作業(yè)地址空間共有7個(gè)頁，每頁的相對(duì)地址為0~1023，114.……..109…0硬件動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)工作如下：1.把該作業(yè)的頁表始址（500）和頁表長(zhǎng)度（7）放入控制寄存器中。2.將程序計(jì)數(shù)器內(nèi)容的頁號(hào)部分（0）與控制寄存器中的頁表長(zhǎng)度（7）相比較，若頁號(hào)<頁表長(zhǎng)度時(shí)轉(zhuǎn)3，否則產(chǎn)生地址越界，終止程序運(yùn)行。010014.……..109…03.將程序計(jì)數(shù)器中的頁號(hào)與控制寄存器中的頁表始址相加，得到該訪問操作所在頁號(hào)在頁表中的入口地址：500+0=5004.用該地址去訪頁表，獲得該頁所對(duì)應(yīng)的主存塊5。5.把主存塊號(hào)5與程序計(jì)數(shù)器中的頁內(nèi)位移相拼接，從而得到該操作所在主存的物理地址：5×1024+100=52206.根據(jù)這個(gè)地址5220，完成指定操作。3.將程序計(jì)數(shù)器中的頁號(hào)與控制寄存器中的頁表始址相加，得到該控制寄存器程序計(jì)數(shù)器50070(頁號(hào)）

100（頁內(nèi)地址）>+57915131016頁表內(nèi)存地址寄存器5(內(nèi)存塊號(hào)）

100（頁內(nèi)地址）12345圖頁式地址變換過程控制寄存器程序計(jì)數(shù)器50070(頁號(hào)）

頁表寄存器

邏輯地址2500

頁號(hào)塊號(hào)

012

每頁1KB(1024)

頁號(hào)2頁內(nèi)地址452頁表始址頁表長(zhǎng)度

2 4 5寫出下圖中邏輯地址2500所對(duì)應(yīng)的物理地址

越界中斷

頁表寄存器

邏輯地址2500

頁號(hào)塊號(hào)

012

每頁1KB(1024)

物理地址55725*1024+452塊號(hào)5塊內(nèi)地址452

頁號(hào)2頁內(nèi)地址452頁表始址頁表長(zhǎng)度﹥

2 4 5邏輯地址2500所對(duì)應(yīng)的物理地址

快表和聯(lián)想存貯器

從上述地址轉(zhuǎn)換過程可以看出，執(zhí)行一次訪內(nèi)操作至少要訪問主存兩次。一次訪頁表，以確定所取數(shù)據(jù)或指令的物理地址；另一次是根據(jù)地址取數(shù)據(jù)或指令。這樣就把程序的執(zhí)行速度降低一倍。為了提高存取速度，通常設(shè)置一個(gè)專用的高速緩沖寄存器組，用來存放頁表的一部分。我們把存放在高速緩沖寄存器中的頁表叫快表，這個(gè)高速緩沖寄存器又叫聯(lián)想存貯器。快表和聯(lián)想存貯器聯(lián)想存貯器的存取速度比主存高，但造價(jià)也高。因此只能采用少量，整個(gè)系統(tǒng)通常只要用8~16個(gè)寄存器即可使程序執(zhí)行速度大大提高。快表的格式見下圖。

頁號(hào)塊號(hào)訪問位狀態(tài)位聯(lián)想存貯器的存取速度比主存高，但造價(jià)也高。因此只能采用少量，其中，“頁號(hào)”是程序訪問過的地址空間的頁號(hào)，“塊號(hào)”是該頁所對(duì)應(yīng)的主存塊號(hào)；訪問位指示該頁最近是否被訪問過?！?”表示沒有被訪問，“1”表示訪問過；“狀態(tài)”位指示該寄存器是否被占用。通常“0”表示空閑，“1”表示占用。為了保證快表中的內(nèi)容為現(xiàn)正運(yùn)行程序的頁表內(nèi)容，在每個(gè)程序被選中時(shí)，由恢復(fù)現(xiàn)場(chǎng)程序把快表的所有狀態(tài)位清“0”，或恢復(fù)已保存的快表內(nèi)容。其中，“頁號(hào)”是程序訪問過的地址空間的頁號(hào)，“塊號(hào)”是該頁所當(dāng)進(jìn)程訪問一頁時(shí)，系統(tǒng)將頁號(hào)與快表中的所有項(xiàng)進(jìn)行并行比較。若訪問的頁在快表中，即可立即進(jìn)行地址轉(zhuǎn)換。當(dāng)被訪問的頁不在快表中時(shí)，就要將由慢表找到的內(nèi)存塊號(hào)與虛頁號(hào)填入快表中，若快表已滿，則置換其中訪問位為0的一項(xiàng)。另外，在設(shè)置快表的情況下，硬件地址轉(zhuǎn)換機(jī)構(gòu)在進(jìn)行地址變換時(shí)，同時(shí)開始兩個(gè)變換過程。當(dāng)進(jìn)程訪問一頁時(shí)，系統(tǒng)將頁號(hào)與快表中的所有項(xiàng)進(jìn)行并行比較。若一個(gè)是利用主存頁表進(jìn)行的正常變換過程，另一個(gè)是利用快表進(jìn)行的快速變換過程。一旦快表中有與查找的頁號(hào)相符合時(shí)，則立即停止正常的訪主存頁表過程。并將快表中的塊號(hào)與CPU給出的頁內(nèi)位移相拼接，得到訪問主存的絕對(duì)地址。從而結(jié)束了快表的查找工作。一個(gè)是利用主存頁表進(jìn)行的正常變換過程，另一個(gè)是利用快表進(jìn)行的當(dāng)利用快表進(jìn)行變換時(shí)，若沒有找到要查詢的頁時(shí)，則繼續(xù)正常的轉(zhuǎn)換過程，直到形成訪問主存的絕對(duì)地址。而且還要把從主存頁表中取出的塊號(hào)和CPU給出的頁號(hào)一起寫入快表中狀態(tài)位為0的一行中。若沒有這樣行存在，則寫入訪問位為0的某一行中，并同時(shí)置狀態(tài)位和訪問位為1。需要說明的是，快表的地址轉(zhuǎn)換是非?？斓?，因?yàn)樗菍㈨撎?hào)與快表中的各行同時(shí)比較，從而大大減少了地址變換時(shí)間，基本上克服了兩次訪問主存的缺點(diǎn)。當(dāng)利用快表進(jìn)行變換時(shí)，若沒有找到要查詢的頁時(shí)，則繼續(xù)正常的轉(zhuǎn)由于成本的原因，快表不可能做得很大，通常只能存放16~512個(gè)頁表項(xiàng)。例如，在Intel80486中有32個(gè)。這對(duì)中、小型作業(yè)來說，已可能把全部頁表項(xiàng)放入快表中；但對(duì)于大型作業(yè)來說，則只能將一部分頁表放入快表中。由于對(duì)程序和數(shù)據(jù)的訪問往往帶有局限性，所以快表的命中率可以達(dá)到80%～90%。例如，假設(shè)檢索聯(lián)想存儲(chǔ)器的時(shí)間為20ns，訪問內(nèi)存的時(shí)間為100ns，訪問聯(lián)想存儲(chǔ)器的的命中率為85%，則CPU存取一個(gè)數(shù)據(jù)的平均時(shí)間T=0.85*120+0.15*220=135ns，所以訪問時(shí)間只增加35%。如果不引入聯(lián)想存儲(chǔ)器，其訪問將延長(zhǎng)一倍（達(dá)200ns）。由于成本的原因，快表不可能做得很大，通常只能存放16~512具有快表的地址變換機(jī)構(gòu)

越界中斷

頁表寄存器

邏輯地址

頁號(hào)塊號(hào)

頁號(hào)塊號(hào)020141252

快表頁表物理地址

頁號(hào)頁內(nèi)地址頁表始址頁表長(zhǎng)度﹥

245塊號(hào)塊內(nèi)地址

輸入寄存器具有快表的地址變換機(jī)構(gòu)4.3.3兩級(jí)頁表機(jī)制80386的邏輯地址有232B，如頁面大小為4KB（212B），則頁表項(xiàng)達(dá)1M個(gè)，每個(gè)頁表項(xiàng)占用4B，故每個(gè)進(jìn)程的頁表占用4MB內(nèi)存空間，還要求是連續(xù)的，顯然這是不現(xiàn)實(shí)的。在80386中，為了減少頁表所占用的連續(xù)的內(nèi)存空間，采用了兩級(jí)頁表機(jī)制：基本方法是將頁表進(jìn)行分頁，每個(gè)頁面的大小與內(nèi)存物理塊的大小相同，并為它們進(jìn)行編號(hào)，可以離散地將各個(gè)頁面分別存放在不同的物理塊中，為此再建立一張頁表，稱為外層頁表（頁表目錄），即第一級(jí)頁表，其中的每個(gè)表目是存放某個(gè)頁表的物理地址。第二級(jí)才是頁表，其中的每個(gè)表目所存放的才是頁的物理塊號(hào)。4.3.3兩級(jí)頁表機(jī)制80386的邏輯地址有232B，如兩級(jí)頁表系統(tǒng)將32位邏輯地址空間的地址分成三段：其中，頁表目錄號(hào)（外層頁號(hào)p1）和頁號(hào)（外層頁內(nèi)地址p2）兩項(xiàng)各占10位，偏移量（頁內(nèi)地址d）占12位。每頁的大小為4KB。由于物理塊號(hào)和頁表的物理地址都占4個(gè)字節(jié)，使每頁中包含1024個(gè)頁表項(xiàng)，所以頁表目錄和頁表的大小也都是4KB，即一頁。在80386中設(shè)置了一個(gè)外層頁表寄存器（CR3），用于存放頁表目錄的基址。兩級(jí)頁表的邏輯地址結(jié)構(gòu)和兩級(jí)頁表的地址變換機(jī)構(gòu)圖如下：31222112110

外層頁表頁表物理地址

外層頁號(hào)p1外層頁內(nèi)地址p2頁內(nèi)地址d外層頁表寄存器++

bd兩級(jí)頁表系統(tǒng)將32位邏輯地址空間的地址分成三段：其中，頁表目?jī)杉?jí)頁表機(jī)制圖

第0頁頁表（物理塊號(hào)10）內(nèi)存010┇110232第1頁頁表（物理塊號(hào)25）