第5章(2)虛存管理技術(shù)+

第五（2）章虛存管理技術(shù)5.1基本概念5.2頁(yè)式管理補(bǔ)充：多級(jí)頁(yè)表

十六進(jìn)制地址轉(zhuǎn)換時(shí)鐘(Clock)置換算法5.3段式管理5.4段頁(yè)式管理5.5局部性原理和抖動(dòng)問(wèn)題前面所述的各種管理技術(shù)統(tǒng)稱(chēng)為實(shí)存管理技術(shù)，其特點(diǎn)是在作業(yè)運(yùn)行時(shí)，必須將整個(gè)作業(yè)的邏輯地址空間全部裝入主存(除覆蓋外)，當(dāng)作業(yè)尺寸大于主存可用空間時(shí)，該作業(yè)就無(wú)法運(yùn)行。同實(shí)存相對(duì)的另一類(lèi)存儲(chǔ)管理技術(shù)稱(chēng)為虛存管理技術(shù)。同實(shí)存管理的主要區(qū)別是：不用將整個(gè)作業(yè)裝入主存就可以投入運(yùn)行。引入如下一些概念：

1.虛擬存儲(chǔ)器：是指一種實(shí)際上并不存在的虛假的存儲(chǔ)器。

2.虛擬地址：把一個(gè)運(yùn)行進(jìn)程訪(fǎng)問(wèn)的地址稱(chēng)為虛擬地址。5.1基本概念

3.實(shí)地址：把處理機(jī)可直接訪(fǎng)問(wèn)的地址稱(chēng)為實(shí)地址。相應(yīng)的有：虛地址空間、實(shí)地址空間的概念?！駟?wèn)題：

把虛地址空間和實(shí)地址空間分開(kāi)后，這樣虛地址空間可以遠(yuǎn)遠(yuǎn)大于實(shí)地址空間，亦即作業(yè)的大小可以遠(yuǎn)遠(yuǎn)大于主存空間的大小。另一個(gè)相關(guān)問(wèn)題是：作業(yè)運(yùn)行時(shí)，其整個(gè)虛地址空間(邏輯地址空間)是否必須全部裝入主存？如果必須的話(huà)，那么虛地址空間仍然不能大于實(shí)地址空間。一個(gè)程序的某次運(yùn)行，常有些部分是不用的(如：無(wú)錯(cuò)誤發(fā)生時(shí)就不會(huì)調(diào)用出錯(cuò)處理程序)。所以，只讓最近要用到的那部分程序和數(shù)據(jù)裝入主存，以后用到哪部分再把哪部分調(diào)入，而把不用部分調(diào)出(暫存外存)。為了完成上述功能，操作系統(tǒng)應(yīng)負(fù)責(zé)下面三個(gè)方面的任務(wù)：（1）把哪部分調(diào)入主存；（2）放在主存什么位置；（3）主存空間不足時(shí)，把哪部分淘汰出去。本章主要介紹目前廣泛使用的三種虛存管理技術(shù)：■頁(yè)式管理(靜態(tài)頁(yè)式管理和動(dòng)態(tài)頁(yè)式管理)■段式管理■段頁(yè)式存儲(chǔ)管理5.2頁(yè)式管理●

實(shí)現(xiàn)原理

1.等分主存把主存劃分成大小相同的存儲(chǔ)塊，稱(chēng)為頁(yè)面(或塊)，并給各頁(yè)面從零開(kāi)始編上序號(hào)：0，1，2，…。

2.等分作業(yè)的邏輯地址空間將程序的邏輯地址空間也劃分若干個(gè)與頁(yè)面大小相同的塊,稱(chēng)為頁(yè)。也編上序號(hào)0，1，2，…?！裰鞔娣峙湓瓌t系統(tǒng)以頁(yè)面(塊)為單位把主存分給作業(yè)，每頁(yè)對(duì)應(yīng)內(nèi)存中一個(gè)頁(yè)面，這些頁(yè)面可以是不相臨的或連續(xù)的。

●頁(yè)式存儲(chǔ)管理根據(jù)進(jìn)程的頁(yè)是否一次全部裝入還是部分裝入而分為：靜態(tài)頁(yè)式管理－實(shí)存管理動(dòng)態(tài)頁(yè)式管理－虛存管理一、靜態(tài)頁(yè)式管理基本原理：要求程序執(zhí)行前，分配其所需的所有頁(yè)面，這些頁(yè)面可以是不相鄰的。這意味著內(nèi)存中有足夠的空閑頁(yè)面才能執(zhí)行某個(gè)程序。需要CPU的硬件支持。

下面圖顯示靜態(tài)頁(yè)式內(nèi)存使用情況：靜態(tài)頁(yè)式管理主存分配情況FrameNumber0123456789101112131401234567891011121314A.0A.1A.2A.3

01234567891011121314A.0A.1A.2A.3B.0B.1B.2在頁(yè)式儲(chǔ)存管理中，是以頁(yè)面為單位分給用戶(hù)使用，為了記錄主存的使用情況，系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)頁(yè)表，最簡(jiǎn)單的頁(yè)表包括如下信息：（1）頁(yè)號(hào)：作業(yè)的各頁(yè)的頁(yè)號(hào)；（2）塊號(hào)：指該頁(yè)裝入主存的第幾個(gè)頁(yè)面上。1.頁(yè)表與頁(yè)表地址寄存器▲頁(yè)的大小帶來(lái)的影響頁(yè)?。簝?nèi)碎片小，頁(yè)表長(zhǎng)，管理復(fù)雜，存儲(chǔ)信息少，可能頻繁調(diào)頁(yè)；頁(yè)大：頁(yè)表短，管理開(kāi)銷(xiāo)小，交換時(shí)對(duì)外存I/O效率高，但內(nèi)碎片大，會(huì)多浪費(fèi)內(nèi)存LOAD1，1120

ADD1，24100100102100068021120200040006251241030000頁(yè)1頁(yè)2頁(yè)3頁(yè)0100020003000頁(yè)號(hào)塊號(hào)03192-3-02頁(yè)號(hào)塊號(hào)14270100020003000LOAD1，1120

ADD1，241031003102400050006000700010000900080002塊3塊4塊5塊6塊7塊8塊9塊0塊1塊91206802操作系統(tǒng)作業(yè)1作業(yè)2頁(yè)表2.靜態(tài)頁(yè)式管理的特點(diǎn)優(yōu)點(diǎn)：

■沒(méi)有外碎片，每個(gè)內(nèi)碎片不超過(guò)頁(yè)的大小■一個(gè)程序不必連續(xù)存放?！鲇捎陧?yè)的大小相等，內(nèi)存的分配、回收簡(jiǎn)單，易于管理。缺點(diǎn)：程序要求全部裝入內(nèi)存才能執(zhí)行。3.邏輯地址的表示用戶(hù)的邏輯地址一般是從基址“0”開(kāi)始連續(xù)編址。在分頁(yè)系統(tǒng)中，每個(gè)虛地址(相對(duì)地址)用一個(gè)數(shù)對(duì)(p，d)來(lái)表示，其中p表示頁(yè)號(hào)，d表示頁(yè)內(nèi)地址(頁(yè)內(nèi)偏移量)。令A(yù)是一個(gè)虛地址，頁(yè)面大小為L(zhǎng),則：

p=INT[A/L]，d=[A]modL

例如：設(shè)頁(yè)面大小L=1000字節(jié),A=3456,則:p=INT[3456/1000]=3L=[3456]mod1000=456在內(nèi)存中的表示：

若頁(yè)面大小為2的冪，邏輯地址轉(zhuǎn)換為頁(yè)號(hào)p和位移量d就非常簡(jiǎn)單(由地址變換機(jī)構(gòu)自動(dòng)完成)。頁(yè)號(hào)頁(yè)內(nèi)地址(頁(yè)內(nèi)偏移量)pd例如：一個(gè)頁(yè)長(zhǎng)為1K，擁有64頁(yè)的虛擬空間地址結(jié)構(gòu)如圖下圖所示。151090pd26=64(頁(yè))，頁(yè)的長(zhǎng)度=210=1024(字節(jié))=1K舉例：采用頁(yè)式存儲(chǔ)管理的系統(tǒng)中，若邏輯地址中的頁(yè)號(hào)用8位表示，頁(yè)內(nèi)地址用16位表示。問(wèn)：（1）用戶(hù)程序的最大長(zhǎng)度是多少兆字節(jié)？（2）主存分塊為多少K字節(jié)？（KB）解：邏輯地址中的頁(yè)號(hào)用8位表示，就是說(shuō)邏輯地址中最大頁(yè)數(shù)是28=256(頁(yè))；頁(yè)內(nèi)地址用16位表示，即一個(gè)(邏輯)頁(yè)大小為216=65536(字節(jié))/1024=64K。（1）用戶(hù)程序的最大長(zhǎng)度就是256頁(yè)全部使用的情況了，即256*64K=16384K=16384K/1024=16MB。（2）主存分塊大小應(yīng)該和邏輯頁(yè)大小相同，即頁(yè)面=64KB4.分頁(yè)管理中的地址轉(zhuǎn)換

