計(jì)算機(jī)存儲管理

本章內(nèi)容提要

■引言

■分區(qū)法

■分頁技術(shù)

■分段技術(shù)

■段頁式技術(shù)

■虛擬存儲器

■請求分頁技術(shù)

■頁面置換算法

■內(nèi)存塊的分配和抖動問題

■請求分段技術(shù)

■Linux系統(tǒng)的存儲管理

5.1引言

■內(nèi)存(MainMemory或PrimaryMemory或RealMemory)也

稱主存，是指CPU能直接存取指令和數(shù)據(jù)的存儲器。

設(shè)

備

內(nèi)存在計(jì)算機(jī)系統(tǒng)中的地位

5.1.1用戶程序的地址空間

1用戶程序的主要處理階段

用戶

■主要處理階段

編輯

編譯

連接

裝入

運(yùn)行

■有關(guān)概念

?裝入程序

相對地址或邏輯地址

絕對地址或物理地址

■程序裝入內(nèi)存的方式

①絕對裝入方式

②可重定位裝入方式

③動態(tài)運(yùn)行時(shí)裝入方式

（執(zhí)行內(nèi)存中可執(zhí)行文件）

5.1.2重定位

■邏輯地址空間（簡稱地址空間）

由程序中邏輯地址組成的地址范圍

■內(nèi)存空間（也稱物理空間或絕對空間）

由內(nèi)存中一系列存儲單元所限定的地址范圍

■重定位

程序和數(shù)據(jù)裝入內(nèi)存時(shí)，需對目標(biāo)程序中的地址進(jìn)行修改。

這種把邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存物理地址的過程稱作重定位

■重定位方式

靜態(tài)重定位

動態(tài)重定位

1.靜態(tài)重定位

目標(biāo)程序裝入內(nèi)存時(shí)進(jìn)行地址變換

程序A的內(nèi)存空間

程序裝入內(nèi)存時(shí)的情況靜態(tài)重定位示意圖

▲優(yōu)點(diǎn)：無需增加硬件地址轉(zhuǎn)換機(jī)構(gòu)

?主要缺點(diǎn):位置“釘死”；不便共享

2.動態(tài)重定位

程序執(zhí)行期間進(jìn)行重定位

重定位寄存器

700

地址空間存儲空間

動態(tài)重定位示意圖

?主要優(yōu)點(diǎn)：位置可變，不必連續(xù)；易于共享

▲主要缺點(diǎn)：需要附加硬件支持；軟件算法比較復(fù)雜

5.1.3對換技術(shù)

時(shí)間一A

操作系統(tǒng)

用

戶

空

間

對換兩個(gè)進(jìn)程示意圖多道程序?qū)Q技術(shù)示例

5.2分區(qū)法

■分區(qū)分配是為支持多道程序運(yùn)行而設(shè)計(jì)的一種最

簡單的存儲管理方式。

5.2.1固定分區(qū)法

■分區(qū)個(gè)數(shù)固定不變，大小固定不變

■劃分分區(qū)方式：

▲等分方式

▲差分方式

固定分區(qū)法

分區(qū)號大小(KB)開始地址(K)狀態(tài)

12520正使用

23545正使用

35080正使用

470130未使用

分區(qū)說明表

固定分區(qū)管理示意圖

?優(yōu)點(diǎn)：管理方式簡單，所需操作系統(tǒng)軟件和處理開銷都小

▲缺點(diǎn)：①內(nèi)存空間利用率不高，碎片嚴(yán)重；

②活動進(jìn)程數(shù)目受限；

③無法預(yù)知所需內(nèi)存大小

5.2.2動態(tài)分區(qū)法

0

操作

進(jìn)程隊(duì)列

1.分區(qū)的分配系統(tǒng)

40K進(jìn)程需要內(nèi)存大小運(yùn)行時(shí)間

160KB10

▲操作系統(tǒng)內(nèi)部設(shè)置一個(gè)2100KB5

內(nèi)存登記表

216KB330KB20

470KB8

550KB15

