Memory Management 内存管理

理想情况下，程序员需要内存

  • 大
  • 快
  • 非易失性

Memory hierarchy 内存层次结构

  • 少量快速、昂贵的内存 – 缓存 (cache)
  • 一些中速、中等价格的主内存 (main memory)
  • 千兆字节的慢速、廉价磁盘存储 (disk storage)

基本的内存管理：只有操作系统和一个用户进程

第一种方案：操作系统位于RAM的底部，以前被用在大型机和小型计算机

第二种方案：用于一些掌上电脑和嵌入式系统中

第三种方案：用于早期的个人计算机中，在ROM中的系统部分称为BIOS

第一种和第三种方案的缺点是用户程序出现的错误可能摧毁操作系统

不使用存储器抽象的情况下运行多个程序：重定位问题

每个内存块有一个用于标记的4位的保护键，会进行识别，然而会有重定位问题，对于内存地址不正确访问

  • 使用绝对物理地址，造成两个程序同时运行时冲突
  • 可以使用静态重定位技术，给所有的可执行程序提供额外的信息来区别那些内存字中存有可重定位的地址

地址空间

物理地址暴露给进程带来的问题：

  • 如果用户程序可以寻址内存的每个字节，他们就可以很容易的破坏操作系统，从而使系统慢慢地停止运行。除非使用特殊硬件进行保护，如IBM360的锁键模式
  • 使用这种模型，想要同时运行多个程序比较困难
概念
  • 解决问题的关键：保护和重定位
  • 地址空间--新的存储器抽象
    • 是一个进程可用于寻址内存的一套地址集合
    • 每个进程都有自己的一个地址空间，并且这个地址空间独立于其他进程的地址空间
基址寄存器和界限寄存器
  • 使用了动态重定位，简单地把每个进程的地址空间映射到物理内存的不同部分
  • 给每个CPU配置两个特殊硬件寄存器，基址寄存器和界限寄存器
  • 使用这两个寄存器时，程序装载到内存中连续的空闲位置且装载期间无须重定位

  • 定位时，会将进程的地址值加上基址寄存器中的值，同时也会检查程序提供的地址是否大于等于界限寄存器里的值。

  • 缺点：每次访问内存都需要进行加法和比较运算

Multiprogramming with Fixed Partitions 固定分区的多道程序设计

  • 每个分区有单独的输入队列
  • 单个输入队列
  • 由于分区大小是固定的，因此特定作业未使用的任何空间都会丢失。
  • 要说明特定作业需要多大的分区可能并不容易。

Swapping & Virtual Memory 交换和虚拟内存

  • 是克服内存限制的两种方法
    • 交换将进程在内存和磁盘上来回放置。
    • 虚拟内存允许程序运行，即使它们只是部分在主内存中

Swapping

  • 交换在内存中产生了多个空闲区--称为空洞(hole)，这时候可以使用内存紧缩
内存紧缩 memory compaction
  • 通过把所有的进程尽可能向下移动，有可能将这些小的空闲区合成一大块
  • 会耗费大量的CPU时间

空闲内存管理

有两种方法跟踪内存使用情况：位图和空闲区链表

Memory Management with Bit Maps & List 使用位图的存储管理

  • 0表示空闲，1表示占用（或者相反）
  • 缺点：在映射中查找连续的 0 位是耗时的

Memory Management with Linked Lists 使用链表的存储管理

  • 链表中的每一个结点都包含以下域
    • 空闲区(H)或进程(P)的指示标志
    • 起始地址
    • 长度
    • 指向下一结点的指针
  • 四种内存管理的算法
    • First fit 首次适配：从头开始搜索适合的空洞。
    • Next fit 下次适配：从上次停止的地方搜索适合的空洞。
    • Best fit 最佳适配：搜索整个列表并取适合的最小空洞。
    • Worst fit 最差适配：搜索适合的最大空洞。
  • 还有一种叫快速适配(quick fit)的算法，维护一个存储空闲区信息的链表

Virtual Memory

  • 问题：程序太大，放不进内存中去
  • 解决：虚拟内存 -- 操作系统将当前正在使用的程序部分保留在内存中
    • OS keeps the part of the program currently in use in memory
  • Paging 分页是一种用于实现虚拟内存的技术。
  • Virtual Address 虚拟地址是程序生成的地址。
  • MMU (memory management unit)（内存管理单元）将虚拟地址转换为物理地址。

  • 虚拟地址空间(virtual address space)按照固定大小分为(虚拟)页面(pages)，物理内存中对应的为页框(page frames)，页面和页框大小通常是一样的

  • 一个在/不在位跟踪页面是否被映射。

  • 对未映射页面的引用会导致 CPU 陷入操作系统。

  • 这个陷阱被称为页面错误(page fault)。 MMU 选择一个很少使用的页框，将其内容写入磁盘，获取刚刚引用的页面放到刚才回收的页框中，修改映射关系，并重新启动被捕获的指令

