第9章 主存

9.1 背景

9.1.1 基本硬件

• 程序必须送入内存并放在一个将要运行它的进程中

• CPU能直接访问的存储空间只有主存和寄存器

• 内存单位（memory unit）只能看到一条这样的流：
  • 地址+读请求 或
  • 地址+数据和写请求
• 访问寄存器在一个CPU周期（或更少）完成

• 主存要用多个CPU周期，引起暂停（stall）

• 缓存（cache）处于主存和CPU寄存器之间

• 内存保护要求保证正确的操作：

  • 需要保证进程只访问自己地址空间里的地址
  • 可以通过用一对基址寄存器（base register）和界限地址寄存器（limit register）提供保护

  

  • CPU必须检查用户模式下生成的每个内存访问来保证它落在该用户的基址和界限地址寄存器之间
• 加载基址和界限寄存器的指令是特权指令

9.1.2 地址绑定（Address Binding）

• 磁盘上、准备进入内存执行的程序形成了一个输入队列（input queue）

  • 没有支持（？）的情况下，必须从地址0000开始

• 使第一个用户进程的物理地址总在0000不方便

• 在程序的生命周期的不同阶段中，地址用不同的方式表示

  • 源码地址总是符号化的（symbolic）

  • 编译代码（compiled code）地址再绑定到重定位（relocatable）地址

    e.g. “从本模块开始14byte”

  • 链接器（linker）/加载器（loader）把重定位地址和绝对（absolute）地址绑定起来

  e.g. 74014

每次绑定都是把地址从一个地址空间映射到另一个

绑定指令和数据到内存可发生在三个阶段

• 编译阶段：若内存位置事先知道，可生成绝对代码（absolute code）；若开始位置改变了，需要重新编译
• 加载阶段：若内存位置在编译阶段未知，必须生成重定向代码（relocatable code）
• 执行阶段：若进程在执行时可以在内存段间移动，绑定要推迟到运行时
  • 需要地址映射的硬件支持（也就是基址寄存器和界限寄存器）

9.1.3 逻辑 vs. 物理地址空间

• 逻辑地址（logical address）/虚拟地址（virtual address）：由CPU生成的地址
• 物理地址（physical address）：对内存单元可见的地址，也是加载进内存地址寄存器（memory-address register）的地址
• 在编译或加载时绑定地址会生成相同的逻辑和物理地址；执行时绑定地址逻辑和物理地址不同
• （在本文中不区分逻辑地址和虚拟地址）
• 逻辑地址空间（logical address space）是由一个程序生成的所有逻辑地址的集合
• 对应于这些逻辑地址的所有物理地址的集合是物理地址空间（physical address space）

在运行时把虚拟地址映射到物理地址的硬件设备叫做MMU（Memory-Management Unit）

有多种映射方式，详见9.2-9.3

一种简单方式（基址寄存器的推广）：

• 基址寄存器现在被叫做重定向寄存器（relocation register）
• 每个由用户进程生成的地址被送到内存里的时候，要加上重定向寄存器的值
• 用户程序使用的是逻辑地址，真实的物理地址对它永远不可见
  • 内存映射硬件将逻辑地址转换成物理地址（详见9.1.2）
  • 在引用完成之前，被引用的内存地址的最后位置都不确定

9.1.4 动态加载（Dynamic Loading）

根据目前我们讨论的内容，整个程序和进程的数据都必须在物理内存中，进程才能执行。这样进程的大小就被限制在物理内存大小以内。

为了提高内存空间的利用率，我们可以用动态加载（dynamic loading）。

有了动态加载，事务（routine）只有被调用时才会被加载。

所有事务都以重定向加载的格式被保存在硬盘上。

• 先将主程序加载进内存并执行
• 当某个例程A需要调用另一个例程B时，A会先检查B有没有被加载过
  • 若没加载，就会调用重定向链接加载器（relocatable linking loader）把B加载入内存，并且更新程序的地址表来反映这一变化。然后控制权就交给B

动态加载的优点：

• 事务仅在被需要时才会加载

• 当需要大量代码来处理不经常发生的情况（例如错误事务 error routine）时，此方法特别有用。在这种情况下，虽然整个程序很大，使用的部分（也就是加载的部分）却要小得多

