存储管理课件

第四章存储管理

4.1概述

4.2段式存储管理

4.3页式存储管理

4.4段页式存储管理

4.5虚拟存储

4.6交换技术与覆盖技术

重要资源

“瓶颈”：关键、紧张

帕金森定律

4.1概述

4.L1存储体系

存储器的层次结构:

Cache

主存

磁盘

高速缓存Cache:

少量的、非常快速、昂贵、易变的

内存RAM:

若干兆字节、中等速度、中等价格、

易变的

磁盘：

数百兆或数千兆字节、低速、价廉、

不易变的

力操作系统协调这些存储器的使用

重要性：直接存取要求内存速度尽量

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

能装下当前运行的程序与数据，否

则CPU执行速度就会受到内存速度

和容量的影响而得不到充分发挥。

内存:

是由存储单元（字节或字）组成的

一维连续的地址空间，简称内存空

间。用来存放当前正在运行程序的

代码及数据，是程序中指令本身地

址所指的、亦即程序计数器所指的

存储器。

内存可以分为：

系统区：用于存放操作系统

用户区：用于装入并存放用户程序

和数据。

4.1.2存储管理目的

用户对内存的使用要求

1充分利用内存，为多道程序并发执行

提供存储基础。

2尽可能方便用户使用

自动装入用户程序

用户程序中不必考虑硬件细节

3系统能够解决程序空间比实际内存空

间大的问题

4程序在执行时可以动态伸缩

5内存存取速度快

6存储保护与安全

7共享与通信

8了解有关资源的使用状况

9实现的性能和代价

4.1.3存储管理的任务

前提：引入多道程序设计技术

满足用户要求

1内存空间的管理、分配与回收

记录内存的使用情况

----设置相应的内存分配表

（内存分配回收的依据）

内存空间划分问题？

静态或动态，等长或不等长

内存空间的管理、分配与回收

内存分配表

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

个空闲页面(0:空闲，1:占用)。

1I0|……|1||0；

第0页第1页第i页第n-1页

内存空间的管理、分配与回收

空闲克面装:包括首页面号和页面个

数，连续若干的页面作为一组登记在

表中

空闲衣装:空闲块首址和空闲块长度,

没有记录的区域即为进程所占用

空闲块链将所有的空闲块链成一

个链表

内存空间的管理、分配与回收

确定分配算法

实施内存分配

回收内存

分配回收方式:静态分配与动态分配

内存空间的管理、分配与回收

连续性;离散性

驻留性；交换性

一次性；多次性

2存储共享

内存共享：两个或多个进程共用内存

中相同区域

的:

节省内存空间，提高内存利用率

实现进程通信（数据共享）

共享内容：

代码共享，要求代码为纯代码

数据共享

3存储保护与安全

保护目的:

为多个程序共享内存提供保障，使在

内存中的各道程序，只能访问他自己

的区域，避免各道程序间相互干拢,

特别是当一道程序发生错误时，不致

于影响其它程序的运行。通常由硬

件完成保护功能,软件辅助实现。

（特权指令不能完成存储保护。）

存储保护

保护系统程序区不被用户侵犯

（有意或无意的）

不允许用户程序读写不属于自己地址

空间的数据

（系统区地址空间，其它用户

程序的地址空间）

保护过程一防止地址越界

每个进程都有自己独立的进程空间,

如果哪个进程在运行时所产生的地

址在其地址空间之外，则发生地址

越界。即当程序要访问某个内存单

元时，由硬件检查是否允许，如果

允许则执行，否则产生地址越界中

断，由操作系统进行相应处理。

保护过程一防止地址越界

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

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

限长寄存器：存放长度

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

保护过程—防止操作越权

对于允许多个进程共享的存储区

域，每个进程都有自己的访问权限。

如果一个进程对共享区域的访问违

反了权限规定，则发生操作越权。

即读写保护。

4内存“扩充”

通过虚拟存储技术实现

用户在编制程序时，不应该受内

存容量限制，所以要采用一定技术

