多级存储器结构

计算机存储系统的设计主要考虑三个问题：容量、速度和成本。

程序的装入和链接

程序的装入

1. 绝对装入
   编译程序将目标模块装入绝对地址。只适合单道程序环境。
2. 静态可重定位装入
   在装入一个作业时，把作业中的指令地址全部转换为绝对地址,在作业执行过程中就无须再进行地址转换工作。
3. 动态运行时装入
   在程序执行过程中，在CPU访问内存之前,将要访问的程序或数据地址转换成内存地址. 动态重定位依靠硬件地址变换机构完成。
   

程序链接

1. 静态链接
   程序运行之前，先将各目标模块和所需的库函数。连接成一个完整的装配模块。以后不再拆开。
2. 装入时动态链接
   用户源程序编译后得到的一组目标模块，边装入内存边链接。
3. 运行时动态链接
   需要该模块时候才进行链接。

指令和地址的绑定

指令和数据绑定到内存地址可以在3个不同的阶段发生。

• 编译时期：如果内存位置已知，可生成绝对代码；如果开始位置改变，需要重新编译代码
• 装入时期: 如果存储位置在编译时不知道，则必须生成可重定位代码
• 执行时期: 如果进程在执行时可以在内存中移动，则地址绑定要延迟到运行时。需要硬件对地址映射的支持，例如基址和限长寄存器

连续分配方式

• 单一分区分配（单用户但任务）
• 多分区分配
  • 固定分区分配
  • 可变分区/动态分区
  • 动态可重定位分区

单一分区分配

内存分成两部分:
OS区
用户区
用户区只能容纳一道作业

固定分区分配

• 固定分区是在作业装入之前，内存就被划分成若干个固定大小的连续分区。
• 划分工作可以由系统管理员完成，也可以由操作系统实现。
• 一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，又称为静态分区。

划分分区的方法如下：

• 分区大小相等：只适用于多个大小相同程序的并发执行，缺乏灵活性。
• 分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。

一般将内存的用户区域划分成大小不等的分区，可适应不同大小的作业需要。
系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志

优点：易于实现，开销小。
缺点：
分区大小固定: 内碎片
分区总数固定: 限制并发执行的进程数目

动态（可变）分区分配

分区的划分是动态的,不是预先确定的。当一个进程到来的时候，它将从一个足够容纳它的分区中分配内存。分配的数据结构有空闲分区表和空闲分区链。

可变分区分配算法

分区分配算法：寻找某个空闲分区，若大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区分配的先后次序通常是从内存低端到高端。
分区释放算法：需要将相邻的空闲分区合并成一个空闲分区。(这时要解决的问题是：合并条件的判断)

首次适应（First Fit）

从空闲分区表的第一个表目开始查找，把找到的第一个满足要求的空闲区分配给作业，目的在于减少查找时间。通常将空闲分区表（空闲区链）中的空闲分区按地址由低到高进行排序。

特点：
分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。
随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。

循环首次适应算法(Next Fit)

是首次适应算法的变种。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到的空闲区的下一个空闲区开始查找（并采用循环查找的方式），直到找到第一个能满足要求的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。

特点：
算法的分配和释放的时间性能较好，使空闲分区分布得更均匀
较大的空闲分区不易保留

最佳适应算法（Best Fit）

从全部空闲区中找出能满足作业要求的、且最小的空闲分区.
能使碎片尽量小
为提高查找效率，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配
特点：
从个别来看，外碎片较小，但从整体来看，会形成较多无法利用的碎片。
较大的空闲分区可以被保留。

动态重定位分区分配

动态分区的碎片问题:在系统不断地分配和回收中，必定会出现一些不连续的小的空闲区，称为外碎片。虽然可能所有碎片的总和超过某一个作业的要求，但是由于不连续而无法分配。
解决碎片的方法是拼接（或称紧凑），即向一个方向（例如向低地址端）移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。
分区的拼接技术，一方面要求能够对作业进行重定位，另一方面系统在拼接时要耗费较多的时间。

