内存管理

---

内存管理

• objects
  to provide a detailed description of various ways of organizing memory hardware
  to dicuss various memory-management techniques

背景

• 内存由很大的一组字或字节组成，每个字或字节都有它们自己的地址
• 内存即主存、分为两大部分：系统区和用户区
• 功能
  存储空间的分配和回收
  地址变换
  存储保护
  存储扩充

基本硬件

cpu能直接访问的存储器有主存、高速缓存和寄存器
main memory, cache, the registers

地址绑定

• 用户程序的执行步骤：compile, link, load

program execution

• 将指令和数据绑定到内存地址有以下几种情况：
  compile time
  load time
  execution time
• 绝对装入方式：

编译时产生绝对地址的目标代码，绝对装入程序按照装入模块中的地址将程序及数据装入内存，不需对地址进行变换
程序中使用的绝对地址可以在编译时给出，也可以由程序员直接赋予
特点：不方便，适合单程序运行

• 可重定位装入方式

relocation

编译时产生相对地址的目标代码，由装入程序根据内存当时的实际使用情况，将装入模块装入内存的适当地方。
加载时：如果在编译时不知道进程在内存的驻留位置，则编译程序必须生成可重定位代码。绑定在加载时进行。

• 动态运行时装入方式

bind in execution

在将装入模块装入内存时不进行地址变换，在程序执行过程中进行地址变换

如果进程在执行时可以在内存中移动，则地址绑定要延时到执行时

逻辑地址空间和物理地址空间

• 逻辑地址：
  由cpu产生的地址，用户编程时所使用的地址，又称相对地址、虚拟地址，其集合称逻辑地址空间、地址空间
• 物理地址：内存单元看到的地址，内存中的地址，又称绝对地址、实地址，其集合称物理地址空间、主存空间
• 内存管理单元 MMU
  运行时把虚拟地址映射到物理地址的设备
• 地址变换
  将逻辑地址转换成物理地址，又称地址映射、重定位，分为两类，静态～、动态～
• 静态地址变换
  地址变换在程序装入时一次完成，以后不再改变
  特点：不需要硬件支持，但程序运行时不能在内存中移动，程序需要连续存储空间，难以共享
• 动态地址变换
  在程序执行过程中，每次访问内存之前要将要访问程序地址转换成内存地址
  特点：需要硬件支持，不需连续空间，可以实现虚拟存储

动态加载

采用动态加载时，子程序只用调用时才会被加载
优点：不用的子程序不会被加载

动态链接

链接被延迟到执行期间

程序的链接

• 功能
  将经过编译或汇编后得到的目标模块以及所需的库函数装配成一个完整的装入模块
• 静态链接
  程序运行之前，将各目标模块及其所需的库函数装配成一个完整的装入模块
• 装入时动态链接
  源程序编译后所得到的目标模块在装入内存时边装入边链接
  特点：便于软件版本的修改和更新，便于目标模块的共享
• 运行时动态链接
  在执行过程中，若发现一个被调用模块尚未装入内存，由os去找到该模块，将它装入内存并链接到调用者模块上
  特点：加快了程序装入，节省了内存

覆盖与交换技术

• 覆盖与交换技术是在多道程序环境下用来扩充内存的方法
• 覆盖技术
  把一个大程序划分为一系列覆盖，每个覆盖是一个相对独立的程序单位，把程序执行时不要求同时装入内存的覆盖组成一组，称为覆盖段，将一个覆盖段分配到同一个存储区，这个存储区称为覆盖区，覆盖区的大小由覆盖段中最大的覆盖来确定

覆盖

• 交换技术
  将内存中暂时不用的程序及数据换出到外存中，再将已具备运行条件的进程或进程所需的程序或数据从外存换入内存中
• 交换空间的管理
  交换空间设置在外存交换区中，交换空间管理的主要目标是提高进程换入/换出速度
  采用连续分配方式，使用与动态分区分配类似的数据结构和分配回收算法
• 进程的换出与换入
  换出：先选择换出进程（阻塞、优先级低、驻留时间长），再申请兑换空间，然后启动磁盘写，若成功则可释放其内存空间并修改数据结构
  换入：先选择换入进程（就绪、优先级、换出时间长），再申请内存空间，然后启动磁盘读

交换

• 覆盖vs交换

连续内存分配与回收

两个区域：一个驻留操作系统（通常位于内存低端），一个用于用户进程（通常位于地址高端）

内存映射和保护

内存分配