来"扩充”内存的容量，使用户得到

比实际内存容量大的多的内存空间。

内存“扩充”

具体实现是在硬件支持下，软硬

件相互协作，将内存和外存结合起

来统一使用。通过这种方法把内存

扩充，使用户在编制程序时不受内

存限制。

5地址映射(地址重定位，地址变换)

(1)逻辑地址(相对地址，虚地址)

(2)物理地址(绝对地址，实地址)

(3)地址映射

源程序0逻辑地址空间物理地址空间

⑴逻辑地址（相对地址，虚地址）

用户的程序经过汇编或编译后形成目

标代码，目标代码通常采用相对地

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

中的地址都相对于首地址而编址。

不能用逻辑地址在内存中读取信息。

(2)物理地址(绝对地址，实地址)

内存中存储单元的地址，可直接寻址。

⑶地址映射

为了保证CPU执行指令时可正确访问

存储单元，需将用户程序中的逻辑

地址转换为运行时由机器直接寻址

的物理地址，这一^过程称为地址映

射。

逻辑地址空间BR物理地址空间

00

100

1100

200

1200

1300

300

原因：当程序装入内存时，操作系统

要为该程序分配一个合适的内存空

间，由于程序的逻辑地址与分配到

内存物理地址不一致，而CPU执行指

令时，是按物理地址进行的，所以

要进行地址转换。

静态重定位

当用户程序被装入内存时，一次性

实现逻辑地址到物理地址的转换，

以后不再转换（一般在连接短配时

由软件完成）。

动态重定位

在程序运行过程中要访问数据时再进

行地址变换（即在逐条指令执行时

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

此工作由硬件地址映射机制来完成。

硬件支持，软硬件结合完成）。

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

4.1.4各种存储管理方案

单一用户（连续区）存储管理：

单用户系统在一段时间内，只有

一个进程在内存，故内存分配管理

十分简单，内存利用率低。内存分

为两个区域，一个供操作系统使用,

一个供用户使用。

OxFFF...

ROM中的

用户程序位于RAM中的

设备驱动程序

操作系统

用户程序

位于RAM中的用户程序

位于RAM中的

操作系统

操作系统

000

分区存储管理方案

系统把内存用户区划分为若干分区，

分区大小可以相等，也可以不等。—

个进程占据一个分区。

固定分区

可变分区

固定分区

预先把可分配的主存储器空间分割

成若干个连续区域，称为一个分区。

每个分区的大小可以相同也可以不

同，如图所示。但分区大小固定不

变，每个分区装一个且只能装一个

作业。

存储分配：如果有一个空闲区，则分

配给

固定分区

内存管理：设置内存分配表

分区号起始地址长度状态进程名

内存分配：

内存回收：简单

缺点：内存利用率不高

可变分区

内存的分配：内存不是预先划分好的,

而是当作业装入时，根据作业的需

求和内存空间的使用情况来决定是

否分配。若有足够的空间，则按需

要分割一部分分区给该进程；否则

令其等待主存空间。

内存的管理：

设置内存空闲块表——记录了空闲区

起始地址和长度。

内存分配：动态分配

内存的回收：当某一块归还后，前后空

间合并，修改内存空闲块表。

内存分配：三种分配算法

首先适配算法:

当接到内存申请时，查空闲块表，找

到第一个不小于请求的空块，将其

分割并分配。

（特点：简单、快速分配）

最佳适配算法:

接到内存申请时，在空闲块表中找到

一个不小于请求的最小空块进行分

配。

（特点：用最小空间满足要求）

最坏适配算法

接到内存申请时，在空闲块表中找到

一个不小于请求的最大空块进行分

配。

（特点：当分割后空闲块仍为较大空

块）

碎片问题:

经过一段时间的分配回收后，内存中

存在很多很小的空闲块。它们每一

个都很小，不足以满足分配要求；

但其总和满足分配要求。这些空闲

块被称为碎片。

造成存储资源的浪费

碎片问题的解决:

紧凑技术：通过在内存移动程序，将

