1 内存管理的概念

• 内存管理指操作系统对内存的划分和动态分配

• 地址空间：
  逻辑地址空间： 相对地址， 从0开始编址
  物理地址空间： 地址转换的最终地址

程序运行时和
编译： 吧源代码编译成目标模块
链接： 吧目标模块、库函数链接成1个装入模块
链接属于形成进程逻辑地址的过程

装入：
绝对装入： 编译时就确定了装入地址
可重定位装入： 根据内存情况， 把程序装到适当位置
运行时动态装入：运行前才真正把程序装起来（前面2个都是先分配，再装，再运行）

2 内存防溢出机制

即怎么防止内存越界

• 设置上下限寄存器：
  存放内存中该进程的 上下限地址
  每次访问时，判断是否越界

重定位+界地址：
重定位寄存器——存放物理地址的最小地址
界地址寄存器——存放逻辑地址的最大值

先把访问地址（相对地址） 与界地址比较是否越界
再加到重定位寄存器上，作为物理地址

min + x， 且x <max， 这样保证地址在min到min+max之内

3 内存分配机制

3.1 连续分配内存

连续分配指 为用户程序分配的内存空间一定是连续的

3.1.1 单一连续：

内存分为系统区和用户区2个区
每次用户区只能放1个程序， 这样可确保不会越界

3.1.2 固定分区分配

用户区分成若干个大小的分区， 每个分区只能装一个作业。
程序如果大了会装不下
程序小了则有内存碎片

3.1.3 动态分区分配

程序装入内存时，按照所需大小动态生成1个分区。 有多少碎片空间就给多少

可能会存在碎片， 比如中间的进程结束了， 于是中间就空出来一个内存碎片，而可能因为太小，其他进程帆布进来。

动态分配策略：

• 首次适应： 从上往下找第一个满足的分区——最简单也最好
• 最佳适应： 找一个大小差距最小的分区——最烂，碎片最多
• 最坏适应： 直接找最大的分区转入
• 邻近适应： 从上次查找位置开始找，而不是从第一个碎片位置开始找。——末尾碎片会很多

3.2 非连续内存分配

非连续指进程内存可以 分成不同地址存放，不一定全部集中在一起。

3.2.1 分页

把内存划分成固定大小的块， 进程以块为单位申请多个不同位置的块作为空间。

• 页表：
  每个进程PCB中会有一个页面寄存器PRT， 告知页表的起始位置和起始长度
  找到页表后， 页面中会告知你所持有的页号和偏移。
  通过 页号 * 块大小 + 偏移， 可知道这段内存的起始位置。

进程每次想通过虚拟地址去定位物理地址时，都需要先去页表中找到虚拟地址对应的页，然后再得到物理地址。

• 快表TBL（Translation Lookaside Buffer )）：
  为了避免每次斗取页表换算地址， 快表会缓存 虚拟地址->物理地址的直接映射，加快速度
  

• 多级页表
  地址空间超级大， 1页装不下怎么办？
  用多级
  一级页表指明二级页表的地址
  二级页表再去实际地址
  这样就可以有多页了。

3.2.2 分段

分页的话， 页的长度时固定的， 所以偏移量的最大值是固定的

分段的话不限制偏移量最大值，即可以很长一段。

分段属于二维地址空间， 因为他除了给出逻辑地址，还得给出段长

有利于做动态链接： 程序动态修改

3.2.3 段页结合

作业先分成若干段， 再把段分页， 每个段可以找到一个也变

段号S 页号P 页内偏移

Q: 遍历二维数组的时候, 行遍历优先和列遍历优先的效率差别, 为什么会这样

A: 按行遍历比按列遍历的效率高体现在这些方面：

1. CPU高速缓存
2. CPU缓存从内存中抓取一般都是整个数据块，所以它的物理内存是连续的，几乎都是同行不同列的，而如果内循环以列的方式进行遍历的话，将会使整个缓存块无法被利用，而不得不从内存中读取数据，而从内存读取速度是远远小于从缓存中读取数据的。随着数组元素越来越多，按列读取速度也会越来越慢。

