操作系统基础（三）内存

基础

程序装入和链接

• 编译：编译程序将源代码编译成若干目标模块
• 链接：链接程序把各个目标模块，包括外部库函数链接在一起
• 装入：由装入程序将装入模块装入内存中运行

其中链接分为三种： 静态链接 装入时动态链接：装入时边装入边链接 运行时动态链接：执行时才链接

装入也分为三种： 绝对（静态）装入：在编程阶段就把物理地址计算好 可重定位装入：有一个逻辑地址到物理地址的映射，之后不能变 动态重定位装入：运行时才转换，之后可以变

地址绑定

将指令和数据绑定到内存地址有三种情况：

• 编译时：生成绝对代码，编译时就知道了进程在内存中的驻留地址，所生成的编译代码就可以从该位置往后扩展（开始位置发生变化就要重新编译）
• 加载时：生成可重定位代码
• 执行时：绑定延迟到执行时才进行

物理地址: 内存地址寄存器中的地址，又叫绝对地址、实地址

逻辑地址: CPU生成的地址，又叫相对地址、虚地址（用户程序在经过汇编后目标代码常用，把首地址设为0，后面是相对地址）

编译和加载时的地址绑定方法生成相同逻辑地址和物理地址，而执行时的地址绑定方案生成不同的逻辑和物理地址，这种情况通常称逻辑地址为虚拟地址

运行时从虚拟地址到物理地址的映射由内存管理单元来完成

内存映射与保护

内存通常分为两个区域：用于驻留操作系统和用于用户进程

为输入队列中需要调入内存的进程分配内存空间，采用连续内存分配，每个进程位于一个连续的区域

逻辑地址通过界限地址寄存器（判断是否合理）、重定位寄存器（加一个基地址）映射到物理地址，定位到内存

内存保护：

（1）界地址保护

1. 设置地址上界寄存器、下界寄存器的地址检查机制
2. 基址、限长寄存器和动态地址转换机构

CPU所能访问的存储器只有内存和CPU内的寄存器，因此执行指令以及指令使用的数据必须在这些可访问的存储设备中，否则就要在CPU使用前把数据移到内存中

确定进程只能访问其合法范围，通过基地址寄存器和界限地址寄存器可以做到：

基地址寄存器：a 界限地址寄存器：b 那么程序可以访问a~a+b的所有地址

寄存器 $\to$ cache $\to$ 内存 $\to$ 外存

交换

进程可以暂时从内存中交换到辅存上（换出），需要再次执行时再调回内存中（换入）

处于阻塞或者优先级低，会被换出，优先级更改会被换入

连续内存分配

内存分配

单一连续分配：分为系统区用户区，简单但是只适用于单用户 固定分区分配：用户空间划分好多个分区（分为大小均相同分区和大小不相同分区两种） 动态分区分配：用户空间一开始不划分，而是在装入内存时根据进程大小动态建立分区

以下都是讨论动态分区（可变分区）：

从一组可用孔中选择一个合适的空闲孔的方法：

• 首次适应：分配第一个足够大的孔（空闲分区链以地址递增顺序链接）
• 最佳适应：分配最小的足够大的孔（空闲分区链按长度递增顺序链接）
• 最差适应：分配最大的孔

首次适应被认为既是最简单的，也是最好最快，最佳和最差容易生成小碎片（不要被最佳的名字忽悠，这家伙性能很差，会产生最多的外部碎片）

分区式存储管理优缺点： 优点：

1. 便于动态申请内存
2. 便于共享内存
3. 便于动态链接

缺点：

1. 碎片问题，内存利用率不高

碎片

内部碎片：固定分区方法会有内部碎片，程序所占空间小于分给它的空间，内部空间的间隙为内部碎片

外部碎片：动态分区随着进程装入和移出内存，空闲内存被分为小片段，中间产生的空隙为外部碎片，首次适应和最佳适应都会有这种外部碎片问题

解决外部碎片的方法：

1. 紧缩，仅在重定位是动态并在运行时可用，把所有的孔移到一段，开销较大（可重定位分区）
2. 允许物理地址非连续，只要有物理内存就能为进程分配，有两种互补的实现技术：分页、分段、段页

分页

以上是连续内存分配管理方式，接下来的分页和分段是非连续内存分配管理方式 连续分配方式，比如说一个需要1GB的程序，就必须要去内存找一块连续的1G空闲区间分配给它，而非连续分配方式可以分散地给这段程序分配内存空间

分页不会产生外部碎片，每个进程平均产生半个块大小的内部碎片（很小的）

把物理内存分为固定大小的块，称为帧，也叫物理块 把逻辑内存分为同样大小的块，称为页

每个地址分为页号p和偏移d，前面的页号经过页表变成内存块号，后面的页内偏移直接对过去

页表：为每个进程建立一张页表，将进程的每一页离散地储存在内存的物理块中（页号→块号）

举个例子：

说明总共有2²⁰页（也就是1M页），每页2¹²大小（也就是4KB）

采用分页技术不会产生外部碎片，但是会有内部碎片，产生的原因是进程所需内存不是页的整数倍，最后一页可能装不满最后一个帧（物理块），导致产生页内碎片

分页的一个重要特点是用户视角的内存和实际物理内存的分离，用户看到的是一整块内存用于一个进程，但实际的物理内存则是分散的，逻辑地址到物理地址的映射用户不知道。

用户进程不能访问该进程非占用的内存，即无法访问页表规定之外的内存

页表的初始地址放在寄存器中

快表

快表（TLB）是一种高速缓冲寄存器，加速地址变换过程，通常采用TLB + 页表的形式