所有小的空闲区域合并为大的空闲区

域。

（紧缩技术，紧致技术，浮动技术，

搬家技术）

问题：开销大；移动时机

讨论：

优点：A便于动态申请内存

B便于共享内存

C便于动态链接

缺点：碎片问题（外碎片）

4.2段式存储管理

421基本思想（工作原理）

0

CALL[X][E]

子程序段[X]数组[A]

CALL[Y][F]

CALL[A]116

K

子程序段[Y]工作区段[B]

主程序段[M]

p

N

用户程序划分

按程序自身的逻辑关系划分为若干个

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

且有一个段号。段号从0开始，每一

段也从0开始编址，段内地址是连续

的。

逻辑地址

段号段内地址

内存划分

内存空间被动态的划分为若干个长度

不相同的区域，这些区域被称为物

理段，每个物理段由起始地址和长

度确定。

内存分配

以段为单位分配内存，每一个段在内

存中占据连续空间（内存随机分割,

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

可以不连续存放。

4.2.2管理

段号段首址段长度

0120K

1100K110K

2260K220K

段表:

它记录了段号，段的首（地）址和

长度之间的关系。

每一个程序设一个段表

空闲块管理:

记录了空闲区起始地址和长度。

内存的分配算法:

首先适配；最佳适配；最坏适配

4.2.3硬件支持

一对寄存器

段表始址寄存器：

用于保存正在运行进程的段表的

始址。

段表长度寄存器：

用于保存正在运行进程的段表的

长度（例如上图的段表长度为3）。

相联（联想）存储器

介于内存与寄存器之间的存储机制,

它又叫快表。

用途：保存正在运行进程的段表的子

集（部分表项）。

特点：按内容并行查找。

引入快表的作用：

为了提高地址映射速度。

快表项目：段号；段始址；段长度；

标识（状态）位；访问位，淘汰位。

快表淘汰问题?

4.2.4段的共享

作业

4.2.5段的保护

作业

优点：

便于动态申请内存

管理和使用统一化

便于共享

便于动态链接

缺点：产生碎片

与可变分区存储管理方案区别

4.3页式存储管理

4.3.1基本思想（工作原理）

用户程序划分

把用户程序按逻辑页划分成大小相等

的部分，称为页。从0开始编制页号,

页内地址是相对于0编址。

逻辑地址

页号页内地址

用户程序的划分是由系统自动完成

的，对用户是透明的。一般，一页

的大小为2的整数次第，因此，地址

的高位部分为页号，低位部分为页

内地址。

内存空间:

按页的大小划分为大小相等的区域,

称为内存块（又叫物理页面）。

内存分配:

以页为单位进行分配，并按作业的页

数多少来分配。逻辑上相邻的页，

物理上不一定相邻。

作业的

地址空间

表主存中页框

（物理块）

4.3.2管理

L页表：系统为每个进程都建立了一

个页表，页表给出逻辑地址号和具

体内方块号相应的关系

2.空块管理——总页表

3.内存的分配与回收

计算一个作业所需要的总块数

O

查总页表，看看是否还有N个空闲块。

如果有相应空闲块，则页表长度为该

为N,可填入PCB中。（申请页表区,

把页表始址填入PCB）。

分配N个空闲块，将块号和页号填入

页表（页表号实际不用填）。

修改总页表。

4.3.3硬件支持

1.一对寄存器：

a页表始址寄存器

b页表长度寄存器

2.相联寄存器---决表

1）页号2）页在内存的块号3）标

识位4）淘汰位

地址映射机制物理地址

434页的共享

作业

435页的保护

作业

4.3.6优缺，乞

优点：a解决了碎片问题

b便于管理

缺点：a不易实现共享

b不便于动态连接

4.4段页式存储管理

4.4.1产生背景及基本思想

背景：结合了二者优点

克服了二者的缺点

基本思想：

用户程序划分：按段式划分（对用户

来讲，按段的逻辑关系进行划分；

对系统讲，按页划分每一段）

逻辑地址:

