内存管理

这部分知识感觉很令人困惑，内存管理本身应该是非常连贯的东西，但是被王道考研的大纲拆分成了 内存管理概念 和 虚拟内存管理 两个意义不明的片段，尽管我第一轮整理笔记的时候是顺序的，但是我希望换一个更人类可理解的顺序理解它

​​

这是在网页上浏览编辑它的链接

内存管理

​​

基础知识

关于数据

储存方式：通常按字节编址

单位转换
8 bits = 1 byte
2^10 ^=1K
2^20^=1M
2**^30^**=1G

关于程序

四个段：
代码，数据，堆，栈

​​

从代码到运行：编译-> 链接-> 装入

​​

链接方式

动态链接库:.so​,.dll​；一般现代软件，静态链接和动态链接都有

装入方式

​./exefile​的时候调用装入器

加载器可以将可执行目标文件中的代码和数据从磁盘复制到内存当中，然后通过跳转到程序的第一条指令或入口点来运行该程序。这个过程叫做加载(load/装入)

重定位是把程序地址空间中的逻辑地址转换为内存的物理地址

​​

内存管理八股

​​

1. 内存空间的分配与回收
2. 对内存空间进行扩充
3. 提供地址转换功能，负责程序的逻辑地址（aka 虚拟地址） 与物理地址的转换
4. 内存保护

内存保护

操作系统内存管理最简单的两个功能，只是寄存器设置的不一样，现实生活中通常使用后者【就是段页式储存方案的一部分】

​​

在 CPU 设置一对上、下限寄存器，判断寻址合法

​​

采用重定位寄存器（基址寄存器） 和界址寄存器（限长寄存器) 进行越界检查 , 界址寄存器中存放进程的最大逻辑地址

内存分配与回收

程序分区的术语

• 内部碎片：分配给某进程的内存区域中，某些部分没有用上
• 外部碎片：是指内存中的某些空闲分区由于太小而难以利用

覆盖和交换

一些额外的扩大内存的办法

​​

​​

连续分配管理方式

并不是很现代很真实的管理方式，只是一些 idea

动态分区分配算法

​​

虚拟地址到物理地址的转换

基本分页地址转换

基本概念

1. Page（页/页面）：在虚拟内存管理中，页面是内存的基本单位。它是一段连续的固定大小的内存区域，通常为 4KB 或更大。操作系统使用分页机制将进程的虚拟地址空间划分为多个页面，以便更高效地管理内存。每个页面可以被映射到物理内存中的一页框。
2. Page Frame（页框，页帧）：页框是物理内存的基本单位。它是与页面大小相同的固定大小的内存块，用于存储操作系统和进程的数据。当操作系统将页面加载到内存时，它将页面映射到一个页框上。页框的数量限定了系统能够同时加载的页面数量。
3. Block（块）：在计算机系统中，块通常是指连续的一组数据元素或内存单元。块可以是固定大小的数据单元，如磁盘上的数据块，也可以是内存中的数据块。块的大小可以根据具体的上下文而变化。
4. Offset（页&块内偏移量）：在地址计算中，偏移量是指一个地址相对于某个起始点的位移量。在虚拟内存和磁盘存储中，页内偏移量表示一个地址相对于所在页面起始点的偏移量。块内偏移量表示一个地址相对于所在块起始点的偏移量。通过使用偏移量，可以确定一个地址在页面或块中的具体位置。

​​

进程的页面与内存的页框有一一对应的关系

⚠️ 这部分会考计算，回去看一下咋计算

页表和地址转换

不会有外部碎片，但是有内部碎片

​​

页表为什么能使虚拟内存的位数大于实际的内存？我们只在内存中保存最近使用的页，其他的储存在磁盘里

​​

具体而言，虚拟地址如何映射到物理地址？

​​

• 把虚拟内存地址，切分成页号和偏移量；
• 根据页号，从页表里面，查询对应的物理页号；
• 直接拿物理页号，加上前面的偏移量，就得到了物理内存地址。

​​

页表寄存器是存储当前进程的页表的物理地址，以便处理器能够根据页表进行地址转换。

具有快表的地址转换

快表（Translation Lookaside Buffer，TLB）是一种缓存结构，用于加速虚拟地址到物理地址的转换过程

简而言之就是维护一个储存最近使用过的地址转换的 cache

​​

两级页表

如果对 2^32^ 地址空间全都采用页表的话，这样页表占用的内存空间过多，我们不妨用一个二级页表索引一级页表，只让我们在用的一级页表和唯一一个二级页表常驻内存，这样节约了空间，加快转换

这样我们要进行 3 次访存

​​

summary

​​

习题

还是得做题，这道题贯穿了上述全部知识，那么请你计算一下罢

​​

​​

在这里看答案和更多知识

虚拟内存管理

基本概念

传统内存管理：一次性 + 驻留性

局部性原理

这是虚拟内存技术依赖的原理

• 时间局部性：一条指令的一次执行和下次执行，一个数组的一次访问和下次访问都集中在一个较短时期内
• 空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据都集中在一个较小区域内