动态加载不需要特别的OS支持

• 利用这种方法设计程序是用户的工作。
• 但是，OS可以通过提供库来实现动态加载来帮助程序员。

9.1.5 动态链接和共享库

动态链接库（DLL, Dynamically linked libraries）是在程序运行时链接到用户程序的系统库。

一些OS只支持静态链接（static linking），也就是说系统库被视同其它对象模块，由加载程序组合为二进制程序映像（binary program image）。

相反地，动态链接和动态加载相似。链接（而不是加载）被推迟到执行时。

这种功能通常与系统库一起使用，例如标准C语言库。

如果没有这个功能，系统上的每个程序都必须在可执行映像中包含其语言库的副本（或至少包含该程序引用的事务）。

这样不仅会增大可执行镜像的大小，还可能浪费主存空间。

DLL优点：

1. 节省空间
2. 这些库可以在多个进程间共享，所以主存中只有DLL的一个实例。（因此DLLs也被称作共享库，并且广泛应用于Windows和Linux系统中）

小段程序，或者叫存根（stub），被用来定位合适的内存驻留库事务（memory-resident library routine）

存根用事务的地址代替自己，然后执行事务

OS检查事务是不是在进程的内存地址里，若不在，就加到地址空间

动态链接对库来说尤其有用：考虑系统库升级的应用场景

• 在库升级之后，原来的库会被新版本代替
• 所有的引用这个库的程序会自动用新版本
• 若没有动态链接，所有的这样的程序都需要重新链接到新库
• 为了使程序不会意外执行新的，不兼容的库版本，程序和库中都包含版本信息。 可以将一个以上版本的库加载到内存中，并且每个程序都使用其版本信息来确定要使用哪个库副本。
• 具有小幅更改的版本保留相同的版本号，而被大幅更改的版本增加版本号。 因此，只有使用新库版本编译的程序会受到其中包含的任何不兼容更改的影响。在安装新库之前链接的其他程序将继续使用旧库。

与动态加载不同，动态链接和共享库一般来说需要OS帮助。若内存中的进程互相保护，OS就是唯一一个可以检查所需事务是否在另一个进程的内存空间中，或者可以允许多个进程访问相同内存地址的实体。

9.2 连续内存分配

主存必须支持OS和用户进程

由于资源有限，要用最高效的方式分配

连续分配是一种早期的方式

主存通常分为两个分区（partition）：

• 常驻操作系统，通常使用中断向量保存在低位内存中
• 用户进程存在高位内存中
• 每个进程被保存在单个连续的内存区间里

9.2.1 内存保护

重定位寄存器用于保护用户进程相互之间不影响，以及用户进程私自更改操作系统代码和数据

• 基址寄存器包含最小的物理地址的值

• 界限地址寄存器包含逻辑地址的范围：每个逻辑地址都要比界限寄存器小

• MMU动态映射逻辑地址

• 然后可以允许一些操作，例如临时（transient）的内核代码和改变内核大小

  

9.2.2 内存分配

一种最简单的分配内存的方法是把进程分配到不一样大小的内存分区中，每个分区可能只包含一个进程。OS保存一个表格，记录内存的哪些部分是可用的，哪些不可用。最开始，整块内存都是可用的。

可用的内存块叫做孔（hole）

• 当进程进入系统时，OS考虑每个进程的内存要求和可用内存量来决定给哪些进程分配内存

• 当进程被分配了空间后，就被载入内存，它就能竞争CPU时间
• 在进程结束后，它会释放它的内存，OS可以把这段内存分配给其它进程

若没有足够内存进程咋办？

1. 可以拒绝这个进程然后粗暴地报错
2. 可以把这个进程加入等待队列，等有空间了再进来

一般来说，可用的内存块由一组大小不一的孔组成，散布在内存的各个位置。

相邻的孔可以合并；过大的孔可以只填一部分

三种常用策略：

1. 最先适应（first-fit）：分配给第一个足够容纳的孔
2. 最佳适应（best-fit）：分配给最小的足够容纳的孔
3. 最差适应（worst-fit）：分配给最大的足够容纳的孔

模拟实验显示，最先适应和最佳适应比最差适应在时间和空间利用上要好；最先适应和最佳适应在空间利用上差不多，但最先适应要快

