存儲管理課件

第四章存儲管理

4.1概述

4.2段式存儲管理

4.3頁式存儲管理

4.4段頁式存儲管理

4.5虛擬存儲

4.6交換技術(shù)與覆蓋技術(shù)

重要資源

“瓶頸”：關(guān)鍵、緊張

帕金森定律

4.1概述

4.L1存儲體系

存儲器的層次結(jié)構(gòu):

Cache

主存

磁盤

高速緩存Cache:

少量的、非常快速、昂貴、易變的

內(nèi)存RAM:

若干兆字節(jié)、中等速度、中等價格、

易變的

磁盤：

數(shù)百兆或數(shù)千兆字節(jié)、低速、價廉、

不易變的

力操作系統(tǒng)協(xié)調(diào)這些存儲器的使用

重要性：直接存取要求內(nèi)存速度盡量

快到與CPU取指速度相匹配，大到

能裝下當(dāng)前運(yùn)行的程序與數(shù)據(jù)，否

則CPU執(zhí)行速度就會受到內(nèi)存速度

和容量的影響而得不到充分發(fā)揮。

內(nèi)存:

是由存儲單元（字節(jié)或字）組成的

一維連續(xù)的地址空間，簡稱內(nèi)存空

間。用來存放當(dāng)前正在運(yùn)行程序的

代碼及數(shù)據(jù)，是程序中指令本身地

址所指的、亦即程序計(jì)數(shù)器所指的

存儲器。

內(nèi)存可以分為：

系統(tǒng)區(qū)：用于存放操作系統(tǒng)

用戶區(qū)：用于裝入并存放用戶程序

和數(shù)據(jù)。

4.1.2存儲管理目的

用戶對內(nèi)存的使用要求

1充分利用內(nèi)存，為多道程序并發(fā)執(zhí)行

提供存儲基礎(chǔ)。

2盡可能方便用戶使用

自動裝入用戶程序

用戶程序中不必考慮硬件細(xì)節(jié)

3系統(tǒng)能夠解決程序空間比實(shí)際內(nèi)存空

間大的問題

4程序在執(zhí)行時可以動態(tài)伸縮

5內(nèi)存存取速度快

6存儲保護(hù)與安全

7共享與通信

8了解有關(guān)資源的使用狀況

9實(shí)現(xiàn)的性能和代價

4.1.3存儲管理的任務(wù)

前提：引入多道程序設(shè)計(jì)技術(shù)

滿足用戶要求

1內(nèi)存空間的管理、分配與回收

記錄內(nèi)存的使用情況

----設(shè)置相應(yīng)的內(nèi)存分配表

（內(nèi)存分配回收的依據(jù)）

內(nèi)存空間劃分問題？

靜態(tài)或動態(tài)，等長或不等長

內(nèi)存空間的管理、分配與回收

內(nèi)存分配表

位示圖表示法：用一位(bit)表示一

個空閑頁面(0:空閑，1:占用)。

1I0|……|1||0；

第0頁第1頁第i頁第n-1頁

內(nèi)存空間的管理、分配與回收

空閑克面裝:包括首頁面號和頁面?zhèn)€

數(shù)，連續(xù)若干的頁面作為一組登記在

表中

空閑衣裝:空閑塊首址和空閑塊長度,

沒有記錄的區(qū)域即為進(jìn)程所占用

空閑塊鏈將所有的空閑塊鏈成一

個鏈表

內(nèi)存空間的管理、分配與回收

確定分配算法

實(shí)施內(nèi)存分配

回收內(nèi)存

分配回收方式:靜態(tài)分配與動態(tài)分配

內(nèi)存空間的管理、分配與回收

連續(xù)性;離散性

駐留性；交換性

一次性；多次性

2存儲共享

內(nèi)存共享：兩個或多個進(jìn)程共用內(nèi)存

中相同區(qū)域

的:

節(jié)省內(nèi)存空間，提高內(nèi)存利用率

實(shí)現(xiàn)進(jìn)程通信（數(shù)據(jù)共享）

共享內(nèi)容：

代碼共享，要求代碼為純代碼

數(shù)據(jù)共享

3存儲保護(hù)與安全

保護(hù)目的:

為多個程序共享內(nèi)存提供保障，使在