虚拟储存器

物理内存 + 磁盘 = 虚拟存储；只加载需要的块进入物理内存->使虚拟内存比真实内存看起来大很多

特性：多次性，对换性，虚拟性

虚拟储存器的实现

• 请求分页¹
• 请求分段
• 请求段页式

虚拟储存需要的支持

• 一定数量的内存和外存
• 页表机制
• 中断机构
• 地址变换机构

请求分页管理方式

【感觉好困惑，我没明白它这么讲的逻辑结构...而且下面的 xx 机构又是什么...】

页表

比之前的朴素分页管理多了很多字段 🤔

新增两个功能

• 请求调页： 操作系统需要知道每个页面是否已经调入内存；如果还没调入，那么也需要知道该页面在外存中存放的位置
• 页面置换： 操作系统需要通过某些指标来决定到底换出哪个页面（需要记录页面是否被修改）

‍

​​

缺页中断机构

在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断

此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒， 放回就绪队列

• 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项
• 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存

地址变换机构

大约是如何处理缺页中断，不同的逻辑线

​​

页框分配

这部分似乎 408 不考了，但是王道里提到过 😭，这部分参考这个博客

基本概念

• 驻留集：指请求分页存储管理中给进程分配的物理块（即页框）的集合。在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。 “进程在内存中的工作副本”

【注】若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

• 工作集：指在某段时间间隔里，进程实际访问页面的集合。 “进程的关注点”
• 窗口尺寸：页面访问序列的集合，窗口尺寸有多大，访问序列中就有多少个页面。 “分析进程的工作集时考虑的时间窗口的大小”

【注 1】工作集和窗口尺寸的区别：

某进程的页面访问序列如下，窗口尺寸为 4。

（24，15，18，23），24，17，（18，24，18，17），17，15

括号表示窗口尺寸，则第一个窗口尺寸对应的工作集是 24，15，18，23，工作集为 4；第二个窗口尺寸对应的工作集是 18，24，17，工作集为 3。

【注 2】驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。

• 抖动：刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够，即驻留集太小）。

分配策略和置换策略

分配-> 固定&可变，关于驻留集大小

置换-> 局部&全局，是发生缺页的时候怎么置换的考虑

策略组合	局部置换	全局置换
固定分配	进程运行前就分配一定数量的物理块，缺页时只能换出进程自己的一页	​此组合不存在​，因为进程的物理块数是固定的，不能再申请或占用操作系统中的空闲物理块
可变分配	进程运行前就分配一定数量的物理块，缺页时只能换出进程自己的一页，系统根据发生缺页的频率来动态地增加或减少进程的物理块	进程运行前就分配一定数量的物理块，只要进程发生缺页，都将获得新的物理块

固定分配全局置换不存在！

物理块调入（分配！）算法

怎么把系统里的空闲物理块分配给各个进程：平均，按比例，优先权分配

调入页面的时机

​​

预调页（prefetch）：预测即将被访问的页（先发）

请求调页：不在内存则提出调页请求（后发）

从何处掉入？

复习：对换

在具有对换功能的操作系统中，通常把磁盘空间（外存空间） 分为文件区和对换区两部分：　

• 对换区：用于存放从内存换出的进程，读/写速度更快，采用连续分配方式。
• 文件区：用于存放文件，读/写速度更慢，采用离散分配方式。

情况	描述
系统拥有足够的对换区空间	运行前将数据从文件区复制到对换区，之后所有页面调入、调出都是在内存和对换区进行
系统缺少足够的对换区空间	不会修改的数据每次都从文件区调入内存，会修改的数据调出对换区，需要时再调入对换区
UNIX 方式	运行前将数据从文件区调入内存，从内存调出的页面都写回对换区，再次使用时从对换区调入内存

如何调出

采取 write back 策略，检查调出的页有没有被修改，若是被修改则写会磁盘，若是未被修改则直接舍弃-> 节约 io

页面置换算法

算法	优缺点
最佳置换算法（OPT）	缺页率最小，性能最好；但无法实现
先进先出置换算法（FIFO）	实现简单；但性能很差，可能出现 Belady 异常
最近最久未使用置换算法（LRU）	性能很好；但需要硬件支持，算法开销大（需要对页号进行排序）
时钟置换算法（CLOCK）	实现简单，算法开销小；但未考虑页面是否被修改过
改进型时钟置换算法（CLOCK）	算法开销较小，性能不错

最佳置换算法只是一种 idea 而无法实现

FIFO 是唯一有 Belady 异常的算法
Belady 异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

LRU 淘汰最近最久未使用的页面
技巧：若需要淘汰页面，可以逆向检查访问序列。假设某进程分配了 n 个内存块，则逆向找到第 n 个不同且在内存中的页号，该页号就是要淘汰的页面。

CLOCK: 淘汰最近未用，通过某些复杂的技巧(TODO)

改进型 CLOCK: 优先淘汰最近未用且未修改，其次是最近未访问已修改

【找一个例题！】

‍