256K

(a)內(nèi)存初始情況和進(jìn)程隊(duì)列

00000

操作

操作

作

操

統(tǒng)

系

統(tǒng)操作

系

操作統(tǒng)

系

系統(tǒng)系統(tǒng)

40K40K40K40K140K

裝入

進(jìn)程1進(jìn)程5

進(jìn)程1進(jìn)程1進(jìn)程1結(jié)束進(jìn)程5

90K，/〃///

I00KI00K100K100K100K

1

進(jìn)程

進(jìn)程2裝入進(jìn)程44進(jìn)程4

進(jìn)程2

MVT的內(nèi)存分配和進(jìn)程調(diào)度情況結(jié)束進(jìn)程4

170K//〃〃/170K，〃/〃/170K//〃〃/

200K200K200K200K200K

進(jìn)程3進(jìn)程3進(jìn)程3進(jìn)程3進(jìn)程3

230K230K230K怒230K230K

256K256K256K256K256K

(1)

(b)內(nèi)存分配和進(jìn)程調(diào)度情況

動態(tài)分區(qū)法

2.數(shù)據(jù)結(jié)構(gòu)

常用的數(shù)據(jù)結(jié)構(gòu)形式:

空閑分區(qū)表

(1)分區(qū)號分區(qū)大小(KB)分區(qū)起始地址(K)狀態(tài)

15075空閑

226170空閑

340275空閑

460418空閑

5?????????

(2)空閑分區(qū)鏈

■使用鏈指針把所有的空閑分區(qū)鏈接成一條鏈

3.分配算法

(1)最先適應(yīng)算法

■空閑表是按地址排列的(即空閑塊地址小的，在表中的序

號也小)。

(2)最佳適應(yīng)算法

■空閑表是以空閑分區(qū)的大小為序、按增量形式排列的，即

小塊在前，大塊在后。

(3)循環(huán)適應(yīng)算法

■最先適應(yīng)算法的變種。它不從空閑表的開頭查找，而從上

次找到的可用分區(qū)的下一個(gè)空閑分區(qū)開始查找，從中選擇

滿足大小要求的第一個(gè)空閑分區(qū)。

分配算法

<—低址低址

8KB

三種算法分配16KB最先適應(yīng)法12KB

空閑分區(qū)之前和之

后的內(nèi)存配置情況

打已分塊

口空閑塊

(a)分配前(b)分配后

4.碎片問題

■“碎片”或“零頭”：

內(nèi)存中這種容量太小、無法利用的小分區(qū)

■內(nèi)部碎片：

在一個(gè)分區(qū)內(nèi)部出現(xiàn)的碎片（即被浪費(fèi)的空間），如固定

分區(qū)法會產(chǎn)生內(nèi)部碎片。

■外部碎片：

在所有分區(qū)之外新增的碎片

5.2.3可重定位分區(qū)分配

1.緊縮

000

■緊縮(或拼湊)操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)

進(jìn)程5

20K進(jìn)程20K20K

1(8KB)(80KB)進(jìn)程1(8KB)進(jìn)程1(8KB)

28K28K28K

■可重定位分區(qū)法進(jìn)程3(24KB)進(jìn)程3

52K52K進(jìn)程

64K進(jìn)程2(20KB)2

進(jìn)程3(24KB)72K72K

■緊縮時(shí)機(jī)88K進(jìn)程4(50KB)進(jìn)程4

I12K122K

釋放所占分區(qū)時(shí)進(jìn)程2(20KB)

132K進(jìn)程5

?分配進(jìn)程分區(qū)時(shí)進(jìn)程4(50KB)(80KB)

182K202KS

256K256K

(a)初始狀態(tài)(b)移動之后(c)分配進(jìn)程5之后

可重定位分區(qū)的緊縮示意圖

2.動態(tài)重定位的實(shí)現(xiàn)過程

■動態(tài)重定位經(jīng)常用硬件實(shí)現(xiàn)

■硬件支持

基址寄存器

限長寄存器