內(nèi)存中的各道程序，只能訪問他自己

的區(qū)域，避免各道程序間相互干攏,

特別是當(dāng)一道程序發(fā)生錯誤時，不致

于影響其它程序的運(yùn)行。通常由硬

件完成保護(hù)功能,軟件輔助實(shí)現(xiàn)。

（特權(quán)指令不能完成存儲保護(hù)。）

存儲保護(hù)

保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯

（有意或無意的）

不允許用戶程序讀寫不屬于自己地址

空間的數(shù)據(jù)

（系統(tǒng)區(qū)地址空間，其它用戶

程序的地址空間）

保護(hù)過程一防止地址越界

每個進(jìn)程都有自己獨(dú)立的進(jìn)程空間,

如果哪個進(jìn)程在運(yùn)行時所產(chǎn)生的地

址在其地址空間之外，則發(fā)生地址

越界。即當(dāng)程序要訪問某個內(nèi)存單

元時，由硬件檢查是否允許，如果

允許則執(zhí)行，否則產(chǎn)生地址越界中

斷，由操作系統(tǒng)進(jìn)行相應(yīng)處理。

保護(hù)過程一防止地址越界

一般由硬件提供一對寄存器:

基址寄存器：存放起始地址

限長寄存器：存放長度

（上界寄存器/下界寄存器）

保護(hù)過程—防止操作越權(quán)

對于允許多個進(jìn)程共享的存儲區(qū)

域，每個進(jìn)程都有自己的訪問權(quán)限。

如果一個進(jìn)程對共享區(qū)域的訪問違

反了權(quán)限規(guī)定，則發(fā)生操作越權(quán)。

即讀寫保護(hù)。

4內(nèi)存“擴(kuò)充”

通過虛擬存儲技術(shù)實(shí)現(xiàn)

用戶在編制程序時，不應(yīng)該受內(nèi)

存容量限制，所以要采用一定技術(shù)

來"擴(kuò)充”內(nèi)存的容量，使用戶得到

比實(shí)際內(nèi)存容量大的多的內(nèi)存空間。

內(nèi)存“擴(kuò)充”

具體實(shí)現(xiàn)是在硬件支持下，軟硬

件相互協(xié)作，將內(nèi)存和外存結(jié)合起

來統(tǒng)一使用。通過這種方法把內(nèi)存

擴(kuò)充，使用戶在編制程序時不受內(nèi)

存限制。

5地址映射(地址重定位，地址變換)

(1)邏輯地址(相對地址，虛地址)

(2)物理地址(絕對地址，實(shí)地址)

(3)地址映射

源程序0邏輯地址空間物理地址空間

⑴邏輯地址（相對地址，虛地址）

用戶的程序經(jīng)過匯編或編譯后形成目

標(biāo)代碼，目標(biāo)代碼通常采用相對地

址的形式，其首地址為0,其余指令

中的地址都相對于首地址而編址。

不能用邏輯地址在內(nèi)存中讀取信息。

(2)物理地址(絕對地址，實(shí)地址)

內(nèi)存中存儲單元的地址，可直接尋址。

⑶地址映射

為了保證CPU執(zhí)行指令時可正確訪問

存儲單元，需將用戶程序中的邏輯

地址轉(zhuǎn)換為運(yùn)行時由機(jī)器直接尋址

的物理地址，這一^過程稱為地址映

射。

邏輯地址空間BR物理地址空間

00

100

1100

200

1200

1300

300

原因：當(dāng)程序裝入內(nèi)存時，操作系統(tǒng)

要為該程序分配一個合適的內(nèi)存空

間，由于程序的邏輯地址與分配到

內(nèi)存物理地址不一致，而CPU執(zhí)行指

令時，是按物理地址進(jìn)行的，所以

要進(jìn)行地址轉(zhuǎn)換。

靜態(tài)重定位

當(dāng)用戶程序被裝入內(nèi)存時，一次性

實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，

以后不再轉(zhuǎn)換（一般在連接短配時

由軟件完成）。

動態(tài)重定位

在程序運(yùn)行過程中要訪問數(shù)據(jù)時再進(jìn)

行地址變換（即在逐條指令執(zhí)行時

完成地址映射。一般為了提高效率,

此工作由硬件地址映射機(jī)制來完成。