分区存储管理是多道程序系统采用的最简单的方法，它把系统的内存划分成若干大小不等的区域，操作系统占一个区，其他区域由并发进程共享，每个进程占一个区域

• 固定分区
• 动态分区管理／可变分区存储管理
  基本思想：根据作业大小动态的建立分区，并使分区的大小正好适应作业的需求。因此，分区的大小和数目都可变
  常用的数据结构：空闲分区表，空闲分区链

空闲分区表 空闲分区链

• 分区分配算法
• 首次适应算法
  进行内存分配时，从空闲分区表中按地址递增的顺序开始查找，直到找到第一个能满足其大小需求的空闲区，然后按照作业大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍然留在空闲分区表中
  特点：优先使用内存低地址端，高地址端有大空闲区，但低地址端有许多小空闲区时会增加查找开销
• 循环首次适应算法／下次适应算法
  进行内存分配时，从空闲分区表上次查找到的空闲去的下一个空闲区中按地址递增的顺序开始查找，直到找到第一个能满足其大小需求的空闲区，然后按照作业大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍然留在空闲分区表中
  特点：使存储空间的利用更加均衡，但会使系统缺乏大的空闲分区
• 最佳适应算法
  进行内存分配时，从空闲分区表中按容量大小递增的顺序开始查找，直到找到第一个能满足其大小需求的空闲区，然后按照作业大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍然留在空闲分区表中
  特点：保留了很大的空闲区，但分割后的剩余空闲区很小
• 最坏适应算法
  进行内存分配时，从空闲分区表中按容量大小递减的顺序开始查找，直到找到第一个能满足其大小需求的空闲区，然后按照作业大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍然留在空闲分区表中
  特点：分割后剩余空闲区较大，但当大作业到来时，其存储空间的申请往往得不到满足

内存分配算法

分区回收

• 回收分区时，应将空闲区插入到适当位置
• 回收分区r上邻接一个空闲分区：合并二者
• 回收分区r下邻接一个空闲分区：合并二者
• 回收分区r上面、下面各邻接一个空闲分区：合并三者
• 回收分区r不与任何空闲分区临接：增加新表项

可重定位分区分配

分页

基本概念

• 基本方法：将物理内存分为固定大小的块，称为帧，将逻辑地址分为同样大小的块，称为页（页内碎片
• 逻辑地址结构：页表项＋页内偏移
• 页表：为每个进程创建一张，记录页面在内存中对应物理块的数据结构，一般放在内存中
• 存储分块表：也称为帧表，记录内存中各物理块使用情况及未分配物理块总数（位示图，空闲存储块链）
• 存储空间的分配与回收
  页面分配：计算进程所需页面数，然后在请求表中登记进程号、请求页面数等。如存储分块表中有足够的空闲块可供进程使用，则在系统中取得页表始址，并在页表中登记页号及其对应的物理块号。否则无法分配。
  页面回收：将存储分块表中相应的物理块改为未分配，或将回收块加入到空闲存储块链中，并释放页表，修改请求表中的页表始址及状态。

硬件支持

• 页表寄存器：存放页表在内存中的起始地址和页表的长度，未执行时放在PCB中
• 分页地址变换

分页地址变换

设页面大小为1K字节，作业的0、1、2页分别存放在第2、3、8块中。则逻辑地址2500的页号及页内地址为：2500/1024=2（页号）；2500 %1024＝452（页内地址）；
查页表可知第2页对应的物理块号为8；
将块号8与页内地址452拼接得到物理地址为：8×1024＋452＝8644。

• 具有快表的分页地址变换
  地址变换机构自动将页号与快表中的所有页号进行并行比较，若其中有与此匹配的页号，则取出该页对应的块号，与页内地址拼接形成物理地址。
  若页号不在快表中，则再到主存页表中取出物理块号，与页内地址拼接形成物理地址。
  同时还应将这次所查到的页表项存入快表中，若快表已满，则必须按某种原则淘汰出一个表项以腾出位置。

具有快表的分页地址变换

存储保护

• 地址越界保护：页表长度与逻辑地址中的页号比较
• 存取控制保护：在页表中增加保护位，与帧关联

共享页

• 使多个进程页表相指向同一个物理块
• 如果代码是可重入代码（纯代码），则可以共享

共享页

页表结构

• 分级页表
• 哈西页表
• 反向页表

分级页表

两级页表：power(2,20)

对64位地址不合适

64位分级页表

哈西页表

反向页表

分段

• 考虑程序段的逻辑完整性