動態(tài)重定位的實(shí)現(xiàn)過程

3.可重定位分區(qū)法的優(yōu)缺點(diǎn)

?優(yōu)點(diǎn)：

可以消除碎片，能夠分配更多的分區(qū)，有助于多道程序設(shè)

計(jì)，提高內(nèi)存的利用率。

▲缺點(diǎn)：

◎緊縮花費(fèi)了大量CPU時(shí)間

◎當(dāng)進(jìn)程大于整個(gè)空閑區(qū)時(shí)，仍要浪費(fèi)一定的內(nèi)存

◎進(jìn)程的存儲區(qū)內(nèi)可能放有從未使用的信息

◎進(jìn)程之間無法對信息共享

5.3分頁技術(shù)

5.3.1分頁存儲管理的基本概念

(1)邏輯空間分頁

(2)內(nèi)存空間分塊內(nèi)存塊或頁框

(3)邏輯地址表示

3112110

頁號P頁內(nèi)地址d

分頁技術(shù)的地址結(jié)構(gòu)示意圖

▲給定的邏輯地址是4頁面的大小為則頁號p和頁內(nèi)地址d可按下式求

得

p=INT(/1/L),c/=>4MODL

式中，INT是向下整除的函數(shù)，MOD是取余函數(shù)。

分頁存儲管理的基本概念

(4)內(nèi)存分配原則

▲以塊為單位▲每個(gè)頁面對應(yīng)一個(gè)內(nèi)存塊▲內(nèi)存塊可不連續(xù)

塊號

頁號塊號0

A

。頁03I

A

1頁152

2頁26進(jìn)程1,0頁3

3頁A3104

4頁48進(jìn)程1,1頁5

進(jìn)程1,2頁6

?????????進(jìn)程頁7

進(jìn)程1,4頁8

A

〃-1頁n—\79

進(jìn)程1地址空間頁表

進(jìn)程1,3頁10

內(nèi)m—2

存

ni—\

分頁存儲管理系統(tǒng)示意圖

分頁存儲管理的基本概念

(5)頁表

頁號塊號

0頁03

—

1頁15

2頁—26

3頁—310

4頁—48

???......

〃-1頁—n-\7

進(jìn)程1地址空間頁表

實(shí)現(xiàn)從頁號到物理塊號的地址映射

分頁存儲管理的基本概念

(6)內(nèi)存塊表

■整個(gè)系統(tǒng)有一■個(gè)內(nèi)存塊表。每個(gè)內(nèi)存塊在內(nèi)存塊表中占一,

項(xiàng)，表明該塊當(dāng)前空閑還是已分出去了。

5.3.2分頁系統(tǒng)中的地址映射

頁表

▲每個(gè)進(jìn)程平均有半個(gè)頁面的內(nèi)部碎片

5.3.3頁面尺寸

■折中方案

■設(shè)進(jìn)程的平均大小為S字節(jié)，頁面尺寸為刀字節(jié)，每個(gè)頁表項(xiàng)占6字節(jié)。

那么，每個(gè)進(jìn)程需要的頁數(shù)大約為s/夕，

占用s?e/夕字節(jié)的頁表空間。

每個(gè)進(jìn)程的內(nèi)部碎片平均為夕/2。

因此，由頁表和內(nèi)部碎片帶來的總開銷是：

sep

總開銷二一十二

P2

5.3.4硬件支持

■由硬件實(shí)現(xiàn)頁表的方式有多種，最簡單的方式是由一組專

門的寄存器來實(shí)現(xiàn)。

■通常修頁表保存在內(nèi)存中，由一個(gè)頁表基址寄存器PTBR指

向該頁表。整個(gè)系統(tǒng)只有一個(gè)PTBR。

▲帶來存取速度下降的矛盾

■聯(lián)想存儲器，也稱(或TranslationLookaside

Buffer,TLB)?？毂砻宽?xiàng)包括鍵號和值兩部分，鍵號是

當(dāng)前進(jìn)程正在使用的某個(gè)頁面號，值是該頁面所對應(yīng)的物

