内存管理基本概念

内存管理模块提纲 基本概念和背景 连续区内存分配 页式内存管理 页表结构 段式内存管理 示例：Intel i386 非连续区内存分配

重温一些计算机组成的知识点 程序必须装入内存后，才能(以进程为单位)被CPU解释、执行 CPU能够直接访问的，只有主存、寄存器 访问主存需要许多时钟周期，或者，需要若干机器周期 Cache 位于主存、寄存器之间

计算机这么处理用户程序 Source Listing Source Listing Create User Library (optional) Librarian C or C++ Compiler Assembly Source File Assembler Relocatable Object Module C or C++ Source File User Library Library Directory Listing Include Files Linker Command File Device Programmer Absolute Object Module Linker Relocatable Object Module Target Development System Link Map

用户程序是如何编译执行的 Compiler: 负责将用户源程序转换成目标程序，通常为二进制代码(binary object code). Linkage editor: 负责将多个目标代码连接产生单个可执行程序(.exe文件）。 Loader：加载程序到内存并准备执行。

汇编器(Assemblers) 把符号指令翻译成二进制指令 把标号(labels)翻译成地址 处理伪指令(pseudo-ops) 区别于编译，它基本上是one-to-one的翻译 产生的目标文件(Object file)添加了 Text段：代码 Data段：初始化了的全程变量 BSS段：未初始化的全程变量

基地址寄存器，界限寄存器 基地址(base)寄存器和界限(limit)寄存器共同划定逻辑地址空间

指令和数据的地址绑定(Binding) 源程序地址通常为符号形式，compiler将其绑定（映射）在可重定位的地址（例如“从本模块开始的第14字节”）；Linkage editor/loader 将其映射为绝对地址，例如“74014”。 指令和数据的地址绑定通常发生在 3 个阶段 编译时绑定：如果代码、数据的存放首地址已知，编译阶段即可确定绝对地址。如果首地址变更，则需要重新编译

指令和数据的地址绑定(续) 装入时绑定：如果代码、数据的存放首地址未知，编译阶段生成可重定位地址，装入时才确定绝对地址 执行时绑定： 如果允许进程在执行时迁移其代码、数据，那么，地址绑定也在执行时进行。需要硬件装置支持其地址映射 (e.g., 基地址寄存器和界限寄存器)

逻辑地址空间 vs. 物理地址空间 区别于物理地址空间的各种逻辑地址空间，是OS得以管理内存的必要条件 逻辑地址 – CPU产生的地址; 也称为虚地址 逻辑地址 – 非物理的各种地址标记包括符号名，包括编译、汇编、连接、装入操作产生的地址 物理地址 – 内存单元接收到的地址。也就是说，“浮现”在地址总线的地址，以二进制形式表达。

存储管理单元 (MMU) 存储管理单元(Memory-Management Unit ，MMU)是CPU内部的硬件装置，其功能是将虚拟地址(或逻辑地址)转换成物理地址 例如一种简单的MMU策略，在用户进程将逻辑地址送往地址总线前，MMU把重定位寄存器(relocation register)的值，加到这个逻辑地址 用户进程只能处理逻辑地址，它无法获取真正的物理地址

基于重定位寄存器的动态重定位(Dynamic relocation)

动态连接(Dynamic Linking) 进程即将用到的代码段，不被预先连接入程序，只有到真正被调用的时刻才连接 需要动态连接库(Linux的.so，或者Windows的.dll)的配合 设计一小段代码，称为存根（stub）。 当真正调用到该段代码时，通过stub定位该段代码，或者从外部装入内存

动态装入(Dynamic Loading) 进程即将用到的子程序，不被预先装入，只有到真正被调用的时刻才装入内存 这样，进程本次运行中没有调用的子程序，就不会被装入内存 更有效地利用了内存空间 不需要操作系统特别的支持。

交换(Swapping) 进程映像暂时传输至后备存储空间保存(换出，swap out)，需要(执行)时再装入内存 (换入，swap in)。称为“交换” 后备存储空间 快速； 大容量； 直接访问机制(direct access) 交换操作结合CPU调度算法，使得及时换出低优先级的进程，让高优先级的进程装入、执行

图示：交换过程

交换(续) 大部分交换时间用于传输。传输时间与交换数据量成正比 交换的思想或者变种，频频见诸于UNIX、 Linux、Windows等 系统只要保障就绪队列里的就绪进程全部驻留内存。其它进程映像可以被换出

例题 在存储管理中，覆盖和交换技术所要解决的是什么问题？各有什么特点？

例题 答：覆盖技术和交换技术是两种扩充内存的技术。覆盖技术主要用于早期的操作系统中，而交换技术在现代操作系统中仍有较强的生命力。 覆盖：一个程序不需要把所有的指令和数据都装入内存，而是将程序划分为若干个功能相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区。这样使用户感觉到内存扩大了，从而达到内存扩充的目的。要求程序员提供一个清晰的覆盖结构，这对程序员的要求较高。 交换: 先将内存某部分的程序或数据写入外存交换区，然后再从外存交换区中调出指定的程序或数据到内存中来并让其执行的一种内存扩充技术。交换完全由操作系统实现，它不要求程序员做特殊的工作，整个过程对程序员是透明的。交换主要是在进程或作业之间进行，而覆盖则主要在同一个作业或同一个进程内进行。

存储管理基本思想 y = f(x) x 为逻辑地址，y为物理地址 存储管理算法的评估和比较 硬件支持，Hardware Support 性能，Performance 碎片，Fragmentation 重定位，Relocation 交换，Swapping 内存共享，Memory sharing 内存保护，Memory protection

连续区内存分配 memory 把主存划分成 2 个分区(partitions) 操作系统占 1 个分区。通常驻留主存的低端。中断矢量也在低端 用户进程占另 1 个分区，通常在主存的高端 Low address OS process 1 process 3 process 2 High address

连续区内存分配(续) 运用重定位寄存器(Relocation registers)防止用户进程访问其它进程的空间，篡改操作系统的代码、数据 基地址寄存器(Base register) 保存了进程物理地址的首地址 界限寄存器(Limit register) 保存了逻辑地址的地址范围。任一个逻辑地址必须小于界限寄存器的值 MMU能够动态地映射每一个地址

利用base和limit寄存器进行地址映射、地址保护

多重分区(Multiple-partition)连续区分配 孔（Hole） – 有效可分配的空闲内存块 多个长度不等的holes散布在内存各区域 当一个进程申请进入主存时，OS选出一个hole，其长度足够容纳进程的映像 OS维护一些管理信息，包括： 已经分配的分区 可分配的分区(hole)

多重分区连续区分配(续) OS OS OS OS process 5 process 5 process 5 process 5

如何在一串holes中找出一个能存储 n 个单元 动态存储分配问题： 如何在一串holes中找出一个能存储 n 个单元 First-fit：找到第1个足够大的hole Best-fit 在所有足够大的holes里面，找出最小的一个hole 必须寻找整个列表 留下一堆“最小”holes

如何找Hole？ Worst-fit 在所有足够大的holes里面，找出最小的一个hole 必须寻找整个列表 留下一堆“最大”holes

例题 1. 可变分区存储管理系统中，若采用最佳适应分配算法，“空闲区表”中的空闲区可按（ ）顺序排列。 A. 长度递增 B. 长度递减 C. 地址递增 D. 地址递减

例题 【答案】A 【解析】最佳适应算法要求每次都分配给用户进程能够满足其要求的空闲区中最小的空闲区，所以为了提高算法效率，我们把所有的空闲区，按其大小以递增的顺序形成一空闲分区链。这样，第一个找到的满足要求的空闲区，必然是符合要求中最小的。所以本题的答案是A。

碎片(Fragmentation) External Fragmentation – 这些内存块加起来能够满足一个请求，但是由于不连续(中间有断层)，不能用来连续区分配 Internal Fragmentation – 分出去的分区略大于请求的内存长度。这个余下的小内存块属于该分区，但是无法利用

碎片(续) 紧缩(compaction)操作减少external fragmentation 重排内存块，使所有空闲内存连续排列，合并成一块大的内存块 前提条件 代码、数据可重定位； 重定位可以在运行时操作

END