操作系统第五章复习

第五章 存储管理

物理地址： 把内存分成若干个大小相等的存储单元， 每个单元给一个编号， 这个编号称为内存地址 （物

理地址、绝对地址、实地址） ，存储单元占 8 位，称作字节（ byte ）。

物理地址空间： 物理地址的集合称为物理地址空间（主存地址空间） ，它是一个一维的线性空间。

程序地址： 用户编程序时所用的地址 （或称逻辑地址 、虚地址 ），基本单位可与内存的基本单位相同， 也可以不相同。

程序地址空间（逻辑地址空间、虚地址空间） : 用户的程序地址的集合称为逻辑地址空间，它的编址总 是从 0 开始的，可以是一维线性空间，也可以是多维空间。

存储管理的功能

1. 虚拟存储器

2. 地址变换

3. 内外存数据传输的控制

4. 内存的分配与回收

5. 内存信息的共享与保护

虚拟存储器

虚拟存储器的实现基础： 实验证明，在一个进程的执行过程中，其大部分程序和数据并不经常被访问。

实现原理： 把进程中那些不经常被访问的程序段和数据放入外存中， 待需要访问它们时再将它们调入内 存。

引入虚拟存储技术的好处

大程序：可在较小的可用内存中执行较大的用户程序； 大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存

（real memory） ； 并发：可在内存中容纳更多程序并发执行；

易于开发：不会影响编程时的程序结构

虚拟存储器—概念 将进程中的目标代码、数据等的虚拟地址（又称逻辑地址，相对地址）组成的虚拟空间称为虚拟存储器 （ Virtual

memory ）。

虚拟存储器不考虑物理存储器的大小和信息存放的实际位置， 只规定每个进程中互相关联的信息的相对 位置。

每个进程都有自己的虚拟存储器，通常是一个以 0 地址为始地址的一维（或多维）虚拟地址空间。 从虚拟地址空间到物理地址空间需要进行地址变换。

地址变换 物理地址空间是一维的，而虚拟地址空间可以是一维的，也可以是多维的。 当程序装入内存时 , 操作系统要为该程序分配一个合适的内存空间， 由于程序的逻辑地址与分配到内存 物理地址不一致，而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。 地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。

地址变换涉及两个问题：

虚拟空间的划分

地址重定位（地址映射）

地址重定位的方法：

静态地址重定位静态地址重定位是在程序装入内存时，完成从逻辑地址到物理地址的转换的。

优点： 实现简单，不要硬件的支持。

缺点 : (1) 程序一旦装入内存，移动就比较困难。

(2) 有时间上的浪费。

(3) 在程序装入内存时要将所有访问内存的地址转换成物理地址。

(4) 无法实现虚拟存储器。

动态地址重定位是在程序执行过程中，在 CPU 访问内存之前，将要访问的程序或数据地址转换成内存 地址。

动态地址重定位依靠硬件地址变换机构完成。

地址重定位机构需要一个(或多个)基地址寄存器 BR和一个(或多个)程序虚拟地址寄存器 VF。内

存地址MR与虚拟地址的关系为： MR=BR+VR 动态地址映射是由硬件在执行时完成的， 程序中不执行的程序就不做地址映射的工作， 这样节省了 CPU 的时间； 重定位寄存器的内容由操作系统用特权指令来设置，比较灵活； 实现动态地址映射必须有硬件的支持，并有一定的执行时间延迟。现代计算机系统中都采用动态地址 映射技术。

可以对内存进行非连续分配；

可以实现虚拟存储器；

有利于程序段共享。

控制内存和外存之间的数据流动的办法：

用户程序控制

主要由用户程序以覆盖技术进行内外存的数据交换。

操作系统控制

交换方式；

请求调入方式( on demand )；

预调入方式( on prefetch )

内存分配与回收的策略：

分配结构：登记使用情况，供分配程序使用的表格与链表。

放置策略：确定调入内存的程序和数据在内存中的位置。

交换策略：在需要将某个程序段和数据调入内存时，确定把内存中哪些程序段和数据调出内

存。

调入策略：外存中的程序段和数据按什么控制方式进入内存。 回收策略：确定回收时机和对所回收的内存区和已存在的内存空闲区进行调整。

内存信息的共享与保护

常用的存储保护有三种：

硬件法：上下界保护法。

软件法：保护键法。

软件与硬件结合：界限寄存器与与 CPU用户态或核心态工作方式结合。

: 在这种方式下，用户态进程只能访问那些在界限寄存器所规定的的内存区域，而核心态

进程则可以访问整个内存地址空间。

保护键法是一种软件保护法： 为每一个被保护的存储块分配一个单独的保护键， 在程序状态字中则设置相应的保护键开关 字段，对不同的进程赋予不同的开关代码和与被保护的存储块中的保护键进行匹配。2 •保护键法一举例

动态分区法也使用分区说明表、可用表、自由链、请求表等数据结构。

固定分区的分配与回收

分配：存储管理程序根据请求表查询分区说明表，从中找出一个满足要求的空闲分区，并将 其分配给申请者。

回收：当进程执行完毕，不再需要内存资源时，管理程序将对应的分区状态置为未使用

动态分区的分配与回收

主要解决三个问题：

(1) 对于请求表中的要求内存长度，从可用表或自由链中寻找出合适的空闲区分配 程序；

(2) 分配空闲区之后，更新可用表或自由链；

(3) 进程或作业释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自 由链。

动态分区的分配算法

最先适应法(first fit algorithm )