硬件支持，軟硬件結(jié)合完成）。

硬件上需要一對寄存器的支持。

4.1.4各種存儲管理方案

單一用戶（連續(xù)區(qū)）存儲管理：

單用戶系統(tǒng)在一段時間內(nèi)，只有

一個進(jìn)程在內(nèi)存，故內(nèi)存分配管理

十分簡單，內(nèi)存利用率低。內(nèi)存分

為兩個區(qū)域，一個供操作系統(tǒng)使用,

一個供用戶使用。

OxFFF...

ROM中的

用戶程序位于RAM中的

設(shè)備驅(qū)動程序

操作系統(tǒng)

用戶程序

位于RAM中的用戶程序

位于RAM中的

操作系統(tǒng)

操作系統(tǒng)

000

分區(qū)存儲管理方案

系統(tǒng)把內(nèi)存用戶區(qū)劃分為若干分區(qū)，

分區(qū)大小可以相等，也可以不等?！?/p>

個進(jìn)程占據(jù)一個分區(qū)。

固定分區(qū)

可變分區(qū)

固定分區(qū)

預(yù)先把可分配的主存儲器空間分割

成若干個連續(xù)區(qū)域，稱為一個分區(qū)。

每個分區(qū)的大小可以相同也可以不

同，如圖所示。但分區(qū)大小固定不

變，每個分區(qū)裝一個且只能裝一個

作業(yè)。

存儲分配：如果有一個空閑區(qū)，則分

配給

固定分區(qū)

內(nèi)存管理：設(shè)置內(nèi)存分配表

分區(qū)號起始地址長度狀態(tài)進(jìn)程名

內(nèi)存分配：

內(nèi)存回收：簡單

缺點(diǎn)：內(nèi)存利用率不高

可變分區(qū)

內(nèi)存的分配：內(nèi)存不是預(yù)先劃分好的,

而是當(dāng)作業(yè)裝入時，根據(jù)作業(yè)的需

求和內(nèi)存空間的使用情況來決定是

否分配。若有足夠的空間，則按需

要分割一部分分區(qū)給該進(jìn)程；否則

令其等待主存空間。

內(nèi)存的管理：

設(shè)置內(nèi)存空閑塊表——記錄了空閑區(qū)

起始地址和長度。

內(nèi)存分配：動態(tài)分配

內(nèi)存的回收：當(dāng)某一塊歸還后，前后空

間合并，修改內(nèi)存空閑塊表。

內(nèi)存分配：三種分配算法

首先適配算法:

當(dāng)接到內(nèi)存申請時，查空閑塊表，找

到第一個不小于請求的空塊，將其

分割并分配。

（特點(diǎn)：簡單、快速分配）

最佳適配算法:

接到內(nèi)存申請時，在空閑塊表中找到

一個不小于請求的最小空塊進(jìn)行分

配。

（特點(diǎn)：用最小空間滿足要求）

最壞適配算法

接到內(nèi)存申請時，在空閑塊表中找到

一個不小于請求的最大空塊進(jìn)行分

配。

（特點(diǎn)：當(dāng)分割后空閑塊仍為較大空

塊）

碎片問題:

經(jīng)過一段時間的分配回收后，內(nèi)存中

存在很多很小的空閑塊。它們每一

個都很小，不足以滿足分配要求；

但其總和滿足分配要求。這些空閑

塊被稱為碎片。

造成存儲資源的浪費(fèi)

碎片問題的解決:

緊湊技術(shù)：通過在內(nèi)存移動程序，將

所有小的空閑區(qū)域合并為大的空閑區(qū)

域。

（緊縮技術(shù)，緊致技術(shù)，浮動技術(shù)，

搬家技術(shù)）

問題：開銷大；移動時機(jī)

討論：

優(yōu)點(diǎn)：A便于動態(tài)申請內(nèi)存

B便于共享內(nèi)存

C便于動態(tài)鏈接

缺點(diǎn)：碎片問題（外碎片）

4.2段式存儲管理

421基本思想（工作原理）

0

CALL[X][E]

子程序段[X]數(shù)組[A]

CALL[Y][F]

CALL[A]116

K

子程序段[Y]工作區(qū)段[B]

主程序段[M]

p

N

用戶程序劃分

按程序自身的邏輯關(guān)系劃分為若干個

