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

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

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

1.虛擬存儲器：是指一種實際上并不存在的虛假的存儲器。

2.虛擬地址：把一個運行進程訪問的地址稱為虛擬地址。5.1基本概念

3.實地址：把處理機可直接訪問的地址稱為實地址。相應(yīng)的有：虛地址空間、實地址空間的概念。●問題：

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

實現(xiàn)原理

1.等分主存把主存劃分成大小相同的存儲塊，稱為頁面(或塊)，并給各頁面從零開始編上序號：0，1，2，…。

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

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

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

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

ADD1，24100100102100068021120200040006251241030000頁1頁2頁3頁0100020003000頁號塊號03192-3-02頁號塊號14270100020003000LOAD1，1120

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

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

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

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

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

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

注：

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

W＝虛地址%頁大小——取余數(shù)根據(jù)題意產(chǎn)生頁表；以頁號查頁表，得到對應(yīng)頁裝入內(nèi)存的塊號計算機公式內(nèi)存地址＝塊號×頁大?。灰屏俊耥撌降刂酚成湫〗Y(jié)2.虛地址(邏輯地址、相對地址)以十六進制、八進制、二進制的形式給出將虛地址轉(zhuǎn)換成二進制的數(shù)；按頁的大小分離出頁號和位移量(高位部分是頁號，低位部分是位移量)；將低位部分——位移量直接復(fù)制到內(nèi)存地址寄存器的低位部分；根據(jù)頁號查頁表，得到該頁裝入內(nèi)存的物理塊號，并將塊號轉(zhuǎn)換成二進制數(shù)填入地址寄存器的高位部分，從而形成內(nèi)存地址。十六進制(參考)：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è)大小是8KB，頁大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地址。解答:（1）虛地址7145P＝INT(7145/2048)＝3(對應(yīng)物理塊5)W＝[7145]mod2048＝1001MR=5*2048+1001=11241虛地址7145的內(nèi)存地址是：11241（2）虛地址3412P＝INT(3412/2048)＝1(對應(yīng)物理塊9)W＝[3412]mod2048＝1364MR=9*2048+1364=19796

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

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

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

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

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

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

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

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

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

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

A.64

B.128

C.256D.512解：邏輯地址空間為216頁，頁表項為2個字節(jié)，故頁表長度為

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

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

128個表項。

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

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

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

(1)

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

(2)

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

(1)

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

外存始址

08Y

120Y

2-N

3-N

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

可在頁表中再增加一項，以記錄該頁是否被修改過。增加后的頁表如下：頁號頁面號標志位改變位

外存始址

修改位5.請求頁式管理中的置換算法

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

(1)

隨機淘汰算法(RG)

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

循回換出內(nèi)存可用區(qū)內(nèi)一個可以被換出的頁面，無論該頁是否剛被換進或以換進很長時間。(3)先進先出(FIFO)

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

選擇以后不再訪問的頁或經(jīng)很長時間之后才可能訪問的頁進行淘汰。

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

該算法的基本思想是:

當需要淘汰某一頁時，選擇離當前時間最近的一段時間內(nèi)最久沒有使用過的頁先淘汰。該算法的主要出發(fā)點是，如果某頁被訪問了，則它可能馬上還要被訪問?；蛘叻催^來說，如果某頁很長時間未被訪問，則它在最近一段時間也不會被訪問。

要完全實現(xiàn)LRU算法是十分困難的。因為要找出最近最久未被使用的頁面的話，就必須對每一個頁面都設(shè)置有關(guān)的訪問記錄項，而且每一次訪問都必須更新這些記錄。這顯然要花費巨大的系統(tǒng)開銷。因此，在實際系統(tǒng)中往往使用LRU的近似算法。LRU頁面置換算法舉例：例如：進程P有5個頁，進程訪問頁的順序為：4，3，2，1，4，3，5，4，3，2，1，5；如果在內(nèi)存中分配給該進程3個頁面，則缺頁情況如下：頁面432143543215頁面1432143543215頁面243214354321頁面34321435432缺頁×××××××√√×××缺頁中斷次數(shù)：10次缺頁率=(10/12)*100%=83.3%頁面淘汰順序：

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

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

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

由訪問位R和修改位M可以組合成下面四種類型的頁面：

1類(R=0,M=0):

表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。

2類(R=0,M=1)：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。

3類(R=1,M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問。

4類(R=1,M=1):

最近已被訪問且被修改，該頁可能再被訪問。2.改進型Clock置換算法

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

(1)從指針所指示的當前位置開始，掃描循環(huán)隊列，尋找R=0且M=0的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位A。

(2)如果第一步失敗，則開始第二輪掃描，尋找R=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位R都置為0。

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

例1：進程P有5頁程序訪問頁的順序為：1,2,3,4,1,2,5,1,2,3,4,5；如果在內(nèi)存中分配3個頁面，則缺頁情況如下:×表示缺頁中斷，√表示無缺頁中斷。FIFO

1

2

3

4

1

2

5

1

2

3

4

5

頁0

1

2

3

4

1

2

5

5

5

3

4

4

頁1

1

2

3

4

1

2

2

2

5

3

3

頁2

1

2

3

4

1

1

1

2

5

5

缺頁

×

×

×

×

×

×

×

√

√

×

×

√

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以LOAD1,1|100為例說明地址轉(zhuǎn)換過程段表地址寄存器

段表長·1100段號s段內(nèi)地址w段號段長主存始址

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

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

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

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

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