靜態(tài)頁(yè)式管理的另一個(gè)關(guān)鍵問(wèn)題是地址變換。即怎樣由頁(yè)號(hào)和頁(yè)內(nèi)相對(duì)地址變換到內(nèi)存物理地址的問(wèn)題。在頁(yè)式管理中，地址變換的速度也是設(shè)計(jì)地址變換機(jī)構(gòu)時(shí)必須考慮的問(wèn)題之一。現(xiàn)以上圖的指令LOAD1,1120為例說(shuō)明分頁(yè)管理中的地址變換過(guò)程。當(dāng)CPU執(zhí)行LOAD1,1120時(shí)，該指令給出的虛地址為1120，首先由地址變換機(jī)構(gòu)自動(dòng)將該地址分為頁(yè)號(hào)p=1和位移量d=120，其轉(zhuǎn)換過(guò)程如下圖所示：頁(yè)號(hào)塊號(hào)03192-3-頁(yè)表長(zhǎng)度頁(yè)表起址112091209×1000+120912068023100LOAD1,120…頁(yè)式管理地址轉(zhuǎn)換示意圖pd控制寄存器內(nèi)存地址越界比較

注：

實(shí)際的地址轉(zhuǎn)換工作是計(jì)算機(jī)系統(tǒng)內(nèi)部采用硬件機(jī)制完成的，即由地址轉(zhuǎn)換機(jī)構(gòu)MMU(MemoryManagementUnit)自動(dòng)完成的，MMU是內(nèi)存管理單元的意思，它是由中央處理器CPU用來(lái)管理虛擬存儲(chǔ)器、物理存儲(chǔ)器的控制線(xiàn)路，同時(shí)也負(fù)責(zé)虛地址映射到物理地址的映射。1.虛地址以十進(jìn)制數(shù)給出頁(yè)號(hào)：P＝INT(虛地址/頁(yè)大小)——取整數(shù)部分位移量：W＝[虛地址]MOD頁(yè)大小或

W＝虛地址%頁(yè)大小——取余數(shù)根據(jù)題意產(chǎn)生頁(yè)表；以頁(yè)號(hào)查頁(yè)表，得到對(duì)應(yīng)頁(yè)裝入內(nèi)存的塊號(hào)計(jì)算機(jī)公式內(nèi)存地址＝塊號(hào)×頁(yè)大小＋位移量●頁(yè)式地址映射小結(jié)2.虛地址(邏輯地址、相對(duì)地址)以十六進(jìn)制、八進(jìn)制、二進(jìn)制的形式給出將虛地址轉(zhuǎn)換成二進(jìn)制的數(shù)；按頁(yè)的大小分離出頁(yè)號(hào)和位移量(高位部分是頁(yè)號(hào)，低位部分是位移量)；將低位部分——位移量直接復(fù)制到內(nèi)存地址寄存器的低位部分；根據(jù)頁(yè)號(hào)查頁(yè)表，得到該頁(yè)裝入內(nèi)存的物理塊號(hào)，并將塊號(hào)轉(zhuǎn)換成二進(jìn)制數(shù)填入地址寄存器的高位部分，從而形成內(nèi)存地址。十六進(jìn)制(參考)：0000=00001=10010=20011=30100=40101=50110=60111=71000=8

1001=91010=A1011=B1100=C1101=D1110=E1111=F記憶：210=1K211=2K212=4K213=8K214=16K215=32K216=64K….例1：有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁(yè)大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地址。解答:（1）虛地址7145P＝INT(7145/2048)＝3(對(duì)應(yīng)物理塊5)W＝[7145]mod2048＝1001MR=5*2048+1001=11241虛地址7145的內(nèi)存地址是：11241（2）虛地址3412P＝INT(3412/2048)＝1(對(duì)應(yīng)物理塊9)W＝[3412]mod2048＝1364MR=9*2048+1364=19796

虛地址3412的內(nèi)存地址是：19796例2：某虛擬存儲(chǔ)器的用戶(hù)空間共32個(gè)頁(yè)面，每頁(yè)1KB，主存16KB，假設(shè)某時(shí)刻系統(tǒng)為用戶(hù)的0、1、2、3頁(yè)分配的物理塊為5、10、4、7，而該用戶(hù)作業(yè)的長(zhǎng)度為6頁(yè)，試將十六進(jìn)制的虛地址0A5C、103C、1A5C轉(zhuǎn)換成物理地址。解答：用戶(hù)空間(邏輯地址空間)為32*1KB=32KB，因215=32KB，故邏輯地址編碼為15位，頁(yè)面為1KB(210KB)，所以頁(yè)號(hào)用5位，頁(yè)內(nèi)地址用10位。（1）0A5C0A5C=000101001011100P=2，W=1001011100

MR=001001001011100=125CH（2）103C103C=001000000111100P=4,W=0000111100

頁(yè)號(hào)為4，合法，但該頁(yè)未裝入主存，故產(chǎn)生缺頁(yè)中斷；（3）1A5C1A5C=001101001011100P=6，因該用戶(hù)作業(yè)的長(zhǎng)度為6頁(yè)(0~5)，故產(chǎn)生地址越界中斷。一道考研題西北工業(yè)大學(xué)（2002）設(shè)有8頁(yè)的邏輯空間，每頁(yè)有1024字節(jié)(1KB)，它們被映射到32塊的物理存儲(chǔ)區(qū)中，那么邏輯地址的有效位是（）位，物理地址至少是（）位。分析：邏輯地址有兩個(gè)部分組成：頁(yè)號(hào)和頁(yè)內(nèi)偏移地址。邏輯空間有8（23）頁(yè)，說(shuō)明頁(yè)號(hào)需要3位二進(jìn)制位編碼，而每頁(yè)有1024（210）字節(jié)，說(shuō)明頁(yè)內(nèi)偏移地址需要10位二進(jìn)制位編碼，因此邏輯地址的有效位為3+10=13位。因?yàn)槲锢淼刂放c邏輯地址的頁(yè)面大小相同，而物理存儲(chǔ)塊為32（25）占5位，所以物理地址至少為5+10=15位內(nèi)存有32個(gè)物理塊，物理塊大小與邏輯塊大小相同，故物理地址空間為32*1KB=32KB。因?yàn)?15=32768B=32768/1024=32KB，故物理地址至少為15位。4.聯(lián)想寄存器和快表聯(lián)想寄存器：可按內(nèi)容并行查找的快速寄存器。比內(nèi)存貴、容量小。引入原因：頁(yè)表駐留內(nèi)存，執(zhí)行訪(fǎng)內(nèi)指令要先到內(nèi)存查頁(yè)表，進(jìn)行地址轉(zhuǎn)換后才能進(jìn)行訪(fǎng)內(nèi)操作，因此執(zhí)行一條指令至少要訪(fǎng)問(wèn)內(nèi)存兩次為提高速度，將內(nèi)存頁(yè)表(也稱(chēng)慢表)中一部分經(jīng)常使用頁(yè)的頁(yè)號(hào)和頁(yè)面號(hào)等內(nèi)容放在聯(lián)想寄存器中(稱(chēng)為快表)。■具有快表的地址轉(zhuǎn)換：每次訪(fǎng)問(wèn)主存時(shí)，首先查找快表，若找到所需的頁(yè)，則快速形成物理地址。否則從頁(yè)表(慢表)中查找后形成物理地址，同時(shí)把該頁(yè)寫(xiě)入快表中。如果設(shè)計(jì)得當(dāng)，快表的命中率可以很高。具有快表的地址變換機(jī)構(gòu)頁(yè)表寄存器頁(yè)表始址頁(yè)表長(zhǎng)度＞頁(yè)號(hào)頁(yè)內(nèi)地址＋邏輯地址L越界中斷塊號(hào)b頁(yè)表頁(yè)號(hào)頁(yè)號(hào)輸入寄存器塊號(hào)bb快表d物理地址這就意味著，在為一個(gè)進(jìn)程分配內(nèi)存空間時(shí)，除了給進(jìn)程本身分配內(nèi)存空間外，還需要另外提供4MB的一塊連續(xù)內(nèi)存空間存放對(duì)應(yīng)的頁(yè)表。因?yàn)槊總€(gè)進(jìn)程都要有自己的頁(yè)表，這就需要更大存儲(chǔ)空間來(lái)存放頁(yè)表。5.兩級(jí)和多級(jí)頁(yè)表補(bǔ)充

CPU具有32位地址時(shí)，使用232邏輯地址空間的分頁(yè)系統(tǒng)，規(guī)定頁(yè)面4KB時(shí)，每個(gè)進(jìn)程頁(yè)表的表項(xiàng)最多有1M個(gè)，即頁(yè)表最多有1M行（？），若每個(gè)頁(yè)表項(xiàng)占用4個(gè)字節(jié)，則每個(gè)進(jìn)程需要占用4MB連續(xù)內(nèi)存空間存放頁(yè)表(即需要1024個(gè)連續(xù)的內(nèi)存物理塊)。