程序段，每個程序段都有一個段名,

且有一個段號。段號從0開始，每一

段也從0開始編址，段內(nèi)地址是連續(xù)

的。

邏輯地址

段號段內(nèi)地址

內(nèi)存劃分

內(nèi)存空間被動態(tài)的劃分為若干個長度

不相同的區(qū)域，這些區(qū)域被稱為物

理段，每個物理段由起始地址和長

度確定。

內(nèi)存分配

以段為單位分配內(nèi)存，每一個段在內(nèi)

存中占據(jù)連續(xù)空間（內(nèi)存隨機(jī)分割,

需要多少分配多少），但各段之間

可以不連續(xù)存放。

4.2.2管理

段號段首址段長度

0120K

1100K110K

2260K220K

段表:

它記錄了段號，段的首（地）址和

長度之間的關(guān)系。

每一個程序設(shè)一個段表

空閑塊管理:

記錄了空閑區(qū)起始地址和長度。

內(nèi)存的分配算法:

首先適配；最佳適配；最壞適配

4.2.3硬件支持

一對寄存器

段表始址寄存器：

用于保存正在運(yùn)行進(jìn)程的段表的

始址。

段表長度寄存器：

用于保存正在運(yùn)行進(jìn)程的段表的

長度（例如上圖的段表長度為3）。

相聯(lián)（聯(lián)想）存儲器

介于內(nèi)存與寄存器之間的存儲機(jī)制,

它又叫快表。

用途：保存正在運(yùn)行進(jìn)程的段表的子

集（部分表項(xiàng)）。

特點(diǎn)：按內(nèi)容并行查找。

引入快表的作用：

為了提高地址映射速度。

快表項(xiàng)目：段號；段始址；段長度；

標(biāo)識（狀態(tài)）位；訪問位，淘汰位。

快表淘汰問題?

4.2.4段的共享

作業(yè)

4.2.5段的保護(hù)

作業(yè)

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

便于動態(tài)申請內(nèi)存

管理和使用統(tǒng)一化

便于共享

便于動態(tài)鏈接

缺點(diǎn)：產(chǎn)生碎片

與可變分區(qū)存儲管理方案區(qū)別

4.3頁式存儲管理

4.3.1基本思想（工作原理）

用戶程序劃分

把用戶程序按邏輯頁劃分成大小相等

的部分，稱為頁。從0開始編制頁號,

頁內(nèi)地址是相對于0編址。

邏輯地址

頁號頁內(nèi)地址

用戶程序的劃分是由系統(tǒng)自動完成

的，對用戶是透明的。一般，一頁

的大小為2的整數(shù)次第，因此，地址

的高位部分為頁號，低位部分為頁

內(nèi)地址。

內(nèi)存空間:

按頁的大小劃分為大小相等的區(qū)域,

稱為內(nèi)存塊（又叫物理頁面）。

內(nèi)存分配:

以頁為單位進(jìn)行分配，并按作業(yè)的頁

數(shù)多少來分配。邏輯上相鄰的頁，

物理上不一定相鄰。

作業(yè)的

地址空間

表主存中頁框

（物理塊）

4.3.2管理

L頁表：系統(tǒng)為每個進(jìn)程都建立了一

個頁表，頁表給出邏輯地址號和具

體內(nèi)方塊號相應(yīng)的關(guān)系

2.空塊管理——總頁表

3.內(nèi)存的分配與回收

計(jì)算一個作業(yè)所需要的總塊數(shù)

O

查總頁表，看看是否還有N個空閑塊。

如果有相應(yīng)空閑塊，則頁表長度為該

為N,可填入PCB中。（申請頁表區(qū),

把頁表始址填入PCB）。

分配N個空閑塊，將塊號和頁號填入

頁表（頁表號實(shí)際不用填）。

修改總頁表。

4.3.3硬件支持

1.一對寄存器：

a頁表始址寄存器

b頁表長度寄存器

2.相聯(lián)寄存器---決表

1）頁號2）頁在內(nèi)存的塊號3）標(biāo)

識位4）淘汰位

地址映射機(jī)制物理地址

434頁的共享

作業(yè)

435頁的保護(hù)

作業(yè)

4.3.6優(yōu)缺，乞

優(yōu)點(diǎn)：a解決了碎片問題

