第四章 存储器管理

——管理对象：内存
——功能：内存分配，地址映射，地址保护，内存扩充（虚拟存储概念）

1.存储器的多层结构

类型	内容
CPU寄存器	寄存器
主存	高速缓存、主存储器、磁盘缓存
辅存	固定磁盘、可移动存储介质

层次越高（越靠近CPU），存储介质访问速度越快，价格越高，存储容量越小。

寄存器和主存储器又被称为可执行存储器

2.程序的装入和链接

步骤：
(1)编译
(2)链接
(3)装入

程序的装入方式：
1.绝对装入方式。装入前指定位置（编译程序或程序员），只适用于单道处理环境。（程序运行前）

2.可重定位装入方式。目标模块的起始地址从0开始，装入时由装入模块进行静态地址重定位。可用于多道程序环境。（程序运行前）

3.动态运行时的装入方式。初装时不进行逻辑地址到物理地址的转换，程序可在内存中移动，地址转换推迟到程序真正运行时进行。——动态地址重定位（程序运行时） 需要重定位寄存器支持

程序的链接方式：
1.静态链接方式。程序装入运行前，个目标模块、库函数等已链接成一个完整的装配模块，以后不再拆开，即形成可执行文件。
2.装入时动态链接。将一组目标模块边装入边链接的链接方式。——优点：便于修改更新；便于实现对目标模块的共享。
3.运行时动态链接。将某些模块的链接推迟到模块要运行时才进行链接。——优点：可加快程序转入过程；节省大量内存空间；提供对动态链接库的支持。

3.连续分配方式

单一连续分配

固定分区分配

数据结构：分区使用表
划分方法：
(1)分区大小均等   缺乏灵活性,空间利用率低。内零头问题
(2)分区大小不同

动态分区分配

数据结构：空闲分区表、空闲分区链
动态分配算法：首次适应算法、最佳适应算法和最坏适应算法
解决内零头问题，产生碎片问题
如何实现地址映射——地址重定位寄存器的硬件支持
地址保护：界地址法、保护键法

回收内存三种情况:

4.基于顺序搜索的动态分区分配算法

(1)首次适应算法(FF)

空闲分区链递增次序链接，从链首到链尾顺序查找，未找到则分配失败。

• 优点：保留了高址部分的大空闲区，为以后到达的大作业分配大空间创造条件。
• 缺点：留下很多碎片。

(2)循环首次适应算法(NF)

从上次找到的空闲分区的下一个空闲分区开始查找，直至找到。如果到链尾还未找到，则返回第一个空闲分区。

• 优点：使内存中的空闲分区分布更均匀，减少查找开销。
• 缺点：缺乏大的空闲分区

(3)最佳适应算法(BF)

每次找最小的能满足要求的空闲分区，要求空闲分区链按量从小到大排列。

• 优点：可避免“大材小用”
• 缺点：看似最佳，宏观上不一定。会留下许多难以利用的碎片。

(4)最坏适应算法(WF)

每次挑最大的空闲分区。算法要求空闲分区链从大到小排列。

• 优点：查找效率高。分区查找方便。
• 缺点：当小作业把大空闲分区分小了，那么，大作业就找不到合适的空闲分区。

5.动态可重定位分区分配

动态重定位分区分配算法与动态分区分配算法相比，增加了紧凑功能。

6.对换

所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存上
对换类型：
(1)整体对换：在中级调度中以进程为单位
(2)页面(分段)对换

7.分页存储管理方式

空间划分

• 将一个用户进程的地址空间（逻辑空间）划分成若干个大小相等的区域，称为页或页面，各页从 0 开始编号。
• 内存空间也分成若干个与页大小相等的区域，称为块（物理块）或页框（frame） ，同样从 0 开始编号。

大-内零头大，小-页表大

内存分配

• 以块为单位，将进程中若干页装入到多个不相邻的块中，最后一页常装不满一块而出现页内碎片。

地址结构

已知逻辑地址求页号和页内地址

页表

分页系统中为每个进程配置一张页表，进程逻辑地址空间中的每一页，在页表中都对应有一个页表项。页表存放在内存中，属于进程的现场信息。
用途：1.记录进程的内存分配情况 2.实现进程运行时的动态重定位。
访问一个数据需访问内存 2 次 (页表一次，内存一次)

地址变换机构

基本的地址变换机构

• 逻辑地址 -> 物理地址 (页表寄存器PTR)
• 每个进程对应一页表，其信息（如长度、始址）放在PCB 中，执行时将其装入页表寄存器

地址变换例题
例1：若在一分页存储管理系统中，某作业的页表如下表所示，已知页面大小为 1024B，试将十进制逻辑地址 1011，2148，5012 转化为相应的物理地址。

设页号为 P，页内位移为 W，逻辑地址为 A，内存地址为 M，页面大小为 L，则
P = int ( A / L )
W = A mod L
对于逻辑地址 1011
P=int(1011/1024)=0
W=1011 mod 1024=1011
A=1011=(0,1011)
查页表第 0 页在第 2 块，所以物理地址为 M=1024*2+1011= 3059。

例2：存储器的用户空间共有 32 个页面，每页 1KB，内存16KB。假定某时刻系统为用户的第 0、1、2、3 页分别分配的物理块号为 5、10、4、7，试将逻辑地址 0A5C 和093C 变换为物理地址。

具有快表的地址变换机构

• 目的：为提高地址变换速度。
• 快表：又称为联想寄存器、联想存储器 (AssociativeMemory) 、IBM-TLB (Translation Lookaside Buffer)。
• 快表是一种特殊的高速缓冲存储器（Cache） ，内容是页表中的一部分或全部内容。
• CPU 产生逻辑地址的页号，首先在快表中寻找，若命中就找出其对应的物理块；若未命中，再到页表中找其对应的物理块，并将之复制到快表。若快表中内容满，则按某种算法淘汰某些页。
• 快表命中时访存1次，未命中时2次。

访问内存的有效时间

• 基本地址变换机构
  
• 具有快表的地址变换机构
  

8.分段存储管理方式

• 目的：满足用户的逻辑需求（方便编程、信息共享、信息保护、动态增长、动态链接）
• 逻辑地址形式：段号和段内地址（二维的）
  （注意：物理空间即内存空间总是一维的）
• 地址转换：段表寄存器实现的动态地址转换机构 要访问2次内存 — 段表、段内容
• 存储保护：段表长度和段长

分页和分段主要区别

相同点

• 都采用离散分配
• 都通过地址映射机构实现地址变换

不同点

• 页是信息的物理单位，段是信息的逻辑单位
• 页的大小固定且由系统决定，段的长度不固定
• 分页的用户程序地址空间是一维的，分段中是二维的

9.段页式存储管理方式

段式和页式的结合，取长补短

• 逻辑地址：二维的
• 数据结构：每个进程一张段表（页表地址和页表长度），每个段一张页表。
• 地址转换：段表寄存器实现的动态地址转换机构
  无快表时，获得数据或指令需访问3次内存