Pure paging

Page Table 页表
  • 给出的虚拟地址和物理内存地址的关系
  • 用页号作为索引，以得出对应于该虚拟页面的页框号。

  • “在/不在”位为0，则将引起一个操作系统陷阱

两个主要问题：

  • 虚拟地址空间很大的话，页表也会非常大（例如大多数计算机使用）32 位地址，4k 页大小，12 位偏移
    • 20 位虚拟页号
    • 100 万个条目
  • 映射必须很快，因为它是在每次内存访问时完成的

针对大内存的页表

Multilevel Page Tables 多级页表
  • 减少表大小。
  • 另外，不要将不需要的页表保留在内存中

  • 32位的虚拟地址被划分为
    • 10位的PT1域
    • 10位的PT2域
    • 12位的Offset(偏移量)域
  • 偏移量是12位，所以页面大小为4KB，共有\(2^{20}\)个页面

  • 由索引顶级页表得到的表项中含有二级页表的地址或页框号。
  • 顶级页表的表项0指向程序正文的页表，表项1指向数据的页表，表项1023指向堆栈的页表，其他的表项未用

  • 示例
    • 32位虚拟地址：0x00403004（十进制为4206596）位于数据部分12292字节处
    • 它的虚拟地址对应PT1 = 1, PT2 = 3, Offset = 4
    • 首先用PT1作为索引访问顶级页表得到表项1
      • 对应地址范围为4M到8M-1
    • 然后用PT2作为索引访问刚刚找到的二级页表并得到表项3
      • 在他的4M块中的12288~16383
    • 如果该页面在内存中，从二级页表中得到的页框号与偏移量结合形成物理地址
Inverted page table 倒排页表

  • 在这种设计中，实际内存中的每个页框对应一个表项，而不是每个虚拟页面对应一个表项

  • 原因：一个进程对应一个页表，每一个页表中会包含大量的entries

  • 使用倒排页表，一个entry能够对应一个内存中的页框

    • 表项中记录了哪一个（进程、虚拟页面）对定位于该页框

    • 表项： <process-id, page-number>

    • 然后在反转页表中搜索匹配项。 如果找到匹配项 i，则生成物理地址 <i, offset>。

    • 否则，已尝试非法地址访问

  • 虽然减少了存储每个页表所需的内存，但增加了发生页引用时查找表所需的时间

  • 不足：从虚拟地址到物理地址的转换会变得很困难

Page Tables

  • 大多数操作系统为每个进程分配一个页表。
  • 由一组硬件寄存器组成的单页表。 加载进程时，寄存器加载页表。
    • 优点 - 简单
    • 缺点 - 如果表很大并且在每次上下文切换时加载完整页表会损害性能，则代价高昂。
  • 将页表留在内存中——单个寄存器指向表
    • 优点 - 上下文切换便宜
    • 缺点 - 一个或多个内存引用来读取表条目

页表结构

  • Page frame number 页框号：对应页框号
  • Present/absent bit 在/不在位：1/0对应有效/无效条目
  • Protection bit 保护位：允许什么类型的访问，使用三位，读、写、执行。
  • Modified 修改位：在修改和写入磁盘时设置，记录
  • Referenced 访问位： 页面被引用时设置（帮助决定要驱逐的页面），记录
  • Caching disabled 高速缓存禁止位：用于将逻辑上属于磁盘的数据保留在内存中以提高性能

加速分页过程

TLB
  • 观察：大多数程序对少量页面进行大量引用
  • 为计算机配备一个小型硬件设备，称为转换检测缓冲区(Translation Look-aside Buffer，TLB)或关联内存，无需使用页表即可将虚拟地址映射到物理地址。

问题

虚拟地址空间总共大小为：\(16 * 2048 = 2^{15}B=32KB\)，所以需要至少15位来标记

Check Points

  1. What is the drawback of the bitmap method for free memory management?
  2. What is the purpose of virtual memory?
  3. What is page table?
  4. What is the purpose of using multi-level page table?
  5. What is the purpose of using TLB？
  6. What is invert page table？

Solution

  1. to find consecutive 0 bits in the map is time-consuming.
  2. 在一定程度上缓解内存不足的压力
  3. The relation between virtual addresses and physical memory addresses given by page table
  4. reduce the table size. Also, don't keep page tables in memory that are not needed.

  1. 加快分页过程
  2. There is one entry for each real page (frame) of memory.