实现紧凑的技术必须获得硬件支持。
只有具有动态重定位硬件机构的计算机系统，才有可能采用动态重定位可变分区管理技术，系统的硬件包括重定位寄存器和加法器。

离散分配方式

连续分配容易造成很多碎片，虽然可以通过紧凑的算法来将碎片拼接成可用的大块空间，但必须付出很大的开销。如果允许一个进程直接分散的装入很多不相邻的分区，则无需紧凑，即离散分配方式。如果离散分配的基本单位是页，称为分页储存管理方式；如果离散分配及基本单位是段，称为分段存储管理方式。

分页储存管理方式

分页存储管理是解决存储碎片的一种方法。
动态重定位是解决存储碎片问题的一种途径，但要移动大量信息从而浪费处理机时间,代价比较高,这是因为这种分配要求把作业必须安置在一连续存储区内的缘故,而分页存储管理正是要避开这种连续性要求。

物理内存分成大小固定的块,称为物理块或页框。逻辑内存也分为固定大小的块，叫做页。
页面大小应该适中，页面太小虽然可以减少页内碎片但是会导致页表过长，占用大量内存，降低页面换进换出的效率；页面较大页内碎片又会增大。通常是512B~8KB。

运行一个有N页大小的程序，需要找到N个空的页框装入程序。建立一个页表，把逻辑地址转换为物理地址。

地址结构

分页地址中的地址结构如下：

程序经过编译链接后形成逻辑地址，对某特定机器其地址结构是一定的。

页表

实现从页号到物理块号的映射

基本的地址变换机构

• 实现从逻辑地址到物理地址的转换:将用户程序中的页号变换成内存中的物理块号
• 地址变换机构：
  页表寄存器
  有效地址寄存器（逻辑地址寄存器）
  物理地址寄存器
  页表
  PCB中增加存放页表始址和页表长度的项

地址变换过程

基本的地址变换

• ①按页的大小分离出页号和位移量，放入有效地址寄存器中
• ②将页号与页表长度进行比较，如果页号大于页表长度，越界中断；
• ③以页号为索引查找页表:将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号；
• ④将该物理块号装入物理地址寄存器的高址部分；
• ⑤将有效地址寄存器中的位移量直接复制到物理地址寄存器的低位部分，从而形成内存地址。
  

页式存储

虚地址以十进制数给出
页号＝虚地址％页大小
位移量＝虚地址 mod 页大小
以页号查页表，得到对应页装入内存的块号
内存地址＝块号×页大小＋位移量

两级和多级页表

将页表进行分页,并进行编号
页表分页存放在不同的物理块中
外层页表（页表目录），即第一级页表，指出页表分页的物理地址
第二级页表（即页表分页），指出每个页对应的物理块号

多级页表的引入，使逻辑地址到物理地址的变换时间增加了许多:二级页表需三次访存,三级页表需四次访存,四级页表需五次访存

纯分页的特点

优点：
没有外碎片，每个内碎片不超过页大小。
一个程序不必连续存放。
缺点：程序全部装入内存。

分段式存储

分段内存管理机制是从用户观点出发的，即为了方便用户

地址变换过程

系统将逻辑地址中的段号S与段表长度TL进行比较。若 S≥TL，访问越界；
若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址；
然后再检查段内地址d是否超过该段的段长SL。若超过，即 d≥SL，同样发出越界中断信号；
若未越界，则将该段的基址与段内地址d相加，得到要访问的内存物理地址。

分段的特点

程序通过分段(segmentation)划分为多个模块，如代码段、数据段、共享段。
可以分别编写和编译
可以针对不同类型的段采取不同的保护
可以按段为单位来进行共享，包括通过动态链接进行代码共享
优点：
没有内碎片，外碎片可以通过内存紧缩来消除。
便于改变进程占用空间的大小。
缺点：
进程全部装入内存。

分段分页比较

段页式

分页和分段存储管理方式都各有其优缺点。
结合两种存储管理方式,则形成一种新的存储管理方式——段页式。
分页系统:提高内存利用率
分段系统:满足用户需要