将可用表或自由链按起始地址递增次序排列；

一旦找到大于或等于所要求内存长度的分区，则结束搜索。

从所找到的分区中划岀所要求的内存长度给用户；

把余下的部分进行合并(如果有相邻空闲区存在)后留在可用表中。

最佳适应法(best fit algorithm )

将可用表或自由链按从小到大的递增次序排列；

找到第一个大于或等于所要求内存长度的分区，则停止查找。

从所找到的分区中划岀所要求的内存长度给用户；

把余下的部分进行合并（如果有相邻空闲区存在）后留在可用表中。

从而把所 内存 当曲程序状态字

幵关审节

IE确访问I

LOAD 1 I^IK)」L处加护

STOFII- 2 52IW开先字•讲匹配

41E确i/」h肛

LOAD 1 2S(M> 出错’

« 歼黄字■序叫配

可用表的每个表目记录一个空闲区。

自由链是利用每个内存空闲区的头几个单元存放本空闲区的大小及下一个空闲区的起始地址, 有空闲区链接起来，便于分配。

请求表的每个表目描述请求内存资源的作业或进程号以及所请求的内存大小。

阖可用表 (切忡由憾 御请求表 最坏适应法（worst fit algorithm ）

将可用表或自由链按从大到小的递减次序排列；

找到第一个大于或等于所要求内存长度的分区，则停止查找。若可用表或自由链的第一项长 度小于所要求的，则分配失败。

从所找到的分区中划岀所要求的内存长度给用户；

把余下的部分进行合并（如果有相邻空闲区存在）后留在可用表中。

算 配法（仙卜

fit）： ■佳區配法 fit）： 曇坏匹配法

（worst-fit）:

优 点 W算祛的井配和澤

放的时间

不需费对空闺区进

杼排駅.时 不瘪蜃新谓整空阳 区的 備找到量想空闺区.

从个别耒看，内轉

较大轉空 基本不谢下小空

阖分区.

缺 点 fit着低灌分区来詣

划分而产生较參小

分区，毎次分配时

査找时间开常会增

大. 从整体来看*会影

且这些外碎片很难

再檢利用祥

井配和何收时有復

大晝找 较大的空闺分崖

不被保留.

分配和團收时有

很大査找负抱*

关于内存扩充

可以使用覆盖和交换的内存扩充技术进行内存扩充。

分区存储管理的主要优缺点：

优点：

实现了内存共享，有利于多道程序设计，提高了内存利用率； 硬件支持少，管理算法简单，容易实现。

缺点：

内存利用率仍不高，小碎片难以利用；

进程大小受分区大小限制； 难以实现分区间的信息共享。

覆盖技术

原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。

将程序的必要部分（常用功能）的代码和数据常驻内存；

可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件） 在需要用到时才装入到内存；

不存在调用关系的模块不必同时装入到内存， 从而可以相互覆盖。（即不同时用的模

块可共用一个分区）

缺点:

编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度 从外存装入覆盖文件，以时间延长来换取空间节省。

交换技术 原理：暂停内存中执行的进程， 将整个进程的地址空间保存到外存的交换区中 (换出 swap out )，

而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列(换 入 swap

in )。 优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序 结构。

缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行 过程中地址访问的统计特性。

考虑的问题：

程序换入时的重定位； 减少交换中传送的信息量，特别是对大程序； 对外存交换区空间的管理：如动态分区方法。

页式管理

各进程的虚拟地址空间被划分成若干个长度相等的页( page)。页长的划分和内存外存之间

数据传输速度以及内存大小等有关，一般为 1-4K 。

物理内存空间也按页的大小划分为页面( page frame )。这些页面为系统中的任一进程所共 享。

页式管理把页式虚拟地址与内存物理地址建立一一对应的页表， 并用相应的硬件地址变换机 构，来解决离散地址变换。

页式管理采用请求调页或预调页技术实现了内外存存储器的统一管理。 静态页面管理方法：

在进程开始执行之前， 把该作业或进程的程序段和数据全部装入内存的各个页面中， 并通 过页表( page mapping table )和硬件地址变换机构实现虚地址到内存物理地址的地址映射。 优点：解决了分区管理时的碎片问题。

缺点： 由于静态页式管理要求进程或作业在执行前全部装入内存，如果可用页面数小于用 户要求时，该作业或进程只好等待。

作业或进程的大小仍受内存可用页面数的限制 动态页式管理

请求页式管理：当需要执行某条指令而又发现它不在内存时或当执行某条指令需要 访问其他的数据或指令时，这些指令或数据不在内存中，从而发生缺页中断，系统 将外存中相应的页面调入内存。

预调入页式管理：系统对那些在外存中的页进行调入顺序计算，估计出这些页中指 令和数据的执行和被访问的顺序，并按此顺序将它们顺次调入和调出内存。

由于页面置换算法选择不当，有可能产生刚被调出内存的页又要马上被调回内存，调回内存 不久又马上调出内存的局面，导致整个系统的页面调度非常频繁，大部分时间都花在内存和 外存之间的来回调入调出上，这种现象称为抖动。

随机淘汰算法 (random glongram) ：在系统设计人员无法确定哪些页被访问的概率较低时， 随机地选择某个用户的页面并将其换出将是一种明智的作法。

轮转法 (round robin) ：轮转法循回地换出内存可用区内一个可被换出的页，无论该页是刚 被换进还是已换进内存很长间。

先进先出 (FIFO) ：选择驻留内存时间最长的页淘汰