b便于管理

缺點(diǎn)：a不易實(shí)現(xiàn)共享

b不便于動態(tài)連接

4.4段頁式存儲管理

4.4.1產(chǎn)生背景及基本思想

背景：結(jié)合了二者優(yōu)點(diǎn)

克服了二者的缺點(diǎn)

基本思想：

用戶程序劃分：按段式劃分（對用戶

來講，按段的邏輯關(guān)系進(jìn)行劃分；

對系統(tǒng)講，按頁劃分每一段）

邏輯地址:

段號段肉痣址

員專員內(nèi)也址

內(nèi)存劃分：按頁式存儲管理方案

內(nèi)存分配：以頁為單位進(jìn)行分配

4.4.2管理

1段表：記錄了每一段的頁表始址和

頁表長度

2頁表：記錄了邏輯頁號與內(nèi)存塊號

的對應(yīng)關(guān)系。（每一段有一個，一

個程序可能有多個頁表）

3空塊管理：

4分配：同頁式管理

4.4.3硬件支持

段表始址寄存器

段表長度寄存器

相聯(lián)存儲器（快表）

4.5虛擬存儲

連續(xù)性；離散性

駐留性；交換性

一次性；多次性

以CPU時間和外存空間換取昂貴內(nèi)存

空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技

術(shù)

4.5.1概述

1問題的提出：

a程序大于內(nèi)存

b程序暫時不執(zhí)行或運(yùn)行完是否還

要占用內(nèi)存。

虛擬存儲器的基本思想是：程序、數(shù)

據(jù)、堆棧的大小可以超過內(nèi)存的大小,

操作系統(tǒng)把程序當(dāng)前使用的部分保留

在內(nèi)存，而把其它部分保存在磁盤上,

并在需要時在內(nèi)存和磁盤之間動態(tài)交

換。

虛擬存儲器支持多道程序設(shè)計(jì)技術(shù)。

CPU

MMU

總線

o皿c。orr。］o。［i［o〔o

F

l

5

OOP0物理地址

4

u

0000

3

24580

l

0000

2

2

l

0000

1

1

1111

頁表1

0

5

000

9

101

1

8

000

0

7

5

000

6

0000

—

5

Tj

on

4

—

1

100

3

1

000

2

1

no

1

虛地址

1

001

0

8196

010

0JOJXO0L0J0OJ00LOLQJ00I110I0

2程序局部性原理:

在一段時間內(nèi)一個程序的執(zhí)行往往呈

現(xiàn)出高度的局部性，表現(xiàn)在時間與

空間兩方面。

時間局部性：

一條指令被執(zhí)行了，則在不久的將來

它可能再被執(zhí)行。

空間局部性：

若某一存儲單元被使用，則在一定

時間內(nèi)，與該存儲單元相鄰的單元

可能被使用。

3虛擬存儲技術(shù)

虛存：把內(nèi)存與外存有機(jī)的結(jié)合起來

使用，從而得到一個容量很大的

“內(nèi)存”，這就是虛存。

實(shí)現(xiàn)思想：當(dāng)進(jìn)程運(yùn)行時，先將一部

分程序裝入內(nèi)存，另一部分暫時留

在外存，當(dāng)要執(zhí)行的指令不在內(nèi)存

時,系統(tǒng)自動完成將它們從外存

調(diào)入內(nèi)存工作。

4.5.2虛擬頁式存儲管理

1基本工作原理

在進(jìn)程開始運(yùn)行之前，不是裝入全部

頁面，而是裝入一個或零個頁面，之

后根據(jù)進(jìn)程運(yùn)行的需要，動態(tài)裝入其

它頁面；當(dāng)內(nèi)存空間已滿，而又需要

裝入新的頁面時，則根據(jù)某種算法淘

汰某個頁面，以便裝入新的頁面。

2頁表表項(xiàng)

頁號駐爵位內(nèi)存塊號外存地址訪問位修改位

頁號、駐留位、內(nèi)存塊號、外存地址、訪問

位、修改位

駐留位（中斷位）：表示該頁是在內(nèi)存還是

在外存

訪問位：根據(jù)訪問位來決定淘汰哪頁（由不

同的算法決定）

修改位：查看此頁是否在內(nèi)存中被修改過

