3.1_内存管理概念

内存相关概念

视频讲解：内存基本概念

程序执行前需要先放到内存中才能被CPU处理。内存是为了缓和CPU与外存之间的速度矛盾。

内存地址从0开始，每一个地址对应一个存储单元（用于存放数据的最小单元）。

若计算机按字节编址，则每个存储单元大小为一字节（1B），即8个二进制位；
若计算机按字编址，且字长为16位，则存储单元大小为一个字长，即16个二进制位。

千字节 (KB): \(2^{10}\) 字节 = 1 KB

兆字节 (MB): \(2^{20}\) 字节 = 1 MB

吉字节 (GB): \(2^{30}\) 字节 = 1 GB

按字节编址的含义是一个地址对应的空间大小是一个字节

内存管理的基本原理和要求

视频讲解：指令的工作原理

逻辑地址与物理地址

逻辑地址：相对于进程的起始地址而言的地址

物理地址：实际在内存中的地址

在程序中，一般使用的是逻辑地址。

程序的装入和链接

视频讲解：从写程序到运行

创建进程时，通常需要将程序和数据装入内存，这一过程通常包含以下几个步骤：

编译：将高级语言翻译为机器语言，形成一组目标模块
链接：形成逻辑地址，将编译后的的目标模块与所需的静态库一起，形成一个完整的装入模块
- 静态链接：在程序执行前将各目标模块及其所需库函数组成一个完整的装入模块
- 装入时动态链接：在各目标模块装入时，一边装入一边链接
- 运行时动态链接：在程序执行到相应目标模块时，才进行链接
  - 便于修改和更新
  - 便于实现对目标模块的共享
视频讲解：链接
装入：将装入模块装入内存运行（逻辑地址→物理地址）
- 绝对装入：若已经知道程序将在内存的哪个位置运行，则编译时就将逻辑地址转换为物理地址
  - 灵活性很差，只适用于单道程序环境
- 静态重定位（可重定位装入）：对所有的逻辑单元进行重定位，将其转化为物理地址
  - 必须要一次全部装入内存（一次分配所需的全部内存）
  - 逻辑地址必须是连续的
  - 程序运行期间不能再次移动
- 动态重定位（动态运行时装入）：设置一个重定位寄存器，里面存放程序的起始地址。程序执行时，会将逻辑地址与重定位寄存器中的值相加得到物理地址
  - 允许程序在内存中移动
  - 可以分配到不连续的区域中
  - 可以动态的分配内存

视频讲解：程序的装入方式

内存管理的功能

视频讲解：内存管理

内存空间的分配与回收：主存储器空间的分配与管理
地址转换：逻辑地址到物理地址
内存空间的扩展：虚拟化
存储保护：保护各个作业只能访问自己的内存空间

内存保护

设置上、下限寄存器，进行越界检测
通过重定位寄存器和界地址寄存器，进行越界检测。其中重定位寄存器存放起始物理地址，界地址寄存器存放最大逻辑地址。

内存共享

可重入代码：允许多个进程同时访问，但不允许修改
为每个进程配备局部数据区，将可能改变的部分复制进去，修改进程自己的私有数据

覆盖与交换

覆盖技术

将用户空间分为一个固定区和若干覆盖区。

常用的部分放入固定区，不常用的段在需要时放入覆盖区，当需要使用时将相应的段从外存调入覆盖区。

内存中能够更新的地方只有覆盖区的部分
对用户不透明

视频讲解：覆盖技术

交换技术

当内存空间紧张时，将内存中的某些进程暂时换出到外存，并将外存中某些已经具备运行条件的进程换入内存。

PCB是常驻内存的

中级调度（内存调度）就是决定将哪个处于挂起状态的进程重新换入内存。

在具有交换功能的操作系统中，磁盘空间通常分为文件区和对换区
- 文件区存储文件，追求磁盘空间的利用率，对磁盘空间的管理采用离散分配方式
- 对换区占用空间很小，追求换入换出速度，对磁盘空间的管理采用连续分配方式
交换通常发生在有较多进程在运行且内存吃紧的时刻
当系统负荷降低时停止交换
一般会优先换出阻塞进程以及底优先级的进程，同时为了防止出现饥饿现象，有时还要考选进程在内存的驻留时间