段号段肉痣址

员专员内也址

内存划分：按页式存储管理方案

内存分配：以页为单位进行分配

4.4.2管理

1段表：记录了每一段的页表始址和

页表长度

2页表：记录了逻辑页号与内存块号

的对应关系。（每一段有一个，一

个程序可能有多个页表）

3空块管理：

4分配：同页式管理

4.4.3硬件支持

段表始址寄存器

段表长度寄存器

相联存储器（快表）

4.5虚拟存储

连续性；离散性

驻留性；交换性

一次性；多次性

以CPU时间和外存空间换取昂贵内存

空间，这是操作系统中的资源转换技

术

4.5.1概述

1问题的提出：

a程序大于内存

b程序暂时不执行或运行完是否还

要占用内存。

虚拟存储器的基本思想是：程序、数

据、堆栈的大小可以超过内存的大小,

操作系统把程序当前使用的部分保留

在内存，而把其它部分保存在磁盘上,

并在需要时在内存和磁盘之间动态交

换。

虚拟存储器支持多道程序设计技术。

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程序局部性原理:

在一段时间内一个程序的执行往往呈

现出高度的局部性，表现在时间与

空间两方面。

时间局部性：

一条指令被执行了，则在不久的将来

它可能再被执行。

空间局部性：

若某一存储单元被使用，则在一定

时间内，与该存储单元相邻的单元

可能被使用。

3虚拟存储技术

虚存：把内存与外存有机的结合起来

使用，从而得到一个容量很大的

“内存”，这就是虚存。

实现思想：当进程运行时，先将一部

分程序装入内存，另一部分暂时留

在外存，当要执行的指令不在内存

时,系统自动完成将它们从外存

调入内存工作。

4.5.2虚拟页式存储管理

1基本工作原理

在进程开始运行之前，不是装入全部

页面，而是装入一个或零个页面，之

后根据进程运行的需要，动态装入其

它页面；当内存空间已满，而又需要

装入新的页面时，则根据某种算法淘

汰某个页面，以便装入新的页面。

2页表表项

页号驻爵位内存块号外存地址访问位修改位

页号、驻留位、内存块号、外存地址、访问

位、修改位

驻留位（中断位）：表示该页是在内存还是

在外存

访问位：根据访问位来决定淘汰哪页（由不

同的算法决定）

修改位：查看此页是否在内存中被修改过

3缺页中断

在地址映射过程中，在页表中发现所

要访问的页不在内存，则产生缺页

中断。操作系统接到此中断信号后,

就调出缺页中断处理程序，根据页

表中给出的外存地址，将该页调入

内存，使作业继续运行下去。

如果内存中有空闲块，则分配一页，

将新调入页装入内存，并修改页表

中相应页表项目的驻留位及相应的

内存块号。

若此时内存中没有空闲块，则要淘汰

某页，若该页在内存期间被修改过,

则要将其写回外存。

4页面淘汰算法

先进先出页面淘汰算法（FIFO）

选择在内存中驻留时间最长的页并

淘汰之。

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

淘汰以后不再需要的或最远的将来才

会用到的页面。

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

选择在最近一段时间内未使用过的

一页并淘汰之。

实现：设置访问位（R）

修改位（M）

启动一个进程时，置0；R被定期清零。

发生缺页中断时，操作系统检查R,M：

第0类：无访问，无修改

第1类：无访问，有修改

第2类：有访问，无修改

第3类：有访问，有修改

操作系统随机从编号最小的非空类中

选择一页淘汰

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

选择最后一次访问时间距离当前时

间最长的一页并淘汰之。

即淘汰没有使用的时间最长的页。

实现代价很高

硬件方法

LRU的软件解决方案：

最不经常使用（NFU）

选择访问次数最少的页面淘汰之。

实现：软件计数器，一页一个，初值

为0。每次时钟中断时，计数器加R。

发生缺页中断时，选择计数器值最

小的一页淘汰。

改进：计数器在加R前先右移一位

R位加到计数器的最左端