解釋?zhuān)喉?yè)面大小為4KB(212KB)，故頁(yè)內(nèi)編址12位，頁(yè)號(hào)編址為:32–12=20位，220=1048576(個(gè))=1048576/1024=1024K(個(gè))=1M(個(gè)),所以共有1M個(gè)頁(yè)表項(xiàng)。每個(gè)頁(yè)表項(xiàng)占4個(gè)字節(jié)，故：1048576*4=4194304B=4096KB=4MB

可以采用兩種方法來(lái)解決頁(yè)表存放問(wèn)題：①采用離散分配方式來(lái)解決難以找到一塊連續(xù)的內(nèi)存空間的問(wèn)題;②只將當(dāng)前需要的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存，其余的頁(yè)表項(xiàng)駐留在磁盤(pán)上，需要時(shí)再調(diào)入。采用此方法解決1）兩級(jí)頁(yè)表(Two-LevelPageTable)兩級(jí)頁(yè)表機(jī)制的做法是：■把整個(gè)頁(yè)表進(jìn)行分頁(yè)，即將整個(gè)頁(yè)表拆分成一張張小頁(yè)表(稱(chēng)為頁(yè)表頁(yè)),小頁(yè)表的大小與頁(yè)框大小相同，然后再為這些小頁(yè)表再建一張表，稱(chēng)為外層頁(yè)表(也稱(chēng)頁(yè)目錄表)，外層頁(yè)表存放每個(gè)小頁(yè)表對(duì)應(yīng)的內(nèi)存物理塊號(hào)。1011107801217421023第0頁(yè)頁(yè)表146…012…1023第1頁(yè)頁(yè)表11411501…102301234567……1141151468第1023頁(yè)頁(yè)表1468012…1023內(nèi)存空間兩級(jí)頁(yè)表結(jié)構(gòu)一個(gè)內(nèi)存物理塊為1KB。本例將頁(yè)表拆分成1024個(gè)小頁(yè)表。頁(yè)目錄表由上圖可知，在頁(yè)表的每個(gè)表項(xiàng)中存放的是進(jìn)程的某頁(yè)在內(nèi)存的物理塊號(hào)，如第0頁(yè)存放在第1個(gè)物理塊中，第1頁(yè)存放在第4個(gè)物理塊中。而在外層頁(yè)表的每個(gè)表項(xiàng)中，所存放的是某頁(yè)表分頁(yè)的首址，如第0號(hào)小頁(yè)表是存放在第1011物理塊中，第1號(hào)小頁(yè)表是存放在第1078物理塊中等。在兩級(jí)頁(yè)表時(shí)，指令所給出的地址分為三部分：（外層頁(yè)號(hào)，外層頁(yè)內(nèi)地址，頁(yè)內(nèi)地址）邏輯地址結(jié)構(gòu)可描述如下(上述例子的邏輯地址結(jié)構(gòu))：1）外層頁(yè)號(hào)用10位，210=1024B(將頁(yè)表拆分為1024個(gè)小頁(yè))2）外層頁(yè)內(nèi)地址用10位，210=1024B（每個(gè)小頁(yè)表為1024B）3）頁(yè)內(nèi)地址用12位，

212=4096B=4KB具有兩級(jí)頁(yè)表的地址變換機(jī)構(gòu)頁(yè)目錄號(hào)頁(yè)號(hào)頁(yè)內(nèi)地址p1p2d邏輯地址+外部頁(yè)表寄存器頁(yè)目錄號(hào)+db頁(yè)表物理地址……b二級(jí)頁(yè)表地址變換需三次訪(fǎng)問(wèn)主存：一次訪(fǎng)問(wèn)頁(yè)目錄、一次訪(fǎng)問(wèn)頁(yè)表頁(yè)、一次訪(fǎng)問(wèn)指令或數(shù)據(jù)。虛擬地址二級(jí)頁(yè)表結(jié)構(gòu)及地址映射頁(yè)表地址…..頁(yè)目錄(每進(jìn)程一個(gè))塊號(hào)….頁(yè)表代碼或數(shù)據(jù)…..內(nèi)存塊++頁(yè)目錄地址外層頁(yè)號(hào)頁(yè)表位移頁(yè)位移2)多級(jí)頁(yè)表（略）

①對(duì)于32位的機(jī)器，采用兩級(jí)頁(yè)表結(jié)構(gòu)是合適的；

②對(duì)于64位的機(jī)器，如果頁(yè)面大小仍采用4KB(即212KB)，那么還剩下52位，假定仍按物理塊的大小(212位)來(lái)劃分頁(yè)表，則將余下的42位用于頁(yè)號(hào)。此時(shí)在頁(yè)表中可能有4096G個(gè)頁(yè)表項(xiàng)(242=4096G)，要占用16384GB的連續(xù)內(nèi)存空間。

必須采用多級(jí)頁(yè)表，將頁(yè)目錄號(hào)表表再為頁(yè)目錄號(hào)表，也是將各分頁(yè)離散地裝入到不相鄰接的物理塊中，再利用第2級(jí)的外層頁(yè)表來(lái)映射它們之間的關(guān)系。一道考研題（東南大學(xué)2001)判斷題：虛擬存儲(chǔ)器是一個(gè)虛假的地址空間，因而這個(gè)地址空間的大小是沒(méi)有限制的（）分析：在虛擬存儲(chǔ)器中，用戶(hù)的地址空間仍然受到地址字長(zhǎng)和外存容量的限制。虛擬存儲(chǔ)器的最大容量受地址長(zhǎng)度（地址總線(xiàn)位數(shù)）決定，一個(gè)擁有32位地址長(zhǎng)度的系統(tǒng)，其虛擬內(nèi)存最大為232字節(jié)。當(dāng)然，一個(gè)實(shí)際的虛擬存儲(chǔ)器的大小還會(huì)受到輔助存儲(chǔ)器大小的限制。答案錯(cuò)選擇題一個(gè)計(jì)算機(jī)系統(tǒng)的虛擬存儲(chǔ)器的最大容量是由（Ａ）確定的，其實(shí)際容量是由（B）確定的。A、Ｂ：①計(jì)算機(jī)字長(zhǎng)；②內(nèi)存容量；③硬盤(pán)容量；④內(nèi)存和硬盤(pán)容量之和；⑤計(jì)算機(jī)的地址結(jié)構(gòu)。答案：⑤、④2010考研題：某計(jì)算機(jī)采用二級(jí)頁(yè)表的分頁(yè)存儲(chǔ)管理方式，按字節(jié)編址，頁(yè)大小為210字節(jié)（1K），頁(yè)表項(xiàng)大小為2字節(jié)，邏輯地址結(jié)構(gòu)為：,邏輯地址空間大小為216頁(yè)，則表示整個(gè)邏輯地址空間的頁(yè)目錄表中包含表項(xiàng)的個(gè)數(shù)至少是

A.64

B.128

C.256D.512解：邏輯地址空間為216頁(yè)，頁(yè)表項(xiàng)為2個(gè)字節(jié)，故頁(yè)表長(zhǎng)度為

216×2=128KB，一個(gè)內(nèi)存物理塊存放1KB，故

128KB/1KB=128，即得頁(yè)目錄表(外層頁(yè)表)至少包含

128個(gè)表項(xiàng)。

頁(yè)目錄號(hào)頁(yè)號(hào)頁(yè)內(nèi)偏移量6.信息的共享和保護(hù)信息共享：允許進(jìn)程的地址空間在內(nèi)存中非連續(xù)存放，使得多個(gè)進(jìn)程可共享某些頁(yè)面。但共享代碼頁(yè)面受限制。為什么？信息保護(hù)：進(jìn)行地址轉(zhuǎn)換時(shí)，檢查是否超頁(yè)（邏輯頁(yè)和頁(yè)表控制寄存器中頁(yè)表長(zhǎng)度相比)；在頁(yè)表中設(shè)置存取權(quán)限項(xiàng)。7.存儲(chǔ)頁(yè)面表存儲(chǔ)頁(yè)面表是整個(gè)系統(tǒng)的一張表，存儲(chǔ)頁(yè)面表指出內(nèi)存各頁(yè)面是否已被分配出去,以及未分配頁(yè)面的總數(shù)。存儲(chǔ)頁(yè)面表也有兩種構(gòu)成方法。（1）位示圖一種是在內(nèi)存中劃分一塊固定區(qū)域，每個(gè)單元的每個(gè)比特代表一個(gè)頁(yè)面。如果該頁(yè)面已被分配，則對(duì)應(yīng)比特位置1，否則置0。這種方法稱(chēng)為位示圖法。如下圖所示。位示圖（2）空閑頁(yè)面鏈存儲(chǔ)頁(yè)面表的另一種構(gòu)成辦法是采用空閑頁(yè)面鏈的方法。在空閑頁(yè)面鏈中，隊(duì)首頁(yè)面的第一個(gè)單元和第二個(gè)單元分別放入空閑頁(yè)面總數(shù)與指向下一個(gè)空閑頁(yè)面的指針。其他頁(yè)面的第一個(gè)單元中則分別放入指向下一個(gè)頁(yè)面的指針?？臻e頁(yè)面鏈的方法由于使用了空閑頁(yè)面本身的單元存放指針，因此不占據(jù)額外的內(nèi)存空間。二、動(dòng)態(tài)頁(yè)式管理1.引入原因