9.2.3 碎片（Fragmentation）

最先适应和最佳适应策略都会遇到外部碎片（external fragmentation）的问题

在进程装载和移出内存的时候，释放的内存空间会被分割成小片段

外部碎片存在于这种情况：总共的内存空间可以满足request，但是不连续

在最差情况下，每两个进程间都有碎片，若这些小片段能连起来，可能可以运行更多进程

影响碎片数量的因素：

• 用最佳适应还是最先适应（二者对不同的系统各有千秋）
• 分配的时候放块的最前面还是最后面

但无论用哪种算法，外部碎片都是一个问题

问题大小取决于总的内存容量和进程的平均大小

对最先适应的统计分析显示，即便有一些优化，有N个分配的块就会有额外0.5N个块由于碎片问题损失掉——也就是说三分之一的内存都不可用，这叫做百分之五十规则（50-percent rule）

内部碎片（internal fragmentation）：分配的内存可能比请求的大那么一点，这之间的差别就是内部碎片

一种解决外部碎片的办法：压缩（compaction）

• 把空闲的内存赶到一大块里
• 仅当重定位是动态的，且在执行时完成，压缩才可行
• I/O问题：I/O做完回来发现地址变了

现在认为后备存储（backing store）也有相同的碎片问题

9.3 分页（Paging）

目前为止讨论的内存管理都要求一个进程的物理地址连续，现在介绍分页，允许物理地址空间不连续

分页避免了外部碎片和相应压缩的需求，这是两个内存分配的大问题

因为分页提供了诸多好处，分页及其大量变体被应用于大多数OS，从大型服务器到移动设备都有

分页在OS和计算机硬件的协作过程中应用

9.3.1 基本方法

最基本的分页方法是把物理内存切成固定大小（由硬件决定，是2的幂）的块，称作帧（frame）；把逻辑内存也切成同样大小的块，称作页（page）

在进程执行前，它的页（可能有好几个）从源（文件系统或后备存储）装载进任何可用的帧

后备存储被切成和一个或几个帧一样大小的块

每个由CPU生成的地址都被分成两部分：页号（page number，p）和页偏移（page offset，d）

页号用来索引页表（page table）。页表包含了物理内存中每个帧的基址，页偏移是帧内被引用的位置。帧的基地址+页/帧内偏移就能决定物理内存地址

逻辑地址到物理地址的转换步骤：

1. 提取页号p，作为查找页表的索引
2. 从页表中查到相应的帧号f
3. 用帧号f替代逻辑地址的页号p

分页是一种动态重定位，每个逻辑地址都通过分页硬件绑定到某个物理地址

使用分页策略不会产生外部碎片，但可能会有一些内部碎片。最差情况每个进程都有几乎一整页的内部碎片，平均情况是半页

随时间推移，进程、数据、主存都变大，页表尺寸也变大，现在页都在4KB或8KB大小，有些系统甚至提供更大的页表尺寸，还有些CPU和OS甚至提供多种页表尺寸

• Windows 10支持4KB和2MB的页表尺寸
• Linux支持默认的4KB和更大的基于架构的页表尺寸，称为大页面（huge page）

注意，在分页内存系统中物理内存的大小通常与进程的最大逻辑大小不同

分页的一个重要方面是分离了编程者视角的内存和实际的物理内存

OS要管理物理内存，所以会保存一个横跨整个系统的系统结构帧表（frame table），包含每个物理帧和它到底有没有被分配，分配给哪个进程的哪个页了

9.3.2 硬件支持

由于页表是每个进程都需要的数据结构，因此指向该页表的指针与其他寄存器值（如指令指针）一起存储在每个进程的PCB中

CPU调度程序选择要执行的进程时，必须从存储的用户页面表中重新加载用户寄存器和适当的硬件页面表值。

页表可以存在寄存器里，但如果页表太大，可以用页表基址寄存器（page-table base register, PTBR）指向页表，页表长度寄存器（page-table length register, PTLR）表示页表大小。换页表的时候就可以只改一个PTBR，减少了上下文交换的时间。

9.3.2.1 转移后备缓冲区（Translation Look-Aside Buffer）

把页表存主存里加快了上下文交换（就是因为上一段说的只改一个PTBR），但增加了内存访问次数（2次：访问页表+访问数据）

