分頁存儲管理課件

4．3分頁管理

4.3.1

分頁管理的基本原理

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

3112110

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

51025＝32（頁）210＝1024（每頁1024字節(jié)）在分配存儲空間時,是以頁面為單位來分配.例如,一個作業(yè)的地址空間有M頁,那么只需要分配給他M個頁面的存儲空間,每一頁分別裝入一個存儲頁面即可.并不需要這些頁面是連續(xù)的.以上這些問題需要一個地址映射.頁號頁內(nèi)地址51025＝32（若給定一個邏輯地址空間中的地址為A，頁面大小為L，則頁號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若給定一個邏輯地址空間中的地址為A，頁面大小為L，則頁號P和3.頁表在將進(jìn)程的每一頁離散地分配到內(nèi)存的多個物理塊中后，系統(tǒng)應(yīng)能保證能在內(nèi)存中找到每個頁面所對應(yīng)的物理塊。為此，系統(tǒng)為每個進(jìn)程建立了一張頁面映射表，簡稱頁表（如下圖所示）。每個頁在頁表中占一個表項(xiàng)，記錄該頁在內(nèi)存中對應(yīng)的物理塊號。進(jìn)程在執(zhí)行時，通過查找頁表，就可以找到每頁所對應(yīng)的物理塊號?？梢?，頁表的作用是實(shí)現(xiàn)從頁號到物理塊號的地址映射。3.頁表

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

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

19183210

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

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

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

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

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

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

頁表寄存器

邏輯地址2500

頁號塊號

012

每頁1KB(1024)

頁號2頁內(nèi)地址452頁表始址頁表長度

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

越界中斷

頁表寄存器

邏輯地址2500

頁號塊號

012

每頁1KB(1024)

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

頁號2頁內(nèi)地址452頁表始址頁表長度﹥

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

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

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

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

越界中斷

頁表寄存器

邏輯地址

頁號塊號

頁號塊號020141252

快表頁表物理地址

頁號頁內(nèi)地址頁表始址頁表長度﹥

245塊號塊內(nèi)地址

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

外層頁表頁表物理地址

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

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

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

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

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

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

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

