第四章:存储器管理

存储器的层次结构

多层结构的存储系统

• 存储器的多层结构
  • CPU寄存器
  • 主存
  • 辅存
• 可执行存储器
  • 寄存器和主存的总称
  • 访问速度快，进程可以在很少的时钟周期内用一条load或store指令完成存取。

主存储器与寄存器

高速缓存和磁盘缓存

程序的装入和链接

步骤

• 编译
  • 源程序 ->目标模块（Object modules）--------Compiler
    • 由编译程序对用户源程序进行编译，形成若干个目标模块
• 链接
  • 一组目标模块 ->装入模块 （Load Module）----------Linker
    • 由链接程序将编译后形成的一组目标模板以及它们所需要的库函数链接在一起，形成一个完整的装入模块
• 装入
  • 装入模块 ->内存 --------Loader
    • 由装入程序将装入模块装入内存

程序的装入

• 绝对装入方式
  • 在编译时，如果知道程序将驻留在内存中指定的位置。编译程序将产生绝对地址的目标代码。
• 可重定位装入方式
  • 在可执行文件中，列出各个需要重定位的地址单元和相对地址值。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换(一般在装入内存时由软件完成)。
  • 优点：不需硬件支持，可以装入有限多道程序。
  • 缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。
• 动态运行时的装入方式
  • 动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的逻辑地址转换为物理地址，而是把这种地址转换推迟到程序真正要执行时才进行
  • 优点：
    • OS可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。
    • 能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。
  • 缺点：需要硬件支持，OS实现较复杂。
  • 它是虚拟存储的基础。

程序的链接

• 静态链接方式(lib)
• 装入时动态链接
• 运行时动态链接(dll)

连续分配存储管理方式

连续分配

• 单一连续分配(DOS)
• 固定分区分配(浪费很多空间)
• 动态分区分配

地址映射和存储保护措施

• 基址寄存器：程序的最小物理地址
• 界限寄存器：程序的逻辑地址范围
• 物理地址 = 逻辑地址 + 基址

内碎片：占用分区之内未被利用的空间

外碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）

把内存划分为若干个固定大小的连续分区。固定式分区又称为静态分区。

• 分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。
• 分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。
• 优点：无外碎片、易实现、开销小。
• 缺点：
  • 存在内碎片，造成浪费
  • 分区总数固定，限制了并发执行的程序数目。
  • 通用Os很少采用，部分控制系统中采用

动态创建分区：指在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。可变式分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分。

• 基于顺序搜索的动态分区分配算法
  • 首次适应算法（first fit,FF）
    • 顺序找，找到一个满足的就分配，但是可能存在浪费
    • 这种方法目的在于减少查找时间。
    • 空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序
  • 循环首次适应算法（next fit，NF）
    • 相对上面那种，不是顺序，类似哈希算法中左右交叉排序
    • 空闲分区分布得更均匀，查找开销小
    • 从上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。
  • 最佳适应算法（best fit，BF）
    • 找到最合适的，但是大区域的访问次数减少
    • 这种方法能使外碎片尽量小。
    • 空闲分区表（空闲区链）中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。
  • 最坏适应算法（worst fit，WF）
    • 相对于最好而言，找最大的区域下手，导致最大的区域可能很少，也造成许多碎片
    • 空闲分区按大小由大到小排序
• 基于索引搜索的动态分区分配算法
  • 快速适应算法（quick fit）
  • 伙伴系统（buddy system）
  • 哈希算法
• 动态可重定位分区分配
  • 紧凑
  • 动态重定位
    • 动态运行时装入，地址转化在指令执行时进行，需获得硬件地址变换机制的支持
    • 内存地址=相对地址+起始地址
  • 动态重定位分区分配算法
    • 1、在某个分区被释放后立即进行紧凑，系统总是只有一个连续的分区而无碎片，此法很花费机时。
    • 2、当“请求分配模块”找不到足够大的自由分区分给用户时再进行紧凑，这样紧缩的次数比上种方法少得多，但管理复杂。采用此法的动态重定位分区分配算法框图如下：