理塊號。

硬件支發(fā)

PTBR

▲命中率

在快表中成功找到指定

頁號的次數(shù)占總搜索次

數(shù)的百分比

利用快表實(shí)現(xiàn)地址轉(zhuǎn)換示例

5.3.5保護(hù)方式

(1)利用頁表本身進(jìn)行保護(hù)

(2)設(shè)置存取控制位

(3)設(shè)置合法標(biāo)志

5.3.6頁表的構(gòu)造

1.多級頁表

大多數(shù)現(xiàn)代計(jì)算機(jī)系統(tǒng)都支持非常大的邏輯地址空

間，如232?264。在這種情況下，只用一級頁表

會使頁表變得非常大。

■一種方法是利用兩級頁表，即把頁表本身也分頁。

外層頁號內(nèi)層頁號頁內(nèi)地址

p\P2d

31222112110

兩級頁表地址結(jié)構(gòu)示意圖

多級頁耒

內(nèi)層頁表

兩級頁表結(jié)構(gòu)示意圖

多級頁

外層頁號內(nèi)層頁號頁內(nèi)地址

外層頁表內(nèi)層頁表

兩級頁表結(jié)構(gòu)的地址轉(zhuǎn)換

多級頁表

外層頁號中間頁號內(nèi)層頁號頁內(nèi)地址

P1P2P3d

32位10位10位12位

三級頁表地址結(jié)構(gòu)示意圖

2.散列頁表(HashedPageTable)

以頁號作為參數(shù)形成散列值。散列表中每一項(xiàng)有一個(gè)

鏈表，它把看相同散列值的元素鏈接起來。每個(gè)鏈表

元素由三部分組成：

①頁號

②對應(yīng)的內(nèi)存塊號

③指向鏈表中下一個(gè)元素的指針

散列頁表

散列頁表構(gòu)成及地址轉(zhuǎn)換過程

3.倒置頁表

■它是按內(nèi)存塊號

排序的，每個(gè)內(nèi)

存塊占有一個(gè)表

項(xiàng)。每個(gè)表項(xiàng)包

括存放在該內(nèi)存

塊中頁面的虛擬

頁號和擁有該頁

面的進(jìn)程標(biāo)識符。

頁表

倒置頁表構(gòu)成及地址轉(zhuǎn)換過程

5.3.7頁面共享

■三個(gè)進(jìn)程共享0

3

ed2data1

大小為三個(gè)頁面41

6

的編輯器的情況,ed32data3

1

每個(gè)進(jìn)程都有自dataIA的頁表______3

ed1

進(jìn)程A

ed2

己的私有數(shù)據(jù)頁。34

4

5

6

ed3

7

6cd3

data2B的頁表

7data2

?可再入代碼（或ed1進(jìn)程B

38

純碼）：在其執(zhí)行ed2

4

9

過程中本身不做任ed36

2

何修改的代碼，通10

data3C的頁表

常由指令和常數(shù)組

進(jìn)程C

成

頁面共享示例

5.4分段技術(shù)

5.4.1分段存儲管理的基本概念

1.分段

▲段是一組邏輯信息的集

合。

▲每段都有自己的名字、

長度。

▲段號

段MAIN（O段）段P（1段）段D（2段）段S（3段）

分段地址空間

2.程序的地址結(jié)構(gòu)

■邏輯地址要用兩個(gè)成分來表示:

段號s和段內(nèi)地址d

進(jìn)程的邏輯地址空間是二維的

段號S段內(nèi)地址d

3116150

分段技術(shù)地址結(jié)構(gòu)示意圖

3.內(nèi)存分配

■內(nèi)存以段為單位進(jìn)行分配，每段單獨(dú)占用一塊連續(xù)的內(nèi)存

分百。各分區(qū)的大小由對應(yīng)段的大小決定。

4.段表和段表地址寄存器

■系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)段映射表，簡稱“段

表力。每個(gè)段在段表中占有一項(xiàng)，段表項(xiàng)中包含