称为老化算法。

第二次机会淘汰算法(SCR)

按照先进先出算法选择某一页面,

检查其访问位，如果为0,则淘汰该

页，如果为1,则给第二次机会，并

将访问位置0。

例子1:计算缺页次数

某程序在内存中分配三个页面，初始

为空，页面走向为4,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:计算缺页次数

某程序在内存中分配m页初始为空，

页面走向为1,2,3,4,1,2,5,

1,2,3,4,5O当m=3,m=4时缺

页中断分别为多少？用FIFO算法。

例子2:计算缺页次数

m=3时，缺页中断9次

m=4时，缺页中断10次

注：FIFO页面淘汰算法会产生异常现

象，当分配给进程的物理页面数增

加时，缺页次数反而增加。

5影响缺页次数的因素

(1)分配给进程的物理页面数

(2)页面本身的大小

⑶程序的编制方法

(4)页面淘汰算法

例子3:内存分配一页，初始时第一■页

在内存，页面大小为128个整数。

矩阵A128X128按行存放。

程序编制方法1：

Forj:=lto128

Fori:=lto128

A[iJ]:=0;

程序编制方法2:

Fori:=lto128

Forj:=lto128

A[i,jl：=0;

453性能问题

1颠簸（抖动）

在虚存中，页面在内存与外存之间频

繁调度，以至于调度页面所需时间

比进程实际运行的时间还多，此时

系统效率急剧下降，甚至导致系统

崩溃。这种现象为颠簸。

原因:

页面淘汰算法不合理。

b分配给进程的物理页面数太少。

2工作集模型

基本思想：根据程序的局部性原理,

一般情况下进程在一段时间内总是

集中访问一些页面,这些页面称为

活跃页面，如果分配给一个进程的

物理页面数太少了，使该进程所需

的活跃页面不能全部装入内存，则

进程在运行过程中则不断发生中断o

如果能为进程提供与活跃页面数相等

的物理页面数，则可减少缺页中断

次数。

工作集:

对于给定的访问序列选取定长的区间,

称为工作集窗口，落在工作集窗口

中的页面集合称为工作集。

工作集:

内容取决于页的三个因素

a访页序列特性

b时刻Ti

C窗口长度(△)

例：

26157775162341234443434441327

占IL

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

ws(t2)={3,4}

4.5.4虚拟段式存储管理

1段表内容

增加：特征位（在/不在内存，是否

可共享），存取权限位（读，写，

执行），标志位（是否修改过，能

否移动），扩充位（固定长/可扩充）

2越界中断处理

进程在执行过程中，有时需要扩大

分段，如数据段。由于要访问的地

址超出原有的段长，所以发越界中

断。操作系统处理中断时，首先判

断该段的“扩充位”，如可扩充，

则增加段的长度；否则按出错处理。

3缺段中断处理

检查内存中是否有足够的空闲空间

a若有，则装入该段，修改有关数据

结构，中断返回

b若没有，检查内存中空闲区的总和

是否满足要求，是则应采用紧缩技

术，转a;否则，淘汰一些段，转a

4段的动态链接

大型程序：

若干程序段，若干数据段

一•些熟知的事实：

*进程的某些程序段在进程运行期间

可能根本不用

*互斥执行的程序段没有必要同时驻

留内存

*有些程序段执行一次后不再用到

静态链接：为了程序正确执行，必须

连接装配程序把它们连接成一个

可运行的目标程序，并在程序运行

前都装入内存。

问题：花费时间，浪费空间

(1)段的动态链接

在程序开始运行时，只将主程序段装

配好并调入内存，其它各段的装配

是在主程序段的运行过程中逐步完

成。每当需要调用一个新段时，再

将这个新段装配好，并与主程序段

链接。

页式存储管理：难以完成动态链接,

其逻辑地址是一维的。】

(2)链接间接字和链接中断

机器指令：直接寻址，间接寻址

数据

直接寻址

间接寻址

数据

800

采用间接寻址时，间接地址指示的单

元的内容称为间接