• 优点：没有内碎片。
• 缺点：外碎片。

对换（了解）

系统把所有的作业放在外存，每次只调用一个作业进入内存运行，当时间片用完时，将它调至外存后备队列上等待，在从后备队列调入另一个作业进入内存运行。

基本分页存储管理方式

分页存储管理的基本方式

• 页面
  • 将一个进程的逻辑地址空间分成若干个大小相等的片
• 页框（frame）
  • 内存空间分成与页面相同大小的存储块
• 由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”
• 地址结构
  • 页号P+位移量W(0-31)
• 页表
  • 在分页系统中，允许将进程的各个页离散地存储在内存在内存的任一物理块中，为保证进程仍然能够正确地运行，即能在内存中找到每一个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表
  • 页表的作用是实现从页面号到物理块号的地址映射

地址变换机构

• 基本的地址变换机构
  • 要访问两次内存
  • 页表大都驻留在内存中
  • 为了实现地址变换功能，在系统中设置页表寄存器（PTR），用来存放页表的始址和页表的长度。
  • 在进程未执行时，每个进程对应的页表的始址和长度存放在进程的PCB中，当该进程被调度时，就将它们装入页表寄存器。
• 具有快表的地址变换机构
  • 提高了效率，此处会有计算题
  • 如果页表存放在内存中，则每次访问内存时，都要先访问内存中的页表，然后根据所形成的物理地址再访问内存。这样CPU存一个数据必须访问两次内存，从而使计算机的处理速度降低了1/2。
  • 为了提高地址变换的速度，在地址变换机构中增设了一个具有并行查询功能的特殊的高速缓冲存储器，称为“联想存储器”或“快表”，用以存放当前访问的那些页表项。
  • 地址变换过程为：
    • 1、CPU给出有效地址
    • 2、地址变换机构自动地将页号送入高速缓存，确定所需要的页是否在快表中。
    • 3、若是，则直接读出该页所对应的物理块号，送入物理地址寄存器；
    • 4、若快表中未找到对应的页表项，则需再访问内存中的页表
    • 5、找到后，把从页表中读出的页表项存入快表中的一个寄存器单元中，以取代一个旧的页表项。

两级和多级页表

• 主要是有的时候页表太多了，要化简
• 格式：外层页号P1+外层页内地址P2+页内地址d
• 基本方法：将页表进行分页，每个页面的大小与内存物理块的大小相同，并为它们进行编号，可以离散地将各个页面分别存放在不同的物理块中。

反置页表

• 反置页表为每一个物理块（页框）设置一个页表项，并按物理块排序，其内容则是页号和其所属进程的标识。

优点：

• 没有外碎片，每个内碎片不超过页大小。
• 一个程序不必连续存放。
• 便于改变程序占用空间的大小。即随着程序运行而动态生成的数据增多，地址空间可相应增长。

缺点：程序全部装入内存。

分段存储管理方式

引入

• 方便编程
• 信息共享
• 动态增长
• 动态链接

在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段是一组完整的逻辑信息，每个段都有自己的名字，都是从零开始编址的一段连续的地址空间，各段长度是不等的。

内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定

分段系统的基本原理

• 分段
  • 格式：段号+段内地址
• 段表
  • 段表实现了从逻辑段到物理内存区的映射。
• 地址变换机构

和分页的区别

• 页是信息的物理单位
• 页的大小固定且由系统固定
• 分页的用户程序地址空间是一维的
• 通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。
• 分页是系统管理的需要，分段是用户应用的需要。一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。

信息共享

• 这是分段最重要的优点

段页式存储管理方式

• 基本原理
  • 格式：段号（S）+段内页号（P）+页内地址（W）
• 地址变换过程
  • 需要三次访问过程
• 在段页式系统中，为了获得一条指令或数据，需三次访问内存：第一次访问内存中的段表，从中取得页表始址；第二次访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正根据所得的物理地址取出指令或数据。

第四章 存储器管理