解决：TLB

• 有些TLB保存每项的地址空间识别符（address-space identifiers, ASIDs），表示是否需要保护这个进程的地址空间
• TLB通常很小（64-1024项）
• 一旦TLB miss，value会装载进TLB，以便加速下一次访问
  • 必须考虑替换策略
  • 一些项可能会断线（wire down），也就是说永远不被替换出去
  • hit ratio: TLB命中的比率

有效访问时间（EAT，effective access time）：

• 假设hit ratio=80%，访问一次内存要10ns，若页号在TLB里映射内存访问数据需要10ns

  即：

  • TLB hit是1次内存访问（数据）
  • TLB miss是2次内存访问（页表+数据）

• 则若在TLB里找不到，就要先去内存中查页表和帧号，再访问内存数据

• EAT = 0.8 * 10 + 0.2 * 20 = 12ns

• 要是命中率更高访问时间就更短

9.3.3 保护

• 通过将保护位与每个帧相关联来实现内存保护，表示是否允许只读或读写访问
  • 还可以增加更多位来表示页是只执行还是其它类型
• 附加有效/无效位（valid-invalid bit）到页表中的每个条目
  • 有效表示关联的页的确在进程的逻辑地址空间内，是合法页
  • 无效表示这个页不在进程的逻辑地址空间内
  • 或者用PTLR（页表长度寄存器）
• 任何违规都会送到内核中，视为陷阱（trap）

9.3.4 共享页

分页的好处就是可以共享代码，对多进程情况特别重要

比如对于Linux下大多数用户进程都要调用的C语言库libc

• 一种选择是每个进程都要把libc的副本拷贝到自己的地址空间，浪费空间
• 但如果是可重入代码（reentrant code），就可以共享，物理内存里仅有libc的一个副本，但每个进程有自己的寄存器副本和数据存储。
  • 可重入代码：在执行阶段不更改，所以多个进程可以同时执行同一段代码
  • 虽然代码一样，两个进程的数据不一样
  • 只有可重入代码可以共享

除了运行时库，编译器、窗口系统、数据系统等都可以共享

共享代码的只读性质由操作系统强制规定。

共享代码：

• 共享代码与多线程共享相同的进程空间类似

• 如果允许共享读写页面，则也是一种进程间通信的方式

私有代码和数据：

• 每个进程持有独立的代码和数据备份
• 私有代码和数据的页可以出现在逻辑空间的任意位置

除了允许多个进程共享相同的物理页面之外，根据页面组织内存还提供了许多好处。 其他一些好处见Chap 10。

9.4 页表的结构

9.4.1 层次分页（Hierarchical Paging）

• 把逻辑地址空间分割成多个页表
• 最简单的方式就是两层页表（two-level page table）
• 然后给页表分页

例如，32位的逻辑地址分为20位页号（10+10）和12位页偏移：

也叫作前向映射页表

对于64位也可以分成三级（甚至四级）：

二级页表的查找过程：

9.4.2 哈希页表（Hashed Page Tables）

对于大于32位的地址空间，一种处理方法是用哈希页表，哈希值是虚拟页号，哈希表中的每一项都包含一个链表（用来处理collision），每个元素都包含三个域：

1. 虚拟页号
2. 映射页的帧的值
3. 指向下一项的指针

算法流程：

1. 虚拟页号哈希到哈希表中

2. 虚拟页号和链表中第一个元素的第一个域比较，如果不匹配，就寻找后续的元素

   

一种适用于64位的变体使用clustered page table，这和哈希页表很相似，除了哈希表里能放很多页（比如16页）而不是一页。因此，单个页表项可以保存多个物理页帧的映射。clustered page table对稀疏地址空间尤其有用。在稀疏地址空间内，内存引用是不连续的，并分布在地址空间的各个地方

9.4.3 反向页表（Inverted Page Tables）

通常来说，每个进程都有一个相关联的页表，页表对每一个进程正在使用的页都有一个条目。

坏处：浪费内存

所以我们可以用反向页表，每一个条目对应真实的物理内存页。