视频讲解：交换技术

连续分配管理方式

连续分配：系统为用户进程分配的必须是一个连续的内存空间

单一连续分配

视频讲解：单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。

系统区通常位于内存的低地址部分，用于存放操作系统相关数据；
用户区用于存放用户进程相关数据。

内存中只能有一道用户程序，用户程序独占整个用户区空间。

优点：
- 实现简单；
- 无外部碎片；
- 可以采用覆盖技术扩充内存；
- 不一定需要采取内存保护（eg: 早期的PC操作系统MS-DOS）
缺点：
- 只能用于单用户、单任务的操作系统中；
- 有内部碎片；
- 存储器利用率极低。

内部碎片：系统分配给进程的内存空间中，没有被利用到的区域

外部碎片：内存中的某些空闲分区太小而难以利用

固定分区分配

视频讲解：固定分区分配

将整个用户空间划分为若千个固定大小的分区，在每个分区中只装入一道作业。

分区大小相等：
- 缺乏灵活性
- 适合用于用一台计算机控制多个相同对象的场合
分区大小不等：
- 增加了灵活性，可以满足不同大小的进程需求；
- 根据常在系统中运行的作业大小情况进行划分（比如：划分多个小分区、适量中等分区+少量大分区）

操作系统需要建立一个数据结构——分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列，内容包括对应分区的大小、起始地址、状态(是否已分配)。

优点：
- 实现简单；
- 无外部碎片
缺点：
- 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；
- 会产生内部碎片，内存利用率低。

动态分区分配（可变分区分配）

视频讲解：动态分区分配

不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。

使用什么数据结构存储内存的使用情况
- 空闲分区表：每一个空闲分区对应一个表项，其内容包括空闲分区的起始地址、大小、分区号、状态等信息
- 空闲分区链：每一个空闲分区的起始部分和末尾部分分别设置前向指针和后向指针，指向前（后）一个空闲分区，同时在起始部分存储分区大小等信息
当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配
- 使用动态分区分配算法
如何进行空间的分配与删除
- 使用空闲分区表
  - 分配：修改或直接删除相应的空闲分区
  - 回收：修改或直接新增空闲分区，若存在合并，则删除掉其中一个
优缺点
- 优点
  - 系统分区的大小和数目是可变的
  - 不会产生内部碎片
- 缺点
  - 可能产生外部碎片

可以采用“拼凑”（紧凑）技术来解决外部碎片，即操作系统不断地移动各个分区，使之相邻，拼出更大的空闲分区。

紧凑技术需要重定位寄存器的支持

动态分区分配算法

在存在多个可用的空闲分区时，通过动态分区分配算法来决定使用哪个空闲分区

首次适应算法（First Fit）

每次都从低地址开始查找，找到第一个能满足大小的空闲分区。相应的，空闲分区以地址递增的方式进行排列。

最佳适应算法（Best Fit）

尽可能优先使用小的空闲分区，找到第一个能满足大小的空闲分区。相应的，空闲分区按照容量递增的方式进行排列。

可能会产生很多外部碎片。

最坏适应（Worst Fit）

也称为最大适应算法。优先使用大分区，找到第一个能满足大小的空闲分区。相应的，空闲分区按照容量递减的方式进行排列。

大的空闲分区不断变小，可能导致后到来的大进程无内存可用。

邻近适应（Next Fit）

视频讲解：领近适应算法

相当于对首次适应算法的改良，每一次从上次查找结束的地方开始继续查找，找到第一个能满足大小的空闲分区。相应的空闲分区在按照地址递增存储的同时，可以使用循环链表等类似数据结构。

首次适应算法相比于临近适应算法开销较大（每次都要从头开始检索）
首次适应每次都从头开始检索，会优先利用低地址部分的小分区，能够给大进程留下更多的大空闲分区

四种算法中，首次适应一般效果是最好的

非连续分配管理方式

基本分页存储方式

数据结构——页表

视频讲解：页框和页面的定义

将内存空间分为一个个大小相等的分区，每个分区就是一个页框（页帧、内存块、物理块、物理页面）。每个页框有一个编号，即页框号（页帧号、内存块号、物理块号、物理页号），页框号从0开始。页框是内存被划分

