内存管理

内存管理

概念

内存管理

1. 将用户源程序变为内存中可执行程序的步骤 - 编译、链接、装入
2. 模块装入内存的方式
   1. 绝对装入 - 适用于单道程序环境，产生的是绝对地址的目标代码
   2. 可重定位装入 - 产生的是目标的相对地址
   3. 动态运行时装入 - 装入内存后，并不会立即转化为绝对地址，而是将这过程推迟到程序真正执行才开
3. 目标模块链接的方式
   1. 静态链接 - 链接时，将所有的目标模块链接成完整的装入模块，以后不再拆开
   2. 动态链接 - 链接时，便装入边链接
   3. 运行时动态链接 - 需要某目标模块时才对它进行链接
4. 操作系统通过内存管理部件(MMU)进行逻辑地址到物理地址的转化
5. 内存映像、内存保护、内存共享与内存的分配回收的概念
6. 连续分配管理方式
   1. 单一连续分配 - 内存被分为系统区与用户区，用户区只有一道程序
   2. 固定分区分配 - 划分为固定的大小分区，每个分区只装一道作业。易产生内部碎片
   3. 动态分区分配 - 分区的大小可根据作业的需要动态调整 - 易产生外部碎片
      1. 回收机制 - 遇上下空格一起合并，若无上下空格则新建表项
      2. 首次适应算法 - 从低地址开始查找，找到第一个能满足需求的分区
      3. 临近适应算法 - 分配地址时从上一次查找结束的位置继续查找
      4. 最佳适应算法 - 按容量递增的次序排序，找到第一个能满足需求的分区
      5. 最坏适应算法 - 按容量递减的次序排序，找到第一个能满足需求的分区
   4. 索引分配算法 - 根据大小对空闲分区分类，对于每类空闲分区，单独设立一个空闲分区链，并设置索引表管理这些链
      1. 快速适应算法 - 索引表中找到能容纳它的最小空闲分区链表，然后从链表中取出第一块进行分配
      2. 伙伴系统 - 空闲分区的大小必须是2的幂次，分配时，若大小n满足2^i − 1 < n ≤ 2ⁱ,则在大小为2ⁿ的空闲分区链进行查找，若未找到，则查找2^i + 1。找到后将其拆分，一个分配一个加入下级空闲分区链，若未找到则继续向上查找
      3. 哈希算法 - 构建一张以空闲分区大小为关键字的哈希表
7. 基本分页存储管理
   1. 基本概念 - 页面与页面大小、地址结构、页表
   2. 快表的性质及使用
   3. 多级页表的性质及计算
8. 段页式存储管理
   1. 即每个程序被分成若干段，每个段被分成固定大小的页
   2. 进程的逻辑地址由三部分组成 - 段号、页号和业内偏移量
   3. 系统建立一张段表，每个段表项包括段号、页表长度和页表始址；每个段有一张页表，每个页表项包括页号和块号。还含有段表寄存器和页表寄存器。作用都是寻址和判断是否越界

虚拟内存管理

1. 传统内存管理的特征 - 一次性与驻留性
2. 局部性原理
   1. 时间局部性 - 某条指令被访问后可能再次被访问
   2. 空间局部性 - 某条指令被访问后，其附近的指令也很可能被访问
3. 虚拟存储器的定义、特征和实现
4. 请求分页管理
   1. 页表机制
      
      1. 状态位 - 记录该页是否被调入内存
      2. 访问字段A - 供置换算法查询，一般是最近时间内访问次数
      3. 修改位 - 记录该页在调入内存后是否被修改过，已决定换出后是否写回外存
      4. 外存地址 - 外存的物理地址
   2. 缺页中断的概念及过程，与一般中断的区别：属于内部中断，一条指令期间可能有多次缺页中断
   3. 请求分页中地址变换过程
      
   4. 页框分配
      1. 给一个进程分配的页框的集合就是驻留集。驻留集越小内存越多，并发性提高，但是缺页率提高
      2. 内存分配策略
         1. 固定分配局部置换 - 进程的驻留集不变，只能在分配给自己的内存换进换出
         2. 可变分配全局置换 - 可从空闲物理块队列分配一块并将缺页调入
         3. 可变分配局部置换 - 不可以从发别人那里抢
      3. 物理块调入算法 - 平均分配算法、按比例分配算法、优先权分配算法
      4. 调入页面的时间 - 预调页策略、请求调页策略
      5. 从何处调用页面 - 足够对换区、不够对换区、UNIX方式
   5. 页面置换算法
      1. 最佳置换算法OPT - 只存在于理论中
      2. 先进先出算法FIFO - 调出最先调入的页面，存在Belady异常
      3. 最近最久未使用算法LRU(也称最近未用NRU) - 调出最近最长时间未使用的页面
      4. 简单的CLOCK置换算法 -
         1. 初始时页面访问位为0.用一个指针指向当前页面，
         2. 每次缺页中断时，指针指向的页面若为0，则将其换入，指针指向下一位
         3. 若为1，则将其置0，指针指向下一个页面继续查看
         4. 若到了队列末尾则循环检查
      5. 改进型CLOCK置换算法 -
         1. 扫描指针循环遍历页面帧，检查当前页面的A位(访问位)和R位(修改位)
         2. 第一轮扫描优先淘汰 A=0 且 R=0 的页面（未访问 + 未修改，直接丢弃）
         3. 第二轮扫描其次淘汰 R=0 且 M=1 的页面（未访问但修改过，需写回磁盘）第二轮扫描中所有扫描的访问位都会被置0
         4. 第三轮扫描仿照步骤二
         5. 第四轮扫描仿照步骤三，此时一定会找到
   6. 内存映射文件的概念
   7. 虚拟存储器性能影响因素

公式

1. 确认页表项大小 - 先根据每页大小和总地址空间计算一共多少页，在计算需要多少位数来表示这些页面，再根据位数计算页表项的大小
2. 在没有快表的情况下，存取一条数据需要访问两次内存，如果有快表，则先查询一次快表，查找到只需访问一次内存，未查找到需要访问两次，且淘汰一个旧页表项

例题

1. 32位逻辑地址空间、页面大小为4KB，页表项大小为4B，求页表需占用多少个页