段號、段長和段起始地址（又稱“基址”）等。

■系統(tǒng)還要建立一個(gè)段表地址寄存器。它有兩部分:

?該段表在內(nèi)存的起始地址

?該段表的長度。

5.分頁和分段的主要區(qū)別

①頁是信息的物理單位

段是信息的邏輯單位

②頁的大小是由系統(tǒng)確定的

段的長度因段而異

③分頁的進(jìn)程地址空間是一維的

分段的進(jìn)程地址空間是二維的

④分頁系統(tǒng)很難實(shí)現(xiàn)過程和數(shù)據(jù)的分離

分段系統(tǒng)卻可以很容易實(shí)現(xiàn)這些功能

5.4.2地址轉(zhuǎn)換

段表長段表地址

*limit

地址錯(cuò)，發(fā)中斷

分段地址轉(zhuǎn)換過程

5.4.3段的共享和保護(hù)

1.段的共享

■共享是在段一^級

實(shí)現(xiàn)的，任何共

享信息可以單獨(dú)

民為一段。

■也可以只共享部

分程序。

分段系統(tǒng)中段的共享

2.段的保護(hù)

■段的保護(hù)措施包括以下三種：

①存取控制

②段表本身可起保護(hù)作用

?表項(xiàng)中設(shè)置該段的長度限制

段長

?段表地址寄存器中有段表長度的信息

③保護(hù)環(huán)

5.5段頁式技術(shù)

5.5.1段頁式存儲管理的基本原理

①等分內(nèi)存

②地址空間分段

③段內(nèi)分頁

瞰）蝴和）勛咖:。）

④邏輯地址結(jié)構(gòu)

⑤內(nèi)存分配

⑥段表、頁表和段頁式存儲邏輯地址結(jié)構(gòu)示意圖

段表地址寄存器

5.5.2地址轉(zhuǎn)換過程

有效地址

內(nèi)存

段,'的頁表

段頁式系統(tǒng)的地址轉(zhuǎn)換機(jī)構(gòu)

5.6虛擬存儲盜

5.6.1虛擬存儲器的概念

■進(jìn)程在執(zhí)行之前要全部裝入內(nèi)存，這種限制是不

合理的。

①程序中往往含有不會被執(zhí)行的代碼

②分配的內(nèi)存空間會大于它們的實(shí)際需要

③一個(gè)程序的某些選項(xiàng)和特性可能很少使用

■程序的執(zhí)行過程也顯示出局部性

■按需分別調(diào)入內(nèi)存會帶來兩點(diǎn)好處：

①用戶編制程序時(shí)不必考慮內(nèi)存容量的限制

②在一定容量的內(nèi)存中就可同時(shí)裝入更多的進(jìn)程

虛擬存儲器的概念

■虛擬存儲器(VirtualMemory)

?用戶能作為可編址內(nèi)存對待的虛擬存儲空間，它使用戶邏輯存儲器

與物理存儲器分離，是操作系統(tǒng)給用戶提供的一個(gè)比真實(shí)內(nèi)存空間大

得多的地址空間。

■實(shí)現(xiàn)虛擬存儲技術(shù)的物質(zhì)基礎(chǔ)

?二級存儲器結(jié)構(gòu)

?動態(tài)地址轉(zhuǎn)換機(jī)構(gòu)(DAT)

■虛擬存儲器實(shí)質(zhì)上是把用戶地址空間和實(shí)際的存儲空間區(qū)

分開來。

■它主要受到兩方面的限制：

①指令中表示地址的字長

②外存的容量

5.6.2虛擬存儲器的特征

①虛擬擴(kuò)充

②部分裝入

③離散分配

④多次對換

5.7請求分頁技術(shù)

5.7.1請求分頁存儲管理的基本思想

■是在單純分頁技術(shù)基礎(chǔ)上發(fā)展起來的

■二者的根本區(qū)別在于請求分頁提供虛擬存儲器。

■基本思想是：

當(dāng)一個(gè)進(jìn)程的部分頁面在內(nèi)存時(shí)就可調(diào)度它運(yùn)行；在運(yùn)行過程中若