6.4 虚拟内存

4.1 概念

虚拟地址可以让进程获得比实际内存要大的内存
特征：

• 多次性——作业可分多次装入内存
• 对换性——可在运行时对内存做兑换处理
• 虚拟性——逻辑上可充分扩充容量

要求：
必须使用非连续分配方式——分页、分段、段页
硬件需要支持 页表、中断、地址变换机构

理论依据：
时间局部性—— 指令和数据总是会在一段时间内被连续访问
空间局部性——某单元被访问，那么他附件的单元也很大概率会被访问

4.2 请求分页机制

再分页的基础上， 增加了2个功能：
请求调页——当页面不在内存中时，从外村申请调入
页面置换——把暂时不用的内存换出去，给其他需要进来的页腾出空间

页表项：
页号、物理块号
状态位P：是否已经调入内存
访问字段A： 记录访问次数或者访问标记，用于置换策略判断
修改维 M： 记录是否被修改过
外村地址——当页被换出去时，指明这个页在外存的何处

缺页中断机构： 当页面不存在时， 负责产生缺页中断，进行页面置换操作。

缺页只能高端和系统中断不同， 属于指令中的操作，在执行期产生多次

地址变换机构：
1.先检索快表，如果能找到，则直接修改页表项的访问位。
2.快表中没有，则去 再检索内存中的页表，通过状态为P确认是否在内存中
如果不在，则产生缺页中断。

4.3 工作集概念

驻留集：指系统给每个进程分配的内存中实际页面集合
但是可能分配了10个， 却只有5个经常在用

工作集： 某时间段内，这个进程访问和使用的页面集合

通过工作集， 系统可以评估这个驻留集是否需要做删减，以及哪些页应该持续保留。
这样可以减少抖动，即减少内外村之间频繁的交换页

4.4 页面置换算法

• 最佳置换算法：
  选未来最长时间不会被用到的页
  这个要基于预测，比较难
• 先进先出FIFO
  可能引发bleady异常：

较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出，并且有Belady现象。所谓Belady现象是指：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。

• 最近最久未使用（LRU）
  选之前最长时间没访问的， 引入优先队列（最大堆）
  需要设置访问时间字段
• 简单时钟clock（最近未使用NRU）
  每个页有个标记。
  刚换入内存或者被访问时，都会置1

如果需要换页时，步骤如下：

1. 扫描围成换的页链表
2. 如果标记为1，则改成0，继续往下扫
3. 如果位0， 则替换，并让指针指向下一页。

• 改进的clock
  把标记为改成 访问位u和修改维m
• 1类(A =0, M = 0)：表示该页面最近既未被访问，又未被修改，是最佳淘汰页。
• 2类(A =0, M = 1)：表示该页面最近未被访问，但已被修改，并不是很好的淘汰页。
• 3类(A =1, M = 0)：表示该页面最近已被访问，但未被修改，该页有可能再被访问。
• 4类(A =1, M = 1)：表示该页最近已被访问且被修改，该页可能再被访问。

1. 先优先找u=0和m=0的页，有就直接替换
2. 没有，则找 u = 0 且m=1的页（ 没访问的最优先替换）， 做替换
3. 如果中间遇到U=1的， 则都会置0， 如果m=1的也会置0
4. 如果一圈都没有，则下一圈肯定有01或者00的。

4.5 页面分配量策略

• 固定分配，局部替换
  每个进程分配固定的物理块， 且只能自己的块之间做替换
• 可变分配，全局替换
  缺页时，可以从全局队列的页替换
• 可变分配，局部置换
  自己替换自己，但是不够的时候可以加块

分配来源：
对换区：频繁切换的区
文件区：补怎么会变动和修改的