2.1：物理内存管理——连续

内存层次

• 处理器中：（硬件控制）

  • 两级缓存：L1缓存L2缓存（由MMU控制）

  • 存储管理单元（MMU）

• 内存、外存（操作系统控制）

  • 高速缓存未命中：缓存中找不到，去内存里找
  • 缺页：内存中也找不到，去外存找

内存管理目的

• 保护 ：进程间的空间相互独立
• 共享 ：全部进程用过一个内核
• 抽象 ：物理地址编号转变逻辑地址空间
• 虚拟化 ：逻辑空间比物理空间的大

内存管理方式

• 重定位 （relocation）：段地址+偏移（相对地址）

• 分段 （segmentation）：程序的逻辑结构不需要连成一片，而是分成代码、数据、 堆栈3块，每一块的空间就减少了；但每段的内容是连续的

• 分页 （paging）：把内存分成最基本的单位；bit太小，段太大

• 虚拟存储 （virtual memory）：目前多数系统（如Linux）采用的是按需页式虚拟 存储、依赖于内存

地址空间和地址生成

地址空间的定义

• 物理地址空间
• 逻辑地址空间
• 线性地址空间（CPU地址线宽度）

地址生成

• 逻辑地址生成过程

  • 编译 ：对源代码进行编译，成为汇编源代码，此时仍然用符号来指代函数
  • 汇编 ：汇编成二进制代码，用具体地址来代替符号了，但是有一些函数还没有找到

  • 链接 ：加入函数库，找到库函数的地址

  • 重定位 ：程序加载时进行，视程序实际位置改变符号地址

• 生成地址的时机

  • 编译时（优点：简单）:
    假设起始地址已知，但如果起始地址改变，就必须重新编译
  • 加载时
    如果加载时起始位置未知，编译器需生成可重定位的代码（relocatable code）
    加载时，生成绝对地址
  • 执行时（优点：灵活）
    执行时代码可移动
    需地址转换（映射）硬件支持（一般是虚拟存储）

地址检测

• 检查偏移量是否超出段长，超出内存异常

• 通过检测，则物理地址 = 偏移量+段基址寄存器的值

连续内存分配

• 内存碎片 （空闲内存不能利用）

  • 外部碎片：空间太小，进程要求空间都比他大

  • 内部碎片：单个单元内，进程用剩的，不过单元不取整，就不会产生了

• 动态分配

  动态分配的要求：大小可变、地址连续，需要知道已分配分区，和空闲分区

  • 最先匹配 （First-fit）：第一个可用的空间比n大的空闲块
  • 最佳匹配 （Best Fit Allocation）策略：查找并使用不小于n的最小空闲分区
  • 最差匹配 （Worst Fit Allocation）策略：使用尺寸不小于n的最大空闲分区

• 碎片整理

  • 紧凑 （挤一挤，把碎片挤掉）
    • 条件：所有应用程序可动态定位
    • 问题：开销大，需要优化开销
  • 分区对换 （把等待的进程，给他挪到外存去）
    虚拟页式存储之后，纯粹的分区对换的意义就不大了

动态分配策略：伙伴系统

分配过程

• 由小到大 在空闲块数组中找最小的可用空闲块

• 如果块太大，则对可用空闲块进行二等分，直到得到合适大小的块

释放过程

• 把释放的块放入空闲块数组

• 合并满足合并条件的空闲块，合并条件是：

  • 大小相同，均为2^i

  • 地址相邻

  • 相邻两块的低地址必须是2^(i+1)的倍数

数据结构

• 空闲块按大小和起始地址组织成二维数组（或者说一维数组+一维链表）
  • 第一维：大小；第二维：地址
  • 初始状态：只有一个大小为2^u的空闲块