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

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

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

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

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

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

實現原理

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

2.等分作業的邏輯地址空間將程序的邏輯地址空間也劃分若干個與頁面大小相同的塊,稱為頁。也編上序號0，1，2，…。●主存分配原則系統以頁面(塊)為單位把主存分給作業，每頁對應內存中一個頁面，這些頁面可以是不相臨的或連續的。

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

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

01234567891011121314A.0A.1A.2A.3B.0B.1B.2在頁式儲存管理中，是以頁面為單位分給用戶使用，為了記錄主存的使用情況，系統為每個進程建立一個頁表，最簡單的頁表包括如下信息：（1）頁號：作業的各頁的頁號；（2）塊號：指該頁裝入主存的第幾個頁面上。1.頁表與頁表地址寄存器▲頁的大小帶來的影響頁小：內碎片小，頁表長，管理復雜，存儲信息少，可能頻繁調頁；頁大：頁表短，管理開銷小，交換時對外存I/O效率高，但內碎片大，會多浪費內存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操作系統作業1作業2頁表2.靜態頁式管理的特點優點：

■沒有外碎片，每個內碎片不超過頁的大小■一個程序不必連續存放。■由于頁的大小相等，內存的分配、回收簡單，易于管理。缺點：程序要求全部裝入內存才能執行。3.邏輯地址的表示用戶的邏輯地址一般是從基址“0”開始連續編址。在分頁系統中，每個虛地址(相對地址)用一個數對(p，d)來表示，其中p表示頁號，d表示頁內地址(頁內偏移量)。令A是一個虛地址，頁面大小為L,則：

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

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

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

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

注：

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

W＝虛地址%頁大小——取余數根據題意產生頁表；以頁號查頁表，得到對應頁裝入內存的塊號計算機公式內存地址＝塊號×頁大小＋位移量●頁式地址映射小結2.虛地址(邏輯地址、相對地址)以十六進制、八進制、二進制的形式給出將虛地址轉換成二進制的數；按頁的大小分離出頁號和位移量(高位部分是頁號，低位部分是位移量)；將低位部分——位移量直接復制到內存地址寄存器的低位部分；根據頁號查頁表，得到該頁裝入內存的物理塊號，并將塊號轉換成二進制數填入地址寄存器的高位部分，從而形成內存地址。十六進制(參考)：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：有一系統采用頁式存儲管理，有一作業大小是8KB，頁大小為2KB，依次裝入內存的第7、9、10、5塊，試將虛地址7145，3412轉換成內存地址。解答:（1）虛地址7145P＝INT(7145/2048)＝3(對應物理塊5)W＝[7145]mod2048＝1001MR=5*2048+1001=11241虛地址7145的內存地址是：11241（2）虛地址3412P＝INT(3412/2048)＝1(對應物理塊9)W＝[3412]mod2048＝1364MR=9*2048+1364=19796

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

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

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

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

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

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

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

①對于32位的機器，采用兩級頁表結構是合適的；

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

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

A.64

B.128

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

216×2=128KB，一個內存物理塊存放1KB，故

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

128個表項。

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

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

在作業或進程開始運行前，只將被認為是經常被反復執行和調用的部分裝入內存，而其它部分在執行過程中動態的調入。即：通過交換的技術以小的內存運行大的作業。3.有兩種動態裝入方式

(1)

請求頁式管理當發現欲執行的某條指令或數據不在內存時，發生缺頁中斷，由系統將外存的頁面調入內存(軟件實現)。

(2)

預調入方管理系統對那些在外存中的頁進行調入順序計算，估計出這些頁中指令和數據的執行和被訪問的順序，并按此順序事先將它們順序調入和調出內存。4.請求頁式管理需要解決的問題

(1)

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

外存始址

08Y

120Y

2-N

3-N

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

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

外存始址

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

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

(1)

隨機淘汰算法(RG)

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

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

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

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

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

該算法的基本思想是:

當需要淘汰某一頁時，選擇離當前時間最近的一段時間內最久沒有使用過的頁先淘汰。該算法的主要出發點是，如果某頁被訪問了，則它可能馬上還要被訪問。或者反過來說，如果某頁很長時間未被訪問，則它在最近一段時間也不會被訪問。

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

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

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

該算法在需要淘汰某一頁時，從那些最近一個時期內未被訪問的頁中任選一頁淘汰。只要在頁表中增設一個訪問位即可實現。當某頁被訪問時，訪問位置1。否則，訪問位置0。系統周期性地對所有引用位清零。當需淘汰一頁時，從那些訪問位為零的頁中選一頁進行淘汰。（6）Clock置換算法(時鐘置換算法)1）簡單的Clock置換算法①為每頁設置一位訪問位，當淘汰一個頁面時，如果指針指向頁面的訪問位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置換算法

其執行過程可分成以下三步：

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

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

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

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

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

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

綜上所述，頁式管理具有如下優點:

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

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

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

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

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

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

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

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

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

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

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

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

段表長·1100段號s段內地址w段號段長主存始址

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

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

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

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

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