内存管理

内存管理基础

内存管理概念

内存管理功能:

1. 内存空间分配和回收
2. 地址转换
3. 内存空间扩充
4. 存储保护

程序装入与链接

用户程序要在系统中运行，必须先装入内存，一般有如下步骤：

1. 编译
2. 链接
3. 装入

链接有以下几种方式：

1. 静态链接 运行之前就把目标模块以及库函数连接成一个完整的装配模块，不再拆开。这种方式需要解决两个问题：
   • 对相对地址的修改
   • 变换外部调用符号
2. 装入时动态链接 装入内存的时候再进行链接。
3. 运行时动态链接 运行的时候需要该模块再调进内存并连接。

装入有以下方式：

1. 绝对装入方式 装入的是绝对地址，一般适用于单道程序的环境。
2. 可重定位装入方式 装入的相对地址，装入时对目标程序指令和数据修改的过程叫重定位。 地址通常是装入时一次完成的，故也称为静态重定位。一旦作业装入内存，则必须分配要求的所有内存空间。（毕竟要给所有指令和数据编址）故又称为静态重定位。
3. 动态运行时装入 也成为动态重定位。程序装入内存后，并不把所有地址都转换成绝对地址，而是推迟到程序真正要执行的时候才执行重定位。这种方式需要一个重定位寄存器实现。

逻辑地址与物理地址空间

逻辑地址指的是编译后每个模块都从0开始的相对地址。 物理地址空间指的是内存中的物理党员集合。是地址转换的最终地址，最后都要根据物理地址从主存中获得数据。

内存保护

内存保护一般可以采用两种方法

1. 设置一对上下限寄存器 每当CPU要访问一个地址时，将该地址和寄存器的值进行对比。
2. 使用重定位寄存器和界地址寄存器 重定位寄存器存储的是最小的物理地址值，界地址寄存器存储的是逻辑地址的最大值。 对于CPU要访问的地址先和界地址值比对，如果符合要求再加上重定位寄存器的值获得物理地址。

交换与覆盖

交换主要是用作与多道程序，覆盖用作于单道程序。 交换中的交换空间通常作为磁盘的一整块，且独立于文件系统。

连续分配管理方式

单一连续分配

这种方式会分为系统区和用户区，这种方式不需要内存保护，但同时只能给单个程序使用。有内部碎片 无外部碎片

固定分区连续

又根据分区大小是否相等分为两种。需要一张内存分区表，程序需要转入时，查询表是否有可用内存，无法满足则不分配内存。 有内部碎片 无外部碎片

动态分区分配

主要分为四种：

1. 首次适应算法。总体效果最好
2. 最佳适应算法。会产生最多的外部碎片
3. 最坏适应算法。又称最大适应，对大程序不友好。
4. 临近适应。

非连续分配管理方式

分页管理方式

分页管理方式没有外部碎片，有内部碎片 分页存储的几个概念

1. 页面和页面大小 进程中的块称为页，内存中的块称为页框，外存的块就成为块。 进程执行的时候会申请空间，对应着页和页框。
2. 地址结构 地质结构包含页号和页内偏移量。
3. 页表 每个进程拥有一个页表。页表一般存放在内存。

PTR 每个系统只有一个。记录页表开始地址和长度。 快表就是在高速缓存存储器中存一部分的页表拷贝，可以提速。快表找不到再去页表找。当然有些系统快慢一起找，快表找到了就停止慢表的查找。

分段管理方式

段式管理结构根据用户进程的自然段划分逻辑空间。段内要求地址连续，段间不要求连续。 每个进程都有一张逻辑空间与内存映射的段表，记录着段号、段长、以及本段在主存的起址。

分段式管理方式有以下优点：

1. 方便编程
2. 信息共享
3. 信息保护
4. 动态增长
5. 动态链接

段页式管理方式

即将分段式和分页式结合，先将程序分成若干个段，再把每个段分为若干个页。 在段页式系统中，为了实现地址转换，需要同时配置段表和页表。和分段式不同的是，段表中记载的不是内存始址和段长，而是页表始址和页表长度。 在一个进程中，段表只有一个，页表可以有很多个（有多少段就多少个）

虚拟内存管理

虚拟内存的基本概念

传统存储管理的特征：

1. 一次性
2. 驻留性

虚拟内存的特征：

1. 多次行
2. 对换性
3. 虚拟性

请求分页管理方式

请求分页系统的页表机制不同于基本分页系统，需要在页表中添加以下字段：