每次要访存两次，为了提高速度，加入TLB（快表），本质是一个cache，可以看成是页表的子集，里面不是连续存储

TLB由键和值组成，包括页表中的一小部分条目，逻辑地址的页号提交给TLB，如果命中那么直接得到帧号，否则就访问页表（TLB失效），同时把页号和帧号加入到TLB中

快表的有效性基于局部性原理

页号在TLB中被查找到的几率称为命中率，有效内存访问时间要按加权计算

保护：每个帧有相关联的保护位

共享页：可以共享公共代码

二级页表和多级页表：把页表再一步离散化，用页表再映射页表

分段

支持用户视角的内存管理方案，逻辑地址空间由一组段组成，分段地址中的地址包括段号和段内偏移，用户通过段号和段内偏移来指定地址 <segment-number, offset>

为每个段分配一个连续的分区

段表可以把二维数组定位到一维物理地址，每个段在段表中占一个表项，记录了该段在内存中的起始地址和段的长度（防止越界），段内地址不能大于段长

段表示例：

硬件支持：一对寄存器（段表基址寄存器和段表长度寄存器）

也可以加快表，逻辑和页表类似

分页和分段的比较

页是信息的物理单位，是出于系统管理的需要； 页的大小固定且由系统确定，由硬件实现，系统中的页只能有一种大小； 分页的作业地址空间是一维的

段是信息的逻辑单位，是出于用户的需要； 段的长度不固定，取决于用户编写的程序的，通常由编译程序在对源程序进行编译时，根据信息的性质来划分； 分段的作业地址空间是二维的，除了要给出段名还要给出段长

段页式

段号+段内页号+页内地址

首先被分为若干个逻辑段，每一段都有自己的段号，然后在里面分页

段页式中，一个进程对应一张段表，每个段对应一张页表

需要三次访问：第一次访问段表，第二次访问页表，第三次访问指令/数据的实际地址

段页式的地址空间是二维的

用分段方法来分配和管理用户地址空间，用分页方法来管理物理存储空间

Tips：

• 链接完成重定位，形成逻辑地址，装载完成从逻辑地址到物理地址的变换
• 内存保护需要操作系统和硬件机构合作完成
• 固定分区、分页、段页都有内部碎片，不过分段没有内部碎片
• 页式管理划分的页面大小是相等的

虚拟内存

引入原因：暂时不运行和运行完的程序仍然占用内存

虚拟内存技术允许执行进程不必完全在内存中，程序可以比物理内存大，将用户逻辑内存与物理内存分开

虚拟存储器：具有请求调入和置换的功能，能从逻辑上对内存容量加以扩充的一种储存系统，其运行速度接近内存，成本又接近外存

虚拟内存特征：多次性、对换性、虚拟性

局部性原理

时间局部性原理：

程序中的某一条指令一旦执行，不久以后该指令可能再次执行；某个数据被访问过，不久以后该数据可能再次被访问

空间局部性原理：

某个储存单元被访问，不久之后其附近的储存单元也将被访问，一段时间内访问的地址可能集中在一定的范围内

虚拟内存的实现

请求分页储存管理 请求分段储存管理 请求段页式储存管理

请求分页管理方式

页表机制扩充：

• 状态位P
• 访问位A
• 修改位M
• 外存地址

缺页中断

在请求分页系统中，每当所要访问的页面不在内存时，就会产生缺页中断

页面置换算法

1. 最佳置换算法（OPT）

选择的被淘汰的页面是之后最长时间内不再访问的，可以保证最低的缺页率，但是无法预知未来所以无法实现，可以拿来测量其他算法

谁最后访问，先换掉谁

2. 先进先出算法（FIFO）

优先淘汰最早进入内存的页面，因为不符合实际规律，用的比较少

谁呆的时间最长，先换掉谁

★ 3. 最近最久未使用算法（LRU）

选择过程： 第一行从后往前数n个（n是物理块数），跳过重复的，那个就是要被替换的

比如上面例子第八列的4，往前数3个 0→3→2（重复的0跳过了），那么就替换2 第十列的3，往前数3个 2->4->0，就替换0

4. Clock算法

页面分配策略

驻留集大小

驻留集大小确定方式： 固定分配：给进程分配一定空间的物理块，后面不可变，即驻留集大小不变 可变分配：给进程分配的物理块在运行期间可以改变 局部置换：发生缺页时只能置换自己的物理块 全局置换：可以置换自己的，也可以置换其他进程的

有三种组合方式： 固定分区局部置换：初始分配固定数量，缺点是很难确定初始分多少 可变分区全局置换：只要缺页就会获得新的物理块，确定是之后缺页率会增多 可变分区局部置换：根据发生缺页的频率来动态改变进程的物理块

调入页面的时机

预调页策略：一次调入若干个相邻的页（根据局部性原理），不过成功率不高，一般是运行前采用 请求调页策略：在缺页时调入，每次调一页，I/O开销大，一般是运行期间采用

从何处调入页面

1. 有足够的对换区空间：全部从对换区调入所需页面，进程运行之前把所有有关文件从文件区复制到对换区
2. 没有足够的对换区空间：不会修改的文件直接从文件区调入，要修改的就得先去对换区

抖动

页面置换中最糟糕的情况：刚换出的页面马上又要换入主存，刚换入的页面马上又要换出，这种频繁的调度称为抖动或颠簸

Tips

• 虚拟内存的实现只能建立在离散分配的内存管理的基础上
• 虚拟内存技术是补充内存逻辑空间的技术
• 虚拟储存器理论逻辑上的最大容量由地址长度决定，实际上可能的最大容量为理论最大容量和内存外存和之中较小的那一个
• 所有的调度策略都不可能完全避免抖动