在靜態(tài)頁(yè)式存儲(chǔ)管理中，要求把進(jìn)程地址空間的全部頁(yè)都要裝入內(nèi)存才能運(yùn)行。而在實(shí)際中一個(gè)作業(yè)的某些部分可能在運(yùn)行過(guò)程中是用不到的，比如：如果沒(méi)有錯(cuò)誤的發(fā)生，錯(cuò)誤處理模塊就不會(huì)被調(diào)用。因此，在靜態(tài)頁(yè)式管理中會(huì)將一些不需要的頁(yè)也裝入內(nèi)存,而且內(nèi)存資源不足時(shí),該作業(yè)或進(jìn)程將無(wú)法運(yùn)行。2.動(dòng)態(tài)頁(yè)式管理的主要思想:

在作業(yè)或進(jìn)程開(kāi)始運(yùn)行前，只將被認(rèn)為是經(jīng)常被反復(fù)執(zhí)行和調(diào)用的部分裝入內(nèi)存，而其它部分在執(zhí)行過(guò)程中動(dòng)態(tài)的調(diào)入。即：通過(guò)交換的技術(shù)以小的內(nèi)存運(yùn)行大的作業(yè)。3.有兩種動(dòng)態(tài)裝入方式

(1)

請(qǐng)求頁(yè)式管理當(dāng)發(fā)現(xiàn)欲執(zhí)行的某條指令或數(shù)據(jù)不在內(nèi)存時(shí)，發(fā)生缺頁(yè)中斷，由系統(tǒng)將外存的頁(yè)面調(diào)入內(nèi)存(軟件實(shí)現(xiàn))。

(2)

預(yù)調(diào)入方管理系統(tǒng)對(duì)那些在外存中的頁(yè)進(jìn)行調(diào)入順序計(jì)算，估計(jì)出這些頁(yè)中指令和數(shù)據(jù)的執(zhí)行和被訪(fǎng)問(wèn)的順序，并按此順序事先將它們順序調(diào)入和調(diào)出內(nèi)存。4.請(qǐng)求頁(yè)式管理需要解決的問(wèn)題

(1)

如何發(fā)現(xiàn)頁(yè)是否在內(nèi)存可以用擴(kuò)充頁(yè)表的方法解決，即除了頁(yè)號(hào)、頁(yè)面號(hào)外，再增加該頁(yè)是否在內(nèi)存的標(biāo)志位及該頁(yè)在外存的起始地址。擴(kuò)充后的頁(yè)表如下：頁(yè)號(hào)頁(yè)面號(hào)標(biāo)志位

外存始址

08Y

120Y

2-N

3-N

(2)如何處理缺頁(yè)問(wèn)題關(guān)于某頁(yè)不在內(nèi)存時(shí)的處理涉及兩個(gè)問(wèn)題：①采用何種方法把所缺的頁(yè)調(diào)入內(nèi)存；②如果內(nèi)存沒(méi)有空閑頁(yè)面，把調(diào)進(jìn)來(lái)的頁(yè)放在什么地方(如何淘汰頁(yè)的問(wèn)題)。采用什么策略淘汰頁(yè)(后面詳細(xì)講)如果內(nèi)存中的某頁(yè)被淘汰，有兩種情況：其一是該頁(yè)在程序運(yùn)行時(shí)被修改過(guò)；其二是沒(méi)被修改。如果被修改過(guò)，淘汰時(shí)應(yīng)重新寫(xiě)到外存，若未修改，則不必重新入外存(因外存已有副本)。問(wèn)題：如何知道被淘汰的頁(yè)是否被修改過(guò)？

可在頁(yè)表中再增加一項(xiàng)，以記錄該頁(yè)是否被修改過(guò)。增加后的頁(yè)表如下：頁(yè)號(hào)頁(yè)面號(hào)標(biāo)志位改變位

外存始址

修改位5.請(qǐng)求頁(yè)式管理中的置換算法

置換算法在內(nèi)存中沒(méi)有空閑頁(yè)面時(shí)被調(diào)用。它的目的是選出一個(gè)被淘汰的頁(yè)面。如果內(nèi)存中有足夠的空閑頁(yè)面存放所調(diào)入的頁(yè)，則不必使用置換算法。把內(nèi)存和外存統(tǒng)一管理的真正目的是把那些被訪(fǎng)問(wèn)概率非常高的頁(yè)存放在內(nèi)存中。因此，置換算法應(yīng)該置換那些被訪(fǎng)問(wèn)概率最低的頁(yè)，將它們移出內(nèi)存。比較常用的置換算法有以下幾種:

(1)

隨機(jī)淘汰算法(RG)

在系統(tǒng)無(wú)法確定哪些頁(yè)被訪(fǎng)問(wèn)的概率較低時(shí)，隨機(jī)地選擇某個(gè)用戶(hù)的頁(yè)面并將其換出。(2)輪轉(zhuǎn)法(RR)

循回?fù)Q出內(nèi)存可用區(qū)內(nèi)一個(gè)可以被換出的頁(yè)面，無(wú)論該頁(yè)是否剛被換進(jìn)或以換進(jìn)很長(zhǎng)時(shí)間。(3)先進(jìn)先出(FIFO)

總是選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的一頁(yè)被換出。FIFO算法認(rèn)為先調(diào)入內(nèi)存的頁(yè)不再被訪(fǎng)問(wèn)的可能性大，因此選擇最先調(diào)入的換出。事實(shí)上，那些在內(nèi)存中停留時(shí)間最長(zhǎng)的頁(yè)往往也是經(jīng)常被訪(fǎng)問(wèn)的頁(yè)。假設(shè)某作業(yè)有5個(gè)頁(yè)面，執(zhí)行時(shí)引用的頁(yè)序列為：0、1、2、3、0、1、4、0、1、2、3、4共訪(fǎng)問(wèn)12個(gè)頁(yè)面，當(dāng)系統(tǒng)給該進(jìn)程3個(gè)內(nèi)存塊時(shí)，F(xiàn)IFO發(fā)生9次缺頁(yè)中斷：(4)最佳算法(OPT)

選擇以后不再訪(fǎng)問(wèn)的頁(yè)或經(jīng)很長(zhǎng)時(shí)間之后才可能訪(fǎng)問(wèn)的頁(yè)進(jìn)行淘汰。

例如：如果一個(gè)進(jìn)程對(duì)頁(yè)面的訪(fǎng)問(wèn)序列為：0、1、2、3、0、1、4、0、1、2、3、4，系統(tǒng)給該進(jìn)程3個(gè)物理頁(yè)塊，則按照最佳置換算法，會(huì)產(chǎn)生7次缺頁(yè)中斷，缺頁(yè)中斷率為f=7/12?！帘硎救表?yè)中斷，√表示無(wú)缺頁(yè)中斷?！痢痢痢痢痢痢痢獭獭獭獭蹋?）最近最久未使用的頁(yè)面置換算法(LRU)

該算法的基本思想是:

當(dāng)需要淘汰某一頁(yè)時(shí)，選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒(méi)有使用過(guò)的頁(yè)先淘汰。該算法的主要出發(fā)點(diǎn)是，如果某頁(yè)被訪(fǎng)問(wèn)了，則它可能馬上還要被訪(fǎng)問(wèn)?；蛘叻催^(guò)來(lái)說(shuō)，如果某頁(yè)很長(zhǎng)時(shí)間未被訪(fǎng)問(wèn)，則它在最近一段時(shí)間也不會(huì)被訪(fǎng)問(wèn)。

要完全實(shí)現(xiàn)LRU算法是十分困難的。因?yàn)橐页鲎罱罹梦幢皇褂玫捻?yè)面的話(huà)，就必須對(duì)每一個(gè)頁(yè)面都設(shè)置有關(guān)的訪(fǎng)問(wèn)記錄項(xiàng)，而且每一次訪(fǎng)問(wèn)都必須更新這些記錄。這顯然要花費(fèi)巨大的系統(tǒng)開(kāi)銷(xiāo)。因此，在實(shí)際系統(tǒng)中往往使用LRU的近似算法。LRU頁(yè)面置換算法舉例：例如：進(jìn)程P有5個(gè)頁(yè)，進(jìn)程訪(fǎng)問(wèn)頁(yè)的順序?yàn)椋?，3，2，1，4，3，5，4，3，2，1，5；如果在內(nèi)存中分配給該進(jìn)程3個(gè)頁(yè)面，則缺頁(yè)情況如下：頁(yè)面432143543215頁(yè)面1432143543215頁(yè)面243214354321頁(yè)面34321435432缺頁(yè)×××××××√√×××缺頁(yè)中斷次數(shù)：10次缺頁(yè)率=(10/12)*100%=83.3%頁(yè)面淘汰順序：

4，3，2，1，5，4，3LRU有兩個(gè)近似算法最不經(jīng)常使用的頁(yè)面淘汰算法(LFU)1）最不經(jīng)常使用頁(yè)面淘汰算法LFU(leastfrequentlyused)