為了衡量一個調(diào)度算法的優(yōu)劣，先介紹幾個概念。為了簡單起見，假定一個作業(yè)分配的主存塊數(shù)固定不變，且采用局部淘汰(淘汰一頁時，只考慮本作業(yè)內(nèi)部實(shí)施淘汰)。假定作業(yè)Ji共有m頁，系統(tǒng)分配給它的主存塊為n塊，這里m>n。開始時，主存沒有裝入任何一頁的信息。如果作業(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。

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

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

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

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

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

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

從外存中找到缺頁

頁號>頁表長度？

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

該頁是否被修改？

將該頁寫回外存

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

修改頁表

CPU從外存讀缺頁

啟動I/O硬件

（2）頁面分配1.最少物理塊數(shù)在為進(jìn)程分配物理塊時，首先應(yīng)該考慮的問題是：能保證進(jìn)程能正常運(yùn)行所需的最少物理塊數(shù)（稱為最小物理塊數(shù)）。若系統(tǒng)為某進(jìn)程所分配的物理塊數(shù)少于此值時，進(jìn)程將無法運(yùn)行，這取決于指令的格式、功能和尋址方式。2.頁面的分配和置換策略在請求分頁系統(tǒng)中，可采取兩種分配策略——固定和可變分配策略。在進(jìn)行置換時，也可采取兩種策略——全局置換和局部置換。于是可組合成以下三種策略：固定分配局部置換策略：它基于進(jìn)程的類型（交互型或批處理型等），或根據(jù)程序員、系統(tǒng)管理員的建議，為每個進(jìn)程分配一固定頁數(shù)的內(nèi)存空間，在整個運(yùn)行期間都不再改變。如果進(jìn)程在運(yùn)行中發(fā)現(xiàn)缺頁，則只能從該進(jìn)程在內(nèi)存的固定頁面中選出一頁換出，然后再調(diào)入另一頁，保證分配給該進(jìn)程的內(nèi)存空間不變。（2）頁面分配1.最少物理塊數(shù)可變分配全局置換策略：系統(tǒng)為每個進(jìn)程分配一定數(shù)目的物理塊，而OS本身也保持一個空閑物理塊隊(duì)列。當(dāng)某進(jìn)程發(fā)現(xiàn)缺頁時，由系統(tǒng)從空閑物理塊隊(duì)列中，取出一物理塊分配給該進(jìn)程，并將欲調(diào)入的缺頁裝入其中。當(dāng)空閑物理塊隊(duì)列中的物理塊用完時，OS才能從內(nèi)存中選擇一頁調(diào)出，該頁可能是系統(tǒng)中任一進(jìn)程的頁?？勺兎峙渚植恐脫Q：根據(jù)進(jìn)程的類型或程序員的要求，為每個進(jìn)程分配一定數(shù)目的內(nèi)存空間；但當(dāng)某進(jìn)程發(fā)生缺頁時，只允許從該進(jìn)程在內(nèi)存的頁面中選出一頁換出，而不影響其它進(jìn)程的運(yùn)行?？勺兎峙淙种脫Q策略：系統(tǒng)為每個進(jìn)程分配一定數(shù)目的物理塊，而3．頁面分配算法在采用固定分配策略時，可采用以下幾種物理塊分配方法：平均分配算法：將系統(tǒng)中所有可供分配的物理塊，平均分配給各個進(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)入頁面的時機(jī)為了將進(jìn)程運(yùn)行時所缺的頁面調(diào)入內(nèi)存，可采取策略有：預(yù)調(diào)頁策略是一種主動的缺頁調(diào)入策略，即將那些預(yù)計(jì)在不久的將來會被訪問的程序或數(shù)據(jù)所在的頁面，預(yù)先調(diào)入內(nèi)存。由于預(yù)測的準(zhǔn)確率不高（50%），所以這種策略主要用于進(jìn)程的首次調(diào)入。有的系統(tǒng)將預(yù)調(diào)頁策略用于請求調(diào)頁，例如在VAX/VMS操作系統(tǒng)中，采用了一種稱為群頁式的調(diào)頁策略，當(dāng)系統(tǒng)將進(jìn)程所請求的頁面調(diào)入內(nèi)存時，也同時將其相鄰的幾個頁面調(diào)入內(nèi)存。請求調(diào)頁策略是指當(dāng)進(jìn)程在運(yùn)行中發(fā)生缺頁時，就立即提出請求，由系統(tǒng)將缺頁調(diào)入內(nèi)存。目前的虛擬存儲器中，大多采用此策略。但這種策略在調(diào)頁時須花費(fèi)較大的系統(tǒng)開銷，如需頻繁啟動磁盤I/O。(3)頁面調(diào)入策略為能使進(jìn)程運(yùn)行，必須事先將一部分要執(zhí)行2.從何處調(diào)入頁面在虛擬存儲系統(tǒng)中，外存（硬盤）常常被分成兩部分；文件區(qū)（用于存放文件）和對換區(qū)（用于存放對換頁面）。通常，對換區(qū)的磁盤I/O速度比文件區(qū)要高。每當(dāng)進(jìn)程發(fā)出缺頁請求時，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存呢？在UNIX系統(tǒng)中，對于從未運(yùn)行過的頁面，都應(yīng)從硬盤文件區(qū)調(diào)入；對于曾經(jīng)運(yùn)行過而又被換出的頁面，可以從對換區(qū)調(diào)入；對于共享頁面，該頁面可能已由其它進(jìn)程調(diào)入內(nèi)存，此時就無須再從對換區(qū)調(diào)入。2.從何處調(diào)入頁面（三）頁面置換算法

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

（三）頁面置換算法

（PageReplacementAl（1）最佳（Optimal）置換算法 它是一種理想化的算法，性能最好，但在實(shí)際上難于實(shí)現(xiàn)。即選擇那些永不使用的，或者是在最長時間內(nèi)不再被訪問的頁面置換出去。但是要確定哪一個頁面是未來最長時間內(nèi)不再被訪問的，目前來說是很難估計(jì)的，所以該算法通常用來評價其它算法。例：假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。如下圖所示，進(jìn)程運(yùn)行時先將7，0，1三個頁面裝入內(nèi)存。當(dāng)進(jìn)程訪問頁面2時，產(chǎn)生缺頁中斷，此時OS根據(jù)最佳置換算法，頁面7將在第18次才被訪問，是三頁中將最久不被訪問的頁面，所以被淘汰。接著訪問頁面0時，發(fā)現(xiàn)已在內(nèi)存中，而不會產(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)入主存儲器的那一頁。FIFO算法容易實(shí)現(xiàn)，但是它所依據(jù)的理由不是普遍成立的。哪些在內(nèi)存中駐留很久的頁，往往是被經(jīng)常訪問的頁，結(jié)果這些常用的頁都被淘汰調(diào)出，而可能又需要立即調(diào)回內(nèi)存。采用FIFO算法還會產(chǎn)生一種奇怪現(xiàn)象，直觀上，分配給的作業(yè)的實(shí)頁越多，進(jìn)程執(zhí)行時發(fā)生的缺頁中斷率就越小，但對FIFO算法這個結(jié)論并不是絕對的。在某些情況下，當(dāng)分配的頁面多反而導(dǎo)致更多的缺頁中斷，這種現(xiàn)象稱為FIFO異常現(xiàn)象或稱Belady現(xiàn)象。

4.7頁面置換算法所謂異?，F(xiàn)象，即在未給進(jìn)程或作業(yè)分配足它所要求的頁面數(shù)時，有時會出現(xiàn)分配的頁面數(shù)增多，缺頁次數(shù)反而增加的奇怪現(xiàn)象。所謂異?，F(xiàn)象，即在未給進(jìn)程或作業(yè)分配足它所要求的頁面數(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)在每個頁面設(shè)置一個訪問字段，用以記錄這個頁面自上次被訪問以來所經(jīng)歷的時間T，當(dāng)要淘汰一個頁面時，選擇T最大的頁面。但在實(shí)現(xiàn)時需要硬件的支持（寄存器或棧）。利用LRU算法對上例進(jìn)行頁面置換的結(jié)果如下：

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

LRU（Least

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

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

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

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

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

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

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

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

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

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

存儲保護(hù)

4．3分頁管理

4.3.1

分頁管理的基本原理

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

3112110

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

51025＝32（頁）210＝1024（每頁1024字節(jié)）在分配存儲空間時,是以頁面為單位來分配.例如,一個作業(yè)的地址空間有M頁,那么只需要分配給他M個頁面的存儲空間,每一頁分別裝入一個存儲頁面即可.并不需要這些頁面是連續(xù)的.以上這些問題需要一個地址映射.頁號頁內(nèi)地址51025＝32（若給定一個邏輯地址空間中的地址為A，頁面大小為L，則頁號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若給定一個邏輯地址空間中的地址為A，頁面大小為L，則頁號P和3.頁表在將進(jìn)程的每一頁離散地分配到內(nèi)存的多個物理塊中后，系統(tǒng)應(yīng)能保證能在內(nèi)存中找到每個頁面所對應(yīng)的物理塊。為此，系統(tǒng)為每個進(jìn)程建立了一張頁面映射表，簡稱頁表（如下圖所示）。每個頁在頁表中占一個表項(xiàng)，記錄該頁在內(nèi)存中對應(yīng)的物理塊號。進(jìn)程在執(zhí)行時，通過查找頁表，就可以找到每頁所對應(yīng)的物理塊號?？梢姡摫淼淖饔檬菍?shí)現(xiàn)從頁號到物理塊號的地址映射。3.頁表

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

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

19183210

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

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

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

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

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

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

頁表寄存器

邏輯地址2500

頁號塊號

012

每頁1KB(1024)

頁號2頁內(nèi)地址452頁表始址頁表長度

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

越界中斷

頁表寄存器

邏輯地址2500

頁號塊號

012

每頁1KB(1024)

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

頁號2頁內(nèi)地址452頁表始址頁表長度﹥

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

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

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

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

越界中斷

頁表寄存器

邏輯地址

頁號塊號

頁號塊號020141252

快表頁表物理地址

頁號頁內(nèi)地址頁表始址頁表長度﹥

245塊號塊內(nèi)地址

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

外層頁表頁表物理地址

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

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

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