3缺頁中斷

在地址映射過程中，在頁表中發(fā)現(xiàn)所

要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁

中斷。操作系統(tǒng)接到此中斷信號后,

就調(diào)出缺頁中斷處理程序，根據(jù)頁

表中給出的外存地址，將該頁調(diào)入

內(nèi)存，使作業(yè)繼續(xù)運(yùn)行下去。

如果內(nèi)存中有空閑塊，則分配一頁，

將新調(diào)入頁裝入內(nèi)存，并修改頁表

中相應(yīng)頁表項(xiàng)目的駐留位及相應(yīng)的

內(nèi)存塊號。

若此時內(nèi)存中沒有空閑塊，則要淘汰

某頁，若該頁在內(nèi)存期間被修改過,

則要將其寫回外存。

4頁面淘汰算法

先進(jìn)先出頁面淘汰算法（FIFO）

選擇在內(nèi)存中駐留時間最長的頁并

淘汰之。

理想淘汰算法一最佳頁面算法（OPT）

淘汰以后不再需要的或最遠(yuǎn)的將來才

會用到的頁面。

最近未使用頁面淘汰算法（NRU）

選擇在最近一段時間內(nèi)未使用過的

一頁并淘汰之。

實(shí)現(xiàn)：設(shè)置訪問位（R）

修改位（M）

啟動一個進(jìn)程時，置0；R被定期清零。

發(fā)生缺頁中斷時，操作系統(tǒng)檢查R,M：

第0類：無訪問，無修改

第1類：無訪問，有修改

第2類：有訪問，無修改

第3類：有訪問，有修改

操作系統(tǒng)隨機(jī)從編號最小的非空類中

選擇一頁淘汰

最近最少使用頁面淘汰算法（LRU）

選擇最后一次訪問時間距離當(dāng)前時

間最長的一頁并淘汰之。

即淘汰沒有使用的時間最長的頁。

實(shí)現(xiàn)代價很高

硬件方法

LRU的軟件解決方案：

最不經(jīng)常使用（NFU）

選擇訪問次數(shù)最少的頁面淘汰之。

實(shí)現(xiàn)：軟件計(jì)數(shù)器，一頁一個，初值

為0。每次時鐘中斷時，計(jì)數(shù)器加R。

發(fā)生缺頁中斷時，選擇計(jì)數(shù)器值最

小的一頁淘汰。

改進(jìn)：計(jì)數(shù)器在加R前先右移一位

R位加到計(jì)數(shù)器的最左端

稱為老化算法。

第二次機(jī)會淘汰算法(SCR)

按照先進(jìn)先出算法選擇某一頁面,

檢查其訪問位，如果為0,則淘汰該

頁，如果為1,則給第二次機(jī)會，并

將訪問位置0。

例子1:計(jì)算缺頁次數(shù)

某程序在內(nèi)存中分配三個頁面，初始

為空，頁面走向?yàn)?,3,2,1,4,

3,5,4,3,2,1,5?

FIFO432143543215

頁1432143555211

頁243214333522

頁34321444355

xxxxxxxHlxxH

共缺頁中斷9次

LRU432143543215

頁1432143543215

頁243214354321

頁34321435432

xxxxxxxHBxxx

共缺頁中斷10次

OPT432143543215

頁1432111555211

頁243333333555

頁34444444444

IIxxxxHHxHHxxH

共缺頁中斷7次

例子2:計(jì)算缺頁次數(shù)

某程序在內(nèi)存中分配m頁初始為空，

頁面走向?yàn)?,2,3,4,1,2,5,

1,2,3,4,5O當(dāng)m=3,m=4時缺

頁中斷分別為多少？用FIFO算法。

例子2:計(jì)算缺頁次數(shù)

m=3時，缺頁中斷9次

m=4時，缺頁中斷10次

注：FIFO頁面淘汰算法會產(chǎn)生異?，F(xiàn)

象，當(dāng)分配給進(jìn)程的物理頁面數(shù)增

加時，缺頁次數(shù)反而增加。

5影響缺頁次數(shù)的因素

(1)分配給進(jìn)程的物理頁面數(shù)

(2)頁面本身的大小

⑶程序的編制方法

(4)頁面淘汰算法

例子3:內(nèi)存分配一頁，初始時第一■頁