該算法在需要淘汰某一頁(yè)時(shí)，首先淘汰到當(dāng)前時(shí)間為止，被訪(fǎng)問(wèn)次數(shù)最少的那一頁(yè)。這只要在頁(yè)表中給每一頁(yè)增設(shè)一個(gè)訪(fǎng)問(wèn)計(jì)數(shù)器即可實(shí)現(xiàn)。每當(dāng)該頁(yè)被訪(fǎng)問(wèn)時(shí)，訪(fǎng)問(wèn)計(jì)數(shù)器加1，而發(fā)生一次缺頁(yè)中斷時(shí)，則淘汰計(jì)數(shù)值最小的那一頁(yè)，并將所有的計(jì)數(shù)器清零。最近沒(méi)使用的頁(yè)面淘汰算法(NUR)2）最近沒(méi)有使用頁(yè)面淘汰算法NUR

該算法在需要淘汰某一頁(yè)時(shí)，從那些最近一個(gè)時(shí)期內(nèi)未被訪(fǎng)問(wèn)的頁(yè)中任選一頁(yè)淘汰。只要在頁(yè)表中增設(shè)一個(gè)訪(fǎng)問(wèn)位即可實(shí)現(xiàn)。當(dāng)某頁(yè)被訪(fǎng)問(wèn)時(shí)，訪(fǎng)問(wèn)位置1。否則，訪(fǎng)問(wèn)位置0。系統(tǒng)周期性地對(duì)所有引用位清零。當(dāng)需淘汰一頁(yè)時(shí)，從那些訪(fǎng)問(wèn)位為零的頁(yè)中選一頁(yè)進(jìn)行淘汰。（6）Clock置換算法(時(shí)鐘置換算法)1）簡(jiǎn)單的Clock置換算法①為每頁(yè)設(shè)置一位訪(fǎng)問(wèn)位，當(dāng)淘汰一個(gè)頁(yè)面時(shí)，如果指針指向頁(yè)面的訪(fǎng)問(wèn)位R為0，就將其淘汰，并把新的頁(yè)面插入這個(gè)位置，指針向前移動(dòng)一個(gè)位置；②如果訪(fǎng)問(wèn)位R為1，就清除R位(置0)，并把指針前移一個(gè)位置，直到找到一個(gè)R位為0的頁(yè)面為止。

由訪(fǎng)問(wèn)位R和修改位M可以組合成下面四種類(lèi)型的頁(yè)面：

1類(lèi)(R=0,M=0):

表示該頁(yè)最近既未被訪(fǎng)問(wèn)，又未被修改，是最佳淘汰頁(yè)。

2類(lèi)(R=0,M=1)：表示該頁(yè)最近未被訪(fǎng)問(wèn)，但已被修改，并不是很好的淘汰頁(yè)。

3類(lèi)(R=1,M=0)：最近已被訪(fǎng)問(wèn)，但未被修改，該頁(yè)有可能再被訪(fǎng)問(wèn)。

4類(lèi)(R=1,M=1):

最近已被訪(fǎng)問(wèn)且被修改，該頁(yè)可能再被訪(fǎng)問(wèn)。2.改進(jìn)型Clock置換算法

其執(zhí)行過(guò)程可分成以下三步：

(1)從指針?biāo)甘镜漠?dāng)前位置開(kāi)始，掃描循環(huán)隊(duì)列，尋找R=0且M=0的第一類(lèi)頁(yè)面，將所遇到的第一個(gè)頁(yè)面作為所選中的淘汰頁(yè)。在第一次掃描期間不改變?cè)L問(wèn)位A。

(2)如果第一步失敗，則開(kāi)始第二輪掃描，尋找R=0且M=1的第二類(lèi)頁(yè)面，將所遇到的第一個(gè)這類(lèi)頁(yè)面作為淘汰頁(yè)。在第二輪掃描期間，將所有掃描過(guò)的頁(yè)面的訪(fǎng)問(wèn)位R都置為0。

(3)如果第二步也失敗，則將指針?lè)祷氐介_(kāi)始的位置，并將所有的訪(fǎng)問(wèn)位R置為0。然后重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁(yè)。6.Belady現(xiàn)象(異?，F(xiàn)象)Belady現(xiàn)象：先進(jìn)先出算法的一個(gè)缺點(diǎn)是它有一種陷阱現(xiàn)象。一般來(lái)說(shuō)，對(duì)于任何一作業(yè)或進(jìn)程，如果給它分配的內(nèi)存頁(yè)面數(shù)越接近于它所要求的頁(yè)面數(shù)，則發(fā)生缺頁(yè)的次數(shù)會(huì)越少。在極限情況下，這個(gè)推論是成立的。因?yàn)槿绻o一個(gè)進(jìn)程分配了它所要求的全部頁(yè)面，則不會(huì)發(fā)生缺頁(yè)現(xiàn)象。但是，使用FIFO算法時(shí)，在未給進(jìn)程或作業(yè)分配足夠的頁(yè)面數(shù)時(shí)，有時(shí)會(huì)出現(xiàn)分配的頁(yè)面數(shù)增多，缺頁(yè)次數(shù)反而增加的奇怪現(xiàn)象。這種現(xiàn)象稱(chēng)為Belady現(xiàn)象。如下圖所示。Belady現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪(fǎng)問(wèn)內(nèi)存的動(dòng)態(tài)特征是矛盾的，即被置換的頁(yè)面并不是進(jìn)程不會(huì)訪(fǎng)問(wèn)的。FIFO算法的Belady現(xiàn)象7.Belady現(xiàn)象舉例

例1：進(jìn)程P有5頁(yè)程序訪(fǎng)問(wèn)頁(yè)的順序?yàn)椋?,2,3,4,1,2,5,1,2,3,4,5；如果在內(nèi)存中分配3個(gè)頁(yè)面，則缺頁(yè)情況如下:×表示缺頁(yè)中斷，√表示無(wú)缺頁(yè)中斷。FIFO

1

2

3

4

1

2

5

1

2

3

4

5

頁(yè)0

1

2

3

4

1

2

5

5

5

3

4

4

頁(yè)1

1

2

3

4

1

2

2

2

5

3

3

頁(yè)2

1

2

3

4

1

1

1

2

5

5

缺頁(yè)

×

×

×

×

×

×

×

√

√

×

×

√

(12次訪(fǎng)問(wèn)中產(chǎn)生9次缺頁(yè)中斷)例2：進(jìn)程P有5頁(yè)程序訪(fǎng)問(wèn)頁(yè)的順序?yàn)椋?,2,3,4,1,2,5,1,2,3,4,5；如果在內(nèi)存中分配4個(gè)頁(yè)面，則缺頁(yè)情況如下:×表示缺頁(yè)中斷，√表示無(wú)缺頁(yè)中斷。(12次訪(fǎng)問(wèn)中產(chǎn)生10次缺頁(yè)中斷)8.抖動(dòng)(Thrashing)現(xiàn)象在請(qǐng)求式頁(yè)式管理中，在作業(yè)或進(jìn)程運(yùn)行過(guò)程中，當(dāng)發(fā)現(xiàn)欲訪(fǎng)問(wèn)的頁(yè)不在內(nèi)存時(shí)，將產(chǎn)生缺頁(yè)中斷，分兩種情況：

（1）如果主存中有空閑頁(yè)面，則將所缺的頁(yè)調(diào)入主存即可

(換入)。（2）如果主存中沒(méi)有空閑的頁(yè)面，則將調(diào)用置換算法將主存的某一個(gè)頁(yè)面淘汰出去(換出)。如果置換算法選擇不當(dāng)，有可能會(huì)產(chǎn)生剛被換出內(nèi)存的頁(yè)又要馬上被換入內(nèi)存，而換入內(nèi)存不久又馬上被換出，如此反復(fù)將使整個(gè)系統(tǒng)的頁(yè)面調(diào)度非常頻繁，以致大部分時(shí)間都花費(fèi)在主存和輔存之間來(lái)回?fù)Q入和換出上，這種現(xiàn)象稱(chēng)為抖動(dòng)現(xiàn)象。

綜上所述，頁(yè)式管理具有如下優(yōu)點(diǎn):

(1)由于它不要求作業(yè)或進(jìn)程的程序段和數(shù)據(jù)在內(nèi)存中連續(xù)存放，從而有效地解決了碎片問(wèn)題。

(2)動(dòng)態(tài)頁(yè)式管理提供了內(nèi)存和外存統(tǒng)一管理的虛存實(shí)現(xiàn)方式，使用戶(hù)可以利用的存儲(chǔ)空間大大增加。這既提高了主存的利用率，又有利于組織多道程序執(zhí)行。