1. 状态位P：记录是否调入了内存
2. 访问字段A：记录一段时间内被访问的次数
3. 修改位M：记录是否被修改过
4. 外存地址：记录在外存上的地址

页面置换算法

最佳（OPT）置换算法

被调出的是最长时间内不被调用的页面。但是无法预测未来时间的调用，因此无法实现。

####先进先出（FIFO）置换算法 优先淘汰最早装进内存的页面。 FIFO算法还会导致Belady异常，即分配的物理块增大，反而导致缺页故障变多的现象。 基于队列实现。

最近最久未使用（LRU）算法

选择最久未使用的算法进行淘汰。性能较好，但需要堆栈支持。

时钟（CLOCK）算法

时钟算法又称最近未用（NRU）算法。 简单的Clock算法只附加一个位：使用位。当某页首次装入内存时，将它使用位置为1，当该页再次被访问时，依旧置为1。需要页面置换的时候，操作系统扫描缓冲区，寻找使用位为0的页面，经过使用位为1的页面时，也会将使用位置0。

改进的Clock算法增加一个修改位，对于被修改过的页来说，需要重新写回到磁盘，而未修改过的页面不需要写回磁盘。那么修改过的页面置换代价更大，因此优先换出未修改过的页面 那么每一帧都会处于以下时钟状态之一：

1. 未被访问，未被修改（A=0，M=0）最佳替换页
2. 未被访问，已被修改（A=0，M=1）不算特别好的置换页
3. 已被访问，未被修改（A=1，M=0），有可能被访问
4. 已被访问，且被修改（A=1，M=1），可能被访问

这里可以看到的是，访问的优先级会比修改高，最近被访问的页面会偏向于不被换出，然后到未被访问但修改过的页面，最易于被换出的是未被访问未被修改。总体的步骤如下：

1. 寻找A=0，M=0的页面，不修改任何标志位
2. 寻找A=0，M=1的页面，将A=1的页面修改为A=0。
3. 重复1 - 2

页面分配策略

驻留集大小

决定驻留集大小需要考虑：

1. 分配给一个进程的存储越小，进程数目就越多，处理机使用率就越高
2. 一个进程的页数越少，就会频繁缺页
3. 页数过多，由于局部性原则，可能并不会提高太多的缺页率。 基于上述考虑，内存分配策略有以下几种：
4. 固定分配局部替换 为每个进程分配一定数目的物理块，整个过程不变，如果缺页只能用自己的页面进行换出。这样的策略难点在于缺点固定分配的数目大小。
5. 可变分配全局置换 最容易实现的分配策略。为进程分配一定数量的物理块，同时也保留一部分空闲的物理块队列。缺页时，从空闲物理块分配给进程。
6. 可变分配局部替换 为每个进程分配一定数量的物理块，缺页时只能用自己的页面进行置换，频繁缺页操作系统则给他分配物理块，直至缺页率正常。反之，如果物理块过多，也会被剥削。

调入页面的时机

有两种调入策略：

1. 预调页策略 根据局部性原理，一次调度若干相邻页会比一次次调入更为高效。目前策略主要为首次预调入，由程序员决定应该先调入哪些页。
2. 请求调页策略 运行的时候需要的页面不在内存则提出请求。

从何处调入页面

外存一般会被分为两部分：连续的对换区和离散的文件区。 因此，从何处调入页面就有了三种情况：

1. 系统拥有足够的对换区：直接全部从对换区调入
2. 系统缺少足够的对换区：不会修改的文件从文件区调入，由于他们未被修改，换出的时候就不必换出来。对于被修改过的部分，则换出的时候放入对换区。
3. Unix方式：和进程有关的文件都放在文件区，未运行过的页面都从文件区调入，曾经运行过的但被调出的放入对换区，下次调入从对换区调入。

工作集

工作集是指某段时间间隔内会访问到的页面集合。取决于窗口大小。 一般分配给进程的物理块数，要大于工作集大小。否则会出现抖动现象

抖动

刚被换出又要被换入，这种现象就叫做抖动。

易错点

1. 若进程在IO操作，不能交换操作
2. 内存保护需要操作系统和硬件一起完成
3. 重定位寄存器系统只需要一个
4. 存储管理目的：方便用户、提高内存利用率
5. 虚拟存储只能基于非连续分配技术
6. 虚拟存储容量只受寻址空间影响
7. 造成LRU算法耗费高的原因是需要对页进行排序，需要硬件支持只是前者导致的
8. 合法位信息决定是否发生缺页故障
9. CPU使用率不高，外存使用率高，说明内存不够