用到的頁面尚未在內(nèi)存，則把它們動態(tài)換入內(nèi)存。

■為了標(biāo)示進(jìn)程的頁面是否已在內(nèi)存，在每個(gè)頁表項(xiàng)中增

加一個(gè)標(biāo)志位。

5.7.2硬件支持及缺頁處理

1.頁表機(jī)制

■頁表項(xiàng)通常包含下列5種信息：

典型的頁表表項(xiàng)示意圖

2.缺頁中斷機(jī)構(gòu)

啟動要處理的指令

指

令

>處

理

周

期

硬

件

軟

件

指令執(zhí)行步驟與

缺頁中斷處理過程

5.7.3請求分頁技術(shù)的性能

■缺頁率.表示缺頁中斷的概率(04〃41)

等于缺頁次數(shù)與全部訪問內(nèi)存次數(shù)之比

■有效存取時(shí)間可表示為：

有效存取時(shí)間=(1-/7)xma+夕X缺頁處理時(shí)間

請求分頁技術(shù)的性能

■缺頁導(dǎo)致以下一系列動作（設(shè)當(dāng)前進(jìn)程為A）：

▲捕俘進(jìn)入操作系統(tǒng)

▲保存進(jìn)程A的各個(gè)寄存器和進(jìn)程狀態(tài)信息

▲確定該中斷是缺頁引起的

▲檢查對該頁的訪問是合法的，并確定該頁在磁盤上的地址

▲把該頁從盤上讀到空閑內(nèi)存塊中，其中包括在設(shè)備隊(duì)列中等待，直

至該請求得到服務(wù)；等待盤尋道以及潛在時(shí)間；把該頁傳送到空閑內(nèi)

存塊。

▲在等待盤I/O完成時(shí)，把CPU分給其他進(jìn)程（如進(jìn)程B）

▲盤I/O完成，發(fā)出盤中斷

▲保存進(jìn)程B的用戶寄存器和進(jìn)程狀態(tài)

▲確定該中斷來自磁盤

▲調(diào)整頁表和其他表格，標(biāo)明所需頁已放入內(nèi)存

▲進(jìn)程A就緒，等待分配CPU

▲調(diào)度到進(jìn)程A,則恢復(fù)它的各寄存器、進(jìn)程狀態(tài)和新的頁表，然后

重新執(zhí)行前面被中斷的指令。

請求分頁技術(shù)的性能

■缺頁中斷處理所花費(fèi)的時(shí)間主要有以下三部分：

①處理缺頁中斷的時(shí)間

②調(diào)入該頁的時(shí)間

③重新啟動該進(jìn)程的時(shí)間

■將頁面從盤上讀到內(nèi)存所花費(fèi)的時(shí)間包括：

?磁盤尋道時(shí)間（即磁頭從當(dāng)前磁道移至指定磁道所用的時(shí)間）

?旋轉(zhuǎn)延遲時(shí)間（即磁頭從當(dāng)前位置落到指定扇區(qū)開頭所用的時(shí)間）

?數(shù)據(jù)傳輸時(shí)間

典型磁盤的旋轉(zhuǎn)延遲時(shí)間約為8ms,尋道時(shí)間約為15ms,傳輸時(shí)間

是1mso

5.8頁面置換算法

5.8.1頁面置換

1.頁面置換過程

內(nèi)存

頁面置換過程

2.頁面走向

■抖動

頻繁地更換頁面，以致系統(tǒng)的大部分時(shí)間花費(fèi)在頁面的調(diào)度和傳輸上。

■盡量避免系統(tǒng)“抖動”

■存儲訪問序列也叫頁面走向

①對于給定的頁面大小，僅考慮其頁號，不關(guān)心完整的地址。

②如果當(dāng)前對頁面0進(jìn)行了訪問，那么，馬上又對該頁訪問就不會缺頁。這

樣連續(xù)出現(xiàn)的同一頁號就簡化為一個(gè)頁號。