9.頁(yè)式管理的優(yōu)缺點(diǎn)其主要缺點(diǎn)是:(1)要求有相應(yīng)的硬件支持。例如地址變換機(jī)構(gòu)，缺頁(yè)中斷的產(chǎn)生和選擇淘汰頁(yè)面等都要求有相應(yīng)的硬件支持。這增加了機(jī)器成本。(2)增加了系統(tǒng)開(kāi)銷(xiāo)，例如缺頁(yè)中斷處理等。(3)在請(qǐng)求頁(yè)式管理中，如果置換算法選擇不當(dāng)，有可能產(chǎn)生抖動(dòng)現(xiàn)象。(4)雖然消除了碎片，但每個(gè)作業(yè)或進(jìn)程的最后一頁(yè)內(nèi)總有一部分空間得不到利用。如果頁(yè)面較大，則這一部分的損失仍然較大。詳解抖動(dòng)：這個(gè)內(nèi)存要求的臨界值被稱(chēng)為工作集。圖5.35說(shuō)明這種情況。圖5.35內(nèi)存與交換次數(shù)的關(guān)系可以利用統(tǒng)計(jì)模型進(jìn)一步分析工作集與抖動(dòng)之間的關(guān)系。設(shè)r為CPU在內(nèi)存中存取一個(gè)內(nèi)存單元的時(shí)間t為從外存中讀出一頁(yè)數(shù)據(jù)所需時(shí)間p(s)為CPU訪(fǎng)問(wèn)內(nèi)存時(shí)（即r時(shí)間內(nèi)），所訪(fǎng)問(wèn)的頁(yè)正好不在內(nèi)存的概率，這里s是當(dāng)前進(jìn)程在內(nèi)存中的工作集。在虛存情況下存取一個(gè)內(nèi)存單元的平均時(shí)間可描述為T(mén)=r+p(s)*t由程序模擬可知，p(s)=ae-bs這里，0<a<1<b，ae-bs<<r假定內(nèi)存中各并發(fā)進(jìn)程具有相同的統(tǒng)計(jì)特性，而且對(duì)于一個(gè)并發(fā)進(jìn)程來(lái)說(shuō)，只有發(fā)生缺頁(yè)時(shí)才變成等待狀態(tài)。

由于訪(fǎng)問(wèn)外存一個(gè)頁(yè)面的時(shí)間為t，且缺頁(yè)發(fā)生的概率為p(s)，則在處理機(jī)訪(fǎng)問(wèn)一個(gè)內(nèi)存單元的r時(shí)間內(nèi)，平均每秒引起的內(nèi)外存之間頁(yè)傳送率為p(s)/r。也就是每r/p(s)秒需要從外存向內(nèi)存?zhèn)魉鸵豁?yè)。(根據(jù)內(nèi)存的讀取時(shí)間和缺頁(yè)概率來(lái)研究外存)對(duì)于一個(gè)在虛存范圍內(nèi)執(zhí)行的進(jìn)程，它可以處于三種可能的狀態(tài)之中，即:t＜r/p(s) (2)t＞r/p(s) (3)t=r/p(s)對(duì)于第一種情況，由于頁(yè)傳送速度大于訪(fǎng)問(wèn)外存頁(yè)面的速度（讀取外存的時(shí)間小于平均缺頁(yè)時(shí)間），因此，進(jìn)程在執(zhí)行過(guò)程中發(fā)生缺頁(yè)的次數(shù)較少，并不經(jīng)常從外存調(diào)頁(yè)。在第二種情況時(shí)，由于內(nèi)外存之間的頁(yè)面?zhèn)魉退俣纫呀?jīng)小于訪(fǎng)問(wèn)外存頁(yè)面速度（讀取外存的時(shí)間大于平均缺頁(yè)時(shí)間），因此，進(jìn)程在執(zhí)行過(guò)程中發(fā)生缺頁(yè)的次數(shù)已經(jīng)多到外存供不應(yīng)求的地步。事實(shí)上，這時(shí)的系統(tǒng)已處于抖動(dòng)狀態(tài)。第三種情況是一種較理想的情況，即進(jìn)程在執(zhí)行過(guò)程中所需要的頁(yè)數(shù)正好等于從外存可以調(diào)入的頁(yè)數(shù)。此時(shí)該進(jìn)程在內(nèi)存中占有最佳工作集。根據(jù)以上討論可知，一個(gè)進(jìn)程在內(nèi)存中占有最佳工作集的條件是:p(s)=r/tr是CPU訪(fǎng)問(wèn)內(nèi)存單元所需平均時(shí)間，t是訪(fǎng)問(wèn)外存一個(gè)頁(yè)面所需平均時(shí)間。因?yàn)閜(s)可表示為p(w)=ae-bs從而有，s=ln(at/r)/b即，與內(nèi)存存取速度r相比，若外存?zhèn)魉退俣仍铰?t大)，所需工作集就越大。實(shí)際中，由于各進(jìn)程所包含的程序段多少，選用的淘汰算法等不一樣，工作集的選擇也不一樣。由以上討論，我們可以找出解決抖動(dòng)問(wèn)題的幾種關(guān)鍵辦法。抖動(dòng)只有在t>r/p(s)時(shí)才會(huì)發(fā)生。而p(s)等于ae-bs是一個(gè)與工作集s、參數(shù)a和b有關(guān)的概率值。p(s)是可以改變的。對(duì)于給定的系統(tǒng)來(lái)說(shuō)，t和r則是一個(gè)很難改變的數(shù)字。解決抖動(dòng)問(wèn)題的最關(guān)鍵辦法是將p(s)減少到使t=r/p(s)。需要:(1)增加s，也就是擴(kuò)大工作集(2)改變參數(shù)a和b，也就是選擇不同的淘汰算法以解決抖動(dòng)問(wèn)題。

在前面介紹的各種管理技術(shù)中，用戶(hù)的邏輯地址空間都是一維的線(xiàn)性地址空間，這要求對(duì)源程序進(jìn)行編譯、鏈接時(shí)，把源程序中的主程序、子程序、數(shù)據(jù)區(qū)等按線(xiàn)性空間的一維地址順序排列起來(lái)。這使得不同作業(yè)或進(jìn)程之間共享公用子程序和數(shù)據(jù)變得非常困難，同時(shí)程序也不能動(dòng)態(tài)地增長(zhǎng)(程序的每部分的修改都要影響到其它部分。因此，程序的任何改動(dòng)都要重新編譯、鏈接和裝配)。

另外，在頁(yè)式管理中，一個(gè)頁(yè)面中可能裝有兩個(gè)不同子程序段的指令代碼，因此，通過(guò)頁(yè)面來(lái)共享一個(gè)邏輯上完整的子程序或數(shù)據(jù)塊是不可能的。

5.3段式管理一、基本概念1.段的定義

所謂段是一組相關(guān)的邏輯信息的集合。如主程序、子程序、數(shù)組和數(shù)據(jù)區(qū)等.2.作業(yè)的邏輯地址空間在分段情況下，每個(gè)作業(yè)的地址空間按照自身的邏輯關(guān)系分成若干個(gè)段，每個(gè)段有自己的段名(由程序員自己給出)和段號(hào)(系統(tǒng)自動(dòng)生成)。每個(gè)段的邏輯地址空間均從基地址“0”開(kāi)始編成連續(xù)的線(xiàn)性地址(故在分段情況下，作業(yè)的邏輯地址空間是二維的)。3.作業(yè)虛地址的表示

每個(gè)作業(yè)或進(jìn)程的虛地址分為兩部分：

即：虛地址（S，W）舉例：

段號(hào)－S段內(nèi)地址－WCALL[x]|<Y>LOAD1,[A]|6STORE1,[B]|<C>………01k分段MAIN＝0(主程序)0600Y:……分段X＝1(子程序)05000800C:……分段A＝2(數(shù)組)分段B＝3(數(shù)據(jù)區(qū))10012061200CALL[x]|<Y>表示轉(zhuǎn)移到子程序x中的入口點(diǎn)Y；LOAD1,[A]|6將數(shù)組A的第六個(gè)單元的值讀入寄存器1中；STORE1,[B]|<C>將寄存器1中的內(nèi)容存入分段B中的地址為C的單元中。段式管理的基本思想：把程序按內(nèi)容或過(guò)程(函數(shù))關(guān)系分成段，每段有自己的段名。一個(gè)用戶(hù)作業(yè)或進(jìn)程所包含的段對(duì)應(yīng)于一個(gè)二維線(xiàn)性虛擬空間。段式管理程序以段為單位分配內(nèi)存，然后通過(guò)地址映射機(jī)構(gòu)把段式虛擬地址轉(zhuǎn)換成物理地址。和頁(yè)式管理一樣，段式管理也采用只把那些經(jīng)常訪(fǎng)問(wèn)的段駐留內(nèi)存，而把那些在將來(lái)一段時(shí)間內(nèi)不被訪(fǎng)問(wèn)的段放入外存，待需要時(shí)自動(dòng)調(diào)入的方法實(shí)現(xiàn)二維虛擬存儲(chǔ)器。二、段式管理的內(nèi)存分配與釋放段式管理中以段為單位分配內(nèi)存，即：每段分配一個(gè)連續(xù)的內(nèi)存區(qū)。由于各段長(zhǎng)度不等，所以這些存儲(chǔ)區(qū)的大小不一。而且，同一個(gè)作業(yè)或進(jìn)程所包含的每個(gè)段分配的空間可以是不相鄰的。段式管理的內(nèi)存分配與釋放在作業(yè)或進(jìn)程的執(zhí)行過(guò)程中動(dòng)態(tài)進(jìn)行。首先，段式管理程序?yàn)橐粋€(gè)進(jìn)入內(nèi)存準(zhǔn)備執(zhí)行的進(jìn)程或作業(yè)分配部分內(nèi)存，隨著進(jìn)程或作業(yè)的執(zhí)行，根據(jù)需要隨時(shí)申請(qǐng)調(diào)入段(換入)或淘汰段(換出)