在內(nèi)存，頁面大小為128個整數(shù)。

矩陣A128X128按行存放。

程序編制方法1：

Forj:=lto128

Fori:=lto128

A[iJ]:=0;

程序編制方法2:

Fori:=lto128

Forj:=lto128

A[i,jl：=0;

453性能問題

1顛簸（抖動）

在虛存中，頁面在內(nèi)存與外存之間頻

繁調(diào)度，以至于調(diào)度頁面所需時間

比進(jìn)程實(shí)際運(yùn)行的時間還多，此時

系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)

崩潰。這種現(xiàn)象為顛簸。

原因:

頁面淘汰算法不合理。

b分配給進(jìn)程的物理頁面數(shù)太少。

2工作集模型

基本思想：根據(jù)程序的局部性原理,

一般情況下進(jìn)程在一段時間內(nèi)總是

集中訪問一些頁面,這些頁面稱為

活躍頁面，如果分配給一個進(jìn)程的

物理頁面數(shù)太少了，使該進(jìn)程所需

的活躍頁面不能全部裝入內(nèi)存，則

進(jìn)程在運(yùn)行過程中則不斷發(fā)生中斷o

如果能為進(jìn)程提供與活躍頁面數(shù)相等

的物理頁面數(shù)，則可減少缺頁中斷

次數(shù)。

工作集:

對于給定的訪問序列選取定長的區(qū)間,

稱為工作集窗口，落在工作集窗口

中的頁面集合稱為工作集。

工作集:

內(nèi)容取決于頁的三個因素

a訪頁序列特性

b時刻Ti

C窗口長度(△)

例：

26157775162341234443434441327

占IL

ws(ti)={l,2,567}

ws(t2)={3,4}

4.5.4虛擬段式存儲管理

1段表內(nèi)容

增加：特征位（在/不在內(nèi)存，是否

可共享），存取權(quán)限位（讀，寫，

執(zhí)行），標(biāo)志位（是否修改過，能

否移動），擴(kuò)充位（固定長/可擴(kuò)充）

2越界中斷處理

進(jìn)程在執(zhí)行過程中，有時需要擴(kuò)大

分段，如數(shù)據(jù)段。由于要訪問的地

址超出原有的段長，所以發(fā)越界中

斷。操作系統(tǒng)處理中斷時，首先判

斷該段的“擴(kuò)充位”，如可擴(kuò)充，

則增加段的長度；否則按出錯處理。

3缺段中斷處理

檢查內(nèi)存中是否有足夠的空閑空間

a若有，則裝入該段，修改有關(guān)數(shù)據(jù)

結(jié)構(gòu)，中斷返回

b若沒有，檢查內(nèi)存中空閑區(qū)的總和

是否滿足要求，是則應(yīng)采用緊縮技

術(shù)，轉(zhuǎn)a;否則，淘汰一些段，轉(zhuǎn)a

4段的動態(tài)鏈接

大型程序：

若干程序段，若干數(shù)據(jù)段

一?些熟知的事實(shí)：

*進(jìn)程的某些程序段在進(jìn)程運(yùn)行期間

可能根本不用

*互斥執(zhí)行的程序段沒有必要同時駐

留內(nèi)存

*有些程序段執(zhí)行一次后不再用到

靜態(tài)鏈接：為了程序正確執(zhí)行，必須

連接裝配程序把它們連接成一個

可運(yùn)行的目標(biāo)程序，并在程序運(yùn)行

前都裝入內(nèi)存。

問題：花費(fèi)時間，浪費(fèi)空間

(1)段的動態(tài)鏈接

在程序開始運(yùn)行時，只將主程序段裝

配好并調(diào)入內(nèi)存，其它各段的裝配

是在主程序段的運(yùn)行過程中逐步完

成。每當(dāng)需要調(diào)用一個新段時，再

將這個新段裝配好，并與主程序段

鏈接。

頁式存儲管理：難以完成動態(tài)鏈接,

其邏輯地址是一維的?！?/p>

(2)鏈接間接字和鏈接中斷

機(jī)器指令：直接尋址，間接尋址

數(shù)據(jù)

直接尋址

間接尋址

數(shù)據(jù)

800

采用間接尋址時，間接地址指示的單

元的內(nèi)容稱為間接