▲如下地址序列（用十進(jìn)制數(shù)表示）：

0100,0432,0101,0612,0102,0103,0104,0101,0611,0102,

0103,0104,0101,0610,0102,0103,0104,0101,0609,0102,

0105

若每頁100個(gè)字節(jié)，則頁面走向簡化為：

1,4,1,6,1,6,1,6,1,6,1

頁面走向

■一般來說，隨著可用塊數(shù)的增加，缺頁數(shù)將減少。

▲統(tǒng)一采用下述頁面走向：

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

并且假定每個(gè)作業(yè)只有三個(gè)內(nèi)存塊可供使用。

5.8.2先進(jìn)先出法(FIFO)

■總是淘汰在內(nèi)存中停留時(shí)間最長（年齡最老）的

一頁，即先進(jìn)入內(nèi)存的頁，先被換出。

FIFO頁面置換序列

▲總共有15次缺頁

先進(jìn)先出(FIFO)法

■優(yōu)點(diǎn)：容易理解，方便程序設(shè)計(jì)。

■缺點(diǎn)：

?性能并不很好，效率不高

?存在Belady異?，F(xiàn)象，即缺頁率隨內(nèi)存塊增加而增加

關(guān)于一個(gè)頁面走向的FIFO淘汰算法的缺頁曲線

5.8.3最佳置換法(OPT)

■最佳置換算法(OptimalReplacement,OPT)其實(shí)質(zhì)是：

為調(diào)入新頁面而必須預(yù)先淘汰某個(gè)老頁面時(shí)，所選擇的老

頁面應(yīng)在圈來不被使用，或者是在最遠(yuǎn)的嚼來才被訪問。

最佳頁面置換序列僅出現(xiàn)9次缺頁中斷

▲保證有最小缺頁率

▲OPT算法在實(shí)現(xiàn)上有困難

5.8.4最近最少使用置換法（LRU）

■以“最近的過去”作為“不久將來”的近似

■實(shí)質(zhì)是：當(dāng)需要置換一頁時(shí)，選擇在最近一段時(shí)間里最久

沒有使用過的頁面予以淘汰。

70120304230321201701

777224440111

000000333TT

1133222227

內(nèi)存塊

最近最少使用算法頁面置換序列

▲產(chǎn)生12次缺頁

1311換法

LRU算法需要實(shí)際硬件的支持。實(shí)現(xiàn)時(shí)的問題

是：怎樣確定最后訪問以來所經(jīng)歷時(shí)間的順

序。有以下兩種可行的辦法：

①計(jì)數(shù)器

②棧

4707101212A7A12

ab

27

12

01

70

44

。以前的棧力以后的棧

利用棧記錄目前訪問最多的頁面示例

5.8.5第二次機(jī)會置換法(SCR)

■第二次機(jī)會置換法(SecondChancePageReplacement,SCR)是對

FIFO算法的改進(jìn)——避免把經(jīng)常使用的頁面置換出去。

■當(dāng)選擇某一頁面置換時(shí)，就檢查最老頁面的引用位：如果是0,就立

即淘汰該頁；如果該引用位是1,就給它第二次機(jī)會。

(a)

3781214151820把A看成新裝入的頁

(b)

第二次機(jī)會法示例

5.8.6時(shí)鐘置換法(Clock)

■簡單時(shí)鐘置換法

該算法又稱最近未使用置換法

(NotRecentlyUsed,NRU)

■改進(jìn)的時(shí)鐘置換法

在頁表項(xiàng)中設(shè)置兩個(gè)狀態(tài)位:

時(shí)鐘置換法示意圖

引用位和修改位

5.8.7最少使用置換法（LFU）

■最少使用（LeastFrequentlyUsed,LFU）頁面置換算法

是基于訪問計(jì)數(shù)的頁面置換法。

■為每個(gè)頁面設(shè)置一個(gè)軟件計(jì)數(shù)器

■將每頁的引用位R的值加到對應(yīng)的計(jì)數(shù)器上。發(fā)