。當(dāng)進(jìn)程要求調(diào)入某一段時(shí)，進(jìn)程申請(qǐng)內(nèi)存區(qū)可分為兩種情況：（1）一種是當(dāng)進(jìn)程要求調(diào)入某一段時(shí)，內(nèi)存中有足夠的空閑區(qū)滿(mǎn)足該段的內(nèi)存要求。（2）另一種是內(nèi)存中沒(méi)有足夠的空閑區(qū)滿(mǎn)足該段的內(nèi)存要求。第一種情況（內(nèi)存有足夠的內(nèi)存區(qū)）當(dāng)發(fā)生缺段時(shí)，內(nèi)存有足夠的連續(xù)的內(nèi)存分區(qū)。系統(tǒng)要用相應(yīng)的表格或數(shù)據(jù)結(jié)構(gòu)來(lái)管理內(nèi)存空閑區(qū)，以便對(duì)用戶(hù)進(jìn)程或作業(yè)的有關(guān)程序段進(jìn)行內(nèi)存分配和回收。事實(shí)上，可以采用和動(dòng)態(tài)分區(qū)式管理相同的空閑區(qū)管理方法。即把內(nèi)存各空閑區(qū)按物理地址從低到高排列或按空閑區(qū)大小從小到大或從大到小排列（空閑區(qū)自由鏈）。分區(qū)式管理時(shí)所用的幾種分配算法:最先適應(yīng)法、最佳適應(yīng)法、最壞適應(yīng)法都可用來(lái)進(jìn)行空閑區(qū)分配。當(dāng)然，分區(qū)式管理時(shí)用到的內(nèi)存回收方法也可以在段式管理中使用。第二種情況（內(nèi)存沒(méi)有足夠的內(nèi)存區(qū)）在內(nèi)存中沒(méi)有足夠的空閑區(qū)滿(mǎn)足調(diào)入段的內(nèi)存要求時(shí)。段式管理程序根據(jù)給定的置換算法淘汰內(nèi)存中在今后一段時(shí)間內(nèi)不再被CPU訪(fǎng)問(wèn)的段，也就是淘汰那些訪(fǎng)問(wèn)概率最低的段。動(dòng)態(tài)頁(yè)式管理中的幾種常用的淘汰算法都可以用來(lái)作為段式管理時(shí)的淘汰算法。但是，與頁(yè)式管理時(shí)每頁(yè)具有相同的長(zhǎng)度時(shí)不一樣，需要調(diào)入的某段長(zhǎng)度可能大于被淘汰的一段程序或數(shù)據(jù)的長(zhǎng)度。這樣，僅僅淘汰一段可能仍然滿(mǎn)足不了需要調(diào)入段的內(nèi)存要求。此時(shí)，就應(yīng)再淘汰另外的段直到滿(mǎn)足需調(diào)入段的內(nèi)存要求時(shí)為止。事實(shí)上，一次調(diào)入時(shí)所需淘汰的段數(shù)與段的大小有關(guān)。如果一個(gè)作業(yè)或進(jìn)程的段數(shù)較多，且段長(zhǎng)之間的差別較大，則有可能出現(xiàn)調(diào)入某個(gè)大段時(shí)，需淘汰好幾個(gè)小段的情況。不過(guò)，在段式管理時(shí)，任何一個(gè)段的段長(zhǎng)都不允許超過(guò)內(nèi)存可用區(qū)長(zhǎng)度，否則將會(huì)造成內(nèi)存分配出錯(cuò)。除了初始分配之外，段的動(dòng)態(tài)分配是在CPU所要訪(fǎng)問(wèn)的指令和數(shù)據(jù)不在內(nèi)存時(shí)產(chǎn)生缺段中斷的情況下發(fā)生的。因此，段的淘汰或置換算法實(shí)際上是缺段中斷處理過(guò)程的一部分。缺段中斷處理過(guò)程的全過(guò)程如下圖所示。其中：X代表所缺段的段號(hào)。該處理程序是在CPU訪(fǎng)問(wèn)執(zhí)行時(shí)，地址變換機(jī)構(gòu)發(fā)現(xiàn)該段不在內(nèi)存，而由硬件發(fā)出缺段中斷信號(hào)后被調(diào)用的。缺段中斷處理過(guò)程FIFO:先來(lái)先服務(wù)LRU:最近最久未使用的頁(yè)面置換算法三、段表和段表地址寄存器同分頁(yè)一樣，系統(tǒng)為每個(gè)作業(yè)建立一個(gè)段映射表－簡(jiǎn)稱(chēng)段表，以實(shí)現(xiàn)動(dòng)態(tài)地址轉(zhuǎn)換(該表由系統(tǒng)自動(dòng)建立)。段表內(nèi)容：段號(hào)、段的長(zhǎng)度、段在主存的始址、段的狀態(tài)位、訪(fǎng)問(wèn)位、修改位、段在外存的地址等(如下表所示)。段表地址寄存器：用以指出運(yùn)行作業(yè)的段表在主存的起始地址和段表的長(zhǎng)度。段表段號(hào)段長(zhǎng)主存始址狀態(tài)位訪(fǎng)問(wèn)位修改位在外存的地址四、段式管理中的地址變換在段式管理中，把一個(gè)虛地址分成段號(hào)和段內(nèi)地址(段內(nèi)偏移量)——（s,w）其中：s:段號(hào)w:段內(nèi)地址(段內(nèi)偏移量)151090sw26=64(段)，每段的最大長(zhǎng)度=210=1024(字節(jié))=1K舉例：若段式存儲(chǔ)管理中，供用戶(hù)使用的邏輯地址為24位，其中段內(nèi)地址占用16位。請(qǐng)分步驟計(jì)算并加以說(shuō)明原因：（1）用戶(hù)程序最多可分為多少段？（2）當(dāng)把程序裝人主存時(shí)，每段占用主存的最大連續(xù)區(qū)為多少K字節(jié)？解:(1)邏輯地址24位，段內(nèi)16位，則用來(lái)表示段號(hào)用了24-16=8位。即用戶(hù)程序最多可分為28=256個(gè)段；(2)每段的最大地址范圍是216=65536B=65536/1024=64K，即每段占用主存的最大連續(xù)區(qū)為64K字節(jié)。四、段式管理中的地址變換在內(nèi)存中給出一塊固定的區(qū)域放置段表。當(dāng)某進(jìn)程開(kāi)始執(zhí)行時(shí)，管理程序首先把該進(jìn)程的段表始址放入段表地址寄存器。通過(guò)訪(fǎng)問(wèn)段表地址寄存器可找到該進(jìn)程的段表始地址址。然后由虛地址中的段號(hào)S查找段表。若該段在內(nèi)存，則從段表相應(yīng)表目中查出該段在內(nèi)存的起始地址，并將其和段內(nèi)相對(duì)地址w相加，從而得到實(shí)際的內(nèi)存地址。如果該段不在內(nèi)存，則產(chǎn)生缺段中斷將CPU控制權(quán)交給內(nèi)存分配程序。內(nèi)存分配程序首先檢查空閑區(qū)，以找到足夠長(zhǎng)度的空閑區(qū)來(lái)裝入所需要的段。如果內(nèi)存中的可用空閑區(qū)總數(shù)小于所要求的段長(zhǎng)時(shí)，則檢查段表中訪(fǎng)問(wèn)位，以淘汰那些訪(fǎng)問(wèn)概率低的段并將需要段調(diào)入。下面以L(fǎng)OAD1,1|100例，說(shuō)明在段式管理中的地址轉(zhuǎn)換過(guò)程MAIN=0[x]=1[A]=2LOAD1,1|100………12345…01K50001002000…段號(hào)段長(zhǎng)主存始址

01K6K15008K23004KOS02k4k6k8k8×1024+100=8292LOAD1,1|100～～～～123458292[A]=2MAIN=0[x]=1段表長(zhǎng)段表地址寄存器●

以L(fǎng)OAD1,1|100為例說(shuō)明地址轉(zhuǎn)換過(guò)程段表地址寄存器

段表長(zhǎng)·1100段號(hào)s段內(nèi)地址w段號(hào)段長(zhǎng)主存始址