尽管反向页表减少了页表的尺寸，却增加了搜索表的时间。为了减轻这个问题，可以用哈希表来减少页表的条目数量。当然，每次访问哈希表又会增加访问内存的次数：一次是哈希表一次是页表（不过TLB可以一定程度上加速）。

反向页表的一个有趣问题涉及共享内存。 使用标准分页，每个进程都有自己的页表，该页表允许将多个虚拟地址映射到同一物理地址。 但这个方法不能用于反向页表， 因为每个物理页面只有一个虚拟页面条目，所以一个物理页面不能具有两个（或多个）共享的虚拟地址。 因此，对于反向页表，在任何给定时间可能只发生一个虚拟地址到共享物理地址的映射。 共享内存的另一个进程的引用将导致页面错误，并将用另一个虚拟地址替换该映射。

9.4.4 Oracle SPARC Solaris

9.5 交换（Swapping）

进程的指令和数据只有在内存里的时候才能操作和执行。然而，进程，或其一部分，可以被暂时交换（swap）出内存，放进后备存储（backing store）中，再被调回内存继续执行。

交换使所有进程的总物理地址空间有可能超过系统的实际物理内存，从而增加了系统中多道程序的程度。

9.5.1 标准交换（Standard Swapping)

标准交换涉及在主存和后备存储之间移动整个进程。

后备存储（backing store）：

• 通常是快速的辅助存储
• 它必须足够大以容纳需要存储和检索的进程的任何部分
• 必须提供对这些内存映像的直接访问

滚出（roll out）、滚入（roll in）：

• 用于基于优先级的调度算法的交换变体；
• 较低优先级的进程被换出，因此可以加载和执行较高优先级的进程

交换时间（swap time）的主要部分是传输时间（transfer time）； 总传输时间与所交换的内存量成正比

系统维护一个就绪队列（ready queue），里面是准备运行，且在硬盘上有内存镜像的进程

Q：交换出去的进程还要交换回原来的物理地址吗？

A：取决于地址绑定的方法

当整个或部分进程交换到后备存储中时，必须将与该进程相关联的数据结构写入后备存储。对于多线程进程，所有每线程（per-thread）数据结构也必须交换。OS还必须为已换出的进程维护元数据，以便在将它们换回内存后可以将其还原。

标准交换的优点是它允许物理内存被超额订购，因此系统可以容纳比实际物理内存更多的进程来存储它们。空闲或大部分空闲的进程是交换的不错选择；然后，可以将已分配给这些非活动进程的任何内存专用于活动进程。如果已换出的非活动进程再次变为活动状态，则必须交换回去。

9.5.2 Swapping with Paging

标准交换用于传统UNIX系统，但不再用于现代OS，因为在内存和后备存储间移动整个进程所需要的时间太太太长了。（一朵奇葩：Solaris仍然使用标准交换，但是仅在可用内存极低的严峻情况下使用。）

修改版的交换应用于很多系统（比如UNIX、Linux和Windows）

• 通常禁用交换
• 若分配的内存量超出阈值，则开始交换
• 一旦内存需求量降到阈值以下就再次禁用

现在swapping这个词一般指标准交换，而paging指带分页的swapping

• page out：把页从内存移到后备存储
• page in：移回来

9.5.3 移动系统中的交换

大多数PC端和服务器的OS都支持交换页，而移动系统一般不支持任何形式的交换。

移动设备通常用闪存（flash memory）作为非易失性的存储，而不是用容量更大的硬盘

这导致的空间限制是移动OS设计者避免交换的一个原因

另一个原因包括闪存容忍的写次数有限，以及移动设备上主存和闪存之间的吞吐量很低。

当可用内存低于某个阈值时，Apple的iOS会要求应用程序自愿放弃分配的内存，而不是使用交换。 只读数据（例如代码）从主存中删除，然后在必要时从闪存中重新加载。 已修改的数据（例如堆栈）永远不会被删除。 然而，任何无法释放足够内存的应用程序都可能会被操作系统终止。

Android采用类似于iOS的策略。 如果没有足够的可用内存，它可能会终止进程。 但是，在终止进程之前，Android会将其应用程序状态写入闪存，以便可以快速重启。

由于这些限制，移动系统的开发人员必须仔细分配和释放内存，以确保应用程序不会使用过多的内存或遭受内存泄漏。

• ← Previous Post
• Next Post →