将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个页或页面。每个页面也有一个编号，即页号，页号也是从0开始。页和页面是进程逻辑划分

操作系统以页框为单位为各个进程分配内存空间；
进程的页面与内存的页框有一一对应的关系；
各个页面不必连续存放，可以放到不相邻的各个页框中。

理解记忆：因为进程最终要放到内存中，所以内存的划分叫页框，页框是用来放东西的，进程的划分叫页面，是被放的东西

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。

一个进程对应一张页表
页表通常存在PCB中，使用专门的页表基址寄存器存放
进程的每个页面对应一个页表项
每个页表项由页号和块号组成
页表记录进程页面和实际存放的页框之间的映射关系

一个进程对应一张页表

进程的每一个页面对应一个页表项，页表项中保存的是这个页面在内存中对应的页表框的编号，保存页表时不用保存页号，因为就是一个数组

页表项大小的计算

Eg：假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节?

页表项大小的计算

假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节？

内存块大小=页面大小=4KB= \(2^{12}\) B

4GB的内存总共会被分为 \(\frac{2^{32}}{2^{12}} = 2^{20}\) 个内存块。

内存块号的范围应该是 \(0 \sim 2^{20} - 1\)。

内存块号至少要用20bit来表示。

至少要用3字节来表示块号(3 * 8 = 24bit)。

每一个页表项中，块号占上述空间，页号不占存储空间（页表项是连续存放的，只要知道起始地址，即可推算出某个块的地址）

视频讲解：页表数据结构和计算每个页表项占的字节数量

逻辑地址的转换

视频讲解：分页系统的地址变换

1. 确定逻辑地址在页面中页号

通用方法是除以页面大小后取除法的整数部分

但是如果把页面大小设置为2的整数幂，比如说是\(2^k\)，相当于二进制右移k位，那么留下的就是页号

2. 查找这个页面在内存块中开始的物理地址

通用方式是以此为下标在页表中查找对应下标单元中存储的对应内存块的编号，用这个编号乘内存块大小即可以得到这个页面在内存块中开始的物理地址

如果页面大小是2的整数幂，比如\(2^k\)，因为将页面映射到内存中，内存中的页框大小和页面大小相同，所以只用将起始地址后k位直接替换为偏移地址即可

3. 用第二步得到的开始的物理地址加逻辑地址的偏移地址即可以得到真正的物理地址

通用方法是除以页面大小后取除法的小数部分

但是如果把页面大小设置为2的整数幂，比如说是\(2^k\)，相当于二进制右移k位，那么移走的k位就是页内偏移量

虽然进程的各个页是离散存放的，但是页面的内部是连续的。

如果有 K 位 表示 页内偏移量，则说明该系统中一个页面的大小是 \(2^{K}\) 个内存单元。

如果有 M 位 表示页号，则说明在该系统中，一个进程最多允许有 \(2^{M}\) 个页面。

基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。

通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块(PCB)中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

根据逻辑地址访问内存单元的流程：

根据逻辑地址计算出页号、页内偏移量
判断页号是否越界（页号应当小于页表长度）
查询页表，找到页号对应的页表项，确定页面的内存块号
用内存块号和页内偏移量得到物理地址
根据物理地址访问内存单元

页表长度：这个页表中总共有几个页表项，即总共有几个页；

页表项长度：每个页表项占多大的存储空间；

页面大小：一个页面占多大的存储空间

举例：

例：若页面大小 \(L\) 为1K字节，页号2对应的内存块号 \(b=8\)，将逻辑地址 \(A=2500\) 转换为物理地址 \(E\)

（这里页面大小1K也可以描述为“按照字节编址，页内偏移量占10位）

计算页号、页内偏移量：

页号：\(P = \frac{A}{L} = \frac{2500}{1024} = 2\)

页内偏移量：\(W = A \% L = 2500 \% 1024 = 452\)

由题可知，页号2没有越界，且内存块号为8

求物理地址：

物理地址：\(E = b \times L + W = 8 \times 1024 + 452 = 8644\)