01K6K15008K23004K8×102410012345物理地址：段式地址映射示意圖8×1024＋100＝8292與頁(yè)式管理時(shí)相同，段式管理時(shí)也必須經(jīng)過(guò)二次以上的內(nèi)存訪(fǎng)問(wèn)。即首先訪(fǎng)問(wèn)段表以計(jì)算得到待訪(fǎng)問(wèn)指令或數(shù)據(jù)的物理地址，然后才是對(duì)物理地址進(jìn)行讀/寫(xiě)操作。為了提高訪(fǎng)問(wèn)速度，頁(yè)式地址變換時(shí)使用的高速聯(lián)想寄存器的方法也可以用在段式地址變換中。如果在聯(lián)想寄存器中找到了所需要的段，則可以大大加快地址變換速度。五、段的共享與保護(hù)段式存儲(chǔ)管理可以方便地實(shí)現(xiàn)內(nèi)存信息共享和進(jìn)行有效地內(nèi)存保護(hù)。1.

段的共享在多道環(huán)境下，常常有許多子程序和應(yīng)用程序是被多個(gè)用戶(hù)所使用。如果每個(gè)用戶(hù)進(jìn)程或作業(yè)都在內(nèi)存保留它們共享程序和數(shù)據(jù)的副本，那就會(huì)極大地浪費(fèi)內(nèi)存空間。最好的辦法是內(nèi)存中只保留一個(gè)副本，供多個(gè)用戶(hù)使用，稱(chēng)為共享。下圖給出了一個(gè)段式系統(tǒng)中共享的例子。如上圖所示，如果用戶(hù)進(jìn)程或作業(yè)需要共享內(nèi)存中的某段程序或數(shù)據(jù)，只要用戶(hù)使用相同的段名，就可在新的段表中填入已存在于內(nèi)存之中的段的起始地址，并以適當(dāng)?shù)淖x寫(xiě)控制權(quán)，就可做到共享一個(gè)邏輯上完整的內(nèi)存段信息。在多道環(huán)境下，由于進(jìn)程的并發(fā)執(zhí)行,一段程序?yàn)槎鄠€(gè)進(jìn)程共享時(shí)，有可能出現(xiàn)多次同時(shí)重復(fù)執(zhí)行該段程序的情況(即某個(gè)進(jìn)程在未執(zhí)行完該段程序之前，其它并發(fā)進(jìn)程又已開(kāi)始執(zhí)行該段程序)。這就要求它在執(zhí)行過(guò)程中，該段程序的指令和數(shù)據(jù)不能被修改。另外，與一個(gè)進(jìn)程中的其它程序段一樣，共享段有時(shí)也要被換出內(nèi)存。這時(shí)，就要在段表中設(shè)立相應(yīng)的共享位來(lái)判別該段是否正被某個(gè)進(jìn)程調(diào)用。顯然一個(gè)正在被某個(gè)進(jìn)程使用或即將被某個(gè)進(jìn)程使用的共享段是不應(yīng)該調(diào)出內(nèi)存的。2.段的保護(hù)

與頁(yè)式管理時(shí)相同，段式管理的保護(hù)主要有兩種:一種是地址越界保護(hù)法，另一種是存取方式控制保護(hù)法。而地址越界保護(hù)則是利用段表中的段長(zhǎng)項(xiàng)與虛擬地址中的段內(nèi)相對(duì)地址比較進(jìn)行的。若段內(nèi)相對(duì)地址大于段長(zhǎng)，系統(tǒng)就會(huì)產(chǎn)生保護(hù)中斷。不過(guò)，在允許段動(dòng)態(tài)增長(zhǎng)的系統(tǒng)中，段內(nèi)相對(duì)地址大于段長(zhǎng)是允許的。為此，段表中設(shè)置相應(yīng)的增補(bǔ)位以指示該段是否允許該段動(dòng)態(tài)增長(zhǎng)。六、段的動(dòng)態(tài)鏈接靜態(tài)鏈接裝配，必須在運(yùn)行前一次就把所有的子程序鏈接在一起并裝入內(nèi)存。這樣，不僅占用大量的主存空間，而且也要耗費(fèi)大量的CPU時(shí)間。所以最好采用什么時(shí)候用到哪一段再把該段調(diào)入內(nèi)存，然后重新鏈接裝配，這種方法稱(chēng)為段的動(dòng)態(tài)鏈接。所謂段的動(dòng)態(tài)鏈接是指：在一個(gè)程序開(kāi)始運(yùn)行時(shí)，只將主程序段調(diào)入內(nèi)存，其它各段的裝配是在主程序段運(yùn)行過(guò)程中逐步進(jìn)行的，每當(dāng)調(diào)入一個(gè)新段時(shí)，再將這個(gè)段裝配好，并與主程序段鏈接。

在段式存儲(chǔ)管理環(huán)境下，因?yàn)榉侄问前葱畔⒌倪壿媶挝粍澐值?，各段有自己的段名，并在作業(yè)運(yùn)行期間仍能保持原有的邏輯信息結(jié)構(gòu)，這不僅存取方便，而且增加一個(gè)段或增大一個(gè)段，不會(huì)影響其它段，段式管理的這一特點(diǎn)，十分有利段的動(dòng)態(tài)鏈接。七、段式虛擬系統(tǒng)在段式虛擬系統(tǒng)中，通常只要把一個(gè)作業(yè)時(shí)當(dāng)前需要的一個(gè)或幾個(gè)段裝入內(nèi)存就可以投入運(yùn)行，而其它分段都保存在外存(如磁盤(pán))上。在運(yùn)行過(guò)程中一旦發(fā)現(xiàn)要訪(fǎng)問(wèn)的段不在內(nèi)存時(shí)，就產(chǎn)生缺段中斷，由缺段中斷處理程序來(lái)處理。（1）缺段中斷處理程序通過(guò)查找主存自由分區(qū)表，若找到一塊足夠大的內(nèi)存區(qū)，就將所缺的段調(diào)入主存；（2）若找不到，就檢查未分配的內(nèi)存空間的總和，確定是否對(duì)內(nèi)存進(jìn)行“緊縮”，或者根據(jù)一定的原則調(diào)出(淘汰)一些段，然后再將所缺的段調(diào)入內(nèi)存，同時(shí)改變各種表格的相關(guān)項(xiàng)目；（3）中斷處理完后，新調(diào)入的段與主存中原有的段進(jìn)行段的動(dòng)態(tài)鏈接，才能正常運(yùn)行。八、段式管理的優(yōu)缺點(diǎn)1.優(yōu)點(diǎn)（1）提供了虛擬存儲(chǔ)器。與頁(yè)式管理不同的是，段式虛存每次交換的是一段有意義的信息，而不是像頁(yè)式虛存那樣只交換固定大小的頁(yè)從而需要多次缺頁(yè)中斷才能把所需信息完整地調(diào)入內(nèi)存。（2）允許動(dòng)態(tài)增長(zhǎng)一個(gè)段。段長(zhǎng)可根據(jù)需要?jiǎng)討B(tài)增長(zhǎng)，這對(duì)那些需要不斷增加或吸收新數(shù)據(jù)的段來(lái)說(shuō)，將是非常有好處的。（3）允許程序的動(dòng)態(tài)鏈接和裝配。（4）便于實(shí)現(xiàn)共享。如果幾個(gè)作業(yè)都需要某子程序或數(shù)據(jù)區(qū)時(shí)，只在內(nèi)存保留一個(gè)副本即可。2.缺點(diǎn)（1）和頁(yè)式管理一樣，段式管理系統(tǒng)在選擇淘汰算法時(shí)也必須十分慎重，否則也有可能產(chǎn)生抖動(dòng)現(xiàn)象。（2）段式管理比其他幾種方式要求有更多的硬件支持。這就提高了機(jī)器成本。另外，由于在內(nèi)存空閑區(qū)管理方式上與分區(qū)式管理相同，在碎片問(wèn)題以及為了消除碎片所進(jìn)行的合并等問(wèn)題上較分頁(yè)式管理要差。再者，允許段的動(dòng)態(tài)增長(zhǎng)也會(huì)給系統(tǒng)管理帶來(lái)一定的難度和開(kāi)銷(xiāo)（3）段式管理的另一個(gè)缺點(diǎn)就是每個(gè)段的長(zhǎng)度受內(nèi)存可用區(qū)大小的限制。段頁(yè)式儲(chǔ)存管理是把分段和分頁(yè)兩種管理技術(shù)相結(jié)合，綜合了二者的優(yōu)點(diǎn)(分段在邏輯上的優(yōu)點(diǎn)和分頁(yè)在管理存儲(chǔ)空間方面的優(yōu)點(diǎn))。即：用分段的方法來(lái)了分配和管理虛存，用分頁(yè)的方法來(lái)分配和管理內(nèi)存。一、基本思想(或?qū)崿F(xiàn)原理)

（1）等分主存：把整個(gè)主存空間分成大小相等的存儲(chǔ)塊－頁(yè)面，并從0依次編上序號(hào)。（2）作業(yè)的地址空間采用分段方式，即按程序的自然邏輯關(guān)系把作業(yè)的地址空間分成若干段，而每一段均有自己的段名和段號(hào)。5.4段頁(yè)式管理04k-1分段MAIN＝0(主程序)03k-1分段X＝1(子程序)02k-1分段A＝2(數(shù)組)內(nèi)存（3）作業(yè)的每一段又采用分頁(yè)方法，即按頁(yè)面大小