页式管理中地址是一维的。在分页存储管理（页式管理）的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。只需要给出逻辑地址，计算机就可以得出页号、页内偏移量。

视频讲解：页表项大小的设置

如果不是页表项\(2^k\)，就会有内部碎片

具有快表的地址变换机构

视频讲解：流程图演示快表

快表，又称联想寄存器（TLB，Translation Lookaside Buffer），是一种访问速度比内存快很多的高速缓存（TLB不是内存），用来存放最近访问的页表项的副本，可以加速地址变换的速度。

与此对应，内存中的页表常称为慢表。

每一次切换进程时处理机会清空快表
在检查完页号是否越界后会尝试访问快表中的副本，若命中，则直接得到内存块号
否则，正常查询，并在找到页表项之后将其存入快表
快表少了一次内存访问

举例：引入快表后耗时计算

例：某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问一次快表耗时1μs，访问一次内存耗时100μs。若快表的命中率为90%，那么访问一个逻辑地址的平均耗时是多少？

\((1+100) \times 0.9 + (1+100+100) \times 0.1 = 111 \mu s\)

视频讲解：引入快表的耗时计算

注意题目中是否支持快慢表一起查询

视频讲解：局部性原理

两级页表

单级页表的问题：

视频讲解：单级页表存在的问题

页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框
没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面（局部性原理）

通过将页表进行分组，例如使得每一组恰好装入一个内存块，并对这些分组后的页表再建立一个页表用于查询。分别称为一级页表（页目录表）、二级页表、三级页表等。

视频讲解：多级页表解决单级页表连续分配问题

举例：

视频讲解

例：某系统按字节编址，采用40位逻辑地址，页面大小为4KB，页表项大小为4B，假设采用纯页式存储，则要采用（）级页表，页内偏移量为（）位?

分析数据：

页面大小 = 4KB = \(2^{12}\) B

页表项大小 = 4B = \(2^2\) B

求页号、页内偏移量：

页内偏移量 = 12

页号位数 = 40 - 12 = 28

每一页内可存放的表项：页面大小 / 页表项大小 = \(2^{10}\)

剩余的28位可以分为8+10+10，即三级页表

当快表不存在时，页表级数越多、访存次数越大。如果有n级页表，需要访存n + 1次

基本分段存储管理

视频讲解：分段的基本操作

进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有-一个段名，每段从0开始编址

内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

分段系统的逻辑地址结构由段号（段名）和段内地址（段内偏移量）所组成，其中：

段号的位数决定了每个进程最多可以分几个段
段内地址位数决定了每个段的最大长度是多少

段表

视频讲解：段表

作用与页表类似，结构包括段号、段长、基址，每个段表项的长度是相同的

注：每个段的大小不同，但是作为用于查询的段表项大小相同

段号：由于段表项长度相同，可以是隐含的
段长：该段的长度
基址：该段在内存中的起始地址

地址变换

视频讲解：分段存储地址转换

根据逻辑地址得到段号、段内地址
判断段号是否越界（段号应当小于段表长度M）
查询段表，得到对应的段表项（段表项地址 = 段表始址 + 段号 * 段表项长度）
判断段内地址是否超过段长

注：这是分段存储与分页存储最大区别，因为分页的话每个页面大小相同，所以根据已知逻辑地址和页面大小直接可以计算得到页内偏移地址，并且这个偏移地址不会存在溢出问题，而段内存储的段内地址是另外给出，所以必须要判断是否溢出
计算得到物理地址（物理地址 = 段基址 + 段内地址）
访问目标内存单元

分段和分页管理的区别

分页管理
- 页是信息的物理单位
- 分页的主要目的是为了实现离散分配，提高内存利用率，不会产生外部碎片，只有少量的内部碎片
- 分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的
- 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址
- 分页不需要给出页面长度，也就不需要检查页面是否越界
分段管理
- 段是信息的逻辑单位
- 分段的主要目的是更好地满足用户需求，会产生外部碎片
- 一个段通常包含着一组属于一个逻辑模块的信息
- 分段对用户是可见的，用户编程时需要显式地给出段名
- 分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址
- 分段更容易实现信息的共享和保护
- 分段由于每个段长不同，所以需要记录段长，也需要检测段中是否越界